M1 Kenji KANEDA (SIG-PDS)

Presentation on theme: "M1 Kenji KANEDA (SIG-PDS)"— Presentation transcript:

1 M1 Kenji KANEDA (SIG-PDS)
Heuristics for Scheduling Parameter Sweep Application in Grid environments M1 Kenji KANEDA (SIG-PDS) 2019年4月12日 全体ミーティング発表

2 Outline of Presentation
Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2019年4月12日 全体ミーティング発表

3 Background (自分の研究) 複数のクラスタ、スーパーコンピュータが高速ネットワークによって結合 多数の計算資源を利用する機会の増大
しかし、FirewallやPrivate Networkなどの管理者が利用に制限を課している場合が多い 管理者の課す制限を自動的に迂回して、遠隔計算機の効率的かつ簡便な利用を目指す 2019年4月12日 全体ミーティング発表

4 Background 多数の異種環境上の計算機に分散計算を行いたい Software DSM MPI
parameter sweep application embarrassing parallel 多数の独立したタスクを多数の計算機にばら撒く 有名なツール 実際に使用されている？ UCSD IPDPS SC 2019年4月12日 全体ミーティング発表

5 AppLeS (Application Level Scheduling)
parameter sweep applicationのスケジューリング 対象 多大なparameter spaces 各々タスクは独立 いくつかのファイルを共有するのみ 資源は動的に利用率が変化 2019年4月12日 全体ミーティング発表

6 AppLeSの想定するシナリオ 計算 Server Information Service output check input input
User 2019年4月12日 全体ミーティング発表

7 Outline of Presentation
Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary & Future Work 2019年4月12日 全体ミーティング発表

8 Network Model (1/2) network topology クラスタ k個のクラスタと利用者のいるホストで構成
いくつかのホストと一つのストレージで構成 ストレージはクラスタ内で共有 クラスタと利用者のいるホストとを直接結ぶリンクは一つ クラスタ内のホスト間の通信は無視できる(比較的高速と仮定) 2019年4月12日 全体ミーティング発表

9 Network Model (2/2) 2019年4月12日 全体ミーティング発表

10 Task Model 各々独立なn個のタスク 想定するアプリケーション いくつかの入力ファイル 一つの出力ファイル
そのうちいくつかは複数のタスクで共有 一旦ストレージに蓄えられた入力ファイルは、全計算中常に蓄えられ続ける 一つの出力ファイル 一度ホストに割り当てられたタスクの移動は考えない 想定するアプリケーション MCell (micro-physiology application) 3-D Monte-Calro simulationを使用 入力ファイルは数百MBytes e.g. ) MCell, a micro-physiology application that uses 3-D Monte-Carlo simulation techniques to study molecular bi-chemical interaction within living cells hundres of MBytes of input 2019年4月12日 全体ミーティング発表

11 Outline of Presentation
Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2019年4月12日 全体ミーティング発表

12 Scheduling 目的 概要 makespanが最も短くなるようなタスクの割り当て adaptiveなスケジューリング
動的な資源の変化に対応する 概要 定期的にschedule()という関数を呼ぶ 2019年4月12日 全体ミーティング発表

13 Gantt Chartというネットワークリンクとホストの状態を表す図を利用
schedule() 次にschedule()を呼ぶタイミングを計算 現在実行中の計算、ファイル転送の終了時間を予測 未実行のタスク中からサブセットTを選択 T中のタスクをHeuristicに割り当てる 入力 Network Topology いままでに送信したinputファイルの位置 現在実行中のタスクやファイルのリスト Gantt Chartというネットワークリンクとホストの状態を表す図を利用 2019年4月12日 全体ミーティング発表

14 次にschedule()を呼ぶタイミング
頻繁なスケジューリングの計算を避けるため 資源の変化、予測の変化に適応するため 実行間隔の決定方法 定期的 偏向を考慮 予測実行時間と実際の実行時間の差を考慮し、ずれが多いときほど、頻繁に計算 2019年4月12日 全体ミーティング発表

15 実行終了時間の予測 (1/2) 概要 現在実行中のタスクの終了時間の予測 Gantt Chartにその状態を書き込む
Networks Links Link 1 Link 2 Cluster 1 Cluster 2 Host 1.1 Host 1.2 Host 2.1 Host 2.2 Host 2.3 送受信中のファイル 実行中のタスク 2019年4月12日 全体ミーティング発表

16 実行終了時間の予測 (2/2) 終了時間の予測方法 NWSなどのシステムから得られる情報をもとにHeuristicに予測
例）実行中のジョブの終了時間の予測 各々のジョブの計算時間は等しいと仮定 過去に実行した際にかかった実行時間とその時のCPU load 実行中のジョブのいままでの実行時間とそのCPU load 現在何%実行が終了したかを予測 2019年4月12日 全体ミーティング発表

17 未実行タスクのサブセットの選択 schedule()の計算時間の削減のため 選択方法
複数回呼び出すため一度に全てのタスクを割り当てる必要はない 選択方法 random maximizing data re-use 巨大な入力ファイルを共有するタスクの数が最大となる集合 2019年4月12日 全体ミーティング発表

18 未実行のタスクの割り当て 未実行のタスクをHeuristicにホストに割り当てる Gantt Chartを重複しないように埋めていく
Networks Links Cluster 1 Cluster 2 Host 1.1 Host 1.2 Host 2.1 Host 2.2 Host 2.3 Link 1 Link 1 Link 2 input ここでの予測も先ほどと同じように行っている output 2019年4月12日 全体ミーティング発表

