Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration

基本信息

• 论文ID: 2511.21346
• 标题: Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
• 作者: Mohamed Shahawy, Julien de Castelnau, Paolo Ienne (École Polytechnique Fédérale de Lausanne)
• 分类: cs.AR (Computer Architecture)
• 发表时间: 2025年11月26日 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2511.21346

摘要

本文提出Bombyx，一个将OpenCilk程序编译为FPGA硬件加速器的工具链。Bombyx将OpenCilk的隐式任务并行模型转换为Cilk-1风格的显式延续传递（continuation-passing）中间表示，更适合FPGA的流式特性。该工具支持多个编译目标：OpenCilk兼容运行时用于验证，以及可综合的处理单元生成器用于Vitis HLS等高层次综合工具。此外，Bombyx引入了解耦访存-执行（DAE）优化，自动生成高性能处理单元，提升存储-计算重叠和整体吞吐量。

研究背景与动机

1. 要解决的核心问题

任务级并行（TLP）是软件中广泛使用的并行技术，能够在运行时动态创建和调度独立任务。虽然已有硬件框架（如ParallelXL和HardCilk）支持FPGA上的TLP，但缺乏从软件TLP框架自动提取和编译处理单元（PE）代码的自动化工具。现有框架通常要求用户手动提供PE代码，这既繁琐又易错。

2. 问题的重要性

• 自动化需求：将CPU导向的TLP应用移植到FPGA需要大量手工工作，包括代码重构、硬件接口适配、配置文件生成等
• 性能优化：手工编写的代码难以应用高级硬件优化（如解耦访存-执行）
• 开发效率：缺少自动化工具链阻碍了TLP在FPGA加速中的广泛应用

3. 现有方法的局限性

• OpenCilk的隐式模型：使用cilk_spawn和cilk_sync的fork-join模型需要在同步点进行上下文切换。在硬件中实现上下文切换需要保存整个电路状态，这对于当前HLS工具来说既不直接支持，也需要大量RTL工程
• TAPIR中间表示：OpenCilk使用的TAPIR采用低级编译器构造，难以生成接近原始代码的可读C++代码用于HLS
• 手动PE编写：需要手动处理闭包对齐、写缓冲接口、配置文件生成等繁琐细节

4. 研究动机

Cilk-1的显式延续传递模型更适合硬件实现，因为它将函数在同步点分裂为终止函数（atomically执行，无需上下文切换）。虽然这种模型对软件编程不够直观（因此在Cilk演化中被淘汰），但对硬件实现却是自然的。Bombyx的目标是自动化从OpenCilk到显式TLP的转换，并生成优化的硬件PE。

核心贡献

1. 自动化编译流程：提出完整的从OpenCilk到FPGA硬件加速器的自动化编译工具链Bombyx
2. 显式中间表示：设计了基于控制流图的隐式和显式IR，实现从fork-join模型到延续传递模型的自动转换
3. 多目标代码生成：
   • HardCilk后端：自动生成可综合的C++ HLS代码和配置文件
   • Cilk-1仿真层：使用OpenCilk运行时验证转换正确性
4. 解耦访存-执行优化：通过编译指导（pragma）支持DAE优化，将访存和计算分离为不同任务，提升硬件性能
5. 实验验证：在图遍历基准测试中，DAE优化实现26.5%的运行时间减少

方法详解

任务定义

输入：使用OpenCilk编写的任务并行C/C++程序（CPU导向）
输出：

• 可综合的C++ HLS代码（用于FPGA PE生成）
• HardCilk系统配置文件（JSON格式）
• 或Cilk-1风格的可执行代码（用于验证）

约束条件：

• 程序必须遵循OpenCilk的fork-join模型
• 函数间依赖关系必须通过cilk_spawn和cilk_sync明确表达

整体架构设计

Bombyx的编译流程包含三个主要阶段（见图3）：

OpenCilk源码 → AST → 隐式IR → 显式IR → 代码生成
                 ↓              ↓          ↓
              Clang前端      DAE优化   HardCilk/Cilk-1

1. AST到隐式IR转换

