（様式 20）成果報告書

TSUBAME 共同利用 平成 26 年度 学術利用 成果報告書

利用課題名 ポストペタ時代の大規模並列数値計算のための技術開発
英文：Research and Development on Large Scale Parallel Numerical Computations in the Post-Peta Era
利用課題責任者 須田礼仁
Reiji SUDA
東京大学 情報理工学系研究科
Graduate School of Information Science and Technology, the University of Tokyo
URL http://sudalab.is.s.u-tokyo.ac.jp/~reiji/sudalab.html
邦文抄録（300 字程度）
TSUBAME, 京コンピュータなど，ペタフロップスを達成するスーパーコンピュータが広がってきている．今後さらなる性能向上が期待されているが，その性能を十分に引き出すためには 100 万コア以上の並列性，深いメモリ階層，ネットワークの遅延などを手なずける必要がある．本研究ではこのような視点から，計算科学と計算機科学の融合・協力により次世代の超並列超高性能計算科学ソフトウェアの構成方式，アルゴリズム，実装技術を開発してゆく．本稿では，通信削減 CG 法のブロック化と，TSUBAME を用いた全点対最短経路問題の並列解法について報告する．
英文抄録（100 words 程度）
Supercomputers over peta-flops are getting widespread, such as TSUBAME and K-computer. The
progress is expected to continue in the following years, but to attain their highest performance, we needto tame several problems such as high parallelism of million order, deep memory hierarchy, network
latency, and so forth. In this research, in a collaboration of computational science and computerscience, we are researching on construction methodology, algorithms, implementation techniques ofextremely parallel high performance computational science software of the next era. In this report,
research on block version of communication avoiding CG method and parallel solver of all-pairs shortest
path problem on TSUBAME.

Keywords: ５つ程度
Post-peta supercomputer, communication avoiding algorithms, graph algorithms, all-pair shortest pathproblem
背景と目的
半導体技術の進歩により，TSUBAME, 京コンピューを用いた全点対最短経路問題の並列解法について報告する．

タなど，ペタフロップスを超えるスーパーコンピュ

CG 法は Krylov 部分空間法のひとつであり，対称ータが増えてきている．今後はさらに，2020 年ごろ

正定値な疎行列を係数とする連立一次方程式の解法と言われるエクサフロップス計算機に向けて研究がとして広く用いられている．CG 法を分散メモリ型の進められている．エクサフロップス級の計算機では，スーパーコンピュータに実装すると，疎行列ベクト

その高い性能を高い並列性と深い階層性によって生ル積と内積において通信が必要となり，バンド幅とみ出すものと考えられている．エクサ級の性能を得遅延の両面で通信オーバーヘッドがかかる．プロセるには，たとえば 100 程度の SIMD 並列性を持つコッサ数が一段と増加したポストペタの計算機では，アが 100 万コア必要である．これは汎用コアではな

通信オーバーヘッドが非常に重要な問題になると考くアクセラレータである可能性も高い．また，メモえられている．これを解決するために提案されていリ周りの性能維持や低消費電力化のために深いメモるのが s ステップ法であり，これは CG 法の s 反復リ階層が用いられると考えられる．本研究では，特分に含まれる通信を一度にまとめて行うものである．に計算科学をターゲットとして，次世代の超並列計

しかし，s ステップ法には数値的な安定性という課算機のためのソフトウェア技術を研究している．本

題がある．我々は数値的に安定なアルゴリズムとし稿では，ブロック化した通信削減 CG 法と，TSUBAMEて ， ブ ロ ッ ク 化 Chebyshev 基 底 CG 法 （ Block（様式 20）成果報告書
Chebyshev Basis Conjugate Gradient: BCBCG 法）の BCBCG 法では，Chebyshev 多項式を用いて数値的を提案している．BCBCG 法の通信を真に最小にするに安定に s 次元を一度に拡大する．これは s ステップ法には，通信削減された行列分解アルゴリズムと通信として知られる方式であり，これにより大域的な集団通削減された行列冪カーネルが必要である．我々はこ信を削減できる．しかし，この方法は Arnoldi 法によってれらの実装を進めている．

探索方向を直交化する従来の CG 法のアイデアと一致

また，従来の並列計算においては並列化効率が重しない．そこで我々はブロック化によりこの問題を軽減す要視されてきた．そのためにはプロセッサあたりのることを提案している．ブロック化によっても 1 反復で拡問題サイズを大きく保つ必要があり，弱スケーリン

大する Krylov 部分空間の次元を増加させることができグが広く採用されてきた．しかし，TSUBAME や京コるからである．

ンピュータをはじめとする大規模並列マシンの登場

しかしブロック化の効果，特に反復回数が少ないとこによってこの考えには限界がきた．さらに応用分野

ろでの効果は，入力となる右辺行列の性質によって大きにおいても，非常に多くのプロセッサを用いて与えく左右される．このため，QR 分解のような方法により，ブられた問題サイズの最短時間での解決，すなわち強ロック探索方向ベクトルを改善する必要が，しばしばあスケーリングが要請としてある．非常に多くのプロる．この際，通信削減という性質を維持するためには，こセッサを用いればプロセッサ１つあたりの問題サイの QR 分解などに TSQR (Tall Skinny QR) 法などの通ズは非常に小さくなり，計算自体にかかる時間に対信削減アルゴリズムを用いる必要がある．我々は，してプロセッサ間の通信にかかる時間の割合が大きTSUBAME2.5 において Intel MKL を利用した TSQR 法

くなってくる．よって通信にかかる時間をいかに減を実装した．

らすかということを考えることは重要である．本研

また，BCBCG 法では Chebyshev 基底も生成するの究では全対最短経路問題を例題として，TSUBAME にで，行列冪カーネルも必要である．行列冪カーネルのおける強スケーリング実装を行った．通信オーバー実装は係数行列の非零パターンにより最適な実装方式

ヘッドを通信隠蔽によって軽減し，ナイーブな実装が大きく異なる．現在行列冪カーネルの実装は開発中

では達成できなかったプロセッサ数の増加とともにであり，今後これに注力して進める予定である．

実行時間が小さくなるという結果および，どのよう次に，全対最短経路問題の並列解法について報告な実装が問題サイズに対して適しているかという知する．我々の実装は Buluc らによる Solving path

見を得た．

problems on the GPUs, Journal of Parallel
Computing,36, pp.241-253(2010)で提案されている

概要
本プロジェクトでは，ナノサイエンス，バイオインフォマ

1GPU 実装をもとにしている．基本的なアルゴリズム
は以下のようになる．

ティクス，コンピュータサイエンスの研究者の協力により，Function APSP(A)

日本最大の GPU 搭載スーパーコンピュータである

if n < bTSUBAME を用いて，共同研究により次世代の計算機

thenのためのアルゴリズム，並列化手法，最適化，プログラミングモデル，アプリケーションの新たな展開に関して研究を行っている．以下では，平成 26 年度に行った，通信削減 CG 法の成果と，全点対最短経路問題の強スケーリング実装について報告する．

Floyed-Warshall 法で計算する
else
A を 2 等分してA≔ APSP A

まず，通信削減 CG 法の研究概要について説明する．

A≔A//*1

従来型の CG 法では，Krylov 部分空間を拡張するのにA

≔

//*2

Arnoldi 法を用い，1 反復で 1 次元を拡張している．我々A

≔A

⊕とする

//*3

（様式 20）成果報告書
信コストに比べて計算コストが時間・電力ともに劇A≔ APSP AA≔//*4A≔A//*5A≔⊕

的に少ない場合において有効である．
丸め誤差に伴う安定性の問題を軽減するには，//*6

Chebyshev 基底のサイズとともに，ブロック化サイ

end ifズもてきせつに選択してやる必要がある．Chebyshev

end function

基底サイズの増加とブロック化サイズの増加の 2 つこのアルゴリズムでは，コード中で*1 の計算と*2による反復回数の削減程度を比較すると，多くの場で示した計算，および*4 と*5 で示した計算が自明に合において Chebyshev 基底サイズの増加のほうが効並列化できる．さらに，APSP を完了した行列 A につ果が大きい．しかし，右辺行列を適切に選ぶことにいては冪等性 Aより，ブロック化サイズの効果を高めることができ*3 における AA がなりたつことに注意すると，は *2 で計算した結果ではなく，ることが観測されている．

*2 で計算する前の結果でもよいことがわかる．これ

TSQR の実装においては，プロセッサ数の適切な選により，*2 と*3 も並列化することができる．これら択が重要であることがわかっている．すなわち，プの考察に基づき，我々の 2GPU 実装では，*1 と*3 をロセッサ数を多く選びすぎると，TSQR の性能が急速1 つの GPU が計算している間にもう 1 つの GPU が*2に低下する．最適なプロセッサ数の自動的な決定はを計算し，また，*4 と*5 を 1 つの GPU が計算してい今後の課題である．

る間にもう 1 つの GPU が*6 を計算するという方式を次に，全対最短経路問題の並列解法について報告す採用した．これにより，通信遅延が隠ぺいできるよる．1GPU 実装（1GPU と称する）と，通信隠蔽を用うになった．

