Cell placement representation and transposition for integrated c

Details Cell placement representation and transposition for integrated c Cell placement representation and transposition for integrated c

1994-04-19

2000-12-05

Teska, Kevin J.

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

39550011, 39550012, 709213, G06F 1750

Patent

active

061557250

ABSTRACT:
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.

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: 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: 4850027 (1989-07-01), Kimmel
patent: 4872125 (1989-10-01), Catlin
patent: 4908772 (1990-03-01), Chi
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: 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: 5349536 (1994-09-01), Ashtaputre 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 Automaton 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.
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 System & TIC Chip", Proceedings of IEEE Computer Society HOT Interconnect Symposium, Stanford Univ., 1993.
Shahookar et al., "VLSI Cell Placement Techniques," ACM Computing Surveys, vol. 23, #2, Jun. 1991, pp. 143-219.

Affiliated with

Also associated with

Rating

Cell placement representation and transposition for integrated c 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 representation and transposition for integrated c, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell placement representation and transposition for integrated c will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-955135