JPH1091673A - Wiring congestion estimation method and semiconductor integrated circuit design system using the same - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable back annotation to an arranging process before an advance to the wiring process, to eliminate the need to repeat virtual arrangement, congestion degree estimation, etc., and to shorten the designing time by expanding a wiring area judged to be unable to wire before virtual wiring is done and securing a bypass. SOLUTION: On the basis of input data, semiconductor elements are virtually arranged on a chip, wiring areas are determined, and the degree of wiring congestion is estimated. For the purpose, wiring costs are calculated for nearly wired gratings G(1, 1) to G(14, 13) formed by dividing the wiring area 1 on the semiconductor chip. Element which are already arranged and scheduled to be wired is selected out of elements D1 to D4 and an area for connecting the selected elements is determined. If it is judged that they can not be wired, the wiring area including the two selected arranged elements diagonally is expanded to secure a bypass. Further, the wiring costs for the nearly wired gratings and the number of wires allocated to the nearly wired gratings are calculated.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] The present invention relates to a semiconductor integrated circuit,
The present invention relates to a wiring method for a printed circuit board or the like, and particularly to a method for estimating a wiring congestion degree after an arrangement step.

[0002]

2. Description of the Related Art An example of a conventional design process for arranging semiconductor elements on a chip on a chip and wiring them will be briefly described with reference to the drawings. Here, this is an example, and the present invention is not limited to this step.

As shown in FIG. 8, predetermined data prepared first is input to a computer (step 1). Next, based on the input data, a computer equipped with a predetermined program automatically arranges a semiconductor element virtually on a chip (step 2).

Next, when wiring is performed for a semiconductor element virtually arranged on a chip, how much the wiring is congested is estimated (step 3). The method of estimating the wiring congestion degree will be described later.

Next, virtual wiring is performed between the semiconductor elements virtually arranged on the chip in consideration of the wiring congestion degree and the like estimated in step 3 (step 4). Next, the virtual wiring data is obtained as an output result (step 5).

An exposure mask is created based on the output result. A series of design steps is completed as described above.
Next, an example of a conventional method of estimating the degree of wiring congestion will be described. As shown in FIG. 9, a semiconductor element 501 is mounted on a chip.
Suppose ~ 503 is located. Now, when it is desired to connect the semiconductor elements 501 to 503 with the same wiring, FIG.
As shown in (1) to (3), various routes are conceivable, and a computer loaded with a predetermined program stochastically determines which route is selected.

Next, as shown in FIG.
The semiconductor elements 201 to 211 are virtually arranged thereon. For example, the semiconductor elements 201 to 203, 204 to 205, to
Let us consider a case where it is desired to connect each of 206 to 207 and 208 to 211 with the same wiring. Now, the semiconductor elements 201 to 201
A minimum rectangle 300 including 203 is formed. Similarly, the minimum rectangles 301 to 303 are formed. These top rectangles 30
A place where 0 to 303 overlap is defined as a wiring congestion part,
A place where there is little overlap is defined as a part where wiring is not congested.

However, as already described with reference to FIG. 9, how the semiconductor elements included in each of the minimum rectangles are wired is determined stochastically, so that the wiring is not necessarily congested at the overlapping portion 600. Not exclusively. Therefore, the estimation of the congestion degree only indicates that there is a high possibility that the wiring is congested. However, the estimation of the degree of congestion is often used in actual designs because of a simple calculation method and high speed.

[0009]

However, in the above congestion degree estimating method, it is assumed that the wiring resources (the amount through which the wiring can pass) are uniform in the wiring area, so that a large-scale When the above method is applied to the design of a semiconductor integrated circuit device, an accurate estimation of the congestion degree cannot be calculated.

[0010] For example, assuming that the area 600 shown in FIG. 10 where the wiring is expected to be congested and the wiring resources (amount of wiring that can be passed) in other places are uniform at, for example, 4 lines / area, the known wiring Because the known placement elements and the effect of the current virtual wiring are not taken into account, wiring may be performed in the region 600, and virtual wiring (for example, five wirings) may be assigned to a wiring source or more. . That is, wiring becomes impossible.

Such a situation can be avoided by repeating virtual arrangement (see step 2 in FIG. 8), estimation of congestion degree (step 3), and virtual wiring (step 4) until real wiring becomes possible.

However, the virtual wiring process in step 4 shown in FIG. 8 determines thousands or tens of thousands of wiring routes and the like.
Requires a great deal of computation time. For this reason, repeating steps 2 to 4 causes a significant increase in calculation time. The present invention has been made in view of the above-described problem, and has as its object to enable back annotation to an arrangement step before proceeding to a wiring step.

