Behavior-Level Observability Analysis for Operation Gating in Low-Power Behavioral Synthesis

Jason Cong, Bin Liu, Rupak Majumdar, Zhiru ZhangACM Trans. Design Autom. Electr. Syst 2010 · DOI

TL;DR

This paper introduces a novel approach to optimize power consumption in hardware designs by analyzing "observability" at a high behavioral level, rather than just at the gate level. By identifying operations that are not observable at runtime, the authors enable more effective power-saving techniques like operation gating during the behavioral synthesis phase, leading to significant power reductions.

What Problem Does This Paper Address?

Reducing power consumption in integrated circuits is a critical challenge. While techniques like clock gating and operand isolation are common, their effectiveness is often limited by the low-level view of the hardware. These methods rely on "Observability Don't-Care" (ODC) conditions, which indicate when a signal's value doesn't affect the final output and can therefore be ignored. However, traditional ODC analysis typically operates at the gate level, missing opportunities for optimization that exist at higher levels of abstraction, such as during behavioral synthesis where the overall structure of the design is being determined. This paper addresses the gap by developing a method to compute ODC conditions at the behavioral level, allowing for more aggressive power optimizations by influencing the design's structure and scheduling before it's translated into RTL.

Methods

The core of this paper is the development of a behavior-level observability analysis framework. Key techniques include:

  • Operation Gating: This is the primary power optimization technique enabled by the analysis. It involves adding a predicate to an operation, so that if the operation's result is unobservable, the operation itself can be skipped, saving power.
  • Dataflow Graph Abstraction: To handle complex operations (like arithmetic) efficiently at the word level, these are modeled as "black boxes." This abstraction allows for analysis without needing to delve into the bit-level details of every operation.
  • Generalized Select Operation: The standard "select" operation (multiplexer) is generalized to handle multiple control and data inputs, making it more representative of complex control flows in behavioral descriptions.
  • Smoothed Behavior-Level Observability (SBLO): This is a key metric computed by the algorithm. It represents the observability condition under the black-box abstraction, providing a conservative yet useful estimate of when an operation's output is unobservable. The algorithm propagates and manipulates SBLO values through the dataflow graph.
  • Algorithm for SBLO Computation: An algorithm is presented that traverses the dataflow graph in reverse topological order, propagating and merging observability conditions through black boxes and generalized select operations.
  • Behavioral Synthesis Flow: The computed behavior-level observability is integrated into a behavioral synthesis flow to guide the scheduler, optimizing for operation gating.

Datasets

The paper evaluates its approach on several real-world designs from arithmetic and multimedia applications. These include:

  • addr (address space translation unit)
  • BoxMuller (Gaussian noise generator)
  • dfmul (floating-point multiplier)
  • MotionComp (motion compensation for MPEG4 decoder)
  • MotionEst (motion estimation for MPEG4 encoder)

These benchmarks are characterized by their number of nodes (operations) in the Control/Data Flow Graph (CDFG). No new benchmarks were introduced.

Key Insights and Ideas

  • Observability at the Behavioral Level is Crucial: The most significant insight is that optimizing for power based on observability is far more effective when done at the behavioral synthesis stage, rather than as a post-processing step on an already scheduled RTL design. This allows for structural changes and better scheduling decisions.
  • Black-Box Abstraction is Effective: Modeling complex arithmetic operations as black boxes is a practical approach to enable word-level observability analysis without becoming computationally intractable. It provides a good balance between accuracy and efficiency.
  • Generalized Select Operation Captures Masking: The generalized select operation is key to capturing how control signals can mask the observability of data paths, a crucial aspect for accurate ODC analysis.
  • Operation Gating as a Scheduling-Guided Technique: The paper demonstrates that operation gating, when guided by behavior-level observability analysis during scheduling, can achieve substantial power savings.
  • Approximation vs. Exactness: While the exact computation of ODC conditions can be prohibitively expensive, the proposed SBLO analysis provides a strong, yet scalable, approximation.

Key Results

The proposed method, integrated into a behavioral synthesis flow, achieved significant power reductions:

  • Average Power Reduction: An average of 33.9% reduction in total power was observed across the experimental designs.
  • Comparison to Prior Work: The method outperformed a previous approach (Chen and Sarrafzadeh [2002]) by an average of 17.1% in power reduction.
  • Scalability: The approach is highly scalable, with experiments finishing within 60 seconds, whereas an exact Integer-Linear Programming (ILP) formulation for optimality study failed to find solutions within 7200 seconds for larger designs.
  • Area Overhead: The approach resulted in minimal area overhead.

Limitations and Future Work

  • Approximation of Binary Penalty: While the approach is very close to optimal, it uses an approximation for binary penalty functions in its optimization formulation. The observed optimality gap is about 1%.
  • Knowledge of Boolean Relations: The paper mentions that while the SBLO is a good approximation, incorporating more specific knowledge about correlations between Boolean values (e.g., "if x == 3, then x < 10") could further strengthen the observability conditions. This is suggested as future work.
  • Compiler Optimization Integration: The authors suggest that their observability analysis could be beneficial for compiler optimizations beyond power management, such as control-flow restructuring.
  • Further Power Savings: The paper notes that additional power savings could be achieved by applying other low-power techniques (e.g., operand isolation, feeding sleep vectors) in conjunction with operation gating.

Summary updated

BibTeX
@article{cong2010behavior,
  author = {Jason Cong and Bin Liu and Rupak Majumdar and Zhiru Zhang},
  title = {{Behavior-Level Observability Analysis for Operation Gating in Low-Power Behavioral Synthesis}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2010},
  doi = {10.1145/1870109.1870113},
}
Figure