초록 ▼

A single pattern-matching algorithm which allows both exact and inexact pattern-matching so that transistor-level design automation tools can reliably perform timing analysis, electrical rules checking, noise analysis, test pattern generation, formal design verification, and the like prior to manufa

A single pattern-matching algorithm which allows both exact and inexact pattern-matching so that transistor-level design automation tools can reliably perform timing analysis, electrical rules checking, noise analysis, test pattern generation, formal design verification, and the like prior to manufacturing custom logic. The user (circuit designer) specifies which of each of the pattern external nets may be matched inexactly (attached to Vdd, attached to GND, and shorted to other external nets), with the remainder of the pattern external net connections being matched using exact isomorphism constraints. The method described herein achieves a substantial reduction in the number of patterns which circuit designers must generate, and altogether eliminates the need for an exponential number of patterns by providing an inexact pattern matcher to circuit designers. It further provides rooted sub-graph isomorphism so that a user can query whether a particular pattern is embedded at a particular location in the main circuit design, utilizing inexact sub-graph isomorphism

대표청구항 ▼

1. 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 pa

1. 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.