Process for fast cell placement in integrated circuit design

• US 6,704,915 B1
• Filed: 06/12/2001
• Issued: 03/09/2004
• Est. Priority Date: 01/08/2001
• Status: Expired due to Fees

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Grinchuk, Mikhail I., Andreev, Alexander E.
• Primary Examiner(s): Garbowski, Leigh M.
• Application Number:
  US09/879,643
• Time in Patent Office: 1,001 Days
• Field of Search: 716/1, 716/2, 716/3, 716/7, 716/8, 716/9, 716/10, 716/11
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A process for re-designing IC chips by altering the positions of cells from a first to a second IC chip layout. An x,y grid is established for the first and second IC layouts such that each cell has identifying x,y coordinates in the first layout. Columns are established in the second layout based on the bounds of the second layout in the x-direction. The cells are sorted to the columns in the order of cell x-coordinates to establish new x-coordinates for each cell based on the x-coordinates of the respective column. The cells are sorted in each column to establish y-coordinates for each cell based on the height of the cells in the column and the height of the column.

Claims

1. A process for altering a distribution of N cells in a first integrated circuit chip layout to position the cells in a second integrated circuit chip layout, the first and second layouts each having respective bounds, the process comprising steps of:

a) establishing an x,y grid for the first and second integrated chip layouts such that each cell has x,y coordinates in the first layout and a height in the y-direction;

b) establishing K columns based on the bounds of the second layout in the x-direction, K being an integer;

c) sorting the cells to the K columns in order of cell x-coordinates in the first layout to establish x-coordinates in the second layout for each cell based on the x-coordinates of the respective column, each column having a height in the y-direction; and

d) sorting the cells in each column to establish y-coordinates in the second layout for each cell based on the height of the cells in the column and the height of the column.

2. The process of claim 1, wherein step (c) is performed by:

c1) assigning a cell index to each cell in each column, and

c2) applying a recursive algorithm to distribute cells of each column to positions in the x-direction between x-coordinates of adjacent columns based on the respective cell indices.

3. The process of claim 2, wherein the recursive algorithm identifies a plurality of positions between x-coordinates of adjacent columns, and identifies maximum and minimum non-overlapping ranges of x-coordinates for each position.

4. The process of claim 2, further including:

calculating a minimum column height H_min for all columns, wherein H_ave≦

H_min<

(H_ave+h_max), where H_ave is the average height of the columns and h_max is the height of the cell of the chip having the maximum height.

5. The process of claim 4, wherein the minimum column height is calculated by:

ordering the columns in order of cell x-coordinates, defining an index for each column based on the number of cells in the column and the order position of the column, the index for the highest-ordered column being smaller than N and not smaller than N−

1,

defining the height of each column based on the sum of the heights of all cells in the column, and

setting H_min equal to the smallest sum of cell heights for all of the columns.

6. The process of claim 2, wherein step (c2) is performed by

assigning a column index to each column,

calculating an average index between column indices of respective first and second columns,

calculating maximum and minimum possible boundary positions between first and second halves of the first column based on the average index,

partitioning an ordered list of cell indices in the first column into first and second segments such that a cell having an index that is an average between the maximum and minimum indices of the cells defines a partition point,

setting the cell whose index is the average to an index between the maximum and minimum possible boundary positions, and

recursively distributing the cells of the first and second segments to the first and second halves of the column.

7. The process of claim 1, wherein step (d) includes steps of:

d1) computing a distance real_D[i] between y-coordinates of adjacent cells of each column based on the first layout,

d2) computing a distance min_D[i] in the y-direction between the adjacent cells based on the heights of the adjacent cells, and

d3) computing an overlap over_D[i] based on a difference between real_D[i] and min_D[i].

8. The process of claim 7, further including the step of:

d4) calculating a correction factor corr_D[i] for each cell.

9. The process of claim 8, wherein step (d4) is performed by:

defining a tree having a plurality of vertices V,

calculating over_D[V] as equal to over_D[i], if V is the lowest terminal node of the tree, or equal to over_D[V1]+over_D[V2] if V is not the lowest terminal node of the tree, where V1 and V2 are descendants of V,

if over_D[V1]≦

0, calculating corr_D[V1]=−

over_D[V1], and calculating corr_D[V2]=corr_D[V]−

corr_D[V1],

if over_D[V2]≦

0, calculating corr_D[V2]=−

over_D[V2], and calculating corr_D[V1]=corr_D[V]−

corr_D[V2];

if both over_D[V1]and over_D[V2] are greater than zero, calculating corr_D[V1] and corr_D[V2] as solutions to;

10. The process of claim 1, further including, before step (c):

shifting the x-coordinates of each cell in the x-direction by an amount within a selected range.

