内容に関する質問はkatagiri@cc.u-tokyo.ac.jp
まで

第２講
並列処理とMPIの基礎
東京大学情報基盤センター

1

座学「並列プログラミング入門」in 金沢

片桐孝洋

講義日程と内容について
 2015年9月12日（土）第1回並列プログラミング講習会
座学「並列プログラミング入門」in 金沢
第１講：プログラム高速化の基礎、10:30-12:00
 イントロダクション、ループアンローリング、キャッシュブロック化、
数値計算ライブラリの利用、その他
 第２講：並列処理とMPIの基礎、13:00-14:30
 並列処理の基礎、MPIインターフェース、MPI通信の種類、その他
 第３講：OpenMPの基礎、14:45-16:15
 OpenMPの基礎、利用方法、その他
 第４講：Hybrid並列化技法(MPIとOpenMPの応用)、16：30-18:00
 背景、Hybrid並列化の適用事例、利用上の注意、その他
 プログラムの性能ボトルネック に関する考えかた（I/O、単体性能(演算機ネック、メモリネック)、並列性能(バランス))、性能プロファイル、
その他


2

座学「並列プログラミング入門」in 金沢

教科書（演習書）
 「スパコンプログラミング入門－並列処理とMPIの学習－」 片桐 孝洋 著、
 東大出版会、ISBN978-4-13-062453-4、
発売日：2013年3月12日、判型:A5, 200頁
 【本書の特徴】
 C言語で解説
 C言語、Fortran90言語のサンプルプログラムが付属
 数値アルゴリズムは、図でわかりやすく説明
 本講義の内容を全てカバー
 内容は初級。初めて並列数値計算を学ぶ人向けの入門書
3

座学「並列プログラミング入門」in 金沢

並列プログラミングの基礎

4

座学「並列プログラミング入門」in 金沢

並列プログラミングとは何か？
 逐次実行のプログラム（実行時間T ）を、ｐ台の計算機を使って、T / ｐ にすること。
T
T / ｐ 素人考えでは自明。
 実際は、できるかどうかは、対象処理の内容（アルゴリズム）で 大きく 難しさが違う
アルゴリズム上、絶対に並列化できない部分の存在
 通信のためのオーバヘッドの存在 通信立ち上がり時間
 データ転送時間5

座学「並列プログラミング入門」in 金沢

並列と並行 並列（Parallel）

物理的に並列（時間的に独立）
 ある時間に実行されるものは多数
T 並行（Concurrent）

論理的に並列（時間的に依存）
 ある時間に実行されるものは１つ（＝１プロセッサで実行）T

時分割多重、疑似並列
 OSによるプロセス実行スケジューリング（ラウンドロビン方式）
6

座学「並列プログラミング入門」in 金沢

並列計算機の分類
 Michael J. Flynn教授（スタンフォード大）の分類（１９６６）
 単一命令・単一データ流（SISD, Single Instruction Single Data Stream）
 単一命令・複数データ流（SIMD, Single Instruction Multiple Data Stream）
 複数命令・単一データ流（MISD, Multiple Instruction Single Data Stream）
 複数命令・複数データ流（MIMD, Multiple Instruction Multiple Data Stream）

7

座学「並列プログラミング入門」in 金沢

並列計算機のメモリ型による分類
1.

共有メモリ型（SMP、
Symmetric Multiprocessor）

2.

分散メモリ型（メッセージパッシング）

3.

分散共有メモリ型（DSM、
Distributed Shared Memory）
8

座学「並列プログラミング入門」in 金沢

並列計算機のメモリ型による分類

4.

共有・非対称メモリ型（ccNUMA、
Cache Coherent NonUniform Memory Access）

9

座学「並列プログラミング入門」in 金沢

並列計算機の分類とMPIとの関係
 MPIは分散メモリ型計算機を想定
 MPIは、分散メモリ間の通信を定めているため

 MPIは共有メモリ型計算機でも動く
 MPIは、共有メモリ内でもプロセス間通信ができるため

 MPIを用いたプログラミングモデルは、（基本的に）SIMD MPIは、（基本的には）プログラムが１つ（＝命令と等価）しかないが、データ（配列など）は複数あるため

10

座学「並列プログラミング入門」in 金沢

並列プログラミングのモデル
 実際の並列プログラムの挙動はMIMD
 アルゴリズムを考えるときは＜SIMDが基本＞
 複雑な挙動は理解できないので

11

座学「並列プログラミング入門」in 金沢

並列プログラミングのモデル
 MIMD上での並列プログラミングのモデル
1.

SPMD（Single Program Multiple Data）
 １つの共通のプログラムが、並列処理開始時に、
全プロセッサ上で起動する
 MPI（バージョン１）のモデル

2.

Master / Worker（Master / Slave）
 １つのプロセス（Master）が、複数のプロセス（Worker）を管理（生成、消去）する。

12

座学「並列プログラミング入門」in 金沢

並列プログラムの種類
 マルチプロセス

MPI （Message Passing Interface）
 HPF （High Performance Fortran）


自動並列化Fortranコンパイラ

ユーザがデータ分割方法を明示的に記述プロセスとスレッドの違い•メモリを意識するかどうかの違い•別メモリは「プロセス」•同一メモリは「スレッド」

 マルチスレッド

Pｔhread (POSIX スレッド)
 Solaris Thread (Sun Solaris OS用)
 NT thread (Windows NT系、Windows95以降)


