A Linear-Time Algorithm for Steady-State Analysis of Electromigration in General Interconnects

The Problem: The "Crowded Highway" Effect

Imagine a copper wire inside a computer chip as a highway for tiny cars called electrons. When a lot of traffic (high current) flows down this highway for a long time, the electrons don't just drive past; they bump into the metal atoms that make up the road itself.

Over time, these bumps push the metal atoms along the road, like a crowd of people shoving their way through a hallway.

The Danger: At one end of the wire (the "cathode"), the metal atoms get pushed out, leaving a hole (a void). If the hole gets big enough, the wire breaks, and the computer stops working. This is called Electromigration (EM).
The Goal: We need to know which wires are safe ("immortal") and which ones will eventually break ("mortal") before we even build the chip.

The Old Way: The "One-Lane Road" Rule

For years, engineers used a rule called the Blech Criterion to check for safety.

The Analogy: Imagine checking if a single-lane road is safe by looking at just one stretch of it. The rule says: "If the traffic speed (current) multiplied by the length of the road is below a certain number, the road is safe forever."
The Flaw: Real computer chips aren't just single-lane roads. They are complex interconnected networks (like a city grid with highways, exits, and merging lanes).
The Result: The old rule was like trying to predict traffic jams in a whole city by only looking at one single block. It often got things wrong. It would sometimes say a dangerous wire was safe, or waste time checking a wire that was actually fine.

The New Solution: A "Linear-Time" Super-Scanner

The authors of this paper invented a new, super-fast way to check the safety of any wire network, no matter how complex (trees, meshes, or city grids).

They call their method "Linear-Time," which is a fancy way of saying: "The time it takes to check the wires grows at the exact same speed as the number of wires."

The Analogy: Imagine you have a stack of 100 letters to sort.
- Old Method: You have to read every letter, then read them again, then read them a third time to find the pattern. (Slow!)
- New Method: You have a magical scanner that reads every letter once and instantly sorts them. If you have 1,000 letters, it takes 10 times longer than 100 letters, but it's still incredibly fast.

How It Works: Two New Tricks

The paper offers two ways to do this fast check, both based on the same physics but using different "languages."

1. The "Current-Density" Method (The Walking Tour)

How it works: This method walks through the wire network like a tour guide. It starts at one end, calculates the stress (pressure) on the first wire, then moves to the next, and so on, adding up the "stress drops" as it goes.
The Analogy: It's like a hiker walking up a mountain, measuring the elevation change at every step to figure out the total height. It's accurate and fast, but it still requires walking the whole path.

2. The "Voltage-Based" Method (The Magic Map)

How it works: This is the paper's "secret weapon." The authors realized that the "stress" in a wire is mathematically identical to the "voltage drop" (the loss of electrical pressure) that engineers already calculate when designing chips.
The Analogy: Imagine you want to know how much water pressure is lost in a pipe system. Instead of walking the pipes and measuring friction (the old way), you just look at the water pressure gauge at the start and end of the system.
- Since chip designers already calculate these voltage numbers to make sure the chip works, this new method just reuses that existing data.
- The Result: It skips the "walking tour" entirely. It's like checking the map instead of hiking the trail. This makes it even faster than the first method.

Why This Matters

Speed: It can analyze massive, complex chip designs in seconds, whereas older physics-based methods could take hours or days.
Accuracy: It correctly identifies wires that the old "Blech rule" missed. It found that wires with low current can sometimes break faster than high-current wires if they are connected to the wrong neighbors (a counter-intuitive finding the old rules missed).
Efficiency: By using the "Voltage-Based" method, engineers can filter out the safe wires instantly. This leaves only the truly dangerous wires for further, more expensive testing.

The Bottom Line

This paper gives chip designers a super-fast, highly accurate calculator to predict which wires will break. It moves away from guessing based on simple rules and uses a clever mathematical shortcut (reusing voltage data) to solve a complex physics problem in the blink of an eye. It's like upgrading from a manual map to a GPS that instantly tells you the safest route.

1. Problem Statement

Electromigration (EM) is a critical reliability failure mechanism in deep-scaled integrated circuits, where high current densities cause metal atom transport, leading to void formation and open circuits.

Limitations of Current Methods: Traditional EM analysis relies on a two-stage process:
1. Filtering: Using the Blech criterion ( $jl \leq (jl)_{crit}$ ) to identify "immortal" wires. This criterion assumes a single-wire segment with blocking boundaries at both ends.
2. Analysis: Applying Black's equation to remaining wires.
The Gap: Modern interconnects are complex tree and mesh structures with multiple segments carrying different current densities. The Blech criterion is invalid for these structures because it ignores the interaction between segments (e.g., one segment acting as a reservoir for another).
Existing Physics-Based Solutions: While physics-based methods exist (solving partial differential equations), they are computationally expensive, often requiring numerical simulations (e.g., COMSOL) or transient analysis that scales poorly (quadratic or cubic time complexity) with circuit size.
Goal: Develop a computationally efficient, exact, linear-time algorithm to determine steady-state stress and test for immortality in general tree and mesh interconnect structures, replacing the inaccurate Blech criterion.

