Combining Power and Arithmetic Optimization via Datapath Rewriting

Samuel Coward, Theo Drane, Emiliano Morini, George A. Constantinides

Abstract

Traditional Electronic Design Automation (EDA) tools often treat arithmetic optimization and power-saving techniques as independent tasks. This decoupling misses significant opportunities for cross-layer optimization where mathematical reordering can expose new avenues for power reduction. We present ROVER, an automated framework that leverages e-graphs to unify these domains. By representing power-saving techniques like clock gating and operand isolation as local rewrites, ROVER explores a vast design space of functionally equivalent circuits. Guided by workload-aware simulation and Integer Linear Programming (ILP), ROVER identifies architectures that optimize for Power, Performance, and Area (PPA) simultaneously. Experimental results on industrial and academic benchmarks demonstrate average power reductions of 23.6%, with peaks up to 33.9%, at a minimal area overhead.

Introduction

In digital logic design, the "Holy Trinity" of optimization is PPA: Power, Performance, and Area. While area and performance are relatively straightforward to estimate during the design phase, power consumption remains a moving target. It is heavily dependent on "switching activity"—the frequency at which bits flip from 0 to 1—which is determined by the specific data workloads the circuit processes.

Conventional EDA workflows handle arithmetic optimization (such as reordering adders) and power optimization (such as gating off unused components) as separate, sequential steps. This "siloed" approach is suboptimal; for instance, reordering a mathematical expression might create a new opportunity to shut down a redundant hardware block that was previously inaccessible. The challenge lies in exploring this combined search space without the prohibitive cost of manually redesigning circuits for every possible data workload.

The ROVER Framework

ROVER is an RTL-to-RTL (Register Transfer Level) optimization tool designed to bridge the gap between arithmetic and power optimization. Its core architecture relies on the e-graph (equivalence graph), a data structure capable of compactly storing millions of functionally equivalent versions of a single circuit.

Technical Components

  1. VeriLang and Local Rewrites: ROVER utilizes an intermediate language called VeriLang to represent hardware logic, including registers and enable signals. It applies a library of rewrite rules that encompass both standard algebraic identities (e.g., $x + x \to x \ll 1$) and power-specific transformations like Data Gating (masking inputs with AND gates) and Clock Gating (using transparent registers to freeze values).
  2. Workload-Aware Simulation: To account for the data-dependent nature of power, ROVER incorporates user-provided "input stimuli." It simulates the e-graph to identify which components exhibit the highest switching activity for a given workload. A key efficiency of this approach is that ROVER only needs to simulate one representative node per "e-class" (a group of equivalent expressions) to determine the switching activity for all versions within that class.
  3. ILP Extraction: Once the e-graph has been populated with equivalent circuit candidates, ROVER employs Integer Linear Programming (ILP) to extract the single most efficient circuit version based on a cost function focused on minimized power consumption.

Experimental Evaluation

The authors evaluated ROVER using a commercial TSMC 5nm library and industrial-grade synthesis tools from Synopsys and Cadence to ensure the results reflected real-world silicon performance. The benchmarks included:

  • Intel Production Snippets: Real-world logic including Combinational Mux Add Trees, Address Generation logic, and Weight Calculation blocks from graphics pipelines.
  • Academic Benchmarks: Standard designs such as Dual Path Floating Point Subtractors and Pipelined Mux Add Trees.

Key Insights and Results

Power and Area Trade-offs

ROVER achieved an average power reduction of 23.6% across the benchmark suite, with a maximum reduction of 33.9% on the "Sequential Reg" benchmark. Interestingly, these savings often required a modest increase in circuit area—averaging 5.0%. This indicates that ROVER successfully identifies scenarios where adding "gating" logic (which consumes area) prevents much larger arithmetic blocks from toggling unnecessarily, leading to a net energy gain.

Synergistic Optimization

One of the primary advantages of ROVER is its ability to exploit the synergy between math and power. By reordering an adder tree, ROVER can push high-activity signals toward the output. This reduces the number of gates those signals must pass through, lowering total power—a transformation that a power-only optimization tool would likely overlook. In the case of the "Pipelined Mux Add Tree," ROVER discovered a design that outperformed previously published manual optimizations, reducing power by 11% and area by 17% simultaneously.

Operational Efficiency

Despite the complexity of the search space, ROVER is highly efficient. Most benchmarks were processed in under 10 seconds. Even the most complex production snippets, which challenged the ILP solver, were completed within 160 seconds.

Limitations and Future Work

While ROVER represents a significant step forward, it has limitations. The internal power model is simplified and occasionally overestimates improvements (by up to 45%) because it uses linear relationships for toggle frequencies and does not fully capture complex downstream synthesis effects. Furthermore, some global optimizations, such as specific types of resource sharing, cannot yet be expressed as local rewrites.

Future development will focus on automatically deriving "case splits" from simulation data. This would allow the tool to recognize common data patterns and automatically generate specialized, low-power hardware paths for those specific scenarios.

Conclusion

ROVER demonstrates that unifying arithmetic and power optimization within an e-graph framework can yield substantial efficiency gains that traditional, decoupled EDA tools miss. By making power optimization an integral part of the architectural rewriting process, ROVER provides a path toward highly specialized, workload-aware hardware design.

Summary updated

Abstract

Industrial datapath designers consider dynamic power consumption to be a key metric. Arithmetic circuits contribute a major component of total chip power consumption and are therefore a common target for power optimization. While arithmetic circuit area and dynamic power consumption are often correlated, there is also a tradeoff to consider, as additional gates can be added to explicitly reduce arithmetic circuit activity and hence reduce power consumption. In this work, we consider two forms of power optimization and their interaction: circuit area reduction via arithmetic optimization, and the elimination of redundant computations using both data and clock gating. By encoding both these classes of optimization as local rewrites of expressions, our tool flow can simultaneously explore them, uncovering new opportunities for power saving through arithmetic rewrites using the e-graph data structure. Since power consumption is highly dependent upon the workload performed by the circuit, our tool flow facilitates a data dependent design paradigm, where an implementation is automatically tailored to particular contexts of data activity. We develop an automated RTL to RTL optimization framework, ROVER, that takes circuit input stimuli and generates power-efficient architectures. We evaluate the effectiveness on both open-source arithmetic benchmarks and benchmarks derived from Intel production examples. The tool is able to reduce the total power consumption by up to 33.9%.
BibTeX
@inproceedings{coward2024combining,
  author = {Samuel Coward and Theo Drane and Emiliano Morini and George A. Constantinides},
  title = {{Combining Power and Arithmetic Optimization via Datapath Rewriting}},
  booktitle = {ARITH},
  year = {2024},
  url = {https://openreview.net/forum?id=yGPWUgA44H},
}
Figure