並列処理論2

1

2

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

3

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

並列化は行われていない

4

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

人手による

並列化が必要

5

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

並列型アルゴリズムが必要

アルゴリズムの並列性

以外の並列化は必要

6

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

並列化のすべてを

コンパイラが行う

並列化は行われていない

7

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

残された並列化を

コンパイラが行う

並列化が行われている

8

並列処理プログラミング

アルゴリズム

プログラミング

言語

並列化

コンパイラ

（一部）並列化が行われている

並列化のための書換え

9

並列処理プログラミングモデル

• プログラミングモデル（ソフトウェア的な通信モデル）

の観点からは次の二つに分類される．

– 共有変数型（単一メモリ空間型）

– メッセージ転送型

10

共有変数型

• 異なるプロセッサ上のプロセス間で変数を共有

共有変数を介してプロセス間通信

→ ポインタ変数などの扱いが楽

• 共有メモリ型や分散共有メモリ型並列計算機上で用

いられることが多い

物理的にメモリを共有する必要は必ずしも無い

→ OSサポートなど

• 分散メモリ型並列計算機での実装では性能低下は大

P0

P1

共有変数

代入

_参照

11

メッセージ転送型

• 異なるプロセッサ上のプロセス間での通信手段

→メッセージ転送のみ

変数のパッキングなどが必要

• 送信側と受信側のプロセッサが協調してデータ転送

• 分散メモリ型並列計算機上で用いられることが多い

共有メモリ型並列計算機でも実現可能

→ 共有メモリ上に通信チャネルを用意する

P0

P1

send

receive

12

• ハードウェア構成とプログラミングモデルを無関係に

したい．

– ハードのメモリ制御（キャッシュ制御を含む）機構や

通信制御機構

– 通信ライブラリ

– ソフトウェア分散共有メモリ

– コンパイラ

• パフォーマンス向上にはH/W構成に適したプログラミ

ングが必要．

プログラミングモデルとH/Wの構成

-PGAS: Partitioned Global Address Space モデル

13

並列処理を可能とするOS環境

• 並列コンピュータ上での並列処理を実現するOS機能

• プロセス間並列（マルチタスキング）

– 単一PEでの複数プロセスの並行処理の発展形

– プログラム中のタスク群を複数のプロセスに割り当

て，それらを複数プロセッサで実行する．

• スレッド間並列（マルチスレッディング）

– ひとつのプロセスをさらにスレッドに分割しそれらを

複数PEで実行する．

– プログラム中のタスク群はスレッド群に割り当て，そ

れらを複数PEで実行する．

14

プロセス間並列

• 例） １PEでの複数プロセスの並行処理

15

• 例） 1PEでの複数プロセスの並行処理

• 例） ２PEでの複数プロセスの並列/並行処理

プロセス間並列

16

プロセス間並列

• プロセスの生成・終了・待合せのための機能

– fork(), exit(), wait()などの関数

• プロセス間データ授受（IPC）のための機能

– データ転送

「パイプ」，「ソケット」，「メッセージキュー」など

– データ共有

共有メモリ領域：

複数プロセスのメモリ空間の一部をオーバーラップ

– 同期

「シグナル」，「セマフォ」など

• 各種操作のコストが大きい．

– プロセス生成，コンテキストスイッチ，同期，通信

17

スレッド間並列（マルチスレッド:MT）

• スレッド：

– 同一プロセス内で複数制御フロー（スレッド）を用意．

– 個別の制御フローを個別のスレッドに対応させる．

– スレッドをPEへのスケジュール単位とする．

– 同一プロセスのスレッドはアドレス空間を共有．

→ メモリ管理の負荷が小さい

→ 通信・同期のコストが小さい

– スレッド固有情報（プログラムカウンタ，スタックポイン

タ，レジスタセット）がプロセス情報（アドレス空間，ユ

ーザID，etc.）より少ない．

→ スレッド生成や各種操作のコストが小さい．

18

スレッド間並列（マルチスレッド:MT）

• スレッド：

19

並列プログラミング環境

• 逐次言語 + マルチタスキング

• 逐次言語 + マルチスレッド

• 逐次言語 + メッセージ通信ライブラリ

例)

MPI (Message Passing Interface)

• 逐次言語 + コンパイラディレクティブ(+α)

例)

OpenMP，OpenACC

• 並列言語

例)

HPF (High Performance Fortran)

20

• 参考書/例題プログラムの出典

「はじめての並列プログラミング｣

21

• forkシステムコールにより複数プロセスを立ち上げての

