2025-11-30T02:10:19.077243

Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration

Shahawy, de Castelnau, Ienne

Task-level parallelism (TLP) is a widely used approach in software where independent tasks are dynamically created and scheduled at runtime. Recent systems have explored architectural support for TLP on field-programmable gate arrays (FPGAs), often leveraging high-level synthesis (HLS) to create processing elements (PEs). In this paper, we present Bombyx, a compiler toolchain that lowers OpenCilk programs into a Cilk-1-inspired intermediate representation, enabling efficient mapping of CPU-oriented TLP applications to spatial architectures on FPGAs. Unlike OpenCilk's implicit task model, which requires costly context switching in hardware, Cilk-1 adopts explicit continuation-passing - a model that better aligns with the streaming nature of FPGAs. Bombyx supports multiple compilation targets: one is an OpenCilk-compatible runtime for executing Cilk-1-style code using the OpenCilk backend, and another is a synthesizable PE generator designed for HLS tools like Vitis HLS. Additionally, we introduce a decoupled access-execute optimization that enables automatic generation of high-performance PEs, improving memory-compute overlap and overall throughput.

academic

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 (コンピュータアーキテクチャ)
発表日時: 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)はソフトウェアで広く使用される並列技術であり、実行時に動的にタスクを作成・スケジュール可能である。FPGA上のTLPをサポートするハードウェアフレームワーク(ParallelXLやHardCilkなど)は存在するが、ソフトウェアTLPフレームワークから処理ユニット(PE)コードを自動的に抽出・コンパイルするツールが不足している。既存フレームワークは通常、ユーザーがPEコードを手動で提供することを要求しており、これは煩雑でエラーが起きやすい。

2. 問題の重要性

自動化の必要性：CPU指向のTLPアプリケーションをFPGAに移植するには、コード再構築、ハードウェアインターフェース適応、設定ファイル生成など多くの手作業が必要
性能最適化：手書きコードでは高度なハードウェア最適化(分離メモリアクセス・実行など)の適用が困難
開発効率：自動化ツールチェーンの欠如がTLPのFPGAアクセラレーション応用を阻害している

3. 既存方法の限界

OpenCilkの暗黙的モデル：cilk_spawnとcilk_syncを使用するfork-joinモデルは同期点でコンテキストスイッチが必要。ハードウェアでのコンテキストスイッチ実装には回路全体の状態保存が必要であり、現在のHLSツールでは直接サポートされておらず、大量のRTLエンジニアリングが必要
TAPIR中間表現：OpenCilkが使用するTAPIRは低レベルのコンパイラ構成を採用しており、HLS用の元のコードに近い可読性のあるC++コード生成が困難
手動PE記述：クロージャアライメント、ライトバッファインターフェース、設定ファイル生成などの煩雑な詳細を手動で処理する必要がある

4. 研究動機

Cilk-1の明示的継続渡しモデルはハードウェア実装に適している。なぜなら、関数を同期点で終了関数に分割し、これらは原子的に実行され、コンテキストスイッチが不要だからである。このモデルはソフトウェアプログラミングには直感的ではない(Cilk進化の過程で廃止された)が、ハードウェア実装には自然である。Bombyx の目標は、OpenCilkから明示的TLPへの変換を自動化し、最適化されたハードウェアPEを生成することである。

核心貢献

自動化コンパイルフロー：OpenCilkからFPGAハードウェアアクセラレータへの完全な自動化コンパイルツールチェーンBombyx を提案
明示的中間表現：制御フローグラフベースの暗黙的および明示的IR を設計し、fork-joinモデルから継続渡しモデルへの自動変換を実現
マルチターゲットコード生成：
- HardCilkバックエンド：合成可能なC++ HLSコードと設定ファイルを自動生成
- Cilk-1シミュレーション層：OpenCilkランタイムを使用して変換の正確性を検証
分離メモリアクセス・実行最適化：コンパイラプラグマによるDAE最適化をサポート。メモリアクセスと計算を異なるタスクに分離し、ハードウェア性能を向上
実験検証：グラフトラバーサルベンチマークにおいて、DAE最適化により26.5%の実行時間削減を実現

方法の詳細

タスク定義

入力：OpenCilkで記述されたタスク並列C/C++プログラム(CPU指向)
出力：

合成可能なC++ HLSコード(FPGA PE生成用)
HardCilkシステム設定ファイル(JSON形式)
またはCilk-1スタイルの実行可能コード(検証用)

制約条件：

プログラムはOpenCilkのfork-joinモデルに従う必要がある
関数間の依存関係はcilk_spawnとcilk_syncで明示的に表現される必要がある

全体アーキテクチャ設計

Bombyx のコンパイルフローは3つの主要段階を含む(図3参照)：

OpenCilk ソースコード → AST → 暗黙的IR → 明示的IR → コード生成
                    ↓            ↓          ↓
                 Clang前端      DAE最適化   HardCilk/Cilk-1

1. ASTから暗黙的IR への変換

OpenCilk Clang前端を使用して抽象構文木を生成
ASTを制御フローグラフ(CFG)表現の暗黙的IR に変換
各関数は1つのCFGに対応し、以下を含む：
- 唯一の入口ブロック(入辺なし)
- 1つ以上の出口ブロック(出辺なし)
- 基本ブロックは順序C文で構成され、制御フロー文で終了

TAPIR を使用しない理由：TAPIR は低レベルの構成(φノード、allocaなど)を使用しており、元のコードに近い可読性のあるC++コード生成が困難。Bombyx のIR は元のコード構造を保持する。

2. 暗黙的IR から明示的IR への変換

これはBombyx の核心的な変換ステップであり、OpenCilkの暗黙的同期モデルをCilk-1の明示的継続渡しモデルに変換する。

主要概念：

クロージャ(Closure)：タスクのデータ構造。以下を含む：
- 準備完了のパラメータ
- 依存待機中のプレースホルダ
- リターンポインタ
spawn_next：依存待機の継続タスクを作成
send_argument：パラメータを待機クロージャに明示的に書き込み、スケジューラに通知

変換アルゴリズム：

パス分割：CFGをトラバースし、関数終了ブロック(return)またはsync操作に遭遇したら新しいパスを開始
- 各パスは自己完結した終了関数となる
- 図4(c)の灰色領域は2つのパスを表す
依存性識別：sync境界の依存関係を分析
- sync後に使用する必要がある変数を識別(図1のxとyなど)
- これらの変数はクロージャフィールドに明示的に保存する必要がある
キーワード置換：
- 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 BOMBYX DAE
struct node_t nd = *n;  // メモリアクセス操作
// 後続コードが実行タスクになる

コンパイラは自動的に：

マークされた行を独立関数(メモリアクセスタスク)に抽出
spawn呼び出しに置換
syncを挿入
明示的形式に変換後、メモリアクセスタスクが実行タスクの継続を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個)

評価指標

実行時間：グラフ全体のトラバーサルに要する時間
リソース利用率：
- LUT (ルックアップテーブル)
- FF (フリップフロップ)
- BRAM (ブロックRAM)

実験結果

主要性能結果

実行時間削減：DAE最適化により26.5%の性能向上を実現
メモリアクセスと実行の分離により、メモリ・計算オーバーラップを向上

リソース利用率分析

コンポーネント	LUT	FF	BRAM
Non-DAE	2,657	2,305	2
DAE (合計)	3,896	3,464	4
- Spawner	133	387	0
- Executor	1,999	1,913	2
- Access	1,764	1,164	2

リソースオーバーヘッド：

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

実験の知見

性能・リソーストレードオフ：26.5%の性能向上は約50%のリソースオーバーヘッドと引き換え。メモリ集約的アプリケーションにとっては合理的なトレードオフ
PE サイズ分析：
- Spawner + Executor ≈ Non-DAE単一PE サイズ
- Accessタスクが追加リソースを占有
- 推奨：RTL実装のデータ並列PE を使用してメモリアクセスタスク費用を分散
最適化の可能性：論文はメモリアクセスタスクをHLS生成ではなく、ブラックボックスプリミティブとして統合できることを指摘

結論と議論

主要な結論

Bombyx はOpenCilkからFPGAハードウェアへの自動化コンパイルフローを成功裏に実現
明示的継続渡しモデルはFPGAのストリーミング特性に適しており、コスト高いコンテキストスイッチを回避
DAE最適化はグラフトラバーサルベンチマークで26.5%の性能向上を実現
ツールは他のハードウェアTLPフレームワークに拡張可能

限界

DAE最適化は手動指導が必要：現在、プログラマがプラグマを挿入する必要があり、完全な自動化が実現されていない
評価が限定的：
- 単一のベンチマーク(グラフトラバーサル)でのみ評価
- 他の方法(手書きコード、他のコンパイラ)との比較がない
- より多様なアプリケーションシナリオのテストがない
リソースオーバーヘッド：DAE最適化は約50%のリソース増加をもたらし、大規模システムを制限する可能性
メモリアクセスタスク実装：HLS生成メモリPE の効率が低い。RTL使用を推奨しているが未実装
ツール成熟度：研究プロトタイプとして、完全なエラーハンドリングとエッジケースサポートが不足

