Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation

Authors: Chung-Ping Chen, C.C.N. Chu, D.F. Wong

Link to full paper: https://ieeexplore.ieee.org/document/743080

---

Preliminaries

Define

• $R_i^D$ to be the driver resistance for the $i$th input driver, $1\le i\le s$.
• $C_i^L$ to be the load capacitance of the $i$th output load, $1\le i\le t$.

A gate, wire segment or an input driver is referred to as a component. We add two factitious components to our circuit:

1. An output component which consists of all $t$ output loads.
2. An input component which consists of all $s$ input drivers. We refer to the connection point two components as a node. We also treat the output point of our output component as a node. There are $n+s+2$ components and $n+s+2$ nodes, where $n$ is the number of gates or wire segments.

Label the nodes $0,\dots ,m$, where $m=n+s+1$, in reverse topological order. That is, index 0 is the output point of the output component and index $i$ for $1\le i\le t$ is the node connecting to the $i$th output load. For $t+1\le i\le n$, the node with index $i$ is the connection among the gates and wire segments. By this ordering, if node $i$ is connected to the input and node $j$ is connected to the output, then $i>j$. We also index the components $i$ if the output is connected to node $i$.

Define

• $input(i)$ to be the set of indexes of components directly connected to the input(s) of component $i$.
• $output(i)$ to be the set of indexes of components directly connected to the output of component $i$.
• $\mathcal{G}$ to be the set of indexes of gates
• $\mathcal{W}$ to be the set of indexes of wire segments
• $\mathcal{D}$ to be the set of indexes of input drivers
• For $i\in \mathcal{G}$, let $x_i$ be the gate size, $r_i$ the output resistance, and $c_i$ the input capacitance of the pin (we assume all pins share the same input capacitance).
• For $i\in \mathcal{G}$, let ${\hat{r}}_i$ and ${\hat{c}}_i$ be the unit size output resistance and input capacitance per unit size of gate $i$, i.e., $r_i=\widehat{r_i}/x_i$ and $c_i=\widehat{c_i}{x}_i$.
• For $i\in \mathcal{W}$, $x_i$ is the segment width.
• For $i\in \mathcal{W}$, let $\widehat{r_i}$, $\widehat{c_i}$ and $f_i$ be the unit width wire resistance, the wire area capacitance per unit width and the wire fringing capacitance of segment $i$. Then for wire $i\in \mathcal{W}$, $r_i=\widehat{r_i}/x_i$ and $c_i=\widehat{c_i}{x}_i+f_i$.
• For $i\in \mathcal{G}\cup \mathcal{W}$, define $L_i$ and $U_i$ such that $L_i\le x_i\le U_i$.

Components are modeled as RC circuits. This allows the use of Elmore delay model for delay calculation. Elmore delay along a signal path is calculated as the sum of the delays associated with the resistors in the path. Each component $i$ (exluding the two facitious components) is assumed to contain a resistor $i$. For input driver $i\in \mathcal{D}$, we define $r_i=R_{i-n}^D$, i.e., the driver resistance of the $(i-n)$th input driver (the $i-n$ is to get it in the right index. Recall $R_i^D$ is in $1\le i\le s$. Each $i\in \mathcal{D}$ is offset by $n$ indices due to the labeling. Basically we are setting the resistance to that input drivers resistance.)

Let $C_i$ be the downstream capacitance of resistor $i\in \mathcal{G}\cup \mathcal{W}\cup \mathcal{D}$. In short, the downstream capacitance of a resistor $i$ is given by the total capacitance of everything “downstream” resistor $i$. For instance, in the figure below the downstream of capacitance of $R1$ is $C1+C2$ as capacitors $C1$ and $C2$ are downstream of $R1$. But the downstream capacitance of $R2$ is just $C2$.

The Elmore delay associated with resistor $i$ is calculated by $D_i=r_i{C}_i$. Thus, if a signal path passes through resistors $i_1,\dots ,i_k$, then the Elmore delay along $p=\{i_1,\dots ,i_k\}$ is given by

$$\sum _{i\in p}{D}_i=\sum _{i\in p}{r}_i{C}_i.$$

We denote the set of all possible paths from node $m$ to node 0 by $\mathcal{P}$, i.e., any $p\in \mathcal{P}$ is a path from an input driver to an output load.

Minimizing Total Area Subject to Maximum Delay Bound

Define $A_0$ to be the maximum delay form any input driver to any output load, i.e., $A_0$ is a bound on the arrival time at node $0$. We wish to minimize the total component area, which can be computed by ${\sum }_{i=1}^n{\alpha }_i{x}_i$ where ${\alpha }_1,\dots ,{\alpha }_n$ are some constants. Thus, the problem is

$$\begin{array}{rlrlr}& \text{minimize}& \sum _{i=1}^n{\alpha }_i{x}_i& & \\ & \text{subject to}& \sum _{i\in p}{D}_i\le A_0& & \forall p\in \mathcal{P}\\ & & L_i\le x_i\le U_i& & \forall i\in \mathcal{G}\cup \mathcal{W}.\end{array}$$

However, there are exponentially many paths. So they partition the path delay constraints into constraints on component delay to form the primal problem:

$$\begin{array}{rlrlrlr}\mathcal{PP}:& & \text{minimize}& & \sum _{i=1}^n{\alpha }_i{x}_i& & \\ & & \text{subject to}& & a_j\le A_0& & \forall j\in input(0)\\ & & & & a_j+D_i\le a_i& & \forall i\in \mathcal{G}\cup \mathcal{W},\forall j\in input(i)\\ & & & & D_i\le a_i& & \forall i\in \mathcal{D}\\ & & & & L_i\le x_i\le U_i& & \forall i\in \mathcal{G}\cup \mathcal{W}.\end{array}$$

The constraints for $\mathcal{PP}$ are as follows:

1. Every input $j\in input(0)$ of our factious output component arrives no later than $A_0$
2. The arrival time of component $i\in \mathcal{G}\cup \mathcal{W}$ cannot be earlier than its inputs $j\in input(i)$ with delay from component $i$: $a_j+D_i$.
3. The arrival time of our input drivers is no less than the input driver’s delay
4. Size constraints for components.

They relax constraints 1-3 to get the Lagrangian relaxation

$$\begin{array}{rlrlrlr}\mathcal{L}\mathcal{R}\mathcal{S}/\lambda :& & \text{minimize}& & L_{\lambda }(x,a)& & \\ & & \text{subject to}& & L_i\le x_i\le U_i& & \forall i\in \mathcal{G}\cup \mathcal{W}\end{array}$$

where

$$\begin{array}{rl}{L}_{\lambda }(x,a)& =\sum _{i=1}^n{\alpha }_i{x}_i+\sum _{j\in input(0)}{\lambda }_{j0}(a_j-A_0)+\sum _{i\in \mathcal{G}\cup \mathcal{W}}\sum _{j\in input(i)}{\lambda }_{ji}(a_j+D_i-a_i)+\sum _{i\in \mathcal{D}}{\lambda }_{mi}(D_i-a_i).\end{array}$$

Notice that the Lagrangian has two variables: component sizes $x$ and arrival times $a$.

They use Kuhn-Tucker conditions to show that in order for the optimal solution, $(x^{\ast },a^{\ast })$, for $\mathcal{L}\mathcal{R}\mathcal{S}/\lambda$ to also be the optimal solution for $\mathcal{PP}$ one needs $\partial L_{\lambda }/\partial a_i(x^{\ast },a^{\ast })=0$ for all $1\le i\le n+s$ (to ensure $(x^{\ast },a^{\ast })$ is a saddle point). That is, $\lambda \in {\Omega }_{\lambda }$ where

$${\Omega }_{\lambda }=\left\{\lambda \ge 0:\sum _{k\in output(i)}{\lambda }_{ik}=\sum _{j\in input(i)}{\lambda }_{ji},\forall 1\le i\le n+s\right\}.$$

This results in a simpler problem which eliminates variables $a_i$:

$$\begin{array}{rlrlrlr}\mathcal{L}\mathcal{R}\mathcal{S}/\mu :& & \text{minimize}& & L_{\mu }(x)& & \\ & & \text{subject to}& & L_i\le x_i\le U_i& & \forall i\in \mathcal{G}\cup \mathcal{W}\end{array}$$

where

$${\mu }_i=\sum _{j\in input(i)}{\lambda }_{ji}\text{ for }0\le i\le n+s$$

and

$$L_{\mu }(x)=\sum _{i=1}^n\alpha x_i+\sum _{i=1}^n{\mu }_i{D}_i.$$

Lemma 1

For any $\lambda \in {\Omega }_{\lambda }$, the optimal $x$ for $\mathcal{L}\mathcal{R}\mathcal{S}/\lambda$ is the same as the optimal $x$ for $\mathcal{L}\mathcal{R}\mathcal{S}/\mu$.

This leaves the following solving strategy:

1. Solve $\mathcal{L}\mathcal{R}\mathcal{S}/\mu$ to find the optimal $x$
2. Find the optimal $a$ by setting $a_i$ to be the smallest possible value that satisfies the constraints of $\mathcal{PP}$.

Solving $\mathcal{L}\mathcal{R}\mathcal{S}/\mu$

Define

• $upstream(i)$ to be the set of resistor indexes (excluding $i$) on the path(s) from component $i$ to the nearest upstream gate(s) or input driver(s). For instance, in Figure 2 above: $upstream(1)=\{3,6\}$.
• $R_i={\sum }_{j\in upstream(i)}{\mu }_j{r}_j$, i.e., the weighted upstream resistance of component $i$.
• Modified downstream capacitance:

$$C_i^{\prime }=\{\begin{array}{ll}{C}_i-\widehat{c_i}{x}_i/2& \text{if }i\in \mathcal{W}\\ C_i& \text{if }i\in \mathcal{G}\cup \mathcal{D}.\end{array}$$

The phrase local re-sizing of component $i$ refers to changing $x_i$ while keeping the sizes of all other components fixed. The optimal local resizing of component $i$ minimizes $L_{\mu }(x)$.

Lemma 2

Let $x=(x_1,\dots ,x_n)$ be a component-sizing solution. An optimal local re-sizing of component $i$ is given by changing the size of component $i$ to $x_i^{\ast }=\min \left(U_i,\max \left(L_i,\sqrt{B_i(x)/A_i(x)}\right)\right)$ where $A_i(x)={\hat{c}}_i{R}_i+{\alpha }_i$ and $B_i(x)={\mu }_i{\hat{r}}_i{C}_i^{\prime }$.

No proof for Lemma 2 is provided. Expression is found by minimizing $L_{\mu }(x)$ while only changing component $i$.

Their algorithm $\text{SOLVE\_LRS}/\mu$ is a greedy algorithm that iteratively re-sizes each component. In each iteration, each component is examined in order and re-sized optimally using Lemma 2 while keeping the other components fixed. The algorithm then recomputes $C_i^{\prime }$ and $R_i$ incrementally by traversing the circuit in reverse topological order followed by topological order.

Algorithm 9 $\textup{SOLVE\_LRS}/\mu$

for $i=1\dots n$ do

$x_i := L_i$

end for

// Compute $C_i'$ for $1\le i\le n$ by traversing the circuit in reverse topological order

for $i=1\dots t$ do

$C_i' := \begin{cases} C_i^L & \text{if }i\in\mathcal{G} \\ C_i^L + f_i/2 & \text{if }i\in\mathcal{W} \end{cases}$

end for

for $i=t+1\dots n$ do

$C_i' := \begin{cases} 0 & \text{if }i\in\mathcal{G} \\ f_i/2 & \text{if }i\in\mathcal{W} \end{cases}$

for all $k$ s.t. $i\in input(k)$ do

$C_i' := \begin{cases} C_i' + \hat{c_k}x_k & \text{if }k\in\mathcal{G} \\ C_i' + \hat{c_k}x_k + f_k/2 + C_k' & \text{if }k\in\mathcal{W} \end{cases}$

end for

end for

// Compute $R_i$ and $x_i$ for $1\le i\le n$ by traversing the circuit in a topological order

for $i=n\dots 1$ do

$R_i:=0$

for all $j\in input(i)$ do

$R_i := \begin{cases} R_i + \mu_j\hat{r_j}/x_j & \text{if }j\in\mathcal{G} \\ R_i + \mu_j\hat{r_j}/x_j + R_j & \text{if }j\in\mathcal{W} \\ R_i + \mu_jR_{j-n}^D & \text{if }j\in\mathcal{D} \end{cases}$

end for

$x_i:=\min\left(U_i,\max\left(L_i,\sqrt{\mu_i\hat{r_i}C_i'/(\hat{c_i}R_i+\alpha_i)}\right)\right)$

end for

If there was an improvement, goto line 5

The main aspect of the algorithm is on line 20 when we apply Lemma 2 to component $i$. Lines 5-13 are simply walking along the circuit from right-to-left and keeping track of the downstream capacitance. Lines 16-19 are simply summing up the resistance from each input to the component. The component sizes and resistances are computed left-to-right.

The algorithm runs in $O(rn)$ time using $O(n)$ memory, where $n$ is the number of sizable components and $r$ is the number of iterations.

Theorem 1

For any fixed vector $\mu \ge 0$, algorithm $\text{SOLVE\_LRS}/\mu$ always converges to the optimal component-sizing solution of the problem $\mathcal{L}\mathcal{R}\mathcal{S}/\mu$

Again they claim this with no proof.

Solving the Lagrangian Dual

Define

$$Q(\lambda )=\text{optimal value of the problem LRS/λ}.$$

They consider the Lagrangian dual problem:

$$\begin{array}{rlrlr}\mathcal{L}\mathcal{DP}:& & \text{maximize}& & Q(\lambda )\\ & & \text{subject to}& & \lambda \in {\Omega }_{\lambda }.\end{array}$$

They use subgradient optimization method to solve $\mathcal{L}\mathcal{DP}$. See Lagrangian Relaxation for more details. In summary, the algorithm works as follows:

1. Iteration 0: Start from an arbitrary $\lambda$
2. Step $k$:
   1. Solve $\mathcal{L}\mathcal{R}\mathcal{S}/\lambda$ (by solving $\mathcal{L}\mathcal{R}\mathcal{S}/\mu$).
   2. For each relaxed constraint $i$, compute the subgradient $g_i(x,a)={\text{LHS}}_i-{\text{RHS}}_i$. For instance, for constraint $a_j\le A_0$ the subgradient is $a_j-A_0$ where $a_j$ is the value given by our current solution $(x,a)$.
   3. Set ${\lambda }_{k+1}={\lambda }_k+{\rho }_{k}g$, where $g={\left[\begin{array}{ccc}{g}_1& g_2& \cdots \end{array}\right]}^{\top }$ and ${\rho }_k$ is some step size.
   4. Project ${\lambda }_{k+1}$ to the nearest point in ${\Omega }_{\lambda }$.

They don’t specify the step size, the simplest would be ${\rho }_k=1/(k+1)$. The only real requirement for convergence is that ${\lim }_{k\to \infty }{\rho }_k=0$ and ${\sum }_{k=1}^{\infty }{\rho }_k=\infty$.

Algorithm 10 $\textup{SOLVE\_LDP}$

$k:=1$, $\lambda:=\text{arbitrary entry in }\Omega_\lambda$

while $(\sum_{i=1}^n\alpha_ix_i - Q(\lambda)) \le \epsilon$ do

$\mu:=(\mu_0,\dots,\mu_{n+s})$ where $\mu_i=\sum_{j\in input(i)}\lambda_{ji}$

Solve $\mathcal{L}\mathcal{R}\mathcal{S}/\lambda$ via $\textup{SOLVE\_LRS}/\mu$ and then calculating $a_1,\dots,a_{n+s}$

for $i=0,\dots,n+s$ do

for all $j\in input(i)$ do

$\lambda_{ji} := \begin{cases} \lambda_{ji} + \rho_k(a_j-A_0) & \text{if } i=0 \\ \lambda_{ji} + \rho_k(a_j+D_i-a_i) & \text{if }i\in\mathcal{G}\cup\mathcal{W} \\ \lambda_{ji} + \rho_k(D_i - a_i) & \text{if }i\in\mathcal{D} \end{cases}$

end for

end for

Project $\lambda$ onto nearest point in $\Omega_\lambda$

$k:=k+1$

end while