• 使用OpenCilk Clang前端生成抽象语法树
• 将AST转换为控制流图（CFG）表示的隐式IR
• 每个函数对应一个CFG，包含：
  • 唯一入口块（无入边）
  • 一个或多个出口块（无出边）
  • 基本块由顺序C语句组成，以控制流语句终止

为什么不使用TAPIR：TAPIR使用低级构造（如φ节点、alloca等），使得生成接近原始代码的可读C++代码变得困难。Bombyx的IR保留原始代码结构。

2. 隐式IR到显式IR转换

这是Bombyx的核心转换步骤，将OpenCilk的隐式同步模型转换为Cilk-1的显式延续传递模型。

关键概念：

• 闭包（Closure）：表示任务的数据结构，包含：
  • 已就绪的参数
  • 等待依赖的占位符
  • 返回指针
• spawn_next：创建等待依赖的延续任务
• send_argument：显式写入参数到等待闭包并通知调度器

转换算法：

1. 路径划分：遍历CFG，在遇到函数终止块（return）或sync操作时开始新路径
   • 每个路径成为一个自包含的终止函数
   • 图4(c)中的灰色区域表示两个路径
2. 依赖识别：分析sync边界的依赖关系
   • 识别需要在sync后使用的变量（如图1中的x和y）
   • 这些变量需要显式存储在闭包中
3. 关键字替换：
   • 在spawn调用处插入闭包声明
   • 将sync替换为spawn_next调用后继函数
   • 将spawn的返回值改为显式写入闭包字段
   • 保留return语句，后续可转换为send_argument

示例转换（图1到图2）：

// 隐式（OpenCilk）
int x = cilk_spawn fib(n-1);
int y = cilk_spawn fib(n-2);
cilk_sync;
return x + y;

// 显式（Cilk-1）
cont int x, y;
spawn_next sum(k, ?x, ?y);  // 创建延续任务
spawn fib(x, n-1);           // 写入x占位符
spawn fib(y, n-2);           // 写入y占位符
// 函数终止，无需sync

HardCilk后端生成

HardCilk是开源的FPGA TLP架构生成器，提供硬件工作窃取调度器。Bombyx自动化生成HardCilk所需的所有组件：

1. 闭包对齐

• 自动添加填充使闭包大小对齐到128/256位
• 便于硬件实现

2. 写缓冲接口

• HardCilk使用写缓冲模块处理spawn_next和send_argument
• Bombyx自动插入所需的元数据（任务类型、目标地址等）

3. JSON配置生成

通过静态分析自动生成系统描述文件，包含：

• 闭包大小
• 任务间spawn/spawn_next/send_argument关系
• 其他系统配置参数

解耦访存-执行（DAE）优化

动机

在朴素PE实现中，同一单元负责发起内存请求和执行计算，导致：

• 内存停顿使PE空闲
• 降低整体吞吐量

传统流水线在HLS工具（如Vitis）中受限：

• 无法处理数据依赖的循环边界
• 静态调度器无法确定何时调度内存访问

DAE方案

在TLP下，将访存和执行表达为不同任务：

• 访存任务：专门负责内存请求
• 执行任务：处理计算逻辑
• 任务调度器：协调执行，实现弹性流水线

实现方式

通过pragma指导编译器：

#PRAGMA BOMBYX DAE
struct node_t nd = *n;  // 访存操作
// 后续代码成为执行任务

编译器自动：

1. 提取被标注行到独立函数（访存任务）
2. 替换为spawn调用
3. 插入sync
4. 转换为显式形式后，访存任务spawn执行任务的延续

实验设置

基准测试

图遍历程序（图5）：

• 并行广度优先图遍历
• 访问节点邻接表（内存密集）
• 递归并行访问相邻节点

数据集

合成生成的树形图：

• 图1：深度D=7，分支因子B=4，共5,461个节点
• 图2：深度D=9，分支因子B=4，共87,381个节点
• 节点数计算：$\frac{B^D - 1}{B - 1}$

实验配置

• FPGA平台：Xilinx Alveo U55C (xcu55c-fsvh2892-2L-e)
• 综合工具：Vivado 2024.1
• 目标频率：300 MHz
• PE数量：
  • Non-DAE：1个PE
  • DAE：3个PE（spawner、executor、access各1个）

评价指标

1. 运行时间：遍历整个图所需时间
2. 资源利用率：
   • LUT (Look-Up Tables)
   • FF (Flip-Flops)
   • BRAM (Block RAM)

实验结果

主要性能结果

• 运行时间减少：DAE优化实现26.5%的性能提升
• 通过解耦访存和执行，提升了内存-计算重叠

资源利用率分析

资源开销：

• LUT增加47% (2,657 → 3,896)
• FF增加50% (2,305 → 3,464)
• BRAM翻倍 (2 → 4)

实验发现

1. 性能-资源权衡：26.5%的性能提升以约50%的资源开销为代价，对于内存密集型应用是合理的权衡
2. PE大小分析：
   • Spawner + Executor ≈ Non-DAE单PE大小
   • Access任务占用额外资源
   • 建议：使用RTL实现的数据并行PE可分摊访存任务成本
3. 优化潜力：论文指出未来可将访存任务作为黑盒原语集成，而非使用HLS生成

相关工作

TLP软件框架

1. Intel Thread Building Blocks (TBB)：工业界广泛使用的任务并行库
2. Cilk Plus：Intel的Cilk扩展版本
3. OpenCilk：最新的Cilk框架，性能优于前述框架

TLP硬件框架

1. ParallelXL：早期FPGA上的TLP架构框架
2. HardCilk：Bombyx的目标平台，开源的FPGA TLP系统，提供硬件工作窃取调度器

Cilk演化

1. Cilk-1：最早采用显式延续传递的版本
2. 后续版本：转向隐式fork-join模型（更适合软件编程）
3. 理论基础：已证明任何隐式程序可转换为显式形式

本文优势

• 首个自动化工具：从OpenCilk到FPGA PE的完整自动化流程
• 显式转换：利用Cilk-1风格避免硬件上下文切换
• 优化支持：集成DAE等硬件特定优化

结论与讨论

主要结论

1. Bombyx成功实现了从OpenCilk到FPGA硬件的自动化编译流程
2. 显式延续传递模型适合FPGA的流式特性，避免了代价高昂的上下文切换
3. DAE优化在图遍历基准测试中实现26.5%的性能提升
4. 工具可扩展到其他硬件TLP框架

局限性

1. DAE优化需要手动指导：当前需要程序员插入pragma，未实现完全自动化
2. 评估有限：
   • 仅在单个基准测试（图遍历）上评估
   • 缺少与其他方法的对比（如手写代码、其他编译器）
   • 未测试更多样化的应用场景
3. 资源开销：DAE优化带来约50%的资源增加，可能限制大规模系统
4. 访存任务实现：使用HLS生成访存PE效率不高，建议使用RTL但未实现
5. 工具成熟度：作为研究原型，缺少完整的错误处理和边界情况支持

未来方向

1. 自动DAE识别：开发编译器分析自动识别适合DAE优化的代码模式
2. RTL访存单元：集成高效的RTL实现的数据并行访存单元
3. 更多优化：探索其他硬件特定优化（如数据重用、局部性优化）
4. 扩展目标：支持更多硬件TLP框架和HLS工具
5. 全面评估：在更多基准测试上评估，包括不同类型的TLP应用

深度评价

优点

1. 方法创新性

• 独特的转换策略：利用Cilk-1的显式延续传递模型巧妙解决硬件上下文切换难题
• 自动化价值：首次实现完整的OpenCilk到FPGA的自动化工具链，填补了重要空白
• IR设计合理：保留原始代码结构的IR设计使生成的HLS代码更可读

2. 工程贡献

• 实用性强：自动化处理闭包对齐、写缓冲接口、配置文件生成等繁琐细节
• 可验证性：提供Cilk-1仿真层用于验证转换正确性，增强工具可信度
• 开源友好：目标HardCilk是开源系统，有利于工具推广

3. 技术洞察

