7th Symposium

学際大規模情報基盤共同利用・共同研究拠点公募型共同研究 平成２７年度採択課題

15-NA24

遠藤敏夫（東京工業大学）

超大規模シミュレーションのためのアーキテクチャ特性を考慮した通信削減技術
副代表者：中島研吾(東大)
共同研究者：松岡聡、額田彰、長坂侑亮(東工大)、片桐孝洋、大島聡史(東大)、岩下武史(北大)本プロジェクトの目的：

将来のスパコンアーキテクチャ上
では、メモリウォール問題のさらなる悪化が予想され、様々なシミュレーションのさらなる大規模化と高速化の両立の妨げになる。

アルゴリズムの特性を考慮した、データ通信（ノード間・ノード内メモリ階層間）の削減技術の研究・異種アーキテクチャ上での評価• 研究項目(A) 疎行列を主な対象とした、メモリレイアウト・通信の最適化• 研究項目(B) ステンシルを主な対象とした、アルゴリズム局所性向上

疎行列計算向け
メモリレイアウト・通信の最適化

ステンシル計算向け
アルゴリズム局所性向上

大規模並列多重格子法の通信最適化
多重格子法（Multigrid）は大規模計算向けスケーラブルな解法であり，次世代ベンチマークHPCGにも採用されている。ノード内・ノード間双方の最適化を行う。

Parallel通信改善

Serial通信改善

ELL (Ellpack-Itpack), Sliced-ELL（S-ELL）
X-ELL-Y-Z：ELLの多くの亜種•

行列ベクトル積（SpMV）に注目1
14
0
1

3 0 0 0
2 5 0 0
1 3 0 0

3 7 4 0
0 0 0 5CGA（Coarse Grid Aggregation），hCGA
Fine

Original

Level=1
Level=2

CGA

Level=m-3

1 2 54 1 34 1 3

3 7 4

3 7 4

1 5

1 5 0(a) CRS(b) ELL

Level=m-2

Level=mMesh # foreach MPI= 1

Coarse grid solver on a single
core (further multigrid)

Coarseオリジナル実装hCGA

各レベルで通信，メッシュ数がプロ
セス当り1のとき1コアに集めてMG継続（Coarse Grid Solver（CGS））

separate arrays
are introduced

hCGA

本研究ではILU系緩和演算子を適用
GS系smootherよりずっと難しい

東大FX10：4,096ノード, 最大17Gメッシュ（コア当り643メッシュ）

sec.

CRS
x1.90

10.00

5.00

0.00
100

1000

10000

SELL+
CGA

100000

hCGA
x1.61

10.0

hCGA
C3, 4,096 nodes
C4, 4,096 nodes
Weak
Scalingsec.

HB 8x2:C0
HB 8x2:C1
HB 8x2:C2
HB 8x2:C3

5.0

120

Parallel Performance (%)

Sliced-ELL
Weak Scaling
20.00

15.00

Process’s data

プロセス数漸減でCGS負担軽減

15.0

hCGAStrong Scaling

10080■ Flat MPI: CGA■ Flat MPI: hCGA
■ HB 16x1: CGA■ HB 16x1: hCGA

60
40x6.27

2000.0Flat MPI

HB 4x4

HB 8x2

HB 16x1

Device memory

cudaMemcpy

CGS（1プロセス）へ早めに移行

1024

CORE#

8192

65536

CORE#

NUS疎行列フォーマットによるメモリ最適化

MPI comm

Outer Temporalloop (Nt/k times)

MPI comm. ofboundaryComputePoints in sub-dom

Inner Temporalloop (k times)
ComputeGrid points

Copy domain
Device  Host

Device memory

MPI comm. ofk boundary

Copy sub-domain
Device  Host

MPI comm

MPI comm. ofk boundary

Process’s data Host memory

Copy gridDevice  Host

1GPUが複数MPIプロセスに共有され実行

Endo, Jin: Software Technologies Coping with Memory Hierarchy of GPGPU Clusters for Stencil Computations, IEEE Cluster 2014

都市気流シミュレーションへの適用 東工大TSUBAME2.5, K20X GPU

デバイスメモリを超えても最大85%の性能維持

8060

最適化

40200

青木尊之（東工大）

CPU版
06

NORMAL

12HH

18243036
Problem Size (GB)

HH_TB

HHTB_MPI

4248

HHTBMPI_OPT54CPU

3次元FDTD法における時空間ブロッキングキャッシュヒット率改善のために行列を列方向に均等分割- 各セグメントはJDSもしくはSELL-C-σに変換- セグメントごとに演算を行い，合算

FDTD法(Finite Difference Time Domain 法)は高周波電磁場解析の標準解法の一つであり、アンテナや電子デバイスの設計に広く用いられる。
時空間ブロッキングの導入により、時間局所性を高めキャッシュヒット率を向上◯Non-Uniformly Segmented (NUS) Formats
リオーダリングによって再利用性が高いベクトル要素を抽出し，部分的な分割を行う
 分割によって生じるオーバーヘッドを削減

東工大TSUBAME Tesla K20X GPU
での性能評価（単精度）

Copy grid
Host  Device

ComputeGrid points

Inner Temporalloop (k times)

Host memory

HHRT上TB

Temporal Loop

Copy sub-domain
Host  Device

HHRT上での実行の様子
NodeCopy domain
Host  Device

Loop overSub-domains

疎行列演算の重要カーネルである疎行列ベクトル積計算（SpMV）の性能はデータフォーマットの選択に大きく影響される。さらに入力ベクトル要素アクセス時のキャッシュヒット率を改善するため、NUSフォーマットを提案している。

提案手法 [Nagasaka, ICPADS2014]◯Segmented Formats

TBなし

ユーザプログラムに対してほぼ透過的に、通常TB実装
プロセス単位のスワップ機構を提供
Outer Temporal
典型的なCUDA+MPI実行の様子
loop (Nt/k times)

NodeCGA

Pure Internal Cells
AUnew3(3,N)

HHRT上の時間ブロッキング実装

メモリ階層利用ランタイムHHRT

Level=m-1

Boundary Cells
AUnew6(6,N)

地下水流れ計算結果

GPUなどにより高速ステンシル計算が可能であるが、小さいデバイスメモリ容量が大規模化を妨げる。ホストメモリの大容量を利用しつつ、時間ブロッキングにより性能を維持し、さらに開発中のランタイム利用により生産性を維持する。

今後の方向性東北大学のNEC社ベクトルマシ
ンSX-ACEなど、異種アーキテク
チャでの評価• コア毎Assignable Data Buffer（ADB）の効率利用など[Nagasaka, ICPADS2014] Yusuke Nagasaka, Akira
Nukada, Satoshi Matsuoka, “Cache-aware Sparse
Matrix Formats for Kepler GPU”, International
Conference on Parallel and Distributed Systems(ICPADS 2014)

冗長計算を伴わない時空間ブロッキング
Skewアルゴリズムを3次元FDTD法で利用可能であることを証明
タイルの更新する領域をタイムステップごとに1格子点分だけずらしていく
1step目の電場更新
1step目の磁場更新
2step目の電場更新
2step目の磁場更新
3step目の電場更新
3step目の磁場更新

時空間タイリングの効果
T2K-Kyodai, 4 thread, 1socketによる実行
4.00E-08

3.3E-08

3.50E-08
3.00E-08

2.2E-08

2.50E-08

Time (sec)

1 2 5

異種メモリを活用する時間ブロッキングと応用

Speed (GFlops)

1 3

1 3 0

ステンシル計算の一般的な実装は局所性の利用が不十分である。
これを改善するため、時間(時空間)ブロッキング(TB)という手法が知られている：
一部領域を取り上げたら、複数のタイムステップを一時に更新  局所性向上

2.00E-08
1.50E-08

1.0E-08

1.00E-08

1.55E-08

5.00E-09
3.10E-22-5.00E-09

Naïve (on cache)NaïveNormal Tiling
1step
5steps10steps
15steps
20steps
25steps

51015

20

25

30

35

40

4550

Tile sizeNaïveな実装手法に対して計算時間は半分以下に

学際大規模情報基盤共同利用・共同研究拠点 第７回シンポジウム
2015年 7月 9日，10日

THE GRAND HALL （品川）