초록 ▼

A large number of possible cell placements for an integrated circuit chip are evaluated to determine which has the highest fitness in accordance with a predetermined criteria such as interconnect congestion. Each cell placement, which constitutes an individual permutation of cells from a population

A large number of possible cell placements for an integrated circuit chip are evaluated to determine which has the highest fitness in accordance with a predetermined criteria such as interconnect congestion. Each cell placement, which constitutes an individual permutation of cells from a population of possible permutations, is represented as an initial cell placement in combination with a list of individual cell transpositions or swaps by which the cell placement can be derived from the initial cell placement. A cell placement can be genetically mutated and/or inverted by adding swaps to the list for its cell placement which designates cells to be transposed. Genetic crossover can be performed by transposing swaps between the lists for two cell placements. This cell representation and transposition method enables any type of cell transposition to be performed without loss or duplication of cells or generation of illegal placements.

대표청구항 ▼

[ We claim:] [1.] A physical design automation system for determining a highest fitness cell placement for an integrated circuit chip, comprising:a memory for storing a first cell placement as including an initial cell placement and a first list of cell transpositions by which said first cell placem

[ We claim:] [1.] A physical design automation system for determining a highest fitness cell placement for an integrated circuit chip, comprising:a memory for storing a first cell placement as including an initial cell placement and a first list of cell transpositions by which said first cell placement can be derived from said initial cell placement, and for storing a second cell placement as including said initial cell placement and a second list of cell transpositions by which said second cell placement can be derived from said initial cell placement; anda fitness processor for determining which of said first and second cell placements has highest fitness in accordance with a predetermined fitness algorithm.