並列処理論2

並列処理のためのプログラム作成
1
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
並列化
コンパイラ
並列性解析・抽出
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
2
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
並列化は行われていない
並列化
コンパイラ
並列性解析・抽出
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
3
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型
人手による
並列化が必要
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
並列化
コンパイラ
並列性解析・抽出
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
4
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型アルゴリズムが必要
並列型
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
アルゴリズムの並列性
並列性解析・抽出
以外の並列化は必要
並列化
コンパイラ
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
5
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型
並列化は行われていない
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
並列化のすべてを
並列性解析・抽出
並列化
コンパイラが行う
コンパイラ
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
6
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
並列型
並列化が行われている
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
残された並列化を
並列性解析・抽出
並列化
コンパイラが行う
コンパイラ
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
7
並列処理プログラミング
解くべき問題
アルゴリズム
逐次型
（一部）並列化が行われている
並列化のための書換え
並列型
プログラミング逐次言語拡張言語並列言語逐次言語+並列化ライブラリ
言語
並列化
コンパイラ
並列性解析・抽出
タスクスケジューリング
マシンコード生成
OS
並列コンピュータ
8
並列処理プログラミングモデル
• プログラミングモデル（ソフトウェア的な通信モデル）
の観点からは次の二つに分類される．
– 共有変数型（単一メモリ空間型）
– メッセージ転送型
9
共有変数型
• 異なるプロセッサ上のプロセス間で変数を共有
共有変数を介してプロセス間通信
→ ポインタ変数などの扱いが楽
• 共有メモリ型や分散共有メモリ型並列計算機上で用
いられることが多い
物理的にメモリを共有する必要は必ずしも無い
→ OSサポートなど
• 分散メモリ型並列計算機での実装では性能低下は大
P0
代入
P1
参照
共有変数
10
メッセージ転送型
• 異なるプロセッサ上のプロセス間での通信手段
→メッセージ転送のみ
変数のパッキングなどが必要
• 送信側と受信側のプロセッサが協調してデータ転送
• 分散メモリ型並列計算機上で用いられることが多い
共有メモリ型並列計算機でも実現可能
→ 共有メモリ上に通信チャネルを用意する
P0
send
P1
receive
11
プログラミングモデルとH/Wの構成
• ハードウェア構成とプログラミングモデルを無関係に
したい．
– ハードのメモリ制御（キャッシュ制御を含む）機構や
通信制御機構
– 通信ライブラリ
– ソフトウェア分散共有メモリ
– コンパイラ
• パフォーマンス向上にはH/W構成に適したプログラミ
ングが必要．
-PGAS: Partitioned Global Address Space モデル
例) UPC(Unified Parallel C), CAF(co-Array Fortran)
12
並列処理を可能とするOS環境
• 並列処理コンピュータ上での並列処理を実現するOS
機能
• プロセス間並列（マルチタスキング）
– 単一プロセッサでの複数プロセスの並行処理の発
展形
– プログラム中のタスク群を複数のプロセスに割り当
て，それらを複数プロセッサで実行する．
• スレッド間並列（マルチスレッディング）
– ひとつのプロセスをさらにスレッドに分割しそれらを
複数のプロセッサで実行する．
– プログラム中のタスク群はスレッドに割り当てる．
13
プロセス間並列
• 例）１プロセッサでの複数プロセスの並行処理
実行中
プロセスb
アイドル
コンテキスト
スイッチ
プロセスa2
プロセスa1
プロセス生成
時間
14
プロセス間並列
• 例）１プロセッサでの複数プロセスの並行処理
実行中
プロセスb
アイドル
コンテキスト
スイッチ
プロセスa2
プロセスa1
プロセス生成
時間
• 例）２プロセッサでの複数プロセスの並列/並行処理
プロセスb
プロセッサ1
プロセスa3
プロセスa2
プロセッサ2
プロセスa1
時間
15
プロセス間並列
• プロセスの生成・終了・待ち合わせ機能
– fork(), exit(), wait()などの関数
• プロセス間でのデータの授受（IPC）のための機能
– データ転送
「パイプ」，「ソケット」，「メッセージキュー」など
– データ共有
共有メモリ領域：
複数プロセスのメモリ空間の一部をオーバーラップ
– 同期
「シグナル」，「セマフォ」など
• 各種操作のコストが大きい．
– プロセス生成，コンテキストスイッチ，同期，通信 16
スレッド間並列（マルチスレッド:MT）
• スレッド：
– 同一プロセス内で複数制御フロー（スレッド）を実現．
– 個別の制御フローを個別のスレッドに対応させる．
– スレッドをプロセッサへのスケジュール単位とする．
– 同一プロセスのスレッドはアドレス空間を共有．
→ メモリ管理の負荷が小さい
→ 通信・同期のコストが小さい
– スレッド固有情報（プログラムカウンタ，スタックポイン
タ，レジスタセット）がプロセス情報（アドレス空間，ユ
ーザID，etc.）より少ない．
→ スレッド生成や各種操作のコストが小さい．
17
スレッド間並列（マルチスレッド:MT）
• スレッド：
プロセスb スレッド1
プロセッサ1
スレッド3
プロセスa スレッド2
プロセッサ2
スレッド1
時間
実行中
アイドル
コンテキスト
スイッチ
スレッド生成
18
並列プログラミングの方法
• 逐次言語 + マルチタスキング
• 逐次言語 + スレッドライブラリ
• 逐次言語 + メッセージ通信ライブラリ
例) MPI (Message-Passing Interface)
• 逐次言語 + コンパイラディレクティブ(+α)
例) OpenMP
• 並列言語
例) HPF (High Performance Fortran)
• 逐次言語 + 自動並列化コンパイラ
19
並列プログラミングの方法
• 参考書/例題プログラムの出典
「はじめての並列プログラミング｣
20
マルチタスキングによる並列処理
• forkシステムコールにより複数プロセスを立ち上げての
並列処理(並行処理)
• (親)プロセスがfork関数を呼び出すと，
– 子プロセスが生成される．
子プロセス環境は親プロセスの環境が複製される．
– 親プロセスと子プロセスはfork関数呼出しから戻った
ところからそれぞれ実行を再開．
– fork関数の戻り値は，子プロセスでは0となり，親プロ
セスでは子プロセスのプロセスIDとなる．
• 子プロセスでは，処理終了後exit()システムコールなど
でプロセスを終了する．
• 親プロセス，子プロセス間では共有変数などを用いて
21
データの授受を行う．
マルチタスキング－例題プログラム
和を部分和として二つの
プロセスで求めるプログラム
#include <sys/shm.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <stdio.h>
pid_t pid1, pid2;
int shared_mem_id;
int *shared_mem_ptr;
int main()
{
int *rc1, *rc2;
int arg1[2] = {1,5}, arg2[2] = {6,10};
int status;
shared_mem_id=shmget(IPC_PRIVATE, 2*sizeof(int),0666);
shared_mem_ptr=shmat(shared_mem_id,0,0);
rc1 = shared_mem_ptr;
rc2 = (shared_mem_ptr+1);
続く
22
マルチタスキング－例題プログラム
和を部分和として二つの
プロセスで求めるプログラム
if((pid1=fork())==0){
*rc1=sum(&arg1);
exit(0);
}
if((pid2=fork())==0){
*rc2=sum(&arg2);
exit(0);
}
int sum(int *arg_ptr)
{
int min = *arg_ptr;
int max = *(arg_ptr+1);
int i, sum;
for (i=min,sum =0;i<=max;i++)
sum += i;
return sum;
}
waitpid(pid1, status, 0);
waitpid(pid2, status, 0);
printf("%d %d\n", *rc1 ,*rc2);
printf("%d+..+%d=%d\n", arg1[0],arg2[1], *rc1 + *rc2);
}
続く
23
マルチタスキング－例題プログラム
和を部分和として二つの
プロセスで求めるプログラム
#include <sys/shm.h>
#include <sys/types.h>
#include <sys/ipc.h>
ヘッダファイルの読み込み
#include <stdio.h>
pid_t pid1, pid2;
プロセスID変数
int shared_mem_id;
int *shared_mem_ptr;
共有変数管理のための変数
int main()
{
共有変数へのポインタ変数
int *rc1, *rc2;
int arg1[2] = {1,5}, arg2[2] = {6,10};
int status;
共有変数領域IDの確保
shared_mem_id=shmget(IPC_PRIVATE, 2*sizeof(int),0666);
shared_mem_ptr=shmat(shared_mem_id,0,0);
rc1 = shared_mem_ptr;
rc2 = (shared_mem_ptr+1); 共有変数領域開始アドレス
続く
24
マルチタスキング－例題プログラム
子プロセスを生成：
戻り値は子プロセスには0、
親プロセスには子プロセスID
和を部分和として二つの
プロセスで求めるプログラム
if((pid1=fork())==0){
*rc1=sum(&arg1);
exit(0);
}
子プロセスならsumを実行し
結果を共有変数へ代入
親プロセスは子プロセスIDを得る
if((pid2=fork())==0){
*rc2=sum(&arg2);
exit(0);
}
子プロセスならsumを実行し
結果を共有変数へ代入
親プロセスは子プロセスIDを得る
waitpid(pid1, status, 0);
waitpid(pid2, status, 0);
子プロセスの終了を待つ
子プロセスの終了を待つ
printf("%d %d\n", *rc1 ,*rc2);
printf("%d+..+%d=%d\n", arg1[0],arg2[1], *rc1 + *rc2);
}
共有変数を参照する
続く
25
マルチタスキング－例題プログラム
int sum(int *arg_ptr)
{
int min = *arg_ptr;
int max = *(arg_ptr+1);
int i, sum;
和を部分和として二つの
プロセスで求めるプログラム
for (i=min, sum =0; i<= max; i++)
sum += i;
return sum;
}
26
マルチタスキングによる並列処理
• プロセス間での
– 同期(セマフォ)： semop関数など
– データ授受：
msgsnd/msgrcv関数など
• SMPやマルチコアシステムでの単一プログラムの並列
処理では，次に紹介するマルチスレッドよる方法の方
が一般的．
27
マルチスレッディングによる並列処理
• スレッドライブラリを使用しスレッドコントロール
• スレッドライブラリはスレッドコントロールのためのAPIを
提供している．
28
MT－例題プログラム
#include <pthread.h>
#include <stdio.h>
extern int *sum(int *);
pthread_t th1, th2;
和を部分和として二つの
スレッドで求めるプログラム
int main()
{
int *ps1, *ps2;
int arg1[2]={1,5}, arg2[2] = {6,10};
pthread_create(&th1,NULL,(void*(*)(void*))sum,&arg1);
pthread_create(&th2,NULL,(void*(*)(void*))sum,&arg2);
pthread_join(th1, (void**)&ps1);
pthread_join(th2, (void**)&ps2);
printf("%d+..+%d=%d\n", arg1[0], arg2[1], *ps1+*ps2);
free(ps1); free(ps2);
}
続く
29
MT－例題プログラム
int *sum(int *arg_ptr)
{
int lb = *arg_ptr;
int ub = *(arg_ptr+1);
int i, sum;
int *p;
和を部分和として二つの
スレッドで求めるプログラム
for (i=lb, sum =0; i<= ub; i++) { sum += i;}
p =(int *)malloc(sizeof(int));
*p = sum;
return p;
}
30
MT－例題プログラム
和を部分和として二つの
スレッドで求めるプログラム
#include <pthread.h>
#include <stdio.h>
extern int *sum(int *); ヘッダファイルの読み込み
pthread_t th1, th2;
スレッドID変数
int main()
スレッド開始関数への引数
{
スレッド開始関数
int *ps1, *ps2;
int arg1[2]={1,5}, arg2[2] = {6,10};
二つのスレッド生成
pthread_create(&th1,NULL,(void*(*)(void*))sum,&arg1);
pthread_create(&th2,NULL,(void*(*)(void*))sum,&arg2);
pthread_join(th1, (void**)&ps1);
pthread_join(th2, (void**)&ps2);
スレッド終了状態
スレッドの終了待ち
printf("%d+..+%d=%d\n",
arg1[0], arg2[1], *ps1+*ps2);
free(ps1); free(ps2);
}
続く
31
MT－例題プログラム
int *sum(int *arg_ptr)
{
int lb = *arg_ptr;
int ub = *(arg_ptr+1);
int i, sum;
int *p;
和を部分和として二つの
スレッドで求めるプログラム
スレッドローカルな変数
for (i=lb, sum =0; i<= ub; i++) { sum += i;}
p =(int *)malloc(sizeof(int));
*p = sum;
return p;
スレッド外からもアクセス
できるように
}
pが終了ステータスとして通知される
pthread_exit(p);でもOK
32
マルチスレッディングによる並列処理
• スレッド間の同期
– 相互排除
pthread_mutex_lock(&mt)
pthread_mutex_unlock(&mt)
pthread_mutex_trylock(&mt)
mtは同期変数： pthread_mutex_t mt
– 条件同期
pthread_cond_wait(&ct, &mt)
pthread_cond_signal(&mt)
pthread_cond_broadcast(&mt)
ctは同期変数: pthread_cond_t ct
– など
33
MT－相互排除
和を部分和として二つの
スレッドで求めるプログラム
#include <pthread.h>
#include <stdio.h>
extern int *sum(int *);
pthread_t th1, th2;
pthread_mutex_t mt = PTHREAD_MUTEX_INITIALIZER;
int gsum;
または
int main()
pthread_mutex_init(&mt, NULL);
{
int *ps1, *ps2;
int arg1[2]={1,5}, arg2[2] = {6,10};
pthread_create(&th1,NULL,(void*(*)(void*))sum,&arg1);
pthread_create(&th2,NULL,(void*(*)(void*))sum,&arg2);
pthread_join(th1, (void**)&ps1);
pthread_join(th2, (void**)&ps2);
printf("%d+..+%d=%d\n", arg1[0], arg2[1], gsum);
free(ps1); free(ps2);
}
続く
34
MT－相互排除
int *sum(int *arg_ptr)
{
int lb = *arg_ptr;
int ub = *(arg_ptr+1);
int i, sum;
和を部分和として二つの
スレッドで求めるプログラム
for (i=lb, sum =0; i<= ub; i++) { sum += i;}
pthread_mutex_lock(&mt);
gsum=gsum+sum;
pthread_mutex_unlock(&mt);
return 0;
}
35
MT－条件同期
pthread_mutex_t mt = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t ct = PTHREAD_COND_INITIALIZER;
int flag;
または
pthread_cond_init(&ct, NULL);
thread 0
...
pthread_mutex_lock(&mt);
flag = 1;
pthread_mutex_unlock(&mt);
pthread_cond_signal(ct);
...
thread 1
...
pthread_mutex_lock(&mt);
while(flag == 0){
pthread_cond_wait(&ct, &mt);
}
pthread_mutex_unlock(&mt);
...
36
マルチスレッドプログラミング
• かなり玄人向けの方法
• 他の方法で並列プログラミングするとしても，スレッドの
メカニズムは理解しておくほうが良い．
• 参考書
– ｢実践マルチスレッドプログラミング｣アスキー出版局
S.Kleimanら/岩本信一訳
– 「Pスレッドプログラミング」ピアソン・エデュケーション
B.Lewisら/岩本信一訳など
37
MPI(Message-Passing Interface)
• メッセージ通信ライブラリ（のAPI仕様）
プロセス間でのデータ授受のための通信関数のライブ
ラリ（百数十） [1]．
• バージョン
1994 May MPI-1.0
・・・
2012 Sep. MPI-3.0
• 複数プロセスが協調して動作する並列実行モデル
プログラム開始時に複数プロセスが一斉に実行を開
始し，一斉に終了する（MPI-1）
例） mpirun –np 8 my_program
[1] http://www.mpi-forum.org/
MPI Forum
38
MPI(Message-Passing Interface)
• メッセージは次の三つの組で指定される
– 通信範囲を示すプロセスグループ（コミュニケータ）
– プロセスグループ中でのプロセスID（ランク）
– 通信の識別子（タグ）
39
MPIー例題プログラム
#include “mpi.h”
int main(int argc, char **argv)
{ int myrank, error, buffer
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD,
if (myrank == 0) {
error = MPI_Send(&buffer,
1, 1234,
} else if (myrank == 1) {
error = MPI_Recv(&buffer,
0, 1234,
}
MPI_Finalize();
}
プロセス間でデータを
授受するプログラム
&myrank);
1, MPI_INT,
MPI_COMM_WORLD);
1, MPI_INT,
MPI_COMM_WORLD, &status);
40
MPIー例題プログラム
MPIプログラムの全体の枠組み
#include “mpi.h”
int main(int argc, char **argv)
{ int myrank, error,
buffer
ヘッダファイルの読み込み
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
MPIライブラリの初期化
if (myrank == 0) {
error = MPI_Send(&buffer, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
} else if (myrank == 1) {
error = MPI_Recv(&buffer, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
}
MPI_Finalize();
}
MPIライブラリの終了処理
41
MPIー例題プログラム
メッセージの送受信
送受信で指定する情報
#include “mpi.h”
int main(int argc, char **argv)
{ int myrank, error, buffer
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
バッファの指定：先頭アドレス,個数,型
if (myrank == 0) {
error = MPI_Send(&buffer, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
} else if (myrank == 1) {
相手と文脈の指定：ランク,タグ,コミュニケータ
error = MPI_Recv(&buffer, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
}
MPI_Finalize();
}
42
MPIー例題プログラム
メッセージの送受信
送受信で指定する情報
#include “mpi.h”
int main(int argc, char **argv)
{ int myrank, error, buffer
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank == 0) {
error = MPI_Send(&buffer, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
} else if (myrank == バッファの指定：先頭アドレス,個数,型
1) {
error = MPI_Recv(&buffer, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
}
相手と文脈の指定：ランク,タグ,コミュニケータ
MPI_Finalize();
受信状態
}
受信メッセージのランクやタグ(ワイルドカード受信の際に利用)など 43
MPIー例題プログラム
プロセスの識別
#include “mpi.h”
プログラム中の各プロセスにラ
int main(int argc, char **argv)
ンクが付加されそれで区別する
{ int myrank, error, buffer
MPI_Status status;
自プロセスのランクの取得
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank == 0) {
自分のランクが0の場合
error = MPI_Send(&buffer, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
} else if (myrank == 1) {
自分のランクが1の場合
error = MPI_Recv(&buffer, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
}
MPI_Finalize();
}
44
MPIー双方向通信例題プログラム
• 双方向送受信をしたい．次のコードは動作するか？
if (myrank == 0) {
MPI_Send(&sb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
MPI_Recv(&rb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD, &status);
} else if (myrank == 1) {
MPI_Send(&sb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD);
MPI_Recv(&rb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
}
ブロッキングsend/receiveのためデッドロック！
45
MPIー双方向通信例題プログラム
• 双方向送受信をしたい．次のコードは動作するか？
if (myrank == 0) {
MPI_Recv(&rb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD, &status);
MPI_Send(&sb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
} else if (myrank == 1) {
MPI_Recv(&rb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
MPI_Send(&sb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD);
}
send/receiveの順序を入れ替えてもだめ
46
MPIー双方向通信例題プログラム
• 双方向送受信をしたい．次のコードは動作するか？
if (myrank == 0) {
MPI_Send(&sb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD);
MPI_Recv(&rb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD, &status);
} else if (myrank == 1) {
MPI_Recv(&rb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD, &status);
MPI_Send(&sb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD);
}
双方の順序を逆にする必要
47
MPIー双方向通信例題プログラム
ノンブロッキングのIsendとWait
if (myrank == 0) {
MPI_Isend(&sb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD,
MPI_Recv(&rb, 1, MPI_INT,
1, 1234, MPI_COMM_WORLD,
MPI_Wait(&id, &wstatus);
} else if (myrank == 1) {
MPI_Isend(&sb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD,
MPI_Recv(&rb, 1, MPI_INT,
0, 1234, MPI_COMM_WORLD,
MPI_Wait(&id, &wstatus);
}
&id);
&rstatus);
&id);
&status);
Isendではブロッキングせずにreceiveに移行
48
MPIー双方向通信例題プログラム
双方向送受信を指示する関数
if (myrank == 0) {
MPI_Sendrecv(&sb, 1, MPI_INT, 1, 1234,
&rb, 1, MPI_INT, 1, 1234,
MPI_COMM_WORLD, &status);
} else if (myrank == 1) {
MPI_Sendrecv(&sb, 1, MPI_INT, 0, 1234,
&rb, 1, MPI_INT, 0, 1234,
MPI_COMM_WORLD, &status);
}
49
MPIー集団通信関数
• 典型的な通信パターンに対応する集団通信関数
– 交換
MPI_Sendrecv
1
2
12
12
– ブロードキャスト
MPI_Bcast
123
123 123
– gather
MPI_Gather
1
2
123 123
3
4
1234
50
MPIー集団通信関数
• 典型的な通信パターンに対応する集団通信関数
– scatter
MPI_Scatter
1234
1
– all gather
MPI_Allgather
1
2
3
2
3
4
4
1234 1234 1234 1234
– all to all
MPI_Alltoall
1234
abcd ABCD
@!%\
1aA@ 2bB! 3cC% 4dD\
51
MPIー集団通信関数
• 集団通信関数の利点
send/receiveの組み合わせより
– プログラムの意図がわかりやすい
– ハードウェアで集団通信の機能がある場合，それが
利用されたMPI実装であれば通信効率が良い
• 同期関数としてはバリアが用意されている
– MPI_Barrier
52
MPIーまとめ
• 分散メモリ向型並列コンピュータ向きの並列プログラ
ムAPI
• 実装は，MPICH2[3]，Open MPI[2] が有名
• 参考書
– MPI並列プログラミング： P.Pacheco著，秋葉博訳
– 実践MPI-2： W. Groppほか著畑崎隆雄訳
• 参考サイト
[1] http://www.mpi-forum.org/ MPI Forum
[2] http://www.open-mpi.org/
[3] http://www.mcs.anl.gov/mpi/
[4] http://phase.hpcc.jp/phase/mpi-j/ml/
53
OpenMP
• 共有メモリ型並列計算機上での並列プログラミングの
ために，
コンパイラ指示文，実行時ライブラリ，環境変数
でベース言語（C/C++, Fortran）を拡張する[1]．
• バージョン
1997 Oct. Fortran ver.1.0
1998 Oct. C/C++ ver.1.0
・・・
2011 July ver.3.1
2013 July ver. 4.0
• 並列実行（同期）はコンパイラ指示文として記述
• ループなどに対しては自動的な負荷分散が可能
[1] http://www.openmp.org/
OpenMP ARB
54
OpenMP
• コンパイラ指示文
– Fortranではdirective
!$OMP...
– Cではpragma
#pragma omp ...
• 指示文を無視すれば逐次実行可能
– インクリメンタルに並列化が可能
– プログラム開発が容易
– 逐次版と並列版が同じソースで管理できる
55
OpenMPー実行モデル
• マルチスレッド上でのfork-joinモデル
• Parallel Region
複数のスレッドで重複して実行する部分を指定する
#pragma omp parallel
{
マスタスレッド
sub();
fork
}
スレーブスレッド
マスタスレッド
call sub()
call sub()
call sub()
join
マスタスレッド
call sub()
56
OpenMPーParallel Region
和計算のプログラム
#pragma omp parallel
スレッドプライベート変数
{
int chunk,start,end,psum;
chunk = 100/omp_get_num_threads();
start = chunk*omp_get_thread_num();
end = start + chunk;
psum = 0;
for(i=start; i < end; i++) psum += a[i];
#pragma omp atomic
sum += psum;
}
57
OpenMPーParallel Region
和計算のプログラム
#pragma omp parallel
{
int chunk,start,end,psum;
スレッド数を得る関数
chunk = 100/omp_get_num_threads();
start = chunk*omp_get_thread_num();
end = start + chunk;
スレッドIDを得る関数
psum = 0;
for(i=start; i < end; i++) psum += a[i];
#pragma omp atomic
k = ceil(n/np)
lb= k*(p-1)+1
sum += psum;
ub= min(k*p,n)
}
do i=lb,ub
ループボディ
enddo
58
OpenMPーParallel Region
和計算のプログラム
#pragma omp parallel
{
int chunk,start,end,psum;
chunk = ceil((float)100/omp_get_num_threads());
start = chunk*omp_get_thread_num();
end = start + chunk <10 ? start + chunk : 10;
psum = 0;
for(i=start; i < end; i++) psum += a[i];
#pragma omp atomic
k = ceil(n/np)
lb= k*(p-1)+1
sum += psum;
ub= min(k*p,n)
}
do i=lb,ub
ループボディ
enddo
59
OpenMPー変数の共有
int i;
int j;
#pragma omp parallel
{
int k;
スレッド間シェアード変数
i = ..
j = ..
k = ..
}
スレッドプライベート変数
60
OpenMPー変数の共有
int i;
int j;
#pragma omp parallel private(j)
{
int k;
スレッド間シェアード変数
i = ..
j = ..
k = ..
}
スレッドプライベート変数
61
OpenMPーWork sharing
• Parallel region内で複数のスレッドで分担して実行す
る部分を指定する
#pragma omp
{
#pragma omp
{ sub1();
#pragma omp
{ sub2();
}
sections
section
}
section
}
• sectionsの最後でバリア同期
62
OpenMPーWork sharing
• Parallel region内で複数のスレッドで分担して実行す
る部分を指定する
• 並列ループ
#pragma omp for
for ( ; ; ) { }
• スケジューリング：
スタティック，ダイナミック（chunk, guided）を指定可
schedule(static,チャンクサイズ)
schedule(dynamic,チャンクサイズ)
schedule(guided,チャンクサイズ)
schedule(runtime)
• forの最後でバリア同期
63
OpenMPーWork sharing
• 並列ループ
ループの制御変数は自動的に
スレッドプライベート変数に
#pragma omp for
for (i=0; i<n; i++)
a[i]=b[i]+c[i];
スレッドプライベート変数の明示が必要
#pragma omp for private(t)
for (i=0; i<n; i++){
t=b[i]+c[i];
a[i]=t/2;
}
64
OpenMPーWork sharing
• 並列ループ
ループの制御変数は自動的に
スレッドプライベート変数に
#pragma omp for
for (i=0; i<n; i++)
a[i]=b[i]+c[i];
スレッドプライベート変数の明示が必要
#pragma omp for private(j)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
a[i][j]=b[i][j]+c[i][j];
65
OpenMPー同期
• バリア同期
チーム内のスレッドがバリアに到達するまで待つ
#pragma omp barrier
• クリティカルセクション
#pragma omp critical
{
}
• アトミック命令
メモリの更新をアトミックに行う
#pragma omp atomic
文(x++, x+=...,など)
• マスタスレッドのみ実行
他のスレッドは素通り
#pragma omp master
{
}
66
OpenMPー同期
• 単一のスレッドのみ実行
他のスレッドはバリア同期で待っている
#pragma omp single
{
}
• paralle for のボディの一部を逐次と同順で実行
#pragma omp for ordered
...
#pragma omp ordered
{
}
• メモリの一貫性保障
#pragma omp flush(変数名)
• メモリコンシステンシモデルはweak consistency
67
OpenMPー実行時ライブラリ
• （逐次内で）次のparallel regionでのスレッド数を指定
omp_set_num_threads(int)
• parallel region内で動作中のスレッド数を返す
omp_get_num_threads()
• 利用できるスレッド数を返す
omp_get_max_threads()
• スレッドidを返す
omp_get_thread_num()
• 利用できるプロセッサ数を返す
omp_get_num_procs()
• lock関数
omp_set_lock(omp_lock_t)
omp_unset_lock(omp_lock_t)
68
OpenMPー環境変数
• parallel regionでのスレッド数を指定
OMP_NUM_THREADS
• 並列ループのスケジューリング方法を指定
OMP_SCHEDULE
69
OpenMP
• 共有メモリ型並列コンピュータ向きの並列実行モデルと
API
• インクリメンタルな並列化をサポート
• 参考書
– OpenMP入門北山洋幸著
– C/C++ﾌﾟﾛｸﾞﾗﾏｰのためのOpenMP並列ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ
（第２版）菅原清文著
• 参考サイト
[1] http://www.openmp.org/
• gcc（ver 4.2～）でもお手軽に使えるのでお試しを
70
HPF(High Performance Fortran)
• 分散メモリ並列計算機での科学技術計算を対象
• 分散メモリ上へのデータ分割配置に主眼を置く．
– データアクセスの局所性を高める．
– プロセッサ間通信を減らす．
• データ分割をプログラマが明示的に指示する．
• プログラムのSPMD化や通信コードの挿入はコンパイ
ラが行う．
SPMD(Single Program Multiple Data Stream) :
各プロセッサは同一プログラムを実行するが，プロセッ
サIDなどに基づき異なるコード（異なるイタレーションや
異なるプログラム部分など）を実行するモデル．
71
HPFーデータの分割配置
• 分散メモリ並列計算機でのデータの分散配置
例）配列変数 X(100)
– ブロック分割
プロセッサ1 X(1)～X(25)
プロセッサ2 X(26)～X(50)
プロセッサ3 X(51)～X(75)
プロセッサ4 X(76)～X(100)
– サイクリック分割
プロセッサ1 X(1),X(5)...X(97)
プロセッサ2 X(2),X(6)...X(98)
プロセッサ3 X(3),X(7)...X(99)
プロセッサ4 X(4),X(8)...X(100)
• データの分割方法の違いによって並列処理の効率に
大きな影響が現れる．
72
HPFーデータの分割配置
PROGRAM EXAMPLE1
PARAMETER(N=100)
REAL X(N), Y(N) 抽象プロセッサ配列宣言
!HPF$ PROCESSORS P(4)
!HPF$ DISTRIBUTE X(BLOCK) ONTO P
!HPF$ DISTRIBUTE Y(BLOCK) ONTO P
...
抽象プロセッサへの
DO I=2,N-1
データレイアウト指定
Y(I) = X(I-1)+X(I)+X(I+1)
ENDDO
...
プロセッサ1
X(1:25)
Y(1:25)
プロセッサ2
X(26:50)
Y(26:50)
プロセッサ3
X(51:75)
Y(51:75)
プロセッサ4
X(76:100)
Y(76:100)
73
HPFー計算処理のプロセッサへの割り当て
• owner computes rule：
変数Xへ代入を行う代入文の計算は，その変数がロー
カルメモリに配置されているプロセッサ(Xのオーナー)
が担当するという計算モデル．
• 先の例示プログラムでは：
DO I=2,N-1
Y(I) = X(I-1)+X(I)+X(I+1)
END DO
プロセッサ1 が I=2,25 を実行
プロセッサ2 が I=26,50 を実行
プロセッサ3 が I=51,75 を実行
プロセッサ4 が I=76,99 を実行
74
HPFーSPMDコード
• コンパイラがIF文からなる実行ガードを挿入しSPMDコ
ードを生成．
各プロセッサは同一プログラムを実行しながら，実際に
は異なる処理を行う．
• 先の例示プログラムでは，コンパイラが以下のようなコ
ードを生成する．
DO I=2,N-1
IF( Y(I)のオーナー ) THEN
Y(I) = X(I-1)+X(I)+X(I+1)
END DO
75
HPFーデータの分割配置（多次元配列）
PROGRAM EXAMPLE2
PARAMETER(N=100)
抽象プロセッサ配列宣言
REAL Z(N,N)
!HPF$ PROCESSORS P(4)
!HPF$ DISTRIBUTE Z(BLOCK,*) ONTO P
抽象プロセッサへの
データレイアウト指定
配列変数Z
プロセッサ1
プロセッサ2
プロセッサ3
プロセッサ4
76
HPFーデータの分割配置（多次元配列）
!HPF$ PROCESSORS P(4)
(BLOCK,*)
(*,BLOCK)
(SYCLIC,*) (*,SYCLIC)
!HPF$ PROCESSORS P(2,2)
(BLOCK,BLOCK)
(SYCLIC,BLOCK)
77
HPFーデータの分割配置（相互関係)
!HPF$ ALIGN A(I) WITH B(I)
A
B
!HPF$ ALIGN A(I) WITH B(I+1)
A
B
!HPF$ ALIGN A(I,J) WITH B(J,I) 転置
!HPF$ ALIGN A(I,*) WITH C(I)
縮退
!HPF$ ALIGN C(I) WITH B(I,*)
複製
78
HPFープロセッサ間通信
• 先のプログラムで必要な通信
DO I=2,N-1
Y(I)=X(I-1)+X(I)+X(I+1)
END DO
– プロセッサ1が，
Y(25) = X(24)+X(25)+X(26) プロセッサ2から
を実行する際にプロセッサ間でデータの通信が必要
データ配置プロセッサ1 X(1)～X(25)
プロセッサ2 X(26)～X(50)
プロセッサ3 X(51)～X(75)
プロセッサ4 X(76)～X(100)
– プロセッサ2,3,4でも同様
プロセッサ2が
Y(26)
Y(50)
プロセッサ3が
Y(51)
Y(75)
プロセッサ4が
Y(76)
合計6回の通信が必要
=
=
=
=
=
X(25)+X(26)+X(27)
X(49)+X(50)+X(51)
X(50)+X(51)+X(52)
X(74)+X(75)+X(76)
X(75)+X(76)+X(77)
79
HPFープロセッサ間通信
DO I=2,N-1
Y(I)=X(I-1)+X(I)+X(I+1)
END DO
• 例示プログラムで，データ分割配置がサイクリックの場
合どのような通信が必要か?
プロセッサ1
プロセッサ2
プロセッサ3
プロセッサ4
X(1),X(5)...X(97)
X(2),X(6)...X(98)
X(3),X(7)...X(99)
X(4),X(8)...X(100)
非常に多くの通信が必要となる!!!
全てのプロセッサが一つの代入文で2回づつ(98X2回!)
Y(I) = X(I-1)+X(I)+X(I+1)
• データの分割配置の形態によって通信回数が大きく異
なる．
→ 実行効率に多大な影響
80
HPFープロセッサ間での計算負荷の均等化
• 負荷分散の面からはサイクリック分割の方が良い場合
DO I = 1,100
DO J = I,100
X(I,J) = X(I,J)/2
ENDDO
ENDDO
J
J
I
I
ブロック分割
サイクリック分割
81
HPF
• データの分割配置はプログラマの知的作業とし，残り
の部分（SPMD化など）をコンパイラに任せる．
• 科学技術計算分野ではそれなりの普及の兆し．
• 参考となるサイト
– http://www.hpfpc.org/ HPF推進協議会
→XcalableMP
http://www.xcalablemp.org/
82
並列プログラミング
• 現在では完全な自動並列化は困難
• ハードウェアアーキテクチャの違いを意識せずにプ
ログラミングできる環境が望まれる
– 共有メモリマシン上でのMPI
– 分散メモリマシン上でのOpenMP
• 高性能を追及するためには，アーキテクチャを理解
した上でのプログラミング，並列アルゴリズムの考
案が必要
• ヘテロジニアスな環境への対応
– マルチコアCPU，マルチCPUノード，GPU搭載
83

Download Report