JPH0680732B2 - Wiring method in IC - Google Patents

Description

TECHNICAL FIELD The present invention relates to a layout method of wiring between blocks on an IC.

Conventional technology The line segment search method has been conventionally used as a method of automatically obtaining a route connecting two terminals A and B belonging to different blocks on an IC. In this method, using both terminals A and B as starting points, horizontal and vertical line segments are generated one after another, and when the line segments generated from both terminals intersect, they are used as a route ( "Iwanami Course Microelectronics 3-VLSI Design I" 1985, Iwanami Shoten, pp.202-20
Five).

For example, when blocks are arranged inside the IC chip as shown in FIG. 3, when trying to find a path from the terminal A to the terminal B, first, the line segments A0 and B0 from the terminals A and B are first searched.
To the outer circumference of another block or chip (the line segment first drawn from the terminal is referred to as the 0th line segment and is called "level 0"). If these line segments match or intersect, then the route has been found, but in the case of FIG. 3, A0 and BG do not intersect. In this case, next, a line segment that is orthogonal to each level 0 line segment and can run in the inter-block passage (or the passage around the chip) is referred to as the line segment generated from the 0th line segment. Level 1 ”is generated. In FIG. 3, it is possible to draw three level 1 line segments for A0 (A1 (1), A (2), A (3)) and one line for B0. A1 in the example of FIG.
Since (3) and B1 intersect to form a route, the search ends here, but if the line segments from both terminals do not intersect, high-level line segments are generated one after another, and the intersection occurs. At that point, the line segment passing through the intersection is taken as the route. However, the number of generated line segments increases in a logarithmic manner as the level increases, and the processing time becomes very long. Therefore, a) an upper limit is usually set for the number of search levels.

b) From the line segment candidates to be generated, i) the longest one, ii) the one closest to the starting point (A or B) is selected.

In this way, the search range is limited.

Problems to be Solved by the Invention As is clear from the example shown in FIG. 3, the route (thick solid line) found by the conventional line segment search method connects terminals A and B with a considerable detour. Is. That is, in many cases, the route by the line segment search method has the smallest number of bends, but the route length is not necessarily the shortest. If a person draws a path between both terminals, he will naturally find the shorter, dotted path. The latter route is preferable from the viewpoint of reducing the resistance of the conductor.

Such inconvenience arises from the fact that in the conventional line segment search method, since the route search is terminated at the first intersection, the line segment that meets the other party's line segment first becomes a route. This also tends to cause the line segment that extends to the farthest place to be a path, and causes a problem that the wiring around the chip and the four corners are concentrated.

An object of the present invention is to solve such a problem, to provide an automatic wiring route search method capable of finding more routes and searching for an optimal inter-terminal route according to the purpose.

Means for Solving the Problems In order to achieve the above object, in the IC wiring method according to the present invention, wiring for connecting terminals belonging to different blocks of an IC chip composed of a plurality of blocks is provided in a passage around the block. The method is characterized by including the following steps.

B) A line segment (called a level 0 line segment) is generated in each passage from each terminal.

B) If the level 0 line segment of each terminal matches or intersects, the level 0 line segment is used as the route.

C) If the level 0 line segment of each terminal does not match or intersect, the line segment that is one level higher in the passage that intersects the current line segment (level 0 is next to level 1, level 1 is next to level 2,・
・) Is generated.

D) If the line segments generated by the steps from each terminal do not intersect, the number of levels is sequentially increased and step c) is repeated until the line segments from each terminal intersect.

E) When a line segment of a certain level from each terminal intersects, thereafter, the level is sequentially increased up to a predetermined number of levels, and the search for the intersection of the line segment from each terminal is repeated.

F) A final route between terminals is determined from the routes found by repeating step e) according to a predetermined rule.

In step a), a line segment of level 0 is drawn from each terminal (usually connecting two terminals, but the idea is the same when connecting three or more terminals) toward the passage.
There is only one level 0 line segment for each terminal. Hereinafter, all the line segments are generated only in the passage around the block (between blocks or around the chip), and end when there is a block. If the level 0 line segments from both terminals match, then both terminals are connected by a straight line, and it is clear that this is the shortest path, so let it be the path (step B)). . Even when the level 0 line segment from each terminal intersects, it is considered to be the shortest, so the level 0 line segment is used as the route (step B)).

If the level 0 line segment does not intersect, the line segment that is one level higher (first level 1) is generated in the passage that intersects the current line segment (first level 0) (step c)). Then, it is checked whether or not the line segments of each level generated up to the present from each terminal intersect, and if they do not intersect, the level is raised one after another, and step c) is repeated until the intersection occurs. (Stepni)). When an intersection occurs, a higher level line segment is generated by a predetermined number of levels from that point in the above manner, and it is checked whether the line segment of each level from each terminal intersects ( Step e)). During this period, all the generated intersections (that is, the routes) are picked up including the first generated intersection, and when the generation of line segments of a predetermined number of levels and the checking of the intersections are completed, the picked-up routes are detected. Of these, the route between the terminals is finally determined according to a predetermined rule (step F)). The rules used here are:
For example, selecting the shortest route among the picked-up routes.

Example An example of carrying out the present invention to search for a wiring path between terminals A and B of an IC chip having the block arrangement shown in FIG. 3 will be described below with reference to the flowchart of FIG. 2 and the block diagram of FIG. I will explain.

First, in steps # 10 and # 11, the line segments A0 and B0 of level 0 are output from the terminals A and B, and drawn until they hit another block. Then, in step # 12, it is checked whether these level 0 line segments A0 and B0 match or intersect. If they match, it means that the terminals A and B are connected by one line segment, and if they intersect, they are connected by a line that bends only once. However, since the route is considered to be the shortest distance connecting both ends A and B, the route is set as the route and the search ends here.

If both level 0 line segments A0 and B0 do not intersect at step # 12, 1 is substituted into the level variable n at step # 13, and at step 14, all possible line segments of level n are generated. In the present case, it is the level "1" line segment, and in FIG. 4, three level 1 line segments A1 can be drawn as in the case of FIG. Then, in step # 15, the line segment of the level n of A and the line segments B1, B2, ...
Check if -1 and -1 intersect. If there is an intersection, the route resulting from the intersection is listed and stored in step # 16. Further, the mower search counter CMS is set to a predetermined value CMS1 only when the intersection found in step # 15 is the first one. The mower search counter CMS is a counter for counting how many levels the route is searched after the route is first discovered.

In the case of FIG. 4, since A1 does not intersect with B0, the determination in step # 15 is “none”, and the process proceeds to step # 17. In step # 17, among the level n line segments generated in step # 14, a line segment for continuing the search is selected according to a predetermined criterion. This is to reduce the processing time because the number of line segments to be generated increases mathematically as the level increases. As the reference here, a plurality of lines are selected according to the above-mentioned criteria of b) -i) and b) -ii). The high-level line segment in the processing of the next step # 14 is generated only for the line segment selected here.

In the next steps # 18 to # 21, the same processing as in steps # 14 to # 17 is performed on the terminal B. In the example of FIG. 4, only one level 1 line segment B1 is generated,
As in the case of FIG. 3, since the intersection with A1 occurs here,
In step # 20, the route is stored, and since this is the first route discovery, the more search counter CMS is set to CMS1 (here, temporarily set to 1).

After that, the level variable n is incremented by 1 in step # 22, and then it is checked in step # 23 whether the more search counter CMS is 0 or not. If not 0, the more search counter CMS is decremented by 1 in step # 24, and then the process returns to step # 14 to repeat the same processing at the next level.

In this way, while gradually increasing the level and searching for a route, after the route is first discovered, the more search counter CMS
The more search counter CMS becomes 0 at the time when the search for the number of levels equal to the number CMS1 set to is completed. In this case, the process proceeds to step # 25, the shortest route among all the routes found so far is checked, and it is set as the final route. In FIG. 4, by the search in steps # 14 to # 21 when n = 2, four routes, ..., Are found in addition to the route shown in FIG. Of these, the path having the shortest length is the path, so this path is determined as the final path between the terminals A and B.

In the above embodiment, as shown in FIGS. 3 and 4, since the block structure is relatively simple, the more search counter CMS
Although the shortest path could be found only by setting 1 to 1, in the case of a complicated chip, by setting the more search counter CMS to 2 or 3, many paths can be found and the optimum path can be selected from many candidates. You can choose the route. In addition,
Prolongation of the processing time due to the occurrence of many high-level line segments can be avoided by appropriately adjusting the selection rules of steps # 17 and # 21.

EFFECTS OF THE INVENTION As described above, according to the present invention, the search is not terminated when the line segments from both terminals first meet, and the search is continued for a predetermined number of stages thereafter, so that a plurality of candidate routes You can select a route that is more suitable for your purpose. Therefore, for example, by selecting the shortest route,
Conductor resistance can be minimized. Further, it is possible to prevent the wiring from being concentrated on the outer periphery and the four corners of the chip, and it is possible to achieve a well-balanced arrangement in which the blocks of the chip are appropriately dispersed.

[Brief description of drawings]

FIG. 1 is a claim correspondence diagram, FIG. 2 is a flow chart showing a procedure of an embodiment of the present invention, FIG. 3 is a block diagram showing a route by a conventional line segment search method, and FIG. 4 is a route by this embodiment. It is a block diagram to represent. A, B ...... Terminal A0, B0 ...... Level 0 line segment A1 (1), A1 (2), A1 (3), B1 ...... Level 1 line segment A2, B2 ...... Level 2 line segment ・ ・ ・… Candidate route …… Determination route

Claims (1)

[Claims] 1. An intra-IC wiring method comprising the following steps in a method of arranging a wiring connecting terminals belonging to different blocks of an IC chip composed of a plurality of blocks in a passage around the block. A) A line segment of level 0 is generated in each passage from each terminal. (B) If the level 0 line segment of each terminal matches or intersects, the level 0 line segment is used as the wiring path between the terminals. C) If the level 0 line segment of each terminal does not match or intersect, a line segment of one level higher is generated in the passage intersecting the current line segment. D) If the line segments generated by the steps from each terminal do not intersect, the number of levels is sequentially increased and step c) is repeated until the line segments from each terminal intersect. E) When a line segment of a certain level from each terminal intersects, then the level is increased from that level to a predetermined number of levels, and the search for the intersection of the line segment from each terminal is repeated. F) A wiring route between terminals is determined according to a predetermined rule from the routes found by repeating step e).