Advanced modular cell placement system

• US 6,292,929 B2
• Filed: 11/22/1999
• Issued: 09/18/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: Jones, Edwin, Scepanovic, Ranko, Andreev, Alexander E., Koford, James S., Pavisic, Ivan
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US09/444,975
• Publication Number:
  US 20010003843A1
• Time in Patent Office: 666 Days
• Field of Search: 716/7, 716/8, 716/14
• US Class Current: 716/118
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for determining an affinity associated with relocating a cell located on a surface of a semiconductor chip to a different location on the surface is disclosed herein. Each cell may be part of a cell net containing multiple cells. The system initially defines a bounding box containing all cells in the net which contains the cell. The system then establishes a penalty vector based on the bounding box and borders of a region containing the cell, computes a normalized sum of penalties for all nets having the cell as a member, and calculates the affinity based on the normalized sum of penalties. Also included in the disclosed system are methods and apparatus for capacity and utilization planning of the use of the floor, or the surface area, and the methods and apparatus for parallelizing the process of affinity based placements using multiple processors. Finally, method and apparatus for connecting the cells based on a Steiner Tree method is disclosed.

Claims

1. A method of placing elements on a surface, said method comprising:

a. dividing the surface into a plurality of regions;

b. assigning a region to each of a plurality of processors, wherein the assigned regions are non-adjacent; and

c. placing elements within the regions, wherein each processor places the elements within its assigned region.

2. The method as defined in claim 1 wherein steps b and c are iterated until all of said plurality of regions are processed.

3. The method as defined in claim 2, further comprising:

d. maintaining a list of elements located within each of said plurality of regions; and

e. updating said list of elements after each iteration of steps b and c.

4. The method as defined in claim 1 further comprising:

d. determining fitness of said placement; and

e. repeating steps b through d until a predetermined level of fitness is achieved.

5. The method as defined in claim 1 wherein said processing is performed using a simulated annealing technique wherein a first element of a first region is swapped with a second element of a second region.

6. The method as defined in claim 1 wherein the elements are cells of an integrated circuit chip (IC) and the surface is the IC.

7. A method of using multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said method comprising:

a. dividing the core area into a plurality of regions, each of said regions containing a plurality of cells, and each of said regions being adjacent to at least one surrounding region;

b. creating, for each of said regions, a list of cells belonging to said region;

c. creating a non-adjacent set of regions from said plurality of regions, wherein no two regions in said non-adjacent set are adjacent to each other;

d. assigning said regions belonging to said non-adjacent set to multiple processors, one region per processor;

e. processing said cells of each of said regions belonging to said non-adjacent set using the multiple processors assigned to said regions; and

f. updating said lists of cells for each of said regions,

wherein a property of non-adjacency is met when either of the following conditions is satisfied;

(1) when a first region is KX regions away from a second region, said KX having a value greater than one, or (2) when the first region is KY regions away from the second region, said KY having a value greater than one.

8. The method as defined by claim 7 wherein when each processor completes processing its assigned region, said processor is assigned a new region that is not adjacent to any other region being processed.

9. The method as defined by claim 8 wherein said property of non-adjacency is met when a first region is KX regions away from a second region, said KX having a value greater than one.

10. The method as defined by claim 8 wherein said property of non-adjacency is met when a first region is KY regions away from a second region, said KY having a value greater than one.

11. The method as defined by claim 8 wherein the regions are assigned in a predetermined order regardless of the processor to which they are assigned.

12. The method as defined by claim 11 wherein the regions are arranged in an array and wherein the regions are assigned by advancing a first fixed number of rows and a second fixed number of columns in the array to identify each successive region to assign.

13. The method as defined by claim 7 further comprising:

g. determining fitness of the core; and

h. iterating steps c through g until a predetermined level of fitness is achieved.

14. The method as defined by claim 13 wherein when iterating steps c through g, each new non-adjacent set includes unprocessed regions.

15. A computer storage medium containing instructions to use multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said instructions comprising steps to:

a. divide the core area into a plurality of regions, each of said regions containing a plurality of cells, and each of said regions being adjacent to at least one surrounding region;

b. create, for each of said regions, a list of cells belonging to said region;

c. create a non-adjacent set of regions from said plurality of regions, wherein no two regions in said non-adjacent set are adjacent to each other;

d. assign said regions belonging to said non-adjacent set to multiple processors, one region per processor;

e. process said cells of each of said regions belonging to said non-adjacent set using the multiple processors assigned to said regions; and

f. update said lists of cells for each of said regions,

wherein a property of non-adjacency is met when either of the following conditions is satisfied;

(1) when a first region is KX regions away from a second region, said KX having a value greater than one, or (2) when the first region is KY regions away from the second region, said KY having a value greater than one.

16. The storage medium according to claim 15 wherein said storage medium is selected from a group consisting of magnetic device, optical device, magneto-optical device, floppy diskette, CD-ROM, magnetic tape, computer harddrive, and memory card.

17. An apparatus for placing cells on an integrated circuit chip, said apparatus comprising:

a plurality of processors; and

memory connected to said processors,

said memory having instructions for said processors to divide the area of said circuit chip into a plurality of regions and to successively assign non-adjacent regions to said processors for said processors to place the cells onto said circuit chip.

18. The apparatus of claim 17 wherein said plurality of processors operate simultaneously to place the cells on the circuit chip.

19. The apparatus of claim 17 wherein the memory further comprises instructions for the processors to maintain a list of cells located within each of said regions.

20. The apparatus of claim 17 further comprising an input device and an output device connected to said processors.

21. The apparatus of claim 17 wherein the memory further comprises instructions for the processors to determine fitness of cell placement.

22. A computer storage medium containing instructions to use multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said instructions comprising steps to:

a. divide the surface into a plurality of regions;

b. assign a region to each of a plurality of processors, wherein the assigned regions are non-adjacent; and

c. place elements within the regions, wherein each processor places the elements within its assigned region.