CCS HPC Seminar 2024

筑波大学計算科学研究センター
CCS HPCセミナー「並列処理の基礎」
朴 泰祐
taisuke@cs.tsukuba.ac.jp
筑波大学大学院システム情報工学研究科
計算科学研究センター

1

CCS HPC Seminar 2024

「並列処理の基礎」内容• 演算性能と通信性能のメトリック• 並列処理とは？
• 並列処理の必要性• 各種並列化手法• 通信・同期• 並列化効率とアムダールの法則• 負荷バランス

2

CCS HPC Seminar 2024

演算性能と通信性能のメトリック• 演算性能（主として浮動小数点演算）– FLOP: (number of) Floating point Operations
その処理の中の浮動小数点演算数ex) for(i=0; i<100; i++) a[i] = b[i] * c + d[i];⇒ 200FLOP– FLOPS: Floating point Operations Per Second
1秒当たりの浮動小数点演算処理性能ex) 上の問題を2μ秒で処理した場合 ⇒ 100 MFLOPS• 通信性能– B/s (Byte/sec):
1秒当たりに通信処理できるデータ量ex) Infiniband EDRの理論ピーク性能＝12.5 GB/sbps (bit per second) で表示される場合もある
システムによって、必ずしも 1Byte=8bit でないことがあるので注意
3

CCS HPC Seminar 2024

並列処理とは？
• 「１つの問題を何らかの方法で分割し、複数の計算リソースに割り当てることによって性能・規模等を向上させること」– 「１つの問題」を解く⇒多重処理とは違う– 「問題の分割」（並列化）⇒処理効率が高くなるように分割– 「向上」するもの⇒速度だけでなく、問題規模の増大、精度の向上等
いろいろなメトリックがある• parallel processing v.s. concurrent processing– 部分問題（並列化）されたものを「見かけ上同時実行」すること⇒concurrent processing(並行処理)– 部分問題を「物理的に同時実行」⇒parallel processing(並列処理)• 並列処理に供されるリソース– CPU, memory, disk, network等、あらゆる計算リソースが並列化に貢献し得る– 複数のCPUに並列に割り当てられる処理単位を以後「並列プロセス」と定義
4

CCS HPC Seminar 2024

高性能計算と並列処理••

数値シミュレーション等の科学技術計算、大量のデータ処理等において、問題規模の拡大要求は日増しに高まっている
問題規模を増大した時の処理量は多くの場合O(N)の増加では済まない– ３次元流体計算（気象予報等）
空間の1次元をN点に分割して数値シミュレーションすると、3次元問題の演算量はO(N3)。
– 行列計算（連立一次方程式）
直接法（消去法）で処理するとN変数の連立一次方程式解法の計算量はO(N3)。
– 多体問題（宇宙物理の重力計算等）
N体の質点間の重力は相互作用の総当たり計算になるため、計算量はO(N2)。

•

計算機の性能とデータ容量はいくら大きくても「大き過ぎる」ことはない⇒大規模計算処理はもはや並列処理なしには成り立たない•大容量計算、大容量データ、大容量通信等の要求に対し、計算リソースを適切にマッピングし、効率的な並列処理を行う技術が必須になっている
5

CCS HPC Seminar 2024

計算性能・データ容量の限界•••••半導体の集積度は1.5年で約2倍になる⇒ムーアの法則
もしIC上のトランジスタ数の増加を演算性能に転換できれば、「プロセッサの性能は1.5年で約2倍になる」と読み替えられる。
右図：Intelプロセッサのトランジ
スタ数の伸びメモリ等の容量の伸びもほぼこれに従う
しかし、これだけでは爆発する
性能向上要求に対応できない（ムーアの法則に従うプロセッサ単体の性能向上も限界に近づいている）⇒（超）並列化

6

CCS HPC Seminar 2024

TOP500 List (May 2024)
Sum of #1～#500#1 Computer
Frontier (ORNL)
富岳（R-CCS）#500 Computer

CP-PACS (U. Tsukuba)

CCS HPC Seminar2024UPDATED

TOP500 list on May 2024
#123Machine

