High level techniques for power-grid noise immunity

Azadeh Davoodi, Vishal Khandelwal, Ankur SrivastavaACM Great Lakes Symposium on VLSI 2004 · DOI

TL;DR

This paper introduces NIVA, a novel high-level synthesis technique that schedules operations in Data Flow Graphs (DFGs) to maximize noise immunity against voltage fluctuations in power grids. By intelligently assigning voltages and allowable voltage variations, NIVA aims to ensure designs remain functional and meet timing/power constraints even with noisy power supplies, a critical challenge in modern integrated circuits.

What Problem Does This Paper Address?

Modern integrated circuits, especially those using deep sub-micron technology, are increasingly susceptible to noise in the power supply network (Vdd-Ground). These fluctuations, caused by various factors like cross-coupling and heavy sub-system switching, can lead to unpredictable voltage drops or spikes. This noise directly impacts the reliability and quality of the design, potentially causing timing violations or functional errors. While existing research often tackles this problem at lower levels of abstraction with limited design flexibility, this paper addresses the challenge at a high level of abstraction, specifically within the context of Data Flow Graphs (DFGs), aiming to build noise immunity into the design process from the start.

Methods

The core of the paper is the Noise Immune Voltage Assignment (NIVA) algorithm. NIVA is a dynamic programming-based approach that modifies the traditional voltage scheduling problem. Instead of just minimizing power under timing constraints, NIVA aims to maximize noise immunity, defined as the maximum allowable voltage fluctuation an operation can tolerate while still meeting timing and power constraints.

Key aspects of NIVA include:

  • Voltage Scheduling with Noise Immunity: The algorithm assigns a voltage and a noise immunity factor ($d_i$) to each operation. This $d_i$ represents the maximum fluctuation the operation can handle.
  • Grid-Based Approach: To make the problem tractable, NIVA discretizes the voltage axis by imposing a grid. This allows for a pseudo-polynomial dynamic programming solution.
  • Forward and Backward Passes: The algorithm traverses the DFG in a topological order. The forward pass computes intermediate results (C, F, FMAX arrays) that capture timing, power, and noise immunity combinations for subtrees. The backward pass then uses these results to determine the optimal voltage assignments and noise immunity factors for the entire DFG.
  • Handling DAGs: For Directed Acyclic Graphs (DAGs) with multiple fanouts, NIVA employs a heuristic to manage potential power overestimation and conflicting voltage assignments.
  • Incorporation of Binding: The paper also discusses how resource binding information can be integrated before voltage scheduling. This allows for more accurate estimation of switched capacitance and better control over resource usage, further enhancing the noise immunity optimization.

Datasets

The paper evaluates NIVA on twelve benchmarks, described as a mix of "Media-Bench benchmark suite [2] and traditional High Level Synthesis benchmarks." Specific benchmark names include motion-2, motion-3, noisest2, fir, jdmergel, jdmerge3, jdmerge4, dct, jctrans2, fft2, ellipt, and ecbenc4. No new benchmarks were introduced.

Key Insights and Ideas

  • Shifting the Optimization Goal: The fundamental insight is to reframe voltage scheduling not just for power reduction but for maximizing resilience to power grid noise. This proactive approach is crucial for modern ICs.
  • Noise Immunity as a First-Class Constraint: By defining and optimizing for "noise immunity" ($d_i$), the paper provides a quantifiable metric that directly addresses the impact of voltage fluctuations.
  • Grid Discretization for Tractability: The clever use of a voltage grid transforms a potentially intractable continuous optimization problem into a manageable discrete one, enabling dynamic programming.
  • Pre-Binding for Enhanced Accuracy: Integrating binding information before voltage scheduling leads to more accurate power estimations and better overall noise immunity, highlighting the interconnectedness of these HLS steps.
  • Trade-offs are Quantifiable: The results clearly show that relaxing timing or power constraints allows for greater noise immunity, providing designers with valuable insights into these trade-offs.

Key Results

  • NIVA effectively generates significant noise immunity for all operations across various benchmarks.
  • The actual power consumption of the generated designs was consistently below the specified power constraint.
  • Experimental results demonstrated that as timing constraints are relaxed, total noise immunity increases. Similarly, increasing the power constraint also leads to higher noise immunity.
  • When binding was performed before scheduling, the observed trends in noise immunity variation with respect to timing and power constraints remained similar, reinforcing the robustness of the approach.

Limitations and Future Work

  • Grid Assumption: The NIVA algorithm is optimal for tree-like DFGs under the grid assumption. While a heuristic is provided for DAGs, it might not be globally optimal. The quality of the solution depends on the granularity of the voltage grid (DVSTEP), with finer grids yielding better results but increasing runtime.
  • Continuous Domain Optimization: The paper suggests exploring the formulation of the noise optimization problem in the continuous domain.
  • Inter-Operation Noise Variation: Future work could involve developing algorithms that optimize the variation of noise immunity between different operations.
  • Integration with Layout Tools: The authors propose using the noise budgets generated by NIVA in placement or routing tools to generate valid, noise-immune designs.

Summary updated

BibTeX
@inproceedings{davoodi2004high,
  author = {Azadeh Davoodi and Vishal Khandelwal and Ankur Srivastava},
  title = {{High level techniques for power-grid noise immunity}},
  booktitle = {ACM Great Lakes Symposium on VLSI},
  year = {2004},
  doi = {10.1145/988952.988957},
}
Figure