ROVER: RTL Optimization via Verified E-Graph Rewriting
<|reference_start|>ROVER: RTL Optimization via Verified E-Graph Rewriting: Manual RTL design and optimization remains prevalent across the semiconductor industry because commercial logic and high-level synthesis tools are unable to match human designs. Our experience in industrial datapath design demonstrates that manual optimization can typically be decomposed into a sequence of local equivalence preserving transformations. By formulating datapath optimization as a graph rewriting problem we automate design space exploration in a tool we call ROVER. We develop a set of mixed precision RTL rewrite rules inspired by designers at Intel and an accompanying automated validation framework. A particular challenge in datapath design is to determine a productive order in which to apply transformations as this can be design dependent. ROVER resolves this problem by building upon the e-graph data structure, which compactly represents a design space of equivalent implementations. By applying rewrites to this data structure, ROVER generates a set of efficient and functionally equivalent design options. From the ROVER generated e-graph we select an efficient implementation. To accurately model the circuit area we develop a theoretical cost metric and then an integer linear programming model to extract the optimal implementation. To build trust in the generated design ROVER also produces a back-end verification certificate that can be checked using industrial tools. We apply ROVER to both Intel-provided and open-source benchmarks, and see up to a 63% reduction in circuit area. ROVER is also able to generate a customized library of distinct implementations from a given parameterizable RTL design, improving circuit area across the range of possible instantiations.<|reference_end|>
@article{coward2024rover:,
    title={ROVER: RTL Optimization via Verified E-Graph Rewriting},
    author={Samuel Coward, Theo Drane, George A. Constantinides},
    journal={arXiv preprint arXiv:2406.12421},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12421},
    primaryClass={cs.AR}
}