ArchitectureCountry

MPP (AMD EPYC, AMDUSA
MI250X GPU)MPP (Intel Xeon, Intel
Aurora, ANLUSAGPU Max)
Eagle, Microsoft Cluster (Intel Xeon, NVUSA
AzureH100)
Frontier, ORNL

Rmax
(PFLOPS)

Rpeak (PFLOPS)GFLOPS/W

1,206.00

1,714.81

52.92

1,012.00

1,980.01

26.15

561.20846.84---

4

Fugaku, R-CCS

MPP (Fujitsu, A64FX)

Japan

442.01537.21

14.78

5

LUMI,
EuroHPC/CSC

MPP (AMD EPYC, AMDFinland
MI250X GPU)

379.70531.51

51.38

6Alps, CSCS

MPP (NVIDIA GH200CPU/GPU)

270.00353.75

51.98

7Leonard,EuroHPC/CINECA

Cluster (Atos, NV H100) Italy

238.70304.4732.24

8Cluster (Intel Xeon, NVMareNostrum 5ACC, EuroHPC/BSC H100)

Spain

175.30249.4442.15

9Summit, ORNL

Cluster (IBM, NV V100)

USA

148.60200.79

14.72

Cluster (Intel Xeon, NV
SuperPOD, NVIDIA H100)

USA

121.40188.65----2024/06

情報科学概論

10 Eos NVIDIA DGXSwitzerland

8

CCS HPC Seminar 2024

並列化手法
• 問題の並列化には様々な切り口がある– １つの問題を分割（例）domain decomposition：問題を空間領域で切り分け、各部の処理を並列プロセスとする– １つの処理を分割（例）parameter search：同じプログラムを多数の異なる入力パラメータで実行して統計値を得る⇒１セットのパラメータを１つのプロセスで行い、それを管理・統合するプロセスを置く• 並列化方法のいろいろ– EP (embarrassingly parallel）：並列化が自明なもの（parametersearch等）、並列処理単位間の独立性が保証されている– data parallel：処理対象のデータを分割（domain decomposition等）– pipeline：流れ作業の中の各部分作業を並列リソースに割り当て– master/worker：処理すべきプロセスのプールを複数のワーカーに順次割り当て
9

CCS HPC Seminar 2024

EPの例
• モンテカルロ・シミュレーション– 多数のケースをランダムパラメータによって試行し、それぞれの結果を統計処理して最終的な結果を求める– 例：1/4単位円を用いたπの計算

N個の( x, y )対（0 £ x £ 1, 0 £ y £ 1)をランダムに生成し、C 1
x + y < 1を満たす組の数を Cとすると、 は p に近づく。
N 4
22– 各(x,y)対に対する単位円内点かどうかの判定は完全に独立に処理可能⇒独立処理（完全並列化）が可能
C/N– 一番最後にCの総和を求めればよい

10

CCS HPC Seminar 2024

データ並列の例• domain decomposition– 空間に一様な計算点が分布しており、これを適当な軸で分割し、並列処理– EP的な処理になる場合もあるが、一般的に隣接点等で何らかのinteractionが必要になる場合が多い– 例：
for(t=0; t < T; t++){for(i=1; i < N-1; i++)a[i] = b[i-1] - 2*b[i] + b[i+1];
for(i=0; i < N; i++)b[i] = a[i];}並列処理単位問題空間11CCS HPC Seminar 2024

domain decomposition（続き）
....

b[5]

b[6]

b[7]

b[8]

b[9]

....

....

a[5]

a[6]

a[7]

a[8]

a[9]

....

並列処理単位の切れ目

