並列化の基礎知識

並列化の基礎（言葉の意味）
並列実行には、複数のタスク実行主体が必要
• 共有メモリ型システム(SMP)での並列
• プロセスを使用した並列化
• スレッドとは？スレッドを使用した並列化
• 分散メモリ型システムでの並列
• メッセージパッシングによる並列化
並列アーキテクチャ関連の言葉を押さえよう
21
SofTek Systems, Inc.
プロセスを使用した並列処理
並列処理を行うためには複数のプロセスの生成必要
プロセスとは、プログラム実行のための能動実態
メモリ空間
親プロセス
子プロセス
しかし、プロセスレベルの
Process
Process
Table
Table
並列処理はオーバヘッド多し
Program
Text
共有
Data
Area
コピー
Data
Area
Stack
Area
コピー
Stack
Area
スレッドの活用
アドレス空間のコピー
は時間がかかる
Process FORK
22
SofTek Systems, Inc.
スレッドの生成と並列処理
軽量プロセス　＝　生成時のコストが小さい
（オーバヘッド）
メモリ空間
マスタ
Process
Table
スレッド
Program
Text
共有
Data
Area
共有
Stack
Area
Stack
Area
プロセス
Thread生成
複数のスレッドを生成し
並列処理を行う
Stack areaは、並列時
独自に使用
Dynamicなallocation
システムコール
23
SofTek Systems, Inc.
スレッドとは
プロセスから実行主体（スレッド）を抽出し
テキスト、データ等は共有する
プロセス＝（メモリ空間＋資源情報）＋ プログラム実行主体
人間　＝　肉体（物理的な体）　＋ 意志（思考形態）
ピアノ
左手 スレッド１
人
右手 スレッド２
24
SofTek Systems, Inc.
スレッドの実行形態と並列実行
Applications
Single process
並列実行ライブラリ
スレッド対応
Multi thread
物理CPU数以上の
スレッドの存在OK
Operating System
渡り歩く
P
P
P
P
P
P
P
P
Hardware (SMP)
P Processor
P
Process
25
Thread
SofTek Systems, Inc.
メッセージパッシングとは
同じ並列プログラム
Applications
データの送受、
同期処理は
プログラム明示
Single process
メッセージの交換
独立の
ハードウェア
OS
OS
OS
P
P
P
P
P
P
Hardware
Hardware
Hardware
MPI
通信路
P Processor
P
Process
26
SofTek Systems, Inc.
スレッド並列＋MPI (Hybrid)
同じ並列プログラム
Applications
MPI
実装
Single process
Multi thread
メッセージの交換
OS
SMP
Cluster
P
P
P
P
Hardware
OS
P
P
P
P
Hardware
OS
P
P
スレッド並列
message Passing
P
P
Hardware
通信路
P Processor
P
Process
27
Thread
SofTek Systems, Inc.
並列化についての話
• 並列プログラムはどのように動くのか？
• 並列プログラミングのモデル (SPMD)
• どのように並列化するのか？
• 並列化のための言語と性能
• OpenMP、HPF、MPI
• 並列の効果、Scalabilityの考え方
• どんなものが並列化可能なのか？
• 並列プログラミング環境
28
SofTek Systems, Inc.
並列動作の形態
単体処理型
P
P
Memory
Process
逐次処理
並列可能
逐次処理
共有メモリ型
P
P
P
P
P
P
分散メモリ型
P
P
Memory
P
P
P
P
Memory
Process
Process
Process
Process 時間
Thread 生成
同期処理
スレッド
P Processor
P
29
同期
冗長実行処理
Message Passing
割当てたデータ部のみ処理
必要であればデータ交換
SofTek Systems, Inc.
並列プログラミングモデル
SPMD =Single Program Multi Data
同一プログラムモジュール
Load
プログラムの
条件文で扱う
データを制御
Load
Load
if Node0
if Node1
if Node2
I=1,2
の計算
I=3,4
の計算
I=5,6
の計算
node0
node1
node2
共有メモリ型＆分散メモリ型
30
SofTek Systems, Inc.
SPMDによる並列モジュール構築
スレッド並列でもメッセージパッシングでも基本はSPMD
• 共有メモリ型システム
• スレッドを使用した並列化モジュール
• コンパイラシステムが自動的にSPMD型　並列モジュールを作成可能
• 分散メモリ型システム
• MPI (Message Passing Interface)ライブラリ
を用いたSPMD型プログラミング必要
31
SofTek Systems, Inc.
どのように並列化するの？
• DO Loopレベルを分割並列（細粒度並列性）
• コンパイラによる自動並列 on SMP
– Directive/Pragmaによる並列指示
– OpenMP directiveによる並列指示
• HPF (High Performance Fortran)による並列化
• コンパイラによる自動並列可能
• 細かな並列指示＝directive用意
• MPI (API)を用いた並列化
• 全て、人がプログラミング（同期処理等も自
分で考える）
32
SofTek Systems, Inc.
プログラム言語とその対応システム
分散メモリ型システム
MPI
粗粒度並列性
細粒度並列性
（DO Loopレベル）
HPF
（要並列計算量）
（計算領域分割）
OpenMP
共有メモリ型システム
33
SofTek Systems, Inc.
OpenMP = SMP Parallel Fortran/C/C++
1) 自動並列
2) directiveを使って細かな並列
Fork/Join Model
F90
F77
C
F95
C++
omp_get_num_threads()
omp_get_num_threads()
omp_set_num_threads()
omp_set_num_threads()
omp_get_thread_num()
omp_get_thread_num()
omp_in_parallel()
omp_in_parallel()
omp_set_dynamic()
omp_set_dynamic()
!OMP$
!OMP$ PARALLEL
PARALLEL [clauses]
[clauses]
<< redundant
redundant work
work >>
!OMP$
!OMP$ DO
DO [clauses]
[clauses]
DO
I
DO I == 1,
1, NN
<< parallel
parallel work
work >>
!$OMP
!$OMP ATOMIC
ATOMIC
X(IDX)
X(IDX) == X(IDX)+1
X(IDX)+1
ENDDO
ENDDO
!$OMP
END
!$OMP END DO
DO
<< redundant
redundant work
work >>
!$OMP
!$OMP END
END PARALLEL
PARALLEL
Parallel Regions/Constructs
Query Functions
34
SofTek Systems, Inc.
自動並列処理による性能向上
-2CPU on SMP Pentium Pro : 2CPUs
Memory access
軽い
アプリケーションの
計算特性に依存する
・メモリアクセス量
・多重演算の度合い
出展： Kuck & Associates, Inc.
http://www.KAI.com/のページより
35
SofTek Systems, Inc.
自動並列処理による性能向上
- 4CPU on SMP Pentium Pro : 4CPUs
分割処理量の均衡
・Load balancing
バランス崩れると
性能飽和
出展： Kuck & Associates, Inc.
http://www.KAI.com/のページより
36
SofTek Systems, Inc.
LS-DYNA under OpenMP
Speedup
2
5458 Elements
25000 Degrees of Freedom
1 CPU Time = 4446 Seconds
2 CPU Time = 2393 Seconds
Dual 450Mhz PII Xeon
1.5
1
0.5
0
1
2
Processors
• LSDYNA = Over 750,000 lines of Fortran and C source code
• 1.86X Speedup on 2 processors
• Parallelized using PGI Fortran and OpenMP
37
SofTek Systems, Inc.
HPF = Standard Parallel Fortran
配列の陽的並列分割
1) 自動並列
2) directiveを使って細かな並列
配列分割
処理分割
!HPF$
!HPF$ INDEPENDENT
INDEPENDENT
DO
DO II == 1,
1, NN
A(IDX(I))
A(IDX(I)) == B(I)
B(I)
ENDDO
ENDDO
Parallel Constructs
Data Distribution
HPF
共有メモリ型
両方対応
分散メモリ型
自動生成
SMP
38
MPI RPM
各種通信系
SofTek Systems, Inc.
MPI = Message Passing Fortran/C/C++
自分のノード番号に
従った部分の計算を
行う
F90
SPMD Model
F77
C
F95
C++
mpi_send()
mpi_send()
mpi_recv()
mpi_recv()
mpi_allgather()
mpi_allgather()
mpi_barrier()
mpi_barrier()
Point-to-point and collective
communications
call
call MPI_INIT(ierr)
MPI_INIT(ierr)
call
call MPI_COMM_RANK(…)
MPI_COMM_RANK(…)
call
call MPI_COMM_SIZE(…)
MPI_COMM_SIZE(…)
if
(myid
if (myid .eq.
.eq. 0)
0) then
then
<get
input>
<get input>
endif
endif
call
call MPI_BCAST(…)
MPI_BCAST(…)
...
...
do
do II == myid+1,
myid+1, n,
n, numprocs
numprocs
xx == hh ** (dble(I)
(dble(I) -0.5d0)
-0.5d0)
sum
=
sum
+f(x)
sum = sum +f(x)
enddo
enddo
mypi
mypi == hh ** sum
sum
call
call MPI_REDUCE(…)
MPI_REDUCE(…)
……
Explicit messaging
39
SofTek Systems, Inc.
MPI-粗粒度計算の例
領域分割法
解析領域
CPU 2
CPU 1
逐次処理
CPU 0
CPU 1
CPU 3
CPU 0
CPU 2
データの交換
CPU 3
各CPUに割り当てる
計算領域を分割
領域境界での
データの交換必要
並列処理
40
SofTek Systems, Inc.
並列の効果（どの位？）
並列化不可
並列化可能
20
80
単体実行（1CPU）
並列ジョブ
並列 1CPU
並列 2CPU
20
20
2
20
20
2
並列化率
並列による性能向上分
並列 3CPU
並列 4CPU
0
20
20
2
並列オーバヘッドもあるよ
20
20
2
高々100/40=2.5倍
20
ロードバランス良好の時
40
41
（分）
60
80
100
SofTek Systems, Inc.
並列の効果 (Scalability)
アムダールの法則＝並列化率P%の時の効果は
＝ 100 / (100-P) : 理想値
並列化効率
並列化率
60.0%
70.0%
80.0%
85.0%
90.0%
91.0%
92.0%
93.0%
94.0%
95.0%
96.0%
97.0%
98.0%
99.0%
99.5%
2
1.43
1.54
1.67
1.74
1.82
1.83
1.85
1.87
1.89
1.90
1.92
1.94
1.96
1.98
1.99
Number of CPU
4
6
8
1.82
2.00
2.11
2.11
2.40
2.58
2.50
3.00
3.33
2.76
3.43
3.90
3.08
4.00
4.71
3.15
4.14
4.91
3.23
4.29
5.13
3.31
4.44
5.37
3.39
4.62
5.63
3.48
4.80
5.93
3.57
5.00
6.25
3.67
5.22
6.61
3.77
5.45
7.02
3.88
5.71
7.48
3.94
5.85
7.73
42
12
2.22
2.79
3.75
4.53
5.71
6.03
6.38
6.78
7.23
7.74
8.33
9.02
9.84
10.81
11.37
16
2.29
2.91
4.00
4.92
6.40
6.81
7.27
7.80
8.42
9.14
10.00
11.03
12.31
13.91
14.88
SofTek Systems, Inc.
並列手法による並列効果の違い
並列手法（共有メモリ／分散メモリ）による
並列効果の違い
並列効果(Scalability)
25
MOM-3,PIPE
Seismicベース
Coarse Grained Parallel
20
MPI
（ 分散メモリ対応）
15
Fine Grained Parallel
（ 共有メモリ対応）
10
現POMベース
SMP
5
現MOM／Seismicベース
0
0
4
8
12
16
20
24
28
32
並列CPU数
43
SofTek Systems, Inc.
どんなものが並列化可能か（１）
• 細粒度並列（SMP：自動並列化含む）
• 基本的にDO Loopが対象
• 多重DO Loopも対象
• ループ反復間に変数の依存関係がない
• I/O処理、配列の動的割付等を行っていない
• ループの反復中にループを抜け出さない
• 依存関係のあるサブルーチンコールを含んで
いないこと
• 間接メモリ参照がない、曖昧なポインタがない
44
SofTek Systems, Inc.
どんなものが並列化可能か（２）
• 並列効果の高いアプリケーションソルバー
• 差分法　： レッド・ブラックSOR法、パイプライン法
： ICCG法はパイプライン法へ
• モンテカルロ法、分子動力学等の粒子を扱うもの
• ニューロンの計算： 行列・ベクトル計算が主体
• 境界要素法： 密行列の連立一次方程式に帰着
• 並列効果が低いソルバー
• 有限要素法（陰解法）：粗行列、計算量少ない
: 領域分割法へ変換
45
SofTek Systems, Inc.
並列最適化における注意点
• 並列化を行う前に単体性能の向上重要
• 並列化率が高くなければ、並列化効果、
scalabilityは期待できない。
• 単体性能の最適化では、それだけで数倍の
性能向上も期待できる
• アプリケーションの特性で並列化手法が変
わる。適切な手法をまず考える。
46
SofTek Systems, Inc.
並列プログラム開発環境での問題
• 見たいものが見えない
• 並列デバッグ時の問題箇所の特定が難しい
• MPI開発では、演算・通信の状況が見えない
並列プログラミング環境必須
業界標準のデバッガ&ツール
マルチプロセスデバッガ
： TotalView
MPI プログラムの性能解析
Sun
Prism
: VAMPIR
47
SofTek Systems, Inc.
並列デバッガ TotalView
• 業界標準並列デバッガ
• 操作性に優れたGUIにより効率よく使用できる
• マウスのボタン操作で主要なコマンドを実行可能
• 多様な分散、並列プログラミングモデルをサポート
• 巨大で、複雑なプログラムもデバッグ可能
• 様々な言語、プラットフォーム、アーキテクチャで利用
可能　(MPIのデバッキング可能）
48
SofTek Systems, Inc.
TotalView の実行状況
Root
ウィンドウ
Data ウィンドウ
右クリック
Process
ウィンドウ
ダイブによりプロセスの
内部を表示可能
49
SofTek Systems, Inc.
TotalView データの可視化
• 分散配列の可視化
Visualize array distribution
50
SofTek Systems, Inc.
VAMPIRの特徴
• MPI (及びアプリケーションイベント)のオフライ
ントレース解析
• VAMPIRtrace ツールによるトレース生成
•
•
•
•
•
扱いやすいユーザインタフェース
スケーラブル（時間とプロセッサ空間）
秀逸なズーミング、フィルタリング機能
高性能グラフィックス
MPIとアプリケーションイベントの表示、解析:
• MPI ルーチン
• 1対1 、集団通信
51
SofTek Systems, Inc.
VAMPIR GUI (1)
MPIの動作挙動が見える
52
SofTek Systems, Inc.
VAMPIR GUI (2)
MPICH(p4)による通信状況のスナップショット
53
SofTek Systems, Inc.
VAMPIR GUI (3)
通信のサマリチャート（二つの結果の同定例）
MPICH
MPI/GAMMA
54
SofTek Systems, Inc.