Heuristics for Scheduling Parameter Sweep Application in Grid environments M1 Kenji KANEDA (SIG-PDS) 2015年9月30日 全体ミーティング発表 1 Outline of Presentation Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2015年9月30日 全体ミーティング発表 2 Background (自分の研究) 複数のクラスタ、スーパーコンピュータが高速 ネットワークによって結合 多数の計算資源を利用する機会の増大 しかし、FirewallやPrivate Networkなどの管理者 が利用に制限を課している場合が多い 管理者の課す制限を自動的に迂回して、遠隔計 算機の効率的かつ簡便な利用を目指す 2015年9月30日 全体ミーティング発表 3 Background 多数の異種環境上の計算機に分散計算を 行いたい Software DSM MPI parameter sweep application embarrassing parallel 多数の独立したタスクを多数の計算機にばら撒く 2015年9月30日 全体ミーティング発表 4 AppLeS (Application Level Scheduling) parameter sweep applicationのスケ ジューリング 対象 多大なparameter spaces 各々タスクは独立 いくつかのファイルを共有するのみ 資源は動的に利用率が変化 2015年9月30日 全体ミーティング発表 5 AppLeSの想定するシナリオ 計算 Server Information Service output check input input User 2015年9月30日 全体ミーティング発表 6 Outline of Presentation Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary & Future Work 2015年9月30日 全体ミーティング発表 7 Network Model (1/2) network topology k個のクラスタと利用者のいるホストで構成 クラスタ いくつかのホストと一つのストレージで構成 ストレージはクラスタ内で共有 クラスタと利用者のいるホストとを直接結ぶリンクは一 つ クラスタ内のホスト間の通信は無視できる(比較的高 速と仮定) 2015年9月30日 全体ミーティング発表 8 Network Model (2/2) 2015年9月30日 全体ミーティング発表 9 Task Model 各々独立なn個のタスク いくつかの入力ファイル そのうちいくつかは複数のタスクで共有 一旦ストレージに蓄えられた入力ファイルは、全計算中 常に蓄えられ続ける 一つの出力ファイル 一度ホストに割り当てられたタスクの移動は考え ない 想定するアプリケーション MCell (micro-physiology application) 3-D Monte-Calro simulationを使用 入力ファイルは数百MBytes 2015年9月30日 全体ミーティング発表 10 Outline of Presentation Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2015年9月30日 全体ミーティング発表 11 Scheduling 目的 makespanが最も短くなるようなタスクの割り当て makespan = 最初の入力ファイルが計算サーバに送信され てから、最後の出力ファイルが利用者に返信されてくるまで の時間 adaptiveなスケジューリング 動的な資源の変化に対応する 概要 定期的にschedule()という関数を呼ぶ 2015年9月30日 全体ミーティング発表 12 schedule() 1. 次にschedule()を呼ぶタイミングを計算 2. 現在実行中の計算、ファイル転送の終了 時間を予測 3. 未実行のタスク中からサブセットTを選択 4. T中のタスクをHeuristicに割り当てる Gantt Chartというネットワークリンクとホスト の状態を表す図を利用 2015年9月30日 全体ミーティング発表 13 次にschedule()を呼ぶタイミング 次にschedule()を呼ぶタイミングを計算 頻繁なスケジューリングの計算を避けるため 資源の変化、予測の変化に適応するため 実行間隔の決定方法 定期的 偏向を考慮 予測実行時間と実際の実行時間の差を考慮し、ず れが多いときほど、頻繁に計算 2015年9月30日 全体ミーティング発表 14 実行終了時間の予測 (1/2) 概要 現在実行中のタスクの終了時間の予測 Gantt Chartにその状態を書き込む Networks Links 送受信 中のファ イル Link 1 Link 2 Cluster 1 Host 1.1 Host 1.2 Cluster 2 Host 2.1 Host 2.2 Host 2.3 実行中 のタスク 2015年9月30日 全体ミーティング発表 15 実行終了時間の予測 (2/2) 終了時間の予測方法 NWSなどのシステムから得られる情報をもとに Heuristicに予測 例）実行中のジョブの終了時間の予測 各々のジョブの計算時間は等しいと仮定 過去に実行した際にかかった実行時間とその時のCPU load 実行中のジョブのいままでの実行時間とそのCPU load 現在何%実行が終了したかを予測 2015年9月30日 全体ミーティング発表 16 未実行タスクのサブセットの選 択 schedule()の計算時間の削減のため 複数回schedule()を呼ぶため計算時間の削減が必須 複数回呼び出すため一度に全てのタスクを割り当て る必要はない 選択方法 random maximizing data re-use 巨大な入力ファイルを共有するタスクの数が最大となる集合 2015年9月30日 全体ミーティング発表 17 未実行のタスクの割り当て 未実行のタスクをHeuristicにホストに割り当てる Gantt Chartを重複しないように埋めていく Networks Links Link 1 Link 2 Cluster 1 Host 1.1 Host 1.2 Cluster 2 Host 2.1 Host 2.2 Host 2.3 input output 2015年9月30日 全体ミーティング発表 18 Heuristics Algorithm (1/5) 用 語、定義 Hjk=j thクラスタ中のk thホスト C（Ti,Hjk）=タスクTiのホストHjkでの実行時間 関数f(x)が最小となるときのxの値 argmaxも同様 2015年9月30日 全体ミーティング発表 19 Heuristics Algorithm (2/5) Min-min Tiを最短時間で計算す るホストHjkの選択 T中で最短時間で終了する タスクTsの選択 2015年9月30日 全体ミーティング発表 20 Heuristics Algorithm (3/5) Max-min Tiを最短時間で計算する ホストHjkの選択 T中で計算に最も時間のか かるタスクTsの選択 2015年9月30日 全体ミーティング発表 21 Heuristics Algorithm (4/5) Sufferage 2つのホストでの計算時間の差がもっとも 大きなタスクTiの選択 最適でないホストに割り当てたとき の影響のでかいタスク 2015年9月30日 全体ミーティング発表 22 Heuristics Algorithm (5/5) XSufferage 異なるクラスタに属する2つホストでの計算 時間の差がもっとも大きなタスクTiの選択 2015年9月30日 同一クラスタ内でのホスト間の性能 差は小さいと考えたため 全体ミーティング発表 23 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 2015年9月30日 全体ミーティング発表 24 Simulation Result (1/2) 2015年9月30日 全体ミーティング発表 25 Simulation Result (2/2) QoI = performance estimation accuracy 2015年9月30日 全体ミーティング発表 26 Outline of Presentation Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2015年9月30日 全体ミーティング発表 27 Related Work : Condor(1/2) 概要 @University of Wisconsin-Madison High Throughput Computingを目指す 分散計算ツール 特徴 ClassAd ジョブの要件と計算機のステータスを利用者が記述 OS, Memory, etc. それを利用してパターンマッチングを行い、タスクの割り当て を行う 2015年9月30日 全体ミーティング発表 28 Related Work : Condor (2/2) 特徴 Remote System Call remote hostからlocal host上のファイルの参照を可能にする open()などを仲介するプロキシを生成 checkpoint ジョブの停止、再実行、実行ホストの移動が可能 fault tolerant preemption stack, processのアドレス空間などの情報を全て複製する Fork(), kernel thread等を禁止 2015年9月30日 全体ミーティング発表 29 Related Work : Nimrod 概要 @Monash University Parameter sweep application用のツール 特徴 Deadline scheduling 多数のタスクからなるアプリケーション全体の実行時間 が利用者の求めるデッドラインを超えないようする GUI interface の提供 2015年9月30日 全体ミーティング発表 30 Related Work : Bricks 概要 @Tokyo titech University スケジューリング及びそのフレームワークの評 価基盤 特徴 Deadline Scheduleに関する評価、研究 Load Correctionアルゴリズム Fallbackアルゴリズム 2015年9月30日 全体ミーティング発表 31 Related Work : Scheduling on Heterogeneous Environments 対象とするネットワーク regular graph irregular graph 対象とする計算 (タスク) タスクが各々独立 タスク間で通信が存在 パイプライン、DAG Task migration スケジューリングの目的 Throughput round trip time 2015年9月30日 全体ミーティング発表 32 Outline of Presentation Background & Overview of AppLeS (Task, Network) Model Scheduling Simulation Experiments Related Work Summary 2015年9月30日 全体ミーティング発表 33 Summary AppLeS parameter sweep application用のスケジュー リング いくつかのHeuristics Algorithmを提案 シミュレーションで各々を比較 2015年9月30日 XSufferageがもっとも良い性能をしめした 特に多大なファイルを共有する際に良い性能 QoIが悪い時にも良い性能 全体ミーティング発表 34 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 2015年9月30日 全体ミーティング発表 35
© Copyright 2024 ExpyDoc
