Bend - GPUで実行される高級言語（HVM2使用）
(github.com/HigherOrderCO)- Bendは、Python・Haskellのような表現力とCUDA式の大規模並列実行の両立を目指す高水準並列プログラミング言語で、HVM2ランタイム上で動作する
- クロージャを持つ高階関数、高速なオブジェクト割り当て、制限のない再帰、continuationをサポートしつつ、スレッド生成、ロック、ミューテックス、atomicのような明示的な並列化記法なしにGPUのような並列ハードウェアで実行される
- 現在の設計目標はコア数に応じたスケーリング性能であり、10,000個以上の同時スレッドをサポートするが、現行バージョンでは単一コア性能が低い可能性があり、コード生成・最適化の改善が進行中
- 実行方法は
bend run-rs、bend run-c、bend run-cuに分かれており、並列化可能なコードは実行コマンドを変えるだけでCインタプリタやCUDAインタプリタで並列実行できる - Windows対応はまだ作業中のため、代替としてWSL2が使え、GPU実行は現在NVIDIA GPUのみ対応している
Bendが目指すプログラミングモデル
- Bendは、高水準言語の使い勝手を維持したまま、大規模並列ハードウェア上で実行されるプログラミング言語
- PythonやHaskellのような表現力のある言語機能を提供する
- 高速なオブジェクト割り当て
- クロージャを持つ高階関数
- 制限のない再帰
- continuation
- CUDAのようにGPUなどの大規模並列ハードウェアで実行され、コア数に基づいてほぼ線形の高速化を目指す
- 並列実行のために次のものを直接書く必要がない
- スレッド生成
- ロック
- ミューテックス
- atomic
- ランタイムにはHVM2を使用する
現在の制約と注意点
- Bendはコア数に応じて性能を拡張することに焦点を当てており、10,000個以上の同時スレッドをサポートするよう設計されている
- 現行バージョンでは単一コア性能が低い可能性がある
- コード生成と最適化手法の発展により性能向上が見込まれる
- Windows対応はまだ作業中で、代替としてWSL2を利用できる
- GPU対応は現在NVIDIA GPUのみ対応している
インストールと実行方法
- LinuxとMacのどちらでもRustのインストールが必要
- C版のBendではGCCを使用し、READMEではGCC 12.x以下を推奨している
- CUDAランタイムを使うには、Linux向けのCUDA Toolkit 12.xのインストールが必要
- HVM2は
cargo install hvmでインストールし、Bendはcargo install bend-langでインストールする - Bendプログラムの実行コマンドは実行系ごとに分かれている
bend run <file.bend>: デフォルトでCインタプリタを使用、並列実行bend run-rs <file.bend>: Rustインタプリタを使用、逐次実行bend run-c <file.bend>: Cインタプリタを使用、並列実行bend run-cu <file.bend>: CUDAインタプリタを使用、大規模並列実行
gen-cとgen-cuを使ってスタンドアロンのC/CUDAファイルにコンパイルできる- コードジェネレータはまだ初期段階で、GCCやGHCのようなコンパイラほど成熟していない
-sフラグでreduction回数、実行時間、1秒あたりのinteraction数を確認できる
逐次加算と並列加算の例
- READMEの加算例では、
startからtargetまでの数値を足すコードを2つの方法で比較している - 逐次版は、
Sum(start + 1, target)の結果に現在のstartを足す構造- 次の計算は前の加算結果に依存する
- 現在の計算が終わる前には次の段階へ進めないため、並列化できない
- 例では
Sum(1, 1_000_000)を呼び出し、Bendの数値の最大値をオーバーフローする可能性があるという注釈が含まれる
- 並列化可能な版は、範囲を半分に分けた後、左側と右側の合計を再帰的に計算する
(3 + 4)の計算は(1 + 2)の計算に依存しない- 2つの計算は同時に起こせるため、並列実行が可能
- Bendでは、コードが並列実行可能であれば実行コマンドを変更するだけで並列実行される
Bitonic Sorterの性能例
- READMEでは、不変ツリー回転で実装したbitonic sorterを速度例として示している
- このアルゴリズムはGPUで高速になりそうなタイプとは期待しにくいが、分割統治アプローチを使うことでBendが複数スレッドで実行する
- 明示的なスレッド生成やロック管理は不要
- ベンチマーク結果は次の通り
bend run-rs: CPU, Apple M3 Max, 12.15秒bend run-c: CPU, Apple M3 Max, 0.96秒bend run-cu: GPU, NVIDIA RTX 4090, 0.21秒
- 他のアルゴリズムはexamples folderで確認できる
参考資料
- Bendの基盤技術はHVM2のpaperで確認できる
- 公式ドキュメントは作業中で、より深い説明はGUIDE.mdにある
- 機能一覧はFEATURES.mdで確認できる
- BendはHigherOrderCOが開発している
1件のコメント
Hacker Newsのコメント
sumの例を純粋な Pythonに移植してみたところ、pypy3ではシングルスレッドで 4.478 秒、Python 3.12 では 1 分 42.148 秒かかりました。一方で Bend のシングルスレッド版は、私のノート PC では 42 分経っても実行中で、メモリを 6GB 使っているにもかかわらず終わりませんでした。環境は 12th Gen Intel(R) Core(TM) i7-1270P、Ubuntu 24.04 です。
これほど単純な例でここまで遅いなら、複雑な処理ではどうなるのか期待しにくく、Mac/aarch64 以外の環境でテストや開発が行われているのか気になります。後で
-s引数を付けて再実行してみるつもりです。sumの例では、Bend が数値演算ごとに IC ノードを 2 つ割り当てるという大きな不利があり、Python にはそれがありません。HVM1 のように近いうちに回避できるようにする予定ですが、HVM2 にはまだ実装されていません。Bend の作業の大半は並列評価器を正しく作ることに費やされており、GPU 上でクロージャと制限のない再帰を実行するのは非常に困難でした。ようやくその部分を終えたところなので、細かな最適化にはほとんど労力をかけておらず、HVM2 のコード生成もまだひどい状態です。
Bitonic Sortの例のように、双方が同じ量の割り当てを行うケースと比較すれば、実際の性能をより公平に見られるはずです。HVM1 は単一コアで GHC より 3 倍遅い程度で、HVM2 もそう遠くないうちにその水準に到達できると考えています。「まだ悪いが良くなる」という言い方が期待外れに聞こえるかもしれないことは理解しています。それでも基盤は整ったので、細かな最適化は最も容易な部分であり、ここから性能は大きく向上すると信じています。
この言語は計算量の多い GPU アプリケーションを狙っており、まだ初期段階です。再帰は目標とするアプリケーションではなく、関連するベンチマークとは見なしにくいと思います。
ISPC が CPU スレッドごとに 32 個の関数呼び出しを同時に実行するようコンパイルできるのと似ています。たとえば AVX512 で 16 ビットデータを使うと、32 コア × コアあたり SMT スレッド 2 本 × コンパイラ実行 32 個で、2048 個の実行が同時に進むことがあります。
Python らしい実装なら、ループと変更可能な状態を使っていたはずです。
+0はなぜ必要なのか分かりません。何もしない演算ではないのですか？このスレッドには否定的な反応が多いですが、ここまで作り上げただけでも作者にkudosを送りたいです。
似たプロジェクトとしては Futhark くらいしか知りませんが、Haskell 風の構文なので、C/C++/Python/JS/Java などに慣れた一般的な開発者にはかなり難解かもしれません。
一番残念なのは、Futhark と違って CUDA やマルチコアだけを対象にしている点です。Futhark は OpenCL、CUDA、ISPC、HIP、単一コア CPU、マルチコア CPU を対象にできます。他の人たちが指摘している性能問題は十分解決可能だと思います。
短い例: https://github.com/m4rs-mt/ILGPU/blob/master/Samples/SimpleM...
インライン PTX アセンブリのような高度な機能にも対応しています: https://github.com/m4rs-mt/ILGPU/blob/master/Samples/InlineP...
NVIDIA も CUDA で Haskell、.NET、Java、Julia の派生版を支援してきましたし、Python JIT もあり、Mojo 側とも協力中です。
1995 年から Ada の設計者として活動している Tucker Taft が作ったもので、ParaSail の並列機能の一部は Ada 2022 に取り込まれています。
OP は最近 HN に上がったものの中でも最もクールなものを持ってきているのに、明らかにまだ初期バージョンであるにもかかわらず、長い批判ばかり受けているようで残念です。
一方で批判は、正しく当てる方法は限られているのに、外し方は多いため、際限なく多様になり得ます。だから肯定的なコメントは数件だけで、ほとんどが批判や「これもやってほしい」に見えるようになります。特定の個人のせいというより、今日の技術者文化はそういう傾向に近いのです。
人々が残酷な真実を拍手の裏に隠すだけなら、世界は崩壊してしまいます。
批判も、アイデアやアプローチに関心を持って参加しているという意味なので、しばしば肯定的なシグナルになります。
しかし、誤解を招いたり、根拠が弱かったり、虚偽の主張をしたりするプロジェクトを批判することも、良い社会的規範です。そうした主張を減らすことにつながるからです。
理解しにくいものはしばしば脅威に感じられ、批判は脅威に対するよくある反応であり、最も少ない理解でも可能な応答の仕方です。
ホームページが本当によく作られている。何をするものなのかがすぐ明確に分かる
「コンビネータ」を扱う人たちは、たいてい怖そうな専門用語をたくさん使いたがるものだが、OP はツールの背後にあるシンプルなアイデアを実際に見せている。最後の細部まで見せながら肝心の何が起きているのかは言わない、という学術界的なアプローチの逆なので良い。こういうやり方がもっと増えるべき
理論的には格好よく、価値提案も理解できるが、正直これが実際に関係のあるツールになるとは思えない
第一印象と論文をざっと見た後のメモ。ごく初期のソフトウェアだという点は分かっている
Bend は非常に制限された DSL のように見える。FFI がなく、生のバッファとやり取りする方法もなく、24ビット浮動小数点形式も奇妙
IC が主流でないのには理由がある。性能は今後もひどいままである可能性が高く、グラフ走査はハードウェアと相性が良くない
最適簡約という前提は有効だが、結局は並列化可能な形でカーネルを書く必要がある。つまりデータ依存があってはならず、再帰の使い方も考慮しなければならない
Bend/HVM のコードと同等の OMP/CUDA プログラムを直接比較する、真面目な例がない。実装の複雑さがどれだけ減り、性能がどの程度なのか評価しにくい
現実の高性能並列コンピューティングでは木構造はほとんどなく、配列が王様だ。メモリがハードウェアレベルで動作する物理的性質のためである。変更可能な連続メモリバッファで最もよく効くのはループだ。HVM がこれを実装するなら見守りたい
現状では外部データからほぼ完全に隔離されており、非常に遅く、ハードウェアの上に巨大な抽象化を載せた半熟の言語に見える。多段キャッシュ、Tensor Core、SIMD、アトミック演算といった機能も活用できていない
きつく聞こえたなら申し訳ないが、技術的実装と理論的背景はいまなお非常に興味深いと思っている。ただ、まだ現実世界での有用性には納得できていない
FFI はすでに実装済みだが、まだ公開していない。グラフィックスレンダリングと一緒に出したいからで、かなり格好いいものになると思う
Haskell/GHC もグラフや木を使っているが、実用的でないと言う人はいない。配列が王様なのはその通りだが、コンパイラ、型検査器、ソルバーなど、配列にうまく合わない現代的なアルゴリズムの多くが Haskell で実装されている
IC が速くない主な理由は、その上で低レベル最適化の作業をきちんと行った人がいなかったからだ。既存の実装はどれもひどく非効率で、私の作業もこれまでは GPU 上で正しく実行させることに時間を使ってきたため、そうなっている
まだループもないという話のように、解決策は単にループを追加することだ。そこに本質的な限界があると思っているなら驚くことになるだろう
HVM2 はついにスケール可能で正しいアルゴリズムになり、これから実際の低レベル性能を最適化する段階だ
Fast Multipole や Barnes-Hut アルゴリズムでは Morton 順序や H-index 順序を使い、O(n²) のペアワイズ演算をそれぞれ O(n)、O(n log n) に減らす。Barnes-Hut は天体物理でより一般的で、Fast Multipole は化学の分子動力学でよりよく見られる
10年前に CMU の並列アルゴリズムの授業である 15-210 を受けた。Moore の法則が限界にぶつかるにつれ、並列性がコンピューティングの未来になると説明され、その話に納得して試してみたくなった
しかし汎用並列プログラミングの選択肢は多くなかった。授業で使った SML でさえ並列ではなく、最後に拡張と CUDA を使うセクションがあったが、記憶では限定的だった
その後 Rust のおかげでマルチスレッディングを少し試せたし、Shadertoy のおかげでシェーダーで創造的な作業もできた。しかし GPU 上の汎用並列言語となると、自分で触ってみるのがとても楽しみだ
210 が気に入ったなら https://futhark-lang.org/ も気に入るかもしれない。ML 系の言語で、GPU にコンパイルされ、性能も良い
アイデアはとても素晴らしいが、私が何か見落としていない限り、非常に遅く見える
C++ で 0 から 2³⁰ まで足す単純なループを書いたところ、最適化なしの単一スレッドで私のノートPCでは 1.7 秒かかり、これは RTX 4090 上での Bend の性能と同程度だった。
-O3を付けるとループがベクトル化され、80ms 未満で実行される実際に割り当てを行う C プログラムと比較すれば、Bend は数スレッドだけでもより速い可能性が高い
Bend のコード生成はまだひどいが、これは低いところにぶら下がっている果実だ。作業の大半は、非常に難しい並列評価器を正しく作ることに費やされてきた
「信じてくれ」と言っているように聞こえるのは分かるが、プロシージャコンパイルやループ生成などを始めれば、単一スレッド性能はずっと良くなる。まだやっていないだけだ
実際、公開する前にもう少し待つべきだったのかもしれない
objdumpで確認してみるとよいそのループは符号付き整数オーバーフローを起こしており、C++ では未定義動作だ。コンパイラは合法的にどんな結果を出してもよい
これを避けるには
sumをunsignedとして宣言する必要がある。符号なし整数オーバーフローは明確に定義されており、最適化は依然として起きるが、少なくとも正しさは保証される-O3を付けてコンパイルすると、ループは完全に削除される: https://godbolt.org/z/M1rMY6qM9おそらく公平な比較ではないだろう
もちろん私も要点を見落としているかもしれない
作者にお祝いを言いたい。本当に素晴らしい仕事だ
正しい自動並列化を作るのは決して簡単なことではなく、十分に誇ってよい。今後プロジェクトがどう発展していくのか楽しみにしている
なぜこんなに否定的な反応が多いのか分からない。怒れる群衆が README の粗を探し、文章の文脈や意図を変えようとするボットのように見えた。
まともに読むのに2分も使わず、何時間も議論するのは無知で残酷だ。OP は1人プロジェクトでここまで来たのだから、このまま突き進んでほしい。
HVM2 が相互作用ネットを、たとえば SPIR-V にコンパイルするのか、それとも従来の HVM のように GPU 上で動くインタプリタなのか気になっていた。
以前、プログラムをできるだけ縮約してから入力は縮約しないという方式で、相互作用ネットを C にコンパイルし、全プログラム最適化のように扱ってみたことがある。シェーダー言語をターゲットにするのも、それほど難しくはなさそうだった。
リポジトリを見ると、HVM2 のネットを指定する低レベル IR 言語と、C/CUDA へのコンパイラを提供しているとある: https://github.com/HigherOrderCO/HVM
ただ、改めて見ると HVM2 CUDA ランタイムは、メモリ内のグラフを走査して縮約を適用するインタプリタのように見える: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
自分が言っているのは、相互作用ネットを走査してラムダ計算式に近い項を復元し、小さな断片として C に落とし、ランタイムオーバーヘッドを最小化する方式だ。
正直な動機は、Bend で ML ワークロードのような場面で手書きの GPU カーネルに勝つのは難しい、という点にある。理論上、HVM は計算カーネル同士をつなぎ、実行順序を並列化する接着剤の役割を果たせるが、そのためには優れた FFI が必要になる。
相互作用ネットは FFI 境界を越えて変換するのが難しいが、FFI 計算カーネルノードを相互作用ネットワークの中に置き、そのネットを C にコンパイルすれば、変換オーバーヘッドなしに妥当な FFI を取り戻せる。
もう一つの選択肢は HVM をハードウェアで実装することで、余っている FPGA で少し触っているところだ。
SPIR-V を直接ターゲットにはしていないが、目標にはしている。
C コンパイラは期待どおりの高速化、つまり3〜4倍、まもなくそれ以上を出しているが、CUDA ランタイムは非コンパイル版と比べて大きな高速化は得られなかった。
原因はワープ分岐だと見ている。コンパイルされていないプロシージャでは、すべての関数呼び出しを1つの「汎用」インタプリタ風の関数展開器にまとめることができ、ワープスレッドが分岐なしで縮約できる。今後この部分をさらに深く研究する予定だ。