Algorithms for Design-for-Manufacturability

---

# Algorithms for Design-for-Manufacturability

### A 30-Minute Introduction

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part I: Foundations** 🧠
- Course Overview & DFM Intro
- Software Development
- Statistics & Correlation
- Convex Optimization

**Part II: Core Algorithms** 🔄
- Ellipsoid & Cutting-plane Methods
- Clock Skew Scheduling
- Network Flow & Useful Skew
- Complexity Theory

]
.pull-right[

**Part III: Advanced Topics** 🔬
- Phase Shifting Mask (PSM)
- Layout Decomposition
- 1D Layout Design

**Research Highlights** 🏆
- Multi-Corner Delay Padding
- PSM Layout Co-optimization
- Spatial Correlation Estimation

]

---

## Part I: Foundations 🧠

---

### 📚 Course Overview

This course explores **algorithmic approaches** to Design-for-Manufacturability (DFM) in VLSI chips — the bridge between what designers draw and what fabs can reliably produce.

**Three Modules:**

.pull-left[
**Foundations (Lec 0-4):**
- DFM motivation & challenges
- Modern C++ / EDA software dev
- Statistics & spatial correlation
- Convex optimization theory
]
.pull-right[
**Core Algorithms (Lec 5-9):**
- Ellipsoid & cutting-plane methods
- Clock skew scheduling (yield-driven)
- Network flow optimization
- Complexity theory & NP-completeness

**Advanced (Lec 10-12):**
- Phase shifting mask algorithms
- Layout decomposition
- 1D layout design
]

---

### 🏭 What is DFM?

**Design for Manufacturability** optimizes IC layouts to improve fabrication yield, performance, and reliability at advanced technology nodes.

.pull-left[
**Three Pillars:**
- 🎯 **Functional Yield** — fewer defects
- 📊 **Parametric Yield** — meets spec across PVT
- 🔒 **Reliability** — long-term operation
]
.pull-right[
**Key Challenges:**
- Sub-10nm process variations
- 193nm lithography resolution limits
- 2000+ design rules at 14nm
- CMP dishing & erosion
- Via reliability & electromigration
]

---

### ⚠️ Lithography Challenges

Current lithography uses **193nm ArF excimer lasers** to create features far smaller than the wavelength.

.pull-left[
**Problems:**
- Resolution limits → blurred features
- Diffraction & interference effects
- Optical proximity errors
- Pattern-dependent distortions
]
.pull-right[
**Solutions:**
- **OPC** — pre-compensate mask shapes
- **Double/Multiple Patterning** — split dense layers
- **Phase Shifting Masks** — interference-based resolution
- **EUV** — 13.5nm next-gen (power challenges remain)
]

---

### 🔬 Process Variations & Defects

.mermaid[
<pre>
graph LR
    subgraph "Systematic"
        S1["Layout-dependent"]
        S2["OPC limitations"]
        S3["CMP topography"]
    end
    subgraph "Random"
        R1["Particle defects"]
        R2["Opens / Shorts"]
        R3["Threshold fluctuations"]
    end
    subgraph "Parametric"
        P1["$L_{eff}$ variations"]
        P2["$V_{th}$ mismatch"]
        P3["Oxide thickness"]
    end
    style S1 fill:#f44336
    style S2 fill:#f44336
    style S3 fill:#f44336
    style R1 fill:#ff9800
    style R2 fill:#ff9800
    style R3 fill:#ff9800
    style P1 fill:#2196f3
    style P2 fill:#2196f3
    style P3 fill:#2196f3
</pre>
]

**Three defect types** → different algorithmic approaches needed

---

### 🛠️ DFM Approaches Overview

