JP3420176B2 - Automatic placement and routing method for semiconductor devices - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for automatically arranging and wiring a semiconductor device, and more particularly to a method for automatically arranging and wiring a semiconductor device capable of automatically arranging and wiring in consideration of timing constraints.

[0002]

2. Description of the Related Art In recent LSI design technology, the influence of parasitic capacitance and resistance of wiring tends to increase as the scale of LSI increases while the miniaturization advances and the speed of elements increases. The signal delay due to wiring has become so large that it cannot be ignored. In particular, the signal delay considered in the circuit design and the wiring delay after the actual layout are inconsistent, and it is necessary to repeat the correction or manually correct the placement and wiring.

There is a method called timing driven layout as one of the methods for reflecting the wiring delay of the circuit created by circuit design and logic synthesis in the layout. In this method, a timing constraint file is created from a circuit created by logic synthesis or the like, delay information of the circuit, and a clock, and layout wiring between a flip-flop (hereinafter referred to as F / F) -F / F is performed.

The problem will be described with reference to FIGS.
FIGS. 10A and 10B are connection diagrams of elements having timing constraints, and here, a case where a flip-flop (F / F) is used as the element having timing constraints is shown. Figure 10
In (a), in order to capture the signal of the F / FA serving as the starting point element 11a into the F / FB serving as the next-stage element 12a,
The signal must arrive within one clock cycle. Therefore, after arranging F / FA and F / FB and performing wiring 14a, it is confirmed whether or not they are satisfied.

When the constraint condition is not satisfied, FIG.
A buffer element 13a for delay reduction as shown in (b) is inserted and connected to the wirings 14 and 15, or the starting point element 11
The F / FA of a is changed to an element having a large drive capacity to satisfy the constraint condition. Since this method uses the clock as a constraint, there is a problem that the timing constraint layout cannot be performed only with the combinational circuit.

Next, the flow of the prior art shown in FIG. 11 will be described. First, the netlist 101 including the connection information and the delay information 106 are created in advance. Next, the timing constraint file 102 for layout is created from the delay information 106 and the clock information / timing standard 107. Next, from the netlist 101, the timing constraint file 102, and the block library 103, the F / F that is the start point of the timing constraint circuit and the F of the end point are
Extract / F. Next, according to the netlist 101, the corresponding element is extracted from the block library 103, and the elements of the entire circuit are automatically arranged on the chip (step S4).
1).

Next, in step S42, rough wiring is performed and the delay time from the start point F / F to the end point F / F is calculated. Further, in step S43, it is confirmed whether or not the delay time satisfies the clock and the specified timing.
If the specified timing is satisfied in step S43 (Y), the process proceeds to step S48, and if the path does not satisfy the specified timing (N), whether there is an element having the same function and a large driving capability, or the library. The search is performed at 103 (step S44). In step S45, it is determined whether or not there is a corresponding element by this search. If there is the corresponding element, the (Y) element is replaced (step S46),
It returns to step S43.

If there is no corresponding element in step S45 (N), the process proceeds to step S47, a buffer for delay reduction is inserted to adjust the timing, and the process returns to step S44. For F / F between all timing constraints,
Steps S41 to S47 are carried out, and step S48
Then, the delay after placement and routing is calculated.

[0009]

However, even a circuit that requires timing constraints cannot be handled if the start point and end point are not F / F. In such a case, the timing does not converge once. For this reason, there is a work of performing redesign from the circuit design, or performing placement and routing once, and then performing modification without changing placement and routing unrelated to the signal of the circuit that does not converge. This requires a lot of man-hours for the work, which becomes a factor of extending the layout period, which is a problem.

Further, although there is a means of forced placement, since there is no placement coordinate, the placement cannot be done according to a certain rule.
Therefore, it takes a lot of time, and it is limited to arrange several hundreds of elements. In a standard LSI, 7
0% is a combinational circuit, 90% of which is between F / F-F / F, but the remaining 10% of the elements cannot be subjected to timing constraint. It is nearly impossible to force-place these elements.

The object of the present invention is to solve these problems,
Automatically place element layout with timing constraints,
An object of the present invention is to provide a method for automatically arranging and wiring a semiconductor device which enables wiring.

[0012]

SUMMARY OF THE INVENTION According to the structure of the present invention, in a semiconductor device automatic placement and routing method for implementing automatic layout with timing constraints on a semiconductor device using multi-layer wiring, the route to which the timing constraints are given is seeking only the delay value of the wiring from the delay limit value, when the equally divided delay value to wiring between the elements, placing searching element arrangeable coordinate within the range of the equally divided delay value, the delay How to divide equally
As the delay value given to the route with timing constraint
Is the sum of the delay values of each element on the route and the wiring delay between each element.
It consists of the sum of extension values, and is given to the route with this timing constraint.
From the obtained delay limit value, the delay coefficient of each element, input
The capacitance, output resistance, etc. of each element calculated from the library
Subtract the extension value and obtain only the wiring delay value of the above route.
The calculated wiring delay value is used for the wiring that connects each element, etc.
Minute, characterized in that.

[0013] Te present invention smell, a method of placing searching deployable coordinate element is a start point element automatically arranged, each element of the following stages is a base point placement coordinates of the previous stage elements, wherein It is possible to search for and place at coordinates that can be placed in an area that satisfies the wiring delay value evenly distributed to each wiring.

Further, according to the configuration of the present invention, the first step of extracting the connection information of the element and the wiring of the path having the timing constraint from the netlist and the delay value of the element on the path having the timing constraint are calculated. Extracted from the block library that describes the element name, delay coefficient, etc., subtracted from the delay limit value,
The second step of calculating only the delay value due to the wiring, the third step of equally dividing the calculated wiring delay value into the wiring connecting the elements on the path with the timing constraint, and the wiring delay value is satisfied. A fourth step of locating and arranging the coordinates capable of arranging the element in the next stage within the wiring length, and a fifth step of deciding whether or not the element has been laid out next for all paths having timing constraints, If there is a path with this timing constraint, repeat from the first step, and if there is no such path, a sixth step of arranging other elements, and a path with timing constraint after the placement of all elements is completed. It is characterized in that it includes a seventh step of wiring the element of, and an eighth step of wiring the other element.

In the present invention, when arranging the element of the next stage in the fourth step, the interval from the element of the starting point to the element of the next stage is set in units of one grid of the wiring delay value so that it overlaps with the existing element. When there is no coordinate position that is arranged without overlapping in the above-mentioned one grid unit, the coordinate position that is arranged without overlapping in the two-grid unit in which one grid unit is added is searched. The search range can be expanded sequentially by performing a search.

Further, in the present invention, when wiring the elements in the seventh step, the wiring from the starting point element to the element of the next stage is
It is possible to move by one wiring grid unit in the direction of the first axis and to search and wire those that can be wired in the direction of the second axis orthogonal to the first axis. Further, in the seventh step. , Second
When the wiring is possible in the axial direction of, the wiring can be performed by the wiring layer in which the wiring resistance of the wiring in the second axial direction and the resistance value of the contact resistance have the minimum resistance value.

[0017]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a connection diagram for explaining the concept of the present invention, and shows the arrangement of paths with timing constraints.
In this case, the wiring 14 is provided between the starting point element 11 of X and the next stage element 12 of A, and the wiring 15 is provided between the next stage element 12 and the third stage element 13 of Y, and the starting point element 11 and the third stage element 13 are connected. The timing constraint path is to the eye element 13 and its delay limit value (= tP
Ds).

As a method of equally dividing the delay according to the present invention, a delay limit value (tP) given to a path having a timing constraint is used.
Ds) subtracts the delay value of each element 11 to 13 calculated from the library of the delay coefficient, input capacitance, output resistance, etc. of the element, and obtains only the wiring delay value of that path (given to the path with timing constraint). The delay value is the sum of the delay values of the respective elements on the path and the wiring delay value between the respective elements, and the calculated wiring delay value is connected to the wirings 14 and 15 between the respective elements.
Equally (t1 = t2). Further, as a method for searching and arranging the element allocable coordinates, the starting point element 11 is automatically arranged, and the elements 12 and 13 in the subsequent stages are the elements in the preceding stage (element 11 in the case of element 12 and element 12 in the case of element 13) Using the arranged coordinates as a base point, a search is performed within an area that satisfies the wiring delay values evenly distributed to each of the above-mentioned wirings, and the coordinates are arranged at the arrangeable coordinates.

The configuration of this embodiment will be described with reference to the flow chart of FIG. As in FIG. 10 of the conventional example, the netlist 1
01 is created. This netlist 101 and a timing constraint file 102 in which timing constraint elements, connection information, and delay limit values are described are input, and from this netlist 101, elements on a path with timing constraints and wiring connection information. Is extracted (step S1).

Next, the delay value of the element on the path having the timing constraint is extracted from the block library 103 in which the element name, the delay coefficient, etc. are described, and subtracted from the delay limit value to calculate only the delay value due to the wiring ( Step S2). next,
The calculated wiring delay value is equally divided into wirings that connect the elements on the path having the timing constraint (step S3).

Further, in step S4, the next stage element is searched for and arranged within the wiring length satisfying the wiring delay value, and then in step S5, all the paths with timing constraints are placed. If it is determined whether or not the element is arranged, and if there is another path with timing constraint (N), repeat from step S1 and if not (Y)
In step S6, other elements are arranged. Then, in step S7, after the placement of all the elements is completed, the elements of the path strip with the timing constraint are wired, and finally, in step S7, the other elements are wired.

Next, the present embodiment will be described in detail with reference to the flow chart of FIG. First, as in the conventional example, the timing constraint file 102 in which timing constraint elements and connection information created at the time of circuit design are described and the delay time limit is described is read, and the timing constraint element and connection information read here are read. Based on the above, a path with timing constraints and elements on the path are extracted from the netlist 101 (step S11). The starting point element of the path having the timing constraint is automatically placed by referring to the element prepared for each process and the block library 103 containing the element delay information by the existing element placement tool.

FIGS. 4A to 6B are coordinate diagrams of element layouts for explaining this processing step. First, the starting point element 11 is automatically arranged. The output of this starting point element is shown in FIG.
As shown in (a), reference coordinates Xa, Ya serving as an origin point =
It is set to (0, 0) (step S12).

Since the delay value is the sum of the output delay value of the starting point element 11, the input delay value of the next-stage element 12 and the wiring delay value, the output delay value tld1 of the starting point element, the output resistance r1 of the starting point element, When the input capacitance Ci2 of the stage element and the wiring delay tdw are extracted from the block library 103, the delay value tpd is given by the following equation.

Tpd = tld1 + (r1 × Ci2) + tdw (1) Next, the delay time limit tPDs is extracted from the timing constraint file 102, the element delay value is subtracted, and only the wiring delay value is calculated (step S13). ). The wiring delay value calculated here is equally divided into the wirings 14 and 15 of FIG. 1 (t1 = t
2) Yes (step S14).

Parasitic capacitance Co per unit wiring length, wiring resistance Ro per unit wiring length, output delay value tl of starting point element
d1, output resistance r1 of starting element, input capacitance C of next-stage element
i2 is extracted from the block library 103. When the wiring length from the output of the starting-point element 11 to the input of the next-stage element 12 is L10, the delay limit time tPDs can be generally expressed by the following equation.

The maximum tPDs = tld1 + r1 (Co × Ll0 / 2 + Ci2) + Ro × Co × (Ll0) 2/2 ......... (2) wiring length L10 determined from the equation (2) is capable wirings of the next element 12 Wiring length.

Next, in step S15, from the starting element,
The wiring length to the next-stage element is Lln = 1. Output coordinates Xa, Ya = (0, 0) of the starting point element A (11) in FIG. 4B
To E2 (0, Lln), E3, which are surrounded by the wiring length Lln from the next-stage element B (12)
Coordinate area 1 of (-Lln, 0) and E4 (0, -Lln)
9 is searched for coordinates for each unit (hereinafter referred to as 1G [grid]) (step S16), and it is determined whether the element B can be arranged at the coordinates without overlapping the existing elements 16 and 11 (step S17).

In the case of this embodiment, the element B (12) is the same as that shown in FIG.
The coordinates E1 (Lln, 0) in (b) overlap the existing element 16, and the coordinates E2 (0, Lln), E3 in FIG.
(0, -Lln), E4 (-Lln, 0) has element A
It overlaps with (11).

Next, since there is no coordinate that can be arranged, the value of Lln is set outside 1 G (Lln = Lln +) in step S18.
The coordinate area 20 surrounded by the wiring length Lln of 1G) is changed to search the coordinate area 20 of FIG. This coordinate area 20 has coordinates F1 (Lln, 0) to F4 (-Lln, 0).
0) and the straight lines G1 to G4 connecting these lines.

Steps S16 to S18 are repeated to search the coordinate area 20 surrounded by the coordinates F1 to F4 in FIG. 5A of the disposable coordinates of the element B (12) and the straight lines G1 to G4 connecting these coordinates. In the present embodiment, FIG.
The coordinates F1 and F2 in (a) overlap with the existing element 16, but can be arranged without overlapping with other elements at the coordinate position of the straight line G2 in FIG. 5 (b). Here, the element B (12) is arranged at the arrangeable coordinates that can be searched first. The element arrangement coordinates are stored in the element arrangement information 104.

Next, in step S20, it is judged whether or not the element placement of the route having the timing constraint is completed, and if it is not finished yet (N), the output of the element B of the previously placed element is Xb in step S21. , Yb = (0,0) (element B (12) in FIG. 5B) and step S15 is repeated. The output coordinate Xb of the starting point element B (12) in FIG.
Coordinates H1 (Lln, 0), H2 surrounded by the wiring length Lln from Yb = (0,0) to the next-stage element B (13)
(0, Lln), H3 (-Lln, 0), H4 (0,-
Lln) coordinate area 21 is searched for coordinates for each grid unit, and element C (1 in FIG.
3) is arranged and the element arrangement coordinates are stored in the element arrangement information 104.

Next, at step S22, it is judged whether or not the element placement of the path having the timing constraint is completed,
When the element placement of the route with the corresponding timing constraint is completed (Y), for all the routes with the timing constraint,
Determine if placement is complete. If there is another route with timing constraint (N), the process from step S12 is repeated for the next route with timing constraint.

If it is determined in step S22 that element placement has been completed for all paths having timing constraints, step S22.
At 24, other elements are automatically arranged. Next, in step S25, the element placement coordinates of the path having the timing constraint stored in the element placement information 104 are read, and step S2
6, the wiring 17 is arranged between the elements A and B and between the elements B and C (FIG. 6B). Then, in step S27, it is determined whether or not the wiring of all the route elements having timing constraints is completed, and if this is not completed, the process is repeated from step S25. When the wiring of all the route elements having timing restrictions is completed, the wiring of other elements is performed in step S28.

According to the present embodiment, it is possible to place and route a timing-constrained route such as a combinational circuit in which a timing constraint cannot be added by a clock in consideration of the timing. Therefore, the timing constraint is applied to all logic circuits. Placement and routing can be performed in consideration, and manual correction is not required, so that timing convergence can be accelerated.

FIG. 7 is a flow chart for explaining another embodiment of the present invention. Steps S1 and S2 in the first half of this embodiment
5 is the same as FIG. 3, but FIG. 7 shows from step S24, and instead of step S26 of FIG.
31 to S34 are added.

In step S25, element placement information 1
The element arrangement coordinates of the path with timing constraints stored in 04 are read, and the output terminal coordinates on the starting point element side are set to X1, Y.
1. Input terminal coordinates on the next-stage element side are X2 and Y2. Next, in step S31, in the coordinate range of Y1 to Y2, 1G is moved in the direction of Y1 to Y2 to search for writable coordinates from X1 to X2. In step S32, it is determined whether or not wiring is possible based on the retrieved coordinates. If this is not possible (N), the process is repeated from step S31.

This state will be described with reference to the layout diagram of FIG. In this figure, elements A, B, C, D (11, 1
2, 13, 18) are arranged as shown in the drawing, and wiring is performed between these elements A and B. In this case, the wirings T1 to T6 parallel to the x-axis are on the lattice, but if these are searched in order, the first coordinate that can be wired without intersecting the elements is the wiring T3. The wiring 22 is connected to the wiring 22 that is orthogonal to the wiring 22 and is connected from the element A to the wiring 22 and from the element A to the wiring 22.

Next, in step S33, wiring impedance is calculated for all usable wiring layers based on the wiring length, the number of contacts used for wiring, and the element characteristic parameter 105.

FIGS. 9A and 9B are sectional views showing the two wiring layers and the four wiring layers used in this embodiment. FIG. 9A shows a two-layer wiring layer, in which elements 31 and 32 are provided on a substrate 30, and an insulating layer on these elements 31 and 32 is provided with a contact 33 to the first layer of wiring in the X direction. The first wiring layer 34, and the second wiring layer 35 in the Y direction in the Y direction via the contact 33 to the insulating layer on the first wiring layer 34.
Are provided, and these wiring layers 34 and 35 are wired orthogonally.

Further, FIG. 9B shows a wiring layer of four layers, and further a third layer in the X direction via a contact 33 to the insulating layer on the second wiring layer 35 of the second layer of FIG. 9A. The third wiring layer 36,
A fourth wiring layer 37, which is the fourth layer in the Y direction, is provided on the insulating layer on the third wiring layer 36 via the contact 33, and the wiring layers 36 and 37 are wired orthogonally.

In this case, the wiring lengths in FIGS. 9A and 9B are almost the same, and the number of contacts 33 is 8 in FIG. 9B.
9 pieces, and FIG. 9 (a) is 4 pieces. The impedance of this wiring layer is smaller in the four-layer impedance than in the two-layer impedance, and the contact resistance is larger in the case of wiring in four layers than in the case of wiring in two layers.

Next, in step S34, wiring is performed using a wiring layer that can be wired with a minimum impedance (resistance value).
In this case, if the difference in wiring resistance is smaller than the difference in contact resistance, wiring is performed in the two wiring layers (35). If the wiring resistance difference exceeds the contact resistance difference,
Wiring is performed in the four wiring layers (37).

Finally, as in FIG. 3, in step S27,
It is judged whether or not the wiring of all the route elements having timing constraints is completed, and if this is not completed, step S2
When the wiring of all the route elements having timing restrictions is repeated from step 5, wiring of other elements is performed in step S28.

[0045]

As described above, according to the configuration of the present invention, it is possible to place and route a timing-considered route for a route having a timing constraint such as a combinational circuit in which a timing constraint cannot be added by a clock. Placement and routing can be executed for the logic circuit in consideration of timing constraints, and there is no need for manual correction, which has the effect of accelerating timing convergence.

Further, by carrying out the wiring in the wiring layer having a low impedance, it is possible to reduce the influence of the parasitic resistance and the parasitic capacitance, and it is possible to apply it to a high speed operation circuit in the future.

[Brief description of drawings]

FIG. 1 is a connection diagram illustrating an arrangement method according to an embodiment of the present invention.

FIG. 2 is a schematic flow diagram illustrating a processing method of the embodiment of FIG.

FIG. 3 is a flowchart illustrating a processing method according to the exemplary embodiment of FIG.

4A to 4C are coordinate diagrams illustrating the layout of the embodiment of FIG.

5A and 5B are coordinate diagrams for explaining the continuation of the layout of FIG.

6A and 6B are coordinate diagrams for explaining the continuation of the layout of FIG.

FIG. 7 is a flowchart illustrating an element wiring method according to a second embodiment of the present invention.

FIG. 8 is a layout diagram illustrating the element wiring method of the embodiment of FIG.

9 (a) and 9 (b) are cross-sectional views illustrating a four-layer, two-layer element arrangement structure of the embodiment of FIG.

10A and 10B are connection diagrams for explaining a conventional element arrangement method.

FIG. 11 is a flowchart illustrating the element arrangement method of FIG.

[Explanation of symbols]

11 Start point element X (A) 11a, 12a Flip-flops 12, 13, 18 Element after the next stage 13a Delay relaxation buffer 14, 14a, 15, 15a, 17, 22, 23 Wiring 16 Existing element 19, 20, 21 Coordinate area 30 substrate 31, 32 element 33 contact 34 first wiring layer 35 second wiring layer 36 third wiring layer 37 fourth wiring layer 101 netlist 102 timing constraint file 103 block library 104 element placement information 105 element characteristic parameter 106 delay information file 107 Timing Standard File S1 to S49 Processing Step

Continuation of the front page (56) Reference JP-A-4-23347 (JP, A) JP-A-8-306866 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) H01L 21 / 82 G06F 17/50 H01L 21/822 H01L 27/04

Claims (6)

(57) [Claims] 1. An automatic placement and routing method for a semiconductor device, which automatically lays out wiring having timing constraints in a semiconductor device using multi-layer wiring, wherein only the delay value of the wiring is determined from the delay limit value of the route to which the timing constraint is given. Then, the delay value is equally divided into the wirings between the respective elements , and when searching and arranging the element arrangeable coordinates within the range of the equally divided delay value ,
As a method to divide the delay of
The delay value given to the path is the sum of the delay values of each element on the path.
And the sum of wiring delay values between each element.
From the delay limit value given to the route with
Library for delay coefficient, input capacitance, output resistance, etc.
The delay value of each element calculated by
Only the delay value is calculated, and the calculated wiring delay value is calculated for each element.
A method for automatically arranging and wiring a semiconductor device, which is characterized by equally dividing wirings that connect between them . 2. A method for retrieving and arranging coordinates in which elements can be arranged is to automatically arrange a starting-point element, and each element in the next and subsequent stages is based on the coordinate in which the element in the preceding stage is arranged as a base point and is evenly distributed in each wiring. 2. The automatic placement and routing method for a semiconductor device according to claim 1 , wherein the area is searched and placed in a coordinate that can be placed in a region that satisfies the wiring delay value distributed to. 3. A first step of extracting connection information of an element and a wiring of a path having a timing constraint from the netlist, and a delay value of an element on the path having the timing constraint, an element name, a delay coefficient, etc. From the block library described above, subtracting from the delay limit value, and calculating only the delay value due to the wiring, and the calculated wiring delay value to the wiring that connects the elements on the path with the timing constraint. A third step of equally dividing, a fourth step of searching for and arranging coordinates capable of arranging an element of the next stage within a wiring length satisfying the wiring delay value, and then all paths with timing constraints 5th step of determining whether or not the element has been arranged, and if there is a path with this timing constraint, repeat from the 1st step, and if there is no such path, another element is arranged. The automatic placement and routing method for a semiconductor device, which includes the step of (4), a seventh step of wiring elements on a path having a timing constraint after completion of placement of all elements, and an eighth step of wiring other elements. 4. When arranging the next stage element in the fourth step,
The distance from the starting point element to the element at the next stage is set in the unit of one grid of the wiring delay value to search the coordinate position where it is arranged without overlapping with the existing element, and it is arranged without overlapping in the unit of one grid. 4. The automatic arrangement of a semiconductor device according to claim 3 , wherein when there is no coordinate position to be set, the search range is sequentially expanded by searching for coordinate positions which are arranged without overlapping in units of two grids obtained by adding one grid unit. Wiring method. 5. When wiring an element in the seventh step, the wiring from the starting point element to the element at the next stage is moved by one wiring grid unit in the first axis direction and is orthogonal to the first axis. claim wired searching for capable straight line in a second axial 3
A method for automatically arranging and wiring a semiconductor device as described. 6. In the seventh step, when wiring is possible in the second axial direction, wiring is performed by a wiring layer in which the wiring resistance of the wiring in the second axial direction and the contact resistance have the minimum resistance value. The automatic placement and routing method for a semiconductor device according to claim 5, which is performed.