Pattern-matching for transistor level netlists

A method of matching a pattern sub-circuit in a master circuit design, the master circuit design being both formed by a plurality of master devices interconnected by master nets and modeled as a graph, and the pattern sub-circuit being formed by a plurality of pattern devices interconnected by pattern nets and modeled as a graph, wherein both nets and devices are explicitly modeled as nodes in the graphs, enabling rooted sub-graph isomorphism and enabling both exact and inexact pattern matching using a single pattern matching engine, the method comprising the steps of:

• a) defining an explicit net comparison function that enables both the exact matching and the inexact matching of the pattern net to a master net, where an inexact match is a match to a master net which is connected to a power supply or to a net which is already matched to another pattern net;
• b) defining an explicit device comparison function that enables the exact matching of the pattern device to the master device based on a device characteristic;
• c) defining a node comparison function which compares two device nodes using the explicit device comparison function or compares two net nodes using the explicit net comparison function;
• d) inputting of a master candidate;
• e) identifying a set of pattern keynodes in the pattern sub-circuit for which the node comparison function is indicative of a potential match between the master candidate and a node in the pattern sub-circuit;
• f) iterating over the set of pattern keynodes;
• g) for each of the pattern keynodes, exploring a potential match of the pattern in the master circuit design containing the master candidate;
• and
• h) repeating steps f) and g) until all instances of the pattern in the master circuit design which contain the master candidate have been identified and invoking a user-supplied function for each of the instances to enable circuit design analysis, verification or optimization prior to its manufacture.

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for matching a pattern sub-circuit in a master circuit design, the master circuit design being both formed by a plurality of master devices interconnected by master nets and modeled as a graph, and the pattern sub-circuit being formed by a plurality of pattern devices interconnected by pattern nets and modeled as a graph, wherein both nets and devices are explicitly modeled as nodes in the graphs, enabling both exact and inexact pattern matching using a single pattern matching engine, the method comprising the steps of:

• a) defining an explicit net comparison function that enables both the exact matching and the inexact matching of the pattern net to a master net which is connected to a power supply or to a net which is already matched to another pattern net;
• b) defining an explicit device comparison function that enables the exact matching of the pattern device to the master device based on a device characteristic;
• c) defining a node comparison function which compares two device nodes using the explicit device comparison function or compares two net nodes using the explicit net comparison function;
• d) identifying a pattern keynode;
• e) identifying a set of candidate nodes in the master circuit design for which the node comparison function is indicative of a potential match between the pattern keynode and a node in the master circuit design;
• f) iterating over a set of master candidate nodes;
• g) for each of the master candidate nodes, exploring a potential match of the pattern in the master circuit design containing the candidate node, and
• h) repeating steps f) and g) until all instances of the pattern in the master circuit design have been identified and invoking a user-supplied function for each of the instances to enable circuit design analysis, verification or optimization prior to its manufacture.