JPH06223134A - Automatic wiring method for integrated circuit - Google Patents

Abstract

PURPOSE:To determine the path branch point and wiring width of a clock wiring path which has a branch so that the delay is minimized while the skew is minimized. CONSTITUTION:A processing for determining the path branch point where the skew is minimized by fixing the wiring width and a processing for determining the wiring width with which the skew is minimized while the path branch point is fixed are repeated alternately to find a convergence solution. In the processing for determining the wiring width, the delay is represented as a function of the wiring width of the path of branch points, a partial derivative for the wiring width of the function is found, and the wiring width is found so that its absolute value becomes minimum.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic wiring method in a layout of a semiconductor integrated circuit by processing using a computer.

[0002]

2. Description of the Related Art In digital logic integrated circuits, sequential circuits represented by flip-flops are almost always used, and the entire circuit operates while synchronizing with a plurality of clock signals having different phases and periods. It is supposed to do. The clock signal is generated inside the chip or supplied from the outside, but is usually supplied to the circuit block via some stages of buffer cells, and between the buffer cells and between the buffer cells and the flip-flops is generally CA.
Wired automatically by D technology.

The propagation delay time (hereinafter referred to as a delay) of a clock signal supplied to a flip-flop is usually different for each flip-flop, and the phase difference is a clock skew (hereinafter referred to as a skew). However, if this skew is too large, it becomes impossible to synchronize the circuits at a desired clock frequency. Therefore, it is important to determine the positions of the buffer cells and the wiring paths so that the clock signals arrive at all the flip-flops on the chip at the same timing as possible.

The delay up to the flip-flop includes an internal delay of the buffer cell to be relayed, a delay required for the buffer cell to charge / discharge the wiring capacitance / wiring resistance of the wiring for connection and the input terminal capacitance of the driven cell. Be done. Among them, the wiring resistance cannot be ignored because of the decrease in transistor size and wiring cross-sectional area due to the recent progress in semiconductor fine processing technology. Therefore, in terms of delay prediction accuracy, it is necessary to treat the circuit as a distributed constant circuit.

For example, a circuit as shown in FIG.
The delay must be predicted as a distributed constant circuit as shown in (b).

As a main method for reducing the skew, there are a mesh method and a tree method. In the mesh method, a wiring path that circulates a chip in a grid pattern is laid, a buffer cell is connected beside the grid path, and a flip-flop is connected through the buffer cell, which is disclosed in Japanese Patent Laid-Open No. 63-107316. Here is an example.

The advantages of this method are that the structure is simple, that the wiring path is ring-shaped, the equivalent resistance of the wiring is reduced and the delay can be reduced, and the delay can be predicted before the layout processing.

However, when the circuit becomes extremely large, the problem is that the skew between the flip-flop close to the root driver and the one far from the root driver cannot be ignored, and the wiring length increases because the grid must be cut finely. Becomes

On the other hand, in the tree system, a buffer in which each stage is connected in parallel has a multi-stage configuration, and a tree-shaped wiring path is provided for each buffer. Japanese Patent Laid-Open No. 61-82445 and Japanese Patent Laid-Open No. 1-157115 are known as conventional examples of buffer insertion, and a typical example of a tree-shaped wiring path is the document “HBBakoglu, et al: A symmetri”.
c clock-distribution tree and optimized high-speed
interconnections for reduced clock skew in ulsi a
nd wsi circuits., IEEE Int.Conf.on Computer Design,
The 1986 "H-tree is known.

The advantage of this method is that the skew can be reduced and that it can be easily applied to a megacell mixed chip. On the other hand, if the number of buffer stages is too deep, the skew becomes small but the delay becomes large, and it is difficult to predict the delay unless the layout process is detailed.

Although both methods have advantages and disadvantages, it can be said that the tree method is preferable in order to cope with the large scale of the circuit. The conventional technique using the tree method will be described below.

The H-tree, which is a typical wiring shape of the tree system, repeats the H-shaped wiring path while recursively proportionally reducing it. Due to its symmetry, equal wiring length and equal delay can be maintained. . However, if the supplied elements / element groups are powers of 2, the elements are arranged symmetrically, and the element capacities are not equal, this equal delay cannot be achieved, and it is difficult to apply in an actual circuit.

As an improvement of this, the document "Mich
ael ABJackson, et al: Clock Routing for High-Perfo
mance ICs., 27th ACM / IEEE Design Automation Conf., 1
There are 990 "MMM algorithms.

According to this method, the equal number of flip-flops (or buffer cells) may be divided from top to bottom, and at the same time, the branch point of the wiring path is set at the center of gravity of the flip-flops in the divided regions. Despite the simple processing, it has a feature that the skew can be made relatively small. However, since it is a top-down process, there is a drawback that a satisfactory skew value cannot be obtained depending on the delay estimation accuracy.

Regarding the optimum insertion method of the buffer cell, the document "S. Boon, et al: High performance clock di
stribution for cmos asic's., IEEE Custom Integrate
dCircuit Conf., 1989 ”, but since the wiring method itself is the same as the algorithm used for general signals, if the wiring area is large, skew due to the difference in wiring resistance between signal paths poses a problem.

On the other hand, in order to solve the problem that the circuit becomes unsynchronized at a desired clock frequency due to too large a skew, an on-chip clock skew reduction method has been recently proposed. Japanese Patent Laid-Open No. 3-137851 is an example.

This method is characterized in that in the binary tree type wiring structure, the position of each path branch point is determined so that the delays on the downstream side are balanced, and the on-chip delay is minimized. The optimum position of the buffer cell is determined so that By minimizing the delay in the chip, the clock skew generated on the board where the chips are scattered is also reduced.

However, in the recent tendency that the minimum line width of the wiring is becoming narrower and narrower, the increase of the delay due to the increase of the wiring resistance is large, and the optimum position setting of the buffer cell is becoming insufficient.

As a method for solving the delay increase due to the large wiring resistance, Japanese Patent Laid-Open No. 2-194545 and Japanese Patent Laid-Open No. 63-5 have been proposed.
1656, is proposed. The former is a method of making the wiring width twice or more the normal line width, but there is a problem that the optimum line width is not quantitatively determined. Further, the latter determines the wiring width that minimizes the delay in consideration of the wiring resistance and the wiring load capacitance for the one-stroke writing wiring path, but has a problem that it cannot be applied to the branching path.

By the way, in the wiring of the integrated circuit, the idea of reducing the wiring width from the signal sending end to the signal receiving end has been proposed in order to reduce the signal propagation delay.
Such wiring is called taper wiring.

Conventionally proposed automatic wiring methods for integrated circuits include a maze method and a line segment expansion method.
For references on the maze method, see T. Ohtsuki, Ed., La.
youtDesign and Verification. Amsterdam: North Hol
land, 1986. is a paper on line segment expansion method by Kojima, Yamada, Sato, and Otsuki, "Expansion of line segment expansion method to two-layer wiring and its evaluation", Research Report of Information Processing Society of Japan, Design Automation Workshop, vol. .91, No.58-3, pp 1-8 (1991). However, the effective realization method of taper wiring in these conventional wiring methods has not been announced until now.

As a method for realizing the tapered wiring, it is conceivable to perform a path search with the maximum width in the wiring and reduce the wiring width as needed after finding the path. Although this method is simple, since it is not possible to find a gap having a small width, it may not be possible to effectively utilize a wiring portion having a small width, and in some cases, a path may not be found.

Further, even if a path is found, the wiring area may be wasted, and it may be difficult to carry out subsequent wiring.

[0024]

As described above, in the conventional automatic wiring method by the tree method, the insertion of the buffer cell and the determination of the wiring path are handled separately, even though the purpose of reducing the skew is the same. Since the wiring path is not determined based on the detailed delay estimation, it is not possible to achieve a fine skew balance.

