Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-03-31
2003-02-11
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06519751
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention generally relates to design and layout of integrated circuits and more specifically relates to automatic placement and routing of signals on VLSI semiconductors and the software for performing such placement and routing.
2. Description of the Related Art
Routing signals (conductors) on integrated circuits from sources to destinations or between multiple drivers and receivers is vital to the design and production of integrated circuits. As the density of circuitry on an integrated circuit increases, the number of these signals tends to increase, thus making routing of the signals more complex. Additionally, the wider and widening data busses tend to result in increasing numbers of signals that must be routed to have similar delays as a group.
In semiconductors, horizontal signal legs often are routed in a first layer of conductor (metal or polysilicon for example) and vertical signal legs are often routed in a second layer of conductor. The horizontal and vertical signal legs are alternated for succeeding layers of conductors (up to the seven or eight layers that may currently be available). An alternative method of routing uses conductors that actually “bend” or are used for both horizontal and vertical legs of a signal.
Furthermore, a common approach to routing involves attempting a general global routing of signals across a device, resulting in assignment of signals to a path through a set of regions. Then, routing of each region of the device occurs, wherein routing of the signals within each region is subject to constraints resulting from the global routing, and signals routed through multiple regions must be routed such that there are no discontinuities at region boundaries.
FIG. 1
illustrates two of the problems commonly found when attempting to route signals on an integrated circuit. The signals enter or exit the regions at crosspoints, the points or vertices on the boundary of the region through which the signal passes. Note that these points or vertices are not geometrically ideal, they have a width fixed by the design limitations of the integrated circuit and the process by which it is manufactured. Likewise, the crosspoints require a minimum spacing that also comes from the same design limitations of the integrated circuit and the process by which it is manufactured. The integrated circuit is divided up into regions through which signals are routed, as illustrated by the grid pattern.
The first problem illustrated is an L-shaped crossover, in which two signals are routed such that portions of the two signals are routed close to each other or even overlap. Signal A is routed from terminator A
1
to terminator A
4
. Along the route, signal A enters a first area at crosspoint A
2
and leaves the first area at crosspoint A
3
. Signal B is routed from terminator B
1
to terminator B
4
. Signal B is also routed through a first area, entering at crosspoint B
2
and leaving at crosspoint B
3
. (It will be appreciated that the conventions of entering and leaving are used for ease of illustration, and that the conductors or signals allow for flow of electrons or information in any direction between terminators on the signal.) As is apparent from the illustration, terminator B
4
and terminator A
4
are nearly at the same location in terms of the horizontal axis of the integrated circuit. As a result, crosspoint A
3
and crosspoint B
3
are nearly connectable by a straight line parallel to the edge of the semiconductor, and thus signal A and signal B nearly overlap in the region where they are made up of horizontal signal legs. If these two horizontal signal legs are routed in the same conductor (for example the first metal layer of a silicon semiconductor), they will be nearly impossible to route because each separate leg within a layer must be separated by a minimum distance determined by the manufacturing process. Furthermore, even this minimum distance may be insufficient, as crosstalk between the signal legs may result in unacceptable noise on the two signal lines.
The second problem illustrated in
FIG. 1
is an X overlap between two signals. Signal C is routed from terminator C
1
to terminator C
4
. Signal C enters a second area at crosspoint C
2
and leaves the second area at crosspoint C
3
. Signal D is routed from terminator D
1
to terminator D
4
. Signal D also traverses the second area, entering at crosspoint D
2
and leaving at crosspoint D
3
. As will be appreciated, terminator C
1
and terminator D
4
are essentially lined up on a line parallel to the edge of the semiconductor, as are terminator D
1
and terminator C
4
. As a result, signal C and signal D must cross at some point to achieve a reasonably short routing between the terminators for each signal. An actual diagonal crossing as illustrated here is likely to result in one of the signals being nearly unroutable or actually unroutable, since it would be nearly impossible to avoid some sort of overlap. Furthermore, diagonally routed signals in a design which primarily uses horizontal or vertical signals tend to effectively foreclose large areas of the integrated circuit from use for other signals relative to the signals actually routed therein.
SUMMARY OF THE INVENTION
In one embodiment the invention is a method. The method includes finding costs to route a net to a set of crosspoints on a boundary. The method also includes propagating the costs to a succeeding set of nodes.
REFERENCES:
patent: 4484292 (1984-11-01), Hong et al.
patent: 4615011 (1986-09-01), Linsker
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5841673 (1998-11-01), Kobayashi et al.
patent: 6295634 (2001-09-01), Matsumoto
Helvig et al. (“Improved approximation bounds for the group Seiner problem”, Proceedings of Design, Automation and Test in Europe, Feb. 23, 1998, pp. 406-413).*
Cong et al. (“Performance-driven routing with multiple sources”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, No. 4, Apr. 1997, pp. 410-419).*
NA9002469 (“Partitioning Logic On to Graph Structures”, IBM Technical Disclosure Bulletin, vol. 32, No. 9A, Feb. 1, 1990, pp. 469-475 ( pages)).*
NB9001129 (“New Algorithm for Stable Rectilinear Seiner Trees”, IBM Technical Disclosure Bulletin, vol. 32, No. 8B. Jan. 1990, pp. 129-132 (6 pages)).*
NA83045571 (“Procedure for Connecting N Points with Near Minimum Cost”, IBM Technical Disclosure Bulletin, vol. 25, No. 11A, Apr. 1983, pp. 5571-5575 (7 pages)).*
NA78308929 (“Chip Model With Wiring Cost Map”, IBM Technical Disclosure Bulletin, vol. 26, No. 3A, Aug. 1983, pp. 929-933 (7 pages)).*
NA8909315 (“Generalization of Min-Cut Partitioning to Tree Structures”, IBM Techical Disclosure Bulletin, vol. 32, No. 4A, Sep. 1989, pp. 315-322 (10 pages)).
Huang May
Sriram Mysore
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Kik Phallaka
Siek Vuthe
LandOfFree
Method and apparatus for accurate crosspoint allocation in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for accurate crosspoint allocation in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for accurate crosspoint allocation in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149730