Reuse of circuit labels in subcircuit recognition

摘要

Method, apparatus and system for finding instances of a pattern in a main netlist include reading in the main netlist and the pattern that is used for finding pattern matches in the main netlist. The main netlist and the pattern include a plurality of vertices. Each of the vertices is a device or a net. Labels for the vertices are computed in both the pattern and the main netlist up to a depth appropriate for the pattern. A vertex of the pattern is identified and used in matching with one or more vertices in the main netlist at the depth appropriate for the pattern using the computed labels. The computed labels for each of the vertices of the main netlist are stored for possible reuse in subsequent pattern matches.

主权项

1. A computer implemented method for matching a pattern in a main netlist, the method comprising:
(a) reading in the main netlist by a processor of the computer; (b) reading in a pattern for finding matches in the main netlist by the processor, wherein the main netlist and the pattern include a plurality of vertices, each of the vertices being a net or a device; (c) computing labels for each of the vertices in both the main netlist and the pattern up to a depth appropriate for the pattern by the processor, 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) matching a vertex of the pattern with one or more vertices of the main netlist using the computed labels by the processor; (e) storing the computed labels including data related to depth for each of the vertices in the main netlist; (f) reading in a next pattern to be the pattern, and (g) 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.