US6292929B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Advanced modular cell placement system
Assignee: Bell Semiconductor LLC
•
Filing: 1999-11-22
•
Granted: 2001-09-18
•
Expires: 2019-11-22
Abstract
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.
Inventors
- 👤 Ranko Scepanovic
- 👤 Ivan Pavisic
- 👤 James S. Koford
- 👤 Alexander E. Andreev
- 👤 Edwin Jones
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:11
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
54 words
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.
Claim 2
Independent Claim
54 words
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.
Claim 3
Dependent Claim
23 words
The method as defined in claim 1 wherein steps b and c are iterated until all of said plurality of regions are processed.
Claim 4
Dependent Claim
39 words
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.
Claim 5
Dependent Claim
30 words
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.
Claim 6
Dependent Claim
35 words
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.
Claim 7
Dependent Claim
24 words
The method as defined in claim 1 wherein the elements are cells of an integrated circuit chip (IC) and the surface is the IC.
Claim 8
Independent Claim
203 words
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.
Claim 9
Independent Claim
203 words
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.
Claim 10
Dependent Claim
33 words
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.
Claim 11
Dependent Claim
34 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
25 words
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.
Claim 14
Dependent Claim
46 words
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.
Claim 15
Dependent Claim
30 words
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.
Claim 16
Dependent Claim
21 words
The method as defined by claim 13 wherein when iterating steps c through g, each new non-adjacent set includes unprocessed regions.
Claim 17
Dependent Claim
209 words
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.
Claim 18
Dependent Claim
209 words
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.
Claim 19
Dependent Claim
34 words
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.
Claim 20
Independent Claim
63 words
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.
Claim 21
Independent Claim
63 words
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.
Claim 22
Dependent Claim
20 words
The apparatus of claim 17 wherein said plurality of processors operate simultaneously to place the cells on the circuit chip.
Claim 23
Dependent Claim
26 words
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.
Claim 24
Dependent Claim
18 words
The apparatus of claim 17 further comprising an input device and an output device connected to said processors.
Claim 25
Dependent Claim
20 words
The apparatus of claim 17 wherein the memory further comprises instructions for the processors to determine fitness of cell placement.
Claim 26
Dependent Claim
72 words
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.
Claim 27
Dependent Claim
72 words
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.
References Cited (Backward Citations)
US5963746A
Cited
US5638292A
Cited
US5568322A
Cited
US5615128A
Cited
US5491641A
Cited
US5742510A
Cited
US5636125A
Cited
US5557533A
Cited
US5495419A
Cited
US5682322A
Cited
US5745363A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
Cited
US5661663A
Cited
US5699265A
Cited
US5712793A
Cited
US6026223A
Cited
US6067409A
Cited
US5859782A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-09-17 | 2005-03-19 | 2005-09-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-17 | 2009-03-19 | 2009-09-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-17 | 2013-03-19 | 2013-09-18 | $7700.00 | Window Closed / Lapsed |