SkyEgg : Joint Implementation Selection and Scheduling for Hardware Synthesis using E-graphs
Youwei Xiao, Yuyang Zou, Yun Liang · 2025
Read SkyEgg : Joint Implementation Selection and Scheduling for Hardware Synthesis using E-graphs by Youwei Xiao, Yuyang Zou, Yun Liang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15323.txt.
Introduction
Yuyang Zou, Youwei Xiao, and two co-authors present SkyEgg, a hardware synthesis system that keeps every design option open until the evidence is in. Synthesis turns high-level programs into accelerator circuits on FPGAs, whose modern resources vary in function and timing in fine detail. Older tools commit early: they fix the program's form, then its schedule, then its mapping, each step discarding options the later steps needed.
SkyEgg instead uses equality saturation, a technique that keeps many equivalent forms of the design alive at once. Implementation choice, scheduling, and mapping are explored together, with chaining and fusion of operations preserved. The heterogeneity-aware search aims at end-to-end speed that staged pipelines leave on the table.
Catalog record
| CREATOR | Youwei Xiao, Yuyang Zou, Yun Liang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-15323
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SkyEgg : Joint Implementation Selection and Scheduling for Hardware Synthesis using E-graphs Youwei Xiao, Yuyang Zou, Yun Liang Abstract . Hardware synthesis from high-level descriptions remains fundamentally limited by the sequential optimization of interdependent design decisions. Current methodologies, including state-of-the-art high-level synthesis (HLS) tools, artificially separate implementation selection from scheduling, leading to suboptimal designs that cannot fully exploit modern FPGA heterogeneous architectures. Implementation selection is typically performed by ad-hoc pattern matching on operations, a process that does not consider the impact on scheduling. Subsequently, scheduling algorithms operate on fixed selection solutions with inaccurate delay estimates, which misses critical optimization opportunities from appropriately configured FPGA blocks like DSP slices. We present SkyEgg , a novel hardware synthesis framework that jointly optimizes implementation selection and scheduling using the e-graph data structure. Our key insight is that both algebraic transformations and hardware implementation choices can be uniformly represented as rewrite rules within an e-graph, modeling the complete design space of implementation candidates to be selected and scheduled together. First, SkyEgg constructs an e-graph from the input program. It then applies both algebraic and implementation rewrites through equality saturation. Finally, it formulates the joint optimization as a mixed-integer linear programming (MILP) problem on the saturated e-graph. We provide both exact MILP solving and an efficient ASAP heuristic for scalable synthesis. Our evaluation on benchmarks from diverse applications targeting Xilinx Kintex UltraScale+ FPGAs demonstrates that SkyEgg achieves an average speedup of 3.01× over Vitis HLS, with improvements up to 5.22× for complex expressions. 1. Introduction Hardware synthesis has emerged as a critical technology for bridging the gap between high-level software descriptions and efficient hardware implementations. As computing demands grow increasingly diverse and performance requirements become more stringent, the ability to automatically translate software algorithms, either in general programming languages ( 4 ; 46 ; 18 ; 28 ) like C/C++ or domain-specific languages (DSLs) ( 36 ; 29 ; 16 ) , into optimized hardware accelerators has become essential for domains ranging from machine learning ( 20 ) to signal processing ( 3 ) . The fundamental challenge in hardware synthesis lies in resolving the semantic differences between software and hardware representations. Software descriptions are inherently untimed and abstract —operations are specified without explicit timing constraints and executed as processor instructions. In contrast, hardware implementations require precise timing and concrete resource mapping —every operation must be scheduled to specific clock cycles and bound to physical hardware modules. This semantic gap necessitates sophisticated compilation techniques that can efficiently navigate the complex trade-offs between performance, resource utilization, and design constraints. Current hardware synthesis methodologies, including high-level synthesis (HLS) tools ( 46 ; 4 ) and accelerator design language compilers ( 36 ; 29 ) , address this challenge through sequential optimization phases. Typically, these tools first select a target hardware implementation for software operations in an ad-hoc manner to obtain their scheduling properties. We refer to this process as implementation selection , which is crucial, especially for heterogeneous FPGAs that have different hardware blocks like LUTs and DSP slices ( 1 ) as implementation candidates with diverse timing properties. Subsequently, they perform scheduling to determine the temporal execution timing of the operations. After scheduling, real hardware modules are allocated with implementations mapped on them, producing the synthesized hardware. While this sequential approach simplifies the synthesis process, it suffers from fundamental limitations leading to non-optimal designs. The core problem stems from the artificial separation of interdependent optimization decisions. Scheduling algorithms must make timing decisions based on implementations’ detailed properties, while traditional approaches’ inaccurate models lead to conservative schedules that underutilize available hardware performance. Conversely, implementation selection must select appropriate implementations and configure them properly to schedule the optimal design. The selection design space is huge, including packing a group of operations into highly-optimized intellectual property (IP) blocks like floating-point units or dedicated hardware blocks like DSP slices ( 1 ) , and configuring their pipeline depth or modes. Existing tools ( 4 ; 46 ; 18 ; 8 ) make heuristic, ad-hoc selection decisions before scheduling, irreversibly causing sub-optimal schedules with significantly worse performance. Recent advances in compiler optimization have demonstrated the power of e-graphs ( 34 ; 48 ) for exploring large design spaces efficiently ( 7 ) . E-graphs provide a compact representation of equivalent program expressions, referred to as terms , and enable systematic exploration of optimization opportunities through rewrite rules. This approach has proven successful in making selection decisions for software compiler optimization ( 38 ) , hardware logic synthesis ( 14 ; 10 ; 9 ) , and FPGA technology mapping ( 40 ; 41 ; 26 ) . However, prior work has not explored the potential of e-graphs by combining the implementation selection and scheduling for addressing the fundamental software-hardware semantic gap. In this paper, we propose SkyEgg , a novel hardware synthesis framework that performs joint implementation selection and scheduling using e-graphs. Our key insight is that both operation rewrites and hardware implementation choices can be uniformly represented as rewrite rules in an e-graph, which models the complete operation selection design space through equality saturation . We formulate the joint selection and scheduling problem as a mixed-integer linear programming (MILP) problem over the saturated e-graph structure, and propose a heuristic scheduler for scalable solving. Specifically, we use egglog ( 48 ) ’s Python binding ( 39 ) to create an e-graph from the software program in MLIR ( 32 ) . We introduce implementation e-nodes in the e-graph to represent the candidate implementations for the terms in the same e-classes. SkyEgg models each implementation candidate on the target FPGA device as an implementation rewrite rule that matches the implementation’s software functionality. We propose a profile-based timing model to calculate the scheduling properties of implementations with the configurations enumerated. After running equality saturation, the e-graph represents the implementation selection design space, and SkyEgg ’s joint problem formulation includes constraints for both the legal selection and the legal scheduling, globally optimizing the objective. For practicality, SkyEgg reduces the constraints involved for the exact MILP solving, and proposes an ASAP (As-Soon-As-Possible) scheduler for much faster and scalable problem solving. Our approach makes the following contributions: • Joint synthesis paradigm : We introduce the first hardware synthesis approach that jointly optimizes implementation selection and scheduling using e-graphs, thereby overcoming the suboptimality inherent in sequential heuristics. We implement an open-source 1 1 1 http://link-omitted-for-blind-review prototype framework, SkyEgg . • Design space definition on e-graph : We define operation implementation candidates with modeled scheduling properties as rewrite rules, enabling compact representation and expansion of hardware synthesis design space. • Problem formulation and solving : We formulate the joint selection and scheduling problem as a mixed-integer linear programming problem over the e-graph structure, and propose an as-soon-as-possible heuristic for scalable solving. Evaluation. We evaluate SkyEgg across diverse benchmarks against Xilinx’s state-of-the-art commercial toolchain. The results show that SkyEgg achieves an average speedup of 3.10× (and up to 5.22×). This performance gain comes with competitive resource usage compared to the baseline: for the MILP and ASAP schedulers, flip-flop (FF) usage was 0.87× and 0.95×, respectively, while look-up table (LUT) usage was 1.51× and 1.28×, respectively. All SkyEgg designs meet timing constraints while Vitis HLS fails 48% of cases at