layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Some thoughts on global placement 💡 ### Analytical placement, HPWL & flow-based optimization @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Overview** 🎯 - Placement fundamentals 🧩 - Analytical vs simulated annealing ⚖️ **Part 2: Wire-length Models** 📏 - HPWL model 📐 - Quadratic & log-sum-exp ➗ ] .pull-right[ **Part 3: Flow-based Optimization** 💻 - Separable x/y directions ↔️ - ASIC placement 🏭 - 1D placement as network flow 🌊 ] --- class: nord-light, middle, center ## Part 1: Overview 🎯 --- ### 🧩 Placement - \>50 years - Most important in VLSI physical design - global placement - mainly: analytic + simulated annealing (SA) - but also: partitioning based, flow based? - wire-length, routability, timing - detailed placement - mainly for legalization - discrete optimization - The devil is in the details --- ### ⚖️ Global placement - Analytical placement - faster - mainly wire-length driven - goal: convex optimization??? - start from ASIC, later used in FPGA - Simulated Annealing - slow - mainly timing-driven - non-convex optimization .mermaid[ <pre> graph LR subgraph "Analytical" AP[Convex Opt] APR["Wire-length driven\n Fast ⚡"] end subgraph "Simulated Annealing" SA[Non-convex Opt] SAR["Timing-driven\n Slow 🐢"] end style AP fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style APR fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style SA fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style SAR fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] --- class: nord-light, middle, center ## Part 2: Wire-length Models 📏 --- ### 📐 Half Perimeter wire-length Model, HPWL - HPWL($e$) = ${\color{blue} \text{xHPWL}(e)} + {\color{orange} \text{yHPWL}(e)}$ - xHPWL($e$) = ${\color{red} \max_{i\in e} x_i} - {\color{blue} \min_{i\in e} x_i}$ - yHPWL($e$) = ${\color{red} \max_{i\in e} y_i} - {\color{blue} \min_{i\in e} y_i}$ - Underestimate when ${\color{red} n} > 3$, where ${\color{red} n}$ = the number of pins of a net. - Convex but non-smooth. - Some compensation factors (e.g. Rent's rule) has been used. .mermaid[ <pre> graph LR BB[Bounding Box] --> XHPW[xHPWL = max x - min x] BB --> YHPW[yHPWL = max y - min y] XHPW --> HPWL[HPWL = xHPWL + yHPWL] YHPW --> HPWL HPWL --> ACC{Accurate?} ACC -->|n ≤ 3| YES[Yes ✅] ACC -->|n > 3| NO[Underestimates ❌] style BB fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style HPWL fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style ACC fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style YES fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style NO fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] --- ### ➗ Analytical placement - Approximations: - Quadratic approximation - QWL($e$) = ${\color{orange} \omega_e} \sum_{(i, j)\in e} [{\color{blue} (x_i - x_j)^2} + {\color{green} (y_i - y_j)^2}]$ - can be solved efficiently by the conjugate gradient method. - Non-quadratic approximation - such as log-sum-exp technique: - ${\color{red} \max_{i\in e} x_i} - {\color{blue} \min_{i\in e} x_i} \approx {\color{green} \gamma} (\log \sum_{i\in e} e^{{\color{blue} x_i/\gamma}} + \log \sum_{i\in e} e^{{\color{orange} -x_i/\gamma}})$ - Gradients required are derived analytically - Constraints: - fixed position constraints - density constraints .mermaid[ <pre> graph TD HPWL[HPWL Objective] --> APPROX{Approximation} APPROX -->|Quadratic| QWL[QWL: Conjugate Gradient] APPROX -->|Log-Sum-Exp| LSE[Smooth Convex] QWL --> GRAD[Analytical Gradients] LSE --> GRAD GRAD --> OPT[Optimization] OPT --> CONS[Constraints] CONS --> FIX[Fixed Positions] CONS --> DENS[Density] style HPWL fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style APPROX fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style QWL fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style LSE fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style GRAD fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style FIX fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style DENS fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] --- class: nord-light, middle, center ## Part 3: Flow-based Optimization 💻 --- ### ↔️ Optimize x- and y-directions separately. Why?  --- ### 🔌 ASIC  --- ### 🌊 Flow-based Optimization - 1D Placement can be formulated as a network flow (dual) problem - Advantage: - Faster than LP 👍 - Allow discrete solution 👍👍👍 - Disadvantage: - Difficult to impose additional constraints 👎 - 2D, 3D: alternating directions .mermaid[ <pre> graph LR P[1D Placement] --> D[Dual Flow Problem] D --> ADV[Faster than LP 👍] D --> DIS[Hard constraints 👎] D --> SOL[Discrete Solution 👍👍👍] P --> EXT[2D/3D Extension] EXT --> X[X-direction] EXT --> Y[Y-direction] style P fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style D fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style ADV fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style DIS fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style SOL fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style EXT fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style X fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style Y fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px </pre> ] --- count: false class: nord-dark, middle, center # 🙋 Q&A ### Questions? Discussion? 💬 --- count: false class: nord-dark, middle, center # 👏 Thank You Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