×

Cell placement alteration apparatus for integrated circuit chip physical design automation system

  • US 5,793,644 A
  • Filed: 09/17/1996
  • Issued: 08/11/1998
  • Est. Priority Date: 04/19/1994
  • Status: Expired due to Term
First Claim
Patent Images

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 all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×