Cell placement alteration apparatus for integrated circuit chip physical design automation system
First Claim
1. A method for selecting cells for transposition such that a probability of each cell being selected is a predetermined function of a fitness associated with each cell respectively, comprising the steps of:
- sorting and ranking said cells in increasing order of fitness;
multiplying said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively, wherein said predetermined function of said fitness is such that said probability of said each cell being selected is substantially linearly proportional to said weighted fitness of said each cell respectively;
computing a weighted fitness summation for said each cell as being substantially equal to the sum of said weighted fitness of said each cell and said weighted fitnesses of said cells having lower fitnesses than said each cell respectively;
generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for a first cell placement; and
selecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number.
3 Assignments
0 Petitions
Accused Products
Abstract
A large number of possible placements of cells on an integrated circuit chip are generated and evaluated to determine the placement with the highest fitness. Cells for transposition or "swapping" within each placement using genetic algorithms are selected using greedy algorithms based on the fitness of each cell. The cell fitnesses are evaluated in terms of interconnect congestion, total net wire length or other criteria. Cells are selected for genetic crossover by sorting the cells in order of fitness and multiplying the cell fitnesses by weighting factors that increase non-linearly with rank. The cells are selected using linear random number generation such that cells with higher fitnesses have a higher probability of selection. Cells having lowest fitness are selected for mutation, and transposed to random locations, to adjacent locations, with cells having second worst fitness, to the center of mass of the respective interconnect nets, or with two or more cells in a cyclical manner.
-
Citations
32 Claims
-
1. A method for selecting cells for transposition such that a probability of each cell being selected is a predetermined function of a fitness associated with each cell respectively, comprising the steps of:
-
sorting and ranking said cells in increasing order of fitness; multiplying said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively, wherein said predetermined function of said fitness is such that said probability of said each cell being selected is substantially linearly proportional to said weighted fitness of said each cell respectively; computing a weighted fitness summation for said each cell as being substantially equal to the sum of said weighted fitness of said each cell and said weighted fitnesses of said cells having lower fitnesses than said each cell respectively; generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for a first cell placement; and selecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A selection processor for use with a cell placement alteration apparatus for an integrated circuit chip physical design automation system, comprising:
-
means for selecting cells such that a probability of each cell being selected is a predetermined function of a fitness of said each cell respectively, wherein the selection processor sorts and ranks said cells in increasing order of fitness and multiplies said fitnesses by weighting factors that increase nonlinearly with cell rank to produce weighted fitnesses respectively, and further wherein said predetermined function of said fitness is such that said probability of said each cell being selected is substantially linearly proportional to said weighted fitness of said each cell respectively; means for computing a weighted fitness summation for said each cell as being substantially equal to the sum of said weighted fitness of said each cell and said weighted fitnesses of said cells having lower fitnesses than said each cell respectively; a random number generator for generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for a first cell placement; and a selector for selecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
Specification