- 追加された行はこの色です。
- 削除された行はこの色です。
//!!edit-lock!!
[[MatsuLab. Lecture Note/sougouenshu2007]]
*第1ラウンド解説 [#daa36b6d]
#contents
**日程 [#oa31bb6b]
基本木曜日。月曜も研究室にいるので、質問があったら来てください。
11/1（木）15:00〜松岡先生からの研究室の予定
**第1回目 [#rac5508b]
10/4
''課題''~
渡したMPI仕様書を読んで、どういった通信関数があるか調べて簡単にまとめてくること。
主に一対一通信、集団通信の2グループに分かれるが、それぞれに多くの通信関数が提供されているので、関数の特徴をまとめてくること
''ヒント''~
一対一通信
-同期通信（ブロッキング通信）
-非同期通信（ノンブロッキング通信）
集団通信
-全対全
-一対多、多対一通信
-Reduction操作
**第2回目 [#ta9f8be7]
10/11
''課題確認''
クイズ
-同期通信、非同期通信はなぜ分類されているのか
-非同期通信だと何がうれしいか
-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 <- 実行
''課題''~
''その1''
mpi_pi.cにおいて、定数N_POINTSや実行するプロセス数をさまざまに変化させて、実行時間を確認すること。
''その2''
以下の指示に従い「COLOR(BLUE){行列とベクトル積を行なうプログラム}」を実装し、実行すること。
シングルプロセッサ用プログラムを用意してあるので、それを参考にして良い。
-行列、ベクトルデータの生成は1つのプロセス上で行い、そのプロセスからMPI通信関数を呼び出して他のプロセスに送ること
-計算終了後には1つのプロセスにデータを集約すること
-行数、列数、使用プロセス数をさまざまに変化させて実行すること
-一対一通信のMPI_Send、MPI_Recvだけで実装できるが、集団通信のMPI_Bcast、MPI_Scatter、MPI_Gatherなどを使って実装すると良い
--なお、任意の数のプロセスに対応するには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回目 [#j771c41c]
10/18
''行列・ベクトル積''~
前回の行列・ベクトル積のMPIプログラムがまだ出来ていない場合はそちらを完成される。
''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 /home/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
このページ末尾にもアップロードしたので、MACでダウンロードしてコンパイル・実行してみるとよい。
:注1|
上のコマンドでコンパイルされて生成された全てのオブジェクトファイルと、算術計算用ライブラリ（libm.so）をリンクして、実行ファイル「main」を作る、と言う意味
:注2|
mainの引数に与えられている数値は問題番号を表す。種類は0、1、2の3種類あり、数字が大きくなるにつれデータ量も増える。また、問題2には検証用データは用意されていない
MPIで実装するにはmain関数だけを編集すればよい。以下のような手順でコンパイルすることになる。
$ gcc -c correct_data_0.c correct_data_1.c problem.c random_generator.c <- 最初の1回だけでよい
$ mpicc -c main.c
$ mpicc -o mpi_main *.o -lm
$ mpirun -np 32 -machinefile machines ./mpi_main
''ヒント''
-main.cにはいくつか関数が定義されているが、round、calc_gravityは特に変更する必要は無い。mainやdo_stepを工夫すること。
-main.c内で分からない関数があったら、ターミナルに次のようにコマンドを入力すると確認できる。ただし英語。
$ man 3 floor
$ man 3 fflush
**第4回目 [#u8b9c3f7]
第3回の続き
''行列・ベクトル積問題の補足''
''その1''~
/home/takizawa/sougouenshu 以下に「sample1.c」、「sample2.c」と言う名前でプログラム実装例を置いた。
sample1.cは行列データ送信時にMPI_Scatterを用いる実装で、sample2.cはそのまま全データをMPI_Bcastで送信するアホな実装。
どちらの実装も、行列・ベクトル積を行なう回数は同じ。
10000x10000行列で、800MBのサイズの問題である。
ためしに4プロセス（pad017 〜 pad020の4ノードを使用）で実行したところ、
|sample1|10.406秒|
|sample2|61.827秒|
となった。
計算処理を分割しただけでは不十分で、処理対象データの転送にも気を配らないと性能が出ないことが理解できると思う。
''その2''~
sample1.cをプロセス数を1,2,4と変化させて実行したところ、次のよう実行時間が変化した。
|1|2.914|
|2|4.994|
|4|10.406|
計算処理を分割しているから、プロセス数を増やせば各プロセスが担当する計算が減るため実行時間も短くなるはず・・・だが、むしろ増えている。
この理由は、計算コストに対して通信コストが高すぎるため。
実際にMPIでプログラムを書くときには、大きな通信コストを払ってでも分割する価値のある問題かどうか考えてから書くべきである。
**第5回目 [#beaa0266]
N体問題の課題をつづける
''Naiveな実装例''~
ページ末尾に「nbody1.c」と言う名前で、N体問題のプログラムをMPIを使って並列化したサンプル実装をアップロードした。
アルゴリズムは前回の講義で説明したもので、C言語だけの実装との違いは、
+do_step関数内での星の位置計算を全プロセスに均等分割
+main関数内ループでMPI_Allgatherを実行
だけであり、高々数行変更しただけである。
プロセス数を1,2,4,8と変化させた場合の問題1にかかった時間は以下のようになった。
|プロセス数|時間（秒）|
|1|209.641|
|2|105.682|
|4|53.038|
|8|26.851|
プロセスを倍に増やすと、実行時間も半分になることが確認できる。
末尾添付のnbody1.cと同じものを松岡研マシン上に「/home/takizawa/sougouenshu/nbody1.c」として置いてある。
必要なら、以下のコマンドで各自のホームディレクトリにコピーして良い。
$ cp ~takizawa/sougouenshu/nbody1.c . <- 「.」を忘れない
''さらなる改良''~
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を実行するほうがラク
**最終課題 [#vee07cb0]
:期限|11/9
:提出物|
-MPIで並列化を行なったN体問題のソースコード
-松岡研PCクラスタ上で、プロセス数を変化させて実行させたときの実行時間をまとめたレポート（テキストファイルでよい）
--最大で36プロセスまで使用可能
--問題1で試すこと。余裕があれば、問題0、2も試すこと
--ある数以上プロセス数を増やすと、実行時間が増加する現象が現れるはず。この理由も考えること
--二人が同時に実行すると良い結果が得られないので、話し合ってスケジュールを決めて実行すること。
-感想
**課題の進め方 [#s7ceb180]
その1
-演習室MACでプログラムを編集
-scpコマンドでプログラムをPrestoIIIクラスタに転送（リモートコピー）
-sshコマンドでPrestoIIIにログイン
-PrestoIII上でプログラムをコンパイル＆実行
その2
-sshコマンドでPrestoIIIにログイン
-PrestoIII上でviやemacs( -nw)などでプログラムを編集、コンパイル＆実行
**松岡研PCクラスタPrestoIIIの使い方 [#t8bbbfb5]
作業には基本的にターミナルを使用する
-ログイン
++ログインノードnimbus.titech.hpcc.jpへログイン
$ ssh USERNAME@nimbus.titech.hpcc.jp
++実行マシンへログイン
$ rsh pad017
-ファイルの転送（リモートコピー）
--以下のコマンドを用いて、カレントディレクトリにあるファイルmpi.cをnimbus.titech.hpcc.jpに転送
$ scp mpi.c USERNAME@nimbus.titech.hpcc.jp:
--最後の「:」を忘れない
-使用するマシン
--16台（最大32CPU）
--どのマシンを使用するかは、/home/USERNAME/sougouenshu/machinesファイルを参考に
**PrestoIII上のデータのバックアップ方法 [#n328387d]
PrestoIIIへのアクセス権は今期いっぱいしか与えられないので、第1ラウンドが終わった後、忘れないうちに以下の手続きに従い各自のデータをバックアップすること。
+ nimbus.titech.hpcc.jpにログイン
$ ssh USER@nimbus.titech.hpcc.jp
+ 総合演習用データのアーカイブ（1つのファイルにまとめること）
$ tar zcf sougouenshu.tar.gz sougouenshu
--このコマンドを実行することにより sougouenshu ディレクトリ以下の全部のファイルを sougouenshu.tar.gz と言う名前の1つのファイルにまとめる
+ lsコマンドを実行し、sougouenshu.tar.gzが存在することを確認
+ nimbus.titech.hpcc.jpからログアウト
+ MACマシン上でscpを実行し、nimbusからアーカイブファイルをダウンロード
$ scp USER@nimbus.titech.hpcc.jp:sougouenshu.tar.gz .
--MACマシンからのプログラムファイル転送とは実行方法が違うので注意
--最後の「.」を忘れない
+ ダウンロードできたかどうか、lsで確認
+ アーカイブファイルを展開
$ tar zxf sougouenshu.tar.gz
--カレントディレクトリにsougouenshuと言う名のディレクトリが出来るはず
**参考文献 [#o65101c7]
+[[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
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