for(t=0; t < T; t++){for(i=1; i < N-1; i++)a[i] = b[i-1] - 2*b[i] + b[i+1]; // 更新時に通信あり
for(i=0; i < N; i++)b[i] = a[i];// 更新時に通信なし}
12

CCS HPC Seminar 2024

パイプライン並列• 一連の処理が流れ作業で進む場合、各ステージの処理にリソースを割り当て、全体を並列に処理• ベクトル処理の例
for(i=0; i < N; i++){a[i]=b[i] * c[i] + s * d[i];}a[i]に連続書き込み加算

c[i]を連続読み込み
乗算
b[i]を連続読み込み

乗算
ｄ[i]を連続読み込みs(スカラー)
13

CCS HPC Seminar 2024

master/worker型並列処理•••

１つのmasterプロセスと複数のworkerプロセスがあり、masterが多数の独立な処理の「プール」を持つ（処理数>>worker数）
masterはプールから処理すべき問題を取り出し、全workerに１つずつ与える
workerは与えられた処理を行い、終了したら結果をmasterに返し、次の処理を割り当ててもらう
master::// give a job to each worker
while(1){// receive worker’s result// give a job to the worker}

worker::while(1){// receive a job from master// process the job// send the result to master}

14

CCS HPC Seminar 2024

master/worker（続き）• 特に各処理の重さが異なり、負荷分散が難しい場合に有効• 各処理は基本的にEPである必要がある
job割り当て／結果回収

worker#1

masterworker#2．．．

job pool (EP)!
!
!

worker#3!
!
!
worker#N

15

CCS HPC Seminar 2024

並列処理における通信と同期•••

各並列プロセスは何らかの関係を互いに持ち、情報を交換する必要がある
逐次処理では本来必要のない処理が追加される例）domain decompositionの例での境界部分のデータ参照
通信(communication)が引き起こす演算性能への影響– 通信そのものにかかる正味時間：
逐次処理では存在しなかったオーバヘッドを引き起こす– 待ち合わせ（同期:synchronization）によって生じる処理の停滞：
負荷不均衡（load imbalance）によって生じる、無駄な待ち時間。各プロセス内の処理が他のプロセスからのデータ待ちで停止•

効率的な並列処理を行うためには、通信と同期のオーバヘッドを最小限に食い止める必要がある（並列処理効率の単元で後述）

16

CCS HPC Seminar 2024

並列処理における通信の形とコスト•

並列処理アーキテクチャの様式に依存– 分散メモリ型アーキテクチャ：
各プロセスは互いに明示的にデータを交換（送受信）し合う⇒message passing (send, receive, ...)
– 共有メモリ型アーキテクチャ：
各プロセスは共有するメモリへのデータの読み書きで通信し合う⇒shared memory access (write read, ...)•

通信のコスト– message passing の場合、通信ペア同士がネットワーク上でどのような位置にいるかが重要⇒「近接な通信」（物理的に近距離にいるプロセッサ同士の通信）は低コスト、かつシステム全体の通信性能に与えるインパクトが小さい– shared memory accessの場合、通信ペア同士とメモリの物理的な位置（必ずしも全てのメモリがプロセッサから等距離にあるとは限らない）が重要– いずれの場合も、底辺にあるハードウェアの性能に左右される

17

CCS HPC Seminar 2024

同期処理のコスト• 同期のオーバヘッド（分散メモリの場合）– 並列計算機を構成するネットワークの形状と同期処理のアルゴリズ
ムに強く依存– システムの規模（並列プロセッサ台数）に強く依存• 同期のオーバヘッド（共有メモリの場合）– 共有メモリアクセスにおける同期処理がハードウェアでサポートされているかどうか（ロック機構等）– 同期に関わる並列プロセス数に強く依存

18

CCS HPC Seminar 2024

並列処理の性能メトリック•

並列処理の目的は速度、問題規模(メモリ＆ディスク）、精度等様々だが、最も本質的なのは速度向上•

並列処理を行った結果、当然総演算処理時間が短縮されることが期待される．．．が、実際の速度が思ったほど上がらないことがしばしば起こる

•
•

•
•

特にシステム規模（プロセッサ数）の増大が性能に結びつかない場合が大きな問題となる⇒並列処理のscalability（拡張性）
並列処理による性能向上を正しく測定するメトリックが必要並列度（degree of parallelism）の定義– 問題の持つ並列度：問題の中に並列処理可能部分がどれくらいあるか（並列性とも呼ぶ）– システムの持つ並列度：システムの並列リソース数（一般的にはプロセッサ数）

19CCS HPC Seminar 2024

並列処理システムの性能指標（１）•

速度向上率– 1プロセッサで実行した時の時間をT1とする。
– pプロセッサで実行した時の時間をT(p)とする。
– s(p)=T1/T(p)s(p)を「プロセッサ台数p台の速度向上率」と呼ぶ。s(p)が1以上であれば速度が上がったことになる。
– 理想的にはs(p)=p。（p台のプロセッサを投入した結果、p倍の速度が得られた）
s(p)=pが理想⇒ linear speed-up

これでも十分（性能が単調増加）pの増加に従いsaturation
する（多くの場合）

s(p)プロセッサ台数p20

CCS HPC Seminar 2024

並列処理システムの性能指標（２）•並列化効率– 速度向上率s(p)はpに依存するので指標として不便– 「s(p)=pが理想的」ということに着目し、実際にはそれがどれくらい達成できたかを「効率」として考える– e(p)=s(p)/pe(p)はpに寄らず、1に近いほど理想的（通常は1以下）
e(p)=1が理想⇒ linear speed-up

1

これでも十分（効率が低下しない）

e(p)pの増加に従いsaturation
する（多くの場合）
プロセッサ台数p21

CCS HPC Seminar 2024

Ideal speed-up vs Super-linear• 速度向上率カーブにおいて– 緑：100%効率の理想線形(ideal speed-up)– 青：線形向上 (linear speed-up)– 黒：通信等にボトルネックがある
場合（一般的）– 赤：超線形 (super linear)s(p)• なぜ super linear が起きるか？

プロセッサ台数p• 基本的にidealまたはlinearである並列処理において• プロセッサ台数 p が増えても効率が落ちず• 全体の問題サイズが一定だと各プロセッサの割り当て領域サイズが小さいため• 主にキャッシュが効いて（例：全データがキャッシュに収まる）プロセッ
サ当たりの性能が大幅に向上• 結果的に１プロセッサの場合を基準とすると p 倍以上の性能になる
22

CCS HPC Seminar 2024

アムダールの法則と並列処理効率•

アムダールの法則– 「処理効率はそれを構成する個々の要素の平均効率で決まるのではなく、一部の非効率部分によって律速される」•並列処理におけるアムダールの法則– 逐次処理における実行時間T1が並列処理可能部分Tpと並列処理不可能部分（逐次処理のみ可能）Tsから成ると仮定

T1 = Tp + Ts
– Tp部分について、p台のプロセッサで理想的な並列化ができるとすると、pプロセッサ投入時の実行時間T(p)はT ( p) = Ts + Tp / p– プロセッサ台数pを無限大にするとT ( p) = Tsp→∞

– この時e( p) = s( p) / p = (T1 / (Ts + Tp / p)) / p = (Ts + Tp ) / (Ts * p + Tp ) = 0p→∞

従って、プロセッサ台数pをいくら増大しても、Tsが存在する限り並列処理効率の極限値は常に0になってしまう

23

CCS HPC Seminar 2024

Scalableな問題
••

•

•

実際、どんな問題にも必ずTsは存在し、並列化におけるscalabilityには限界がある「大規模並列」「超並列」は無意味か？
⇒Tsが無視できるぐらいTpの大きな問題を想定すればよい⇒scalable(拡張性のある）問題
大規模科学技術計算の多くがscalableな問題
ただし、Tsが問題規模またはシステム規模(p)に応じて増大しないよう注
意が必要
実問題上で、それがシステム規模に応じてscaleしているかどうかを見極めるための新しいメトリックが必要⇒並列処理の粒度（granularity）

24

CCS HPC Seminar 2024

Scalability: Strong vs Weak
• 並列システムの規模を大きくする際、対象問題のサイズをどう考えるか？
– 全体の問題サイズは変わらず、システムの並列度を上げる⇒ 各プロセッサに割り当てられる問題領域は小さくなる⇒ 通信等のオーバヘッドは相対的に大きくなる⇒ Strong Scaling– プロセッサ当たりの問題領域は変わらず、システムの並列度を上げる⇒ 全体の問題サイズがプロセッサ台数に応じて（比例して）大きくなる⇒ 通信等のオーバヘッドは相対的に（ほぼ）一定⇒ Weak Scaling• strong scaling は weak scaling に比べ遙かに難しい– strong scaling = 一定問題をいかに速く解くか (time-to-solution)– weak scaling = 一定時間でいかに大規模な問題を解くか (scalable)
25

CCS HPC Seminar 2024

並列処理の粒度（granularity）•

並列処理性能を低下させる最大要因は通信と同期のオーバヘッド– 逐次処理にはなかった余計な時間が発生– 同期により演算も通信もしていない待ち時間が発生••

一定時間、通信も同期も発生しない状況は逐次処理を行っているのと等価である⇒この時間が長いほど処理効率が高い
通信・同期を伴わない処理部分の相対的評価– この部分が長い⇒「粒度が粗い」(coarse grain)– この部分が短い⇒「粒度が細かい」(fine grain)•

一般に、問題規模を固定のままシステムの並列度を上げると、並列処理の粒度が細かくなる⇒ strong scaling が難しい最大の理由

26

CCS HPC Seminar 2024

domain decompositionの例
....

b[5]

b[6]

b[7]

b[8]

b[9]

....

a[5]

a[6]

a[7]

a[8]

a[9]

....

粗粒度並列処理....
••

各プロセスは2点分の要素を処理
隣接プロセスに対し2点分のデータを送り、2点分のデータを受け取る

....

b[5]

b[6]

b[7]

b[8]

b[9]

....

a[5]

a[6]

a[7]

a[8]

a[9]

....

細粒度並列処理....
••

各プロセスは1点分の要素を処理
隣接プロセスに対し2点分のデータを送り、2点分のデータを受け取る
27

CCS HPC Seminar 2024

並列処理性能を左右する要因•

システム並列度を上げた場合、それに応じて問題規模を大きくすれば粒度を下げずに済む (weak scaling)•

粒度の概念は相対的なものなので、各アプリケーションにおいてこれを計る尺度を設けておくべき⇒例えば通信の前後に計時機能を組み込む等•

システム並列度を上げた場合、常に並列処理効率を観測し、リソースの有効利用に注意を払うことが望ましい
性能ボトルネックの最も大きな要因が通信と同期のオーバヘッド、すなわ
ち処理の細粒度化
アプリケーション自体が本質的に細粒度である可能性があるが、これはアルゴリズムの修正、プログラミングの工夫等で対応しなければならない•••

粒度を上げるために、従来と異なる通信パターンが発生してしまうような場合は注意が必要⇒システムの通信・同期性能自体が変わってしまう

28

CCS HPC Seminar 2024

負荷バランスと並列処理効率• 負荷バランス：各並列プロセスに与えられる処理の量は均一であることが望ましい
例）一斉同期を取る場合にボトルネックとなるプロセスが生じると処理が停止する• 均質なデータに対する単純なデータ並列では、基本的に負荷バランスは暗黙のうちに保たれる• 負荷バランス問題が生じる場合– 不均質なdomainに対する分割– parameter searchにおいて個々の処理量がparameterに依存する
場合– 問題空間が一様でなく、「境界」「内点」等が存在する場合（例：周期境界条件でない問題）

29

CCS HPC Seminar 2024

負荷バランスを考慮した問題分割• domain decompositionでは、問題空間をなるべく粗く分割（隣接点を１つのプロセスに閉じ込める）することが理想• 問題空間が不均質な場合、この方針では負荷バランスが崩れることがある• 問題空間の形状を無視し、並列プロセス間の処理量が均等になるよう分割を変更することも必要⇒ただし通信が近接でなくなることがあるので要注意！
⇒さらに処理粒度が低下する可能性もある

30

CCS HPC Seminar 2024

具体例：cut-off付きMD• MD (Molecular Dynamics)等の実例– n次元空間上にP個の粒子があり、粒子間力の相互作用をシミュレーションする– クーロン力のようななだらかなポテンシャルではなく、距離に応じて急激に縮小するポテンシャル（井戸型等）を持つため、力の影響する空間範囲にcut-off半径が存在する

cut-off半径• 「全対全」のinteractionではないため、通信コストを削減するためにデータ交換（通信）範囲をcut-off半径内の粒子（を持つプロセッサ）に限定したい– 空間をdomain decompositionし、プロセスに割り当てられた部分空間（cell）内の粒子を処理対象とする⇒cellサイズをcut-off半径以上にすれば、隣接cellを受け持つプロセスとのみ通信すればよい（cell mapping method）

注目する粒子31

CCS HPC Seminar 2024

cut-off付きMD（続き）••••

粒子は他の粒子との力の相互作用により時間と共に移動するので、右図のように特定cellに固まる可能性がある
cell単位で並列プロセスにマッピングすると負荷バランスが崩れる

計算負荷の軽いcell

負荷バランスを保つには、プロセス内の粒子数（cell数ではなく）をなるべく均一にする必要がある方法– 1) 粒子数/cellの密度に応じ、プロセスに割り当てるcell数を一定時間毎に再調整する– 2) cell数がプロセス数より遥かに多い場合、cellをblockでプロセスにマップせず、cyclicにマップする– 3) cellマッピングを諦め、粒子単位での管理を行う

計算負荷の重いcell32

CCS HPC Seminar 2024

cut-off付きMD（続き）
••
•

•
•

方法1)
cellとプロセスの割り当てを変更するには大量のデータを頻繁に移動しなければならない。また、cell間の通信は隣接するとは限らない（非定型形状）。
方法2)
cyclic分割により比較的負荷分散が容易にできる。ただし、隣接cellが隣接プロセスにマップされなくなるため、通信距離が長くなる。
方法3)
cell法を捨てるため、通信相手プロセスがどこにいるかを、毎回テーブル（粒子とプロセスの関係管理）引きによって求め、かつ通信距離も長くなる。
⇒決定的な方法はない
問題の特性（粒子の固まり易さ、ポテンシャルの性質等）に依存するため、一般解はない
極端な負荷非均衡が生じている場合、通信コストを犠牲にしても負荷バランスを保つ価値があるかもしれない

33

CCS HPC Seminar 2024

まとめ• 大規模科学技術計算における並列処理の重要性• 並列処理の典型的な手法、並列化方法• 並列処理効率の概念• アムダールの法則• 並列処理のscalabilityと処理粒度の関係• 負荷分散問題

34

CCS HPC Seminar 2024

レポート課題[1] 以下の仮定のの下に、並列処理性能と並列処理効率について設問に答えよ。
単一プロセッサである問題を処理した時、その実行時間がT1[sec]だったとする。
この問題はp台のプロセッサで完全に並列化可能だが、その際の並列処理中に通信時間Tcomm(p)だけのオーバーヘッドが発生するとする。
(a) p台のプロセッサでこの問題を解いた時の実行時間T(p)はどうなるか？
(b) Tcomm(p) = αp だった場合とTcomm(p) = αp2だった場合を比較し、並列処理通信時間が並列処理性能に与えるインパクトについて簡潔に記述せよ。
(c) Tcomm(p) = αpのケースについて、速度向上率s(p)と並列処理効率e(p)をそれぞれ式で表せ。
(d) 上記(c)において、10台のプロセッサで処理した場合に並列処理効率を50%以上に保つためのαの条件をT1を用いて示せ。

35

CCS HPC Seminar 2024

レポート課題（続き）[2] 2021年11月以降の6回分のTOP500リストを調べ以下の設問に答えよ。
(a) 2022年6月に起きた特徴的な事象は何か？
(b) 2021年11月と2024年5月一位のマシンについてプロセッサアーキテクチ
ャの特徴について簡単に比較せよ。
(c) 2021年11月と2024年5月のTOP10システムのLinpack性能の合計値を比べ、2年半の間にどの程度の性能差が生じているかを述べよ。
(d) 最新のリストでヨーロッパでは保有する国が散らばっている。その理由について簡単に述べよ。

36