MatsuLab. Lecture Note/sougouenshu2008/round1 の変更点

追加された行はこの色です。
削除された行はこの色です。
MatsuLab. Lecture Note/sougouenshu2008/round1 へ行く。
MatsuLab. Lecture Note/sougouenshu2008/round1 の差分を削除
//!!edit-lock!!
[[MatsuLab. Lecture Note/sougouenshu2008]]

*第1ラウンド解説 [#z54cb085]
#contents

**日程 [#a616bf73]
基本木曜日。月曜も15:00以降なら研究室にいるので、質問があったら来てください。


**第1回 [#rf63b86d]
10/9

''課題''~
渡したMPI仕様書を読んで、どういった通信関数があるか調べて簡単にまとめてくること。
主に一対一通信、集団通信の2グループに分かれるが、それぞれに多くの通信関数が提供されているので、関数の特徴をまとめてくること

''ヒント''~
一対一通信
-同期通信（ブロッキング通信）
-非同期通信（ノンブロッキング通信）

集団通信
-同期
--MPI_Barrier
-全対全
--MPI_Alltoall、MPI_Allgather
-一対多、多対一通信
--MPI_Bcast、MPI_Gather、MPI_Scatter
-Reduction操作
--MPI_Reduce、MPI_Allreduce、MPI_Reduce_scatter

XXv、XXwは無視してよい
-MPI_Alltoallvなど


**第2回 [#l9064a48]
10/23

''前回の課題の確認''~
-ブロッキング通信と、ノンブロッキング通信の両方がある理由
--ブロッキング通信だと通信中にCPUがアイドル（使用されない状態）になる。特にサイズの大きい配列データなどを送受信する場合には、そのアイドル時間も大きくなり、その分のCPU時間が無駄になる。ノンブロッキング通信では、CPUでの計算と通信をオーバーラップさせることでCPUを有効活用する。
--現状のMPIでは集団通信はすべてブロッキングだが、研究レベルではノンブロッキングのものもある。
-なんのために集団通信は用意されているか
--MPIが提供する集団通信と同じパターンの通信は、MPIを使ったプログラムを書く人が一対一通信を組み合わせることで実現可能である。
--集団通信を高速に実行するには賢いアルゴリズムを使う必要があり、一般のプログラマーには実行が困難である。実際、集団通信の実装によって、通信時間がプロセス数に対してO(n)だったり、O(logn)となったり、通信されるデータ量もO(n)からO(logn)へと減らすことが可能である。MPIが提供する集団通信はデータサイズやプロセス数に応じて適したアルゴリズムを使用するように調整されている。

''MPIを使った並列プログラミング''

基本
-分散メモリモデルのプログラミングモデル
--プロセス（マシン）間でデータは共有されないので、明示的なデータの送受信が必要
-- <-> 共有メモリモデル
-処理対象のデータ、問題を細かく分割し、多くのコンピュータに配分・実行させる
--通信量を出来るだけ少なくするように工夫
--計算量と通信のバランスも考える必要がある
--マシン性能に応じて配分する問題サイズを変えること（負荷分散）も重要だけど、今回使用するマシンの性能はほぼ等しいので省略

MPIアプリケーションと、サーバ・クライアント型アプリケーションの違い
-サーバ・クライアント型
--一般にサーバとクライアントアプリケーションは異なるプログラム（MPMD: Multiple Program Multiple Data）
--WebサーバとWebブラウザ、ファイルサーバとクライアント（専攻の演習マシン）
-MPI並列アプリケーション
--全てのプロセス（マシン）が同じプログラムを実行、ただし、処理対象データは異なる（SPMD: Single Program Multiple Data）
--もちろん、MPIライブラリを用いてサーバ・クライアント型アプリケーションも書ける

MPIプログラムのサンプル: mpi_pi.c~
このファイルはモンテカルロ法を用いてPIを計算する、本当に初歩的なMPIプログラム。
MPI関数もMPI_BcastとMPI_Reduceしか用いていず、1関数での通信量も高々4バイト。

-MPIアプリケーションはMPI_Init関数で始まり、MPI_Finalize関数で終わる
-MPI_Comm_sizeで、アプリケーション実行に参加しているプロセス数を得る
-MPI_Comm_rankでMPIアプリケーション内での自分（プロセス、マシン）の名前を得る
--名前の範囲は0～N_PROCS-1
---具体的に4つのプロセスでアプリケーションを実行する場合には、0,1,2,3といった名前が割り当てられる
--一対一通信ではこの名前で通信先プロセスを指定する
-MPI_Bcastで分割した問題を各プロセスに送信
--プロットする点の数をばらまく
--実はこのサンプルではMPI_Bcastする必要は無い
-MPI_Reduceで各プロセスの計算結果を1つのプロセスに集約

mpi_pi.cのコンパイル＆実行方法
 $ mpicc -c mpi_pi.c
 $ mpicc -o mpi_pi mpi_pi.o -lm
 $
 $ mpirun -np 2 -machinefile machines ./mpi_pi  <- 実行

''課題''~
PrestoIII上のtakizawaのホームディレクトリから今回の演習用プログラムをコピーする。
 $ cp -r ~takizawa/sougouenshu/n01 .
 $ cp ~takizawa/sougouenshu/machines n01

''その1''
mpi_pi.cにおいて、定数N_POINTSや実行するプロセス数をさまざまに変化させて、実行時間を確認すること。特に、N_POINTSを比較的大きい値に固定したときに、プロセス数を変化させた場合の実行時間を比較すること。

''その2''~
以下の指示に従い「COLOR(BLUE){行列とベクトル積を行なうプログラム}」を実装し、実行すること。
シングルプロセッサ用プログラムを用意してあるので、それを参考にして良い。

-行列、ベクトルデータの生成は1つのプロセス上で行い、そのプロセスからMPI通信関数を呼び出して他のプロセスに送ること
-計算終了後には1つのプロセスにデータを集約すること
-一対一通信のMPI_Send、MPI_Recvだけで実装できるが、集団通信のMPI_Bcast、MPI_Scatter、MPI_Gatherなどを使って実装すると良い
-特定のパターンのプロセス数で実行できればよい。たとえば、1,2,4,8,16と2べきの数のプロセスでしか実行できなくてもかまわない。
--任意の数のプロセスに対応するにはMPI_Scatter、MPI_Gatherの変わりに、MPI_Scatterv、MPI_Gathervを使うことになる
-行数、列数、使用プロセス数をさまざまに変化させて実行すること

シングルプロセッサ用プログラムのコンパイル＆実行方法
 $ gcc -c vector.c    <- vector.oが既に生成されていれば実行しなくても良い
 $ gcc -c mul_matrix.c
 $ gcc -o mul_matrix mul_matrix.o vector.o
 $ ./mul_matrix    <- 実行
MPIプログラム（例 mpi_mm.c）のコンパイル方法
 $ gcc -c vector.c    <- vector.oが既に生成されていれば実行しなくても良い
 $ mpicc -c mpi_mm.c
 $ mpicc -o mpi_mm mpi_mm.o vector.o
 $ mpirun -np 4 -machinefile machines ./mpi_mm   <- 実行


**第3回 [#v9bd9dd7]
''行列・ベクトル積問題の補足''

''その1''
/home/takizawa/sougouenshu 以下に「sample1.c」、「sample2.c」と言う名前でプログラム実装例を置いた。
sample1.cは行列データ送信時にMPI_Scatterを用いる実装で、sample2.cはそのまま全データをMPI_Bcastで送信するアホな実装。
どちらの実装も、行列・ベクトル積を行なう回数は同じ。
10000x10000行列で、800MBのサイズの問題である。

ためしに4プロセスで実行したところ、
|sample1|10.406秒|
|sample2|61.827秒|
となった。
計算処理を分割しただけでは不十分で、処理対象データの転送にも気を配らないと性能が出ないことが理解できると思う。

''その2''
sample1.cをプロセス数を1,2,4と変化させて実行したところ、次のよう実行時間が変化した。
|1|2.914|
|2|4.994|
|4|10.406|
計算処理を分割しているから、プロセス数を増やせば各プロセスが担当する計算が減るため実行時間も短くなるはず・・・だが、むしろ増えている。
この理由は、計算コストに対して通信コストが高すぎるため。
実際にMPIでプログラムを書くときには、大きな通信コストを払ってでも分割する価値のある問題かどうか考えてから書くべきである。

また、問題によってはプロセス数を変化させた場合、ある程度まで増やせば実行時間が短縮されるが、それ以上増やすと逆に実行時間が増加するものもある。
ある程度までであれば、計算コストが通信コストを上回り、問題を分割することでプロセスあたりの処理量を減らし性能向上するが、それ以上にプロセスを増やすと通信コストが計算コストを上回ることになり、sample1.c同様に通信に多くの時間が取られ、性能低下する。
このトレードオフを見極め、問題に対して適切なプロセス数を捜し出すことが重要となる。

''N体問題''~
N体問題の基礎問題をMPIを用いてC言語で実装する。
N体問題では、N個の質点間における相互作用の力を解くことによって、例えば宇宙空間に散らばる惑星間の引力、物質を構成する分子間の引力のシミュレーション等を行なう。
末尾の参考文献に、N体問題を理解するためのオンラインデモと重力ゲームへのリンクを載せたのでそちらも参考に。

今回解いてもらうのはスパコンコンテスト2001で出題された問題である。
細かい問題の内容は[[こちらのページ>http://www.gsic.titech.ac.jp/supercon/supercon2001/honsen.html]]を参考。

MPIを用いていない、C言語だけで書かれたシングルプロセス用のプログラムとデータファイルを以下の場所に置いたので、自分の作業ディレクトリにコピーすること。このページにも添付してある。
:場所|/home/takizawa/sougouenshu/n-body.tar.gz
 $ cd sougouenshu
 $ cp ~takizawa/sougouenshu/n-body.tar.gz .    <- 「.」を忘れない
 $ tar zxf n-body.tar.gz                            <- 圧縮ファイルの展開
 $ cd n-body
 $ ls
 correct_data_0.c  correct_data_1.c  main.c problem.c  random_generator.c

このプログラムは以下のようにコンパイル、実行できる。
 $ gcc -c *.c             <- 拡張子が「.c」のファイルを全てコンパイル
 $ gcc -o main *.o -lm    <- 注1
 $ ./main 0               <- 実行  注2

:注1|
上のコマンドでコンパイルされて生成された全てのオブジェクトファイルと、算術計算用ライブラリ（libm.so）をリンクして、実行ファイル「main」を作る、と言う意味
:注2|
mainの引数に与えられている数値は問題番号を表す。種類は0、1、2の3種類あり、数字が大きくなるにつれデータ量も増える。また、問題2には検証用データは用意されていない

MPIで実装するにはmain.cだけを編集すればよい。以下のような手順でコンパイルすることになる。
 $ gcc -c correct_data_0.c correct_data_1.c problem.c random_generator.c   <- 注3
 $ mpicc -c main.c
 $ mpicc -o mpi_main *.o -lm
 $ mpirun -np 32 -machinefile machines ./mpi_main

:注3|
既にcorrect_data_0.o correct_data_1.o problem.o random_generator.oが存在する場合は実行しなくてよい。

''ヒント''
-main.cにはいくつか関数が定義されているが、round、calc_gravityは特に変更する必要は無い。mainやdo_stepを工夫すること。
-main.c内で分からない関数があったら、ターミナルに次のようにコマンドを入力すると確認できる。ただし英語。
 $ man 3 floor
 $ man 3 fflush


**第4回 [#t2ac8275]

''N体問題のNaiveな実装''~
PrestoIII上に「/home/takizawa/sougouenshu/nbody1.c」と言う名前で、N体問題のプログラムをMPIを使って単純に並列化したサンプル実装をアップロードした。
C言語だけの実装との違いは、

+do_step関数を引数を1つ取るように変更。引数に与えた数分の星をdo_step関数は処理する。
+forループ
--各プロセスが均等に星を処理する
--Allgatherで結果を集約

だけであり、高々数行変更しただけである。
プロセス数を1,2,4,8と変化させた場合の問題1にかかった時間は以下のようになった。
|プロセス数|時間（秒）|
|1|209.641|
|2|105.682|
|4|53.038|
|8|26.851|
プロセスを倍に増やすと、実行時間も半分になることが確認できる。

takizawaのホームディレクトリからのコピー方法。
 $ cp ~takizawa/sougouenshu/nbody1.c .       <- 「.」を忘れない

''さらなる改良''~
さらに以下のような改良が出来る。
+MPI_Allgatherでの通信量を減らす
--nbody1.cではperticle構造体そのままを転送している。しかし、m, ax, ayは転送する必要がなく、1つの星データにつき24バイト無駄に転送している（約半分が無駄）。必要なデータのみを転送するように修正すると、通信が最適化される
+do_stepの内側のループ回数を減らす
--内側のループではいまだにn_particles回処理を繰り返している。距離が1024（32x32）以上の点からは影響を受けないので、距離が32+α以下の点のみをピックアップし、処理するように修正
---一般に「COLOR(RED){粒子登録法}」と言われる
--αの値のとり方によって実行時間が変化するので、最適なαを見つけること
--参考文献を参考に
--ためしに滝澤が実装して実行してみたところ、以下に示す結果となった
---nbody2が粒子登録法を用いた実装。ただし、1の通信量を減らす処理は行っていない。このソースコードは後日公開します
|プロセス数|nbody1|nbody2(α=2)|
|2|105.682|12.171|
|4|53.038|7.033|
|8|26.851|4.285|
+任意の数のプロセスで実行できるようにする
--通信関数にはMPI_Allgathervを使うと良い（ちょっと難しいけど）
--プロセス数回MPI_Bcastを実行するほうがラク

''課題''~
N体問題をMPI並列実装し、問題1、2の実行時間をプロセス数を以下のようにできるところまで変化させた時の実行時間をまとめること。
|''問題''|''粒子数''|''プロセス数''|
|1|5000|2, 4, 8, 10, 20, 40, 50|
|2|20000|2, 4, 8, 16, 32, 40, 50|
レポートにはどのように実装したかを簡単に記述し、実験結果は表形式で見やすくまとめてください。
締め切りは11/21とします。
また、粒子登録法を用いて実装したサンプルプログラムをCOLOR(RED){11/13}頃に配布します。
締め切りはCOLOR(RED){11/21}とします。
また、粒子登録法を用いて実装したサンプルプログラムを11/13頃に配布します。
こちらを参考にしてもかまいません。

2人以上が同時にプログラムを実行すると性能が出ないので、調整するように。pad041にログインした後に「who」コマンドで自分以外のユーザがいないことを確認した後で実行するとよいです。


**課題の進め方 [#v74ce563]
+演習室MACでプログラムを編集
+scpコマンドでプログラムをPrestoIIIクラスタに転送（リモートコピー）
+sshコマンドでPrestoIIIにログイン
+PrestoIII上でプログラムをコンパイル＆実行


**松岡研PCクラスタPrestoIIIの使い方 [#j81f0642]
作業には基本的にターミナルを使用する
-ログイン
++ログインノードnimbus.m.gsic.titech.ac.jp (131.112.28.30)へログイン
 $ ssh USERNAME@nimbus.m.gsic.titech.ac.jp
++実行マシンへログイン
 $ rsh pad041
-ファイルの転送（リモートコピー）
--以下のコマンドを用いて、*演習室のmac上の* カレントディレクトリにあるファイルmpi.cをnimbus.m.gsic.titech.ac.jpに転送
 $ scp mpi.c USERNAME@nimbus.m.gsic.titech.c.jp:
--最後の「:」を忘れない
--また、ファイルをnimbus上の~/sougouenshu/n01以下に直接コピーしたい場合には、次のようにも実行できる。
 $ scp mpi.c USERNAME@nimbus.m.gsic.titech.c.jp:sougouenshu/n01
-使用するマシン
--20台（最大80CPU）
--どのマシンを使用するかは、/home/USERNAME/sougouenshu/machinesファイルを参考に
--マシンは故障することがあるので、プログラムを実行できないなど、問題があったら連絡するように


**PrestoIII上のデータのバックアップ方法 [#e4687d48]
PrestoIIIへのアクセス権は今期いっぱいしか与えられないので、第1ラウンドが終わった後、忘れないうちに以下の手続きに従い各自のデータをバックアップすること。

+ nimbus.m.gsic.titech.ac.jpにログイン
 $ ssh USER@nimbus.m.gsic.titech.ac.jp
+ 総合演習用データのアーカイブ（1つのファイルにまとめること）
 $ tar zcf sougouenshu.tar.gz sougouenshu
--このコマンドを実行することにより sougouenshu ディレクトリ以下の全部のファイルを sougouenshu.tar.gz と言う名前の1つのファイルにまとめる
+ lsコマンドを実行し、sougouenshu.tar.gzが存在することを確認
+ nimbus.m.gsic.titech.ac.jpからログアウト
+ MACマシン上でscpを実行し、nimbusからアーカイブファイルをダウンロード
 $ scp USER@nimbus.m.gsic.titech.ac.jp:sougouenshu.tar.gz .
--MACマシンからのプログラムファイル転送とは実行方法が違うので注意
--最後の「.」を忘れない
+ ダウンロードできたかどうか、lsで確認
+ アーカイブファイルを展開
 $ tar zxf sougouenshu.tar.gz
--カレントディレクトリにsougouenshuと言う名のディレクトリが出来るはず


**参考文献 [#n46c9329]
+[[MPIドキュメント集:http://www.mpi-forum.org/docs/docs.html]]
--初回配布資料は、この文献の前半部分（140ページまで）
+[[TSUBAMEの構成:http://www.gsic.titech.ac.jp/~ccwww/tgc/]]
+[[MPIによる並列プログラミングの基礎(PDF):http://mikilab.doshisha.ac.jp/dia/smpp/cluster2000/PDF/chapter02.pdf]]
--同志社大の先生が書かれた、非常に詳しい日本語資料
+[[スパコンコンテスト2001:http://www.gsic.titech.ac.jp/supercon/supercon2001/]]
--優勝チームのプログラムも掲載されているので、必要なら参考にして良い
+[[N体問題オンラインデモ:http://www.cs.cmu.edu/~scandal/applets/bh.html]]
+[[N体問題重力ゲーム:http://homokaasu.org/gasgames/game.gas?21]]
+粒子登録法
--http://madeira.cc.hokudai.ac.jp/RD/emaru/Research/DPG/sld001.html
--http://venus.netlaboratory.com/material/messe/winmasphyc2/support/TIPS_tm/NeighborList.html