.mermaid[
<pre>
graph LR
    subgraph "Challenges"
        C1["Process Variations"]
        C2["Lithography Limits"]
        C3["Design Rule Complexity"]
    end
    subgraph "DFM Approaches"
        A1["Litho-Friendly Design"]
        A2["CMP-Aware Fill"]
        A3["OPC / PSM"]
        A4["Statistical Timing"]
        A5["Via Optimization"]
    end
    C1 --> A4
    C2 --> A1
    C2 --> A3
    C3 --> A2
    C3 --> A5
    style C1 fill:#f44336
    style C2 fill:#f44336
    style C3 fill:#f44336
    style A1 fill:#4caf50
    style A2 fill:#4caf50
    style A3 fill:#4caf50
    style A4 fill:#4caf50
    style A5 fill:#4caf50
</pre>
]

Each challenge maps to specific DFM techniques — many are NP-hard optimization problems at their core.

---

### 💻 Software Development for EDA

Why software engineering matters for DFM algorithm research:

.pull-left[
**Tools & Practices:**
- Modern C++17/20 (concepts, ranges)
- Python prototyping (CVXPY, networkx)
- Git / CI workflows
- Doxygen + KaTeX documentation
- AI-assisted code validation
]
.pull-right[
**Key Packages:**
- `ellalgo` — Ellipsoid/cutting-plane
- `digraphx` — Graph algorithms
- `ckpttnpy` — Hypergraph partitioning
- `physdes` — Geometry toolkit
- `netlistx` — Netlist algorithms
- `csdigit` — Canonical signed digit
]

---

### 📊 Statistics & Spatial Correlation

Process variations are **spatially correlated** — nearby devices have similar parameters.

**Key concepts:**

$$ \rho(d) = \text{correlation between devices at distance } d $$

.pull-left[
**Variation Components:**
- Die-to-die (global)
- Within-die (systematic + random)
- Spatially correlated residual
]
.pull-right[
**Estimation Methods:**
- Parametric (Gaussian model)
- Non-parametric (empirical variogram)
- Grid-based extraction
- Application: statistical timing analysis
]

---

### 📐 Convex Optimization in DFM

Many DFM problems can be formulated as **convex optimization**:

$$ \begin{aligned}
\text{minimize} \quad & f_0(x) \\
\text{subject to} \quad & f_i(x) \le 0, \quad i = 1,\dots,m
\end{aligned} $$

.pull-left[
**Common Formulations:**
- Linear Programming (LP)
- Geometric Programming (GP)
- Semi-definite Programming (SDP)
- Quasi-convex (bisection method)
]
.pull-right[
**DFM Applications:**
- Clock skew scheduling
- Robust circuit sizing
- Delay padding optimization
- Statistical optimization
- Yield maximization
]

---

## Part II: Core Algorithms 🔄

---

### 🧮 Algorithmic Toolbox

The course covers a progression of algorithmic paradigms:

.mermaid[
<pre>
graph LR
    subgraph "Convex Optimization"
        E["Ellipsoid Method"]
        C["Cutting-plane"]
    end
    subgraph "Graph Algorithms"
        N["Network Flow"]
        S["Shortest Path"]
        M["Mean Cycle"]
    end
    subgraph "Complexity"
        P["P vs NP"]
        A["Approximation"]
    end
    E --> C
    C --> N
    N --> S
    S --> M
    style E fill:#4caf50
    style C fill:#4caf50
    style N fill:#2196f3
    style S fill:#2196f3
    style M fill:#2196f3
    style P fill:#ff9800
    style A fill:#ff9800
</pre>
]

From exact convex methods to combinatorial optimization and complexity classification.

---

### 📦 Ellipsoid Method

The ellipsoid method is a **polynomial-time** algorithm for convex optimization:

$$ x_{k+1} = x_k - \frac{1}{n+1} \cdot \frac{A_k g_k}{\sqrt{g_k^T A_k g_k}} $$

.pull-left[
**Key Properties:**
- Polynomial convergence
- Works with separation oracles
- Handles non-differentiable objectives
- Deep cuts, central cuts, parallel cuts
]
.pull-right[
**DFM Applications:**
- Robust circuit sizing
- Geometric programming (posynomials)
- Linear Matrix Inequalities (LMI)
- Convex piecewise-linear fitting
- Package: `ellalgo` (Python)
]

---

### ✂️ Cutting-plane Method