Further, in the conventional automatic wiring method, no method has been established for determining the optimum wiring width that minimizes the delay with respect to a general clock wiring path having a branch.

Further, in the conventional automatic wiring method, there is a problem that, when performing tapered wiring, it is not possible to find a path that effectively utilizes a wiring portion having a small width, or the wiring area is wasted. .

The present invention has been made in view of such circumstances, and an object of the first invention is to make a more accurate delay while coordinating the buffer cell insertion processing and the wiring path determination processing. By deciding the branch point of the wiring path based on the estimation, it is possible to provide an automatic wiring method for an integrated circuit that can drastically reduce the skew regardless of whether the element positions such as flip-flops are uniform or non-uniform. is there.

The object of the second invention is as follows.
An object of the present invention is to provide an automatic wiring method for an integrated circuit that can determine an optimum wiring width that minimizes delay even in a general clock wiring path having a branch.

Further, an object of the third invention is that, in the case of taper wiring, a necessary wiring width is calculated at any time in the course of a path search, so that the wiring area is not wasted, and the taper wiring is fast. An object of the present invention is to provide an automatic wiring method of an integrated circuit capable of realizing processing.

[0030]

In order to achieve the above object, the first invention is to provide a clock signal from a route driver cell placed on a semiconductor substrate to a plurality of terminal cells via a relay buffer cell. At the time of supplying, a cluster including at least one of the terminal cells is generated, the terminal cells are divided into a plurality of groups, and the root driver cell is used as a root node and the cluster is used as a leaf node to form a binary tree-like wiring path. When the depth of the subtree that is generated and driven by the relay buffer cell exceeds a certain depth, the delay at any point on the downstream side of the depth of the subtree is more delayed when another relay buffer cell is inserted in the subsequent stage. The depth of the subtree that can reduce the time is obtained, and the clock on the binary tree is set with the depth of the subtree as the upper limit. After inserting the relay buffer cell in a portion where the signal propagation delay time is minimized, the RC delay amount of the path from the branch node to the leaf node is calculated in order from the lower branch node of the binary tree, and the difference is calculated. The physical position of the branch node is set so as to minimize, and the circuit connection information is updated due to the insertion of the relay buffer cell and the cell arrangement information near the buffer cell is corrected to eliminate the overlap between cells. Then, the detailed wiring path in each cluster is determined based on the determined placement information, and the position of each branch node is determined based on the accurate delay amount in the cluster obtained from the determined wiring path. The feature is that a detailed wiring path between them is determined.

According to a second aspect of the present invention, in a binary tree type wiring path structure, a wiring delay function having a wiring width of a path between adjacent branch points as a parameter is obtained, and further, the wiring delay function for each wiring width parameter is calculated. Partial derivatives are obtained, and each wiring width is determined so that the absolute value of the partial derivative is minimized within a constraint range in which each wiring width parameter is equal to or larger than the standard wiring width.

Alternatively, in the second invention, when the topology structure of the binary tree type wiring path of the clock signal is predetermined, each wiring width of the path between the adjacent branch points is fixed and each branch point is separated from each branch point. The first process that minimizes skew by recursively repeating the process of determining branch points so that the delays on the downstream side are balanced from the lower part of the tree to the upper part, and the position of each path branch point is fixed. The second process for determining each wiring width by the method described above and minimizing the delay, and whether or not the delay change amount after alternately repeating the first and second processes has reached within the allowable value It is characterized in that the path in the state where the delay change amount reaches within the allowable value is set as the clock wiring path.

Further, in the second invention, the average wiring width of the path between the adjacent branch points in the binary tree type wiring path structure is
The value is 0.4 times the average wiring width of the path one level higher than the path on the binary tree type wiring path structure and the standard wiring width for general signals is less than or equal to the larger value. The feature is that the wiring width is determined as described above.

Further, a third invention is an automatic wiring method for an integrated circuit, wherein a path search for a wiring whose wiring width becomes smaller from a signal sending end to a receiving end is carried out by sequentially searching a wiring region. It is characterized in that a wiring area is searched from an edge having a small width to an edge having a large width, and each time a new wiring area is searched, an ideal wiring width is obtained in the wiring area.

In the third invention, the ideal wiring width in the new wiring area is set to the already obtained accurate wiring path length from the end of the small wiring width to this new wiring area. It is characterized in that it is obtained based on the shortest path length using only the horizontal path and the vertical path from the new wiring area to the end with the large wiring width.

[0036]

According to the first aspect of the present invention, a plurality of terminal cells, such as flip-flops which receive a clock signal, which are close to each other are grouped together to form a cluster, and the clusters are wired by a wiring route determination algorithm for general signals. The wiring path is laid from the root driver cell to the cluster in a binary tree shape.

At this time, the size of each cluster has an upper limit so that the delay time due to the wiring resistance in the cluster does not become too large, and in addition, clustering is performed so that the load capacity in the cluster is uniform.

In addition, a plurality of relay buffer cells are automatically inserted at the entrance of the cluster and the portion where the delay of the binary tree can be minimized, and the root driver or the relay buffer cell is used as the starting point for the multi-stage subtree. Form a hierarchical structure.

The position of the branch node in each subtree, that is, the branch point on the wiring path is set at a position where the difference between the two child nodes and the subsequent RC delays is calculated to minimize the difference, and this process is bottomed up. The wiring shape of the subtree is determined by repeating the above.

Further, in the process of forming the wiring shape of the hierarchical sub-tree in a bottom-up manner, the positions of the buffer cells are finely adjusted so that the delays after the sub-trees of the same hierarchy become uniform.

The second aspect of the present invention is that in a binary tree type wiring tree structure, the wiring width on the path between adjacent branch points is constant, and the wiring width of branch paths at the same depth on the tree. Assumes that they have the same line width, the wiring delay is expressed by the Elmore equation using each wiring width as a parameter.

Next, a partial differential function for each wiring width parameter of the delay is calculated, and each wiring width is minimized in the constraint range that each wiring width parameter is equal to or larger than the standard wiring width. The delay is minimized by determining

Further, the process of fixing the wiring width to determine the path branch point at which the skew is minimized and the process of fixing the path branch point to determine the wiring width at which the delay is minimized are alternately repeated. By using the path when converged as the final solution of the clock wiring path, the skew and the delay can be minimized within a practical time while simplifying a complicated problem.

Further, in the third aspect of the invention, when the tapered wiring is used, a path search is performed from an end having a small wiring width to an end having a large wiring width, and every time a new wiring area is searched, an ideal wiring width in that area is obtained. By advancing the search using the Manhattan distance (the shortest path length using only the horizontal path and the vertical path), the path in consideration of the wiring width can be obtained without violating the design rule. As a result, it is possible to efficiently realize a tapered wiring that effectively utilizes the wiring area by only searching the wiring area once.

[0045]

【Example】

First Invention First Embodiment FIG. 1 is a flowchart showing an automatic wiring processing procedure according to a first embodiment of the first invention. The automatic wiring processing according to the first aspect of the present invention includes specification data input (step 1), provisional determination of tree branch points (steps 2 to 5), engineering change (steps 6 and 7), and determination of actual wiring paths (step 8). To step 11).

It is assumed that this processing is performed after the cell arrangement position is determined and before the general signal wiring path is determined. The wiring process of the first invention will be described below with reference to FIG.

First, in step 1, specification data is input. The specification data refers to a clock signal name input to the root driver, the number of buffer cell insertion stages, the type of buffer cell used, and target values of delay and skew.

In the next step 2, the cells such as flip-flops to be driven (hereinafter, terminal cells) are clustered for each designated clock signal.

In generating a cluster, the region in which the end cells are present is divided into a grid shape, and the end cells arranged in the grid are initialized so that they belong to the same cluster. The end cells belonging to the adjacent clusters are moved and exchanged so that the sum of the line capacity calculated from the wire length and the input load capacity of the end cells becomes uniform.

The size of the grid is such that the load capacity in the cluster is within the drive capacity of the buffer cell to be driven,
Also, it is set on the basis that the delay effect due to the wiring resistance is not so large.

In step 3, an entire binary tree is formed in which only parent-child relationships with clusters as leaf nodes are shown. That is, the process of dividing the leaf node into two for each node of the tree is recursively repeated for the child node starting from the root node (root driver cell).

When dividing into two, the difference in the number of leaf nodes is set to be within 1 at most, and finally the difference in depth (hierarchy) from the root node in each leaf node is within 1 level. To be The hierarchy of the binary tree is determined in advance according to the allowable delay.

In step 4, the physical positions of the nodes other than the root node and the leaf nodes in the tree determined in step 3 are provisionally determined. The position of this node is a branch point when determining the wiring path,
Set the position so that the delay difference after the branch destination is minimized.

It is assumed that the position of the leaf node is at the center of the cluster at this point. In addition, in step 4, the relay buffer cell is inserted into the tentatively determined physical position of the tree node based on the input spec data. At that time, the depth and cell type on the entire tree are made the same for each insertion stage of the buffer cells.

In the next judgment processing of step 5, it is checked whether or not there is a clock signal which has not been processed from step 2 to step 4. If it remains, the processing from step 2 to step 4 is repeated and it remains. If not, go to Step 6.

In step 6, the circuit connection information changed by inserting the buffer cell is updated. That is, a new net and its connection terminal are added, and the connection net of the connection terminal of the old clock net is changed.

In step 7, if there is a pattern in the vicinity of the inserted buffer cell that overlaps this cell, the position of the neighboring cell is corrected so as to remove it. in this way,
The detailed arrangement position is determined so that the position of the buffer cell is as close as possible to the position of the branch point to be inserted determined in step 4.

In step 8, the actual wiring path in the cluster is determined by a general signal wiring path determination algorithm so that the wiring length is as short as possible.

In step 9, the position of the branch point of the tree is corrected. This is to correct the position of the branch point so that accurate delay balance can be obtained in response to the confirmation of the wiring capacity in the cluster. Position determination is performed according to step 4.

In step 10, the actual wiring route between the nodes of the tree is determined. Basically, nodes having a parent-child relationship on the tree are connected by the shortest path. Further, as the wiring layer used here, it is desirable to use a dedicated clock layer having a small resistance and a small capacitance from the viewpoint of delay minimization.

In the judgment processing of step 11, it is checked whether or not there is a clock signal for which the actual wiring path has not been obtained,
If there is, the processing from step 8 to step 10 is repeated, and if not, all processing is ended.

Next, regarding the details of step 4 above,
It will be described with reference to FIG.

First, in step 12, the type of buffer cell to be inserted and the insertion level are set for each insertion stage. As for the type of buffer cell, the one specified in the spec data is within the usable range, and the insertion level is such that when the depth of the subtree driven by the buffer cell reaches a certain depth or more, another buffer cell for relay is provided in the subsequent stage. If you insert
The upper limit is the depth to the subtree that can reduce the clock signal propagation delay time at any point downstream of the subtree depth. Also, buffer cells of the same type are inserted at the same level.

In step 13, buffer cells are inserted into the entire tree under the conditions set in step 12,
Create a hierarchical tree.

In step 14, the position of the branch point is determined and the delay from the branch point to the leaf node is calculated.

For each branch point, the sum of the delay due to the wiring resistance of the wiring at the lower level and the delay after the subsequent buffer cell is calculated for every two child nodes, and the difference is calculated from the branch point to the child node. It is decided to cancel by the difference in delay due to the wiring resistance of. Although the details will be described later, such a branch point is determined bottom-up from the leaf node of the entire tree toward the root node.

In the judgment processing of step 15, it is checked whether or not the delay skew from the root node to the leaf node at the present time satisfies the specifications, or the numerical value thereof is the minimum, and the best calculation among the already calculated is performed. If the result is yes, go to step 16, otherwise go to step 17.

In step 16, this data is saved assuming that the current tree structure and the delay value are the best data. If there is already saved data, delete the old data and replace it with new data.

In the judgment processing of step 17, it is checked whether or not there is a combination of buffer cell type and insertion level which has not been tried, and if there is a combination, the procedure proceeds to step 18, and if there is no combination, a series of steps from 12 to 18 The process ends.

In step 18, the data of the buffer cell inserted in the tree data structure at the present time is reduced and the uninserted state is restored. Then, to set different types of buffer cells and insertion levels, step 12
Return to.

The delay estimation method for setting the upper limit value of the subtree depth and the setting method of the upper limit value, which are performed in step 12, will be described below.

First, the delay estimation for obtaining the upper limit value of the subtree depth will be described.

The delay varies depending on the wiring shape,
Here, in order to obtain an average delay value, a completely symmetrical path in which an H-shaped path is recursively repeated is assumed, and the arrangement position of the buffer cell or the root driver cell is assumed to be the center of the H-shaped portion. At this time, the delay tn in the subtree directly driven by the buffer cell or the root driver cell is

[Equation 1] It can be calculated by C _k = 4 C _{k + 1} +3 cD · 21 ^-k / 2.

Where: I: internal delay of buffer cell or root driver cell R ₀ : on-resistance of buffer cell or root driver cell r: wiring resistance value per unit length c: wiring load capacitance value per unit length D: Length of one side of subtree area n: Depth of subtree (number of repetitions of H-shaped path) C _k : Load capacity of partial tree, downstream of k-th H-shaped path W ₁ , W ₂ : time weight constant, the wiring resistance and the wiring load capacitance were approximated to be the same (average value) in both XY directions, and the subtree region was assumed to be square.

[0075] C C than recurrence formula ^{_{k k + 3cD2 1-k /}} 2 = 4 {C k + 1 + 3cD · 2 1- (k + 1) / 2} = 4 n + 1-k (C n + 1 + 3cD · 2 ⁻ⁿ / 2) Here, if the load capacity C _{n + 1} of the leaf node is Cg, then C _k = (Cg +3 cD · 2 ⁻ⁿ / 2) · 4 ^{n + 1 −k} −3 cD · 2 ^-k .

Substituting this C _k into Equation 1, the delay t
n is

[Equation 2] Becomes

[0077] Furthermore, _{W 2 = W 1/2,} 1-8 -n = 1
, 1-4 ⁻ⁿ = 1, tn = I + W ₁ (R ₀ + 3rD / 14) (3cD · 2 ⁿ / 2 + Cg · 4 ⁿ ) -3W ₁ (R ₀ + rD / 3) cD / 2 is obtained. To be

Next, using this equation, the difference in delay depending on the presence / absence of buffer cell insertion is derived. If the depth of the subtree driven by the buffer cell of interest (root driver cell) is n1 and the depth of the subtree driven by the buffer cell in the subsequent stage is n2, there is no buffer cell in the subsequent stage. And the delay difference Δt between Δt = ⁽¹⁾ t _{n1 + n2} − ( ⁽¹⁾ t _n1 + ⁽²⁾ t _n2 ) = 2 ⁿ² W ₁ {( ⁽¹⁾ R ₀ + 3rD / 14) · 3cD2 ⁿ¹ /
_{^{2- ((2) R 0 +}} 3rD2 -n1 / 14) · 3cD2 -n1 /
2} +4 ⁿ² · W ₁ {( ⁽¹⁾ R ₀ + 3rD / 14) · Cg · 4 ^{n1
_{- ((2) R 0 +}} 3rD2 -n1 / 14) Cg} -W1 ((1) R 0 + 3rD / 14) · (3cD2 n1 / 2 +
^{Cg 4 n1) - (2)} I + W 1 ((2) R 0 + rD2 -n1 / 3) · 3rD2
^-n1 / 2> W ₁ ( ⁽¹⁾ R ₀ + 3rD / 14) · (3cD · 2 ⁿ¹ / 2)
_{^{+ 3Cg 4 n1) -W 1 (}} (2) R 0 + 3rD / 28) · (3cD / 2 + 4C
g)- ⁽²⁾ I. The parenthesized subscript on the left shoulder of the variable represents the buffer cell column.

Now, letting f (n1) be the right side of the above inequality, the solution n1 ^* satisfying f (n1 ^* -1) ≤0≤f (n1 ^* ) is the subtree depth driven by the buffer cell of interest. Is the upper limit of. This is because when n1 ≧ n1 ^* , Δt> f (n1) ≧ f (n1 ^* ) ≧ 0, that is, the delay can be always reduced by inserting the subsequent buffer cell regardless of n2.

Thus, given the driving force of the buffer cell, the internal delay, and the size of the subtree region, the upper limit value n1 ^{* of the} depth of the driven subtree can be obtained.

Such processing is checked in step 12 for a combination of the buffer cell type and the insertion level for each buffer cell insertion stage, within the upper limit value of the subtree depth, and only the combinations within the range are checked. Should be selected. By doing so, it is possible to omit the wiring route determination processing for unnecessary combinations and save the processing time.

Next, the above step 1 as shown in FIG.
Regarding the details of the branch point position deciding method in 4), after explaining the delay calculation model which is a prerequisite for deciding the position, first, the branch point locating method in one subtree is explained, and finally the processing for the whole tree The method will be described.

(1) Delay Calculation Model Here, the calculation in one subtree, that is, the delay between the input terminal of the root driver cell (buffer cell) and the input terminal of the next-stage buffer cell will be described.

For convenience of explanation, the first branch point on the subtree is the node number 1, and when k is an even number, the node number k /
Two child node numbers for the branch point of 2 are k and k + 1. When k is an odd number, the node numbering is set so that the two child node numbers for the branch point of the node number k / 2 are k and k-1. It has been done (see FIG. 4).

Further, it is set in advance that the input end and the output end of the root driver cell have node numbers of -1, 0, respectively.

At this time, node number 0 to node number e
Delay t (1,
e) is approximately calculated by the following recurrence formula.

T (e, e) = 0 t (k / 2, e) = t (k, e) + d (k / 2, k) k ≧ 1 d (k / 2, k) = w ₁ * r _{x * L x (k / 2} , k) * C (k) + w 1 * r y * L y (k / 2, k) * C (k) + w 1 * α xy * L x (k / 2, k ) * L _y (k / 2, k) + w ₂ * α _xx * L _x (k / 2, k) * L _x (k / 2, k) + w ₂ * α _yy * L _y (k / 2, k) ) * L _y (k / 2, k) C (e) = C _e C (k) = C (2 * k) + c _x * L _x (k, 2 * k) + c _y * L _y (k, 2) * k) + C (2 * k + 1) + c _x * L _x (k, 2 * k + 1) + c _y * L _y (k, 2 * k + 1) α _xx = r _x * c _x α _yy = r _y * c _y α _xy = 0.5 * (r _x * c _y + r _y * c _x ) where t (a, b) is the delay due to the wiring resistance from node number a to node number b, and C _e Is the input terminal capacitance of the leaf node e, C (a) is the sum of the wiring capacitance on the downstream side of the node number a and the input capacitance of the leaf node, and r _x and r _y are the unit lengths of the wiring in the X and Y directions, respectively. Wiring resistance per unit, c _x , c _y Are the wiring capacitance values per unit length of the wiring in the X and Y directions, L _x (k / 2, k) and L _y (k /
2, k) is an X connecting the parent node k / 2 and the child node k.
The wiring length in the direction and Y direction.

The essential point of this expression is RC when the load capacity on the downstream side of each resistor is charged and discharged.
The delays are sequentially added, and the multiplier w ₁ is used as a lumped constant and the multiplier w ₂ is used as a distributed constant.

The wiring length is calculated assuming that it is the Manhattan distance connecting the parent node and the child node, that is, the shortest path, and the difference in delay due to the bent shape is ignored. This is the difference between the broken maximum and minimum delay due to the shape of the bending _{w 1 * (r x * c} y -r y * c x) * L x (k / 2, k) * L y (k / 2, k ) Is practically much smaller than other terms in the d (k / 2, k) definition formula. In the above equation, the median delay value of the maximum and minimum delay patterns (corresponding to the patterns of FIGS. 5A and 5C) is adopted.

Further, assuming that the internal delay and on-resistance of the root driver cell are I and R ₀ , respectively, the node number −
Total delay t from 1 to the leaf node with node number e
(-1, e) is calculated as follows.

T (-1, e) = I + w ₁ * R ₀ * C (0) + t (0, e) C (0) = C (1) + c _x * L _x (0,1) + c _y * L _{From y} (0,1) and above, the maximum value T _L (K) and the minimum value T _S (k) of the delay from the node k to the leaf node are: T _L (K) = max (T _L (2 * k) + D (k, 2 * k), _TL (2 * k
+1) + d (k, 2 * k + 1)) T _S (K) = min (T _S (2 * k) + d (k, 2 * k), T _S (2 * k)
+1) + d (k, 2 * k + 1) skew S (k) is determined, from node k for delay to the leaf node as) _{is, S (k) = T L} (k) -T S ( It is expressed as k).

At the input terminal (node number -1) and output terminal (node number 0) of the route driver, T _S (0) = T _S (1) + d (0,1) + w ₁ * R ₀ * C (0) T _L (0) = T _L (1) + d (0,1) + w ₁ * R ₀ * C (0) T _S (-1) = T _S (0) + I T _L (-1) _{= T L (0) + I} S (-1) = S (0) = S (1) = T L (1) a -T _S (1).

It is assumed that the leaf nodes e of the subtree have delays set for the subtrees below the leaf node T _L (e) and T _S (e).

As described above, the delay calculation model can be considered, and the branch point position determining method will be described below using this model.

(2) Method for deciding branch point position in subtree Now, assuming that the position of the node downstream from the node k has already been determined, the position of the node k, that is, the position of the branch point, can be minimized. A method of determining will be described. However, in order to avoid an unnecessary increase in delay due to the bypass wiring and to simplify the calculation, it is selected from the points on the straight line segment connecting the two child node positions. Now, node k
The skew S (k) at is σ (k) = d (k, 2 * k) -d (k, 2 * k + 1) ε (k) = 0.5 * (T _L (2 * k + 1) + T _S (2 * k + 1) −T
_L (2 * k) −T _S (2 * k)) λ (k) = σ (k) −ε (k) μ (k) = 0.5 * (T _L (2 * k + 1) −T _S (2 * k + 1) + T
_{When L} (2 * k) -T _S (2 * k)) = 0.5 * (S (2 * k + 1) + S (2 * k)) is defined, S (k) = _TL (k ) −T _S (k) = max (S (2 * k), S (2 * k + 1), _TL (2 * k) + d (k, 2 * k) -T _S (2 * k + 1) -d (k, 2 * k + 1), T _L (2 * k + 1) + d (k, 2 * k + 1) -T _S (2 * k) -d (k, 2 * k )) = Max (S (2 * k), μ (k) -ε (k) + σ (k), S (2 * k +
1), μ (k) + ε (k) −σ (k)) = max (S (2 * k), S (2 * k + 1), μ (k) + | λ (k) |) To be done.

From the preconditions regarding the processing order, the one that can be changed by the position of the branch point of the node k in this equation is λ (k) or σ (k), and the other terms are known. Therefore, minimizing | λ (k) | will minimize skew.

Here, a point (0≤Z≤ where the position of the node k internally divides the node (2 * k) and the node (2 * k + 1) into Z: (1-Z).
1), the intersection angle between the X axis and the straight line connecting the two child nodes is θ, and the straight line distance between the two child nodes is L,
That is, L = ((L _x (k, 2 * k) + L _x (k, 2 * k + 1)) ² + (L _y (k, 2 * k) + L _y (k, 2 * k + 1) )) ² ) ^1/2 (Fig. 6
L _x (k, 2 * k) = L * Z * | COS (θ) | L _y (k, 2 * k) = L * Z * | SIN (θ) | L _x (k, 2 *) k + 1) = L * (1-Z) * | COS (θ) | L _y (k, 2 * k + 1) = L * (1-Z) * | SIN (θ) | ₁ = w ₁ * L * (C (2 * k) + C (2 * k + 1)) * (r _x * | COS (θ) | + r _y * | SIN (θ) |) β ₂ = ( w ₂ * α _xx * COS ² (θ) + w ₂ * α _yy * SIN ² (θ) + w ₁ * α _xy * | COS (θ) |) * | SIN (θ) |) * 2 * L ² γ = If C (2 * k + 1) / (C (2 * k) + C (2 * k + 1)) 0 <γ <1 is defined, σ (k) = d (k, 2 * k) −d ( k, 2 * k + 1) = w ₁ * r _x * L * | COS (θ) | * (Z * C (2 * k)-(1-Z) * C (2 * k + 1)) + w ₁ * r _y * L * | SIN (θ) | * (Z * C (2 * k)-(1-Z) * C (2 * k + 1)) + w ₁ * α _xy * L ² * (2 * Z -1) * | COS (θ) | * | SIN (θ) | + w ₂ * α _xx * L ² * (2 * Z -1) * COS ² (θ) + w ₂ * α _yy * L ² * (2 * Z-1) * SIN ² (θ) = w ₁ * L * (Z * (C (2 * k) + C (2 * k + 1)) -C (2 * k + 1)) * (r _x * | COS (θ) | + r _y * | SIN (θ) |) + L ² * 2 * (Z-0.5) * (w ₁ * α _xy * | COS (θ) | * | SIN (θ) | + w ₂ * α _xx *
COS ² (θ) + w ₂ * α _yy * SIN ² (θ)) = β ₁ * (Z-γ) + β ₂ * (Z-0.5) λ (k) = (β ₁ + β ₂ ) * Z- (β _{1 * γ + β 2 * 0.5} ) to obtain -ε a (k).

Since λ (k) is a linear function of Z, the following is a Z (parameter for determining the branch point position) that minimizes │λ (k) │ when 0≤Z≤1. You can choose

[0099]

[Equation 3] At this time, the skew at node k is

[Equation 4] Becomes

A branch point is determined at the position k internally divided by Z.

The above is the details of the method for deciding the branch point in the subtree. The greatest feature of this method is that
The point is that the skew can be very small. Because
β ₁ and β ₂ increase about 2 to 4 times each time the depth of the tree increases, so ε near the leaf node
If (k) is relatively small, the above case (c) can be set for each tree depth node, that is, λ (k) = 0, and the skew at the root node is almost the same as the skew near the leaf node. Because you can In particular, if the skew at the leaf node can be set to 0, the skew at the root node can also be set to 0.

(3) Processing Method for Whole Tree Finally, a method for determining the branch point position 27 in the hierarchical binary tree in which the buffer cells 26 are inserted in multiple stages as shown in FIG. 7 will be described. This process is step 1 in FIG.
4 and its flowchart is shown in FIG.
For convenience of explanation, in this hierarchical tree, the hierarchy of the tree driven by the root driver cell 31 is defined as the first hierarchy, and the second hierarchy and the third hierarchy are sequentially counted in the signal propagating direction to directly drive the clusters. The hierarchy of the tree having the buffer cell 26 that is a leaf node as the leaf node is the m-th hierarchy.

First, in step 19, the hierarchy of the subtree to be processed is set to the lowest hierarchy, that is, the mth hierarchy.

In step 20, the branch point position determining process in the subtree is performed on the plurality of subtrees in the hierarchy. At this time, the position of the buffer cell that is the root of the subtree is 2 on the subtree as shown in FIG.
The delay balance point 27 determined based on the positions of the two child nodes is once set.

In the judgment processing of step 21, it is checked whether or not there is an unprocessed subtree in the processing hierarchy, and if there is, the processing of step 20 is repeated, and if not, the processing proceeds to step 22.

In the judgment processing of step 22, it is checked whether or not the hierarchy is the top hierarchy, and if so, the process is exited from the whole of the processing, and if not so, the routine proceeds to step 23.

In step 23, the subtree having the maximum delay among the subtrees of the same hierarchy is examined using the model described above, and the delay value is extracted.

In the following step 24, the position of the buffer cell 35, which is the root node, is shifted as shown in FIG. 9 in subtrees other than the subtree having the maximum delay.
Make sure that the delay values of each tree are aligned. The shift direction is set so as to approach the position of a node having a sibling relationship with the shift node.

At step 25, the process hierarchy is moved up by one, and then the process returns to step 20 to repeat the subsequent processes.

An example of step 24 in this processing will be described below.

[0111] For example, the most delay maximum delay minimum value of the subtree Q with large delay _{^{(Q) T L, (Q}} ) and T _S, the delay maximum delay smallest in processed subtree P in the hierarchy The value is ^(P) _TL , ^(P) T
_{Let S} be a straight line segment (dashed line in FIG. 9) connecting the position 27 of the root node 34 of the subtree sibling to the subtree P and the position 27 of the root node 35 of the subtree P (temporary buffer cell position) 27. , A point (0 ≦ Z ≦ 1) that internally divides the latter and the former into Z: (1-Z) is selected as a new position of the buffer cell 35, and the intersection angle between the straight line and the X axis is θ and the root node is Assuming that the linear distance between them is L, the delay increase amount δ due to the position shift is: δ = w ₁ * L * Z * ^(P) C (0) * (r _x * | COS (θ) | + r _y * | SIN (θ) |) + L ² * Z ² * (w ₁ * α _xy * | COS (θ) | * | SIN (θ) | + w ₂ * α _xx * COS ² (θ) + w ₂ * α _yy ^{* SIN 2 (θ)) +} w 1 * R 0 * L * Z * is _{a) = ζ 1 * Z + ζ} 2 * Z 2 | (c x * | COS (θ) | + c y * | SIN (θ).

Now, in order to align the delay of the subtree P with the delay of the subtree Q, the difference τ = 0.5 * ( ^(Q) T _L + ^(Q) T _S − ^(P) T _L −
^(P) T _S ) should be equal to δ, so the solution of ζ ₂ * Z ² + ζ ₁ * Z−τ = 0 has a positive value, that is,

[Equation 5] The moving position may be determined so that

[0113] _{Here, ζ 1 = w 1 * L} * ((P) C (0) * (r x * | COS (θ) | + r y * | SIN (θ) |) + (c x * | COS (θ) | + _cy * | SIN (θ) |) * R ₀ ) ζ ₂ = L ² * (w ₂ * α _xx * COS ² (θ) + w ₁ * α _xy * | COS (θ) | * | SIN (θ) | + w ₂ * α _yy * SIN ² (θ)).

By doing so, the median delay values of the subtrees of the hierarchy become the same, and therefore, the maximum skew value in the subtree of the hierarchy becomes the maximum skew value of the entire hierarchy below the hierarchy. The maximum and minimum delay values in this hierarchy are set as the initial delay values of the leaf nodes in the subtree of the next higher hierarchy.

The first embodiment according to the first invention has been described above in detail. If the delays in a cluster are the same in all clusters, the skew will be infinitely 0 in all binary trees.
Can be close to. Even if the delays in the cluster vary, if the initial delay of the leaf node in the subtree of the m-th layer is calculated as 0 and the above process is performed, the skew in parts other than in the cluster will be infinitely 0. Since they can be close to each other, the total skew can be suppressed near the maximum value of the intra-cluster skew.

Second Embodiment In the first embodiment, it was assumed that the number of buffer cell insertion stages was specified in advance, but it is also possible to find the optimum number of insertion stages.

First, the maximum value a of the upper limit values of the depth of the subtree to be driven is obtained for each buffer cell type, and the minimum value N _{I of the} number of buffer cell insertion stages is calculated based on this a.
Ask for. Now, assuming that the depth of the entire tree is h, N _I is given by N _I = h / a, and this calculation is performed in step 1 of FIG.

Next, the processing is carried out in accordance with the flowcharts of FIGS. 1 and 2. In step 17, after the judgment processing described in the first embodiment, the number of buffer cell insertion steps is smaller than that when the number of steps is one. Whether or not there is a delay decrease is checked, and if there is a decrease, the number of buffer cell insertion steps is increased by one and the subsequent processing is repeated.
A judgment process of exiting the process of is added.

By making such a correction, the number of buffer cell insertion stages that minimizes the delay can be obtained. Moreover, the buffer cell insertion stages rather than examining the exhaustive from one stage to start from N _I stage, the processing time efficient.

Second Invention The wiring width optimizing method according to the second invention will be described below. Considering the clarity of the explanation, the wiring width determination method in the completely symmetrical path will be described first, then the wiring width determination method in the general path will be described, and finally the actual clock wiring processing flow will be described.

(1) Optimization of Wiring Width of Perfectly Symmetrical Path The completely symmetrical path means a shape in which an H-shaped path as shown in FIG. 10 is recursively repeated.

It is assumed that the wiring width is constant on the path between adjacent branch points and the branch points are fixed. Ideally,
It is better to consider the wiring width to be different at any point on the path, but this only complicates the calculation unnecessarily, so here, the above-mentioned assumption is used to obtain an approximate optimal solution.

Further, in the inter-branch path, the branches corresponding to the same depth on the H-tree have the same line width. This is an assumption to make the delays to each leaf node of the H-tree uniform, that is, to minimize clock skew. At this time, the delay T from the output terminal of the driver cell driving the H-tree to the leaf node of the tree is expressed by the Elmore equation as follows. However, the constant coefficient part is omitted.

[0124]

[Equation 6] C (i) = 2 * (C (i + 1) + c _{i + 1} * l _{i + 1} ) l _2j-1 = l _2j = D * (1/2) ^{j + 1} r _i = H On tree Resistance per unit length of branch path having depth i from root c _i = capacity per unit length of branch path having depth i from root l _i = from root on H tree The wiring length of the branch path whose depth is i is C (i) = the capacitance sum on the H tree downstream from the branch path whose depth is i is Ron = the on resistance of the driver cell D = the target of the tree wiring The length of one side of the square area is usually equal to the input terminal capacitance of the driven cell at the leaf node, but since it is smaller than the wiring capacitance, C (n) = 0
To consider.

Now, if the wiring thickness and the interlayer insulating film thickness are constant,
Assuming that the capacitance between adjacent parallel wirings is small (taking such a sufficient spacing rule), the wiring resistance / capacitance per unit length at the depth i is r _i = ρ / W _i ρ: constant related to resistance c _i = ζ * (W _i + f) ζ: A constant related to the capacity. Here, W _i is the wiring width of depth i, and f
Represents the fringe effect. Substituting this equation into Equation 6, T
Is a function of W _i (i = 1,2, ..., n). Therefore, in order to determine each W _i to minimize T, calculated partial derivatives with respect to W _i T, then it may be determined a solution thereof simultaneous equations become zero.

The partial differentiation is as follows.

[0127]

[Equation 7] Therefore, the solution of the simultaneous equation G _i = 0 (i = 1,2, ..., n) should be obtained, but when G _i = 0 is not satisfied or the solution W _i becomes smaller than the standard line width s. There may be cases.
However, since C (i) is a linear function of W _i , G _i
Is expressed as a positive value by a function of G _i = -A1 * (W _i + A2) / W _i ² + A3 A1, A2, A3: W _j (j ≠ i), and G _i '= A1 * (1 ^{_{/ W i 2 + 2 * A2}} / W i 3)> 0 in other words, since the G _i is in a monotonically increasing function with respect to W _i, G _i = 0 to become a local minimum W _i is only at most one. A meaningful solution can be obtained by G when W _i = s
_This is the case where _i ≦ 0, and conversely, when W _i = s, G _i
When> 0, there is no solution that satisfies W _i ≧ s and G _i = 0, and T increases monotonically, so the minimum value of T is when W _i = s.

From these facts, the problem of finding the minimum value of T is rigorously formulated as follows.

Minimize | G _i | for all i subject to W _i ≧ s That is, the wiring width that minimizes the delay is obtained regardless of the wiring width of any depth i. The constraint condition at this time is not less than the standard wiring width.

Next, the solution to this problem will be described with a specific example.

Now, n = 3, f = s, sRon / ρD = 0.
0537, the solution to the above problem is W ₁ = 4.6
5 * s, W ₂ = 1.4 * s, and W ₃ = s. At this time, T is T = 0.693 * ρζD ² .

By the way, the condition that the wiring width is constant, that is, the minimum value of T when W ₁ = W ₂ = W ₃ is T = 0.97 * ρζD ² The delay can be made smaller by determining the wiring width for each branch wiring path connecting the points.

(2) Wiring Width Determining Method in General Pathway Although a general binary tree type path is an asymmetrical path, the optimum wiring width in this case can also be determined according to the method described above. . However, also here, the wiring width is fixed on the path between the adjacent branch points, and the branch points are fixed. Further, in the path between the branch points, the branches corresponding to the branches at the same depth on the tree have the same line width. The delay from the output terminal of the driver cell driving the tree to the leaf node of the tree is different for each leaf node because the tree is asymmetric. Therefore, in order to minimize the delay, a path path having the maximum delay is found, the wiring width is determined so as to minimize the path delay, and the wiring widths of the other paths are matched with this.

Now, assuming that delay is Tmax, Tma
x becomes a function of W _i like Tmax = Tmax (W ₁ , W ₂ , ..., W _n ) in the same manner as described above. Therefore, the problem of finding the minimum value of Tmax can be formulated as follows in the same manner as described above.

Minimize | ∂Tmax / ∂W _i | for all i subject to W _i ≧ s The method for obtaining this solution is the same as described above. In addition, if the first branch point 4 of the path tree as shown in FIG.
When there is a long path from 5 to the driver cell 46, the wiring width of this portion is set to W _O and Tmax is the same as above.
Then, the optimum wiring width can be calculated by using the above formula as it is.

(3) Clock Wiring Processing Flow A processing flow for actual clock wiring will be described below.

In the clock wiring, the path branch point is determined so as to reduce the skew, but the wiring width needs to be known at that time, and the wiring width is determined so as to reduce the delay. Needs to know the path bifurcation. For this reason, it is difficult to simultaneously determine the path branch point and the wiring width that minimize the skew and the delay. Therefore, the process of fixing one and optimizing the other is repeated, and the path when the delay converges is adopted.

FIG. 12 is a flow chart showing this processing. However, the topology of the path (tree structure) is
It is assumed that it is determined in advance by another method.

First, in step 41, a branch point is calculated assuming a symmetrical path. This means the initial solution of the wiring path.

In the next step 42, the position of the path branch point is fixed and the wiring width is optimized. For this, the above-described optimization method is used.

In step 43, the wiring width of each branch of the path tree is fixed to the value determined in step 42, and the path branch point is recalculated so as to minimize the skew. This method is based on the method disclosed in Japanese Patent Laid-Open No. 3-137851.

In the next judgment processing of step 44, a convergence judgment is made as to whether the variation of the wiring width is within the allowable error range and the variation of the maximum path delay is also within the allowable error range. If it has not converged, the process returns to step 42, and if it has converged, the process ends.

The initial solution may be set by another method. For example, first set the wiring width first, and find the path branch point with the minimum skew under that condition.
This may be used as the initial solution. At this time, s ≦ W _i ≦ max (
s, W _i-1 /2.5), that is, a value that is 0.4 times the average wiring width W _i-1 of the route one level higher than the route and the standard wiring width s for general signals. If the wiring width is determined so as to be less than or equal to the larger value when compared, the processing time until convergence can be shortened.

Further, this wiring width determining method can be applied to the wiring width determination in the binary tree type wiring path structure regardless of the present embodiment.

Third Invention An embodiment in which the automatic wiring method according to the third invention is applied to a computer program for automatic wiring of an integrated circuit will be described below.

The outline of the wiring area is composed of vertical and horizontal line segments. However, the present invention can be applied even when an oblique line segment is used. Further, the present invention is premised on sequential wiring, and an area where wiring has already been made and new wiring is prohibited is registered as a wiring prohibited area. In this embodiment, the wiring area is one layer, but the present invention is of course effective in a multilayer wiring area.

Each wiring request is given at two points: a search start point (hereinafter simply referred to as a start point) and a search end point (hereinafter simply referred to as an end point). In the following, the search will be focused on the search for the tapered wiring path between two given points.

First, how to obtain the wiring width when searching for a new wiring area will be described below.

In the present invention, as shown in FIG. 13, the end of the tapered wiring 81 with the smaller wiring width is the starting point S, and the end with the larger wiring width is the ending point T. The route search is performed from S to T.

The wiring widths in S and T are W _s and W _t , respectively.

Here, with a path length as an axis, and S is 0 and T is 1, a specific function that can determine the wiring width (W _x ) at a point X (0 ≦ X ≦ 1) between S and T (Width
(X)) is given. Furthermore, it is assumed that there is no constriction in the wiring. In other words, the following equation holds.

Arbitrary points A and B between S and T (0≤A≤B≤
For 1), always W _a ≦ W _b (1) For the point X between S and T, the path length between S and X is L _sx , X
When the path length between T and T is L _xt , the value of X is expressed by the following equation.

X = L _sx / (L _sx + L _xt ) (2) Therefore, the wiring width W _x (= Width (X)) at X can also be obtained.

However, at this time, L _sx is obtained within the already searched area, so an accurate value can be obtained, but since the path between X and T has not been determined for L _xt , an accurate value must be calculated. I can't. Therefore, for L _xt , X to T
If the Manhattan distance between them (the shortest path length using only the horizontal path and the vertical path) M _xt is used, an approximate value of W _x can be obtained as a result.

The following formula always holds between L _xt and M _xt .

[0156] When L _xt ≧ M _xt (3) the value of X obtained by using the M _xt and X _m, X _m is expressed by the following equation. X _m = L _sx / (L _sx + M _xt ) (4) At this time, the following equation holds from the equation (3).

X _m = L _sx / (L _sx + M _xt ) ≧ L _sx / (L _sx + L _xt ) = X (5) From the expression (5), the following expression is always satisfied.

X _m ≧ X (6) Here, from Expressions (1) and (6), Width (X _m ) ≧ Width (X) (7), so that Width (X _m ) is guaranteed at the time of wiring. If so, the finally obtained wiring does not violate the design rules. Further, when L _xt = M _xt , X _m = X.
The optimum wiring width can be obtained. After that, Width
(X _m ) will be referred to as a “required wiring width”.

As described above, when searching from S to T, a path search is performed based on Width (X _m ). Since accurate values for both L _sx and L _xt can be calculated in the step of reverse tracing after finding the path, it is necessary to determine the accurate wiring width using Width (X) and obtain the final wiring path. Become.

Although there are vias in the wiring of two or more layers, L _sx is calculated by converting the vias into the corresponding path lengths, while M _xt has the path lengths corresponding to the minimum required vias. By adding, the required wiring width considering the via can be obtained.

First Embodiment An embodiment in which the wiring method according to the third invention is applied to the maze method will be described with reference to FIGS. In this embodiment, each rectangle divided into a grid is a "cell".
Call. The start point and the end point are composed of one or a plurality of cells.

FIG. 14 is a flow chart when the wiring method according to the third invention is applied to the maze method. In the figure, step 51 of inserting a cell including the start point into the heap, step 52 of extracting one cell from the heap, step 55 of checking whether the end point has been found, and insertion of a newly labeled cell into the heap. Step 56 and step 57 of performing reverse tracking to obtain a path are the same procedures as in the conventional maze method.

On the other hand, the step 53 of calculating the necessary wiring width in the taken out cell and the step 54 of recognizing the adjoining cell satisfying the necessary wiring width with the taken out cell are the features of the third invention. Thus, taper wiring can be efficiently performed.

An actual wiring example is shown in FIG. Here, the starting point is S, the ending point is T, and the wiring width is the function Wid.
th (X) = {1 (1-X) + 3X rounding}. In the wiring area, S is a cell 1 × 1
, T occupies the size of the cell 3 × 3. Also,
It is assumed that the length of the path 132 when obtaining the required wiring width is the Manhattan distance based on the number of cells, and the distance to T is the distance to the cell at the center of T. It is assumed that there is a wiring prohibited area 141 in the wiring area.

The inside of the grid set in the wiring area is shown in FIG.
As in the shaded area in (a), the search is performed from S to T.
Here, considering a point X in the middle of the search, a method of obtaining a necessary wiring width in a new wiring area (each cell in this embodiment) including this point X will be described.

In FIG. 15A, the path length of the wiring path 131 already obtained is L _sx = 7, and the path 1 from X to T is 1.
The path length of 33 is L _xt = 20, but it is impossible to find the correct value of L _xt when the search is performed up to X. Therefore, when the value of M _xt = 18 is used and X _m is calculated based on this, X _m = 7 / (7 + 18) = 0.
28. Therefore, the value of Width (X _m ) is 1 (1
The required wiring width at X is 2 because the value is rounded to -X _m ) + 3X _m = 1.56.

Therefore, since the required wiring width in X is two cells, labeling after X is performed in units of two cells.

After the search from S to T is completed, the correct wiring width is determined in the process of reverse tracing from T, and the final path 134 is obtained.
Is obtained (see FIG. 15 (b)).

Second Embodiment An embodiment in which the wiring method according to the third invention is applied to the line segment expansion method will be described with reference to FIGS.

FIG. 16 is a flow chart when the wiring method according to the third invention is applied to the line segment expansion method. In the figure,
Step 61 of generating an auxiliary line segment including the start point in the wiring area and inserting it into the heap, step 62 of extracting one auxiliary line segment from the heap and expanding it in the wiring area, and confirming whether the end point has been found The step 63 to perform and the step 66 to obtain the path by performing the reverse tracking are the same procedures as the conventional line segment expansion method.

On the other hand, the step 64 of calculating the required wiring width in the expanded area and the step 65 of inserting only the new auxiliary line segment satisfying the required wiring width into the heap are the features of the third invention. Thus, taper wiring can be efficiently performed.

An actual wiring example is shown in FIG. The starting point is S and the ending point is T, and the wiring widths of both are W respectively.
_{Let s} and W _t . The wiring width at the point X between S and T is expressed by the formula W
_{idth (X) = W s (} 1-X) + W be assumed that can be obtained by _t X.

Auxiliary line segments are expanded in the wiring area and searched from S to T as indicated by a thick arrow. Here, a method of generating a new auxiliary line segment by considering a point X in the middle of a search and obtaining a necessary wiring width in a new wiring area including the point X (in this embodiment, each line segment development area) will be described.

In FIG. 17A, the wiring path 131 has already been obtained by the line segment expansion indicated by 142, and the candidate auxiliary line segments that can be newly generated are X ₁ and X ₂ in the figure.

When the required wiring widths at X ₁ and X ₂ are estimated using the Manhattan path 132, X ₁ is close to S between ST, but X ₂ is close to T.
Considering that the required wiring width becomes smaller as the tapered wiring becomes closer to S, the required wiring width at X ₁ becomes smaller than the required wiring width at X ₂ .

Here, as shown in FIG. 17A, assuming that a new auxiliary line segment can be generated at the position of X ₁ , but a new auxiliary line segment cannot be generated at X ₂ , according to the design rule, this is Thus, a path search of S → T is performed through X ₁ .

After the search from S to T is completed, the trace is traced back from T while determining the correct wiring width, and the final path 134 is obtained (see FIG. 17B). Path indicated by 135 in the figure is an example of a tapered wire path when passed through the X ₂ but, when determining the shape of the tapered wire to minimize the propagation delay of the electrical signal to think first, the X ₂ Wiring prohibited area 4 at the position
The minimum interval between 1 and 1 cannot be kept.

[0178]

As described above in detail, according to the first aspect of the present invention, branch points for balancing so as to have equal delays can be obtained in the subtrees of each layer, and the difference in delays between layers can be obtained in the buffer cell. It is balanced by adjusting the position of and the addition of bypass wiring near the cell. Therefore, it is possible to distribute the clock signal with high accuracy and minimize the skew, and also to minimize the delay. According to the second invention,
It is possible to obtain a clock wiring path having a skew value close to zero and a minimum delay value. In particular, regarding the delay, the delay due to the wiring can be reduced by about 20 to 30% as compared with the case where the delay is minimized by using a single wiring width within the same net.

Further, according to the third invention, when the tapered wiring is performed, the wiring width is calculated while the wiring width is calculated at any time in the process of searching the path from the end having the small wiring width to the end having the large wiring width. As a result, it is possible to obtain the tapered wiring in consideration of the wiring width in a short time without violating the design rule by only searching the wiring area once.

[Brief description of drawings]

FIG. 1 is a flowchart showing an overall processing procedure in a first embodiment of the first invention.

FIG. 2 is a flowchart showing a processing procedure for forming a binary tree in the first embodiment of the first invention.

FIG. 3 is a flowchart showing a processing procedure for determining a branch point position in a tree in the first embodiment of the first invention.

FIG. 4 is a simplified diagram showing an example of the structure of a subtree.

FIG. 5 is a route diagram showing an example of a wiring pattern having different bent shapes.

FIG. 6 is a conceptual diagram for explaining a branch point position deciding method in a subtree.

FIG. 7 is a simplified diagram showing an example of a tree structure in which buffer cells are inserted in multiple stages.

FIG. 8 is a layout diagram showing an initial setting state of buffer cell layout positions.

FIG. 9 is a layout diagram showing a state after the buffer cell layout position is corrected.

FIG. 10 is a diagram showing an example of an H-tree wiring structure according to a second invention.

FIG. 11 is a diagram showing a general clock tree wiring structure according to a second invention.

FIG. 12 is a diagram showing a processing flow of the second invention.

FIG. 13 shows a typical taper wiring shape example, wiring width,
It is a figure showing the definition of a path length.

FIG. 14 is a flowchart showing a processing procedure of an embodiment in which the automatic wiring method according to the third invention is applied to the maze method.

FIG. 15 is a diagram showing how a path is obtained when the automatic wiring according to the third invention is applied to the maze method.

FIG. 16 is a flowchart showing a processing procedure of an embodiment in which the automatic wiring method according to the third invention is applied to the line segment expansion method.

FIG. 17 is a diagram showing how a path is obtained when the automatic taper wiring according to the third invention is applied to the line segment expansion method.

FIG. 18 is a diagram illustrating an equivalent circuit when the wiring resistance is treated in a distributed constant manner according to the first invention.

[Explanation of symbols]

26 buffer cell 27 branch node of subtree 28 leaf node of subtree 29 parent node of subtree 30 child node of subtree 31 root driver cell 32 chip area 33 buffer cell at m-th stage 34 having maximum delay at the (m-1) -th stage Buffer cell 35 Buffer cell that is not the maximum delay at the (m-1) th stage 45 Driver cell 46 Branching point 81 Tapered wiring shape example 131 Already obtained path between S and X 132 Manhattan path 133 Path between X and T 134 finally obtained path 135 path of design rule violation 141 wiring prohibited area 142 already searched area

Claims (6)

[Claims] 1. When a clock signal is supplied from a root driver cell placed on a semiconductor substrate to a plurality of end cells via a relay buffer cell, a cluster including at least one end cell is generated. Then, the terminal cells are divided into a plurality of groups, a binary tree-like wiring path is generated with the root driver cell as a root node and the cluster as a leaf node, and at a depth of a subtree driven by a relay buffer cell, When the depth is more than the depth, the case of inserting another relay buffer cell in the subsequent stage is to find the depth of the subtree that can reduce the delay time at any point on the downstream side of the subtree depth, and the depth of the subtree. With the upper limit as the upper limit, the relay buffer is located at a portion of the binary tree where the clock signal propagation delay time is minimized. After inserting the cell, calculate the RC delay amount of the path from the branch node to the leaf node in order from the lower branch node of the binary tree, and set the physical position of the branch node so that the difference is minimized. Then, the circuit connection information is updated with the insertion of the relay buffer cell and the cell placement information in the vicinity of this buffer cell is corrected to remove the overlap between cells, and detailed information in each cluster based on the determined placement information. An integrated circuit characterized by deciding the wiring path, deciding the position of each branch node based on the accurate delay amount in the cluster obtained from the decided wiring path, and deciding the detailed wiring path between the branch nodes. Circuit automatic wiring method. 2. In a binary tree type wiring path structure, a wiring delay function having a wiring width of a path between adjacent branch points as a parameter is obtained, and partial derivatives of the delay with respect to each wiring width parameter are further obtained. An automatic wiring method for an integrated circuit, wherein each wiring width is determined so that the absolute value of the partial derivative is minimized within a constraint range in which each wiring width parameter is equal to or larger than the standard wiring width. 3. When the topological structure of the binary tree type wiring path is determined in advance, each wiring width of the path between the adjacent branch points is fixed and branching is performed so that the delay on the downstream side is balanced from each branch point. The first process for minimizing the skew by recursively repeating the process of determining the points from the lower part of the tree to the upper part, and fixing the position of each path branch point by the method according to claim 2. A second process for determining the wiring width to minimize the delay, and a third process for determining whether or not the delay change amount after repeating the first and second processes alternately reaches within an allowable value. An automatic wiring method for an integrated circuit, comprising: a path in which a delay change amount reaches within an allowable value as a final wiring path. 4. An average wiring width of a path between adjacent branch points in a binary tree type wiring path structure is 0 of an average wiring width of a path one layer higher than the path in the binary tree type wiring path structure. An automatic wiring method for an integrated circuit, characterized in that the wiring width is determined so as to be equal to or less than the larger one of the four times the numerical value and the standard wiring width for general signals. 5. An automatic wiring method for an integrated circuit, wherein a route search for a wiring whose wiring width becomes smaller from a signal sending end to a receiving end is performed by sequentially searching a wiring region, and the wiring is made larger from a small wiring width end. An automatic wiring method for an integrated circuit, characterized in that a wiring area is searched toward an edge, and each time a new wiring area is searched, an ideal wiring width in the wiring area is searched for while proceeding with the search. 6. The ideal wiring width in the new wiring area is defined as follows:
It is characterized in that it is obtained based on an accurate wiring path length that has already been obtained and the shortest path length from this new wiring area to the end with the large wiring width using only the horizontal path and the vertical path. Item 6. An automatic wiring method for an integrated circuit according to item 5.