[0013]

SUMMARY OF THE INVENTION The present invention divides a wiring area on a chip into schematic wiring grids, and arranges a plurality of already arranged wirings for each of the general wiring grids. The wiring cost is calculated based on the elements and the already-wired wiring, and further, a set of two already-arranged elements to be wired among a plurality of already-arranged elements is selected. Next, based on the wiring cost and the wiring grid, a region for connecting the selected placed devices is determined, and in the determined wiring region, the two placed devices are stochastically determined. A virtual wiring is performed, and the wiring cost is calculated again based on the virtual wiring, the existing wiring and the existing arrangement.

As described above, according to the present invention, before the virtual wiring is performed, the wiring area determined to be unroutable is enlarged and the detour path is secured, so that the virtual wiring step performed after the securing of the wiring area is performed. Nothing is possible. Therefore, it is not necessary to repeat the virtual arrangement, the congestion degree estimation, and the virtual wiring process until the actual wiring becomes possible as in the related art, so that the design time can be greatly reduced.

[0015]

Next, an embodiment of the present invention will be described in detail with reference to the drawings. FIG. 1 shows an example of a design method according to the present invention. As shown in FIG. 1, predetermined data prepared first is input to a computer (step 1).

Next, based on the input data, a computer having a predetermined program automatically arranges a semiconductor element virtually on a chip (step 2). next,
A computer equipped with a predetermined program automatically determines a wiring area and estimates a wiring congestion degree (step 3).

Next, if the semiconductor elements need to be rearranged in consideration of the wiring congestion degree estimated in the previous step, back-annotation is made to step 2; otherwise, the processing proceeds to the next step (step 4). Next, virtual wiring is performed between the semiconductor elements to be wired (step 5).

Next, output data is obtained from the virtual wiring data (step 6). An exposure mask is created based on this output result. A series of design steps is completed as described above.

Next, the above-mentioned wiring congestion degree estimation step (step 3) will be described in detail with reference to the drawings. The wiring congestion degree estimation step includes (1) a division step for dividing a wiring area into a rough wiring grid, (2) a wiring cost calculation step of allocating a wiring cost to the rough wiring grid, and (3) a set of known arrangement elements. (4) a wiring area determining step for determining a wiring area based on the wiring cost and the like assigned to each schematic wiring grid, and (5) a wiring cost and a schematic wiring of the general wiring grid. And a data updating step for calculating the number of wirings allocated to the grid (see FIG. 2). Hereinafter, each of the above-described steps will be described.

First, (1) a dividing step for dividing a wiring region into a general wiring grid will be described. As shown in FIG. 3, D1 to D4 indicate the already-arranged semiconductor elements arranged in the arrangement step. Further, the wiring area 1 on the semiconductor chip is roughly divided into wiring grids G (1, 1) to G (14,
13). Here, the semiconductor element D1 is in the general wiring grid G (3, 11), the semiconductor element D2 is in the general wiring grid G (5, 3), and the semiconductor element D3 is in the general wiring grid G (3, 11).
In (10, 1), the semiconductor element D4 has a rough wiring grid G (1
2, 4).

Next, a description will be given of (2) a wiring cost calculation step of allocating a wiring cost to a schematic wiring grid. A wiring cost is assigned to each of the above-described general wiring grids. The concept of a method of calculating the wiring cost is described below.

FIG. 4 is an enlarged view of one of the schematic wiring grids shown in FIG. As shown in FIG. 4, in this schematic wiring grid G (X, Y), the grid in the X direction (the number of wires that can be wired) is 5, and the grid in the X direction is 4, and the general wiring grid G (X, Y) Assuming that there is an obstacle Z (for example, an already-arranged element or the like) inside, there are one usable wiring in the general wiring grid G (X, Y) in the X direction and two wirings in the Y direction.

In this case, it is assumed that the ease of wiring in the X direction in the schematic wiring grid G (X, Y) is 1 and the ease of wiring in the Y direction is 2, and the general wiring grid G (X, Y) Is estimated as C (1, 2). That is, the wiring cost in the X direction is 1 and the wiring cost in the Y direction is 2.

The wiring cost is calculated as described above. The above-described method of calculating the wiring cost is an example taken for simplicity of description, and there are various other calculating methods. Next, (3) a selection step for selecting a set of known arrangement elements will be described.

