Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-03-08
2002-07-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06415427
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method and apparatus for global routing performed prior to detailed routing in computer-aided automatic layout design of LSI and VLSI and a storage medium, readable by a computer, having a global routing program stored therein, and particularly, to a method and apparatus for global routing used in order to search the minimum cost routing between net terminals using a Steiner tree and a storage medium, readable by a computer, having a global routing program stored therein.
BACKGROUND ART
In a CAD system used for automatically designing a large scale semiconductor integrated circuit such as LSI and VLSI using a computer, firstly, a logical design is performed that determines cells such as AND and OR therebetween and nets connecting the cells therebetween; secondly, an automatic design for cell layout placing the cells on a chip is performed based on a netlist obtained by the logical design and finally, routing is performed that determines wires connecting nets between the cells placed on the chip. The routing is divided into two phases: one is global routing in which net routing is determined without considering timing, delay and so on and the other is detailed routing in which actual routing on the chip is determined in consideration of timing, delay and others. Along with progress in circuit design technology in recent years, improvement on degree of integration in VLSI and increase in circuit scale have been tremendous. For this reason, automatic layout design faces requirement for high speed processing of a large scale circuit.
Simple description will be given, here, of a definition of a global routing problem, an object of the present invention. Consider a region on a grid structure called a grid graph. A grid graph is obtained by a procedure in which a chip region is divided into cell blocks with horizontal and vertical lines and thus formed rectangular cells are represented by vertices and the vertices are connected to form a grid structure, and a terminal of a layout cell is expressed by a black point on a grid structure. Intersections of the horizontal and vertical lines of the grid graph are called grids. A grid size is a total number of grids and in a case where the number of grids in the vertical direction is v counts and the number of grids in the horizontal direction is h counts, the grid size is a value of (h×v). In a case of
FIG. 1
, h=6 and v=6, so a grid size is 36. A global routing problem is to generate line segments on a grid structure so as to connect terminals t
1
, t
2
ad t
3
of a net N therebetween with the line segments. In a case where a plurality of wiring layers exist, each line segment is allotted on a route of the lowest cost. A cost function is generally a wirelength given by a total sum of lengths of line segments and the cost is minimized. Constraints on global routing is not to pass through regions
100
and
102
shadowed with hatching, which regions are a wiring prohibiting region or a highly wiring congested region.
Concise description will be given of well known ones of global routing methods below:
Typically, a maze method and a line search method are named as first two which are procedures regarding a net with two terminals. The maze method is effected as follows: As shown in
FIG. 2
, one terminal t
1
is a source and the other terminal t
2
is a target, and search is performed in a way such that a wave is propagated from the source t
1
. At first, the source t
1
is labeled with [0]. A value of the label is a distance from the source t
1
. Then, a vertex adjacent to the source t
1
is labeled with [1] and a vertex adjacent to the vertex of label [1] is labeled with [2]. Such a procedure is advanced such that a wave propagates. The process is repeated till the wave reaches the target t
2
or till the wave is not propagate any longer. A strong point of the maze method is that the shortest route can be obtained even in consideration of a region where no wiring can be effected. Furthermore, a calculation time is dependent on a grid size, which is O(h×w) wherein a height is indicated by h and a width by w, and O( ) is Order( ) for short. For this reason, the a maze method increases a calculation cost with increase in scale of a circuit and therefore, increase in grid size. Moreover, a memory size for use in storing labels is also dependent on a grid size of a chip.
A line search method is such that as in
FIG. 3
, line segments are generated from the source t
1
and the target t
2
and the line segments are added into lists called an s list and a t list, respectively. A line segment is elongated as long as no obstacle is encountered by the line segment. Search is terminated where a line segment of the s list and a line segment of the t list are encountered by each other. In
FIG. 3
, line segments are elongated such that line segments s
1
, s
2
and s
3
are added to the s list and line segments s
4
, s
5
and s
6
are added to the t list and such a process is terminated where the line segments s
2
and s
4
are encountered by each other to find a route. The line search method reduces the use of a memory by employing line segments instead of grids. In this method, a calculation cost is dependent on the number of line segments L, which is O(L). Such maze and line search methods are capable of not only considering regions
100
and
102
, which regions are a wiring prohibiting region or a highly wiring congested region as obstacles, but performing a multilayer wiring.
Extended methods of the maze method and the line search method are employed for a multiterminal net with three or more terminals, but such an extended method has a defect of falling into a local solution; therefore, a method using a Steiner tree of
FIG. 4
is more excellent in that a high quality solution is obtained. The method using a Steiner tree generates a Sterner tree
104
called RST (rectilinear Steiner tree). A problem of searching the Steiner tree
104
with the minimum cost cannot be solved in a significant time and is of a non-polynominal order complexity that solutions increases in an explosive manner or of no solution being obtainable in polynominal time, but some heuristic methods have been proposed for the problem. A proposed method known is such that when the number of nets is N by definition, the method requires a calculation time and a used memory amount up to the order of O(N
3
logN). A general method using a Steiner tree is performed such that a Steiner tree is generated without any of constraints and in no consideration of obstacles, and when routes of branches of the Steiner tree are obtained, the obstacles are avoided using a maze method or the like.
In a method dependent on a grid size such as a maze method, a problem arises since a calculation time and a used memory amount are increased in a large scaled circuit. On the other hand, the method using Steiner tree has dependency of a calculation time on the number of net terminals. The number of net terminals is at the most several hundreds in a practical circuit. In contrast to this, a grid size of a wiring region amounts to at least several millions or more. Therefore, the method using a Steiner tree is more advantageous in calculation time and used memory amount compared with the maze method. In a general algorithm for generating a Steiner tree, however, no consideration is given to layers, prohibition, a wiring capacity; therefore, such constraints are left up to detailed routing. In this case, a problem imposed on the detailed routing becomes hard and contrary to the expectation, a possibility arises of increasing a calculation time for all the wiring.
DISCLOSURE OF INVENTION
According to the present invention, provided are a method and apparatus for global routing capable of obtaining a high quality solution for global routing that alleviates a load on detailed routing using a Steiner tree, and a storage medium, readable by a computer, having a global routing program stored therein
Matsuoka Hidetoshi
Nitta Izumi
Do Thuan
Fujitsu Limited
Smith Matthew
Staas & Halsey , LLP
LandOfFree
Method and apparatus for global routing, and storage medium... 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 global routing, and storage medium..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for global routing, and storage medium... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2875576