（様式 20）成果報告書

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

利用課題名 ポストペタ時代の大規模並列数値計算のための技術開発
英文：Development of Parallel Numerical Computation Technology for Post-Peta Era
須田礼仁
Reiji Suda
東京大学 情報理工学系研究科
Graduate School of Information Science and Technology, the University of Tokyo
http://sudalab.is.s.u-tokyo.ac.jp/~reiji/
邦文抄録
我々は通信を削減した疎行列ベクトル積である行列冪カーネルについて、通信の回数は複数になるが、一般の非零構造を持つ疎行列に対して計算重複の少ない手法を提案した。小規模行列で評価した結果、実際に計算重複が効果的に削減される行列がある一方、通信削減が有効でない行列が存在することも示した。
英文抄録（100 words 程度）
We proposed a method to reduce duplicated computations in matrix powers kernel for matrices withgeneral non-zero patterns.
In the experiments, our method actually reduces the duplicatedcomputations. We also notice that there are matrices to which matrix powers kernel is not effective.

Keywords: ５つ程度
通信削減アルゴリズム、行列冪カーネル、計算重複の削減
背景と目的

い。

半導体技術の進歩により、プロセッサ性能が高くなっ一般の非零構造を持つ行列に対する行列冪カーネているため、光の速度で制限を受ける通信時間は相対ルとして、従来研究では、Hoemmen の論文に含まれ的に長く見えるようになっている。とりわけ、きわめて多る PA1, PA2 という手法が知られている。これらの手数のプロセッサをネットワークで結合したスーパーコン法では通信の回数は（集合的に）1 回だけとなるが、計ピュータにおいて、通信時間の影響が大きい。場合に算の重複が大量に発生するという課題があった。これ

よっては、処理時間の半分以上が通信の時間であるとに対し、我々は計算の重複がほとんどない手法を提案いうことも珍しくなくなっている。このような条件下では、した。ただし、我々の手法では通信の回数は複数回に多少の計算量を増やしてでも通信の量や回数を削減なってしまう。すなわち、我々の手法を従来手法とともす る 通 信 削 減 ア ル ゴ リ ズ ム （ Communication-に選択肢とすることにより、計算コストと通信コストのトAvoiding algorithms）が有効であると期待されており、レードオフを取ることができる。

様々な研究が行われている。
疎行列を係数とする連立一次方程式の反復解法な概要

どにおいて通信削減アルゴリズムを設計する際、ひと正方行列

つ の 構 成 要 素 と な る の が 行 列 冪 カ ー ネ ル （ Matrix

1,2, … ,とベクトルに対し、をに対してすべて求める計算が行列冪カPowers Kernel: MPK）である。偏微分方程式を有限ーネルである。ここで差分法などで離散化して得られる疎行列の場合、非零を残したい場合と、最終結果

構造に規則性があり、ステンシル計算で用いられていがあるが、計算とプロセッサ間通信については同じと考る時空間ブロッキング（temporal blocking）の手法をえてよい。これらの計算をできるだけ少ない通信回数で使って行列冪カーネルが実現できる。しかし有限要素実行したい。本稿では行列法などにより不規則な非零構造を持つ行列に対して時すべて非零であるとする。またベクトル空間ブロッキングの手法を拡張することは自明ではな

要素をと表す。

は正の整数である。途中結果だけがほしい場合とは対称で、対角要素はの第（様式 20）成果報告書
添え字の集合は重なりのない部分集合に分割され、リズムを設計することとした。具体的には、最後の領域プロセッサに割り当てられているとする。通常の用語に分割従い、各プロセッサに割り当てられている部分集合を領ステップの通信と計算は前述の方式によらず、域と呼ぶ。あるプロセッサがベクトル

Hoemenn の論文の PA2 と同様に、各プロセッサが領域の要素

き、添え字ｊ| ∈のうちを持っているとする。このとは最初の領域分割

担当領域の最終結果| ∈と同じとし、最後のを計算するように、必要な通信と計算を行うものとした。これにより、|に対して0 ⊆段であれば、までの計算が終了するとデータ分散が初期状態に戻り、は他のプロセッサと通信することなく、手元のデー同じ通信・計算パターンで行列・ベクトル積を繰り返し計タだけで計算できる。このように通信なしで計算できるの要素をすべて計算したとする。すると、算することができるようになる。の一部がそれらの要素だけを参照して計算できる可能性

結果および考察がある。このようにして、手元のデータだけから計算で我々はまだ並列実装には至っていないので、小規模きる限りの要素の集合を「錘」と呼ぶ。ステンシル計算

行列を用いて提案手法の計算量と通信回数を評価した。の場合、領域を底辺とする錘になるからである。

100

100 の 2 次元メッシュを 25 プロセッサに分割し、10 まで計算させた例では、従来手法 PA1 はこのようにして、各プロセッサが通信なしに計算できる要素をできるかぎり計算する。これを第 0 ステップの84%、PA2 は 52% 計算量が増加したのに対し、提案計算と呼ぶ。次に、新たな領域分割手法ではを定義する。

2 で 14%、3 で 1% の計算量の各プロセッサは新たな領域とその袖領域に含まれる第増加で済んだ。なお PA2 は提案手法の0 ステップの計算結果を受信する。これが第 1 ステッ

一である。3 次元メッシュや Florida 疎行列コレクショプの通信となる。次に、先と同様に、手元のデータからンの shuttle_eddy でも同様の傾向が得られた。これ計算できる限りの要素を計算する。これが第 1 ステッに 対 し 、 Florida 行 列 の cage10 で は 、 従 来 手 法プの計算となる。第 1 ステップの計算が終わると、さらPA1 では計算量が 15.3 倍、PA2 では 14.8 倍であに新たな領域分割り、提案手法でもを定義し、通信と計算を行う。

1 と同

5 でも 5.4 倍の計算量となった。この条件では、多くのアーキテクチャでは、行列ベこれを繰り返すことにより、計算が進んでゆく。
各ステップで計算がどこまで進むかを考える。大雑クトル積のたびに通信を行う古典的な手法のほうが有把にいうと、領域の端ではあまり計算が進まず、領域効ではないかと推測される。このように、行列冪カーネの中央部では計算が進むことがわかる。このため、いルの有効性が行列の非零構造に依存することも明らか

ずれかの添え字が常に領域の端の方にあると、そこだとなった。

け計算が進まないことになる。これを避けるため、計算が進んでいるところが領域の端になるように領域分割まとめ、今後の課題を定義する必要がある。そのような機能は通常のグラ

本報告では、一般的な非零構造を持つ行列に対すフ分割ソフトウェアに備わっている。我々は METIS をる行列冪カーネルにおいて計算の重複を削減する手法用い、辺に重みをつけて領域分割を実施した。すなわを報告した。実際にいくつかの行列に適用し、計算の重ち、計算が進んでいる頂点を結ぶ辺の重みは軽く、計複の削減が達成されていることを確認した。

算が進んでいない頂点を結ぶ辺の重みを重くすること通信削減反復法の並列実装は行っているが、今回で、計算が進んでいない頂点が領域の中央部に来や提案した手法はまだ並列実装されておらず、それが第すいようにすることができた。

一の課題である。また、提案手法は通信遅延隠蔽がでこのような領域分割を何度も繰り返すのはコストがかかる。そこで我々は冪指数と通信の回数を固定して、同一の計算と通信が繰り返されるようにアルゴきないので、そのようなアルゴリズムの拡張などが望まれる。