Method of labelling swappable pins for integrated circuit pattern matching
The present invention seeks to provide a simple, but novel regime, for re-labelling swappable pins that permits swappability information to be maintained without significantly increasing computational complexity and is conducive to inexact pattern matching for the purposes of developing more complex logical processing blocks from elementary components in design analysis. The method comprises a recursive application of a simple labelling procedure. This method is repeated recursively until all gate instances in the circuit fragment have been assigned a swappability number.
1. A method of assigning labels to nodes of integrated circuit components to indicate swappability relationships between the nodes, the method comprising the steps of:
(a) identifying a first gate instance without an assigned label;
(b) determining if each input node associated with the identified gate instance has a common swappability characteristic, wherein the common swappability characteristic is chosen from the group consisting of: the node is swappable with any other input node, associated with the identified gate instance, and the node is not swappable with any other input node, associated with the identified gate instance;
(c) for each input node associated with the identified gate instance that is swappable with any other input node thereof, creating a common node between the swappable input nodes and linking the common node to the identified gate instance, and assigning each swappable input node a first set of swappability labels, using a computer;
(d) for each input node associated with the identified gate instance that is not swappable with any other input node thereof, assigning each non-swappable input node a second set of swappability labels; and
(e) repeating all previous steps for each gate instance until no gate instances remain with unassigned labels, such that labeled nodes contain information regarding the swappability of input nodes that is used for circuit analysis.
2. A method as in claim 1 , wherein steps (b) through (d) are performed for groups of nodes that have a common swappability characteristic between them, wherein a swappability label is assigned to them to identify the common swappability between the groups of nodes.
3. A method of assigning labels according to claim 1 , wherein the first set of swappability labels comprises a single label.
4. A method of assigning labels according to claim 1 , where the second set of swappability labels are all different.
5. A method of assigning labels according to claim 1 , wherein swappability labels are reused for different gate instances.
6. A method of assigning labels according to claim 1 , wherein each output node associated with a gate instance is assigned a swappability label that is different from those assigned to the input nodes associated therewith.
7. A method of assigning labels according to claim 6 , wherein if an output node associated with a gate instance is swappable with another output node associated therewith, the swappability labels assigned thereto are the same.
8. A method of assigning labels according to claim 6 , wherein if an output node associated with a gate instance is not swappable with another output node associated therewith, the swappability labels assigned thereto are different.
9. A system for assigning labels to nodes of integrated circuit components to indicate swappability relationships between the nodes, the system comprising a computer and a computer-accessible memory storing instructions for execution by the computer, the instructions comprising:
a software module for identifying a first gate instance without an assigned label;
a software module for determining if each input node associated with the identified gate instance has a common swappability characteristic, wherein the common swappability characteristic is chosen from the group consisting of: the node is swappable with any other input node, associated with the identified gate instance, and the node is not swappable with any other input node, associated with the identified gate instance;
a software module, executable for each input node associated with the identified gate instance that is swappable with any other input node thereof, for creating a common node between the swappable input nodes and linking the common node to the identified gate instance, and for assigning each swappable input node a first set of swappability labels;
a software module, executable for each input node associated with the identified gate instance that is not swappable with any other input node thereof, for assigning each non-swappable input node a second set of swappability labels; and
a software module for repeating all previous steps for each gate instance until no gate instances remain with unassigned labels, such that labeled nodes contain information regarding the swappability of input nodes that is used for circuit analysis.
10. A non-transitory computer-readable medium having computer-executable instructions, when executed by a computer, that cause the computer to perform the method of claim 1 .