Integrated circuit layout routing using multiprocessing

Details Integrated circuit layout routing using multiprocessing Integrated circuit layout routing using multiprocessing

1996-12-04

1999-11-09

Teska, Kevin J.

Boots, shoes, and leggings

364488, G06F 1750

Patent

active

059800933

ABSTRACT:
A multithreaded wavefront routing system for simultaneously planning routes for wiring a semiconductor chip surface. The surface has a plurality of grids located thereon, and routes are planned according to a predetermined netlist. The system steps across the surface from a first location to a second location in a wave-type pattern. The system sequentially steps through the grid arrangement on the chip surface and plans routing one grid at a time using a plurality of threaded processors. The system recognizes pins as it steps through grids and determines a plan for the current grid by evaluating current wire position, target pin location, and any currently planned routes, designating reserved locations wherein the route may be planned subsequent to the current grid, and establishing a wire direction for each wire traversing the current grid. The system plans wiring through grids using multiple threaded processors employing shared memory and a semi-hard coded rule based expert system applying heuristics by planning various routes based on current and potential wire locations.
The system propagates wiring and performs memory bookkeeping functions. The system also has the capability to plan an additional route from one target pin toward a first pin. Meetings between routes are designated and resolved. Reservations may be established when a processor plans a route. Mutex locks may be utilized to avoid multiprocessor conflicts.

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: 4613941 (1986-09-01), Smith 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: 4777606 (1988-10-01), Fournier
patent: 4815003 (1989-03-01), Putatunda et al.
patent: 4850027 (1989-07-01), Kimmel
patent: 4872125 (1989-10-01), Catlin
patent: 4908772 (1990-03-01), Chi
patent: 4918614 (1990-04-01), Modarres et al.
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: 5198987 (1993-03-01), Shindo 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), Antereich et al.
patent: 5297283 (1994-03-01), Kelly, Jr. et al.
patent: 5361214 (1994-11-01), Aoki
patent: 5587923 (1996-12-01), Wang
patent: 5631842 (1997-05-01), Habra et al.
patent: 5636129 (1997-06-01), Her
patent: 5742510 (1998-04-01), Rostoker et al.
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.
Sherwani, Naveed, "Algorithms for VLSI Physical Design Automation," Kluwer Academic Publishers, 1993.
Sechen, Carl and Sangiovanni-Vincentelli, Alberto, Timber Wolf 3.2: A New Standard Cell Placement and Global Routing Package, IEEE 23rd Design Automation Conference, 1986, Paper 26.1.
Nowatzyk, A. and Parkin, M., "The S3.MP Interconnect System & TIC Chip," Proceedings of IEEE Computer Society Hot Interconnect Symposium, Stanford University, 1993.
Shahookar et al., "A Genetic Approach to Standard Cell Placement Using Metagenetic Parameter Optimization," IEEE 1990, vol. 9, No. 5, no pp#.

Affiliated with

Also associated with

Rating

Integrated circuit layout routing using multiprocessing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Integrated circuit layout routing using multiprocessing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated circuit layout routing using multiprocessing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1446803