Search

EP-3803644-B1 - METHOD AND SYSTEM FOR HIERARCHICAL CIRCUIT SIMULATION USING PARALLEL PROCESSING

EP3803644B1EP 3803644 B1EP3803644 B1EP 3803644B1EP-3803644-B1

Inventors

  • CAO, Henry, Hongwei

Dates

Publication Date
20260506
Application Date
20190531

Claims (15)

  1. A method performed by one or more computer systems (100/152) to simulate a circuit (200), each of the one or more computer systems (100/152) including at least one processor (102) (102), the one or more computer systems (100/152) including or having access to one or more memory devices (106), comprising: receiving, by one or more processors (102) of the one or more computer systems (100/152), a netlist (201) of the circuit (200), the netlist (201) including a top circuit (402) and a plurality of sub-circuit instances (412/414/422/424) forming a hierarchy (400) having a first level (410) under the top circuit (402) and at least one second level (420) under the first level (410) such that 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 (402), and that each SCI of the plurality of SCIs is either a leaf in the hierarchy (400) or a parent of a different SCI at a lower level, each of the plurality of SCIs having external ports (202/204), at least one of the plurality of SCIs including internal nets (212/214); and for each iteration step of a series of iteration steps: starting from a bottom level of the hierarchy (400), for each respective level of the hierarchy (400) and for each respective SCI at the respective level: obtaining, by a processor (102) of the one or more computer systems (100/152), first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii' ] and [ Ie ']) of the respective SCI, and storing the first submatrix ([ Gie' ]) and the first subvector ([ Ii ']) of the respective SCI in one or more memory devices (106), wherein the first and second subvectors ([ Ii '] and [ Ie' ]) of the respective SCI correspond to respective ones of the first and second submatrices ([ Gie '] and [ Ge' ]) of the respective SCI; wherein, for at least one first SCI of the plurality of SCIs and during at least one of the series of iteration steps, obtaining first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii '] and [ Ie' ]) of the first SCI includes incorporating the second submatrix ([ Ge ']) and the second subvector ([ Ie ']) of each of one or more second SCIs into a circuit equation representing electrical characteristics of the first SCI, and extracting the first and second submatrices ([ Gie '] and [ Ge' ]) and the first and second subvectors ([ Ii '] and [ Ie' ]) of the first SCI from the circuit equation, each of the one or more second SCI being a child of the first SCI; wherein obtaining, by a processor (102) of the one or more computer systems (100/152), first and second submatrices ([Gie'] and [Ge']) and first and second subvectors ([Ii'] and [le']) of the respective SCI includes, by one or more second processors (102) of the one or more computer systems (100/152): obtaining first and second submatrices ([Gie'] and [Ge']) and first and second subvectors ([Ii'] and [le']) of the respective SCI, storing the first submatrix ([Gie']) and the first subvector ([Ii']) of the respective SCI into one or more memory devices (106), and passing the second submatrix ([Ge']) and the second subvector ([Ie']) of the respective SCI to the one or more processors (102); determining, by the one or more processors (102) of the one or more computer systems (100/152), signal values in the top circuit (402), the signal values including signal values at the external ports (202/204) of the top circuit (402) and signal values at the external ports (212/214) of the SCIs at the first level (410) immediately below the top circuit (402); starting from the first level (410) of the hierarchy (400), determining, by the one or more processors (102) of the one or more computer systems (100/152), signal values of each specific SCI at each level of the hierarchy (400), wherein signal values of a third SCI corresponding external signal values of a fourth SCI are passed down to the fourth SCI and used to determine internal signal values of the fourth SCI, together with the first submatrix ([Gie']) and the first subvector ([Ii']) of the fourth SCI stored in the one or more memory devices (106), the fourth SCI being the child of the third SCI.
  2. The method of claim 1, wherein the circuit equation includes a left-hand matrix (G) and a right-hand vector (1), and wherein the first and second submatrices ([G ie '] and [ Ge' ]) of the first SCI are extracted from the left-hand matrix, and the first and second subvectors ([ Ii '] and [ Ie' ]) of the first SCI are extracted from the right-hand vector.
  3. The method of any of claims 1-2, wherein the series of iteration steps include one or more initial iteration steps, wherein, for each iteration step subsequent to the one or more initial iteration steps, obtaining first and second submatrices ([ Gie '] and [ Ge ']) and first and second subvectors ([ Ii '] and [ Ie' ]) of the respective SCI comprises determining whether the respective SCI is an active SCI, and in response to the respective SCI is not an active SCI, reusing first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii '] and [ Ie ']) obtained for the respective SCI in a prior iteration step.
  4. The method of claim 3, wherein determining whether a respective SCI is active comprises determining whether any signal values of the respective SCI has changed more than a preset threshold during previous iteration steps.
  5. The method of any of claims 1-4, wherein the series of iteration steps include one or more initial iteration steps, wherein, for each iteration step subsequent to the one or more initial iteration steps, obtaining first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii' ] and [ Ie' ]) of the respective SCI comprises determining whether the respective SCI is a leaf SCI.
  6. The method of claim 5, further comprising, in response to the respective SCI is a leaf SCI, determining whether the leaf SCI is an active SCI and has corresponding precalculated submatrix templates and subvector templates, and in response to the respective SCI being an active SCI and having precalculated submatrix templates and subvector templates, computing the first and second submatrices ([ Gie '] and [ Ge' ]) and the first and second subvectors ([ Ii '] and [ Ie' ]) of the respective SCI using the precalculated submatrix templates and subvector templates.
  7. The method of claim 6, wherein determining whether a respective SCI is active comprises determining whether any signal value of the respective SCI has changed more than a preset threshold during previous iteration steps.
  8. The method of any of claims 1-7, wherein: obtaining first and second submatrices ([ Gie '] and [ Ge ']) and first and second subvectors ([ Ii '] and [ Ie' ]) of a particular SCI on a particular level of the hierarchy (400) is independent of obtaining first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii '] and [ Ie' ]) of another SCI on the particular level; the one or more computer systems (100/152) include a first computer system (100) and a second computer system (100) coupled to the first computer system (100) by a network (154); the one or more processors (102) include a first processor (102) in the first computer system (100) and a second processor (102) in the second computer system; obtaining first and second submatrices ([G ie '] and [ Ge ']) and first and second subvectors ([ Ii '] and [ Ie ']) of the particular SCI on the particular level is performed by the first processor; and obtaining first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([I i' ] and [ Ie' ]) of the other SCI on the particular level is performed by the second processor (102).
  9. The method of claim 1, wherein: the one or more computer systems (100/152) include a third computer system (100) and a fourth computer system (100) coupled to the third computer system (100) by a network (154); the one or more processors (102) include a third processor (102) in the third computer system (100) and a fourth processor (102) in the fourth computer system; the first and second submatrices ([ Gie '] and [ Ge ']) and first and second subvectors ([Ii'] and [ Ie ']) of the first SCI are obtained by the third processor; and the second submatrix ([Ge']) and the second subvector ([Ie']) of at least one of one or more second SCIs are obtained by the fourth processor; the method further comprising: passing the second submatrix ([Ge']) and the second subvector ([Ie']) of the at least one of one or more second SCIs from the third computer system 100 to the fourth computer system (100) via the network (154).
  10. The method of any of claims 1-9, wherein the one or more processors (102) include a fifth processor (102) and a sixth processor (102), and wherein receiving the netlist (201) comprises receiving a first portion of the netlist (201) by the fifth processor (102) and receiving a second portion of the netlist (201) by the sixth processor (102).
  11. The method of claim 1, wherein the one or more processors (102) include a seventh processor (102) and an eighth processor (102), and wherein receiving the netlist (201) comprises receiving the netlist (201) by the seventh processor (102) and providing at least a portion of the netlist (201) by the seventh processor (102) to the eighth processor (102).
  12. The method of claim 11, wherein the one or more computer systems (100/152) include a first computer system (100) and a second computer system (100) coupled to the first computer system (100) by a network (154), wherein the first processor (102) is in the first computer system (100) and the second processor (102) is in a second computer system, and wherein the at least a portion of the netlist (201) is transmitted by the first computer system (100) to the second computer system (100) via the network (154).
  13. A system configured to perform the method of claim 1 to simulate a circuit (200), the system comprising: a first processor (102) configured to receive at least a first portion of a netlist (201) of the circuit (200), the netlist (201) including a top circuit (402) and a plurality of sub-circuit instances (SCI/412/414/422/424) forming a hierarchy (400) having a first level (410) under the top circuit (402) and at least one second level (420) under the first level (410) such that 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 (402), and that each SCI of the plurality of SCIs is either a leaf in the hierarchy (400) or a parent of a different SCI at a lower level, each of the plurality of SCIs having external ports (202/204), at least one of the plurality of SCIs including internal nets (212/214); and one or more second processors 102 configured to, for each respective SCI of one or more first SCIs of the plurality of SCIs and during at least one of a series of iteration steps, obtain first and second submatrices ([ Gie '] and [ Ge' ]) and first and second subvectors ([ Ii' ] and [ Ie ']) of the respective SCI, storing the first submatrix ([Gie']) and the first subvector ([Ii']) of the respective SCI into one or more memory devices 106, and passing the second submatrix ([Ge']) and the second subvector ([Ie']) of the respective SCI to the first processor; wherein the first processor (102) is further configured to,: incorporating the second submatrix ([Ge']) and the second subvector ([Ie']) of each of the one or more first SCIs into a circuit equation representing electrical characteristics of a second SCI, and extracting first and second submatrices and first and second subvectors ([ Ii' ] and [ Ie' ]) of the second SCI from the circuit equation, the second SCI being a parent of the one or more first SCI.
  14. The system of claim 13, further comprising one or more third processors (102), wherein a processor (102) of the first processor (102), the one or more second processor (102), and the one or more third processor (102) is configured to determine signal values in the top circuit (402), the signal values including signal values at the external ports (202/204) of the top circuit (402) and signal values at the external ports (202/204) of the SCIs at the first level (410) immediately below the top circuit (402).
  15. The system of claim 14, wherein one or more processors (102) of the first processor (102), the one or more second processors (102), and the one or more third processors (102) are configured to: starting from the first level (410) of the hierarchy (400), determine signal values of each specific SCI at each level of the hierarchy (400), wherein signal values of a third SCI corresponding external signal values of a fourth SCI are passed down to the fourth SCI so that internal signal values of the fourth SCI are determined using the signal values of the third SCI and the first submatrix ([Gie']) and the first subvector ([Ii']) of the fourth SCI stored in the one or more memory devices (106), the fourth SCI being the child of the third SCI.

