Reliability-Driven Power/Ground Routing for Analog ICs

Jing-Wei Lin, Tsung-Yi Ho, Iris Hui-Ru JiangACM Trans. Design Autom. Electr. Syst 2012 · DOI

TL;DR

This paper introduces a novel automatic routing algorithm for analog integrated circuits that specifically addresses electromigration and IR-drop, two critical reliability issues. By employing a transportation formulation for global routing and a wire-bundling/sizing approach for detailed routing, the method achieves optimal solutions for electromigration avoidance with superior efficiency and effectively reduces IR-drop.

What Problem Does This Paper Address?

Modern integrated circuits (ICs) are constantly shrinking, leading to higher power densities and increased susceptibility to reliability issues. Two major concerns in analog IC design are electromigration and IR-drop. Electromigration, caused by excessive current densities, can lead to permanent circuit failures by creating open or short circuits. IR-drop, a voltage drop across power and ground (P/G) networks due to wire resistance, can degrade performance or cause functional errors, especially in low-voltage designs. While P/G routing in digital ICs is well-studied, analog P/G routing remains largely manual and inefficient, especially with increasing chip complexity. Existing methods for electromigration avoidance often struggle with efficiency or optimality, and few explicitly address IR-drop in conjunction with electromigration for analog P/G networks. This paper aims to fill this gap by proposing an automated P/G router that simultaneously considers both electromigration and IR-drop.

Methods

The proposed approach consists of two main stages: global routing for electromigration avoidance and detailed routing for IR-drop reduction.

  • Global Routing (Electromigration Avoidance):
    • Current-Driven Electromigration-Aware Rectilinear Steiner Tree (CDEARST): The core of this stage is formulating the problem as finding an optimal rectilinear Steiner tree that considers current flow and electromigration constraints.
  • Transportation Formulation: The CDEARST problem is transformed into a transportation problem. This allows for an optimal solution to be found efficiently.
  • Russell's Approximation Method: Used to find an initial basic feasible (BF) solution for the transportation problem.
  • Pivot Procedure: Refines the BF solution to achieve optimality.
  • Obstacle-Avoiding Wirelength Calculation: Utilizes an obstacle-avoiding spanning graph (OASG) and obstacle-avoiding shortest path (OASP) to accurately calculate wire lengths while avoiding module obstacles.
  • Detailed Routing (IR-Drop Reduction):
    • Wire Bundling: To improve routability and reduce congestion, wires of the same type (power or ground) are bundled. This also frees up space for potential wire width expansion.
  • Negotiation-Based Routing: A technique adapted from PathFinder is used for detailed routing, handling congestion and potential overlaps between power and ground nets.
  • Wire-Width Extension: If IR-drop exceeds the tolerant limit, wire widths are expanded to reduce resistance and thus voltage drop. This is done while considering available routing space and potential obstacles.

Datasets

The paper evaluates its algorithm on several benchmarks:

  • INP1-INP4, IND1-IND5, RT01-RT05: These are industrial benchmarks, with IND1-IND5 originating from Synopsys.
  • RPG1-RPG5: These are analog P/G routing examples.
  • RC01-RC12: These are additional benchmarks used for obstacle-avoiding routing results.

The paper notes that for the IND benchmarks, current information was not provided, so positive or negative current values were randomly assigned to terminals, ensuring the total sum followed Kirchhoff's current conservation law.

Key Insights and Ideas

  • Unified Approach for EM and IR-drop: The paper demonstrates that it's feasible and beneficial to address both electromigration and IR-drop simultaneously in analog P/G routing, rather than treating them as separate problems.
  • Transportation Problem for CDEARST: Transforming the electromigration-aware routing problem into a transportation problem is a key innovation that allows for efficient and optimal solutions, proving the problem belongs to Class P.
  • Wire Bundling for Congestion and IR-drop: Bundling wires not only helps alleviate congestion but also creates opportunities to expand wire widths, which is crucial for reducing IR-drop.
  • Wire-Width Extension as a Targeted IR-drop Solution: The adaptive wire-sizing approach effectively tackles IR-drop by increasing wire width only where necessary, balancing reliability with routing cost.

Key Results

  • Optimal Electromigration Avoidance: The proposed algorithm achieves equally optimal solutions for electromigration avoidance compared to existing methods.
  • Superior Efficiency: The algorithm demonstrates superior efficiency, often requiring fewer iterations and less runtime than previous approaches, particularly when compared to Jiang et al. [2010].
  • Effective IR-drop Reduction: Experimental results show that the wire-width extension method effectively reduces IR-drop to meet specified tolerances.
  • Reduced Wire Area: While prioritizing reliability, the algorithm also aims to minimize total wiring area. For example, in the RPG2 benchmark, the wire area was reduced from 2715 (CDEARST) to 5837 (Routing) after detailed routing and IR-drop reduction, which is a significant improvement over the initial CDEARST result.
  • Performance on Benchmarks: The algorithm was tested on various benchmarks, showing competitive or superior performance in terms of wire area and runtime compared to established methods. For instance, Table III shows that the proposed algorithm achieves comparable or better wire areas than previous methods across multiple benchmarks. Table IV indicates a significant reduction in iterations and runtime compared to Jiang et al. [2010].

Limitations and Future Work

  • Overlap Handling: While the paper mentions dealing with power and ground net overlaps in detailed routing, the figures (e.g., Figure 7(a) and 7(b)) show overlapping lines in intermediate stages, suggesting that complete avoidance might require careful negotiation and rip-up/reroute.
  • Infeasible IR-drop Thresholds: The paper acknowledges that in some cases, even with wire-width expansion and rerouting, it might be impossible to meet the IR-drop threshold, indicating a need for chip redesign.
  • Future Work: The paper implicitly suggests that further optimization of the wire-bundling and wire-sizing procedures could lead to even better results. The effectiveness of the approach on larger and more complex analog designs could also be a direction for future research.

Summary updated

BibTeX
@article{lin2012reliability,
  author = {Jing-Wei Lin and Tsung-Yi Ho and Iris Hui-Ru Jiang},
  title = {{Reliability-Driven Power/Ground Routing for Analog ICs}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2012},
  doi = {10.1145/2071356.2071362},
}
Figure