Abstract:
A method of accurately estimating horizontal and vertical wire densities in a datapath or hardmac. The method provides that the datapath or hardmac is divided into areas, and mathematical expectations are calculated for full and partial horizontal and vertical segments for each of the areas. The mathematical expectations are summed for both the horizontal and vertical segments, and this is done for each connection within the datapath or hardmac in order to estimate both horizontal and vertical wire densities. A congestion map can be created, and 100% detail routing is effectively guaranteed as a result of using the method. Preferably, a model with minimum bends is used in areas with low wire density, and models with more bends are used in areas with middle and high wire density.

Description:
BACKGROUND 
   This invention generally relates to probabilistic models for calculating wire density in different areas of a datapath or hardmac, and more specifically relates to a probabilistic model which differentiates between horizontal and vertical segments. 
     FIG. 1  shows a general datapath structure. As shown, datapath cells are located in blocks (clusters) and control cells may be located in columns along left and right sides of the datapath and in blocks as well. Current datapaths are typically very large and complex, and require design datapath macros with complex hierarchical structures that have a high design quality. Additionally, complex constraints on the placement of cells, pins and nets, as well as the size of gaps between cells, blocks, etc. must be respected, and there must be guaranteed 100% detail routing. 
   One prior art approach for calculating wire density in different areas of a datapath is based on a simplified density model and is used for placement quality estimation only. The approach is not accurate, does not differentiate between vertical and horizontal segments of connections, does not take into account all possible shortest length configurations of connections, and is unacceptable for calculating a congestion map. 
   OBJECTS AND SUMMARY 
   A general object of an embodiment of the present invention is to provide a method of estimating wire densities which differentiates between horizontal and vertical segments. 
   Another object of an embodiment of the present invention is to provide a method of estimating wire densities which facilitates the formulation of a congestion map. 
   Still another object of an embodiment of the present invention is to provide a probabilistic model which takes into account all possible shortest length configurations of connections, thereby being sufficiently accurate to estimate wire density. 
   Briefly, and in accordance with at least one of the foregoing objects, an embodiment of the present invention provides a method of accurately estimating horizontal and vertical wire densities in a datapath or hardmac. The method provides that the datapath or hardmac is divided into areas, and mathematical expectations are calculated for full and partial horizontal and vertical segments for each of the areas. The mathematical expectations are summed for both the horizontal and vertical segments, and this is done for each connection within the datapath or hardmac in order to estimate both horizontal and vertical wire densities. A congestion map can be created, and 100% detail routing is effectively guaranteed as a result of using the method. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The organization and manner of the structure and operation of the invention, together with further objects and advantages thereof, may best be understood by reference to the following description, taken in connection with the accompanying drawings, wherein like reference numerals identify like elements in which: 
       FIG. 1  is a general schematic diagram of a datapath structure; 
       FIG. 2  is a general schematic diagram showing a datapath area divided into square areas, and two pins, P 1  and P 2 , contained in the datapath area; 
       FIG. 3  is a general schematic diagram of a portion (i.e., rectangle [a,b,c,d]) of the area shown in  FIG. 2 ; 
       FIGS. 4   a – 4   f  show six different possible connection configurations in a given area A; 
       FIG. 5  is similar to  FIG. 3 , showing a full horizontal segment through area A in rectangle [a,b,c,d]; 
       FIG. 6  is similar to  FIG. 3 , showing a partial horizontal segment through area A in rectangle [a,b,c,d]; 
       FIG. 7  is similar to  FIG. 3 , showing another type of partial horizontal segment through area A in rectangle [a,b,c,d]; 
       FIG. 8  is a general schematic diagram showing a datapath area divided into square areas and a bounding area [a,b,c,d] defined in the datapath; 
       FIGS. 9   a  and  9   b  show two different minimum bends configurations; 
       FIG. 10  shows bounding area [a,b,c,d] and the four different ways in which a minimal bends connection can go through a given area; 
       FIG. 11   a  shows the horizontal probabilities for the configuration shown in  FIG. 9   a;    
       FIG. 11   b  shows the horizontal probabilities for the configuration shown in  FIG. 9   b;    
       FIG. 12  shows the overall horizontal probabilities for the configurations shown in  FIGS. 9   a  and  9   b;    
       FIG. 13  is similar to  FIG. 12 , but shows the overall vertical probabilities; 
       FIGS. 14   a  and  14   b  show two different two bends configurations; 
       FIG. 15  shows the horizontal probabilities for the configuration shown in  FIG. 14   a;    
       FIG. 16  shows the horizontal probabilities for the configuration shown in  FIG. 14   b;    
       FIG. 17  shows the overall horizontal probabilities for the configurations shown in  FIGS. 14   a  and  14   b ; and 
       FIGS. 18   a  and  18   b  show two different three bends configurations. 
   

   DESCRIPTION 
   While the invention may be susceptible to embodiment in different forms, there are shown in the drawings, and herein will be described in detail, specific embodiments with the understanding that the present disclosure is to be considered an exemplification of the principles of the invention, and is not intended to limit the invention to that as illustrated and described herein. 
   An embodiment of the present invention provides a probabilistic method for calculating wire density in different areas of the datapath (the term “datapath” is to be construed very broadly herein, as the term is used herein to mean any type of real estate) and other hardmacs with a given cell placement. The method is based on a probabilistic model of connection between two pins. The model takes into account all possible shortest length configurations of the connection, and differentiates between vertical and horizontal segments of the connection. Thus, the model is sufficiently accurate to be used for wire density estimation, and provides that congestion maps can be calculated. 
   Initially, as shown in  FIG. 2 , a datapath area is divided into M DP  by N DP  squared areas (effectively a matrix of columns and rows), where each area size is about equal to the width of placement columns or cell width. It is known that the number of the shortest length paths (configurations) from P 1  to P 2  (see  FIG. 3 ) is: 
   
     
       
         
           
             
               
                 
                   N 
                   ⁡ 
                   
                     ( 
                     
                       P1 
                       , 
                       P2 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     ( 
                     
                       
                         
                           
                             m 
                             - 
                             1 
                           
                         
                       
                       
                         
                           
                             n 
                             + 
                             m 
                             - 
                             2 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           m 
                           + 
                           n 
                           - 
                           2 
                         
                         ) 
                       
                       ! 
                     
                     
                       
                         
                           ( 
                           
                             m 
                             - 
                             1 
                           
                           ) 
                         
                         ! 
                       
                       · 
                       
                         
                           ( 
                           
                             n 
                             - 
                             1 
                           
                           ) 
                         
                         ! 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
         
       
     
   
   With regard to the possible shortest length configurations for connection C from pin P 1  to pin P 2  (see  FIG. 1 ), it is known that any shortest length connection (P 1 , P 2 ) will belong to rectangle [a,b,c,d]. Therefore, for any area A 1  from [a,b,c,d] there exists some probability P(A 1 )&gt;0 that connection (P 1 , P 2 ) will go through this area, and for any area A 2  outside [a,b,c,d] there is zero probability that connection (P 1 , P 2 ) will go through this area. If the probability P(a) is known, then the mathematical expectation of area A having connection (P 1 , P 2 ) can be calculated as being M(A)=P(A). 
   As shown in  FIGS. 4   a – 4   f , any connection (P 1 , P 2 ) can go through area A in six different ways. The configurations shown in  FIGS. 4   a – 4   d  are possible if pin P 2  is higher than pin P 1 , and the configurations shown in  FIGS. 4   e  and  4   f  are possible if pin P 1  is higher than pin P 2 . The segment (i.e., the connection through area A) shown in  FIG. 4   a  is a full horizontal segment, while the segment shown in  FIG. 4   b  is a full vertical segment. Each one of the segments shown in  FIGS. 4   c – 4   e  is both a partial horizontal and partial vertical segment. 
   The situation where pin P 2  is higher than pin P 1  (as shown in  FIG. 2 ) will be discussed below. The analysis would be analogous in the case where pin P 1  is higher than P 2 . 
     FIG. 5  shows the rectangle [a,b,c,d] (see  FIG. 2 ) wherein there is a full horizontal segment (see  FIG. 4   a ) through area A ( FIGS. 5–7  also show the numeration of the columns and rows which form the rectangle [a,b,c,d]). The mathematical expectations M h1 (A) of full horizontal segments can be calculated as follows: 
                     M   h1     ⁡     (   A   )       =         N   ⁡     (     P1   ,     A   ′       )       ·     N   ⁡     (       A   ″     ,   P2     )           N   ⁡     (     P1   ,   P2     )                 (   2   )               
where
 
N(P 1 , A′) is the number of possible paths from P 1  to area A′;
 
N(A″, P 2 ) is the number of possible paths from area A″ to P 2 ; and
 
N(P 1 , P 2 ) is the number of possible paths from P 1  to P 2 .
 
   Taking into account the formula (equation (1) above) for the number N(P 1 , P 2 ) of paths between two points, all the numbers which are needed to calculate the mathematical expectation M h1 (A) can be found: 
   
     
       
         
           
             
               
                 
                   N 
                   ⁡ 
                   
                     ( 
                     
                       P1 
                       , 
                       
                         A 
                         ′ 
                       
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ( 
                       
                         i 
                         + 
                         j 
                         - 
                         3 
                       
                       ) 
                     
                     ! 
                   
                   
                     
                       
                         ( 
                         
                           i 
                           - 
                           1 
                         
                         ) 
                       
                       ! 
                     
                     · 
                     
                       
                         ( 
                         
                           j 
                           - 
                           2 
                         
                         ) 
                       
                       ! 
                     
                   
                 
               
             
             
               
                 ( 
                 3 
                 ) 
               
             
           
         
       
     
   
   
     
       
         
           
             
               
                 
                   N 
                   ⁡ 
                   
                     ( 
                     
                       
                         A 
                         ″ 
                       
                       , 
                       P2 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ( 
                       
                         m 
                         - 
                         i 
                         + 
                         n 
                         - 
                         j 
                         - 
                         1 
                       
                       ) 
                     
                     ! 
                   
                   
                     
                       
                         ( 
                         
                           m 
                           - 
                           i 
                         
                         ) 
                       
                       ! 
                     
                     · 
                     
                       
                         ( 
                         
                           n 
                           - 
                           j 
                           - 
                           1 
                         
                         ) 
                       
                       ! 
                     
                   
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
   
     FIG. 6  shows the rectangle [a,b,c,d] (see  FIG. 2 ) wherein there is a half or partial horizontal segment (see  FIG. 4   c ) through area A. The mathematical expectations M h2 (A) of half horizontal segments can be calculated as follows: 
                     M   h2     ⁡     (   A   )       =     0.5   ·       N   ⁢       (     P1   ,     A   ′       )     ·     N   ⁡     (       A   ′′′     ,   P2     )             N   ⁡     (     P1   ,   P2     )                   (   5   )               
where
 
N(A′″, P 2 ) is the number of possible paths from area A′″ to P 2 , and coefficient 0.5 indicates that there is only half of a horizontal segment in area A.
 
   Taking into account the formula (equation (1) above) for the number N(P 1 , P 2 ) of paths between two points, all the numbers which are needed to calculate the mathematical expectation M h2 (A) can be found: 
   
     
       
         
           
             
               
                 
                   N 
                   ⁡ 
                   
                     ( 
                     
                       
                         A 
                         ′′′ 
                       
                       , 
                       P2 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ( 
                       
                         m 
                         - 
                         i 
                         + 
                         n 
                         - 
                         j 
                         - 
                         1 
                       
                       ) 
                     
                     ! 
                   
                   
                     
                       
                         ( 
                         
                           m 
                           - 
                           i 
                           - 
                           1 
                         
                         ) 
                       
                       ! 
                     
                     · 
                     
                       
                         ( 
                         
                           n 
                           - 
                           j 
                         
                         ) 
                       
                       ! 
                     
                   
                 
               
             
             
               
                 ( 
                 6 
                 ) 
               
             
           
         
       
     
   
     FIG. 7  shows the rectangle [a,b,c,d] (see  FIG. 2 ) wherein there is another type of half or partial horizontal segment (see  FIG. 4   d ) through area A. The mathematical expectations M h3 (A) of half horizontal segments can be calculated as follows: 
                     M   h3     ⁡     (   A   )       =     0.5   ·       N   ⁢       (     P1   ,     A   ″″       )     ·     N   ⁡     (     A   ,   P2     )             N   ⁡     (     P1   ,   P2     )                   (   7   )               
where
 
N(P 1 , A″″) is the number of possible paths from P 1  to area A″″, and coefficient 0.5 indicates that there is only half of a horizontal segment in area A.
 
   Taking into account the formula (equation (1) above) for the number N(P 1 , P 2 ) of paths between two points, all the numbers which are needed to calculate the mathematical expectation M h3 (A) can be found: 
   
     
       
         
           
             
               
                 
                   N 
                   ⁡ 
                   
                     ( 
                     
                       P1 
                       , 
                       
                         A 
                         ″″ 
                       
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ( 
                       
                         i 
                         + 
                         j 
                         - 
                         3 
                       
                       ) 
                     
                     ! 
                   
                   
                     
                       
                         ( 
                         
                           i 
                           - 
                           2 
                         
                         ) 
                       
                       ! 
                     
                     · 
                     
                       
                         ( 
                         
                           j 
                           - 
                           1 
                         
                         ) 
                       
                       ! 
                     
                   
                 
               
             
             
               
                 ( 
                 8 
                 ) 
               
             
           
         
       
     
   
   To determine the whole mathematical expectation M h   All (A) of all horizontal segments of all connections, the following summation is calculated: 
                     M   h   All     ⁡     (   A   )       =       ∑     c   ⁢           ⁢   ε   ⁢           ⁢   Connections       ⁢           ⁢       M   h   c     ⁡     (   A   )                 (   9   )               
where M h   c (A)=M h (a) is the whole mathematical expectation of horizontal segments in area A for one connection c.
 
   The same approach can be used to obtain formulas for vertical segments and the case where P 1  is higher than P 2 . 
   From the formulas above, it can be concluded that the time complexity of the algorithm will depend on how fast factorials (n!) Can be calculated. If a straightforward calculation is used, then the time complexity for one connection and one area is O(m+n). The time complexity for one connection and all areas (see  FIG. 2 ) is O(M DP N DP (m+n)). Finally, the time complexity for all N connections and all areas is O(M DP N DP N(m+n)). There are several ways how to deduce the time complexity, especially for long connections with large m and n. One method is to use the Sterling formula for factorial calculation:
 
 n!=e   (n+0.5)·1nn−n+1n√{square root over (2π)}   (10)
 
Then, the time complexity becomes O(M DP N DP N). The same time complexity and even better time can be obtained if factorials of integer numbers are tabulated in advance for the range of approximately [1–100].
 
   The time efficient method (time complexity is proportional to the product of the connections and areas) described above can be used to accurately estimate horizontal and vertical wire density in different areas of datapath or hardmac. The approach is a good probabilistic model for connections going through areas with high wire density. The model differentiates between horizontal and vertical segments, and takes into account all possible shortest length configurations of connections. The model also provides for the calculation of a congestion map. 
   However, the approach described above has the following two drawbacks for chip areas with low and middle wire density. First, it assumes that the connection can have any configuration with the same probability. This is not always true as the connection more likely has a configuration with a small number of bends in chip areas with low and middle wire density. Second, it assumes that the probability of any connection configuration that goes through or near the center of the bounding box (i.e. rectangle [a,b,c,d]) (see  FIG. 8 ) around the connection is higher than for other configurations. This is not always true as it will depend on the location of other pins and wires. 
   A better approach uses the model with minimum bends in areas with low wire density, and uses models with more bends in areas with middle and high wire density. The rule is: “the more wire density the more bends in the model”. First, the model with minimum bends is found, then the model is used recursively to build other models with more bends. 
   Initially, the chip is divided into M DP  by N DP  squared areas as shown in  FIG. 8 , where each area size is about equal to the width of placement columns (or cell width) (in some cases the chip may be rotated 90 degrees, hence there are no placement columns, but rather placement rows). 
   The minimum bends model (i.e. model 1) describes all connection configurations with only one bend and the shortest length.  FIGS. 9   a  and  9   b  show these configurations for connection C from pin P 1  to pin P 2 . 
   The probability P(a) for each area A of the connection bounding box [a,b,c,d] to have the connection (P 1 , P 2 ) will now be found (see  FIG. 10 ). For any area A 1  from [a,b,c,d] there exists some probability P(A)&gt;0 that connection (P 1 , P 2 ) will go through this area, and for any area A outside [a,b,c,d] there is zero probability that connection (P 1 , P 2 ) will go through this area. If probability P(A) is known, then the mathematical expectation of area A having connection (P 1 , P 2 ) is M(A)=P(A). Any connection (P 1 , P 2 ), where P 1  is lower than P 2 , con go through area A in four different ways as shown in  FIG. 10 . The case where pins P 1  and P 2  are placed as shown in  FIGS. 9   a  and  9   b  will be considered. For the situation where pin P 1  is higher than pin P 2 , the analysis will be analogous. 
     FIG. 11   a  shows the bounding box [a,b,c,d] (see  FIG. 10 ) ( FIGS. 10 ,  11   a ,  11   b ,  12 ,  13  and  15 – 17  also show the numeration of the columns and rows which form the rectangle or bounding box [a,b,c,d]), and all horizontal probabilities (mathematical expectations) for the configuration shown in  FIG. 9   a . Areas with a full horizontal segment have 0.5 probability, because there are only two possible configuration, while areas with a half horizontal segment have 0.25 probability, because these areas contain about 0.5 part of the segment and there are only two possible configurations.  FIG. 11   b  shows all the horizontal probabilities for the configuration shown in  FIG. 9   b.    
   The whole mathematical expectation M h (A) can be found as a sum:
 
 M   h ( A )= M   h1 (A)+ M   h2 (A)  (11)
 
of mathematical expectations for both configurations shown in  FIG. 11  (see  FIG. 12 ). The formula for mathematical expectation M h (A) is as follows:
 
 M   h ( A )=0.5 if  i= 1 and  j= 2, 3 , . . . , n− 1  (12)
 
 M   h ( A )=0.5 if  i=m  and  j= 2,3 , . . . , n− 1  (13)
 
 M   h ( A )=0.25 if  i= 1 and  j= 1 or  j=n   (14)
 
 M   h ( A )=0 if  i= 2, 3 , . . . , m− 1 and  j= 1, 2 , . . . , n,   (15)
 
where local (inside [a,b,c,d]) numeration of rows and columns is used.
 
   The same formulas can be used for horizontal segments when point P 1  is higher than point P 2 . 
   To determine the mathematical expectation M h   All (A) of all horizontal segments of all the connections, the following summation is calculated: 
                     M   h   All     ⁡     (   A   )       =       ∑     c   ⁢           ⁢   ε   ⁢           ⁢   Connections       ⁢           ⁢       M   h   c     ⁡     (   A   )                 (   16   )               
where M h   c (A) M h (A) is the whole mathematical expectation of horizontal segments in area A for one connection c.
 
   The same approach is used to obtain formulas for vertical segments (see  FIG. 13 ):
 
 M   v ( A )=0.5 if  j− 1 and  i= 2, 3 , . . . , m   −1   (17)
 
 M   v ( A )=0.5 if  j=m  and  i= 2,3 , . . . , m   −1   (18)
 
 M   v ( A )=0.25 if  j= 1 and  i= 1 or  i=m   (19)
 
 M   v ( A )=0 if  j= 2,3 , . . . , n− 1 and  i= 1,2 , . . . , m,   (20)
 
where local (i.e. inside [a,b,c,d]) numeration of rows and columns is used.
 
   The same formulas can be used for vertical segments when point P 1  is higher than point P 2 . 
   To calculate the mathematical expectation M v   All  (A) of all vertical segments of all the connections, the following summation is calculated: 
   
     
       
         
           
             
               
                 
                   
                     M 
                     v 
                     All 
                   
                   ⁡ 
                   
                     ( 
                     A 
                     ) 
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       c 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       ε 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       Connections 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       M 
                       v 
                       c 
                     
                     ⁡ 
                     
                       ( 
                       A 
                       ) 
                     
                   
                 
               
             
             
               
                 ( 
                 21 
                 ) 
               
             
           
         
       
     
   
   From the formulas above, it can be concluded that the time complexity of the model will depend on n and m. The time complexity for one connection is O(m+n). The time complexity for all N connections is O(N(m+n)). 
   Next, the obtained formulas for one bend configurations are recursively used to find models with 2, 3 . . . bends. With regard to a connection configuration with two bends, there are two possible types of configurations, and these are shown in  FIGS. 14   a  and  14   b.    
   To determine all mathematical expectations, two bend configurations are considered as a combination of all possible one bend configurations (P 1 , P 2 ′). There are m possible locations for P 2 ′ for the configurations shown in  FIG. 14   b . The whole mathematical expectation M h (A) can be found as a sum:
 
 M   h ( A )= M   h1 ( A )+ M   h2 ( A )+ . . . + M   h ( m+n )( A )  (22)
 
of mathematical expectations for all possible configurations in  FIG. 14 .  FIG. 15  shows the mathematical expectations for the configuration shown in  FIG. 14   a , while  FIG. 16  shows the mathematical expectations for the configuration shown in  FIG. 14   b .  FIG. 17  shows the overall horizontal mathematical expectations.
 
   The formula for mathematical expectation M h (A) is as follows: 
                                       (23)   M h (A) = 0.5(mn + n − (j − 1)m)/nm   if i = 1 and j = 2, 3, . . . ,               n − 1       (24)   M h (A) = 0.5(jm + n)/nm   if i = m and j = 2, 3,               . . . , n − 1       (25)   M h (A) = 0.25(m + 1)/m   if i = 1 and j = 1       (26)   M h (A) = 0.25(n + m)/nm   if i = m and j = 1 or j = n       (27)   M h (A) = 0.25(m + 1)/nm   if i = m and j = n       (28)   M h (A) = 0.5/m   if i = 2, 3, . . . , m − 1               and j = 1, 2, . . . , n,                    
where local (i.e. inside [a,b,c,d]) numeration of rows and columns is used.
 
   The same formulas can be used for horizontal segments when point P 1  is higher than point P 2 . The same approach can be used to obtain formulas for vertical segments: 
                                       (29)   M v (A) = 0.5(mn + m − (i − 1)n)/nm   if j = 1 and i = 2, 3, . . . ,               m − 1       (30)   M v (A) = 0.5(in + m)/nm   if j = n and i = 2, 3, . . . ,               m − 1       (31)   M v (A) = 0.25(n + 1)/n   if j = 1 and i = 1       (32)   M v (A) = 0.25(n + m)/nm   if j = n and i = 1 or i = m       (33)   M v (A) = 0.25(n + 1)/nm   if j = n and i = m       (34)   M v (A) = 0.5/n   if j = 2, 3, . . . , n − 1               and i = 1, 2, . . . , m,                    
where local (i.e. inside [a,b,c,d]) numeration of rows and columns is used.
 
   From the formulas above, it can be concluded that the time complexity of the model will depend on n and m. The time complexity for one connection and one area is O(mn). The time complexity for all N connections is O(Nmn). With the increase of bends in the model, the time complexity also increases. 
   A three bends model will now be outlined. To arrive at the three bend model, the obtained formulas for the two bend configuratiosn will be used.  FIGS. 18   a  and  18   b  show the two possible three bend configurations. To determine all the mathematical expectations, the three bend configurations are considered as being a combination of all possible two bend configurations (P 1 , P 2 ′). There are n possible locations for P 2 ′ for the configuration shown in  FIG. 18   a , and m possible locations for P 2 ′ for the configuration shown in  FIG. 18   b . Using the approach described above recursively, a model with any given number of bends can theoretically be built. However, the calculations to build k-bends (k≧3) models may be such that such a model would be impractical in light of the large expense compared to the relatively small improvement in accuracy. To increase the speed of all the calculations, all possible matrices for the mathematical expectations for given sizes of connections m and n can be tabulated (there will be mn matrices for each model). Then, for any k-bends model, the time complexity for all N connections will always be O(Nmn) due to the fact that the time for tabulation can be ignored since the tabulation is only perormed once. 
   The time efficient models described above can be used to accurately estimate horizontal and vertical wire density in different areas of datapath or hardmac. These models take into account all possible minimal bends and shortest length configurations of the connection. Thus, these models are accurate enough to be used for wire density estimation in areas with low, middle and high wire density. Preferably, the model with minimum bends is used in areas with low wire density, and models with more bends are used in areas with middle and high wire density. 
   While embodiments of the present invention are shown and described, it is envisioned that those skilled in the art may devise various modifications of the present invention without departing from the spirit and scope of the appended claims.