Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-01-28
2001-07-17
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06263480
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 Semiconductor 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. In this task, the invention relaxes the requirement of a shortest path to an approximation of a shortest path to take full advantage of the hierarchical structure of the VLSI design.
2. Background Description
The problem of tracing shorts in a design is to find an electrical path consisting out 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 VLSI 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 the 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. Mehlhorn, and S. Naher (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, Dijkstra's algorithm solves it in weighted undirected graphs in O(N log N) time.
In a hierarchical design, any standard shortest path search (as BFS or Dijkstra's algorithm) cannot be applied directly without flattening the design, which results in un-processable amounts of data for large designs. The BFS and Dijkstra's algorithm requires at least two Boolean values (representable as two bits in a computer memory) per vertex, which indicate whether or not the vertex was unprocessed, touched or visited. A vertex is called visited if its outgoing edges were investigated during the algorithm. It is called touched if it was found by investigating an outgoing edge of another node. In the following, we will refer to the different flavors of shortest paths searches as “SPS”. 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.
Since very large designs might contain hundreds of millions of shapes, even storing one bit per shape instance is extremely storage consuming, in addition to the indexing problem. Hence, techniques to store the state temporarily for a limited number of instances or techniques taking advantage of the hierarchical structure of the problem are necessary.
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.
According to the present invention, full advantage is taken of the hierarchical character of the design. The input to the trace short process is a hierarchically represented connected component of a net known to contain a short; i.e., it contains at least two VLSI design component instances attributed with net names, whose net names are different. 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 of a set of VLSI component instances in conducting layers of the design, is mapped to a graph as described above. Weights are determined for the edges of the graph out of an approximation for the diameter of the two adjacent nodes (i.e., VLSI design objects). The approximation “deflattens” the problem of finding the short.
A starting component instance with the label “A” and additional “start object properties” is identified as the starting instance. A hierarchical SPS is performed until a path of leaf instances between two leaf instances with labels “A” and “B” is found. The output is an approximation for the shortest path from the starting leaf to the determined offending leaf. In the same fashion as hierarchical layout verifications, this method takes advantage of the multiple use of identical sub-circuits by investigating such circuits only once in comparison to investigating each instance (i.e., each copy).
REFERENCES:
patent: 4484292 (1984-11-01), Hong et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4852016 (1989-07-01), McGehee
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-2506037