Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-10-31
2002-10-29
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C703S014000
Reexamination Certificate
active
06473881
ABSTRACT:
FIELD OF THE INVENTION
This invention is related generally to the design of integrated circuit chips and, more particularly, to a method of matching sub-circuit patterns in a larger transistor-level circuit design for the purpose of timing analysis, electrical rules checking, noise analysis, test pattern generation, design verification and circuit optimization.
BACKGROUND OF THE INVENTION
VLSI (Very Large Scale Integration) and ULSI (Ultra Large Scale Integration) chips involve a heavy commitment of computer resources to design, test and manufacture chips and systems that involve millions of circuits interconnected to each other. Because of the large number of transistors, it is no longer possible to perform this task manually. As a result, a new field referred to as Electronic Design Automation (EDA) has been developed over the last decades to address the complexity of this design process.
Much of the increase in the size of modern VLSI has been accomplished through levels of abstraction and reuse. Large designs commonly consist of pre designed logic functions called “cells”. These cells are provided in a library complete with characterizations of their function, timing performance, layout characteristics etc. While this greatly facilitates ease of reuse, the dependence on pre characterization tends to come at a cost. The necessity of limiting the number of cells provided in a library to a manageable number limits the flexibility that a designer has with regard to circuit topologies, device sizes and layout choices. This generally manifests itself in a reduction in chip performance and density. For this reason, large portions of those designs most sensitive to performance and/or density considerations are still implemented at a lower level of abstraction. So-called custom logic is designed at the transistor rather than the cell-level which affords the designer much greater flexibility to tune the design to his/her application. In addition to being more labor intensive, this custom design style places an additional burden on the design tools.
Unlike a high-level abstraction, transistor-level designs require tools to infer functionality from connectivity. All circuit design analysis and verification tools require identification of sub-circuits from a flat (nonhierarchical) netlist. The task of EDA tools is compounded by a large number of circuit combinations and a need to understand many custom design styles. This need to identify sub-circuits from a sea of transistors motivates an invention for pattern matching which can identify groups of transistors for any transistor-level EDA tool.
Sub-Graph Isomorphism
Isomorphism is defined as having the “same form” or “same shape”. If two groups of elements are isomorphic, there is a one-to-one relationship between the elements of one group and the elements of another. Graph isomorphism signifies that two entire graphs are identical. Sub-graph isomorphism implies that there is a one-to-one relationship between each element of the sub-graph and one of the elements of the larger graph.
Sub-graph isomorphism is a technique that is used advantageously for pattern matching. Pattern matching in a transistor-level netlist implies that every instance of a pattern, consisting of a plurality of transistors, can be found in a larger transistor-level netlist. The pattern is represented as a sub-graph, while the larger transistor-level netlist is modeled as a graph. In the field of circuit design analysis and verification, sub-graph isomorphism implies that all the transistors and electrical net connections which are present in the sub-graph can be found in a larger circuit graph. Typically, a circuit designer attempts to localize specific sub-circuits, such as an inverter or a multiplexer, in a larger circuit design. These sub-circuits need to be found such that the VLSI or ULSI design can be correctly timed, analyzed for circuit noise, checked for compliance with electrical rules specifications, tested, and formally verified. This identification of sub-circuits in a larger transistor-level circuit design is sometimes referred to sub-circuit extraction.
By way of example of how the problem of pattern matching has been handled heretofore, there is shown in
FIG. 1
an inverter pattern
102
integral to a larger circuit design
104
. There is one instance of the pattern in the larger circuit design. The match can be seen as follows:
Pattern:
Larger circuit design:
input
matches
inp
output
matches
mid
P1
matches
MPinv
N1
matches
MNinv
Vdd
matches
Vdd
GND
matches
GND
In an exact pattern-matching, a pattern instance in the circuit design can only be identified as such if it precisely matches the specification of the pattern. The pattern instance will be missed by the pattern matcher if inputs are attached to Vdd or GND, or if inputs are shorted together. If any modification exists, the instance will not be recognized by the pattern matcher. Inexact pattern matching, on the other hand, implies that the instance can be recognized even if certain modifications are made in the imbedding of the pattern in the larger transistor-level netlist. Common modifications made by circuit designers include attaching inputs to Vdd or GND and shorting together of inputs. Only an inexact pattern matcher is able to identify such pattern instantiations.
In an inexact pattern-matching, the constraints for isomorphism are relaxed at the pattern external (boundary) net connections such that external nets in the pattern instance can be connected to special nets, such as Vdd or GND, or shorted to other external nets. Inexact sub-graph isomorphism is critical in transistor pattern-matching because, heretofore, users were required to specify a potentially exponential number of exact patterns in order to find all possible combinations of external connectivity.
The difficulties encountered by circuit designers who employ a prior art pattern matcher will be better understood with reference to the 3-input multiplexers illustrated in FIG.
2
. Therein are shown fourteen patterns that are typically required to enumerate all possible combinations of external net connectivity of the 3-input multiplexer. The fourteen patterns capture all possible combinations of inputs attached to Vdd, to GND, and shorted together. Practitioners in the art will readily realize that, in the prior art, the number of patterns required grows exponentially with the number of inputs.
An effective way of avoiding the enumeration of exact patterns has not been identified up to now. Thus, circuit designers spend countless hours enumerating patterns and manually ensuring that they identified all external net configurations that are present in their design. Circuit designers called a pattern matcher for each of the thirteen possible modified patterns in order to find all instances of the general pattern referenced by
FIG. 2
numeral
1
in their circuit design. Missed pattern instances due to a failure to identify all of the external net configurations lead to transistor-level timing errors, design verification errors, errors in circuit test pattern generation, and errors in electrical rules checking, resulting in a significant loss of functionality and slowing down many of the steps required to bring a circuit design to market.
Graph isomorphism techniques have been used for transistor-level netlist comparison in the past. Corneil's graph labeling algorithm, described in “Recent Results on the Graph Isomorphism Problem”, Proc. Eighth Manitoba Conference on Numerical Mathematics and Computing, 1978, pp.13-31, is well-known and is the initial work on graph labeling using matched neighbors. Applications of Corneil's graph isomorphism algorithm and graph coloring for graph isomorphism are described in U.S. Pat. No. 6,009,252 to Lipton entitled “Methods, apparatus, and computer program products for determining equivalencies between integrated circuit schematics and layouts using color symmetrizing matrices” and in U.S. Pat. No. 5,463,561 to Razdan entitled “High Capacity Netlist Comparison”. The aforementione
Cohn John M.
Finkler Ulrich A.
Lehner Valerie D.
Kik Phallaka
Schnurmann H. Daniel
LandOfFree
Pattern-matching for transistor level netlists does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern-matching for transistor level netlists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern-matching for transistor level netlists will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2954141