Quick placement of electronic circuits using orthogonal one dimensional placements

• US 6,665,851 B1
• Filed: 12/04/2001
• Issued: 12/16/2003
• Est. Priority Date: 12/04/2001
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Naylor, William C., Donelly, Ross A.
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): LIN, SUN J
• Application Number:
  US10/006,965
• Time in Patent Office: 742 Days
• Field of Search: 716/8, 716/9, 716/10, 716/11, 716/1
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method and system for the quick placement of electronic circuits using orthogonal one dimensional placements. All circuits of a design may be placed in a linear dimension to obtain a first placement. Next, those same circuits may be placed in a second linear dimension, orthogonal to the first dimension, in order to obtain a second placement. Finally, a two dimensional placement for the circuits may be created by selecting for each circuit element a first coordinate from the first placement and a second coordinate from the second placement.

Claims

1. A method for placing electronic circuits, the method comprising:

a) placing said circuits in a first linear dimension to obtain a first placement;

b) placing said circuits in a second linear dimension to obtain a second placement, wherein said second linear dimension is orthogonal to said first linear dimension; and

c) assigning a two dimensional placement for said circuits by selecting for each circuit element a first coordinate from said first placement and a second coordinate from said second placement,

wherein placing said circuits in said first linear dimension and said second linear dimension include assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval is a desired length of placement.

2. The method as described in claim 1 further comprising:

d) placing said circuits simultaneously in two dimensions, wherein said two dimensional placement is an input to said placing.

3. The method as described in claim 1 wherein said first linear dimension is parallel to an edge of a semiconductor package.

4. The method as described in claim 1 wherein said second linear dimension is parallel to an edge of a semiconductor package.

5. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports; and

c) placing remaining cells in available positions along said interval.

6. The method as described in claim 5 wherein said interval is the length of one side of an integrated circuit.

7. The method as described in claim 5 wherein said c) comprises:

c1) placing remaining cells using a random choice in selecting one of said remaining cells from a plurality of said remaining cells.

8. The method as described in claim 5 further comprising:

d) dividing said interval into a first interval and a second interval.

9. The method as described in claim 8 wherein said first interval represents substantially one half of said interval.

10. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports; and

c) placing remaining cells alternately in an available positions nearest to said beginning of said interval and alternately in an available position nearest to said end of said interval.

11. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports;

c) placing remaining cells in available positions along said interval;

d) organizing said remaining cells into a priority queue; and

e) selecting one of said remaining cells from said priority queue.

12. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports; and

c) placing remaining cells in available positions along said interval,

wherein said c) comprises;

c1) organizing said remaining cells into a first priority queue, a second priority queue and an unattached list;

c2) selecting one of said remaining cells from selectively said first priority queue, said second priority queue and said unattached list; and

c3) placing said one of said remaining cells in an available position nearest to said beginning of said interval if said one of said remaining cells was selected from said first priority queue, placing said one of said remaining cells in an available position nearest to said end of said interval if said one of said remaining cells was selected from said second priority queue, and placing said one of said remaining cells in available position selectively in an available position nearest to said beginning of said interval and in an available position nearest to said end of said interval if both said first priority queue and said second priority queue are empty, wherein said placing results in a fixed cell.

13. The method as described in claim 12 further comprising:

d) repeating said a) through c3) until all cells are placed.

14. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports;

c) placing remaining cells in available positions along said interval; and

d) assigning a pull direction to a net attached to one of said fixed cells.

15. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports;

c) placing remaining cells in available positions along said interval; and

d) assigning a pull value to a net attached to one of said remaining cells.

16. The method as described in claim 15 wherein said pull value of said net is given by the relationship:

pull value=w/square root((number of cells attached to said net)−

1), wherein said w is an optional user-defined weighting factor.

17. A method of placing electronic circuits in one dimension, the method comprising:

a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;

b) placing fixed cells at the linear location of their fixing ports;

c) placing remaining cells in available positions along said interval;

d) dividing said interval into a first interval and a second interval;

e) computing a pull value for a net attached to one of said remaining cells;

f) assigning a pull direction to said pull value as low pull if said net is attached to one of said fixed cells located within said first interval; and

g) assigning a pull direction to said pull value as high pull if said net is attached to one of said fixed cells located within said second interval.

18. The method as described in claim 17 further comprising:

h) computing an edge pull value for a remaining cell, wherein said edge pull value is the difference between the total high pull of all nets attached to said remaining cell less the total low pull of all nets attached said remaining cell; and

i) computing an unattached pull value for said remaining cell, wherein said unattached pull value is the total pull of all nets attached to said remaining cell, wherein said nets are not attached to a fixed cell.

19. A method of placing electronic circuits in one dimension, the method comprising:

a) placing cells in one dimension to produce a first placement;

b) moving cells in said first placement to improve wire length, wherein said moving produces a new placement; and

c) creating a data structure for determining the number of wires crossing a point in said new placement.

20. The method as described in claim 19 further comprising using a random choice in the selection of one of a plurality of cells to move.

21. The method as described in claim 19 wherein said c) comprises:

c1) creating a tree data structure.

22. The method as described in claim 19 wherein said c) comprises:

c1) creating a skip list data structure.

23. The method as described in claim 19 wherein said b) comprises:

b1) choosing a cell at random from said first placement;

b2) determining the optimal destination to relocate said cell;

b3) shifting cells between the location of said cell in said first placement and said optimal destination to make room for said cell; and

b4) moving said cell to said optimal destination.

24. The method as described in claim 23 further comprising:

d) repeating said b1) through b4), wherein said moving produces an improved placement, wherein said improved placement is used in place of said first placement for subsequent iterations.

25. The method as described in claim 23 wherein said b2) further comprises:

b2a) finding a value x which minimizes f(x)=g(x)+h(x),

wherein x is a candidate destination position for a cell,

wherein h(x) is a piecewise linear function describing the changes in total wire length caused by moving said cell to said position x, and g(x) is a piecewise linear function describing the changes in total wire length caused by moving the cells between said cell and said position.

26. The method as described in claim 25 wherein said finding comprises a branch and bound method.

27. A method of placing electronic circuits in one dimension, the method comprising:

a) placing cells in one dimension to produce a first placement;

b) clustering cells to form a super cell; and

c) moving cells in said first placement to improve wire length, wherein said moving produces a new placement,

wherein said b) comprises;

b1) calculating the number of wires passing through every point in said first placement;

b2) initializing a current range value to be empty;

b3) beginning at the cell at the beginning of the placement interval;

b4) adding the number of wires passing through said cell to said current range value;

b5) finding the best cut point within a span of said current range value;

b6) recording said best cut point as a final cut point and setting the current range value to be empty; and

b7) moving to the next cell and repeating said b4) through b7).