JPH11161694A - Wiring path searching method for automatic wiring design and storage medium stored with wiring path searching program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a wiring path searching method which meets height restriction, etc., in a wring area. SOLUTION: In an input processing S1, height restriction and connection information in a wiring area is inputted. In a searchable grid extracting processing S2, a grid which can be searched for at present is extracted. In a grid array margin calculating processing S3, degree of grid array margin defined by a value obtained by subtracting from the restriction the height of a wiring inhibited are of the grid array and the height of the area that wires already allocated to the grid array occupy is calculated. When advancing to the above searchable grid, a grid array passing cost is set in a grid array passing cost addition processing S4 on the basis of the grid array margin degree that the searchable grid belongs to and added to a wiring path cost. In a target arrival decision processing S5, a return to the searchable grid extracting processing S2 is made when a target is not reached, but when the target is reached, a minimum-cost wiring path is extracted by tracing in a cost minimum path selecting processing S6.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to an improvement in a wiring route search method used for automatic wiring design of LSIs and the like.
More specifically, this is a wiring route search method using a maze method in a wiring area divided into grids, and in particular, when a height constraint or a lateral width constraint of a wiring area is given, regardless of the number of grids in the wiring area, The present invention relates to a wiring route search method that can satisfy a restriction on a width.

[0002]

2. Description of the Related Art Conventionally, there is a maze search method as a wiring route search method. As a conventional example of this maze search method, 1974
IEEE Transactions on Computers, vol c-23, no.9
"The Lee Path Conn, presented by Frank Rubin
Section Algorithm ". A processing procedure of a conventional wiring route searching method using this maze searching method will be described with reference to a flowchart shown in FIG.

The input processing S10 is processing for inputting connection information. The searchable grid extraction process S20 is a process of extracting a searchable grid at the current time. A searchable grid adjacent to the grid in the list L, that is, a grid that can be wired, such as a grid set as a wiring prohibited area or a grid where terminals are located, is put in the list L1. At the same time, the search direction from the grid in the list L to the searchable grid is stored. The grid in the list L1 is extracted as a searchable grid.

The wire length cost adding process S40 is a process of adding a wire length cost when a search is performed on the searchable grid extracted in the searchable grid extracting process S20.
Each time one grid is advanced, the wiring length cost of “1” is added. Next, a process of inserting a lattice having the minimum cost from the lattices in the list L1 into the list L is performed.

[0005] The target arrival determination processing S50 proceeds to the next processing when the target is reached, and returns to the searchable lattice extraction processing S20 when the target is not reached. If the grid in the list L includes the grid of the target,
The process proceeds to the next minimum cost route selection processing S60. List L
If the target grid is not included in the middle grid, the process returns to the searchable grid extraction processing S20.

The minimum cost route selection process S60 is a process of extracting the minimum cost wiring route by tracing. By tracing using the search direction stored in the searchable grid extraction process S20, a wiring route with the minimum cost is extracted.

A specific description will be given with reference to FIG. For simplicity, the number of wiring layers is one. The wiring area 20 has a large number of grids 30
And the terminals 10A, 10a, 10B, 10b,
10C and 10c and the wiring prohibited area 21 exist.

In input processing S10, connection information is input. The numbers in the terminals 10A, 10a, 10B, 10b, 10C, and 10c indicate net numbers, and it is necessary to connect terminals having the same net number.

The case of wiring the net 1 will be described. The terminal 10A is a starting point, and the terminal 10a is an ending point. In searchable lattice extraction processing S20, first, list L
Insert the grid where 0A is placed. Then, a searchable grid adjacent to the starting point 10A is entered in the list L1. Four grids adjacent to the starting point 10A in the vertical and horizontal directions are entered in the list L1.
At the same time, the search direction indicated by the arrow in FIG. 16 is stored. The four grids in the list L1 are extracted as searchable grids.

In the wiring length cost adding process S40, a wiring length cost of "1" is added each time the grid is advanced.

Next, a lattice having the minimum cost is inserted into the list L from the lattices in the list L1. Current list L1
Since the costs of all the four grids in the list are "1", the four grids in the list L1 are inserted into the list L.

Next, in the target arrival determination processing S50, it is determined that the target which is the end point grid 10a has not been reached, and the process returns to the searchable lattice extraction processing S20. The processing from the searchable grid extraction processing S20 to the target arrival determination processing S50 is repeated until the search reaches the end point grid 10a.

In FIG. 16, the numbers in each grid indicate the result of adding the wiring length cost.

If the end point grid 10a is included in the list L in the target arrival determination processing S50 during the repetition of the above processing, in the subsequent minimum cost path selection processing S60, the search direction in FIG. By tracing the arrow indicating, the wiring path 40 with the minimum cost is extracted.

FIG. 17A shows the wiring result. FIG.
FIG. 3A shows the result of compaction in the downward direction. Due to the compaction, not only the wiring but also the terminal and the wiring prohibited area can be moved downward if there is a free area, so that the terminals 10A and 10c are each moved downward.

[0016]

In the conventional wiring route searching method, when wiring is performed in a wiring area divided into grids, if the number of grids is insufficient, the existing wiring hinders the wiring, and in some cases, wiring cannot be performed. , To complete the wiring, add a grid from the beginning or if the wiring is not completed,
It is necessary to have a sufficient number of grids.

However, if a height constraint or a width constraint is imposed on the wiring area, later insertion of a lattice causes a constraint violation. This will be described with reference to FIGS. 18 to 20 by taking an example of wiring design relating to a standard cell used for designing an ASIC.

In FIG. 18 to FIG. 20, a standard cell 100 is usually given a height constraint 101. In the cell 100, there are transistors 50A and 50B, a terminal 10, and a power supply wiring 60. For simplicity, only the first wiring layer (first metal wiring layer in the case of a standard cell) 71 is shown for wiring.

FIG. 18 shows the grid spacing 32 uniformly divided by the wiring pitch of the first wiring layer 71. If maze wiring is completed on a grid having a uniform wiring pitch, the cell height constraint can be satisfied naturally. That is, in order to complete the wiring, it is necessary to previously provide an interval between the transistor 50A and the transistor 50B in accordance with the wiring passing therethrough.

However, it is very difficult to accurately estimate the distance before wiring. In fact, in manual wiring design, trial and error of adjusting the transistor interval while performing wiring is performed.

For example, as shown in FIG. 19, as a result of the estimation before wiring, if the distance between the transistor 50A and the transistor 50B is estimated to be small, a wiring failure due to an insufficient number of grids (wiring cannot be completed) is caused. It can be seen that the connection between the terminal 10A and the terminal 10B cannot be wired due to the insufficient number of grids.

In order to solve this problem, conventionally, as shown in FIG. 20, a lattice having a spacing smaller than the wiring pitch between transistors 50A and 50B, that is, a lattice having a spacing 32B smaller than a regular spacing 32A, is provided. To complete the wiring.
Thereafter, the spacing between the transistors and the spacing between the wirings are corrected by compaction, and the same result as in FIG. 18 is obtained.

However, as shown in FIG. 20, since the number of grids in the height direction increases as a result of the insertion of the grids with a narrow interval 32B, the conventional wiring route searching method of inserting a grid requires the height of the cell 100. A problem that the constraint cannot be satisfied. The case where the height constraint is not satisfied has been described above, but the same applies to the case where the width constraint is given.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problem, and an object of the present invention is to provide a wiring region having a height constraint and a width constraint, regardless of the number of grids in the wiring region. An object of the present invention is to provide a wiring route search method that can satisfy the constraint.

[0025]

In order to achieve the above-mentioned object, according to the present invention, as a cost in a maze method, a wiring margin of a grid column with a height constraint or a grid row with a width constraint is used. Is set, and this passing cost is added to the wiring route cost.

That is, in the wiring route search method in the automatic wiring design according to the first aspect of the present invention, in the automatic wiring design of the LSI, the cost is added every time the process proceeds to each grid in the wiring area divided into a plurality of grids. A wiring route searching method for searching for a wiring route by using a maze method for calculating a wiring route cost, comprising: an input process for inputting at least one of a height constraint and a lateral width constraint of the wiring region and connection information; When performing wiring based on the information, for each grid column with a height constraint or each grid row with a horizontal width constraint in the wiring area, a margin calculation process of calculating a margin according to the number of grids that can be wired, When searching for a route of the wiring, if this route proceeds to each grid column or each grid row, a passing cost is set based on the margin calculated for the grid column or grid row to be advanced. Characterized in that it comprises a passage cost addition process of adding the cost to the wiring route cost.

According to a second aspect of the present invention, in the wiring route searching method in the automatic wiring design according to the first aspect, the margin calculation processing is performed based on a height constraint or a width constraint of the wiring region, based on a grid row or a grid. The margin is calculated by subtracting the height or the width of the wiring prohibited area in the row and the height or the width of the area occupied by the wiring already allocated to the grid column or the grid row.

According to a third aspect of the present invention, there is provided the wiring route searching method in the automatic wiring design according to the first or second aspect, further comprising a minimum cost route selecting process for extracting a wiring route having a minimum wiring route cost. And

According to a fourth aspect of the present invention, in the wiring route searching method in the automatic wiring design according to the first or second aspect, the passing cost adding process includes the following in addition to the margin:
The transit cost is set based on a penalty for a height or width constraint violation.

According to a fifth aspect of the present invention, in the wiring route searching method in the automatic wiring design according to the fourth aspect, after the search for all the wirings is completed, the height constraint or the width constraint of the wiring area is not satisfied. And a penalty change process for changing a penalty for violating the height or width constraint each time the search for the wiring is repeated, and further separately each time the search for the wiring is repeated.

According to a sixth aspect of the present invention, in the wiring route searching method in the automatic wiring design according to the fifth aspect, the penalty changing process gradually changes the penalty from a small value to a large value. .

The recording medium storing the wiring route search program in the automatic wiring design according to the invention of claim 7 proceeds to each grid in a wiring area divided into a plurality of grids at the time of automatic wiring design of an LSI by a computer. A recording medium on which a wiring route search program for searching for a wiring route is recorded by using a maze method of calculating a wiring route cost by adding a cost for each of the wiring routes, wherein at least one of a height constraint and a width constraint of the wiring region is provided. And when wiring information is input and wiring is performed based on the wiring information, a margin corresponding to the number of grids that can be wired for each grid column having a height constraint or each grid row having a horizontal width constraint in the wiring area. Is calculated, and when searching for the route of the wiring, if this route proceeds to each grid column or each grid row, it is calculated based on the margin calculated for the proceeding grid column or grid row. Set the Ku passing cost, characterized by adding the passing cost wiring route cost.

According to an eighth aspect of the present invention, in the recording medium storing the wiring route search program in the automatic wiring design according to the seventh aspect, when calculating the margin, the height constraint or the lateral width constraint of the wiring area is used. Calculating the margin by subtracting the height or the width of the wiring prohibited area in the grid column or the grid row and the height or the width of the area occupied by the wiring already allocated to the grid column or the grid row. Features.

According to a ninth aspect of the present invention, in the recording medium storing the wiring route search program in the automatic wiring design according to the seventh or eighth aspect, after calculating a wiring route cost from a terminal at a start point to a terminal at an end point. And extracting a wiring route with the minimum wiring route cost.

According to a tenth aspect of the present invention, there is provided a recording medium in which the wiring route search program in the automatic wiring design according to the seventh or eighth aspect is recorded, wherein the passing cost is added to the margin, and the height or width is further increased. Is set based on the penalty for the constraint violation.

According to an eleventh aspect of the present invention, in the recording medium storing the wiring route search program in the automatic wiring design according to the ninth aspect, after the search for all the wirings is completed, the height constraint or the width of the wiring area is reduced. When the constraint is not satisfied, the search for the wiring is repeated, and every time the search for the wiring is repeated, the penalty for the violation of the height or width constraint is changed from a small value to a large value.

With the above arrangement, according to the first to eleventh aspects of the present invention, there is a small margin and a high passing cost in a wiring route that may cause a height constraint violation or a width constraint violation in the wiring region. Value, and the wiring route cost also increases. On the other hand, in a wiring route that is unlikely to cause a constraint violation, the margin is large, the passing cost is low, and the wiring route cost is low. Therefore, if a wiring route with a low wiring route cost is selected, the height constraint or the width constraint of the wiring region can be satisfied regardless of the number of grids in the wiring region.

In particular, in the inventions according to the fourth, fifth, tenth and eleventh aspects, after the search for all the wirings is completed, if there is a violation of the height constraint or the width constraint of the wiring area, the height constraint or the width constraint is violated. While gradually increasing the penalty for violations,
Since the search for the wiring is repeated until the above constraint is satisfied, the path of the wiring having the largest wiring path cost among all the wirings can be changed to another path having the smaller wiring path cost. Therefore, the height constraint or the width constraint of the wiring region can be satisfied almost without depending on the wiring order.

[0039]

Embodiments of the present invention will be described below with reference to the drawings.

(First Embodiment) FIG. 1 is a flowchart showing a processing procedure of a wiring route searching method according to a first embodiment of the present invention. The wiring path search program, which is this flowchart, is recorded on a computer-readable recording medium, and is used by the computer to design an LSI or the like.

The input processing S1 is an input processing for inputting the height constraint of the wiring area and the connection information. These height restrictions and connection information will be specifically described with reference to FIG.

In FIG. 2, the wiring area 20 has a large number of grids 30.
And the terminals 10A, 10a, 10B, 10b,
10C and 10c and the wiring prohibited area 21 exist. The height “4” (the number of lattices is “4”) is given as the height constraint 101 of the wiring region. There are two wiring layers, a first wiring layer and a second wiring layer.

FIG. 2 shows a wiring region of the first wiring layer. The numbers in the terminals 10A, 10a, 10B, 10b, 10C, and 10c indicate net numbers, and it is necessary to connect terminals having the same net number. In the figure, it is assumed that the wiring of the net 2 and the net 3 has already been completed, and the case where the wiring of the net 1 is performed will be described. Starting from terminal 10A, terminal 1
0a is the end point.

The searchable grid extraction processing S2 is performed in the same manner as the searchable grid extraction processing S20 of the conventional method.

The lattice column margin calculation processing (margin calculation processing) S3 in FIG. 1 will be described with reference to FIG.

The lattice column margin is defined by the following equation (1).

(Grating column margin) = (height restriction of wiring area) − (height of wiring prohibited area) − (height of area occupied by wiring) --- (Equation 1) In FIG. In the wiring region 20 of the wiring layer, a grid column margin regarding the net 1 of the grid columns having grid column numbers 5, 6, and 10 is calculated.

In the grid row of grid row number 5, there is a terminal 10C of the net 3. The size of the terminal is “1”. Since the terminal 10C of the net 3 is a wiring prohibition area for the net 1, the lattice column margin is "3" (= 4-1-0).

The height of the grid row of grid row number 6 is “2”.
The terminal 10B of the net 2 and the horizontal wiring of the net 3 exist. It is assumed that the size of the terminal and the height of the area occupied by one wiring are each “1”. Since the terminal 10B of the net 2 is a wiring-prohibited area for the net 1, the lattice column margin is “0” (= 4-3-1).

In the grid row of grid row number 10, the vertical wiring of the terminal 10a of the net 1, the terminal 10b of the net 2 and the net 2 exists. The terminal 10a of the net 1 does not become a wiring prohibited area for the net 1. Terminal 10b of net 2 is net 1
Is a wiring prohibited area, and the size of the terminal is “1”. Since the length of the vertical wiring of the net 2 is “2”,
The lattice row margin is “1” (= 4-1-2).

FIG. 2 shows the lattice row margins of the lattice row numbers 1 to 11 obtained in the same manner. The lattice column margin in the second wiring layer can be calculated similarly. Since there are no terminals and no wiring prohibited areas in the second wiring layer, the lattice column margin is “4” in all lattice columns.

When the search is advanced to the searchable grid obtained in the searchable grid extraction processing S2, the grid row passing cost addition processing (passing cost addition processing) S4 of FIG. The grid row passing cost based on the grid row margin calculated in the row margin calculation processing S3 is added.

The grid row passing cost when passing through a grid row whose grid row margin is S is defined by the following equation (2).

Lattice column passing cost = 100 (when S <= 0) Lattice column passing cost = 0, (when S> 0) --- (Equation 2) where: The passing cost may be a high value so that another wiring route is selected.
It is not limited to 0 ".

The target arrival determination processing S5 and the minimum cost path selection processing S6 are the same as the target arrival determination processing S50 and the minimum cost path selection processing S60 of the conventional method, respectively.

The processing from the searchable grid extraction processing S2 to the target arrival determination processing S5 is repeated until the end point grid 10a is reached.

FIGS. 3A and 3B show the result of the wiring route search for the net 1. FIG. The value in each grid indicates the result of adding the wiring length cost and the contact cost in the first term, and the second term
The term indicates the grid row passing cost. For example, the notation “4” in FIG.
In “+100” and “15 + 100”, “4” and “15” indicate the cost addition result of the first term, and “100” indicates the grid row passing cost. Shows only the first term.
In FIGS. 7A and 7B, a to k and A to E are codes indicating horizontal and vertical coordinates.

The wiring length cost is as described in the prior art. The contact cost is also a commonly used cost, and is described in the literature cited in the related art. The cost “5” is added every time one contact is generated.

The search results of FIGS. 3A and 3B will be specifically described. For example, when the net 1 is wired as shown in FIG. 4A, the wiring cost is "117", and the net cost is "117". In the case where 1 is wired as shown in FIG. 4B, the wiring cost is "17".
Becomes This difference in cost is due to the fact that the grid at the coordinates (g, A) belonging to the grid row number “7” in the first wiring layer is given a grid row passing cost “100” (see FIG. 2). This is because the contacts are arranged on the grid of the coordinates (g, A) in the wiring route of FIG. 2A, whereas no contacts are arranged on the grid of the wiring route of FIG.

Next, when the vehicle arrives at the terminal terminal 10a, in the minimum route selection process S6, the search direction in FIGS. 3A and 3B is traced from the terminal terminal 10a to extract the wiring route 40 with the minimum cost. Is done. The search direction is indicated by an arrow or a circle. A circle without an oblique line inside indicates a search direction from the first wiring layer 71 to the second wiring layer 72, and a circle with an oblique line inside indicates a reverse search direction.

FIG. 5A shows the result of wiring. The wiring path 40 with the minimum wiring path cost of the net 1 is transferred from the first wiring layer 71 to the second wiring layer 72 via the contact 80A, and further from the second wiring layer 72 to the first wiring layer via the contact 80B. It becomes a route to change to.

FIG. 5B shows the result of compacting FIG. 5A downward. It can be seen that the height constraint 101 is satisfied.

(Second Embodiment) FIG. 6 shows a second embodiment of the present invention.
10 is a flowchart showing a processing procedure of the wiring route searching method according to the embodiment. The wiring path search program, which is this flowchart, is recorded on a computer-readable recording medium, and is used by the computer to design an LSI or the like.

In FIG. 6, an initialization process S100 initializes a penalty (cost when passing through a congested area) p for a height constraint violation used in a wiring route search process S300 described later, and an end determination process described later. A predetermined value of the height constraint violation number used in S400 is initialized to “0”.

The penalty change process S200 in FIG. 6 changes the penalty p for the height constraint violation. This change is performed so as to increase the penalty p as the number of repetitions of the penalty change processing S200 to the end determination processing S400 increases. That is, at the beginning of the repetition, the penalty p for the height constraint violation is reduced, and as the number of repetitions increases, the penalty p for the height constraint violation is increased.

In FIG. 6, next, a wiring route search S300 is performed for all nets. The processing flow of the wiring route search processing S300 is the same as the flow chart of FIG.

The grid row passing cost adding process S4 in FIG.
, The lattice row passing cost when passing through a lattice row whose lattice row margin is S is defined by the following equation 3 using a penalty p.

Grid row passing cost = p (when S <= 0) Grid row passing cost = 0 (when S> 0) --- (Equation 3) The end determination processing S400 of FIG. It is determined whether or not the number of height constraint violations in the grid row is equal to or less than a predetermined value, and if it is equal to or less than the predetermined value, the wiring process is ended. If the number exceeds the predetermined value, the process returns to the penalty change process S200. . In the initialization process S100, the predetermined value of the number of height constraint violations is set to “0”, so that the penalty change process S200 to the end determination process
Repeat up to S400.

In the following description, the wiring route cost is calculated by the following equation (4).
As shown in (2), the calculation is performed based on the wiring length, the number of contacts, and the cost of passing through the grid array.

(Wiring path cost) = a × (wiring length) + b × (number of contacts) + p × (number of times of passing through the grid row without grid row margin) a and b are parameters --- (Equation 4) Next, before describing a specific example of the present embodiment, a problem when the penalty p is fixed to a large value will be described with reference to FIGS.

FIGS. 7 to 9 show the case where the nets 1 to 4 are wired under the height constraint 101 of two wires (two grids) in each layer using the first wiring layer and the second wiring layer. Indicate the problem. The terminal and wiring prohibited area 21 is assumed to be in the first layer.

In the above equation (4), when the first wiring layer is used, a =
1. In the case of the second wiring layer, a = 2, b = 5, and the penalty p is fixed to a value p = 100 which is larger than the parameters a and b.

FIG. 7 shows net 1 → net 2 → net 3 →
The result of wiring in the order of the net 4 is shown. The wiring route cost of each net is as follows.

Net 1, Net 2, Net 3: 1 × 4 (first layer wiring length) = 4 Net 4: 2 × 10 (second layer wiring length) + 5 × 2 (number of contacts) = 30 The sum of the net wiring route costs is 42.

FIG. 8 shows net 1 → net 4 → net 2 →
The result of wiring in the order of the net 3 is shown. The wiring route cost of each net is as follows.

Net 1: 1 × 4 (first layer wiring length) = 4 Net 2, Net 3: 2 × 2 (second layer wiring length) + 5 × 2 (number of contacts) = 14 Net 4: 1 × 8 (1st layer wiring length) + 2 × 4 (2nd layer wiring length)
+ 5 × 2 (the number of contacts) = 26 Therefore, the total sum of the wiring route costs of all nets = 58.

FIG. 9 shows net 4 → net 1 → net 2 →
The result of wiring in the order of the net 3 is shown. The wiring route cost of each net is as follows.

Net 1, Net 2, Net 3: 2 × 2 (second layer wiring length) + 5 × 2 (number of contacts) = 14 Net 4: 1 × 12 (first layer wiring length) = 12 The sum of net wiring route costs = 54.

Although FIGS. 7 to 9 all satisfy the height constraint, the case of FIG. 7 in which the total sum of the wiring route costs of all the nets is the minimum is compared with FIGS. 8 and 9. The best. As described above, when the penalty p is fixed to a large value, the wiring result largely depends on the wiring order of the nets, and there is a problem that the cost of the wiring as a whole is not always the minimum.

Next, a specific example of the present embodiment will be described with reference to FIGS.

First, in the initialization processing S100, the initial value of the penalty p used in the lattice row passing cost addition processing S4 in the wiring path search processing S300 is set to "0". The predetermined value of the height constraint violation number used in the end determination processing S400 is set to “0”.

The wiring order is changed from net 4 → net 1 → net 2
→ The order of net 3 is assumed. In Equation 4, a = 1 for the first wiring layer, a = 2 for the second wiring layer, and b = 5. In the following description, the number of repetitions refers to the number in FIG.
From the penalty change process S200 to the end determination process S400.

FIG. 10 shows a case where the number of repetitions = 1. The penalty p is set to p = 0 with the initial value. In this case, the equation 4 is as follows: (wiring path cost) = 1 × (wiring length) + 5 × (number of contacts) --- (equation 4a), and the wiring path cost of each net is net 1, net 2, Net 3: 1 × 4 (first-layer wiring length) = 4 Net 4: 1 × 12 (first-layer wiring length) = 12 A wiring path is obtained. In this case, the penalty p
Since = 0, the wiring result does not satisfy the height constraint. In FIG. 10, that the margin is a negative value (−1) means that the height constraint is not satisfied.

FIG. 11 shows a case where the number of repetitions = 2. In the penalty change processing S200, the penalty is changed to p = 1. In this case, the above equation 4 is obtained by (wiring path cost) = 1 ×
(Wiring length) + 5 × (the number of contacts) + 1 × (the number of times of passing through the grid row without grid row margin) --- (Formula 4b). The net 4, the net 1, the net 2, and the net 3 have the number of times of passing through the grid row without the grid row margin being “9”, “3”, “3”, and “3”, respectively. As the cost of contact generation is higher, no route change occurs, and FIG.
The result is the same as 0. The wiring route cost of each net is as follows.

Net 1, Net 2, Net 3: 1 × 4 (First layer wiring length + 1 × 3
(Number of times of grid line passage without grid line margin)) = 7 Net 4: 1 × 12 (1st layer wiring length) + 1 × 9 (Number of times of grid line passage without grid line margin)) = 21 , The number of repetitions = 3, and the penalty is changed to p = 3 in the penalty change processing S200. Regarding the net 4, the wiring route cost of the same route as in FIG. 10 is as follows: net 4: 1 × 12 (first layer wiring length) + 3 × 9 (the number of times of passing through the grid row without the grid row margin) = 39 As shown in FIG. 12, the two contacts and the second
Since the cost of the wiring route using the wiring layer and the net 4: 2 × 10 (first layer wiring length) + 5 × 2 (the number of passes through the grid row without the grid row margin) = 30 is smaller, FIG. Is changed. The wiring route cost of Net 1, Net 2, and Net 3 is Net 1, Net 2, Net 3: 1 × 4 (first layer wiring length) = 4, which is the same minimum cost as the route shown in FIG. , The route is not changed.

The number of height constraint violations becomes "0" by the above repetition, and the process is terminated.

As described above, when the re-routing is repeated while the penalty p is gradually increased without changing the net wiring order (see FIG. 13), the cost and the contact when passing through the congested area are generated. In consideration of both costs, it is possible to find a wiring route that minimizes the wiring route cost as a whole wiring, and all the wirings are completed with a small value of the penalty p. The smaller the penalty p, the better the result of wiring independent of the wiring order of the nets. In the present embodiment, it is possible to obtain a wiring result that minimizes the total number of contacts and satisfies the height constraint without depending on the wiring order.

The change of the penalty p for the violation of the height constraint is not limited to the example shown in the present embodiment. In addition, for example, as shown in the following equation 5, the penalty change processing is performed.
It is also possible to increase from S200 in proportion to the repetition number i of the end determination processing S400.

Penalty p = (1−exp (i)) × 100 (Equation 5) FIG. 14 is a diagram showing Equation 5 in a graph.

Further, in this embodiment, the penalty p is gradually changed from a small value to a large value. Conversely, the penalty p may be gradually changed from a large value to a small value.

Further, in the present embodiment, the wiring route search processing S300 is repeated for all nets. However, only the net that causes a height constraint violation is selected and the wiring path search processing is performed. Can obtain the same result.

Further, in the first and second embodiments, the height constraint in the vertical direction is given. However, even when the constraint on the horizontal width is given, the margin of the grid rows in the horizontal direction is obtained. Thereby, the width constraint can be satisfied, and the present invention includes this case.

[0093]

As described above, according to the first to eleventh aspects of the present invention, a wiring path that may cause a height constraint violation or a lateral constraint violation of a wiring region is
Since the wiring cost can be increased by setting the passing cost to a high value according to the small margin, it is possible to select another wiring route that has a low wiring route cost and does not easily cause a constraint violation.
There is an effect that the height constraint or the width constraint of the wiring region can be satisfied regardless of the number of grids in the wiring region.

In particular, according to the inventions set forth in claims 4, 5, 10, and 11, after the search for all the wirings is completed, if there is a violation of the height constraint or the width constraint of the wiring region, the height constraint or the width constraint is violated. The search for the wiring is repeated until the constraint is satisfied while sequentially increasing the penalty for violation of the width constraint, so that the route of the wire having the largest wire route cost among all the wires has another smaller wire route cost. You can change to a route. Therefore, there is an effect that the height constraint or the width constraint of the wiring region can be satisfied almost without depending on the wiring order.

[Brief description of the drawings]

FIG. 1 is a flowchart illustrating a processing procedure of a wiring route searching method according to a first embodiment of the present invention.

FIG. 2 is an explanatory diagram of a calculation method of a grid column margin in the wiring route search method according to the embodiment;

FIG. 3A is a diagram showing a result of a wiring route search on a first wiring layer of a predetermined net in the wiring route searching method according to the embodiment, and FIG. 3B is a diagram showing a result of a wiring route search on a second wiring layer of the same net; FIG. 14 is a diagram illustrating a wiring route search result.

FIG. 4A is a diagram showing a specific example in which a wiring route of the net 1 is specified using the wiring route search results of FIGS. 3A and 3B;
(b) is a diagram showing a specific example in which the wiring route of the same net 1 is specified in another way.

FIG. 5A is a diagram illustrating a wiring result of the wiring route searching method according to the embodiment, and FIG. 5B is a diagram illustrating a result of compacting the result.

FIG. 6 is a flowchart illustrating a processing procedure of a wiring route searching method according to the second embodiment of this invention.

FIG. 7 is a diagram illustrating a problem when a penalty for violation of a height constraint is fixed, and is a diagram illustrating a result of performing wiring in the order of net 1, net 2, net 3, and net 4.

FIG. 8 is a diagram for explaining the same problem, showing a result of performing wiring in the order of net 1 → net 4 → net 2 → net 3;

FIG. 9 is a diagram for explaining the same problem, showing a result of performing wiring in the order of net 4 → net 1 → net 2 → net 3;

FIG. 10 is a diagram showing the progress of processing when the number of processing repetitions = 1 in the wiring route searching method according to the second embodiment of the present invention.

FIG. 11 shows a wiring route search method according to the embodiment;
FIG. 9 is a diagram showing the progress of processing when the number of processing repetitions = 2.

FIG. 12 is a diagram illustrating a wiring route searching method according to the embodiment;
FIG. 9 is a diagram showing the progress of processing when the number of times of processing repetition = 3.

FIG. 13 is an explanatory diagram showing how a penalty p changes.

FIG. 14 is a diagram illustrating a wiring route searching method according to the embodiment;
It is a figure which shows the relationship between the number of processing repetitions and the penalty for height constraint violation.

FIG. 15 is a flowchart illustrating a processing procedure of a conventional wiring route searching method.

FIG. 16 is a diagram showing a search progress of a conventional wiring route search method.

FIG. 17A is a diagram showing a wiring result of a conventional wiring route searching method, and FIG. 17B is a diagram showing a result of compacting the result.

FIG. 18 is a diagram showing a result of a wiring design of a standard cell using a grid uniformly divided at a wiring pitch in a conventional wiring route searching method.

FIG. 19 is a diagram illustrating a state in which wiring is not completed due to a shortage of the number of grids in the wiring route searching method of the conventional example.

FIG. 20 is a diagram illustrating a state in which wiring is completed by providing a grid narrower than a wiring pitch in the wiring route searching method of the conventional example.

[Explanation of symbols]

S1 input processing S2 searchable grid extraction processing S3 grid row margin calculation processing (margin calculation processing) S4 grid row passing cost addition processing (passing cost addition processing) S5 target arrival determination processing S6 minimum cost route selection processing S200 penalty change processing 10A, 10a, 10B, 10b, 10C, 10c Terminal 20 Wiring area 21 No wiring area 30 Lattice 50 Transistor 71 First wiring layer 72 Second wiring layer 80A, 80B Contact 101 Height constraint

Claims (11)

[Claims] 1. In an automatic wiring design of an LSI, a wiring path is searched for by using a maze method in which a cost is added and a wiring path cost is calculated each time the processing proceeds to each grid in a wiring area divided into a plurality of grids. A wiring route search method, comprising: input processing for inputting at least one of a height constraint and a lateral width constraint of the wiring area and connection information; and performing wiring based on the connection information, wherein the wiring area has a height constraint. For each grid column or each grid row having a width constraint, a margin calculation process of calculating a margin corresponding to the number of routable grids, and in searching for a route of the wiring, the route is determined by each grid column or each grid. When proceeding to a row, set a passing cost based on the margin calculated for the proceeding grid column or grid row,
And a passing cost adding process for adding the passing cost to the wiring route cost. 2. The margin calculation processing is performed by assigning a height or width of a wiring prohibited area in a grid column or a grid row and the grid column or grid row from a height constraint or a width constraint of the wiring area. 2. The method according to claim 1, wherein the margin is calculated by subtracting a height or a width of a region occupied by the wiring. 3. The method according to claim 1, further comprising a minimum cost route selection process for extracting a wiring route having a minimum wiring route cost. 4. The pass-through cost adding process according to claim 1, wherein the pass-through cost is set based on a penalty for a height or width constraint violation in addition to the margin. Route search method in automatic routing design of a computer. 5. After the search for all the wirings is completed, when the height constraint or the width constraint of the wiring area is not satisfied, the search for the wiring is repeated. Further, each time the search for the wiring is repeated, The method according to claim 4, further comprising a penalty change process for changing a penalty for a height or width constraint violation. 6. The method according to claim 5, wherein in the penalty change processing, the penalty is gradually changed from a small value to a large value. 7. In an automatic wiring design of an LSI by a computer, wiring is performed by using a maze method of calculating a wiring path cost by adding a cost each time advancing to each grid in a wiring area divided into a plurality of grids. A recording medium on which a wiring route search program for searching a route is recorded, wherein at least one of a height constraint and a lateral width constraint of the wiring area and connection information are input, and the wiring is performed based on the connection information. For each grid column with a height constraint or each grid row with a horizontal width constraint in the area, calculate a margin according to the number of routable grids. When proceeding to a grid row, set a passing cost based on the margin calculated for the grid row or grid row to be advanced,
A recording medium storing a wiring route search program in automatic wiring design, wherein the passing cost is added to the wiring route cost. 8. When calculating the margin, the height or width of a wiring prohibited area in a grid column or a grid row and the grid column or grid row are already assigned from the height constraint or the width constraint of the wiring area. 8. The recording medium according to claim 7, wherein the margin is calculated by subtracting a height or a width of an area occupied by the wiring. 9. The wiring in automatic wiring design according to claim 7, wherein after calculating the wiring path cost from the terminal at the start point to the terminal at the end point, the wiring path with the minimum wiring path cost is extracted. A recording medium that stores a route search program. 10. The wiring route in automatic wiring design according to claim 7, wherein the passing cost is set based on a penalty for a height or width constraint violation in addition to the margin. A recording medium that stores a search program. 11. When the height constraint or the width constraint of the wiring area is not satisfied after the search for all the wirings is completed, the search for the wiring is repeated. 11. The recording medium according to claim 10, wherein a penalty for a violation of a width constraint is changed from a small value to a large value.