MatsuLab. Lecture Note/sougouenshu2007

第1ラウンド解説 †

↑

日程 †

基本木曜日。月曜も研究室にいるので、質問があったら来てください。

11/1（木）15:00〜松岡先生からの研究室の予定

↑

第1回目 †

10/4

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

ヒント
一対一通信

集団通信

↑

第2回目 †

10/11

課題確認

クイズ

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

基本

MPIアプリケーションと、サーバ・クライアント型アプリケーションの違い

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

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 以下の指示に従い「行列とベクトル積を行なうプログラム」を実装し、実行すること。 シングルプロセッサ用プログラムを用意してあるので、それを参考にして良い。

シングルプロセッサ用プログラムのコンパイル＆実行方法

$ 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回目 †

10/18

行列・ベクトル積
前回の行列・ベクトル積のMPIプログラムがまだ出来ていない場合はそちらを完成される。

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

今回解いてもらうのはスパコンコンテスト2001で出題された問題である。 細かい問題の内容はこちらのページを参考。

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

ヒント

↑

第4回目 †

第3回の続き

行列・ベクトル積問題の補足

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

ためしに4プロセス（pad017 〜 pad020の4ノードを使用）で実行したところ、

sample110.406秒
sample261.827秒

となった。 計算処理を分割しただけでは不十分で、処理対象データの転送にも気を配らないと性能が出ないことが理解できると思う。

その2
sample1.cをプロセス数を1,2,4と変化させて実行したところ、次のよう実行時間が変化した。

12.914
24.994
410.406

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

↑

第5回目 †

N体問題の課題をつづける

Naiveな実装例
ページ末尾に「nbody1.c」と言う名前で、N体問題のプログラムをMPIを使って並列化したサンプル実装をアップロードした。 アルゴリズムは前回の講義で説明したもので、C言語だけの実装との違いは、

  1. do_step関数内での星の位置計算を全プロセスに均等分割
  2. main関数内ループでMPI_Allgatherを実行

だけであり、高々数行変更しただけである。 プロセス数を1,2,4,8と変化させた場合の問題1にかかった時間は以下のようになった。

プロセス数時間（秒）
1209.641
2105.682
453.038
826.851

プロセスを倍に増やすと、実行時間も半分になることが確認できる。

末尾添付のnbody1.cと同じものを松岡研マシン上に「/home/takizawa/sougouenshu/nbody1.c」として置いてある。 必要なら、以下のコマンドで各自のホームディレクトリにコピーして良い。

$ cp ~takizawa/sougouenshu/nbody1.c .       <- 「.」を忘れない

さらなる改良
nbody1.cの場合、さらに以下のような改良が出来る。

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

最終課題 †

期限
11/9
提出物
↑

課題の進め方 †

その1

その2

↑

松岡研PCクラスタPrestoIIIの使い方 †

作業には基本的にターミナルを使用する

↑

PrestoIII上のデータのバックアップ方法 †

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

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

参考文献 †

  1. MPIドキュメント集
    • 初回配布資料は、この文献の前半部分（140ページまで）
  2. TSUBAMEの構成
  3. MPIによる並列プログラミングの基礎(PDF)
    • 同志社大の先生が書かれた、非常に詳しい日本語資料
  4. スパコンコンテスト2001
    • 優勝チームのプログラムも掲載されているので、必要なら参考にして良い
  5. N体問題オンラインデモ
  6. N体問題重力ゲーム
  7. 粒子登録法
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS