layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🎯 Multi-Objective Optimization in EDA ### Beyond PPA — Yield, Robustness & the Pareto Front @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **1️⃣ Beyond PPA** 🏭 - The Traditional Objective Space - Yield, Robustness, DFT, DFM **2️⃣ Algorithm Perspective** 🧠 - Beyond Runtime & Memory - Energy Efficiency & Simplicity **3️⃣ Global Placement** 🗺️ - Wirelength, Congestion, Timing - Why Single-Objective Fails ] .pull-right[ **4️⃣ Multi-to-Single Objective** 🎯 - Weighted Sum Method - Ratio & Quasi-Convexity **5️⃣ Pareto Front** 📊 - Pareto Dominance - Finding Trade-off Points **6️⃣ Summary** 💎 - Key Takeaways - Q&A ] --- class: nord-light, middle, center ## 🏭 Part 1: Beyond PPA --- ### 📐 The Traditional Objective Space: PPA **Classic EDA optimization is driven by three pillars:** .mermaid[ <pre> graph LR P["⚡ Performance\n(speed, fmax)"] PWR["🔋 Power\n(dynamic, leakage)"] A["📐 Area\n(transistors, wires)"] P --> OPT["🎯 Optimization\nEngine"] PWR --> OPT A --> OPT OPT --> D["📦 Chip\n(layout, netlist)"] style P fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style PWR fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style A fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style OPT fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style D fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px </pre> ] **PPA = Performance, Power, Area** — the classic trinity 📦 --- ### 🌱 Beyond PPA: The Hidden Objectives **Modern chips must be *manufacturable, testable, and robust* — not just fast:** .mermaid[ <pre> graph TD PPA["📦 PPA\nPerformance · Power · Area"] PPA --> Y["📈 Yield"] PPA --> R["🛡️ Robustness"] PPA --> D["🧪 Design-for-Test (DFT)"] PPA --> C["🧠 Design-for-CAD"] PPA --> M["🏭 Design-for-Manufacturability"] style PPA fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style Y fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style R fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style D fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style C fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style M fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] **Every additional objective competes with PPA** — the design space is inherently multi-dimensional 🧩 --- ### 📊 The Extended Objective Landscape .pull-left[ **Quality / Reliability:** - 📈 **Yield** — % of working chips per wafer - 🛡️ **Robustness** — tolerance to PVT variations - 🧪 **DFT** — testability & fault coverage - 🏭 **DFM** — manufacturability, printability **Every one of these trades off against PPA.** ] .pull-right[ **Cost / Time:** - ⏱️ **Time-to-market** - 💰 **Total cost** (design + mask + test) - 🔄 **Reusability** across designs .font-sm[ | Objective | Typical Conflict | |-----------|------------------| | 📈 Yield | ↓ with aggressive scaling | | 🛡️ Robustness | ↓ with tight margins | | 🧪 DFT | ↑ area & power | | 🏭 DFM | ↓ performance | ] ] --- class: nord-light, middle, center ## 🧠 Part 2: Algorithm Perspective --- ### ⚡ Beyond Runtime & Memory **Algorithms have objectives too — the same multi-objective thinking applies:** .mermaid[ <pre> graph LR RT["⏱️ Runtime"] --> ALG["🧮 Algorithm\nDesign"] MEM["💾 Memory"] --> ALG EN["🔋 Energy\nEfficiency"] --> ALG SIM["🧩 Simplicity"] --> ALG ALG --> DEP["🚀 Deployable\non-chip"] style RT fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style MEM fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style EN fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style SIM fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style ALG fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style DEP fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] **Key insight:** for **hardware-embedded algorithms**, energy and simplicity often matter more than raw speed 🔋 --- ### 💡 Why Energy & Simplicity Matter .pull-left[ **🔋 Energy Efficiency** - Embedded / battery-powered devices - Thermal budget limits frequency - Energy ≈ area × activity × voltage² **Example:** A slightly slower but **squarer** algorithm may win on energy. ] .pull-right[ **🧩 Simplicity** - Fewer moving parts → fewer bugs - Easier to verify & maintain - Smaller silicon footprint - **Occam's razor for algorithms** ✂️ > ⚖️ **The trade-off:** performance vs. energy vs. simplicity is *itself* a Pareto problem! ] --- class: nord-light, middle, center ## 🗺️ Part 3: Global Placement --- ### 🏠 Global Placement: A Canonical Example **Place cells on a chip to optimize several competing objectives simultaneously:** .mermaid[ <pre> graph TD NP["📋 Netlist\n(cells + nets)"] --> GP["🗺️ Global Placement"] GP --> WL["📏 Total Wirelength"] GP --> CG["🚦 Congestion"] GP --> TM["⏱️ Timing"] WL --> OPT["🎯 Single Solution"] CG --> OPT TM --> OPT style NP fill:#e8eaf6,stroke:#283593,color:#2e3440,stroke-width:3px style GP fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style WL fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style CG fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style TM fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style OPT fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] **Three objectives, one placement.** They pull in different directions ⚔️ --- ### ⚔️ The Conflict in Placement .pull-left[ **📏 Wirelength:** pack cells tightly - Shortens nets → faster, smaller - ❌ Causes congestion & hotspots **🚦 Congestion:** spread the routing - Avoids overflow & detours - ❌ Increases wirelength **⏱️ Timing:** align critical paths - Optimizes delay, not density - ❌ May sacrifice area & power ] .pull-right[ .font-sm[ | Objective | Push | Pull | |-----------|------|------| | 📏 Wirelength | Tight packing | Congestion ↑ | | 🚦 Congestion | Spread out | Wirelength ↑ | | ⏱️ Timing | Path alignment | Area ↑ | | 🔋 Power | Low activity | Delay ↑ | | 📐 Area | Small die | Routability ↓ | ] ] **No single placement maximizes all three** → we need **trade-off analysis** 🧭 --- ### 🤔 Why Single-Objective Optimization Fails **Collapsing everything into one number hides the trade-offs:** .mermaid[ <pre> graph LR A["🧩 Multi-objective\nproblem"] -->|"naive merge"| B["📉 Single objective\n(one weighted number)"] B --> C{"❓ Which solution?"} C -->|"Option A"| D1["✅ great timing\n❌ terrible congestion"] C -->|"Option B"| D2["✅ great congestion\n❌ terrible timing"] style A fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style B fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style D1 fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style D2 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] **Weights depend on context** — and are chosen *before* we see the solutions. **Pareto analysis shows the options first** 🎯 --- class: nord-light, middle, center ## 🎯 Part 4: Multi-to-Single Objective --- ### ⚖️ Method 1: Weighted Sum **Combine objectives into one scalar — the classic approach:** $$ \min_x \sum_{i=1}^{m} \alpha_i f_i(x), \qquad \alpha_i \geq 0 $$ .pull-left[ **How it works:** - Assign weight $\alpha_i$ to each objective - Solve one standard (convex) problem - Vary weights → explore trade-offs **Simple, fast, widely supported** ✅ ] .pull-right[ .mermaid[ <pre> graph LR F1["f₁(x)"] -->|"α₁"| S["Σ αᵢ fᵢ(x)"] F2["f₂(x)"] -->|"α₂"| S F3["f₃(x)"] -->|"α₃"| S S --> MIN["minimize"] MIN --> X["x*"] style F1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style F2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style F3 fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style S fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style MIN fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style X fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] ] --- ### ⚠️ Weighted Sum Caveats **The weighted sum has well-known blind spots:** .pull-left[ **❌ Scaling sensitivity** - Objectives have different units (ns, mm², mW) - Weights are only meaningful after **normalization** $$ \min_x \sum_{i=1}^{m} \alpha_i \frac{f_i(x)}{f_i^{\text{ref}}} $$ **❌ Non-convex Pareto front** - Points on the *concave* part of the front are **unreachable** by any weight combination ] .pull-right[ **✅ When it works** - Convex Pareto front - Small number of objectives - A *priori* preference is known **💡 Rule of thumb:** normalize first, then sweep weights $0 \to \infty$ to trace the front. ] --- ### 🧮 Method 2: Ratio Objective **Optimize one objective *relative* to another:** $$ \min_x \frac{f_1(x)}{f_2(x)}, \qquad f_2(x) > 0 $$ .pull-left[ **Key property — quasi-convexity:** - The ratio of a **convex** function to a **concave** function is **quasi-convex** - Sublevel sets are convex: $$ \{ x : f_1(x) / f_2(x) \leq t \} \iff f_1(x) - t\, f_2(x) \leq 0 $$ **Example:** minimize **delay / slack**, **power / performance** 🔋 ] .pull-right[ .mermaid[ <pre> graph TD R["min f₁/f₂"] --> Q["Quasi-convex?"] Q -->|"yes"| B["Bisection on t"] B --> C{"f₁ - t·f₂ ≤ 0\nfeasible?"} C -->|"yes → lower t"| B C -->|"no → raise t"| B B --> S["t* = optimal ratio"] style R fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style Q fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style S fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px </pre> ] ] --- ### 🔍 Quasi-Convex Optimization via Bisection **A ratio objective is solved by *binary search* on the ratio $t$:** $$ \text{minimize } \frac{f_1(x)}{f_2(x)} \quad \Longleftrightarrow \quad \text{find smallest } t \text{ s.t. } \exists x: f_1(x) - t\, f_2(x) \leq 0 $$ .font-sm[ ```python def min_ratio(f1, f2, lo, hi, eps=1e-6): # f1: convex, f2: concave positive → quasi-convex ratio while hi - lo > eps: t = (lo + hi) / 2 if feasible(f1, f2, t): # solve convex feasibility hi = t # try a smaller ratio else: lo = t # must raise the ratio return hi ``` ] **Each feasibility check is a convex problem** → solvable by CVXPY / ellipsoid method 🧮 --- class: nord-light, middle, center ## 📊 Part 5: Pareto Front --- ### 🏆 Pareto Dominance **A solution dominates another if it is *no worse* in every objective and *better* in at least one:** $$ u \prec v \quad \Longleftrightarrow \quad u_i \leq v_i \ \forall i \ \wedge \ \exists j : u_j < v_j $$ .pull-left[ **Pareto-optimal point:** dominated by *no* other feasible point $$ x^* \text{ optimal} \iff \nexists\, x \in \mathcal{F} : f(x) \prec f(x^*) $$ **Pareto front:** the set of all Pareto-optimal points 🗺️ ] .pull-right[ **Why it matters:** - ✅ No need to pick weights *a priori* - ✅ Reveals the full trade-off landscape - ✅ Designer chooses *after* seeing the options - ✅ Removes dominated (useless) candidates > 🎯 **"Show me the front, then let me choose."** ] --- ### 📈 Visualizing the Pareto Front .mermaid[ <pre> graph TD subgraph "Objective Space (f₁ vs f₂)" D1["⬤ Dominated\n(f₁ worse, f₂ worse)"] D2["⬤ Dominated\n(f₁ worse)"] D3["⬤ Dominated\n(f₂ worse)"] P1["🟢 Pareto-optimal\n(no one better)"] P2["🟢 Pareto-optimal"] P3["🟢 Pareto-optimal"] FR["🟥 Infeasible"] end D1 --> PF["🏆 Pareto Front\n(trade-off curve)"] D2 --> PF D3 --> PF P1 --> PF P2 --> PF P3 --> PF FR -.-> PF style D1 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style D2 fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style D3 fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style P1 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style P2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style P3 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style FR fill:#e8eaf6,stroke:#283593,color:#2e3440,stroke-width:3px style PF fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] **Every point on the front is optimal** — moving to improve one objective worsens another ⚖️ --- ### 🤔 Why Multi-Objective is Hard: Preference Revelation **The real difficulty is not computation — it is that we don't know exactly what we want:** $$ \underbrace{\text{"timing is 2× more important than area"}}_{\text{a priori guess}} \quad \xrightarrow{\text{see the front}} \quad \text{actually, yield matters more!} $$ .pull-left[ **1️⃣ Preferences form *a posteriori*** 🔄 - You only learn the true trade-off rate by *seeing* the options - A 2× weight looks right… until it costs 30% yield **2️⃣ Objectives are incommensurable** 🧮 - Can't meaningfully add 0.3 ns + 12 μm² + 4 mW - Any scalarization forces an artificial exchange rate ] .pull-right[ **3️⃣ Preferences are context-dependent** 🌍 - Mobile vs. server vs. automotive - Process maturity & product lifecycle **4️⃣ The fix: interactivity** 🤝 - Generate the front *first* - Let seeing trade-offs define the preference - **Show the front, then choose** 🎯 ] --- ### 🎛️ Generating Pareto Points **Sweep scalarizations to trace the front:** .font-sm[ | Method | Formula | Pros | Cons | |--------|---------|------|------| | Weighted sum | $\min \sum \alpha_i f_i$ | Simple, convex | Misses concave parts | | ε-constraint | $\min f_k \ \text{s.t.}\ f_i \leq \varepsilon_i$ | Hits concave parts | ε choice is tricky | | Ratio / quasi-convex | $\min f_1 / f_2$ | Natural for EDA | Requires quasi-convexity | ] $$ \varepsilon\text{-constraint:} \qquad \min_x f_k(x) \quad \text{s.t.} \quad f_i(x) \leq \varepsilon_i,\ i \neq k $$ **Each ε sweep gives one Pareto point** → repeat for a dense front 📊 --- ### 🧭 Trade-off Analysis in Practice **From Pareto front to a decision:** .mermaid[ <pre> graph LR S["🎯 Generate\nPareto front"] --> T["⚖️ Trade-off analysis\n(normalize objectives)"] T --> U["📊 Utilities / preferences\n(designer or user)"] U --> D["✅ Pick solution\n(human-in-the-loop)"] D --> E["📦 Sign-off\n(PPA + yield + test)"] style S fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style T fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style U fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px style D fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px style E fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] **EDA reality check:** in practice the front is computed *approximately* (placement, sizing, routing are NP-hard) → **heuristics + Pareto filtering** 🧠 --- class: nord-light, middle, center ## 💎 Part 6: Summary --- ### 🔑 Key Takeaways **1️⃣ Beyond PPA** — yield, robustness, DFT, DFM are real objectives that trade off against PPA 🏭 **2️⃣ Algorithms are multi-objective too** — energy & simplicity often beat raw speed on-chip 🔋 **3️⃣ Global placement** — wirelength, congestion, timing pull in opposite directions ⚔️ **4️⃣ Multi-to-single methods** — weighted sum (simple, misses concave) and ratio (quasi-convex, bisection) 🧮 **5️⃣ Pareto front** — show the trade-offs *first*, choose *later* 📊 **6️⃣ Practice** — scalarize, sweep, filter: **the front is the map, the designer is the navigator** 🧭 --- ### 🎯 The Core Message **Multi-objective optimization is not about one "best" answer — it is about *understanding the trade-off space*.** $$ \underbrace{f(x) = \big(f_1(x),\, f_2(x),\, \ldots,\, f_m(x)\big)}_{\text{objective vector}} \quad \xrightarrow{\text{Pareto}} \quad \text{front of nondominated solutions} $$ .mermaid[ <pre> graph LR M["🧩 Many objectives"] --> P["🏆 Pareto front"] P --> W["⚖️ Weighted sum / ratio\n(scalarization)"] W --> D["✅ One decision"] style M fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style P fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style W fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style D fill:#ffe0b2,stroke:#e65100,color:#2e3440,stroke-width:3px </pre> ] **Weakest link in your trade-off analysis determines design quality** — invest in all of it. --- ### 📖 Related Slides in `cvx/` .pull-left[ **Convex & Quasi-convex:** - [Introduction to Convex Optimization](cvxprog-remark.html) 🎯 - [Quasi-convex Programming](quasicvx-remark.html) 🧮 - [Convexify the Non-convex's](convexify-remark.html) 🔄 - [Geometric Programming](geomprog-remark.html) 📐 **Methods:** - [Alternating Minimization](alternating-remark.html) 🔁 - [LMI & Semidefinite Programming](lmi.html) 🧩 ] .pull-right[ **Ellipsoid & Oracles:** - [Ellipsoid Method Revisited](ellipsoid.html) 🥚 - [Cutting-plane Method](cutting_plane.html) ✂️ - [The ellalgo Package](ellalgo-remark.html) 🐍 **Applications:** - [Multiplierless FIR Design](fir.html) 🎛️ - [Convex PWL Fitting](cvx_pwl_fit.html) 📈 ] --- count: false class: nord-dark, middle, center # 🙋 Q&A ### Questions? Discussion? --- count: false class: nord-dark, middle, center # 👏 Thank You ### Multi-Objective Optimization in EDA @luk036 👨‍💻 · 2026 📅 **Slides built with Remark.js 🎉 | KaTeX | Mermaid | Nord Theme** Core idea: **Show the Pareto front first — then choose.** 🎯 **Links:** - Slides: `luk036.github.io/cvx/multi-obj-optim-remark.html` - Notes: `idea/optimization.md` - Code: `github.com/luk036/luk036.github.io`