並列処理(並行処理)

• (親)プロセスがfork関数を呼び出すと，

– 子プロセスが生成される．

子プロセス環境は親プロセスの環境が複製される．

– 親プロセスと子プロセスはfork関数呼出しから戻った

ところからそれぞれ実行を再開．

– fork関数の戻り値は，子プロセスでは0となり，親プロ

セスでは子プロセスのプロセスIDとなる．

• 子プロセスでは，処理終了後exit()システムコールなど

でプロセスを終了する．

• 親プロセス，子プロセス間では共有変数などを用いて

データの授受を行う．

マルチタスキングによる並列処理

22

マルチタスキング－例題プログラム

{

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);

和を部分和として二つの

プロセスで求めるプログラム

続く

23

マルチタスキング－例題プログラム

和を部分和として二つの

プロセスで求めるプログラム

続く

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; }

24

マルチタスキング－例題プログラム

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);

和を部分和として二つの

プロセスで求めるプログラム

続く

ヘッダファイルの読み込み

プロセスID変数

共有変数管理のための変数

共有変数領域IDの確保

共有変数へのポインタ変数

共有変数領域開始アドレス

25

マルチタスキング－例題プログラム

和を部分和として二つの

プロセスで求めるプログラム

続く

子プロセスならsumを実行し

結果を共有変数へ代入

親プロセスは子プロセスIDを得る

子プロセスの終了を待つ

子プロセスの終了を待つ

子プロセスを生成：

戻り値は子プロセスには0、

親プロセスには子プロセスID

子プロセスならsumを実行し

結果を共有変数へ代入

親プロセスは子プロセスIDを得る

共有変数を参照する

26

マルチタスキング－例題プログラム

{

int min = *arg_ptr;

int max = *(arg_ptr+1); int i, sum;

for (i=min, sum =0; i<= max; i++) sum += i;

return sum; }

和を部分和として二つの

27

• プロセス間での

– 同期(セマフォ)： semop関数など

– データ授受：

msgsnd/msgrcv関数など

28

• スレッドライブラリを使用しスレッドコントロール

• スレッドライブラリはスレッドコントロールのためのAPIを

提供している．

29

MT－例題プログラム

#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);

}

和を部分和として二つの

スレッドで求めるプログラム

30

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; }

MT－例題プログラム

_{和を部分和として二つの}

スレッドで求めるプログラム

31

MT－例題プログラム

#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); }

和を部分和として二つの

スレッドで求めるプログラム

続く

ヘッダファイルの読み込み

二つのスレッド生成

スレッド開始関数への引数

スレッド開始関数

スレッドID変数

スレッドの終了待ち

スレッド終了状態

32

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; }

MT－例題プログラム

_{和を部分和として二つの}

スレッドで求めるプログラム

スレッドローカルな変数

pが終了ステータスとして通知される

でもOK

スレッド外からもアクセス

できるように

33

• スレッド間の同期

– 相互排除

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

– など

マルチスレッディングによる並列処理

34

MT－相互排除

extern int *sum(int *); pthread_t th1, th2; pthread_mutex_t mt = PTHREAD_MUTEX_INITIALIZER; int gsum; 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], gsum); free(ps1); free(ps2); }

和を部分和として二つの

スレッドで求めるプログラム

続く

35

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; }

MT－相互排除

_{和を部分和として二つの}

スレッドで求めるプログラム

36

• メッセージ通信ライブラリ（のAPI

仕様）

プロセス間でのデータ授受のための通信関数のライブ

ラリ（百数十）

．

• バージョン

1994 May MPI 1.0

・・・

2015 June MPI 3.1

MPI 4.0

• 複数プロセスが協調して動作する並列実行モデル

プログラム開始時に複数プロセスが一斉に実行を開

始し，一斉に終了する（MPI-1）

例） mpirun

–np 8 my_program

[1] http://www.mpi-forum.org/ MPI Forum

37

• メッセージは次の三つの組で指定される

– 通信範囲を示すプロセスグループ（コミュニケータ）

– プロセスグループ中でのプロセスID（ランク）

– 通信の識別子（タグ）

MPI(Message-Passing Interface)

38

MPIー例題プログラム

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(); }

プロセス間でデータを

授受するプログラム

39

MPIー例題プログラム

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(); }

MPIプログラムの全体の枠組み

ヘッダファイルの読み込み

MPIライブラリの初期化

MPIライブラリの終了処理

40

MPIー例題プログラム

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(); }

バッファの指定：先頭アドレス,個数,型

メッセージの送受信

送受信で指定する情報

相手と文脈の指定：ランク,タグ,コミュニケータ

41

MPIー例題プログラム

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ー例題プログラム

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(); }

自プロセスのランクの取得

自分のランクが0の場合

プロセスの識別

プログラム中の各プロセスにラ

ンクが付加されそれで区別する

自分のランクが1の場合

43

MPIー双方向通信例題プログラム

• 双方向送受信をしたい．次のコードは動作するか？

ブロッキングsend/receiveのためデッドロック！

44

MPIー双方向通信例題プログラム

• 双方向送受信をしたい．次のコードは動作するか？

send/receiveの順序を入れ替えてもだめ

45

MPIー双方向通信例題プログラム

• 双方向送受信をしたい．次のコードは動作するか？

双方の順序を逆にする必要

46

MPIー双方向通信例題プログラム

ノンブロッキングのIsendとWait

MPI_Wait(&id, &wstatus); } else if (myrank == 1) {

MPI_Isend(&sb, 1, MPI_INT,

0, 1234, MPI_COMM_WORLD, &id); MPI_Recv(&rb, 1, MPI_INT,

0, 1234, MPI_COMM_WORLD, &status);

MPI_Wait(&id, &wstatus); }

47

MPIー双方向通信例題プログラム

双方向送受信を指示する関数

48

• 典型的な通信パターンに対応する集団通信関数

– 交換

MPI_Sendrecv

– ブロードキャスト

MPI_Bcast

– gather

MPI_Gather

MPIー集団通信関数

1 2

1 2

2

1

123

123

123

123

123

1234

4

3

2

1

49

• 典型的な通信パターンに対応する集団通信関数

– scatter

MPI_Scatter

– all gather

MPI_Allgather

– all to all

MPI_Alltoall

MPIー集団通信関数

4dD¥

3cC%

2bB!

1aA@

@!%¥

ABCD

abcd

1234

4

3

2

1

1234

1234

1234

1234

1234

4

3

2

1

50

• 集団通信関数の利点

send/receiveの組み合わせより

– プログラムの意図が明確になる

– ハードウェアで集団通信の機能がある場合，それを

利用しMPI実装であれば通信効率が良い

• バリア同期関数

– MPI_Barrier

MPIー集団通信関数

51

• 分散メモリ型並列計算機向きの並列プログラムAPI

• MPICH2

，Open MPI

の実装が有名

• 参考書

– 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/

52

• 共有メモリ型並列計算機上での並列プログラミングの

ために，

コンパイラ指示文，実行時ライブラリ，環境変数

でベース言語（C/C++, Fortran）を拡張する．

• バージョン

1997 Oct. Fortran ver.1.0

1998 Oct. C/C++ ver.1.0

・・・

2013 July ver. 4.0

2015 Nov. ver. 4.5

• 並列実行（同期）は

コンパイラ指示文

として記述

• ループなどに対しては自動的な負荷分散が可能

OpenMP

53

• コンパイラ指示文

– Fortranではdirective

!$OMP...

– Cではpragma

#pragma omp ...

• 指示文を無視すれば逐次実行可能

– インクリメンタルに並列化が可能

– プログラム開発が容易

– 逐次版と並列版が同じソースで管理できる

OpenMP

54

• マルチスレッド上でのfork-joinモデル

• Parallel Region

複数のスレッドで重複して実行する部分を指定する

OpenMPー実行モデル

call sub()

call sub()

call sub()

call sub()

#pragma omp parallel

{

sub();

}

fork

join

マスタスレッド

マスタスレッド

55

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;

}

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;

}

スレッド数を得る関数

和計算のプログラム

スレッドIDを得る関数

57

OpenMPーParallel Region

#pragma omp parallel

{

int chunk,start,end,psum,i;

chunk = ceil((float)100/omp_get_num_threads());

start = chunk*omp_get_thread_num();

end = start + chunk <100 ? start + chunk : 100;

psum = 0;

for(i=start; i < end; i++) psum += a[i];

#pragma omp atomic

sum += psum;

}

和計算のプログラム

58

OpenMPー変数の共有

int i;

int j;

#pragma omp parallel

{

int k;

i = ..

j = ..

k = ..

}

スレッドプライベート変数

スレッド間シェアード変数

スレッド間シェアード変数

59

OpenMPー変数の共有

int i;

int j;

#pragma omp parallel

private(j)

{

int k;

i = ..

j = ..

k = ..

}

スレッドプライベート変数

スレッド間シェアード変数

スレッドプライベート変数

60

• Parallel region内で複数のスレッドで分担して実行す

る部分を指定する

• sectionsの最後でバリア同期

OpenMPーWork sharing

#pragma omp sections

{

#pragma omp section

{ sub1(); }

#pragma omp section

{ sub2(); }

61

• Parallel region内で複数のスレッドで分担して実行す

る部分を指定する

• 並列ループ

• スケジューリング：

スタティック，ダイナミック（chunk, guided）を指定可

schedule(static,

)

schedule(dynamic,

)

schedule(guided,

)

schedule(runtime)

• forの最後でバリア同期

OpenMPーWork sharing

#pragma omp for

for ( ; ; ) { }

62

ループの制御変数は自動的に

スレッドプライベート変数に

• 並列ループ

OpenMPーWork sharing

#pragma omp for

for (i=0; i<n; i++)

a[i]=b[i]+c[i];

スレッドプライベート変数の明示が必要

private(t)

#pragma omp for

for (i=0; i<n; i++){

t=b[i]+c[i];

a[i]=t/2;

}

63

• 並列ループ

OpenMPーWork sharing

#pragma omp for

for (i=0; i<n; i++)

for (j=0; j<n; j++)

a[i][j]=b[i][j]+c[i][j];

スレッドプライベート変数の明示が必要

private(j)

ループの制御変数は自動的に

スレッドプライベート変数に

#pragma omp for

for (i=0; i<n; i++)

a[i]=b[i]+c[i];

64

• バリア同期

チーム内のスレッドがバリアに到達するまで待つ

#pragma omp barrier

• クリティカルセクション

#pragma omp critical

{ }

• アトミック命令

メモリの更新をアトミックに行う

#pragma omp atomic

文(x++, x+=...,など)

• マスタスレッドのみ実行

他のスレッドは素通り

#pragma omp master

{ }

65

• 単一のスレッドのみ実行

他のスレッドはバリア同期で待っている

#pragma omp single

{ }

• paralle for のボディの一部を逐次と同順で実行

#pragma omp for ordered

...

#pragma omp ordered

{ }

• メモリの一貫性保障

#pragma omp flush(変数名)

• メモリコンシステンシモデルはweak consistency

66

• （逐次内で）次の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)

OpenMPー実行時ライブラリ

67

• parallel regionでのスレッド数を指定

OMP_NUM_THREADS

• 並列ループのスケジューリング方法を指定

OMP_SCHEDULE

OpenMPー環境変数

68

• 共有メモリ型並列計算機向きの並列実行モデルとAPI

• インクリメンタルな並列化をサポート

• 参考書

– OpenMP入門 北山洋幸 著

– C/C++ﾌﾟﾛｸﾞﾗﾏｰのためのOpenMP並列ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ

（第２版）菅原清文 著

– 並列ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ入門: ｻﾝﾌﾟﾙﾌﾟﾛｸﾞﾗﾑで学ぶOpenMP

とOpenACC 片桐孝洋 著

• gcc（ver. 4.2～）でもサポート

• http://www.openmp.org/

OpenMP

69

• 主にアクセラレータ（例：GPU) の並列プログラミングの

ために，

コンパイラ指示文，実行時ライブラリ，環境変数

でベース言語(C/C++,Fortran)を拡張する．

• バージョン

(原型：PGI Accelerator Programming Model)

2011 Nov. ver.1.0

・・・

2015 Oct. ver. 2.5

2017 Nov. ver. 2.6

• 並列実行（同期）は

コンパイラ指示文

として記述

• ループなどに対しては自動的な負荷分散が可能

OpenACC

70

• OpenMPと同じアプローチ

– コンパイラ指示文

– 指示文を無視すれば逐次実行可能

• GPU等のアクセラレータ特有の性質に対応

– 並列ループをオフロード（アクセラレータに任す）

– CPUメモリとGPUメモリ間でのデータ転送

OpenACC

CPU

GPU

71

• オフロードしたい並列ループの指定

OpenACC

while(err > s) {

for (i=0; i<n; i++){

t[i]= ・・・a[i]・・・;

}

for (i=0:, i<n; i++){

a[i]= ・・・t[i]・・・；

}

}

#pragma acc kernels

#pragma acc kernels

GPU用コードの生成

データ転送コードの生成

CPU->GPU: a[]

GPU->CPU: t[]

GPU用コードの生成

データ転送コードの生成

CPU->GPU: t[]

GPU->CPU: a[]

72

• 明示的なデータ転送指定

OpenACC

while(err > s) {

for (i=0; i<n; i++){

t[i]= ・・・a[i]・・・;

}

for (i=0:, i<n; i++){

a[i]= ・・・t[i]・・・；

}

}

#pragma acc kernels

#pragma acc kernels

#pragma acc data copy(a), create(t)

データ転送コードの生成

CPU->GPU: a[] while前

GPU->CPU: a[] while後

GPU内に配置する

73

• アクセラレータ用の並列実行モデルとAPI

• CUDA，OpenCLといった低レベルでのGPUプログラミ

ングが不要

• プログラムのポータビリティの向上

• gcc（ver. 5.1～）でもサポート

• http://www.openacc.org/

OpenACC

74

• 分散メモリ並列計算機

での科学技術計算を対象

• 分散メモリ上へのデータ分割配置に主眼を置く．

– データアクセスの局所性を高める．

– プロセッサ間通信を減らす．

• データ分割をプログラマが明示的に指示する．

• プログラムのSPMD化や通信コードの挿入はコンパイ

ラが行う．

SPMD

(Single Program Multiple Data Stream) :

各プロセッサは同一プログラムを実行するが，プロセッ

サIDなどに基づき異なるコード（異なるイタレーションや

異なるプログラム部分など）を実行するモデル．

75

• 分散メモリ並列計算機でのデータの分散配置

例）配列変数 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)

• データの分割方法の違いによって並列処理の効率に

大きな影響が現れる．

HPFーデータの分割配置

76

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

...

HPFーデータの分割配置

77

• 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 を実行

HPFー計算処理のプロセッサへの割り当て

78

• コンパイラがIF文からなる実行ガードを挿入しSPMDコ

ードを生成．

各プロセッサは同一プログラムを実行しながら，実際に

は異なる処理を行う．

• 先の例示プログラムでは，コンパイラが以下のようなコ

ードを生成する．

DO I=2,N-1

IF( Y(I)のオーナー ) THEN

Y(I) = X(I-1)+X(I)+X(I+1)

END DO

79

PROGRAM EXAMPLE2

PARAMETER(N=100)

REAL Z(N,N)

!HPF$ PROCESSORS P(4)

!HPF$ DISTRIBUTE Z(BLOCK,*) ONTO P

HPFーデータの分割配置（多次元配列）

80

HPFーデータの分割配置（多次元配列）

(BLOCK,*)

(*,BLOCK)

(BLOCK,BLOCK)

(SYCLIC,*) (*,SYCLIC)

(SYCLIC,BLOCK)

81

HPFーデータの分割配置（相互関係)

A

!HPF$ ALIGN A(I) WITH B(I)

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,*)

複製

82

• 先のプログラムで必要な通信

– プロセッサ1が，

Y(25) = X(24)+X(25)+X(26)

を実行する際にプロセッサ間でデータの通信が必要

データ配置 プロセッサ1 X(1)～X(25)

プロセッサ2

X(26)

～X(50)

プロセッサ3 X(51)～X(75)

プロセッサ4 X(76)～X(100)

– プロセッサ2,3,4でも同様

HPFープロセッサ間通信

プロセッサ2から

プロセッサ2が

Y(26) = X(25)+X(26)+X(27)

Y(50) = X(49)+X(50)+X(51)

プロセッサ3が

Y(51) = X(50)+X(51)+X(52)

Y(75) = X(74)+X(75)+X(76)

プロセッサ4が

Y(76) = X(75)+X(76)+X(77)

合計6回の通信が必要

83

• 例示プログラムで，データ分割配置がサイクリックの場

合どのような通信が必要か?

プロセッサ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)

• データの分割配置の形態によって通信回数が大きく異

なる．

→ 実行効率に多大な影響

HPFープロセッサ間通信

非常に多くの通信が必要となる!!!

全てのプロセッサが一つの代入文で2回づつ(98X2回!)

Y(I) = X(I-1)+X(I)+X(I+1)

84

• 負荷分散の面からはサイクリック分割の方が良い場合

DO I = 1,100

DO J = I,100

X(I,J) = X(I,J)/2

ENDDO

ENDDO

HPFープロセッサ間での計算負荷の均等化

I

J

I

J

ブロック分割

サイクリック分割

85

• データの分割配置はプログラマの知的作業とし，残り

の部分（SPMD化など）をコンパイラに任せる．

• 科学技術計算分野ではそれなりの普及の兆し．

• 参考となるサイト

– http://www.hpfpc.org/ HPF推進協議会

→XcalableMP

http://www.xcalablemp.org/

HPF