Refinement of ellipsoid — iteratively refines feasible region with cutting planes:

.mermaid[
<pre>
graph LR
    A["Initial box"] --> B["Query oracle"]
    B --> C{"Feasible?"}
    C -->|No| D["Add cutting plane"]
    D --> E["Shrink feasible set"]
    E --> B
    C -->|Yes| F["Query objective"]
    F --> G{"Optimal?"}
    G -->|No| H["Add optimality cut"]
    H --> E
    G -->|Yes| I["✓ Solution found"]
</pre>
]

**Key insight:** Oracles encode problem structure — separation oracle for feasibility, subgradient for optimality.

---

### ⏰ Clock Skew Scheduling

Clock skew $T_\text{skew}(i,j) = t[i] - t[j]$ can be **intentionally tuned** for better performance.

$$ T_\text{skew}(i,j) = t[i] - t[j] $$

.pull-left[
**Timing Constraints:**
- **Setup:** $t[i] - t[j] \le P - D[i,j] - T_\text{setup}$
- **Hold:** $t[i] - t[j] \ge T_\text{hold} - d[i,j]$

Where $D[i,j]$ = max delay, $d[i,j]$ = min delay
]
.pull-right[
**Key Insight:**
- Zero skew: all $t[i]$ equal (traditional)
- **Useful skew**: intentionally non-zero
- Trade-off: setup margin ↔ hold margin
- Formulated as **system of difference constraints**
]

---

### 📈 Yield-Driven Clock Skew

Under process variations, delays are **statistical** — not fixed values:

.pull-left[
**Traditional vs Statistical:**
- **Deterministic**: fix worst-case corner
- **Statistical**: model variations as distributions
- **Yield-driven**: maximize # chips meeting target

**Methods:**
- EVEN: uniform slack distribution
- PROP: propagate slacks
- C-PROP: correlation-aware
]
.pull-right[
**Algorithms Used:**
- Bellman-Ford (negative cycle detection)
- Karp's algorithm (minimum mean cycle)
- Lawler's algorithm (binary search)
- Howard's algorithm (policy iteration)
- Parametric shortest paths
]

---

### 🌐 Network Flow & Useful Skew

**Useful skew scheduling** as minimum cost-to-time ratio cycle problem:

$$ \text{Minimize} \quad \frac{\text{cost}}{\text{time}} $$

.pull-left[
**Graph Formulation:**
- Nodes = flip-flops
- Edges = timing constraints
- Edge weights: delay bounds
- Find: feasible skew assignment

**Algorithms:**
- Bellman-Ford for negative cycle detection
- Karp's min mean cycle
- Howard's policy iteration
]
.pull-right[
**Advanced Topics:**
- Multi-corner optimization
- Delay padding integration
- Dual decomposition for corner coupling
- RVI (Redundant Via Insertion)
- Network flow + convex opt hybrids
]

---

### 🎯 Complexity Theory in EDA

Many DFM optimization problems are **NP-hard**:

.pull-left[
**NP-complete in EDA:**
- Vertex Cover → via redundancy
- Steiner Tree → global routing
- TSP → scan chain ordering
- MAX-CUT → phase assignment
- Graph Coloring → layout decomposition
]
.pull-right[
**Approach:**
1. Prove NP-hardness (reduction)
2. Identify approximation classes:
   - PTAS, FPTAS, APX
3. Design algorithm:
   - Greedy, LP-rounding, primal-dual
   - Randomized, local search, DP
   - Fixed-parameter tractable
]

---

### ⚖️ Algorithm Design Techniques

.pull-left[
**Exact Methods:**
- Linear Programming + Rounding
- Dynamic Programming
- Branch & Bound
- Integer Programming

**Approximation:**
- Greedy (MST, Knapsack)
- Primal-dual methods
- LP-rounding ( randomized rounding)
- Local search & Simulated annealing
]
.pull-right[
**Paradigm Examples:**
- Hadlock's algorithm — planar MAX-CUT via perfect matching
- Christofides — TSP 3/2-approximation
- Primal-dual for covering problems
- Parametric shortest paths
- Discrete Exterior Calculus (DEC)

**Key message:** Choose the right tool for the problem class.
]

