2011年7月7日木曜日

CCS HPC SS 二日目

*注:このブログは生物学を主に取り扱う研究室のです。あしからず(?)

二日目は並列処理化する計算アルゴリズムの具体例としての高速フーリエ変換の話から始まりました。フーリエ変換は学部生のときにチャレンジしましたが、難易度Lunaticだったので逃げ出してしまった苦い記憶があります。

高速フーリエ変換(FFT)は離散フーリエ変換(DFT)を高速に計算するためのアルゴリズムで、DFTの周期性に着目して行列の分解を行い、演算量の減少を狙います。理学的には偏微分方程式の解法、工学的には信号処理などの分野で使われるみたいです。

FFTのやり方については、バタフライ演算に則ったCooley-Tukey法までなら分かりました。この方法は仕組み的にもMPIに適応する場合を直感的に理解することができたので、苦ではなかったです。が、続くSix-Step FFTやNine-Step FFTなんかのアルゴリズムは理解不能でしたね。なにやってんのか数式見てもプログラム見ても分かんない。まあフーリエ変換自体は多分分子系統解析では使わないと思うので、いいか・・・

この講義で重要だったのは、データをどのように分割するかということだったでしょう。データ(問題領域)のサイズは、それがキャッシュに載るか載らないかという点で計算処理の効率に大きく影響します。でかいデータを一気に処理しようとすれば、そのデータがキャッシュに入りきらず、処理プロセスがパンク状態になってしまいます。従って、データ分割(ブロック分割、サイクリック分割、ブロックサイクリック分割、またそれらを一次元でやるか二次元でやるか)をし、キャッシュ容量にあったサイズのデータを処理できるようにすることは、プログラムを書くときにはきちんと吟味しないといけない課題です。
この点は次の最適化の講義でも重要だったと思います。

最適化の講義では、ソフトウェアの最適化と通信の最適化について学びました。まずはソフトウェアですが、最近ではコンパイラも優秀だしプロセッサも高性能だから、ソフトウェアをプログラマ側がちゃんと最適化して性能チューニングするという認識が甘い人が多いみたいです。

んで、ちゃんと最適化しようとすると、まずプロファイラ(例えばgprof)を使ってコードのどの部分がホットスポットなのかを同定する必要があります。(実際の計算処理ではコードの5%が全体の処理の95%を占める)

ホットスポットが分かったなら、その部分に対して最適化を行いますが、この時大切なのがデータの再利用性です。再利用性のないデータ処理では記憶域(メモリ、キャッシュ、レジスタとか)に対するアクセスパターンの局所性が無くなり、特にキャッシュに載るか否かの境界を超えると、問題の規模に応じて処理性能が下がってしまいます。なので、計算処理は行列ベクトル積やベクトル積ではなく、行列同士の積にして、再利用性を高めることが重要です。また、コードの中でループアンローリング(ループの展開)をして、ロード・ストア回数に対する浮動小数点演算回数の比を大きくすることも有効です。

あとはループの入れ替え(ストライドの減少)、パディング(スラッシング予防)、ループのブロック化(データの分割とメモリ参照の最適化)とか。ループアンローリングはレジスタブロッキング、ループのブロック化などはキャッシュブロッキングに有効みたいですが、プログラマ側がどこでそれを区別するのかはまだいまいちよく分かってません。

また、浮動小数点演算命令(SSE3)についての話もありました。今ではSSE4.2とか出てますが、SSE3とSSE4では新しい命令はあまり追加されてないようです。

それよりも、sandy bridgeで追加されたIntel AVX命令の方が効果的とのことです。AVXではこれまで128bit長のデータにSIMD処理してたのが256bitまで拡大されたので、計算処理の向上はかなり見込めるみたいです。

AVXはICCで対応してるみたいなので、sandy積んでるPC買って性能を見てみたいですね。GCCでは5になるまで対応しないんじゃないか、ということらしいです。

さて一方で、MPIでの通信の最適化を考えたときには、扱うデータサイズが大きいほど性能がいい(スループット・通信バンド幅が大きい)とのことです(データサイズが十分大きくなるとピークには達してしまうのですが)。とりあえず、元々のデータが小さいならまだしも(それなら並列処理しなくてもいい)、でかいデータをちまちま分けて通信しては当然粒度が細かくなってしまうし、なるべくでかいデータを通信し、各計算処理ではデータの分割を行って最適化をする、というのがいいようです。なるべくでかいデータを通信するためには、複数の通信データを纏めて一回で通信する(通信ブロッキング)ことが有効で、どうしても小さいデータを個別に通信しなければならないときには、非ブロック型通信を利用して通信と計算処理のオーバーラップを試みるのが良い。ちなみに、大抵研究室レベルまでで所有するクラスタ計算機では、ネットワークとしてGigabit Ethernetが使われますが、Gigabit Ethではパケットを落とすことがあるので、通信性能が安定しないことが往々にしてあるみたいです。T2KなんかはInfiniBandを使っているので、パケットを落とすことはないです。


OpenMPの講義はMPIよりは分かりやすかったです。まずプログラムの書き方がMPIよりは単純だったことが一番でしょうね。

OpenMPは共有メモリ型システムでの並列処理用の並列プログラミングモデルですが、共有メモリ型システムでもMPIは使用可能で、実は共有メモリ型システムでOpenMPとMPIを実行したときにはMPIの方が性能が良かったりするそうです。共有メモリ型では通信や同期のコストがMPI,OpenMPでほぼ差がないので、MPIの方が遅くなる道理はありません。さらに、MPIではメモリが分散していることが前提となっているので、同じ共有メモリ型での処理でもメモリアクセスの最適化という点でMPIの方に分があるのでしょう。(ハード的にはNUMAみたいなもんか)

ただ、OpenMPはコードを書くことが容易だし、並列処理のためのコーディングの練習や、16コア以下の共有メモリ型システムでのみ使うプログラムの開発にはやはりOpenMPを使うのがいいと思います。ちなみにOpenMPでもソフトを使うことで分散メモリ型システムにも対応可能みたいです。

ざっとこんな感じでしたが、この二日間は非常に濃かったですね。このサマースクールで学んだことはちゃんと復習して、後に続く試験や神戸理研のSS(連絡来ないけど行けるのかな?そして宿泊費とか支給してもらえるようになったのかな?)に生かそうと思います。

まあ今はそれはおいといて、これからマニュアルとの対決を再開せねば。解析に使うプログラムは選定できてマニュアルも凄く丁寧に作られて読みやすいんですけど、とにかく長い。PAMLくらい。ちゃんとオプションとか調べてないといけないので熟読する必要がありますが、早いとこ一気に解析したい。

0 件のコメント: