JPH01304584A - Wiring design method for integrated circuit - Google Patents

Abstract

PURPOSE:To improve the route finding capability and to quickly design wiring by using a quick wiring technique for the inside of a sparse area and using a wiring technique superior in route finding capability for the area between sparse areas. CONSTITUTION:In a processing process 1, a group of sparse areas where the degree of thickness of already arranged wiring patterns is lower than a threshold is extracted. In a processing process 2, the manner in which wiring should pass extracted sparse areas is determined. In a processing process 3, concrete wiring routes in the sparse area are obtained by the quick wiring technique. In a processing process 4, wiring routes between sparse areas are obtained by the wiring technique superior in route finding capability. In a processing process 5, sparse areas are corrected in accordance with wiring information newly generated in the processing process 3 for wiring in sparse areas and the processing process 4 for wiring between sparse areas.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a wiring design method for integrated fIf circuits, and particularly to a wiring design method for large-scale integrated circuits.

[Conventional technology]

Conventionally, in integrated circuit wiring design, all wiring is routed using the same wiring method, or for connection requests that cannot be routed using high-speed wiring methods, a low-speed wiring method with excellent route finding ability is used. I am using it.

For example, Hightower's algorithm is a high-speed wiring method, and Hiichi's algorithm is a low-speed wiring method with excellent route finding ability. The details of both can be found in Sucup's ``Circuit Layout'' and Proceedings of the ITriple E (1'ROCF,E
DINGS OF THE IEEE>1981
No, 10 PP1.281 ~1304
5 of them are listed in .

[Problem to be solved by the invention]

The conventional wiring design method described above has the disadvantage that if all wiring is done using a high-speed wiring method, many connection requests that cannot be routed (hereinafter referred to as unconnected lines) remain. If this is done using a wiring method that has excellent route discovery ability, it has the disadvantage that the computer processing time will be enormous.

In addition, even if a wiring method with excellent route finding ability is used only for unconnected wires after using a high-speed wiring method, if the unconnected terminal pairs are located far apart on the board, The disadvantage is that wiring design takes time. That is, the wiring method, which has a poor route discovery ability, has to investigate all possibilities of the existence of a route, so the processing time increases in proportion to the area of the rectangle that encloses the terminal pair.

An object of the present invention is to provide a wiring design method for integrated circuits that enables wiring design for integrated circuits to be performed efficiently in a short period of time, and that allows wiring design to be easily performed even if the terminals to be connected are far apart. Our goal is to provide the following.

[Means to solve the problem]

The integrated circuit wiring design method of the present invention is an integrated circuit that realizes an integrated circuit having a desired logical function by forming a wiring pattern between signal input and output terminals of a plurality of functional cells formed on a semiconductor substrate by computer processing. In a circuit wiring design method, there is a step of extracting a heel region group in which the density of already placed wiring patterns is less than a threshold value, and a step of extracting each connection request between the terminals as wiring within a sparse region and wiring between line regions. The process of dividing into
The method includes a step of wiring the sparse area wiring using a high-speed wiring method, and a step of wiring the inter-line region wiring using a high-performance route detection wiring method.

〔Example〕

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a flow diagram for explaining the outline of wiring design according to the present invention.

As shown in Figure 1, the Gagaru wiring design begins with processing step 1 of extracting a line area where wiring or wiring prohibitions are not concentrated from information on the wiring and wiring prohibition areas existing on the semiconductor substrate, and then Processing step 2 for determining how to route wiring through the sparse 6y area extracted in the line area extraction step for one connection request, and the sparse area determined to be routed through in the routing determination processing step. Step 3 of determining a specific wiring route in the sparse area and determining a wiring route between the heel areas, that is, a wiring route between the heel areas in the dense area. 4, and a processing step 5 of correcting the line area from the wiring information newly generated in the sparse area wiring processing step 3 and the line area wiring processing step 4.

FIG. 2 is a plan view of a semiconductor substrate having a wiring pattern formed according to the flow shown in FIG. 1.

As shown in FIG. 2, this semiconductor substrate 12 has terminals 6 and 7.
The line areas 8 and 11 are used for connection. First, line regions 8~], 1 are determined on the semiconductor substrate]2, and terminals 6,
Determine the line area 8.11 to be used in determining the route connecting between 7 and 7.

After that, wiring 13.14 in the line area 8.11 is performed,
Next, wiring 15 and 16 between the heel regions is performed. This heel area 8,
11 is formed using a high-speed wiring method, and the heel area 8,
The 11 questions and between the line area 11 and the terminal 7 are formed using a high-performance wiring method. Therefore, even if the terminals 6 and 7 are far apart on the board 12, the areas to which the high-performance wiring method is applied are the wiring 13 and 14 in the dense area 17, and the wiring 14 and terminal 1.
Since it is limited to a relatively narrow area between 7 and 7, it has the advantage that processing time can be significantly shortened.

FIGS. 3(a) to 3(f) are plan views for determining line areas on a semiconductor substrate shown in the order of steps for explaining an embodiment of the present invention. Note that a wiring grid is formed on the semiconductor substrate. X
They are defined in the axial direction and the Y-axis direction, respectively.

In such a line region extraction process, first, as shown in FIG. 3(a), a wiring pattern 18 and one straight region in the X-axis direction with a length of 2 or more where no inhibition exists are determined using a wiring grid. Next, as shown in FIG. 3(b),
) The linear region 19 obtained in step 2 is duplicated α times in the upper and lower directions. Next, as shown in FIG. 3(c), the sum of the overlapping linear regions 19 obtained in FIGS. 3(a) and 3(b) is taken to make one line. Next, as shown in FIG. 3(d), among the straight line regions 19 obtained in FIG. 3(c), those adjacent to each other and having the same length are summed to form one X-direction rectangle. . Next, as shown in FIG. 3(e), the above-mentioned FIG.
A rectangle 21 in the Y direction is created in the same manner as in (d).

Furthermore, as shown in FIG. 3(f), FIG.
Among the rectangles obtained in step e), those that overlap each other are summed to form one sparse region 22.

Next, the formation of wiring patterns inside and outside the sparse area will be explained with reference to FIGS. 4(a) to 4(c).

FIGS. 4(a) to 4(c) are diagrams of wiring patterns inside and outside the sparse region shown in the order of steps for explaining one embodiment of the present invention.

As shown in FIG. 4(a), when selecting the sparse area, first, the first cost (a function of expected processing time and path length) required for passing through the sparse area 22 is determined. Next, the second cost I· required to connect the sparse regions 22 is determined. Next, the third cost required to connect from the connection request terminal 21 to the sparse area 22 and the connection request terminal 21
Find the fourth cost required for the connection between. Next, the terminals to be passed through to connect between the connection request terminals 21 and the sparse area 2
2 series and the sum of the second costs between consecutive sparse regions 22 on the series, the phase of the first cost of the sparse regions 22 on the series, and the sparse regions 22 at the beginning and end of the series, respectively. The series 23 with the minimum cost is determined such that the sum of the third and fourth costs up to the terminal 21 is the minimum.

Next, as shown in FIG. 4(b), in the wiring process within the sparse area, a line is drawn from the positional relationship of two consecutive sparse areas on the series obtained in the process of FIG. 4(a) above. The edge of the boundary where the inter-area wiring intrudes into the sparse area 22 is determined. After finding the boundary edges for all sparse regions in this way, each sparse region 2
Using the Hightower method, the determined wiring pattern 25 is routed between the two sides of the boundary of the sparse region 22 just determined in 2, where there is no wiring prohibition pattern 24 or the like.

Next, as shown in FIG. 4(c), in the wiring process between the line areas, 2
Between the two continuous sparse areas 22 (the terminals 21), the wiring pattern 25 obtained in Fig. 4(b) (between the wiring pattern and the terminals obtained in Fig. 4(b)) is The obtained wiring pattern 27 is wired in a place where there is no wiring prohibition pattern 24 using the method.

Regarding sparse region reconstruction processing 5 when all connection request processing has not been completed, the same processing as line region extraction processing 1 is newly performed on the sparse regions passed through sparse region selection processing 2, and the sparse region is Update.

〔Effect of the invention〕

As explained above, the integrated circuit wiring design method of the present invention divides the determination of wiring routes into sparse areas and between line areas, uses a high-speed wiring method within the sparse areas, and uses a high-speed wiring method between line areas. By using a wiring method with excellent route discovery ability, the route discovery ability is higher than when only using a high-speed wiring method, and when compared with only using a wiring method with excellent route discovery ability. This has the advantage that it can be performed at high speed.

[Brief explanation of the drawing]

FIG. 1 is a flowchart for explaining the outline of the wiring process of the present invention, FIG. 2 is a plan view of a semiconductor substrate having a wiring pattern formed based on the flow shown in FIG. 1, and FIG.
) to (f) are plan views of line regions on a semiconductor substrate shown in the order of steps for explaining an embodiment of the present invention, and FIGS.
(c) is a wiring pattern diagram inside and outside the sparse region shown in the order of steps for explaining one embodiment of the present invention. ■...Line area extraction processing, 2...Sparse area selection processing,
3... Wiring processing within the sparse area, 4... Wiring processing between line areas, 5... Reconfiguration processing of the sparse area, 6, 7.21...
・Signal input/output terminal, 8 to 11.22...Sparse area, 12
...Semiconductor substrate, 13-16, 1.8, 25.27.
... Wiring pattern, 17... Dense area, 1... Straight line area, 20... Rectangle in the X direction, 21... Rectangle in the X direction, 23... Line area series with minimum cost, 24...・Wiring prohibited or already wired pattern. Taku j Kasumi Straw Z Kasumi Sword 3 Trouble 22 ゛, 23 Kos, Yumika/2) no Mi 11
Figure 4

Claims (1)

[Claims] In an integrated circuit wiring design method, a wiring pattern is formed between the signal input and output terminals of a plurality of functional cells formed on a semiconductor substrate by computer processing to realize an integrated circuit having a desired logical function. a step of extracting a group of sparse regions in which the density of wiring patterns is less than a threshold;
a step of dividing each connection request between the terminals into wiring within the sparse area and wiring between the sparse areas; a process of wiring the wiring within the sparse area using a high-speed wiring method; 1. A wiring design method for an integrated circuit, comprising the step of wiring using a route detection wiring method.