Advanced modular cell placement system with fast procedure for finding a levelizing cut point

• US 5,870,311 A
• Filed: 06/28/1996
• Issued: 02/09/1999
• 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): Siek, Vuthe
• Application Number:
  US08/671,699
• Time in Patent Office: 956 Days
• Field of Search: 364/488-491, 364/468.28
• US Class Current: 716/124
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for defining a cut point dividing a plurality of cells located on the surface of a semiconductor chip is disclosed herein. The surface has at least one region located thereon. The system comprises dividing each region into subregions, computing the capacity of each subregion, finding the maximum and minimum cell locations within each region, dividing the range spanning the maximum and minimum cell locations into a plurality of subintervals, calculating an index for each cell based on the subinterval containing the cell, accumulating cell heights for each subinterval, determining the values of cell heights for each region as the sum of cell heights for all prior regions, locating the minimum index such that the cell heights for each region are most closely proportional to the capacity of the associated subregion, and finding the cut line based on said minimum index and the maximum and minimum cell locations.

Claims

1. A method for determining a division between a plurality of elements within a region on a surface, said method comprising the steps of:

a. selecting a dividing line on said surface, wherein said dividing line establishes subregions having capacities;

b. locating the maximum and minimum points of elements within the region, said maximum and minimum points defining an interval;

c. dividing the interval into a plurality of equal subintervals;

d. initializing an array;

e. calculating indices of the subinterval where every element coordinate is located;

f. accumulating a first parameter associated with each element in each subinterval into the array location for the subinterval;

g. sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion; and

h. choosing the division based on said minimum index value.

2. The method of claim 1, further comprising the step of subdividing the subinterval containing said division into a second plurality of subintervals.

3. The method of claim 1 wherein said first parameter is the size of said element.

4. The method of claim 1, wherein said predetermined criterion comprises selecting a ratio of elements equal to said ratio between subregions induced by said dividing line.

5. The method of claim 1, wherein said predetermined criterion comprises locating a value such that the sum of all elements with coordinates below the value is not greater than a first subregion capacity over the region capacity and the sum of all elements with coordinates above the value is not greater than a second subregion capacity over the region capacity.

6. The method of claim 1, wherein said method is applied to determine a division between cells on the surface of a semiconductor chip.

7. A method for determining a division between a plurality of elements located within a region on a surface, said method comprising the steps of:

a. dividing the range of elements within the region into a series of subintervals;

b. accumulating a parameter associated with each element into an array identified with each subinterval; and

c. determining the minimum subinterval satisfying a predetermined criterion, wherein said division is established via the minimum subinterval,

said minimum subinterval determination step comprises

sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion; and

choosing the division based on said minimum index value.

8. The method of claim 7, further comprising the steps of:

a. selecting a dividing line on said surface, wherein said dividing line establishes subregions having capacities; and

b. locating the maximum and minimum points of elements within the region, said maximum and minimum points defining an interval.

9. The method of claim 7, wherein said parameter accumulation step comprises:

a. calculating indices of the subinterval where every element coordinate is located; and

b. accumulating be parameter associated with each element in each subinterval into the array location for the subinterval.

10. The method of claim 7, wherein said minimum subinterval determination step comprises sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion;

and choosing the division based on said minimum index value.

11. The method of claim 7, further comprising the step of subdividing the subinterval containing said division into a second plurality of subintervals.

12. The method of claim 9 wherein said parameter is the size of said element.

13. The method of claim 10, wherein said predetermined criterion comprises selecting a ratio of elements equal to said ratio between subregions induced by said dividing line.

14. The method of claim 10, wherein said predetermined criterion comprises locating a value such that the sum of all elements with coordinates below the value is not greater than a first subregion capacity over the region capacity and the sum of all elements with coordinates above the value is not greater than a second subregion capacity over the region capacity.

15. The method of claim 7, wherein said method is applied to determine a division between cells on the surface of a semiconductor chip.

16. A method for defining a cut point dividing a plurality of cells located on the surface of a semiconductor chip, said surface having at least one region located thereon, said system comprising:

a. dividing each region into subregions;

b. computing the capacity of each subregion;

c. finding the maximum and minimum cell locations within each region;

d. dividing the range spanning the maximum and minimum cell locations into a plurality of subintervals;

e. calculating an index for each cell based on the subinterval containing the cell;

f. accumulating cell heights for each subinterval;

g. determining the values of cell heights for each region as the sum of cell heights for all prior regions;

h. locating the minimum index such that the cell heights for each region are most closely proportional to the capacity of the associated subregion; and

i. finding the cut line based on said minimum index and the maximum and minimum cell locations.

17. The method of claim 16, further comprising the step of subdividing the subinterval containing said cut line into a plurality of subintervals smaller than said subregions, and then repeating the method steps of claim 16 to determine a second cut line.

18. A method for locating a division of elements on a surface comprising at least one region, said method comprising the steps of:

a. dividing the area spanning the maximum and minimum element locations into a plurality of subintervals;

b. accumulating a parameter associated with each element into arrays indexed according to said subinterval; and

c. locating the minimum subinterval satisfying a predetermined criterion, wherein said minimum subinterval is utilized to define said division,

said minimum subinterval determination step comprises

sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion; and

choosing the division based on said minimum index value.

19. The method of claim 18, further comprising the steps of:

a. selecting a dividing line on said surface, wherein said dividing line establishes subregions having capacities; and

b. locating the maximum and minimum points of elements within the region, said maximum and minimum points defining an interval.

20. The method of claim 18, wherein said parameter accumulation step comprises:

a. calculating indices of the subinterval where every element coordinate is located; and

b. accumulating the parameter associated with each element in each subinterval into the array location for the subinterval.

21. The method of claim 18, wherein said minimum subinterval locating step comprises sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion;

and choosing the division based on said minimum index value.

22. The method of claim 18, further comprising the step of subdividing the subinterval containing said division into a second plurality of subintervals.

23. The method of claim 20 wherein said parameter is the size of said element.

24. The method of claim 21, wherein said predetermined criterion comprises selecting a ratio of elements equal to said ratio between subregions induced by said dividing line.

25. The method of claim 21, wherein said predetermined criterion comprises locating a value such that the sum of all elements with coordinates below the value is not greater than a first subregion capacity over the region capacity and the sum of all elements with coordinates above the value is not greater than a second subregion capacity over the region capacity.

26. The method of claim 18, wherein said method is applied to determine a division between cells on the surface of a semiconductor chip.

27. A computer storage device having located thereon a computer program comprising the following steps:

a. dividing an area spanning the maximum and minimum element locations into a plurality of subintervals;

accumulating a parameter associated with each element into arrays indexed according to said subintervals; and

b. locating the minimum subinterval satisfying a predetermined criterion,

said minimum subinterval determination step comprises

sequentially summing array elements until a minimum index value is attained which satisfies a predetermined criterion; and

choosing the division based on said minimum index value.