Patent Publication Number: US-11663383-B2

Title: Method and system for hierarchical circuit simulation using parallel processing

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation-in-part application of U.S. patent application Ser. No. 16/428,703, filed May 31, 2019, which claims priority to U.S. Provisional Application Ser. No. 62/679,645, filed Jun. 1, 2018, entitled “Method and System for Hierarchical and Parallel Circuit Simulation,” each of which is hereby incorporated by reference in its entirety. 
    
    
     FIELD OF THE INVENTION 
     The various embodiments described in this document relate in general to computer aided design of very large-scale integrated circuits, and more specifically to method and system for hierarchical circuit simulation using parallel processing. 
     BACKGROUND 
     The increasing density and complexity of integrated circuits place higher and higher demand on the speed and capacity of computer systems performing circuit simulations for computer aided circuit design. Conventional circuit simulators, such as SPICE (Simulation Program with Integrated Circuit Emphasis) or SPICE 2, have been employed as a computer-aided design tool to analyze electromagnetic propagation behavior on circuits. Although SPICE or SPICE 2 could be used to simulate a microelectronic circuit, including the logic devices and the interconnect paths, a complete simulation using SPICE or SPICE 2 has become extremely time consuming, and may exceed the storage and processing capabilities of the computer system used to run the simulation, as the sizes and complexities of microelectronic circuits continue to increase. 
     SUMMARY 
     In some embodiments, a method to simulate a circuit is performed using one or more computer systems. The method comprises determining a top circuit and a plurality of sub-circuit instances (SCIs) from a netlist of the circuit, the plurality of SCIs forming a hierarchy under the top circuit such that each sub-circuit instance (SCI) of the plurality of SCIs is a parent SCI of one or more SCIs lower in the hierarchy and/or a child SCI of either the top circuit or another SCI higher in the hierarchy, each of the plurality of SCIs having external ports, at least one of the plurality of SCIs including internal nets. 
     The method further comprises, during an iteration round of one or more iteration rounds, obtaining respective circuit equation parameters for each respective SCI of the plurality of SCIs and storing at least a first portion of the circuit equation parameters for the respective SCI in electronic memory, wherein circuit equation parameters for each respective parent SCI among the plurality of SCIs are obtained after circuit equation parameters for each respective child SCI of the respective parent SCI are obtained, and wherein some of the circuit equation parameters for the respective parent SCI are obtained using a second portion of the circuit equation parameters for the respective child SCI. 
     The method further comprises, during the iteration round, determining signal values in the top circuit, the signal values including signal values at external ports of the top circuit and signal values at external ports of one or more child SCIs of the top circuit, and determining respective signal values of each respective SCI of the plurality of SCIs in the hierarchy in a top-down process. In some embodiments, in the top-down process, for any specific child SCI having internal nets, signal values at internal nets of the specific child SCI are obtained using one or more signal values of a parent SCI of the specific child SCI and a first portion of the circuit equation parameters for the specific child SCI, the one or more signal values of the parent SCI of the specific child SCI corresponding to one or more signal values at external ports of the specific child SCI. 
     In some embodiments, obtaining respective circuit equation parameters for each respective SCI of the plurality of SCIs comprises identifying a set of SCIs having a common circuit topology, where circuit equation parameters for each child SCI of each of the set of SCIs have been obtained during the iteration round. In some embodiments, some circuit equation parameters for each particular SCI of the set of SCIs are obtained using circuit equation parameters for each child SCI of the particular SCI, and remaining circuit equation parameters of the particular SCI are obtained by executing a same set of computer program instructions to corresponding to the common circuit topology. The subset of the set of SCIs includes one, some, or all of the SCIs in the set of SCIs. 
     In some embodiments, executing a same set of computer program instructions to obtain remaining circuit equation parameters for each subset of the set of SCIs having the common circuit topology comprises executing a same set of computer program instructions once to obtain remaining circuit equation parameters for each of two or more SCIs of the set of SCIs in parallel. 
     In some embodiments, determining respective signal values of each respective SCI of the plurality of SCIs in the hierarchy comprises identifying a set of SCIs having a common circuit topology after signal values for a parent SCI of each of the set of SCIs having been obtained during the iteration round, and executing a same set of computer program instructions to compute signal values at internal nets of each SCI of the set of SCIs having the common circuit topology. 
     In some embodiments, executing a same set of computer program instructions to compute signal values at internal nets of each SCI of the set of SCIs having the common circuit topology comprises executing a same set of computer program instructions once to compute signal values at internal nets of each of two or more SCIs of the set of SCIs in parallel. 
     In some embodiments, obtaining respective circuit equation parameters for each respective SCI of the plurality of SCIs comprises obtaining first circuit equation parameters for a first SCI and obtaining second circuit equation parameters for a second SCI, the first circuit equation parameters having a first value precision and the second circuit equation parameters having a second value precision that is different from the first value precision. 
     In some embodiments, the first SCI is a child SCI of the second SCI, and obtaining the second circuit equation parameters for the second SCI comprises converting a second portion of the first circuit equation parameters for the first SCI from the first value precision to the second value precision before using the second portion of the first circuit equation parameters to obtain some of the second circuit equation parameters for the second SCI. 
     In some embodiments, signal values at internal nets of the first SCI are determined with a first value precision and signal values at internal nets of the second SCI are determined with a second value precision that is different from the first value precision. In some embodiments, determining respective signal values of each respective SCI of the plurality of SCIs in the hierarchy comprises converting and one or more signal values of the second SCI from the second value precision to the first value precision before using the one or more signals values of the second SCI to determine the signal values at the internal nets of the first SCI, the one or more signal values of the second SCI corresponding to one or more signal values at external ports of the first SCI. 
     In some embodiments, a system to simulate a circuit comprises processors. At least one processor among the processors is configured to determine a top circuit and a plurality of sub-circuit instances (SCIs) from a netlist of the circuit, the plurality of SCIs forming a hierarchy under the top circuit such that each sub-circuit instance (SCI) of the plurality of SCIs is a parent SCI of one or more SCIs lower in the hierarchy and/or a child SCI of either the top circuit or another SCI higher in the hierarchy, each of the plurality of SCIs having external ports, at least one of the plurality of SCIs including internal nets. 
     At least some of the processors is configured to obtain, during an iteration round of one or more iteration rounds, respective circuit equation parameters for each respective SCI of the plurality of SCIs in a bottom-up process, where circuit equation parameters for each respective parent SCI among the plurality of SCIs are obtained after circuit equation parameters for each respective child SCI of the respective parent SCI, and wherein at least some of the circuit equation parameters for the respective parent SCI are obtained using a second portion of the circuit equation parameters for the respective child SCI. 
     A first processor among the processors is configured to obtain, during the iteration round, first circuit equation parameters for a first SCI of the plurality of SCIs during the iteration round. A second processor among the processors is configured to obtain second circuit equation parameters for a second SCI of the plurality of SCIs during the iteration round, the second SCI being a parent SCI of the first SCI. The first processor is further configured to pass at least a second portion of the first circuit equation parameters to the second processor. The second processor is further configured to use the second portion of the first circuit equation parameters to obtain at least some of the second circuit equation parameters for the second SCI. 
     In some embodiments, at least one processor among the one or more processors is configured determine, during the iteration round, signal values in the top circuit, the signal values including signal values at external ports of the top circuit and signal values at external ports of one or more child SCIs of the top circuit. At least some of the processors is configured to determine, during the iteration round, respective signal values of each respective SCI of the plurality of SCIs in a top down process, where, for a specific child SCI having internal nets, signal values at internal nets of the specific child SCI are obtained using one or more signal values of a parent SCI of the specific child SCI and a first portion of the circuit equation parameters for the specific child SCI, the one or more signal values of the parent SCI of the specific child SCI corresponding to one or more signal values at external ports of the specific child SC. 
     A third processor is configured to determine, during the iteration round, first signal values of the first SCI. A fourth processor is configured to determine, during the iteration round, second signal values of the second SCI, and to pass at least one or more of the second signal values to the third processor, the one or more of the second signal values corresponding to one or more signal values at external ports of the first SC. The third processor is further configured to determine at least some of the first signal values of the first SCI using the one or more of the second signal values and a second portion of the first circuit equation parameters. 
     Thus, in the bottom-up process, intermediate results of lower-level calculations are incorporated into higher-level calculations until the circuit equation for the top circuit is generated. In the top-down process, signal values from higher-level calculations are used in the lower-level calculations until the signal values of all the leaf SCIs are determined. The calculations related to the individual SCIs can be distributed among multiple processors of one or more computers. The calculation of any SCI can be simplified/skipped when the signals of the SCI change slowly or remain constant between previous consecutive iteration rounds. The method according to some embodiments enables simulation of very large circuit hierarchically at the same SPICE accuracy using multiple processors/computers. The method also has capabilities to speed up like FAST-SPICE while maintaining SPICE accuracy. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present embodiments are illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements, and in which: 
         FIG.  1 A  is a block diagram of a computer system that can be configured to carry out, either individually or in conjunction with one or more other similarly configured computer systems, a method of simulating a hierarchical circuit according to some embodiments; 
         FIG.  1 B  is a block diagram illustrating multiple computer systems that can be used to jointly carry out a method of simulating a circuit according to some embodiments; 
         FIG.  2 A  illustrates a circuit  200  including primitive devices and subcircuit instances (SCIs), according to some embodiments; 
         FIG.  2 B  illustrates an example of a netlist for a circuit, according to some embodiments; 
         FIG.  2 C  illustrates an example of a wave form of an input signal changing with time according to some embodiments. 
         FIG.  2 D  illustrates an example of a simulated output signal changing with time according to some embodiments. 
         FIGS.  3 A to  3 D  are flowcharts illustrating a method  300  of simulating a hierarchical circuit according to some embodiments; 
         FIG.  4    illustrates a hierarchical netlist including a top circuit, primitive devices, and a plurality of sub-circuit instances, according to some embodiments; 
         FIG.  5 A  illustrates a flattened circuit as an example; 
         FIG.  5 B  illustrates a hierarchical circuit as an example; 
         FIGS.  6 A through  6 O  illustrate processed of obtaining submatrices and subvectors for each SCI in a hierarchical netlist, and constructing circuit equations for the top circuit, according to some embodiments; 
         FIG.  7 A  illustrates a bottom-up process, according to some embodiments; 
         FIG.  7 B  illustrates a top-down process, according to some embodiments; and 
         FIGS.  8 A and  8 B  illustrate hierarchical circuit simulation using parallel processing, according to some embodiments. 
         FIG.  9    illustrates a hierarchical circuit having SCIs with different preset value precisions as an example. 
         FIG.  10 A  is a flowchart illustrating a process of using a single set of computer program instructions to compute circuit equation parameters for a set of SCIs having a common circuit topology in accordance with some embodiments. 
         FIG.  10 B  is a flowchart illustrating a process of using a single set of computer program instructions to compute signal values for a set of SCIs having a common circuit topology in accordance with some embodiments. 
         FIG.  11 A  illustrates a hierarchical circuit including one or more sets of SCIs, each set of SCIs having a common circuit topology in accordance with some embodiments. 
         FIG.  11 B  illustrates matrices/vectors of circuit equations for two SCIs having a common circuit topology in accordance with some embodiments. 
         FIG.  12 A  illustrates a hierarchical circuit as an example. 
         FIGS.  12 B and  12 C  illustrate matrices/vectors of circuit equations for two child SCIs, respectively, in accordance with some embodiments. 
         FIG.  12 D  illustrates a global matrix of a hierarchical circuit in accordance with some embodiments. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     According to some embodiments, a method of simulating a circuit can be performed by one or more processors in one or more computer systems, each of the one or more computer systems including at least one processor. The one or more computer systems include or have access to one or more memory devices.  FIG.  1 A  is a block diagram of a computer system  100  that can be configured to carry out, either individually or in conjunction with one or more other similarly configured computer systems, a method of simulating a circuit according to some embodiments. As shown in  FIG.  1 A , computer system  100  includes one or more processors  102  coupled to a bus  108 , one or more optional graphic processing units (GPUs)  104  coupled to bus  108 , memory  106  accessible by processors  102  and GPUs  104 , and input devices  112 , output devices  114 , and storage device  116  coupled to bus  108 . Input devices  112  may include, for example, keyboard, mouse, and scanner etc. Output devices  114  may include, for example, display and printer etc. Storage devices  116  may include, for example, solid state disks, hard disks, USB disks, DVD CD etc. In some embodiments, the method of simulating a circuit is carried out by one or more of the processors  102  executing computer program instructions stored in the memory  106 . 
       FIG.  1 B  is a block diagram illustrating a computer network  150  including multiple computer systems that can be used to jointly carry out a method of simulating a circuit according to some embodiments. In some embodiments, the multiple computer systems include a main computer system  152  and one or more other computer systems (e.g., computer systems  162 ,  164 ,  166 , and/or  168 ), coupled with each other either directly or via a network  154 . Network  154  can be a local area network (LAN) or wide area network (WAN). In some embodiments, computer system  100  can be used as each of computer systems  152 ,  162 ,  164 ,  166 , and  168 . A processor in main computer  152  is configured to receive a circuit netlist representing a circuit to be simulated, to start the method of simulating the circuit and to manage the other processors and/or GPUs in computer system(s)  152 ,  162 ,  164 ,  166 , and/or  168  to calculate output results. The memory or memories  106  of computer system(s)  152 ,  162 ,  164 ,  166  and/or  168  are configured to store the circuit netlist, intermediate results and final results. In some embodiments, network  154  is configured pass the intermediate results among the computer systems  152 ,  162 ,  164 ,  166  and/or  168 . 
     In some embodiments, a processor in main computer system  152  is configured to retrieve from storage devices  116 , the circuit netlist (or netlist), which is a textual representation of the circuit to be simulated. The processor may also receive the netlist from another computer system or storage device via network  154 , or as user input via input devices  112 . In some embodiments, the circuit includes interconnected circuit elements. The design of a modern day integrated circuit (e.g., very large scale integrated circuit or VLSI) relies heavily on its hierarchical architecture, in which the circuit is viewed as a collection of building blocks or modules that are further divided into submodules or subcircuits in a recursive and hierarchical manner. The use of a subcircuit at a given level of the hierarchy is called an instance. A subcircuit instance at a given level may include other subcircuit instance(s) at a lower level. In this case, the subcircuit instance at the given level is said to be the parent of the other subcircuit instance(s) at the lower level, the other subcircuit instance(s) at the lower level can be said to be the child subcircuit instance(s) of the subcircuit instance at the given level. A subcircuit instance with no child subcircuit is called a leaf subcircuit instance. At any level of the hierarchy, there may also be primitive circuit elements or devices such as resistors, capacitors, and transistors, which does not include any instances of other subcircuits. In general, a subcircuit instance (SCI) is represented by its external ports and not by its contents (e.g., circuit components). A circuit that has all its subcircuit instances recursively replaced with their respective contents would be reduced to a hierarchical depth of one and is said to be flattened, or fully instantiated. 
     For example,  FIG.  2 A  illustrates a circuit  200  including primitive devices and subcircuit instances (SCIs), according to some embodiments. As shown, circuit  200  includes a plurality of external ports (e.g., port “in”  202 , port “out”  204 , power terminal VDD  206 , and ground terminal GND  208 ). Circuit  200  further includes subcircuit instances (e.g., SCI_ 1   230 , SCI_ 2   232 ), primitive device (e.g., resistor r 1   222  and capacitor r 1   224 ), and internal nets (e.g., internal net “n 1 ”  212  between subcircuit instance SCI_ 1   230  and resistor r 1   222 ). Resistor r 1   222  is coupled between port “in”  202  and internal net “n 1 ”  212 , and capacitor c 1   224  is coupled between internal net “n 1 ”  212  and ground terminal GND  208 . SCI_ 1   230  has four external ports (e.g., port “n 1 ”  212 , port “out”  204 , port VDD  206  and port GND  208 ). SCI_ 1   230  has two child SCIs (e.g., SCI_ 11   226  and SCI_ 12   228 ) and one internal net “n 2 ”  214  between the two child SCIs. SCI_ 2   232  has two external ports (e.g., port VDD  206  and port GND  208 ) and no internal net. SCI_ 11   226  has external port “n 1 ”  212 , “n 2 ”  214 , VDD  206  and GND  208 , and no internal net. SCI_ 12   228  has external ports “n 2 ”  214 , out  204 , VDD  206  and GND  208 , and no internal net. The external ports and internal nets of an SCI are also referred to as its nodes. 
       FIG.  2 B  illustrates an example of a netlist  201  for circuit  200 , according to some embodiments. As shown, netlist  201  includes textual definition of circuit topology and element values in circuit  200 . In netlist  201 , each element in the circuit is specified by an element line including the element name (e.g., SCI_ 1 ), the connecting ports or nodes (e.g., n 1  GND out VDD GND), and electrical parameter values if any. 
     Conventionally, a circuit hierarchy is typically flattened to the device level during circuit simulation. For example, circuit simulation programs such as SPICE would read a netlist of a circuit to be simulated and all of its input signals, and solve a set of mathematical equations involving all of the circuit components or elements in the flattened circuit to obtain the circuit response in the form of output signals. Because the circuit is flattened and fully instantiated, the device connectivity and device parameters for each of a large number (e.g., millions) of interconnected devices have to be stored during simulation. Such massive amount of memory usage makes it impractical to use existing circuit simulators to perform full-chip circuit simulation on today&#39;s VLSI circuits. Furthermore, solving the set of mathematical equations involving all of the circuit components or elements in the flattened circuit together makes it difficult, if not impossible, to use multiple processors or computers to speed up the calculation. Thus, conventional circuit programs fall short in both speed and capacity. 
     Systems and methods for simulating a circuit according to some embodiments overcome the problems of conventional circuit simulators by utilizing the hierarchical structure of the circuit.  FIGS.  3 A to  3 D  are flowcharts illustrating a method  300  of simulating a circuit (e.g., circuit  200 ) according to some embodiments. Method  300  can be performed by one or more processors in one or more computer systems (e.g., computer system(s)  100 ,  152 ,  162 ,  164 ,  166 , and/or  168 ). As shown in  FIG.  3 A , method  300  includes receiving ( 310 ), by one or more processors of the one or more computer systems, a netlist of the circuit to be simulated, and determining ( 320 ) if the netlist describes a hierarchical circuit. Sometimes the netlist can be transferred from a conventional simulator and is flattened. In this case, method  300  further includes partitioning ( 330 ) the netlist into a hierarchical structure. 
     For example, as shown in  FIG.  4   , a hierarchical netlist  400  for circuit  200  includes a top circuit  402 , which includes primitive devices such as r 1  and c 1 , and a plurality of sub-circuit instances (SCIs) (e.g., SCI_ 1   412  corresponding to SCI_ 1   230 , SCI_ 2   414  corresponding to SCI_ 1   232 , SCI_ 11   422  corresponding to SCI_ 1   226 , and SCI_ 12   424  corresponding to SCI_ 1   228 ) forming at least three hierarchical levels, including a first level  410  under the top circuit  402  and a second level  420  under first level  410 , which happens to be at the bottom level for one of the branches under the top circuit  402 . First level  410  includes subcircuit instance SCI_ 1   412 , and subcircuit instance SCI_ 2   414 , which happens to be at the bottom level of another branch under the top circuit  402 . Second level  420  includes subcircuit instances SCI_ 11   422 , and SCI_ 12   424 . Each sub-circuit instance (SCI) of the plurality of SCIs is a child of another SCI at a higher level or a child of the top circuit. Each sub-circuit instance (SCI) of the plurality of SCIs is a parent of one or more other SCIs at a lower level or it is a leaf SCI with no child SCI. Thus, each level of the hierarchy includes at least one SCI. In some embodiments, each of the plurality of SCIs (e.g., SCI_ 1   412 ) has external ports (e.g., port “n 1 ” and output port  204 ), and at least one of the plurality of SCIs (e.g., SCI_ 1   230 ) includes one or more internal nets (e.g., node “n 2 ”). In some embodiments, an external port of a child SCI could be an external port or internal net of the parent SCI, while any internal net of the child SCI is not an internal net of the parent SCI. In this example, top circuit  402  is at the top of the hierarchy and has child SCI_ 1   412  and SCI_ 2   414 . SCI_ 1   412  has child SCI_ 11   422  and SCI_ 12   424 . Also, SCI_ 2   414 , SCI_ 11   422  and SCI_ 12   424  are leaf SCIs in the hierarchy and have no child SCIs. Each of the top circuit  402  and the SCIs  412 ,  414 ,  422 , and  424  may also include primitive devices such as resistors, capacitors, inductors, mutual inductors, transmission lines, diodes, bipolar junction transistors (BJT), junction field effect transistors (JFET), metal-oxide-semiconductor field effect transistors (MOSFET), metal-semiconductor field effect transistors (MESFET), thin-film transistors (TFT), etc. 
     In some embodiment, if the received circuit is a flat circuit netlist which has primitive devices but no SCIs and no hierarchical structure, method  300  would include partitioning ( 330 ) the flat circuit netlist to form a hierarchical netlist. In some embodiments, partitioning ( 330 ) the flat circuit may include grouping the primitive devices to different groups, add one or more SCIs to each group by moving primitive devices to the corresponding SCIs. For example, as shown in  FIG.  5 A , a circuit  502  when flattened is shown to include primitive device  1 ˜ 8 , all in one level. During partitioning, primitive device  3 ˜ 4  are place in group  522  as SCI_ 11 , primitive device  5 ˜ 6  are place in group  524  as SCI_ 12 , primitive device  7 ˜ 8  are place in group  514  as SCI_ 2 . SCI_ 11  and SCI_ 12  are grouped together in group  512  as SCI_ 1 . Thus, after partitioning, circuit  502  has a hierarchical structure similar to that shown in  FIG.  4   , as illustrated in  FIG.  5 B . 
     In some embodiments, for efficiency purpose, partitioning ( 330 ) the flat circuit netlist to form a hierarchical netlist may further include adjusting the hierarchical structure by (1) collapsing part of the hierarchical structure (e.g., absorbing SCI_ 11  and SCI_ 12  into SCI_ 1 ), and (2) expanding the hierarchical structure by partitioning some of the SCIs into multiple SCIs in multiple levels. 
     In some embodiments, one or more processors in one or more computer systems receive respective portions of the circuit netlist. Each processor of the one or more processors may be assigned to perform a respective part of the simulation process and may read the entire circuit netlist or a respective portion of the circuit netlist that is required to perform the calculation assigned to the processor. The one or more processors may read the entire circuit netlist or respective portions of the circuit netlist in parallel and performed their respective parts of the simulation process in parallel. 
     Referring to  FIG.  3 A , method  300  further includes reading ( 332 ) user inputs. In some embodiments, the user inputs may be provided from a user of the one or more computer systems as a wave form of an input signal at an external port (e.g., port “in”) of the top circuit (e.g., circuit  200 ).  FIG.  2 C  illustrates an example of a wave form of input signal changing with time according to some embodiments. Method  300  further includes determining ( 334 ) a series of iteration rounds (or steps) each corresponding to an input signal value of a set of input signal values at different points in time. As shown in  FIG.  3 A , in some embodiments, method  300  then iterates ( 340 ) through the series of iteration rounds to calculate a response output signal value at another external port (e.g., port “out”) corresponding to each of the set of input signal values.  FIG.  2 D  illustrates an example of an output signal changing with time, as simulation results output by the one or more computer system performing method  300 . 
     Referring to  FIG.  3 A , method  300  includes, in each iteration round of the series of iteration rounds, a bottom-up process ( 350 ) that starts from the bottom level of each of one or more branches and moves up the hierarchy level by level to obtain ( 3502 ), for each level in the hierarchy and for each SCI in the level, first and second submatrices and first and second subvectors of the SCI. As shown in  FIG.  3 C , according to some embodiments, at each respective level of the hierarchy and for each respective SCI at the respective level, obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI includes determining ( 3504 ) if the current iteration round is an initial iteration round (e.g., one of the first one or more iteration rounds in the series of iteration rounds). In response to the determination that the current iteration round is an initial iteration round, process  350  proceeds to generate ( 3514 ) a circuit equation representing electrical characteristics and behaviors of the each respective SCI in the form of, for example, a matrix equation, such as equation (1) below:
 
 G·V=I   (1)
 
where G is a left-hand matrix of the SCI, V is a signal vector of the SCI, and I is a right-hand vector of the respective SCI. In its expanded form, equation (1) becomes the following for an SCI with n nodes:
 
                       [           G   11         …         G     1   ⁢   n               ⋮       ⋱       ⋮             G     n   ⁢   1           …         G   nn           ]     ⁡     [           V   1             ⋮             V   n           ]       =     [           I   1             ⋮             I   n           ]             (     1   ⁢   a     )               
where G ij  represents a left-hand matrix element corresponding to node i and node j (i=1, . . . , n, j=1, . . . , n), I i  represents a right-hand vector element corresponding to node i, V i  represents a signal value at node i. G ij  and I i  can be determined using, for example, standard SPICE method known to those skilled in the art. V i  is a signal value to be calculated using the method  300 . In some embodiments, the matrix equation is arranged such that nodes  1  through k are external ports (k=2, . . . , n), and nodes k+1 through n are internal nets. In other words, the external ports and internal nets are organized separately in the matrix equation (1) or (1a). By organizing external ports and internal nets separately, the equation (1) can be expressed using submatrices Ge, Gie, Gei, G and subvectors Ve, Vi, Ie, Ii, as follows:
 
     
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             Ge 
                           
                           
                             Gei 
                           
                         
                         
                           
                             Gie 
                           
                           
                             Gi 
                           
                         
                       
                       ] 
                     
                     × 
                     
                       [ 
                       
                         
                           
                             Ve 
                           
                         
                         
                           
                             Vi 
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           Ie 
                         
                       
                       
                         
                           Ii 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 where 
               
               
                 
                     
                 
               
             
             
               
                 
                   Ge 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             G 
                             11 
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             
                               1 
                               ⁢ 
                               k 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             G 
                             
                               k 
                               ⁢ 
                               1 
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             kn 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     a 
                   
                   ) 
                 
               
             
             
               
                 
                   Gie 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             G 
                             
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               ⁢ 
                               1 
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               ⁢ 
                               k 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             G 
                             
                               n 
                               ⁢ 
                               1 
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             nk 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     b 
                   
                   ) 
                 
               
             
             
               
                 
                   Gei 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             G 
                             
                               1 
                               ⁢ 
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             
                               1 
                               ⁢ 
                               n 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             G 
                             
                               k 
                               ⁡ 
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             kn 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     c 
                   
                   ) 
                 
               
             
             
               
                 
                   Gi 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             G 
                             
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               ⁢ 
                               n 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             G 
                             
                               n 
                               ⁡ 
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         
                           ⋯ 
                         
                         
                           
                             G 
                             nn 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     d 
                   
                   ) 
                 
               
             
             
               
                 
                   Ve 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             Ve 
                             1 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Ve 
                             k 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     e 
                   
                   ) 
                 
               
             
             
               
                 
                   Vi 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             Vi 
                             
                               k 
                               + 
                               1 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Vi 
                             n 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     f 
                   
                   ) 
                 
               
             
             
               
                 
                   Ie 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             Ie 
                             1 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Ie 
                             k 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     g 
                   
                   ) 
                 
               
             
             
               
                 
                   Ii 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             Ii 
                             
                               k 
                               + 
                               1 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Ii 
                             n 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     h 
                   
                   ) 
                 
               
             
           
         
       
     
     As shown in  FIG.  3 B , obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI further includes extracting ( 3516 ) first and second submatrices from the left-hand matrix and first and second subvectors from the right-hand vector. The first and second subvectors correspond to respective ones of the first and second submatrices. In some embodiments, extracting ( 3516 ) the submatrices and subvectors includes performing Gaussian elimination on equation (2) to transform the left-hand matrix and the right-hand vector. As a result, equation (2) becomes equation (3), as follows: 
                       [           Ge   ′           Gei   ′               Gie   ′           Gi   ′           ]     ×     [         Ve           Vi         ]       =     [           Ie   ′               Ii   ′           ]             (   3   )             where                           Ge   ′     =     [           Ge   ′11         ⋯         Ge     ′1   ⁢   k               ⋮       ⋱       ⋮             Ge     ′   ⁢   k   ⁢   1           ⋯         Ge     ′   ⁢   kn             ]             (     3   ⁢   a     )                 Gie   ′     =     [           Gie       ′   ⁡     (     k   +   1     )       ⁢   1           ⋯         Gie       ′   ⁡     (     k   +   1     )       ⁢   k               ⋮       ⋱       ⋮             Gie     ′   ⁢   n   ⁢   1           ⋯         Gie     ′   ⁢   nk             ]             (     3   ⁢   b     )                 Gei   ′     =     [         0       ⋯       0           ⋮       ⋱       ⋮           0       ⋯       0         ]             (     3   ⁢   c     )                 Gi   ′     =     [         1       ⋯       0           ⋮       ⋱       ⋮           0       ⋯       1         ]             (     3   ⁢   d     )               
where Gie′ and Ge′ are the extracted first and second submatrices, respectively, of the SCI, and Ii′ and Ie′ are the extracted first and second subvectors, respectively, of the SCI. Submatrix Gei′ is now a [0] matrix, submatrix Gi′ is now a unit matrix. Equation (3) can also be written as:
 
                       [           Ge   ′           [         0       ⋯       0           ⋮       ⋱       ⋮           0       ⋯       0         ]               Gie   ′           [         1       …       0           …       1       …           0       …       1         ]           ]     ×     [         Ve           Vi         ]       =     [           Ie   ′               Ii   ′           ]             (     3   ⁢   e     )               
which can be broken into two sub-equations:
 
[ Vi ]=[ Ii ′]−[ Gie ′]×[ Ve ]  (4a)
 
[ Ge ′]×[ Ve ]=[ Ie ′]  (4b)
 
     From sub-equation (4a), internal signal value [Vi] can be calculated by external port signal values [Ve], first submatrix [Gie′] and first subvector [Ii′]. In sub-equation (4b), second submatrix Ge′ is representative characteristic matrix corresponding to the external ports, the second subvector Ie′ is right hand vector corresponding to the external ports, vector Ve includes external port values, which are unknown at this point. 
     In some embodiments, using Gaussian elimination to transform equation (2) into equation (3) can be done by lower-upper (LU) decomposition or factorization of submatrix Gi, with proper row and/or column orderings or permutations, into two factors—a lower triangular matrix Li and an upper triangular matrix Ui, e.g., 
                   Gi   =     Li   *   Ui             (     5   ⁢   a     )             or                             [         Ge       Gei           Gie         Li   ×   Ui           ]     ×     [         Ve           Vi         ]       =     [         Ie           Ii         ]             (     5   ⁢   b     )               
