# US 8,788,990 B2 · Reuse of circuit labels in subcircuit recognition

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,990 B2
- Document ID: US8788990B2
- Status: Granted
- Kind: B2
- Application number: 12/604,368
- Filed: 2009-10-22
- Published: 2010-02-18
- Granted: 2014-07-22
- Earliest claimed: 2008-02-21
- Assignees: Oracle America, Inc.
- Applicants: Douglas C. Meserve
- Inventors: Douglas C. Meserve
- Web page: https://patentgrep.com/patent/US8788990B2

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein computing labels for both the main netlist and the pattern further includes,
determining a vertex of the pattern;
identifying the vertex depth appropriate for the pattern; and
computing the labels for each of the vertices in both the main netlist and the pattern up to the vertex depth appropriate for the pattern, each of the computed labels identifying the topology information of the corresponding vertex.

### Claim 3 (depends on 2)

The method of claim 2, wherein matching a vertex further includes,
identifying one or more vertices in the main netlist whose labels match the computed label of the vertex of the pattern; and
performing topology tracking to confirm matching of the pattern by matching vertices in the pattern with the corresponding vertices in the main netlist.

### Claim 4 (depends on 3)

The method of claim 3, wherein performing topology tracking further includes,
tracing the pattern from the vertex of the pattern to identify each of the vertices that define the topology of the pattern; and
recursively matching the respective labels associated with the identified vertices of the pattern with the labels of corresponding vertices in the main netlist starting from the one or more vertices in the main netlist whose labels match the label of the vertex of the pattern.

### Claim 5 (depends on 1)

The method of claim 1, wherein the computed labels for the matched vertices in the main netlist are stored in a netlist label database.

### Claim 6

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.

### Claim 7 (depends on 6)

The computer readable medium of claim 6, wherein program instructions for computing labels for both the main netlist and the pattern further includes,
program instructions for determining a vertex of the pattern;
program instructions for identifying depth of the vertex appropriate for the pattern; and
program instructions for computing the labels for each of the nodes in both the main netlist and the pattern up to the vertex depth appropriate for the pattern, each of the computed labels identifying the topology information of the corresponding vertex.

### Claim 8 (depends on 7)

The computer readable medium of claim 7, wherein program instructions for matching a vertex further includes,
program instructions for identifying one or more vertices in the main netlist whose labels match the computed label of the vertex of the pattern; and
program instructions for performing topology tracking to confirm matching of the pattern by matching vertices in the pattern with the corresponding vertices in the main netlist.

### Claim 9 (depends on 8)

The computer readable medium of claim 8, wherein program instructions for performing topology tracking further includes,
program instructions for tracing the pattern from the vertex of the pattern to identify each of the vertices that define the topology of the pattern; and
program instructions for recursively matching the respective labels associated with the identified vertices of the pattern with the labels of corresponding nodes in the main netlist starting from the one or more vertices in the main netlist whose labels match the label of the vertex of the pattern.

### Claim 10

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.

### Claim 11 (depends on 10)

The system of claim 10, further includes a netlist label database for storing computed labels of each of the vertices in the main netlist.