Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-01-28
2001-08-14
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06275974
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to tracing of shorts in very large nets in Very Large Scale Integrated (VLSI) circuit designs and, more particularly, to efficiently finding one electrical path containing at least one of the VLSI design component instances causing the short using Breadth First Search (BFS) with optimal pruning.
2. Background Description
The problem of tracing shorts in a circuit design is to find an electrical path, consisting of a small number of VLSI design component instances, such that it contains at least one of the VLSI design component instances that cause the short. We refer to such a path in the following as a “shorting path”. Shorts between large nets, e.g., between circuit ground (GND) and source voltage (VDD), occur frequently in designs. Although existing tools are able to detect the existence of a short in a hierarchical design, finding a shorting path in large designs is extremely time consuming. The automated tracing of shorts between very large nets by existing software tools typically fails due to extreme storage or computation time requirements.
The problem of finding a short electrical path between two VLSI design component instances with different net attributes can be mapped to finding a short path in a graph, in which the vertices correspond to VLSI design component instances and the edges correspond to direct electrical connectivity between the two adjacent vertices. Net attributes are names attached to at least one VLSI design component instance on a net, where a net is a set of VLSI design component instances which form a connected component with respect to a relation as, for example, intersection between geometric shapes of which the VLSI design components are composed. Geometric shapes are the most elementary type of VLSI design components, which usually form the leaf components in the VLSI design hierarchy. In the following, we will refer to leaf components as “leafs”. For detailed definitions of hierarchy, VLSI design components, nets, etc., see U.S. Pat. Nos. 5,519,628 and 5,481,473 and the reference materials,
Introduction to Algorithms,
by T. H. Corment, C. E. Leiserson, R. L. Rivest (MIT Press), hereafter referred to as “Algorithms”, and
The LEDA Platform for Combinatorial and Geometric Computing,
by K. Mehlhom, and S. Näher (Cambridge University Press), hereafter referred to as “Geometric Computing”.
“Algorithms” shows that the single source shortest path problem can be solved with a Breadth First Search (BFS) in O(N) time in unweighted graphs. In a hierarchical design, the standard shortest path search in unweighted and undirected graphs, BFS, cannot be applied directly without flattening the design. Flattening the design before processing results in unprocessable amounts of data for large designs.
BFS requires at least two Boolean values (representable as two bits in a computer memory) per instance of a leaf (i.e., per vertex), which indicate whether or not the vertex was unprocessed, touched or visited. A vertex was is called visited if its outgoing edges were investigated during the BFS. It is called touched if it was found by investigating an outgoing edge of another vertex. In a shortest path search in a hierarchical design at least these Boolean variables must be stored for each instance of a leaf, i.e., flat, even when the design is not flattened before processing.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method to trace shorts efficiently with respect to time and storage requirements in large hierarchical designs. Particularly, the invention does not require a special representation of the design, only a capability to find all VLSI design component instances intersecting one particular design component instance is necessary in addition to access to the list of all objects in the considered net.
According to the present invention, there is provided a method which efficiently traces shorts in very large nets using the technique of pruning. The input to the trace short process of the invention is a hierarchically represented connected component of a net which is known to contain a short; i.e., it contains at least two VLSI design component instances attributed with different net names. In the following, we use place holders “A” and “B” for their net names. A connected component of a net is a set of VLSI design components such that there is an electrical path between each pair of components in that set. Note that this does not require a direct contact between each pair. Note also, that only a subset of the components are attributed due to the hierarchical structure. The connected component of the net containing the short, which consists out of a set of VLSI component instances in conducting layers of the design, is mapped to a graph as described above.
A starting leaf instance is identified. Since the only available information is the set of leaf instances and the net attributes, a leaf instance with label “A” and additional “start object properties” is identified as the starting leaf. A flat BFS is performed, storing instance related information in an auxiliary data structure.
REFERENCES:
patent: 5481473 (1996-01-01), Kim et al.
patent: 5519628 (1996-05-01), Russell et al.
patent: 5880969 (1999-03-01), Hama et al.
patent: 6014507 (2000-01-01), Fujii
Bartels Ronald Allen
Finkler Ulrich Alfons
International Business Machines - Corporation
McGuireWoods LLP
Otterstedt Paul J.
Phan Trong
LandOfFree
Efficient tracing of shorts in very large nets in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient tracing of shorts in very large nets in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient tracing of shorts in very large nets in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2507509