科学技術計算におけるソフトウェア自動チューニング:<ソフトウェア自動チューニング技術の応用>8.並列反復法と自動チューニング-マルチコア時代の並列プログラミングモデル-
6
0
0
全文
(2) 特集）科学技術計算におけるソフトウェア自動チューニング どの反復法が広く使用されている．したがって，並列反 復法の高速化が，並列計算機上での大規模有限要素法ア プリケーションの計算効率の鍵を握っているのである． 有限要素法は，計算プロセスの点からは以下のような 特徴がある： ① 要素内で成立するローカルな方程式に基づくため， 得られる係数行列は 0 成分が多い疎行列である．係 数行列が密であれば，CG 法などの反復法によく現 れる {Y}=[A]{X} という行列ベクトル積を計算する場 合に，以下に示すように計算する： for (i=0; i<N; i++) { for (j=0; j<N; j++) { Y[i]= Y[i] + A[i,j]*X[j]; } }. 図 -3 有限要素による要素分割・領域分割例，赤い部分は並列計 算向けに領域分割した場合の領域間境界である 2）．. Hybrid では Flat MPI と比較して，MPI プロセス数が少. 疎行列の場合には，非ゼロ成分だけ記憶しておけば. なくて済む（図 -1, 2 の場合は 4 分の 1） ．. よいため，下記のようになる：. 文献 1）によると Flat MPI と Hybrid の優劣は，①対象. for (i=0; i<N; i++) { for (k=Index(i-1); k<Index(i); k++) { Y[i]= Y[i] + A [k]*X[Item[k]]; } }. とするアプリケーションの性質，問題サイズ，②ハード ウェア諸元（CPU 速度，メモリ性能，ネットワーク性能， それらのバランス）によって決まり一意に決めることは 難しい．今世紀初頭を中心にさまざまな研究が実施され たが，Hybrid はあまり流行らなかった．最大の理由は，. ここで Index は各行における非ゼロ成分の数，Item. プログラミングの困難さと比べて，得られる性能の向上. は対応する列番号である．密行列の場合と比較する. が少なく，アプリケーションによっては却って低下する. と，間接参照が多くなり，メモリへの負担が大きく. 場合もあることである．. なるため，メモリ性能がアプリケーション全体の性 能を決定する，すなわち memory bound なプロセス となる．. 並列反復法とプログラミングモデル. ② 並列計算においては，全体領域を MPI の各プロセス. 筆者は「GeoFEM（http://geofem.tokyo.rist.or.jp/） 」とい. に割り当てて計算するが，もともと要素ごとのロー. う地球シミュレータ向けの並列有限要素法のためのフレ. カルな方程式を基本としているため，通信は領域境. ームワークを開発するプロジェクトを通して Hybrid 並. 界（図 -3 の赤い部分）を中心に，隣接している領域に. 2）. 列プログラミングモデルとかかわることになった ．有. おいてのみ発生する．したがって，通信バンド幅よ. 限要素法は，図 -3 に示すように対象領域を要素分割す. りはレイテンシがよりクリティカルである．疎行列. ることによって偏微分方程式を数値的に解く手法であ. を対象とした反復法を並列化する場合についても同. り，さまざまな実用的問題に使用されている．有限要素. じことが言える．. 法は最終的には個々の要素において成立する線形化され た積分方程式を重ね合わせて得られる大規模で「疎な」. 図 -4 は「地球シミュレータ」160 ノード（1,280 PE. （sparse，0 成分が大部分を占める）係数行列を持つ連立. （Processing Element） ）を使用して，3 次元弾性体におけ. 1 次方程式を解くことに帰着させられる．対象とする問. る静的な荷重のつりあいの問題（静的弾性問題）を有限. 題にもよるが，有限要素法で最も時間を要するプロセス. 要素法で解く場合に得られる疎行列を ICCG 法☆ 2 で解. はこの連立 1 次方程式を解く部分である．方程式の解法. いた場合の性能比較である 2）．横軸が PE 数，縦軸が. としては，逆行列を陽に計算する直接法と，反復的に計 算する反復法があるが，大規模な疎行列を並列計算機上 で解く場合，共役勾配法（Conjugate Gradient，CG 法）な. 518. 情報処理 Vol.50 No.6 June 2009. ☆2. CG 法に不完全コレスキー法（Incomplete Cholesky Facorization，IC） による前処理を施したもの．.
(3) 8 並列反復法と自動チューニング 4.00. したいわゆる「Weak Scaling」の計算結果である☆ 4．本来， 性能はノード数，PE 数に比例して増加するはずである. 3.00. ノードあたりの問題規模が大きいケース（●●）は，. Flat MPI と Hybrid の差はなくほぼ理想値に近い効率で あるが，ノード数が増加すると，若干 Hybrid が優位に. TF LOPS. が，通信のオーバヘッドがあるためノード数が増加する と理想値よりは若干低めとなる．. Flat MPI: Large Flat MPI: Small Hybrid: Large Hybrid: Small. 2.00. 1.00. なる．ノードあたりの問題規模が小さい場合 （▲▲） は最 内ループ長が短く，「地球シミュレータ」 のようなベクト. 0.00. ル型並列計算機では絶対的な性能が全体的に低いが，ノ. 0. 256. 比較して，通信レイテンシが比較的大きい 2）．ノードあ たり問題規模が小さい場合は，レイテンシによるオーバ. 768. 1024. 1280. PE#. ード数が増加すると Hybrid（▲）が優位である．「地球 シミュレータ」は，CPU・メモリ性能，通信バンド幅と. 512. 図 -4 「地球シミュレータ」上での 3 次元静的弾性問題向け ICCG ソ ル バ ー の 性 能 比 較（Weak Scaling）（Large : 12,582,912 DOF/ node, Small : 786,432 DOF/node）， （DOF： 自 由 度（Degrees of Freedom），PE : Processing Element）2）．. ヘッドの効果が顕著となり，ノード数増加によってさら に増幅され，MPI プロセス数の少ない Hybrid の方が優 位となっている．このような現象の可能性については，. 分が最も計算時間がかかる．また，疎行列を対象とした. 地球シミュレータが本格的に稼働する前から米国ロスア. 並列反復法においては，レイテンシがクリティカルであ. ラモス国立研究所の性能評価モデル 3）によって予測され. る．この影響は MPI プロセスが増加するほど深刻とな. ていた．. るため，ペタ／エクサスケールのシステムでは Hybrid. しかし，このような Hybrid の優位性は通信レイテン. 並列プログラミングモデルの導入によって，MPI プロ. シ値が相対的に大きい「地球シミュレータ」 のみで発生す. セス数の爆発的な増加を少しでも抑制することが重要で. 2）. る現象であり他の超並列計算機では観察されていない ．. ある． また疎行列を対象とした並列反復法は memory bound なプロセスである．したがって，メモリに負担をかけな. なぜ「また」Hybrid か？. いように，できるだけ各コアあたりの問題規模を小さく. James Sexton（IBM Research）による最近の講演. 4）. によ. 抑えて，多くのコアを使って計算することが得策であ る．図4 の説明でも示したように，このような場合も，. ると：. Hybrid 並列プログラミングモデルが有利となる可能性 •. コモディティプロセッサのコアあたり性能は今後も. 2 ∼ 4GHz 程度にとどまり，ペタスケール. ☆5. ☆6. テムのコア数は数十万，エクサスケール. •. のシス. では数億. がある． このような背景もあり，マルチコアの時代を迎えて，. Hybrid 並列プログラミングモデルは再び脚光を浴びつ. の規模になる. つ あ る．2008 年 初 頭 か ら SIAM や SC-XY Conference. メモリの性能は将来それほど向上せず，むしろ消費. Series でも関連した発表やチュートリアルが目立つよう. 電力を下げることが研究開発の中心となるであろう. になってきた． 今世紀初頭のブームの時と違い，現在は T2K オープ ンスパコン（http://www.open-supercomputer.org/）に代表. ということである． すでに述べたように，並列計算機による有限要素法ア. されるマルチコア，マルチソケットの cc-NUMA（Cache. プリケーションでは，大規模な疎行列を反復法で解く部. Coherent Non-Uniform Memory Access）アーキテクチャが 主流となりつつある．. ☆3 ☆4 ☆5 ☆6. TFLOPS=Tera Floating OPerations per Second，1 秒間に 10 (51 Tera) 回の浮動小数点演算を実行していることを示す，計算性能の指標． これに対して「Strong Scaling」では，全体の問題規模を固定して，ノ ード数を変化させる． Peta51015，「テラ」の 1,000 倍． エクサ：Exa51018， 「ペタ」のさらに 1,000 倍． 12. T2K オ ー プ ン ス パ コ ン は 図 -5 に 示 す よ う に， 各 ノ ー ド 上 に 4 コ ア を 有 す る AMD Opteron（2.3GHz） （Barcelona）を 4 ソケット搭載している（合計 16 コア）．. SMP ではすべてのプロセッサからメモリに平等にアク 情報処理 Vol.50 No.6 June 2009. 519. ソフトウェア自動チューニング技術の応用. TFLOPS 値☆ 3 である．ノードあたりの問題規模を固定.
(4) 特集）科学技術計算におけるソフトウェア自動チューニング Memory. L2 L1. L2 L1. L3. L2 L1. ⿎⿎問題設定等. Memory. L2 L1. Core Core Core Core. L2 L1. L2 L1. L3. L2 L1. 問題サイズは 2,097,152 要素，6,440,067 自由度（DOF） であり，2 ノード（16 コア）から 32 ノード（512 コア）. L2 L1. ま で ノ ー ド 数 を 変 え た 計 算 を 実 施 し た．Flat MPI と. Hybrid 並列プログラミングモデルの比較を実施した．. Core Core Core Core. Hybrid については以下の 3 種類のプログラミングモデ ルを適用した． Core Core Core Core L1 L2. L1 L2. L3. L1 L2. L1 L2. . Core Core Core Core L1 L2. Memory. L1 L2. L3. L1 L2. •. L1 L2. Hybrid 434（HB 434）: 図 -5 の 各 ソ ケ ッ ト に OpenMP スレッド 34，ノード当たり 4 つの MPI プ ロセス. Memory. •. 図 -5 T2K オ ー プ ン ス パ コ ン の ノ ー ド 構 成，AMD Quad-core Opteron（2.3GHz）× 4 ソケット，合計 16 コア. Hybrid 832（HB 832）: 2 ソケットに OpenMP スレ ッド 38，1 ノード当たり 2 つの MPI プロセス. •. Hybrid 1631（HB 1631）: 1 ノ ー ド 全 体 に 16 の OpenMP スレッド，1 ノード当たりの MPI プロセス は1つ. セスすることが可能であった．T2K オープンスパコン. . の各ノード内では他ソケットのメモリ上のデータをア. 各 MPI プロセスに図 -3 における 1 領域が割り当てられ. クセスすることは可能であるが，ローカルなメモリと. ている．将来的なことを考えると，MPI プロセスの数. 比べてアクセスに時間がかかる（Non-Uniform Memory. を減らすためには，できるだけ HB 1631 の性能を上げ. Access）．ここで，cc-NUMA の「Cache-Coherent」とは「キ. たいところである．ここでは，特にその点に注目した．. ャッシュが整合している」すなわち，メモリ上と各ソケ ット上のキャッシュ上のデータの整合性が保たれる，と. ⿎⿎チューニングの戦略. いうことである．. チューニングにあたって以下の 3 つのプロセスを実施. したがって，計算効率を上げるためにはできるだけ各. した．なお，CASE-2，CASE-3 は Flat MPI に対しては. ソケット上のローカルなメモリ上にデータを格納するよ. 実施していない：. うな工夫が必要となる．. CASE-1：NUMA Control による実行時制御. Linux OS で は，cc-NUMA ア ー キ テ ク チ ャ に お い て，各コアの使用するメモリを明示的に指定するため. 並列反復法のチューニング. の実行時制御コマンドとして「NUMA control」が提供さ. 本章では，文献 5） に従って， T2K オープンスパコン（東. れており，これによって性能が向上することはよく知. 大）において，Hybrid 並列プログラミングモデルを使用. られている．さまざまなオプションが用意されている. した並列有限要素法プログラム向けの疎行列反復法ソル. が，CASE-1 では，文献 5）に示す 5 種類の制御コマンド. バーの最適化（チューニング） の実例を示す．. 群（NUMA Policy） を適用した． CASE-2：First Touch Data Placement. cc-NUMA アーキテクチャでは，変数や配列を宣言し. ⿎⿎アプリケーション概要，計算環境. 対象とする問題は，3 次元弾性体における静的な荷重. た時点では，物理的メモリ上に記憶領域は確保されず，. のつりあいの問題（静的弾性問題） で，これを並列有限要. 変数を最初にアクセスしたコア （の属するソケット）のロ. 素法によって解く．SGS （Symmetric Gauss-Seidel） 前処理. 5）. ーカルメモリ上に，その変数の記憶領域が確保される．. に基づく CG 法により得られた連立 1 次方程式を解く．. これを First Touch Data Placement6）と呼び，配列の初期. プログラムは，FORTRAN90，OpenMP，MPI によっ. 化手順により大幅な性能の向上が達成できる場合もある．. て記述されている．本稿では T2K オープンスパコン（東. CASE-2 では計算と同じ処理に従って，各スレッドで利. 大）のうち 32 ノード（合計 512 コア）を使用し，日立製. 用するデータを同一スレッドで初期化するようにプログ. コンパイラ，MPICH-MX を使用した．詳細について興. ラムを変更した．. 味のある読者は文献 5） を参照されたい．. 520. 情報処理 Vol.50 No.6 June 2009.
(5) 8 並列反復法と自動チューニング. Relative Performance. Initial CASE- 1 CASE- 2 CASE- 3. 1.00. 自動チューニングと性能評価モデル 本稿では，Hybrid 並列プログラミングモデルに基づ く並列有限要素法における疎行列反復法ソルバーの性能 に注目し，T2K オープンスパコン（東大）上でのさまざ まなチューニングを試みた． 「地球シミュレータ」 の場合. 0.50. と比べてさらに複雑なチューニングが必要であった．コ ア数が多く，コア当たりの問題規模が比較的小さい場合. 0.00. は Hybrid 並列プログラミングモデルの性能が相対的に Flat MPI. HB 4×4. HB 8×2. HB 16×1. Parallel Programming Models 図 -6 32 ノード（512 コア）使用時の並列反復法ソルバー部分の 相対性能：Flat MPI の CASE-1 におけるベストケースで無次元化， 1 コアあたりの自由度数は約 12.6 千．. 向上することが確認された．特に，各ソケットに MPI プ ロ セ ス を 配 置 す る Hybrid 434 は， 適 切 な NUMA. Control を適用すれば，Flat MPI に十分匹敵する性能で ある． First Touch Data Placement，データ再配置等により，. Hybrid 832，1631 の性能もさらに向上することも明ら かとなった．このことは，数億コア規模を有するエクサ CASE-3：データ再配置. スケールシステムに向けては朗報である．T2K オープ. 本プログラムでは，Hybrid 並列プログラミングモデ. ンスパコン（東大）の BYTE/FLOP 値は，0.136 程度であ. ルを適用する場合には，OpenMP 向けに並列計算時の結. り5），この値が将来さほど向上しないことを考慮すると，. 果の一貫性を保つためのデータの並び替えを実施してい. 反復法ソルバー単体のチューニングも重要な課題である. 5）. る ．この並び替えのために，同じスレッド（すなわち. が，有限要素法の不規則なデータを対象とした劇的な性. 同じコア）に属する要素は連続の番号ではなくなるため，. 能向上の達成は困難である．エクサスケールシステムの. 効率が低下している可能性がある．そこで，CASE-2 の. 全系メモリでないと入りきらないような超大規模問題以. First Touch Data Placement に加えて，CASE-3 ではデー. 外は，できるだけ多くのコア数を使って，効率的に計算. タ再配置を実施し，同一スレッドに属する要素が連続の. を実施する運用方法の考慮も必要であり，スレッド数の. 番号となるよう配慮した．. 多い Hybrid プログラミングモデルは有効である． 本稿で示したのは，特定のハードウェア，特定の問題. ⿎⿎チューニングの結果. サイズに対する 「手動チューニング」 の一例である．問題. 図 -6 は，32 ノードを使用した場合の各ケースのベス. サイズによっても各並列プログラミングモデルの挙動は. トケースの性能である．計算性能は解が収束するまでの. 異なる（詳細は文献 5）を参照） ．さまざまなペタ／エク. 反復法ソルバーの計算時間より算出している． 「Initial」. サスケールシステムでの適用を考えると，まず「CASE-. は，NUMA Control を適用しない場合であり，これが文. 3」で示した「データ再配置」のような配慮のほか：. 献 2）等で紹介されている地球シミュレータ向けの計算 とほぼ同等である．性能は，Flat MPI を使用した場合の. •. ルの選択. CASE-1 のベスト性能の計算時間で無次元化してある． 「Initial」と「CASE-1」を比較すると，Flat MPI ではそれ. 問題サイズに応じた最適な並列プログラミングモデ. •. 最適な NUMA Policy の選択. ほど大きな変化はないが，Hybrid では NUMA Control による実行時制御の有無により，2 倍から 3 倍の性能の. を自動的に実施できるような仕組みを整備する必要があ. 向上が見られる．特に HB 434 では Flat MPI より高い. る． 「自動チューニング」という観点からは，文献 3）で. 性能が得られる．. 紹介されているような性能評価モデルを開発し，ハード. HB 434 では各ソケットに 1 領域が割り当てられて. ウェア諸元と問題サイズから最適な並列プログラミン. いるため，First Touch（CASE-2）やデータ再配置（CASE-. グモデル，NUMA Policy を選択することが目標である．. 3）の影響は少ないが，HB 832，1631 の場合は効果的. 今後開発されるさまざまなアーキテクチャを使用した検. である．32 ノードでは HB 434 が最も良く，HB 832，. 証を繰り返しつつ，性能評価モデルを整備していく必要. 1631 も Flat MPI に匹敵する性能である．. がある．実用的には，本稿で紹介したアプリケーション 情報処理 Vol.50 No.6 June 2009. 521. ソフトウェア自動チューニング技術の応用. 1.50.
(6) 特集）科学技術計算におけるソフトウェア自動チューニング を実際に動かしてみて，コア数，問題規模に応じて最適 な並列プログラミングモデルを選択することも可能であ る．本アプリケーションは T2K オープンスパコン （東大） 上で，数分以内に終了するので，ベンチマークとしては 適切である．. Computing, SIAM Conference on Computational and Engineering (CSE09), Miami, FL, USA (2009). 5）中島研吾 : マルチコアクラスタにおける有限要素法アプリケーション のための階層型領域間境界分割に基づく並列前処理手法，情報処理学 会研究報告 (HPC-119-18), pp.103-108 (2009). 6）Mattson, T. G., Sanders, B. A. and Massingill, B. L. : Patterns for Parallel Programming, Software Patterns Series (SPS), Addison-Wesley (2005). （平成 21 年 3 月 31 日受付）. 参考文献 1）Rabenseifner, R. : Communication Bandwidth of Parallel Programming. Models on Hybrid Architectures, Lecture Notes in Computer Science 2327, pp.437-448 (2002). 2）Nakajima, K. : Parallel Iterative Solvers of GeoFEM with Selective Blocking Pre-conditioning for Nonlinear Contact Problems on the Earth Simulator, ACM/IEEE Proceedings of SC2003 (2003). 3）Kerbyson, D. J., Hoisie, A. and Wasserman, H. : A Comparison between the Earth Simulator and Alpha Server Systems using Predictive Application Performance Models, LA-UR-02-5222, LANL (2002). 4）Sexton, J. : Computational Science Challenges from Petascale and Exascale. 522. 情報処理 Vol.50 No.6 June 2009. 中島 研吾（正会員） [email protected] 東京大学情報基盤センター教授・工学（博士） ，専門は計算力学・数 値線形代数・並列プログラミングモデル，平成 20 年度山下記念研究賞．.
(7)
図
関連したドキュメント
テキストマイニング は，大量の構 造化されていないテキスト情報を様々な観点から
一階算術（自然数論）に議論を限定する。ひとたび一階算術に身を置くと、そこに算術的 階層の存在とその厳密性
[r]
[r]
第４ 回モニ タリン グ技 術等の 船 舶建造工 程へ の適用 に関す る調査 研究 委員 会開催（ レー ザ溶接 技術の 船舶建 造工 程への 適
英語の関学の伝統を継承するのが「子どもと英 語」です。初等教育における英語教育に対応でき
分だけ自動車の安全設計についても厳格性︑確実性の追究と実用化が進んでいる︒車対人の事故では︑衝突すれば当
ご使用になるアプリケーションに応じて、お客様の専門技術者において十分検証されるようお願い致します。ON
