Congestion-driven placement method and computer-implemented integrated-circuit design tool

Claim 3

The method of claim 1, wherein: the balancing includes hierarchically adjusting the macrocell density amongst regions; and said cost estimation includes a vertical and horizontal supply, and a vertical and horizontal demand, where a weight is attached to each term that is based on the number of available interconnecting layers in a current design and any preferred routing direction for each layer.

Claim 4

An electronic design automation tool comprising: a hierarchical quadratic programming layout process with a Min-Cut placement process to improve wire length, wherein a single region with a set of macrocells to be placed is set as an initial condition and arithmetic processes are used to solve quadratic equations based on the weighted clique model of net routing, and wherein at a next iteration level, said Min-Cut is used to split the macrocells with severe overlapping into two sub-regions with balanced macrocell densities such that the resulting macrocell placements provide uniform densities across the whole core that suffer from localized routing congestion; and a hierarchical look-ahead congestion-driven placement process included in each iteration level of said splitting of said regions into sub-regions that estimates congestion in the next iteration level, balances the routing resources and adjusts macrocell densities.

Claim 5

An electronic design automation tool comprising: a hierarchical quadratic programming layout process with a Min-Cut placement process to improve wire length, wherein a single region with a set of macrocells to be placed is set as an initial condition and arithmetic processes are used to solve quadratic equations based on the weighted clique model of net routing, and wherein at a next iteration level, said Min-Cut is used to split the macrocells with severe overlapping into two sub-regions with balanced macrocell densities such that the resulting macrocell placements provide uniform densities across the whole core that suffer from localized routing congestion; and a hierarchical look-ahead congestion-driven placement process included in each iteration level of said splitting of said regions into sub-regions that estimates congestion in the next iteration level, balances the routing resources and adjusts macrocell densities.

Claim 6

The tool of claim 3, further comprising: means for defining the area of a sub-region (A), the total macrocell area of the sub-region (A c ), the macrocell area to be removed from the sub-region (A m ), the actual congestion cost of a sub-region (C a ), the target congestion cost of the sub-region (C t ), a difference between the actual and the target congestion cost of a sub-region (C t -C a ) which can be positive or negative, and the congestion per macrocell area (R c ).

Claim 7

The tool of claim 4, wherein: said target congestion cost of a first sub-region (C t1 ) is the sum of the actual congestion costs of the first and a second sub-region (C a1 and C a2 ) multiplied by the area of the first sub-region (A 1 ), all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t1 =(C a1 +C a2 ) A 1 /(A 1 +A 2 ).

Claim 8

The tool of claim 4, wherein: said target congestion cost of the second sub-region (C t2 ) is the sum of the actual congestion costs of the first and second sub-regions (C a1 and C a2 ) multiplied by the area of the second sub-region (A 2 ), and all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t2 =(C a1 +Ca 2 ) A 2 /(A 1 +A 2 ).

Claim 9

The tool of claim 4, wherein: said congestion per macrocell area of the first region (R c1 ) is the ratio of the actual congestion cost of the first sub-region (C a1 ) to the total macrocell area of the first sub-region (A c1 ) that can be expressed mathematically as, R c1 =C a1 /A c1 .

Claim 10

The tool of claim 4, wherein: said congestion per macrocell area of the second region (R c2 ) is the ratio of the actual congestion cost of the second sub-region (C a2 ) to the total macrocell area of the second sub-region (A c2 ) that can be expressed mathematically as, R c2 =C a2 /A c2 .

Claim 11

The tool of claim 4, wherein: said macrocell area to be removed from the first sub-region (A m1 ) is the absolute difference between the target congestion cost of the first sub-region (C t1 ) and the actual congestion cost of the first sub-region (C a1 ), divided by the congestion per macrocell area of the first sub-region (R c1 ) that can be expressed mathematically as, A m1 =|C t1 -C a1 |/R c1 .

Claim 12

The tool of claim 4, wherein: said macrocell area to be removed from the second sub-region (A m2 ) is the absolute difference between the target congestion cost of the second sub-region (C t2 ) and the actual congestion cost of the second sub-region (C a2 ), divided by the congestion per macrocell area of the second sub-region (R c2 ) that can be expressed mathematically as, A m2 =|C t2 -C a2 |/R c2 .

Claim 13

The tool of claim 4, wherein: the final amount of macrocell area (A m ) to be moved from the sub-region with a positive (C t -C a ) to the other sub-region with a negative (C t -C a ) is the average of the two macrocell areas to be moved (Am1 and Am2) and can be expressed mathematically as, A m =(A m1 +A m2 )/2.

Claim 14

