Spice: Zigでサブナノ秒オーバーヘッドを目指す高粒度並列処理技術

 (github.com/judofyr)
2 ポイント 投稿者 GN⁺ 2024-08-14 | 1件のコメント | WhatsAppで共有
  • Spiceは、Zigでheartbeat schedulingを使い、関数に並列実行の可能性を加えてもオーバーヘッドを1ns未満に抑えることを目指す研究プロジェクト
  • 中核設計は、forkで別スレッドが処理できる仕事を示しつつ、どのスレッドも取らなければjoinで現在のスレッドが自分で実行するフォールバック構造
  • 1億ノードの二分木合計ベンチマークでは、Rayonは1スレッド時のオーバーヘッドが約15nsで、16スレッドではbaseline比で約4.5倍だった一方、Spiceは16スレッドでbaseline比ほぼそのまま約11倍の高速化を得た
  • 1000ノードのように実行時間が極めて短いタスクでは、Rayonは32スレッドで合計60倍遅くなる例があったが、Spiceは並列化が不要だと判断すると追加スレッドを休止させ、マルチスレッド処理を開始しない
  • 現在の実装はテスト、ドキュメント、配列・スライス対応、追加ベンチマークが不足しており、@panicの使用も多く、作者は本番利用前に多くの制約を理解すべきだとしている

Spiceが解決しようとしている問題

  • Spiceは、Zigで非常に細粒度な並列処理を低オーバーヘッドで実現しようとするプロジェクト
  • 目標は、並列化を追加したときにプログラムが遅くならないかを利用者が常に心配しなくてよくすること
  • 性能を最大化するには精緻なベンチマークが必要だが、Spiceは一般に並列性を追加しても実質的なオーバーヘッドがほとんどないよう設計されている
  • このプロジェクトは主に研究プロジェクトであり、本番利用を考えるなら先に制約を確認すべき
  • 2024年9月の更新として、このアイデアをRustに移植した Chili が紹介されている

使い方と中核API

  • Spiceの並列関数は、調停に使うための *spice.Task を引数に取る
  • 再帰呼び出しや並列化可能な関数呼び出しは直接呼ばず、t.call を通して呼ぶ必要がある
  • fork は、別スレッドが実行可能な仕事を設定する
  • 関数は fork の後、自分でも意味のある仕事を直接行う必要がある
  • join は、別スレッドが仕事を完了したか待つが、null を返す場合がある
    • null は、その仕事を別スレッドが取得しなかったことを示す
    • この場合、現在のスレッドがその仕事を自分で実行しなければならない

「すべての仕事がキューから来るわけではない」という設計

  • Spiceの中核アイデアは、すべての仕事がキューから始まるわけではないという点
  • fork は別スレッドが実行できる仕事があることを知らせるが、他スレッドが忙しければ元の逐次実行と同じように現在のスレッドが処理する
  • 並列実行の可能性がないとき、hot pathでSpiceが行うのはキューへのpush/pop程度で、キュー項目の中身を実際に見ることはない
  • 他スレッドとの実際の調停は、固定間隔のheartbeatで発生する
    • 約100マイクロ秒ごとにスレッドが現在の作業キューを確認する
    • キュー先頭の仕事を待機中の別スレッドへ渡す
    • heartbeat頻度が低いため、数百ns使っても全体オーバーヘッドは小さい

Rayonベンチマークとの比較

  • 1億ノードの二分木合計は、実計算が非常に速いため並列フレームワークのオーバーヘッドが大きく表れる例
  • Rustの Rayon とSpiceは、どちらも読みやすく推論しやすいfork/join APIとして比較されている
  • Rayonのベンチマークでは、オーバーヘッドは約15nsと測定された
    • 7.48nsから22.99nsへ増加
    • 4スレッドでは逐次性能に戻る水準だが、CPUは4倍使う
    • 16スレッドではRayon自身の基準で約14倍高速化、baseline比では約4.5倍高速化
  • Spiceは、1スレッドから16スレッドに増やしたとき約11倍の高速化を示した
    • Rayonよりスケーリングはやや悪いが、低オーバーヘッドのおかげでbaseline比の高速化もほぼそのまま維持される
  • ベンチマークはGoogle Cloudの c4-standard-16 インスタンス、16コア環境で実行された
  • Zig baselineがRust baselineより約2倍速い理由は明確ではない
    • compiled assembly によると、Rustはスタックにレジスタを5個保存し、Zigは3個保存している

小さなタスクでの挙動

  • 1000ノードの二分木合計は、総実行時間が数マイクロ秒規模の非常に短いタスク
  • Rayonはこの場合、オーバーヘッドが約19nsとさらに高く現れ、スレッドを増やすほど性能が悪化した
  • 16コアマシンで32スレッドを使うと、総実行時間が60倍遅くなった
    • 32コアマシンでも同じ減速が起こると断定はできない
    • それでもこのスケーリング挙動は懸念されると評価されている
  • 従来の並列化判断は、「十分な仕事があるときにだけ価値がある」という形になりがち
    • 「十分な仕事」の基準は、入力ごとのベンチマークで把握する必要があるかもしれない
    • 二分木のようにルートだけ見ても全体サイズが分からない入力では、小さな仕事かどうか判断しにくい
    • 仕事量の90%が小さな入力なら、極端な減速が問題になりうる
    • プログラムが進化すると、十分な仕事の基準も変わる
  • Spiceは同じ1000ノードのケースでは、実行時間が短すぎると判断してマルチスレッド処理を開始しない
    • 追加スレッドは眠ったままになる
    • コアは他のプログラム実行に使える

work-stealingとSpiceの違い

  • Spiceはfork/joinモデルを提供し、このモデルは通常 work-stealing で実装される
  • 一般的なwork-stealingでは、各スレッドがローカル作業キューを持ち、キューが空になると他スレッドのキュー末尾から仕事を盗む
  • work-stealingの非効率は3点に整理できる
    • すべての仕事が汎用的な「動的関数呼び出し」形式になり、動的ディスパッチのコストが生じる
    • ローカルキューが実際には全スレッドから盗まれうるキューなので、アトミック操作が必要になる
    • キュー競合時にspinningが発生し、条件によっては10〜100倍遅くなることがある
  • Spiceはこれらの非効率を直接減らす
    • 作業キューの動的ディスパッチは、他スレッドへ仕事を送るときにだけ使う
    • 単一スレッド内で行われる仕事は通常の関数呼び出しを使う
    • 作業キューへのpushはスタックポインタ、現在のスタックフレーム、レジスタ保存で処理し、他スレッドと同期しない
    • wait() 呼び出しなしに回り続ける while ループがなく、spinningがない

実装の詳細

  • 静的ディスパッチ最適化

    • Spiceは、fork した仕事の大半は他スレッドに取得されないと見なし、関数内部にそのコード実行経路を重複配置する
    • 仕事が他スレッドで実行されなければ、プログラムは予測しやすい分岐が少し増えただけの逐次版のように動作する
    • この構造はインライン化などのコード最適化やCPU実行に有利

  • 低オーバーヘッドなheartbeatシグナル

    • heartbeat schedulingは、スケジューリングをローカルで低頻度に行う
    • 約100マイクロ秒ごとにスレッドがローカル作業キューを見て、別スレッドに仕事を送る
    • 100マイクロ秒ごとに100ns使っても、全体オーバーヘッドは0.1%程度
    • OSシグナルの代わりに、協調的に tick() を呼び出す方式を取る
      • t.call ヘルパー使用時に tick() が自動で呼ばれる
      • 別のheartbeatスレッドが、各スレッドのatomic heartbeat値を定期的に false から true に切り替える
      • tick() はこの値を読み、true のときheartbeatコードを実行する
    • heartbeat関数は cold としてマークされる必要があり、そうでないとオーバーヘッドは大幅に増える

  • 競合のないグローバルmutex

    • Spiceのスレッドプールには、複数箇所でロックされる単一のmutexがある
    • グローバルmutexは、スレッドが実際にblockするときに問題になる
    • Spiceではheartbeatのため、通常は1つのスレッドだけがheartbeatを実行する
    • ロック保持中にユーザーコードは実行されず、定数時間で終わる単純なメモリ読み書きだけを保護する

  • 分岐なしの双方向連結リスト

    • Spiceは作業キュー追跡に双方向連結リストを使う
    • fork() は末尾にappendし、join() はまだ残っていれば末尾からpopし、バックグラウンドworkerへ送るときは先頭からpopする
    • 一般的なappendでは、空リストかどうかを調べる条件分岐が必要
    • Spiceは常に存在するsentinel headノードを置いてリストを空でなくし、push/popを分岐なしで行う

  • スタック使用の最小化

    • Future はqueuedまたはexecuting状態を持つ
    • heartbeatはqueuedなfutureをexecutingへ切り替える
    • executing状態に必要な追加状態は別のpool-allocated構造体に置き、queued futureのスタック使用量を減らす
    • prev_or_null の先頭フィールドが null かどうかでqueued/executing状態を区別する、手動のtagged unionのような形を使う

  • レジスタでの値受け渡し

    • Task はowning workerポインタと作業キューtailポインタを持つ
    • LLVMはstruct受け渡しをスタック経由にしがちなため、Spiceは worker と job_tail を別引数で受け取る callWithContext を定義している
    • この関数は常にinlineされるよう呼び出され、ポインタ引数がレジスタで渡されるようにしている

研究的背景と関連研究

現在の制約

  • Spiceは、誤って使うと荒っぽい挙動になる可能性がある
    • 特に fork と join の使い方に敏感
    • compile-time検査、debug-mode assertion、API変更で改善すべき
  • 並行コードが多いにもかかわらず、テストカバレッジは0
  • 細粒度並列処理の一般的な用途である、配列・スライスの各要素処理に対するネイティブ対応がない
  • 使い方を説明する良いドキュメントが不足している
  • 現在は単一の小さなベンチマーク中心でしか試されていない
    • そのベンチマークは代表性があるはずだとされるが、結果検証には追加ベンチマークが必要
  • エラー処理で @panic を多用している
    • 適切なZigライブラリと見なすには、エラーケース処理をもっと考慮する必要がある
  • Zigの ReleaseSafe でどの程度うまく動くか、追加ベンチマークとテストが必要
  • コードベース全体は約500行で、作者は時間不足のため、現時点でSpiceを積極的に改善する開発計画はない
  • forkや他言語での再実装による改善は推奨されている

関連記事

1件のコメント

 
GN⁺ 2024-08-14
Hacker News の意見

  • この実装は、近年の研究の流れであるハートビートスケジューリングに基づくもので、並列性を生成するコストを償却し、一種の動的で自動的な作業単位制御を実現している
    関連論文:
    (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
    (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

    • これは本当に興味深い。Spice を書いた時点では、前の2本の論文しか知らなかった
      後ろの2本もぜひ読んでみるつもり

  • コードを詳しく読んだわけではないが、1ナノ秒未満のオーバーヘッドという表現は誤解を招くマーケティング文句のように見える
    一見すると、スレッド数が「タスク」数よりはるかに少ない状況で計算した、複雑な「タスクあたり時間」の測定値に見える

    • 作者です
      一部の人がその表現に否定的に反応するだろうとは思っていましたが、意図は Spice と Rayon をいつ、どのように使うべきかをより正確に理解してもらうことです
      ベンチマーク文書を読んでみることをおすすめします: https://github.com/judofyr/spice/blob/main/bench/README.md
      通常、並列コードを比較するときは、逐次/基準実装と、すべてのスレッド（16個）を使う並列実装だけを比較します。100M のケースでは Rayon の数値は逐次版が 7.48ns、Rayon が 1.64ns で、そうすると「Rayon はこの問題では 4.5倍速かったが、16スレッドを使っているので割に合わない」と結論づけて終わりがちです。その指摘は正しいのですが、別のタイプの問題にどう適用すればいいかは学びにくいです
      同じベンチマークをさまざまなスレッド数で走らせると、より興味深い点が見えてきます。Rayon のスケジューラは別スレッドに作業を分けるのはかなり得意ですが、タスク実行メカニズム全体には約15ns のオーバーヘッドがあります。このプログラムがまったく役に立たない例であっても、以後に適用できる事実は学べます。Rayon を使うなら、最小の作業単位はおおむね7ns より大きい必要がある可能性が高いということです。ただし、全体スループットを犠牲にしてでも全体のレイテンシを下げることのほうが重要な場合は例外です
      Rayon のドキュメントは数値を示さず、「概念的には join() 呼び出しは2つのスレッドを生成してそれぞれ1つのクロージャを実行するのに似ているが、実装はかなり異なり、非常に低いオーバーヘッドを持つ」とだけ述べています: https://docs.rs/rayon/latest/rayon/fn.join.html
      もし誤解を招きたかったのなら、「Spice は10倍の高速化で、Rayon は4.5倍だから、Spice は Rayon より2倍速い」と言っていたでしょう
    • 「1ナノ秒未満のオーバーヘッド」が誤解を招くマーケティング文句になるには、1スレッドの Spice - 非並列の基準実装が 1ns より大きくなければならない
      テスト結果はその主張を裏付けている: https://github.com/judofyr/spice/tree/main/bench
    • これも引用されているRayon の生態的な位置づけと同じではないかと思う
      数千〜数百万個のタスクを処理する必要があり、数十コアの範囲でできるだけ並列化したく、スケジューリングのオーバーヘッドに食われたくないので、タスクあたりのオーバーヘッドを気にする構造だ
    • 昨日 Reddit に上がっていたとき、ベンチマークについて懸念を示した
      ベンチマークは呼び出しあたり0.36ns のオーバーヘッドを主張しているが、計算関数しか含んでいない。スケジューリングを行う2つ目のスレッドがあるが、オーバーヘッドの数値には含まれていない。ハイパースレッディング対応の8コア、つまり16スレッドのマシンで走らせたものに見え、3GHz と仮定すると文字どおり1サイクルのオーバーヘッドということになる
      追加スレッドごとにロック競合のためオーバーヘッドが増える。16スレッドでは 3.6ns と10倍に増えている。推測だが、そうだとすると 0.36ns のオーバーヘッドには競合のないロックが含まれているという意味になるが、それは不可能だ。ベンチマークデータにはほかにも奇妙な点がある。実際に何を測っているのか私が理解できていないのか、ベンチマークコードにバグがあるのかもしれない
      値をすべて掛け合わせると、ミリ秒単位で時間を測っているように見える。実行時間が計算され、ミリ秒に変換されるときに整数に落ちている。普通、ベンチマーカーはこれより良い精度を使うのでは？ time prog だけを使っていてデータが非常に汚いか、この目的にはまったく役に立たない指標を選んでいるのかもしれない
    • README を読むと、タイトルの主張が正確に何を意味するのかが非常に精密に説明されていると思う
      誤解の余地がまったくないタイトルなどなく、このタイトルは十分だ。私が受け取ったのは、ある測定基準において極めて低いレイテンシを持つライブラリという程度で、その測定基準は README で確認できた。かなり明確だ

  • この分野にそれほど詳しいわけではないが、ここで提示されている並行性モデルは気に入った
    README もとてもよく書かれていて、読むだけで何が起きているのか感覚がつかめる。ただ、いくつかの箇所では首をかしげた。幸いコードはかなり読みやすい

    • Debug モードで zig build でビルドすると Baseline,3.92809172、Spice 1 thread,19.1012624 になった
      ReleaseSafe モードで zig build --release=safe でビルドすると Baseline,3.264224280000001、Spice 1 thread,3.78043278 になった
      つまり Spice はリリースビルドでないと性能低下がかなり大きい。基準実装は Zig の Debug ビルドモードでも同程度には遅くならない
      使用バージョンは zig 0.13.0

  • 興味深い研究的な取り組みで、コードそのものだけでなく判断根拠も良く、ドキュメントもよく書かれている
    2018年のハートビートスケジューリング論文も読む価値がある: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

  • プロジェクトの制限事項一覧: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

    • このプロジェクトは素晴らしく、作者が時間をかけて動くものにし、HN コミュニティに共有した点は大いに称賛されるべきだ
      HN は概して過度に批判的、あるいは悲観的な反応で知られる場でもある
      作者が自分のプロジェクトの限界を認めている点も良く、そのおかげでよくある冷笑の大半を先回りして防いでいる
      「テスト不足: Spice には難しい並行処理コードが多いが、テストカバレッジは 0 だ。Spice を重要な作業に責任を持って使うには改善が必要だ」という部分について、重要な作業の実行正確性をテストすることとは別に、難しい並行処理コードを実装したライブラリなら、少なくとも回帰テストはあるべきだと思う
      エンドユーザーの立場からすると、今日動いている機能が明日、微妙で厄介なリグレッションによって壊れないという保証は何なのか気になる
      SQLite は純粋な C ソースコードよりもテストコードとテストスクリプトが 590倍 多い https://www.sqlite.org/testing.html。安定性と移植性に加えて、この点も SQLite が世界中で事実上の標準組み込みデータベースになった複数の理由の一つだ
      無理にリンゴとオレンジを比べる例ではあるが、一般的な要点はなお有効だ。回帰テストはプロジェクトの安定性と信頼を生む
      私の職場では、基本的な回帰テストをどうしても後回しにする必要がある場合、たいてい同じエピック内にフォローアップチケットを作り、機能／エピックのリリース前には少なくとも書くようにしている

  • 説明によると、ナノ秒レベルのレイテンシを得るためにワーカーでビジーウェイトを使っている
    タスクが数万個ある大規模アプリケーションで、ビジーウェイトがどれほど現実的なのか気になる。タスクがスレッドベースではなく非同期なら、実行器のスレッドプールサイズ N 分の待機者しかいないので可能かもしれない。いずれにせよ、この構造はエネルギー消費がより高くなるはずだ
    関連して、タスクの生産者がビジーウェイトなしで消費者をもっと速く起こす方法があるのか、昔から気になっていた。たとえば生産者のタイムスライス内で消費者を実行する方式が可能かどうかを考えたことがある
    さらに関連して、ユーザー空間の FUTEX_WAKE 操作が可能になり、消費者を起こすコストを通常の半分、つまり消費者側のコストだけに減らせるのではないかとも気になる

  • すっきりしていて、良い論文もリンクされている
    ただし比較対象が OpenMP タスクだったらよかった。Rayon は少し遅いという評判を聞いたことがある

  • 協調的スケジューリングは、優れた指標を出す多くのパターンの基盤だ

    • ただし、タスク同士が互いに譲るという意味での協調的スケジューリングではない
      主に一部のタスクを他のスレッドに渡せるよう協調する方式で、常に行われるわけでもなく、ハートビートごとに1回だけ起きる。スケジューリングがまれにしか発生しないため、償却コストが低い

  • bench 配下の README も参考になる: https://github.com/judofyr/spice/blob/main/bench/README.md