⌚ Clock Skew Scheduling Under Process Variations

---

# Yield-driven Clock Skew Scheduling Under Process Variations ⌚

@luk036 👨‍💻 · 2026 📅

---

## Abstract 📝

The main topic of the lecture is clock skew scheduling under process variations. The lecture discusses various techniques and methods for optimizing clock skew to improve circuit performance or minimize timing failures. 🔧

The lecture begins with an overview of the problem and background of clock skew scheduling. It then explains the concept of clock skew and the difference between zero skew and useful skew designs. The importance of meeting timing constraints, such as setup time and hold time, is discussed, along with the potential problems that can occur if these constraints are violated. 🔄

The lecture presents various approaches to clock skew scheduling, such as traditional scheduling, yield-driven scheduling, and minimum cost-to-time ratio cycle formulation. It also examines various methods for finding the optimal clock period and the corresponding skew schedule, including linear programming and the use of the Bellman-Ford algorithm.

---

### Abstract (II) 📝

The lecture goes on to discuss primitive solutions and their shortcomings, such as pre-allocating timing margins and using the Least Center Error Square (LCES) problem formulation. The lecture also introduces more advanced techniques such as slack maximization (EVEN) and prop-based methods that distribute slack along the most timing-critical cycle based on Gaussian models. The drawbacks of these methods are highlighted, particularly their assumptions about gate delay distributions. ⚡

Finally, statistical static timing analysis (SSTA) and the use of statistical methods to account for process variations are discussed. The concept of the most critical cycle is introduced, and the lecture provides experimental results to demonstrate the effectiveness of various clock skew scheduling techniques. 📈

---

### Overview 🗺️

-   Background 📚
-   Problem formulation ❓
-   Traditional clock skew scheduling ⏳
-   Yield-driven clock skew scheduling 🎯
-   Minimum cost-to-time ratio cycle formulation 🔄

]
.pull-right[

![image](figs/dfm.svg)

]

---

### Sequential Logic

-   Local data path 🔗

![image](lec05.files/fig01.svg)

---

### Sequential Logic (cont'd)

-   Graph

![image](lec05.files/fig02.svg)

---

### Clock Skew

-   $T_\text{skew}(i,f) = {\color{firebrick}t_i} - {\color{firebrick}t_f}$, where ⏱️
  -   ${\color{firebrick}t_i}$: clock signal delay at the initial register
  -   ${\color{firebrick}t_f}$: clock signal delay at the final register
-   We are not interested in the absolute time. Why? 🤔

]
.pull-right[

![image](lec05.files/fig04.svg)

]

---

### Timing Constraint

-   Setup time constraint ⏱️
    $$T_\text{skew}(i,f) \le T_\text{CP} - D_{if} - T_\text{setup} = {\color{blue}u}_{if}$$
    While this constraint destroyed, cycle time violation (zero
    clocking) occurs.

-   Hold time constraint ⏳
    $$T_\text{skew}(i,f) \ge T_\text{hold} - d_{if} = {\color{blue}l}_{if}$$ While
    this constraint destroyed, race condition (double clocking) occurs.

---

### Zero Skew vs. Useful Skew

-   Zero skew (${\color{firebrick}t_i} = {\color{firebrick}t_f}$) : Relatively easy to implement. ⚖️

-   Useful skew. Improve: 🎯
  -   The performance of the circuit by permitting a higher maximum
        clock frequency, or
  -   The safety margins of the clock skew within the permissible
        ranges.

-   Max./min. path delays are got from static timing analysis
    (STA).

---

### Timing Constraint Graph (TCG)

-   Create a graph by 📈
  -   replacing the hold time constraint with a *h-edge* with cost
        $-(T_\text{hold} - d_{ij})$ from $\text{FF}_i$ to $\text{FF}_j$,
        and
  -   replacing the setup time constraint with an s-edge with cost
        $T_\text{CP} - D_{ij} - T_\text{setup}$ from $\text{FF}_j$ to
        $\text{FF}_i$.
