layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Some thoughts on global placement π‘ ### Fairness-centric analytical placement @luk036 π¨βπ» Β· 2026 π --- ### π Agenda .pull-left[ **Part 1: Motivation** π― - Who is to blame for congestion? π€ - Smooth approximation βοΈ - HPWL wire-length model π **Part 2: Fairness-Centric Objective** βοΈ - Lessons from timing optimization π§ - Min-max fairness π - Min-Sum vs Min-Max βοΈ ] .pull-right[ **Part 3: Flow-based Optimization** π» - Separable x/y directions βοΈ - ASIC placement π - Parametric network flow π ] --- class: nord-light, middle, center ## Part 1: Motivation π― --- ### π€ Who is to blame for the congestion problem? -- A1. The smooth approximated HPWL of the analytical placer should be blamed. - Convex β analytical placement (gradient can be computed analytically) - Note 1: Quadratic approximation: can be efficiently solved by the conjugate gradient method. - Note 2: Non-quadratic approximation: e.g. log-sum-exp technique. - Fixed position constraints - Density constraints - Non-convex β simulated annealing - Legalization β detailed placement .mermaid[ <pre> graph LR A["Netlist with\n Fixed Pins"] --> B{Objective} B -->|Quadratic| CG["Conjugate\n Gradient"] B -->|Log-Sum-Exp| LSE["Smooth\n Approximation"] CG --> P["Global\n Placement"] LSE --> P P --> L[Legalization] L --> D["Detailed\n Placement"] style A fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style CG fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style LSE fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style P fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style L fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] --- ### βοΈ Who is to blame for the congestion problem? A2. HPWL wire-length model should be blamed. - Underestimated when ${\color{red} n} > 3$, where ${\color{red} n}$ = the number of pins of a net. - Thereafter, some compensate factor (e.g. Rent's rule) are used. -- A simple fact that has been ignored for 50 years? π€ --- ### π HPWL: 2-pin vs Multi-pin Nets .mermaid[ <pre> graph LR subgraph "2-pin Net" P1[Pin A] --- P2[Pin B] EQ[HPWL = Actual β ] end subgraph "Multi-pin Net (n>3)" P3[Pin C] --- P4[Pin D] P3 --- P5[Pin E] P3 --- P6[Pin F] NEQ[HPWL < Actual β] end style EQ fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style NEQ fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] --- class: nord-light, middle, center ## Part 2: Fairness-Centric Objective βοΈ --- ### π§ What have I learned from timing optimization? - "δΈζ£ε―‘θζ£δΈε" - "δΈε" means "unfair", not "uneven" - Cantonese: "εη" - **As long as the objective is to minimize the total wire-length, the problem will not go away.** --- ### π How to achieve fairness while reducing wire-length - Min-max fairness: minimize the worst wire length (still convex) - Min-max is usually (but not always) easier to solve than Min-sum. - Imposing proportional fairness through weighted costs - Related paper: A. Kahng, S. Mantik and I. L. Markov, Min-Max Placement For Large-Scale Timing Optimization, ISPD'03. (minimize the worst delay path, non-convex?) --- ### βοΈ Min-Sum vs Min-Max .mermaid[ <pre> graph LR subgraph "Min-Sum" MS["Minimize\n β wirelength"] R1["Some nets very long\n Congestion β"] end subgraph "Min-Max" MM["Minimize\n max wirelength"] R2["Balanced distribution\n Fairness β "] end style MS fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style R1 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style MM fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style R2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- class: nord-light, middle, center ## Part 3: Flow-based Optimization π» --- ### βοΈ Optimize x-direction and y-direction separately. Why?  --- ### π ASIC  --- ### π Flow-based Optimization - 1D Placement can be formulated as a network flow (dual) problem - Min-sum objective: min-cost flow problem - Min-Max objective: parametric network flow problem - Advantage: - Faster than LP π - Allow discrete solution πππ - Disadvantage: - Difficult to impose additional constraints π - 2D, 3D: alternating directions .mermaid[ <pre> graph TD subgraph "1D Placement" Prob[Placement] --> Dual[Dual Network Flow] Dual --> MCF{Objective} MCF -->|Min-Sum| MCS[Min-Cost Flow] MCF -->|Min-Max| PAR[Parametric Flow] MCS --> SOL[Discrete Solution] PAR --> SOL end Prob --> Alt[Alternating Directions] Alt --> X[X-axis] Alt --> Y[Y-axis] style Prob fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style Dual fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style MCF fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style MCS fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style PAR fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style SOL fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style Alt fill:#fff3e0,stroke:#e65100,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 π