応用数理工学特論第6回計算理工学専攻張研究室山本有作ポアソン方程式の数値解法ポアソン方程式    u  f ( x, y) x  y 2 u 2 応用     2 2 熱伝導静電場流体力学応力とひずみの解析物理的意味  ある点でのu の値 = その周囲でのu の値の平均値 + 外力の項大規模計算の例３次元の応力・ひずみ解析簡単な例２次元正方領域での熱伝導方程式 y    u  f ( x, y) x  y 2 u 2 2 2 1 u(0, y) = 0 u(1, y) = 0 u(x, 0) = 0 u(x, 1) = 0 0 x 1 ２次元ポアソン方程式の離散化５×５の２次元格子差分法で離散化 → 疎行列格子行列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 反復法の収束特性の例ヘルムホルツ方程式張研で開発されたGPBi-CG法→ ２次元ポアソン方程式のオーダリング５×５の２次元格子分割を２段階行い，領域を４個の部分領域に分割格子行列 1 2 3 4 5 1 3 9 5 7 6 7 8 9 10 2 4 10 6 8 11 12 13 14 15 21 22 23 24 25 16 17 18 19 20 11 13 19 15 17 21 22 23 24 25 12 14 20 16 18 ND法によるオーダリング ND法によるオーダリング第１段階でのセパレータ第２段階でのセパレータ各対角ブロックの分解は独立に実行可能一般の場合のオーダリングセパレータ Nested Dissection 法によるオーダリング（有限要素法から生じる疎行列の場合）    セパレータと呼ばれる節点集合を取り除くことにより，メッシュを２つの部分に分割この分割に従って行列の行・列を並び替え，行列を縁付きブロック対角形に変形この処理を各対角ブロックに対して再帰的に繰り返す有限要素法メッシュ 0 0 置換後の行列オーダリングによる並列性抽出   コレスキー分解のステップでは，各対角ブロックを並列に分解可能各対角ブロックの演算負荷が均等で，かつ縁の部分が狭い（セパレータに属する節点の個数が小さい）分割が望ましい 00 1 0 2 3 4 0 5 6 77 ３段階の分割後の行列消去木と演算の並列性消去木とは   疎行列のコレスキー分解における消去演算の依存関係を表現するグラフ消去木の各節点は行列 L の各列に対応 ND法でオーダリングした行列に対する消去木  再帰的縁付きブロック対角行列 25 消去木と行列の対応関係 24  鎖の部分 ⇔ 縁の部分 22 23 21  部分木 ⇔ 対角ブロック  共通部分を持たない２つの部分木に対する分解演算は並列に実行可能 10 20 9 19 4 8 14 18 3 7 13 17 2 6 12 16 1 5 11 15 対応する消去木消去木を用いたデータ割り当て 25 subtree-to-subcube 割り当て   鎖の部分では，周期的に節点をプロセッサに割り当てる分岐点でプロセッサ群を２分割し，各部分木をそれぞれのプロセッサ群に割り当てる。この操作を再帰的に行う消去木が不均等な場合   単純な subtree-to-subcube 割り当てでは大きな負荷不均衡が生じる場合あり subtree-to-subcube 割り当ての改良が必要 24 23 22 21 10 20 9 19 4 8 14 18 3 7 13 17 2 6 12 16 1 5 11 15 コレスキー分解処理  入力行列各プロセッサに分散された行列 A を入力として，並列にコレスキー分解を行うアルゴリズム  対角ブロックの分解と縁の部分の計算を，小さいレベルのブロックから順に再帰的に繰り返す消去木 25 24 ４プロセッサで協調して消去演算 23 22 21 ２プロセッサで協調して消去演算各プロセッサで独立に消去演算（通信なし） 10 20 9 19 4 8 14 18 3 7 13 17 2 6 12 16 1 5 11 15 スパースソルバの処理フロー START オーダリング置換行列Pの作成。演算量削減と並列性抽出が目標シンボリック分解I 分解後の非零要素決定，演算量・所要メモリ量算定，消去木作成各プロセッサへの消去木に基づき，負荷均等化・通信最小化を達成するデータ割り当て決定ように行列の列のプロセッサへの割り当てを決定データ分散上記の割り当て方法に基づき，行列データを分散シンボリック分解II 分解後の非零要素を格納するデータ構造を作成コレスキー分解前進後退代入データ収集 END 試作版スパースソルバの性能評価結果概要  以上のアルゴリズムに基づく並列プログラムを開発し，２種のPC クラスタ上で性能評価を行った計算機環境  Alphaクラスタ（mellon）      Alpha EV5 533Mhz ×8ノード RAM 128MB／ノード 100base-tx 接続コンパイラは g77 –O3 を使用 Power PC G5クラスタ（muscat）     PowerPC G5 2.0Ghz × 8ノード RAM 2GB／ノード Gigabit Ether接続コンパイラは g77 –O3 を使用例題 Harwell Boeing Matrix Collectionの５種の行列と，３次元ポアソン方程式を離散化して得られる行列に対し，コレスキー分解の性能を評価 Title Discipline Size(N) Nonzero 演算量 (Gflop) 3dp24 ３次元ポアソン 243 41472 1.15 3dp32 ３次元ポアソン 323 98304 6.59 BCSSTK17 Elevated pressure vessel 10974 428650 0.24 BCSSTK18 R.E. Ginna Nuclear Power Station 11948 149090 0.11 BCSSTK29 Buckling model of a Boeing 767 rear pressure bulkhead 13992 619488 0.66 BCSSTK30 Statics module of an off-shore generator platform 28924 1036208 1.37 BCSSTK31 Statics module of an automobile component 35538 608502 1.87 １プロセッサでの実行時間（コレスキー分解部） Alphaプロセッサでの実行時間 G5プロセッサでの実行時間 G5 は Alpha の10倍程度高速並列実行時の加速率  3dp24，32，bcsstk30，31は比較的よい結果  bcsstk29は加速率が低い  bcsstk17，18は加速率が低いが，問題規模が小さいためやむを得ないと考えられる消去木による分析消去木を用いて，各レベルでの負荷分散と演算・通信の時間比を調べ，性能評価結果を分析 3dp24の場合   負荷分散は比較的良い → 加速率良好上のレベルでの演算が多く，独立に実行可能な演算が少ない → これを改善すれば，並列化効率を更に改善可能レベル0：全PUで協調レベル1： 4PUで協調レベル2： 2PUで協調レベル3：各PUが独立に計算演算時間通信時間面積が時間の長さを表す消去木による分析（続き） bcsstk30 ・独立に演算できる部分が多い → 加速率良好・負荷分散はやや不均衡 → これを改善すれば，並列化効率を更に向上可能 bcsstk29 ・演算のほとんどは最上位レベルで，独立に演算できる部分が少ない → 並列化効率の改善には，より良いオーダリングが必要消去木を用いて並列性能を解析し，性能改善に役立てることが可能グループ発表について概要    最後の２回の授業を使って行う。２～３人のグループで１つの発表を行う。講義で勉強したことをもとに，自分たちで数値実験を行った結果を発表。スケジュール    グループ決定： 6/15 まで発表テーマ決定： 6/22 まで発表： 7/6，7/13 （各グループ15～20分程度）発表テーマの例自分の取り組んでいるシミュレーションのプログラムを，高性能化あるいは並列化した結果の報告講義で学んだ行列計算アルゴリズムの性能評価    分散メモリ型計算機上でのLU分解の並列化スパースソルバの性能評価固有値計算アルゴリズムの性能評価，など高性能計算に関する論文を読み，まとめて報告その他