Advanced modular cell placement system with overlap remover with minimal noise

• US 6,223,332 B1
• Filed: 02/14/2000
• Issued: 04/24/2001
• 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): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/503,691
• Time in Patent Office: 435 Days
• Field of Search: 395/500.02-500.19, 716/1-21
• 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 method for refining the positions of linearly aligned cells on the surface of a semiconductor chip, comprising the steps of:

(a) defining an array of spaces between the linearly aligned cells;

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

(c) processing each space in the array of spaces as follows;

(c1) if a first condition is satisfied, increasing the space, wherein the first condition includes a condition that the space is less than the minimum spacing;

(c2) if a second condition is satisfied, increasing the space, wherein the second condition includes a condition that the first condition has failed and a condition that the space is less than the maximum spacing; and

(c3) if a third condition is satisfied, decreasing the space, wherein the third condition includes a condition that the second condition has failed and a condition that the space is greater than the maximum spacing; and

(d) adjusting the positions of the cells based on the spaces determined in accordance with steps (a) through (c).

2. A method according to claim 1, wherein if the first condition is satisfied, the space is increased by a predetermined amount.

3. A method according to claim 2, wherein if the second condition is satisfied, the space is increased by a second predetermined amount, and wherein the predetermined amount and the second predetermined amount are equal.

4. A method according to claim 1, wherein if the second condition is satisfied, the space is increased by a predetermined amount.

5. A method according to claim 1, wherein the spaces are processed in step (c) in an order in which they occur on the surface of the semiconductor chip.

6. A method according to claim 1, wherein if the third condition is satisfied, the space is decreased to the maximum spacing.

7. A method according to claim 1, wherein step (c) further comprises a step of maintaining a running summation of positive and negative space adjustments.

8. A method according to claim 7, wherein the second condition further comprises a condition that the running summation is greater than zero.

9. A method according to claim 7, further comprising a step of adjusting the space based on whether a fourth condition has been satisfied, wherein the fourth condition includes a condition that a difference between the space and a minimum spacing is less than a predetermined function of the running summation.

10. A method according to claim 9, further comprising a step of reducing the space by a negative of the running summation if the fourth condition is satisfied and reducing the space to the minimum spacing if the fourth condition has failed.

11. A method according to claim 10, wherein the predetermined function of the running summation is the negative of the running summation.

12. A method according to claim 7, further comprising a step of repeating steps (c1) to (c2) for said each space until the running summation becomes zero.

13. A method according to claim 1, further comprising a step of repeating step (c1) for said each space until the first condition is not satisfied.

14. A method according to claim 1, further comprising a step of repeating steps (c1) to (c3) for said each space until the third condition is not satisfied.

15. A method according to claim 1, further comprising a step of reducing the space to the minimum spacing if a fourth condition is satisfied.

16. A method according to claim 1, further comprising a step of repeating step (c) for each space in the array of spaces.

17. A method according to claim 16, wherein at each repetition of step (c) the spaces are processed in an order in which they occur on the surface of the semiconductor chip.

18. A method according to claim 17, wherein during each repetition of step (c) the spaces are processed in a reverse order of that in which said spaces were processed in an immediately preceding repetition.

19. A method according to claim 1, wherein step (c) is repeated with the spaces in the array of spaces being processed forward and backward alternately.

20. An apparatus for refining the positions of linearly aligned cells on the surface of a semiconductor chip, said apparatus comprising:

(a) means for defining an array of spaces between the linearly aligned cells;

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

(c) means for processing each space in the array of spaces as follows;

(c1) if a first condition is satisfied, increasing the space, wherein the first condition includes a condition that the space is less than the minimum spacing;

(c2) if a second condition is satisfied, increasing the space, wherein the second condition includes a condition that the first condition has failed and a condition that the space is less than the maximum spacing; and

(c3) if a third condition is satisfied, decreasing the space, wherein the third condition includes a condition that the second condition has failed and a condition that the space is greater than the maximum spacing; and

(d) means for adjusting the positions of the cells based on the spaces determined by means (a) through (c).

21. A computer-readable medium storing computer-executable process steps for refining the positions of linearly aligned cells on the surface of a semiconductor chip, said process steps comprising steps to:

(a) define an array of spaces between the linearly aligned cells;

(b) establish a minimum spacing and a maximum spacing between the cells;

(c) process each space in the array of spaces as follows;

(c1) if a first condition is satisfied, increase the space, wherein the first condition includes a condition that the space is less than the minimum spacing;

(c2) if a second condition is satisfied, increase the space, wherein the second condition includes a condition that the first condition has failed and a condition that the space is less than the maximum spacing; and

(c3) if a third condition is satisfied, decrease the space, wherein the third condition includes a condition that the second condition has failed and a condition that the space is greater than the maximum spacing; and

(d) adjust the positions of the cells based on the spaces determined in accordance with steps (a) through (c).