今後の方向性

自動DAE識別：DAE最適化に適したコードパターンを自動識別するコンパイラ分析を開発
RTL メモリユニット：効率的なRTL実装データ並列メモリユニットを統合
さらなる最適化：他のハードウェア固有最適化を探索(データ再利用、局所性最適化など)
ターゲット拡張：より多くのハードウェアTLPフレームワークとHLSツールをサポート
包括的評価：より多くのベンチマークで評価。異なるタイプの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 半自動化：手動プラグマが必要。易用性を制限
最適化の空間が限定的：1つの最適化(DAE)のみを示す。他のハードウェア最適化の探索がない
リソースオーバーヘッドが大きい：50%のリソース増加は実際の応用を制限する可能性

3. 技術詳細が不足

変換アルゴリズムが不完全：依存性分析、クロージャフィールド選択などの主要アルゴリズムの詳細説明がない
正確性保証：形式的証明またはシステム的検証方法がない
エッジケース：再帰、ポインタ、複雑なデータ構造などの処理が議論されていない

4. 評価の深さ

スケーラビリティ不明：大規模アプリケーションや複雑な制御フローのテストがない
汎用性に疑問：グラフトラバーサルが典型的なTLPアプリケーションを代表しているか？
理論との乖離：26.5%の向上は理論上限に接近しているか？

影響力

1. 分野への貢献

ツールチェーン空白を埋める：TLPのFPGA応用に重要なインフラストラクチャを提供
後続研究への示唆：明示的変換思想を他の並列モデルに応用可能
ハードウェアTLP推進：使用敷居を低下させ、TLPのFPGAアクセラレーション推進に有利

2. 実用価値

中程度の実用性：HardCilk ユーザーに直接的価値。さらなる成熟が必要
学習コスト：TLP概念とハードウェア制約の理解が必要
本番運用準備度：研究プロトタイプとして、本番使用までに距離がある

3. 再現性

中程度：OpenCilk、HardCilk、Vitis HLS などツールチェーンに依存
コード未公開：論文でコード公開計画が言及されていない
実験詳細は充分：実装と実験の詳細が十分提供されている

適用シーン

適切なシーン

動的タスク並列アプリケーション：グラフアルゴリズム、ツリートラバーサル、動的計画法など
メモリ集約型計算：DAE最適化は特にメモリボトルネックアプリケーションに適している
HardCilk ユーザー：既にHardCilk を使用または計画しているユーザー
高速プロトタイピング：CPU TLPコードをFPGAに高速移植する必要がある場合

不適切なシーン

規則的並列処理：データ並列、パイプライン処理など動的スケジューリング不要なシーン
リソース制約：50%のリソースオーバーヘッドが受け入れられない場合
極限性能：手書きRTL最適化がより優れている可能性
複雑なメモリパターン：複雑なポインタ、動的メモリへのツール対応が不明

改善提案

評価拡張：より多くのベンチマークテストを追加(ソート、検索、科学計算など)
性能比較：手書きHLSコード、CPU実装、GPU実装との比較
自動DAE：DAE機会を自動識別するコンパイラ分析を開発
最適化多様性：データ再利用、ローカルキャッシュなど他のハードウェア最適化を探索
形式的検証：変換正確性の形式的保証を提供
オープンソース公開：ツールをオープンソース化してコミュニティ貢献と検証を促進

参考文献

本論文が引用する主要文献：

2 OpenCilk (PPoPP'23)：最新のCilkフレームワーク。Bombyx の入力言語
4 HardCilk (FCCM'24)：Bombyx のターゲットプラットフォーム。著者の先行研究
5 Cilk-1 (SIGPLAN'95)：古典的な明示的継続渡しTLPシステム。Bombyx の理論的基礎
6 Joerg博士論文 (1996)：暗黙的から明示的への変換の理論的可行性を証明

総合評価：Bombyx はOpenCilkからFPGAハードウェアアクセラレータへの自動化ツールチェーン空白を埋める価値のある研究成果である。その核心的革新はCilk-1の明示的継続渡しモデルを活用してハードウェアコンテキストスイッチを回避し、完全なコンパイルフローを提供することにある。しかし、初期段階の研究として、実験評価の広度と深度に明らかな不足がある。DAE最適化の半自動化も易用性を制限している。本ツールはHardCilk ユーザーとTLP研究者に直接的価値を持つが、広範な応用には進一步の成熟が必要である。後続研究は自動最適化識別、ベンチマーク評価拡張、オープンソース公開に重点を置くことを推奨する。