Advanced modular cell placement system
First Claim
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 affinities of the elements; and
connecting the elements on the surface,wherein said step of repositioning the elements is performed using a plurality of processors and comprises;
(1) dividing the surface into a plurality of regions;
(2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and
(3) repositioning at least some of the elements to locations in other regions based on the affinities.
9 Assignments
0 Petitions
Accused Products
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.
179 Citations
23 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 affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises;
(1) dividing the surface into a plurality of regions;
(2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and
(3) repositioning at least some of the elements to locations in other regions based on the affinities. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. 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 a 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; assigning non-adjacent regions to a plurality of processors; calculating affinities of at least some of the elements to locations in other regions using the plurality of processors, each processor determining affinities of the elements in its assigned region; repositioning at least some of the elements to other regions 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. - View Dependent Claims (10, 11, 12)
-
-
13. An apparatus for placing a plurality of elements on a surface, said apparatus comprising:
-
a plurality of processors; memory connected to said processors; said memory having instructions for said processors to assign the elements to portions of the surface;
to preplace the elements onto the surface;
to reposition the elements depending on affinities of the elements; and
to connect the elements on the surface,wherein said instructions to reposition the elements comprise instructions to;
(1) divide the surface into a plurality of regions;
(2) assign non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and
(3) reposition at least some of the elements to locations in other regions based-on the affinities. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
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 affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises;
(1) dividing the surface into a plurality of regions;
(2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions and (3) repositioning at least some of the elements to locations in-other regions based on the affinities. - View Dependent Claims (21, 22, 23)
-
Specification