Optimization processing for integrated circuit physical design automation system using optimally switched fitness improvement algorithms
First Claim
1. A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip, comprising:
- a processor for altering a population of cell placements using a predetermined first fitness improvement algorithm or a predetermined second fitness improvement algorithm; and
a controller for controlling the processor to select and use said first fitness improvement algorithm or said second fitness improvement algorithm in accordance with a predetermined optimization criterion.
10 Assignments
0 Petitions
Accused Products
Abstract
A physical design automation system produces an optimal placement of microelectronic components or cells on an integrate circuit chip. An initial population of possible cell placements is generated, and repeatedly altered using simulated on or other fitness improvement algorithm to progressively increase the fitnesses (decrease the costs) of the placements. After each alteration step, the fitnesses of the placements are calculated, and less fit placements are discarded in favor of more fit placements. After a termination criterion is reached, the placement having the highest fitness is designated as the optimal placement. Two or more fitness improvement algorithms are available, and are optimally switched from one to the other in accordance with an optimization criterion to maximize convergence of the placements toward the optimal configuration.
125 Citations
33 Claims
-
1. A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip, comprising:
-
a processor for altering a population of cell placements using a predetermined first fitness improvement algorithm or a predetermined second fitness improvement algorithm; and
a controller for controlling the processor to select and use said first fitness improvement algorithm or said second fitness improvement algorithm in accordance with a predetermined optimization criterion. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
a fitness computer for computing fitnesses of said cell placements, in which;
said optimization criterion comprises a predetermined function of said fitnesses.
-
-
10. A system as in claim 9, in which the fitness computer computes said fitnesses as a predetermined function of cell interconnect congestion in said cell placements.
-
11. A system as in claim 9, in which the controller controls the processor to repeatedly alter said cell placements until a predetermined termination criterion is reached.
-
12. A system as in claim 11, in which the controller selects a cell placement from said population that has a highest fitness value as said highest fitness cell placement after said termination criterion is reached.
-
13. A system as in claim 11, in which the controller controls the processor to initially select and use said first fitness improvement algorithm, and to select and use said second fitness improvement algorithm after the processor has altered said cell placements a predetermined number of times.
-
14. A system as in claim 11, in which the controller controls the processor to initially select and use said first fitness improvement algorithm, and to select and use said second fitness improvement algorithm after a fitness value of a placement having a highest fitness has reached a predetermined value.
-
15. A system as in claim 11, in which the controller controls the processor to initially select and use said first fitness improvement algorithm, and to select and use said second fitness improvement algorithm after the processor has altered said cell placements a predetermined number of times without producing a change in a fitness value of a placement having a highest fitness value.
-
16. A system as in claim 11, in which the controller controls the processor to initially select and use said first fitness improvement algorithm, and to select and use said second fitness improvement algorithm after the processor has altered said cell placements and a fitness value of a placement having a highest fitness value has changed by less than a predetermined value.
-
17. A method of increasing a fitness of a permutation of a predetermined number of entities, comprising the steps of:
-
(a) altering said permutation using a predetermined first fitness improvement algorithm or a predetermined second fitness improvement algorithm; and
(b) selecting said first fitness improvement algorithm or said second fitness improvement algorithm in accordance with a predetermined optimization criterion.
-
-
18. A method of increasing a fitness of a cell placement for an integrated circuit chip, comprising the steps of:
-
(a) altering a population of cell placements using a predetermined first fitness improvement algorithm or a predetermined second fitness improvement algorithm; and
(b) controlling step (a) to select and use said first fitness improvement algorithm or said second fitness improvement algorithm in accordance with a predetermined optimization criterion. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
(c) computing fitnesses of said cell placements;
in whichstep (b) comprises computing said optimization criterion as including a predetermined function of said fitnesses.
-
-
27. A method as in claim 26, in which step (c) comprises computing said fitnesses as a predetermined function of cell interconnect congestion in said cell placements.
-
28. A method as in claim 26, in which step (b) further comprises controlling step (a) to repeatedly alter said cell placements until a predetermined termination criterion is reached.
-
29. A method as in claim 28, further comprising the step of:
(d) selecting a cell placement from said population that has a highest fitness value as said highest fitness cell placement after said termination criterion is reached.
-
30. A method as in claim 28, in which step (b) comprises controlling step (a) to initially select and use said first fitness improvement algorithm, and to subsequently select and use said second fitness improvement algorithm after said cell placements have been altered a predetermined number of times.
-
31. A method as in claim 28, in which step (b) comprises controlling step (a) to initially select and use said first fitness improvement algorithm, and to subsequently select and use said second fitness improvement algorithm after a fitness value of a placement having a highest fitness has reached a predetermined value.
-
32. A method as in claim 28, in which step (b) comprises controlling step (a) to initially select and use said first fitness improvement algorithm, and to subsequently select and use said second fitness improvement algorithm after said cell placements have been altered a predetermined number of times without producing a change in a fitness value of a placement having a highest fitness value.
-
33. A method as in claim 28, in which step (b) comprises controlling step (a) to initially select and use said first fitness improvement algorithm, and to subsequently select and use said second fitness improvement algorithm after said cell placements have been altered and a fitness value of a placement having a highest fitness value has changed by less than a predetermined value.
Specification