layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # ⏱️ Novel Multi-Corner Delay Padding using Path Relationship Analysis and Dual Decomposition @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Introduction & Timing Constraints** ⏱️ - Setup & Hold Constraints ⏳ - Timing Constraint Graph (TCG) 📈 - GEV Statistical Timing 📊 **Part 2: Path Relationship Analysis** 🧩 - Feasible Padding Locations 🔍 - Four Structural Configurations 🔢 ] .pull-right[ **Part 3: Dual Decomposition** 🤝 - Multi-Corner Consistency 🌐 - Iterative Optimization 🔄 **Part 4: Experimental Results** 📊 - Benchmarks & Setup 🔬 - Optimization Performance 🚀 **Conclusion** 🎉 ] --- class: nord-light, middle, center ## Part 1: Introduction & Timing Constraints ⏱️ --- ### The Challenge: Timing Under PVT Variation 🌡️ - Modern designs face significant variability from **Process, Voltage, Temperature (PVT)** and manufacturing variations 🌡️⚡⚙️. - Circuits must stay **robust and correct** across all these conditions 🛡️. - **Setup Time** ⏳: data must settle and be accurately read by a flip-flop. - **Hold Time** ⏲️: data must be latched without changing prematurely. - Timing violations (setup or hold) → circuit malfunction 💥. --- ### Limitations of Traditional Methods 🔄 - Optimize for a **single worst-case corner** → overdesign and sub-optimal performance under typical conditions. - **"Ping-pong" effect** 🔄: fixing one corner can violate another → non-convergent optimization. - A **multi-corner, path-aware** approach is needed. --- ### Fixing Violations: Clock Skew Scheduling (CSS) ⏰ - Adjusts **clock arrival times** at flip-flops, **without altering data paths** 🚫🔧. - Balances **setup** and **hold** constraints ⚖️. - **Limitation** 🚧: if the Timing Constraint Graph (TCG) has **negative cycles**, CSS alone cannot fix the violations. --- ### Fixing Violations: Delay Padding 🛠️ - **Delay padding**: strategically **inserting additional delay** into a specific data path. - Primarily fixes **hold violations**, without altering logic functionality. - **Integrated approach** 🤝: CSS + delay padding = additional degree of freedom → more robust, flexible timing closure. --- ### Challenges: Cost & Physical Feasibility 🏗️ - **Cost** 💰: minimizing $\sum {\color{blue}p}$ **may not reflect the true design cost** — delay insertion often means **swapping a faster cell for a slower one** 🔄. - **Feasibility** 🏗️: some paths lack valid insertion positions; many methods ignore the **relationship between max/min delay paths** (shared logic, mutual influence). --- ### Challenge: Multi-Corner Complexity 🌐 - Applying padding **consistently across corners** is hard: - Conflicting constraints between corners - Prevalence of **"ping-pong" effects** 🔄 - Requires **joint, coordinated** optimization across corners. --- ### Our Methodology: PRA + Dual Decomposition ✨ - **Goal** 🎯: find **feasible padding** and the **minimum clock period** satisfying setup/hold in **all corners**. - **PRA** 🔍: identify **physically feasible padding locations first**, then compute delays 💡. - **Dual Decomposition** 🔄: per-corner network flow subproblems, **coupled via shared delays** (Lagrange multipliers). - **Result** 📊: up to **6% clock period reduction** vs. single worst-case baseline. --- ### Clock Skew & Timing Constraints 📐 - **Clock skew**: $${\color{darkblack} T_{skew}}(i, j) = {\color{darkblack} t_i} - {\color{darkblack} t_j}$$ (2) — arrival-time difference at FFs $FF_i$, $FF_j$. - **Setup** ⏳: $${\color{darkblack} T_{skew}}(i, j) \le {\color{darkblack} T_\text{CP}} - {\color{blue}D}_{ij} - {\color{blue}T_{setup}}$$ (3) - **Hold** ⏲️: $${\color{darkblack} T_{skew}}(i, j) \ge {\color{blue}d}_{ij} - {\color{blue}T_{hold}}$$ (4) - ${\color{blue}D}_{ij}$: **max** path delay; ${\color{blue}d}_{ij}$: **min** path delay; ${\color{darkblack} T_\text{CP}}$: clock period. --- ### Timing Constraint Graph (TCG) 📈 - The difference constraints (2)–(4) form a **timing constraint graph** $G({\color{salmon}V}, {\color{lime}E})$. - **Vertices** 🎯: flip-flops ($i \in {\color{salmon}V}$), plus virtual ${\color{salmon}v}_0$ for primary inputs/outputs. - **Edges** 🔗: **solid** = setup relation; **dashed** = hold relation. - **Negative cycle** 🔄: negative edge-weight sum → **timing failure** ❌; no skew assignment can satisfy the constraints. - $$\sum_{{\color{lime}e}_{ij} \in {\color{lime}C}} ({\color{darkblack} t_i} - {\color{darkblack} t_j}) = 0 \le \sum_{{\color{lime}e}_{ij} \in {\color{lime}C}} ({\color{darkblack} T_\text{CP}} - {\color{blue}D}_{ij} - {\color{blue}T_{setup}})$$ - $$\sum_{{\color{lime}e}_{ij} \in {\color{lime}C}} ({\color{darkblack} t_j} - {\color{darkblack} t_i}) = 0 \le \sum_{{\color{lime}e}_{ij} \in {\color{lime}C}} ({\color{blue}d}_{ij} - {\color{blue}T_{hold}})$$ (5) - Delay padding **relaxes the hold constraint** (4), eliminating negative cycles. --- ### TCG Example 🗺️ - Nodes = flip-flops (or virtual I/O); edges = setup/hold constraints with slack values. .mermaid[ <pre> graph LR V0(V0 - PI/O) FF1(FF1) FF2(FF2) FF3(FF3) FF4(FF4) V0 -- "CP-3" --> FF1 FF1 -- "3" --> V0 V0 -- "CP-7" --> FF2 FF2 -- "6" --> V0 FF1 -- "CP-10" --> FF4 FF4 -- "8" --> FF1 FF1 -- "6" --> FF2 FF2 -- "CP-6" --> FF1 FF2 -- "6" --> FF3 FF3 -- "CP-6" --> FF2 FF3 -- "6" --> FF4 FF4 -- "CP-8" --> FF3 style V0 fill:#e1f5fe,stroke:#01579b,stroke-width:3px style FF1 fill:#fce4ec,stroke:#880e4f,stroke-width:3px style FF2 fill:#fce4ec,stroke:#880e4f,stroke-width:3px style FF3 fill:#fce4ec,stroke:#880e4f,stroke-width:3px style FF4 fill:#fce4ec,stroke:#880e4f,stroke-width:3px </pre> ] - **Note** 📝: simplified conceptual representation inspired by Fig. 1b (edge weights illustrative). --- ### Process Variation & Statistical Timing Analysis 📊 - Process variations → **statistical uncertainty** in circuit behavior 🌪️. - **SSTA** 📈: models gate/interconnect delays as **probability distributions**. - **Gaussian models fail** 📉: max-delay distributions are **asymmetric**, deviating from Gaussian assumptions. - **Our choice: GEV** 📈: captures the **tail distribution** critical for worst-case timing; enables yield-targeted optimization; focus on ${\color{green} \xi} \ne 0$ (heavy tails, delays strictly positive). --- ### GEV Distribution: Parameters & PDF 📉 - Three parameters: location ${\color{green} \mu}$ 📍, scale ${\color{orange} \sigma} > 0$ 📏, shape ${\color{green} \xi}$ 🔄. - **PDF**: $${\color{purple}f}({\color{blue}x}) = \frac{1}{{\color{orange} \sigma}} {\color{purple}t}({\color{blue}x})^{{\color{green} \xi}+1} e^{-{\color{purple}t}({\color{blue}x})}$$ (8) - with $${\color{purple}t}({\color{blue}x}) = \left[ 1 + {\color{green} \xi} \left( \frac{{\color{blue}x}-{\color{green} \mu}}{{\color{orange} \sigma}} \right) \right]^{-1/{\color{green} \xi}}$$ if ${\color{green} \xi} \ne 0$ --- ### GEV Distribution: CDF & Quantile 📊 - **CDF**: $${\color{purple}F}({\color{blue}x}) = e^{-{\color{purple}t}({\color{blue}x})}$$ (9) - Support: ${\color{blue}x} \in [{\color{green} \mu}-\frac{{\color{orange} \sigma}}{{\color{green} \xi}}, \infty)$ (${\color{green} \xi} > 0$) or $(-\infty, {\color{green} \mu}-\frac{{\color{orange} \sigma}}{{\color{green} \xi}}]$ (${\color{green} \xi} < 0$). - **Quantile** 🔢: inverse of the CDF, used for statistical timing checks. - $${\color{purple}Q} = {\color{green} \mu} + \frac{{\color{orange} \sigma}}{{\color{green} \xi}} ( (-\ln{\color{green} \beta})^{-{\color{green} \xi}} - 1)$$ (10) - ${\color{green} \beta}$: timing satisfaction probability. --- ### Statistical Setup Constraint ⏳ - Probabilistic constraint → deterministic equivalent via the GEV **quantile**. - $${\color{darkblack} T_{skew}} \le {\color{darkblack} T_\text{CP}} - {\color{blue}\tilde{D}} - {\color{blue}T_{setup}}$$ (15) - Deterministic: $${\color{darkblack} T_\text{CP}} - {\color{blue}T_{setup}} - {\color{darkblack} T_{skew}} \ge {\color{purple}Q}_D({\color{green} \beta})$$ - Setup failures occur under **slow** conditions → sensitive to the delay **tail**. --- ### Statistical Hold Constraint ⏲️ - $${\color{darkblack} T_{skew}} \ge {\color{blue}T_{hold}} - {\color{blue}\tilde{d}}$$ (16) - Deterministic: $${\color{blue}T_{hold}} - {\color{darkblack} T_{skew}} \ge {\color{purple}Q}_d(1-{\color{green} \beta})$$ (18) - Hold violations occur under **fast** conditions → sensitive to the **lower tail**. - ${\color{purple}Q}_D({\color{green} \beta})$, ${\color{purple}Q}_d(1-{\color{green} \beta})$: quantiles of max/min delay distributions. --- class: nord-light, middle, center ## Part 2: Path Relationship Analysis 🧩 --- ### PRA: Feasible Padding Locations 🔍 - **First step** 🔍: analyze how setup & hold paths **interact**. - **Purpose** 🎯: identify **physically feasible** padding locations; enhance the TCG to capture structural overlap & timing coupling. - Four structural configurations determine how delays are inserted (next slide). --- ### PRA: Four Structural Configurations 🔢 - **a. Direct** 🔗: FF pair directly connected → no insertion path; TCG unchanged. - **b. Independent** ✂️: max/min delay paths disjoint → independent padding ${\color{blue}p}_s$, ${\color{blue}p}_h$. - **c. Shared** 🤝: paths overlap entirely → ${\color{blue}p}_s = {\color{blue}p}_h$ (single shared node). - **d. Contained** 📦: hold path ⊂ setup path → coupling ${\color{blue}p}_s \ge {\color{blue}p}_h$. --- ### Visualizing PRA: Four Configurations 🖼️ .mermaid[ <pre> graph TD subgraph "Type a: No delay can be inserted (Direct connection)" ui_a["ui"] -- "CP-4" --> uj_a["uj"] ui_a -- "1.5" --> uj_a end subgraph "Type b: ps, ph independently (Independent structure)" ui_b["ui"] -- "0" --> us_b(us) ui_b -- "0" --> uh_b(uh) us_b -- "CP-4" --> uj_b["uj"] uh_b -- "1.5" --> uj_b end subgraph "Type c: ps = ph (Shared path segment)" ui_c["ui"] -- "0" --> us_c(us=uh) us_c -- "CP-4" --> uj_c["uj"] us_c -- "1.5" --> uj_c end subgraph "Type d: ps >= ph (Hierarchical containment)" ui_d["ui"] -- "0" --> us_d(us) ui_d -- "0" --> uh_d(uh) us_d -- "0" --> uh_d us_d -- "CP-4" --> uj_d["uj"] uh_d -- "1.5" --> uj_d end style ui_a fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style uj_a fill:#ffccbc,stroke:#bf360c,stroke-width:3px style ui_b fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style us_b fill:#fff9c4,stroke:#f57f17,stroke-width:3px style uh_b fill:#fff9c4,stroke:#f57f17,stroke-width:3px style uj_b fill:#ffccbc,stroke:#bf360c,stroke-width:3px style ui_c fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style us_c fill:#fff9c4,stroke:#f57f17,stroke-width:3px style uj_c fill:#ffccbc,stroke:#bf360c,stroke-width:3px style ui_d fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style us_d fill:#fff9c4,stroke:#f57f17,stroke-width:3px style uh_d fill:#fff9c4,stroke:#f57f17,stroke-width:3px style uj_d fill:#ffccbc,stroke:#bf360c,stroke-width:3px </pre> ] - **Legend** 📜: `ui`, `uj` = flip-flops; `us`, `uh` = auxiliary nodes for setup/hold padding. --- class: nord-light, middle, center ## Part 3: Dual Decomposition 🤝 --- ### Dual Decomposition: Formulation 🤝 - **Motivation** 🌍: padding must stay **consistent across corners** — avoids the iterative "ping-pong" effect 🔄. - **Core idea** 💡: each corner optimizes independently; global consistency via **Lagrange multipliers**. - **Objective**: minimize deviation from consensus — $$\min_{\{{\color{darkblack} y_k}\} } \sum_k {\color{firebrick}\lambda}_k^\top({\color{darkblack} y_k} - {\color{darkblack} y_{shared}})$$ - **Constraints**: flow conservation ${\color{red} A} \cdot {\color{red} u} = {\color{darkblack} y}$; setup bound ${\color{darkblack} y_{kij}} \le {\color{darkblack} T_\text{CP}} - {\color{blue}D}_{k,ij} - {\color{blue}T_{setup}}$; hold bound ${\color{darkblack} y_{kij}} \ge {\color{blue}T_{hold}} - {\color{blue}d}_{k,ij}$ (12). --- ### Dual Decomposition: Iterative Process 🔄 - **Lagrangian relaxation** 🔗 decouples the consistency constraint ${\color{darkblack} y_k} = {\color{darkblack} y_{shared}}$ → independent per-corner subproblems. - Repeat until convergence: 1. **Solve** each corner's subproblem independently and in parallel 🧩. 2. **Average**: $${\color{darkblack} y_{shared}} \leftarrow \frac{1}{K} \sum_{k=1}^{K} {\color{darkblack} y_k}$$ (13) — $K$ = number of corners. 3. **Update** multipliers (sub-gradient ascent): $${\color{firebrick}\lambda}_k \leftarrow {\color{firebrick}\lambda}_k + {\color{green}\rho}({\color{darkblack} y_k} - {\color{darkblack} y_{shared}})$$ (14) — step size ${\color{green}\rho} > 0$. - **Convergence** ✅: local solutions agree with the global average. --- ### Statistical (GEV) Formulation 📊 - Replace deterministic delays with **GEV random variables**. - Quantile-based constraints ensure **probabilistic** timing satisfaction: - Setup: $${\color{darkblack} y_{kij}} \le {\color{darkblack} T_\text{CP}} - {\color{purple}Q}_{D}^k({\color{green}\beta}) - {\color{blue}T_{setup}}$$ - Hold: $${\color{darkblack} y_{kij}} \ge {\color{blue}T_{hold}} - {\color{purple}Q}_{d}^k(1-{\color{green}\beta})$$ (19) --- ### Complete Optimization Flow 🚀 - Minimize feasible ${\color{darkblack} T_\text{CP}}$ via **dual decomposition + binary search** under target yield ${\color{green}\beta}$. .mermaid[ <pre> graph TD A[Circuit Design] --> B{Multi-Corner STA}; B --> C[Timing Info. Extraction]; C --> D[Path Relationship Analysis]; D --> E[TCG Enhancement]; E --> F{Build Timing Constraint Graph}; F --> G{Detect Negative Cycles?}; G -- Yes --> H[TCP Infeasible]; H --> I["Update T_low, TCP = (T_high + TCP)/2"]; G -- No --> J{Feasible Timing Solution?}; J -- No --> K["Dual Decomposition Delay Padding Solver (Multi-Corner)"]; K --> J; J -- Yes --> L{T_high - T_low < ε?}; L -- No --> M["Update T_high, TCP = (T_low + TCP)/2"]; L -- Yes --> N[Optimal TCP Found]; I --> F; M --> F; style A fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style B fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style C fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style E fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style F fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style G fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style H fill:#fce4ec,stroke:#ad1457,color:#2e3440,stroke-width:3px style I fill:#fff3e0,stroke:#e65100,stroke-width:3px style J fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style K fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style L fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style M fill:#fff3e0,stroke:#e65100,stroke-width:3px style N fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px </pre> ] --- ### Flow: Key Steps 🔑 1. **Multi-corner SSTA** 🌐: GEV-based; quantile checks at yield ${\color{green}\beta}$. 2. **Binary search** 🔍 over candidate ${\color{darkblack} T_\text{CP}}$. 3. **PRA & TCG enhancement** 🧩: add auxiliary nodes & coupling edges. 4. **Negative cycle check** ❌: infeasible → raise the lower bound. 5. **Dual decomposition solver** 🤖: corner-aware padding via Lagrange multipliers. 6. **Convergence** ✅: stop when ${\color{blue}T}_{high} - {\color{blue}T}_{low} < {\color{coral}\epsilon}$. --- class: nord-light, middle, center ## Part 4: Experimental Results 📊 --- ### Experimental Setup 🔬 - **Benchmarks** 🏗️: OpenCore & OpenABC-D. - **Library** 📚: open-source ASAP 7nm, multi-corner standard cells. - **Corners** 🌐: FF 🚀, SS 🐌, TT ⚖️. - **SSTA** 📊: GEV-based delay distributions. - **Yield** 🎯: quantile checks at ${\color{green}\beta} = 0.99$. - **Solver** ⚙️: binary search + CSS; dual-decomposition padding via **CVXPY**. --- ### Results: PRA Insights 🗺️ - Path-type distribution varies significantly across benchmarks 📊. - Most **critical paths** exhibit **Type C (shared)** and **Type D (containment)** relationships. - **Implication** 💡: padding critical paths can **unintentionally affect hold** → correct handling of path relationships is crucial. --- ### Results: Optimization Performance 🚀 - Optimized ${\color{darkblack} T_\text{CP}}$ lies **between FF (best) and SS (worst)** single-corner results ✅. - Balanced trade-off — avoids pessimistic single-corner margins. - **Average 6.12% reduction** vs. SS corner ⬆️. --- ### Results: Per-Benchmark Improvements 📈 | Benchmark | Reduction | |-----------|-----------| | `aes` | 4.97% | | `gcd` | **9.22%** | | `ethmac` | 7.85% | | `ibex` | 3.81% | | `jpeg` | 4.80% | | `tv80` | 6.88% | - Effectively **reduces the clock period** while maintaining timing correctness under variation. --- class: nord-light, middle, center ## Conclusion 🎉 --- ### Key Contributions ✨ - **GEV-based statistical modeling** 📊: accurate delay characterization → robust timing yield. - **Path Relationship Analysis (PRA)** 🔍: physically feasible padding locations, safe delay insertion. - **Dual decomposition** 🔄: scalable multi-corner optimization, eliminates "ping-pong" effects. - **Impact** 🌟: reduces the minimum feasible ${\color{darkblack} T_\text{CP}}$ while maintaining yield across all corners. --- count: false class: nord-dark, middle, center # 🙋 Q&A ### Questions? Discussion? 💬 - Thank you for your attention! 🙏 - **Future Work** 🔮: - Dynamic variations and their impact. - Integration with other physical design steps. - Larger, more complex industrial designs.