arXiv:2511.15323cs.PLcs.CL2025-11被引 1

用e图统一优化硬件实现选择与调度,提升FPGA设计效率。

SkyEgg: Joint Implementation Selection and Scheduling for Hardware Synthesis using E-graphs

  • 将算术变换和硬件实现统一为重写规则,构建完整设计空间。
  • 在Xilinx Kintex UltraScale+上平均提速3.01倍,复杂表达式最高5.22倍。
  • 适合需要高效FPGA硬件生成的开发者和系统架构师。

从高层描述进行硬件合成仍受限于相互依赖设计决策的串行优化。现有方法(包括最先进的高层次综合工具)人为分离实现选择与调度,导致无法充分挖掘现代FPGA异构架构的潜力。实现选择通常通过操作上的启发式模式匹配完成,不考虑对调度的影响;随后的调度算法基于固定选择方案与不准确的延迟估计运行,错失了如DSP切片等配置得当的优化机会。我们提出SkyEgg,一种新颖的硬件合成框架,利用e图联合优化实现选择与调度。核心洞察是:代数变换与硬件实现选择均可统一表示为e图中的重写规则,从而建模完整的候选实现与调度空间。首先,SkyEgg从输入程序构建e图;接着通过等式饱和应用代数与实现重写;最后,将联合优化问题建模为饱和e图上的混合整数线性规划(MILP)问题。我们提供精确的MILP求解与高效的ASAP启发式算法以支持可扩展合成。在涵盖多样化应用的基准测试中,针对Xilinx Kintex UltraScale+ FPGA的评估表明,SkyEgg相比Vitis HLS平均提速3.01倍,复杂表达式最高达5.22倍。

原文摘要 · Abstract (English)

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.01x over Vitis HLS, with improvements up to 5.22x for complex expressions.

FPGA硬件合成e图调度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。