Theory and Algorithm of Local-Refinement Based

Optimization with Application to Device and Interconnect Sizing

Jason Cong and Lei He

Abstract— In this paper we formulate three classes of optimization problems: the simple, monotonically-constrained and bounded CH-programs. We reveal the dominance property under the local refinement (LR) operation for the simple and monotonically-constrained CH-programs, as well as the general dominance property under the pseudo-LR operation for the monotonically-constrained CH-program and the extended-LR operation for the bounded CH-program. These properties enable a very efficient polynomial-time algorithm, using different types of LR operations to compute tight lower and upper bounds of the exact solution to any CH-program. We show that the algorithm is capable of solving many layout optimization problems in deep submicron IC and/or high-performance MCM/PCB designs. In particular, we apply the algorithm to the simultaneous transistor and interconnect sizing problem, and to the global interconnect sizing and spacing problem considering the coupling capacitance for multiple nets. We use tables pre-computed from SPICE simulations and numerical capacitance extractions to model device delay and interconnect capacitance, so that our device and interconnect models are much more accurate than many used in previous interconnect optimization algorithms. Experiments show that the boundcomputation algorithm can efficiently handle such complex models, and obtain solutions close to the global optimum in most cases. We believe that the CH-program formulations and the bound-computation algorithm can also be applied to other optimization problems in the CAD field.

I. Introduction

The interconnect delay has become the dominant factor in determining circuit performance in deep submicron (DSM) designs [1]. Many optimization techniques have been proposed to reduce interconnect delay, including interconnect topology optimization, buffer insertion, and device and interconnect sizing (see [2] for a comprehensive survey). We believe that the most effective approach to performance optimization in deep submicron designs is to consider both logic and interconnect designs throughout the entire design process (from RTL level to layout design). This motivates our study of the simultaneous device and interconnect sizing problem in DSM designs.

Several recent studies considered the simultaneous device and interconnect sizing problem. One class of algorithms minimizes the weighted delay. In [3], the simultaneous driver and wire sizing problem was formulated to minimize the weighted delay between the source and a set of sinks for a single net. Procedures of device sizing and wire sizing are alternately carried out, with device sizes computed by closed-form formulas and wire widths computed by algorithms from [4], [5]. In [6], [7], the simultaneous transistor and interconnect sizing problem was studied to minimize the weighted delay for multiple paths (a path contains multiple nets). The local refinement operation, previously used only for wire sizing solutions [4], [3], [5], is applied to optimize both devices and interconnects. It leads to a unified and very efficient algorithm. Recently, the simultaneous buffer insertion

Both authors are with the computer science department, the university of California at Los Angeles, CA 90095. E-mails: cong@cs.ucla.edu and helei@cs.ucla.edu. This work is partially supported by DARPA/ETO under contract DAAL01-96-K-3600, the NSF Young Investigator Award MIP-9357582 and a grant from Intel Corporation under the NYI matching award program. This research makes use of the software donated from Avant! Corporation, whose generous donation is greatly appreciated.

and wire sizing problem was also addressed [8]. It is assumed that the number of buffers to insert is given for each wire segment, and that the wire widths between any two buffers are monotonic. Therefore, the problem can be solved as a convex quadratic program to find the lengths of wire segments for different wire widths.

The other class of simultaneous device and interconnect sizing algorithms considers the maximum delay. In [9], the simultaneous gate and wire sizing problem was formulated to minimize the area under the maximum-delay constraint for multiple paths. The problem is shown to be a posynomial program, and is transformed into a convex program solved by a sequential quadratic programming technique. In addition, the simultaneous buffer insertion and wire sizing problem was studied to minimize the maximum delay from the source to a set of sinks for a single net [10]. The potential locations for buffer insertion are a priori given. Based on a bottom-up dynamic programming approach, buffers are then inserted with optimal sizes, and optimal wire widths determined simultaneously. In general, the algorithms for minimizing the weighted delay are more efficient. By adjusting the weight assignments, a sequence of such minimizations can be used to minimize the maximum delay under the area constraint or to minimize the area under the delay constraint. In particular, a Lagrangian relaxation technique was proposed in [11] to optimally assign the weights for the sequence of weighted-delay minimizations. The simultaneous buffer and wire sizing problem was also solved.

However, most of these works assumed over-simplified models for devices and interconnects. For example, a gate of size d and output load c_{l} is assumed to have a delay t_{d} = t_{0} + r_{d} · c_{l}, where t_{0} and r_{d} are the intrinsic delay and effective resistance of the gate, respectively. In addition, r_{d} = r_{0}/d, where r_{0} is the unitsize effective-resistance for the gate. Both t_{0} and r_{0} are assumed to be constants. Moreover, the capacitance for a wire of width w and length l is given by c_{a} · w · l + c_{f} · l, where c_{a} and c_{f} are unit-area capacitance and unit-length fringe capacitance for the wire. Both are again assumed to be constants.

These assumptions are no longer realistic for DSM designs. For example, we computed r_{0} for an inverter in Table I. We apply HSPICE simulations, and use device parameters for the 0.18μm technology in Table 5 of the National Technology Roadmap for Semiconductors (NTRS) [12]. When the inverter is driven by a rising input, we first measure two delay values t_{1} and t_{2} for a pair of output loads c_{1} and c_{2} under the same size and input switching time. Using the assumption that t_{1} = t_{0} + r_{d} · c_{1} and t_{2} = t_{0} + r_{d} · c_{2}, we can obtain r_{d} = (t_{1} − t_{2})/(c_{1} − c_{2}), and t_{0} = t_{1} − r_{d} · c_{1}. We then compute t_{0} values for different combinations of size, input switching time (t_{s}) and output load (c_{l}). Because we assume that the intrinsic delay t_{0} is a constant in this paper, we derive the “best” t_{0} value by least-square-fitting over t_{0} values for different combinations of size, t_{s} and c_{l}. Finally, we use the “best” t_{0} value to compute r_{0} = (t_{d} − t_{0})/c_{l} · d, where t_{d} is the inverter delay, and d the size for the n-transistor in the inverter. We compute r_{0} for the n-transistor under different combinations of size, t_{s} and c_{l}. Similarly, when the inverter is driven by a falling input, r_{0} for the p-transistor can be determined in the same way under different combinations of size, t_{s} and c_{l}. As one can see from Table I, r_{0} is clearly not a constant. Its value may vary by a factor of 2.

We also computed the capacitance for the basic geometric structure (see Figure 1), where the victim wire is centered between two neighboring wires on the same layer and both top and down grounds (two layers away from the victim). We apply

size = 100x

n-transistor  p-transistor
c_{l} / t_{s} 0.05ns 0.1ns 0.2ns 0.05ns 0.1ns 0.2ns
0.225pF 12200 13370 19180 17200 19920 24550
0.425pF 8135  9719  12500 17180 17190 18820
0.825pF 8124  8665  10250 17090 17150 17290
1.625pF 8114  8170  8707  16140 17140 17150
3.225pF 7578  8137  8251  14710 16940 17100

size = 400x

n-transistor  p-transistor
c_{l} / t_{s} 0.05ns 0.1ns 0.2ns 0.05ns 0.1ns 0.2ns
0.501pF 12200 15550 19150 18200 19970 27030
0.901pF 11560 13360 17440 17340 19590 24560
1.701pF 8463  9688  12470 17070 17420 18790
3.301pF 7725  8812  10420 17030 16780 17440
4.901pF 7554  8480  10010 16090 17020 17060

TABLE I

Unit-size effective-resistance r_{0} for different combinations of sizes (100x and 400x of the minimum inverter size), input

switching times (t_{s}) and output loads (c_{l}).

a numerical capacitance extraction tool FastCap [13], and use interconnect geometric parameters for the 0.18μm technology in Table 22 of the NTRS.^{1} Figure 2(a) depicts the unit-length ground capacitance c_{g} between the victim and grounds, with each curve for c_{g} under different wire widths but a fixed edge-to-edge spacing (in short, spacing). If we assume c_{g} = c_{a}·w·l+c_{f} ·l, the curve slope should be c_{a}, and the curve intercept should be c_{f}. Because none of these curves is linear, and different curves have different intercepts, neither c_{a} nor c_{f} is a constant. The total capacitance of the victim is

c_{total} = c_{g} + c_{x} · l = c_{a} · w · l + (c_{f} + c_{x}) · l

where c_{x} is the unit-length coupling capacitance between the victim and the neighboring wires. One can define the unitlength effective-fringe capacitance c_{ef} = c_{f} + c_{x}, and compute c_{total} = c_{a} · w · l + c_{ef} · l. We also obtained c_{ef} for different widths for the victim, under the assumption that the center-to-edge spacing (see Figure 1) from the center of the victim to the edges of its neighboring wires is fixed. As shown in Figure 2(b) for two different center-to-edge spacing, c_{ef} is a not a constant either.

Fig. 1. The basic geometric structure for capacitance extraction.

We say that a device model is a simple model if it assumes that r_{0} is a constant, and a capacitance model is a simple model if it assumes that both c_{a} and c_{ef} are constants. Most existing device and interconnect sizing works assume simple device

1The NTRS gives capacitance values only for the minimum width and spacing. Our extracted capacitance values closely match those given in the NTRS (see [1]).

Fig. 2. (a) Ground capacitance and (b) effective-fringe capacitance for the central wire (the victim) in the basic geometric structure shown in Figure 1. Each curve in (a) has the same spacing but different wire widths, and each curve in (b) has the same centerto-edge spacing but different wire widths. The capacitance values are given for the unit-length wire.

and capacitance models. Little progress has been made for optimization beyond the simple models. The simultaneous buffer insertion and wire sizing algorithm [10] was extended to consider the impact of the input switching time for the device delay. The unit-size effective-resistance, in essence, is assumed to be r_{0} = r′_{0} + δ · t_{s}, where r′_{0} is the unit-size effective-resistance under the step input, t_{s} the input switching time, and δ an empirical constant. The algorithm based on the bottom-up dynamic-programming, however, no longer has a polynomialtime complexity under the extended device model. The posynomial program formulation for the simultaneous gate and wire sizing problem [9] was also extended to accommodate a voltageramp gate model, which considers the impacts of the input switching time and output loading under the C_{eff} model [14]. The resulting sizing problem, however, is no longer a posynomial program. It is unknown how far away the solution obtained by solving a posynomial program is from the exact solution under the voltage-ramp model. Two very recent works [15], [16] begin to consider coupling capacitance for multiple nets.^{2} Both allow variable c_{ef} but still assume that r_{0} and c_{a} are constants. Even though all these algorithms still use the simple model for either device delay or interconnect capacitance, their runtime is already high. For example, it took over twenty minutes to optimize a 16-bit bus of 320 wire segments in [16].

We will call the device table, like Table I, STL-bounded model, where r_{0} is determined by the size, input switching time (t_{s}) and output load (c_{l}), and its value is bounded (i.e., there exist lower and upper bounds for r_{0}) for any given ranges of size, t_{s} and c_{l}. In addition, a WS-bounded capacitance model will be presented in Section IV, where c_{a} and c_{ef} are determined by the width (w) and spacing (s), and their values are also bounded for any

2The formulation in [15] is based on the dominant time constant, which is an approximation to the maximum delay among multiple sinks in a net. Because it is difficult to efficiently minimize the sum of the dominant time constants [15], the Elmore delay model (used in this paper) is more appropriate for path delay minimization.

given ranges of w and s. We build tables for the STL-bounded device model via HSPICE simulations, and for the WS-bounded capacitance model via numerical capacitance extractions. These models are more accurate than the simple models, and have been widely used for verification purposes. However, there are virtually no algorithms that allow us to use these models for the device and interconnect sizing problems.

In this paper, we apply the STL-bounded device model and the WS-bounded capacitance model to the simultaneous transistor and interconnect sizing problem (STIS), and to the global interconnect sizing and spacing (GISS) problem considering the coupling capacitance for multiple nets. In order to efficiently handle the two problems, we develop the theory and algorithm of local-refinement based optimization. We formulate three classes of optimization problems: the simple, monotonicallyconstrained, and bounded CH-programs. We reveal the dominance property (Theorem 1) under the local refinement (LR) operation for the simple and monotonically-constrained CHprograms, as well as the general dominance property (Theorem

2) under the pseudo-LR (PLR) operation for the monotonicallyconstrained CH-program and under the extended-LR (ELR) operation for the bounded CH-program. These properties enable a very efficient polynomial-time algorithm, using the LR, PLR, or ELR operation for computing lower and upper bounds of the exact solution to any CH-program.

We show that in general, the STIS and GISS problems are bounded CH-programs. Therefore, the ELR operation is needed in the bound-computation algorithm for the two problems. We also show that when the WS-bounded capacitance model is monotonically-constrained, the GISS problem becomes a monotonically-constrained CH-program. In this case, the PLR operation that is more efficient than the LR and ELR operations can be used.^{3} According to Theorem 2, our boundcomputation, which uses the ELR operation for the STIS algorithm and the ELR and PLR operations for the GISS algorithm, guarantees that there exist exact solutions to the two problems between resulting lower and upper bounds. Experiments also show that the bound-computation obtains solutions close to the global optimum in the most cases. Based on HSPICE simulations, our algorithm in this paper obtained up to 15.1% and 11% addition delay reductions when compared with STIS results in

[7] and GISS results in [16]. Moreover, our algorithm is extremely efficient. A speedup of over 100x is achieved compared with the algorithm in [16].

Note that our algorithm is applicable to any bounded model, which simply requires that the values for r_{0}, c_{a} and c_{ef} be bounded. Furthermore, the bounded model can use either tablelookup or high-order complex characteristic functions. In addition, although we use the device and interconnect sizing problem in DSM IC designs to illustrate the effectiveness and efficiency of our LR-based optimization, it is not difficult to see that it can be easily applied to the device and interconnect sizing problem in PCB and MCM layout designs as well. Besides, results presented in this paper can be used for both pre-layout interconnect planning, and post-layout interconnect optimization.

The rest of the paper is organized as follows: we first present the theory and algorithm of LR-based optimization in Section II, then apply the algorithm to the STIS and GISS problems in Sections III and IV, and finally conclude in Section V. The proofs of Theorems 1 and 2, which are the basis of this paper, are presented in the Appendix to this paper. Proofs of other

3We show in Section III-B that the STIS problem is not a monotonicallyconstrained CH-program. Therefore, the LR and PLR operations might be not applicable to the bound-computation for the STIS problem.

theorems, together with tables for the device delay and interconnect capacitance used in our experiments, are available from a technical report [17]. Part of preliminary results of this work was presented in two conference papers [7], [18].

II. Theory and Algorithm for CH-Programs

A. Formulations of CH-functions

We first define the CH-function (Cong-He function)^{4} as a function of a positive vector X = {x_{i} | x_{i} ≥ 0, i = 1, ⋯, n} with the following form:

f(X) = ∑_{p≥0} ∑_{q≥0} ∑_{i=1}^{n} ∑_{j=1,j≠i}^{n}( \frac{a_{p,q,i,j}(X)}{x_{i}^{p}}) · (b_{p,q,i,j}(X) · x_{j}^{q}) (1)

where coefficients a_{p,q,i,j}(X) and b_{p,q,i,j}(X), as well as exponents p and q, are positive.

Depending on the coefficient a_{p,q,i,j}(X) and b_{p,q,i,j}(X), we define the following three types of CH-functions:

Definition 1: (simple CH-function) Eqn. (1) is a simple CH-function if coefficients a_{p,q,i,j} and b_{p,q,i,j} are constants. The concept of simple CH-function was first introduced in [6], [7]. It was shown that many previous works on device and interconnect sizing problems, including the single-source and multi-source wire sizing problems [4], [5], continuous wire sizing problem [19], and simultaneous driver and wire sizing problem [3], use simple CH-functions as objective functions.

In some applications however, coefficients a_{p,q,i,j}(X) and b_{p,q,i,j}(X) may vary as functions depending on X. For two vectors X and X′, we say that X dominates X′ (denoted by X ≥ X′) if x_{i} ≥ x′_{i} for i = 1, ⋯, n. We then define the following monotonically-constrained CH-function:

Definition 2: (monotonically-constrained CH-function) Eqn. (1) is a monotonically-constrained CH-function, if it satisfies the following monotonic constraints: for any vector X′ ≥ X, (i)

\frac{a_{p,q,i,j} (X′)}{x_{i}^{′p}} ≤ \frac{a_{p,q,i,j} (X)}{x_{i}^{p}} and a_{p,q,i,j}(X′) ≥ a_{p,q,i,j}(X); (ii)

b_{p,q,i,j}(X′) · x_{j}^{′q} ≥ b_{p,q,i,j}(X) · x_{j}^{q} and b_{p,q,i,j}(X′) ≤ b_{p,q,i,j}(X). The monotonically-constrained CH-function was defined differently (and called bounded-variation CH-posynomial^{5}) in [18], where we say (i) a_{p,q,i,j} is a function depending only on x_{i}. With respect to an increase of x_{i}, \frac{a_{p,q,i,j} (x_{i})}{x_{i}^{p}} monotonically decreases

and a_{p,q,i,j}(x_{i}) monotonically increases; (ii) b_{p,q,i,j} is a function depending only on x_{j}. With respect to an increase of x_{j}, b_{p,q,i,j}(x_{j}) · x_{j}^{q} monotonically increases and b_{p,q,i,j}(x_{j}) monotonically decreases. It is easy to see that Definition 2 subsumes the old definition and covers a wider class of functions, because now each coefficient may vary as a function of all variables in X, instead of a single variable in [18].

We finally remove the monotonic constraints for the CHfunction by formulating the following bounded CH-function:

Definition 3: (bounded CH-function) Eqn. (1) is a bounded CH-function, if its coefficients are bounded: for any p, q, i and j, there exist positive constant a_{p,q,i,j}^{L}, a_{p,q,i,j}^{U}, b_{p,q,i,j}^{L} and b_{p,q,i,j}^{U}, such that a_{p,q,i,j}^{L} ≤ a_{p,q,i,j}(X) ≤ a_{p,q,i,j}^{U} and b_{p,q,i,j}^{L} ≤ b_{p,q,i,j}(X) ≤ b_{p,q,i,j}^{U}.

4CH-function was called CH-posynomial in [7], [18]. As recommended by reviewers, we renamed it to show that it is not, in general, a posynomial.

5According to reviewers’ recommendations, we saved the name “bounded” for the type of CH-function defined in Definition 3, which was called the general CH-posynomial in [18].

Clearly, the simple CH-function is a subset of the monotonically-constrained CH-function, which in turn is a subset of the bounded CH-function (see Figure 3). In addition, the simple CH-function is a subset of the posynomial. A posynomial [20] is a function of a positive vector X having the form g(X) = ∑_{i=1}^{m} u_{i}(X) with

u_{i}(X) = c_{i}x_{1}^{a_{i1}}x_{2}^{a_{i2}} ⋯ x_{n}^{a_{in}},  i = 1, 2, ⋯, m  (2)

where the exponents a_{ij} are real numbers and the coefficients c_{i} are positive. For example,

f(x_{1}, x_{2}, x_{3}) = x_{1}^{1/2} + 1/x_{2} + x_{3}  (3)

is a simple CH-function as well as a posynomial. However,

f(x_{1}, x_{2}, x_{3}) = x_{1}^{2} · x_{2} · \frac{1}{x_{3}}  (4)

is a posynomial but not a simple CH-function. On the other hand, the monotonically-constrained and bounded CHfunctions may be no longer a posynomial. For example,

f(x_{1}, x_{2}) = \frac{1}{ln x_{1}} · x_{1}^{2} + \frac{x_{2}}{x_{1}} , x_{1} > 3  (5)

is neither a simple CH-function nor a posynomial. However, one can easily verify that it is a monotonically-constrained CHfunction by treating \frac{1}{ln x_{1}} as the coefficient function for x_{1}^{2}.

Fig. 3. The simple CH-function is a subset of the monotonicallyconstrained CH-function, which is in turn a subset of the bounded CH-function.

B. Properties for CH-programs

We define the CH-program as an optimization problem to minimize a CH-function subject to L ≤ X ≤ U (i.e., l_{i} ≤ x_{i} ≤ u_{i} for i = 1, ⋯, n). It may be a simple, monotonicallyconstrained or bounded CH-program depending on whether its objective function is a simple, monotonically-constrained or bounded CH-function. We will introduce the dominance property for the simple and monotonically-constrained CHprograms, as well as the general dominance property for the monotonically-constrained and bounded CH-programs.

B.1. Dominance property. We first define the following local refinement operation:

Definition 4: (local refinement operation) Given a function f(X) and a solution vector (or simply, a solution) X′, the local refinement operation for any particular variable x_{i} is to minimize f(X) by only varying x_{i} while keeping all values of other x_{j}(j ≠ i) in X′ fixed. Such an operation is also called an LR operation in short. The resulting solution vector is called the local refinement of X′ (with respect to x_{i}).

We have proved the following dominance property in the Appendix to this paper.

Theorem 1: (Dominance Property) Let f(X) be a simple or monotonically-constrained CH-function, and X^{∗} an exact solution to minimize f(X). For any solution X′ of f(X), if X′ dominates X^{∗}, any local refinement of X′ leads to a solution that still dominates X^{∗}. Similarly, if X′ is dominated by X^{∗}, any local refinement of X′ leads to a solution that is still dominated by X^{∗}.

The dominance property under the LR operation was first introduced in [4] for the single-source wire sizing problem. Later on, the LR operation was successfully applied to the multisource wire sizing problem [5], continuous wire sizing problem [19], simultaneous buffer and wire sizing problem [11], and simultaneous transistor and interconnect sizing problem [7]. It is easy to verify that these problems using simple device and capacitance models are all simple CH-programs. Therefore, the dominance property holds for these problems. Nevertheless, Theorem 1 shows that the dominance property holds for all simple CH-programs, not just these several programs. Furthermore, it reveals that the dominance property holds for the monotonically-constrained CH-program, which has not been discussed in previous works.

When coefficients for variable x_{i}, like the case of simple CH-program, are all constants, the LR operation of x_{i} is a single-variable posynomial program that can be solved very efficiently.^{6} The LR operation for the monotonicallyconstrained CH-program, however, may be less efficient. First, it might be no longer a posynomial program. An example is the LR operation of x_{1} to minimize Eqn. (5), where a logarithm function is involved. Second, when a coefficient varies depending on a table rather than a closed-form formula, we may have to enumerate all possible values for x_{i} in order to find out its local optimal value (an example is given later on in Section IV-B).

The usage of the LR operation is also limited by the fact that the dominance property under the LR operation generally does not hold for a bounded CH-program. To overcome these limitations, we introduce the pseudo-LR and extended-LR operations, then show a general dominance property.

B.2. General dominance property. The pseudo-LR and extended-LR operations (in short, the PLR and ELR operations) are defined as the following:

Definition 5: (pseudo-LR operation) Given a CH-function f(X) and a solution vector X′, the pseudo-LR operation for variable x_{i} with respect to X′ is an LR operation using constant coefficients a_{p,q,i,j}(X′) and b_{p,q,i,j}(X′) when solving the “local-optimal” x_{i} for any p, q, i and j. That is, we fix the coefficients under the current solution when performing an PLR operation. The PLR and LR operations are same for a simple CH-program, but may produce different results for a monotonically-constrained CH-program.

Definition 6: (extended-LR operation) Given a CHfunction f(X) and a solution X′, the extended-LR operation

6 According to [20], a posynomial program is the following minimization problem:

min g_{0}(X) subject to g_{k}(X) ≤ 1
k = 1, 2, ⋯, p and X > 0

where each g_{k} (k = 0, 1, 2, ⋯, p) is a posynomial function. In the case of LR operation of x_{i} for a simple CH-program, the local optimum is also a global optimum no matter whether x_{i} has continuous or discrete value. More detailed discussion of posynomial programs can be found in Section II-D.

for a particular variable x_{i} in X′ is the LR operation using the following coefficients for any p, q, j ≠ i, and k ≠ i:

(i) When X′ ≥ X^{∗}, we replace a_{p,q,ij}(X′) and a_{p,q,k,j}(X′) by a_{p,q,i,j}^{U} and a_{p,q,k,j}^{L}, and replace b_{p,q,j,i}(X′) and b_{p,q,k,j}(X′) by b_{p,q,j,i}^{L} and b_{p,q,j,k}^{U}. (ii) When X′ ≤ X^{∗}, we replace a_{p,q,ij}(X′) and a_{p,q,k,j}(X′) by a_{p,q,i,j}^{L} and a_{p,q,k,j}^{U}, and replace b_{p,q,j,i}(X′) and b_{p,q,k,j}(X′) by b_{p,q,j,i}^{U} and b_{p,q,j,k}^{L}. We call the solution given by the PLR or ELR operation as the pseudo- or extended-local refinement of X′, respectively. Note that the lower and upper bounds are not unique for coefficient functions. The definition of the ELR operation is applicable to any valid lower and upper bounds.

According to these definitions, even though coefficients are functions of the variable vector X in the monotonicallyconstrained or bounded CH-program, coefficients during each PLR or ELR operation are still treated as constants. Therefore, the PLR or ELR operation for a monotonically-constrained or bounded CH-program again becomes a single-variable posynomial program that can be solved very efficiently, exactly as the LR operation for a simple CH-program. We will illustrate the PLR and ELR operations using the following CH-function:

f(x_{1}, x_{2}) = \frac{a_{1}(x_{1}, x_{2})}{x_{1}} · (b_{2}(x_{1}, x_{2}) · x_{2}^{2}) + \frac{a_{2}(x_{1}, x_{2})}{x_{2}} · (b_{1}(x_{1}, x_{2}) · x_{1}), (6)

The pseudo-local refinement of x_{1} with respect to X′ = {x′_{1}, x′_{2}} is

x̃_{1}^{P LR} = \sqrt{\frac{a_{1}(x′_{1}, x′_{2}) · (b_{2}(x′_{1}, x′_{2}) · x_{2}^{′3})}{a_{2}(x′_{1}, x′_{2}) · b_{1}(x′_{1}, x′_{2})}} .  (7)

If we assume that a_{1}(x_{1}, x_{2}) ∈ [a_{1}^{L}, a_{1}^{U}], a_{2}(x_{1}, x_{2}) ∈ [a_{2}^{L}, a_{2}^{U}], b_{1}(x_{1}, x_{2}) ∈ [b_{1}^{L}, b_{1}^{U}] and b_{2}(x_{1}, x_{2}) ∈ [b_{2}^{L}, b_{2}^{U}]. When {x′_{1}, x′_{2}} is dominated by exact solution {x_{1}^{∗}, x_{2}^{∗}}, the extended-local refinement of x_{1} concerning {x′_{1}, x′_{2}} is

x̃_{1}^{ELR} = \sqrt{\frac{a_{1}^{L} · (b_{2}^{L} · x_{2}^{′3})}{a_{2}^{U} · b_{1}^{U}}} .  (8)

Even though we assume continuous variables in this example, our definition for the PLR and ELR operations (as well as the LR operation) applies to both continuous and discrete variables. We proved the following theorem concerning the PLR and ELR operations:

Theorem 2: (General Dominance Property) Let X^{∗} an exact solution to minimize a CH-function f(X).

(i) When f(X) is a monotonically-constrained CH-function, for any solution X′ of f(X), if X′ dominates X^{∗}, any pseudo-local refinement of X′ leads to a solution that still dominates X^{∗}; if X′ is dominated by X^{∗}, any pseudo-local refinement of X′ leads to a solution that is still dominated by X^{∗}. (ii) When f(X) is a bounded CH-function, for any solution X′ of f(X), if X′ dominates X^{∗}, any extended-local refinement of X′ leads to a solution that still dominates X^{∗}; if X′ is dominated by X^{∗}, any extended-local refinement of X′ leads to a solution that is still dominated by X^{∗}. The proof can be found in the Appendix to this paper. Because the simple CH-program is a subset of the monotonicallyconstrained CH-program, and the PLR operation is same as the LR operation in the case of simple CH-program, Theorem 2 also shows that the dominance property holds under the LR operation for the simple CH-program.

C. LR-based algorithm

Again, let X^{∗} be an exact solution to a CH-program. We say that a solution X is the lower bound of X^{∗} if X is dominated by X^{∗}, and X is an upper bound of X^{∗} if X dominates X^{∗}. Theorems 1 and 2 enable an algorithm based on different types of LR operations to compute a set of lower and upper bounds for X^{∗}.

Bound-Computation Algorithm

1. Initialize lower and upper bounds;

2. If lower and upper bounds do not meet

3. Perform ELR operation on every x_{i} of the lower bound iteratively;

4. Perform ELR operation on every x_{i} of the upper bound iteratively;

5. Goto 2 if there is any improvement in 3 and 4;

6. Return ELR-tight lower and upper bounds.

TABLE II Algorithm using the ELR operation to compute ELR-tight lower and upper bounds. The ELR operation may be replaced by the LR or PLR operation to compute LR-tight or PLR-tight (rather than ELR-tight) lower and upper bounds. In addition, the LR, PLR or ELR operation can be speeded up by the BLR operation. We will refer to the bound-computation algorithm as the LR-based algorithm, where LR, in general, refers to the LR, PLR, ELR and BLR operations.

Because the bounded CH-program is the most general case, we use the ELR operation to illustrate the bound-computation algorithm (see Table II). Starting with the initial lower and upper bounds (L and U), the algorithm carries out interleaved passes of lower- and upper-bound computations. A pass of lower-bound computation will perform an ELR operation on every x_{i} of a lower bound X in an arbitrary order. Because X is dominated by X^{∗}, its extended-local refinement becomes closer to X^{∗} but is still a lower bound. Similarly, a pass of upper bound computation will perform an ELR operation on every x_{i} of an upper bound X. The iteration of passes is stopped when the lower and upper bounds meet for every x_{i}, or both bounds are ELR-tight. We say that a lower or upper bound is ELR-tight if it can not be improved by any ELR operation.^{7} Although the ELR operation may use any valid lower and upper bounds for coefficients according to Definition 6, in general, the closer the lower and upper bounds for coefficients, the smaller the gap between the resulting ELR-tight lower and upper bounds. Because reducing the size of the solution space may narrow the range for coefficients, lower- and upper-bound computations are carried out alternately. The algorithm guarantees that within the resulting ELR-tight lower and upper bounds, there would exist an exact solution to the bounded CH-program.

For a simple or monotonically-constrained CH-program, we may replace the ELR operation in Table II by the LR or PLR operation. Then, the algorithm computes the LR-tight or PLRtight lower and upper bounds, where a lower or upper bound of an exact solution is LR-tight or PLR-tight if it can not be

7Even though the lower and upper bounds are ELR-tight, there may still be a gap between them. We say that the computation for a variable x_{i} is convergent if its lower and upper bounds are identical. The ELR operation does not guarantee the convergence for all variables. We define the convergence rate as the percent of variables that has identical lower and upper bounds. Both average gap among all variables and convergence rate will be presented for our experiments in Sections III-D and IV-E.

improved by any LR or PLR operation. In essence, the boundcomputation algorithm generalizes the greedy wiresizing algorithm GWSA that has been used for computing LR-tight lower and upper bounds for the exact wire sizing solution under fixed c_{a} and c_{ef} in [4], [5]. When the exact solution has the monotone property like those for the single-source and multi-source wire sizing problems [4], [5], the bundled-LR (BLR) operation [5] can be used to speed up the LR, PLR or ELR operation. We also use the LR-based algorithm to refer to the bound-computation algorithm, where LR, in general, refers to the LR, PLR, ELR and BLR operations.

The LR-based algorithm has the same worst-case complexity when using different types of LR operations. Let r be the average number of the possible values for variables x_{i}(i = {1, ⋯, n}) ∈ X when all variables x_{i} have discrete values. Because each pass of the lower- and upper-bound computation at least changes the value of one variable to narrow the solution space by at least one unit, the worst-case number of passes is Θ(r · n). In addition, each pass has at most 2n LR operations. Therefore, the bound-computation algorithm needs Θ(r · n^{2}) LR operations. We observed in our experiments that the total number of LR operations is much smaller than Θ(r · n^{2}) and is empirically linear with respect to the number of variables.

D. Comparison with the posynomial program

In order to better appreciate the implications of Theorems 1 and 2, we compare the CH-programs with the posynomial program (defined in Footnote 6). When every variable is of continuous value, the posynomial program has the important property that the local optimum is unique, and therefore is also the global optimum. The posynomial program plays an important role in the device and wire sizing works. In [21], the transistor sizing problem was first formulated as a posynomial program and solved by a sensitivity-based method. Later on, the posynomial program formulation was used for transistor sizing [22], wire sizing [23] and simultaneous gate and wire sizing [9], and was solved by being transformed into the convex program.^{8} Note that optimality of these solutions depends on the assumption that the local optimum is unique. The assumption holds for the continuous sizing formulation and simple models for the interconnect capacitance and device delay, but may be not true for the discrete sizing formulation and more general models for the interconnect capacitance and device delay.

Our LR-based algorithm is similar to the coordinate descent approach [24] for the posynomial program. The approach iteratively optimizes the value for each variable (i.e., coordinate) while keeping the values for the rest of the variables fixed.^{9} Because the local optimum is unique for the posynomial program regarding continuous variables, one may even start with an arbitrary solution (see [25]) rather than a lower or upper bound used in the LR-based algorithm. However, when the variables x_{1}, x_{2}, ⋯, x_{n} are of discrete values for the simple CHprogram, or when the coefficients are not constants as in the monotonically-constrained or bounded CH-program (for both

8Same as the method in [9] that we reviewed in Section 1, methods in [22], [23] minimize the maximum delay.

9An alternative method, called the steepest descent approach or the gradient method [24], minimizes the objective function along the direction of the steepest gradient, and may simultaneously change all coordinates. In general, it is n − 1 times faster than the coordinate descent approach, where n is again the number of variables [24]. However, because of the special nature of the sizing problems, the LR-based optimization (the coordinate descent approach) turns out to be very efficient in experiments. In fact, it was recently shown that when using the simple device and capacitance models, the LR-based algorithm can be finished in a linear time for the continuous wire sizing problem [25].

continuous or discrete variables), there may be more than one local optimum.^{10} Then, the global optimum can not be achieved by the coordinate descent approach starting from an arbitrary solution. However, the LR-based algorithm, which uses the LR or PLR operation for a simple or monotonically-constrained CHprogram, or uses the ELR operation for a bounded CH-program, can still be used to compute lower and upper bounds for the exact (i.e., globally optimal) solution. We will apply the ELR operation to the simultaneous transistor and interconnect sizing problem under the STL-bounded device model, and apply the PLR and ELR operations to the global interconnect sizing and spacing (GISS) problem considering the coupling capacitance for multiple nets. Both problems are no longer the simple CH-program, and may have multiple local optimum solutions.

III. STIS Problem under STL-Bounded Device Model

A. Problem formulation

Our formulation is similar to that in [7]. The delay is computed based on a stage. It is defined as a DC-connected path from a power supply (either the Vdd or the ground) to the gate node of a transistor, containing both transistors and wires. The delay of a stage P (N_{s}, N_{t}) with N_{s} being the source and N_{t} being the sink can be written as Eqn. (9) under the Elmore delay model.

t(P (N_{s}, N_{t}), X)
= ∑_{i,j} f(i, j) · \frac{r_{0}(i)}{x_{i}} · c_{a}(j) · x_{j} + ∑_{i,j} f(i, j) · \frac{r_{0}(i)}{x_{i}} · c_{ef} (j)

+ ∑_{i} g(i) · \frac{r_{0}(i)}{x_{i}} + ∑_{i} r_{0}(i) · h(i) + ∑_{i} h(i) · \frac{r_{0}(i)}{x_{i}} (9)

where x_{i} is the width for a transistor M_{i} or a wire E_{i}, r_{0}(i) is its unit-size effective-resistance, and c_{a}(i) and c_{ef} (i) are its unitarea capacitance and unit-length effective-fringe capacitance. Coefficients f(i, j), g(i) and h(i) are determined by the transistor netlist and routing topology.

In order to simultaneously minimize delays along multiple critical paths, we minimize the weighted delay t(X) of all stages in the set of critical paths denoted as P:

t(X) = ∑_{P (N_{s},N_{t})∈P} λ_{st} · t(P (N_{s}, N_{t}), X)  (10)

where the weight λ_{st} indicates the criticality of stage P (N_{s}, N_{t}). After we eliminate those terms independent of X, Eqn. (10) can be re-written as

t(X)
= ∑_{i,j} F (i, j) · \frac{r_{0}(i)}{x_{i}} · c_{a}(j) · x_{j} + ∑_{i,j} F (i, j) · \frac{r_{0}(i)}{x_{i}} · c_{ef} (j)

+ ∑_{i} G(i) · \frac{r_{0}(i)}{x_{i}} + ∑_{i} H(i) · \frac{r_{0}(i)}{x_{i}}  (11)

where F (i, j), G(i) and H(i) are weighted functions of f(i, j), g(i) and h(i), respectively.

We formulate the following simultaneous transistor and interconnect sizing (STIS) problem:

Formulation 1: Given the lower and upper bounds (L and U) for the width of each transistor and wire, the STIS problem is to

10The simple CH-program using continuous variables belongs to the posynomial program, and therefore has a unique local optimum.

determine a width for each transistor and wire (or equivalently, a sizing solution X, L ≤ X ≤ U) such that the weighted delay through multiple critical paths given by Eqn. (11) is minimized. Note that a sequence of weighted-delay minimization can be used to minimize the maximum delay by adjusting the weight assignment based on the Lagrangian-relaxation method as in [11]. Therefore, we focus on how to minimize weighted delay in this paper. In addition, we assume that the possible width is from a discrete width set determined by the technology. The discrete sizing problem is more difficult than the continuous sizing problem, but is more convenient for placement and routing tools and fabrication.

B. Bound computation for the STIS problem

Under the simple models, r_{0}, c_{a} and c_{ef} are constants for each wire/transistor, and Eqn. (11) is a simple CH-function. In this case, the STIS problem is a simple CH-program solved in [7]. Because the simple models are no longer valid for DSM designs, we study the STIS problem under the STL-bounded device model that is more suitable for DSM designs. For simplicity of presentation, we assume here that c_{a} and c_{ef} are constants for each wire segment, but will remove the assumption in Section IV.

In the STL-bounded model, r_{0} is pre-computed and stored in tables (e.g., see Table I) indexed by the size, input switching time (t_{s}), and output load (c_{l}). It could be very accurate depending on the table size.^{11} Because the value for r_{0} is bounded, it is easy to verify the following Theorem 3:

Theorem 3: The STIS problem under the STL-bounded device model is a general CH-program.

Note that the STL-bounded model might not be monotonic with respect to the sizing solution X. Therefore, the STIS problem is unlikely a monotonically-constrained CH-program, and the LR and PLR operations are not applicable. It can be justified by the following observations: r_{0} in our model is a monotonic function of t_{s}, whereas t_{s} is not monotonic with respect to X, because the optimal wire sizing solution (see [4], [23], [5]) to minimize t_{s} often has neither minimum nor maximum wire width.

Therefore, the ELR operation is needed in the LR-based algorithm (Table II) to compute lower and upper bounds for an exact solution to the STIS problem. We assume that r_{0}(i) ∈ [r_{0}^{L}(i), r_{0}^{U}(i)] and r_{0}(j) ∈ [r_{0}^{L}(j), r_{0}^{U}(j)]. In an ELR operation on a transistor M_{i} for the lower-bound computation, we use r_{0}^{L}(i) instead of r_{0}(i), and r_{0}^{U}(j) instead of r_{0}(j) for M_{j}, where M_{j} is an upstream transistor in the same net for M_{i}. Symmetrically, in an ELR operation on M_{i} for the upperbound computation, we use r_{0}^{U}(i) instead of r_{0}(i) for M_{i}, and r_{0}^{L}(j) instead of r_{0}(j) for an upstream transistor M_{j}.

We determine r_{0}^{L}(i) as follows: Let X^{L} and X^{U} be lower and upper bounds of the exact solution X^{∗}. We assume that transistor M_{i} has size x_{i} ∈ [x_{i}^{L}, x_{i}^{U}], input switching time t_{s}(i) ∈ [t_{s}^{L}(i), t_{s}^{U}(i)], and capacitance load c_{l}(i) ∈ [c_{l}^{L}(i), c_{l}^{U}(i)]. We often observe in our experiments that r_{0}(i) increases with respect to an increase of x_{i} or t_{s}(i), but decreases with respect to an increase of c_{l}(i). Therefore, r_{0}^{L}(i) for M_{i} can be obtained

11In our experiments, r_{0} table for a type of gate (e.g., an inverter) considers the combinations of five different device sizes (from 1x to 800x of the minimum size), three different input switching times, and five different load capacitances. Therefore, the total table size is 5 × 3 × 5 × m = 75m, where m is the number of gate types. Satisfactory optimization results are obtained according to experiments in Section III-D. For simplicity, we assume that c_{l} is the lumped capacitance in this paper. Extension to the effective capacitance model [14] is ongoing work and will be discussed briefly in Section V.

by table lookup using x_{i}^{L}, t_{s}^{L}(i) and c_{l}^{U}(i). Symmetrically, r_{0}^{U}(i) is determined using x_{i}^{U}, t_{s}^{U}(i) and c_{l}^{L}(i). In addition, contributions of transistors or wires to c_{l}^{U}(i) are computed using sizes in X^{U}, and contributions to c_{l}^{L}(i) computed using sizes in X^{L}. After the ELR operation on M_{i}, for every stage P (N_{i}, N_{j}) (N_{i} is the source, N_{j} is the sink) driven by M_{i}, we will update the lower and upper bounds for the switching time t_{s}(j) at sink N_{j}, because t_{s}(j) is the input switching time for the transistor M_{j} with gate connected to node N_{j}. The lower or upper bound of t_{s}(j) is assumed to be the lower or upper bound of the delay through P (N_{i}, N_{j}), respectively. As X^{L} and X^{U} move closer during the ELR-based optimization procedure, the range of r_{0} is also narrowed. In general, the closer the values for r_{0}^{U} and r_{0}^{L}, the smaller the gap between the lower and upper bounds given by the ELR operations.

Because the unit-size resistance r_{0}(i) is a constant for each wire segment E_{i}, we can simply use the LR operation for E_{i}. Furthermore, in order to achieve better wire sizing solutions, we can divide a wire segment into a sequence of uni-segments, then find a wire width for each uni-segment [5]. We assume that each segment always stays in the same layer, has the fixed r_{0}, c_{a} and c_{ef}, as well as same allowable wire widths.^{12} With these assumptions, we have proved the following local monotone property:

Theorem 4: (local monotone property) There exists an optimal STIS solution where the wire widths for uni-segments are monotonic within each wire segment. The proof is available from the technical report [17]. This theorem enables us to use the BLR operation [5] instead of the LR operation for each wire segment E_{i}. The BLR operation is shown to be 100x faster than the LR operation for the wiresizing problem [5].

C. Overall algorithm for the STIS problem

Let L′ and U′ be the ELR-tight lower and upper bounds given by the above bound-computation procedure. If L′ and U′ are identical, we obtain the exact solution to the STIS problem under the STL-bounded model. Otherwise, we traverse all wire segments and transistors by iterative PLR operations until there is no improvement in the last round of traversal. Note that the PLR operation is bounded by L′ and U′, and it uses r_{0} obtained from the device table. Even though the PLR operation may lead to further improvement over L′ and U′, in general it does not lead to a lower or upper bound of the exact solution.^{13}

Our experiments in Section III-D.2 show that the ELR-tight lower and upper bounds (L′ and U′) are often close to each other in most cases. Therefore, we can simply treat L′ as the final solution (for smaller area and often lower power-dissipation). Note that the STIS problem to minimize a weighted-sum of delay and area is shown to be a CH-program in [7], with a smooth trade-off obtained between delay and area. A similar approach can be used to better minimize the capacitive power by minimizing the weighted-sum of delay and capacitive power.

D. Experimental results

For all experiments in this paper, we computed the delays via HSPICE using the distribute RC model and the level-3 MOS-FET model that is also used in HSPICE simulations for devicetable generation. The use of HSPICE simulation results not

12Different segments may have different r_{0}, c_{a} and c_{ef} if they are in different layers, or have different spacings to neighboring wires.

13In our experiments, we tried to use PLR operations starting from either the minimum or maximum sizing solution. The resulting solutions are often outside the range defined by L′ and U′, and are worse than L′.

only shows the quality of our sizing solutions, but also verifies the validity of our interconnect and device modeling, and the correctness of our problem formulations.

D.1. Comparison between manual optimization and STIS algorithm. To illustrate the effectiveness of the STIS algorithm, we first compare the sizing solution obtained by our algorithm and the manual optimization applied to a spread spectrum IF transceiver chip in [26]. The design is under the 1.2 μm twolayer metal SCMOS technology. There are two clock nets, dclk and clk; each uses a chain of four cascade drivers in the clock signal source and chains of four cascade buffers in order to drive long interconnects and register files. The maximum delays of the two nets need to be minimized to reduce the clock skew. Therefore, source drivers and buffers are tuned manually via iterative procedures of layout, extraction and HSPICE simulation. We retain the manual sizing solutions for the first stage drivers at the source and for the drivers of the register files, then apply the STIS algorithm to optimize the sizes for every 10μm-long wire and the rest of the drivers and buffers. We use two formulations under the simple device model, one is simultaneous transistor and wire sizing formulation (stis/simple) where optimal sizes are found for p- and n- transistors in each driver/buffer, and the other one is simultaneous gate and wire sizing formulation (sgws/simple) where an optimal size is found for each driver/buffer. We also assume that the allowable wire widths are {w, 2w, 3w, 4w, 5w} with w = 1.2μm being the minimum wire width in the 1.2μm technology, and the allowable transistor sizes are multiples of 0.6μm between 1.2μm and 500μm. The constant value for r_{0} in the simple model is determined under the typical input switching time, device size and output load. The fixed ratio between p- and n- transistors in the sgws/simple formulation is tuned to make sure that the inverter will have same pull-up and pull-down resistance values.

Because the simple device model is applied, we use the LR operation to compute the LR-tight lower and upper bounds for devices. Experiments show that the identical LR-tight lower and upper bounds are achieved for almost all devices and wire segments, therefore we use the LR-tight lower bounds as the final sizing solution. We report HSPICE simulation results in Table III. When compared with the manual optimization, sgws/simple and stis/simple formulations reduce the maximum delay by up to 6.2% and 14.4%, respectively. More significantly, both reduce the power consumption by 42.6% and 42.8%. Because we use the same simple model for two formulations in this experiment, the extra delay reduction (8.2%) of the stis/simple formulation comes from the flexibility of the transistor sizing formulation.

D.2. Comparison between simple and STL-bounded models. We then apply our STIS algorithm under different device models. We use the 0.18 μm technology given in the NTRS [12] in order to study the impact of the DSM technologies. The wire sheet-resistance R_{□} = 0.0638Ω. We generate device and capacitance tables via HSPICE simulations and numerical extractions, respectively, and use c_{a} and c_{ef} values where the wire is 1.10μm wide and neighboring wires are 1.65μm away. We size two global nets, one is a 2cm line with five buffers optimally inserted for delay minimization. The other is the above dclk net. In addition to different device models (simple model versus STL-bounded model), we also use different sizing formulations (sgws versus stis). There are four combinations, including sgws/simple and stis/simple using the LR operation for devices, and sgws/bounded and stis/bounded using the ELR operation for devices. For simplicity, we assume that the fixed ratio between p- and n- transistors for the gate sizing formulation is 1.0. For both nets, we find the optimal wire width for each 10 μm-long wire, and assume that allowable transistor sizes are multiples of 0.18μm between 0.18μm and 144μm, and that allowable wire widths are multiples of 0.56μm between 0.56μm and 5.6 μm. Table IV summarizes experimental comparisons between different formulations. We computed convergence rate under different formulations. For the simple model, the computation for a transistor or wire is convergent if its LR-tight lower and upper bounds are identical. For the STL-bounded model, the computation for a transistor or wire is convergent if its ELRtight lower and upper bounds are identical. The convergence is not significantly different. For example, computations for about 85% transistor are convergent in dclk net under all four formulations. We also computed the average width and the average gap between lower and upper bounds for all wire segments and transistors, respectively. The ELR operation does give larger gap than the LR operation. However, the difference is small. Overall, the average gap is only 1% of the average width, except that net dclk has a large gap, nearly 10% of the transistor size. We simply use the ELR-tight lower bound as the final solution under the STL-bounded model, and the LR-tight lower bound as the final solution under the simple model, because lower and upper bounds given by bound computations are very close to each other. Table IV also give the maximum delay via HSPICE simulation. The solutions under the STL-bounded model are consistently better than those under the simple device model. When compared with the sgws/simple formulation, the sgws/bounded formulation further reduce the maximum delay by up to 6.4%. When compared with the stis/simple formulation, the stis/bounded formulations further reduce the maximum delay by up to 15.1%. Note that both sgws/simple and stis/simple formulations already give very good sizing solutions as shown in the experiment of Section III-D.1. Although ELR operations under the STL-bounded model are more complex, the runtime is still impressively small. It used just 3.17 seconds to optimize dclk net of 154 buffers and 41518.2μm wires, with two optimal transistor sizes for a buffer and one optimal width for each 10μm-long wire. Therefore, our STIS algorithm is extremely efficient.

IV. GISS problem considering coupling capacitance

The unit-area capacitance c_{a} and unit-length effective-fringe capacitance c_{ef} are assumed to be constants for each wire segment in the STIS problem in Section III. We shall proceed to remove this assumption using the more general WS-bounded capacitance model in this section. For simplicity of presentation, we assume that the device sizes are fixed, and study the global interconnect sizing and spacing (GISS) problem for multiple nets with consideration of the coupling capacitance. However, our algorithm and implementation are able to use the STL-bounded device model and the WS-bounded capacitance model (with consideration of the coupling capacitance) at the same time.

A. Problem formulation

Our GISS formulation was first presented in [16]. We assume that an initial layout is a priori given and defines the initial central-line for each wire segment. The initial pitch-spacing, i.e., the distance between the initial central-lines, remains unchanged during the sizing procedure. We consider two wire sizing formulations. One is the symmetric wire sizing formulation, where wires are always symmetric with respect to initial central-lines as illustrated in Figure 4(a). In contrast, in the asymmetric wire sizing formulation shown in Figure 4(b), wires of same widths

# of  wire length  max delay (ns)  average power (mW)
net drivers/buffers  (μm)  manual  sgws/simple  stis/simple  manual  sgws/simple  stis/simple
dclk  154  41518.2  4.6324 4.3447(-6.2%) 3.9635(-14.4%)  60.85  46.09(-24.3%) 46.29(-24.2%)
clk  367  59304.0  6.2016 6.1578(-0.7%) 5.9035(-4.8%)  499.7  286.8(-42.6%) 285.6(-42.8%)

TABLE III

Comparison between manual optimization and STIS algorithms: manual – manual optimization via iterative procedure of

layout, extraction and HSPICE simulation; sgws/simple – simultaneous gate and wire sizing under the simple model; stis/simple – simultaneous transistor and wire sizing under the simple model. The LR operation is used for devices, and the

BLR operation for wires.

net  sgws/simple sgws/bounded  stis/simple  stis/bounded  sgws/simple sgws/bounded  stis/simple stis/bounded
convergence rate for transistors  convergence rate for wire
dclk  85.8%  83.2%  87.7%  86.7%  99.4%  95.9%  97.1%  95.2%
line  60.0%  100%  70.0%  60.0%)  98.4%  70.9%  88.4%  72.9%
average width / average gap (for transistors, μm)  average width / average gap (for wires, μm)
dclk  5.39/0.07  13.0/1.91  17.2/1.53  21.6/2.36  2.50/0.003  2.78/0.025  2.69/0.017  2.82/0.030
line  108/0.108  112/0.0  126/0.97  125/1.98  4.98/0.004  4.99/0.106  5.05/0.032  5.11/0.091
maximum delay (ns)  runtime (s)
dclk  1.159 (0.0%)  1.007(-6.4%)  1.132(0.0%) 0.961 (-15.1%)  1.18  2.32  0.88  3.17
line  0.821  0.818(-0.4%)  0.751(0.0%)  0.694(-7.6%)  0.72  0.58  0.55  1.22

TABLE IV

Comparisons between different device and wire sizing algorithms: sgws/simple – simultaneous gate and wire sizing under the

simple model; sgws/bounded – simultaneous gate and wire sizing under the bounded model; stis/simple – simultaneous transistor and wire sizing under the simple model; and stis/bounded – simultaneous transistor and wire sizing under the

bounded model. The BLR operation is used for wires, while the LR operation is used for devices in sgws/simple and stis/simple, and the ELR operation for devices in sgws/bounded and stis/bounded.

are asymmetric with respect to initial central-lines, and have smaller capacitance and less delay. Because neighboring wires are, in general, asymmetrically away from interested nets, the asymmetric wire sizing formulation is capable of further reducing the interconnect delay.

Fig. 4. (a) symmetric wire sizing, and (b) asymmetric wire sizing.

The asymmetric wire sizing has smaller capacitance and less delay.

Given the asymmetric formulation, in general, the wire sizing solution for wire segment E_{i} needs to be represented by a pair of widths (x_{i}^{↑}, x_{i}^{↓}), where x_{i}^{↑} is the width of the piece of wire above (or left to) the initial central-line when E_{i} is a horizontal (or vertical) segment, and x_{i}^{↓} the width of the piece of wire on the other side of the initial central-line. Similarly, we denote the spacing above (or left to) E_{i} as s_{i}^{↑}, and spacing on the other side as s_{i}^{↓}. In order to maintain the connectivity, we say that a wire width x_{i} is valid if x_{i}^{↑} and x_{i}^{↓} are at least W_{min}/2, where W_{min} is the minimum wire width set by the manufacture technology.

With consideration of both symmetric and asymmetric wire sizing formulations, we define the following GISS problem:

Formulation 2: Given multiple nets with initial central-line for each wire segment E_{i}, the GISS problem is to determine a valid wire width (x_{i}^{↑}, x_{i}^{↓}) for each E_{i} with respect to its initial central-line, such that the weighted delay given by Eqn. (11) is minimized for multiple critical paths over these nets. Note that, as shown in Figure 2, both c_{a} and c_{ef} are functions of wire widths and spacings. In the following, we shall first consider the symmetric wire sizing formulation, then extend our algorithms to the asymmetric wire sizing formulation.

B. Bound computation for the symmetric GISS problem

Our WS-bounded capacitance model is a table-based model simplified from the 2.5D capacitance model in [27]. In this model, for a wire segment E with width w and spacing s^{↑} and s^{↓} to its two nearest neighboring wires, we denote c_{a} as c_{a}(w, s^{↑}, s^{↓}), and c_{ef} as c_{ef} (w, s^{↑}, s^{↓}). Furthermore, for two spacing values s_{1} and s_{2}, we have shown in [27] that the following approximations

c_{a}(w, s_{1}, s_{2}) = {c_{a}(w, s_{1}, s_{1}) + c_{a}(w, s_{2}, s_{2})}/2, (12)
c_{ef} (w, s_{1}, s_{2}) = {c_{ef} (w, s_{1}, s_{1}) + c_{ef} (w, s_{2}, s_{2})}/2 (13)

are accurate enough. Therefore, we only need to use the numerical capacitance extraction to solve the basic geometric structure with equal spacings (see Figure 1). We consider different width and spacing combinations, and store c_{a} and c_{ef} in twodimensional tables indexed by widths and spacings. Then, for the given wire segment with width w and spacings s^{↑} and s^{↓} to its two nearest neighboring wires, c_{a}(w, s^{↑}, s^{↓}) and c_{ef} (w, s^{↑}, s^{↓}) are obtained from two-dimensional tables using Eqn. (12)-(13). Justifications and more details about the capacitance model can be found in [27], and the capacitance table used for this paper is available from the technical report [17].

For wire segment E_{i} with width x_{i} = (x_{i}^{↑}, x_{i}^{↓}) and spacing (s_{i}^{↑}, s_{i}^{↓}), let s_{i}^{↑} and s_{i}^{↓} be the spacings between E_{i} and its neighboring wire segments E_{j} and E_{k}, respectively. Because our GISS formulation assumes that the initial central-lines are fixed, s_{i}^{↑} can be determined by x_{i}^{↑} and x_{j}^{↓}, and s_{i}^{↓} by x_{i}^{↓} and x_{k}^{↑}. Therefore, c_{a}(i)(x_{i}, s_{i}^{↑}, s_{i}^{↓}) and c_{ef} (i)(x_{i}, s_{i}^{↑}, s_{i}^{↓}) can be rewritten as c_{a}(i)(x_{i}^{↑}, x_{i}^{↓}, x_{j}^{↓}, x_{k}^{↑}) and c_{ef} (i)(x_{i}^{↑}, x_{i}^{↓}, x_{j}^{↓}, x_{k}^{↑}). Because coefficients c_{a} and c_{ef} are bounded, we have the following Theorem 5:

Theorem 5: The GISS problem under the WS-bounded capacitance model is a bounded CH-program. Note that the GISS problem is easier than the STIS problem in the sense that coefficient c_{a} or c_{ef} in GISS is a function of just four variables, whereas coefficient r_{0} in STIS may depend on all variables.

Based on this theorem, we may use the ELR operation to compute the lower and upper bounds for x_{i}^{∗}, the optimal width for a wire segment E_{i}. We assume that c_{a} ∈ [c_{a}^{L}, c_{a}^{U}] and c_{ef} ∈ [c_{ef}^{L} , c_{ef}^{U}]. In an ELR operation on a wire E_{i} during the lowerbound computation, we use c_{a}^{U}(i) and c_{ef}^{L} (i) instead of c_{a}(i) and c_{ef} (i) for E_{i}, and use c_{a}^{L}(j) and c_{ef}^{L} (j) instead of c_{a}(j) and c_{ef} (j) for E_{j}, where E_{j} is a downstream segment in the same net as E_{i}. Similarly, during the upper-bound computation for E_{i}, we use c_{a}^{L}(i) and c_{ef}^{U} (i) instead of c_{a}(i) and c_{ef} (i) for E_{i}, and use c_{a}^{U}(j) and c_{ef}^{U} (j) instead of c_{a}(j) and c_{ef} (j) for downstream segment E_{j}.

The bound-computation for the GISS problem can be simplified when the WS-bounded model is monotonically-constrained. We first define the following monotonically-constrained capacitance table:

Definition 7: A capacitance table is monotonically-constrained if the following is true with respect to the basic geometric structure in Figure 1: for any two combinations of widths and spacings (w_{1}, s_{1}) and (w_{2}, s_{2}), if w_{1} ≤ w_{2} and s_{1} ≥ s_{2}, then c_{a}(w_{1}, s_{1}, s_{1}) ≥ c_{a}(w_{2}, s_{2}, s_{2}), c_{a}(w_{1}, s_{1}, s_{1}) · w_{1} ≤ c_{a}(w_{2}, s_{2}, s_{2}) · w_{2}, and c_{ef} (w_{1}, s_{1}, s_{1}) ≤ c_{ef} (w_{2}, s_{2}, s_{2}), Intuitively, when the width increases and the spacing decreases, c_{ef} often increases because of the larger coupling capacitance (see c_{ef} for center-to-edge spacing = 1.1μm in Figure 2(b)). Also, the unit-area capacitance c_{a} often decreases because of the stronger shielding effect due to that the neighboring wires are closer. Note that the unit-length area-capacitance (like c_{a}(w_{1}, s_{1}, s_{1}) · w_{1} and c_{a}(w_{2}, s_{2}, s_{2}) · w_{2}) often still increases even though the unit-area capacitance c_{a} decreases.

We say that the WS-bounded model is monotonically-constrained if its capacitance table is monotonically-constrained. We proved the following theorem (the proof is available from [17]):

Theorem 6: The GISS problem under the WS-bounded capacitance model is a a monotonically-constrained CH-program if the capacitance model is monotonically-constrained. In this case, the PLR operation can be used instead of the ELR operation. To tighten a lower- (upper-) bound x_{i} for a wire E_{i}, we assume that its neighboring wires have lower- (upper-) bound widths at spacings s_{i}^{↑} and s_{i}^{↓} away from E_{i}. We obtain c_{a}(x_{i}, s_{i}^{↑}, s_{i}^{↓}) and c_{ef} (x_{i}, s_{i}^{↑}, s_{i}^{↓}) by table lookup, and perform an PLR operation on x_{i}. Compared with the ELR operation, the PLR operation is more efficient and may lead to smaller gaps between lower and upper bounds.

In order to exploit the optimality of the ELR operation and the efficiency of the PLR operation, our implementation of the ELR operation is a hybrid of both operations. When working on a wire E_{i}, we first check capacitance values with respect to all valid widths and spacings for E_{i},^{14} then use an PLR operation if Definition 7 is satisfied. Otherwise, we use an ELR operation. By using the ELR or PLR operation, we obtain lower and upper bounds only for the optimal total-width x_{i}^{∗}. If the resulting bound is x_{i}, we assign x_{i}^{↑} = x_{i}^{↓} = x_{i}/2 for the symmetric GISS problem. Therefore, starting with the minimum and maximum symmetric wire sizing solutions for all wire segments, and using iterative ELR or PLR operations, we can compute ELR-tight lower and upper bounds for the globally optimal solution to the symmetric GISS problem.

Note that Theorem 6 also enables the LR operation for the GISS problem when the WS-bounded model is monotonicallyconstrained. It is less efficient than the PLR operation as shown in the following: we assume that for wire segment E_{i} with width x_{i} = {x_{i}^{↑}, x_{i}^{↓}}, there are ten choices for both x_{i}^{↑} and x_{i}^{↓}. Because c_{a} and c_{ef} in the WS-bounded model depend on x_{i}^{↑} and x_{i}^{↓}, we need to enumerate these width choices to find the local optimal value for x_{i}. It costs ten computations for the symmetric wire sizing formulation, and 10×10 computations for the asymmetric wire sizing formulation. On the other hand, the PLR operation needs only one computation to find out the pseudo-local optimal value for x_{i}. Even though the LR operation may need fewer numbers of passes of lower- and upper-bound computations in the bound-computation algorithm, overall, using LR operations is less efficient than using PLR operations in our experiments.

C. Bound computation for the asymmetric GISS problem

We first extend the dominance relation to consider the asymmetric wire sizing formulation. We say that the wire sizing solution X dominates another solution X′ (denote as X ≥ X′), if (x_{i}^{↑}, x_{i}^{↓}) ≥ (x′_{i}^{↑}, x′_{i}^{↓}) (i.e., x_{i}^{↑} ≥ x′_{i}^{↑} and x_{i}^{↓} ≥ x′_{i}^{↓}) holds for any wire segment E_{i}. A lower and upper bound of the exact solution to the asymmetric GISS problem will be determined according to the new definition of dominance relation.

We solve the asymmetric GISS problem by augmenting the bound-computation algorithm presented in Section IV-B. Each ELR or PLR operation gives only the total-width x_{i}, which is a lower or upper bound of the optimal total-width x_{i}^{∗} for E_{i}. To obtain an asymmetric wire sizing solution, we need to separate x_{i} into x_{i}^{↑} and x_{i}^{↓}, which are respective widths for the “two pieces” of wires around the initial central-line of E_{i}. This separation is equivalent to embed a wire with total-width x_{i} around the initial central-line of E_{i}. It also affects the ELR and PLR operations in the subsequent steps. We propose to perform a conservative embedding right after any ELR or PLR operation.

We assume that x_{i}^{∗} = (x_{i}^{↑∗}, x_{i}^{↓∗}) is the width for E_{i} in the exact asymmetric solution. Let x_{i}^{↑L} and x_{i}^{↑U} be the lower and upper bounds for x_{i}^{↑∗}, and x_{i}^{↓L} and x_{i}^{↓U} the lower and upper bounds for x_{i}^{↓∗}. If we obtain a total-width x_{i}^{L} in the lower-bound computation, the conservative embedding (CE) operation computes x_{i}^{↓L} = x_{i}^{L} − x_{i}^{↑U}, which is a conservative lower-bound for x_{i}^{↓∗}. Similarly, x_{i}^{↑L} = x_{i}^{L} − x_{i}^{↓U} is a conservative lower bound for x_{i}^{↑∗}. Note that the sum of x_{i}^{↑L} and x_{i}^{↓L} may be less than x_{i}^{L} in the CE operation. Symmetrically, for an upper-bound x_{i}^{U}, we compute x_{i}^{↑U} = x_{i}^{U} − x_{i}^{↓L}, and x_{i}^{↓U} = x_{i}^{U} − x_{i}^{↑L}. This augmented algorithm leads to the lower and upper bounds of the exact solution to the asymmetric GISS problem.

14A dynamic-programming scheme is used based on two-dimensional cache tables, which, similar to our capacitance tables, are indexed by widths and spacings. For given width and spacing, the cache tables return the minimum or maximum values for c_{a} and c_{ef}, or imply that the PLR operation can be used.

We also propose a greedy embedding (GE) operation. Recall that neighboring wires of E_{i} have their lower- (upper-) bound widths during lower- (upper-) bound computation for E_{i}. If the lower or upper bound of wire width for E_{i} is x_{i}, we find x_{i}^{↑} and x_{i}^{↓} such that x_{i}^{↑} + x_{i}^{↓} = x_{i} and the objective function Eqn. (11) is minimized with respect to the given neighboring wires. Different from the CE operation, the GE operation does not always lead to a lower or upper bound of the exact solution for the asymmetrical GISS problem. We will show, however, that the GE operation has a higher convergence rate than the CE operation in experiments, and achieves satisfactory experimental results in Section IV-E. Again, we say the computation on a wire segment is convergent if lower and upper bounds are identical.

D. Overall algorithm for the asymmetric GISS problem

Our overall asymmetric GISS algorithm (denoted as GISS/EPLR algorithm) is based on the ELR and PLR operations. It consists of the following steps (see Table V). First, we compute the ELR-tight lower and upper bounds using iterative ELR operations and CE operations. Then, we compute the PLR-tight “lower” and “upper” bounds using iterative PLR operations and GE operations. Finally, if the resulting lower and upper bounds do not meet, for each net that has non-convergent wire segments, we will assume that other nets have lower-bound wire widths, and invoke the single-net interconnect sizing and spacing (SISS) algorithm presented in [16] to find the final sizing and spacing solution within its lower and upper bounds. The SSIS algorithm combines the asymmetric wire sizing formulation and the wire sizing algorithm based on the bottom-up dynamic-programming technique [10].^{15} We apply the SSIS algorithm in the greedy order such that the more timing-critical net is processed earlier.

GISS/EPLR Algorithm

1. Compute ELR-tight lower and upper bounds using iterative ELR operations and CE operations;

2. Compute PLR-tight “lower” and “upper” bounds using iterative PLR operations and GE operations;

3. For all non-convergent nets in the greedy order, invoke single-net dynamic-programming based algorithm within resulting lower and upper bounds.

TABLE V

Asymmetric GISS algorithm based on ELR and PLR operations

E. Experimental results

We have tested our GISS algorithm on a 16-bit parallel bus structure. In this bus, each bit is a 1cm line with a 119 Ω driver resistance and a 12.0fF sink capacitance. We assume that initially these lines are equally spaced. We will find an asymmetric wire sizing for every 500μm-long wire segment. In addition, the minimum wire width is 0.22μm, and the minimum spacing 0.33μm. The allowable wire widths are from 0.22 to 1.1

15The SISS problem finds the optimal wire sizing and spacing solution for a single net, under the assumption that all its neighboring wires are fixed. The GISS/EPLR algorithm, i.e., first computing ELR-tight bounds based on the ELR operation, and then computing the final solution within bounds based on dynamic programming, can also be used to solve the SISS problem. It will be much more efficient than the purely dynamicprogramming based approach in [16].

μm, with the incremental step of 0.11 μm. The capacitance tables are generated using numerical capacitance extraction for the 0.18μm technology in Table 22 of NTRS [12].

We optimized the bus for different initial pitch-spacings, from 2x to 6x of the minimum pitch-spacing (0.55μm). Our GISS/EPLR algorithm has two bound-computation phases, the first one using ELR/CE operations and the second one using PLR/GE operations (see Table V). As shown in Table VI, computations for from 57% to 91% wire segments are convergent, i.e., identical lower and upper bounds are achieved for these segments after the ELR/CE phase. The PLR/GE phase further increases the convergence rate to at least 94%. We also reported the average gap between lower and upper bounds with respect to all wire segments. The average gap after the ELR/CE phase is between 0.013 μm and 0.090 μm, and becomes less than 0.0059 μm after the PLR/GE phase. Therefore, in most cases, our bound computation directly leads to the global and asymmetric wire sizing and spacing solution by obtaining identical lower and upper bounds for almost all wire segments. In addition, we report the average numbers of PLR operations and ELR operations for a wire segment. Note that our ELR implementation automatically invokes the PLR operation when the PLR operation does not lose the optimality; therefore, the number of PLR operations include PLR operations in the ELR/CE phase. An important observation is that in most cases the PLR operation is used. It implies that the GISS problem is mainly a monotonically-constrained CH-program.

The GISS/EPLR is the first algorithm we proposed for the GISS problem. It was also leveraged to reveal the effectivefringing property by assuming c_{a} and c_{f} are constants in [16]. The property enables a bottom-up dynamic programming technique to compute lower and upper bounds for the exact solution to the asymmetric GISS problem, when c_{a} and c_{f} are constants. We call the alternative algorithm GISS/FAF. It may be extended to use variable c_{a} and c_{f} under the WS-bounded capacitance model. In this case, the exact solution may be outside the range defined by the resulting lower and upper bounds, and we call the algorithm GISS/VAF. Both GISS/FAF and GISS/VAF algorithms further use the SISS algorithm to obtain final solutions within the lower and upper bounds, whereas the GISS/EPLR algorithm uses the lower bound as the final solution due to its high convergence. In addition, we also apply the SISS algorithm in a greedy order, which is equivalent to invoking only step 3 in the GISS/EPLR algorithm (Table V). The SISS algorithm obtains a local-optimal solution for the GISS problem.

We compare the average HSPICE delay for solutions given by these algorithms in Table VII (average delay is our objective function). As seen from the table, the GISS/EPLR algorithm always achieves results better than the SISS solutions, with up to 39% delay reduction. Therefore, it is important to find the globally optimal solution to the GISS problem. The improvement of the GISS/EPLR algorithm over the SISS algorithm is reduced when the pitch spacing increases, due to the fact that the coupling capacitance is less significant for larger pitch spacings. Nevertheless, compared with the SISS algorithm, the GISS/EPLR algorithm still reduces the average delay by 8.6% in the case of maximum pitch spacing. Both GISS/EPLR and GISS/VAF algorithms outperform the GISS/FAF algorithm because neither c_{a} and c_{f} is a constant in DSM designs. The GISS/EPLR algorithm obtains results similar to the GISS/VAF algorithm in smaller pitch-spacing cases, and achieves better results in the case of larger pitch-spacings. It is 11% and 5.9% better than the GISS/FAF and GISS/VAF algorithms, respec-

pitch-  Convergence  Average gap (μm) Average # of operations
spacing ELR/CE PLR/GE ELR/CE PLR/GE PLR  ELR
2x  91%  98.1%  0.013  0.0021  17.0  2.58
3x  77%  99.9%  0.040  0.0001  29.1  2.34
4x  65%  95.0%  0.069  0.0055  34.4  1.47
5x  57%  94.1%  0.090  0.0059  36.6  4.43
6x  69%  100%  0.066  0.0000  37.4  4.35

TABLE VI Convergence of ELR/CE and PLR/GE in GISS/EPLR algorithm.

pitch-  Average Delay (ns)  Run Time (s)
spacing SISS GISS/FAF GISS/VAF GISS/EPLR GISS/VAF GISS/EPLR
2x  1.31 0.81(-38%) 0.79(-39%) 0.79(-39%)  183  3.68
3x  0.72 0.56(-22%) 0.53(-26%) 0.52(-27%)  189  4.69
4x  0.46 0.46(-0.0%) 0.42(-8.7%) 0.42(-8.7%)  511  4.62
5x  0.38 0.39(+2.6%) 0.37(-2.6%) 0.36(-5.3%)  1083  6.82
6x  0.35 0.36(+2.9%) 0.34(-2.9%) 0.32(-8.6%)  1379  9.26

TABLE VII

Comparison of different sizing algorithms when sizing 16-bit buses under 2x-6x minimum pitch-spacing. SISS is single-net

interconnect sizing and spacing algorithm applied to multiple nets in a greedy order; GISS/FAF and GISS/VAF are bottom-up dynamic programming algorithms; GISS/EPLR is the algorithm presented in this paper.

tively, in the case of maximum pitch-spacing. Most significantly, the GISS/EPLR algorithm runs 100x faster. It also uses much less memory.

Note that even though we show in [16] that the dynamicprogramming based GISS algorithm leads to lower- and upperbounds of the exact solution to the GISS problem only under constant c_{a} and c_{f} (i.e., GISS/FAF), we believe that when the capacitance model is monotonically-constrained (and GISS problem is a monotonically-constrained CH-program), the algorithm (i.e., GISS/VAF) still leads to lower- and upper-bounds of the exact solution. However, the capacitance model is no longer monotonically-constrained in the case of large pitch-spacings as shown by c_{ef} for center-to-edge spacing = 2.2μm in Figure 2(b). Therefore, the GISS/EPLR obtains better results for large pitch-spacings (5x and 6x cases in Table VII). Because the GISS/EPLR algorithm is much faster and always achieves the best results, we suggest that the GISS/EPLR algorithm shall be used instead of other algorithms.

V. Conclusions and Discussions

In this paper we formulated three classes of optimization problems: the simple, monotonically-constrained and bounded CH-programs. We revealed the dominance property (Theorem

1) under the local refinement (LR) operation for the simple and monotonically-constrained CH-programs, as well as the general dominance property (Theorem 2) under the pseudo-LR (PLR) operation for the monotonically-constrained CH-program and under the extended-LR (ELR) operation for the bounded CHprogram. These properties enable a very efficient polynomialtime algorithm, using the LR, PLR, or ELR operation for computing lower and upper bounds of the exact solution to any CHprogram. In addition, we introduced the bundled-LR (BLR) operation in [5]. It may be used to speed up the LR, PLR and ELR operations. We also called the bound-computation algorithm as the LR-based algorithm, where LR, in general, refers to the LR, PLR, ELR or BLR operation.

We showed that the algorithm is very effective and efficient for many layout optimization problems in deep submicron (DSM) designs. It unifies solutions to several problems, including the single-source and multi-source wire sizing problems [4], [5], continuous wire sizing problem [19], and simultaneous driver/buffer and wire sizing problem [3], [11].^{16} Because these problems assume the simple models for the device delay and interconnect capacitance, they are all simple CH-program where the LR operation can be used for bound computations. Furthermore, we applied the bound-computation algorithm to the simultaneous transistor and interconnect sizing (STIS) problem, and to the global interconnect sizing and spacing (GISS) problem with consideration of the coupling capacitance for multiple nets. We used tables pre-computed from SPICE simulations and numerical capacitance extractions to model device delay and interconnect capacitance, so that our device and interconnect models are much more accurate than many used in previous works. We first showed that the STIS and GISS problems are, in general, bounded CH-programs, and that the GISS problem is a monotonically-constrained CH-program when the capacitance model is monotonically-constrained. We then developed the STIS algorithm based on bound-computation using the ELR operation, and the GISS algorithm based on bound-computation using the ELR and PLR operations. According to Theorem 2, our bound-computation guarantees that there exist exact solutions to the two problems between resulting lower and upper bounds. Experiments also showed that our algorithms obtained solutions close to the global optimum in the most cases. Moreover, the algorithms are extremely efficient. It took less than 10 seconds to optimize the largest example in this paper.

16A recent work [28] extended the algorithm in [3] to consider simultaneous buffer and wire sizing, where alternate buffer and wire sizing procedures are used, with buffer sizes computed by closed-form formulas, and wire sizes computed by the BLR operation.

Solutions to the STIS and GISS problems, as well as other device and wire sizing problems [4], [5], [3], [28], have been integrated in the TRIO package [29]. Routines using the LR, PLR, ELR and BLR operations are shared. Note that our boundcomputation algorithm is applicable to any bounded model for the device delay and interconnect capacitance. The bounded model simply requires that values for the device delay and interconnect capacitance be bounded. Furthermore, the bounded model can use either table-lookup or high-order complex characteristic functions.

In this paper, we assumed that the lumped capacitance is the load capacitance. In the future, we will extend our algorithm to use the effective capacitance (C_{eff}) [14] as the load capacitance for our device model. Because the ELR operation requires only the lower and upper bounds for the load capacitance, we plan to develop methods computing the lower and upper bounds for C_{eff}, which may be more efficient than computing C_{eff} directly. The Elmore delay model is used in this paper. Several recent works [30], [31], [9] have applied the higher-order delay model. We also plan to extend the LR-based algorithm to consider the higher-order delay model.

Note that the coupling capacitance affects not only the interconnect delay, but also the signal integrity. Furthermore, the inductive effect becomes increasingly significant for global interconnects in DSM designs. We plan to develop suitable delay and noise models considering both capacitive and inductive effects, then apply the LR-based algorithm and/or other techniques. The extended algorithm, with consideration of the inductive effect and higher-order delay model, will also be applicable to the device and interconnect sizing problem in PCB and MCM layout designs. Moreover, we believe that our CH-program formulations and the LR-based algorithm can be applied to other optimization problems in the CAD field.

Acknowledgments

The authors would like to thank Dr. J. P. Fishburn at Bell Laboratories, Prof. S. S. Sapatnekar at University of Minnesota, Minneapolis, and the anonymous reviewers for their helpful comments.

References

[1] J. Cong, L. He, K. Khoo, C. Koh, and Z. Pan, “Interconnect design for deep submicron ICs,” in Proc. Int. Conf. on Computer Aided Design, pp. 478–485, 1997.

[2] J. Cong, L. He, C.-K. Koh, and P. H. Madden, “Performance optimization of VLSI interconnect layout,” Integration, the VLSI Journal, vol. 21, pp. 1–94, 1996.

[3] J. Cong and C.-K. Koh, “Simultaneous driver and wire sizing for performance and power optimization,” in Proc. Int. Conf. on Computer Aided Design, pp. 206–212, Nov. 1994.

[4] J. Cong and K. S. Leung, “Optimal wiresizing under the distributed Elmore delay model,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, pp. 321–336, Mar. 1995.

[5] J. Cong and L. He, “Optimal wiresizing for interconnects with multiple sources,” ACM Trans. on Design Automation of Electronics Systems, vol. 1, pp. 478–511, Oct. 1996.

[6] J. Cong and L. He, “Simultaneous transistor and interconnect sizing based on the general dominance property,” in Proc. ACM SIGDA Workshop on Physical Design, pp. 34–39, April 1996.

[7] J. Cong and L. He, “An efficient approach to simultaneous transistor and interconnect sizing,” in Proc. Int. Conf. on Computer-Aided Design, pp. 181–186, Nov. 1996.

[8] C. Chu and D. F. Wong, “A new approach to simultaneous buffer insertion and wire sizing,” in Proc. Int. Conf. on Computer Aided Design, pp. 614–621, 1997.

[9] N. Menezes, R. Baldick, and L. T. Pileggi, “A sequential quadratic programming approach to concurrent gate and wire sizing,” in Proc. Int. Conf. on Computer Aided Design, pp. 144–151, 1995.

[10] J. Lillis, C. K. Cheng, and T. T. Y. Lin, “Optimal wire sizing and buffer insertion for low power and a generalized delay model,” in Proc. Int. Conf. on Computer Aided Design, pp. 138–143, Nov.

[11] C. P. Chen, Y. W. Chang, and D. F. Wong, “Fast performancedriven optimization for buffered clock trees based on Lagrangian relaxation,” in Proc. Design Automation Conf, pp. 405–408, 1996.

[12] Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1994.

[13] K. Nabors and J. White, “Fastcap: A multipole accelerated 3-d capacitance extraction program,” in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1447–1459, Nov. 1991.

[14] J. Qian, S. Pullela, and L. T. Pileggi, “Modeling the “effective capacitance” for the RC interconnect of CMOS gates,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, pp. 1526–1535, Dec. 1994.

[15] L. Vandenberghe, S. Boyd, and A. E. Gamal, “Optimal wire and transistor sizing for circuits with non-tree topology,” in Proc. Int. Conf. on Computer Aided Design, pp. 252–259, 1997.

[16] J. Cong, L. He, C. Koh, and Z. Pan, “Global interconnect sizing and spacing with consideration of coupling capacitance,” in Proc. Int. Conf. on Computer Aided Design, pp. 628–633, 1997.

[17] J. Cong and L. He, “Theory and algorithm of local refinement based optimization with application to transistor and interconnect sizing,” Tech. Rep. 970034 (available at http://cadlab.cs.ucla.edu/ ˜ helei/publications.html), UCLA CS Dept, Sept. 1997.

[18] J. Cong and L. He, “An efficient technique for device and interconnect optimization in deep submicron designs,” in Proc. Int. Symp. on Physical Design, pp. 45–51, April 1998.

[19] C. P. Chen and D. F. Wong, “A fast algorithm for optimal wire-sizing under elmore delay model,” in Proc. IEEE Int. Symp. on Circuits and Systems, pp. 412–415, 1996.

[20] J. G. Ecker, “Geometric programming: Methods, computations and applications,” SIAM Review, vol. 22, pp. 338–362, July 1980.

[21] J. P. Fishburn and A. E. Dunlop, “TILOS: A posynomial programming approach to transistor sizing,” in Proc. Int. Conf. on Computer Aided Design, pp. 326–328, 1985.

[22] S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, “An exact solution to the transistor sizing problem for CMOS circuits using convex optimization,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, pp. 1621–1634, Nov. 1993.

[23] S. S. Sapatnekar, “Wire sizing as a convex optimization problem: exploring the area-delay tradeoff,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, pp. 1001–1011, Aug. 1996.

[24] D. Luenberger, Linear and Non-linear Programming. Addison-Wesley, 1989.

[25] C. Chu and D. F. Wong, “Greedy wire-sizing is linear time,” in Proc. Int. Symp. on Physical Design, pp. 39–44, 1998.

[26] C. Chien, P. Yang, E. Cohen, R. Jain, and H. Samueli, “A 12.7Mchip/s all-digital BPSK direct sequence spread-spectrum IF transceiver in 1.2μm CMOS,” in Proc. IEEE Int. Solid-State Circuits Conf., pp. 30–31, 1994.

[27] J. Cong, L. He, A. B. Kahng, D. Noice, N. Shirali, and S. H.-C. Yen, “Analysis and justification of a simple, practical 2 1/2-d capacitance extraction methodology,” in Proc. Design Automation Conf, pp. 627–632, 1997.

[28] J. Cong, C.-K. Koh, and K.-S. Leung, “Simultaneous buffer and wire sizing for performance and power optimization,” in Proc. Int. Symp. on Low Power Electronics and Design, pp. 271–276, Aug. 1996.

[29] J. Cong, L. He, C. Koh, and Z. Pan, User Manual for TRIO – UCLA Interconnect Optimization Package. UCLA CS Dept, 1998 (available at http://cadlab.cs.ucla.edu/ ˜ helei/publications.html).

[30] T. Xue, E. S. Kuh, and Q. Yu, “A sensitivity-based wiresizing approach to interconnect optimization of lossy transmission line topologies,” in Proc. IEEE Multi-Chip Module Conf., pp. 117–121, 1996.

[31] N. Menezes, S. Pullela, and L. T. Pileggi, “Simultaneous gate and interconnect sizing for circuit-level delay optimization,” in Proc. Design Automation Conf, pp. 690–695, June 1995.