Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-10-27
2001-07-24
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06266802
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to electronic circuit design, and more particularly, to layout of a detailed grid point interconnect for integrated circuits.
2. Description of Related Art
The process of creating a complex integrated circuit (IC) chip design or a Printed Circuit Board (PCB) requires a wiring process that connects the inputs and outputs of each component within the design. This process is typically one of the last steps in the overall design process, so the designer is always under time pressure to finish the wiring process very quickly. Moreover, the designer wants the wiring process to optimize the circuit performance and reduce the noise interactions on the IC chip or PCB.
The IC chip and PCB designs of today contain up to 4 billion grid points across their topology, where the grid points are intersections of a three-dimensional mesh that is used as a construct to make the interconnections required by the IC chip or PCB. A “pin” is a set of grid points, not necessarily contiguous, that are defined to be electrically connected to each other. A “net” consists of pins, plus interconnect wiring that connects the pins to each other. The interconnect wiring is a sequential set of grid points such that each pair of grid points in the sequence is adjacent. The final net becomes an interconnection from one point on an IC chip to another point on the IC chip. The net should be of minimal length and may be constrained because of other design factors, e.g., noise tolerance, speed, etc., so a given net may have to be separated by a certain distance from other nets on the IC chip or PCB. Further, the design factors for a given net may include a width factor, where the net must have a width greater than one grid point, for current carrying capabilities or other reasons.
Large “nets” that connect components can be contained in an average area of less than 15 thousand grid points, and the average connection is in the range of 100 to 200 grid pins. Millions of nets per IC chip or PCB must be traced out through these grid points.
Creating optimal solutions to these large problems with today's CPU power and state-of-the-art software takes days or weeks to get usable results. The wiring process typically takes on the order of n
2
in time, where n is the number of grid points for the length of the path. As designs get larger, the time to complete the wiring process will take an increasingly longer time. Further, long run times discourage optimization, resulting in interconnects that may exceed a maximum length and result in poor design operation or fail due to noise problems.
When the problem is partitioned into sub areas through hierarchy or simple area partitioning, the resulting solution is not globally optimized and results in longer paths for the final net interconnects. Further, area partitioning does not allow for finding and repairing local problems, nor does it allow for weighting of interconnects on a global scale.
There is a need, then for a suitable approach to the wiring process. There is also a need for a solution that reduces the time taken to solve the wiring problem. Further, there is a need for a solution that takes less time but still optimizes the wiring process. There is also a need for finding localized problems quickly for manual intervention if necessary. There is also a need for allowing dynamic weight changes for interconnect and grid point propagation. There is also a need for allowing dynamic grid point propagation blocking.
SUMMARY OF THE INVENTION
To minimize the limitations in the prior art described above, and to minimize other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a powerful and highly productive method and apparatus for solving a detailed grid point layout scheme.
The present invention solves the above-described problems by using a small inner loop concentrated on the nearest neighbors of the grid point, and uses a global solution technique to reduce the time required to something on the order of n, where n is the number of grid points in the average connection. This is accomplished by using massively parallel systems to trace multiple interconnects for each desired interconnect simultaneously.
A method in accordance with the principles of the present invention comprises the steps of creating a grid point model with originations and associated destinations, and also creating a weighting for each of the points within the grid point model. Interconnects can then be routed from the originations to the associated destinations, wherein the interconnect contains grid points. The weights for each of the grid points within each interconnect are then accumulated.
REFERENCES:
patent: 3653072 (1972-03-01), Ballas et al.
patent: 4306286 (1981-12-01), Cocke et al.
patent: 4484292 (1984-11-01), Hong et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4752887 (1988-06-01), Kuwahara
patent: 4777606 (1988-10-01), Fournier
patent: 4890238 (1989-12-01), Klein et al.
patent: 4910680 (1990-03-01), Hiwatashi
patent: 5072402 (1991-12-01), Ashtaputre et al.
patent: 5198987 (1993-03-01), Shindo et al.
patent: 5245550 (1993-09-01), Miki et al.
patent: 5341310 (1994-08-01), Gould et al.
patent: 5361214 (1994-11-01), Aoki
patent: 5375069 (1994-12-01), Satoh et al.
patent: 5394337 (1995-02-01), Shinjo
patent: 5402359 (1995-03-01), Oyanagi
patent: 5434972 (1995-07-01), Hamlin
patent: 5483481 (1996-01-01), Hizume et al.
patent: 5500804 (1996-03-01), Honsinger et al.
patent: 5551013 (1996-08-01), Beausoleil et al.
patent: 5566342 (1996-10-01), Denneau et al.
patent: 5583788 (1996-12-01), Kuribayashi
patent: 5636129 (1997-06-01), Her
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5673201 (1997-09-01), Malm et al.
patent: 5717600 (1998-02-01), Ishizuka
patent: 5757089 (1998-05-01), Ishizuka
patent: 5856927 (1999-01-01), Greidinger et al.
Malm Richard LaVerne
Meiley Charles L.
Nemec, II Frank Albert
Garbowski Leigh Marie
International Business Machines - Corporation
Merchant, Gould, Smith, Edell, Welter & Schmidt
Smith Matthew
LandOfFree
Detailed grid point layout using a massively parallel logic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detailed grid point layout using a massively parallel logic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detailed grid point layout using a massively parallel logic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2482968