Advanced modular cell placement system with sinusoidal optimization

• US 6,085,032 A
• Filed: 06/28/1996
• Issued: 07/04/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): DO, THUAN V
• Application Number:
  US08/671,659
• Time in Patent Office: 1,467 Days
• Field of Search: 364/491, 364/490
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for optimizing placement of cells a surface of a semiconductor chip divided into regions is provided herein. The system repetitively calculates affinities for relocating cells to alternate regions, repositioning cells having a maximum affinity greater than a predetermined threshold to the region providing the maximum affinity for the cell based on an influence parameter. The system then alters the influence parameter and repeats the previous functions for a predetermined number of times.

Claims

1. A system for providing equal densities of elements located in multiple regions on a surface, wherein a capacity penalty influence parameter is associated with the capacity of the regions, comprising:

(a) performing a first predetermined number of discrete placement optimization steps;

(b) setting the capacity penalty influence parameter to a first predetermined value multiplied by the capacity penalty influence parameter;

(c) performing a second predetermined number of discrete placement optimization steps;

(d) setting the capacity penalty influence parameter to a second predetermined value multiplied by the capacity penalty influence parameter;

(e) performing a third predetermined number of discrete placement optimization steps;

(f) setting the capacity penalty influence parameter to a third predetermined value multiplied by the capacity penalty influence parameter;

(g) performing a fourth predetermined number of discrete placement optimization steps; and

(h) setting the capacity penalty influence parameter to a fourth predetermined value multiplied by the capacity penalty influence parameter.

2. The system of claim 1, wherein said system further comprises iterating all steps in combination with other region density levelizing procedures.

3. The system of claim 1, wherein the discrete placement optimization steps comprise:

(a) calculating propensities for relocating elements to an alternate regions;

(b) computing a first threshold; and

(c) repositioning any element having a maximum propensity greater than said first threshold to the region providing the maximum propensity for the element.

4. The system of claim 1, further comprising:

(a) distributing relevant parameters associated with elements occupying more than one region to all regions where elements overlap; and

(b) updating region occupancy after elements are repositioned.

5. The system of claim 1, wherein the capacity penalty influence parameter is the propensity for moving elements into different regions based on capacity of said regions.

6. A method for optimizing placement of a plurality of elements on a surface divided into regions, comprising the steps of:

(a) calculating propensities for relocating an element to plural alternate regions and repositioning the element to the region providing a maximum propensity for the element if the maximum propensity is greater than a predetermined threshold, based on an influence parameter;

(b) repeating step (a) for plural elements;

(c) altering said influence parameter; and

(d) repeating steps (a), (b) and (c) for a first predetermined number of times.

7. The method of claim 6 wherein said repetition outlined in step (b) occurs a second predetermined number of times.

8. The method of claim 7 wherein the second predetermined number of times varies for different iterations of step (a).

9. The method of claim 6, further comprising iterating all steps in combination with other region density levelizing procedures.

10. The method of claim 6, further comprising:

(a) distributing relevant parameters associated with elements occupying more than one region to all regions where elements overlap; and

(b) updating region occupancy after elements are repositioned.

11. The method of claim 6, wherein the influence parameter is the propensity for moving elements into different regions based on capacity of said regions.

12. A method for optimizing placement of cells on a surface of a semiconductor chip divided into regions, comprising the steps of:

(a) calculating affinities for relocating a cell to plural alternate regions and repositioning the cell to the region providing a maximum affinity for the cell if the maximum affinity is greater than a predetermined threshold, based on an influence parameter;

(b) repeating step (a) for plural cells;

(c) altering said influence parameter; and

(d) repeating steps (a), (b) and (c) for a predetermined number of times.

13. The method of claim 12 wherein said repetition outlined in step (b) occurs a second predetermined number of times.

14. The method of claim 13 wherein the second predetermined number of times varies for different iterations of step (a).

15. The method of claim 12, further comprising iterating all steps in combination with other region density levelizing procedures.

16. The method of claim 12, further comprising:

a. distributing relevant parameters associated with cells occupying more than one region to all regions which cells overlap; and

b. updating region occupancy after cells are repositioned.

17. The method of claim 12, wherein the influence parameter is the propensity for moving cells into different regions based on capacity of said regions.

18. Computer-executable process steps stored on a computer readable medium, said process steps for optimizing placement of a plurality of elements on a surface divided into regions, said process steps comprising steps to:

(a) calculate propensities for relocating an element to plural alternate regions and reposition the element to the region providing a maximum propensity for the element if the maximum propensity is greater than a predetermined threshold, based on an influence parameter;

(b) repeat step (a) for plural elements;

(c) alter said influence parameter; and

(d) repeat steps (a), (b) and (c) for a first predetermined number of times.

19. An apparatus for optimizing placement of a plurality of elements on a surface divided into regions, said apparatus comprising:

a processor for executing stored program instruction steps; and

a memory connected to the processor for storing the program instruction steps,

wherein the program instruction steps include steps to;

(a) calculate propensities for relocating an element to plural alternate regions and reposition the element to the region providing a maximum propensity for the element if the maximum propensity is greater than a predetermined threshold, based on an influence parameter;

(b) repeat step (a) for plural elements;

(c) alter said influence parameter; and

(d) repeat steps (a), (b) and (c) for a first predetermined number of times.