초록 ▼

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

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.

대표청구항 ▼

[ We 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

[ We 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; andselecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number.