（様式 20）成果報告書

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

利用課題名 ポストペタ時代の大規模並列数値計算のための技術開発
英文：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 万コア以上の並列性，深いメモリ階層，ネットワークの遅延などを手なずける必要がある．本研究ではこのような視点から，計算科学と計算機科学の融合・協力により次世代の超並列超高性能計算科学ソフトウェアの構成方式，アルゴリズム，実装技術を開発してゆく．本稿では，TSUBAME を用いたブロック化チェビシェフ基底共役勾配(BCBCG)法、Tall Skinny QR (TSQR), 通信削減行列冪カーネル（CA-MPK）の実装について報告する．
英文抄録（100 words 程度）
Supercomputers over peta-flops are getting widespread, such as TSUBAME and K-computer. Theprogress is expected to continue in the following years, but to attain their highest performance, weneed to 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 andcomputer science, we are researching on construction methodology, algorithms, implementationtechniques of extremely parallel high performance computational science software of the next era. In
this report, research on Block Chebyshev Basis CG (BCBCG) method, Tall Skinny QR (TSQR),
Communication-Avoiding Matrix Powers Kernel (CA-MPK) on TSUBAME.

Keywords: ５つ程度
Post-peta supercomputer, communication avoiding algorithms, block CG method, TSQR, CA-MPK
背景と目的
半導体技術の進歩により，TSUBAME, 京コンピュータなど，ペタフロップスを超えるスーパーコンピュ

Tall Skinny QR (TSQR), 通信削減行列冪カーネル(CA-MPK) の TSUBAME における実装について報告する。

ータが増えてきている．今後はさらに，2020 年ごろ

CG 法は Krylov 部分空間法のひとつであり，対称と言われるエクサフロップス計算機に向けて研究が正定値な疎行列を係数とする連立一次方程式の解法進められている．エクサフロップス級の計算機では，として広く用いられている．CG 法を分散メモリ型のその高い性能を高い並列性と深い階層性によって生スーパーコンピュータに実装すると，疎行列ベクトみ出すものと考えられている．エクサ級の性能を得

ル積と内積において通信が必要となり，バンド幅とるには，たとえば 100 程度の SIMD 並列性を持つコア遅延の両面で通信オーバーヘッドがかかる．プロセが 100 万コア必要である．これは汎用コアではなくッサ数が一段と増加したポストペタの計算機では，アクセラレータである可能性も高い．また，メモリ通信オーバーヘッドが非常に重要な問題になると考周りの性能維持や低消費電力化のために深いメモリえられている．これを解決するために提案されてい階層が用いられると考えられる．本研究では，特にるのが s ステップ法であり，これは CG 法の s 反復分計算科学をターゲットとして，次世代の超並列計算に含まれる通信を一度にまとめて行うものである．

機のためのソフトウェア技術を研究している．本稿

しかし，s ステップ法には数値的な安定性という課では，ブロック化チェビシェフ基底 CG (BCBCG) 法、題がある．我々は数値的に安定なアルゴリズムとし（様式 20）成果報告書て ， ブ ロ ッ ク 化 Chebyshev 基 底 CG 法 （ Block解のアルゴリズムである。通信削減 CG 法の数値安定

Chebyshev Basis Conjugate Gradient: BCBCG 法）

性と収束の速度を維持するため、QR 分解のような方を提案している．本稿では TSUBAME での実装を報告

法は必要である。しかし、従来の QR 分解アルゴリズムするが、ブロック化の効果は高くなく、右辺行列のは、並列化された後、集団通信の数は O(n) である生成に工夫が必要と思われる。また、BCBCG 法の数（n は行列の行また列の数である）。よって、そのような値的安定性を改善するために QR 分解を利用するこ

QR 分解を使うと、通信削減 CG を使う意味がなくなっとを想定して、通信削減された QR 分解アルゴリズムてしまう。TSQR は 2 分木の Point-to-Point (P2P) のである Tall Skinny QR (TSQR) を TSUBAME に実装し通信パターンで，プロセス間の情報を同期する。これにた。Scalapack の QR 法よりも高いスケーラビリティより、全部の通信のオーバーヘッドは１回の集団通信が得られた。また、BCBCG 法の内部で必要となる通のオーバーヘッドと同等にすることができる。我々は，

信削減行列冪カーネルとして、PA1 と呼ばれるアルTSUBAME2.5 に お い て Intel MKL を 利 用 し たゴリズムの実装に取り組んでいるところである。

TSQR 法を実装した。
最後には、行列冪カーネルの実装の進捗について、説明する。BCBCG 法では Chebyshev 基底も生成す概要
本プロジェクトは、ナノサイエンス，バイオインフォマるので，行列冪カーネルも必要である。我々は、

ティクス，コンピュータサイエンスの研究者の協力により，Avoiding

communicationinsparse

matrix

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

computations 、 IPDPS 2008 で 提 案 さ れ て い る

TSUBAME を用いて、共同研究により次世代の計算

Communication-avoiding Matrix Powers Kernels

機のためのアルゴリズム、並列化手法，最適化，プロ(CA-MPK) の PA1 を TSUBAME2.5 において実装しグラミングモデル，アプリケーションの新たな展開に関た。原則的に CA-MPK PA1 は一回の集団通信でして研究を行っている。以下では、平成２７年に行った，P0(A)x, P1(A)x,…, Pk(A)x を計算できる。k は行列多通信削減アルゴリズムの成果について報告する。

項式の次数で、x はベクトルである。CA-MPK PA1 の

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

実装は四つの部分からなる。第１に、Breadth First

従来型の CG 法では，Krylov 部分空間を拡張するのSearch (BFS) でデータ間の依存関係を計算する。に Arnoldi 法を用いて１反復あたり１次元を拡張していHyper-graph を計算するアルゴリズムも提案されている。我々の Block Chebyshev Basis CG (BCBCG)法

るが、我々の実装では通常のグラフを用いて計算する。

では，Chebyshev 多項式を用いて数値的に安定に s第２に、そのデータの依存関係に基づいて，行列 A の次元を一度に拡大する。これは s ステップ法といて知ら行をプロセス間で分散する。第３に、もとのプロセスでれる方式であり，これにより大域的な集団通信を削減計算できる部分を計算して、同時に、他のプロセスに依できる。しかし、この方法は Arnoldi 法によって探索方存しているデータと依存されているデータをプロセス間向を直交化する従来の CG 法のアイデアと一致しない。

で P2P 通信，あるいは一回の集団通信で交換する。第そこで，我々はブロック化によりこの問題を軽減するこ

４に、もとのプロセスに残っている未処理データの処理とを提案している。ブロック化によっても１反復で拡大すを完成する。CA－MPK PA1 の実装は従来の MPK

る Krylov 部分空間の次元を増加させることができるかの実装より複雑で，ソースコードの行数は大幅にも増えらである。ている。高い性能を出すためには、十分なチューニング

次に、Tall Skinny QR (TSQR) の概要についてが必要である。

説 明 す る 。 TSQR は Communication-optimal
ParallelandSequential

QRandLU

結果および考察Scientific

まず, BCBCG 法について実験の結果および考Computing, 2008 で提案されている通信削減 QR 分察を説明する。実験において使用した行列は The

Factorizations,

SIAM

Journalon（様式 20）成果報告書
University of Florida Sparse Matrix Collection

BCBCG-m1s5

11.50

14.1419.76

51.50

からの bmw7st_1 という行列である。行数と列数は

BCBCG-m5s553.8852.4160.40185.38141,347 で非零元素の数は 7,318,399 である。CG

表１．CG 法と通信削減 CG 法の性能、単位は sec.

法と通信削減 CG 法の Tsubame2.5 における性能

列はプロセス数．

評価を表１に示す。表１に示している実行時間（sec.）
は完全に収束した時間ではなく、残差（residual）が128256512

10242,000 程度までの実行時間である。m はブロック数

CG200200201201で、s はステップ数である。表 2 は残差が 2,000 程度

BCBCG-m1s543434342まで収束するまでの反復回数を示す。表３はそれぞ

BCBCG-m5s544454544

表２．残差が 2,000 になるまでの反復の回数

れの solver が１反復にかかった時間を示す。
表１から、512 プロセスまで、CG 法は BCBCG 法より速いことが分かる。1024 プロセスから BCBCG－

1282565121024m1s5 は CG 法より早くなった。原因は、プロセスの数CG0.022

0.024

0.029

0.525が多くなる場合、使ったノードの数も増えるという点

BCBCG-m1s5 0.267

0.329

0.4601.226にある。ノードが増える時、通信オーバーヘッドも増BCBCG-m5s5 1.224

1.165

1.342

4.213

