学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

15-NA06

行列分解のタイルアルゴリズムの高並列環境における最適化
鈴木智博（山梨大学・大学院総合研究部）
概要 数値線形代数計算の行列分解に対するタイルアルゴリズムは、行列を小行列（タイル）に分割し、個々のタイルに対して処理を行うことで、細粒度のタスクを大量に生成することが可能であり、高並列な計算環境で効果的に負荷分散が行えるアルゴリズムとして近年多くの研究が行われている。タイルサイズを小さくすることによって、計算資源に対し十分な量のタスクを生成可能である一方で、クラスタシステムでのノード間通信ではサイズの小さな通信が大量に発生し、通信遅延の原因となる可能性がある。また、LU 分解においてはタイルサイズが小さいほど丸め誤差が大きくなることが報告されており、計算環境、問題規模に応じた適切なチューニングが必要である。本研究の目的
は、大規模問題に適用する行列分解のタイルアルゴリズムに対して、タイルサイズチューニング、ノード間通信の最適化を行うことである。また、高並列な計算環境下において高速な実装とするために、アルゴリズムの改良と共に、通信処理の最適化を行う。

1.

共同研究に関する情報っても、その前処理を行う Cholesky、LU、QR などの(1) 共同研究を実施した拠点名

行列分解に多くの時間を要し、これが全計算時間の東京大学情報基盤センター大部分を占めることが多い。そのため大規模な行列分解を高速に実行するソフトウェアが求められてい(2) 共同研究分野る。

■

超大規模数値計算系応用分野

行列分解のタイルアルゴリズムは、行列を小行列□

超大規模データ処理系応用分野（タイル）に分割し、個々のタイルに対して処理を行う□

超大容量ネットワーク技術分野

ことで、細粒度のタスクを大量に生成することが可能□

超大規模情報システム関連研究分野であり、高並列な計算環境で効果的に負荷分散が行えるアルゴリズムとして海外では多くの研究が行われ(3) 参加研究者の役割分担lている。

鈴木智博（山梨大学・大学院総合研究部）

本研究の目的は、大規模問題に適用する行列分アルゴリズム開発、研究総括
ll

解のタイルアルゴリズムに対して、

大島聡史（東京大学・情報基盤センター）l タイルサイズチューニング

プログラム並列化、最適化

l ノード間通信の最適化高坂知寛（山梨大学・大学院総合教育部）を行うことである。タイルサイズを小さくすることによっ実証実験て、計算資源に対し十分な量のタスクを生成可能である一方で、クラスタシステムでのノード間通信ではサ2.

研究の目的と意義イズの小さな通信が大量に発生し、通信遅延の原因

科学技術計算の中で、線形方程式や、行列の固となる可能性がある。また、LU 分解においてはタイル有値問題、特異値問題の数値解法が重要であること

サイズが小さいほど丸め誤差が大きくなることが報告は言うまでもない。一般行列に前処理を適用することされており、計算環境、問題規模に応じた適切なチュで生成された特殊な形状の行列に対して、これらのーニングが必要である。また、高並列な計算環境下に問題を高速、高精度に解くいくつかの数値解法が確おいて高速な実装とするために、アルゴリズムの立されている。しかし、これらの数値解法が高速であ改良と共に、通信処理の最適化を行う必要がある。
1

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

科学技術計算の大規模化に伴って行列を扱うリッド並列化を行う必要がある。また、高速な実数値線形代数計算の大規模化、高速化の要求が高装とするためにメモリ階層を考慮した古典的な最くなっており、高い並列性を持つ近年のハードウ適化以外に、ノード間通信の最適化を行うことがェアの性能を最大限に引き出す行列分解アルゴリ必須である。近年の複雑な計算環境においてこのズムが現在求められている。特に LU 分解（不完ような最適化を行うためには専門的な知識・技術

全 LU 分解）、QR 分解は数値線形代数分野で多用が必要である。

される計算であり、高並列環境における大規模行これまで、このような研究テーマに関して、ア列向けの高速な実装は有用性が高い。

ルゴリズム開発を行う数理的な分野の専門家自身

クラスタシステムにおける標準的な数値線形が並列化を行うことが多かった。しかし近年の計代数ライブラリである ScaLAPACK が近年のハ算機アーキテクチャの複雑化により、効率的に並ードウェアの性能を十分に発揮できていないこと

列化・最適化を行うために高度な知識・技術が必が指摘されて久しいが、現在クラスタシステム上要となり、アルゴリズム開発者とこのような知の多くのアプリケーションがこのライブラリを使識・技術を持った研究者との協業が必須となって用している。これに換わるクラスタシステム向けいる。

数値計算ライブラリを開発するという側面から、本研究の成果物は、大規模並列環境で効果的な国内で最高クラスのスーパーコンピュータを使用実装であることが求められる。そのため、研究室した研究開発を行う意義は非常に高い。

レベルで所有するワークステーションによる小規

前述の通り、タイルアルゴリズムのタイルサイ模ベンチマーク的な実験結果ではなく、申請する

ズチューニングは負荷分散、通信最適化、誤差へ共同研究拠点における計算資源を使用した実用的の影響の面から重要性が高いが、これに関する研な規模の実験結果によって実装の性能を評価する究報告は現在ほとんど見られない。

必要がある。

上記をまとめると以下となる。
l 大規模並列環境における高速な行列分解ル

4. 前年度までに得られた研究成果の概要

ーチンの提供なし

l 国内最高クラスのスーパーコンピュータに

5. 今年度の研究成果の詳細

よる実装の性能評価
l 未着手の研究課題への取り組み

マルチコアクラスタシステム向けのタイル QR分解のこれまでの我々の実装の特徴を以下に挙げ

3. 当拠点公募型共同研究として実施した意義る。
l 縦方向 1D ブロックサイクリックデータ分散

本研究は、大規模な問題に対して、高並列な計算環境下において高速な行列分解の実装を得るた

l 1 ノード 1MPI プロセス

めに、

l OpenMP スレッド化（ノード内）

l アルゴリズム開発を行う代表者

l 動的タスクスケジューリング（ノード内）

l 実計算環境において実装を最適化する副代

l 通信専用スレッド（1）と計算用スレッド（他）

表者

この中でノード内の OpenMP スレッドを動的にスの共同研究を行う。本研究で想定している高並列ケジューリングする機構は、タスクキューとプロ計算環境は近年のマルチコアアーキテクチャのノグレステーブルから成るオリジナルの実装であり、ードからなるクラスタシステムであり、ノード内スレッドの同期処理が多用されているもののタイとノード間でそれぞれスレッド並列化と分散メモルアルゴリズムの実装として高い性能を発揮できリ並列化の異なる流儀での並列化が必要なハイブることが示されている。他のスーパーコンピュー2

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月
Performance)result

共同研究拠点の FX-10 スーパーコンピュータ上に1600)
New8)node1200)

GFlops

これを実装した。１ドメインを１プロセスに割り当て、ドメイン内のタスクをスレッド並列で処理SM2013Pするハイブリッド並列化を行った（後述）。この実

ScaLAPACK

装方式では、マージの操作にドメイン間通信が必

800)4)node400)要であり、これが性能のボトルネックとなる。
マージ操作に対して幾つかの手法を実装し、性

2)node1)node

能評価を行った。

0)0)

10000)

20000)

30000)

40000)

Matrix+size

50000)

60000)

1.

70000)

フラットツリー：最上ドメインから下方向のドメインに向かって逐次的にマージを行う。

図 1 タイル QR 分解の性能（青線が研究開始時の2.

実装の性能）

フラットバイナリツリー：ドメインを複数のグループに分け、グループ内でフラットツリ

タ環境における最適化により、通信処理を最適化

ーマージを行った後に二分木的にマージをし、本研究を開始する時点で少ないノード数では行う。
3.

スケールする実装が得られていた（図 1、国際会

マージシフトフラットツリー：フラットツリ

議プロシーディングス 1）。この実装に対して、共ーでは、各ステップで最上ドメインに向かっ同研究拠点の計算資源上で評価、最適化を行う。てマージをしていたが、マージシフトフラッ
トツリーでは、ステップが進む毎にひとつ下のドメインに向かってマージを行う。これに以下では、これまで本年度に行った研究の 3 つの部分について報告する。

より、最上ドメインを扱うプロセスへの負荷I.の集中を避けることが出来る。

縦方向の並列化（国内会議発表 1）4.

行列分解に対するタイルアルゴリズムのうち、

マージシフトフラットバイナリツリー：フラタイル QR 分解、部分ピボット選択付きタイル LU

ットバイナリツリーにおけるドメイングル分解は行列の縦方向のタスクに依存関係がある。

ープ内のフラットツリーマージをマージシそのため、特に縦長の行列に対して高い性能を発フトフラットツリー方式で行う。