Thus, by performing Gaussian elimination on equation (5b), [Ge], [Gie] and [Gei] are eliminated along with column/row of Li and Ui, and Gei′ becomes [0].
 
     In some embodiments, as shown in  FIG.  3 C , in response to the determination that the current iteration round is not one of the initial iteration round(s), obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI would include determining ( 3506 ) if the respective SCI is an active SCI. In some embodiments, an SCI is an active SCI if any of its signal values has changed more than a preset threshold during previous iteration rounds e.g., the difference in the values of a particular signal (e.g., Ve i , i=1, . . . , n) determined in two consecutive iteration rounds immediately prior to the current iteration round is greater than the preset threshold for the particular signal. In response to the determination that the respective SCI is not an active SCI, obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI could include retrieving and reusing ( 3510 ), in the current iteration round, the submatrices and subvectors obtained in the previous iteration round, and steps  3514 ,  3516 , and  3518  for this SCI at the current iteration round can be skipped. In response to the determination that the respective SCI is an active SCI, obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI would include determining whether the respective SCI is a leaf SCI and has precalculated submatrix and subvectors templates. 
     In response to the determination that the each respective SCI is a leaf SCI and has precalculated submatrix and subvector templates, obtaining ( 3502 ) first and second submatrices and first and second subvectors of the SCI would include calculating ( 3512 ) the first and second submatrices and the first and second subvectors for the leaf SCI from the precalculated submatrix and subvectors templates. In response to the determination that the each respective SCI is not a leaf SCI or does not have precalculated submatrix and subvector templates, the matrix equation representing electrical characteristics of the each respective SCI is generated ( 3514 ), and first and second submatrices are extracted ( 3516 ) from the left-hand matrix and first and second subvectors are extracted ( 3516 ) from the right-hand vector, as discussed above. Thus, for each SCI in the netlist, the left-hand matrix and right-and vector of the SCI are generated during the initial iteration rounds and when the SCI is an active SCI and is not a leaf SCI with precalculated submatrix and subvector templates. 
     In some embodiments, the first submatrix and the first subvector obtained in step  3502  are stored in the one or more memory devices (e.g., memory  106 ), while the second submatrix and the second subvector obtained in step  3502  are incorporated into the matrix equation for the parent SCI of the current SCI. Thus, as shown in  FIG.  3 B , process  350  further includes saving ( 3518 ) at least the first submatrix and the first subvector into memory (e.g., memory  106 ) and/or storage (e.g., storage  116 ). In some embodiments, the second submatrix and the second subvector of the current SCI are passed ( 3520 ) to the processor assigned to calculate the matrix equation for the parent SCI at the next hierarchical level. In some embodiment, the second submatrix and the second subvector of the respective SCI are cached by a respective processor performing calculations on the respective SCI if the respective processor is also designated to perform calculation on the parent SCI. Or, if another processor in the same or different computer system has been designated to perform calculation on the parent SCI, access to the memory space holding the second submatrix and the second subvector of the current SCI is provided by the respective processor to the other processor via bus  108  or network  154 . In either case, the second submatrix and the second subvector of the current SCI is passed ( 3520 ) to and incorporated into the matrix equation of the parent SCI in the same iteration round. 
     Referring to  FIG.  3 B , after the submatrices and subvectors for the respective SCI have been extracted and saved and/or passed to the next level of calculation, process  350  proceeds to determine ( 3522 ) whether each SCI at the current hierarchical level has had its submatrices and subvectors extracted, and if so, to determine ( 3523 ) if the next hierarchical level above is the top level in the hierarchy. If there are more SCI(s) in the current level to be worked on, or the next hierarchical level above is not the top level in the hierarchy, process  350  returns to step  3502  to perform calculation on the next SCI at the same level or at the next level above. Process  350  completes after the submatrices and subvectors for each SCI in the netlist are obtained for the current iteration round. 
     As discussed above, generating ( 3514 ) a matrix equation representing electrical characteristics and behaviors of a parent SCI would include incorporating the second submatrix and the second subvector of each of its child SCI(s). Since process  350  starts from the bottom hierarchical level and moves upwards one level at a time, the second submatrix and the second subvector of each of the child SCI(s) should have already been extracted before process  350  starts to generate the matrix equation (e.g., equation (1)) for the parent SCI. 
     As example,  FIGS.  6 A through  6 O  illustrate how the submatrices and subvectors are obtained for each SCI in hierarchical netlist  400  (shown in  FIG.  4   ). Starting at a leaf SCI (e.g., SCI_ 11   422 ) at the lowest hierarchical level (i.e., bottom level  420 ),  FIG.  6 A  shows the matrix equation for the SCI_ 11 , including a left-hand matrix [G 11 ] and a right-hand vector [I 11 ] of SCI_ 11 . SCI_ 11  has external ports “n 1 ”  212 , “n 2 ”  214 , VDD  206 , GND  208  and internal nets represented by “ . . . ” The equation representation of SCI_ 11  can be organized as shown in  FIG.  6 A , although the columns and rows orders can be different. Since this is a leaf SCI, the elements in the left-hand matrix [G 11 ] can be calculated either from existing templates or from standard SPICE circuit analysis.  FIG.  6 B  shows the transformed matrix equation for the SCI_ 11  after Gaussian elimination, with extracted first and second submatrices [Gie′ 11 ] and [Ge′ 11 ], and first and second subvectors [Ii′ 11 ] and [Ie′ 11 ]. Since there is another SCI (e.g., SCI_ 12 ) at this level, process  350  proceeds to calculate the submatrices and subvectors for SCI_ 12 .  FIG.  6 C  shows the matrix equation for the SCI_ 12 , including a left-hand matrix [G 12 ] and a right-hand vector [I 12 ] of SCI_ 12 . SCI_ 12  has external ports “n 2 ”  214 , out, VDD  206 , GND  208  and internal nets represented by “ . . . ” The equation representation of SCI_ 12  can be organized as shown in  FIG.  6 C , although the columns and rows orders can be different.  FIG.  6 D  shows the transformed matrix equation for the SCI_ 12  after Gaussian elimination, with extracted first and second submatrices [Gie′ 12 ] and [Ge′ 12 ], and first and second subvectors [Ie′ 12 ] and [Ii′ 12 ]. In some embodiments, the second submatrix [Ge′ 11 ] and second subvector [Ie′ 11 ] of SCI_ 11 , and the second submatrix [Ge′ 12 ] and second subvector [Ie′ 12 ] of SCI_ 12 , are passed up the hierarchical level and used to generate the left-hand matrix and right-hand vector of SCI_ 1 , as shown in  FIG.  7 A . 
     After each SCI at the bottom level  420  has been calculated, process  350  continues to the next SCI (e.g., SCI_ 1 ) at the next level, which in this example is the first level  410  under the top circuit  402 . SCI_ 1  has external ports “n 1 ”  212 , out  204 , VDD  206 , GND  208  and internal net “n 2 ”  214 , and the equation representation of SCI_ 1 , with its the left-hand matrix [G 1 ] and right-hand vector [I 1 ], can be ordered as shown in  FIG.  6 E . Since this SCI_ 1  has child SCI&#39;s, according to some embodiments, the elements of the left-hand matrix [G 1 ] and right-hand vector [I 1 ] of SCI_ 1  are generated by incorporating the corresponding elements in the second submatrix and second subvector of each of its child SCI(s). 
     For example, as shown in  FIG.  6 F , SCI_ 11 &#39;s second submatrix Ge′ 11  is incorporated into some of the elements (marked in bold texts) of SCI_ 1 &#39;s left-hand matrix by adding each element of SCI_ 11 &#39;s second submatrix Ge′ 11  to the element in the left-hand matrix [G 1 ] corresponding to the same row/column nodes (e.g., elements Ge′ 11   [11]  corresponding to the nodes n 1 /n 1 , Ge′ 11   [12]  corresponding to the nodes n 1 /n 2 , Ge′ 11   [13]  corresponding to the nodes n 1 /VDD, and Ge′ 11   [14]  corresponding to the nodes n 1 /GND, are added to elements Ge 1   [11]  corresponding to the nodes n 1 /n 1 , Gei 1   [11]  corresponding to the nodes n 1 /n 2 , Ge 1   [13]  corresponding to the nodes n 1 /VDD, and Ge 1   [14]  corresponding to the nodes n 1 /GND, respectively). Also, SCI_ 11 &#39;s second subvector Ie′ 11  is incorporated into some of the elements (marked in bold texts) of SCI_ 1 &#39;s right-hand vector by adding each element of SCI_ 11 &#39;s second subvector Ie′ 11  to the element in the right-hand vector [I 1 ] corresponding to the same row node (e.g., elements Ie′ [1]  corresponding to the nodes “n 1 ”, Ie′ 11   [2]  corresponding to the node “n 2 ”, Ie′ 11   [3]  corresponding to the node VDD, and Ie′ 11   [4]  corresponding to the node GND, are added to elements Ie 1   [1]  corresponding to the node “n 1 ”, Ii 1   [1]  corresponding to the node “n 2 ”, Ie 1   [3]  corresponding to the node VDD, and Ie 1   [4]  corresponding to the node GND, respectively). 
     Likewise, as shown in  FIG.  6 G , SCI_ 12 &#39;s second submatrix Ge′ 12  is incorporated into some of the elements (marked in bold texts) of SCI_ 1 &#39;s left-hand matrix by adding each element of SCI_ 12 &#39;s second submatrix Ge′ 12  to the element in the left-hand matrix [G 1 ] corresponding to the same row/column nodes (e.g., elements Ge′ 12   [11]  corresponding to the nodes n 2 /n 2 , elements Ge′ 12   [12]  corresponding to the nodes n 2 /out, Ge′ 12   [13]  corresponding to the nodes n 2 /VDD, and Ge′ 12   [14]  corresponding to the nodes n 2 /GND, are added to elements Gi 1   [11]  corresponding to the nodes n 2 /n 2 , Gie 1   [12]  corresponding to the nodes n 2 /out, Gie 1   [13]  corresponding to the nodes n 2 /VDD, and Gie 1   [14]  corresponding to the nodes n 2 /GND, respectively). Also, SCI_ 12 &#39;s second subvector Ie′ 12  is incorporated into some of the elements (marked in bold texts) of SCI_ 1 &#39;s right-hand vector by adding each element of SCI_ 12 &#39;s second submatrix Ge′ 12  to the element in the right-hand vector [I 1 ] corresponding to the same row node (e.g., elements Ie′ 12   [1]  corresponding to the nodes “n 2 ”, Ie′ 12   [2]  corresponding to the node out, Ie′ 12   [3]  corresponding to the node VDD, and Ie′ 12   [4]  corresponding to the node GND, are added to elements Ii 1   [1]  corresponding to the node “n 2 ”, Ie 1   [2]  corresponding to the node out, Ie 1   [3]  corresponding to the node VDD, and Ie 1   [4]  corresponding to the node GND, respectively). 
     In other words, the elements of SCI_ 1 &#39;s left-hand matrix can be generated using its child SCIs&#39; second submatrices as follows: Ge 1   [11] =Ge′ 11   [11] , Ge 1   [12] =0, Ge 1   [13] =Ge′ 11   [13 , Ge 1   [14] =Ge′ 11   [14] , Ge 1   [21] =0, Ge 1   [22] =Ge′ 12   [22] , Ge 1   [23] =Ge′ 12   [23] , Ge 1   [24] =Ge′ 12   [24] , Ge 1   [31] =Ge′ 11   [31] , Ge 1   [32] =Ge′ 12   [32] , Ge 1   [33] =Ge′ 11   [33] +Ge′ 12   [33] , Ge 1   [34] =Ge′ 11   [34] +Ge′ 12   [34] , Ge 1   [41] =Ge′ 11   [41] , Ge 1   [42] =Ge′ 12   [42] , Ge 1   [43] =Ge′ 11   [43] +Ge′ 12   [43] , Ge 1   [44] =Ge′ 11   [44] +Ge′ 12   [44] , Gie 1   [11] =Ge′ 11   [21] , Gie 1   [12] =Ge′ 12   [12] , Gie 1   [13] =Ge′ 11   [23] +Ge′ 12   [13] , Gie 1   [14] =Ge′ 11   [24] +Ge′ 12   [14] , Gei 1   [11] =Ge′ 11   [12] , Gei 1   [21] =Ge′ 12   [21] , Gei 1   [31] =Ge′ 11   [32] +Ge′ 12   [31] , Gei 1   [41] =Ge′ 11   [42] +Ge′ 12   [41] , and Gei 1   [11] =Ge′ 11   [22] +Ge′ 12   [11] . Also the elements of SCI_ 1 &#39;s right-hand vector can be generated using its child SCIs&#39; second subvectors as follows: Ie 1   [1] =Ie′ 11   [1] , Ie 1   [2] =Ie′ 12   [2] , Ie 1   [3] =Ie′ 11   [3] +Ie′ 12   [3] , Ie 1   [4] =Ie′ 11   [4] +Ie′ 12   [4] , and Ii 1   [1] =Ie′ 11   [2] +Ie′ 12   [1] . 
       FIG.  6 H  shows transformed matrix equation for the SCI_ 1  after Gaussian elimination, with extracted first and second submatrices [Gie′ 1 ] and [Ge′ 1 ], and first and second subvectors [Ie′ 1 ] and [Ii′ 1 ] of SCI_ 1 .  FIG.  6 I  shows the generated left-hand matrix [G] and right-hand vector [I] of SCI_ 2 .  FIG.  6 J  shows the transformed matrix equation for the SCI_ 2  after Gaussian elimination, with extracted first and second submatrices [Gie′ 2 ] and [Ge′ 2 ], and first and second subvectors [Ie′ 2 ] and [Ie′ 2 ] of SCI_ 2 . In some embodiments, the second submatrix [Ge′ 1 ] and second subvector [Ie′ 1 ] of SCI_ 1 , and the second submatrix [Ge′ 2 ] and second subvector [Ie′ 2 ] of SCI_ 2 , are passed up the hierarchical level and used to generate the left-hand matrix and right-hand vector of top circuit  402 , as shown in  FIG.  7 A . 
     Thus, in some embodiments, Equation (2) for an SCI&#39;s can be formed after the submatrices and subvectors of each of its child SCI(s) have been obtained by incorporating the second submatrix Ge′ and second subvector Ie′ of each of its child SCI(s). When there are multiple child SCIs, the process to obtain the submatrices and subvectors for each child SCI can be carried out independently before, after, or in parallel with the processes to obtain the submatrices and subvectors for each of the other child SCIs. In other words, in some embodiments, an SCI has calculation dependency on its child SCIs, but there is no calculation dependency among the child SCIs. 
     Referring back to  FIG.  3 A , in some embodiments, method  300  further includes, in each iteration round of the series of iteration rounds, computing ( 360 ) circuit equation parameters for the top circuit and solving ( 362 ) the top circuit&#39;s circuit equation to determine the top circuit&#39;s signal values. In some embodiments, computing ( 360 ) circuit equation parameters for the top circuit includes incorporating the 2 nd  submatrices and 2 nd  subvectors of each of the SCIs in the first hierarchical level immediately under the top circuit. For example,  FIG.  6 K  shows the matrix equation for top circuit  402 , which includes a left-hand matrix G, signal vector V and a right hand vector I. Left-hand matrix G includes rows corresponding, respectively, to the top circuit&#39;s external ports (e.g., external ports “in,” out, VDD, GND) and internal net(s) (e.g., internal net “n 1 ”), and columns corresponding, respectively, to the top circuit&#39;s external ports (e.g., external ports “in,” out, VDD, GND) and internal net(s) (e.g., internal net “n 1 ”). Right hand vector I includes a set of elements corresponding, respectively, to the top circuit&#39;s external ports (e.g., external ports “in,” out, VDD, GND) and internal net(s) (e.g., internal net “n 1 ”). In some embodiments, each element in the left-hand matrix G can be computed using the corresponding element in the left-hand matrix of each of the primitive devices (e.g., r 1  and c 1 ) of top circuit  402  and the corresponding element in the 2 nd  submatrix of each SCI (e.g., SCI_ 1  and SCI_ 2 ) in the first hierarchical level immediately below top circuit  402 . Likewise, each element in the right-hand matrix I can be computed using the corresponding element in the right-hand vector of each of the primitive devices (e.g., r 1  and c 1 ) of top circuit  402  and the corresponding element in the 2 nd  subvector of each SCI (e.g., SCI_ 1  and SCI_ 2 ) in the first hierarchical level immediately below top circuit  402 . 
     For example,  FIG.  6 L  shows that parameters associated with primitive device r 1  in top circuit  402  are incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s left-hand matrix by adding each of r 1 &#39;s parameters to the corresponding elements (e.g., elements corresponding to “n 1 ” and “in,” which are nodes on both sides of r 1 ) in the left-hand matrix G and right-hand vector I of top circuit  402 .  FIG.  6 M  shows that parameters associated with primitive device c 1  in top circuit  402  are incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s left-hand matrix by adding each of c 1 &#39;s parameters to the corresponding elements (e.g., elements corresponding to “n 1 ” and GND, which are nodes on both sides of c 1 ) in the left-hand matrix G and right-hand vector I of top circuit  402 . 
       FIG.  6 N  shows SCI_ 1 &#39;s second submatrix Ge′ 1  is incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s left-hand matrix [G] by adding each element of SCI_ 1 &#39;s second submatrix Ge′ 1  to the corresponding element in the left-hand matrix [G] (e.g., elements Ge′ 1   [11]  corresponding to the row/column n 1 /n 1 , Ge′ 1   [12]  corresponding to the row/column n 1 /out, Ge′ 1   [13]  corresponding to the row/column n 1 /VDD, and Ge′ 1   [14]  corresponding to the row/column n 1 /GND, are added to elements G [22]  corresponding to the row/column n 1 /n 1 , G [23]  corresponding to the row/column n 1 /out, G [24]  corresponding to the row/column n 1 /VDD, and G [25]  corresponding to the row/column n 1 /GND, respectively, and so on).  FIG.  6 N  also shows SCI_ 1 &#39;s second subvector Ie′ 1  is incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s right-hand matrix [I] by adding each element of SCI_ 1 &#39;s second subvector Ie′ 1  to the corresponding element in the right-vector matrix [I] (e.g., elements Ie′ 1   [1]  corresponding to the row n 1 , Ie′ 1   [2]  corresponding to the row out, Ie′ 1   [3]  corresponding to the row VDD, and Ie′ 1   [4]  corresponding to the row GND, are added to elements I [2]  corresponding to the row n 1 , I [3]  corresponding to the row out, I [4]  corresponding to the row VDD, and I [5]  corresponding to the GND, respectively, and so on). 
       FIG.  6 O  shows SCI_ 2 &#39;s second submatrix Ge′ 2  is incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s left-hand matrix [G] by adding each element of SCI_ 2 &#39;s second submatrix Ge′ 2  to the corresponding element in the left-hand matrix [G] (e.g., elements Ge′ 2   [11]  corresponding to the row/column VDD/VDD, AND Ge′ 2   [12]  corresponding to the row/column VDD/GND are added to elements G [44  corresponding to the row/column VDD/VDD, G [45]  corresponding to the row/column VDD/GND, respectively, and so on).  FIG.  6 O  also shows SCI_ 2 &#39;s second subvector Ie′ 2  is incorporated into some of the elements (marked in bold texts) of the top circuit&#39;s right-hand matrix [I] by adding each element of SCI_ 2 &#39;s second subvector Ie′ 2  to the corresponding element in the right-vector matrix [I] (e.g., elements Ie′ 2   [1]  corresponding to the row VDD, and Ie′ 2   [2]  corresponding to the row GND, are added to elements I [4]  corresponding to the row VDD, I [5]  corresponding to the row GND, respectively, and so on). 
     Referring back to  FIG.  3 A , in some embodiments, method  300  further includes, in each iteration round of the series of iteration rounds, computing ( 360 ) circuit equation parameters for the top circuit and solving ( 362 ) the top circuit&#39;s circuit equation to determine the top circuit&#39;s signal values. Using the hierarchical circuit simulation approach according to some embodiments, the dimensions of the matrix equation for the top circuit is much smaller than the flattened whole circuit because matrix equation for the top circuit only includes parameters associated with the top circuit&#39;s external ports and the internal nets between its primitive devices and the SCIs in the first hierarchical level immediately below the top circuit. Furthermore, the elements in the top circuit&#39;s left-hand matrix and right-hand vector can determined by incorporating the second submatrix and second subvector of each of the SCI(s) in the first level, as discussed above. Thus, given the signal values at some of the top circuit&#39;s external ports (e.g., V [1]  corresponding to external port “in”), the signal values at others of the top circuit&#39;s external ports (e.g., V [3]  corresponding to external port “out,” V [4]  corresponding to external port VDD, and V [5]  corresponding to external port GND) and its internal net(s) (e.g., V [2]  corresponding to internal net “n 1 ”) can be readily solved using the top circuit&#39;s matrix equation by one or more processors in computer system  100  or  150 . 
     In some embodiments, at least some of the signal values of the top circuit are passed down to the next hierarchical levels and used to determine some of the signal values for the SCIs in the next hierarchical level, at least some of which are then passed down and used to determine the signal values for the SCI&#39;s in the hierarchical level below the next hierarchical level, and so on. As shown  FIG.  3 A , method  300  further includes, in each iteration round of the series of iteration rounds, a top-down process ( 370 ) that determine lower-level SCI&#39;s signal values using the signal values passed down from higher-level SCIs (or top circuit), starting from the first hierarchical level and moving down the hierarchy one level at a time. 
     As shown in  FIG.  3 D , according to some embodiments, process  370  performs circuit calculation on each SCI in the netlist, starting ( 3702 ) from the first level of the hierarchy and moving down the hierarchy one level at a time. For each SCI at a particular level, process  370  includes obtaining ( 3704 ) signal values of the SCI&#39;s external ports from the SCI&#39;s parent SCI (or the top circuit), and determining ( 3706 ) the signal values of the SCI&#39;s internal nets using the external ports&#39; signal values. Process  370  then proceeds to determine ( 3708 ) whether signal values for all of the SCIs in the current level have been calculated. If not all SCIs in the current level have had their signal values calculated, process  370  then moves to the next SCI in the same level and repeats steps  3704  and  3706  for the next SCI. If signal values for all of the SCIs in the current level have been calculated for the current iteration round, process  370  proceeds to determine whether the current level is the bottom level (or whether no other level(s) are below the current level). If the current level is not the bottom level, process  370  moves to the next hierarchical level and repeats steps  3704  and  3706  for each SCI in the next hierarchical level. Otherwise, process  370  completes and process  300  continues to determine ( 380 ) whether the current iteration round is the last iteration round, and repeats processes  350 ,  360 / 362 , and  370  for the next iteration round if the current iteration round is not the last iteration round. 
     For example, for the hierarchical circuit  400 , signal vector V in the matrix equation shown in  FIG.  6 K  for top circuit  402  include signal values at nodes “n 1 ”, “out,” VDD and GND. Nodes “n 1 ”, “out,” VDD and GND happen to be the external ports of SCI_ 1 , and nodes VDD and GND happen to be the external ports of SCI_ 2 . Thus, the signal values at “n 1 ”, “out” VDD, and GND correspond to the signal values in subvector [Ve 1 ], the signal values at VDD, and GND also correspond to the signal values in subvector [Ve 2 ]. In some embodiments, as shown in  FIG.  7 B , the signal values at “n 1 ”, “out” VDD, and GND, which correspond to the signal values in subvector [Ve 1 ], are passed down the hierarchy and used to calculate the signal values [Vi 1 ] at the internal net(s) of SCI_ 1  using equation 4(a). Likewise, as also shown in  FIG.  7 B , the signal values at VDD and GND, which correspond to the signal values in subvector [Ve 2 ], are passed down the hierarchy and can be used to calculate the signal values [Vi 2 ] at the internal net(s) of SCI_ 2  (if there is any) using equation 4(a). 
     In this example, SCI_ 2  does not have any internal net. SCI_ 1  has an internal net “n 2 ,” which is an external port for SCI_ 11  and SCI_ 12  at next level below. In some embodiments, as shown in  FIG.  7 B , the signal values at “n 1 ”, “n 2 ” VDD, and GND, which correspond to the signal values in subvector [Ve 11 ], are passed down the hierarchy and can be used to calculate the signal values [Vi 11 ] at the internal net(s) of SCI_ 11  (if there is any) using equation 4(a). Likewise, as also shown in  FIG.  7 B , the signal values at “n 2 ,” “out,” VDD and GND, which correspond to the signal values in subvector [Vel 2 ], are passed down the hierarchy and can be used to calculate the signal values [Vi 12 ] at the internal net(s) of SCI_ 12  (if there is any) using equation 4(a). 
     In some embodiments, the matrices/vectors and submatrices/subvectors of different SCIs&#39; in hierarchical circuit  400 , as illustrated in  FIGS.  6 A through  6 O , can be computed in different processors/computers. For example, as shown in  FIG.  8 A , a first processor (e.g., processor  1 ) in a first computer can be assigned to compute the submatrices/subvectors of SCI_ 11 , while a second processor (e.g., processor  2 ) in the first or a second computer may be assigned to compute the submatrices/subvectors of SCI_ 12 . The second processor (e.g., processor  2 ) may pass the second submatrix/subvector of SCI_ 12  to the first processor (e.g., processor  1 ), which would incorporate the second submatrices/subvectors of SCI_ 11  and SCI_ 12  into SCI_ 1 , and compute the submatrices/subvectors of SCI_ 1 . The second processor (e.g., processor  2 ) may compute the submatrices/subvectors of SCI_ 2  at about the same time when the submatrices/subvectors of SCI_ 1  is computed. The second processor (e.g., processor  2 ) can then provide the second submatrices/subvectors of SCI_ 2  to the first processor (e.g., processor  1 ) to compute the left-hand matrix and right-hand vector of the top circuit  402 . 
     As another example, as shown in  FIG.  8 B , the second processor (e.g., processor  2 ) can be assigned to compute the submatrices/subvectors of SCI_ 11 , SCI_ 12  and SCI_ 1 , while the first processor (e.g., processor  1 ) may be assigned to compute the submatrices/subvectors of SCI_ 2  and the top circuit. 
     Circuit equation parameters (and/or signal values) of different sub-circuit instances (SCIs) in a netlist (e.g., netlist  400 ) are computed with different value precisions, which can be preset for the SCIs based on, for example, user inputs and/or complexities of the different circuit topologies. Thus, some SCIs are calculated at higher precision for accuracy and convergence than other SCIs. For example, as shown in  FIG.  9   , the plurality of SCIs in a netlist (e.g., netlist  400 ) may include a child SCI (e.g., child SCI_ 1 ) having a first circuit topology, a parent SCI of child SCI_ 1  having a second circuit topology, and another child SCI of the parent SCI (e.g., child SCI_ 2 ) having a third topology. In some embodiments, circuit equation parameters (e.g., first and second submatrices, and first and second subvectors) for child SCI_ 1  are computed with a first value precision (e.g., quadruple precision, or 128-bit precision), circuit equation parameters for the parent SCI are computed with a second value precision (e.g., double precision, or 64-bit precision), and circuit equation parameters for child SCI_ 2  are computed with a third value precision (e.g., float precision, or 32-bit precision). 
     In some embodiments, when a child SCI and it&#39;s parent SCI are computed at different precisions, precision conversion is used when passing the second submatrix and second subvector of the child SCI to its parent SCI and when passing signal values from the parent SCI to the child SCI. As discussed above, circuit equation parameters for child SCI_ 1  are computed or otherwise obtained before circuit equation parameters for the parent SCI. As shown in  FIG.  9   , a second portion of the circuit equation parameters (e.g., second submatrix and second subvector) for child SCI_ 1  are converted from the first value precision (e.g., quadruple precision) to the second value precision (e.g., double precision) before being used to obtain some of the circuit equation parameters for the parent SCI. Likewise, circuit equation parameters for child SCI_ 2  are computed or otherwise obtained before circuit equation parameters for the parent SCI, and a second portion of the circuit equation parameters (e.g., second submatrix and second subvector) for child SCI_ 2  are converted from the third value precision (e.g., float precision) to the second value precision (e.g., double precision) before being used to obtain some of the circuit equation parameters for the parent SCI. 
     In some embodiments, signal values at internal nets of child SCI_ 1  are determined with the first value precision (e.g., quadruple precision), signal values at internal nets of the parent SCI are determined with a second value precision (e.g., double precision). Thus, as shown in  FIG.  9   , one or more first signal values of the parent SCI are converted from the second value precision (e.g., double precision) to the first value precision (e.g., quadruple precision) before being used to compute the signal values at the internal nets of the child SCI_ 1 . The one or more first signal values of the parent SCI correspond, respectively, to one or more signal values at external ports of the child SCI_ 1 . Likewise, one or more second signal values of the parent SCI are converted from the second value precision (e.g., double precision) to the third value precision (e.g., float precision) before being used to compute the signal values at the internal nets of the child SCI_ 2 . The one or more first signal values of the parent SCI correspond, respectively, to one or more signal values at external ports of the child SCI_ 2 . 
     In some embodiments, the plurality of SCIs in the netlist (e.g., netlist  400 ) include at least one set of SCIs having a common circuit topology and/or sharing a common circuit master, and process  350  includes a subprocess  1000  for computing the circuit equation parameters of each such set of SCIs. As shown in  FIG.  10 A , subprocess  1000  includes identifying ( 1010 ) a set of SCIs having a common circuit topology, each of the set of SCIs bring either a leaf SCI or a parent SCI that has one or more child SCIs, circuit equation parameters for each of the one or more child SCIs having been obtained in the same iteration round (or step). As shown in  FIG.  11 A , in a circuit netlist  1100 , a first set of SCIs having a common circuit topology and/or sharing a common circuit master (e.g., Master_D) can be, for example, SCI_ 5  and SCI_ 7 , which are leaf SCIs, and a second set of SCIs having a common circuit topology and/or sharing a common circuit master (e.g., Master_E) can be SCI_ 6  and SCI_ 8 , which are also leaf SCIs. After process  350  proceeds to the next level of the hierarchy (e.g., after circuit equation parameters for SCI_ 5  SCI_ 7 , SCI_ 6  and SCI_ 8  at the bottom level of the circuit netlist  1100  have been obtained), a third set of SCIs having a common circuit topology and/or sharing a common circuit master (e.g., Master_C) can be SCI_ 2  and SCI_ 4 , each of which is a parent SCI. 
     In some embodiments, as shown in  FIG.  10 A , in the case that each of the set of SCIs is a parent SCI, subprocess  1000  further includes obtaining ( 1020 ) some of the circuit equation parameters for the parent SCI using a portion of the circuit equation parameters (e.g., 2 nd  submatrices and 2 nd  subvectors) for each child SCI of the parent SCI. 
     In some embodiments, because the set of SCIs (e.g., SCI_ 2  and SCI_ 4 ) have a common circuit topology, their circuit equations tend to correspond with each other. For example, as shown in  FIG.  11 B , circuit equation parameters for SCI_ 2  (e.g., elements in left hand matrix [G 2 ] and right hand vector [V 2 ] correspond, respectively, to elements in left hand matrix [G 4 ] and right hand vector [V 4 ], although the corresponding elements may or may not have equal values. Furthermore, [G 2 ] and [G 4 ] tend to have the same sparseness (e.g., if the matrix element in the i th  row and j th  column of [G 2 ] is zero, or G 2   ij =0, then the matrix element in the i th  row and j th  column of [G 4 ] is also zero, or G 4   ij =0; and if the matrix element in the m th  row and n th  column of [G 2 ] is not zero, or G 4   mn ≠0, then the matrix element in the m th  row and n th  column of [G 4 ] is also not zero, or G 4   mn ≠0. Similarly, [V2} and [V4] also tend to have the same sparseness (e.g., if the i th  component of [V 2 ] is zero, then the i th  component of [V 4 ] is also zero; and if the m th  component of [V 2 ] is not zero, then the m th  component of [V 4 ] is also not zero. Thus, circuit equation parameters for the set of SCIs (e.g., SCI_ 2  and SCI_ 4 ) can be computed by executing or calling a same circuit equation computation function (e.g., a set of computer program instructions for computing the remaining circuit equation parameters for any one of the set of SCIs). 
     In some embodiments, subprocess  1000  further includes computing ( 1030 ) the remaining circuit equation parameters for each of the set of SCIs by executing the same set of computer program instructions at least once (i.e., by making at least one function call to the same circuit equation parameter computation function). In some embodiments, circuit equation parameters for a subset of one or more SCIs of the set of SCIs can be computed by executing the same set of computer program instructions once (i.e., by making a single function call to the same circuit equation parameter computation function). For example, corresponding circuit equation parameters of SCI_ 2  and SCI_ 4  can be computed together or in parallel during the same function call using two respective sets of inputs for SCI_ 2  and SCI_ 4 , respectively. Thus, by incorporating subprocess  1000 , process  350  can be carried out more speedily using less computer resources. 
     In some embodiments, process  370  includes a subprocess  1001  for computing the signal values of a set of SCIs having a common topology. As shown in  FIG.  10 B , subprocess  1001  includes identifying ( 1011 ) a set of SCIs having a common circuit topology (e.g., SCI_ 6  and SCI_ 8 ). In the case that each of the set of SCIs is a child SCI of a respective parent SCI (e.g., SCI_ 6  being a child SCI of SCI_ 2 , and SCI_ 8  being a child SCI of SCI_ 4 ), subprocess  1001  further includes determining ( 1021 ) signal values at external ports of the child SCI using corresponding signal values of the respective parent SCI. 
     In some embodiments, as discussed above, because the set of SCIs (e.g., SCI_ 6  and SCI_ 8 ) have a common circuit topology, their circuit equations tend to have a same structure. Thus, internal signal values for the set of SCIs (e.g., SCI_ 6  and SCI_ 8 ) can be computed by executing or calling a same signal value computation function (e.g., a set of computer program instructions for computing signal values at internal nets of any of the set of SCIs). 
     In some embodiments, subprocess  1001  further includes computing ( 1031 ) the signal values at internal nets of each of the set of SCIs by executing the same set of computer program instructions at least once (i.e., by making at least one function call to the same signal value computation function). In some embodiments, signal values at internal nets of a subset of one or more SCIs of the set of SCIs can be computed by executing the same set of computer program instructions once (i.e., by making a single function call to the same signal value computation function). For example, corresponding signal values can be computed together or in parallel with the same function call using two respective sets of inputs for SCI_ 6  and SCI_ 8 , respectively. Thus, using subprocess  1001 , process  370  can be carried out more speedily using less computer resources. 
     In some embodiments, as discussed above, a circuit netlist is represented by respective left-hand matrices and right-hand vectors of the respective SCIs of the plurality of SCIs, where a parent SCI and its child SCIs are considered as have their own respective left-hand matrices and right-hand vectors. As a result, circuit equation parameters for multiple child SCIs of a parent SCIs can be computed independently and concurrently, as discussed above. 
     Alternatively, a circuit netlist can be represented by one global matrix and one global vector, while each SCI can logically (or virtually) have its matrix/vector, which contribute to the global matrix/vector. For example, for a circuit netlist  1200  shown in  FIG.  12 A , child SCI_ 1  logically or virtually can have its own matrix/vector, where internal nets and external ports are organized in respective submatrices/subvectors Gi, Gie, Gei Ge Ie and Ii, as shown in  FIG.  12 B , and child SCI_ 2  logically or virtually can have its own matrix/vector, where internal nets and external ports are organized in respective submatrices/subvectors as shown in  FIG.  12 C . 
     In some embodiments, as shown in  FIG.  12 D , Child SCI_ 1 &#39;s matrix/vector and Child SCI_ 2 &#39;s matrix/vector contribute to portions of a global matrix/vector  1210 / 1220  and thus can be used to obtain elements in the portions of the global matrix/vector  1210 / 1220 . Thus, the logical or virtual matrices/vectors of the SCIs in the netlist can be computed using the method  300 , as discussed above, except that, since the external ports of SCI_ 1  and the external ports of SCI_ 2  may overlap partially with each other in areas marked by bolded rectangles  1201  and  1202 , respectively, circuit equation parameters for SCI_ 1  and SCI_ 2  in these areas cannot be accessed at the same time. Thus, circuit equation parameters for SCI_ 1  corresponding to these areas are not computed, or used to build the global matrix/vector  1210 / 1220 , concurrently with circuit equation parameters for SCI 2  corresponding to the same areas. 
     Thus, the methods according to some embodiments allow the computation of the circuit equations to be distributed across multiple processors in a single or multiple computer systems, which operate in parallel to perform the simulation. Furthermore, since the second submatrices and second subvectors of each SCI in the netlist are passed up the hierarchical levels and incorporated into the left-hand matrices and right-hand vectors of their respective parent SCIs or the top circuit, they do not need to be saved into memory  106  or storage  116  of the computer system(s) performing the calculation for the SCI. Thus, the methods according to certain embodiments provide faster simulation with significantly reduced memory requirements, making it possible to perform whole circuit simulation on very large-scale integrated circuits.