Patent Document ID: 5557533
Application ID: 08229821
Patent Flag: 1

Claim One:
1. A cell placement alteration apparatus for an integrated circuit chip physical design automation system, comprising: a memory for storing a first cell placement as including cell locations on the chip, cells allocated to said cell locations and fitnesses of said cells respectively; a transposition processor for performing a predetermined cell transposition operation on said first cell placement to produce a second cell placement, and storing said second cell placement in the memory; and a selection processor for selecting cells for transposition by the transposition processor such that a probability of each cell being selected is a predetermined function of said fitness of said each cell respectively, in which: the selection processor sorts and ranks said cells in increasing order of fitness and multiplies said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively; 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; the selection processor computes 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; and the selection processor further comprises: a random number generator for generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for said 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.