---

## Part III: Advanced Topics 🔬

---

### 🎭 Phase Shifting Mask (PSM)

PSM uses **destructive interference** to improve lithographic resolution:

.pull-left[
**Phase Assignment Problem:**
- Features assigned 0° or 180° phase
- Adjacent features ⟹ different phases
- Phase conflicts → layout hotposts
- Minimize conflicts = **MAX-CUT on planar graph**

**Algorithms:**
- Greedy (max spanning tree)
- Hadlock's algorithm (dual graph + minimum perfect matching)
- MAX-CUT reformulation
]
.pull-right[
.mermaid[
<pre>
graph LR
    subgraph "Phase Conflict Graph"
        N1((F1)) --- N2((F2))
        N2 --- N3((F3))
        N3 --- N4((F4))
        N4 --- N1
    end
    subgraph "Assignment (2-color)"
        C1[0°] --- C2[180°]
        C2 --- C3[0°]
        C3 --- C4[180°]
        C4 --- C1
    end
</pre>
]
]

---

### 🧩 Layout Decomposition

For **Multiple Patterning Lithography (MPL)**, layouts must be split across masks:

.pull-left[
**Problem:**
- Decompose single layer into $k$ masks
- Minimum spacing rule between same-mask features
- Equivalent to **graph $k$-coloring**
- Minimize stitches (feature cuts)

**Algorithms:**
- Integer Linear Programming
- Network flow based redistribution
- Pairwise coloring co-optimization
]
.pull-right[
**Challenges:**
- np-hard for $k \ge 3$
- Stitch minimization
- Overlay error management
- Native conflict detection
- Coloring balance across masks

**Applications:** LELE, LELELE, SAQP
]

---

### 📐 1D Layout Design

Unidirectional (1D) layouts simplify manufacturing at advanced nodes:

.pull-left[
**Advantages:**
- Lithography-friendly
- Reduced process variation
- Simpler OPC/MRC
- Better CD control

**Algorithms:**
- Network flow for track assignment
- Convex optimization for spacing
- Grid-based routing
]
.pull-right[
**1D Design Flow:**
- All wires on preferred direction
- Fixed pitch / tracks
- Via access at track intersections
- Optimization objectives:
  - Minimum area
  - Maximum density
  - Via minimization
]

---

## Research Highlights 🏆

---

### 🛡️ Multi-Corner Delay Padding

**Novel methodology** using Path Relationship Analysis + Dual Decomposition:

.pull-left[
**Challenge:**
- Timing violations across multiple PVT corners
- Single-corner fix creates "ping-pong" effects
- Physical feasibility of padding locations

**Solution:**
1. **PRA**: Identify viable padding locations _first_
2. **Dual decomposition**: Couple corner sub-problems via Lagrange multipliers
3. **Result**: Up to **6% clock period reduction**
]
.pull-right[
**Key Equation:**
$$ \begin{aligned}
\min \quad & P \\\\
\text{s.t.} \quad & t[i] - t[j] \le P - D[i,j]^c - S^c \\\\
  & t[i] - t[j] \ge H^c - d[i,j]^c \\\\
  & \forall c \in \text{Corners}
\end{aligned} $$

Zhu K, et al. _ASP-DAC'26_ (accepted)
]

---

### 🎨 PSM & Layout Co-optimization

.pull-left[
**Cut Redistribution (Best Paper Nominee):**
- Network flow based approach
- Redistribute cuts efficiently
- Minimize phase conflicts

**Layout Decomposition Co-optimization:**
- Simultaneous coloring + stitch minimization
- Pairwise coloring formulation
- Best Paper Nominee
]
.pull-right[
**Spatial Correlation Estimation:**
- Non-parametric variogram estimation
- Grid-based correlation extraction
- Application in statistical timing

**Yield-driven CSS:**
- Multi-parameter clock skew scheduling
- Timing yield driven optimization
- DAC 2008 & ASP-DAC'25 publications
]

---

### 🎯 Course Learning Objectives

By the end of this course, you will be able to:

1. **Analyze computational complexity** of EDA problems 🧠
2. **Apply appropriate algorithmic paradigms** to different problem types ⚙️
3. **Implement clock skew scheduling** for yield optimization ⏱️
4. **Solve phase assignment** for lithography-friendly designs 🎭
5. **Use convex optimization** for VLSI design automation 📐
6. **Understand the software engineering** behind EDA tools 💻

---

### 📖 Recommended Reading

.pull-left[
**Textbooks:**
- Orshansky M, et al. _Design for Manufacturability and Statistical Design_, Springer, 2008
- Balasinski A. _Design for Manufacturability_, Springer, 2014
- Yu B, et al. _DfM with Advanced Lithography_, Springer, 2016
- Ausiello G, et al. _Complexity and Approximation_, Springer, 1999
- Sherwani N. _Algorithms for VLSI Physical Design Automation_, 3rd ed, KAP, 2004
]
.pull-right[
**Key Papers:**
- Tsai et al. "Yield-Driven, False-Path-Aware Clock Skew Scheduling", IEEE D&T, 2005
- Hadlock. "A Finding of the Minimum Set of Missing Edges in a Bipartite Graph", 1975
- Zhu et al. "Novel Multi-Corner Delay Padding", ASP-DAC'26
- Zhu et al. "Yield-driven Clock Skew Scheduling", ASP-DAC'25
]

---

### 🛠️ Software Tools Used

.pull-left[
**Python Ecosystem:**
- **CVXPY** — Convex optimization
- **digraphx** — Graph algorithms (NCF, MCR, parametric SP)
- **ellalgo** — Ellipsoid & cutting-plane methods
- **physdes** — Geometric operations, DME, Steiner routing
- **netlistx** — Covering, matching, independent set
- **csdigit** — Canonical signed digit
]
.pull-right[
**Algorithm Implementations:**
- Bellman-Ford — negative cycle detection
- Karp's algorithm — minimum mean cycle
- Howard's algorithm — policy iteration
- Lawler's algorithm — binary search for min cycle ratio
- Hadlock's algorithm — planar MAX-CUT
- Christofides — TSP 3/2-approximation
]

---

### 📊 Course Structure 🗺️

.mermaid[
<pre>
graph TD
    subgraph "Foundations"
        F1["Lec 0: Overview"]
        F2["Lec 1: DFM Intro"]
        F3["Lec 2: Software Dev"]
        F4["Lec 3: Statistics"]
        F5["Lec 4: Convex Opt"]
    end
    subgraph "Core Algorithms"
        C1["Lec 5: Ellipsoid"]
        C2["Lec 6: Cutting-plane"]
        C3["Lec 7: Clock Skew"]
        C4["Lec 8: Network Flow"]
        C5["Lec 9: Complexity"]
    end
    subgraph "Advanced Topics"
        A1["Lec 10: PSM"]
        A2["Lec 11: Layout Decomp"]
        A3["Lec 12: 1D Layout"]
    end
    F5 --> C1
    C3 --> A1
    C4 --> A2
    style F5 fill:#4caf50
    style C1 fill:#2196f3
    style C3 fill:#ff9800
    style C4 fill:#ff9800
    style A1 fill:#9c27b0
    style A2 fill:#9c27b0
</pre>
]

---

# 🙋 Q&A

### Questions? Discussion?

**Course Page:** [luk036.github.io/algo4dfm/](https://luk036.github.io/algo4dfm/)

---

# 👏 Thank You

### Algorithms for Design-for-Manufacturability

**Course Topics:**
- DFM foundations & lithography challenges
- Convex optimization (ellipsoid, cutting-plane)
- Clock skew scheduling under process variations
- Network flow & useful skew optimization
- Phase shifting mask & layout decomposition
- Complexity theory & approximation algorithms

Slides built with Remark.js 🎉 | KaTeX | Mermaid | Nord Theme