US6155725A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cell placement representation and transposition for integrated circuit physical design automation system
Assignee: Bell Semiconductor LLC
•
Filing: 1994-04-19
•
Granted: 2000-12-05
•
Expires: 2014-04-19
Abstract
Abstract A large number of possible cell placements for an integrated circuit chip are evaluated to determine which has the highest fitness in accordance with a predetermined criteria such as interconnect congestion. Each cell placement, which constitutes an individual permutation of cells from a population of possible permutations, is represented as an initial cell placement in combination with a list of individual cell transpositions or swaps by which the cell placement can be derived from the initial cell placement. A cell placement can be genetically mutated and/or inverted by adding swaps to the list for its cell placement which designates cells to be transposed. Genetic crossover can be performed by transposing swaps between the lists for two cell placements. This cell representation and transposition method enables any type of cell transposition to be performed without loss or duplication of cells or generation of illegal placements.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S Koford
- 👤 Edwin R. Jones
- 👤 Douglas B. Boyle
- 👤 Michael D. Rostoker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 04:32
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
111 words
A physical design automation system for determining a highest fitness cell placement for an integrated circuit chip, comprising: a memory for storing a first cell placement as including an initial cell placement and a first list of cell transpositions by which said first cell placement can be derived from said initial cell placement, and for storing a second cell placement as including said initial cell placement and a second list of cell transpositions by which said second cell placement can be derived from said initial cell placement; and a fitness processor for determining which of said first and second cell placements has highest fitness in accordance with a predetermined fitness algorithm.
Claim 2
Dependent Claim
111 words
A physical design automation system for determining a highest fitness cell placement for an integrated circuit chip, comprising: a memory for storing a first cell placement as including an initial cell placement and a first list of cell transpositions by which said first cell placement can be derived from said initial cell placement, and for storing a second cell placement as including said initial cell placement and a second list of cell transpositions by which said second cell placement can be derived from said initial cell placement; and a fitness processor for determining which of said first and second cell placements has highest fitness in accordance with a predetermined fitness algorithm.
Claim 3
Dependent Claim
35 words
An automation system as in claim 1, further comprising an alteration processor for producing said second list of cell transpositions by altering said first list of cell transpositions in accordance with a predetermined alteration algorithm.
Claim 4
Dependent Claim
15 words
An automation system as in claim 2, in which said alteration algorithm comprises genetic mutation.
Claim 5
Dependent Claim
15 words
An automation system as in claim 2, in which said alteration algorithm comprises simulated annealing.
Claim 6
Dependent Claim
15 words
An automation system as in claim 2, in which said alteration algorithm comprises genetic inversion.
Claim 7
Dependent Claim
15 words
An automation system as in claim 2, in which said alteration algorithm comprises genetic crossover.
Claim 8
Dependent Claim
59 words
An automation system as in claim 2, in which: the memory stores a plurality of selected contiguous cells as a block; and the alteration processor comprises means for altering said first list of cell transpositions such that said block is moved from a first position in said first cell placement to a second position in said second cell placement.
Claim 9
Dependent Claim
50 words
An automation system as in claim 2, in which the alteration processor comprises means for altering said first list of cell transpositions in accordance with an operator that designates a cell transposition operation and an operand that designates cells to be transposed in accordance with said designated cell transposition operation.
Claim 10
Dependent Claim
32 words
An automation system as in claim 8, in which said cell transposition operations comprise at least one of single cell transposition, cell block transposition, cell block rotation, row transposition and column transposition.
Claim 11
Dependent Claim
28 words
An automation system as in claim 8, in which the memory further stores a cell placement transposition history including said operator and said operand for each cell transposition.
Claim 12
Dependent Claim
85 words
An automation system as in claim 2, in which: the memory further stores a table including cell locations on the integrated circuit chip and identifiers of cells that correspond to said cell locations respectively in said first cell placement; and the alteration processor comprises means for designating first and second cells to be transposed by adding a transposition to said first list of cell transpositions including first and second cell locations that correspond to identifiers of said first and second cells respectively in said table.
Claim 13
Dependent Claim
81 words
An automation system as in claim 2, in which: the memory further stores a table including cell locations on the integrated circuit chip and identifiers of cells that correspond to said cell locations respectively in said first cell placement; and the alteration processor comprises means for designating first and second cells to be transposed by adding a transposition to said first list of cell transpositions including first and second identifiers corresponding to said first and second cells respectively in said table.
Claim 14
Dependent Claim
87 words
An automation system as in claim 2, in which: the memory further stores a table including cell locations on the integrated circuit chip and identifiers of cells that correspond to said cell locations respectively in said first cell placement; and the alteration processor comprises means for designating first and second cells to be transposed by adding a transposition to said first list of cell transpositions including a cell location that corresponds to said first cell and an identifier that corresponds to said second cell in said table.
Claim 15
Dependent Claim
96 words
An automation system as in claim 1, further comprising a genetic crossover processor for producing third and fourth lists of cell transpositions by transposing portions of said first and second lists of cell transpositions respectively, producing a third cell placement as including said initial cell placement and said third list of cell transpositions and producing a fourth cell placement as including said initial cell placement and said fourth list of cell transpositions; in which the fitness processor further determines which of said third and fourth cell placements has highest fitness in accordance with said fitness algorithm.
Claim 16
Dependent Claim
17 words
An automation system as in claim 1, in which said fitness algorithm comprises estimation of interconnect congestion.
Claim 17
Dependent Claim
100 words
An automation system for determining a highest fitness permutation of a predetermined number of entities, comprising: a memory for storing a first permutation as including an initial permutation and a first list of entity transpositions by which said first permutation can be derived from said initial permutation, and for storing a second permutation as including said initial permutation and a second list of entity transpositions by which said second permutation can be derived from said initial permutation; and a fitness processor for determining which of said first and second permutations has highest fitness in accordance with a predetermined fitness algorithm.
Claim 18
Dependent Claim
100 words
An automation system for determining a highest fitness permutation of a predetermined number of entities, comprising: a memory for storing a first permutation as including an initial permutation and a first list of entity transpositions by which said first permutation can be derived from said initial permutation, and for storing a second permutation as including said initial permutation and a second list of entity transpositions by which said second permutation can be derived from said initial permutation; and a fitness processor for determining which of said first and second permutations has highest fitness in accordance with a predetermined fitness algorithm.
Claim 19
Dependent Claim
35 words
An automation system as in claim 16, further comprising an alteration processor for producing said second list of entity transpositions by altering said first list of entity transpositions in accordance with a predetermined alteration algorithm.
Claim 20
Dependent Claim
15 words
An automation system as in claim 17, in which said alteration algorithm comprises genetic mutation.
Claim 21
Dependent Claim
15 words
An automation system as in claim 17, in which said alteration algorithm comprises genetic inversion.
Claim 22
Dependent Claim
15 words
An automation system as in claim 17, in which said alteration algorithm comprises genetic crossover.
Claim 23
Dependent Claim
91 words
An automation system as in claim 16, further comprising a genetic crossover processor for producing third and fourth lists of entity transpositions by transposing portions of said first and second lists of entity transpositions respectively, producing a third permutation as including said initial permutation and said third list of entity transpositions and producing a fourth permutation as including said initial permutation and said fourth list of entity transpositions; in which the fitness processor further determines which of said third and fourth permutations has highest fitness in accordance with said fitness algorithm.
Claim 24
Independent Claim
38 words
A method of representing a permutation of a predetermined number of entities, comprising: providing an initial permutation of said entities; and providing a list of entity transpositions by which said permutation can be derived from said initial permutation.
Claim 25
Independent Claim
38 words
A method of representing a permutation of a predetermined number of entities, comprising: providing an initial permutation of said entities; and providing a list of entity transpositions by which said permutation can be derived from said initial permutation.
Claim 26
Independent Claim
53 words
A method of storing a representation of a permutation of a predetermined number of entities in an electronic memory; comprising: storing an initial permutation of said entities in said electronic memory; and storing a list of entity transpositions by which said permutation can be derived from said initial permutation in said electronic memory.
Claim 27
Independent Claim
53 words
A method of storing a representation of a permutation of a predetermined number of entities in an electronic memory; comprising: storing an initial permutation of said entities in said electronic memory; and storing a list of entity transpositions by which said permutation can be derived from said initial permutation in said electronic memory.
Claim 28
Dependent Claim
45 words
A physical representation of a permutation of a predetermined number of entities, comprising: an initial permutation of said entities stored in electronic memory; and a list of entity transpositions by which said permutation can be derived from said initial permutation stored in said electronic memory.
Claim 29
Dependent Claim
45 words
A physical representation of a permutation of a predetermined number of entities, comprising: an initial permutation of said entities stored in electronic memory; and a list of entity transpositions by which said permutation can be derived from said initial permutation stored in said electronic memory.
References Cited (Backward Citations)
US4306286A
Cited
US4484292A
Cited
US4495559A
Cited
US4656580A
Cited
US4612618A
Cited
US4621339A
Cited
US4615011A
Cited
US4850027A
Cited
US5157778A
Cited
US5222029A
Cited
US4908772A
Cited
US4872125A
Cited
US5051895A
Cited
US5255345A
Cited
US5159682A
Cited
US5267176A
Cited
US5140526A
Cited
US5144563A
Cited
US5140530A
Cited
US5200908A
Cited
US5251147A
Cited
US5187668A
Cited
US5249259A
Cited
US5222031A
Cited
US5136686A
Cited
US5208759A
Cited
US5202840A
Cited
US5245550A
Cited
US5349536A
Cited
US5224056A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-05 | 2004-06-05 | 2004-12-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-05 | 2008-06-05 | 2008-12-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-05 | 2012-06-05 | 2012-12-05 | $7700.00 | Window Closed / Lapsed |