Cell placement alteration apparatus for integrated circuit chip physical design automation system
US5557533A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 19, 1994 |
| Grant date | Sep 17, 1996 |
| Priority date | — |
| Expiry date | Apr 19, 2014 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/392
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.