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

1994-04-19

1996-09-17

Teska, Kevin J.

Boots, shoes, and leggings

364490, 364489, 395 13, G06F 1750, G06F 1518

Patent

active

055575331

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: 4675829 (1987-06-01), Clemenson
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), McDermith 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.
Sherwani, Naveed, "Algorithms For VLSI Physical Design Automation", Kluwer Academic Publishers, 1993.
Sechen, Carl and Sangiovanni-Vincentelli, Alberto, "TimberWolf 3.2: A New Standard Cell Placement and Global Routing Package", IEEE 23rd Design Automation Conference, 1986, Paper 26.1.
Shahookar, Khushro and Mazumder, Pinaki, "A Genetic Approach to Standard Cell Placement Using Meta-Genetic Parameter Optimization", IEEE Transactions on Computer-Aided Design, vol. 9, No. 5, May 1990.
Mohan, S. and Mazumder, Pinaki, "Wolverines:Standard Cell Placement on a Network of Workstations", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 9, Sep. 1993.
Lenoski, Daniel, et al., "The Stanford Dash Multiprocessor", Computer, Mar. 1992.
Koza, John, Genetic Programming, MIT Press, Cambridge, MA 1993, pp. 94-101 and 173.
Nowatzyk, A. and Parkin, M., "The S3.mp Interconnect & TIC Chip", Proceedings of IEEE Computer Society HOT Interconnect Symposium, Stanford Univ., 1993.

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-418713