Method and apparatus for storing routes

Abstract

Some embodiments of the invention provide a method of pre-computing routes for nets a region of a design layout. These routes are used by a router that uses a set of partitioning lines to partition the region into a plurality of sub-regions. For each particular set of potential sub-regions, the method initially identifies a set of routes that traverse the particular set of potential sub-regions. For each particular route identified for each particular set of sub-regions, the method then determines whether the particular route is stored in a storage structure. If not, the method stores the particular route in the storage structure.

We claim: 
     
       1. For a router that uses a set of partitioning lines to partition a region of a design layout into a plurality of sub-regions, a method of pre-computing routes for nets, the method comprising:
 a) for each particular set of potential sub-regions, identifying a set of routes that traverse the particular set of potential sub-regions; 
 b) for each identified route for each particular set of sub-regions, determining whether the identified route is stored in a storage structure; and when the identified route is not stored in the storage structure, storing the identified route in the storage structure. 
 
     
     
       2. The method of  claim 1 , wherein some of the identified routes have diagonal route edges. 
     
     
       3. The method of  claim 2 , wherein a first route is identified for a first set of potential sub-regions, and the first route is stored in the storage structure, the method further comprising associating the first route with the first set of potential sub-regions. 
     
     
       4. The method of  claim 2  further comprising: when a first route that is identified for a first set of sub-regions is already stored in the storage structure, associating the first route with the first set of potential sub-regions. 
     
     
       5. The method of  claim 2 , wherein determining whether the identified routes are stored in the storage structure comprises:
 using a binary tree to sort the stored routes; and 
 traversing the binary tree to determine whether routes are stored in the storage structure. 
 
     
     
       6. For an electronic design automation (“EDA”) router that routes nets within a region of an integrated-circuit layout, a method of pre-computing routes, the method comprising:
 a) defining a set of partitioning lines for partitioning the region into a plurality of sub-regions; 
 b) for a first set of sub-regions, 
 identifying a first set of routes that connect the first set of sub-regions; 
 storing the first set of routes in a storage structure; and 
 establishing a relationship between the first set of routes and the first set of sub-regions; and 
 c) for a second set of sub-regions, 
 identifying a second set of routes that connect the second set of sub-regions; 
 determining whether each route in the second set is stored in the storage structure; 
 when a new route in the second set is not stored in the storage structure, storing the new route in the storage structure and establishing a relationship between the new route and the second set of sub-regions; and 
 when a repeating route in the second set is stored in the storage structure, establishing a relationship between the repeating route and the second set of sub-regions. 
 
     
     
       7. The method of  claim 6 , wherein some of the identified routes have diagonal route edges. 
     
     
       8. The method of  claim 6 , wherein determining whether particular routes are stored in the storage structure comprises:
 using a binary tree to sort the stored routes; and 
 traversing the binary tree to determine whether routes are stored in the storage structure. 
 
     
     
       9. The method of  claim 8 , wherein each route is specified by a bitstring having a plurality of bits, wherein traversing the binary tree comprises traversing the tree based on the bits in the bitstrings of the routes. 
     
     
       10. The method of  claim 9 ,
 wherein the binary tree includes nodes and each node includes either zero or two branches, 
 wherein each node corresponds to a particular bit in the bitstrings, and 
 wherein traversing the binary tree based on the route bitstrings comprises identifying, for a particular route bitstring, the branch to select at a particular node based on the value of the route bitstring's bit that corresponds to the particular node. 
 
     
     
       11. The method of  claim 9  wherein a plurality of paths exist between the sub-regions defined by the set of partitioning lines, wherein each route's bitstring bits represent the paths used by the route. 
     
     
       12. The method of  claim 11 , wherein a plurality of the paths are diagonal paths, and wherein some of the routes traverse some of the diagonal paths. 
     
     
       13. The method of  claim 9  wherein a plurality of inter-sub-regions exist between the sub-regions defined by the set of partitioning lines, wherein each route's bitstring bits represent the inter-sub-regions intersected by the route. 
     
     
       14. The method of  claim 13 , wherein a plurality of the inter-sub-regions are diagonal inter-sub-regions, and wherein some of the routes intersect some of the diagonal inter-sub-regions. 
     
     
       15. The method of  claim 6 , wherein establishing a relationship between each particular set of sub-regions and each set of routes for the particular set of sub-regions comprises:
 for each set of sub-regions, storing a set of references to routes, 
 wherein each stored reference set includes one or more references to stored routes. 
 
     
     
       16. The method of  claim 6 , wherein the sets of routes for some set of sub-regions includes only one route, while the sets of routes for other set of sub-regions includes more than one route.