# US 8,751,995 B1 · Method of common-centroid IC layout generation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,751,995 B1
- Document ID: US8751995B1
- Status: Granted
- Kind: B1
- Application number: 13/919,548
- Filed: 2013-06-17
- Granted: 2014-06-10
- Earliest claimed: 2013-06-17
- Assignees: National Chung Cheng University
- Applicants: National Chung Cheng University
- Inventors: Po-Hung Lin; Yi-Ting He; Wei-Hao Hsiao
- Web page: https://patentgrep.com/patent/US8751995B1

## CPC

- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of common-centroid IC layout generation includes the following steps of acquiring a netlist of one circuit-element set; summing up the numbers of the unit element of all elements of the circuit-element set to get the total number of the unit elements and then determine the unit element array, the aspect ratio of which is closest to 1, via a combination operation; generating multiple common-centroid placements according to the unit element array and applying global routing assignment to each of the common-centroid placements; proceeding with cost evaluation in such a way that a cost calculation is applied to each of the common-centroid placements to get a corresponsive value; and comparing all of the common-centroid placements according to the values got from the cost evaluation and selecting the common-centroid placement corresponding to one of the values according to a predetermined condition for detailed routing.

## Claims

### Claim 1

A non-transitory computer-readable medium containing instructions, which when read and executed by a computer, cause the computer to execute a method of common-centroid IC layout, wherein the method comprises steps of:
acquiring a netlist of an circuit-element set, the netlist at least containing the number of unit element corresponding to each element of the circuit-element set;
summing up the numbers of the unit elements of all elements of the circuit-element set to get the total number of the unit elements and, based on said total number of the unit elements, determining a unit element array, having an aspect ratio closest to 1 by an algorithm, the aspect ratio being a ratio of the number of the unit elements at a column of the unit element array to the number of the unit elements at a row of the unit element array;
generating multiple common-centroid placements according to the umnnlement array and applying global routing assignment to each of the common-centroid placements where each of the common-centroid placements is formed of multiple nets, each of which is formed of multiple unit element;
performing cost evaluation by applying a cost calculation to each common-centroid placement to get a corresponsive value, which can be used for evaluating matching quality of each common-centroid placement and the induced parasitics incurred by the global routing assignment; and
comparing the values acquired from all of the common-centroid placements according to the cost evaluation and select the common-centroid placement to which one of the values corresponds according to a predetermined condition for detailed routing assignment.

### Claim 2 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein the algorithm is based on the following two equations:
r
1
=
⌈
∑
i
=
1
m
⁢
k
i
⌉
;
s
1
=
⌈
∑
i
=
1
m
⁢
k
i
r
1
⌉
(
1
)
r
2
=
r
1
+
1
;
s
2
=
⌈
∑
i
=
1
m
⁢
k
i
r
2
⌉
(
2
)
where m denotes the total unit element number, r1 and s1 denote the height and width of the array Ar1×s1 respectively, r2 and s2 denote the height and width of the array Ar2×s2 respectively, and k denotes one single unit element;
wherein the two arrays Ar1×s1 and Ar2×s2 are calculated based on the aforesaid algorithm and which of the two arrays is the unit element array having the aspect ratio of 1 can be determined.

### Claim 3 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein the multiple common-centroid placements are generated based on a pair-sequence representation.

### Claim 4 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein among the multiple common-centroid placements generated by the aforesaid unit element array, all of the unit elements belong to the same net must be distributed connected and one-track routable.

### Claim 5 (depends on 4)

The non-transitory computer-readable medium as defined in claim 4, wherein the placement style of distributed connected indicates that all of the unit elements belonging to the same net are unequally divided into a number of groups in which all unit elements form a connected placement and the connected placements of different groups are dispersively distributed all over the unit element array, in such a way that the connected placements are not adjacent to one another, and connected with one another via a plurality of routing tracks, such placement requires at most r/2 (s/2) horizontal (vertical) routing tracks.

### Claim 6 (depends on 4)

The non-transitory computer-readable medium as defined in claim 4, wherein whether all of the unit elements belong to the same net are one-track routable is determined by a determination logic for one of the nets in the unit element array, the determination logic being adapted to make each unit element form a disjoined subset and next to determine one by one whether the unit elements corresponding to different disjoined subsets are adjacent to one another; if the answer is positive, combine the disjoined subsets to which the adjacent unit elements correspond to form a new disjoined subset; after the combination, determine whether there are any other adjacent unit elements; if other adjacent unit elements are still available, combine the disjoined subsets; after the combination, determine whether there are any other adjacent unit elements; combine them if they are available; proceed with this step iteratively until none of any adjacent unit elements corresponding to different disjoined subsets is available; when none of any adjacent unit elements corresponding to different disjoined subsets is available, define the last disjoined subset as a set and then determine whether the next unit element which has not been determined is adjacent to another; after all of the unit elements are determined, the multiple disjoined sets can be combined together and the unit elements in each of the disjoined sets are connected with one another; at last, in these sets, locate a vertical or horizontal channel for connection with the sets and make it serve as a common channel; if the common channel is located, it will be determined that the common-centroid placement is one-track routable, the vertical channel indicating the channel between each two unit elements of the columns in the unit element array, the horizontal channel indicating the channel between each two unit elements of the rows in the unit element array.

### Claim 7 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein the global routing assignment is based on a minimum-weighted bipartite-matching whereby the trunk distance of the trunk, the bridge distance of the bridge wire, and the branch distance of the branch wire are acquired, respectively, and summed up to get the total routing wirelength.

### Claim 8 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein the calculation is based on the following equation:
Φ
=
(
α
×
M
-
M
avg
M
avg
+
β
×
ρ
avg
-
ρ
ρ
avg
+
γ
×
W
-
W
avg
W
avg
+
(
1
-
α
-
β
-
γ
)
×
W
P
-
W
avg
P
W
avg
P
)
(
4
)
where M denotes induced mismatch resulting from oxide-gradient, p denotes an overall correlation coefficient, W denotes the total routing wirelength, Wp denotes the total wirelength parallel to the trunk, α, β, and γ are user-specified parameters and 0≦α,β,γ≦1, the subscript avg denotes the average of the corresponsive parameter, and Φ denotes resultant value of the cost evaluation.

### Claim 9 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein when the comparison proceeds, the predetermined condition is the minimum value.

### Claim 10 (depends on 1)

The non-transitory computer-readable medium as defined in claim 1, wherein The detailed routing assignment includes the steps of arranging the trunks from left to right on the channel between the columns or rows of the unit elements in the unit element array of the selected common-centroid placement; while the trunk wires are arranged, the three-layer horizontal-vertical-horizontal or vertical-horizontal-vertical routing model is used for decreasing the occurrence of parallel problem of the trunk wires between different layers; next the branch wire is arranged; and finally the bridge wire is arranged.