え 、 通 信 削 減 CG 法 の メ リ ッ ト も 見 え る 。 だ が 、表３．１反復の平均時間

BCBCG-m5s5 は BCBCG-m1s5 より３倍ぐらい遅い。

実験をした時，我々はプロセスの数が多い場合、m の数が増えると、計算に参加した行列のサイズも測った時間が不安定にある現象があった。測った時増える。そのゆえ，ブロックのサイズは収束にあまり間の最小値は表１に記入したが、最大値は表４に載役立たない場合は、m の数が増えれば増えるほど性っている。その原因は、ネットワークの性能が変わっ能は悪くなる。このことは表２に見える。表２に示すよていたと見られる。ネットワークの性能の不安定性もうに m の値を大きくしても収束に全然利かない、むし通信削減を提案した原因の一つである。通信の数をろ、悪い点があると見える。ブロックという技術は入できるだけ減らせるとその不安定性は solver に与え力となる右辺行列の性質によって大きく左右される。

る影響も減らせられることからである。

この実験に使った右辺行列はランダムで生成された512ものであった。右辺行列を工夫することでｍの効果1024を高める技術の開発もこれからの重要な課題であCG

323.70 211.91

る。

BCBCG-m1s5

45.53 208.77

BCBCG-m5s5217.38

表３から、BCBCG 法の１反復のかかった時間はCG 法より多いことがわかる。それは、通信削減法の表４．測った時間の最大値共通している問題である。通信の数を減らすため、計算量は増えるようになる。だが、通信削減法の収次 に 、 TSQR の 性 能 を 評 価 す る 。 図 １ に束の速度は CG 法より速いから、通信オーバーヘッ

Tsubame2.5 において、我々は実装した TSQR 法のドは大きい場合、計算量のオーバーヘッドが補償で性能と Intel の MKL に実装した Scalapack QR のきる。なお、これまでに実装した BCBCG 法は十分性能を示す。MKL の Scalapack QR の実装の性能にチューニングされていない。今後、BCBCG の実装は，最初に我々の実装した TSQR より速かったが，の性能をチューニングする予定である。

プロセス数が 128 を越えた後、プロセス数を増やすほど悪くなる。原因は，MKL の Scalapack QR の実CG

1282565121024

装にプロセス数が増えた時、集団通信のオーバーヘ

4.53

4.77

5.81105.51

ッ ド も 増 え る た め であ る 。だ が 、我 々 の 実 装 し た（様式 20）成果報告書
TSQR 法は、プロセス数が 2048 まで、よい性能を維ィ が 高 い が 。 通 信 パ タ ー ン の 変 更 や持できる。TSQR 法の実装では，主に P2P 通信を使multithreading による性能の最適化がまだ実施でった。従って，通信オーバーヘッドはプロセス数と一きていない。これらの性能の最適化もこれから取り緒に増えることはない。

組みたい課題である。
CA-MPK については，hybrid programming という技術を使っての実装に取り組みたい。そして、実装の性能の最適化もこれからの課題である。

図 1. TSQR と MKL Scalapack QR 性能比較。
縦軸は性能，単位は sec. 横軸はプロセスの数。r は行列の行数，c は列数を示している
我々は CA－MPK PA1 も実装した。CA－MPK
PA1 法は計算量が普通の MPK より増え、メモリも多 く 必 要 で あ る 。 し た が っ て 、 MPI+X の よ う な
hybrid programming という技術を使わなければ性能 が 出 せ な い と 予 想 さ れ る 。 我 々 は MPI ＋OpenMP という組み合わせを試した。Tsubame2.5に OpenMPI，MPICH2 と MVAPICH の 3 つのMPI バージョンがある。その中、Tsubame2.5 のOpenMPI では multithreading の機能が使えないようである。我々の MPICH2 と MVAPICH でもまだ成功していない。原因はまだ調査中であり、目下努力している。
まとめ、今後の課題

本研究では、次世代ポストペタスーパーコンピュータにおける計算科学の手法開発を行っている。本稿
では、ブロック化した Chebyshev 基底 CG 法による通信削減と,通信削減 CG 法にとって重要通信削減カーネルについて報告した。
BCBCG 法では，Chebyshev 基底のサイズに比べてブロックサイズの効果は小さい。今後はブロック化サイズの効果を高める手法の開発に取り組みたい。そして、実装の性能をチューニングしたい。
TSQR 法では，今の実装の性能のスケーラビリテ