揮しにくい。これに対して小行列に分割された行

上記の手法について、行列サイズ 96,000×12,000列を縦方向の領域（ドメイン）に分割し、それぞの縦長行列の QR 分解を 1 から 64 ノードで行い、Bring+a+parallelism+for+ver)cal+direc)on+
れにドメイン内で並列に行われた処理結果をマー

強スケールの並列性能を調査した結果を図 3 に示ジすることで行列分解を行う手法がある（図 2）。

す。単純なバイナリツリー方式のドメイン間マー! Domain+decomposi)on+ジ（先行研究）に比べて、マージシフトフラット
バイナリツリー方式は格段に性能向上しているこ

D0

D0とが分かる。16 ノード以降ではやや速度向上が鈍くなるものの、16 ノードで理想性能の 80%を達成

D1D1している。
D2

D2II. ハイブリッド並列化の性能評価（国内会議発D3D3表 1）
上述の縦方向の並列化を行った実装において、
step k+1

step k

FX-10 の 1 ノード上で、MPI プロセス数を変化させ図 2 ドメイン分割とマージ操作た性能評価を行った。ここで、各プロセス内のス
311

StrongScaling
学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

分解速度[GFLOPS]マージシフトフラットバイナリツリー
1600
1400

（ここまでの内容をまとめたものが図 3 の「先行研究」。中間報告後にこの部分について改良を行っ相対速度100 た）
16ノードで理想性能の約80%III. タイルサイズチューニング（国内会議発表 3）

1200

タイルアルゴリズムにおいてタイルサイズはマージシフトフラットツリー

1000

実行時に調整可能な性能パラメータであり、その800
フラットバイナリツリー

600

10 チューニングは非常に重要である。また、タイル内のタスクはブロック化されており、そのブロック幅（内部ブロック幅）も重要な性能パラメータ4000である。タイルサイズを b、内部ブロック幅を s

先行研究

200

フラットツリー010 20 30 40 50 60 70

1ノード数として問題サイズに応じて適切な組(b,s)を選ぶ1ことが求められる。
10 これに対して Agullo
100 等は参考ノード数[1]で(b,s)の枝刈り探索を行った。
44

タイル QR 分解に対する枝刈り探索では、複数

図 3 各マージ方式の性能比較の組(b,s)に対して網羅的に QR 分解を実行するのレッド数=16/MPI プロセス数とした。分解対象のではなく、主要な小タスクに対して組(b,s)の探索行列は行数：列数=10:1 の縦長行列である。

を行う。主要な小タスクの実行時間は QR 分解と比図 4 より、MPI プロセス数が少ない場合、縦方較して非常に短い。主要な少タスクが高速に実行

向分割を行わない場合（block）よりも分割をしたできる組(b,s)をいくつか抽出し、これを最適パラ場合の方が高性能であり、逆に、MPI プロセス数メータの候補とし、この候補についてのみ QR 分解が多い場合には縦方向の分割が少ない方が高性能を実行して問題サイズに応じた最適な組(b,s)をであることが分かる。これは、ドメイン間のマー選択する。以上が枝刈り探索である。（図 5）ジを行う際の MPI プロセス間通信が大きなボトル枝刈り探索では、最適パラメータ候補のネックとなっていることが原因だと考えられる。

抽出は比較的高速に行えるが、その後、想ブロック分割とサイクリック分割の比較(タイルサイズ200)
block80

80! ÌĤFĶĎ (b, s) Xeon _ PLASMA

分解速度 [Gflops]100

分解速度[Gflops](b,s)jŎŒwňō 

100
60
40
20024000

40000

56000

行サイズ

72000

cyclic2

cyclic4

cyclic860
40
20024000

40000

56000

行サイズ

72000

2MPI プロセス ,8 スレッド

1MPI プロセス ,16 スレッド

250""

Performance*(GFlops)

200""

80

分解速度 [Gflops]

分解速度 [Gflops]

100100" {(80,40),((120,40),((240,80),((420,84),((640,128),((920,184),((1120,112),((1360,136)}(60
4020024000

40000

56000

行サイズ

(80,40)"4MPI プロセス ,4 スレッド

72000

80
60
40
20024000

40000(120,40)"150""(240,80)"

56000

行サイズ

72000

8MPI プロセス ,2 スレッド30

図 4 縦方向並列化実装の性能(420,84)"(640,128)"
定される問題サイズの区間で、すべての候補に対100""(920,184)"

