ＭＰＩ行列計算（圷・牧野・内藤班）
ポイント
- SendとReceiveのみで実装されている。
- 任意の台数で実行できる。
- 任意の行列のサイズで実行できる。
通信の高速化
行列の分割方法
Ｎ台のマシンで計算をする場合、Ｐ＊Ｑ＝Ｎで、差が最小となるような自然数ＰＱでそれぞれの行列を分解する。たとえば、Ｎが８のときはＰ＝４、Ｑ＝２となる。そして掛け合わせる行列をＡ、Ｂとすると、Ａを４つに、Ｂを２つに分解する。分割されたそれぞれの行列を下の図のように組みあわせ、計算する。
行列ＡＢの送信
行列Ａ，Ｂを各プロセスに送信する。プロセスに０〜Ｎ−１の番号が振られている場合、分割されたＡをA(0),A(1),A(2)・・・A(P-1)とすると、A(i)をプロセスi,i+P*1,i+P*2,・・・・i+P*(Q-1)に送信する。また、分割されたＢをB(0),B(1),B(2)・・・・B(Q-1)とすると、B(i)をプロセスi*Q,i*Q+1,i*Q+2,・・・・,i*Q+(P-1)に送信する。
送信方法
サイズの等しいＭ種類のデータをＭ＊ＲのプロセスにＲ個づつ送信する効率のよいと思われる方法は次のとおりである。
まず、１種類のデータをＲ個のプロセスに送信する方法（BroadCast）を考える。以下のような木を作り、送信すればroot(R)の手間で送信できる。
たとえばＲ＝８のときは上のような木を作ればすべてのプロセスにおいて通信は手間３で終了する。
この木は再帰的に次のように定義できる。
- broadcast(k)はbroadcast((K-1)^2)とbroadcast((K-1)^2)の親を連結し、一方を親と決めたもの。ただし、新しくできた親はまず最初にこの連結間で通信をする。
- broadcast(1)は各プロセスに相当し、それ自身が親である。
次に、Ｍ種類のデータをＭ＊ＲのプロセスにＲ個づつ送信する場合を考える。
開始プロセスは、Ｒ−１個の第二の親プロセスを決め、それぞれの親ごとに異なるＲ−１種類のデータを送る。そして送り終えたところで、開始プロセス自身が第二の親となり、すべての第二の親は自分の子プロセスにデータをbroadcastする。
この方法だと、root(R)+M-1の手間ですべてのデータを送信できる。
ＡとＢの行列を両方送る場合、(root(P)+Q-1)+(root(Q)+P-1)の手間がかかる。
受信方法
すべての結果をプロセス０（開始プロセス）に一気に集めると、最終的な行列の形にするために、大規模なメモリのコピーが必要になる。このコピーによるオーバーヘッドは以外に大きいので、一度、各第２の親プロセスに結果を集め、そこで行列の整形を行ってから第１の親プロセスに送ることにした。これで、メモリコピーの手間を1/Pにできるが、無駄な送信が増えるため、通信速度の遅い環境だと、一気に第一の親プロセスに集めてしまったほうが早い場合もあるかもしれない。
また、メモリのコピーには、memcpy関数を使って高速化している。
行列演算の高速化
行列演算の高速化に対するアプローチは以下のとおりである。
行列のブロック化
二次キャッシュのヒット率を上げることができる。
ループのアンローリング
最も重視するべきなのはループの最も内側のオーバーヘッドを削減することである。for文による分岐命令を減らすことができる。しかしやりすぎると、コードが巨大になり、それ自身がキャッシュに納まらなくなるので、適度にする。
レジスタ変数の使用
ループの内側にあるような最も頻繁にアクセスされる変数にレジスタ変数を割り当てることで、よりきめ細かく動作を指示でき、コンパイラによる余計な最適化を避けることができる。
コンパイラ
Folon3のＯＳがRedHat7.1であったので、それに対応したIntel社から無償で公開されているコンパイラを使用した。プロセッサ用の特殊な命令コードを使うので、非常に高速化される。Edamは対応するバージョンがなかったため、gccでコンパイルした。
結果
- 計算対象の行列は、自然数列を生成しそれを使用した。
- 結果の値は何回か計測した中で最も早いものを採用した。
- かけられるほうの行列はあらかじめ転置されているものとした。
- 実行時間には含まれていないが、実行結果の正当性はチェックした。
Folon3
仕様
並列マシン(8台)
Intel PentiumIII 1Ghz
ネットワーク：myrinet2k
キャッシュ：512 Kbyte
OS : RedHatLinux7.1
通信・行列演算
| サイズ・台数 |
1 |
2 |
4 |
6 |
8 |
| 1000×1000 |
3.160215 |
1.703865 |
0.966179 |
0.724819 |
0.595649 |
2000×2000 |
25.857840 |
13.368239 |
7.052869 |
5.050389 |
3.977846 |
3000×3000 |
- |
44.617790 |
23.171409 |
16.196120 |
12.553940 |
4000×4000 |
- |
- |
- |
37.963817 |
29.095459 |
通信のみ
| サイズ・台数 |
2 |
4 |
6 |
8 |
| 1000×1000 |
0.126600 |
0.176368 |
0.2003109 |
0.199336 |
2000×2000 |
0.505231 |
0.697185 |
0.798988 |
0.606364 |
3000×3000 |
1.710484 |
1.531072 |
1.754059 |
1.741623 |
4000×4000 |
2.028043 |
2.721654 |
3.124276 |
3.106741 |
Edam
仕様
Ultra enterprise 4000 (Sun)
Ultra SPARC 167MHz * 10 個
メモリ：256 (= 8 * 32) MByte * 5 枚 = 1280 MByte
キャッシュ：512 Kbyte * 10
OS : Solaris2.5.1
通信・行列演算
| サイズ・台数 |
1 |
2 |
4 |
6 |
8 |
10 |
| 1000×1000 |
33.983181 |
17.254878 |
8.750679 |
6.012076 |
4.619827 |
3.742117 |
2000×2000 |
- |
- |
- |
47.364784 |
36.186154 |
29.127327 |
通信のみ
| サイズ・台数 |
2 |
4 |
6 |
8 |
10 |
| 1000×1000 |
0.304640 |
0.337489 |
0.358953 |
0.385802 |
0.381394 |
2000×2000 |
1.049632 |
1.281590 |
1.416138 |
1.523557 |
1.533921 |
folon4
仕様
並列マシン(16台)
Intel PentiumIII 1.2Ghz×2
ネットワーク：myrinet2k
キャッシュ：512 Kbyte
OS : RedHatLinux7.2
通信・行列演算
| サイズ・台数 |
1 |
2 |
4 |
8 |
16 |
32 |
| 1000×1000 |
2.503601 |
1.441973 |
0.885680 |
0.551317 |
0.413384 |
0.315199 |
| 2000×2000 |
20.435509 |
11.202000 |
6.138873 |
3.512726 |
2.313990 |
1.614884 |
| 3000×3000 |
- |
37.841344 |
20.363139 |
11.201318 |
6.758927 |
4.380207 |
| 4000×4000 |
- |
- |
47.058436 |
25.297544 |
14.894702 |
9.321221 |
| 5000×5000 |
- |
- |
- |
45.747425 |
26.283388 |
16.032726 |
| 6000×6000 |
- |
- |
- |
- |
44.482365 |
26.259553 |
| 7000×7000 |
- |
- |
- |
- |
- |
41.561834 |
| 8000×8000 |
- |
- |
- |
- |
- |
61.100860 |
問題点
- 素数台の計算機で実行するときに効率が悪い。
- 行列をすべてのプロセスに送信し終わるまでに暇なプロセスが存在する。
ソース