Detailed method for routing connections using tile expansion techniques and associated methods for designing and manufacturing VLSI circuits

Abstract

Disclosed herein is a method and associated apparatus for the design and manufacture of VLSI circuit which incorporates therein a method for routing connections between component tiles of the VLSI circuit being designed.

What is claimed is:  
     
       1. For a routing area having a plurality of component tiles positioned thereon in a non-maximal arrangement, a method for determining an optimal tile path between a starting tile and a destination tile, comprising: 
       characterizing a first span which extends across said routing area;  
       identifying a next span which extends across said routing area and has a characterization different from said first span;  
       generating one or more maximal component tiles and/or one or more maximal space tiles based upon differences between said characterization of said first span and said characterization of said next span;  
       recharacterizing said first span based upon said generated maximal component tiles and said generated maximal space tiles;  
       repeatedly identifying a next span, generating one or more component tiles and/or maximal space tiles and recharacterizing said first span until said routing area is fully populated with maximal component tiles and maximal space tiles;  
       identifying first and second ones of said maximal component tiles as a starting tile S and a destination tile T, respectively; and  
       determining a low cost path between said starting tile S and said destination tile T.  
     
     
       2. The method of  claim 1 , wherein determining a low cost path between said starting tile S and said destination tile T further comprises: 
       selecting a low cost tile E from plural tiles which adjoin said starting tile S;  
       if said low cost tile E is said destination tile T, identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T.  
     
     
       3. The method of  claim 2 , wherein selecting a low cost tile E from plural tiles adjoining said starting tile S further comprises: 
       determining a distance between each one of said plural tiles adjoining said starting tile S and said destination tile T; and  
       selecting, as said low cost tile E, the tile closest to said destination tile T.  
     
     
       4. The method of  claim 3 , wherein identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T further comprises: 
       setting an initial path cost;  
       determining a path cost from starting tile S to destination tile T along said low cost tile E; and  
       identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T if said determined path cost is less than said initial path cost.  
     
     
       5. The method of  claim 1 , wherein determining a low cost path between said starting tile S and said destination tile T further comprises: 
       setting a path cost;  
       selecting a low cost tile E from plural tiles which adjoin said starting tile S;  
       if said low cost tile E is said destination tile T, identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T;  
       if said low cost tile E is not said destination tile T, for each tile F adjoining said low cost tile T:  
       selecting a tile F which adjoins said low cost tile E;  
       determining a minimum cost CF from said starting tile S to said selected tile F;  
       determining a lower cost bound CT from said selected tile F to said destination tile T; and  
       summing said minimum cost CF and said lower cost bound CT to determine an estimated cost CE;  
       if said estimated cost CE is less than said path cost, setting said estimated cost to be said path cost.  
     
     
       6. The method of  claim 5 , and further comprising: 
       constructing a search tree ST having said starting tile S as its root;  
       expanding said search tree ST to include plural tile paths which extend from said starting tile T, through said low cost tile E, and to said plural adjoining tiles F thereof;  
       pruning, from said search tree, tile paths for which said estimated cost CE is greater than said path cost; and  
       if said estimated cost CE for said tile F is less than said path cost, adding said tile F to said search tree ST as a child node of said low cost tile E.  
     
     
       7. The method of  claim 6 , wherein characterizing a first span across said routing area further comprises identifying active and inactive segments of said first span. 
     
     
       8. The method of  claim 7 , wherein generating one or more maximal component tiles and/or maximal space tiles further comprises: 
       identifying active and inactive segments of said next span;  
       for each identified active segment of said first span, determining if an active segment of said next span matches said identified active segment of said first span;  
       for each identified active segment of said first span not having a matching active segment in said next span, generating a maximal component tile having a width generally equal to a width of said identified active segment of said first span and a height generally equal to a distance separating said first span and said next span;  
       for each identified inactive segment of said first span, determining if an inactive segment of said next span matches said identified inactive segment of said first span; and  
       for each identified inactive segment of said first span not having a matching inactive segment in said next span, generating a maximal space tile having a width generally equal to a width of said identified inactive segment of said first span and a height generally equal to the distance separating said first span and said next span.  
     
     
       9. The method of  claim 8 , wherein recharacterizing said first span based upon said generated maximal component tiles and said generated maximal space tiles further comprises: 
       deleting, from said first span, each identified active segment having a matching active segment in said next span;  
       adding, to said first span, each unmatched active segment of said next span;  
       deleting, from said first span, each identified inactive segment having a matching inactive segment in said next span; and  
       adding, to said first span, each unmatched inactive segment of said next span.  
     
     
       10. For a routing area having a plurality of component tiles positioned thereon in a first maximal arrangement and a plurality of space tiles positioned thereon in a second maximal arrangement, a method for determining an optimal tile path between a starting tile and a destination tile, comprising: 
       identifying first and second ones of said maximal component tiles as a starting tile S and a destination tile T, respectively;  
       selecting a low cost tile E from plural tiles which adjoin said starting tile S;  
       if said low cost tile E is said destination tile T, identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T;  
       setting a path cost;  
       selecting a low cost tile E from plural tiles which adjoin said starting tile S;  
       if said low cost tile E is not said destination tile T, for each tile F adjoining said low cost tile T:  
       selecting a tile F which adjoins said low cost tile E;  
       determining a minimum cost CF from said starting tile S to said selected tile F;  
       determining a lower cost bound CT from said selected tile F to said destination tile T; and  
       summing said minimum cost CT and said lower cost bound CF to determine an estimated cost CE;  
       if said estimated cost CE is less than said path cost, setting said estimated cost to be said path cost; and  
       determining that the path corresponding to said estimated cost CE which is less than said path cost is said low cost path between said starting tile S and said destination tile T.  
     
     
       11. The method of  claim 10 , and further comprising: 
       constructing a search tree ST having said starting tile S as its root;  
       expanding said search tree ST to include plural tile paths which extend from said starting tile T, through said low cost tile E, and to said plural adjoining tiles F thereof;  
       pruning, from said search tree, tile paths for which said estimated cost CE is greater than said path cost; and  
       if said estimated cost CE for said tile F is less than said path cost, adding said tile F to said search tree ST as a child node of said low cost tile E.  
     
     
       12. The method of  claim 11 , wherein selecting a low cost tile E from plural tiles adjoining said starting tile S further comprises: 
       determining a distance between each one of said plural tiles adjoining said starting tile S and said destination tile T; and  
       selecting, as said low cost tile E, the tile closest to said destination tile T.  
     
     
       13. The method of  claim 12 , wherein identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T further comprises: 
       setting an initial path cost;  
       determining a path cost from starting tile S to destination tile T along said low cost tile E; and  
       identifying said low cost tile E as said low cost tile path between said starting tile S and said destination tile T if said determined path cost is less than said initial path cost.  
     
     
       14. A computer system, comprising: 
       a memory subsystem;  
       a processor subsystem;  
       a bus subsystem, said bus subsystem coupling said memory subsystem and said processor subsystem for exchange of signals therebetween; and  
       a VLSI circuit design module, said VLSI circuit design module stored in said memory subsystem and executable by said processor subsystem;  
       said VLSI circuit design module comprising:  
       means for configuring a routing area for a layer of a VLSI circuit design, said routing area having a plurality of component tiles positioned thereon;  
       means for reconfiguring said plurality of component tiles positioned on said routing area for a layer of a VLSI circuit design into a plurality of maximal component tiles and a plurality of maximal space tiles;  
       means for identifying a first one of said plurality of maximal component tiles as a starting tile S and for identifying a second one of said plurality of maximal component tiles as a destination tile T; and  
       means for determining a low cost path between said starting tile S and said destination tile T.  
     
     
       15. The computer system of  claim 14  wherein said means for determining a low cost path between said starting tile S and said destination tile T further comprises: 
       means for constructing a search tree ST having said starting tile S as its root;  
       means for expanding said search tree ST to include plural tile paths;  
       means for determining a cost associated with each of said plural tile paths of said search tree ST; and  
       means for pruning, from said search tree ST, tile paths having an excessive cost associated therewith.