# Automatic Datapath Optimization using E-Graphs

**Authors:** Samuel Coward, George A. Constantinides, Theo Drane  
**arXiv:** [2204.11478](https://arxiv.org/abs/2204.11478)  
**Date:** 2022-04-25  
**Summary page:** https://www.summarizepaper.com/en/paper/2204.11478v1/

## Key points

- The paper proposes a novel approach to automate circuit design space exploration and optimize RTL datapath architectures.
- The authors utilize graph rewriting techniques, e-graphs, and equality saturation for automating RTL optimization.
- Complex transformations of one RTL into another equivalent RTL can be broken down into smaller, localized transformations.
- By representing RTL as a graph and using modern graph rewriting techniques, functionally equivalent but optimized architectures can be discovered.
- Precisely defined rewrites facilitate efficient design space exploration in designs with multiple bitwidth parameters.
- The proposed approach generates a library of optimized designs instead of a single design point typically obtained through manual optimization.
- Fuzzing techniques are used to quantify a "noise floor" in datapath logic synthesis, identifying potential errors or limitations in automated optimizations.
- Previous work on transformation-based datapath improvement is discussed, including carry-save representation and solving the multiple constant multiplication (MCM) problem.
- The authors generalize these approaches using their methodology and replicate results from prior studies.
- Overall, the proposed approach significantly reduces circuit area while considering various bitwidth parameters and has the potential to accelerate circuit design development.

## Summary

The paper focuses on the manual optimization of Register Transfer Level (RTL) datapath in the industry, which is a time-consuming process. To address this issue, the authors propose a novel approach that utilizes graph rewriting techniques to automate circuit design space exploration and discover optimized architectures. The key contribution of the paper includes the application of e-graphs and equality saturation for automating RTL optimization. The authors demonstrate that complex transformations of one RTL into another equivalent RTL can be broken down into smaller, localized transformations. By representing RTL as a graph and deploying modern graph rewriting techniques, they are able to automate the discovery of functionally equivalent but optimized architectures. The paper also introduces a set of precisely defined rewrites that facilitate efficient design space exploration in designs utilizing multiple bitwidth parameters. This allows for the optimization of architectures based on different bitwidth parameters, resulting in a library of optimized designs rather than a single design point typically generated by manual optimization. Furthermore, the authors quantify a "noise floor" in datapath logic synthesis using fuzzing techniques from software testing. This helps identify potential errors or limitations in automated optimizations and provides insights into improving their effectiveness. In terms of background, the paper discusses previous work on transformation-based datapath improvement such as maximizing carry-save representation and solving the multiple constant multiplication (MCM) problem. The authors generalize these approaches using their methodology and show that their automated optimization approach can replicate results obtained in prior studies. Overall, this paper presents an automated optimization approach for RTL datapath that can significantly reduce circuit area while considering various bitwidth parameters. It not only reproduces typical industrial manual optimizations but also expands upon prior academic work on carry-save representation and multiple constant multiplication. The proposed approach has the potential to accelerate circuit design development by automating time-consuming manual optimizations.