 |
 |
| ホーム | 主筆 | その他ソフト | その他情報 | Syuhitu.org | English |
Windows関連
Solaris関連
画像入出力
その他アルゴリズムなど
自動並列化を試してみる
[1] 
主筆嬢 06/04/15 13:05
最近のSunのコンパイラには自動並列化機能がついているらしいから、試してみることにする。
[2] 
nabiki_t 06/04/15 13:07
かなり久しぶりの更新なのに挨拶もねぇのか。
[3] 主筆嬢 06/04/15 13:09
どうでもいいじゃん。そんなもの。
でぇ、自動並列化を試すということは、何らかのプログラムをコンパイルして動かしてみるって事になるんだけど、そうすると何のプログラムを使うのかって事が問題になる。
自分で適当なプログラムを作って、それをコンパイルして走らせてもいいのかも知れない。だけど、それだと何か説得力に欠けるような気がするから、今回は既製品のベンチマーク・プログラムを使う事にする。
[4] 主筆嬢 06/04/15 13:10
そう言うことで、使うプログラムはSPLASH-2のLU分解のプログラムを使う事にする。
一応、これが元のプログラム(LU_non_contiguous.c)。
[5] 主筆嬢 06/04/15 13:16
自動並列化をやる前に、比較参照用にOpenMPで並列化をやってみる。
だから、まず最初はこのプログラムがどういうアルゴリズムで計算を行ってるのかを考えてみる。
そーゆーことで、後はよろしく。
[6] nabiki_t 06/04/15 13:18
「よろしく」ってなんだよ。
解説丸投げかよ。横着な野郎だ。
しかたねぇな・・・
[7] 
広告 06/04/15 13:26
ブロック
まず、このプログラムでは行列はブロックに分割される。
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 行列の大きさは、デフォルトでは128×128。ブロックの大きさは、デフォルトでは16×16。ただし、これは起動時のスイッチで変更できる。
着目点
このプログラムの中で、特に注意してみるべきは関数LU。そこで実際のLU分解を行っている。
それ以外の奴は、とりあえず無視。
主な動作
関数LUの中のkのループが一番外側のループ。これは、縦ないし横のブロック数-1回廻る。
kのループの中では、主に4つの処理を行っている。
Ａ
(k, k)のブロックに対して、関数lu0の処理を行う。正直言ってlu0で何をやっているのかがよく判らない。プログラム中のコメント、ないし、俺の手元の資料では対角行列を求めるといっている。本当だろうか？ よく判らない。
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｂ
Ａでいじったブロックの右にあるブロックと、Ａでいじったブロックに対して、関数bdivを適用する。プログラム中のコメントによれば、下記の青いブロックで赤いブロックを割り算しているらしい。
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｃ
Ａでいじったブロックの下にあるブロックと、Ａでいじったブロックに対して、関数bmoddを適用する。
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｄ
残りのブロックを、その上と左にあるブロックを使って更新する。関数bmodを適用する。
一つ目
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 二つ目
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 の、要領で
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 残りのブロックを更新する
その後はkが一つ進んで、Ａに戻る。つまり、
Ａ
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｂ
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｃ
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 Ｄ
16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 16×16 と、繰り返す。
・・・ってこんな感じでいいか？
[9] 主筆嬢 06/04/15 13:37
はい、おつかれさん。
[10] 主筆嬢 06/04/15 13:38
で、ようやくOpenMP化なんだけど、その前にプログラムの簡略化を考えてみる。
元のプログラムは何の嫌がらせか知らないけど、やたら汚い。それに、時間を計る処理がたくさん入っていて、全体的な見通しが悪い。
このままだと並列化のしようがないから、ここは思い切ってLU分解のアルゴリズムに関わる部分以外は全部削っちゃう。
そうしてできたのがこれ(LU2.c)。
とりあえず、手当たり次第にコメントアウトしまくってみた。でもって、古い表記を修正した。
[11] 主筆嬢 06/04/15 13:39
そう言うことで、OpenMPでの並列化、よろしく。
[12] nabiki_t 06/04/15 13:40
「よろしく」じゃねぇよ。
おまえがやれ、おまえが。
[13] 
主筆嬢 06/04/15 13:41
あーそー。
判らないんだ。
ふーん。
[14] 主筆嬢 06/04/15 13:45
そういうことで、私がさっきのプログラムをOpenMPで並列化してみた。
OpenMPの使い方はこの辺とか、この辺（バージョン1.0の日本語訳）を見ておけばいいと思う。まぁ、英語が分かるならopenmp.orgで公開してる正式な仕様書（バージョン2.5）を見るのが一番確かなんだけど。
で、苦労して作り上げたのがこれ(LU3.c)。
[15] 主筆嬢 06/04/15 13:46
ばかに代わってちょっとだけ解説しておく。
まず、並列化できるのは>>8で言うところのＢ・Ｃ・Ｄの処理。これは各ブロック間の処理に依存性がないから並列化できる。
だからＢ・Ｃ・Ｄの処理のループの前に「#pragma omp parallel for ・・・」と書いてあげればいい事になる。
具体的には、LU3.cのプログラムにおける、関数LUの中の285行目・297行目・307行目のforループが並列化の対象になる。
ここで気を付けなきゃいけないのは、関数LUで定義されている自動変数の内のいくつかがループ内で使われているということ。こういった奴は、private指示節で明示的にプライベートにしてやる必要がある。
例えば285行目のループ内で使われている変数「il」なんかが問題になる。ループ内がマルチスレッドになるんだから、何もしなかったら286行目の代入でおかしくなるのは目に見えてる。
[15] 主筆嬢 06/04/15 13:48
[16] 広告 06/04/15 13:50
[17] 主筆嬢 06/04/15 13:53
そういうことで、実行してみる。
ここでは、行列サイズは4096×4096、ブロックサイズは64×64を使っている。つまり、実行時のコマンドは「a.out -n4096 -b64」ということ。
それと、実行環境はいつものFire v250。
まずは逐次。
使用したプログラム コンパイル時のスイッチ 実行時間(ms) 32bit LU2.c -fast 842,896 64bit LU2.c -fast -xarch=v9 781,027 今度はOpenMP版
使用したプログラム コンパイル時のスイッチ 実行時間(ms) 32bit LU3.c -fast -xopenmp=parallel 345,458 64bit LU3.c -fast -xopenmp=parallel -xarch=v9 324,978 一応、-xloopinfoスイッチを指定してコンパイルしたときに表示されたメッセージも示しておく。これを見る限りではちゃんとOpenMPでの並列化は行われているみたい。
[18] nabiki_t 06/04/15 13:55
おい、なんか、おかしくないか？
なんで並列化して実行時間が半分以下になってるんだ？ CPUが二つあるから半分強になるというのであれば判るけど、半分を下回っちゃったらおかしいんじゃないのか？
[19] 
主筆嬢 06/04/15 13:57
そう、なんだけどねぇ。
まぁ、早くなったから、いいんじゃない？
[20] nabiki_t 06/04/15 14:00
いいわけないだろう。
[21] 主筆嬢 06/04/15 14:03
細かいことには目をつぶって、ここで本題の自動並列化を試してみる。
自動並列化するには-xautoparというスイッチを指定してあげればいい。あと、Sun CCのマニュアルを見ると、実行する際には使用するCPUの数を、環境変数「PARALLEL」に指定しろって書いてある。
だから今回は「export PARALLEL=2」としてから実行した。
使用したプログラム コンパイル時のスイッチ 実行時間(ms) 32bit LU2.c -fast -xautopar 406,475 64bit LU2.c -fast -xautopar -xarch=v9 375,052
[22] 主筆嬢 06/04/15 14:05
-xloopinfoのメッセージを見ると、中にこんな記述がある。
「"LU2.c", 516 行目: 並列化されます、逐次版が生成されました(インライン化されたループ)」
これは一体どう解釈したらいいのだろうか？ 並列化したのか、してないのか？ とりあえず実行してみると、実行時間は大分短縮されているようだけど。
[23] 主筆嬢 06/04/15 14:06
まぁ、速くなったから、いいか。
[24] nabiki_t 06/04/15 14:08
いや、だから、いいわけないだろう。
[25] 主筆嬢 06/04/15 14:10
細かいことは気にするな。
とりあえず、自動並列でもある程度速くなるっていうことでめでたしめでたし。
[26] 主筆嬢 06/04/15 14:15
それと後、余談だけど。
OpenMPで並列化したついでに、MPIでも並列化してみた(LU4.c)。
まぁ、何かの参考にでもなれば。
[27] 主筆嬢 06/04/15 14:17
一応、実行したらこういう結果になった。
行列サイズ＼実行台数 2台 4台 8台 16台 1024×1024 1,313 1,431 1,774 2,941 2048×2048 14,536 15,238 17,478 30,968 4096×4096 119,727 118,907 138,017 160,005 単位はms、ブロックサイズは128×128。
実行環境は
mpi処理系 mpich OS linux 2.6.8-2-686 コンパイラ gcc 3.3.4 CPU Pentium XEON 2.8GHz ネットワーク 1Gbps Ethernet ちなみに、同じ環境で逐次で実行した場合は
1024×1024 1,404 2048×2048 10,445 4096×4096 84,141 こうなった。
[28] nabiki_t 06/04/15 14:20
いろんな意味ですっげー悲しい結果になってないか？
逐次で実行した方が圧倒的に速いし、XEONの方がSPARCより10倍も速いし。
[29] 主筆嬢 06/04/15 14:25
細かいことは気にするな。
[30] nabiki_t 06/04/15 14:26
泣けるぜ・・・
[19] 名無しさん 06/04/15 14:30