Patent Document ID: 8788990
Application ID: 12604368
Patent Status: 1

Claim One:
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.