Patent attributes
A method for indentifying instances of a smaller circuit in a larger circuit is disclosed. Both the smaller circuit and the larger circuit have a plurality of vertices. A vertex is one of a device or a net. The device, such a transistor, includes a Gate, a Drain, and a Source. The net is a wired connection between devices. In this method, one initial unique label is assigned to each of the plurality of vertices, each of a plurality of connection-types, power connection, and ground connection. A zero label is assigned to each of an input/output ports and a same initial unique label is assigned to same types of circuit components. Then each net is relabeled using labels of neighboring vertices. The neighboring vertices of a vertex are vertices that are directly connected to the vertex. Then, each device in the plurality of vertices is relabeled using labels of neighboring vertices excluding a label of a vertex that is connected to the Gate of the each device. The new labels of each vertex are stored in a data store and these labels are used in the calculation of the new labels of the vertices in a next iteration of relabeling.
