Advanced modular cell placement system with overlap remover with minimal noise

• US 6,026,223 A
• Filed: 06/28/1996
• Issued: 02/15/2000
• Est. Priority Date: 06/28/1996
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Andreev, Alexander E., Koford, James S.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/672,937
• Time in Patent Office: 1,327 Days
• Field of Search: 364/488, 364/491, 364/578
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for refining the position of linearly aligned cells on the surface of a semiconductor chip is disclosed herein. The method comprises defining an array of spaces between cells based on maximum and minimum cell positions, establishing a minimum spacing between cells, and linearly shifting cells in a predetermined manner such that no cells are closer to one another than the minimum spacing between cells. Linear shifting is accomplished by shifting any cell in a positive direction if the spacing associated the cell is less than the minimum spacing between cells; shifting any cell in a negative direction if the spacing associated with the cell is greater than the minimum spacing between cells, but only if all cells on the negative side of the cell have been shifted in their maximum negative direction; and performing positive shifting and negative shifting until all cells have been shifted such that no space between cells is less than the negative space between cells.

Claims

1. A computer implemented method for optimizing cell placement for integrated circuit design, comprising the steps of:

(a) assigning a plurality of cells to one column of an integrated circuit surface abstraction; and

(b) arranging cells in the one column to remove overlap between cells while maintaining a running summation of positive and negative cell movement distances for cells in the one column.

2. A computer implemented method according to claim 1, wherein step (b) comprises sequentially processing the cells in the one column while attempting simultaneously to maintain a minimum cell spacing and to minimize an absolute value of the running summation.

3. A computer implemented method according to claim 2, wherein when processing each cell in step (b), if cell spacing between two cells is less than the minimum cell spacing, then the cell spacing between the two cells is increased and the running summation is adjusted to reflect such increase.

4. A computer implemented method according to claim 2, wherein when processing each cell in step (b), if cell spacing between two cells is greater than the minimum cell spacing and the running summation indicates a net increase in cell spacing, then the cell spacing between the two cells is decreased, but not below the minimum cell spacing, and the running summation is adjusted to reflect any such decrease.

5. A method for efficiently placing a plurality of elements on a surface divided into a plurality of regions each having at least one linear channel thereon, comprising the steps of:

(a) indexing elements in each linear channel;

(b) computing an array representing relative element positions; and

(c) modifying said array such that elements do not overlap.

6. The method of claim 5, wherein said modifying step comprises shifting the cells in a linear manner comprising:

(a) shifting any cell in a positive direction if the spacing associated the cell is less than a minimum spacing between cells;

(b) shifting any cell in a negative direction if the spacing associated with the cell is greater than the minimum spacing between cells, but only if all cells on the negative side of the cell have been shifted in their maximum negative direction; and

(c) performing said positive shifting and said negative shifting steps until all cells have been shifted such that no space between cells is less than the minimum spacing between cells.

7. The method of claim 6, wherein said modifying step comprises:

(d) initializing a counter and selecting a first element associated with the corresponding lowest array element;

(e) increasing position of an element in said linear channel by one unit and decreasing said counter by one if the array element associated with said element is less than the minimum unit spacing between elements, and proceeding to the next element and repeating this step if this condition is satisfied;

(f) decreasing position of an element in said linear channel by one unit and increasing said counter by one if the array element associated with said element is greater than the minimum unit spacing between elements, and proceeding to the next element and reexecuting step (e) if this condition is satisfied;

(g) repeating steps (e) and (f) until step (e) is satisfied;

(h) halting the procedure once all array elements are not less than the minimum spacing between the elements and the counter equals zero; and

(i) modifying element coordinates based on the recalculated array elements.

8. The method of claim 5, wherein said modifying step comprises:

(j) initializing a counter and selecting a first element associated with the corresponding lowest array element;

(k) comparing the value of the selected array element to a minimum allowable spacing between the elements;

(l) increasing the value of the selected array element by one unit and decreasing the counter by one unit if the value of the selected array element is less than the minimum allowable spacing; and

(m) repeating step (l) until the value of the selected array element is not less than the minimum allowable spacing.

9. The method of claim 8, wherein said modifying step further comprises:

(n) increasing the value of the selected array element by one unit and decreasing the counter by one unit if the value of the selected array element is less than a maximum allowable spacing between the elements and the counter is greater than zero; and

(o) repeating step (n) until the value of the counter equals zero.

10. The method of claim 9, wherein said modifying step further comprises:

(p) increasing the counter by the difference between the selected array element and the maximum allowable spacing and decreasing the selected array element to the value of the maximum allowable spacing if the value of the selected array element is greater than the value of the maximum allowable spacing.

11. The method of claim 10, wherein said modifying step further comprises:

(q) defining a variable to be equal to the difference between the selected array element and the minimum allowable spacing;

(r) changing the value of the variable to be equal to the negative value of the counter if the variable is greater than the negative value of the counter;

(s) subtracting the value of the variable from the selected array element; and

(t) adding the value of the variable to the counter.

12. The method of claim 11, wherein said modifying step further comprises:

(u) adjusting the positions of the elements based upon the value of the corresponding array elements.

13. A method for refining the position of linearly aligned cells on the surface of a semiconductor chip, comprising the steps of:

(a) defining an array of spaces between cells based on maximum and minimum cell positions;

(b) establishing a minimum spacing between the cells; and

(c) linearly shifting cells in a predetermined manner such that no cells are closer to one another than the minimum spacing between cells, while maintaining a running summation of positive and negative cell movement distances for the cells.

14. A method according to claim 13, wherein step (c) comprises sequentially processing the cells in the one column while attempting simultaneously to maintain the minimum spacing between cells and to minimize an absolute value of the running summation.

15. A method according to claim 14, wherein when processing each cell in step (c), if cell spacing between two cells is less than the minimum spacing between cells, then the cell spacing between the two cells is increased and the running summation is adjusted to reflect such increase.

16. A method according to claim 14, wherein when processing each cell in step (c), if cell spacing between two cells is greater than the minimum spacing between cells and the running summation indicates a net increase in cell spacing, then the cell spacing between the two cells is decreased, but not below the minimum spacing between cells, and the running summation is adjusted to reflect any such decrease.

17. A system for efficiently locating a plurality of linearly aligned elements, comprising:

(a) computing a spacing array based on maximum and minimum element positions; and

(b) modifying element alignment based on keeping spacing between elements greater than a minimum spacing value, while maintaining a running summation of positive and negative element adjustment distances.

18. A computer storage device containing instructions for a computer to optimize cell placement in an integrated circuit including the following computer implemented steps:

(a) assigning a plurality of cells to one column of an integrated circuit surface abstraction; and

(b) arranging cells in the one column as necessary to remove overlap between cells while maintaining a running summation of positive and negative cell movement distances for cells in the one column.

19. The storage device in claim 18, wherein the storage device is a CD-ROM.

20. The storage device in claim 18, wherein the storage device is a floppy disk.