JPH05243383A - Automatic wiring method - Google Patents

Abstract

PURPOSE:To suppress a delay due to a crosstalk within a range observing a given restriction and to reduce a manual correction process by a method wherein the length of parallel interconnections is controlled so as to be adapted to a parallel wiring restriction in an automatic wiring processing operation. CONSTITUTION:An automatic wiring processing operation is divided into a data input processing part 101, a restriction-generation processing part 102 and an allocation processing part 103. In the restriction-generation processing part 102, a parallel wiring, restriction-generation processing operation 106 proceeds in the order of a restriction-generation, inspection-object generation processing operation 107 and a restriction-generation, inspection processing operation 108. Although it is required to separate two trunk lines by a distance suppressing a delay due to a crosstalk between them within a permissible range, it is not required to decide their relative positions. As a result, they can be expressed by a nondirectional edge in the same manner as a horizontal restriction. Thereby, it is possible to generate a wiring route which observes a delay restriction without violating a parallel wiring operation.

Description

Detailed Description of the Invention

[0001]

[Industrial field of application] Delays have been taken into consideration beforehand as the allowable values of signal delays have become stricter due to demands for miniaturization and higher integration of semiconductor integrated circuits in recent years, and higher speed of circuit operation. Automatic wiring processing is required.

According to the present invention, in an automatic wiring processing method for a semiconductor integrated circuit such as VLSI, a constraint is imposed to prohibit the determination of a route close to a wiring which may possibly be parallel during the processing, and delay due to crosstalk between signals is prevented. The present invention relates to a method of performing automatic wiring so as not to exceed an allowable range.

[0003]

2. Description of the Related Art Conventionally, in automatic wiring processing, high speed and
A high wiring rate has been demanded to be satisfied. But,
With the development of semiconductor technology in recent years, the allowable value for signal delay of semiconductor integrated circuits is becoming stricter, and after performing automatic wiring processing, it is inspected whether all parallel wiring violates the limit length, Countermeasures have been taken such as manually correcting the violated items.

[0004]

In the above prior art, after the automatic wiring process is once performed, (1) a set of parallel wirings is extracted, and (2) a parallel length of the wiring set is given in advance. If it exceeds the limit length, it is inspected. If it exceeds, (3) the path of the wiring is manually corrected to avoid the violation. For this reason, the number of parallel wiring violations causes a significant increase in man-hours. Furthermore, with the recent increase in the scale and speed of semiconductor integrated circuits, the constraint that prohibits parallel path determination (hereinafter, parallel wiring constraint) is becoming more and more severe, and the number of man-hours is increasing more than ever. There is.

It is an object of the present invention to provide an automatic wiring method for generating a wiring path complying with a delay constraint without causing a parallel wiring violation in order to eliminate the manual correction of the parallel wiring.

[0006]

Before the wiring route is determined, for each combination of wirings, the one that may violate the delay constraint when the combination is parallel is detected, and the parallel length between the combinations is detected. And a parallel wiring constraint that controls the wiring interval and a wiring route is determined so as to comply with the delay constraint.

[0007]

According to the present invention, the above-mentioned parallel wiring constraint is given to a set of wirings which are parallel for a long time and which may violate the delay constraint, and the route determination is performed in compliance with the parallel wiring constraint. By shortening the length of, the delay due to crosstalk is reduced so that it falls within the range that satisfies the requirements given to the circuit.

[0008]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 shows an example of the flow of automatic wiring processing in which the present invention is applied to a channel allocation method which is one of the existing basic methods of automatic wiring. The channel allocation method is
This is a method of determining a wiring path in a rectangular wiring region 202 in which terminals 201 of circuit elements are arranged on the upper and lower sides called channels as shown in FIG. 2A. The terminals of the same net (203 and 204 in the example of FIG. 7B) are connected by using a horizontal wiring 205 called a trunk line and a vertical wiring 206 called a branch line. Also, two or more wiring layers are prepared (207 and 208 in the case of two layers in the example of FIG. 7C), and the direction of the wiring using each layer is fixed to either horizontal or vertical, and the main line and the branch line are fixed. Through holes 209 are used for connection. In the layer 207 for the horizontal direction, a grid (track) 210 to which main lines are allocated, and the layer 20 in the vertical direction are provided.
In 8, grids (columns) 211 for setting main lines and branch lines are set, and the main lines and branch lines are assigned to each grid so as not to overlap each other.

