Spice: Zigにおけるサブナノ秒オーバーヘッドの高精細並列処理技術
(github.com/judofyr)Spice: Sub-nanosecond Overheadの並列処理
Spiceは、Zigで heartbeat scheduling を用いて非常に効率的な並列処理を実現します。
- サブナノ秒オーバーヘッド: 関数に並列処理機能を追加しても、発生するオーバーヘッドは1ナノ秒未満です
- 競合なし: スレッド同士が同じ作業を奪い合いません。システムにスレッドを追加しても、プログラムが遅くなりません
性能比較
- Rayon (Rust): 4スレッドで約15nsのオーバーヘッドが発生。16スレッドで約14倍の高速化
- Spice (Zig): 16スレッドで約11倍の高速化。オーバーヘッドが低く、ベースライン性能とほぼ同等
小さなツリーでの性能
- 小さなツリー: プログラム全体の実行時間は1.56マイクロ秒。スレッドを増やすほど性能が低下
- 並列処理の一般論: 十分な作業量がなければ、並列化する価値はない
Spiceの目標
- 目標: 並列処理を追加してもプログラムが遅くならないようにすること
- 短い実行時間: 実行時間が短いとマルチスレッドは機能しない。追加されたスレッドは待機状態に移行する
Spiceの使い方
const spice = @import("spice");
fn sum(t: *spice.Task, node: *const Node) i64 {
var res: i64 = node.val;
if (node.left) |left_child| {
if (node.right) |right_child| {
var fut = spice.Future(*const Node, i64).init();
fut.fork(t, sum, right_child);
res += t.call(i64, sum, left_child);
if (fut.join(t)) |val| {
res += val;
} else {
res += t.call(i64, sum, right_child);
}
return res;
}
res += t.call(i64, sum, left_child);
}
if (node.right) |right_child| {
res += t.call(i64, sum, right_child);
}
return res;
}
- すべての並列関数は引数として task を受け取る必要があります
- 関数を直接呼び出さず、
t.callを使う必要があります forkを呼び出して、別スレッドで作業を設定します- 関数はそれ自体で意味のある処理を行う必要があります
joinを呼び出して、別スレッドの作業完了を待ちますjoinがnullを返した場合は、その作業を自分で実行する必要があります
Work-stealingと非効率性
- Work-stealing: 各スレッドは自身のローカル作業キューを持ちます。キューが空になると、他のスレッドの作業を奪います
- 非効率性: 動的ディスパッチ、ローカルでない作業キュー、スピンロック
実装の詳細
静的ディスパッチ最適化
- コードブロックの並列実行:
forkとjoinを使ってコードブロックを並列実行します - 重複排除: コードブロックが別スレッドで実行されない場合は、逐次実行されます
低オーバーヘッドのハートビート信号
- ハートビートスケジューリング: 100マイクロ秒ごとにローカル作業キューを確認し、作業を他のスレッドへ送ります
- 効率性: ハートビートが発生しないときでも、関数が効率的に動作する必要があります
グローバルミューテックス
- グローバルミューテックスの使用: グローバルミューテックスは、競合がない場合には問題ありません
分岐のない双方向リンクリスト
- 双方向リンクリスト: 作業キューを管理するために使われます。分岐なしで動作します
スタック使用の最小化
- スタック使用の最適化:
Futureの状態を最小限にして、スタック使用量を減らします
レジスタによる値の受け渡し
- レジスタの使用:
Task構造体のフィールドをレジスタ経由で渡し、性能を最適化します
ベンチマーク
- ベンチマーク: 初期開発は単一のベンチマークを中心に進められました
謝辞
- ハートビートスケジューリング研究: 複数の研究論文に基づいて開発されました
制約
- 制約条件: 誤って使用すると、奇妙な挙動が発生する可能性があります
- テスト不足: テストカバレッジが不十分です
- 配列/スライス対応不足: 配列やスライスに対する並列処理のサポートが不十分です
- ドキュメント不足: 使い方に関するドキュメントが不足しています
- 追加ベンチマーク不足: さらなるベンチマークが必要です
- エラー処理: エラー処理に対する考慮が不足しています
- ReleaseSafeテスト不足: ReleaseSafeモードでのテストが必要です
FAQ
- 名前の由来: 非常に細粒度な並列処理を意味します
- Zigで実装された理由: さまざまな言語で実装可能です
- Rustでの安全な並列処理: Rustの厳格なセマンティクスのため、初期アイデアの探索が困難です
GN⁺のまとめ
- Spiceは、Zigで非常に効率的な並列処理を提供する研究プロジェクトです
- サブナノ秒オーバーヘッド と 競合のない 並列処理によって性能を最大化します
- ハートビートスケジューリング により、作業を効率的に分配します
- 制約条件 や テスト不足 などの限界があります
- Rust のような他言語でも、同様のアプローチを探る価値があります
1件のコメント
Hacker Newsの意見
この実装は最近の研究である「heartbeat scheduling」に基づいており、並列性生成のオーバーヘッドを分散させることで、動的な自動細粒度化制御を実現している
コードの詳細までは読んでいないが、「sub-nanosecond overhead」は誤解を招く表現であり、マーケティング用語だと思う
この分野には詳しくないが、提示されている並行性モデルは気に入った
興味深い研究成果であり、コードだけでなく、優れた論旨とよく書かれたドキュメントもある
プロジェクトの制限事項一覧:
説明によると、この実装ではワーカーがナノ秒レベルのレイテンシを達成するためにビジーウェイトを使っている
タスクの生産者がビジーウェイトなしで消費者を起こす、より高速な方法があるのか気になる
興味深く、優れた論文群とつながっている
協調的スケジューリングは、優れたメトリクスを持つ多くのパターンの基盤になっている
素晴らしい
ベンチマーク関連のREADMEも参照: