P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発 修士2年　斉藤　宏樹

研究背景 グリッド グリッドコンピューティング ネットワークで遠隔地にある計算資源を接続 グリッドを利用して大規模計算 アプリケーションのスケジューリングが必要

スケジューリングの必要性 適切な計算資源を選択することが困難 グリッドはCPUやネットワーク性能等が不均質 計算資源の状態が動的に変動 従来の均質環境と大きく異なる特徴を持つ

スケジューリングへのアプローチ Launch-time Scheduling ReScheduling Meta-Scheduling アプリケーション実行前のみ行う 適切な計算資源を選択 ReScheduling アプリケーション実行中にも行う 動的情報を考慮しながら計算資源を再選択 Meta-Scheduling 同時に同じ計算資源で実行するアプリケーションを考慮して順序などを決定

研究目標 グリッドにおけるスケジューラの開発 ScaLAPACKのスケジューラ開発 分散アプリケーションを対象 有効な計算資源を選択したスケジュール生成 ScaLAPACKのスケジューラ開発 アプリケーション実行前に計算資源を選択 ScaLAPACKは計算と通信を頻繁に実行するため， スケジューリングの対象として有効

ScaLAPACKとは？ 分散メモリ用の線形計算ライブラリ 通信しながら行列を分解（MPIなど使用） 計算資源に合わせてパラメータ調整可能 Scalable LAPACK 共有メモリ用のLAPACKを並列用に拡張 通信しながら行列を分解（MPIなど使用） LU分解，QR分解 計算資源に合わせてパラメータ調整可能 問題サイズ，ブロックサイズ，P,Q比など 科学技術分野で使用される重要なライブラリ

P,Q比とは？（２次元） 行方向と列方向へのプロセスの割り当て方 ６ノードに行列を分配する場合

コスト見積もり関数とは？ スケジューラ

従来のコスト見積もり関数 パラメータに制限 Pが１に固定（１次元のみ）

開発したコスト見積もり関数 P,Q比が変更可能 ２次元の方が１次元よりも実行時間は短くなる

P,Q比が変更可能なコスト見積もり関数の開発 密連立一次方程式を解くアルゴリズムを対象 PDGESVルーチン LU分解による行列演算時間を見積もる 従来のコスト見積もり関数を調査 PDGESVルーチンのアルゴリズム解析 演算量と通信量の見積もり値・方法を決定 評価（見積もり値の正確さ） 修正

ブロックLU分解フェーズ（１） 最大要素の探索（PDAMAX）

ブロックLU分解フェーズ（２） ブロック列において行交換（PDSWAP）

ブロックLU分解フェーズ（３） ブロック列（L）の計算（PDSCAL）

ブロックLU分解フェーズ（４） ブロックパネル（U）の更新（PDGER）

演算範囲の推移 これまでの演算をNB-1回繰り返す

ピボット情報の送信 列方向にBroadCast

各ブロック列において行交換 行方向でSendRecv

ブロック行の更新フェーズ（１） 分解済みブロックパネル（L）の送信 BroadCast

ブロック行の更新フェーズ（２） ブロック行（U）の更新

未更新行列の更新フェーズ（１） 分解済みブロック（L）の送信 BroadCast

未更新行列の更新フェーズ（２） 分解済みブロックの送信 BroadCast

未更新行列の更新フェーズ（３） 行列積の演算（PDGEMM）

コスト見積もり関数の開発 演算量の見積もり 演算時間の算出 計算時間の大部分を占めるルーチンを分析 行列更新の浮動小数点演算量を見積もる DGEMMルーチン 行列更新の浮動小数点演算量を見積もる 演算時間の算出 DGEMMのピーク性能値（Flops）を用いる 演算量（Flops）/ピーク性能(Flops)=時間(sec)

通信時間の見積もり SendRecv BroadCast 行交換の際に発生（P≧２） 送受信にかかる時間を計算 Split-ring方式を見積もる 送信ステップは(n+1)/2

Split-ringの見積もり プロセス番号０の送受信が終了するまで

数値実験（関数の評価） ScaLAPACKをクラスタで実行 ParadynによりScaLAPACKを実行 NWSにより計算資源情報を収集し関数へ入力 CPU利用可能率，バンド幅，レイテンシ収集 ATLAS, High Performance BLASを使用 正確な演算性能で計算させる コスト見積もり関数による見積もり値と比較 ParadynによりScaLAPACKを実行 Paradynにより演算時間や送受信量を計測 演算時間と送受信量を見積もり値と比較

実験環境 ・静的情報 ・動的情報（NWSより） Cluster Gregor Xenia クロック周波数（MHz） FLOPS／クロック周波数（Hz） DGEMMピーク性能（%） メモリ（MB） ノード数 1000 1.0 60 512 30 2400 2.0 87.5 48 ・動的情報（NWSより） CPU利用可能率（%） バンド幅（Mbps） レイテンシ（μsec） [0.0 – 1.0] -

ScaLAPACKのパラメータ ・Gregor ・Xenia Problem Size(N) 9600 Block Size(NB) 80 Process Grid(P,Q) (1×30),(2×15),(3×10),(5×6), (6×5),(10×3),(15×2),(30×1) ・Xenia Problem Size(N) 11520 Block Size(NB) 80 Process Grid(P,Q) (1×48),(2×24),(3×16),(4×12), (6×8),(8×6),(12×4),(16×3), (24×2),(48×1)

実測値と見積もり値の比較 ・Gregor ・Xenia 最小実行時間をとるP,Qの値が異なる

見積もり値の誤差 ・Gregor ・Xenia GregorとXeniaで誤差に大きな差

演算時間・送受信量の比較（Gregor） 演算時間の誤差は小さい

まとめ P,Q比が変更可能な見積もり関数開発 実測値と見積もり値の比較 PDGESVルーチン解析 送受信の見積もりに行交換を新しく追加 クラスタにScaLAPACK，NWSをインストール Paradynにより演算時間と送受信量を比較 誤差の原因を把握して修正する必要がある