第十四報：分散コンピューティングに挑戦！
所用で分散コンピューティングに手を出す可能性が出てきたので、今のうちに勉強しておこうと思って LAM という MPI（メッセージ通信インタフェイス）のライブラリをインストールしてみました。（非職業）プログラマの血が騒ぐような騒がないような微妙なところですが（何じゃそりゃ）、やはり何となく楽しみなところではあります（結局楽しみなんかい！）。
ということで、今回のプログラマの友のテーマは「分散コンピューティング」です。計算機科学などで使われるこの技術は、巨大な計算を沢山のコンピュータを使って並列計算しよう、というものです。そこではプログラム上、ハード上の様々な問題がありますが、それらにできるだけ無駄な労力を割かないようにするためにはやはり専用のライブラリが必要だと思います。
今回私が使ったのは上記にある MPI という規格に沿った LAM（Local Area Multicomputer）というライブラリです。他にも MCI-1.0 の規格作成を行ったグループの作った mpich というライブラリもありますが、最新規格 MPI-2 への対応がいまいちなのでスルーしました。
基本的な説明から実際に使ってみるところまで話すつもりですが、なにぶん初めてのことなのでこまごましたところまでちゃんと合ってるかは疑った方がいいかもしれません。
MPI は message passing interface（メッセージ通信インタフェース）の略で、並列コンピューティングを行うために作られたライブラリの規格です。上述の通り、実際この規格をもとに作られたライブラリには mpich や LAM などがあります。
「並列コンピューティング」というのは１台に複数のＣＰＵを付けて並列計算するのも、多くのコンピュータを繋げて計算するのも、両方を意味するものです。とにかく「複数のＣＰＵで高速に計算してやろう！」というのがアイディアの根底にあります。
並列化処理で問題になることは、多ＣＰＵを使う方法や、複数のコンピュータ間での通信法がプラットフォームに依存することだったようで、MPI はそれを統一的に扱えるようにするために作られたようです。
2002年11月現在では、新しい規格 MPI-2 が作られ、各ライブラリが対応に奔走しているところのようです。フリーなライブラリでは LAM が一番対応が進んでいるようです（間違ってたらすみません）。Red Hat Linux 7.2 と 8.0 で確認したところ LAM パッケージが含まれているようなので、LAM を使うのが一番楽なのかもしれません。
今回使ったパソコンの OS も Red Hat Linux 7.2 ということで LAM が入っていましたが、最新のバージョンを使いたいこともあってインストールしました。インストールの方法については第３節で話します。
さて、実際プログラムに入る前に、ちょっと並列化について話したいと思います。
みなさんは「何でも並列化すれば速くなる」と思いますか？ 思いませんか？ 常識的に考えれば、ある仕事を１００万人でやったからといって１００万倍効率が上がるわけではないので、答えはＮＯであることが分かります。
では、なぜこのようなことが起こるのでしょうか？ 問題は主に次の２つに分けられます。
１．の通信速度については簡単な話です。10秒で終わる処理なのに、例えば通信に20秒もかかったらそれだけで遅くなってしまいますよね。極端な例のように見えますが、実際巨大計算を行う場合には巨大なデータを送る必要がある場合があるので、通信時間はかなり重要になってくるようです。聞いた話ではＬＡＮの良し悪しはある程度以上はそれほど大きくは効いてこないようで、通信量をなるべく減らすことの方が重要なようです。
例として、巨大な行列の積をとることを考えます。正方行列の積は
for(int i = 0; i < d; i++)
{ for(int j = 0; j < d; j++)
{ for(int k = 0; k < d; k++)
{ c[i][j] = a[i][k] * b[k][j]; }
}
}
という形になります。これを何も考えずに c[x 〜 x + d/n][0 〜 d-1] の範囲の計算を n 台のコンピュータに渡すと（x は各コンピュータ毎に割り当てられる領域の始点です）、それぞれのコンピュータは a[x 〜 x + d/n][0 〜 d-1] と b[0 〜 d-1][0 〜 d-1] のデータが必要になります。この場合、全体の通信量は a の d2/n と b の d2 と c の d2/n を合わせて n 倍すれば求められ、d2(n + 2) になります。
これを c[x 〜 x + d/m][y 〜 y + d/m] というブロックに分割して n = m2 台のコンピュータに渡すようにすると、それぞれのコンピュータは a[x 〜 x + d/m][0 〜 d-1] と b[0 〜 d-1][y 〜 y + d/m] のデータで済むようになります。すると、全体の通信量は a の d2/m と b の d2/m と c の d2/m2 を足して n 倍して、d2(2m + 1) になります。例えば m = 2（n = 4）の時は 5d2 で、上の 6d2 より無駄な通信量が減っていることが分かります。m = 4（n = 16）の場合は 9d2 と 18d2 と、さらに差が開きます。
しかし、見れば分かるとおり台数を増やすと通信量が増え、いずれ通信量と並列化による恩恵とが逆転して、台数を増やすと逆に遅くなるという事態に陥ります。扱わなければならない計算によっては、通信量が多すぎて並列化できないということもあるようです。
あと、上の例は思いつきで書いたので、行列の積に関するもっといい分散法があるかもしれません。あしからず。
２．のアルゴリズムについてですが、これは単にアルゴリズムが遅いというのではなく、並列化に向いたアルゴリズムになっていない、もしくは、なりようがないということです。通信量を抑えることも確かにアルゴリズムの問題ではありますが、ここでいうアルゴリズムというのはそれとは別の話です。
例えば同じ初期化作業を各コンピュータで行わなければならないとき、それは並列化には何の寄与も与えませんよね。また、処理するべき量にばらつきがあると、沢山の作業を割り当てられたＣＰＵの処理が終わるまで作業が完了しません。また、ある計算の結果を使わなければ次の計算ができないという場合、両者の計算を完全に並列化することは不可能です。これらの場合は一切通信が発生しないので、純粋にアルゴリズムの問題になります。
アルゴリズムの x が純粋に並列化されているとします（100 % を 1 、0 % を 0 とします）。これを並列化率と呼びます。ここでは通信速度は無視して、純粋にアルゴリズムのみを考えます。この場合、2 台のコンピュータで計算すると、処理時間は x/2 + (1-x) になります。100 % 並列化されていれば 0.5 （半分）になりますし、全く並列化されていなければ 1 （変わらない）になります。
同じように考えると、n 台のコンピュータで計算すると、処理時間は x/n + (1-x) になります。ここからコンピュータを a 倍に増やした場合、処理時間は {x/an + (1-x)} / {x/n + (1-x)} = 1 + (1/a - 1)/{1 + n(1-x)/x} 倍になります。
このように、完全に 100 % 並列化されている場合は、処理時間は素直に 1/a 倍になってくれます。しかし、例えば 50 % しか並列化されていない場合は、処理時間は 1 - 1/(1+n) + 1/a(1+n) 倍にしかなってくれません。n が大きくなると 1/(1+n) が小さくなり、台数を増やしてもあまり処理速度が上がらなくなってしまいます。これを飽和と呼びます。
一般的に考えると、1/{1 + n(1-x)/x} が小さくなれば、つまり n(1-x)/x が 1 より随分大きくなれば、それ以上台数を増やしても仕方がないということになります。この値が 100 になったときに飽和したとみなすと、飽和台数は 100x/(1-x) 台と求められます。これに従うと、理想的な飽和台数は並列化率 99 % の時には 9900 台、90 % の時には 900 台、50 % の時には 100 台、20 % の時には 25 台ということになります。
また、上にあるように、台数が多い場合に効率を十分上げるには a 台増やすというのではなく、a 倍にするという風にしないといけません。この場合、キリよく 2 の累乗の台数を使うようにしているところが多いみたいです。
たとえば、n 台のコンピュータがあるところに a 台マシンを増やした場合、処理時間は {x/(n+a) + (1-x)} / {x/n + (1-x)} = 1 - {a/(n+a)} / {1 + n(1-x)/x} 倍になります。
このように、完全に 100 % 並列化されていても a 台増やした時の処理時間は 1 - a/(n+a) 倍にしかならず、n が大きくなれば少々台数を増やしてもあまり処理時間は変わらなくなります。今ある台数と同程度のオーダーの台数を増やして初めて速くなるのです。
このように、何でも並列化すれば速くなるのではなく、並列化には限界があるのです。その１つの目安となるのが並列化効率です。並列化効率は n 台使った場合に 1 台の時よりも何倍速くなったか、というものです。並列化効率は一般に台数が増えるごとに減っていきます。そして、そのうち並列化効率は殆ど増えなくなり、最後にはむしろ悪くなるのが普通のようです。上の理想的なアルゴリズムの並列化効率はアルゴリズムを改悪しない限りマイナスになることはありませんが、理想的な並列化率がプラスであっても通信時間を加味すると実効的にはマイナスになることもあるわけです。
また、理想的な並列化効率は x が大きければ 1/n に、x が小さければ 1 に近づいていくことが分かります。実際にはアルゴリズムを見て直接 x を計算することはできませんが、処理時間を比較すれば P を求めることが可能です。P が分かれば、逆算により実効的な並列化率 x を x = (P-1)/(1/n - 1) の式から求めることができます。アルゴリズムのみで並列化率をチェックするには、通信時間の部分を差っぴいておく必要があります。
アルゴリズムの並列化率を上げ、通信量を減らし、そして実際の並列化効率をチェックする。これが並列プログラミングの基本的な作業になるようです。
さて、LAM のインストールですが、rpm を使わず手動でインストールしました。いろいろ設定を変えてコンパイルすることを考えているので、このようにしました。ただ、今回は１つの設定のみで説明します。
インストールした LAM のバージョンは 6.5.8 です。OS は前述の通り Red Hat Linux 7.2 です。大まかな手順としては
と、これだけです。
configure のオプションには、インストールしたい場所の指定 --prefix=~/bin/MPI/gcc と、C++ 例外を有効にする --with-exceptions とを指定しました。LAM はこの指定されたディレクトリの中にインストールされます。あとは環境変数にコンパイラとそのオプションの指定を入れておきました。設定を使いまわしたり、いろいろ修正をかけやすくするため、一応 configure を実行するためのスクリプトを書きました。こんな感じです。
#!/bin/bash -f gcc='gcc' if [[ $1 == "-$gcc" ]] then export CC=gcc export CPP=cpp export CFLAGS='-O3 -funroll-loops' export CXX='g++' export CXXCPP=cpp export CXXFLAGS='-O3 -funroll-loops' export FC=g77 export FFLAGS='-O3 -funroll-loops' else echo 'conf : auto-configure' echo " -$gcc : configure for GCC" exit fi dirname=~/bin/MPI/$1 mkdir $dirname ./configure --prefix=$dirname --with-exceptions
インストールは、諸般の事情でホームの下にしました。ループのアンロール（展開）は場合によっては諸刃の剣になることがありますが、まぁその時はその時です。全部のループをアンロールする -funroll-all-loops フラグじゃないので、有効に働いてくれることを期待しておきます。これで ./conf -gcc とすれば configure 完了です（./conf に実行属性を与えるのを忘れずに）。
次に make です。これは特に何もいうことはありません。
% make % make install
そして、次に設定です。環境変数 LAMHOME を設定しておき、${LAMHOME}/bin にパスを通します。LAMHOME は上で LAM をインストールしたディレクトリになります。これは .cshrc や .bash_login などの環境に合わせたしかるべき場所に
(csh/tcsh)
setenv LAMHOME ~/bin/MPI/gcc
setenv PATH ${PATH}:${LAMHOME}/bin
(bsh/bash)
export LAMHOME=~/bin/MPI/gcc
export PATH=${PATH}:${LAMHOME}/bin
と書きます。実際には、既に LAM のインストールされている環境だったので ${LAMHOME}/bin の方を先に書きましたが。これもまぁ問題ないですね。
最後にデーモンの起動です。デーモンというのはいわゆる常駐プログラムのことで、LAM では lamd というデーモンを各マシン上に常駐させておく必要があります。
先ず、ホスト名を羅列したファイルを作っておきます。例えば lamhosts というファイルに
host0.robert.com host1.robert.com host2.robert.com host3.robert.com host4.robert.com host5.robert.com host6.robert.com host7.robert.com
という風に書いておきます（当然上のホスト名は仮の名前で、実際には多分存在しません）。
そして、recon というコマンドで先ずきちんとデーモンを起動できるかチェックします。
% recon -v lamhosts
これで、成功すると次のようなメッセージが表示されます。
----------------------------------------------------------------------------- Woo hoo! recon has completed successfully. This means that you will most likely be able to boot LAM successfully with the "lamboot" command (but this is not a guarantee). See the lamboot(1) manual page for more information on the lamboot command. If you have problems booting LAM (with lamboot) even though recon worked successfully, enable the "-d" option to lamboot to examine each step of lamboot and see what fails. Most situations where recon succeeds and lamboot fails have to do with the hboot(1) command (that lamboot invokes on each host in the hostfile). -----------------------------------------------------------------------------
成功すれば、次にデーモンを起動します。デーモンは lamd を直接起動するのではなく、lamboot というコマンドで起動します。
% lamboot -v lamhosts
これで成功すれば、topology done と表示されます（-v 「おしゃべり」オプションをつけていないと表示されません）。そして、一応 lamnodes コマンドでちゃんと lamd が走ってるかどうか確かめます。
% lamnodes n0 host0.robert.com:1 n1 host1.robert.com:1 n2 host2.robert.com:1 n3 host3.robert.com:1 n4 host4.robert.com:1 n5 host5.robert.com:1 n6 host6.robert.com:1 n7 host7.robert.com:1
これで LAM が使えるようになりました。もし失敗するとごちゃごちゃとエラーメッセージが表示されるので、そうなってない時点で先ず成功しているとは思います。
lamd はターミナルを終了させてもずっと実行され続けます。まぁ、当然そうなってないと困るわけですが。これを終わらせるには wipe というコマンドを使います。
% wipe -v lamhosts
何事もなければ、これで全部終了してくれるはずです。
もし LAM を使用中のプログラムを実行している場合は、wipe の前に lamclean を実行します。
% lamclean -v % wipe -v lamhosts
関数の説明などごちゃごちゃしたことは後回しにして、とりあえず使ってみることにしました。
やっぱり初めて使うときに作るプログラムというと、あれでしょう。Hello, World! です。ただ、そのままでは面白くないし、並列実行してる気分も出ないので、"Hello, host<ホスト名>!" とホスト毎に違った値を出力してみたいと思います。
| FORTRAN77 | |
|---|---|
| プログラム | 実行結果例 |
Program TestLAM
Implicit None
Include 'mpif.h'
Integer err
Integer rank
Call MPI_Init(err)
Call MPI_Comm_rank(MPI_COMM_WORLD, rank, err)
Write(*, *) 'Hello, host', rank, '!'
Call MPI_Finalize(err)
Stop
End |
Hello, host 0! Hello, host 1! |
| C | |
| プログラム | 実行結果例 |
#include <stdio.h>
#include <mpi.h>
int main(int argc, char** argv)
{
int rank;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank)
printf("Hello, host%d!\n", rank);
MPI_Finalize();
} |
Hello, host0! Hello, host1! |
| C++ | |
| プログラム | 実行結果例 |
#include <iostream>
#include <mpi++.h>
using namespace std;
int main(int argc, char** argv)
{
MPI::Init(argc, argv);
cout << "Hello, host"
<< MPI::COMM_WORLD.Get_rank()
<< '!' << endl;
MPI::Finalize();
} |
Hello, host0! Hello, host1! |
３つの言語を使ってみました。Fortran90 はコンパイラがないし、文法知らないので回避です。
先ずは上からということで、FORTRAN77 から見てみます。
先ず、mpif.h というヘッダファイルをインクルードします。C プリプロセッサの #include でも別にいいのですが、ここでは FORTRAN77 の Include 命令を使いました。
次に MPI を使うために必要なのは、MPI の初期化です。これは MPI_Init というサブルーチンで行います。引数にはエラーが起こったときにその値が返ってきます。どうやら FORTRAN77 用の MPI の関数は大抵引数の最後にエラーを返す引数が用意されているようです。ただ、今回はエラーを拾うだけ拾って、処理はしませんでした。
そして、真ん中のを飛ばして、最後にすることが MPI の後処理です。これは MPI_Finalize というサブルーチンで行います。引数には同じくエラー変数を入れておきます。
MPI の処理は、この初期化と後処理の間に書きます。これは別に変わったことでもありませんね。
で、その処理ですが、MPI_Comm_rank というサブルーチンを呼んでいます。この関数は、この関数を呼んだプロセスのコミュニケータ（どうやら MPI のハンドル（操作するためのもの）に相当するようです）内での番号を返すようです。MPI_COMM_WORLD というのがデフォルトで用意される、全てのプロセスを含んだコミュニケータのようです。まぁとにかく、上の様に書けばプロセスの通し番号が得られる、ということのようです。
また、MPI のほかの細かい点としては、
ということが挙げられると思います。
あと MPI とは関係ない細かいことを言えば、
ということです。研究者の人たちは「研究に余り関係ないので」と、プログラミングスタイルとか新しいプログラミング言語とかに無頓着な人が多いのですが（たまにマニアがいるかもしれませんが）、プログラムの作成・改造・デバッグに要する時間が減ればそれだけ研究は速く進むので実は非常に重要です。理論に求めるエレガントさをプログラムにも求めてみてはどうでしょうか。後のプログラムでも、いろいろプログラミングスタイルにも言及していくので、参考にしてみて下さい。
では、次は C です。
C でのヘッダファイルは mpi.h です。
先ず初めに MPI_Init を呼ぶところまでは同じなのですが、引数が違うことに気付くと思います。C では FORTRAN77 とは異なり、エラーを全て戻り値で返します。戻り値の型は int のようです。さらに MPI_Init にはコマンドライン変数を参照渡しします（参照渡しというのは、変数の値ではなくアドレスを渡すことです。値を渡すことは値渡しと呼びます）。
そのほかについては、FORTRAN77 の場合とさほど変わらないようです。一応コミュニケータの型が FORTRAN77 では INTEGER だったのが MPI_Comm に変わっているようですが、このプログラムにおいてはさほど重要なことではないでしょう。
また細かいことですが、デーモンの様に実行しっぱなしのプログラムでない限り、main 関数の戻り値は int で、正常終了時には 0 （stdlib.h 内で定義されるマクロ EXIT_SUCCESS の方が分かりやすい）を、エラー終了時には 1 （EXIT_FAILURE）を返しておくのが普通です。でないと、エラーが出たかどうかで分岐するようなシェルスクリプトを書きたいときに困るからです。また、多くのコンパイラでは int や return 0; を省略することができます。上では return 0; だけ省略しています。
ただ、MPI のプログラムを実行する場合には戻り値が捨てられてしまうようなので（mpirun というコマンドを使って実行するのですが、これは mpirun 自身が成功したかどうかしか返さないようです。多分、子プロセスからは複数の戻り値が返されるので返すことができないからだと思います）、void main でもいいのかもしれません。しかし、ここは int main にしておく癖をつけておくためにも int main にしておきました。別に使い捨てのプログラムならどうでもいいのかもしれませんが、せめて公開するプログラムくらいは int main にしておきましょう（カーネルとか「永遠に終わらない」プログラムは、そのことを銘記する意味から void main にするのが通例のようですが）。
最後は C++ です。C++ ではクラスや名前空間への対応がなされているようです。MPI-2 の資料を見ると「C++ への対応は、C や FORTRAN77 との違いがあまり大きくならない程度にしか行っていない」と書かれています。ちと残念ですが、使えるだけ良しとします。
先ず、全ての関数、クラスは MPI 名前空間の中に入っています。名前空間の使えないコンパイラでは、MPI というのがクラスで代用されているようです。従って、using 宣言はしない方が可搬性は高いかもしれません。尤も、上ではそんなものは無視していますが。MPI 名前空間を using 宣言していないのは、Init とかだと何の関数だか分かりにくいからです。書いても書かなくても同じ状況で書いたり書かなかったりするのは紛らわしいので、using 宣言しないことにしました。
他にも、C++ では C とちょっと変わっているところがあります。クラスや名前空間については当然ですが、他にも
というところが違うようです。このプログラムでは、１と２が MPI::Init に、３は全ての関数に影響しています。４についてはこのプログラム中には出てきていませんが、ヘッダファイルを読んだ限りはそうなっているようです。
従って、MPI::Init の引数には & をつける必要がなく、MPI::Init と MPI::Finalize の戻り値の型は void で、MPI::Comm::Get_rank（MPI_Comm_rank に相当）はランクを直接戻り値から返します。もしかしたら３は例外を使うようなオプションをつけて configure したからなのかもしれませんが、元のファイルを見た限りは多分関係はないと思います。
以上で上のプログラムに関する解説は終わりです。
最後に、上の実行結果例ですが、「例」と書いてあるのには訳があります。C++ 講座の方を見ている人の中には知っている人もいると思いますが、実行結果が必ずしもこのようになるとは限らない場合には「例」をつけています。キーボードなどからの入力がある場合はもちろんですが、乱数を使っている場合や機種依存がある場合などにも例と銘記していました。
では、ここではなぜ「例」とつけているかですが、先ず 2 つしか実行していないというのが挙げられます。しかし実はそれだけではなく、0 と 1 とが逆に表示されることがあるからでもあります。必ずしも先に起動した（と推測される）０番目のホストより後から起動した（と推測される）１番目のホストの方が、後に文字列を出力するという保証はないのです。
と、Hello, World! 程度にここまで解説をするかというくらいの解説を終了したところで、次はコンパイルの方法について話します。
MPI を使った FORTRAN77, C, C++ のプログラムをコンパイルするには、それぞれ mpif77, mpicc, mpic++（または mpiCC）というコマンドを使います。これは、インクルードパスやリンクするライブラリの指定などを勝手にやってくれるコマンドです。ここで使うコンパイラを指定するためにも、上の configure でコンパイラを指定していたのでした（もちろん LAM をコンパイルするためにも必要なわけですが）。
その他のオプションについては、元のコンパイラと同じように指定してやります。例えば...
% mpif77 -O3 -o testlamf fmain.F % mpicc -O3 -o testlamc cmain.c % mpic++ -O3 -o testlamcpp cppmain.cpp
こんな感じです。
で、コンパイルが終了すると次は実行です。
実行はいくつかのホストに投げるわけですが、それを円滑に進めるために mpirun というコマンドが用意されています。MPI-2 の本を見ると mpiexec という新しいコマンドを用意するようになる予定のようですが、LAM はまだ対応していないようです。
全ての mpirun で存在することが保証されていると思われるオプションは -np オプションで、これでノード数（何個実行するか）を指定します。上の実行例では 2 ノードで実行しました。ですから、
% mpirun -np 2 testlamc Hello, host0! Hello, host1!
という形で実行したわけです。5 ノードで実行する場合は、
% mpirun -np 5 testlamf Hello, host 0! Hello, host 1! Hello, host 2! Hello, host 4! Hello, host 3!
とすればいいわけですね（わざと 4 と 3 の順番を変えてみたりして上の注意を思い出させてみるテスト）。特に難しいことはないと思います。
これでとりあえず LAM を使って MPI のプログラムを作って、コンパイルして、実行することができました。まだ大したことはしていませんが、こう実際に動いてるのを見ると感慨深いものがありますね。
長くなったので、今回はこれで終わりにします。続きは第十五報をお楽しみに...。
Last update was done on 2002.11.16