Hierarchical partitioning

• US 7,555,733 B1
• Filed: 09/18/2006
• Issued: 06/30/2009
• Est. Priority Date: 09/18/2005
• Status: Active Grant

• Current Assignee: Infinisim, Inc.
• Original Assignee: Infinisim, Inc.
• Inventors: Gee, Perry, Hussain, Syed Zakir
• Primary Examiner(s): Whitmore; Stacy A
• Assistant Examiner(s): Dimyan; Magid Y
• Application Number:
  US11/532,898
• Time in Patent Office: 1,016 Days
• Field of Search: 716/1, 716/5, 716/7, 716/8
• US Class Current: 716/106
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

Some embodiments provide a method of simulating an electrical circuit that receives a circuit description that has a set of sub-circuits. The method defines several partitions for several sub-circuits. The method then simulates the circuit using the partitioned sub-circuits. In some embodiments, the method ranks the sub-circuits prior to partitioning based on a parent-child relationship that shows how a sub-circuit is instantiated by other sub-circuits. These embodiments partition child sub-circuits first. Some embodiments provide a method of partitioning an electrical circuit that has a set of sub-circuits. For a particular sub-circuit that is instantiated from other sub-circuits, the method duplicates the particular sub-circuit into a first copy and a second copy when one port of the particular sub-circuit is connected to a voltage source in at least one instance and the same port is not connected to a voltage source in at least another instance.

Claims

1. A method for simulating an electrical circuit, the method comprising:

a. receiving a circuit description comprising a set of sub-circuit descriptions;

b. defining a plurality of partitions for each of at least a plurality of sub-circuits;

c. performing a simulation of the circuit using the partitions for the sub-circuits;

d. prior to said defining the plurality of partitions, determining whether at least one particular port of a child sub-circuit is connected to a voltage source in a first instantiated instance while the particular port is not connected to a voltage source in a second instantiated instance;

e. creating a duplicate copy of said child sub-circuit; and

f. storing data indicative of the results of said simulation.

2. The method of claim 1 further comprising:

a. ranking the sub-circuits prior to defining the plurality of partitions, wherein said ranking is based on a parent-child relationship showing how each sub-circuit is instantiated by other sub-circuits; and

b. defining partitions for child sub-circuits first.

3. The method of claim 1 further comprising:

a. referencing a first copy of the child sub-circuit when the child sub-circuit is instantiated by a parent sub-circuit in which said port is connected to a voltage source; and

b. referencing a second copy of the child sub-circuit when the child sub-circuit is instantiated by a parent sub-circuit in which said port is not connected to a voltage source.

4. The method of claim 1, wherein defining the plurality of partitions comprises:

for all device terminals in the same partition, grouping all nets connected to those terminals unless said nets are voltage source nets, wherein a net is a connection on a device.

5. The method of claim 4, wherein defining the plurality of partitions further comprises:

a. grouping devices of a sub-circuit together in a plurality of partitions;

b. computing a level for each partition, wherein the level of a partition identifies a distance that the partition has from primary inputs to the circuit;

c. identifying partitions that form feedback loops in each sub-circuit; and

d. merging said identified partitions.

6. A computer readable medium storing a computer program for simulating an electrical circuit, the computer program executable by at least one processor, said computer program comprising:

a. a set of instructions for receiving a circuit description comprising a set of sub-circuit descriptions;

b. a set of instructions for defining a plurality of partitions for each of at least a plurality of sub-circuits;

c. a set of instructions for simulating the circuit using the partitions for the sub-circuits;

d. a set of instructions for, prior to said defining the plurality of partitions, determining whether at least one particular port of a child sub-circuit is connected to a voltage source in a first instantiated instance while the particular port is not connected to a voltage source in a second instantiated instance; and

e. a set of instructions for creating a duplicate copy of said child sub-circuit.

7. The computer readable medium of claim 6, wherein said program further comprises a set of instructions for:

a. ranking the sub-circuits prior to defining the plurality of partitions, wherein said ranking is based on a parent-child relationship showing how each sub-circuit is instantiated by other sub-circuits; and

b. defining partitions for child sub-circuits first.

8. The computer readable medium of claim 6, wherein said program further comprises:

a. a set of instructions for referencing a first copy of the child sub-circuit when the child sub-circuit is instantiated by a parent sub-circuit in which said port is connected to a voltage source; and

b. a set of instructions for referencing a second copy of the child sub-circuit when the child sub-circuit is instantiated by a parent sub-circuit in which said port is not connected to a voltage source.

9. The computer readable medium of claim 6, wherein said program further comprises:

a set of instructions for grouping all nets connected to device terminals in a same partition unless said nets are voltage source nets, wherein a net is a connection on a device.

10. A computer readable medium storing a computer program for simulating an electrical circuit, the computer program executable by at least one processor, said computer program comprising:

a. a set of instructions for receiving a circuit description comprising a set of sub-circuit descriptions;

b. a set of instructions for defining a plurality of partitions for each of at least a plurality of sub-circuits;

c. a set of instructions for simulating the circuit using the partitions for the sub-circuits;

d. a set of instructions for grouping all nets connected to device terminals in a same partition unless said nets are voltage source nets, wherein a net is a connection on a device;

e. a set of instructions for grouping devices of a sub-circuit together in a plurality of partitions;

f. a set of instructions for computing a level for each partition, wherein the level of a partition identifies a distance that the partition has from primary inputs to the circuit;

g. a set of instructions for identifying partitions that form feedback loops in each sub-circuit; and

h. a set of instructions for merging said identified partitions.

11. A computer readable medium storing a computer program for simulating an electrical circuit, said computer program having a set of instructions for:

a. receiving a circuit description comprising a set of sub-circuit descriptions;

b. identifying whether a sub-circuit is instantiated from other sub-circuits; and

c. for a particular sub-circuit that is instantiated from other sub-circuits, duplicating the particular sub-circuit into a first copy and a second copy when one port of the particular sub-circuit is connected to a voltage source in at least one instance and the same port is not connected to a voltage source in at least another instance.

12. The computer readable medium of claim 11, wherein said program further comprises a set of instructions for:

a. referencing the first copy when the particular sub-circuit is instantiated by another sub-circuit in which said port is connected to a voltage source; and

b. referencing the second copy when the particular sub-circuit is instantiated by another sub-circuit in which said port is not connected to a voltage source.