2. Methodology

The authors derive a solution based on first principles, solving the fundamental stress equations that relate electron wind forces and back-stress forces.

A. Theoretical Foundation

Steady-State Equations: In the steady state, the stress gradient along a wire segment is linear and proportional to the current density ( $j$ ). The stress difference between two nodes is $\Delta \sigma = -\beta j l$ , where $\beta$ is a material constant.
Mass Conservation: The total number of atoms in the interconnect remains constant. This implies that the integral of stress over the entire structure (weighted by cross-sectional area) must be zero.
Handling Meshes (Theorem 1): The authors prove that for any graph containing cycles (meshes), the steady-state stress equations are linearly dependent. Therefore, the solution for a mesh can be found by analyzing a spanning tree of the mesh. This reduces the general problem to a tree problem.

B. Proposed Algorithms

The paper proposes two equivalent methods, both with $O(|V| + |E|)$ linear time complexity (where $|V|$ is nodes and $|E|$ is edges):

Current-Density-Based Method (Traversal Required):
- Selects a reference leaf node.
- Performs a graph traversal (e.g., BFS) to calculate the "Blech sum" ( $BP_i$ ) for every node. The Blech sum is the algebraic sum of $j_k l_k$ along the path from the reference node.
- Uses the mass conservation principle to solve for the reference node's stress, then back-calculates stress for all other nodes.
Voltage-Based Method (Traversal-Free):
- Key Insight: The "Blech sum" ( $j l$ ) along a segment is directly proportional to the IR voltage drop across that segment ( $j l = \Delta V / \rho$ ).
- Since circuit simulators (like SPICE) already compute nodal voltages ( $V$ ) and currents, this method reuses existing simulation data.
- It calculates steady-state stress using nodal voltages and average segment voltages without performing any additional graph traversals.
- Formula: $\sigma_i = \frac{\beta}{\rho} \left[ \frac{\sum w_k h_k l_k V_{avg,k}}{\sum w_k h_k l_k} - V_i \right]$ .

3. Key Contributions

First Linear-Time Exact Solution: This is the first algorithm to provide an exact steady-state EM solution for general tree and mesh structures in linear time.
Generalization of Blech Criterion: The method mathematically generalizes the Blech criterion to multi-segment structures, proving that the traditional single-segment criterion is insufficient for complex nets.
Voltage-Based Formulation: The discovery that EM stress can be computed directly from nodal voltages (IR drops) eliminates the need for explicit graph traversals during the EM analysis phase, significantly reducing overhead.
Proof of Equivalence: The paper proves that the current-density approach and the voltage-based approach yield identical results.
Direct Proportionality: It establishes a direct proportionality between IR drop reduction and EM susceptibility reduction, suggesting that optimizing power grids for IR drop inherently aids EM reliability.

4. Experimental Results

The authors validated their methods against numerical simulations (COMSOL) and applied them to large-scale benchmarks.

Accuracy:
- Results matched COMSOL simulations exactly (with discrepancies only due to numerical discretization errors in COMSOL).
- The voltage-based and current-density-based methods produced identical stress values (mean error < 60 pPa).
Performance on IBM Power Grid Benchmarks:
- Speed: The voltage-based method was 1.5x to 1.9x faster than the current-density method.
- Scalability: The algorithm handled benchmarks with over 1.6 million edges (e.g., ibmpg6) in under 250 seconds.
- Blech Criterion Failure: The traditional Blech filter showed significant inaccuracy on multi-segment wires:
  - False Negatives: Labeling truly immortal wires as mortal (leading to over-design).
  - False Positives: Labeling mortal wires as immortal (leading to potential reliability failures).
Modern Technology Nodes:
- Tested on 12nm FinFET, 28nm FDSOI, and 45nm open-source nodes.
- The traditional Blech criterion produced numerous false positives in these modern meshes, confirming the necessity of the proposed method.
- The voltage-based approach was 1.7x to 2.7x faster than the traversal-based approach in these scenarios.

5. Significance

Design Flow Integration: This method can be seamlessly integrated into standard Electronic Design Automation (EDA) flows. Since it relies on voltages already computed by power grid analysis tools, it adds negligible overhead to the design cycle.
Reliability Assurance: By accurately identifying "immortal" wires in complex meshes, it prevents the over-optimization of wires that are actually safe and, more critically, prevents the under-design of wires that are actually at risk.
Unified Optimization: The voltage-based formulation allows EM constraints to be translated into IR drop constraints. This enables a unified optimization framework for power grids that simultaneously minimizes IR drop and ensures EM reliability.
Scalability: The linear-time complexity makes it feasible to analyze massive, modern on-chip interconnect networks that were previously too large for exact physics-based steady-state analysis.