2011年8月4日木曜日

AICS Summer School 3日目

9時開始なのに、起きたら8時半で危うく遅刻しそうになった3日目。

そして講義の初っぱなからこんな↓数式が出てきて僕のCPUが熱暴走を起こしました。




これは一次元熱伝導方程式を有限体積法による空間離散化で求める際の熱流束に関するつりあい式です(詳しくは分かりませんw)第一項では要素i(色つき五角形)とそれに隣り合わせの要素kでどのように熱が伝わっていくかを示す。第二項の温度境界面は図中T(iBe)の面が空気や水に触れていると仮定し、面で一様に温度勾配があり、それが要素iの中心に伝わっていく様子を示す。第三項はq(id)の面で温度勾配が一様でないことを仮定する。第四項は要素iの要素体積が発熱する様子を示す。

この式が要素1,2,..i,...N分だけ並んでいる。

んでこの式を求めるためのプログラムがあり、その解説がまず行われました。
が、まず理論の背景が分からん。講義資料が膨大。それを駆け足で説明。しかも言語が説明されるのはFortranで作られたプログラム(Cで書かれたコードのファイルもあるが)。今日は何度も置いて行かれそうになりながらついていくのがやっとでした。

有限体積法では内部熱伝導(要素間のコネクティビティ)、ディリクレ境界条件(表面温度固定)、ノイマン境界条件(表面熱流束)のためのパラメタを持つメッシュデータを読み込み、上記方程式の各項を要素iについて計算します。

この方程式は行列ベクトル計算と見なすことが出来ますが、このままではコネクティビティのパラメタから計算される行列が疎行列であり(各要素は隣り合った要素としか関係を持たないため)、無駄なデータを多く持つことになり計算の効率が悪くなります。

そこで、上記の式を変形し、以下のようにします。



こうすると、先ほどの疎行列の対角成分と非零非対角成分しか使わないで済むようになるので、要素間コネクティビティのパラメタからなる行列より、CRS(Compressed Row Strage)法を使って対角成分と非零非対角成分のデータのみ抽出することで、計算の効率化を図ります。あとは変形後の方程式を解くだけですが、これは要素1~NでみるとAx=bの形をしているので(AがCRSした行列、xは各要素の温度を表すベクトルTに相当、bは右辺)、反復法(共役勾配法)によるソルバーを用います。

共役勾配法ソルバーについてはまだコードを概観しただけでちゃんと理解が及んではいない。

そして、このプログラムを並列化するための準備として、午後は局所分散データ構造・領域分割について学びました。
SPMDの考え方から、MPIでは各プロセスで実行される命令は同じだが、扱うデータが違うようにする必要があります。

このとき、有限体積法プログラムなどでは隣り合わせの要素のパラメータを使った計算があるので、プロセスによっては他のプロセスの持つデータを貰ってこなければいけないことがあります。従って、各プロセスの持つデータはオーバーラップ付きの局所分散データ構造をとる必要があり、どこが内点で、どこが外点(他のプロセスからの受信あるいは他のプロセスへの送信が必要な領域)で、どこが中間点であるかをプログラマがしっかりと理解することが不可欠です。

今回の講義では、より簡単な二次元配列データを分割し、3プロセスでオーバーラップ付き局所分散データを分担、外点を送受信するプログラムを実際に作りました。
この外点の送受信の場合、プロセス間通信のあり方としては、全てのプロセスが単純にsend,recvするだけでは昨日も書いたデットロックが生じてしまうので、非ブロック通信を行うためにMPI_Send,MPI_Recvの代わりにMPI_Isend,MPI_Irecv,MPI_Waitallを使う(この際通信識別子と状況オブジェクト配列をちゃんと定義すること)。

これには4時間ほど費やして座学演習を行いましたが、それほどに領域分割と局所分散データ構造の概念は並列処理で重要なものだそうです。


また、最後には「どのようにデータを分割すればいいか」を自動的に最適化するPartitioningツールとして、METISが紹介されました。

METISはメッシュデータだけでなく二次元行列の分割にも使えるし、フリーソフトで自前のプログラムにも組み込めるので、系統解析のソフトにも使えるかも知れません。ただ、系統解析にある計算で、データをどのように分割しているのか(例えば配列データをサイトごとに分割しているのか)が分からないと、このツールの有用性は分かりませんね。そもそも系統解析だと疎行列を使うのだろうか、それとも密行列を使うのだろうか・・・?

ちなみに、上記の有限体積法の計算結果では、下のような三次元メッシュでどのように熱が伝わっていくかを示す図が得られます。

0 件のコメント: