これ - funini.com

Grid Workflow Scheduler
高橋慧
Grid Schedulerとは
たくさんの逐次タスクを、グリッド上で
効率よく簡単に実行するシステム
タスク分配
ファイル転送
逐次のアプリケーションを書き換えるこ
となく、手軽にグリッドの能力を発揮で
きる
2
依存性のあるジョブへの対応
Workflowとは (特にScientific Workflow)
複数のタスクの実行手順を記述したもの
依存性を持ち、主にDAGによって表される
Workflowのスケジューリング
多くの考慮すべき条件
データの場所 (locality)
前のジョブの終了時間
賢い戦略が必要になる
3
実例1 : 自然言語処理
単語の用例別統計の抽出
パーズ後、キーワードごとの用例を抽出
Corpus
Parsed
Corpus
Phrases
(by words)
Concurrence
analysis
Corpus
Parsed
Corpus
Phrases
(by words)
Concurrence
analysis
Corpus
Parsed
Corpus
Phrases
(by words)
Concurrence
analysis
4
実例2 : 量子化学
FMO (Fragment Molecular Orbital)
部分に分けて量子シミュレーションを行う
部分計算後につなぎ合わせる「補正」を行
う
部分構造の結果を使い回せる
例えばCH3やOHなど
(但し扱うデータサイズは小さい)
5
[1]
スケジューリング戦略
スケジュラーの構成
集中的 : 一つのスケジュラーが全プロセッサを担当
階層的 : クラスタ単位でのスケジューリングを行い、
細かいタスク割り当ては各クラスタ
で行う
分散的 : 全体を統括するスケジュラーを持たない
リソースとタスクの割り当て (Planning
Scheme)
静的 : 実行前に決める
実行時間予測が必要
動的 : 実行中に決める
Matchmaking (性能・data localityなどを考慮)
[1] Srikumar Venugopal, et al., "A taxonomy of Data Grids for distributed data sharing,
完全に動的だと、賢い戦略は取りにくい
management,
and processing” ACM Computing Surveys (CSUR) archive Vol.38, Issue 1 (2006)
6
既存システム
Workflowに対応したスケジュラー
Condor DAGMan
Pegasus (DAGManの改良)
Triana, JOpera
GrADS
スケジュラーではないけど…
Dmake
DistCC
7
DAGMan[2] : 動的に配分
最も有名なGrid Scheduler
単一ジョブ : Condor-G
データ転送 : Stork
Workflow : DAGMan
DAGManは依存性を解析し、Condorと
Storkに(ばらばらに)ジョブを投入
Data Intensiveアプリでは、データ転送が
静的解析により、データ転送時にレプリカ
を作成し、高速化を図る研究もある (松岡研)
[2] http://www.cs.wisc.edu/condor/
8
Condorのスケジューリング
タスクをキューから一つずつ取り出し
Matchmakingによって実行ノードを決定
ノードの利用権限
使用可能ディスクサイズ
ノードの混み具合
計算元データの場所
9
Pegasus[3] : Jobをグループ化
ジョブをグループ化 (クラスタリング)
必要とするファイルによって分類
クラスタ(site)ごとにジョブを割り当て
密に結合したジョブは近いマシンに
実行時間予測はしない
静的分析
[3] Luiz Meyeret al., "Planning Spatial Workflows to Optimize Grid Performance”
SAC’06, April, 23-27, 2006, Dijon, France.
10
Pegasusでの性能改善
4手法を比較
ランダム
クラスタリング
キャッシュ
データのある場所
でジョブを実行
資源を10%に制限
タスクが多くなると
改善が少ない
Prescript : 同時にsubmitされるjob
11
GrADS[4] : 実行時間を予測
実行時間を予測
実行モデル + 小さなデータでの挙動
CPU・メモリ・ネットワーク資源の情報
浮動小数点演算の割合など
各タスクを実行するのにかかる時間を予測
スケジューリング
三つのヒューリスティクスから最良を選ぶ
静的に行う
[4] Anirban Mandal et.al, "Scheduling Strategies for Mapping Application
Workflows onto the Grid“, HPDC’05
12
実行時間の予測
静的に全マシンについて計算する
実行時間 = CPU時間 + データ転送時間
Rank(ci, rj) = w1 * eCost(ci, rj) + w2 * dCost(ci, rj)
eCost = (演算 + キャッシャミス) / クロック
dCost = sum(データサイズ * レイテンシ /バンド幅)
Rank(実行予測時間)
Task 1 Task 2
Task 3
Task 4
Resource 1
10
6
7
5
Resource 2
6
8
4
5
Resource 3
11
12
2
10
13
スケジューリング戦略
三つの戦略で別々に計算
Min-min :各タスクの最短コスト中、最もコ
ストが小さいものを採用
Max-min : 各タスクの最短コスト中、最も
コストが大きいものを採用
Sufferage : 各タスクについて、最短コスト
と二番目に短いコストの差が最も大きいも
のを採用
最短の総実行時間のものを採用
14
スケジューリング例
Rank
Task 1
Task 2
Task 3
Task 4
Resource 1
1
2
10
6
Min-min Resource 2
2
5
11
5
Resource 3
3
6
12
4
Rank
Task 1
Task 2
Task 3
Task 4
Resource 1
1
2
10
4
Min-max Resource 2
2
5
11
5
Resource 3
3
6
12
6
Rank
Task 1
Task 2
Task 3
Task 4
Resource 1
1
2
Sufferage Resource 2
Resource 3
2 2-1=1
5 5-2=3
10 Sufferage 4 Sufferage
11 11-10=1 5 5-4=1
3
6
12
Sufferage
Sufferage
6
15
実行結果
4手法を比較
HA : 本手法 (正確な予測 + 賢いマッピン
グ)
HC : ラフな予測 + 賢いマッピング
RN : ランダムスケジューリング
Mapped tasks Used nodes Exec. time Makespan
RA : 予測に基づいた重みを付けてランダ
ム
16
DistCC / DMake
一ファイルずつスケジュールするっぽい
all : main
echo "done"
main : main.o a.o b.o c.o d.o
gcc -o main main.o a.o b.o c.o d.o
a.o : a.c
gcc -c a.c
b.o : b.c
gcc -c b.c
…
newcamel
ermine
logosgw
rr56428@sx103> dmake
dmake: defaulting to parallel mode.
sx103.ecc.u-tokyo.ac.jp --> 1 job
cc -c main.c
sx103.ecc.u-tokyo.ac.jp --> 2 jobs
gcc -c a.c
sx103.ecc.u-tokyo.ac.jp --> 2 jobs
gcc -c b.c
sx103.ecc.u-tokyo.ac.jp --> 2 jobs
gcc -c c.c
sx103.ecc.u-tokyo.ac.jp --> 2 jobs
gcc -c d.c
sx103.ecc.u-tokyo.ac.jp --> 1 job
gcc -o main main.o a.o b.o c.o d.o
sx103.ecc.u-tokyo.ac.jp --> 1 job
echo "done"
sx103.ecc.u-tokyo.ac.jp --> Job output
echo "done"
done
17
まとめ?
実行時間の解析がポイント
動的に再計画するといい?
対象を絞らないと有り難みが無い
依存性が少ない
Data Intensiveでない
Dmakeの記述性は良いかも
18
Sun grid engine
19

Download Report