Advanced modular cell placement system with median control and increase in resolution

• US 6,030,110 A
• Filed: 06/28/1996
• Issued: 02/29/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): Voeltz, Emanuel Todd
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/671,651
• Time in Patent Office: 1,341 Days
• Field of Search: 364/490, 364/488, 364/489, 364/491, 364/578, 395/500
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for proportionally partitioning multiple groups of cells on the surface of a semiconductor chip into subregions is disclosed herein. The cell groups are separated by dividing lines, and the system comprising a calculator which determines an offset of the cut line from the dividing line; a shifter which moves the location of said groups of cells by the offset such that the cut line coincides with the dividing line; and an overflow evaluator and compensator which shifts any cells outside said region to an edge of said region.

Claims

1. A method for reallocating cells assigned to a region of the surface of an integrated circuit device, said method comprising the steps of:

a. dividing said region into a first subregion and a second subregion with a dividing line;

b. with respect to cells located within said region, determining a desired allocation of cells between said first subregion and said second subregion;

c. locating a cut line across said region such that said cut line cuts said region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion;

d. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line;

e. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and

f. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

2. The method of claim 1, wherein the allocation of the cells between said first part and said second part in step c matches said desired allocation of cells between said first subregion and said second subregion determined in step b.

3. The method of claim 1, wherein said region is rectangular and both the cut line and the dividing line are substantially parallel to each other and to two opposing sides of said rectangular region.

4. The method of claim 3, wherein the area of each subregion is half of the area of the region.

5. The method of claim 2, wherein said desired allocation of cells between said subregions is a function of the capacities of said subregions.

6. The method of claim 5, wherein (1) said first subregion has a first capacity and said second subregion has a second capacity, (2) each cell has an associated cell height, and (3) the desired allocation of cells between said subregions is such that the sum of the cell heights in the first subregion divided by the first capacity substantially equals the sum of the cell heights in the second region divided by the second capacity.

7. The method of claim 5, wherein (1) said first subregion has a first capacity and said second subregion has a second capacity, and (2) the desired allocation of cells between said subregions is such that the sum of the number of cells in the first subregion divided by the first capacity substantially equals the sum of the number of cells in the second region divided by the second capacity.

8. A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising:

a. assigning cells to a region of the surface of an integrated circuit device;

b. dividing said region into a first subregion and a second subregion with a dividing line;

c. with respect to cells located within said region, determining desired allocation of cells between said first subregion and said second subregion;

d. locating a cut line across said region such that said cut line cuts said region in a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion;

e. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line;

f. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and

g. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

9. A storage medium according to claim 8 wherein said storage medium is selected from a group consisting of floppy diskette, hard drive, and CD-ROM.

10. A method for optimizing the placement of cells on a portion of the surface of an integrated circuit device, said method comprising the steps of:

a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions;

b. assigning to each of the regions a plurality of cells;

c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and

d. for each region in said first row of regions, performing the following substeps;

i. with respect to cells located within the region, determining a desired allocation of cells between the region'"'"'s first subregion and second subregion;

ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region'"'"'s first subregion and second subregion;

iii. determining an offset representing the distance between a first point on the region'"'"'s cut line and a second point on said first region dividing line, said second point being within the region;

iv. shifting cells assigned to said region said offset; and

v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

11. The method of claim 10, wherein, for each region within said first row of regions, the allocation of the cells between said first part and said second part in substep ii matches the desired allocation of cells between the region'"'"'s first subregion and second subregion determined in substep i.

12. The method of claim 10, wherein, for each region within said first row of regions, the region'"'"'s cut line and said first region dividing line of said first row of regions are substantially parallel.

13. The method of claim 12, wherein, for each region within said first row of regions, the shortest distance between the first point on the region'"'"'s cut line and the region'"'"'s second point on the first region dividing line is a line substantially perpendicular to the first region dividing line.

14. The method of claim 10, wherein, for each region in said first row of regions, the area of each subregion is half of the area of the region.

15. The method of claim 11, wherein, for each region within said first row of regions, said desired allocation of cells between said subregions is a function of the capacities of said subregions.

16. The method of claim 15, wherein, for each region within said first row of regions, (1) said first subregion has a first capacity and said second subregion has a second capacity, (2) each cell has an associated cell height, and (3) the desired allocation of cells between said subregions is such that the sum of the cell heights in the first subregion divided by the first capacity is substantially equal to the sum of the cell heights in the second region divided by the second capacity.

17. The method of claim 15, wherein, for each region within said first row of regions, (1) said first subregion has a first capacity and said second subregion has a second capacity, and (2) the desired allocation of cells between said subregions is such that the sum of the number of cells in the first subregion divided by the first capacity substantially equals the sum of the number of cells in the second region divided by the second capacity.

18. The method of claim 10, wherein steps (c) and (d) are repeated for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

19. The method of claim 18, wherein the following additional steps are taken:

e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and

f. for each subregion in said first row of subregions, performing the following substeps;

i. locating a cut line across the subregion;

ii. determining an offset representing the distance between a first point on the subregion'"'"'s cut line and a second point on the first subregion dividing line, said second point being within the subregion;

iii. shifting cells assigned to said subregion said distance; and

iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.

20. The method of claim 19, wherein steps (e) and (f) are repeated for the rows of subregions which are parallel to said first row of subregions with each parallel row of subregions having its own dividing line.

21. The method of claim 10, wherein the number of regions in said grid is 4.

22. The method of claim 10, wherein the number of regions in said grid is 8.

23. The method of claim 10, wherein the number of regions in said grid is 16.

24. A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising:

a. dividing a portion of the surface of a integrated circuit device into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions;

b. assigning to each of the regions a plurality of cells;

c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and

d. for each region in said first row of regions, performing the following substeps;

i. with respect to cells located within the region, determining a desired allocation of cells between the region'"'"'s first subregion and second subregion;

ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region'"'"'s first subregion and second subregion;

iii. determining an offset representing the distance between a first point on the region'"'"'s cut line and a second point on said first region dividing line, said second point being within the region;

iv. shifting cells assigned to said region said offset; and

v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

25. The machine-readable storage medium of claim 24, wherein the instructions thereon further comprise repeating steps (c) and (d) for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

26. The machine-readable storage medium of claim 25, wherein the instructions contained therein further comprise taking the following additional steps:

e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and

f. for each subregion in said first row of subregions, performing the following substeps;

i. locating a cut line across the subregion;

ii. determining an offset representing the distance between a first point on the subregion'"'"'s cut line and a second point on the first subregion dividing line, said second point being within the subregion;

iii. shifting cells assigned to said subregion said distance; and

iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.

27. A storage medium according to claim 24 wherein said storage medium is selected from a group consisting of floppy diskette, hard drive, and CD-ROM.

28. An integrated circuit device having cells placed on a portion of its surface, wherein said cells are allocated on said portion with a method comprising the following steps:

a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions;

b. assigning to each of the regions a plurality of cells;

c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and

d. for each region in said first row of regions, performing the following substeps;

i. with respect to cells located within the region, determining a desired allocation of cells between the region'"'"'s first subregion and second subregion;

ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region'"'"'s first subregion and second subregion;

iii. determining an offset representing the distance between a first point on the region'"'"'s cut line and a second point on said first region dividing line, said second point being within the region;

iv. shifting cells assigned to said region said offset; and

v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

29. The integrated circuit device of claim 28 wherein said method further comprises repeating steps (c) and (d) for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

30. The integrated circuit device of claim 29 wherein said method further comprises the following additional steps:

e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and

f. for each subregion in said first row of subregions, performing the following substeps;

i. locating a cut line across the subregion;

ii. determining an offset representing the distance between a first point on the subregion'"'"'s cut line and a second point on the first subregion dividing line, said second point being within the subregion;

iii. shifting cells assigned to said subregion said distance; and

iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.