11. A computer useable medium having a computer readable program embodied therein for addressing data to alter a distribution of N cells in a first integrated circuit chip layout to position the cells in a second integrated circuit chip layout, the computer readable program comprising:

computer readable program code for causing the computer to establish an x,y grid for the first and second integrated chip layouts such that each cell has x,y coordinates in the first layout and a height in the y-direction;

computer readable code for causing the computer to establish K columns based on the bounds of the second layout in the x-direction, K being an integer;

computer readable code for causing the computer to sort the cells to the K columns in order of cell x-coordinates in the first layout to establish x-coordinates in the second layout for each cell based on the x-coordinates of the respective column, each column having a height in the y-direction; and

computer readable code for causing the computer to sort the cells in each column to establish y-coordinates in the second layout for each cell based on the height of the cells in the column and the height of the column.

12. The computer readable medium of claim 11, further including:

computer readable code for causing the computer to assign a cell index to each cell in each column, and

computer readable code for causing the computer to apply a recursive algorithm to distribute cells of each column to positions in the x-direction between x-coordinates of adjacent columns based on the respective cell indices.

13. The computer readable medium of claim 12, wherein the computer readable code that causes the computer to apply the recursive algorithm also causes the computer to identify a plurality of positions between x-coordinates of adjacent columns and maximum and minimum non-overlapping ranges of x-coordinates for each position.

14. The computer readable medium of claim 12, further including

computer readable code for causing the computer to calculate a minimum column height, H_min, for all columns wherein H_ave≦

H_min<

(H_ave+h_max), where H_ave is the average height of the columns and h_maxis the height of the cell of the chip having the maximum height.

15. The computer readable medium of claim 14, wherein the computer code that causes the computer to calculate a minimum column height includes:

computer readable code for causing the computer to order the columns in order of cell x-coordinates,

computer readable code for causing the computer to define an index for each column based on the number of cells in the column and the order position of the column, the index for the highest-ordered column being smaller than N and not smaller than N−

1,

computer readable code for causing the computer to define the height of each column based on the sum of the heights of all cells in the column, and

computer readable code for causing the computer to set H_min equal to the smallest sum of cell heights for all of the columns.

16. The computer readable medium of claim 12, wherein the computer code that causes the computer to apply a recursive algorithm to distribute cells includes:

computer readable code for causing the computer to assign a column index to each column,

computer readable code for causing the computer to calculate an average index between column indices of respective first and second columns,

computer readable code for causing the computer to calculate maximum and minimum possible boundary positions between first and second halves of the first column based on the average index,

computer readable code for causing the computer to partition an ordered list of cell indices in the first column into first and second segments such that a cell having an index that is an average between the maximum and minimum indices of the cells defines a partition point,

computer readable code for causing the computer to set the cell whose index is the average to an index between the maximum and minimum possible boundary positions, and

computer readable code for causing the computer to recursively distribute the cells of the first and second segments to the first and second halves of the column.

17. The computer readable medium of claim 11, wherein the computer readable code that causes the computer to apply a recursive algorithm includes:

computer readable code for causing the computer to compute a distance real_D[i] between y-coordinates of adjacent cells of each column based on the first layout,

computer readable code for causing the computer to compute a distance min_D[i] in the y-direction between the adjacent cells based on the heights of the adjacent cells, and

computer readable code for causing the computer to compute an overlap over_D[i] based on a difference between real_D[i] and min_D[i].

18. The computer readable medium of claim 17, further including:

computer readable code for causing the computer to calculate a correction factor corr_D[i] for each cell.

19. The computer readable medium of claim 18, wherein the computer readable code causing the computer to add a correction factor includes:

computer readable code that define a tree having a plurality of vertices V,

computer readable code for causing the computer to identify if V is the lowest vertex in the tree,

computer readable code for causing the computer to calculate over_D[V] equal to over D[i], if V is the lowest terminal node of the tree,

computer readable code for causing the computer to calculate over_D[V] equal to over_D[V1]+over_D[V2] if V is not the lowest terminal node of the tree, where V1 and V2 are descendants of V,

computer readable code for causing the computer to calculate whether either or both over_D[V1] and over_D[V2] is greater than 0,

computer readable code for causing the computer to calculate corr_D[V1]=−

over_D[V1], and corr_D[V2]=corr_D[V]−

corr_D[V1], if over_D[V1]≦

0,

computer readable code for causing the computer to calculate corr_D[V2]=−

over_D[V2], and corr_D[V1]=corr_D[V]−

corr_D[V2], if over_D[V2]≦

0,

computer readable code for causing the computer to calculating corr_D[V1] and corr_D[V2] as solutions to;

20. The computer readable medium of claim 11, further including:

computer readable code for causing the computer to shifting the x-coordinates of each cell in the x-direction by an amount within a selected range.