Patent ID: 7958468
Filing Date: 2011-06-07
Classification: G06F

Abstract:
1. A method for indentifying instances of a smaller circuit in a larger circuit, both the smaller circuit and the larger circuit having a plurality of vertices, each of the plurality of vertices is one of a device or a net, the device having a Gate, a Drain, and a Source, the method comprising: (a) assigning one initial unique label to each of the plurality of vertices, each of a plurality of connection-types, power connection, and ground connection in the smaller circuit and the larger circuit, a zero label being assigned to each of an input/output ports and a same initial unique label is assigned to same types of circuit components; (b) relabeling each net in the plurality of vertices using labels of neighboring vertices, the neighboring vertices of a vertex are vertices that are directly connected to the vertex; (c) relabeling each device in the plurality of vertices using labels of neighboring vertices excluding a label of a vertex that is connected to the Gate of the each device in the plurality of vertices; (d) storing new labels of each net and each device in a data store; and (e) repeating method operations (b) to (d) until labels of all neighboring vertices of a selected vertex are zero, wherein the new labels of method operation (d) being used in subsequent iterations of method operations (b) and (c), wherein each of the method operations is executed by a processor.