Constraint-aware e-graph rewriting for hardware performance optimization
File(s)
Accepted version
Author(s)
Coward, Samuel
Drane, Theo
Constantinides, George A
Type
Journal Article
Abstract
Data-dependent constraints commonly occur across hardware and software, often in the form of code branches or input constraints. Expert designers exploit these constraints to realize new optimization opportunities. Numerical hardware designers exploit this aggressively, as if a particular module input value can never be seen, then there is no need to dedicate any circuit area to handling that input value. Floating-point hardware designers have gone further, specifically introducing carefully constructed case-splits to exploit underutilized critical paths. To automate constraint-aware optimization, we developed a theoretical framework, based on the e-graph data structure, that localizes constraint reasoning tasks and makes it simple to realize optimizations exploiting the underlying control structures. The theory introduced here provides an approach to encode multiple equivalence relations within a single e-graph. To demonstrate the value of the theoretical developments, we extend an existing register transfer level (RTL) optimization tool, ROVER, allowing it to exploit constraints present in the RTL itself. We combine this new constraint-awareness with a new RTL value range analysis, allowing ROVER to understand what values each intermediate signal can take. We further add to ROVER by developing a model for circuit delay, allowing ROVER to explore the tradeoffs between performance and circuit area. With these latest developments, ROVER is capable of fully automatically discovering known floating-point architectures from the computer arithmetic literature. The designs generated by constraint-aware ROVER are, on average, 30% faster and 1% smaller than those generated by state-of-the-art EDA tools.
Date Issued
2025-04-01
Date Acceptance
2024-10-12
Citation
IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems, 2025, 44 (4), pp.1366-1379
ISSN
0278-0070
Publisher
Institute of Electrical and Electronics Engineers
Start Page
1366
End Page
1379
Journal / Book Title
IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems
Volume
44
Issue
4
Copyright Statement
Copyright © 2024 IEEE. This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Publication Status
Published
Date Publish Online
2024-10-17