US5481473A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for building interconnections in a hierarchical circuit design
Assignee: International Business Machines Corp
•
Filing: 1993-02-19
•
Granted: 1996-01-02
•
Expires: 2013-02-19
Abstract
Abstract A computer-based system and method is provided for creating a representation of interconnections between VLSI circuit design components. A VLSI circuit design component identifying a leaf design entity is stored in memory. Placements in the design where the design component appears are stored in memory. A set of links is formed to connect placements to one another. The links further specify placement of the design component in the circuit design. The interconnections themselves are then computed. The interconnections denote where placements of the VLSI circuit design component instances are interconnected, and may specify any meaningful coupling, such as electrical conductivity, magnetic, or optical. The interconnections are represented by a nested net graph which includes a list of nets, and instance counts associated with the nets. The nested net graph may also include a second list, which specifies instances of lower nested nets contained in the nested net graph. The nested net graph may further include a shape-to-net table attached at the root of the nested net graph. The shape-to-net table defines a mapping from the VLSI circuit design component to a corresponding net. Also provided is a system and method for building interconnections using a bridge component, or bridge net. The bridge net denotes the interconnection between two nets derived from a pair of VLSI circuit design component instances.
Inventors
- 👤 Young O. Kim
- 👤 Philip J. Russell
- 👤 Glenwood S. Weinert
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 23:02
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
152 words
A computer-implemented method for creating in computer memory a representation of interconnections between very large scale integrated (VLSI) circuit design components of a hierarchical circuit design, comprising the steps of: storing in the computer memory a VLSI circuit design component identifying a leaf design entity from the hierarchical circuit design; storing in the computer memory a set of placements in the design where the VLSI circuit design component appears, the placements representing a subset of instances of the leaf design entity; associating with the VLSI circuit design component and the placements a set of links, the links connecting various ones of the placements to one another to further denote placement of the VLSI circuit design component within the hierarchical circuit design; storing the set of links in the computer memory; computing interconnections denoting where placements of instances of VLSI circuit design components are interconnected; and storing the interconnections in the computer memory.
Claim 2
Dependent Claim
152 words
A computer-implemented method for creating in computer memory a representation of interconnections between very large scale integrated (VLSI) circuit design components of a hierarchical circuit design, comprising the steps of: storing in the computer memory a VLSI circuit design component identifying a leaf design entity from the hierarchical circuit design; storing in the computer memory a set of placements in the design where the VLSI circuit design component appears, the placements representing a subset of instances of the leaf design entity; associating with the VLSI circuit design component and the placements a set of links, the links connecting various ones of the placements to one another to further denote placement of the VLSI circuit design component within the hierarchical circuit design; storing the set of links in the computer memory; computing interconnections denoting where placements of instances of VLSI circuit design components are interconnected; and storing the interconnections in the computer memory.
Claim 3
Dependent Claim
78 words
The method as recited in claim 1, further comprising the steps of: representing the interconnections by a nested net graph; and associating with the nested net graph a first list of nets and instance counts, each instance count including a first number and a second number, the second number denoting a quantity of instances of the net that could be represented at an associated node, the first number denoting a quantity of instances actually represented at the node.
Claim 4
Dependent Claim
33 words
The method as recited in claim 2, further comprising the step of associating with the nested net graph a second list denoting instances of lower nested nets contained in the nested net graph.
Claim 5
Dependent Claim
31 words
The method as recited in claim 3, wherein the nested net graph is used for determining net membership of a shape instance and determining nested shape components of a subject net.
Claim 6
Dependent Claim
38 words
The method as recited in claim 2, further comprising the step of forming a shape-to-net table at a root of the nested net graph to define a mapping from the VLSI circuit design component to a corresponding net.
Claim 7
Dependent Claim
154 words
A computer system for creating a representation of interconnections between very large scale integrated (VLSI) circuit design components of a hierarchical circuit design, comprising: a computer memory storing a VLSI circuit design component identifying a leaf design entity from the hierarchical circuit design and a set of placements in the design where the VLSI circuit design component appears, the placements representing a subset of instances of the leaf design entity; and processor means for accessing the computer memory and associating with the VLSI circuit design component and the placements a set of links, the links connecting various ones of the placements to one another to further denote placement of the VLSI circuit design component within the hierarchical circuit design and storing the set of links in the computer memory, said processor means computing interconnections denoting where placements of instances of VLSI circuit design components are interconnected and storing the interconnections in the computer memory.
Claim 8
Dependent Claim
154 words
A computer system for creating a representation of interconnections between very large scale integrated (VLSI) circuit design components of a hierarchical circuit design, comprising: a computer memory storing a VLSI circuit design component identifying a leaf design entity from the hierarchical circuit design and a set of placements in the design where the VLSI circuit design component appears, the placements representing a subset of instances of the leaf design entity; and processor means for accessing the computer memory and associating with the VLSI circuit design component and the placements a set of links, the links connecting various ones of the placements to one another to further denote placement of the VLSI circuit design component within the hierarchical circuit design and storing the set of links in the computer memory, said processor means computing interconnections denoting where placements of instances of VLSI circuit design components are interconnected and storing the interconnections in the computer memory.
Claim 9
Dependent Claim
80 words
The system as recited in claim 6, wherein the interconnections are represented in computer memory by a nested net graph, the nested net graph including a first list of nets and instance counts associated with the nets, each instance count including a first number and a second number, the second number denoting a quantity of instances of the net that could be represented at an associated node, the first number denoting a quantity of instances actually represented at the node.
Claim 10
Dependent Claim
29 words
The system as recited in claim 7, wherein the nested net graph further includes a second list denoting instances of lower nested nets contained in the nested net graph.
Claim 11
Dependent Claim
31 words
The system as recited in claim 8, wherein the nested net graph is used for determining net membership of a shape instance and determining nested shape components of a subject net.
Claim 12
Dependent Claim
38 words
The system as recited in claim 7, further comprising the step of forming a shape-to-net table at a root of the nested net graph to define a mapping from the VLSI circuit design component to a corresponding net.
Claim 13
Dependent Claim
139 words
A computer-implemented method for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising the steps of: computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in a placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph; identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph; comparing the net numbers obtained from the identifying step with one another; and if the net numbers are different from one another, forming from the two nets a single net.
Claim 14
Dependent Claim
139 words
A computer-implemented method for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising the steps of: computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in a placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph; identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph; comparing the net numbers obtained from the identifying step with one another; and if the net numbers are different from one another, forming from the two nets a single net.
Claim 15
Dependent Claim
92 words
The method as recited in claim 11, wherein the identifying step further comprises the substep of recursively following an ancestor sub-graph of the placement graph starting at a leaf node of an inverse graph and (a) if a present ancestor node is not a root of the ancestor sub-graph of the placement graph, inserting into the nested net graph an instance of the net of the ancestor node, (b) if the present ancestor node or the leaf node is the root of the placement graph, associating a net number with the root.
Claim 16
Dependent Claim
38 words
The method as recited in claim 12, wherein substep (a) further includes updating a net membership list to indicate that the instance of the net at the ancestor node is contained in the net at the leaf node.
Claim 17
Dependent Claim
154 words
A computer system for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising: a computer memory storing the hierarchical circuit design; processor means for accessing the computer memory and computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in a placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph, said processor means identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph, said processor means comparing the identified net numbers with one another and forming from the two nets a single net if the net numbers are different from one another.
Claim 18
Dependent Claim
154 words
A computer system for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising: a computer memory storing the hierarchical circuit design; processor means for accessing the computer memory and computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in a placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph, said processor means identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph, said processor means comparing the identified net numbers with one another and forming from the two nets a single net if the net numbers are different from one another.
Claim 19
Dependent Claim
87 words
The system as recited in claim 14, wherein the processor means recursively follows an ancestor sub-graph of the placement graph starting at a leaf node of an inverse graph and (a) if a present ancestor node is not a root of the ancestor sub-graph of the placement graph, inserts into the nested net graph an instance of the net of the ancestor node, (b) if the present ancestor node or the leaf node is the root of the placement graph, associates a net number with the root.
Claim 20
Dependent Claim
43 words
The system as recited in claim 15, wherein if condition (a) is true, the processor means further updates a net membership list to indicate that the instance of the net at the ancestor node is contained in the net at the leaf node.
Claim 21
Dependent Claim
180 words
A computer-implemented method for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising the steps of: computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in an inverse placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph; identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph; comparing the net numbers obtained from the identifying step with one another; if the net numbers are different from one another, determining for each VLSI circuit design component in the pair whether the VLSI circuit design component is a bridge component which denotes an interconnection between two nets; and if either VLSI circuit design component in the pair is a bridge component, forming a bridge interconnection between the two nets.
Claim 22
Dependent Claim
180 words
A computer-implemented method for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising the steps of: computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in an inverse placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph; identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph; comparing the net numbers obtained from the identifying step with one another; if the net numbers are different from one another, determining for each VLSI circuit design component in the pair whether the VLSI circuit design component is a bridge component which denotes an interconnection between two nets; and if either VLSI circuit design component in the pair is a bridge component, forming a bridge interconnection between the two nets.
Claim 23
Dependent Claim
204 words
A computer system for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising: a computer memory storing the hierarchical circuit design; and processor means for accessing the computer memory and computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in an inverse placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph, said processor means identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph and comparing the identified net numbers with one another; said processor means invoking a first process, if the net numbers are different from one another, for determining for each VLSI circuit design component in the pair whether the VLSI circuit design component is a bridge component and invoking a second process, if the VLSI circuit design component is a bridge component which denotes an interconnection between two nets, for forming a bridge interconnection between the two nets.
Claim 24
Dependent Claim
204 words
A computer system for building a representation of interconnections between instances of very large scale integrated (VLSI) circuit design components in a hierarchical circuit design, comprising: a computer memory storing the hierarchical circuit design; and processor means for accessing the computer memory and computing a pair of VLSI circuit design component instances where an interconnection occurs, the pair being denoted as instances of VLSI circuit design components in an inverse placement graph, the pair having a common leaf node where the instances are interconnected, the common leaf node defining an interconnect node in a nested net graph, said processor means identifying each instance of the pair as a net having a net number associated therewith, the net being in the interconnect node of the nested net graph and comparing the identified net numbers with one another; said processor means invoking a first process, if the net numbers are different from one another, for determining for each VLSI circuit design component in the pair whether the VLSI circuit design component is a bridge component and invoking a second process, if the VLSI circuit design component is a bridge component which denotes an interconnection between two nets, for forming a bridge interconnection between the two nets.
References Cited (Backward Citations)
US4554625A
Cited
US4831543A
Cited
US5267175A
Cited
US4815003A
Cited
US5146583A
Cited
US5262959A
Cited
US5249133A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-01 | 1999-07-03 | 2000-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-01 | 2003-07-03 | 2004-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-01 | 2007-07-03 | 2008-01-02 | $7700.00 | Window Closed / Lapsed |