As shown in FIG. 5, a line segment Nij (i is 1 to 3, j is 1 to 3, i 、 j) connecting each of the already arranged elements D1 to D4 arranged on the chip is considered. Now, assume that virtual wiring is performed in ascending order of these line segments. In this case, the semiconductor element D
The virtual wiring of 3 and D4 will be performed first. That is, it is selected first.

Next, a description will be given of (4) a wiring area determining step for determining a wiring area based on a wiring cost or the like assigned to each schematic wiring grid. Now, when wiring the semiconductor elements Dl and Dm, the wiring always crosses the general wiring grid row. However, if all of the schematic wiring grid columns have already been wired, the semiconductor element D
1 and Dm cannot be wired.

Therefore, in the case where the wiring is impossible, the wiring area is shown in FIG.
The wiring area is enlarged in the X and Y directions as shown in FIG. Next, a method for enlarging the wiring area will be described in detail. Now, let the total number of grids (the number of wirings) crossing the edges of the rough array grid rows (G (p, j) to G (p, m)) be Ntotal, and the rough array grid rows (G (p, j)) ＧG (p, m)) assuming that the total wiring cost in the X direction is Ctotal, it can be determined that wiring is still possible when Ntotal−Ctotal> 0. The reason is that the sum of wiring (Ntotal) is
This is because it is larger than the number of wirings that cannot be used due to obstacles (Ctotal).

When Ntotal-Ctotal <0, it can be determined that wiring is impossible. The reason is the sum of wiring (Ntotal)
However, the number of wires that cannot be used due to obstacles (Ctotal)
Because it is less. In this case, as shown in FIG. 6, the wiring area is enlarged and a detour path is secured. That is, a state in which wiring is possible is achieved.

Next, in the area enlarged as described above, the same procedure is performed for all other schematic wiring grid arrays, and further, for the general wiring grid array in the Y direction, the wiring area is expanded if necessary. .

In the wiring area determined as described above, stochastic wiring is performed based on wiring cost and the like. Next, the stochastic wiring will be described in detail. FIG. 7 is an enlarged view of a schematic wiring grid around the semiconductor element D1 shown in FIG.

Now, the wiring cost is defined as C (X, Y),
X means the wiring cost in the X direction, and Y means the wiring cost in the Y direction. Also, a schematic wiring grid G (2, 8),
The wiring costs of G (3, 9) and G (4, 8) are C
Assume (5,2), C (2,1), C (3,4).

Now, the virtual wiring is a general wiring grid G (3, 8).
It is assumed that virtual wiring is performed from there to the semiconductor element D1. Further, assuming that the virtual wiring is not wired obliquely, from the general wiring grid G (3, 8),
It can be wired left, top, right. That is, the schematic wiring grid G
Virtual wiring is possible at (2, 8), G (3, 9), and G (4, 8). Here, G (3, 8) to the left (G (2,
8)) wiring cost is 5, G (3, 8) to higher (G
The wiring cost to (3, 9)) is 1, and the wiring cost from G (3, 8) to the right (G (4, 8)) is 3. left,
The location of the wiring on the upper and right sides is determined stochastically in consideration of the respective wiring costs. For example, the probability of wiring to the left is 3/23, the probability of wiring to the top is 15/23, and the probability of wiring to the left is 5/23. As described above, the most likely to be virtually wired from the schematic wiring grid G (3, 8) is the schematic wiring grid G (3, 9) thereabove. This is obvious considering that the wiring cost from G (3, 8) to the upper side (G (3, 9)) is the smallest compared to the other two, that is, that wiring is easy. As described above, virtual wiring is performed up to the destination D1.

As described above, a wiring area is determined and stochastic wiring is performed. Next, (5) a data updating process for calculating the wiring cost of the schematic wiring grid and the number of wirings allocated to the general wiring grid will be described.

As described above, when the wiring area is determined and stochastic wiring is performed, wiring is performed, so that the wiring cost and the number of usable grids of the rough wiring grid on which virtual wiring is performed are changed. I do. Therefore, the wiring cost is updated again, and the number of wirings allocated to the general wiring grid is calculated.
The number of wires assigned to the rough wiring grid on an arbitrary edge is calculated by the following equation. The number of wirings = C / Ctotal where C is the wiring cost of an arbitrary schematic wiring grid, Ctota
l represents the sum of the wiring costs of all the schematic wiring grids on the edge.

The above-described steps are performed for one set of already-arranged elements to which wiring is to be performed, and the above operation is repeated for another set to which wiring is to be planned. As described above, the number of wirings is calculated, and the congestion degree of the wiring is estimated. In that case, if necessary, back annotation is performed until the arrangement step, and the semiconductor element is rearranged.

Further, a program for realizing the above calculations is installed in a computer, predetermined data is input by input means such as a keyboard and a floppy desk, and data is output by means such as a CRT and a printer.

As described above, according to the present invention, it is possible to accurately and quickly estimate the degree of wiring congestion without performing virtual wiring, which could not be estimated accurately without virtual wiring. Therefore, it is not necessary to repeat the virtual arrangement, the congestion degree estimation, and the virtual wiring process until the actual wiring becomes possible as in the related art, so that the design time can be greatly reduced.

[0038]

According to the present invention, it is possible to accurately and quickly estimate the degree of wiring congestion without performing virtual wiring, which could not be accurately estimated without performing virtual wiring in the past. Since it is not necessary to repeat the virtual arrangement, the congestion degree estimation, and the virtual wiring process until the actual wiring becomes possible, the design time can be greatly reduced. In addition, in order to obtain a route stochastically, it is possible to absorb a habit of a wiring route by a wiring algorithm.

[Brief description of the drawings]

FIG. 1 is a view showing a flow chart of an arrangement and wiring process according to the present invention.

FIG. 2 is a diagram showing a detailed flowchart of a wiring congestion degree estimation step.

FIG. 3 is a diagram showing a state in which a wiring region is divided into schematic wiring grids.

FIG. 4 is a diagram for explaining wiring costs.

FIG. 5 is a diagram for explaining selection of a pin pair.

FIG. 6 is a diagram illustrating a state where a wiring region is enlarged.

FIG. 7 is a diagram for explaining stochastic wiring.

FIG. 8 is a view showing a conventional arrangement and wiring flowchart.

FIG. 9 is a diagram showing a state of wiring.

FIG. 10 is a diagram showing a conventional wiring congestion estimation method.

[Explanation of symbols]

 G (X, Y) Schematic wiring grid D1 to D4 Semiconductor element Nij Graph

Claims (7)

[Claims] A dividing step of dividing a wiring region on a chip into a general wiring grid; a wiring cost calculating step of calculating a wiring cost for each of the general wiring grids; A selecting step for selecting a set of already-arranged elements for which wiring is scheduled among the arranged elements; and a wiring-area determining step for determining an area for connecting the selected already-arranged elements. And a data update step of calculating the wiring cost of the schematic wiring grid and the number of wirings allocated to the schematic wiring grid,
A wiring congestion estimation method characterized by having: 2. A dividing step for dividing a wiring region on a chip into a rough wiring grid, and a plurality of already-arranged elements already placed and a wiring already wired for each of the rough wiring grids. A wiring cost calculating step for calculating a wiring cost based on the wiring; a selecting step for selecting a set of already arranged elements to which the wiring is scheduled from among the plurality of already arranged elements; A wiring area determining step for determining an area for connecting the selected placed elements based on the wiring grid and updating the data for calculating the number of wirings allocated to the general wiring grid And a wiring congestion estimating method, comprising: 3. The wiring area determination step, wherein in the wiring cost calculation step, when it is determined that the wiring is impossible by the determination means for determining whether or not the virtual wiring is possible, the selected two existing arrangements are performed. Enlarging a wiring area having a diagonal element, and using the enlarged area as a wiring area,
The wiring congestion estimation method according to claim 1 or 2, wherein the method is a step. 4. A determination for determining whether or not virtual wiring is possible based on a wiring cost and a wiring grid assigned to each of the schematic wiring grids in the wiring cost calculating step. By means, when it is determined that wiring is possible, a region having the selected two already-placed elements as a diagonal is defined as a wiring region, and when it is determined that wiring is impossible, the two selected already-placed elements are replaced with each other. 3. The wiring congestion estimation method according to claim 1, wherein the diagonal wiring area is enlarged, and the enlarged area is used as a wiring area. 5. The wiring congestion estimating method according to claim 1, wherein in said selecting step, a plurality of already placed elements are selected. 6. The method according to claim 1, wherein, after the data updating step, the selecting step, the wiring area determining step, and the data updating step are repeated until all sets of the already-arranged elements for which wiring is scheduled are selected. The wiring congestion estimation method according to claim 1 or 2. 7. An input means for inputting predetermined input data necessary for wiring and arrangement of elements, and the elements are virtually arranged on a chip based on the input data. A computer equipped with a program for performing virtual wiring between semiconductor elements to be further wired using a wiring congestion degree estimation method, and output means for outputting predetermined output data calculated by the computer A semiconductor integrated circuit design system characterized by having: