グリッド環境におけるタスクスケジューラの構築

グリッド環境における
タスクスケジューラの構築
斉藤宏樹
博士前期課程 2003年度 737番
知的システムデザイン研究室
Intelligent Systems Design Laboratory
研究背景
グリッド
ネットワークで遠隔地にある計算資源を接続
ユーザに大規模な計算資源を提供
グリッドコンピューティング
効率的に分散・並列アプリケーションを実行
Intelligent Systems Design Laboratory
スケジューリングの必要性
適切な計算資源を選択することは困難
グリッドはCPUやネットワーク性能等がヘテロ
計算資源の状態が動的に変動
Intelligent Systems Design Laboratory
研究目的
大規模計算を効率的に実行
グリッドによって実行時間を短縮
グリッドにおけるタスクスケジューラの開発
分散アプリケーションScaLAPACKを対象
有効な計算資源を選択
アプリケーションのタスクを割り振る
ScaLAPACKは計算と通信を頻繁に実行するため，
スケジューリングの対象として有効
Intelligent Systems Design Laboratory
ScaLAPACK
分散メモリ用の線形計算ライブラリ
Scalable LAPACK
共有メモリ用のLAPACKを並列・分散用に拡張
通信しながら行列計算（MPIなど使用）
実行前に行列を計算資源へ分配
行列の分解・通信・更新を繰り返し行う
計算資源に合わせてパラメータ調整可能
問題サイズ，ブロックサイズ，P,Q比など
科学技術分野で使用される重要なライブラリ
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
1. 行列の分配
プロセスグリッド（P,Q）に基づいて分割
N：問題サイズ NB:ブロックサイズ
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
2．行列計算（LU分解）
分解・通信・更新を繰り返す
ブロック列（L）を計算
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
2．行列計算（LU分解）
分解・通信・更新を繰り返す
分解パネルの送信
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
2．行列計算（LU分解）
分解・通信・更新を繰り返す
更新パネル送信
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
2．行列計算（LU分解）
分解・通信・更新を繰り返す
未更新行列の更新
Intelligent Systems Design Laboratory
ScaLAPACKの実行手順
2．行列計算（LU分解）
分解・通信・更新を繰り返す
Intelligent Systems Design Laboratory
ScaLAPACKをグリッド上で実行
実行時間の短縮を目指す
計算資源の選択が重要（計算と通信のバランス）
パラメータ（プロセスグリッド）が重要
有効な計算資源やパラメータを
実行して設定するには時間がかかる
実行する前にシミュレーションが必要
実行する環境でどの程度の時間を要するか予測したい
GrADS Projectはシミュレータを開発
ScaLAPACKのコスト見積もり関数によって，
実行時間を予測
Intelligent Systems Design Laboratory
ScaLAPACKのコスト見積もり関数
ScaLAPACKの行列計算の時間を予測
行列の分解や更新に必要な浮動小数点演算量を算出
分解パネルの通信量を算出
入力情報
計算資源情報
CPU性能，ネットワーク性能，メモリの容量など
ScaLAPACKのパラメータ
問題サイズ，ブロックサイズ，プロセスグリッド
出力情報
ScaLAPACKの見積もり実行時間
本研究では実行時間をより短縮するために，
従来のコスト見積もり関数を拡張する
Intelligent Systems Design Laboratory
従来のコスト見積もり関数
パラメータに制限
Pが１に固定（１次元のみ）
Intelligent Systems Design Laboratory
コスト見積もり関数の拡張
P,Q比が変更可能
２次元の方が１次元よりも実行時間は短くなる
Intelligent Systems Design Laboratory
拡張したコスト見積もり関数
プロセスグリッド（P,Q）が変更可能
P方向に複数プロセスが割り当てられる
計算の待ち時間が短縮
１つのプロセスの通信量が減少
新たにＰ方向の通信が発生
従来の関数（P=1に固定）よりも短い実行時間を
正確に見積もることができるか確認
Intelligent Systems Design Laboratory
拡張したコスト見積もり関数の評価
ScaLAPACKをクラスタで実行し，実測値と見積もりの比較
実験環境
Cluster
クロック周波数（MHz）
FLOPS／（Hz）
DGEMMピーク性能（%）
メモリ（MB）
ノード数
Gregor
1000
1.0
60
512
30
パラメータ
Problem Size(N)
Block Size(NB)
Process Grid(P,Q)
9600
80
(1×30),(2×15),(3×10),(5×6),
(6×5),(10×3),(15×2),(30×1)
Intelligent Systems Design Laboratory
実験結果（１）
見積もり値と実測値の比較
最小実行時間をとるP,Qの値が異なるが，傾向がほぼ等しい
Ｐの値が３よりも大きくなるにつれて誤差が大きくなる
Intelligent Systems Design Laboratory
実験結果（２）
演算時間・通信量の比較
演算時間の誤差は小さく，通信量の増減の傾向も同じ
最適なプロセスグリッドが異なったのは，通信方式の見積もりが
正確でないと考えられる
Intelligent Systems Design Laboratory
タスクスケジューラの構築
スケジュールを最適化
Intelligent Systems Design Laboratory
GAによるスケジューリング手法
生物の進化を工学的に模倣した最適化手法
Intelligent Systems Design Laboratory
GAによるスケジューリング手法
生物の進化を工学的に模倣した最適化手法
Intelligent Systems Design Laboratory
数値実験
グリッド環境でScaLAPACKのスケジューリング
スケジューラによる見積もり値と実測値を比較
生成されたスケジュールの検討
OBIグリッド（Open BioInformatics Grid）で実験
国内バイオインフォマティクス関連の大学・研究機関・
企業の27サイトが参加
12ノード利用（全て同じスペック）
各サイト間のネットワーク速度はヘテロ
最大で20Mbps，最小で3Mbps程度
Intelligent Systems Design Laboratory
GAのパラメータ
組み合わせ最適化
総個体数
遺伝子長
設計変数
交叉
交叉率
突然変異率
選択
トーナメントサイズ
エリート保存
終了世代
配置最適化
100
12
12
一点交叉
50
dMSXF
0.6
1.0
0.0833
1/12
トーナメント選択
トーナメント選択
4
4
1
1
200
10
Intelligent Systems Design Laboratory
実験結果（１）
見積もり値と実測値の比較
各問題サイズにおいて誤差が小さい
最適なスケジュールは最大で４台を利用
Intelligent Systems Design Laboratory
実験結果（２）
生成された最適なスケジュール（N=8000の場合）
同志社大の２台(sand, dnis)，東工大(kona02)，
統計数理研究所(obism220)の各１台の計４台
P,Q=2×2
他のP,Qの値よりも短い実行時間
ノード数 Measured time(sec)
3
1347.01
4
1293.63
5
1412.86
P,Q
1293.63(sec)
Measured time(sec)
1×4
2×2
1233.97
1293.63
Intelligent Systems Design Laboratory
主要ノードとのネットワーク速度
obism220とのネットワーク速度一覧
From node
obism220
To Node
sand
dnis
Knis
Pluto
kona02
hpq02
Mrin
gnis2
ryukyu02
cirobi
ipabnis
Mbps
7.65
7.72
6.63
6.67
7.82
3.83
4.79
2.67
3.18
2.65
4.3
Intelligent Systems Design Laboratory
結論
1. ScaLAPACKのコスト見積もり関数の拡張により，
より短い時間で実行可能
P,Qのパラメータが重要
従来よりも効率的に実行可能となった
2. グリッド環境においてタスクスケジューリングを
行った結果，良好なスケジュールを生成
計算資源から有効な組み合わせを選択・配置
最小時間で実行
Intelligent Systems Design Laboratory
発表論文リスト
廣安知之，三木光範，斉藤宏樹，谷村勇輔，Jack Dongarra
グリッド環境におけるScaLAPACKのためのGAによるスケジューリング
第10回MPSシンポジウム，同志社大学，2003.10
斉藤宏樹，廣安知之，三木光範，谷村勇輔，Jack Dongarra
グリッド環境における分散アプリケーションのための
GAによるスケジューリング
同志社大学理工学研究報告書第45巻第4号 2005.1
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
数値実験
1. 拡張したコスト見積もり関数の評価
ScaLAPACKをクラスタで実行し，実測値と見積もり
値の比較
演算時間や送受信量についても，実測値と見積もり値
の比較
2. グリッド環境におけるスケジューリング
OBIグリッドの分散処理プラットフォームで
ScaLAPACKを実行し，実測値と見積もり値の比較
最適なスケジュールの有効性の検討
Intelligent Systems Design Laboratory
発表の流れ
研究背景・目的
グリッド
スケジューラの必要性
分散アプリケーションScaLAPACK
実行手順
コスト見積もり関数
ScaLAPACKのコスト見積もり関数の拡張
最適化手法GAの実装
数値実験
拡張したコスト見積もり関数の評価
OBIグリッドにおけるスケジューリング
結論
Intelligent Systems Design Laboratory
タスクスケジューラの構築
スケジューラ
Intelligent Systems Design Laboratory
From node
sand
To Node
obism220
dnis
Knis
Pluto
kona02
hpq02
Mrin
gnis2
ryukyu02
cirobi
ipabnis
Mbps
9.07
9.38
8.34
8.38
9.34
3.7
4.66
2.28
3.81
2.78
4.26
Intelligent Systems Design Laboratory
From node
dnis
To Node
sand
obism220
Knis
Pluto
kona02
hpq02
Mrin
gnis2
ryukyu02
cirobi
ipabnis
Mbps
9.26
9.28
8.70
8.65
9.35
3.55
4.89
0.77
3.95
2.77
4.31
Intelligent Systems Design Laboratory
From node
kona02
To Node
sand
obism220
Knis
Pluto
dnis
hpq02
Mrin
gnis2
ryukyu02
cirobi
ipabnis
Mbps
7.82
7.80
6.74
6.80
7.92
3.70
4.95
2.20
3.42
2.65
4.38
Intelligent Systems Design Laboratory
dMSXF（いいとこどり交叉）
TSPで良好な結果
近傍とステップ数で探索
Intelligent Systems Design Laboratory
スケジューリングへのアプローチ
Launch-time Scheduling
アプリケーション実行前のみ行う
適切な計算資源を選択
ReScheduling
アプリケーション実行中にも行う
動的情報を考慮しながら計算資源を再選択
Meta-Scheduling
同時に同じ計算資源で実行するアプリケーショ
ンを考慮して順序などを決定
Intelligent Systems Design Laboratory
シミュレーション環境
Intelligent Systems Design Laboratory
実験結果
見積もり値と実測値の比較
拡張したコスト見積もり関数が良好な結果
２回GAを行う手法が良好
Intelligent Systems Design Laboratory
実験結果（関数の比較）
最適なスケジュール(N=14000)
Intelligent Systems Design Laboratory
実験結果（GAの比較）
最適なスケジュール（N=14000）
Intelligent Systems Design Laboratory
P,Q比が変更可能なコスト見積もり関数の開発
密連立一次方程式を解くアルゴリズムを
対象
PDGESVルーチン
LU分解による行列演算時間を見積もる
Intelligent Systems Design Laboratory
見積もり関数の入力パラメータ
計算資源情報
CPU性能，ネットワーク性能，メモリ容量など
（P,Q）の値，N， NB
Intelligent Systems Design Laboratory
ブロックLU分解フェーズ（１）
最大要素の探索（PDAMAX）
Intelligent Systems Design Laboratory
ブロックLU分解フェーズ（２）
ブロック列において行交換（PDSWAP）
Intelligent Systems Design Laboratory
ブロックLU分解フェーズ（３）
ブロック列（L）の計算（PDSCAL）
Intelligent Systems Design Laboratory
ブロックLU分解フェーズ（４）
ブロックパネル（U）の更新（PDGER）
Intelligent Systems Design Laboratory
演算範囲の推移
これまでの演算をNB-1回繰り返す
Intelligent Systems Design Laboratory
ピボット情報の送信
列方向にBroadCast
Intelligent Systems Design Laboratory
各ブロック列において行交換
行方向でSendRecv
Intelligent Systems Design Laboratory
ブロック行の更新フェーズ（１）
分解済みブロックパネル（L）の送信
BroadCast
Intelligent Systems Design Laboratory
ブロック行の更新フェーズ（２）
ブロック行（U）の更新
Intelligent Systems Design Laboratory
未更新行列の更新フェーズ（１）
分解済みブロック（L）の送信
BroadCast
Intelligent Systems Design Laboratory
未更新行列の更新フェーズ（２）
分解済みブロックの送信
BroadCast
Intelligent Systems Design Laboratory
未更新行列の更新フェーズ（３）
行列積の演算（PDGEMM）
Intelligent Systems Design Laboratory
コスト見積もり関数の開発
演算量の見積もり
計算時間の大部分を占めるルーチンを分析
DGEMMルーチン
行列更新の浮動小数点演算量を見積もる
演算時間の算出
DGEMMのピーク性能値（Flops）を用いる
演算量（Flops）/ピーク性能(Flops)=時間(sec)
Intelligent Systems Design Laboratory
通信時間の見積もり
SendRecv
行交換の際に発生（P≧２）
送受信にかかる時間を計算
BroadCast
Split-ring方式を見積もる
送信ステップは(n+1)/2
Intelligent Systems Design Laboratory
Split-ringの見積もり
プロセス番号０の送受信が終了するまで
Intelligent Systems Design Laboratory
数値実験（関数の評価）
ScaLAPACKをクラスタで実行
NWSにより計算資源情報を収集し関数へ入力
CPU利用可能率，バンド幅，レイテンシ収集
ATLAS, High Performance BLASを使用
正確な演算性能で計算させる
コスト見積もり関数による見積もり値と比較
ParadynによりScaLAPACKを実行
Paradynにより演算時間や送受信量を計測
演算時間と送受信量を見積もり値と比較
Intelligent Systems Design Laboratory
実験環境
・静的情報
Cluster
クロック周波数（MHz）
FLOPS／クロック周波数（Hz）
DGEMMピーク性能（%）
メモリ（MB）
ノード数
Gregor
1000
1.0
60
512
30
Xenia
2400
2.0
87.5
512
48
・動的情報（NWSより）
CPU利用可能率（%）
バンド幅（Mbps）
レイテンシ（μsec）
[0.0 – 1.0]
Intelligent Systems Design Laboratory
ScaLAPACKのパラメータ
・Gregor
Problem Size(N)
Block Size(NB)
Process Grid(P,Q)
9600
80
(1×30),(2×15),(3×10),(5×6),
(6×5),(10×3),(15×2),(30×1)
・Xenia
Problem Size(N)
Block Size(NB)
Process Grid(P,Q)
11520
80
(1×48),(2×24),(3×16),(4×12),
(6×8),(8×6),(12×4),(16×3),
(24×2),(48×1)
Intelligent Systems Design Laboratory
実測値と見積もり値の比較
・Gregor
・Xenia
最小実行時間をとるP,Qの値が異なる
Intelligent Systems Design Laboratory
見積もり値の誤差
・Gregor
・Xenia
GregorとXeniaで誤差に大きな差
Intelligent Systems Design Laboratory
演算時間・送受信量の比較（Gregor）
演算時間の誤差は小さい
Intelligent Systems Design Laboratory
従来の探索手法：Ad-Hoc greedy
CPU，ネットワーク性能の高いノードを選択
メモリの制約も満たしながら探索
ScaLAPACKの特徴に基づいた探索法
ScaLAPACKは均質環境向けのアプリケーション
クラスタ内のノードを優先的に利用
Intelligent Systems Design Laboratory
従来の探索手法：SA
局所解を回避できる確率的探索法
メモリ制約を満たすノード数ごとに探索する
Intelligent Systems Design Laboratory
GAによるスケジューリング手法
生物の進化を工学的に模倣した最適化手法
Intelligent Systems Design Laboratory
数値実験
異なる計算資源でのスケジューリング
論文の資源[Yarkhan 2002]
小規模（15ノード），大規模（100ノード）計算資源
GA，Ad-Hoc greedy，SAによる性能比較
ScaLAPACKの見積もりコスト値による比較
スケジューリング，計算時間による比較
ScaLAPACKのパラメータ
問題サイズ
ブロックサイズ
（P,Q）
1000～15000，25000～37000
80
1×使用ノード数
Intelligent Systems Design Laboratory
GA，SAのパラメータ
GA [伊庭 1994]
SA [小西 1994]
総個体数
100
遺伝子長
ノード数（=L）
設計変数
ノード数
交叉
二点交叉
交叉率
0.6
突然変異率
1/L
選択
トーナメント選択
トーナメントサイズ
4
エリート保存
1
終了世代
500
ペナルティρ
300,500
最高温度
最低温度
ステップ数
クーリング関数
クーリング間隔
クーリング率
150
4.3
1.0×104
a(T )  aT
100
0.9648
Intelligent Systems Design Laboratory
論文の値による性能比較
Intelligent Systems Design Laboratory
実験結果
問題サイズ11000以下でGAの探索が悪い
各問題サイズでAd-Hoc greedyの探索が悪い
Intelligent Systems Design Laboratory
選択ノード
N=11000
問題サイズ11000を計算するのに必要なメモリ容量は
2307.8MB以上
GAが選択した資源の総メモリ容量は，2304MBでメモリ
制約を満たしていない
ペナルティ値の設定が不適切
Intelligent Systems Design Laboratory
ノード順序
N=14000
ノード順序
Ad-Hoc
SA
GA
5,3,4,0,1,2,6,7,8,9,10,11,12,13,14
9,7,11,13,8,14,4,5,3,1,0,2,6,12,10
5,4,8,7,11,10,12,14,13,6,9,0,1,2,3
見積もりコス
ト
1507.1
1292.1
1235.5
各手法が全15ノードを使用しているが，
順序が異なる
GA，SAは順序を考慮した探索が行えており，
見積もりコストの値が良い
Intelligent Systems Design Laboratory
計算資源の規模による性能比較
15ノードを小規模，100ノードを大規模と定義
計算資源を性能により4パターンに分類
1: ネットワーク速度差大
CPU速度差
小
2: ネットワーク速度差大
CPU速度差
大
3: ネットワーク速度差小
CPU速度差
小
4: ネットワーク速度差小
CPU速度差
大
Intelligent Systems Design Laboratory
小規模計算資源による実験結果
各パターンでGAとSAの探索が良い
Intelligent Systems Design Laboratory
大規模計算資源による実験結果
大きい問題サイズにおいて，GAの探索が最も良い
Intelligent Systems Design Laboratory
探索履歴（パターン2）
N=37000
GAの見積もりコストが最も小さい
Ad-Hoc greedy，SAは局所解に陥っている
Intelligent Systems Design Laboratory
使用ノード（パターン2）
N=37000
各手法で求めているスケジュールが異なる
GAで生成されたスケジュールは他の手法で生成
されていない
Intelligent Systems Design Laboratory
スケジューリング時間比較（パターン2）
N=37000
Ad-Hoc greedyの時間が最も短い
Intelligent Systems Design Laboratory
計算時間比較
パターン2（N=37000）
スケジューリング時間と見積もり実行時間の和
GAが最も短い
Intelligent Systems Design Laboratory
ペナルティ関数
不足しているメモリ量をもとに，ペナル
ティ値を決定
g（ρ）=ρ{N-(Total memory[byte]/8)1/4}
Intelligent Systems Design Laboratory
必要メモリ容量
問題サイズNの場合，N×Nの行列要素
要素はdouble型
N2×8=Total memory[byte]
Intelligent Systems Design Laboratory
LU分解
Intelligent Systems Design Laboratory
SAのパラメータ
最高温度
最大の改悪となる状態遷移が50%の確率で受理
される温度
最低温度
最小の改悪となる状態遷移が一定温度のアニー
リング処理の間に，1回は受理されるような温度
Intelligent Systems Design Laboratory
論文の値
計算資源情報
TORC
ノード数
CPU処理速度（MHz）
CPU利用可能率
バンド幅（Mbps）
レイテンシ（μsec）
メモリ容量（MB）
MSC
3
550
0.9
75
0.15
512
OPUS
3
933
0.9
75
0.15
512
9
450
0.9
75
0.15
256
Intelligent Systems Design Laboratory
計算資源のパターン
4つのパターンによる性能比較
CPU処理速度とバンド幅の差により分類
パターン
1
2
3
4
ネットワークバンド幅の差
小（SD < 50）
大（SD > 500）
小
大
CPU速度差
小（SD < 150）
小
大（SD > 300）
大
Intelligent Systems Design Laboratory

Download Report