スレッドの Fork（分離） と Join（融合） を明示的に記述

 Java

言語仕様としてスレッドを規定

 OpenMP

13

ユーザが並列化指示行を記述

マルチプロセスとマルチスレッドは共存可能→ハイブリッドMPI/OpenMP実行

座学「並列プログラミング入門」in 金沢

並列処理の実行形態（１） データ並列

データを分割することで並列化する。
 データの操作（＝演算）は同一となる。
 データ並列の例：行列－行列積


SIMDの考え方と同じ 1 2 3   9 8 7   1 * 9  2 * 6  3 * 3 1 * 8  2 * 5  3 * 2 1 * 7  2 * 4  3 *1   ＝  4 * 9  5 * 6  6 * 3 4 * 8  5 * 5  6 * 2 4 * 7  5 * 4  6 *1 4 5 6   6 5 4   7 * 9  8 * 6  9 * 3 7 * 8  8 * 5  9 * 2 7 * 7  8 * 4  9 *1 
7 8 9 3 2 1 
 


●並列化

全CPUで共有2 3  9 8 7 
 1 * 9  2 * 6  3 * 3 1 * 8  2 * 5  3 * 2 1 * 7  2 * 4  3 *1   ＝  4 * 9  5 * 6  6 * 3 4 * 8  5 * 5  6 * 2 4 * 7  5 * 4  6 *1

CPU１  4 5 6   6 5 4 
 7 * 9  8 * 6  9 * 3 7 * 8  8 * 5  9 * 2 7 * 7  8 * 4  9 *1 
CPU２  7 8 9   3 2 1   並列に計算：初期データは異なるが演算は同一CPU０  1

14

座学「並列プログラミング入門」in 金沢

並列処理の実行形態（２） タスク並列タスク（ジョブ）を分割することで並列化する。
 データの操作（＝演算）は異なるかもしれない。
 タスク並列の例：カレーを作る

仕事１：野菜を切る
 仕事２：肉を切る
 仕事３：水を沸騰させる
 仕事４：野菜・肉を入れて煮込む
 仕事５：カレールゥを入れる


●並列化

仕事１
仕事２

仕事４

仕事３
15

仕事５

時間
座学「並列プログラミング入門」in 金沢

MPIの特徴
 メッセージパッシング用のライブラリ規格の１つ

メッセージパッシングのモデルである
コンパイラの規格、特定のソフトウエアやライブラリを指すものではない！

 分散メモリ型並列計算機で並列実行に向く
 大規模計算が可能

１プロセッサにおけるメモリサイズやファイルサイズの制約を打破可能
プロセッサ台数の多い並列システム（MPPシステム、Massively Parallel
Processingシステム）を用いる実行に向く

１プロセッサ換算で膨大な実行時間の計算を、短時間で処理可能

移植が容易
 API（Application Programming Interface）の標準化

 スケーラビリティ、性能が高い


16

通信処理をユーザが記述することによるアルゴリズムの最適化が可能
プログラミングが難しい（敷居が高い）
座学「並列プログラミング入門」in 金沢

MPIの経緯（1/2）
 MPIフォーラム（http://www.mpi-forum.org/）が仕様策定
 １９９４年５月1.0版（MPI-１）
 １９９５年６月1.1版
 １９９７年７月1.2版、 および 2.0版（MPI-2）

 米国アルゴンヌ国立研究所、およびミシシッピ州立大学

で開発
 MPI-2 では、以下を強化：
 並列I/O
 C++、Fortran 90用インターフェース 動的プロセス生成/消滅 主に、並列探索処理などの用途

17

座学「並列プログラミング入門」in 金沢

MPIの経緯 MPI3.0策定
 以下のページで経緯・ドキュメントを公開中
 http://meetings.mpi-forum.org/MPI_3.0_main_page.php
 http://meetings.mpi-forum.org/mpi3-impl-status-Nov14.pdf(Implementation Status, as of November 2014)
 注目すべき機能 ノン・ブロッキングの集団通信機能（MPI_IALLREDUCE、など）
 片方向通信（RMA、Remote Memory Access) Fortran2008 対応、など

18

座学「並列プログラミング入門」in 金沢

MPIの経緯 MPI4.0策定
 以下のページで経緯・ドキュメントを公開中
 http://meetings.mpi-forum.org/MPI_4.0_main_page.php
 検討されている機能
 ハイブリッドプログラミングへの対応
 MPIアプリケーションの耐故障性（Fault Tolerance, FT）
 いくつかのアイデアを検討中
 Active Messages (メッセージ通信のプロトコル)
計算と通信のオーバラップ 最低限の同期を用いた非同期通信
 低いオーバーヘッド、パイプライン転送
 バッファリングなしで、インタラプトハンドラで動く Stream Messaging
 新プロファイル・インターフェース
19

座学「並列プログラミング入門」in 金沢

MPIの実装
 MPICH（エム・ピッチ） 米国アルゴンヌ国立研究所が開発
 LAM（Local Area Multicomputer）
 ノートルダム大学が開発
 その他
 OpenMPI（FT-MPI、LA-MPI、LAM/MPI、PACX-MPIの統合プロジェクト） YAMPII（東大・石川研究室）（SCore通信機構をサポート） 注意点:メーカ独自機能拡張がなされていることがある
20

座学「並列プログラミング入門」in 金沢

MPIによる通信
 郵便物の郵送に同じ
 郵送に必要な情報：
1.
2.
3.
4.
5.

