ADVANCED MODULAR CELL PLACEMENT SYSTEM

• US 20010003843A1
• Filed: 11/22/1999
• Published: 06/14/2001
• Est. Priority Date: 06/28/1996
• Status: Active Grant

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: Alexander E. Andreev, Edwin Jones, Ivan Pavisic, James S. Koford, Ranko Scepanovic
• Inventors: PAVISIC, IVAN, JONES, EDWIN, KOFORD, JAMES S, ANDREEV, ALEXANDER E, SCEPANOVIC, RANKO
• Granted Patent: US 6,292,929 B2
• Time in Patent Office: Days
• US Class Current: 716/7
• 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 for locating a plurality of elements on a surface, said method comprising the steps of:

assigning the elements to portions of the surface;

preplacing the elements onto the surface;

repositioning the elements depending on relative affinities of the elements to each other; and

connecting the elements on the surface.

2. A method according to

claim 1

, wherein the elements are cells of an integrated circuit chip (IC), and the surface is surface of said IC.

3. A method according to

claim 1

, further comprising the step of planning the element layout on the surface prior to preplacing the elements onto the surface.

4. A method according to

claim 3

, wherein said step of planning the element layout comprises steps:

partitioning the surface into a grid comprising a plurality of regions;

defining pieces, each piece comprising at least one of said regions, and each piece having a capacity;

allocating said capacity of each of said pieces to predefined groups of the elements; and

reallocating said capacity of said pieces to said groups of the elements.

5. A method according to

claim 1

, wherein said step of repositioning the elements is performed using a plurality of processors.

6. A method according to

claim 5

, wherein plurality of processors operate simultaneously.

7. A method according to

claim 5

, wherein said step of repositioning the elements comprises the steps:

dividing the surface into a plurality of regions;

assigning non-adjacent regions to said processors, each processor determining affinities of the elements of its assigned region; and

repositioning the elements.

8. A method according to

claim 5

, wherein said step of repositioning the elements comprises the steps:

assigning the elements to said processors, each processor determining affinities of its assigned elements; and

repositioning the elements.

9. A method according to

claim 1

, wherein said step of connecting the elements comprises the steps:

partitioning the elements into a plurality of sets, each set having at least a predetermined number of elements;

constructing a minimal spanning tree having vertices and edges, said vertices of said spanning tree representing the elements and said sets; and

connecting the elements per said edges of said minimal spanning tree.

10. A computer-implemented method for locating a plurality of elements on a surface, said method comprising the steps of:

forming a neighborhood defined as a set of the elements;

ordering the elements within each said neighborhood according to their relative distance from said target element;

preplacing the elements within a two-dimensional abstraction of the surface;

iteratively subdividing the surface into a plurality of regions;

assigning the elements to said plurality of regions;

calculating affinities of the elements using a plurality of processors;

moving the elements based on affinities of the elements;

levelizing element density over the surface based on relationships between the elements;

relocating any overlapping elements; and

performing a final cell adjustment for element positions.

11. A computer-implemented method according to

claim 10

, further comprising the steps:

dividing the surface into a plurality of regions; and

assigning non-adjacent regions to each of said plurality of processors to place the elements onto said regions simultaneously.

12. A computer-implemented method according to

claim 10

, further comprising the steps:

assigning the elements to each of said plurality processors; and

determining the element placements by simultaneously operating said plurality of processors.

13. A computer-implemented method according to

claim 10

, wherein the elements are grouped into functions and the surface can be partitioned into portions, each of said portions having a capacity, and further comprising the step of assigning said groups of the elements to said portions of the surface to meet a predetermined utilization requirement of said capacity of each of said portions of the surface.

14. An apparatus for placing a plurality of elements on a surface, said apparatus comprising:

a processor;

memory connected to said processor;

said memory having instructions for said processor to assign the elements to portions of the surface;

to preplace the elements onto the surface;

to reposition the elements depending on relative affinities of the elements to each other; and

to connect the elements on the surface.

15. An apparatus according to

claim 8

further comprising a plurality of processors.

16. An apparatus according to

claim 9

wherein said plurality processors operate simultaneously.

17. An apparatus according to

claim 8

further comprising a harddrive and a monitor.

18. An apparatus according to

claim 8

wherein said apparatus is a general purpose computer.

19. An apparatus according to

claim 8

wherein said elements are cells of an integrated circuit chip (IC), and said surface is the IC.

20. A machine-readable storage medium containing instructions for a processor, said instructions comprising the steps for locating a plurality of elements on a surface and comprising the steps of:

assigning the elements to portions of the surface;

preplacing the elements onto the surface;

repositioning the elements depending on relative affinities of the elements to each other; and

connecting the elements on the surface.

21. A storage medium according to

claim 5

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