性能解析

次にプログラムを各ステップに分けて時間測定を⾏うことで実⾏時間の内訳を⽰したものが 図 6.10である．ここでは⾏列サイズとして，𝑚 = 1, 200または2, 500，𝑛 = 2, 500，または5, 000の 組み合わせとして 4 種類⽤いた．ステップは，並列化⼿法によって多少異なるが，計算カーネル部分

（kernel8x24に相当）と，𝑋̄のパッキング（⾏うもののみ）， ̄𝑌のパッキング，𝐶の総和（内積⽅向分 割のみ），その他（同期や初期化処理）に分けている．

図 6.6などの結果と対応して，図 6.10においても 1D+X がとくに遅い．実⾏時間の内訳をみると，1D と⽐べて，単に同期や𝑋̄のパッキングの時間が増えているだけではなく，計算カーネルの実⾏時間⾃

体が増えていることがわかる．1D と 1D+X とでは計算領域の形状が⼀致するが，𝑋̄ をコア間で共有す る 1D+X は 1D より頻繁に同期を⾏う．この結果，複数のコアで共通のデータへのアクセスが頻繁に 発⽣し，単純なメモリアクセスより低速となるデータブロードキャストが頻繁に発⽣したことが原因 ではないかと考えられる．

1D+X 以外についてみると，まず 1D は 1D+X ほどではないが計算カーネルの実⾏時間が⼤きい．と くに𝑚 = 1, 200のときは 2D のものと⽐べて約 2 倍となっているが，𝑚 = 2, 400のときは約 1.2 倍ま で低下する．これは純粋に，1D の⽋点である，列ブロックの幅が⼩さくなりやすく，データ再利⽤性 が低下する問題が表れているものと考えられる．

1D 2D 1D+X 2D+X 1.5D 2.5D 1.5D+X 2.5D+X 0

0.01 0.02 0.03

timeinsec.

m= 1,200,n= 2,500

1D 2D 1D+X 2D+X 1.5D 2.5D 1.5D+X 2.5D+X 0

0.02 0.04

m= 1,200,n= 5,000

1D 2D 1D+X 2D+X 1.5D 2.5D 1.5D+X 2.5D+X 0

0.02 0.04 0.06

timeinsec.

m= 2,400,n= 2,500

1D 2D 1D+X 2D+X 1.5D 2.5D 1.5D+X 2.5D+X 0

0.05 0.1

m= 2,400,n= 5,000

kernel pack X pack Y reduce C others

図6.10 実⾏時間の内訳

2D や 2D+X は 他 と ⽐ べ て 顕 著 に ̄𝑌 の パ ッ キ ン グ に か か る 時 間 が ⼤ き い． こ れ ら はblocked-matmul2 の 再 内 側 処 理 を 複 数 の コ ア で 並 列 化 す る が， こ の と き ̄𝑌 の パ ッ キ ン グ については並列化していないことが影響していると考えられる．

また，全体として，𝑚が増加したとき𝑋̄ や ̄𝑌のパッキングの割合が減少し，𝑛が増加したとき，𝐶 の総和の割合が減少していることが確認できる．𝐶の総和の割合は𝑚が増加したときも減少してい る．これは，𝑚 = 1, 200のときは内積⽅向の分割数𝑁 = 18であるのに対して，𝑚 = 2, 400のときは

𝑁 = 5となり，総和の演算量の占める割合が減少することを反映していると考えられる．

以上の通り，将来利⽤されるアーキテクチャとしてメニーコア CPU の 1 つである KNC に対して，

⽚側ブロックヤコビ法の計算においてオーダーの意味でボトルネックとなっている Gram ⾏列計算の 実装⼿法について検討した結果，並列化⼿法の変更によって，ピーク演算性能の 7 割以上に達する⾼

性能を実現できることが分かった．ここでの実装⼿法は KNC を対象としているが，キャッシュや共有 メモリなどの構造を持つ他のメニーコア CPU や将来のものに対しても応⽤可能な⼿法であると考え られる．そこで，性能モデル化などと組み合わせた⾃動チューニング機構などを開発することで，よ り汎⽤性を⾼めることが課題である．これらのテクニックは将来に⽚側ブロックヤコビ法をメニーコ ア CPU に移植する場合に役⽴つものと考えられる．

第 7 章

結論

本論⽂は，⾮常に⾼い並列性を持つ現代と将来の⾼性能計算機に適する SVD 計算⼿法を開発するた め，⽚側ヤコビ法に着⽬した．⽚側ヤコビ法は LAPACK に実装された優れた SVD 計算⼿法の⼀つで あるが，ブロック化や並列化などの拡張⼿法と組み合わせることで，⾼い計算効率と，粗粒度な並列 性を持たせることができ，⾼性能計算機に適すると考えられる．しかし，ブロック化や並列化につい ては理論的・実験的検証が不⼗分であり，また現代の⾼い並列性を持つ⾼性能計算機に向けた実装の 研究も進んでいなかった．

そこで本研究では第⼀に⾼性能計算に適した Hari の V2 ⼿法 [7] と呼ばれる⽚側ヤコビ法のブロッ ク化⼿法に対して理論的な誤差解析を⾏うことで，計算結果の直交性に対する誤差上界を求めた．直 交性に対する誤差は⽚側ブロックヤコビ法の収束性に影響する．経験的には Hari の V2 ⼿法の直交性 の誤差が⼩さいことは知られていたが，理論的になぜそうなるかは不明であった．我々の結果は，⾏

列計算における誤差を詳細に追跡していくものであり，この証明によって，⽚側ブロックヤコビ法に おける列スケーリングした条件数が⼩さいという性質が直交性の誤差の⼩ささに影響していることが 判明した．

次に本研究では，Bečka らの並列動的オーダリングを⽤いたときの，⼀次収束性に対するより新し い上界を求めた．これまでの研究では，この上界が並列数に関係せず⼀定であったが，我々の上界は 並列数に反⽐例する形となっているため，我々は，Bečka らの⼿法を⽤いたときの計算時間の上限が 並列化によって減少することを⽰したことになる．

第三に，我々は Hari の V2 ⼿法を⽤いたときの⽚側ブロックヤコビ法の計算の特徴を利⽤したデー タ分散⼿法・並列化⼿法である，⼆次元ブロック化⼿法を開発し，⼤規模並列計算機において，⾼い 並列性を有することを実証した．このデータ分散⼿法はごく単純なものであるが，並列化において，

AllReduce 型と呼ばれる，通信量や回数の削減を重視した計算⼿順となっている．そこで，理論的に 通信量や回数を算出した後に，並列計算機上で検証を⾏い，理論から予測された結果に従った結果を 得た．また，京コンピュータを⽤いた⼤規模並列計算機上での性能検証を⾏い，10, 000次元の⾏列の SVD を計算するときに3, 072並列という，⾏列の次元数と近いノード数まで計算が加速することを確 かめた．

そして最後に，Hari の V2 ⼿法を⽤いた⽚側ブロックヤコビ法において主要な演算の 1 つとなる DSYRK という対称な形を持つ⾏列積について，将来使⽤されるであろうと⽬されるアーキテクチャ を持つメニーコア CPU，Xeon Phi (Knights Corner, KNC) を⽤いて性能検証と，実装⼿法の研究を⾏

った．KNC は Intel が開発したメニーコア CPU であり，Intel が提供する計算ライブラリには最適化

された DSYRK も含まれているが，ピーク演算性能と⽐べるとずっと⼩さな性能しか得られなかった．

我々は，KNC の持つ多数の並列性を活かす DSYRK の並列化⼿法を検討し，⾏列積の持つ 3 次元的な 並列化軸をすべて利⽤する並列化アルゴリズムを⽤いることで，通常の⾏列積 DGEMM に近い，⾼い 性能を得た．これは将来の計算機において⽚側ブロックヤコビ法を実装するときに役⽴つものと期待 される．

今後，実際に⽚側ブロックヤコビ法を⾼性能計算機上で活⽤していくためには，次のことが課題に なると考えている．第⼀に，収束性の証明であり，我々の Hari の V2 ⼿法に対する誤差解析によって，

多くの謎が解決したが，実際に，誤差を持った環境における収束性の証明にはまだたどり着いていな い．誤差のない環境におけるブロックヤコビ法の収束性の証明⾃体がごく最近に⾏われたものである が，それを，本研究の成果と組み合わせることで，この証明が可能になるものと考えられる．

また，⾼性能計算機に向けた実装の改善・強化や性能解析はさらに発展させる必要がある．本論⽂

で提案した⼆次元ブロック分割⼿法はデータ分散と列ブロック数を決定するパラメータ𝛼があり，こ れを最適化することで性能改善を⾏えるが，最適な𝛼の値を決定するには事前の性能測定か，あるい は性能モデル化が必要である．現実には，5 章での京コンピュータにおける実験のように⼤規模計算 を⾏う場合は，事前の性能測定がコスト⾯などの制約のため困難な場合もあるため，詳細な性能解析 に基づく良い性能モデルの構築が今後の課題となる．また，現代の⾼性能計算機の発展は著しく，と くに並列度の増⼤や性能バランスの変化は急速である．我々は⾏列の次元数とノード数が近い状態に おいても加速するほどの性能を得たが，将来の計算機に対応するためには，さらに⾼度な並列性能が 必要になる．それに対しては，本研究で⾏った DSYRK の実装技術の研究のように，個々の部品に対 する研究も必要になってくると考える．実際に現状においては QR 前処理という，ScaLAPACK の実 装を⽤いた部分が⼤きな部分を占めるものとなっており，単に⽚側ブロックヤコビ法だけでなく，そ こに⽤いる部品のアルゴリズムも含めた改善・強化が必要になってくると考える．

謝辞

本研究にあたり，学部・修⼠を含めて 6 年にわたり，指導教員としてご指導くださった⼭本有作教 授に感謝します．また，指導教員として研究室⽣活についてご相談に乗っていただき，また，審査委 員を引き受けてくださった緒⽅秀教教授に感謝します．修⼠時代にご指導いただき，また外部審査委 員を引き受けてくださった神⼾⼤学⼤学院システム情報学研究科の横川三津夫教授に感謝します．ま た，審査委員を引き受けてくださり，公聴会や予備審査においては貴重な意⾒やご指導をくださった

⼭本野⼈教授，成⾒哲教授，⼭﨑匡准教授に感謝します．また，関連論⽂ [b,c] の共著者として有益な コメントやアドバイスを下さった，スロヴァキア科学アカデミーの Bečka 教授と，ザルツブルグ⼤学 の Vajteršic 教授に感謝します．

こ の 研 究 は ⽇ 本 学 術 研 究 振 興 会 科 研 費 （26286087, 15H02708, 15H02709, 16KT0016, 17H02828, 17K19966）の補助を受けている．また，⽇本学術振興会特別研究員 DC2（17J07747）の補助を受けて いる．