Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
6223328
Ito , ; et al.
April 24, 2001
Title
Wire processing method, wire processing equipment, and recording medium for wire processing program used in designing a large scale integrated circuit
Abstract
The invention concerns a technique of a wiring processing method used in designing, for example, a large scale integrated circuit. The wiring processing method of the invention is provided with: a segment dividing step for dividing a wiring connecting between two receivers of a clock net into three or more segments; an equal delay branch segment determining step for comparing a first delay time from one branch point on one end of the segment to one receiver with a second delay time from the one branch point to the other receiver, and comparing a third delay time from the other branch point on the other end of the segment to the one receiver with a fourth delay time from the other branch point to the other receiver, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment; and an equal delay branch point determining step for determining an equal delay branch point in the equal delay branch segment. Thus, the equal delay branch point is accurately determined, and thereby the clock skew on the clock distributing circuit in a clock synchronous circuit is reduced.
Inventors:
Ito; Noriyuki
(Kawasaki,
JP
)
, Isomura; Tomoyuki
(Kawasaki,
JP
)
, Ikeda; Hiroshi
(Kawasaki,
JP
)
, Tada; Toshihiko
(Kawasaki,
JP
)
Assignee:
Fujitsu, Limited
(Kawasaki,
JP
)
Appl. No.:
896079
Filed:
July 17, 1997
Foreign Application Priority Data
Dec 03, 1996 [JP] 8-323100
Current U.S. Class:
716/6
716/12
Field of Search:
364/488-491 716/6,2,5,7,12
U.S. Patent Documents
5109168
April 1992
Rusu
5198987
March 1993
Shindo et al.
5375069
December 1994
Satoh et al.
5410491
April 1995
Minami
5557779
September 1996
Minami
5651012
July 1997
Jones, Jr.
5656963
August 1997
Masleid et al.
5784289
July 1998
Wang
5787268
July 1998
Sugiyama et al.
Foreign Patent Documents
3-76144
Apr., 1991
JP
5-128214
May., 1993
JP
5-54100
Mar., 1993
JP
Other References
Sato et al "Post-Layout Optimization for Deep Submicron Design," ACM, pp. 1-6, Jan. 1996.
Primary Examiner:
Smith; Matthew
Assistant Examiner:
Siek; Vuthe
Attorney, Agent or Firm:
Armstrong Westerman Hattori McLeland & Naughton, LLP
Claims
What is claimed is:
1. A wire processing method for processing a wiring of clock nets connecting between two receivers on a clock distributing circuit of a clock synchronous circuit in which a clock is to be propagated from an external clock source to the two receivers along opposite routes of the wiring via a tapping point with a minimal delay difference, said method comprising the steps of:
(a) dividing the wiring into three or more series segments by two or more dividing points in such a manner that each segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each segment being different from that of any adjacent segment;
(b) obtaining a delay time of the clock from one dividing point at one end of each said segment to one receiver as a first delay time, a delay time of the clock from said one dividing point to the other receiver as a second delay time, a delay time of the clock from the other driving point at the other end of each said segment to said one receiver as a third delay time, and a delay time of the clock from said other dividing point to said other receiver an a fourth delay time;
(c) comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said segments, one segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located; and
(d) determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the wiring.
2. A wire processing method as claimed in claim 1, wherein the dividing points are physical points on the wiring.
3. A wire processing method as claimed in claim 1, wherein each of the segments is evaluated by a single .PI.-type RC circuit.
4. A wire processing method as claimed in claim 1, wherein in said determining of said equal delay branch segment, the first through the fourth delay time are given by the following equations: ##EQU8##
where
r.sub.i : resistance across a segment
c.sub.j : capacitance at a segment
C.sub.A : capacitance at the one receiver
C.sub.B : capacitance at the other receiver
t.sub.A : delay time by the one receiver
t.sub.B : delay time by the other receiver
k+1: total number of the branch points
k: first number of the branch points forming the equal delay branch segment.
5. A wire processing method as claimed in claim 1, wherein the equal delay branch point in said equal delay branch segment determining step is given by [(t.sub.B -t.sub.A)+.alpha.L(C.sub.B +.beta.L/2)]/[.alpha.L(.beta.K+C.sub.A +C.sub.B)] where
TBL L wiring length between the two receivers .alpha. resistance for a unit length of the wiring .beta. capacitance for a unit length of the wiring C.sub.A capacitance at the one receiver C.sub.B capacitance at the other receiver t.sub.A delay time by the one receiver t.sub.B delay time by the other receiver.
6. A wire processing method for processing a wiring connecting between an external clock source and an equal delay branch point on a clock distributing circuit of a clock synchronous circuit, said method comprising
(a) dividing the wiring into three more series segments by two or more dividing points in such a manner that each segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each segment being different from that of any adjacent segment;
(b) obtaining a delay time of each of said segments;
(c) obtaining a propagation delay time of the wiring based on said delay time of each said segment;
(d) comparing said propagation delay time of the wiring with a preset target value; and
(e) if said propagation delay time does not coincide with said preset target value, adjusting the wire length of an arbitrary one of said segments so as to conform said propagation delay time to said target value.
7. A wire processing method as claimed in claim 6, wherein each of the segments is evaluated by a single .PI.-type RC circuit.
8. A wire processing method for processing a first wiring connecting between two receivers on a clock distributing circuit of a clock synchronous circuit in which a clock is to be propagated from an external clock source to the two receivers along opposite routes of the first wiring via a tapping point with a minimal delay difference, and a second wiring connecting between the external clock source and the tapping point, said method comprising the steps of:
(a) dividing the first wiring into three or more series first segments by two or more first dividing points in such a manner that each first segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each first segment being different from that of adjacent first segment;
(b) obtaining a delay time of the clock from one first dividing point at one end of each said first segment to one receiver as a first delay time, a delay time of the clock from said one first dividing point to the other receiver as a second delay time, a delay time of the clock from the other first dividing point at the other end of each said first segment to said one receiver as a third delay time, and a delay time of the clock from said other first dividing point to said other receiver as a fourth delay time;
(c) comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said first segments, one first segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located;
(d) determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the first wiring via the second wiring;
(e) obtaining a delay time from the equal delay branch point to each of the two receivers as a fifth delay time;
(f) dividing the second wiring into three or more series second segments by two or more second dividing points in such a manner that each second segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each second segment being different from that of any adjacent second segment;
(g) obtaining a sixth delay time of each of said second segments;
(h) obtaining a propagation delay time of the second wiring based on said sixth delay time of each said second segment;
(i) comparing said propagation delay time of the second wiring with a preset target value: and
(j) if said propagation delay time does not coincide with said preset target value, adjusting the wire length of an arbitrary one of said second segments so as to conform said propagation delay time to said target value.
9. A wire processing method as claimed in claim 8, wherein, in said adjusting of said wire length, the sum of the fifth delay time, the propagation delay time, and an external clock delay time at the external clock source is compared with a preset time, and based on the comparison result, the wire length of said arbitrary segment is adjusted.
10. A wire processing method for determining an optimal target path of wiring on a circuit board by a segment search method using flags, comprising the steps of:
(a) dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) providing available flags one at each intersection of the grid for indicating whether an intersection of the grid is available for the wiring, arrival state flags one at each intersection of the grid for indicating whether a search segment has arrived at an intersection of the grid, and arrival direction flags one at each intersection of the grid for indicating a direction in which a search segment has arrived at an intersection of the grid;
(c) carrying out forward search by, for every stage of generation search segments,
(i) generating a search segment so as to cause (1) the arrival state flag of the adjoining intersection to indicate the arrival of the search segment and (2) the arrival direction flag of the same adjoining intersection to indicate the direction of the search, if the available flag of an intersection of the grid adjoining one intersection whose arrival state flag indicates the arrival of a search segment and disposed on a side opposite to the direction of arrival indicated by the arrival direction flag of said one intersection indicates that the adjoining intersection is available and if the available flag of the adjoining intersection indicates that a search segment has not yet arrived, and (ii) repeating these two flag processing procedures in parallel until none of the intersections whose flags each indicate the arrival of the search segment remains; and
(d) carrying out backward search by searching the target path of wiring backwardly from a desired intersection of the grid along the successive arrival direction flags.
11. A wire processing method for determining an optimal target path of wiring on a circuit board by a segment search method using flags, comprising the steps of:
(a) dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) providing arrival direction flags one at each intersection of the grid for indicating two or more directions in which two or more search segments have arrived at an intersection of the grid;
(c) carrying out forward search by causing the arrival direction flag of each said intersection to indicate two or more directions of arrival of the search segments;
(d) carrying out backward search by searching candidate paths backwardly from a desired intersection of the grid in accordance with the indicated directions of the arrival direction flags; and
(e) selecting one path, among said two or more candidate paths, as the optimal target path of wiring.
12. A wire processing equipment for processing a wiring of clock nets connecting between two receivers on a clock distributing circuit of a clock synchronous circuit in which a clock is to be propagated from an external clock source to the two receivers along opposite routes of the wiring via a tapping point with a minimal delay difference, said equipment comprising:
(a) a segment dividing processor for dividing the wiring into three or more series segments by two or more dividing points in such a manner that each segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each segment being different from that of any adjacent segment;
(b) means for obtaining a delay time of the clock from one dividing point at one end of each said segment to one receiver as a first delay time, a delay time of the clock from said one dividing point to the other receiver as a second delay time, a delay time of the clock from the other driving point at the other end of each said segment to said one receiver as a third delay time, and a delay time of the clock from said other dividing point to said other receiver as a fourth delay time;
(c) means for comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said segments, one segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located; and
(d) an equal delay branch point determining processor for determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the wiring.
13. A wire processing equipment for processor processing a wiring connecting between an external clock source and an equal delay branch point on a clock distributing circuit of a clock synchronous circuit, said equipment comprising:
(a) a segment dividing processor for dividing the wiring into three or more series segments by two or more dividing points in such a manner that each of said segments is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each segment being different from that of any adjacent segment;
(b) means for obtaining a delay time of each of said segments;
(c) a propagation delay time determining processor for obtaining a propagation delay time of the wiring based on said delay time of each said segment;
(d) means for comparing said propagation delay time of the wiring with a preset target value; and
(e) a wiring length adjusting processor for determining if said propagation delay time does not coincide with said preset target value, and adjusting the wire length of an arbitrary one of said segments so as to conform said propagation delay time to said target value.
14. A wire processing equipment for processing a first wiring connecting between two receivers on a clock distributing circuit of a clock synchronous circuit in which a clock is to be propagated from an external clock source to the two receivers along opposite routes of the first wiring via a tapping point with a minimal delay difference, and a second wiring connecting between the external clock source and the tapping point, said equipment comprising:
(a) a first segment dividing processor for dividing the first wiring into three or more series first segments by two or more first dividing points in such a manner that each first segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each first segment being different from that of any adjacent segment;
(b) means for obtaining a delay time of the clock from one first dividing point at one end of each said first segment to one receiver as a first delay time, a delay time of the clock from said one first dividing point to the other receiver as a second delay time, a delay time of the clock from the other first dividing point at the other end of each said first segment to said one receiver as a third delay time, and a delay time of the clock from said other first dividing point to said other receiver as a fourth delay time;
(c) a propagation delay time determining processor for comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said first segments, one first segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located;
(d) an equal delay branch point determining processor for determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the first wiring via the second wiring;
(e) a delay time determining processor for obtaining a delay time from the equal delay branch point to each of the two receivers as a fifth delay time;
(f) a second segment dividing processor for dividing the second wiring into three or more series second segments by two or more second dividing points in such a manner that each of said second segments is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each first segment being different from that of any adjacent segment;
(g) means for obtaining a sixth delay time of each of said second segments;
(h) a propagation delay time determining processor for obtaining a propagation delay time of the second wiring based on said sixth delay time of each said second segment;
(i) means for comparing said propagation delay time of the second wiring with a preset target value; and
(j) a wiring length adjusting processor for determining if said propagation delay time does not coincide with said preset target value, and adjusting the wire length of an arbitrary one of said second segments so as to confirm said propagation delay time to said target value.
15. A wire processing equipment for determining an optimal target path of wiring on a circuit board by a segment search method using flags, said equipment comprising:
(a) means for dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) means for providing available flags one at each intersection of the grid for indicating whether an intersection of the grid is available for the wiring, arrival state flags one at each intersection of the grid for indicating whether a search segment has arrived at an intersection of the grid, and arrival direction flags one at each intersection of the grid for indicating a direction in which a search segment has arrived at an intersection of the grid;
(c) a forward searching processor for carrying out forward search by, for every stage of generation search segments,
(i) generating a search segment so as to cause (1) the arrival state flag of the adjoining intersection to indicate the arrival of the search segment and (2) the arrival direction flag of the same adjoining intersection to indicate the direction of the search, if the available flag of an intersection of the grid adjoining one intersection whose arrival state flag indicates the arrival of a search segment and disposed on a side opposite to the direction of arrival indicated by the arrival direction flag of said one intersection indicates that the adjoining intersection is available and if the available flag of the adjoining intersection indicates that a search segment has not yet arrived, and (ii) repeating these two flag processing procedures in parallel until none of the intersections whose flags each indicate the arrival of the search segment remains; and
(d) a backward searching processor for carrying out backward search by searching the target path of wiring backwardly from a desired intersection of the grid along the successive arrival direction flags.
16. A wire processing equipment for determining an optimal target path of wiring on a circuit board by a segment search method using flags, said equipment comprising:
(a) means for dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) means for providing arrival direction flags one at each intersection of the grid for indicating two or more directions in which two or more search segments have arrived at an intersection of the grid;
(c) a forward search processor for carrying out forward search by causing the arrival direction flag of each said intersection to indicate two or more directions of arrival of the search segments;
(d) a backward searching processor for carrying out backward search by searching candidate paths backwardly from a desired intersection of the grid in accordance with the indicated directions of the arrival direction flags; and
(e) an optimum wiring path determining processor for selecting one path, among said two or more candidate paths, as the optimal target path of wiring.
17. A recording medium for a wiring processing program in which a wiring program is stored, whereby a computer executes:
(a) a segment dividing procedure for dividing the wiring into three or more series segments by two or more dividing points in such a manner that each segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each segment being different from that of any adjacent segment;
(b) a procedure for obtaining a delay time of the clock from one dividing point at one end of each said segment to one receiver as a first delay time, a delay time of the clock from said one dividing point to the other receiver as a second delay time, a delay time of the clock from the other driving point at the other end of each said segment to said one receiver as a third delay time, and a delay time of the clock from said other dividing point to said other receiver as a fourth delay time;
(c) a procedure for comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said segments, one segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located; and
(d) an equal delay branch point determining procedure for determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the wiring.
18. (Amended) A recording medium for a wiring processing program in which a wiring program is stored, whereby a computer executes:
(a) a segment dividing procedure for dividing the wiring into three or more series segments by two or more dividing points in such a manner that each of said segments is substantially uniform in impedance per unit length segment along its entire length, the impedance per unit length of each segment being different from that of any adjacent;
(b) a procedure for obtaining a delay time of each of said segments;
(c) a propagation delay time determining procedure for obtaining a propagation delay time of the wiring based on said delay time of each said segment;
(d) a procedure for comparing said propagation delay time of the wiring with a preset target value; and
(e) a wiring length adjusting procedure for determining if said propagation delay time does not coincide with said preset target value, and adjusting the wire length of an arbitrary one of said segments so as to conform said propagation delay time to said target value.
19. A recording medium for a wiring processing program in which a wiring program is stored, whereby a computer executes:
(a) a first segment dividing procedure for dividing the first wiring into three or more series first segments by two or more first dividing points in such a manner that each first segment is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each first segment being different from that of any adjacent first segment;
(b) a procedure for obtaining a delay time of the clock from one first dividing point at one end of each said first segment to one receiver as a first delay time, a delay time of the clock from said one first dividing point to the other receiver as a second delay time, a delay time of the clock from the other first dividing point at the other end of each said first segment to said one receiver as a third delay time, and a delay time of the clock from said other first dividing point to said other receiver as a fourth delay time;
(c) a propagation delay time determining procedure for comparing said first delay time with said second delay time to obtain a first delay difference and also comparing said third delay time with said fourth delay time to obtain a second delay difference, and determining, among said first segments, one first segment in which the sign of a resultant value of subtraction of said first delay difference from said second delay difference is inverted from positive to negative or vice versa, as an equal delay segment on which the tapping point is to be located;
(d) an equal delay branch point determining procedure for determining an equal delay branch point in said equal delay segment as the tapping point via which the external clock source is to be connected to the first wiring via the second wiring;
(e) a delay time determining procedure for obtaining a delay time from the equal delay branch point to each of the two receivers as a fifth delay time;
(f) a second segment dividing procedure for dividing the second wiring into three or more series second segments by two or more second dividing points in such a manner that each of said second segments is substantially uniform in impedance per unit length along its entire length, the impedance per unit length of each first segment being different from that of any adjacent first segment;
(g) a procedure for obtaining a sixth delay time of each of said second segments;
(h) a propagation delay time determining procedure for obtaining a propagation delay time of the second wiring based on said sixth delay time of each said second segment;
(i) a procedure for comparing said propagation delay time of the second wiring with a preset target value; and
(j) a wiring length adjusting procedure for determining if said propagation delay time does not coincide with said preset target value, and adjusting the wire length of an arbitrary one of said second segments so as to confirm said propagation delay time to said target value.
20. A recording medium for a wiring processing program in which a wiring program is stored, whereby a computer executes:
(a) a procedure for dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) a procedure for providing available flags one at each intersection of the grid for indicating whether an intersection of the grid is available for the wiring, arrival state flags one at each intersection of the grid for indicating whether a search segment has arrived at an intersection of the grid, and arrival direction flags one at each intersection of the grid for indicating a direction in which a search segment has arrived at an intersection of the grid;
(c) a forward searching procedure for carrying out forward search by, for every stage of generation search segments,
(i) generating a search segment so as to cause (1) the arrival state flag of the adjoining intersection to indicate the arrival of the search segment and (2) the arrival direction flag of the same adjoining intersection to indicate the direction of the search, if the available flag of an intersection of the grid adjoining one intersection whose arrival state flag indicates the arrival of a search segment and disposed on a side opposite to the direction of arrival indicated by the arrival direction flag of said one intersection indicates that the adjoining intersection is available and if the available flag of the adjoining intersection indicates that a search segment has not yet arrived, and (ii) repeating these two flag processing procedures in parallel until none of the intersections whose flags each indicate the arrival of the search segment remains; and
(d) a backward searching procedure for carrying out backward search by searching the target path of wiring backwardly from a desired intersection of the grid along the successive arrival direction flags.
21. A recording medium for a wiring processing program in which a wiring program is stored, whereby a computer executes:
(a) a procedure for dividing a wiring area of the circuit board into a grid by units of a minimum pitch of the wiring;
(b) a procedure for providing arrival direction flags one at each intersection of the grid for indicating two or more directions in which two or more search segments have arrived at an intersection of the grid;
(c) a forward search procedure for carrying out forward search by causing the arrival direction flag of each said intersection to indicate two or more directions of arrival of the search segments;
(d) a backward searching procedure for carrying out backward search by searching candidate paths backwardly from a desired intersection of the grid in accordance with the indicated directions of the arrival direction flags; and
(e) an optimum wiring path determining procedure for selecting one path, among said two or more candidate paths, as the optimal target path of wiring.
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a wiring processing method, wiring processing equipment, and recording medium for a wiring processing program suitable for use in designing a large scale integrated circuit (LSI) using the computer aided design (CAD) system.
In clock nets on a clock distributing circuit of a clock synchronous circuit, to equalize the delay time (propagation delay time of a clock) from a clock generator (driver) to each of clock receivers, namely, to decrease a clock skew being a difference of a clock propagation delay time is a very important technique for stabilizing the operation of the clock distributing circuit. If the clock skew is large, the receivers on the nets will have a problem with synchronizing operation on the nets; and therefore, the clock skew of the clock distributing circuit has to be reduced.
Further, to minimize the lengths of wirings to connect circuit elements on an LSI and to enhance quality of wiring is necessary to speed up the processes in the LSI.
In this case, to estimate a possibility of a wiring before executing the wiring and from the possibility to improve a layout of the circuits and to optimize a wiring area should also be considered.
Especially at present, a wiring objective is inclined to have a gigantic scale, and an early estimation and evaluation of the possibility of wirings has increased the need.
2. Description of the Related Art
There have been many reports on the wiring processing method for reducing the clock skew, namely, a difference of a clock propagation delay time in the clock synchronous circuit.
The IBM method will hereunder be described which is a typical wiring processing method for reducing the clock skew. This method is detailed in `Ren-Song Tsay, "Exact zero skew", Proc. IEEE Int. Conference on CAD, pp336-339, 1991`.
Before explaining the wiring processing method for reducing a clock skew, first, FIG. 34 illustrates a configuration of a clock tree in a clock net on a clock distributing circuit of a clock synchronous circuit.
A clock tree 130 comprises a sub-clock tree consisting of a clock receiver (receiving circuit) 112 and a wiring 118 and another sub-clock tree consisting of a clock receiver (receiving circuit) 115 and a wiring 121, which are connected at an equal delay branch point (tapping point) "x" where the sub-clock trees have an equal delay.
Thus, in the clock tree 130, a clock driver (clock generator) not illustrated in FIG. 34 supplies a clock signal to the receiver 112 and 115 through the equal delay branch point "x".
Here, the receiver 112 is composed of a flip-flop (time constant t.sub.1) 113 and a capacitor (capacitance C.sub.1) 114, and the receiver 115 is composed of a flip-flop (time constant t.sub.2) 116 and a capacitor (capacitance C.sub.2) 117.
The wire 118 forms a .PI. type RC circuit consisting of one resistor (resistance r.sub.1) 119 and two capacitors (capacitance c.sub.1 /2) 120.
Further, in the same manner as the wire 118, the wire 121 also forms the .PI. type RC circuit consisting of one resistor (resistance r.sub.2) 122 and two capacitors (capacitance c.sub.2 /2) 123.
Here, the reason that a wiring between the receiver 112 and 115 is represented by means of the one .PI. type RC circuit in FIG. 34 will now be described.
First, a close look at one sub-clock tree is requested.
FIG. 32 illustrates a model for a clock tree with a buffer, and as shown in this figure, the clock tree with a buffer 100 comprises a clock generator (clock source) 101 as the driver, a clock receiver (latch) 103 as the receiver, and a buffer 102
through which the former two are connected.
Here, the clock source 101 is connected to the buffer 102 through a wire 104 and the buffer 102 is connected to the latch 103 through the wire 105.
This clock tree 100 has a configuration as shown in FIG. 33 in detail.
The clock source 101 has a resistor (resistance r.sub.s) 106; the buffer 102 has a delay circuit (internal delay time d.sub.b) 111, a resistor (resistance r.sub.b) 107, and a capacitor (capacitance c.sub.b) 109; the latch 103 has a capacitor (capacitance c.sub.1) 110.
The delay time from the clock source 101 to the latch 103 includes the delay time due to the wiring resistors and capacitors of the wiring 104 and 105, and the internal delay time d.sub.b by the delay circuit 111 of the buffer 102.
The wiring resistor has become a big problem as not negligible, since the size of transistors and the cross-sectional area of wirings have decreased owing to the recent progress in the semiconductor microstructuring technique.
Accordingly, it has become necessary to deal with the wiring 104 and 105 as a distributed constant circuit from accuracy for estimating the delay time. Generally, as shown in FIG. 33, the wiring 104 and 105 have been evaluated by means of the .PI. type RC circuit composed of one resistor (resistance r.sub.s) 106 and two capacitors (capacitance c.sub.1 /2) 108 as a concentrated constant circuit being a typical form of the distributed constant circuit.
Incidentally, the equal delay branch point "x" is an input point of a clock from the driver (clock generator) not illustrated in FIG. 34.
In the clock tree 130 shown in FIG. 34, the clock skew by the two sub-clock trees of the clock tree 130 varies depending on the position of the equal delay branch point "x". Therefore, the position of the equal delay branch point "x" has to be set very accurately so as to reduce the clock skew in the clock tree 130.
According to the method (zero-skew-merge) to determine the equal delay branch point "x" in the wiring between the two sub-clock trees, the equal delay branch point "x" is known to satisfy the following equation.
Where L, .alpha., .beta. are given as below,
L: wiring length between the two sub-clock trees
.alpha.: resistance for unit length of the line
.beta.: capacitance for unit length of the line the equal delay branch point "x" is determined by the following:
Incidentally, circuits on an LSI are connected through optimum wiring paths searched by means of an automatic wiring system.
There have been many reports on the automatic searching method for wiring paths, and the Mikami-Tabuchi method as a kind of the line segment searching method will hereafter be described.
The line segment searching method is a method to search wiring paths while sequentially generating vertical or horizontal probes, which has an advantage in a high speed processing with a small storage capacity.
In the Mikami-Tabuchi method, as shown in FIG. 35, first, temporal line segments of level 0 are generated in the horizontal direction from the search start point S and the search end point T. Where there is no overlapping with these temporal line segments, next, temporal line segments of level 1 intersecting vertically to the line segments of level 0 are generated.
And, repeating these steps, when the temporal line segments from both sides intersect, the intersecting line segments are searched backward, thereby finding a wiring path, for example, as shown in FIG. 36.
The Mikami-Tabuchi method can find a wiring path invariably where there is a wiring path, however, the number of the temporal line segments increases rapidly as the level increases, and in the worst case, as many temporal line segments as the number of the grids have to be searched. Thus, the method is applied wherein the level number of the temporal line segments is limited to, for example, 2 or 3.
However, in the clock tree 130 as shown in FIG. 34, the foregoing wiring 118 and 121 each are evaluated by means of a single .PI. type RC circuit (.PI. type RC model).
This is because the resistance and capacitance for each unit grid in the wiring on both sides of the equal delay branch point x are assumed equal regardless of the position in determining the equal delay branch point "x".
However in reality, it is impossible that the resistance and capacitance for each unit grid are equal regardless of the position; and therefore, it becomes necessary to determine the equal delay branch point "x" from the evaluation of a series .PI. type RC circuit (series .PI. type RC model) obtained by dividing the wiring 118 and 121 into a plurality of segments, which will be a problem to be solved.
Furthermore, in the clock tree 130 as shown in FIG. 34, there is another problem in determining the equal delay branch point "x" that the delay time from the clock driver to each of the clock receivers has to be set to a target value while considering gate delays (extra-source gate delay) increased by applying loads to the clock driver not illustrated.
In the Mikami-Tabuchi method being one method for automatic searching for wiring paths, the temporal line segments (search segments) of the same level are processed without influencing each other, and therefore, it is possible to speed up the search for the line segments when the processing of search segments can be executed in parallel.
However, in the Mikami-Tabuchi method, since a point once searched is not searched again, and when a wiring path not optimum is searched before an optimum wiring path is searched, the wiring path not optimum can possibly be selected, which is another problem.
Accordingly, to solve the problem requires a method whereby a plurality of wiring paths can be searched and an optimum wiring path can be selected therefrom.
Further as mentioned above, if the possibility of wiring can be estimated before executing a wiring in the design of an LSI, it will be possible to improve the layout of a circuit and to optimize a wiring area from the possibility of wiring.
However, it is difficult to know the wiring possibility of a wiring objective when finishing the layout of a circuit, and there is a problem that the wiring possibility cannot be known before finishing the wiring.
SUMMARY OF THE INVENTION
The present invention has been made in view of the foregoing problems, and it is therefore an object of the present invention to provide a wiring processing method suitable for use in the design of an LSI using the CAD. More concretely, it is an object to provide a wiring processing method and wiring processing equipment, whereby the clock skew of a clock distributing circuit can be reduced through determining an equal delay branch point (tapping point) and taking an external clock delay time into account, the processing speed can be increased through performing a parallel processing of search segments in searching wiring paths, the lengths of wirings connecting to the circuits on an LSI can be minimized and the quality of wiring can be improved through selecting optimum wiring paths, and the layout of the circuits on an LSI can be improved and the wiring areas can be optimized through estimating the wiring possibility before executing wiring. It is further an object to provide a recording medium in which a wiring processing program is recorded for a computer executing the procedure of the aforementioned wiring processing.
In order to accomplish the foregoing objects, a wiring processing method of the invention comprises: a segment dividing step for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more dividing points; an equal delay branch segment determining step for comparing a first delay time from one dividing point on one end of the segment obtained by the segment dividing step to one receiver of the two receivers with a second delay time from the one dividing point to the other receiver of the two receivers, and comparing a third delay time from the other dividing point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other dividing point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; and an equal delay branch point determining step for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining step.
The abovementioned dividing points set by the segment dividing step may be physical points on the wiring, or points at which an impedance for a unit length of the wiring changes. And, the segments obtained by the segment dividing step can be evaluated by means of a single .PI. type circuit.
Further, the first through the fourth delay time in the foregoing equal delay branch segment determining step can be obtained by the following equations: ##EQU1##
here,
r.sub.i : resistance across a segment
c.sub.j : capacitance at a segment
C.sub.A : capacitance at the one receiver
C.sub.B : capacitance at the other receiver
t.sub.A : delay time by the one receiver
t.sub.B : delay time by the other receiver
n+1: total number of the dividing points
k: first number of the dividing points forming the equal delay branch segment.
Further, the equal delay branch point in the equal delay branch segment determining step can be obtained by
here,
L: wiring length between the two receivers
.alpha.: resistance for a unit length of the wiring
.beta.: capacitance for a unit length of the wiring
C.sub.A : capacitance at the one receiver
C.sub.B : capacitance at the other receiver
t.sub.A : delay time by the one receiver
t.sub.B : delay time by the other receiver.
Accordingly, in the wiring processing method of the invention, a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit is divided into three or more segments in obtaining an equal delay branch point, thereby, the equal delay branch point can accurately be obtained taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions. Therefore, the clock skew being a difference of a clock propagation delay in the clock synchronous circuit can be reduced.
According to another aspect of the invention, the wiring processing method comprises: a segment dividing step for dividing a wiring on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more dividing points; a propagation delay time determining step for obtaining a propagation delay time of the wiring in which the delay time of each of the segments obtained by the segment dividing step is taken into account; and a wiring length adjusting step for comparing the propagation delay time of the wiring obtained by the propagation delay time determining step with a preset time, and on the basis of the comparison result, adjusting a wiring length for each of the segments.
Further, the dividing points set by the foregoing segment dividing step may be points at which an impedance for a unit length of the wiring changes.
Furthermore, the segments obtained by the segment dividing step can be evaluated by means of a single .PI. type circuit.
Accordingly, in the wiring processing method of the invention, a wiring on a clock distributing circuit of a clock synchronous circuit is divided into three or more segments to adjust a wiring length for each segment, thereby, a delay time to each of the receivers can be made equal taking an external clock delay time into account. Therefore, the clock skew being a difference of a clock propagation delay in the clock synchronous circuit can be reduced.
According to another aspect of the invention, the wiring processing method comprises: a first segment dividing step for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more dividing points; an equal delay branch segment determining step for comparing a first delay time from one dividing point on one end of the segment obtained by the first segment dividing step to one receiver of the two receivers with a second delay time from the one dividing point to the other receiver of the two receivers, comparing a third delay time from the other dividing point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other dividing point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; an equal delay branch point determining step for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining step; a delay time determining step for obtaining a fifth delay time from the equal delay branch point obtained by the equal delay branch point determining step to each of the receivers; a second segment dividing step for setting two or more dividing points on a wiring from the equal delay branch point through an external clock source gate and dividing the wiring into three or more segments; a propagation delay time determining step for obtaining a propagation delay time of the wiring in which the delay time of each of the segments obtained by the second segment dividing step is taken into account, and a wiring length adjusting step for comparing the sum of the fifth delay time from the equal delay branch point to each of the receivers obtained by the delay time determining step and the propagation delay time of the wiring obtained by the propagation delay time determining step with a preset time, and on the basis of the comparison result, adjusting a wiring length for each segment.
In the foregoing wiring length adjusting step, the sum of the fifth delay time, the propagation delay time, and an external clock delay time at the external clock source gate is compared with a preset time, and on the basis of the comparison result, a wiring length may be adjusted for each segment.
Accordingly, in the wiring processing method of the invention, a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit is divided into three or more segments to obtain an equal delay branch point and the length of a wiring from the equal delay branch point to an external clock source gate is adjusted for each segment while dividing the wiring into more than three segments. Thereby, the equal delay branch point can accurately be obtained taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions, and a delay time to each of the receivers can be made equal taking an external clock delay time into account. Therefore, the clock skew being a difference of a clock propagation delay time in the clock synchronous circuit can effectively be reduced.
According to another aspect of the invention relating to the wiring processing method, in determining a wiring path of a wiring on a circuit board, a wiring area is in advance divided into grids by a unit of a minimum pitch of the wiring, and an available flag to indicate whether a grid is available for the wiring or not, an arrival state flag to indicate that a search segment arrives at the grid, and an arrival direction flag to indicate a direction in which the search segment arrives at the grid are provided. With this provision, the wiring processing method comprises a forward search processing step that, when the available flag indicates an available state and the arrival flag indicates a non-arrival state of the search segment as for an adjoining grid next to the grid at which the arrival state flag indicates an arrival of the search segment, executes in parallel an adjoining grid flag processing procedure to set the arrival state flag at the adjoining gird to the arrival state of the search segment and to make the arrival direction flag at the adjoining grid to indicate a search direction of the search segment, and further repeats the adjoining grid flag processing procedure as to each of the search segments until the grid requiring the arrival state flag to indicate the arrival state of the search segment comes into nonexistence. The wiring processing method further comprises a backward search processing step for searching, after the forward search processing step, a wiring path backward from a desired grid in compliance with the arrival direction flag.
Therefore, in the wiring processing method of the invention, the parallel processing of the foregoing adjoining grid flag processing procedure can increase the speed of the operation in the forward search processing step, thus significantly reducing time for searching the wiring paths.
According to another aspect of the invention relating to the wiring processing method, in determining a wiring path of a wiring on a circuit board, a wiring area is in advance divided into grids by a unit of a minimum pitch of the wiring and an arrival direction flag to indicate a direction in which a search segment arrives at a grid is provided. The wiring processing method further comprises: a forward search processing step for searching each of the grids forward, while indicating a plurality of search directions of the search segments on the arrival direction flag; a backward search processing step for searching, after the forward search processing step, a plurality of wiring paths backward from a desired grid in compliance with the arrival direction flag; and an optimum wiring path determining step for determining an optimum wiring path out of a plurality of wiring paths obtained by the backward search processing step.
Accordingly, in the wiring processing method of the invention, a plurality of search directions are indicated on the arrival direction flag as for each of the grids, and thereby a plurality of wiring paths can be searched and an optimum wiring path can be selected therefrom. Therefore, it is possible to enhance quality of the wiring while minimizing a wiring length.
According to another aspect of the invention, the wiring processing method is provided with: a circuit layout determining step for determining a layout of circuits on a circuit board; and a wiring congestion degree evaluating step for evaluating, after the circuit layout determining step determines the layout of the circuits, a wiring congestion degree of a wiring from the (L-G)/L, in which L is a total wiring length of a wiring to connect the circuits, G is a number of dots used for the wiring.
Accordingly, in the wiring processing method of the invention, the wiring congestion degree of a circuit can be estimated for a wiring possibility at the finishing stage of a layout of a circuit before executing the wiring. Therefore, the estimation and evaluation of the wiring possibility becomes possible at an early stage, which is requested as wiring objectives become increasingly big.
The wiring processing equipment of the invention is provided with: a segment dividing processor for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; an equal delay branch segment determining processor for comparing a first delay time from one branch point on one end of the segment obtained by the segment dividing processor to one receiver of the two receivers with a second delay time from the one branch point to the other receiver of the two receivers, and comparing a third delay time from the other branch point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other branch point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; and an equal delay branch point determining processor for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining processor.
Accordingly, in the wiring processing equipment of the invention, the equal delay branch point can accurately be obtained taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions. Therefore, the clock skew being a difference of a clock propagation delay in the clock synchronous circuit can be reduced.
According to another aspect of the invention, the wiring processing equipment is provided with: a segment dividing processor for dividing a wiring on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; a propagation delay time determining processor for obtaining a propagation delay time of the wiring in which a delay time of each of the segments obtained by the segment dividing processor is taken into account; and a wiring length adjusting processor for comparing a propagation delay time of the wiring obtained by the propagation delay time determining processor with a preset time, and on the basis of the comparison result, adjusting a wiring length for each of the segments.
Accordingly, in the aforementioned wiring equipment of the invention, a delay time to each of the receivers can be made equal taking an external clock delay time into account, thereby reducing the clock skew being a difference of a clock propagation delay time in the clock synchronous circuit.
According to another aspect of the invention, the wiring processing equipment is provided with: a first segment dividing processor for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; an equal delay branch segment determining processor for comparing a first delay time from one branch point on one end of the segment obtained by the first segment dividing processor to one receiver of the two receivers with a second delay time from the one branch point to the other receiver of the two receivers, comparing a third delay time from the other branch point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other branch point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; an equal delay branch point determining processor for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining processor; a delay time determining processor for obtaining a fifth delay time from the equal delay branch point obtained by the equal delay branch point determining processor to each of the receivers; a second segment dividing processor for setting two or more branch points on a wiring from the equal delay branch point through an external clock source gate and dividing the wiring into three or more segments; a propagation delay time determining processor for obtaining a propagation delay time of the wiring in which the delay time of each of the segments obtained by the second segment dividing processor is taken into account; and a wiring length adjusting processor for comparing the sum of the fifth delay time from the equal delay branch point to each of the receivers obtained by the delay time determining processor and the propagation delay time of the wiring obtained by the propagation delay time determining processor with a preset time, and on the basis of the comparison result, adjusting a wiring length for each segment.
Accordingly, in the wiring processing equipment of the invention, the equal delay branch point can accurately be obtained taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions, and a delay time to each of the receivers can be made equal taking an external clock delay time into account. Therefore, the clock skew being a difference of a clock propagation delay time in the clock synchronous circuit can effectively be reduced.
According to another aspect of the invention, the wiring processing equipment is provided with: a forward searching processor that, as for an adjoining grid next to a grid at which an arrival state flag for indicating an arrival of a search segment at the grid obtained by dividing a wiring area into grids by a unit of a minimum pitch of a wiring on a circuit board indicates an arrival of the search segment, when an available flag for indicating whether a grid is available for a wiring or not indicates an available state and the arrival state flag indicates a non-arrival state of the search segment, executes in parallel an adjoining grid flag processing procedure that sets the arrival state flag at the adjoining gird to the arrival state of the search segment and makes an arrival direction flag for indicating an arrival direction of a search segment at the adjoining grid to indicate a search direction thereof, and further repeats the adjoining grid flag processing procedure as to each of the search segments until the grid requiring the arrival state flag to indicate the arrival state of the search segment comes into nonexistence; and a backward searching processor for searching backward, after the forward search processing finishes, a wiring path backward from a desired grid in compliance with the arrival direction flag.
Accordingly, the operation in the foregoing forward search processing procedure can be performed in an increased speed by the parallel processing, thus significantly reducing time for searching the wiring paths.
According to another aspect of the invention, the wiring processing equipment is provided with: a forward searching processor for searching forward each grid obtained by dividing a wiring area into grids by a unit of a minimum pitch of a wiring on a circuit board, while indicating a plurality of search directions of the search segments on an arrival direction flag for indicating a direction in which a search segment arrives at the grid; a backward searching processor for searching, after the forward search processing, a plurality of wiring paths backward from a desired grid in compliance with the arrival direction flag; and an optimum wiring path determining processor for determining an optimum wiring path out of a plurality of wiring paths obtained by the backward searching processor.
Accordingly, in the wiring processing equipment of the invention, a plurality of wiring paths can be searched and an optimum wiring path can be selected therefrom, thus enhancing quality of the wiring while minimizing a wiring length.
According to another aspect of the invention, the wiring processing equipment is provided with: a circuit layout determining processor for determining a layout of circuits on a circuit board; and a wiring congestion degree evaluating processor for evaluating, after the circuit layout determining processor determines a layout of the circuits, a wiring congestion degree of a wiring from the (L-G)/L, in which L is a total wiring length of the wiring to connect the circuits, G is a number of dots used for the wiring.
Accordingly, in the wiring processing equipment of the invention, the wiring congestion degree of a circuit can be estimated for a wiring possibility at the finishing stage of a layout of a circuit before executing the wiring. Therefore, the estimation and evaluation of the wiring possibility becomes possible at an early stage, which is requested as wiring objectives become increasingly big.
The recording medium for a wiring processing program according to the invention is characterized in that a wiring processing program is stored, whereby a computer executes: a segment dividing procedure for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; an equal delay branch segment determining procedure for comparing a first delay time from one branch point on one end of the segment obtained by the segment dividing procedure to one receiver of the two receivers with a second delay time from the one branch point to the other receiver of the two receivers, and comparing a third delay time from the other branch point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other branch point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; and an equal delay branch point determining procedure for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining procedure.
Accordingly, in the recording medium for a wiring processing program of the invention, the equal delay branch point can accurately be determined taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions. Therefore, the clock skew being a difference of a clock propagation delay in the clock synchronous circuit can be reduced.
According to another aspect of the invention, the recording medium for a wiring processing program is characterized in that a wiring processing program is stored, whereby a computer executes: a segment dividing procedure for dividing a wiring on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; a propagation delay time determining procedure for obtaining a propagation delay time of the wiring in which a delay time of each of the segments obtained by the segment branch procedure is taken into account; and a wiring length adjusting procedure for comparing a propagation delay time of the wiring obtained by the propagation delay time determining procedure with a preset time, and on the basis of the comparison result, adjusting a wiring length for each of the segments.
Accordingly, in the recording medium for a wiring processing program of the invention, a delay time to each of the receivers can be made equal taking an external clock delay time into account, thereby reducing the clock skew being a difference of a clock propagation delay time in the clock synchronous circuit.
According to another aspect of the invention, the recording medium for a wiring processing program is characterized in that a wiring processing program is stored, whereby a computer executes: a first segment dividing procedure for dividing a wiring connecting between two receivers of a clock net on a clock distributing circuit of a clock synchronous circuit into three or more segments through setting two or more branch points; an equal delay branch segment determining procedure for comparing a first delay time from one branch point on one end of the segment obtained by the first segment dividing procedure to one receiver of the two receivers with a second delay time from the one branch point to the other receiver of the two receivers, comparing a third delay time from the other branch point on the other end of the segment to the one receiver of the two receivers with a fourth delay time from the other branch point to the other receiver of the two receivers, and determining a segment in which a magnitude of the first delay time against the second delay time and a magnitude of the third delay time against the fourth delay time are inverted as an equal delay branch segment where an equal delay branch point exists; an equal delay branch point determining procedure for determining an equal delay branch point in the equal delay branch segment determined by the equal delay branch segment determining procedure; a delay time determining procedure for obtaining a fifth delay time from the equal delay branch point obtained by the equal delay branch point determining procedure to each of the receivers; a second segment dividing procedure for setting two or more branch points on a wiring from the equal delay branch point through an external clock source gate and dividing the wiring into three or more segments; a propagation delay time determining procedure for obtaining a propagation delay time of the wiring in which the delay time of each of the segments obtained by the second segment dividing procedure is taken into account; and a wiring length adjusting procedure for comparing the sum of the fifth delay time from the equal delay branch point to each of the receivers obtained by the delay time determining procedure and the propagation delay time of the wiring obtained by the propagation delay time determining procedure with a preset time, and on the basis of the comparison result, adjusting a wiring length for each segment.
Accordingly, in the recording medium for a wiring processing program of the invention, the equal delay branch point can accurately be obtained taking into account that a resistance and capacitance for a unit grid on the wiring are not equal independently of the positions, and a delay time to each of the receivers can be made equal taking an external clock delay time into account. Therefore, the clock skew being a difference of a clock propagation delay time in the clock synchronous circuit can effectively be reduced.
According to another aspect of the invention, the recording medium for a wiring processing program is characterized in that a wiring processing program is stored, whereby a computer executes: a forward searching procedure that, as for an adjoining grid next to a grid at which an arrival state flag for indicating an arrival of a search segment at the grid obtained by dividing a wiring area into grids by a unit of a minimum pitch of a wiring on a circuit board indicates an arrival of the search segment, when an available flag for indicating whether a grid is available for a wiring or not indicates an available state and the arrival state flag indicates a non-arrival state of the search segment, executes in parallel an adjoining grid flag procedure that sets the arrival state flag at the adjoining gird to the arrival state of the search segment and makes an arrival direction flag for indicating an arrival direction of a search segment at the adjoining grid to indicate a search direction thereof, and further repeats the adjoining grid flag processing procedure as to each of the search segments until the grid requiring the arrival state flag to indicate the arrival state of the search segment comes into nonexistence; and a backward searching procedure for searching, after the forward searching procedure finishes, a wiring path backward from a desired grid in compliance with the arrival direction flag.
Accordingly, in the recording medium for a wiring processing program of the invention, the operation in the forward searching procedure can be performed in an increased speed by the parallel processing, thus significantly reducing time for searching the wiring paths.
According to another aspect of the invention, the recording medium for a wiring processing program is characterized in that a wiring processing program is stored, whereby a computer executes: a forward searching procedure for searching forward each grid obtained by dividing a wiring area into grids by a unit of a minimum pitch of a wiring on a circuit board, while indicating a plurality of search directions of the search segments on an arrival direction flag for indicating a direction in which a search segment arrives at the grid; a backward searching procedure for searching, after the forward searching procedure, a plurality of wiring paths backward from a desired grid in compliance with the arrival direction flag; and an optimum wiring path determining procedure for determining an optimum wiring path out of a plurality of wiring paths obtained by the backward searching procedure.
Accordingly, in the recording medium for a wiring processing program of the invention, a plurality of wiring paths can be searched and an optimum wiring path can be selected therefrom, thus enhancing quality of the wiring while minimizing a wiring length.
According to another aspect of the invention, the recording medium for a wiring processing program is characterized in that a wiring processing program is stored, whereby a computer executes a wiring congestion degree evaluating procedure for evaluating a wiring congestion degree of a wiring from the (L-G )/L, in which L is a total wiring length of a wiring on a circuit board, G is a number of dots used for the wiring.
Accordingly, in the recording medium for a wiring processing program of the invention, the wiring congestion degree of a circuit can be estimated for a wiring possibility at the finishing stage of a layout of a circuit before executing the wiring. Therefore, the estimation and evaluation of the wiring possibility becomes possible at an early stage, which is requested as wiring objectives become increasingly big, presenting an advantage.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be fully understood from the detailed description given below and from the accompanying drawings of the preferred embodiments of the invention, which, however, should not be taken to limit the specific embodiment, but are for explanation and understanding, in which:
FIG. 1 is a block diagram showing a construction of an interactive circuit designing equipment relating to one embodiment of the invention;
FIG. 2 is an illustration showing a total construction of the interactive circuit designing equipment relating to the embodiment of the invention;
FIG. 3 is an illustration of a model for a clock tree with a buffer in the first mode of the wiring processing method for reducing a clock skew according to the invention;
FIG. 4 is an illustration showing a major part of a construction of a clock tree with a buffer in the first mode of the wiring processing method for reducing the clock skew according to the invention;
FIGS. 5 and 6 are illustrations typically showing a construction of a clock tree of a clock net on a clock distributing circuit in the first mode of the wiring processing method for reducing the clock skew according to the invention;
FIG. 7 is a flow chart for explaining the first mode of the wiring processing method for reducing the clock skew according to the invention;
FIG. 8 is a functional block diagram for explaining the first mode of the wiring processing equipment for reducing the clock skew according to the invention;
FIGS. 9 and 10 are illustrations typically showing a construction of a clock net on a clock distributing circuit in the second mode of the wiring processing method for reducing the clock skew according to the invention;
FIG. 11 is an illustration for explaining a calculation method of y1, y2, and y3 for calculating the admittance;
FIG. 12 is an illustration for explaining an external clock delay;
FIG. 13 is a flow chart for explaining the second mode of the wiring processing method for reducing the clock skew according to the invention;
FIG. 14 is a functional block diagram for explaining the second mode of the wiring processing equipment for reducing the clock skew according to the invention;
FIG. 15 is a flow chart for explaining the third mode of the wiring processing method for reducing the clock skew according to the invention;
FIG. 16 is a functional block diagram for explaining the third mode of the wiring processing equipment for reducing the clock skew according to the invention;
FIG. 17 is an illustration for explaining a construction of an available flag, arrival state flag, and arrival direction flag;
FIGS. 18(a) through 18(e), FIGS. 19(a) through 19(e), FIGS. 20(a) through 20(e), FIGS. 21(a) through 21(e), FIGS. 22(a) through 22(f) are illustrations for explaining the first mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 23 is a flow chart for explaining the first mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 24 is a functional block diagram for explaining the first mode of the wiring processing equipment for determining a wiring path according to the invention;
FIGS. 25(a), 25(b), FIGS. 26(a) and 26(b) are illustrations for explaining the second mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 27 is a flow chart for explaining the second mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 28 is a functional block diagram for explaining the second mode of the wiring processing equipment for determining a wiring path according to the invention;
FIG. 29 is an illustration for explaining the third mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 30 is a flow chart for explaining the third mode of the wiring processing method for determining a wiring path according to the invention;
FIG. 31 is a functional block diagram for explaining the third mode of the wiring processing equipment for determining a wiring path according to the invention;
FIG. 32 is an illustration of a model for a clock tree with a buffer;
FIG. 33 is an illustration showing a major part of a construction of a clock tree with a buffer;
FIG. 34 is an illustration showing a construction of a clock tree consisting of two sub-clock trees;
FIG. 35 is an illustration for explaining a method for searching a wiring path in an automatic wiring process; and
FIG. 36 is an illustration for explaining the method for searching a wiring path in the automatic wiring process.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Preferred embodiment of the present invention will hereafter be described in detail with reference to the accompanying drawings.
(a) Description on the Construction of an Interactive Circuit Designing Equipment relating to one Embodiment of the Invention
FIG. 1 is a block diagram showing a construction of an interactive circuit designing equipment being a wiring processing equipment relating to one embodiment of the invention.
In an interactive circuit designing equipment 1 shown in FIG. 1, numeral 3 is a display unit for displaying designing processes of various circuits and wiring paths etc. to connect circuits, 4 is a display control unit for controlling the display mode, 7 is an input device such as a key board and a mouse for a designer, referring to the data displayed on the display unit 3, to enter an information responsive to the displayed data.
5 is an external file write unit that writes into an external file 5A the wiring path drawings, etc. displayed on the display unit 3 by the display control unit 4 in accordance with the instruction from the input device 7.
6 is a printing device that prints out on a specific printing paper the wiring path drawings, etc. displayed on the display unit 3 by the display control unit 4 in accordance with the instruction from the input device 7.
8 is a hard disk in which all the data (logic circuit data, circuit layout data, etc.) used in designing circuits by the interactive circuit designing equipment 1 are stored and a wiring processing program (software) for the interactive circuit designing equipment 1 to execute the procedure for various wiring processing methods detailed later in (b) is stored, and in this embodiment, it functions as the recording medium for the wiring processing program.
2 is a CPU whereby each of the parts constituting the interactive circuit designing equipment 1 is administratively controlled.
Further, the function of the display control unit 4 is concretely achieved when the CPU 2 executes a program(software)stored in the hard disk 8; in FIG. 1, the display control unit 4 is illustrated in a block in order to define the function.
Accordingly, the interactive circuit designing equipment 1 relating to this embodiment can be embodied by a general computer system (refer to FIG. 2) that comprises the CPU 2, display unit 3, external file write unit 5, printing device 6, input device 7, hard disk 8, etc. In FIG. 2, numeral 9 is a computer main frame.
(b) Description on the Wiring Processing Method by the Interactive Circuit Designing Equipment relating to one Embodiment of the Invention
(b1) Description on the first Mode of the Wiring Processing Method for Reducing the Clock Skew
The first mode of the wiring processing method for the interactive circuit designing equipment 1 relating to one embodiment of the invention will be described, whereby the clock skew, namely, the difference of clock propagation delay time in a clock synchronous circuit can be reduced.
For explaining the first mode, FIGS. 5 and 6 illustrate a construction of a clock tree of a clock net on a clock distributing circuit of a clock synchronous circuit.
The clock tree 30 comprises, as shown in FIG. 6, a sub-clock tree consisting of a clock receiver(receiving circuit) 31 and a wiring 37 and another sub-clock tree consisting of a clock receiver(receiving circuit) 34 and a wiring 40, which are connected at an equal delay branch point (tapping point) x where the sub-clock trees have an equal delay.
Thus, in the clock tree 30, a clock driver (clock generator) not illustrated in FIG. 6 supplies a clock to the receiver 31 and 34 through the equal delay branch point x.
Here, the receiver 31 is composed of a flip-flop circuit (time constant t.sub.A) 32 and a capacitor (capacitance C.sub.A) 33, and the receiver 34 is composed of a flip-flop circuit (time constant t.sub.B) 35 and a capacitor (capacitance C.sub.B)
36.
The wiring 37 comprises a plurality of the .PI. type RC circuits (namely, segments 43) each of which consists of one resistor (resistance r.sub.1) 38 and two capacitors (capacitance c.sub.1 /2) 39, from a reason described later.
Further, in the same manner as the wiring 37, the wiring 40 also comprises a plurality of the .PI. type RC circuits (namely, segments 43) consisting of one resistor (resistance r.sub.2) 41 and two capacitors (capacitance c.sub.2 /2) 42.
In FIG. 6, the .PI. type RC circuit (segment 43) is illustrated only for one circuit each for the wiring 37 and 40, and the other segments are omitted.
Further in FIG. 5, the wiring 37 and 40 are omitted, however, a plurality of the segments in the wiring between the receiver 31 and 34 are illustrated with the symbol 43 (half-tone dot meshing in FIG. 5).
Incidentally, the equal delay branch point x shown in FIG. 6 is an input point of the clock from the driver (clock generator) not illustrated in FIG. 6, as described above.
In the clock tree 30 shown in FIG. 6, the clock skew by the two sub-clock trees of the clock tree 30 varies depending on the position of the equal delay branch point x. Therefore, the position of the equal delay branch point x has to be set very accurately to reduce the clock skew in the clock tree 30.
The method for determining an equal delay branch point x on a wiring between two sub-clock trees will now be described.
The wiring processing method for determining the equal delay branch point x in the present mode comprises, as shown in FIG. 7, a segment dividing step (step S1), equal delay branch segment determining step (step S2), equal delay branch point determining step (step S3).
The segment dividing step (step S1) sets, as shown in FIG. 5, at least two or more dividing points (branch points) P.sub.1, . . . P.sub.n+1 on the wiring between the receiver 31 and 34 and divides the wiring into at least three or more segments
43.
Here, the reason to divide the wiring (the wiring 37 and 40 shown in FIG. 6) between the receiver 31 and 34 into a plurality of segments 43 will be described.
First, a close look at one sub-clock tree is requested.
FIG. 3 illustrates a model for a clock tree with a buffer, and as shown in this figure, the buffer built-in clock tree 10 comprises a clock signal generator (clock source) 11 as the driver, a clock receiver (latch) 13 as the receiver, and a buffer 12 through which the former two are connected.
Here, the clock source 11 is connected to the buffer 12 through a wire 14 and the buffer 12 is connected to the latch 13 through a wire 15.
This buffer built-in clock tree 10 has a configuration as shown in FIG. 4 in detail.
The clock source 11 has a resistor (resistance r.sub.s) 16; the buffer 12 has a delay circuit (internal delay time d.sub.b) 19, a resistor (resistance r.sub.b) 17, and a capacitor (capacitance c.sub.b) 18; the latch 13 has a capacitor (capacitance c.sub.1) 20.
The delay time from the clock source 11 to the latch 13 includes, as already described by means of FIG. 33, the delay time due to the wiring resistors and capacitors of the wire 14 and 15, and the internal delay time d.sub.b by the delay circuit
19 of the buffer 12.
The wiring resistor has become a problem as cannot be ignored, since the size of transistors and the cross-sectional area of wirings have decreased owing to the recent progress in the semiconductor microstructuring technique.
Accordingly, it has become necessary to deal with the wire 14 and 15 as a distributed constant circuit from accuracy for estimating the delay time.
In the buffer built-in clock tree 100 as already shown in FIG. 33, as a concentrated constant circuit being a typical form of the distributed constant circuit, the wire 104 and 105 each have been evaluated by means of one .PI. type RC circuit (single .PI. type RC model). In the present mode, from the consideration that the resistance and capacitance for unit grid in the wire 14 and 15 are not equal independently of the positions on the wiring, the delay time is evaluated by means of a plurality of the .PI. type RC circuits given by dividing the wire 14 and 15 into a plurality of segments 43.
The wire 14 comprises a plurality of the .PI. type RC circuits 21 (namely, segments) each of which consists of one resistor (resistance r.sub.1, . . . , r.sub.k) 21A and two capacitors [capacitance (c.sub.1 /2), . . . , (c.sub.k /2)] 21B, as shown in FIG. 4.
The wire 15 also comprises a plurality of the .PI. type RC circuits 22 (namely, segments consisting of one resistor (resistance r.sub.m, . . . , r.sub.a) 22A and two capacitors [capacitance (c.sub.m /2), . . . , (c.sub.n /2)] 22B.
In the segment dividing step (step S1), the wiring between the receiver 31 and 34 shown in FIG. 5 is divided into the segments 43 by the dividing points P.sub.1, . . . , P.sub.n+1 with the conditions mentioned below.
(1) a physical branch point on a wiring connecting between the receiver 31 and 34.
Here, the physical branch point is a point at which a wiring layer changes, for example, in FIG. 5, the dividing point P.sub.4 and P.sub.7 are equivalent to the physical point.
(2) a point at which the impedance for a unit length of the wiring connecting between the receiver 31 and 34 changes.
Here, the impedance for a unit length of the wiring changes where the wiring layer changes, however, it changes even where the wiring layer does not change (for example, where a power supply is disposed in the underlayer of the wiring). Therefore, it is effective to divide the wiring at such a point that the impedance for a unit length of the wiring changes. Here, the impedance is resistance or capacitance.
(3) a point at which the length of a segment 43 exceeds a predetermined length s (s: optional constant).
Here, the length s is a length obtained from experience.
The segments 43 are divided at the dividing points P.sub.1, . . . , P.sub.n+1 which correspond to the aforementioned (1) through (3), each of which is evaluated by means of one .PI. type RC model.
The equal delay branch segment determining step (step S2) determines the segment 43 containing the equal delay branch point x out of the segments 43 obtained by the segment dividing step (step S1) as the equal delay branch segment.
Concretely, in the equal delay branch segment determining step (step S2), the delay time from one dividing point P.sub.k on one end of the segments 43 to one receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 31 connected to a gate A on the subsequent stage) is obtained as a first delay time [Delay (P.sub.k .fwdarw. A)], and the delay time from one dividing point P.sub.k to the other receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 34 connected to a gate B on the subsequent stage) is obtained as a second delay time [Delay (P.sub.k .fwdarw. B)].
And, the first delay time [Delay (P.sub.k .fwdarw. A)] and the second delay time [Delay (P.sub.k .fwdarw. B)] are compared.
Furthermore, the delay time from the other dividing point P.sub.k+1 on the other end of the segments 43 to one receiver of the foregoing two receivers 31, 34 is obtained as a third delay time [Delay (P.sub.k+1 .fwdarw. A)], and the delay time from the other dividing point Pk+1 to the other receiver of the foregoing two receivers 31, 34 is obtained as a fourth delay time [Delay (P.sub.k+1 .fwdarw. B)].
And, the third delay time [Delay (P.sub.k+1 .fwdarw. A)] and the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] are compared.
If there is a segment in which the magnitude of the first delay time [Delay (P.sub.k .fwdarw. A)] against the second delay time [Delay (P.sub.k .fwdarw. B)] and the magnitude of the third delay time [Delay (P.sub.k+1 .fwdarw. A)] against the fourth delay time [Delay (P.sub.k+1 .fwdarw.60 B)] are inverted, the segment is determined as an equal delay branch segment where the equal delay branch point "x" exists.
Namely, the equal delay branch segment determining step (step S2) is to find out the dividing points P.sub.k, P.sub.k+1 which satisfy
by means of dichotomy, out of the dividing points P.sub.1 through P.sub.n+1 ; the equal delay branch segment is a segment (segment P.sub.k P.sub.k+1) between the dividing point P.sub.k and P.sub.k+1.
Here, the first delay time [Delay (P.sub.k .fwdarw. A)], the second delay time [Delay (P.sub.k .fwdarw. B)], the third delay time [Delay (P.sub.k+1 .fwdarw. A)], and the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] are obtained from the following equations. ##EQU2##
Here,
r.sub.i : resistance across a segment
r.sub.k : resistance of a resistor at an equal delay branch segment
c.sub.j : capacitance at a segment
c.sub.k : capacitance of a capacitor at an equal delay branch segment
C.sub.A : capacitance at the one receiver
C.sub.B : capacitance at the other receiver
t.sub.A : delay time by the one receiver
t.sub.B : delay time by the other receiver
n+1: total number of the dividing points
k: first number of the dividing points forming the equal delay branch segment.
Furthermore, the equal delay branch point determining step (step S3) determines the equal delay branch point x in an equal delay branch segment given by the equal delay branch segment determining step (step S2).
In this equal delay branch point determining step (step S3), as shown in FIG. 6, t.sub.A and C.sub.A are calculated regarding the segment from the dividing point P.sub.k to the gate A as a sub-clock tree A, and t.sub.B and C.sub.B are calculated regarding the segment from the dividing point P.sub.k+1 to the gate B as a sub-clock tree B.
Here,
C.sub.A : total capacitance from the dividing point P.sub.k to the gate A
C.sub.B : total capacitance from the dividing point P.sub.k+1 to the gate B
t.sub.A : delay by the wiring from the dividing point P.sub.k to the gate A
t.sub.B : delay by the wiring from the dividing point P.sub.k+1 to the gate B
In the segment from the dividing point P.sub.k to P.sub.k+1, since the capacitance and resistance for a unit length are equal, the equal delay branch point x can be determined by the following equation, in the same method as the conventional technique from IBM.
here,
L: wiring length between the two receivers
.alpha.: resistance for a unit length of the wiring
.beta.: capacitance for a unit length of the wiring.
Here, the wiring processing method formed of the foregoing steps (step S1 through S3) is executed on the basis that the CPU 2 (refer to FIG. 1) of the interactive circuit designing equipment 1 has the functions equivalent to a segment dividing processor A1, equal delay branch segment determining processor A2, and equal delay branch point determining processor A3, as shown in FIG. 8.
The segment dividing processor A1 divides the wiring connecting between the two receivers 31, 34 of the clock net on the clock distributing circuit of the clock synchronous circuit into at least three or more segments 43 through setting at least two or more dividing points P.sub.1, . . . , P.sub.n+1 on the wiring. The equal delay branch segment determining processor A2 determines the segment 43 containing the equal delay branch point x out of the segments 43 picked up by the segment dividing processor A1 as the equal delay branch segment.
Concretely, the equal delay branch segment determining processor A2 compares the first delay time [Delay (P.sub.k .fwdarw. A)] from one dividing point P.sub.k on one end of the segment 43 to one receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 31 connected to a gate A on the subsequent stage) with the second delay time [Delay (P.sub.k .fwdarw. B)] from the one dividing point P.sub.k to the other receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 34
connected to a gate B on the subsequent stage), and compares the third delay time [Delay (P.sub.k+1 .fwdarw. A)] from the other dividing point P.sub.k+1 on the other end of the segment 43 to the one receiver of the foregoing two receivers 31, 34 with the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] from the other dividing point P.sub.k+1 to the other receiver of the foregoing two receivers 31, 34. Further, the equal delay branch segment determining processor A2 determines that the segment 43 in which the magnitude of the first delay time [Delay (P.sub.k .fwdarw. A)] against the second delay time [Delay (P.sub.k .fwdarw. B)] and the magnitude of the third delay time [Delay (P.sub.k+1 .fwdarw. A)] against the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] are inverted as the equal delay branch segment where the equal delay branch point x exists.
Furthermore, the equal delay branch point determining processor A3 determines an equal delay branch point x in the equal delay branch segment given by the equal delay branch segment determining processor A2.
And in practice, such functions as being equivalent to these processors A1 through A3 can be embodied by a wiring processing program, stored in the hard disk 8, whereby the CPU 2 of the interactive circuit designing equipment 1 executes the procedures described later.
Here, the wiring processing program in the present mode is a software whereby the interactive circuit designing equipment 1 executes a segment dividing procedure, equal delay branch segment determining procedure, and equal delay branch point determining procedure.
The segment dividing procedure sets at least two or more dividing points P.sub.1, . . . , P.sub.n+1 on the wiring between the receiver 31 and 34 of the clock net on the clock distributing circuit of the clock synchronous circuit and divides the wiring into at least three or more segments 43.
The equal delay branch segment determining procedure determines the segment 43 containing the equal delay branch point "x" out of the segments 43 obtained by the segment dividing procedure as the equal delay branch segment.
Concretely, the equal delay branch segment determining procedure compares the first delay time [Delay (P.sub.k .fwdarw. A)] from one dividing point P.sub.k on one end of the segment 43 to one receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 31 connected to a gate A on the subsequent stage) with the second delay time [Delay (P.sub.k .fwdarw. B)] from the one dividing point P.sub.k to the other receiver of the foregoing two receivers 31, 34 (in FIG. 5, the receiver 34
connected to a gate B on the subsequent stage), and compares the third delay time [Delay (P.sub.k+1 .fwdarw. A)] from the other dividing point P.sub.k+1 on the other end of the segments 43 to the one receiver of the foregoing two receivers 31, 34 with the fourth delay time [Delay (P.sub.k+1 .fwdarw. B] from the other dividing point P.sub.k+1 to the other receiver of the foregoing two receivers 31, 34. Further, the equal delay branch segment determining procedure determines the segment in which the magnitude of the first delay time [Delay (P.sub.k .fwdarw. A)] against the second delay time [Delay (P.sub.k .fwdarw. B)] and the magnitude of the third delay time [Delay (P.sub.k+1 .fwdarw. A)] against the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] are inverted as the equal delay branch segment where the equal delay branch point "x" exists.
Furthermore, the equal delay branch point determining procedure determines an equal delay branch point x in the equal delay branch segment given by the equal delay branch segment determining procedure.
Based on the foregoing construction, in the interactive circuit designing equipment 1 relating to the embodiment of the invention, the following operation determines the equal delay branch point x in the wiring between the two sub-clock trees.
In the interactive circuit designing equipment 1, the segment dividing step (step S1) sets at least two or more dividing points P.sub.1, . . . , P.sub.n+1 on the wiring between the receiver 31 and 34 by, and divides the wiring into at least three or more segments 43.
Next, the equal delay branch segment determining step (step S2) determines, as described above, the first through the fourth delay time [Delay (P.sub.k .fwdarw. A), Delay (P.sub.k .fwdarw. B), Delay (P.sub.k+1 .fwdarw. A), Delay (P.sub.k+1
.fwdarw. B)] out of the segments 43 obtained by the segment dividing step (Step S1); and compares the first delay time [Delay (P.sub.k .fwdarw. A)] with the second delay time [Delay (P.sub.k .fwdarw. B)], and the third delay time [Delay (P.sub.k+1
.fwdarw. A)] with the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)].
The equal delay branch segment determining step (step S2) further determines the segment in which the magnitude of the first delay time [Delay (P.sub.k .fwdarw. A)] against the second delay time [Delay (P.sub.k .fwdarw. B)] and the magnitude of the third delay time [Delay (P.sub.k+1 .fwdarw. A)] against the fourth delay time [Delay (P.sub.k+1 .fwdarw. B)] are inverted as the equal delay branch segment where the equal delay branch point "x" exists.
Furthermore, the equal delay branch point determining step (step S3) determines the equal delay branch point "x" in the equal delay branch segment obtained by the equal delay branch segment determining step (step S2).
According to the first mode of the wiring processing method for reducing the clock skew in the interactive circuit designing equipment 1 relating to the embodiment of the invention, in the clock net on the clock distributing circuit of the clock synchronous circuit, the wiring between the receiver 31 and 34 is divided into a plurality of segments 43 to evaluate the delay time by means of a plurality of single .PI. type RC circuits. Thereby, it is possible to take into account that the resistance and capacitance for a unit grid are not equal independently of the positions on the wiring, and to determine the equal delay branch point "x" accurately on the wiring between the receiver 31 and 34.
Further, the dividing points P.sub.1, . . . , P.sub.n+1 are determined from (1) a physical branch point on a wiring connecting between the receiver 31 and 34, (2) a point at which the impedance for a unit length of the wiring connecting between the receiver 31 and 34 changes, or (3) a point at which the length of a segment 43 exceeds a predetermined length s (s: optional constant). Thereby, the dividing points P.sub.1, . . . , P.sub.n+1 can be set so as to match the condition of each of the clock nets, and the equal delay branch point "x" can be determined more precisely.
Since it is possible to precisely determine the equal delay branch point in this manner, the delay time from the driver (not illustrated in FIG. 6) to the receiver 31 and 34 can be made equal; thereby, reducing the clock skew in the clock tree 30
on the clock nets.
(b2) Description on the second Mode of the Wiring Processing Method for Reducing the Clock Skew
Furthermore, the second mode of the wiring processing method for the interactive circuit designing equipment 1 relating to the embodiment of the invention will be described, whereby the clock skew, namely, the difference of clock propagation delay time in a clock synchronous circuit can be reduced.
The second mode of the wiring processing method for reducing the clock skew will be described in which the gate delay (extra-source gate delay) increased by applying the driver being the clock generator to a load is considered in determining the equal delay branch point on the wiring between the receivers. Further, the length of the wiring between the equal delay branch point and the driver output point (external clock source gate) can be adjusted to set the delay time from the driver to the receivers to a target value, thereby the clock skew on the clock nets can effectively be reduced.
FIG. 9 shows a typical construction of a clock net 44 including a driver (clock generator) 45A and a clock tree 45B.
Here, the clock net 44 lies on the clock distributing circuit of the clock synchronous circuit, and the clock tree 45B comprises a plurality of clock trees (refer to FIGS. 5 and 6, reference symbol 30).
Namely, this FIG. 9 represents a state that a plurality of receivers (refer to FIGS. 5 and 6, reference symbol 31, 34) have completely been connected to form clock trees and a plurality of the clock trees thus formed have completely been connected each other to form the clock tree 45B, and then, the equal delay branch point Q (the final equal delay branch point on the wiring between the receivers) and the driver output point P (external clock source gate) are connected by the shortest wiring.
In this mode, after the equal delay branch point Q is accurately determined on the clock tree 45B, the length of the wiring between the equal delay branch point Q and the driver output point P is designed to be adjusted so that the delay time from the driver output point P to each of the receivers in the clock tree 45B can be set to the predetermined time.
The wiring processing method in this mode comprises, as shown in FIG. 13, a first segment dividing step (step S4), equal delay branch segment determining step (step S5), equal delay branch point determining step (step S6), delay time determining step (step S7), second segment dividing step (step S8), propagation delay time determining step (step S9), and wiring length adjusting step (step S10).
The first segment dividing step (step S4) sets at least two or more dividing points (branch points) on the wiring (the same as one shown in FIG. 5) between the two receivers in the clock tree 45B on the clock net 44 and divides the wiring into at least three or more segments.
In this mode, in the same manner as the abovementioned, from the consideration that the resistance and capacitance for a unit grid in the wiring are not equal independently of the positions, the delay time is evaluated by means of a plurality of the .PI. type RC circuits (refer to FIG. 6, reference symbol 43) given by dividing the wiring connecting between two receivers in the clock net 44 into a plurality of segments.
In FIG. 9, the dividing points and segments in the clock tree 45B are omitted.
The dividing points are determined, in the same manner as the foregoing case, from (1) a physical branch point on a wiring connecting between the receivers, (2) a point at which the impedance for unit length of the wiring connecting between the receivers changes, or (3) a point at which the length of a segment exceeds a predetermined length s (s: optional constant).
Further, the equal delay branch segment determining step (step S5) determines the segment containing the equal delay branch point Q out of the segments obtained by the first segment dividing step (step S4) as the equal delay branch segment.
Concretely, the equal delay branch segment determining step (step S5) compares, in the same manner as the foregoing case, the first delay time from one dividing point on one end of the segment to one receiver of the foregoing two receivers with the second delay time from the one dividing point to the other receiver of the foregoing two receivers, and compares the third delay time from the other dividing point on the other end of the segment to the one receiver of the foregoing two receivers with the fourth delay time from the other dividing point to the other receiver of the foregoing two receivers. The equal delay branch segment determining step (step S5) further determines the segment in which the magnitude of the first delay time against the second delay time and the magnitude of the third delay time against the fourth delay time are inverted as the equal delay branch segment where the equal delay branch point Q exists.
The foregoing first through fourth delay time can be obtained in the same manner as the foregoing case (b1) [refer to Delay (P.sub.k .fwdarw. A), Delay (P.sub.k .fwdarw. B), Delay (P.sub.k+1 .fwdarw. A), Delay (P.sub.k+1 .fwdarw. B) in the above mentioned].
Furthermore, the equal delay branch point determining step (step S6) determines an equal delay branch point Q in the equal delay branch segment given by the equal delay branch segment determining step (step S5).
The equal delay branch point Q can also be obtained in the same manner as the case described in (b1).
Further, the delay time determining step (step S7) obtains the fifth delay time t.sub.R from the equal delay branch point Q given by the equal delay branch point determining step (step S6) to each of the receivers.
The fifth delay time t.sub.R is a delay time from the equal delay branch point Q in the clock tree 45B to each of the receivers, as shown in FIG. 10.
Here, the fifth delay time t.sub.R is obtained from the following equation:
here,
L: wiring length between the receivers
.alpha.: resistance for a unit length of the wiring
.beta.: capacitance for a unit length of the wiring.
The second segment dividing step (step S8) sets, as shown in FIG. 9, at least two or more dividing points (branch points) P.sub.1, . . . , P.sub.n+1 on the wiring from the equal delay branch point Q through the driver output point P and divides the wiring into at least three or more segments 46.
In this mode, in the same manner as the abovementioned, from the consideration that the resistance and capacitance for a unit grid in the wiring are not equal independently of the positions, the delay time is evaluated by means of a plurality of the .PI. type RC circuits (refer to FIG. 10) given by dividing the wiring connecting between the equal delay point Q and the driver output point P into a plurality of segments 46.
In the second segment dividing step (step S8), the wiring between the equal delay point Q and the driver output point P is divided into the segments 46 by the dividing points P.sub.1, . . . , P.sub.n+1 with the conditions mentioned below.
(1) a point at which the impedance for a unit length of the wiring connecting between the equal delay point Q and the driver output point P changes.
Here, the impedance for a unit length of the wiring changes where the wiring layer changes, however, it changes even where the wiring layer does not change. Therefore, it is effective to divide the wiring at such a point that the impedance for a unit length of the wiring changes. Here, the impedance is a resistance or capacitance.
(2) a point at which the length of a segment 46 exceeds a predetermined length s (s: optional constant).
Here, the length s is a length determined from experience.
The segments 46 are divided at the dividing points P.sub.1, . . . , P.sub.n+1 which correspond to the aforementioned) (1) and (2), each of which is evaluated by means of the .PI. type RC circuit (.PI. type RC model) consisting of one resistor
48 (resistance Ra.sub.1, . . . , Ra.sub.n) and two capacitors 47 [capacitance (Ca.sub.1 /2), . . . , (Ca.sub.n /2)], as shown in FIG. 10.
The propagation delay time determining step (step S9) obtains a propagation delay time t.sub.PQ of the wiring in which the delay time of each of the segments 46 given by the second segment dividing step (step S8) is taken into account.
Here, the propagation delay time t PQ is obtained from the following equation. ##EQU3##
n+1: total number of the dividing points
The wiring length adjusting step (step S10) compares the delay time [Delay (P .fwdarw. each receiver)] from the driver output point P to each of the receivers with a preset time, and on the basis of the comparison result, adjusts the wiring length for each segment.
Here, the delay time [Delay (P .fwdarw. each receiver)] from the driver output point P to each of the receivers is the sum of the fifth delay time t.sub.R from the equal delay branch point Q given by the delay time determining step (step S7) to each of the receivers, the propagation delay time t.sub.PQ of the wiring given by the propagation delay time determining step (step S 9), and the external clock delay time (extra-source gate delay) t.sub.LOAD at the driver output point P.
Namely, as shown in FIG. 10, assuming that the delay time from the equal delay branch point Q to each of the receivers in the clock tree 45B is t.sub.R (the fifth delay time) and the total capacitance from the equal delay branch point Q to each of the receivers is C.sub.R, the delay time [Delay (P .fwdarw. each receiver)] from the driver output point P to each of the receivers is given by the following equation.
Here, the external clock delay time (extra source gate delay) t.sub.LOAD is described with reference to FIG. 12. In the figure, the delay time T.sub.INTERCONNECT delay delay in the wiring between the driver (SOURCE) and the receiver (LOAD) is given by the following equation:
here,
T.sub.AB (0): delay through an unloaded source gate
T.sub.AB (L): delay through the same source gate loaded by an interconnect net of length L.
And, [T.sub.AB (L)-T.sub.AB (0)] in the foregoing equation represents the external clock delay t.sub.LOAD.
In the wiring length adjusting step (step S10), y1, y2, and y3 for calculating the admittance viewed from the dividing point P.sub.1 shown in FIGS. 9, 10 are calculated in order to obtain t.sub.LOAD at the dividing point P.sub.1.
Namely, t.sub.LOAD at the dividing point P.sub.1 can be obtained through the calculation that the equations y1, y2, and y3 for calculating the admittance viewed from the dividing point P.sub.1 are calculated and a specific calculation (whose detailed content does not concern this mode) is carried out using these three equations.
Namely, t.sub.LOAD =F (y1, y2, y3).
In this embodiment, the calculation of y1, y2, and y3 for calculating the admittance is performed on the basis of the method mentioned in `P. R. O'Brien and T. L. Savarino, "Modeling the Driving-Point Characteristics of Resistive Interconnect for Accurate Delay Estimation", IEEE Intl. Conference on CAD, pp512-515, 1989`.
Here, a general wiring model to obtain y1, y2, and y3 is shown in FIG. 11.
In FIG. 11, numeral 49 is a capacitor, 50 resistor, 51 output pin from the driver or receiver, and P.sub.1.about.P.sub.9 are dividing points.
A calculation method of y1, y2, and y3 for calculating the admittance viewed from the dividing point P.sub.1 will hereafter be described.
First, assuming that the Laplace transform expression is y.sub.1 (s), the Laplace transform from the receiver to the driver will be given by the following.
The tertiary approximation of y.sub.1 (s) is expressed in the following equation:
and the coefficient y1, y2, and y3 are obtained from this equation.
Thus, in the wiring length adjusting step (step S10), the delay time [Delay (P .fwdarw. each receiver)] from the driver output point P calculated by the foregoing equation to each of the receivers is compared with a preset time .gamma., and on the basis of this comparison, the wiring length between the equal delay branch point Q and the driver output point P can be adjusted for each segment.
When the delay time [Delay (P .fwdarw. each receiver)] from the driver output point P to each of the receivers exceeds the preset time .gamma. at the beginning, the layout of the driver 45A and/or the clock tree 45B (refer to FIGS. 9 and 10) are relocated before the wiring length between the equal delay branch point Q and the driver output point P is readjusted.
Concretely, the relocation or the wiring length adjustment is done in accordance with the fo