As shown in FIG. 1, the automatic wiring process is roughly divided into three parts (data input processing unit 101, constraint generation processing unit 102, allocation processing unit 103).

When the automatic wiring process is started, first, logical information about wiring such as the name of the net assigned to the terminal of the circuit element by the data input processing unit 101, the shape of the wiring channel and the terminal position of the circuit element. Is received, and data necessary for automatic wiring by the channel allocation method such as a trunk line, a branch line, and a connection relationship between them is generated.

Next, the generation constraint processing unit 102 is divided into three processing portions (vertical constraint generation processing unit 104, horizontal constraint generation processing unit 105, parallel wiring constraint generation processing unit 106) according to the types of constraints generated therein. Be done. The present invention relates to the parallel wiring constraint generation processing unit 106 among them.

Here, the vertical constraint and the horizontal constraint will be described with reference to FIG. 3 by taking the case where the number of wiring layers is two as an example. In the figure, 301 is a column, 302 is a track, and 30
3, 306, 312 and 315 are trunk lines, 304, 30
7, 313 and 316 are branch lines. The trunk line and branch line are connected by through holes indicated by 304, 308, 314 and 317, respectively.

As shown in FIG. 3A, branch lines 304 and 307 in which trunk lines 303 and 306 exist in the same column.
If it has, the two main lines cannot be assigned to the same track, and if the main line 303 is assigned below the main line 306, the branch lines 304 and 307 will overlap, so the main line 303 must be assigned above the main line 306. In order to avoid this, a relationship in which the relative relationship of the wiring allocation positions is determined by the direction in which the branch line exits from the main line is called vertical constraint, and on the graph, 309 and 31 in FIG.
It is represented by a directed edge 311 that is stretched between two trunk lines represented by 0 nodes.

Further, even when there is a horizontal overlapping portion between the main lines like the main lines 312 and 315 shown in FIG. 7C, it is impossible to allocate the two main lines to the same track. However, here, the relative positional relationship for allocating the two wirings cannot be determined so that the main line 312 may be allocated above or below the main line 315. Such a relationship is called a horizontal constraint. The graph is represented by an undirected edge 320 stretched between two trunk lines represented by the nodes 318 and 319 in (d). These edges have the distance between wires obtained from the design rule as their weight.

The vertical constraint generation processing unit 104 and the horizontal constraint generation processing unit 105 detect the above relationship and generate directed / undirected edges.

Next, the parallel wiring constraint generation processing 106 according to the present invention will be described. In the processing, the processing proceeds in the order of the constraint occurrence inspection target generation processing 107 and the constraint occurrence inspection processing 108,
The parallel wiring constraint generated here is a horizontal constraint because it is necessary to separate the two trunk lines by a distance such that the delay due to crosstalk between them falls within an allowable range, but it is not necessary to determine their relative positions. It is expressed by an undirected edge similar to. The following is a description of each process.

In the constraint generation inspection target generation processing 107, in order to consider the worst case of overlapping of wirings, 1
The unit of the inspection is a set of trunk lines that can be arranged without breaking and overlapping on the track. The process of obtaining a set will be described below with reference to the flowcharts of FIGS.

