Efficient tracing of shorts in very large nets in hierarchical designs using breadth-first search with optimal pruning

Abstract

Tracing a short as a shortest path of explicit VLSI design component instances between two VLSI design component instances with different net names in a hierarchical design is a non-hierarchical problem. The method described in this document computes a shortest path of VLSI design leaf component instances containing at least one of the leaf design components causing the sort. To avoid exceeding available storage, the non-hierarchical instance information maintained during the process is pruned optimally. To achieve feasible performance, two methods to find “good” starting points are provided, based on geometrical distribution or based on connectivity information from the net build (if available).

Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows:  
     
       1. A method for efficiently tracing shorts in very large nets in hierarchical Very Large Scale Integrated (VLSI) circuit designs comprising the steps of: 
       inputting a net which is known to contain a short, said net consisting of a set of VLSI leaf components in conducting layers of the design;  
       mapping said net to a graph;  
       identifying a set of starting VLSI design leaf component instances wherein VLSI design leaf component instances on a shortest path between two VLSI design leaf component instances with different net attributes form a minimal set of VLSI design leaf component instances for which it is guaranteed that it contains the short; and  
       using a Breadth First Search to determine shortest paths.  
     
     
       2. The method according to claim  1 , wherein the mapping step virtually maps the connected component to the graph such that the flat graph is never constructed explicitly. 
     
     
       3. The method according to claim  2 , further comprising the step of pruning at the earliest possible time all inactive paths to minimize an amount of flat information that is maintained. 
     
     
       4. A method of tracing a short as a shortest path of explicit Very Large Scale Integrated (VLSI) circuit component instances between two VLSI design component instances with different net names in a hierarchical design comprising the steps of: 
       inputting a virtual graph of the hierarchical design and a set of starting shapes corresponding to components in the design;  
       computing a shortest path of VLSI design leaf component instances containing at least one of the leaf design components causing a short; and  
       pruning non-hierarchical instance information to avoid exceeding available storage.  
     
     
       5. The method according to claim  4 , wherein a connected component of a net contains VLSI design leaf component instances with two different attributes A and B,VLSI design leaf component instances with attribute B being called offending VLSI design leaf component instances, and further comprising the step of determining starting VLSI design leaf component instances comprising the steps of: 
       tracking attributes during computation of electrical connectivity in the hierarchical net; and  
       identifying a design leaf component instance next to an intrusion that merges two subnets with different attributes.  
     
     
       6. The method according to claim  4 , wherein the step of computing a shortest path of VLSI design leaf component instances comprises the steps of: 
       starting a first Breadth First Search (BFS) with pruning to look for any shape instance with attribute A found in the net; and  
       starting a second BFS with pruning to find a shortest path from a shape found by the first BFS to an offending shape instance with attribute B.  
     
     
       7. The method according to claim  4 , wherein the step of computing a shortest path of VLSI design leaf component instances comprises the step of starting a Breadth First Search (BFS) of the selected starting VLSI design leaf component instances to find one offending shape. 
     
     
       8. The method according to claim  4 , further comprising the step of determining VLSI design leaf component instances by selecting a set of geometrically evenly distributed starting VLSI design leaf component instances in the net.