Description

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. Exemplary prior art is disclosed in publications US 2006/161413 A1, US 6 577 992 B1, US 6 807 520 B1 and US 7 181 383 B1. SUMMARY The invention is set out in the appended claims. In some embodiments, a method to simulate a hierarchical circuit is performed using one or more computer systems. The one or more computer systems receive a hierarchical circuit netlist including a top circuit and a plurality of sub-circuit instances (SCIs) in a hierarchy, or receive a flat circuit netlist and partition the flat circuit into a hierarchical circuit netlist. The hierarchy includes a first level under the top circuit and at least one second level under the first level such that 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. In some embodiments, each level of the hierarchy includes at least one SCI, each of the plurality of SCIs have external ports, and at least one of the plurality of SCIs also includes internal nets. In certain embodiment, the method can be performed through a series of iteration rounds. Each iteration round includes a bottom-up process to generate circuit equations for each SCI and the top circuit, followed by a top-down process to solve the circuit equations for the top circuit and the SCIs in the hierarchy. In each iteration round, the bottom-up process starts from the bottom level of the hierarchy and moves up the hierarchy one level at a time. For each level in the hierarchy and for each SCI in the level, the bottom-up process obtains first and second submatrices and first and second subvectors for the SCI. The first and second subvectors correspond to respective ones of the first and second submatrices. The first submatrix and the first subvector are then stored in one or more memory devices. The second submatrix and the second subvector are passed up to the next level in the hierarchy and incorporated into the circuit equations of a parent SCI. In certain embodiments, multiple computer systems or multiple processors in one or more computer system can be used to generate the circuit equations and to extract the submatrices and subvectors for different SCIs at the same or different hierarchical levels in parallel. In certain embodiments, access to the second submatrix and the second subvector of a child SCI extracted by a first processor in a first computer system is passed or provided to a second processor in the first or a second computer system, which is used to generate the circuit equation of the parent SCI. During the same iteration round, in the top-down process, the one or more computer systems further determines signal values in the top circuit, the signal values including signal values at the external ports of the SCIs at the first level immediately below the top circuit. Then, starting from the first level of the hierarchy, the one or more computer systems proceeds to determine external and internal signal values of each SCI at each level of the hierarchy. The external signal values of each SCI are passed down from its parent SCI or the top circuit, and are used, together the first submatrix and the first subvector of the SCI, to compute the internal signal values of the SCI. 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