layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # ⌚ Clock Skew Scheduling for Unimodal Distributed Delay Models @luk036 👨‍💻 · 2026 📅 --- ### Useful Skew Design: Why and Why not? .pull-left[ Bad 👎: - Needs more engineer training. - Balanced clock-trees are harder to build. - Don't know how to handle process variation, multi-corner multi-mode, ..., etc. ] .pull-right[ Good 👍: If you do it right, - spend less time struggling about timing, or - get better chip performance or yield. ] --- ### 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 --- ### CSS Flow with Unimodal Delay .mermaid[ <pre> flowchart LR A["Timing Analysis"] --> B["Unimodal Delay Model"] B --> C["Quantile Function"] C --> D["Yield Constraints"] D --> E["Linear/Convex Solver"] E --> F["Optimal Skew Schedule"] style A fill:#4caf50 style B fill:#2196f3 style C fill:#ff9800 style D fill:#9c27b0 style E fill:#f44336 style F fill:#4caf50 </pre> ] --- ### Quantile function - The quantile function $z_p$ of a distribution is the inverse of the cumulative distribution function $\Phi^{-1}(p)$. - Close-form expression for some unimodal distributions: - Normal: $\mu + \sigma\sqrt 2 \text{erf}^{-1}(2p - 1)$ - Log-normal: $\exp\left( \mu + \sigma\sqrt 2 \text{erf}^{-1}(2p - 1)\right)$ - Log-logistic: $\alpha\left( \frac{p}{1-p} \right)^{1/\beta}$ - For log-normal distribution: - mode: $\exp(\mu - \sigma^2)$ - CDF at mode: $1/2 (1 + \text{erf}(-\sigma / \sqrt 2))$ --- ### Setup- and Hold-time Constraints - Let $T_\text{skew}(i,f) = {\color{red}t_i} - {\color{red}t_f}$, where - ${\color{red}t_i}$: clock signal delay at the initial register - ${\color{red}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{red}t_i} - {\color{red}t_f} \le S_{if}$$ $$T_\text{skew}(i,f) \ge -H_{if} \implies {\color{red}t_f} - {\color{red}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{Pr}\{ {\color{red}t_j} - {\color{red}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{Pr}\{ {\color{red}t_i} - {\color{red}t_j} \le T_\text{CP} - \tilde{D}_{ij} \} \ge {\color{coral}\beta} \\ & \text{Pr}\{ {\color{red}t_j} - {\color{red}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{red}t_i} - {\color{red}t_j} \le T_\text{CP} - \Phi^{-1}_{D_{ij}\ }({\color{coral}\beta}) \\ & {\color{red}t_j} - {\color{red}t_i} \le \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{red}t_i} - {\color{red}t_j} \le T_\text{CP} - (\mu^D_{ij} + \sigma^D_{ij} {\color{blue}\sqrt 2\text{erf}^{-1}(2{\color{coral}\beta} - 1)} ) \\ & {\color{red}t_j} - {\color{red}t_i} \le \mu^H_{ij} + \sigma^H_{ij} {\color{blue}\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{coral}\beta'} \\ \text{subject to} & {\color{red}t_i} - {\color{red}t_j} \le T_\text{CP} - \mu^D_{ij} - \sigma^D_{ij} {\color{coral}\beta'} \\ & {\color{red}t_j} - {\color{red}t_i} \le \mu^H_{ij} - \sigma^H_{ij} {\color{coral}\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{red}t_i} - {\color{red}t_j} \le T_\text{CP} - \exp(\mu^D_{ij} + \sigma^D_{ij} {\color{blue}\sqrt 2\text{erf}^{-1}(2{\color{coral}\beta} - 1)} ) \\ & {\color{red}t_j} - {\color{red}t_i} \le \exp(\mu^H_{ij} + \sigma^H_{ij} {\color{blue}\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{coral}\beta'} \\ \text{subject to} & {\color{red}t_i} - {\color{red}t_j} \le T_\text{CP} - \exp(\mu^D_{ij} + \sigma^D_{ij} {\color{coral}\beta'}) \\ & {\color{red}t_j} - {\color{red}t_i} \le \exp(\mu^H_{ij} - \sigma^H_{ij} {\color{coral}\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{coral}\beta'}$. --- count: false class: nord-dark, middle, center .pull-left[ # Q&A 🎤 ] .pull-right[  ] --- ### Backup: Some operations that preserve convexity - $-f$ is concave if and only if $f$ is convex. - Nonnegative weighted sums: - if $w_1, \ldots, w_n \ge 0$ and $f_1, \ldots, f_n$ are all convex, then so is $w_1 f_1 + \cdots + w_n f_n.$ In particular, the sum of two convex functions is convex. - Composition: - If $f$ and $g$ are convex functions and $g$ is non-decreasing over a univariate domain, then $h(x) = g(f(x))$ is convex. As an example, if $f$ is convex, then so is $e^{f(x)},$ because $e^x$ is convex and monotonically increasing. - If $f$ is concave and $g$ is convex and non-increasing over a univariate domain, then $h(x) = g(f(x))$ is convex. - Convexity is invariant under affine maps.