いない 2GPU 実装（2GPU と称する）と，2GPU で通また，複数のノードを用いた実装では 2 分割では信隠蔽を用いてさらに問題サイズが 512 以下になp の分割を用いている．そして，1 つのると 1GPU に切り替えるような実装（2GPU opt とGPU に 1 つの MPI プロセスを割り当て，2 次元正方称する）の 3 つの実装につき，を問題サイズごとグリッドで分割することによって並列化を施した．に実行時間(ms)を計測したものを表 1 に示す．

なく p

複数ノード実装についても 2GPU の場合と同じ原理を用いて通信隠蔽を施した．この方式ではプロセッ

頂点数

1GPU

2GPU

2GPU opt

サの相当数が遊ぶため，並列化効率は高くないが，

1024

11.95118.95011.000

できるだけ多数のノードに計算を分散させることに

2048

44.16675.26935.776より，強スケーリングを目指した．

4096

249.25239.71178.988192

1784.11403.31215.016384

13831.5

9827.39275.3

結果および考察
まず，BCBCG 法については，概要で説明したように，TSQR 法は実装が完了したが，行列冪カーネルに

表 1. ノード内並列化による性能．単位は ms．下線は，実行時間最小のものを示す．

ついての実装を進めているところである．これまでに Matlab を用いた小規模計算で数値的な性質を分

表 1 から，2GPU で通信隠ぺいを行った実装が高速析しているので，ここではそれについて報告する．

であり，通信削減の効果が高いことがわかる．

BCBCG 法では，CG 法に比べて少ない反復回数で収また，複数のノードを用いた実装について通信束することができている．すなわち，ブロック化に隠蔽を用いた場合の性能を，行にプロセッサ数より，分散メモリ並列計算器における大域的な通信(p)，列に頂点数(n)をとり，実行時間(s)をまとめを削減することができる．ただし計算量は CG 法よりたものが表 2 である．表 2 においてn/ pの値が 1も多く，将来のスーパーコンピュータにおいて，通プロセッサあたりに割り当てられる問題サイズを表（様式 20）成果報告書しているが，これが 1024 以上の場合においては，プ並列実装では，1 ノード上の 2 つの GPU を使用しロセッサ数の増加に伴って実行時間がより短くなるた実装と，複数のノードを使用した実装の 2 つをことがわかる．1024 未満になる場合にそうならない実装した．そしてそれぞれの実装について，冪等のは，1 プロセッサあたりの問題サイズが十分な大性を用いて通信隠蔽を施した実装も提案した．実きさが無いため GPU の計算効率が低下してしまうた験結果としては全対最短経路問題に対して、頂点めである．

数が 512 以下であれば 1 つの GPU を用いた実装
が，頂点数 1,024 以上 4,096 以下では 1 ノード上

2048

4096

8192

16384の 2 つの GPU を用いた実装が，それ以上の頂点数

40.05285

0.22647

1.36530

9.63585の場合には複数のノードを用いた実装がそれぞ

160.08674

0.17608

0.57560

3.17227

れ最短時間を記録した．今後の課題としては，行640.22080

0.230080.351391.20455

列積を GPU 上で計算する際に，行列の大きさがあ0.52978

0.77171

0.96503

る程度大きくないと GPU での計算の効率が著しくpn256下がってしまうということが分かっているので，
pn3276865536

1310722622144

小さなサイズの行列に特化したような GPU 実装を考えることで全体の実行時間を小さくすること

472.3535

16

21.6361

161.13364

6.7252245.6037

338.770256

2.52223

13.8227

93.5249に寄与できると思われる．

694.174

表 2. ノード間並列化による全点最短経路問題の並列解法の性能．行はプロセス数，列は問題サイズを示す．単位は ms．下線は，各サイズで実行時間最小のものを示す．
まとめ、今後の課題
本研究では，次世代ポストペタスーパーコンピュータにおける計算科学の手法開発を行っている．本稿では，ブロック化した Chebyshev 基底 CG 法による通信削減と，全対最短経路問題の強スケーリング実装について報告した．
BCBCG 法では，ブロック化により収束性を安定化することができた．ブロック化サイズを増加させることにより，数値的な安定性を損なうことなく，大域的な通信のオーバーヘッドを削減することができる．しかし，Chebyshev 基底のサイズに比べてその効果は小さい．今後はブロック化サイズの効果を高める手法の開発に取り組みたい．また，BCBCG 法の並列実装に必要な TSQR 法は実装したが，行列冪カーネルは現在進行中である．TSQR の最適化とともに，行列冪カーネルに取り組む予定である．

全対最短経路問題に対する TSUBAME 2.5 上での