してタイル QR 分解を実行する段階で非常に時間(1120,112)"(1360,136)"
がかかる。

50""

タイルアルゴリズムにおいて、タイルサイズを0""0"

Size*of*matrix

適切に選択することで、実行環境に応じたタスク

5000" 10000" 15000" 20000" 25000" 30000" 35000" 40000"

|"#«ìpdgeqrf jÓô4

図 5 枝刈り探索（8 つの候補点について 4000" ¨Ń|5GQR 分解を実行）
qeVZr
から 40000 までタイル" |"#«ìjÅ¨³¶L³¶HĆ¨¼ÛOI

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

数を生成できることを既に述べた。我々はタスク

1-3 タイルサイズの通信への影響評価数の指標を導入し、これを一定の範囲内とするよ

ノード間通信の最適化に関しては以下の通り。

うなタイルサイズの範囲を問題サイズに応じて導2-1 現在のクラスタシステム向け実装の FX-10 での性出することで、特定の問題サイズにおいて試行さ能評価れるパラメータ候補を削減することに成功した。

2-2 ノード間通信の最適化（図 6）これにより、組(b,s)のパラメータ探索時

2-3 ノード間通信削減アルゴリズムの開発

現在まで 1-1 は完了、1-2 は途中、1-3 は未間を半分以下とすることができた。

着手、2-1、2-2、2-3 は完了である。特に 2-2により、FX-10 64 ノードまでで強スケールするクラスタシステム向け実装が得られた。
本申請課題を終えて、ドメイン間通信（マージ）について新たな着想が得られ、今後、 これについても共同研究拠点の設備を使用した実装、

ňōĶĎØjĮè
図 6 候補点の削減（各行列サイズにおいてタイル評価を行いたい。

QR 分解を実行する候補点が削減された）! ĮèYy`ĶĎØe|QR«ì(pdgeqrf)

7. 研究成果リスト

zÅ¨((1) 学術論文

250""

なし
(80,40)"

Performance*(GFlops)

200""(120,40)"(2) 国際会議プロシーディングス(240,80)"150""(420,84)"

1. T. Suzuki, Improved internode communication(640,128)"(920,184)"for tile QR decomposition for multicore cluster

100""(1120,112)"

systems, Proceedings of IEEE 29th IEEE

(1360,136)"(1600,200)"
International50""

Parallel & Distributed Processing(1840,184)"

Symposium (IPDPS2015), pp. 1214 – 1220.

(2040,204)"0""0"ĶĎØÛkêà5000" 10000" 15000" 20000" 25000" 30000" 35000" 40000"

Size*of*matrix! ¨Ń|ņi(3) 国際会議発表

TvējFjrĪîなし

参考[1] Agullo, E., Hadri, B., Ltaief, H., Dongarra, J.:! |"#«ìjÅ¨³¶L³¶HĆ¨¼ÛOI(4) 国内会議発表

Comparative
study of one-sided
factorizations with" ]ndjĶĎØaf
³¶
multiple software packages on multi-core hardware, In

1. 高 坂 知 寛 , 鈴 木 智 博 , タ イ ル CAQR の20

Proceedings of SC’09: International Conference for HighMPI/OpenMP ハイブリッド並列化, 日本応用数理

Performance Computing, Networking, Storage and学会 2015 年度年会, 2015.9 （金沢大学）.
2. 高柳雅俊, 鈴木智博, CPU/GPU 混在環境におけAnalysis (2009).

る再帰的タイル QR 分解, 日本応用数理学会

6.

今年度の進捗状況と今後の展望

2015 年度年会, 2015.9 （金沢大学）.

申請時の研究計画のうち、タイルサイズチュ

3. 鈴木智博, 共有メモリ環境上でのタイル QR 分解ーニングに関しては以下の通り。のタイルサイズチューニング, 情報処理学会第1-1 タイルサイズの実行時間への影響評価

151 回ハイパフォーマンスコンピューティング研究1-2 タイルサイズの誤差への影響評価

会, 2015.9 （那覇市沖縄産業支援センター）.
5学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

4. 高柳雅俊, 鈴木智博, CPU/GPU 混在環境における再帰的タイル QR 分解の動的スケジューリング実装, 日本応用数理学会 2016 年度研究部会連合発表会, 2016.2 （神戸学院大学）.
(5) その他（特許，プレス発表，著書等）
なし

6