First, as preprocessing, a set S0 having all nets as elements is created and the list Ln to be inspected is cleared. Further, the number n of survey targets is set to 0 (401). Here, as step 1, it is checked whether or not the element exists in S0, and if it does not exist, the process ends (402). on the other hand,
When an element exists in S0, the set S1 having the trunk line as its element is once cleared (403), and an arbitrary element N of S0 is set.
Put all the trunk lines Tij belonging to i into S1, and from S0 to Ni
Is deleted (404). Next, in step 2, the inspection target number n is incremented by 1 (405), the main line Tmin having the smallest coordinate of the left end point among the elements of S1 is added to the inspection target list Ln, and S1 to Tmin are deleted (406). ). Further, in step 3, the trunk line Tnext having the same left coordinate as the right coordinate of the last element Tlast of Ln is detected from S1 (501), and if Tnext exists, it is added to the end of Ln,
Tnext is deleted from S1 (502). This step is repeated (503) as long as Tnext can be detected. Tne
If xt cannot be detected (504), it is checked whether or not the element exists in S1, and if it exists, the process returns to step 2 (505), and if not, the process returns to step 1 (506) to continue the processing.

Next, the outline of the constraint occurrence inspection process 108 will be described with reference to FIG. For example, it is assumed here that there is a parallel wiring constraint that prohibits two wirings parallel to each other with an interval W0 from overlapping with a length exceeding L0. Here, when the allocation processing is performed without any parallel wiring constraint, the wiring 6 is obtained as a result as shown in FIG.
For 01 and 602, the wiring interval W and the overlapping length L in the horizontal direction are L> L0, W ≦ W0, and the parallel wiring constraint may be violated. In this processing, a situation in which the above result may occur is detected, and as shown in FIG. 7B, the length L that overlaps in the horizontal direction between the wirings 601 and 602 is a distance W1 (> W0) that is not affected by crosstalk. )
It gives an undirected edge with a weight of.

Further, here, considering the degree of congestion in the horizontal direction (the number of trunks passing through a column or having an end point in that column), as shown in the graph of FIG. 6 (b). Since there is a large degree of freedom in the process of allocating the main line when the congestion degree has a margin to the maximum allowable congestion degree, the parallel wiring constraint given to the whole long wiring results in the allocation of the entire channel. if,
Although the influence on the number of tracks required for allocation is small, as shown in the graph of FIG. 6C, there is a portion where the margin of the congestion degree is insufficient with respect to the maximum allowable congestion degree in the range where the two wirings overlap. In this case, even if there is no constraint between the part (601 in FIG. 6C) 602 and the part 602 where the margin is particularly insufficient, the overlapping length L1 of the wiring does not cause a parallel wiring constraint violation. In other words, L
Partial wiring having a wiring length L2 (≧ L−L0) related to a large margin such that 1 ≦ L0 (FIG. 6C).
603) is extracted and a parallel wiring constraint is given between the partial wiring and 602, so that it is possible to comply with the parallel wiring constraint without increasing the number of required tracks. In this process, partial extraction is facilitated by using a set of a plurality of trunks of the same net that can be arranged in one column as a unit to be inspected in the constraint occurrence inspection as described above.

FIG. 7 shows an example of data for expanding the above-mentioned constraint generation processing function.

First, as shown in FIG. 7A, the lengths of a plurality of parallel wirings are prepared in stages, and the distances between the wirings are given correspondingly, so that the parallel wiring constraint between the wirings can be further reduced. It is possible to increase the accuracy.

Secondly, it is conceivable that the signal passing through each wiring has a different effect on the circuit performance, particularly here on the speed, depending on the type. Therefore, in the constraint generation processing, by preparing data representing a combination of signal types of the constraint target wiring as shown in FIG. 7B, the parallel wiring constraint considering the influence on the circuit speed of the signal. It is possible to obtain the value. Furthermore, it is possible to prepare the data of FIG. 11C and combine it with the data of FIG.

Third, when there are a plurality of wiring layers, there are problems of the layers themselves, such as a difference in signal transmission speed depending on the layers.
Also, due to problems due to layer combinations such as crosstalk characteristics different between wires existing in the same layer and wires existing in different layers, it is used by itself given to the wires as shown in FIG. 7D. By combining layers with data, it is possible to obtain a parallel wiring constraint value in which the problem of crosstalk due to the difference in layers is taken into consideration. As in the case described above, the data shown in FIG. 9A can be used as a combination target here as well.

Furthermore, by using FIG. 7 (b) and FIG. 7 (d) in combination, it is possible to obtain a more detailed parallel wiring constraint that simultaneously considers the difference between the signal type and the wiring layer.

At the end of the automatic wiring process, the allocation processing unit 1
In 03, the constraint generation processing unit 102 such as the parallel wiring constraint described above.
The main line is assigned to the track while observing the various constraints generated in step 1, and the automatic wiring process ends.

[0027]

According to the present invention, the parallel wiring constraint is adapted in the automatic wiring processing to control the length of the parallel wiring, so that the delay due to the crosstalk can be kept within the range of complying with the given constraint. As a result, it is possible to reduce the number of man-hours required for manual correction, which has been related to the handling of the wiring that has caused the delay constraint violation.

[Brief description of drawings]

FIG. 1 is a flowchart of an example of an automatic wiring process to which a parallel wiring constraint process according to the present invention is applied.

FIG. 2 is an explanatory diagram of a channel allocation method.

FIG. 3 is an explanatory diagram of an example of vertical constraint / horizontal constraint and its graph representation.

FIG. 4 is a first flowchart of constraint generation inspection target generation processing.

FIG. 5 is a second flowchart of constraint generation inspection target generation processing.

FIG. 6 is an explanatory diagram showing an example of a method of giving a parallel wiring constraint.

FIG. 7 is an explanatory diagram showing an example of data expressing a parallel wiring constraint.

[Explanation of symbols]

101-108 ... Each process in the automatic wiring method considering the parallel wiring constraint.

Claims (6)

[Claims] 1. An automatic wiring method in an automatic layout system of a semiconductor integrated circuit, wherein when a path is determined in which two wirings are close to each other in the same direction (hereinafter, this state is referred to as parallel), signal interference between them is determined. A case in which the performance of the semiconductor integrated circuit may not satisfy the required standard is detected in advance due to a delay in the signal arrival time (hereinafter referred to as “delay”) (hereinafter referred to as “crosstalk”). Satisfies the circuit delay requirement at the time of design by applying a constraint (hereinafter referred to as a parallel wiring constraint) that prohibits the determination of parallel routes between the wirings to be searched and a route that complies with the constraint. An automatic wiring method characterized by: 2. A wiring is represented by a node, and an edge whose weight is a minimum distance between two wirings (hereinafter referred to as an inter-wiring distance) is shown, and a relative positional relationship of a path between the wirings (for example, The wiring A must be on the wiring B, etc.) by an automatic wiring method using a graph representation in which a directed edge is present when there is such a positional relationship, and an undirected edge when the positional relationship does not exist between them. The automatic wiring method according to claim 1, wherein the parallel wiring constraint is expressed by an undirected edge, and the wiring path is determined in compliance with the constraint expressed by the graph. 3. When generating a parallel wiring constraint, wirings (hereinafter referred to as nets) through which the same signal flows are grouped, the wiring segments have the same direction in the group, and the end points of the wiring segments have the same coordinates. The group is divided so that the set of the wiring segments that can share the same is set as the inspection target of the parallel wiring constraint occurrence, and the inspection of the presence or absence of the parallel wiring constraint occurrence between all the inspection targets is performed. The automatic wiring method according to claim 1, which is characterized in that. 4. Considering that the degree of influence of the delay on the performance of the semiconductor integrated circuit varies depending on the type of signal flowing through each wiring and the parallel wiring constraint is different, the identification data of the flowing signal is given to the wiring, 2. The automatic wiring method according to claim 1, further comprising a process of obtaining a parallel wiring constraint value used when determining a route using the data. 5. In consideration of the fact that there are a plurality of wiring layers used by the wiring, the magnitude of the wiring delay due to crosstalk is different for each layer, and the parallel wiring constraint is different, the identification data of the used wiring layer is used as the wiring. 2. The automatic wiring method according to claim 1, further comprising a process of giving the data and determining a parallel wiring constraint value used when determining a route. 6. A limit length for a plurality of parallel wirings and a distance between the wirings corresponding thereto are prepared so as to have a process of selecting an optimum parallel wiring constraint value corresponding to the parallel lengths. The automatic wiring method according to claim 1.