# タスク並列フレームワーク ## 定義 タスク並列フレームワークとは、計算を**タスク**(自律的に実行可能な小単位)に分解し、それらを分散クラスタ上で並列・依存順に実行するソフトウェア基盤である。フューチャ(future)とデータ依存を基本プリミティブとして持ち、計算グラフの動的構築・スケジューリング・耐障害性を担う。 強化学習(RL)・エージェント型 AI・超並列シミュレーションの台頭により、「毎秒 100 万件超のタスクをミリ秒以下のレイテンシで実行する」という要件が顕在化した。 ## 主要システムの比較 | システム | モデル | 特徴 | 限界 | |---|---|---|---| | MapReduce / Spark | BSP データフロー | 豊富な API・straggler 緩和 | 静的 DAG 前提、細粒度タスクに高オーバーヘッド | | CIEL | 動的タスクグラフ | 血統耐障害性 | アクター抽象なし、中央集権スケジューラ | | Dask | 動的タスクグラフ + Python 統合 | Python 親和性 | 中央集権スケジューラで 3K tasks/s 上限 | | Ray | 動的タスクグラフ + アクター統合 | 1.8M tasks/s、タスク+アクター統合 | 汎用ゆえ特化最適化に限界 | | TensorFlow / MXNet | 静的計算グラフ | GPU 最適化 | 動的グラフ変更・シミュレーション統合が困難 | ## 横断的知見 - **BSP 静的 DAG の原点としての MapReduce**: 本表の「MapReduce / Spark」行が指す BSP データフローモデルの起源は [[@2004__OSDI__MapReduce - Simplified Data Processing on Large Clusters]](2004)である。M 個の map タスクと R 個の reduce タスクという静的な2フェーズ DAG を master が O(M+R) で中央集権的にスケジューリングする設計は、Ray(2018)が乗り越えようとした「中央スケジューラへの状態集中によるオーバーヘッド」の直接の前身にあたる。MapReduce の master は状態を O(M×R) 保持し(1タスクペアあたり約1バイト)、実運用上限は M=200,000・R=5,000・worker 2,000台程度に留まる。Ray の GCS 分離はこの中央集権ボトルネックを解消する後続の設計判断として位置づけられる - **耐障害性戦略の分岐点: 再実行 vs 血統**: MapReduce は「完了済み map タスクの出力はローカルディスクにあり、worker 故障で消える」という前提のもとで**タスク全体の再実行**を耐障害性の主機構とする(reduce タスクはグローバルファイルシステム(GFS)保存のため再実行不要)。これは Spark RDD 以降の**血統(lineage)ベース**再計算の直接の起源であり、Ray の血統管理もこの系譜にある。ただし MapReduce は血統グラフを明示的に持たず、タスク単位の全再実行のみをサポートする点で、Spark/Ray の細粒度な部分再計算より粗い - **straggler 緩和の起源としてのバックアップタスク**: MapReduce の「完了間近のタスクにバックアップ実行を投入する」機構(sort ベンチマークで44%の時間短縮効果を実測)は、eager scheduling(Charlotte System 由来)を発展させたものであり、Ray を含む後続の動的タスクグラフ系フレームワークが引き継ぐ straggler 対策の起点である。MapReduce はこれを静的 DAG・固定粒度タスクの枠内で実現しているのに対し、Ray は動的タスクグラフの中でより柔軟な冗長実行を可能にする ## 未解決の問い - 超大規模 LLM 訓練(数千 GPU・数兆パラメータ)ではタスク粒度の管理コストが問題になるか? Ray 上の FSDP/Megatron-LM 実装の実績は? - RL の密結合ループを前提とした設計と、バッチ型推論サービングを前提とした設計は将来的に収束するか? - GCS のシャード分散モデルで、グローバルスナップショットやトランザクション的な状態変更が必要な場合はどう扱うか? - MapReduce のタスク全体再実行モデルから Spark RDD の血統ベース部分再計算への移行は、具体的にどの設計変更(RDD の不変性・変換の遅延評価等)によって可能になったか? Spark の原論文を wiki に取り込んで検証する必要がある ## 関連 - [[動的タスクグラフ]] — Ray の計算モデル基盤 - [[グローバル制御ストア]] — Ray の制御状態管理 - [[分散スケジューラ]] — ボトムアップスケジューリング - [[LLM分散学習]] — 現代の超大規模訓練フレームワークへの展開 - [[GPUクラスタスケジューリング]] — タスク並列スケジューラとの交差領域 ## 出典 - [[@2018__OSDI__Ray A Distributed Framework for Emerging AI Applications]] — Ray の提案論文。タスク並列フレームワークの設計課題を RL 要件から導出し GCS + ボトムアップスケジューラで解決 - [[@2004__OSDI__MapReduce - Simplified Data Processing on Large Clusters]] — BSP データフローモデルの起源論文。静的 DAG・master 中央集権スケジューリング・タスク再実行による耐障害性・バックアップタスクによる straggler 緩和を提案