Fast Lagrangian Relaxation Based Multi-Threaded Gate Sizing Using Simple Timing Calibrations

Authors: Ankur Sharma, David Chinnery, Tiago Reimann, Sarvesh Bhardwaj, Chris Chu

Link to paper: https://dl.acm.org/doi/abs/10.1109/TCAD.2019.2915324

---

Define

• $T$ = Target clock period
• $\mathcal{G}$ = Set of gates in the design
• ${\mathcal{X}}_g$ = Discrete set of cells for gate $g$
• $x_g\in {\mathcal{X}}_g$ = Current cell assigned to gate $g$
• $lea{k}_x$ = Leakage power of cell $x$
• $max\_loa{d}_x$ = Maximum load capacity of cell $x$
• $\mathcal{N}$ = Set of nodes in the timing graph
• ${\mathcal{N}}_{in}$ = Set of input pins of gates and output ports
• ${\mathcal{N}}_{out}$ = Set of output pins of gates and input ports
• ${\mathcal{N}}_{end}$ = Set of timing endpoints, i.e., data input pin of a sequential gate or an output port
• $\mathcal{E}=$ Set of timing arcs in the timing graph
• $a_i$ = Arrival time at node $i$
• $g_i$ = Gate or port associated with node $i$
• ${\lambda }_{ij}$ = Lagrangian multiplier for the timing arc $(i,j)$
• $\mathbf{x},\mathbf{a},\lambda$ = Set of variables $x$, $a$ and $\lambda$, e.g., $\mathbf{x}=\{x_g\mid g\in \mathcal{G}\}$
• $d_{ij}(\mathbf{x})=$ Delay of the timing arc from node $i$ to node $j$
• $sle{w}_i(\mathbf{x})$ = Slew at node $i$
• $cef{f}_i(\mathbf{x})$ = Effective capacitance at node $i\in {\mathcal{N}}_{out}$
• $S_{max}$ = Maximum slew defined in the cell library

They use a similar primal problem as Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation with the exception of the objective being to minimize leakage power instead of size:

$$\begin{array}{rlrlr}& \underset{\mathbf{x},\mathbf{a}}{\mathrm{minimize}}& \sum _{g\in \mathcal{G}}lea{k}_{x_g}& & \\ & \text{subject to}& a_k\le T& & \forall k\in {\mathcal{N}}_{end}\\ & & a_i+d_{ij}(\mathbf{x})\le a_j& & \forall (i,j)\in \mathcal{E}\\ & & cef{f}_i(\mathbf{x})\le max\_loa{d}_{x_{g_i}}& & \forall i\in {\mathcal{N}}_{out}\\ & & sle{w}_i(\mathbf{x})\le S_{max}& & \forall i\in {\mathcal{N}}_{in}\\ & & x_g\in {\mathcal{X}}_g& & \forall g\in \mathcal{G}.\end{array}$$

Timing violations is quantified by total negative slack:

$$TNS=\sum _{k\in {\mathcal{N}}_{end}}(a_k-T).$$

Then again like Chen et al., they take the Lagrangian relaxation of the primal:

$${\mathcal{L}}_{\lambda }(\mathbf{x},\mathbf{a})=\sum _{g\in \mathcal{G}}lea{k}_{x_g}+\sum _{(i,j)\in \mathcal{E}}{\lambda }_{ij}(a_i+d_{ij}(\mathbf{x})-a_j)+\sum _{k\in {\mathcal{N}}_{end}}{\lambda }_k(a_k-T).$$

Note that they do not relax the load and slew constraints; they claim these are easy to track. This leaves the first problem:

$$\begin{array}{rlrlr}LRS/\lambda :& \underset{\mathbf{x},\mathbf{a}}{\mathrm{minimize}}& L_{\lambda }(\mathbf{x},\mathbf{a})& & \\ & \text{subject to}& cef{f}_i(\mathbf{x})\le max\_loa{d}_{x_{g_i}}& & \forall i\in {\mathcal{N}}_{out}\\ & & sle{w}_i(\mathbf{x})\le S_{max}& & \forall i\in {\mathcal{N}}_{in}\\ & & x_g\in {\mathcal{X}}_g& & \forall g\in \mathcal{G}.\end{array}$$

By Karush-Kuhn-Tucker optimality we get the following ideal $\lambda$ values:

$$\begin{array}{rlr}\Lambda :\sum _{\{v\mid (i,v)\in \mathcal{E}\}}{\lambda }_{iv}& =\sum _{\{u\mid (u,i)\in \mathcal{E}\}}{\lambda }_{ui}& \forall i\in \mathcal{N}\setminus {\mathcal{N}}_{end}\\ {\lambda }_k& =\sum _{\{u\mid (u,k)\in \mathcal{E}\}}{\lambda }_{uk}& \forall k\in {\mathcal{N}}_{end}.\end{array}$$

These are the same conditions as Chen et al., just with different notation. They refer to them as the flow constraints.

Remark: According to Wang et al., the KKT conditions are sufficient but not necessary.

The use $\Lambda$ to simplify $LRS/\lambda$ into a new problem without the arrival times:

$$\begin{array}{rlrlr}sLRS/\lambda :& \underset{\mathbf{x}}{\mathrm{minimize}}& \sum _{g\in \mathcal{G}}lea{k}_{x_g}+\sum _{(i,j)\in \mathcal{E}}{\lambda }_{ij}{d}_{ij}(\mathbf{x})& & \\ & \text{subject to}& cef{f}_i(\mathbf{x})\le max\_loa{d}_{x_{g_i}}& & \forall i\in {\mathcal{N}}_{out}\\ & & sle{w}_i(\mathbf{x})\le S_{max}& & \forall i\in {\mathcal{N}}_{in}\\ & & x_g\in {\mathcal{X}}_g& & \forall g\in \mathcal{G}\end{array}$$

for $\lambda \in \Lambda$. The sum ${\sum }_{(i,j)\in \mathcal{E}}{\lambda }_{ij}{d}_{ij}(\mathbf{x})$ is referred to as the lambda-delay sum. The objective of $sLRS/\lambda$ is called the LRS cost and it’s optimal value is denoted by $L_{\lambda }^{\ast }$.

Thus, the Langrangian Dual problem is given by

$$\begin{array}{rlr}LDP:& \underset{\lambda }{\mathrm{maximize}}& L_{\lambda }^{\ast }-T\sum _{k\in {\mathcal{N}}_{end}}{\lambda }_k\\ & \text{subject to}& \lambda \in \Lambda .\end{array}$$

Remark: The $T\sum {\lambda }_k$ term is from converting the optimal $L_{\lambda }^{\ast }$ of $sLRS/\lambda$ back into ${\mathcal{L}}_{\lambda }(\mathbf{x},\mathbf{a})$ by setting $\mathbf{a}$ to the smallest possible value that satisfies $\mathcal{P}$, i.e., $a_j=a_i+d_{ij}(\mathbf{x})$ for all $(i,j)\in \mathcal{E}$ and $a_k=0$ for all $k\in {\mathcal{N}}_{end}$. From this assumption, we get

$$\begin{array}{rl}{\mathcal{L}}_{\lambda }(\mathbf{x},\mathbf{a})& =\sum _{g\in \mathcal{G}}lea{k}_{x_g}+\sum _{(i,j)\in \mathcal{E}}{\lambda }_{ij}\times 0+\sum _{k\in {\mathcal{N}}_{end}}{\lambda }_k(0-T)\\ & =\sum _{g\in \mathcal{G}}lea{k}_{x_g}-T\sum _{k\in {\mathcal{N}}_{end}}{\lambda }_k.\end{array}$$

Flow of the Algorithm

They make use of a five stage flow:

1. Initialization
2. Calibration of effective capacity
3. LDP Solver for LR timing (solve $\mathcal{D}$)
4. Calibration
5. Greedy post-pass for greedy timing

The two calibration stages are done by passing the model to an external timer.

Initialization

1. Set each gate to the size with the minimal leakage power
2. Fix the maximum load and maximum slew violations.
   1. Scan design in reverse topological order, increase the size of gates that exceed the gate’s maximum load capacity.
   2. Scan design in forward topological order, increase the drive strength of any cells whose output slew is too high.

Calibration

Pass the current model to an external timer (Synopsys PrimeTime) and update our parameters. In the second stage, only the effective capacitance of each gate is updated. In the fourth stage, all timing parameters (including effective capacitance) are updated.

LDP Solver

The $LDP$ is solved in two-substages:

1. LR timing recovery
2. LR power recovery

Each of these substages follow the same design, which is iterative until the desired parameter converges or a cap of 200 iterations is reached:

1. At step $k$:
   1. Solve $LRS/\lambda$ to find optimal $\mathbf{x}$ and $\mathbf{a}$
   2. Perform static timing analysis
   3. Update Lagrangian multipliers

Algorithm 9 Solve $LRS/\lambda$

Compute local negative slack around each gate

for each gate $g$ in forward topolical order do

$min\_cost:=\infty$

$best\_cell:=$current of $g$

for each valid cell alternative $x_g$ do

$cost:=x_g.leakage() + g.lambda\_delay\_sum(x_g)$

$delta\_tns := g.local\_slack\_check(x_g)$

if $cost < min\_cost$ and $delta\_tns\le0$ then

$min\_cost:=cost$

$best\_cell:=x_g$

end if

end for

Apply $best\_cell$ to $g$ and update timing locally

end for

The algorithm walks through the design greedily setting each gate’s cell to the one with the minimal cost that reduces the $TNS$, where cost is given by the sum of the cell’s leakage and a rough approximation of the delay (scaled by $\lambda$):

$$lambda\_delay\_sum(x_g)\approx \sum _{(i,j)\in local\_arcs(g)}{\lambda }_{ij}{d}_{ij}(\mathbf{x}).$$

Here “local-arc” refers to fanin-arcs, gate-arcs, side-arcs and fanout-arcs in the area surrounding gate $g$ (see Figure below).

Timing Models and Calibration Mechanism

They use a “simple” RC model to estimate the effective capcitance as well as delays and slews for gates and interconnects. They’re RC model is calibrated in stages two and four with Synopsys Primetime.

Given a design, a net or interconnect $n$ is an RC tree $T_n$ composed of taps and wire segments connecting two adjacent taps. Each tap $i$ has a corresponding capacitance $ca{p}_i$ and a subtree $subtree(i)$ rooted at $i$. Wire segments connecting the parent of tap $i$, $parent(i)$, to to tap $i$ has a upstream resistance give by $r_i$. The sum of all the resistances on the path connecting the root of the $T_n$ to tap $i$ is denoted by $r_{oi}$.

For estimating effective capacitance of a net $n$, they use

$$ceff(n)=\sum _{i\in tap(T_n)}\frac{ca{p}_i}{1+{\alpha }_n{r}_{oi}/R_d},$$

where ${\alpha }_n\ge 0$ is a net-specific parameter and $R_d$ is the drive resistance (computed via lookup table) of the arc that drives net $n$. By default ${\alpha }_n=0$, during calibration ${\alpha }_n$ is updated so that $ceff(n)$ matches the result from Synopsys PrimeTime. Before calibration, $ceff(n)$ had an average error of $4.4\%$, but a large standard deviation of $17\%$ and maximum error of $>500\%$.

They estimate slew by

$$sle{w}_i=\sqrt{s_0^2+sc{f}_i\times d_i^2}$$

where

• $s_0$ is the slew at the root of the net
• $d_i$ is the Elmore delay from the root of the RC tree to tap $i$
• $sc{f}_i$ is the slew correction factor which initially is set to $(\ln 4{)}^2\approx 1.92$.

Elmore delay is given by the path from the root to tap $i$:

$$d_i=\sum _{j\in tap(path(i))}{r}_j{c}_j$$

where $r_j$ and $c_j$ are the upstream resistance and downstream capacitance at tap $j$. They modify the Elmore delay by scaling it by a delay correction factor $dc{f}_i$. $dc{f}_i$ is initially set to 1 and updated during calibration so that $dc{f}_i\times d_i$ matches the result from PrimeTime.

Gate slew and gate delay are given by a lookup table then scaled by a slew correction factor and delay correction factor, respectively.

The calibration algorithm essentially boils down to three steps:

1. Generate a verilog file for the design
2. Run Synopsys PrimeTime
3. Update various parameters so that our estimations match PrimeTime’s output

This is clearly the slowest part of their algorithm. On average, the calibration steps take $46\%$ of the runtime with a high of $94\%$ of the runtime.

Multi-Threaded LRS Solver

They speedup solving $LRS/\lambda$ by using parallel computing. The idea is, that multiple gates can be sized simultaneously, but not any two gates can be resized at the same time.

In order for two or more gates to be resized simultaneously, they must satisfy two properties:

1. None of them have a fan-in arc in common; and
2. None of them lie in each other’s fan-out cone.

They first ensure property 1 is satisfied with an algorithm they call mutual exclusion edges (MEE):

Algorithm 10 MEE assignment

// Stage 1: Assign random IDs

$max\_id:=0$

for each level $l=0$ to maximum topological level do

$x:=max\_id$

for each gate $g$ in level $l$ do

$g.id:=x$

while $g.id$ is not unique do

$g.id := x + rand()$

end while

if $g.id > max\_id$ then

$max\_id:=g.id$

end if

end for

end for

// Stage 2: MEE assignment

for each gate $g$ in the design do

$s:=$ fan-outs of $g$ sorted by ascending IDs

for each $i=0$ to $s.size()-2$ do

Assign MEE from $s[i]$ to $s[i+1]$

end for

end for

The MEE edges are essentially “dummy edges” to form a chain of fan-outs for every gate. For $(s[i],s[i+1])$, they refer to $s[i]$ as the pseudo fan-in of $s[i+1]$ and $s[i+1]$ as the pseudo fan-out of $s[i]$. An example is given in the Figure below; the dashed lines show the fanouts of $A$ ($\{D,E,F\}$) and $C$ ($\{F,G\}$) are connected by MEE edges. In this case, $E$ and $F$ cannot be resized simultaneously as they share a fan-in from $A$. Likewise, $F$ and $G$ share a fan-in from $C$. Finally $E$ and $D$ share a fan-in from $A$. The MEEs enforce a sequential order for resizing fan-outs.

They ensure property 2 is satisfied with a DAG based netlist traversal:

• For each gate, let $pre\_count$ be the number of fan-ins and pseudo fan-ins of that gate that are yet to be resized.
  • Initialize variable to total number of fan-ins and pseudo fan-ins.
• After a gate is resized, the $pre\_count$ variable for all its fan-outs and pseudo fan-outs is decremented by 1.
• Any gate whose $pre\_count=0$ is ready to be resized.