グリッド環境におけるScaLAPACKのための
GAによるスケジューリング
廣安 知之(同志社大学)
三木 光範(同志社大学)
○斉藤 宏樹(同志社大学 大学院)
谷村 勇輔(同志社大学 大学院)
Jack Dongarra(University of Tennessee/
Oak Ridge National
Laboratory)
発表内容
• 研究背景
– グリッド上における並列・分散計算
– スケジューリング
• ScaLAPACKのスケジューリング
– ブロックサイクリックデータ分割
– ScaLAPACKのコスト見積もり関数
• 従来のスケジューリング手法
– Ad-Hoc greedy, SA
• GAによるスケジューリング手法
• 数値実験
– 各手法の見積もりコスト,スケジューリング時間比較
• まとめ
研究背景
•
グリッド
– ネットワークで遠隔地にある計算資源を接続
– ユーザに大規模な計算資源を提供
•
グリッドコンピューティング
– 計算資源を有効利用した分散・並列計算
グリッド上における並列・分散計算
• 非均質な計算資源上で実行
– CPUやネットワーク性能,メモリ性能等が非均質
– 計算資源の状態が動的に変動
従来の均質環境と大きく異なる特徴を持つ
• ジョブ・タスクスケジューリングが困難
– 適切な計算資源の選択
• アプリケーションの特性に依存
• 計算資源の組み合わせパターンは 2N 通り
NP困難な大域的最適化問題 [J Ullman,1975]
最適化手法によるスケジューリング
• Simulated Annealing(SA),Ad-Hoc greedy
– ScaLAPACKのスケジューリング [Yarkhan 2002]
– タスクを割り当てる最適な計算資源を選択
• SA:確率的探索
• Ad-Hoc greedy:アプリケーションの特徴による探索
SAによる手法が良好な探索を行うが,
スケジューリング時間に問題
特定のグリッド環境における実験結果のみ
本研究では,遺伝的アルゴリズム(GA)による
ScaLAPACKのスケジューリング手法を提案
ScaLAPACK
• 分散メモリ用の線形計算ライブラリ
– Scalable LAPACK
• 共有メモリ用のLAPACKを並列用に拡張
• 行列演算(LU分解・QR分解)を分散実行
– 通信層にBLACSを使用
• PVMやMPIにより複数のプロセッサ間で通信
分配するデータ(行列)は,
ブロックサイクリックデータ分割により,
グリッド上の計算資源に割り当てられる
ブロックサイクリックデータ分割
• プロセスグリッド(P,Q)に基づいて分割
(P,Q)の値とプロセスを割り当てる計算資源性能で,
ScaLAPACKの実行時間が決定する
ScaLAPACKのコスト見積もり関数
• ScaLAPACKの予測実行時間を見積もる
– ScaLAPACKに関するパラメータ
• (P,Q)の値,N, NB
– 計算資源情報
• CPU性能,ネットワーク性能,メモリ容量など
ScaLAPACKのスケジューリング
Genetic Algorithm
従来の探索手法:Ad-Hoc greedy
• ネットワーク性能の高いノードを選択
– メモリの制約も満たしながら探索
• ScaLAPACKの特徴に基づいた探索法
– ScaLAPACKは均質環境向けのアプリケーション
ネットワーク性能が高いクラスタ内のノードが有効
従来の探索手法:SA
• 局所解を回避できる確率的探索法
メモリ制約を満たすノード数ごとに探索する
GAによるスケジューリング手法
• 生物の進化を工学的に模倣した最適化手法
数値実験
• 異なる計算資源でのスケジューリング
– 論文の資源[Yarkhan 2002]
– 小規模(15ノード),大規模(100ノード)計算資源
• GA,Ad-Hoc greedy,SAによる性能比較
– ScaLAPACKの見積もりコスト値による比較
– スケジューリング時間による比較
ScaLAPACKのパラメータ
問題サイズ
ブロックサイズ
(P,Q)
1000~15000,25000~37000
80
1×使用ノード数
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
論文の値による性能比較
実験結果
• 問題サイズが小さい場合にGAの探索が悪い
選択ノード
• N=11000
Ad-Hoc greedyとSAが選択した資源の
総メモリ容量は,12690MB
GAが選択した資源の総メモリ容量は,
ペナルティ値の設定が不適切
10990MBでメモリ制約を満たしていない
ノード順序
• 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は順序を考慮した探索が行えており,
見積もりコストの値が良い
計算資源の規模による性能比較
• 15ノードを小規模,100ノードを大規模と定義
– 計算資源を性能により4パターンに分類
1: ネットワーク速度差 大
CPU速度差
小
2: ネットワーク速度差 大
CPU速度差
大
3: ネットワーク速度差 小
CPU速度差
小
4: ネットワーク速度差 小
CPU速度差
大
小規模計算資源による実験結果
各パターンでGAとSAの探索が良い
大規模計算資源による実験結果
性能差が大きいグリッド上で,GAの探索が最も良い
探索履歴(パターン2)
• N=37000
– GAの見積もりコストが最も小さい
メモリ制約付近に最適解が存在
使用ノード(パターン2)
• N=37000
– 各手法で求めているスケジュールが異なる
– GAで生成されたスケジュールは他の手法で生成
されていない
スケジューリング時間比較(パターン2)
• N=37000
– Ad-Hoc greedyの時間が最も短い
総合スケジューリング時間比較
• パターン2(N=37000)
総合スケジューリング時間はGAが最も短い
まとめ
• ScaLAPACKのスケジューリング
– 数種類の計算資源のパターンで実験
– 従来手法とGAによる手法を実装
• GAによるスケジューリング手法の性能評価
– ノード数が多く性能差が大きいグリッド上において,
最も良好な見積もり時間を生成
– スケジューリング時間において,
最も短い時間で計算
論文の値による性能比較
計算資源情報
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
計算資源のパターン
• 4つのパターンによる性能比較
– CPU処理速度とバンド幅の差により分類
パターン
1
2
3
4
ネットワークバンド幅の差
小(SD < 50)
大(SD > 500)
小
大
CPU速度差
小(SD < 150)
小
大 (SD > 300)
大
ダウンロード

ppt - 同志社大学