Reuse of circuit labels in subcircuit recognition

A non-transitory computer readable medium having program instructions which when executed by a computer performs pattern matching in a main netlist, the computer readable medium comprising:

• (a) program instructions for reading in the main netlist;
• (b) program instructions for reading in a pattern, the pattern used for finding matches in the main netlist, wherein the main netlist and the pattern include a plurality of vertices, each of the vertices being a net or a device;
• (c) program instructions for computing labels for each of the vertices in both the main netlist and the pattern up to a depth appropriate for the pattern, wherein the label for each of the vertices is computed through iterative relabeling to encode topology surrounding and including each of the vertices such that the vertices with matching topology are assigned a same label in both the pattern and the main netlist;
• (d) program instructions for matching a vertex of the pattern with one or more vertices of the main netlist using the computed labels;
• (e) program instructions for storing the computed labels including data related to depth for each of the vertices in the main netlist;
• (f) program instructions for reading in a next pattern to be the pattern;
• and
• (g) program instructions for performing operations (c)-(e),
• wherein the matching of the next pattern is performed by determining a depth of the next pattern and reusing stored labels computed for the main netlist when the depth of the next pattern is less than or equal to the depth of the vertices in the main netlist for which computed labels are stored, and when the depth of the next pattern is greater than the depth of the vertices in the main netlist with computed labels each computing in (c) is for vertices in the main netlist for which labels have not yet been computed and each storing in (e) adds newly computed labels to stored labels computed for the main netlist for possible reuse in subsequent pattern matches.

A system for matching a pattern in a main netlist, comprising:

• a processor for executing program instructions;
• a memory to provide program instructions execution support to the processor;
• and
• a pattern matching module to,
• a) retrieve data representation of the main netlist and the pattern including data associated with a plurality of vertices, wherein each of the vertices being a net or a device;
• b) compute labels for each of the vertices in both the main netlist and the pattern up to a depth appropriate for the pattern, wherein the label for each of the vertices is computed through iterative relabeling to encode topology surrounding and including each of the vertices such that the vertices with matching topology are assigned a same label in both the pattern and the main netlist;
• and
• c) match a vertex of the pattern with one or more vertices of the main netlist using the computed labels, wherein the computed labels are stored for possible reuse in subsequent pattern matches;
• d) store the computed labels including data related to depth for each of the vertices in the main netlist in the memory;
• e) receive data representation of a next pattern as the pattern;
• and
• f) perform operations (b)-(d), wherein the match of the next pattern is performed by determining a depth of the next pattern and reusing stored labels computed for the main netlist when the depth of the next pattern is less than or equal to the depth of the vertices in the main netlist for which computed labels are stored, and when the depth of the next pattern is greater than the depth of the vertices in the main netlist with computed labels each computing in (b) is for vertices in the main netlist for which labels have not yet been computed and each storing in (d) adds newly computed labels to stored labels computed for the main netlist for possible reuse in subsequent pattern matches.