自分の住所、送り先の住所中に入っているものはどこにあるか中に入っているものの分類中に入っているものの量（荷物を複数同時に送る場合の）認識方法（タグ） MPIでは：
1.
2.
3.
4.
5.
21

自分の認識ID、および、送り先の認識ID
データ格納先のアドレス
データ型
データ量
タグ番号
座学「並列プログラミング入門」in 金沢

MPI関数 システム関数


MPI_Init； MPI_Comm_rank； MPI_Comm_size； MPI_Finalize； １対１通信関数


ブロッキング型
 MPI_Send；



MPI_Recv；

ノンブロッキング型
 MPI_Isend；

MPI_Irecv；

 １対全通信関数


MPI_Bcast 集団通信関数


MPI_Reduce； MPI_Allreduce； MPI_Barrier； 時間計測関数
22

MPI_Wtime
座学「並列プログラミング入門」in 金沢コミュニケータ
 MPI_COMM_WORLDは、コミュニケータとよばれる概念を保存する変数 コミュニケータは、操作を行う対象のプロセッサ群を定める
 初期状態では、０番～numprocs –１番までのプロセッサが、１つのコミュニケータに割り当てられる


この名前が、“MPI_COMM_WORLD”

 プロセッサ群を分割したい場合、MPI_Comm_split 関数を利用
メッセージを、一部のプロセッサ群に放送するときに利用 “マルチキャスト”で利用

23

座学「並列プログラミング入門」in 金沢

性能評価指標
並列化の尺度

24

座学「並列プログラミング入門」in 金沢

性能評価指標－台数効果
 台数効果SP  TS / TP (0  S p)
TP ：P台での実行時間
 TS ：逐次の実行時間、
 P台用いてSP  P のとき、理想的な（ideal）速度向上
 P台用いてSP  P のとき、スーパリニア・スピードアップ式： 主な原因は、並列化により、データアクセスが局所化されて、キャッシュヒット率が向上することによる高速化
 並列化効率

式： EP  SP / P 100 (0  Ep) [%] 飽和性能速度向上の限界 Saturation、「さちる」


25

座学「並列プログラミング入門」in 金沢Ｐアムダールの法則
K とする。
そのうち、並列化ができる割合を α とする。
 このとき、台数効果は以下のようになる。
 逐次実行時間をSP  K /(K / P  K(1)) 1/( / P  (1))  1/((1/ P 1) 1) 上記の式から、たとえ無限大の数のプロセッサを使っても（P→∞）、台数効果は、高々 １／（１－α） である。
（アムダールの法則）


26

全体の９０％が並列化できたとしても、無限大の数のプロセッサをつかっても、 １/(１-0.9) = １0 倍 にしかならない！
→高性能を達成するためには、少しでも並列化効率を上げる
実装をすることがとても重要である
座学「並列プログラミング入門」in 金沢アムダールの法則の直観例
並列化できない部分（１ブロック） 並列化できる部分（８ブロック）●逐次実行＝88.8%が並列化可能●並列実行（４並列）

9/3=3倍●並列実行（８並列）

9/2=4.5倍 ≠ 6倍

27

座学「並列プログラミング入門」in 金沢

基本演算 逐次処理では、「データ構造」が重要
 並列処理においては、「データ分散方法」が重要

になる！
1.

2.
3.
4.

各PEの「演算負荷」を均等にする
ロード・バランシング： 並列処理の基本操作の一つ

粒度調整
各PEの「利用メモリ量」を均等にする
演算に伴う通信時間を短縮する
各PEの「データ・アクセスパターン」を高速な方式にする（＝逐次処理におけるデータ構造と同じ）

 行列データの分散方法＜次元レベル＞： １次元分散方式、２次元分散方式
 ＜分割レベル＞： ブロック分割方式、サイクリック（循環）分割方式
28

座学「並列プログラミング入門」in 金沢

１次元分散
N/4行

PE=0

N/4行

PE=1

N/4行

PE=2

N/4行

PE=3

•（行方向) ブロック分割方式•(Block, *) 分散方式

N列
1行•(行方向) サイクリック分割方式•(Cyclic, *) 分散方式

2行•(行方向)ブロック・サイクリック分割方式•(Cyclic(2), *) 分散方式

この例の「２」： ＜ブロック幅＞とよぶ
29

座学「並列プログラミング入門」in 金沢2次元分散
N/2

N/2

N/2

PE=0 PE=1

N/2

PE=2 PE=3•ブロック・ブロック分割方式•(Block, Block)分散方式•サイクリック・サイクリック分割方式•(Cyclic, Cyclic)分散方式

0

1

0

1

0

1

0

1

2

3

2

3

2

3

2

3

0

1

0

1

0

1

0

1

2

3

2

3

2

3

2

3

0

1

0

1

0

1

0

1

2

3

2

3

2

3

2

3

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

1

1

0

0

1

1

2

3

2

3

2

3

2

3

2

2

3

3

2

2

3

3

2

2

3

3

2

2

3

3

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

2

2

3

3

2

2

3

3

2

2

3

3

2

2

3

3

•二次元ブロック・サイクリック分割方式•(Cyclic(2), Cyclic(2))分散方式

座学「並列プログラミング入門」in 金沢30

ベクトルどうしの演算 以下の演算z  a x y

ここで、αはスカラ、ｚ、ｘ、ｙ はベクトル

 どのようなデータ分散方式でも並列処理が可能

