layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Some thoughts on global placement 💡 @luk036 👨‍💻 · 2026 📅 --- ### 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:#2196f3 style APR fill:#4caf50 style SA fill:#ff9800 style SAR fill:#f44336 </pre> ] --- ### Half Perimeter wire-length Model, HPWL - HPWL($e$) = xHPWL(e) + yHPWL(e) - xHPWL($e$) = $\max_{i\in e} x_i - \min_{i\in e} x_i$ - yHPWL($e$) = $\max_{i\in e} y_i - \min_{i\in e} y_i$ - Underestimate when $n > 3$, where $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:#ff9800 style HPWL fill:#2196f3 style ACC fill:#f44336 style YES fill:#4caf50 style NO fill:#f44336 </pre> ] --- ### Analytical placement - Approximations: - Quadratic approximation - QWL($e$) = $\omega_e \sum_{(i, j)\in e} [(x_i - x_j)^2 + (y_i - y_j)^2]$ - can be solved efficiently by the conjugate gradient method. - Non-quadratic approximation - such as log-sum-exp technique: - $\max_{i\in e} x_i - \min_{i\in e} x_i \approx \gamma (\log \sum_{i\in e} e^{x_i/\gamma} + \log \sum_{i\in e} e^{-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:#ff9800 style APPROX fill:#f44336 style QWL fill:#2196f3 style LSE fill:#2196f3 style GRAD fill:#4caf50 style FIX fill:#9c27b0 style DENS fill:#9c27b0 </pre> ] --- ### Optimize x- and y-directions separately. Why?  ---  --- ### 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:#ff9800 style D fill:#2196f3 style ADV fill:#4caf50 style DIS fill:#f44336 style SOL fill:#4caf50 style EXT fill:#9c27b0 style X fill:#2196f3 style Y fill:#2196f3 </pre> ] --- count: false class: nord-dark, middle, center Q&A 🎤 ==========