Method of adding constrained cluster points to interconnection nets in integrated circuit chips and packages

• US 6,014,508 A
• Filed: 08/11/1997
• Issued: 01/11/2000
• Est. Priority Date: 08/11/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Martin, Cynthia L., Bauer, Hope L., Selinger, Craig R., Christian, Kenneth L., Dhaliwal, Hardev S.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/909,112
• Time in Patent Office: 883 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/500.03, 395/500.14, 395/500.09, 395/500.13, 395/500.15
• US Class Current: 716/112
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method of wiring a plurality of integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net that includes a plurality of nodes to be interconnected. The interconnected nodes are designed to meet system requirements, commonly expressed by a set of wiring rules, include among others, physical, electrical and noise constraints. The method includes matching interconnection net attributes to wiring rule logical definitions, wherein the wiring rules include rule nodes and rule connections. The rule nodes define constraints for the pins, vias and cluster point structures. The rule connections define wiring constraints between the node structures to establish the net topology. The process described is based on net ordering and checking. The net ordering, which defines the pin-to-pin connections based on the wiring rule, is performed prior to chip or package wiring. Net ordering imposes the wiring rule added cluster points, the desired interconnection topology and the wiring constraints to the net. Checking verifies the correctness of the net attributes when the design wiring is complete.

Claims

1. A method of wiring a plurality of integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net comprising a plurality of nodes to be interconnected while ensuring that the interconnected nodes meet system requirements that include physical, electrical and noise constraints, wherein the system requirements are expressed by wiring rules, the method comprising the steps of:

a) building a trace structure comprising;

i) a plurality of rule nodes, each of the rule nodes comprising at least one rule node constraint;

ii) a plurality of net node lists associated with the rule nodes, each of the net node lists comprising net nodes having first attributes that meet the rule node constraints; and

iii) a plurality of rule connections, each of the rule connections comprising connection constraints to be imposed on a pair of the rule nodes;

b) successively linking each of the rule nodes to each of the rule connections until all the rule nodes have been linked, thereby forming the net; and

c) matching the rule connection constraints to second attributes associated with the pair of rules nodes, wherein;

when the matching is successful, the rule connection constraints are imposed on the pair of rule nodes;

when the matching is successful and the net node list of at least one pair of the rule nodes is empty, at least one cluster point is added to the net; and

when the matching is unsuccessful, the connection between the linked rule nodes is flagged as violating the wiring rules.

2. The method as recited in claim 1, wherein each of the rule connections includes from-to constraints and min-max constraints.

3. The method as recited in claim 1, wherein the first attributes are selected from the group consisting of drivers, receivers, IO types, component names and component functions.

4. The method as recited in claim 1, wherein the second attributes include a wiring interconnection length and/or a wiring interconnection delay.

5. The method as recited in step c) of claim 1, further comprising the steps of:

d) selecting a first one of the rule connections and assigning a `from` attribute to the first net node in the net node list and characterizing as used the net node having the assigned `from` attribute;

e) assigning a `to` node to a first unused net node in the net node list to form a potential interconnection, wherein

i) if the assignment is successful by finding the unused net node, the potential interconnection is validated, and the `to` node of a next one of the rule connections is allocated to the first unused net node in the net node list;

ii) if the unused net node in the net node list is not found, the assignment is deemed unsuccessful, and another `to` node is selected out of a previous one of the rule connections;

iii) if the assignment is successful, step i) is repeated until an end of a rule connection list comprising ordered rule connections is reached; and

iv) if the unused net node in the net node list is not found while at the beginning of the rule connection list, then another net node is selected.

6. The method as recited in step i) of claim 5, wherein the validation of the potential interconnection is based on an estimated routed wire attribute or an actual routed wire attribute.

7. The method as recited in steps i) and ii) of claim 5, further comprising the steps of:

recording a failure of the validation when no previous rule connection in the rule connection list is available; and

recording a success of the validation when a next rule connection in the rule connection list is not available; and

adding at least a cluster point and constraints to the validated net when success is recorded.

8. The method as recited in claim 7, wherein no cluster point is added to the validated net in the event that no cluster point is defined by the wiring rules.

9. A method of wiring a plurality of integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net comprising a plurality of nodes to be interconnected while ensuring that the interconnected nodes meet system requirements that include physical, electrical and noise constraints, wherein the system requirements are expressed by wiring rules, the method comprising the steps of:

a) designing the integrated circuit chip or package;

b) building a trace structure comprising;

i) a plurality of rule nodes, each of the rule nodes comprising at least one rule node constraint;

ii) a plurality of net node lists associated with the rule nodes, each of the net node lists comprising net nodes having first attributes that meet the rule node constraints; and

iii) a plurality of rule connections, each of the rule connections comprising rule connection constraints to be imposed on a pair of the rule nodes;

c) successively linking each of the rule nodes to each of the rule connections until the rule nodes have all been linked, thereby forming the net; and

d) matching the rule connection constraints to second attributes associated with the pair of rule nodes, wherein;

when the matching is successful, the rule connection constraints are imposed on the pair of rule nodes;

when the matching is successful and the net node list of at least one pair of the rule nodes is empty, then at least one cluster point is added to the net; and

when the matching is unsuccessful, the interconnection between the linked rule nodes is flagged as violating the wiring rules; and

e) fabricating the integrated circuit chip or package having the added cluster points and the interconnection constraints to each of the nets that were successfully matched as determined in the prior steps.

10. The method as recited in step d) of claim 9, further comprising the steps of:

a) selecting a first one of the rule connections and assigning a `from` attribute to the first net node in the net node list and flagging the net node having the assigned `from` attribute as used;

b) assigning a `to` node to a first unused net node in the net node list, thereby forming a potential interconnection;

i) if the unused net node in the net list is found, thereby making the assignment successful, the potential interconnection is validated, and the `to` node of a next one of the rule connections is allocated to the first unused net node in the net node list;

ii) if the unused net node in the net node list is not found, thereby making the assignment unsuccessful, then another `to` node is selected out of a previous one of the rule connections;

iii) if the assignment is successful, then step i) is repeated until an end of the rule connections is reached; and

iv) if the unused net node in the net node list is not found while at the beginning of the rule connections, then another net node from the rule connection is selected.

11. A system for wiring integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net comprising a plurality of nodes to be interconnected while ensuring that the interconnected nodes meet system requirements that include physical, electrical and noise constraints, wherein the system requirements are expressed by wiring rules, the system comprising:

a) means for building a trace structure comprising;

i) a plurality of rule nodes, each of the rule nodes comprising at least one rule node constraint;

ii) a plurality of net node lists associated with the rule nodes, each of the net node lists comprising net nodes having first attributes that meet the rule node constraints; and

iii) a plurality of rule connections, each of the rule connections comprising rule connection constraints to be imposed on a pair of the rule nodes;

b) means for successively linking each of the net rule nodes to each of the rule connections until all the rule nodes have been linked, thereby forming the net; and

c) means for matching the rule connection constraints to second attributes associated with the pair of rule nodes, wherein;

when the matching is successful, the rule connection constraints are imposed on the pair of rule nodes;

when the matching is successful and the net node list of at least one pair of the rule nodes is empty, at least one cluster point is added to the net; and

when the matching is unsuccessful, the connection between the linked rule nodes is flagged as violating wiring the rules.

12. The system as recited in claim 11, wherein each of the rule connections includes from-to constraints and min-max constraints.

13. The system as recited in claim 11, wherein the first attributes are selected from the group consisting of drivers, receivers, IO types, component names and component functions.

14. The system as recited in claim 11, wherein the second attributes include a wiring interconnection length and/or a wiring interconnection delay.

15. The means for matching as recited in claim 11, further comprising:

d) means for selecting a first one of the rule connections and means for assigning a `from` attribute to the first net node in the net node list and characterizing as used the net node having the assigned `from` attribute;

e) means for assigning a `to` node to a first unused net node in the net node list, thereby forming a potential interconnection, wherein

i) if the assignment is successful by finding the unused net node, the potential interconnection is validated, and the `to` node of a next one of the rule connections is allocated to the first unused net node in the net node list;

ii) if the unused net node in the net node list is not found, the assignment is deemed unsuccessful, and another `to` node is selected out of a previous one of the rule connections;

iii) if the assignment is successful, step i) is repeated until an end of the rule connection is reached; and

iv) if the unused net node in the net node list is not found while at the beginning of the rule connections, then another net node from the rule connections is selected.

16. The system as recited in claim 15, wherein the means for validating the potential interconnection includes an estimated routed wire attribute or an actual routed wire attribute.

17. The system as recited in claim 15, further comprising:

means for recording a failure of the validation when no previous rule connection in the rule connection list is available; and

means for recording a success of the validation when a next rule connection in the rule connection list is not available; and

means for adding at least a cluster point and constraints to the validated net when success is recorded.

18. The system as recited in claim 17, wherein no cluster point is added to the validated net in the event that no cluster point is defined by the wiring rules.

19. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for wiring a plurality of integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net comprising a plurality of nodes to be interconnected while ensuring that the interconnected nodes meet system requirements that include physical, electrical and noise constraints, wherein the system requirements are expressed by wiring rules, the method comprising the steps of:

a) building a trace structure comprising;

i) a plurality of rule nodes, each of the rule nodes comprising at least one rule node constraint;

ii) a plurality of net node lists associated with rule nodes, each of the net node lists comprising net nodes having first attributes that meet the rule node constraints; and

iii) a plurality of rule connections, each of the rule connections comprising rule connection constraints to be imposed on a pair of the rule nodes;

b) successively linking each of the rule nodes to each of the rule connections until all the rule nodes have been linked; and

c) matching the rule connection constraints to second attributes associated with the pair of rule nodes, wherein;

when the matching is successful, the rule connection constraints are imposed on the pair of rule nodes;

when the matching is successful and the net node list of at least one pair of the rule nodes is empty, then at least one cluster point is added to the net; and

when the matching is unsuccessful, the connection between the linked rule nodes is flagged as violating the wiring rules.

20. A computer program product for wiring integrated circuits within a chip or between chips in one or more packages by adding cluster points to a net comprising a plurality of nodes to be interconnected while ensuring that the interconnected nodes meet system requirements that include physical, electrical and noise constraints, wherein the system requirements are expressed by wiring rules, the computer program product comprising:

a) a computer usable medium having computer readable program code means embodied therein for a causing a computer to effect a means for building a trace structure comprising;

i) a plurality of rule nodes, each of the rule nodes comprising of at least one rule node constraint;

ii) a plurality of net node lists associated with the rule nodes, each of the net node lists comprising net nodes having first attributes that meet the rule node constraints; and

iii) a plurality of rule connections, each of the rule connections comprising rule connection constraints to be imposed on a pair of the rule nodes;

b) a computer usable medium having computer readable program code means embodied therein for a causing a computer to effect a means for successively linking each of the net rule nodes to each of the rule connections until all the rule nodes have been linked; and

c) a computer usable medium having computer readable program code means embodied therein for a causing a computer to effect a means for matching the rule connection constraints to second attributes associated with the pair of linked rule nodes, wherein;

when the matching is successful, the rule connections constraints are imposed on the pair of linked rule nodes;

when the matching is successful and the net node list of at least one of the pairs of the linked rule nodes is empty, at least one cluster point is added to the net; and

when the matching is unsuccessful, the connection between the linked rule nodes is flagged as violating wiring the rules.