19 Heuristics Algorithm (1/5) 用語、定義
Hjk=j thクラスタ中のk thホスト C（Ti,Hjk）=タスクTiのホストHjkでの実行時間 関数f(x)が最小となるときのxの値 argmaxも同様 2019年4月12日 全体ミーティング発表

20 Heuristics Algorithm (2/5) Min-min
Tiを最短時間で計算するホストHjkの選択 Hj,k jthクラスタ中のkthホスト C（Ti,Hjk）タスクTiのホストHj,kでの終了時間 argmin(C(Ti, Hjk)) は min argmaxも同様 T中で最短時間で終了するタスクTsの選択 2019年4月12日 全体ミーティング発表

21 Heuristics Algorithm (3/5) Max-min
Tiを最短時間で計算するホストHjkの選択 T中で計算に最も時間のかかるタスクTsの選択 2019年4月12日 全体ミーティング発表

22 Heuristics Algorithm (4/5) Sufferage
最適でないホストに割り当てたときの影響のでかいタスク 2019年4月12日 全体ミーティング発表

23 Heuristics Algorithm (5/5) XSufferage
ほとんどどのホストで計算するか、しないかという選択は、そのクラスタ内のストレージに共有する入力ファイルがあるかないかということが問題となる 異なるクラスタに属する2つホストでの計算時間の差がもっとも大きなタスクTiの選択 2019年4月12日 全体ミーティング発表 同一クラスタ内でのホスト間の性能差は小さいと考えたため

24 Simulation Environments
task 1600 tasks (各々は均一) input = unshared 10K file + shared file output = 10K file network topology 5 clusters = (6, 6, 8, 20, 20) network bandwidth = 6 ~ 600Kbytes/sec interval of scheduling event = 500sec 2019年4月12日 全体ミーティング発表

25 Simulation Result (1/2) 2019年4月12日 全体ミーティング発表
Workqueue = なにもHeuristicsを使わずにタスクを割り当てる。Performance estimationなども行わない 2019年4月12日 全体ミーティング発表

26 QoI = performance estimation accuracy
Simulation Result (2/2) shared file 40Mbytes QoI = performance estimation accuracy 2019年4月12日 全体ミーティング発表

27 Outline of Presentation
Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2019年4月12日 全体ミーティング発表

28 Related Work : Condor(1/2)
概要 @University of Wisconsin-Madison High Throughput Computingを目指す 分散計算ツール 特徴 ClassAd ジョブの要件と計算機のステータスを利用者が記述 OS, Memory, etc. それを利用してパターンマッチングを行い、タスクの割り当てを行う 2019年4月12日 全体ミーティング発表

29 Related Work : Condor (2/2)
特徴 Remote System Call remote hostからlocal host上のファイルの参照を可能にする open()などを仲介するプロキシを生成 checkpoint ジョブの停止、再実行、実行ホストの移動が可能 fault tolerant preemption stack, processのアドレス空間などの情報を全て複製する Fork(), kernel thread等を禁止 preemption = 各々のタスクに優先度を利用者がつける。 より優先度の高いものが、そのホストで実行される もし優先度の低いものの実行中に、より高い優先度のものが投入された場合は 低い優先度のものを 2019年4月12日 全体ミーティング発表

30 Related Work : Nimrod 概要 特徴 @Monash University
Parameter sweep application用のツール 特徴 Deadline scheduling 多数のタスクからなるアプリケーション全体の実行時間が利用者の求めるデッドラインを超えないようする GUI interface の提供 Grid Economy Model 利用者がレンタル料と計算終了時間の間でトレードオフのできる環境を提供 性能や計算資源の需要の高さから計算資源に優先度をつけ、 はじめは優先度の低い資源にタスクを割り当てて、 各タスクの実行時間と計算資源との関係から計算資源に対する評価を改めて、 多数のタスクからなるアプリケーション全体の実行時間がユーザの求めるデッドラインを超えないように次のタスクを割り当てていく 2019年4月12日 全体ミーティング発表

31 Related Work : Bricks 概要 特徴 @Tokyo titech University
スケジューリング及びそのフレームワークの評価基盤 特徴 Deadline Scheduleに関する評価、研究 Load Correctionアルゴリズム Fallbackアルゴリズム 2019年4月12日 全体ミーティング発表

32 Related Work : Scheduling on Heterogeneous Environments
対象とするネットワーク regular graph irregular graph 対象とする計算 (タスク) タスクが各々独立 タスク間で通信が存在 パイプライン、DAG Task migration スケジューリングの目的 Throughput round trip time 異種環境上でスケジューリングを行おうという研究は多数ある 実際に実装するかどうかは別にして パイプライン Data Intensive 2019年4月12日 全体ミーティング発表

33 Outline of Presentation
Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2019年4月12日 全体ミーティング発表

34 Summary AppLeS parameter sweep application用のスケジューリング
いくつかのHeuristics Algorithmを提案 シミュレーションで各々を比較 XSufferageがもっとも良い性能をしめした 特に多大なファイルを共有する際に良い性能 QoIが悪い時にも良い性能 Related Work take into account data storage issues no assumption constant perfectly predictable performance characteristics シミュレーションで使ったモデルがそうだという気もする 2019年4月12日 全体ミーティング発表

35 References Heuristics for Scheduling Parameter Sweep applications in Grid environments Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov and Francine Berman (HCW'2000) Using Simulation to Evaluate Scheduling Heuristics for a Class of Applications in Grid Environments Francine Berman, Henri Casanova, Dmitrii Zagorodnov and Arnaud legrand Research Report 2019年4月12日 全体ミーティング発表