並列アルゴリズム
２００５年後期 火曜 ２限
青柳 睦
Aoyagi@cc.kyushu-u.ac.jp
http://server-500.cc.kyushu-u.ac.jp/
10月18（火）４．数値計算における各種の並列化
5. MPI の基礎
1

講義の概要
並列計算機や計算機クラスターなどの分散環境における並列処理の概論
・ＭＰＩおよびＯｐｅｎＭＰによる並列計算
・理工学分野の並列計算アルゴリズム
2

成績評価
出席点５割，レポート５割
aoyagi@cc.kyushu-u.ac.jpへメール
Subject: 並列アルゴリズム
学籍番号，氏名，専攻，座席番号(A-1,A-2,・・C-3など)
3

3.並列処理の課題(続き)計算負荷のアンバランス


同期待ち時間の増大

通信のオーバーヘッド
 プロセッサ間通信の「頻度」と計算粒度
並列アルゴリズムによるオーバーヘッド
並列化の為にデータをコピーする
 並列化の為の制御文を挿入
5

ＭＰＩプログラムの例/* greetings.c -- greetings program */#include <stdio.h>#include <string.h>#include "mpi.h"main(int argc, char* argv[]) {int
my_rank;/* rank of process
*/
int
p;
/* number of processes */intsource;/* rank of sender
*/
int
dest;
/* rank of receiver */int
tag = 0;/* tag for messages */charmessage[100]; /* storage for message */MPI_Status status;/* return status for receive *//* Start up MPI */MPI_Init(&argc, &argv);/* Find out process rank */MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

if (my_rank != 0) {/* Create message */sprintf(message, "Greetings from process %d!",my_rank);
dest = 0;/* Use strlen+1 so that '¥0' gets transmitted */MPI_Send(message, strlen(message)+1, MPI_CHAR,
dest, tag, MPI_COMM_WORLD);} else { /* my_rank == 0 */for (source = 1; source < p; source++) {MPI_Recv(message, 100, MPI_CHAR, source, tag,
MPI_COMM_WORLD, &status);printf("%s¥n", message);}}/* Shut down MPI */MPI_Finalize();} /* main *//* Find out number of processes */MPI_Comm_size(MPI_COMM_WORLD, &p);

6

４．数値計算における各種の並列化
数値計算コアとなるSolverによる分類
数値積分，連立一次方程式，固有値問題，・・
概して計算粒度が小さなアルゴリズムが多い
シミュレーション手法による分類
差分法，有限要素法，粒子多体問題，・・
自然を模倣したアルゴリズム等・・
シミュレーテッドアニーリング，遺伝的アルゴリズム，ニューラルネットワーク ，・・
計算粒度の大きなアルゴリズムが多い

7

4.1 並列性による分類
自明な並列
最初にデータと仕事をばらまいて，最後に結果を回収・整理統合するタイプ． もっとも粒度が大きな並列化が実現しやすい． モンテカルロ法，パラメータサーベイ，探索問題，等． ただし，データのばらまき・回収に通信量が多すぎたり，データが１プロセッサのメモリに入りきらない場合には，別の並列性を考慮する必要がある．

タスク並列
内容の異なる複数のタスク（処理のまとまり）からなり，それらを一定の順序制約のもとに処理するタイプ． 探索問題，分割統治法，疎行列計算など． 中粒度から大粒度．

データ並列
沢山の（別の）データのそれぞれに対して（同一の）処理を行うタイプ． 密行列・ベクトルな
ど線形演算，物理シミュレーション，画像処理など． 「個々のデータに対する処理に， （近傍か遠方か又は部分データか全体データか）どこのデータが必要となるか」が効率の良い並列アルゴリズム生成のカギとなる． 中粒度～小粒度．

パイプライン型
データの列があり，データ要素に対して複数の処理を逐次的に施すタイプ．いわゆる流れ作業． 多倍長演算や動的計画法など．
84.2 分散メモリにおける並列プログラミング
SPMD(Single Program Multiple Data )並列プログラミングの一つのスタイルで，複数の計算機上に個々別々のデータが乗っているが、それを処理するプログラムはすべて同一のものを使う． しかし、プログラムが同一だからといって処理内容が同一であるとは限らない． 条件分岐を用いて、プロセッサ毎に全く異なる処理を行うプログラムを SPMD の枠内で記述することもできる（・・というか，通常そうする）．

Owner Computes Rule
分散メモリにおける並列プログラミングの３つのＫＥＹポイントは，データの分散，処理（タスク）の分散，そして通信方法と通信量（頻度も重要）である．３つを同時に考えながらプロ
グラミングを行うことは難しい．まずはデータの分散を考え，処理（タスク）の分散をデータの分散に従わせることをOwner Computes Ruleと呼ぶ．通信は最適になるとは限らないが．

同期通信
同期通信では，データを持っているプロセスは 送信 (send) というルーチンを呼び，それを受け取るプロセスは受信 (recv) というルーチンを呼ぶ．このタイプの通信では，データのやり取りと同期を兼ねており，受信ルーチンを呼び出すまでは相手のメッセージは自分の領域に入ってこないことが保証される点でプログラムの構造は比較的簡単な場合が多い
が，通信は各時刻で必ず一方通行 (half duplex) となる．
9非同期通信
非同期通信では、受け手が受信ルーチンを呼び出していなくても送り手はデータを送信することができるので，送ってしまったら次の処理を開始し，演算と通信が同時に行われる様にアルゴリズムを工夫できる場合には「通信遅延の隠蔽」ができる．
非同期通信では（うまくゆけば）双方向(full duplex)の通信が可能である．また動的負荷分散を考慮したMaster-Workerモデルなど，柔軟なプログラミングが可能だが，多用するとプ
ログラムの構造が複雑になる．一般に，非同期通信は同期通信よりも多くのバッファメモリを必要とする．
（例）自作の電子構造計算プログラムにおける２電子積分ルーチンの負荷分散
Master-Workerタイプのアルゴリズムを用いており，各計算ノード（横軸）でIteration （奥行に表示）毎，「積分計算の処理量」（縦軸）が異なる．
10

4.3 並列プログラミング環境
MPI (Message Passing Interface)
分散メモリプログラミングのためのライブラリルーチンのインタフェースを定義．
MPI Forumh(ttp://www.mpi-forum.org/)により策定（MPI-2.0, MPI-1.2, ・・)
実装としては，MPICH(http://www-unix.mcs.anl.gov/mpi/mpich/), LAMなどオープンソース＆フリーなものから，ベンダー提供のライブラリなど各種ある．
事実上の世界標準． 共有メモリマシンでも利用できる．
OpenMP
共有メモリプログラミングのための指示文のセット
逐次プログラムをベースとし，Pragma指示行という形で並列処理の仕方を定義．
アルゴリズムが特定のパターンにマッチすれば簡単に並列化ができる．
HPF (High Performance Fortran)
逐次版 fortranプログラム に指示行を加えて，データと処理の分散を指示．
必要な通信はコンパイラにより自動的に生成される． 分散メモリ計算機上で，共有メモリ的なプログラミングを行うことを意図． 最近は少し元気がない?
11

5.１ ＭＰＩの序 （history）
MPI （Message Passing Interface ）は，メッセージ通信のプログラムを記述するために広く使われる「標準」を目指して作られた，メッセージ通信のAPI 仕様である． MPI の標準化への取り組みはSupercomputing’92 会議において，後にMPI フォーラムとして知られることになる委員会が結成され，メッセージ・パッシングの標準が作成された．これには主としてアメリカ，ヨーロッパの40 の組織から約60 人の人間が関わっており，産官学の研究者，主要な並列計算機ベンダのほとんどが参加した．そしてSupercomputing’93 会議において草案MPI 標準が示され， 1994 年にMPI-1がリリースされた．MPI の成功を受けて，MPI フォーラムはオリジナルのMPI 標準文書の改定と拡張を検討し始めた．このMPI-2 フォーラムにおける最初の成果物として，1995 年６月にMPI1.1 がリリースされた．1997年７月には，MPI1.1 に対する追加訂正と説明がなされたMPI1.2 と，MPI-1 の機能の拡張を行ったMPI-2 がリリースされた．MPI-2 の仕様は基本的にMPI-1 の改定
ではなく，新たな機能の追加であるために，MPI-1 で書かれたプログラムもMPI-2 をサポートするプラットフォームで実行できる．
以上（ http://www.mpi-forum.org/）とMPI-1，MPI-2 の日本語訳（MPI-J プロジェクト）より抜粋．

12

ＭＰＩの実装 ＭＰＩＣＨとLAM
MPIはインターフェースの規定であり，実装パッケージそのものではない．MPICHは，アメリカのアルゴンヌ国立研究所(Argonne National Laboratory) が模範実装として開発し，無償でソースコードを配布したライブラリである．移植しやすさを重視した作りになっているため盛んに移植が行われ，LAM 同様，Linuxマシンは勿論，世界中のほとんどのベンダの並列マシン上で利用することができる．特に，MPICH ではUNIX 系に限らずWindows 系へのサポートも行われている．さらに，SMP，Myrinet などのハード面にも対応している上，バッチシステムDQS，グリッドツールキットGlobus といった様々なツールを使用できることも大きな特徴の一つである．また，MPICH 1.2.0 では，MPI-1.2 の全ての機能をカバーしており，MPI-2 に関しても幾つかの機能についてはサポートしている．MPICH 1.2.0 におけるMPI-2 への対応等に関する詳細な情報は， http://wwwunix.mcs.anl.gov/mpi/mpich/に載せられている．
LAM(Local Area Multicomputer) は，ノートルダム大学の科学コンピュータ研究室(Laboratory for ScientificComputing, University of Notre Dame ) が作成したフリーのMPI ライブラリである．LAMは，標準的なMPI API だけでなく幾つかのデバッキングとモニタリングツールをユーザに提供している．MPI-1 を完全にサポートしているだけでなくMPI-2 の標準的な幾つかの要素についても機能を提供している．最新バージョン7.0.x ではMPI-2 における1 方向通信，動的プロセスの管理に関する機能がカバーされている．また，LAM は世界中のほとんどのUNIX 系ベンダの並列マシン上で利用することができる．ただし，2003年秋時点でWindows に関してはサポートされていない．LAM は，並列ジョブ実行・デバッグ統合環境であるXMPI との相性が良くXMPI を使用したいのであれば便利である．LAM に関する詳細な情報は， http://www.mpi.nd.edu/lam/ にある．
13

ＭＰＩの紹介と並列アルゴリズム
ＭＰＩプログラムの例/* greetings.c -- greetings program */#include <stdio.h>#include <string.h>#include "mpi.h"main(int argc, char* argv[]) {int
my_rank;/* rank of process*/intp;/* number of processes */intsource;/* rank of sender*/
int
dest;
/* rank of receiver */int
tag = 0;/* tag for messages */charmessage[100]; /* storage for message */MPI_Status status;/* return status for receive *//* Start up MPI */MPI_Init(&argc, &argv);/* Find out process rank */MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);/* Find out number of processes */MPI_Comm_size(MPI_COMM_WORLD, &p);

if (my_rank != 0) {/* Create message */sprintf(message, "Greetings from process %d!",my_rank);
dest = 0;/* Use strlen+1 so that '¥0' gets transmitted */MPI_Send(message, strlen(message)+1, MPI_CHAR,dest, tag, MPI_COMM_WORLD);} else { /* my_rank == 0 */for (source = 1; source < p; source++) {MPI_Recv(message, 100, MPI_CHAR, source, tag,MPI_COMM_WORLD, &status);printf("%s¥n", message);}}/* Shut down MPI */MPI_Finalize();} /* main */14

コミュニケータ，ｒａｎｋ，利用可能プロセッサ数

コミュニケータ：お互いに通信を行うプロセスの集合である．ほとんどのMPIルーチンは引数としてコミュニケータを取る．変数MPI_COMM_WORLD は，あるアプリ
ケーションを一緒に実行している全プロセスからなるグループを表しており，これは最初から用意されている．また新しいコミュニケータを作成することも可能である．

rank ：コミュニケータ内の全てのプロセスは，プロセスが初期化されたときにシステムによって示されたID をもっている．これは0 から始まる連続した正数が割り当てられる．プログラマはこれを用いて，処理の分岐，あるいはメッセージの送信元や受信先を指定することができる． MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

利用可能プロセッサ数 ：コミュニケータ内で利用できるプロセッサ数（ｐ）は，MPI_Comm_size(MPI_COMM_WORLD, &p); により取得できる ．

15

