2.5-D graph for multi-layer routing

Details 2.5-D graph for multi-layer routing 2.5-D graph for multi-layer routing

2002-01-28

2004-09-14

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06792587

ABSTRACT:

BACKGROUND
1. Field of the Invention
The present invention relates to path search techniques and, more particularly, to systems and methods for routing around obstacles such as for integrated circuit (e.g., VLSI) routing.
2. Description of the Related Art
There are many important engineering applications for solutions to the problem of path searching through a space that includes obstacles. The path searching or routing problem typically includes determining a path from a source to a target through a field or area which includes certain obstacles and a clear space around such obstacles. Path searching is often performed in a two-dimensional space covering the search area. In the semiconductor and electronics arts, for example, routing techniques are often employed for layout of conductive traces around obstacles such as circuit elements or devices.
Path searching problems often involve or even require the use of a greater than two-dimensional search space. For example, modern integrated circuit fabrication processes allow up to seven or more layers of metal for routing electrical connections between pins or nodes of a circuit. Therefore, standard two-dimensional solutions for integrated circuit routing (e.g., VLSI routing) are often insufficient.
Existing approaches to solving the multi-dimensional search problem typically suffer from at least one, and sometimes all of the following disadvantages: (i) complexity, (ii) overlong computational time, (iii) failure to achieve an efficient or optimal path when multiple paths exist, (iv) failure to find a path when one exists. Computational efficiency of path search and routing techniques is important, particularly for complex routing problems such as those presented by modern semiconductor technology. The semiconductor routing industry is one industry which is constantly looking to improve techniques for solving this problem so that the above disadvantages are eliminated or at least mitigated.
SUMMARY
A 2.5-dimensional graph may be constructed for more efficient multiple-layer path searching and routing. The construction of a 2.5-dimensional graph may be conceptualized as taking place in two phases: the subgraph generation phase (e.g., for each layer) and a via connection creation phase. The resulting 2.5-dimensional graph may be used in VLSI routing, for example, which commonly includes multiple routing layers in a given design space.
In one embodiment, a method of building a multi-layer graph for greater than two dimensional integrated circuit routing is provided. The method includes the steps of generating subgraphs and combining the subgraphs into a single, multi-layer graph. Each subgraph corresponds to a layer of circuitry. Each of the subgraphs includes segments based on segments from other layers and intersection points of all such segments. A subgraph for a layer may be generated by generating a set to include graph segments from the layer and from other layers. Two sets may be generated, a first set for segments having a first orientation (e.g., horizontal), and a second set for segments having a second orientation (e.g., vertical). Another set including intersection points of graph segments in the first and second sets, and minimal segments from the first and second sets. Points may be marked according to possible coverage by elements in other layers as is discussed in detail herein. The subgraph includes the intersection points as nodes of the subgraph and the minimal segments as edges between the nodes. An integrated circuit may be made by a process including such steps.
In another embodiment, a method of routing through a route space including a plurality of route layers includes the steps of generating a subgraph for each of the routing layers and generating a multi-layer route graph including a plurality of the generated subgraphs. Each subgraph corresponds to a routing layer. Each subgraph includes a plurality of route segments based on information from the corresponding routing layer and a plurality of route segments based on information from other routing layers.
In another embodiment, a product (e.g., a computer program product) for receiving routing data regarding a multi-layer routing problem and for generating a multi-layer graph to facilitate resolution of the routing problem includes a first module for generating a plurality of subgraphs, and a second module for combining all of the plurality of subgraphs into a single, multi-layer graph. Each of the plurality of subgraphs corresponds to each of a plurality of layers of the routing data, and each of the plurality of subgraphs includes a plurality of segments based on information from other layers of the routing data
In another embodiment, a 2.5-D graph is used for multi-layer, integrated circuit routing. The 2.5-D graph includes subgraphs corresponding to circuit layers, and each subgraph includes a set of routing segments selected using information from the corresponding circuit layer and at least one other circuit layer.
The foregoing is a summary and thus contains, by necessity, simplifications, generalizations and omissions of detail. Consequently, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting. Other aspects, inventive features, and advantages of the present invention, as defined solely by the claims, will become apparent in the nonlimiting detailed description set forth below.


REFERENCES:
patent: 5748844 (1998-05-01), Marks
patent: 5841664 (1998-11-01), Cai et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6182272 (2001-01-01), Andreev et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6292928 (2001-09-01), Yamaguchi et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 6353918 (2002-03-01), Carothers et al.
patent: 6415427 (2002-07-01), Nitta et al.
patent: 6477692 (2002-11-01), Marchenko et al.
Wu, Ying-Fung et al., “Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles,” IEEE Transactions on computers, vol. C-36, No. 3, Mar. 1987, pp. 321-331.
Zheng, S. Q. et al., “Finding Obstacle-Avoiding Shortest Paths Using Implicit Connection Graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 1, Jan. 1996, pp. 103-110.

Affiliated with

Also associated with

Rating

2.5-D graph for multi-layer routing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with 2.5-D graph for multi-layer routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 2.5-D graph for multi-layer routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3199700