An electronic design automation tool comprising: a hierarchical quadratic programming layout process with a Min-Cut placement process to improve wire length, wherein a single region with a set of macrocells to be placed is set as an initial condition and arithmetic processes are used to solve quadratic equations based on the weighted clique model of net routing, and wherein at a next iteration level, said Min-Cut is used to split the macrocells with severe overlapping into two sub-regions with balanced macrocell densities such that the resulting macrocell placements provide uniform densities across the whole core that suffer from localized routing congestion; a hierarchical look-ahead congestion-driven placement process included in each iteration level of said splitting of said regions into sub-regions that estimates congestion, in the next iteration level balances the routing resources and adjusts macrocell densities; and means for defining the area of a sub-region (A), the total macrocell area of the sub-region (A c ), the macrocell area to be removed from the sub-region (A m ), the actual congestion cost of a sub-region (C a ), the target congestion cost of the sub-region (C t ), a difference between the actual and the target congestion cost of a sub-region (C t -C a ) which can be positive or negative, and the congestion per macrocell area (R c ); wherein, said target congestion cost of a first sub-region (C t1 ) is the sum of the actual congestion costs of the first and a second sub-region (C a1 and C a2 ) multiplied by the area of the first sub-region (A 1 ), all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t1 =(C a1 +C a2 ) A 1 /(A 1 +A 2 ); wherein, said target congestion cost of the second sub-region (C t2 ) is the sum of the actual congestion costs of the first and second sub-regions (C a1 and C a2 ) multiplied by the area of the second sub-region (A 2 ), and all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t2 =(C a1 +C a2 ) A 2 /(A 1 +A 2 ); wherein, said congestion per macrocell area of the first region (R c1 ) is the ratio of the actual congestion cost of the first sub-region (C a1 ) to the total macrocell area of the first sub-region (A c1 ) that can be expressed mathematically as, R c1 =C a1 /A c1 ; wherein, said congestion per macrocell area of the second region (R c2 ) is the ratio of the actual congestion cost of the second sub-region (C a2 ) to the total macrocell area of the second sub-region (A c2 ) that can be expressed mathematically as, R c2 =C a2 /A c2 ; wherein, said macrocell area to be removed from the first sub-region (A m1 ) is the absolute difference between the target congestion cost of the first sub-region (C t1 ) and the actual congestion cost of the first sub-region (C a1 ), divided by the congestion per macrocell area of the first sub-region (R c1 ) that can be expressed mathematically as, A m1 =|C t1 -C a1 |/R c1 ; wherein, said macrocell area to be removed from the second sub-region (A m2 ) is the absolute difference between the target congestion cost of the second sub-region (C t2 ) and the actual congestion cost of the second sub-region (C a2 ), divided by the congestion per macrocell area of the second sub-region (R c2 ) that can be expressed mathematically as, A m2 =|C t2 -C a2 |/R c2 ; and wherein, the final amount of macrocell area (A m ) to be moved from the sub-region with a positive (C t -C a ) to the other sub-region with a negative (C t -C a ) is the average of the two macrocell areas to be moved (A m1 and A m2 ) and can be expressed mathematically as, A m =(A m1 +A m2 )/2.

Claim 15

An electronic design automation tool comprising: a hierarchical quadratic programming layout process with a Min-Cut placement process to improve wire length, wherein a single region with a set of macrocells to be placed is set as an initial condition and arithmetic processes are used to solve quadratic equations based on the weighted clique model of net routing, and wherein at a next iteration level, said Min-Cut is used to split the macrocells with severe overlapping into two sub-regions with balanced macrocell densities such that the resulting macrocell placements provide uniform densities across the whole core that suffer from localized routing congestion; a hierarchical look-ahead congestion-driven placement process included in each iteration level of said splitting of said regions into sub-regions that estimates congestion, in the next iteration level balances the routing resources and adjusts macrocell densities; and means for defining the area of a sub-region (A), the total macrocell area of the sub-region (A c ), the macrocell area to be removed from the sub-region (A m ), the actual congestion cost of a sub-region (C a ), the target congestion cost of the sub-region (C t ), a difference between the actual and the target congestion cost of a sub-region (C t -C a ) which can be positive or negative, and the congestion per macrocell area (R c ); wherein, said target congestion cost of a first sub-region (C t1 ) is the sum of the actual congestion costs of the first and a second sub-region (C a1 and C a2 ) multiplied by the area of the first sub-region (A 1 ), all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t1 =(C a1 +C a2 ) A 1 /(A 1 +A 2 ); wherein, said target congestion cost of the second sub-region (C t2 ) is the sum of the actual congestion costs of the first and second sub-regions (C a1 and C a2 ) multiplied by the area of the second sub-region (A 2 ), and all divided by the sum of the areas of the first and second sub-regions (A 1 and A 2 ) that can be expressed mathematically as, C t2 =(C a1 +C a2 ) A 2 /(A 1 +A 2 ); wherein, said congestion per macrocell area of the first region (R c1 ) is the ratio of the actual congestion cost of the first sub-region (C a1 ) to the total macrocell area of the first sub-region (A c1 ) that can be expressed mathematically as, R c1 =C a1 /A c1 ; wherein, said congestion per macrocell area of the second region (R c2 ) is the ratio of the actual congestion cost of the second sub-region (C a2 ) to the total macrocell area of the second sub-region (A c2 ) that can be expressed mathematically as, R c2 =C a2 /A c2 ; wherein, said macrocell area to be removed from the first sub-region (A m1 ) is the absolute difference between the target congestion cost of the first sub-region (C t1 ) and the actual congestion cost of the first sub-region (C a1 ), divided by the congestion per macrocell area of the first sub-region (R c1 ) that can be expressed mathematically as, A m1 =|C t1 -C a1 |/R c1 ; wherein, said macrocell area to be removed from the second sub-region (A m2 ) is the absolute difference between the target congestion cost of the second sub-region (C t2 ) and the actual congestion cost of the second sub-region (C a2 ), divided by the congestion per macrocell area of the second sub-region (R c2 ) that can be expressed mathematically as, A m2 =|C t2 -C a2 |/R c2 ; and wherein, the final amount of macrocell area (A m ) to be moved from the sub-region with a positive (C t -C a ) to the other sub-region with a negative (C t -C a ) is the average of the two macrocell areas to be moved (A m1 and A m2 ) and can be expressed mathematically as, A m =(A m1 +A m2 )/2.