Patent ID: 6473881
Filing Date: 2002-10-29
Classification: G06F

Abstract:
A method of matching a pattern sub-circuit in a master circuit design, the master circuit design being both formed by a plurality of master devices interconnected by master nets and modeled as a graph, and the pattern sub-circuit being formed by a plurality of pattern devices interconnected by pattern nets and modeled as a graph, wherein both nets and devices are explicitly modeled as nodes in the graphs, enabling both exact and inexact pattern matching using a single pattern matching engine, the method comprising the steps of:a) defining an explicit net comparison function that enables both the exact matching and the inexact matching of the pattern net to a master net, where an inexact match is a match to a master net which is connected to a power supply or to a net which is already matched to another pattern net; b) defining an explicit device comparison function that enables the matching of the pattern device to the master device based on a device characteristic; c) defining a node comparison function which compares two device nodes using the explicit device comparison function or compares two net nodes using the explicit net comparison function; d) identifying a pattern keynode; e) identifying a set of candidate nodes in the master circuit design for which the node comparison function is indicative of a potential match between the pattern keynode and a node in the master circuit design; f) iterating over a set of master candidate nodes; g) for each of the master candidate nodes, exploring a potential match of the pattern in the master circuit design containing the candidate node, and h) repeating steps f) and g) until all instances of the pattern in the master circuit design have been identified and invoking a user-supplied function for each of the instances to enable circuit design analysis, verification or optimization prior to its manufacture.