• 硬件-软件协同：深刻理解软件TLP模型与硬件实现的适配问题
• DAE优化：将经典硬件优化与TLP结合，展示了编译器指导优化的潜力

4. 写作清晰度

• 通过Fibonacci示例清晰展示隐式到显式的转换
• 图4的IR对比直观易懂
• 编译流程图清晰

不足

1. 实验不充分

• 基准测试单一：仅评估图遍历，无法全面验证工具的通用性
• 缺少对比：未与手写代码、其他编译方法对比
• 规模有限：测试图相对较小（最大87K节点）
• 性能分析不深入：未分析性能提升的具体来源（带宽利用率、任务调度效率等）

2. 方法局限

• DAE半自动化：需要手动pragma，限制了易用性
• 优化空间有限：仅展示一种优化（DAE），未探索其他硬件优化
• 资源开销大：50%的资源增加可能限制实际应用

3. 技术细节缺失

• 转换算法不完整：未详细说明依赖分析、闭包字段选择等关键算法
• 正确性保证：未提供形式化证明或系统性验证方法
• 边界情况：未讨论递归、指针、复杂数据结构等的处理

4. 评估深度

• 可扩展性未知：未测试大规模应用或复杂控制流
• 通用性存疑：图遍历是否代表典型TLP应用？
• 与理论差距：26.5%的提升是否接近理论上限？

影响力

1. 对领域的贡献

• 填补工具链空白：为TLP在FPGA上的应用提供重要基础设施
• 启发后续研究：显式转换思路可应用于其他并行模型
• 推动硬件TLP：降低使用门槛，有助于TLP在FPGA加速中的推广

2. 实用价值

• 中等实用性：对于HardCilk用户有直接价值，但需要进一步成熟
• 学习成本：仍需理解TLP概念和硬件约束
• 生产就绪度：作为研究原型，距离生产使用有距离

3. 可复现性

• 中等：依赖OpenCilk、HardCilk、Vitis HLS等工具链
• 代码未开源：论文未提及代码开源计划
• 实验细节充分：提供了足够的实现和实验细节

适用场景

适合的场景

1. 动态任务并行应用：图算法、树遍历、动态规划等
2. 内存密集型计算：DAE优化特别适合访存瓶颈应用
3. HardCilk用户：已使用或计划使用HardCilk的开发者
4. 快速原型：需要快速将CPU TLP代码移植到FPGA

不适合的场景

1. 规则并行：数据并行、流水线等不需要动态调度的场景
2. 资源受限：50%的资源开销可能不可接受
3. 极致性能：手工优化的RTL仍可能更优
4. 复杂内存模式：工具对复杂指针、动态内存的支持未知

改进建议

1. 扩展评估：增加更多基准测试（排序、搜索、科学计算等）
2. 性能对比：与手写HLS代码、CPU实现、GPU实现对比
3. 自动化DAE：开发编译器分析自动识别DAE机会
4. 优化多样性：探索更多硬件优化（数据重用、局部缓存等）
5. 形式化验证：提供转换正确性的形式化保证
6. 开源发布：开源工具以促进社区贡献和验证

参考文献

本文引用的关键文献：

1. 2 OpenCilk (PPoPP'23)：最新的Cilk框架，Bombyx的输入语言
2. 4 HardCilk (FCCM'24)：Bombyx的目标平台，作者之前的工作
3. 5 Cilk-1 (SIGPLAN'95)：经典的显式延续传递TLP系统，Bombyx的理论基础
4. 6 Joerg博士论文 (1996)：证明隐式到显式转换的理论可行性

总体评价：Bombyx是一个有价值的研究工作，填补了OpenCilk到FPGA硬件加速的自动化工具链空白。其核心创新在于利用Cilk-1的显式延续传递模型避免硬件上下文切换，并提供完整的编译流程。然而，作为初步工作，论文在实验评估的广度和深度上存在明显不足，DAE优化的半自动化也限制了易用性。该工具对于HardCilk用户和TLP研究者有直接价值，但需要进一步成熟才能广泛应用。建议后续工作重点关注自动化优化识别、扩展基准测试评估，以及开源发布以促进社区验证和改进。