ただし、スカラ α は全PEで所有する。
 ベクトルはO(ｎ)のメモリ領域が必要なのに対し、スカラはO(１)のメモリ領域で大丈夫。
＝→スカラメモリ領域は無視可能
 計算量：O(N/P)
 あまり面白くないｚ
31

座学「並列プログラミング入門」in 金沢

＋

α

ｘ

ｙ

行列とベクトルの積 ＜行方式＞と＜列方式＞がある。
＜データ分散方式＞と＜方式＞組のみ合わせがあり、少し面白い
①②

①②

①②

①

①
②

…

…

=

…

…

②
=

①
②

for(i=0;i<n;i++){y[i]=0.0;
for(j=0;j<n;j++){y[i] += a[i][j]*x[j];}}for(j=0; j<n; j++) y[j]=0.0;
for(j=0; j<n; j++) {for (i=0; i<n; i++) {y[i] += a[i][j]*x[j];}}＜行方式＞： 自然な実装
C言語向き
32

＜列方式＞： Fortran言語向き
座学「並列プログラミング入門」in 金沢

行列とベクトルの積＜行方式の場合＞＜行方向分散方式＞ ：行方式に向く分散方式
PE=0

PE=0

PE=1

PE=1

=

PE=2
PE=3

PE=2
PE=3

右辺ベクトルを MPI_Allgather関数を利用し、全PEで所有する各PE内で行列ベクトル積を行う＜列方向分散方式＞ ：ベクトルの要素すべてがほしいときに向く=
各PE内で行列-ベクトル積
を行う
33

+

+

+

MPI_Reduce関数で総和を求める（※ある１PEにベクトルすべてが集まる）

座学「並列プログラミング入門」in 金沢

行列とベクトルの積＜列方式の場合＞＜行方向分散方式＞ ：無駄が多く使われない
PE=0

PE=0

PE=1

PE=1

PE=2

= + + + = PE=2

PE=3

PE=3

右辺ベクトルを MPI_Allgather関数を利用して、全PEで所有する結果をMPI_Reduce関数により総和を求める＜列方向分散方式＞ ：列方式に向く分散方式=
各PE内で行列-ベクトル積
を行う
34

+

+

+

MPI_Reduce関数で総和を求める（※ある１PEにベクトルすべてが集まる）

座学「並列プログラミング入門」in 金沢基本的なMPI関数
送信、受信のためのインタフェース

35

座学「並列プログラミング入門」in 金沢

略語とMPI用語
 MPIは「プロセス」間の通信を行います。
 プロセスは、HT（ハイパースレッド）などを使わなければ、「プロセッサ」（もしくは、コア）に１対１で割り当てられます。
 今後、「MPIプロセス」と書くのは長いので、ここではPE（Processer Elementsの略）と書きます。


ただし用語として「PE」は、現在あまり使われていません。

 ランク（Rank）
各「MPIプロセス」の「識別番号」のこと。
 通常MPIでは、MPI_Comm_rank関数で設定される変数（サンプルプログラムではmyid）に、０～全PE数－１ の数値が入る
 世の中の全MPIプロセス数を知るには、MPI_Comm_size関数を使う。
（サンプルプログラムでは、numprocs に、この数値が入る）


36

座学「並列プログラミング入門」in 金沢ランクの説明図

37

MPI
プログラム

MPI
プログラム

MPI
プログラム

MPI
プログラム

ランク０

ランク１

ランク２

ランク３

座学「並列プログラミング入門」in 金沢

C言語インターフェースとFortranインターフェースの違い
 Ｃ版は、 整数変数ierr が戻り値
ierr = MPI_Xxxx(….);
 Ｆｏｒｔｒａｎ版は、最後に整数変数ierrが引数
call MPI_XXXX(…., ierr) システム用配列の確保の仕方
 Ｃ言語

MPI_Status istatus;
 Ｆｏｒｔｒａｎ言語
integer istatus(MPI_STATUS_SIZE)
38

座学「並列プログラミング入門」in 金沢

C言語インターフェースとFortranインターフェースの違い
 MPIにおける、データ型の指定
 C言語

MPI_CHAR (文字型) 、 MPI_INT (整数型)、
MPI_FLOAT (実数型)、MPI_DOUBLE(倍精度実数型)
 Fortran言語
MPI_CHARACTER (文字型) 、MPI_INTEGER (整数型)、
MPI_REAL (実数型)、MPI_DOUBLE_PRECISION(倍精度実数型) 、MPI_COMPLEX(複素数型)
 以降は、Ｃ言語インタフェースで説明する

39

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Recv（１／２）
 ierr =MPI_Recv(recvbuf, icount, idatatype, isource,
itag, icomm, istatus);

recvbuf : 受信領域の先頭番地を指定する。
 icount : 整数型。受信領域のデータ要素数を指定する。
 idatatype : 整数型。受信領域のデータの型を指定する。
 MPI_CHAR (文字型) 、MPI_INT (整数型)、

MPI_FLOAT (実数型)、 MPI_DOUBLE(倍精度実数型)
isource : 整数型。受信したいメッセージを送信するPEのランクを指定する。
 任意のPEから受信したいときは、MPI_ANY_SOURCE を指定する。

40

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Recv（２／２）
itag : 整数型。受信したいメッセージに付いているタグの値を指定。
 任意のタグ値のメッセージを受信したいときは、MPI_ANY_TAG を指定。



icomm : 整数型。PE集団を認識する番号であるコミュニケータ
を指定。
 通常ではMPI_COMM_WORLD を指定すればよい。



