第8回 並列計算の概念
（プロセスとスレッド）
長岡技術科学大学
電気電子情報工学専攻
出川智啓
今回の内容
並列計算の分類
並列アーキテクチャ
並列計算機システム
並列処理
プロセスとスレッド
スレッド並列化
プロセス並列化
260
OpenMP
MPI
GPGPU実践基礎工学
2015/10/28
CPUの性能の変化
動作クロックを向上させることで性能を向上
Pentium 4 Processor
Pentium III Processor
Pentium II Processor
Pentium Processor
486 Processor
386 Processor
286
8085
8080
8086
4004
Intelが公開している資料を基に作成
http://pc.watch.impress.co.jp/docs/2003/0227/kaigai01.htmで見ることができる
261
GPGPU実践基礎工学
2015/10/28
CPUの性能の変化
増加し続けるトランジスタ数をコアの増加に充てる
クロックを下
げることで
発熱を抑制
Intelが公開している資料を基に作成
ASCII.technologies(Dec‐2009)やhttp://www.gdep.jp/page/view/248で見ることができる
262
GPGPU実践基礎工学
2015/10/28
CPUの性能の変化
FLOPS = 1コアの演算性能
× コア数
× CPUの動作周波数
1コアの演算性能の向上
複数のコアを使うように
プログラムを書かないと
速くならない
コア数の増加
演算器（トランジスタ）の増加
トランジスタ数の増加
CPUの動作周波数
263
コンパイラの最適化を利用
回路の効率化や印可電圧の向上
GPGPU実践基礎工学
劇的な性能向上は期待できない
2015/10/28
CPUの性能の変化
シングルコア
動作クロックを向上させることで性能を向上
CPUの動作は指数関数的に高速化
遅いプログラムでもCPUを新しくすれば高速化
マルチコア
効率的な利用には並列計算を意識したプログラミングが必要
待っていればCPUが勝手に速くなっていった時代はもう終わり
Free Lunch is Over
（タダ飯食いは終わり）
264
GPGPU実践基礎工学
2015/10/28
並列処理による高速化
処理をN個に分割して各コアが処理を分担
実行時間が1/Nに高速化されると期待
シングルコアCPU
資源1
資源2
資源3
資源4
マルチコアCPU
資源1
資源2
資源3
資源4
資源1
資源2
資源3
資源4
265
処理時間
GPGPU実践基礎工学
2015/10/28
並列処理による高速化
Hyper Threading Technology
一つの物理CPUを複数のCPUに見せる技術
CPU内のレジスタやパイプラインの空きを利用
10～20%程度の高速化
シングルコアCPU
資源1
資源2
資源3
資源4
Hyper Threading Technology
資源1
資源2
資源3
資源4
266
処理時間
GPGPU実践基礎工学
2015/10/28
並列計算の分類
並列アーキテクチャ
並列計算機システム
プロセッサレベルでの処理の並列化
データの処理と命令の並列性に着目
計算機レベルでの処理の並列化
計算機のメモリ構成に着目
並列処理
267
プログラムレベルでの処理の並列化
処理の並列化の方法に着目
GPGPU実践基礎工学
2015/10/28
並列アーキテクチャの分類
プロセッサの分類
Flynnの分類
並列アーキテクチャのグループ分け
データの処理と命令の並列性に着目
単一命令単一データ
2. SIMD 単一命令複数データ
3. MISD 複数命令単一データ
4. MIMD 複数命令複数データ
1. SISD
268
GPGPU実践基礎工学
2015/10/28
Single Instruction Single Data stream
単一命令単一データ
一つのデータに対して一つの処理を実行
逐次アーキテクチャ，単一アーキテクチャ
一度に一つの命令を実行
命令
パイプライン処理することで並列処理
が可能
データ
269
GPGPU実践基礎工学
A + B
2015/10/28
Single Instruction Multiple Data streams
単一命令複数データ
数値シミュレーションに最適
命令
数学のベクトルや配列計算の概念
に一致
複数のまとまったデータに対して同じ演算を同時に実行
命令は一つ，その命令が同時に多くのデータに対して適用さ
れるアーキテクチャ
ベクトルプロセッサとも呼ばれる
GPUも（一応）ここに分類
データ
A0
B0
A1
B1
A2
A3
270
GPGPU実践基礎工学
+
B2
B3
2015/10/28
CPUのSIMD拡張命令セット
SSE(Streaming SIMD Extensions)
1命令で4個の単精度浮動小数点データを一括処理
インラインアセンブラで命令を記述
コンパイラの最適化で利用されることを期待
AVX(Advanced Vector Extensions)
271
1命令で8個の単精度浮動小数点データを一括処理
1命令で4個の倍精度浮動小数点データを一括処理
GPGPU実践基礎工学
2015/10/28
Multiple Instructions Single Data stream
複数命令単一データ
複数のプロセッサが単一のデータに対して異なる処理を同時
に実行
形式上分類されているだけ
実際にはほとんど見かけない
命令
対故障冗長計算
272
誤り訂正機能（ECC）を持たないGPU
（Tesla以外）を2個同時に利用
計算して結果を比較，異なっていれば
やり直し
GPGPU実践基礎工学
A + B
データ
A ‐ B
2015/10/28
Multiple Instructions Multiple Data streams
複数命令複数データ
複数のデータに対して複数の処理を同時に実行
一般的な並列コンピュータ
複数のプロセッサがプログラマから見え，プロセッサごとに異なる命
令を実行
対称マルチプロセッサ
命令
複数の同一種類のプロセッサを持つ
どのプロセッサでも同じようにプログラム
を実行できる
非対称マルチプロセッサ
273
複数のプロセッサを持つが，各プロセッ
サは同一種類ではない
プロセッサごとに処理の最適化ができる
GPGPU実践基礎工学
A0 + B0
データ
A1 / B1
A2 ‐ B2
A3 * B3
2015/10/28
その他の分類
Single Program Multiple Data Streams
単一プログラム複数データ
MIMDシステムのプログラミング手法
現在のスーパーコンピュータやPCクラスタでプログラムを作る
際の標準的な手法
各PC用にプログラムを作らず，一つのプログラムの中で役割
を認識
274
GPGPU実践基礎工学
2015/10/28
その他の分類
Single Instruction Multiple Threads
単一命令複数スレッド
GPUのアーキテクチャ
一つの命令に対して，レジスタと演算器のペアがそれぞれ
データを処理
CPUでは逐次処理が基本で，SIMD用の演算器を使って並列処理
SIMTでは並列処理が基本
複数のまとまったスレッドが同じ演算を同時に実行
275
各スレッドが分岐命令に基づいて異なる処理を実行することもできる（=
厳密なSIMDではない）
GPGPU実践基礎工学
2015/10/28
並列計算の分類
並列アーキテクチャ
並列計算機システム
プロセッサレベルでの処理の並列化
データの処理と命令の並列性に着目
計算機レベルでの処理の並列化
計算機のメモリ構成に着目
並列処理
276
プログラムレベルでの処理の並列化
処理の並列化の方法に着目
GPGPU実践基礎工学
2015/10/28
並列計算機システム
並列処理の基本
処理を何らかの方法で分割
分割した処理をプロセッサ（やコア）に割り当て同時に処理
並列計算機システム
複数のプロセッサをもつ
主にメモリに違いがある
1. 共有メモリシステム
2. 分散メモリシステム
3. ハイブリッドシステム
277
GPGPU実践基礎工学
2015/10/28
共有メモリシステム
複数のプロセッサがメモリ空間を共有
分割した処理は各プロセッサ上で並列的に処理
共有されたメモリ空間上の変数は全てのCPU（やコア）か
らアクセス（読み書き）可能
他からアクセスされない変数を持つことも可能
CPU
CPU
CPU
CPU
メモリ
278
GPGPU実践基礎工学
2015/10/28
共有メモリシステム
各プロセッサが同等な条件でメモリにアクセス
SMP : Symmetric Multi‐Processor
物理的に共有されていないがSMPに見えるシステム
NUMA : Non‐Uniform Memory Access
SMP
NUMA
CPU
CPU
メモリ
CPU
CPU
メモリ
メモリ
CPU
CPU
メモリ
メモリ
CPU
279
CPU
GPGPU実践基礎工学
2015/10/28
分散メモリシステム
複数のプロセッサが独立なメモリ空間を持つ
分割した処理は各PC上で並列的に処理
共有されたメモリ空間上の変数は全て共有されない
データの共有には通信を行う
CPU
CPU
CPU
CPU
メモリ
メモリ
メモリ
メモリ
高速ネットワーク,LAN
280
GPGPU実践基礎工学
2015/10/28
ハイブリッドシステム
大規模な分散メモリシステム
Massively Parallel Processor(MPP)
1ノードが共有メモリシステムからなるMPP
SMP/MPPハイブリッドシステム
~16CPUs
CPU
CPU
~16CPUs
CPU
CPU
・・・
メモリ
・・・
キャッシュ
キャッシュ
CPU
CPU
・・・
キャッシュ
キャッシュ
~16CPUs
メモリ
・・・
キャッシュ
キャッシュ
メモリ
高速ネットワーク
281
GPGPU実践基礎工学
2015/10/28
並列計算の分類
並列アーキテクチャ
並列計算機システム
プロセッサレベルでの処理の並列化
データの処理と命令の並列性に着目
計算機レベルでの処理の並列化
計算機のメモリ構成に着目
並列処理
282
プログラムレベルでの処理の並列化
処理の並列化の方法に着目
GPGPU実践基礎工学
2015/10/28
並列処理の分類
タスク並列
データ並列
独立なタスクを異なるCPU,コアで同時に実行
独立なタスクが処理するデータを分割し，異なるCPU,コアが
参照し，処理を実行
Embarrassingly parallel (perfectly parallel)
各CPU,コアが同じタスクを異なるパラメータで実行
283
GPUが各ピクセルの色を決定し，ディスプレイに描画する処理
あるタスクに対してパラメータの影響を調査するような問題
天気予報等での活用が期待されている
GPGPU実践基礎工学
2015/10/28
タスク並列
独立な処理A, B, Cを各CPU,コアが実行
逐次処理
処理A
コア
コア1
コア2
処理B
処理C
並列処理
処理A
処理C
処理B
高速化
284
GPGPU実践基礎工学
2015/10/28
データ並列
独立な処理A, B, Cが取り扱うデータを分割して実行
逐次処理
処理A
コア
処理B
処理C
並列処理
コア1
処理A
処理B
処理C
コア2
処理A
処理B
処理C
高速化
285
GPGPU実践基礎工学
2015/10/28
Embarrassingly Parallel
ある処理Aを複数の異なるパラメータで実行
逐次処理
処理A
パラメータ1
コア
処理A
パラメータ2
並列処理
コア1
処理A
パラメータ1
コア2
処理A
パラメータ2
高速化
286
GPGPU実践基礎工学
2015/10/28
プロセスとスレッド
プログラムの実行を抽象化した概念
プロセス
OSから資源を割り付けられたプログラムの状態
命令実行を行うスレッドとメモリ空間を含む
スレッド
287
プロセスの中における命令実行を抽象化した概念
GPGPU実践基礎工学
2015/10/28
プロセス
OSから資源を割り付けられ，実行状態（または待機状
態）にあるプログラム
システムプロセス
プログラムで定められた命令実行
割り当てられたメモリの管理
OSの実行に関係するプログラム
ユーザプロセス
288
ユーザ権限で実行されているプログラム
GPGPU実践基礎工学
2015/10/28
マルチプロセス
複数のプロセスが存在し，並列に実行
シングルプロセス
マルチプロセス
マルチプロセスに対応したOSが必要
プロセスが一つのみ
プロセスが二つ以上
現在のOSはマルチプロセスに対応
シングルコアCPU一つでもマルチプロセスが可能
289
OSが複数のプロセスを切替
複数のプロセスが並列に実行されているように見せる
GPGPU実践基礎工学
2015/10/28
マルチプロセス
各プロセスに専用のメモリ領域を割り当て
CPUやメモリは複数のプログラムに割り当てられる
プログラムはCPUやメモリを独占しているように振る舞う
プロセスA
スレッド
メモリ
CPU
メモリ
OS
プロセスB
スレッド
メモリ
290
GPGPU実践基礎工学
2015/10/28
スレッド
プログラムの処理の最小実行単位
プロセス内で複数のスレッドが存在
1プロセスに一つ
1プロセスに二つ以上
シングルプロセス
シングルスレッド
マルチスレッド
シングルスレッド
マルチスレッド
マルチプロセス
シングルスレッド
マルチスレッド
291
GPGPU実践基礎工学
2015/10/28
マルチスレッド
一つのプロセスに二つ以上のスレッドが存在
一つのプロセスには専用のメモリ領域が割り当てられる
プロセス内の複数のスレッドはメモリ領域を共有
プロセスA
スレッド
スレッド
メモリ
CPU
メモリ
OS
プロセスB
スレッド
スレッド
メモリ
292
GPGPU実践基礎工学
2015/10/28
並列処理と並行処理
並列処理 Parallel Processing
一つの処理を複数の処理に分割
複数の処理が協調しながら処理を実行
真の並列処理 複数のプロセッサにそれぞれ一つのプロセス
疑似並列処理 一つのプロセッサに複数のプロセス
並行処理 Concurrent Processing
293
複数の処理を実行
複数の処理は必ずしも協調していない
GPGPU実践基礎工学
2015/10/28
並列計算
Parallel Computing
計算を複数に分割
各処理を計算機，プロセッサ，プロセス，スレッドが担当
複数の計算機
複数のプロセッサ ワークステーション
複数のコア
294
スーパーコンピュータ，PCクラスタ
マルチコアCPU, GPU
GPGPU実践基礎工学
2015/10/28
並列計算の方法
マルチスレッド
計算を複数に分割し，一つの処理を一つのスレッドが
担当
複数のスレッドはメモリ領域を共有
複数スレッドの協調処理は容易
OpenMP (Open Multi‐Processing)
295
プログラムに指示句（ディレクティブ）を挿入
ディレクティブで指定した箇所が自動で並列化
非常にお手軽な並列化方法
GPGPU実践基礎工学
2015/10/28
並列計算の方法
マルチプロセス
計算を複数に分割し，一つの処理を一つのプロセスが
担当
異なるプロセス同士はメモリの共有が不可能
協調して処理を行うにはデータを共有する手段が必要
MPI (Message Passing Interface)
296
異なるプロセス間でデータを交換する仕組みを提供
細かい命令を記述
並列化に手間はかかるが高い性能を達成
GPGPU実践基礎工学
2015/10/28
マルチスレッド
対象
並列アーキテクチャ（SIMD）
並列計算機システム（共有メモリ計算機）
CPUレベルでの処理の並列化
データの処理と命令の並列性に着目
計算機レベルでの処理の並列化
計算機のメモリ構成に着目
並列処理（データ並列）
298
プログラムレベルでの処理の並列化
処理の並列化の方法に着目
GPGPU実践基礎工学
2015/10/28
OpenMP
共有メモリシステムの並列処理に利用
標準化されたオープンな規格
OpenMPをサポートしているコンパイラであれば同じ書き
方が可能
並列化したい箇所をコンパイラに指示
299
ディレクティブを挿入
コンパイラが対応していなければコメントとして扱われる
修正が最小限で済み，共通のソースコードで管理
GPGPU実践基礎工学
2015/10/28
OpenMPによる並列化
処理を並列実行したい箇所に指示句（ディレクティブ）を
挿入
for文の並列化
ディレクティブを一行追加(#pragma omp ～)
#pragma omp parallel for
for(int i=0; i<N; i++)
C[i] = A[i] + B[i]
300
GPGPU実践基礎工学
2015/10/28
ベクトル和C=A+Bの計算
配列要素に対して計算順序の依存性がなく，最も単純に
並列化可能
・・・
a[i]
＋
301
＋
＋
＋
＋
＋
b[i]
・・・
c[i]
・・・
GPGPU実践基礎工学
2015/10/28
逐次（並列化前）プログラム
#include<stdio.h>
for(i=0; i<N; i++)
c[i] = a[i] + b[i];
#define N (1024*1024)
for(i=0; i<N; i++)
printf("%f+%f=%f¥n",
a[i],b[i],c[i]);
int main(){
float a[N],b[N],c[N];
int i;
return 0;
}
for(i=0; i<N; i++){
a[i] = 1.0;
b[i] = 2.0;
c[i] = 0.0;
}
vectoradd.c
302
GPGPU実践基礎工学
2015/10/28
逐次（並列化前）プログラム
#include<stdio.h>
#include<stdlib.h>
#define N (1024*1024)
#define Nbytes (N*sizeof(float))
for(i=0; i<N; i++)
c[i] = a[i] + b[i];
for(i=0; i<N; i++)
printf("%f+%f=%f¥n",
a[i],b[i],c[i]);
int main(){
float *a,*b,*c;
int i;
a = (float *)malloc(Nbytes);
b = (float *)malloc(Nbytes);
c = (float *)malloc(Nbytes);
free(a);
free(b);
free(c);
return 0;
}
for(i=0; i<N; i++){
a[i] = 1.0;
b[i] = 2.0;
c[i] = 0.0;
}
vectoradd_malloc.c
303
GPGPU実践基礎工学
2015/10/28
逐次（並列化前）プログラム
malloc/free
指定したバイト数分のメモリを確保/解放
stdlib.hをインクルードする必要がある
#include<stdlib.h>
main(){
int *a;
a = (int *)malloc( sizeof(int)*100 );
free(a);
}
sizeof
データ型1個のサイズ（バイト数）を求める
printf("%d, %d¥n", sizeof(float), sizeof(double));
実行すると4,8と表示される
304
GPGPU実践基礎工学
2015/10/28
並列化プログラム（スレッド並列）
#include<stdio.h>
#include<stdlib.h>
#define N (1024*1024)
#define Nbytes (N*sizeof(float))
#include<omp.h>
int main(){
float *a,*b,*c;
int i;
a[i] = 1.0;
b[i] = 2.0;
c[i] = 0.0;
}
#pragma omp for//for文を分担して実行
for(i=0; i<N; i++)
c[i] = a[i] + b[i];
}
a = (float *)malloc(Nbytes);
b = (float *)malloc(Nbytes);
c = (float *)malloc(Nbytes);
for(i=0; i<N; i++)
printf("%f+%f=%f¥n",
a[i],b[i],c[i]);
//複数スレッドで処理する領域を指定
//この指定だけだと全スレッドが同じ処理を行う
#pragma omp parallel
{
#pragma omp for//for文を分担して実行 }
for(i=0; i<N; i++){
305
free(a);
free(b);
free(c);
return 0;
GPGPU実践基礎工学
vectoradd.cpp
2015/10/28
処理の並列化
データ並列
forループをスレッドの数だけ分割
分割されたforループを各スレッドが実行
実行時間は1/スレッド数になると期待
スレッド0
スレッド1
＋
＋
a[i]
スレッド0
for(i=0; i<N/2‐1; i++)
c[i] = a[i] + b[i];
＋
＋
b[i]
スレッド1
306
for(i=N/2; i<N; i++)
c[i] = a[i] + b[i];
GPGPU実践基礎工学
c[i]
2015/10/28
プログラムのコンパイルと実行
コンパイル時にコンパイルオプション‐fopenmpを付与
‐fopenmpを付けるとディレクティブを処理
‐fopenmpを付けないとディレクティブは処理されない
grouseでは
ソースファイルの拡張子は.cではなく.cpp
コンパイラはccではなくg++
$ g++ ‐fopenmp vectoradd.cpp
307
GPGPU実践基礎工学
2015/10/28
速度向上率と並列化効率
N個のCPU・コア・PCで並列処理
理想的には1個で処理した時のN倍高速化
N倍の基準は？ 処理時間？FLOPS？
速度向上率
処理時間に着目して評価
T (1) T(1) : 1個のCPU・コア・PCで処理した時間
S
T ( N ) T(N) : N個のCPU・コア・PCで処理した時間
並列化効率
S(N )
E
N
308
GPGPU実践基礎工学
2015/10/28
速度向上率と並列化効率の例
並列度N
計算時間
T(N)[ms]
速度向上率S
=T(1)/T(N)
並列化効率E
=S/N
1
8.00 8.00/8.00 = 1.00
1.00/1 = 1.00
2
4.21 8.00/4.21 = 1.90
1.90/2 = 0.95
3
2.86 8.00/2.86 = 2.78
2.78/3 = 0.93
4
2.16 8.00/2.16 = 3.70
3.70/4 = 0.93
5
1.74 8.00/1.74 = 4.60
4.60/5 = 0.92
6
1.45 8.00/1.45 = 5.52
5.52/6 = 0.92
7
1.25 8.00/1.25 = 6.40
6.40/7 = 0.91
8
1.10 8.00/1.10 = 7.27
7.27/8 = 0.91
9
0.98 8.00/0.98 = 8.16
8.16/9 = 0.91
10
0.88 8.00/0.88 = 9.09
9.09/10 = 0.91
309
GPGPU実践基礎工学
2015/10/28
速度向上率と並列化効率
1
10
9
0.9
8
0.8
速度向上率
7
0.7
6
0.6
5
0.5
4
0.4
3
0.3
2
0.2
0.1
1
1
2
3
4
5
6
7
並列化効率
310
GPGPU実践基礎工学
8
9
10
並列化効率
速度向上率
並列化効率
速度向上率と並列化効率
よい計算機，計算アルゴリズム，
プログラム
悪い計算機，計算アルゴリズム，
プログラム
1
N
1
N
理想
理想
並列度
311
N
速度向上率
速度向上率
1
並列化効率
並列化効率
0
1
0
1
1
並列度
GPGPU実践基礎工学
N
2015/10/28
計算時間の変化
6
Processing time [ms]
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9
10
11
12
Number of Threads
312
GPGPU実践基礎工学
2015/10/28
速度向上率
12
11
10
Speedup ratio
9
ideal
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
11
12
Number of Threads
313
GPGPU実践基礎工学
2015/10/28
マルチプロセス
対象
並列アーキテクチャ（MIMD, SPMD）
並列計算機システム（分散メモリ計算機）
CPUレベルでの処理の並列化
データの処理と命令の並列性に着目
計算機レベルでの処理の並列化
計算機のメモリ構成に着目
並列処理（データ並列）
315
プログラムレベルでの処理の並列化
処理の並列化の方法に着目
GPGPU実践基礎工学
2015/10/28
Single Program Multiple Data streams
単一プログラム複数データ
MIMDシステムのプログラミング手法
現在のスーパーコンピュータやPCクラスタでプログラムを
作る際の標準的な手法
各PC用にプログラムを作らず，一つのプログラムの中で
役割を認識
316
GPGPU実践基礎工学
2015/10/28
MPI (Message Passing Interface)
メッセージ通信用ライブラリの標準規格の一つ
分散メモリシステムの並列処理に利用
共有メモリシステムでも動作
共有できないメモリ内のデータを，ネットワークを介して
送受信
317
送受信されるデータをメッセージと呼ぶ
GPGPU実践基礎工学
2015/10/28
MPIの処理の概要
通信を行うノード（計算機，CPU，コアなど）の集合を定義
各ノードに0からn‐1（nはノード総数）の番号を付与
各ノードでどのような処理を行うかを記述
通常の四則演算や関数呼出
メッセージ通信
どのノードへデータを送るか，どのノードからデータを受け取るか
各ノード用にプログラムを書くのではなく，一つのプログ
ラム内で各ノードが行う処理を書く
318
GPGPU実践基礎工学
2015/10/28
ベクトル和C=A+Bの計算
配列要素に対して計算順序の依存性がなく，最も単純に
並列化可能
・・・
a[i]
＋
319
＋
＋
＋
＋
＋
b[i]
・・・
c[i]
・・・
GPGPU実践基礎工学
2015/10/28
逐次（並列化前）プログラム
#include<stdio.h>
#include<stdlib.h>
#define N (1024*1024)
#define Nbytes (N*sizeof(float))
for(i=0; i<N; i++)
c[i] = a[i] + b[i];
for(i=0; i<N; i++)
printf("%f+%f=%f¥n",
a[i],b[i],c[i]);
int main(){
float *a,*b,*c;
int i;
a = (float *)malloc(Nbytes);
b = (float *)malloc(Nbytes);
c = (float *)malloc(Nbytes);
free(a);
free(b);
free(c);
return 0;
}
for(i=0; i<N; i++){
a[i] = 1.0;
b[i] = 2.0;
c[i] = 0.0;
}
vectoradd_malloc.c
320
GPGPU実践基礎工学
2015/10/28
並列化プログラム（プロセス並列）
#include<stdlib.h>
#include<mpi.h>
#define N (1024*1024)
int main(int argc, char* argv[]){
float *a, *b, *c;
int i, nsize, rank, nproc, bytes;
//MPIのライブラリを初期化して実行準備
MPI_Init(&argc, &argv);
//全ノード数を取得
MPI_Comm_size(MPI_COMM_WORLD, &nproc);
//各ノードに割り振られた固有の番号を取得
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
//各ノードで処理するデータサイズを設定
nsize = N/nproc;
if(rank==nproc‐1)nsize+=N%nproc;
}
bytes = sizeof(float)*nsize;
321
a=(float *)malloc(bytes);//各ノード
b=(float *)malloc(bytes);//でメモリを
c=(float *)malloc(bytes);//確保
//各ノードで配列の初期化と加算を実行
for(i=0;i<nsize;i++){
a[i]=1.0;
b[i]=2.0;
c[i]=0.0;
}
for(int i=0;i<nsize;i++)
c[i] = a[i]+b[i];
//全ノードの同期を取る
MPI_Barrier(MPI_COMM_WORLD);
free(a);
free(b);
free(c);
MPI_Finalize();//MPIのライブラリを終了
return 0;
GPGPU実践基礎工学
vectoradd_mpi.cpp
2015/10/28
MPIライブラリの内容
MPI_Init
MPI_Comm_rank(MPI_COMM_WORLD, &rank)
全ノード数を取得
MPI_Barrier(MPI_COMM_WORLD)
各ノードに割り振られた固有の番号を取得
MPI_Comm_size(MPI_COMM_WORLD, &nproc)
MPIのライブラリを初期化
MPI_COMM_WORLDという名前のノードの集合を用意
各ノード間の同期をとる
MPI_Finalize
322
MPIのライブラリを終了
GPGPU実践基礎工学
2015/10/28
処理の並列化
データ並列
ノード0
ノード1
forループをスレッドの数だけ分割
分割されたforループを各ノードが実行
実行時間は1/スレッド数になると期待
a[i]
ノード0
＋
for(i=0; i<N/2‐1; i++)
c[i] = a[i] + b[i];
＋
＋
＋
b[i]
ノード1
323
for(i=0; i<N/2‐1; i++)
c[i] = a[i] + b[i];
GPGPU実践基礎工学
c[i]
2015/10/28
プログラムのコンパイルと実行
コンパイル，実行にはMPI用のコンパイラや実行プログラ
ムを利用
コンパイル mpic++
mpic++ vectoradd_mpi.cpp
標準で a.out という実行ファイルを作成（これまでと同じ）
実行 mpiexec
mpiexec –n 4 ./a.out
‐n 4
プロセスの数を4で実行
grouseでは ‐mca btl ^openib というオプションも必要
324
GPGPU実践基礎工学
2015/10/28
計算時間の変化
9
MPI
8
Processing time [ms]
OpenMP
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9
10
11
12
Number of Threads
325
GPGPU実践基礎工学
2015/10/28
速度向上率
12
11
10
Speedup ratio
9
ideal
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
11
12
Number of Processes
326
GPGPU実践基礎工学
2015/10/28
OpenMPとの比較
OpenMPよりも若干実行に時間がかかる
MPIを利用するための準備が必要
OpenMPの並列化の上限は1ノード内のCPUのコア数
MPIの並列化の上限は計算機システム上のCPUの
全コア数
大規模な計算をするにはMPIしか選択肢がない
327
GPGPU実践基礎工学
2015/10/28
ハイブリッドシステム
大規模な分散メモリシステム
Massively Parallel Processor (MPP)
1ノードが共有メモリシステムからなるMPP
SMP/MPPハイブリッドシステム
~16CPUs
CPU
CPU
~16CPUs
CPU
CPU
・・・
メモリ
・・・
キャッシュ
キャッシュ
CPU
CPU
・・・
キャッシュ
キャッシュ
~16CPUs
メモリ
・・・
キャッシュ
キャッシュ
メモリ
高速ネットワーク
328
GPGPU実践基礎工学
2015/10/28
ハイブリッドシステムでのプログラミング
大規模な計算ではMPIしか選択肢がない
全てMPIでプログラムを作成（Flat MPI）
メモリが共有できないノード間ではMPI
メモリが共有できるノード内もMPI
MPIとOpenMPでプログラムを作成（Hybrid MPI）
329
メモリが共有できないノード間ではMPI
メモリが共有できるノード内はOpenMP
GPGPU実践基礎工学
2015/10/28
並列処理の性能評価
速度向上率
アムダールの法則(Amdahl’s law)
スケーリング
強いスケーリング(strong scaling)
弱いスケーリング(weak scaling)
330
GPGPU実践基礎工学
2015/10/28
速度向上率
N個のCPU・コア・PCで並列処理
理想的には1個で処理した時のN倍高速化
N倍の基準は？ 処理時間？FLOPS？
速度向上率
処理時間に着目して評価
T (1) T(1) : 1個のCPU・コア・PCで処理した時間
S
T ( N ) T(N) : N個のCPU・コア・PCで処理した時間
並列化効率
S(N )
E
N
331
GPGPU実践基礎工学
2015/10/28
アムダールの法則
並列度を大きくした際の性能向上の予測
問題のサイズは固定
並列化が不可能な箇所の割合によって性能向上の上限が決定
T (1)
S
T (N )
T(1) : 1個のCPU・コア・PCで処理した時間
T(N) : N個のCPU・コア・PCで処理した時間
T ( N ) 1 T (1)
N
: プログラム中で並列化
可能な箇所の割合
並列化不可能
時間
並列化可能
・・・
並列度
332
GPGPU実践基礎工学
2015/10/28
アムダールの法則
並列化可能な割合()が98％のプログラムを並列化
並列度(N)を変えた時の並列化効率(E)の変化
T (1)
S
E
T (N)
N
N
333
N=2のとき
N=4のとき
N=16のとき
N=128のとき
N=1024のとき
T (1)
1 N T (1)
N
E=0.98
E=0.94
E=0.77
E=0.28
E=0.047
感覚的には98%並列化できていれば十分
だと感じるが，並列度が増加すれば残り
2%の並列化できない影響が相対的に大き
くなる
GPGPU実践基礎工学
2015/10/28
スケーリング（scaling）
いくつかの条件を固定したとき，速度向上率が並列度に
比例すること
スケーラビリティ(scalability)
ストロング（強い）スケーリング(strong scaling)
スケーリングの度合い
問題の大きさを固定したときのスケーラビリティ
ウィーク（弱い）スケーリング(weak scaling)
334
各CPU，コア，PCの負荷を固定したときのスケーラビリティ
問題の大きさは並列度に比例して大規模化
GPGPU実践基礎工学
2015/10/28
ストロング（強い）スケーリング
問題の大きさを固定して並列度を増加
並列度の増加に伴って一つのCPU，コア，PCの負荷が減少
並列度0
335
並列度8
GPGPU実践基礎工学
並列度64
2015/10/28
ウィーク（弱い）スケーリング
各CPU，コア，PCの負荷を固定したときのスケーラビリティ
並列度の増加に伴って問題が大規模化
並列度0
336
並列度8
GPGPU実践基礎工学
2015/10/28
付録
OpenMPによる総和計算の並列化
計算順序に依存性はないが，出力結果に依存性がある
・・・
a[i]
＋
＋
＋
＋
＋
＋
sum
338
GPGPU実践基礎工学
2015/10/28
逐次（並列化前）プログラム
#include<stdio.h>
#include<stdlib.h>
for(i=0; i<N; i++)
sum += a[i];
#define N 100
#define Nbytes (N*sizeof(float))
int main(){
float *a,sum=0.0f;
int i;
printf("%f¥n",sum);
return 0;
}
a = (float *)malloc(Nbytes);
for(i=0; i<N; i++)
a[i] = (float)(i+1);
sum_serial.c
339
GPGPU実践基礎工学
2015/10/28
並列化プログラム（スレッド並列）
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#define N 100
#define Nbytes (N*sizeof(float))
printf("%f¥n",sum);
return 0;
}
int main(){
float *a, sum=0.0f;
int i;
a = (float *)malloc(Nbytes);
#pragma omp parallel for
for(i=0; i<N; i++)
a[i] = (float)(i+1);
#pragma omp parallel for ¥
num_threads(4) reduction(+:sum)
for(i=0; i<N; i++)
sum += a[i];
340
//num_threads()でスレッド数を設定
//reduction(+:sum)でsumに値の合計を集約
GPGPU実践基礎工学
sum.cpp
2015/10/28
データ競合
reduction()を付けないとどうなるか
実行結果が毎回変わる
データ競合（データレース）が発生
スレッド1
a[i]
sumの値(0)を参照
1
2
3
4
5
6
54
55
56
sum
0
sumの値(0)を参照
スレッド2
51
341
52
a[i]
53
GPGPU実践基礎工学
2015/10/28
データ競合
reduction()を付けないとどうなるか
実行結果が毎回変わる
データ競合（データレース）が発生
スレッド1
1
a[i]
2
3
4
5
6
54
55
56
sum
51
0+51をsumに書き込み
スレッド2
51
342
52
a[i]
53
GPGPU実践基礎工学
2015/10/28
データ競合
reduction()を付けないとどうなるか
実行結果が毎回変わる
データ競合（データレース）が発生
スレッド1
a[i]
0+1をsumに書き込み
1
2
3
4
5
6
54
55
56
sum
1
スレッド2
51
343
52
a[i]
53
GPGPU実践基礎工学
2015/10/28
MPIによる総和計算の並列化
計算順序に依存性はないが，出力結果に依存性がある
OpenMPの時は計算順序が問題
MPIの時はノード間通信が必要
・・・
a[i]
＋
＋
＋
＋
＋
＋
sum
344
GPGPU実践基礎工学
2015/10/28
並列化プログラム（プロセス並列）
#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>
//各ノードに割り振られた固有の番号を取得
MPI_Comm_rank(MPI_COMM_WORLD,
&rank);
#define ROOT 0 //rank 0のノードは特別扱い
#define N 100
//各ノードで処理するデータサイズを設定
nsize = N/nproc;
if(rank==nproc‐1) nsize+=N%nproc;
int main(int argc, char* argv[]){
float *a,sum;
int i, nsize, rank, nproc,bytes;
int src, dst,tag;
float sum_rcv;
MPI_Status stat;
//MPIのライブラリを初期化して実行準備
MPI_Init(&argc, &argv);
//全ノード数を取得
MPI_Comm_size(MPI_COMM_WORLD, &nproc);
345
//各ノードでメモリを確保
bytes = sizeof(float)*nsize;
a=(float *)malloc(bytes);
//値の設定
for(i=0;i<nsize;i++)
a[i]=(float)(i+rank*N/nproc+1);
MPI_Barrier(MPI_COMM_WORLD);
GPGPU実践基礎工学
sum_mpi.cpp
2015/10/28
並列化プログラム（プロセス並列）
for(src=ROOT+1; src < nproc; src++){
tag=0;
MPI_Recv(&sum_rcv, 1, MPI_FLOAT, src, tag, MPI_COMM_WORLD, &stat);
sum +=sum_rcv;
}
//各ノードで配列の総和を求める
sum=0.0;
for(i=0;i<nsize;i++)
sum += a[i];
//全ノードの同期を取る
MPI_Barrier(MPI_COMM_WORLD);
//各ノードの総和の値をrank0に送る
if(rank != ROOT){
//rank0以外のノードはrank0に
//sumの値を送信
dst=ROOT;
tag=0;
MPI_Send(&sum, 1, MPI_FLOAT, dst, tag, MPI_COMM_WORLD);
}else{
}
//rank0はそれ以外の全ノードから
//送られてくる値を受信し，総和を計算
346
}
if(rank == ROOT)
printf("%f¥n",sum);
free(a);
MPI_Finalize();//MPIのライブラリを終了
return 0;
GPGPU実践基礎工学
sum_mpi.cpp
2015/10/28
MPIライブラリの内容
MPI_Send
指定したノードへメッセージを送信
送信したメッセージが正常に受信されるまで停止（同期実行）
MPI_Recv
347
指定したノードからメッセージを受信
送信された（されてくるはずの）メッセージを正常に受信するま
で停止（同期実行）
GPGPU実践基礎工学
2015/10/28
実行イメージ（1から100までの総和）
PC1(rank0)
PC2(rank1)
PC3(rank2)
nsize=33
1 2 3 … 32 33
nsize=33
34 35 36 … 65 66
nsize=34
67 68 69 … 99 100
sum
sum
sum
MPI_Send
MPI_Send
sum_rcv
sum
＋
MPI_Recv
sum_rcv
sum
348
＋
MPI_Recv
GPGPU実践基礎工学
2015/10/28
デッドロック
ノード間のデータ交換
処理の順序を間違えるとプログラムが停止
正常
デッドロック
PC1(rank0)
PC2(rank1)
PC1(rank0)
PC2(rank1)
MPI_Send
MPI_Recv
MPI_Send
MPI_Send
MPI_Recv
MPI_Send
MPI_Recv
MPI_Recv
の順に実行
349
の順に実行
GPGPU実践基礎工学
2015/10/28
デッドロック
ノード間のデータ交換
処理の順序を間違えるとプログラムが停止
正常
デッドロック
PC1(rank0)
PC2(rank1)
PC1(rank0)
PC2(rank1)
MPI_Send
MPI_Recv
MPI_Send
MPI_Send
MPI_Recv
MPI_Send
の順に実行
350
相手が受信するまで停止し続
け，プログラムが正常に動作しな
MPI_Recv
MPI_Recv
い
の順に実行
GPGPU実践基礎工学
2015/10/28
MPIプログラムのコンパイル，実行
補足
MPIプログラムのコンパイル，実行
標準の環境ではmpic++やmpiexecを実行できない
OSがmpic++やmpiexecの場所を把握していないことが原因
‐bash‐3.2$ mpic++
‐bash: mpic++: command not found
‐bash‐3.2$ mpiexec
‐bash: mpiexec: command not found
‐bash‐3.2$
OSが実行ファイルなどを探す場所（PATH）を設定
352
PATH（パス）にmpic++やmpiexecがあるディレクトリを追加
PATHは.bashrcに記述
.bashrcはホームディレクトリ（grouseにログインしたときの
ディレクトリ）に置く
GPGPU実践基礎工学
2015/11/04
補足
MPIプログラムのコンパイル，実行
ホームディレクトリでls ‐a を実行して
.bashrcが見つかる場合
.bashrcが見つからない場合
353
エディタで.bashrcを開いて編集
ホームディレクトリに.bashrcを新しく作成
.(ドット)から始まるファイルはlsで表示されない
lsに‐aオプションを付けて実行すると全てのファイルを表示
GPGPU実践基礎工学
2015/11/04
補足
MPIプログラムのコンパイル，実行
.bashrcに記述（追記）する内容
MPIROOT=/opt/mpi/openmpi/gcc
PATH=$MPIROOT/bin:$PATH
LD_LIBRARY_PATH=$MPIROOT/lib:$LD_LIBRARY_PATH
MANPATH=$MPIROOT/share/man:$MANPATH
export PATH
export LD_LIBRARY_PATH
export MANPATH
.bashrcに記述した内容を有効化
sourceコマンドを利用
354
source 設定ファイル名 として実行
source .bashrc
GPGPU実践基礎工学
2015/11/04
補足
MPIプログラムのコンパイル，実行
.bashrcをストリーミング配信サイトからダウンロードし
て利用するには
1. ストリーミング配信サイト（GPGUP実践基礎工学第8回）にアク
セス
2. bashrcをダウンロードしてホームディレクトリに置く
アップロードしているファイル名はbashrc
3. mvコマンドを使ってファイル名を変更
$ mv 変更前ファイル名 変更後ファイル名
$ mv bashrc .bashrc
4. sourceコマンドで設定を有効化
355
$ source .bashrc
GPGPU実践基礎工学
2015/11/04
© Copyright 2024 ExpyDoc
