Abstract
ROVER is an automated optimization tool for hardware datapath designs (RTL) that leverages e-graphs and equality saturation to navigate complex design spaces. By integrating automated rewrite-rule discovery with a formally verified equivalence-checking pipeline, ROVER achieves area reductions of up to 63%, frequently surpassing the performance of both human experts and commercial synthesis tools.
Introduction
In semiconductor design, manual optimization of Register Transfer Level (RTL) code remains common because commercial logic synthesis tools often fail to identify optimal datapath architectures. Hardware optimization is inherently non-monotonic; achieving a highly efficient design frequently requires applying transformations that initially appear to degrade performance—such as duplicating operators—to unlock significant downstream simplifications. Traditional "destructive" rewriting tools, which replace one structure with another, are prone to local optima. ROVER addresses these challenges by treating optimization as a graph-rewriting problem supported by formal verification.
Methodology
ROVER introduces a robust pipeline for datapath optimization centered on three core innovations:
- E-Graphs and Equality Saturation: ROVER utilizes e-graphs to represent all discovered equivalent versions of a design simultaneously. This approach avoids the "phase-ordering problem," where the sequence of applied rules limits the final design quality.
- Automated Condition Synthesis: To handle the nuances of hardware bitvectors (e.g., bitwidth and signage), ROVER uses program synthesis and decision tree classifiers to automatically learn the validity conditions for rewrite rules.
- Verified Extraction: ROVER employs an Integer Linear Programming (ILP) model to select the optimal design from the e-graph, accounting for common sub-expression elimination. Crucially, it generates a "proof certificate"—a sequence of simple equivalences—that can be verified by industrial equivalence checkers (EC).
The system operates on VeriLang, a custom intermediate representation tailored for hardware bitvectors.
Key Insights: The Power of Non-Monotonicity
A defining characteristic of ROVER's approach is its ability to explore "worse" designs to find better ones.
As shown in the optimization trace, the circuit area metric often increases significantly during the rewrite process before plummeting to a final state much lower than the original. This confirms that temporary design expansion is often a prerequisite for global optimization. Furthermore, ROVER adapts architectures based on bitwidth; for instance, it might switch from individual adders to a SUM-tree or Fused-Multiply-Add (FMA) structure as constraints change.
Evaluation and Results
ROVER was evaluated against industrial and academic benchmarks, including Intel media kernels and standard FIR filters. Key findings include:
- Significant Area Savings: ROVER achieved a peak area reduction of 63% on Shift-Multiplier benchmarks.
- Outperforming Experts: On an Intel Media Kernel previously optimized by human experts, ROVER reduced both area and delay by an additional 50%.
- Synthesis Resilience: By exploring the design space, ROVER identifies "synthesis-friendly" RTL versions that commercial tools like Synopsys Design Compiler can optimize more effectively.
- Efficient Verification: While industrial tools often time out on complex end-to-end comparisons, ROVER’s decomposed proof chain allows verification to complete in seconds.
Conclusion and Future Work
ROVER demonstrates the efficacy of e-graphs for hardware optimization. Future work will focus on incorporating more sophisticated timing and delay models into the cost function and improving the scalability of the ILP extraction process for larger e-graphs. Integrating formal theorem provers like ACL2 could further enhance the "correct-by-construction" nature of the synthesized rules.
Summary updated