istatus : MPI_Status型（整数型の配列）。受信状況に関する情報が入る。かならず専用の型宣言をした配列を確保すること。
 要素数がMPI_STATUS_SIZEの整数配列が宣言される。
 受信したメッセージの送信元のランクが istatus[MPI_SOURCE]、

タグが istatus[MPI_TAG] に代入される。
 C言語： MPI_Status istatus;
 Fortran言語： integer istatus(MPI_STATUS_SIZE)ierr(戻り値) : 整数型。エラーコードが入る。
41

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Send ierr = MPI_Send(sendbuf, icount, idatatype, idest,

itag, icomm);
sendbuf : 送信領域の先頭番地を指定
 icount : 整数型。送信領域のデータ要素数を指定
 idatatype : 整数型。送信領域のデータの型を指定
 idest : 整数型。送信したいPEのicomm内でのランクを指定 itag : 整数型。受信したいメッセージに付けられたタグの値を指定
 icomm : 整数型。プロセッサー集団を認識する番号である
コミュニケータを指定
 ierr (戻り値) : 整数型。エラーコードが入る。
42

座学「並列プログラミング入門」in 金沢

Send－Recvの概念（１対１通信）
PE0

PE１

PE２

PE３

MPI_Send

MPI_Recv

43

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Bcast ierr = MPI_Bcast(sendbuf, icount, idatatype,iroot, icomm);
sendbuf : 送信および受信領域の先頭番地を指定する。
 icount : 整数型。送信領域のデータ要素数を指定する。
 idatatype : 整数型。送信領域のデータの型を指定する。
 iroot : 整数型。送信したいメッセージがあるPEの番号を指定する。全PEで同じ値を指定する必要がある。
 icomm : 整数型。PE集団を認識する番号である
コミュニケータを指定する。
 ierr (戻り値) : 整数型。エラーコードが入る。


44

座学「並列プログラミング入門」in 金沢

MPI_Bcastの概念（集団通信）
PE0
MPI_Bcast()

PE１
MPI_Bcast()

iroot

45

PE２

PE３

MPI_Bcast()

MPI_Bcast()

全PEが関数を呼ぶこと座学「並列プログラミング入門」in 金沢

リダクション演算
 ＜操作＞によって＜次元＞を減少（リダクション）させる処理
 例：

内積演算
ベクトル（ｎ次元空間） → スカラ（１次元空間）

 リダクション演算は、通信と計算を必要とする
 集団通信演算（collective communication operation）と呼ばれる
 演算結果の持ち方の違いで、２種のインタフェースが存在する
46

座学「並列プログラミング入門」in 金沢

リダクション演算 演算結果に対する所有PEの違い
 MPI_Reduce関数
 リダクション演算の結果を、ある一つのPEに所有させる

PE0
PE0
PE1

操作
操作

PE2

PE0

 MPI_Allreduce関数
 リダクション演算の結果を、全てのPEに所有させる

PE0
PE1
47

PE0

操作
PE2
座学「並列プログラミング入門」in 金沢

PE1

PE2

基礎的なMPI関数―MPI_Reduce ierr = MPI_Reduce(sendbuf, recvbuf, icount,

idatatype, iop, iroot, icomm);
sendbuf : 送信領域の先頭番地を指定する。
 recvbuf : 受信領域の先頭番地を指定する。iroot で指定したPEのみで書き込みがなされる。
送信領域と受信領域は、同一であってはならない。
すなわち、異なる配列を確保しなくてはならない。
 icount : 整数型。送信領域のデータ要素数を指定する。
 idatatype : 整数型。送信領域のデータの型を指定する。
 （Fortran）＜最小／最大値と位置＞を返す演算を指定する場合は、MPI_2INTEGER(整数型)、 MPI_2REAL(単精度型)、MPI_2DOUBLE_PRECISION(倍精度型) 、を指定する。
48

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Reduce iop :

整数型。演算の種類を指定する。

 MPI_SUM (総和)、 MPI_PROD (積)、 MPI_MAX (最大)、MPI_MIN (最小)、 MPI_MAXLOC (最大と位置)、
MPI_MINLOC (最小と位置) など。
 iroot :整数型。結果を受け取るPEのicomm 内でのランクを指定する。全てのicomm 内のPEで同じ値を指定する必要がある。
 icomm : 整数型。PE集団を認識する番号であるコ
ミュニケータを指定する。
 ierr : 整数型。 エラーコードが入る。
49

座学「並列プログラミング入門」in 金沢

MPI_Reduceの概念（集団通信）
PE0
MPI_Reduce()

PE１

PE２

PE３

MPI_Reduce()

MPI_Reduce()

MPI_Reduce()

データ３

データ４

iroot
データ１

データ２

iop（指定された演算）50

座学「並列プログラミング入門」in 金沢

MPI_Reduceによる２リスト処理例（MPI_2DOUBLE_PRECISION と MPI_MAXLOC）
PE0
PE１
PE２
PE３
MPI_Reduce()

MPI_Reduce()

MPI_Reduce()

MPI_Reduce()

iroot
3.1

4.1

5.9

2.6

2.0

5.0

9.0

13.0

MPI_MAXLOC
5.9
9.0
51

LU分解の枢軸選択処理

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Allreduce ierr = MPI_Allreduce(sendbuf, recvbuf, icount,

idatatype, iop, icomm);
sendbuf : 送信領域の先頭番地を指定する。
 recvbuf : 受信領域の先頭番地を指定する。iroot で指定したPEのみで書き込みがなされる。
送信領域と受信領域は、同一であってはならない。
すなわち、異なる配列を確保しなくてはならない。
 icount : 整数型。送信領域のデータ要素数を指定する。
 idatatype : 整数型。送信領域のデータの型を指定する。
 最小値や最大値と位置を返す演算を指定する場合は、

MPI_2INT(整数型)、MPI_2FLOAT (単精度型)、
MPI_2DOUBLE(倍精度型) を指定する。

52

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Allreduce iop :

整数型。演算の種類を指定する。
 MPI_SUM (総和)、 MPI_PROD (積)、 MPI_MAX(最大)、MPI_MIN (最小)、 MPI_MAXLOC (最大と位置)、 MPI_MINLOC (最小と位置) など。
 icomm : 整数型。PE集団を認識する番号であるコ
ミュニケータを指定する。
 ierr : 整数型。 エラーコードが入る。

53

座学「並列プログラミング入門」in 金沢

MPI_Allreduceの概念（集団通信）
PE0

PE１

PE２

PE３

MPI_Allreduce()

MPI_Allreduce()

MPI_Allreduce()

MPI_Allreduce()

データ０

データ１

データ２

データ３

iop（指定された演算）
演算済みデータの放送

54

座学「並列プログラミング入門」in 金沢

リダクション演算
 性能について リダクション演算は、１対１通信に比べ遅い
 プログラム中で多用すべきでない！
 MPI_Allreduce は MPI_Reduce に比べ遅い
 MPI_Allreduce は、放送処理が入る。
 なるべく、MPI_Reduce を使う。

55

座学「並列プログラミング入門」in 金沢

行列の転置 行列

A が（Block,＊）分散されているとする。
T 行列 A の転置行列 A を作るには、MPIでは
次の２通りの関数を用いる


MPI_Gather関数

a
b
c


MPI_Scatter関数

a b c
56

a b c

a
b
c
座学「並列プログラミング入門」in 金沢

集めるメッセージ
サイズが各PEで均一のとき使う
集めるサイズが各PEで均一でないときは：
MPI_GatherV関数
MPI_ScatterV関数

基礎的なMPI関数―MPI_Gather
 ierr = MPI_Gather (sendbuf, isendcount, isendtype,recvbuf, irecvcount, irecvtype, iroot, icomm);
sendbuf : 送信領域の先頭番地を指定する。
 isendcount: 整数型。送信領域のデータ要素数を指定する。
 isendtype : 整数型。送信領域のデータの型を指定する。
 recvbuf : 受信領域の先頭番地を指定する。iroot で指定したPEのみで書き込みがなされる。
 なお原則として、送信領域と受信領域は、同一であってはならない。

すなわち、異なる配列を確保しなくてはならない。


irecvcount:

整数型。受信領域のデータ要素数を指定する。

 この要素数は、１PE当たりの送信データ数を指定すること。
 MPI_Gather 関数では各PEで異なる数のデータを収集することはできないので、同じ値を指定すること。
57

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Gather
 irecvtype :整数型。受信領域のデータ型を指定する。
 iroot : 整数型。収集データを受け取るPEのicomm 内でのランクを指定する。
 全てのicomm 内のPEで同じ値を指定する必要がある。
 icomm : 整数型。PE集団を認識する番号である
コミュニケータを指定する。
 ierr : 整数型。エラーコードが入る。
58

座学「並列プログラミング入門」in 金沢

MPI_Gatherの概念（集団通信）
PE0

PE１

PE２

PE３

MPI_Gather()

MPI_Gather()

MPI_Gather()

MPI_Gather()

データC

データD

iroot
データA

データB

収集処理
データA
データB
データC
データD
59

座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Scatter ierr = MPI_Scatter ( sendbuf, isendcount, isendtype,recvbuf, irecvcount, irecvtype, iroot, icomm);
sendbuf : 送信領域の先頭番地を指定する。
 isendcount: 整数型。送信領域のデータ要素数を指定する。
 この要素数は、１PE当たりに送られる送信データ数を指定すること。
 MPI_Scatter 関数では各PEで異なる数のデータを分散することはできないので、同じ値を指定すること 。

isendtype : 整数型。送信領域のデータの型を指定する。
iroot で指定したPEのみ有効となる。
 recvbuf : 受信領域の先頭番地を指定する。
 なお原則として、送信領域と受信領域は、同一であってはならない。

すなわち、異なる配列を確保しなくてはならない。
60

irecvcount:

整数型。受信領域のデータ要素数を指定する。
座学「並列プログラミング入門」in 金沢

基礎的なMPI関数―MPI_Scatter irecvtype :整数型。受信領域のデータ型を指定する。
 iroot : 整数型。収集データを受け取るPEのicomm 内でのランクを指定する。
 全てのicomm 内のPEで同じ値を指定する必要がある。
 icomm : 整数型。PE集団を認識する番号である
コミュニケータを指定する。
 ierr : 整数型。エラーコードが入る。
61

座学「並列プログラミング入門」in 金沢

MPI_Scatterの概念（集団通信）
PE0

PE１

PE２

PE３

MPI_Scatter()

MPI_Scatter()

MPI_Scatter()

MPI_Scatter()

iroot
データA
データB
データC
データD

分配処理
データA
62

データB

データC

座学「並列プログラミング入門」in 金沢

データD

MPIプログラム実例

63

座学「並列プログラミング入門」in 金沢

MPIの起動
 MPIを起動するには
1.

MPIをコンパイルできるコンパイラでコンパイル 実行ファイルは a.out

2.

とする（任意の名前を付けられます）

以下のコマンドを実行 インタラクティブ実行では、以下のコマンドを直接入力
 バッチジョブ実行では、ジョブスクリプトファイル中に記載$ mpirun –np 8./a.out

MPI起動
コマンド

MPIの
実行ファイル
名

64

MPI
プロセス
数

※スパコンのバッチジョブ実行
では、MPIプロセス数は専用の指示文で指定する場合があります。
その場合は以下になることがあります。

$mpirun ./a.out

座学「並列プログラミング入門」in 金沢

MPIの起動
mpirun -np 4 ./a.out

a.out

65

a.out

a.out

座学「並列プログラミング入門」in 金沢

a.out並列版Helloプログラムの説明（C言語）#include <stdio.h>#include <mpi.h>

このプログラムは、全ＰＥで起動される

void main(int argc, char* argv[]) {int
int

myid, numprocs;
ierr, rc;

MPIの初期化
自分のID番号を取得：各ＰＥで値は異なる

ierr = MPI_Init(&argc, &argv);
ierr = MPI_Comm_rank(MPI_COMM_WORLD, &myid);ierr = MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
printf("Hello parallel world! Myid:%d ¥n", myid);rc = MPI_Finalize();exit(0);}66

全体のプロセッサ台数を取得：各ＰＥで値は同じ

MPIの終了座学「並列プログラミング入門」in 金沢

変数myidの説明図

同じ変数名でも別メモリ上に別変数で確保
67

MPI
プログラム

MPI
プログラム

MPI
プログラム

MPI
プログラム

ランク０
myid=0

ランク１
myid=1

ランク２
myid=2

ランク３
myid=3

座学「並列プログラミング入門」in 金沢

並列版Helloプログラムの説明（Fortran言語）
このプログラムは、全ＰＥで起動される

program main
include 'mpif.h'common /mpienv/myid,numprocs
integer myid, numprocs
integer ierr

MPIの初期化
自分のID番号を取得：各ＰＥで値は異なる

call MPI_INIT(ierr)call MPI_COMM_RANK(MPI_COMM_WORLD, myid, ierr)call MPI_COMM_SIZE(MPI_COMM_WORLD, numprocs, ierr)print *, "Hello parallel world! Myid:", myid
call MPI_FINALIZE(ierr)
stop
end
68

全体のプロセッサ台数を取得：各ＰＥで値は同じ

MPIの終了座学「並列プログラミング入門」in 金沢

プログラム出力例
 ４プロセス実行の出力例

Hello parallel world! Myid:0
Hello parallel world! Myid:3
Hello parallel world! Myid:１
Hello parallel world! Myid:2

4プロセスなので、表示が４個でる（1000プロセスなら1000個出力がでる）
myid番号が表示される。全体で重複した番号は無い。
必ずしも、myidが0から3まで、連続して出ない→各行は同期して実行されていない→実行ごとに結果は異なる
69

座学「並列プログラミング入門」in 金沢

総和演算プログラム（逐次転送方式）


各プロセスが所有するデータを、全プロセスで加算し、あるプロセス１つが結果を所有する演算を考える。

 素朴な方法（逐次転送方式）（0番でなければ）左隣のプロセスからデータを受信する；
左隣のプロセスからデータが来ていたら；

1.
2.
1.
2.
3.
4.

受信する;
＜自分のデータ＞と＜受信データ＞を加算する;（最終ランクでなければ）右隣のプロセスに＜2の加算した結果を＞送信する;
処理を終了する;

実装上の注意

左隣りとは、（myid-１）のIDをもつプロセス

右隣りとは、（myid+１）のIDをもつプロセス70

myid=0のプロセスは、左隣りはないので、受信しない

myid=p-１のプロセスは、右隣りはないので、送信しない
座学「並列プログラミング入門」in 金沢バケツリレー方式による加算
所有データ

所有データ
０

１

０

所有データ

所有データ

２

３

１

CPU0

CPU１

３
CPU２

送信

送信

０ ＋ １ ＝ １

CPU３
送信

１ ＋ ２ ＝ ３

３ ＋ ３ ＝ ６

最終結果

71

座学「並列プログラミング入門」in 金沢

１対１通信利用例（逐次転送方式、C言語）
受信用システム配列の確保
void main(int argc, char* argv[]) {MPI_Status istatus;
自分より一つ少ない….
ID番号（myid-1）から、dsendbuf = myid;
double型データ１つをdrecvbuf = 0.0;
受信しdrecvbuf変数に
if (myid != 0) {ierr = MPI_Recv(&drecvbuf, 1, MPI_DOUBLE, myid-1, 0, 代入
MPI_COMM_WORLD, &istatus);}
自分より一つ多い
dsendbuf = dsendbuf + drecvbuf;
ID番号（myid+1）に、if (myid != nprocs-1) {ierr = MPI_Send(&dsendbuf, 1, MPI_DOUBLE, myid+1, 0, dsendbuf変数に入っているdouble型データ
MPI_COMM_WORLD);
１つを送信}
if (myid == nprocs-1) printf ("Total = %4.2lf ¥n", dsendbuf);….
}
72

座学「並列プログラミング入門」in 金沢

１対１通信利用例（逐次転送方式、Fortran言語）
program main
受信用システム配列の確保
integer istatus(MPI_STATUS_SIZE)….
dsendbuf = myid
自分より一つ少ない
drecvbuf = 0.0
ID番号（myid-1）から、
if (myid .ne. 0) thendouble型データ１つを
call MPI_RECV(drecvbuf, 1, MPI_DOUBLE_PRECISION,
受信しdrecvbuf変数に&
myid-1, 0, MPI_COMM_WORLD, istatus, ierr)endif
代入
dsendbuf = dsendbuf + drecvbuf
if (myid .ne. numprocs-1) thencall MPI_SEND(dsendbuf, 1, MPI_DOUBLE_PRECISION,&
myid+1, 0, MPI_COMM_WORLD, ierr)
自分より一つ多い
endif
ID番号（myid+1）に、if (myid .eq. numprocs-1) thendsendbuf変数にprint *, "Total = ", dsendbuf
endif
入っているdouble型….
データ１つを送信
stop
end
73

座学「並列プログラミング入門」in 金沢

総和演算プログラム（二分木通信方式）
 二分木通信方式

k = １;for (i=0; i < log2(nprocs); i++)if ( (myid & k) == k)

1.
2.
3.




else

4.



74

(myid – k)番 プロセス からデータを受信；
自分のデータと、受信データを加算する；
k = k * 2;
(myid + k)番 プロセス に、データを転送する；
処理を終了する；

座学「並列プログラミング入門」in 金沢

総和演算プログラム（二分木通信方式）
３段目＝ｌog2（８）段目

3

1

3

２段目
0

1段目

1

2

7
5

3

4

7

5

6

7

7
7

3

0
75

5

3

1
1

2

3

4

7
5

座学「並列プログラミング入門」in 金沢

67

総和演算プログラム（二分木通信方式）
 実装上の工夫

要点： プロセス番号の２進数表記の情報を利用する
 第i段において、受信するプロセスの条件は、以下で書ける：
myid & k が k と一致 ここで、k = 2^(i-１) 。
 つまり、プロセス番号の２進数表記で右からi番目のビットが立っている

プロセスが、送信することにする

また、送信元のプロセス番号は、以下で書ける：
myid + k つまり 、通信が成立するPE番号の間隔は２＾(i-１)



76←二分木なので

送信プロセスについては、上記の逆が成り立つ。

座学「並列プログラミング入門」in 金沢

総和演算プログラム（二分木通信方式）
 逐次転送方式の通信回数

明らかに、nprocs－１ 回

 二分木通信方式の通信回数

見積もりの前提
 各段で行われる通信は、完全に並列で行われる（通信の衝突は発生しない）

段数の分の通信回数となる
 つまり、log2(nprocs) 回 両者の通信回数の比較

プロセッサ台数が増すと、通信回数の差（＝実行時間）がとても大きくなる １０２４構成では、１０２３回 対 １０回！




77

でも、必ずしも二分木通信方式がよいとは限らない（通信衝突の多発）
座学「並列プログラミング入門」in 金沢

その他の話題（MPIプロセスの割り当て）
 MPIプロセスと物理ノードとの割り当て

Machine fileでユーザが直接行う
 スパコン環境では、バッチジョブシステムが行う バッチジョブシステムが行う場合、通信網の形状を考慮し、通信パターンを考慮し、最適にMPIプロセスが物理ノードに割り当てられるかはわからない
最悪、通信衝突が多発する
 ユーザが、MPIプロセスを割り当てるネットワーク形状を指定できる、
バッチジョブシステムもある （例：富士通FX１０）
 MPIプロセス割り当てを最適化するツールの研究もある
 スパコンセンタの運用の都合で、ユーザが望む

ネットワーク形状が常に確保できるとは限らない→通信を減らす努力、実行時通信最適化の研究進展、が望まれる
78

座学「並列プログラミング入門」in 金沢

参考文献
1.
2.

3.
4.

79

MPI並列プログラミング、P.パチェコ 著 ／ 秋葉 博 訳
並列プログラミング虎の巻MPI版、青山幸也 著、
高度情報科学技術研究機構（ＲＩＳＴ） 神戸センター（ http://www.hpci-office.jp/pages/seminar_text ）Message Passing Interface Forum（ http://www.mpi-forum.org/ ）並列コンピュータ工学、富田眞治著、昭晃堂（１９９６）

座学「並列プログラミング入門」in 金沢

レポート課題（その１） 問題レベルを以下に設定
問題のレベルに関する記述：•L00: きわめて簡単な問題。
•L10： ちょっと考えればわかる問題。
•L20： 標準的な問題。
•L30： 数時間程度必要とする問題。
•L40： 数週間程度必要とする問題。複雑な実装を必要とする。
•L50： 数か月程度必要とする問題。未解決問題を含む。
※L４０以上は、論文を出版するに値する問題。

 教科書のサンプルプログラムは以下が利用可能
 Sample-fx.tar

80

座学「並列プログラミング入門」in 金沢

レポート課題（その２）
1.
2.

3.

[L05] MPIとは何か説明せよ。
[L10] 逐次転送方式、２分木通信方式の実行時間を計測し、どの方式が何台のプロセッサ台数で有効となるかを明らかにせよ。また、その理由について、考察せよ。
[L15] 二分木通信方式について、プロセッサ台数が２のべき乗でないときにも動作するように、プログラムを
改良せよ。

81

座学「並列プログラミング入門」in 金沢