（補足） ジョブ，プロセス，スレッドジョブ(Job)
コンピュータが処理する仕事の単位 ．
プロセス(Process)
アドレス空間を排他的に利用する計算処理の単位．
プロセス実行中の資源や情報は個別に管理，生成や切り替えに時間がかかる．
複数プロセスを並列計算に使うためには，プロセス間通信が必要．
スレッド(Thread)
プロセスをさらに細分化した並行処理単位． 実行に必要な資源や情報の多くをスレッド間で共有できるため，スレッド固有の必要資源を少なくし，操作負荷を軽減することができる．

165.1
int MPI_Send(MPI send と recv/* 機能：送信バッファのデータを特定の受信先に送信する．*/

void*

message/* 送信バッファの開始アドレス(IN) */,

int

count

/* データの要素数(IN) */,MPI_Datatype

datatype/* データタイプ(IN) */,

int

dest

/* 送信先(IN) */,

int

tag

/* メッセージ・タグ(IN) */,MPI_Comm

comm/* コミュニケータ(IN) */ )int MPI_Recv( /* 機能：要求されたデータを受信バッファから取り出す．
またそれが可能になるまで待つ． */void*message/* 受信バッファの開始アドレス(OUT) */,

int

count

/*データの要素数(IN) */,MPI_Datatype

datatype/*データタイプ(IN) */,int

source/* 送信元(IN) */,inttag/* メッセージ・タグ(IN) */,MPI_Comm

comm/*コミュニケータ(IN) */,MPI_Status*

status/* ステータス(OUT) */ )17

定義済みMPIデータ型
MPIデータ型
MPI_CHARMPI_SHORTMPI_INTMPI_LONG
MPI_UNSIGNED_CHAR
MPI_UNSIGNED_SHORTMPI_UNSIGNEDMPI_UNSIGNED_LONG
MPI_FLOATMPI_DOUBLEMPI_LONG_DOUBLEMPI_BYTEMPI_PACKED

Cデータ型
signed charsigned short int
signed int
signed long int
unsigned char
unsigned short int
unsigned int
unsigned long int
float
doublelong double

定義済みMPIデータ型：ポータビリティを高めるために，MPI によって前もって定義されたデータ型である．例えば，int型であればMPI_INT というハンドルを用いる．BYTE とPACKED以外はＣ言語の型と対応している．プログラマが，新たなデータ型を定義することも可能である．
18

5.2 プログラム例 積分の台形公式

y端点と刻幅(h)y = f (x)a = x0 , b = xn , h = (b − a ) / nxi = a + ih (i = 0,1, 2" , n)" h

積分をｎ個の台形面積の和で近似
n −11()fxdx
h[ f ( xi ) + f ( xi +1 )]∑∫ai =0 2bn −1axi xi +1"bx（図）非負関数の定積分と台形公式

h= ∑ h f ( xi + ) または素直に，
2i =0f ( x0 ) f ( xn )=[++ f ( x1 ) + f ( x2 ) + " f ( xn −1 )]h2219

【例題】

4π =∫dx
20 1+ x1を用いて，πを数値計算で求める【証明】

4∫0 1 + x2 dx 変数変換 x = tanθ により，dθdx =,[0,1] → [0, π / 4],だから
2cos θπ /4π /44dθ
∫0 1 + tan2 θ cos2 θ = 4∫0 dθ = π120

台形公式を用いたπの計算 逐次プログラム（例）#include <stdio.h>
int main(int argc, char **argv){
int i,loop;
double width,x,pai=0.0;loop = atoi(argv[1]);width = 1.0 / loop;

4π =∫dx
20 1+ x1for(i=0; i<loop; i++){x = (i + 0.5) * width;pai += 4.0 / (1.0 + x * x);}
pai = pai * width;
printf("PAI = %f¥n",pai);return 0;}
21

5.3 ＭＰＩを用いた並列化 台形公式を用いたπの計算#include <mpi.h>#include <stdio.h>#include <math.h>double PI25DT =3.141592653589793238462643;
int main( int argc, char *argv[]){
int i, loop;
int numprocs, my_rank;
double pai, width, sum, x;
int source, dest , tag = 0;
int local_loop;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);

if (my_rank == 0) {loop=atoi(argv[1]);for (dest = 1; dest < numprocs; dest++) {MPI_Send(&loop, 1, MPI_INT, dest, tag,MPI_COMM_WORLD);}} else {source=0;
MPI_Recv(&loop, 1, MPI_INT, source, tag,MPI_COMM_WORLD, &status);}
width = 1.0 / loop;
local_loop = loop / numprocs;
sum = 0.0;
for (i = my_rank*local_loop;i < (my_rank+1)*local_loop; i++) {x = (i + 0.5) * width;
sum += 4.0 / (1.0 + x*x);}22

ＭＰＩを用いた並列化 台形公式を用いたπの計算
tag=1;
if (my_rank == 0) {pai=sum;for (source = 1; source < numprocs; source++) {MPI_Recv(&sum, 1, MPI_DOUBLE, source,tag, MPI_COMM_WORLD, &status);
pai=pai+sum;}} else {dest=0;MPI_Send(&sum, 1, MPI_DOUBLE, dest, tag,
MPI_COMM_WORLD);}
pai = pai * width;
if (my_rank == 0) {printf("PAI =%.16f¥n",pai);
printf("Error = %.16f¥n", fabs(pai - PI25DT));}}

MPI_Finalize();
return 0;23

5.4 並列化の効果



何故並列化するか？


高速に実行したい！


メモリをたくさん使いたいという理由で並列化する場合もある｡

本当に速くなったか？
計測してみないとわからない．⇒ ６．性能評価

24

5.5 MPIプログラムの実行

MPIプログラムの翻訳方法、実行方法は計算機によって異なる。
MPICH の場合：
MPIプログラム（C言語） の翻訳コマンド例）% mpicc test.c –o testmpicc

MPIプログラムの実行コマンド mpirun
例）% mpirun –np 8 ./test25

並列プログラムの実行時間

プログラムの評価に用いる時間は二通り• CPU使用時間： CPUが働いた時間．
• 経過時間： 計算機の動作にかかわらず，消費した時間．
計算が主体のプログラムでは，CPU使用時間 ≒ 経過時間
だが，CPU以外の装置（ディスク，ネットワーク等）を使用している時間が長いプログラムでは，その間CPUは待機するのでCPU使用時間 ＜ 経過時間となる．
並列プログラムは通信時間による影響も評価の対象となるので，通常は経過時間を用いる．
26

実行環境
プロセッサ
メモリ
OS
コンパイラ
ノード数
ネットワークライブラリ

PCクラスタIntel Itanium2 ９００MHｚ
５１２MB
RedHat Linux Advanced ServerIntel C compiler 7.1
１６
Myrinet2000 PCI64B(GM-1.6.4)
MPICH-GM 1.2.5.10

27

MPIプログラムの実行時間 （台数公式プログラム）
Loop = 1000000000

Loop = 1000

使用プロセッサ数

経過時間（秒）111.41

25.94

4

3.26

82.20

161.95

使用プロセッサ数

経過時間（秒）

10.28

20.37

40.47

80.78

161.3028

並列化すればよいというものではない

並列プログラムの作成は非並列プログラムより難しい．
• 問題解決のアルゴリズム以外に少なくとも処理の分割方法を考慮する必要がある．
• MPIの場合，さらにデータの分割方法や通信のタイミングも重要である．
苦労に見合うだけの結果が得られるかどうかを事前に検討する．

29

どんなプログラムでも並列化可能というわけではない

並列化とは，複数の処理を同時に進行させることであるので，実行の順序が非並列の場合と異なる．そのため，実行順序によって値が変わる処理は並列化できない．
並列化できないループの例：
for (i = 0; i < N; i++){a[i] = f(a[i-1]);
}

再帰参照

30

次週講義の振替のお知らせ
次週10/25（火）の並列アルゴリズム講義「グリッド講演会」
日時：平成17年10月25日(火) 9:00～12:00
場所：九州大学 国際ホール
http://www.nii.ac.jp/gridforum/

講演演題：
9:00～ 9:45 『グリッド技術入門』
独立行政法人 産業技術総合研究所グリッド研究センター長 関口 智嗣
9:45～10:30 『グリッドの研究開発状況』
国立大学法人 東京工業大学 学術国際情報センター 教授 松岡 聡（休憩）10:40～11:10 『グリッドの新たな可能性』
独立行政法人 産業技術総合研究所 グリッド研究センター長 関口 智嗣
11:10～11:40 『情報基盤センターの取り組み』
国立大学法人 九州大学 情報基盤センター
11:40～12:00 『大学間連携のための全国共同電子認証基盤（UPKI）構築事業』
国立大学法人 九州大学 情報基盤センター

31