-   Two sets of constraints stemming from clock skew definition: 🔗
  -   The sum of skews for paths having the same starting and ending
        flip-flop to be the same;
  -   The sum of clock skews of all cycles to be zero

]
.pull-right[

.mermaid[
<pre>
graph LR
    A(("v1")) -- "D12 = 2" --> B(("v2"))
    A -. "d12 = 2" .-> B
    B -- "D23 = 3" --> C(("v3"))
    B -. "d23 = 3" .-> C
    C -. "d31 = 1.5" .-> A
    C -- "D31 = 4.0" --> A

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

]

---

### Timing Constraint Graph (TCG)

Assume $T_\text{setup} = T_\text{hold}$ = 0 ⏱️

Clock period $T_\text{CP}$ is feasible if and only if current graph contains no
negative cost cycles.

]
.pull-right[

.mermaid[
<pre>
graph LR
    A(("v1")) -- "Tcp - 2" --> B(("v2"))
    A -. "2" .-> B
    B -- "Tcp - 3" --> C(("v3"))
    B -. "3" .-> C
    C -. "1.5" .-> A
    C -- "Tcp - 4" --> A

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

]

---

### Minimize Clock Period

-   Linear programming (LP) formulation
  $$\begin{array}{ll}
      \text{minimize} & {\color{coral}T_\text{CP} } \\
      \text{subject to} & {\color{blue}l}_{ij} \leq {\color{firebrick}t_i} - {\color{firebrick}t_j} \leq {\color{blue}u}_{ij}
  \end{array}$$
  where $\text{FF}_i$ and $\text{FF}_j$ are sequential adjacent

-   The above constraint condition is so-called **system of difference
  constraints** (see Introduction to Algorithms, MIT): 🔍

-   👉 Note: easy to check if a feasible solution exists by detecting
  negative cycle using for example Bellman-Ford algorithm.

---

### Basic Bellman-Ford Algorithm

```matlab
function BellmanFord(list vertices, list edges, vertex source)
    // Step 1: initialize graph
    for each vertex i in vertices:
        if i is source then u[i] := 0
        else u[i] := inf
        predecessor[i] := null

// Step 2: relax edges repeatedly
    for i from 1 to size(vertices)-1:
        for each edge (i, j) with weight d in edges:
            if u[j] > u[i] + d[i,j]:
                u[j] := u[i] + d[i,j]
                predecessor[j] := i

// Step 3: check for negative-weight cycles
    for each edge (i, j) with weight d in edges:
        if u[j] > u[i] + d[i,j]:
            error "Graph contains a negative-weight cycle"
return u[], predecessor[]
```

---

### Problems with Bellman-Ford Algorithm

-   The algorithm is originally used for finding the shortest paths. 🔍
-   Detecting negative cycle is just a side product of the algorithm. ⚠️
-   The algorithm is simple, but... 🔧
  -   detects negative cycle at the end only.
  -   has to compute all `d[i,j]`.
  -   Restart the initialization with `u[i] := inf`.
  -   requests the input graph must have a source node.

Various improvements have been proposed extensively.

---

### DiGraphX Example

```python
from digraphx.neg_cycle import NegCycleFinder

def has_negative_cycle(digraph, TCP, dist):
    finder = NegCycleFinder(digraph)
    for _ in finder.howard(
        dist,
        lambda e: TCP - e["delay"] if e["type"] == "s" else e["delay"]
    ):
        return True
    return False

digraph = {
    "v1": {"v2": {"type": "s", "delay": 2},
           "v3": {"type": "h", "delay": 1.5} },
    "v2": {"v3": {"type": "s", "delay": 3},
           "v1": {"type": "h", "delay": 2.0} },
    "v3": {"v1": {"type": "s", "delay": 4},
           "v2": {"type": "h", "delay": 3.0} },
}
dist = {'v1': 0, 'v2': 0, 'v3': 0}
assert has_negative_cycle(4.0, dist) is False
assert has_negative_cycle(2.0, dist) is True
assert has_negative_cycle(3.0, dist) is False
assert dist == {'v1': -1, 'v2': 0, 'v3': 0}
```

---

### Minimize clock period (I)

-   Fast algorithm for solving the LP: ⚡
  -   Use binary search method for finding the minimum clock period.
  -   In each iteration, Bellman-Ford algorithm is called to detect if
        the timing constraint graph contains negative weighted edge
        cycle.
-   👉 Note: Originally Bellman-Ford algorithm is used to find a
    shortest-path of a graph.

---

### NetOptim Example

```python
from digraphx.neg_cycle import NegCycleFinder
from pytest import approx
from ellalgo.cutting_plane import bsearch
from ellalgo.ell_typing import OracleBS
from ellalgo.ell_config import Options

def has_negative_cycle(digraph, TCP, dist):...

class MyBSOracle(OracleBS):
    def __init__(self, digraph, dist):
        self.digraph = digraph
        self.dist = dist

def assess_bs(self, gamma):
        return not has_negative_cycle(self.digraph, gamma, self.dist)

dist = {'v1': 0, 'v2': 0, 'v3': 0}
digraph = {...
omega = MyBSOracle(digraph, dist)
options = Options()
options.tolerance = 1e-14
TCP, num_iter = bsearch(omega, (2.0, 4.0), options)
assert TCP == approx(3.0)
```

---

### Minimize clock period (II)

-   When the optimal clock period is solved, the corresponding skew
    schedule is got simultaneously. ⏱️

-   However, many skew values are on the bounds of feasible range. ⚠️

![Timing uncertainty emerges under processvariations](lec05.files/fig07.png)

---

### Yield-driven Clock Skew Scheduling

-   When process variations increase more and more,
    timing-failure-induced yield loss becomes a significant problem. 🔄

-   Yield-driven Clock Skew Scheduling becomes important. 🎯

-   Primary goal of this scheduling is to minimize the yield loss
    instead of minimizing the clock period. 🎯

---

### Timing Yield Definition

-   The circuit is called functionally correct if all the setup- and
    hold-time constraints are satisfied under a group of determinate
    process parameters. ✅

-   Timing Yield = (functional correct times) / sample number \* 100% 📈

---

### Primitive solution (1)

-   Pre-allocate timing margins (usually equivalent to maximum timing
    uncertainty) at both ends of the FSR's (Feasible Skew Region). ⚙️
    $${\color{blue}l}_{ij} \leq {\color{blue}s}_{ij} \leq {\color{blue}u}_{ij} \implies {\color{blue}l}_{ij} + \Delta d \leq {\color{blue}s}_{ij} \leq {\color{blue}u}_{ij} - \Delta d$$

-   Then perform clock period optimization.

---

### Problems with this method

-   The maximum timing uncertainty is too pessimistic. Lose some
    performance; ⚠️

-   $\Delta d$ is fixed; it does not consider data path delay
    differences between cycle edges. ⚠️

---

### References (1) 📑

-   "Clock skew optimization", IEEE Trans. Computers, 1990 📚
-   "A graph-theoretic approach to clock skew optimization", ISCAS'94
-   "Cycle time and slack optimization for VLSI-chips", ICCAD'99 ⏳
-   "Clock scheduling and clocktree construction for high performance
    Asics", ICCAD'03 ⚙️
-   "ExtensiveSlackBalance: an Approach to Make Front-end Tools Aware of
    Clock Skew Scheduling", DAC'06 🔄

---

### Primitive solution (2)

-   Formulate as LCES (Least Center Error Square) problem 📐
  -   A simple observation suggests that, to maximize slack, skew
        values should be chosen as close as possible to the middle
        points of their FSR's.

$${\color{blue}l}_{ij} + lm_k ({\color{blue}u}_{ij} - {\color{blue}l}_{ij}) \leq {\color{blue}s}_{ij} \leq {\color{blue}u}_{ij} - um_k ({\color{blue}u}_{ij} - {\color{blue}l}_{ij})$$

$$\begin{array}{ll}
      \text{minimize} & \sum_k (0.5 - \min(lm_k, um_k) )^2 \\
      \text{subject to} & 0 \leq lm_k \leq 0.5 \\
      & 0 \leq um_k \leq 0.5
    \end{array}$$

---

### References (2) 📑

-   Graph-based algorithm
  -   (J. L. Neves and E. G. Friedman, "Optimal Clock Skew Scheduling
        Tolerant to Process Variations", DAC'96)

-   Quadratic Programming method
  -   (I. S. Kourtev and E. G. Fredman, "Clock skew scheduling for improved reliability via quadratic programming", ICCAD'99)

Shortcoming: might reduce some slacks to be zero to minimum **total** CES.
This is not optimal for yield. ⚠️

---

### Primitive solution (3)

-   Incremental Slack Distribution 🔄
  -   (Xinjie Wei, Yici CAI and Xianlong Hong, "Clock skew scheduling under process variations", ISQED'06)

-   Advantage: check all skew constraints ✅

-   Disadvantage: didn't take the path delay difference intoconsideration ⚠️

---

### Minimum Mean Cycle Based

-   **Even**: solve the slack optimization problem using a minimum mean
    cycle formulation. ⚖️
-   **Prop**: distribute slack along the most timing-critical cycle
    proportional to path delays 📏
-   **FP-Prop**: use sensitizable-critical-path search algorithm for
    clock skew scheduling. 🔍

---

### Slack Maximization (EVEN)

-   Slack Maximization Scheduling 📈
  $$\begin{array}{ll}
      \text{maximize} & {\color{coral}\beta} \\
      \text{subject to} & {\color{firebrick}t_j} - {\color{firebrick}t_i} \leq {\color{blue}\mu}_{ij} - {\color{coral}\beta}
  \end{array}$$

-   Equivalent to the so-called minimum mean cycle problem (MMC), where 🔄
  $${\color{coral}\beta^*} = \frac{1}{|{\color{lime}C}|} \sum\limits_{(i,j)\in {\color{lime}C} } {\color{blue}\mu}_{ij}$$

${\color{lime}C}$: critical cycle (first negative cycle)

-   Can be solved efficiently by the above method. ⚡

---

### NetOptim Example

```python
def has_negative_cycle_EVEN(beta, dist, digraph):
    finder = NegCycleFinder(digraph)
    for _ in finder.howard(dist, lambda edge: edge - beta):
        return True
    return False

class MyBSOracle2(OracleBS):
    def __init__(self, dist, digraph):...
    def assess_bs(self, gamma):
        return has_negative_cycle_EVEN(gamma, self.dist, self.digraph)

TCP = 4.5
digraph = {
    "v1": {"v2": TCP - 2, "v3": 1.5},
    "v2": {"v3": TCP - 3, "v1": 2.0},
    "v3": {"v1": TCP - 4, "v2": 3.0},
}
dist = {'v1': 0, 'v2': 0, 'v3': 0}
omega = MyBSOracle2(dist, digraph)
options = Options()
options.tolerance = 1e-14
opt, num_iter = bsearch(omega, [0.0, 10.0], options)
assert opt == approx(1.0)
```

---

### Even - iterative slack optimization

-   Identify the circuit's most timing-critical cycle, 🔍
-   Distribute the slack along the cycle,
-   Freeze the clock skews on the cycle, and 🧊
-   Repeat the process iteratively. 🔄

---

### Identify the timing-critical cycle

.mermaid[
<pre>
graph LR
    A(("v1")) -- "2.5" --> B(("v2"))
    A -. "2" .-> B
    B -- "1.5" --> C(("v3"))
    B -. "3" .-> C
    C -. "1.5" .-> A
    C -- "0.5" --> A

A:::Rose
    C:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

1. Identify the circuit's most timing-critical cycle 🔍
2. Solve the minimum mean-weight cycle problem by ⚙️
   -   Karp's algorithm
   -   A. Dasdan and R.K.Gupta, "Faster Maximum and Minimum Mean Cycle
        Algorithms for System-Performance", TCAD'98.

---

### Distribute the slack

.mermaid[
<pre>
graph LR
    A(("v1")) -- "2.5" --> B(("v2"))
    A -. "2" .-> B
    B -- "1.5" --> C(("v3"))
    B -. "3" .-> C
    C -. "1.5" .-> A
    C -- "0.5" --> A

A:::Rose
    C:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

Distribute the slack evenly along the most timing-critical cycle.

-   $-1.5 \leq {\color{firebrick}t_3} - {\color{firebrick}t_1} \leq 0.5$
-   $\implies {\color{firebrick}t_3} - {\color{firebrick}t_1} = -0.5$ (evenly)
-   $\implies {\color{firebrick}t_1} = 0.5, {\color{firebrick}t_3} = 0$

---

### Freeze the clock skews (I)

.mermaid[
<pre>
graph LR
    A(("0.5")) -- "2.5" --> B(("v2"))
    A -. "2" .-> B
    B -- "1.5" --> C(("0"))
    B -. "3" .-> C
    C -. "1.5" .-> A
    C -- "0.5" --> A

A:::Rose
    C:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

Replace the critical cycle with super vertex. 🧊

---

### Freeze the clock skews (II)

.mermaid[
<pre>
graph LR
    D(("vS")) -- "2" --> B(("v2"))
    D -. "2.5" .-> B
    B -. "3" .-> D
    B -- "1.5" --> D

D:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

To determine the optimal slacks and skews for the rest of the graph, we replace the critical cycle with super vertex.

-   $-2 \leq {\color{firebrick}t_1} - {\color{firebrick}t_2} \leq 2.5$
-   $\implies -2 \leq (0.5 + {\color{firebrick}t_s}) - {\color{firebrick}t_2} \leq 2.5$
-   $\implies -2.5 \leq {\color{firebrick}t_s} - {\color{firebrick}t_2} \leq 2$ (1)
-   On the other hand, $-3 \leq {\color{firebrick}t_2} - {\color{firebrick}t_3} \leq 1.5$
-   $\implies -1.5 \leq {\color{firebrick}t_2} - {\color{firebrick}t_s} \leq 3$ (2)
-   From (1) and (2), we have $-1.5 \leq {\color{firebrick}t_s} - {\color{firebrick}t_2} \leq 2$

---

### Repeat the process (I)

D:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

-   $-2 \leq {\color{firebrick}t_2} - {\color{firebrick}t_s} \leq 1.5$
-   $\implies {\color{firebrick}t_2} - {\color{firebrick}t_s} = -0.25$ (evenly)
-   $\implies {\color{firebrick}t_2} = 0, {\color{firebrick}t_s} = 0.25$

---

### Repeat the process (II)

D:::Rose
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

---

### Final result

-   $\text{Skew}_{12}$ = 0.75 ⏱️
-   $\text{Skew}_{23}$ = -0.25 ⏱️
-   $\text{Skew}_{31}$ = -0.5 ⏱️
-   $\text{Slack}_{12}$ = 1.75 📈
-   $\text{Slack}_{23}$ = 1.75 📈
-   $\text{Slack}_{31}$ = 1 📈

]
.pull-right[

.mermaid[
<pre>
graph LR
    A(("0.75")) -- "2.5" --> B(("0"))
    A -. "2" .-> B
    B -- "1.5" --> C(("0.25"))
    B -. "3" .-> C
    C -. "1.5" .-> A
    C -- "0.5" --> A

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

]

where $\text{Slack}_{ij} = T_\text{CP} - D_{ij} - T_\text{setup} - \text{Skew}_{ij}$

---

### Problems with Even

-   Assume all variances are the same. ⚠️
-   However, the timing uncertainty of a long combinational path is
    usually larger than that of a shorter path. ⚠️
-   Therefore, the even slack distribution along timing-critical cycles
    performed by **Even** is not optimal for yield if data path delays
    along the cycles are different. ⚠️

---

### Prop-Based on Gaussian model (I)

-   Assuming there are $n$ gates with delay $N(\mu,\sigma^2)$ in a path,
    then this path delay is $N(n\mu,n\sigma^2)$
-   Distribute slack along the most timing-critical cycle, according to
    the square root of each edge's path delays (???). 📏
-   To achieve this, update the weights of s-edges and h-edges: ⚙️
    $$\begin{array}{ll}
    T_\text{CP} - (D_{ij} + \alpha \sqrt{D_{ij} } \sigma) - T_\text{setup} \\
    -T_\text{hold} + (d_{ij} - \alpha \sqrt{d_{ij} } \sigma)
    \end{array}$$

where $\alpha$ ensures a minimum timing margin for
    each timing constraint.

---

### Prop-Based on Gaussian model (II)

-   Given a specific clock period $T_\text{CP}$, we gradually increase $\alpha$ and
    use the Bellman-Ford algorithm to detect whether it is still feasible. 🔍
-   After finding the maximum $\alpha$, the edges along the most
    timing-critical cycle will have slacks equal to the pre-allocated
    timing margins. 🎯
-   Many edges in a circuit have sufficiently large slack. Therefore, we
    can perform proportional slack distribution only for the most
    timing-critical cycle. Assign the rest of skews using **Even**. 🔄

---

### Problems with Prop

-   Assume all gate delay has the same distribution. ⚠️
-   Not justify using the square root of path delay for timing margin. ⚠️

---

### FP-Prop (I)

![image](lec05.files/fig18.png)
False path

---

### FP-Prop (II)

-   If we do not consider false path, some non timing-critical cycles
    become timing-critical. Then, more slacks are distributed to these
    cycles, but the slacks in actually timing-critical cycles are not
    sufficient. As a result, the overall timing yield decreases. ⚠️

---

### Problems with FP-Prop

-   Same problems as Prop ⚠️

---

### Experimental Results 🧪

![image](lec05.files/fig20.png)

---

### Statistical Method

-   Setup time constraint

$$T_\text{skew}(i,f) \le T_\text{CP} - \tilde{D}_{if} - T_\text{setup}$$

-   Hold time constraint

$$T_\text{skew}(i,f) \ge T_\text{hold} - \tilde{d}_{if}$$

where $\tilde{D}_{if} \text{ and } \tilde{d}_{if}$
    are random variable under process variations.

---

### Statistical TC Graph

.mermaid[
<pre>
graph LR
    A(("v1")) -- " (2.5, 3.1) " --> B(("v2"))
    A -. " (2, 2.2) " .-> B
    B -- " (1.5, 4.1) " --> C(("v3"))
    B -. " (3, 1.5) " .-> C
    C -. " (1.5, 0.7) " .-> A
    C -- " (0.5, 5.1) " --> A

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

After SSTA, edge weight is represented as a pair of value (mean, variance).

---

### Most Critical Cycle

-   Traditional criteria: minimum mean cycle ⏳

$$\frac{\sum_{(i,j)\in {\color{lime}C} } {\color{blue}\mu}_{ij} }{|{\color{lime}C}|}$$

${\color{lime}C}$: critical cycle (first negative cycle)

-   New criteria: 🆕

$$\frac{\sum_{(i,j)\in {\color{lime}C} } {\color{blue}\mu}_{ij} }{\sum_{(i,j)\in {\color{lime}C} } {\color{blue}\sigma}_{ij} }$$

(We show the correctness later)

---

### Slack Maximization (C-PROP)

-   Slack Maximization Scheduling 📈
  $$\begin{array}{ll}
    \text{maximize} & {\color{coral}\beta} \\
    \text{subject to} & {\color{firebrick}t_j} - {\color{firebrick}t_i}\leq {\color{blue}\mu}_{ij} - {\color{blue}\sigma}_{ij} {\color{coral}\beta}
  \end{array}$$

-   Equivalent to the *minimum cost-to-time ratio cycle* problem (MMC), where:
  -   ${\color{coral}\beta^*} = \frac{\sum_{(i,j)\in {\color{lime}C} } {\color{blue}\mu}_{ij} }{\sum_{(i,j)\in {\color{lime}C} } {\color{blue}\sigma}_{ij} }$
  -   ${\color{lime}C}$: critical cycle (first negative cycle)

---

### NetOptim Example

```python
def has_negative_cycle_PROP(beta, dist, digraph):
    finder = NegCycleFinder(digraph)
    for _ in finder.howard(dist, lambda e: e["c"] - beta * e["t"]):
        return True
    return False

class MyBSOracle3(OracleBS):...

TCP = 4.5
digraph = {
    "v1": {"v2": {"c": TCP-2, "t": 3.1}, "v3": {"c": 1.5, "t": 0.7} },
    "v2": {"v3": {"c": TCP-3, "t": 4.1}, "v1": {"c": 2.0, "t": 2.2} },
    "v3": {"v1": {"c": TCP-4, "t": 5.1}, "v2": {"c": 3.0, "t": 1.5} },
}
dist = {'v1': 0, 'v2': 0, 'v3': 0}
omega = MyBSOracle3(dist, digraph)
options = Options()
options.tolerance = 1e-14
opt, num_iter = bsearch(omega, (0.0, 10.0), options)
print(opt, num_iter)
assert opt == approx(0.3448275862069039)
```

---

### Whole flow

-   After determining the clock arrival time at each vertex in the most
    critical cycle, the cycle is replaced with a super vertex $v'$. 🔄
-   In-edge $(u, v)$ from outside vertex $u$ to cycle member $v$ is
    replaced by an in-edge $(u, v')$ with weight mean
    $\mu(u, v) - T_v$. 🔗
-   Out-edge $(v, u)$ is replaced by out-edge $(v', u)$ with
    weight mean $\mu(v, u) + T_v$. However, the variance of the edge
    weight is not changed. And parallel edges can be remained. 🔗
-   Repeat the process iteratively until the graph is reduced to a
    single super vertex, or the edges number is zero. 🔄

---

### Data structure

.mermaid[
<pre>
graph TD
    A(("v9")) --> B(("v5"))
    A --> C(("v6"))
    A --> D(("v7"))
    A --> E(("v8"))
    D --> F(("v1"))
    D --> G(("v2"))
    E --> H(("v3"))
    E --> I(("v4"))

%% Caption: Timing Constraint Graph (TCG).
</pre>
]

Final $T_1 = T_1 + T_7 +T_9$

---

### Advantages of This Method

-   Fast algorithm exists for minimum cost-to-time ratio cycle problem.
-   Reduce to Even when all variances are equal. 🔄
-   When a variance tends to zero, it makes sense that only minimal
    slack is assigned to this variable, and hence others can be assigned
    more.

---

### Results

![image](lec05.files/fig21.png)\

---

### Main Reference 📑

-   Jeng-Liang Tsai, Dong Hyum Baik, Charlie Chung-Ping Chen, and Kewal
    K. Saluja, "Yield-Driven, False-Path-Aware Clock Skew Scheduling",
    IEEE Design & Test of Computers, May-June 2005 📚

---

### General Formulation

$$\begin{array}{ll}
      \text{maximum} & g(\beta) \\
      \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \leq f_{ij}(\beta), \; \forall (i,j) \in {\color{lime}E}
    \end{array}$$

where $f_{ij}(\beta)$ a linear function that represents various problems defined above.

| Problem | $g(\beta)$ | $f_{ij}(\beta)$ (setup)                                 | $f_{ji}(\beta)$ (hold)                        |
| ------- | ------ | --------------------------------------------------- | ----------------------------------------- |
| Min CP | $-\beta$   | $\beta - D_{ij} - T_\text{s}$                       | $-T_\text{h} + d_{ij}$                 |
| EVEN    | $\beta$    | $T_\text{CP} - D_{ij} - T_\text{s} - \beta$         | $-T_\text{h} + d_{ij} - \beta$             |
| C-PROP  | $\beta$    | $T_\text{CP}-D_{ij}-T_\text{s} - \sigma_{ij} \beta$ | $-T_\text{h} + d_{ij} - \sigma_{ij} \beta$ |

---

### General Formulation (cont'd)

-   In fact, $g(\beta)$ and $f_{ij}(\beta)$ are not necessarily linear functions.
    Any monotonic decreasing function will do. 🔍
-   Theorem: if $g(\beta)$ and $f_{ij}(\beta)$ are *monotonic decreasing*
    functions for all $i$ and $j$, then there is a unique solution to the problem. prove later). 📐
-   Question 1: Does this generalization have any application? ❓
-   Question 2: What if $g(\beta)$ and $f_{ij}(\beta)$ are convex but not monotone? ❓

---

### Non-Gaussian Distribution

-   ~~65nm and below,~~ the path delay is likely to have a non-Gaussian distribution 🔕:

👉 Note: central limit theorem does not apply here. Why?
]

![image](figs/non-gaussian.png)

]

---

### Timing Yield Maximization

-   Formulation:
  -   $\max\{\min\{\text{\color{olive}Pr}\{ {\color{firebrick}t_j} - {\color{firebrick}t_i} \leq \tilde{W}_{ij} \}\}\}$
  -   is not exactly timing yield but reasonable.
  -   does not require correlation information among $\tilde{W}_{ij}$. Why?

-   It is equivalent to: 🔄

$$\begin{array}{ll}
    \text{maximum} & {\color{coral}\beta} \\
    \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - {\color{olive}F}^{-1}_{ji}({\color{coral}\beta}) \\
      & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le {\color{olive}F}^{-1}_{ij}(1 - {\color{coral}\beta})
    \end{array}$$
    where ${\color{olive}F}_{ij}(\cdot) \text{ is CDF of } \tilde{W}_{ij}$

-   Luckily, any CDF must be a monotonic increasing function. ✅

---

### Statistical Interpretations of C-PROP

-   Reduce to C-PROP when $\tilde{W}_{ij}$ is Gaussian, or precisely 🔄

$${\color{olive}F}_{ij}(x) = K((x - {\color{blue}\mu}_{ij})/{\color{blue}\sigma}_{ij})$$

-   EVEN: identical distribution up to shifting ⚖️

$${\color{olive}F}_{ij}(x) = H(x - {\color{blue}\mu}_{ij})$$

Not necessarily worse than C-PROP

---

### Comparison

![image](lec05.files/fig23.png)

---

## Related Algorithms

---

### Three Solving Methods in General

-   Binary search based 🔍
  -   Local convergence is slow.
-   Cycle based 🔄
  -   Idea: if a solution is infeasible, there exists a negative cycle
        which can always be "zero-out" with minimum effort (proof of
        optimality)
-   Path based 🛤️
  -   Idea: if a solution is feasible, there exists a (shortest) path
        from where we can always improve the solution.

---

#### Parametric Shortest Path Algorithms

-   Lawler's algorithm (binary search) ⚙️
-   Howard's algorithm (based on cycle cancellation) 🔄
-   Hybrid method 🔀
-   Improved Howard's algorithm ⚡
-   Input: 📥
  -   Interval [βmin, βmax] that includes β\*
  -   Tol: tolerance
  -   G({\color{salmon}V}, {\color{lime}E}): timing graph
-   Output: 📤
  -   Optimal β* and its corresponding critical cycle C

---

#### Lawler's Algorithm

![image](lec05.files/lawler.svg)

---

#### Howard's Algorithm

![image](lec05.files/howard.svg)

---

#### DigraphX Example (Howard)

```python
from pytest import approx
from digraphx.neg_cycle import NegCycleFinder

def find_beta(digraph, beta, dist, weight_fn,
    zero_cancel_fn, max_iter=2000
):
    finder = NegCycleFinder(digraph)
    num_iter = 0
    while num_iter < max_iter:
        num_iter += 1
        weight_fn = make_weight_fn(beta)
        cycle_found = False
        for neg_cycle in finder.howard(dist, weight_fn):
            beta = zero_cancel_fn(neg_cycle)
            cycle_found = True
            break # pick only the first neg. cycle
        if not cycle_found:
            return beta, num_iter
    return beta, max_iter
```

---

#### Example TCG

.mermaid[
<pre>
graph LR
    A -- "Tcp - 7" --> E(("v2"))
    A -. "6" .-> E
    A(("v0")) -- "Tcp - 6" --> B(("v3"))
    A -. "6" .-> B
    D(("v1")) -- "Tcp - 9" --> E
    D -. "6" .-> E
    E -- "Tcp - 6" --> B
    E -. "6" .-> B
    B -- "Tcp - 8" --> C(("v4"))
    B -. "8" .-> C
    C -- "Tcp - 3" --> D
    C -. "3" .-> D
    %% Caption: Timing Constraint Graph (TCG).
</pre>
]

---

#### DigraphX Example (EVEN)

```python
def even(digraph, beta, dist, max_iter=2000):
    return find_beta(digraph, beta, dist,
        lambda b: (lambda edge: edge - b),
        lambda neg_cycle: sum(neg_cycle) / len(neg_cycle),
        max_iter)

TCP = 7.5
digraph = {
    "v0": {"v3": TCP - 6, "v2": TCP - 7},
    "v1": {"v2": TCP - 9, "v4": 3},
    "v2": {"v0": 6, "v1": 6, "v3": TCP - 6},
    "v3": {"v4": TCP - 8, "v0": 6, "v2": 6},
    "v4": {"v1": TCP - 3, "v3": 8},
}
dist = {"v0": 0, "v1": 0, "v2": 0, "v3": 0, "v4": 0}
beta, num_iter = even(digraph, 10, dist)
assert beta == approx(1.0)
```

---

#### Example TCG

.mermaid[
<pre>
graph LR
    A -- "(Tcp - 7, 1.5) " --> E(("v2"))
    A -. "(6, 3.1) " .-> E
    A(("v0")) -- "(Tcp - 6, 3.1) " --> B(("v3"))
    A -. "(6, 2.5) " .-> B
    D(("v1")) -- "(Tcp - 9, 4.1) " --> E
    D -. "(6, 2.5) " .-> E
    E -- "(Tcp - 6, 3.1) " --> B
    E -. "(6, 2.5) " .-> B
    B -- "(Tcp - 8, 4.1) " --> C(("v4"))
    B -. "(8, 1.5) " .-> C
    C -- "(Tcp - 3, 1.1) " --> D
    C -. "(3, 1.0)" .-> D
    %% Caption: Timing Constraint Graph (TCG).
</pre>
]

---

#### DigraphX Example (PROP)

```python
def prop(digraph, beta, dist, max_iter=2000):
    return find_beta(digraph, beta, dist,
        lambda b: (lambda edge: edge["c"] - b * edge["t"]),
        lambda neg_cycle: sum(edge["c"] for edge in neg_cycle) \
                        / sum(edge["t"] for edge in neg_cycle),
        max_iter)

TCP = 7.5
digraph = {
    "v0": {
        "v3": {"c": TCP - 6, "t": 3.1},
        "v2": {"c": TCP - 7, "t": 1.5},
    },
    "v1": {"v2": {"c": TCP - 9, "t": 4.1}, "v4": {"c": 3, "t": 1.0} },
    "v2": {...
    "v3": {...
    "v4": {"v1": {"c": TCP - 3, "t": 1.1}, "v3": {"c": 8, "t": 1.5} },
}
dist = {"v0": 0, "v1": 0, "v2": 0, "v3": 0, "v4": 0}
beta, num_iter = prop(digraph, 10, dist)
assert beta == approx(0.32258064516129037)
```

---

#### Hybrid Method

![image](lec05.files/hybrid.svg)

---

#### Improved Howard's Algorithm

![image](lec05.files/improved.svg)

---

#### What can modern STA tools do today?

-   Manually assign clock arrival times to registers (all zeros by default) ⚙️
-   Grouping: Non-critical parts can be grouped as a single unit. 🧩
  In other words, there is no need for full-chip optimization.
-   Takes care of multi-cycle paths, slew rate, clock-gating, false paths etc. All we need are the reported **slacks**.
-   Provide 3-sigma statistics for slacks/path delays (POCV). 📈
-   However, the full probability density function and correlation information are not available. ⚠️

---

#### Unimodality

-   In statistics, a unimodal probability distribution or unimodal distribution is a probability distribution with a single peak.
-   In continuous distributions, unimodality can be defined through the behavior of the cumulative distribution function (cdf). If the cdf is *convex* for $x < m$ and *concave* for $x > m$, then the distribution is unimodal, $m$ being the *mode*. 🔍
-   Examples 📚
  -   Normal distribution
  -   Log-normal distribution
  -   Log-logistic distribution
  -   GEV distribution

---

#### Quantile function

-   The quantile function $z_p$ of a distribution is the inverse of the cumulative distribution function ${\color{olive}\Phi}^{-1}({\color{coral}p})$. 📐
-   Close-form expression for some unimodal distributions: 🔢
  -   Normal: ${\color{blue}\mu} + {\color{blue}\sigma}\sqrt 2 \text{erf}^{-1}(2 {\color{coral}p} - 1)$
  -   Log-normal: $\exp\left( {\color{blue}\mu} + {\color{blue}\sigma}\sqrt 2 \text{erf}^{-1}(2 {\color{coral}p} - 1)\right)$
  -   Log-logistic: ${\color{blue}\alpha}\left( \frac{\color{coral}p}{1 - \color{coral}p} \right)^{1/{\color{blue}\beta} }$

-   For log-normal distribution:
  -   mode: $\exp({\color{blue}\mu} - {\color{blue}\sigma}^2)$
  -   CDF at mode: $1/2 (1 + \text{erf}(-{\color{blue}\sigma} / \sqrt 2))$

---

#### Setup- and Hold-time Constraints

-   Let $T_\text{skew}(i,f) = {\color{firebrick}t_i} - {\color{firebrick}t_f}$, where ⏱️
  -   ${\color{firebrick}t_i}$: clock signal delay at the initial register
  -   ${\color{firebrick}t_f}$: clock signal delay at the final register
  -   Assume in zero-skew, i.e. $T_\text{skew}(i,f) = 0$,
    -   the reported setup-time slack is $S_{if}$
    -   the reported hold-time slack is $H_{if}$
-   Then, in useful skew design:
    $$T_\text{skew}(i,f) \le S_{if} \implies {\color{firebrick}t_i} - {\color{firebrick}t_f} \le S_{if}$$
    $$T_\text{skew}(i,f) \ge -H_{if} \implies {\color{firebrick}t_f} - {\color{firebrick}t_i} \le H_{if} $$
-   In principle, $H_{if} \text{ and } T_\text{CP} - S_{if}$ represent the minimum- and maximum-path delay, and should be always greater than zero.
-   Let $D_{if} = T_\text{CP} - S_{if}$

---

#### Yield-driven Optimization

-   Max-Min Formulation: 🎯
  -   $\max\{\min\{ \text{\color{olive}Pr}\{ {\color{firebrick}t_j} - {\color{firebrick}t_i} \le \tilde{W}_{ij} \}\}\}$,
  -   No need for correlation information between $\tilde{W}_{ij}$.
  -   Not exactly the timing yield objective but reasonable.
-   Equivalent to: 🔄
  $$\begin{array}{ll}
    \text{maximum} & {\color{coral}\beta} \\
    \text{subject to} & \text{\color{olive}Pr}\{ {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - \tilde{D}_{ij} \} \ge {\color{coral}\beta} \\
    & \text{\color{olive}Pr}\{ {\color{firebrick}t_j} - {\color{firebrick}t_i} \le \tilde{H}_{ij} \} \ge {\color{coral}\beta}
  \end{array}$$
  or
  $$\begin{array}{ll}
    \text{maximum} & {\color{coral}\beta} \\
    \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - {\color{olive}\Phi}^{-1}_{D_{ij}\ }({\color{coral}\beta}) \\
      & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le {\color{olive}\Phi}^{-1}_{H_{ij}\ }(1 - {\color{coral}\beta})
  \end{array}$$

---

#### Yield-driven Optimization (cont'd)

-   In general, Lawler's algorithm (binary search) can be used. ⚙️
-   Depending on the distribution, there are several other ways to solve problem. 🔄

---

#### Gaussian Model (Bell shape 🔔)

-   Reduce to: 🔄

$$\begin{array}{ll}
  \text{maximum} & {\color{coral}\beta} \\
  \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - ({\color{blue}\mu}^D_{ij} + {\color{blue}\sigma}^D_{ij} {\color{forestgreen}\sqrt 2\text{erf}^{-1}(2{\color{coral}\beta} - 1)} ) \\
    & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le {\color{blue}\mu}^H_{ij} + {\color{blue}\sigma}^H_{ij} {\color{forestgreen}\sqrt 2 \text{erf}^{-1}(2(1 - {\color{coral}\beta})-1)}
\end{array}$$

-   Linearization. Since $\text{erf}^{-1}(\cdot)$ is anti-symmetric and monotonic, we have:

$$\begin{array}{ll}
  \text{maximum} & {\color{forestgreen}\beta'} \\
  \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - {\color{blue}\mu}^D_{ij} - {\color{blue}\sigma}^D_{ij} {\color{forestgreen}\beta'} \\
    & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le {\color{blue}\mu}^H_{ij} - {\color{blue}\sigma}^H_{ij} {\color{forestgreen}\beta'}
\end{array}$$

-   is equivalent to the minimum cost-to-time ratio cycle (linear).

-   However, actual path delay distributions are non-Gaussian 🔕.

---

#### Log-normal Delay Model

-   Reduce to:

$$\begin{array}{ll}
  \text{maximum} & {\color{coral}\beta} \\
  \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - \exp({\color{blue}\mu}^D_{ij} + {\color{blue}\sigma}^D_{ij} {\color{forestgreen}\sqrt 2\text{erf}^{-1}(2{\color{coral}\beta} - 1)} ) \\
    & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le \exp({\color{blue}\mu}^H_{ij} + {\color{blue}\sigma}^H_{ij} {\color{forestgreen}\sqrt 2 \text{erf}^{-1}(2(1 - {\color{coral}\beta})-1)})
\end{array}$$

-   Since $\text{erf}^{-1}(\cdot)$ is anti-symmetric and monotonic, we have:

$$\begin{array}{ll}
  \text{maximum} & {\color{forestgreen}\beta'} \\
  \text{subject to} & {\color{firebrick}t_i} - {\color{firebrick}t_j} \le T_\text{CP} - \exp({\color{blue}\mu}^D_{ij} + {\color{blue}\sigma}^D_{ij} {\color{forestgreen}\beta'}) \\
    & {\color{firebrick}t_j} - {\color{firebrick}t_i} \le \exp({\color{blue}\mu}^H_{ij} - {\color{blue}\sigma}^H_{ij} {\color{forestgreen}\beta'})
\end{array}$$

-   Bypass evaluating error function. Non-linear and non-convex, but still can be solved efficiently by for example binary search on ${\color{forestgreen}\beta'}$.

---

#### Conclusion and Future Direction

-   Asymmetric Delays

Path delays often exhibit asymmetric and heavy-tailed distributions, which cannot be accurately captured by the commonly used Gaussian model.

-   GEV Distribution

The Generalized Extreme Value (GEV) distribution can better fit the actual delay distributions, with its flexible parameters allowing for a variety of skewness and tail behaviors.

---

## Q&A 🎤

]
.pull-right[

![image](figs/questions-and-answers.svg)

]