Cell placement alteration apparatus for integrated circuit chip

Details Cell placement alteration apparatus for integrated circuit chip Cell placement alteration apparatus for integrated circuit chip

1996-09-17

1998-08-11

Teska, Kevin J.

Boots, shoes, and leggings

364489, 364490, 395 13, G06F 1750

Patent

active

057936447

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.

REFERENCES:
patent: 4306286 (1981-12-01), Cocke et al.
patent: 4484292 (1984-11-01), Hong et al.
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 4607339 (1986-08-01), Davis
patent: 4612618 (1986-09-01), Pryor et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4621339 (1986-11-01), Wagner et al.
patent: 4656580 (1987-04-01), Hitchcock, Sr. et al.
patent: 4697242 (1987-09-01), Holland et al.
patent: 4850027 (1989-07-01), Kimmel
patent: 4872125 (1989-10-01), Catlin
patent: 4908772 (1990-03-01), Chi
patent: 4961152 (1990-10-01), Davis
patent: 5051895 (1991-09-01), Rogers
patent: 5136686 (1992-08-01), Koza
patent: 5140526 (1992-08-01), Mc Dermith et al.
patent: 5140530 (1992-08-01), Guha et al.
patent: 5144563 (1992-09-01), Date et al.
patent: 5157778 (1992-10-01), Bischoff et al.
patent: 5159682 (1992-10-01), Toyonaga et al.
patent: 5187668 (1993-02-01), Okude et al.
patent: 5200908 (1993-04-01), Date et al.
patent: 5202840 (1993-04-01), Wong
patent: 5208759 (1993-05-01), Wong
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5222029 (1993-06-01), Hooper et al.
patent: 5222031 (1993-06-01), Kaida
patent: 5224056 (1993-06-01), Chene et al.
patent: 5245550 (1993-09-01), Miki et al.
patent: 5249259 (1993-09-01), Harvey
patent: 5251147 (1993-10-01), Finnerty
patent: 5255345 (1993-10-01), Shaefer
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5465218 (1995-11-01), Handa
patent: 5557533 (1996-09-01), Koford et al.
C. Sechen et al.; Timber Wolf 3.2: A New Standard Cell Placement and Global Routing Package; 1986 IEEE, Paper No. 26.1; pp. 432-439.
D. Lenoski et al.; The Stanford Dash Multiprocessor; Mar. 1992 IEEE; pp. 63-80.
S. Mohan et al.; Wolverines; Standard Cell Placement on a Network of Workstations; Sep. 1993 IEEE, vol. 12, No. 9; pp. 1312-1326.
J.R. Koza; Genetic Programming--On the Programming of Computers by Means of Natural Selection; 1992 MIT, Chapter 6; pp. 94-101 and p. 173.
K. Shahookar et al; A Genetic Approach to Standard Cell Placement Using Meta-Genetic Parameter Optimization; May 1990 IEEE, vol. 9, No. 5; 500-511.
A Nowatzyk et al.; The S3.MP Interconnect System & TIC Chip; Hot Interconnect Symposium, IEEE Computer Society, 1993 Stanford Univ.
J.M. Kleinhans et al.; Gordian: VLSI Placement by Quadratic Programming and Slicing Optimization; Mar. 1991, vol. 10, No. 3; pp. 356-365.
N.A. Sherwani; Algorithms for VLSI Physical Design Automation; 1993 Kluwer Academic Publishers; pp. 70-123.
Swartz et al., "New Algorithms for the placement and Routing of Macro cells," IEEE, 1990, pp. 336-339.

Affiliated with

Also associated with

Rating

Cell placement alteration apparatus for integrated circuit chip does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cell placement alteration apparatus for integrated circuit chip , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell placement alteration apparatus for integrated circuit chip will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-395948