様式８の１の１ 別紙１
論文の内容の要旨
専攻名 システム創成工学専攻 氏 名 圓谷 友紀
有限要素法（FEM）を使用した電磁界解析で現れる線形方程式は，反復計算法である前処 理付きクリロフ部分空間法により求解される。求解に費やされる時間は FEM の総計算時間 の半分以上を占めるため，高速な線形方程式解法は工学設計における時間短縮の観点から重 要な研究課題である。高速化達成の一方策として，方程式解法に関わる演算を並列化するこ とが考えられる。解法の主要計算部には，三角行列に分解された行列を用いて前進・後退代 入を計算する演算が含まれる。この計算部は，行列ベクトル積のように行列を横方向に分割 するだけでは並列化を実現できないため，何らかの工夫が必要である。先行研究では，三角 行列の対角ブロック内の非零要素のみの演算を並列化に使用するブロック化前処理が考案さ れていた。この方法ではスレッド間の同期が不要であるため，行列ベクトル積に比べて並列 化効率が高い。しかし，ブロック行列の外にある非零要素は前進・後退代入の計算では使用 されないため，逐次演算時よりも収束特性が劣化するケースが多い。それゆえ，解法の高速 化のためには，上記の欠点を解消した並列化法の確立が重要である。
本論文ではまず，一反復当たりの計算時間を削減できる並列化法の確立を目的とし て，Eisenstatの方法を導入した前処理付き解法の並列化法を開発した。Eisenstatの方法 では，行列ベクトル積は前進代入一回，後退代入一回の演算に置換されるので，演算 回数を大幅に削減できる。しかし，係数行列の全ての非零要素を使用して前進・後退 代入を評価しなければならず，対角ブロック内の非零要素を使用するブロック化前処 理では並列化を行えない。この問題点を解決するために，マルチカラーオーダリング
（以下 MCと略記）をEisenstatの方法における前進・後退代入の並列化に利用すること を提案した。MCでは全ての非零要素を使用した前進・後退代入の並列化が実現できる ので，前述の問題点は解消される。よって，行列ベクトル積が並列化された前進・後 退 代 入 に 置 き 換 え ら れ る た め ， 本 論 文 で 提 案 す る 手 法 はReverse Cuthill-McKee（ 以 下 RCM）付きブロック化前処理以上の高速化を実現できることを明らかにした。
しかし，MCでは，バンド幅の拡大による収束特性の劣化，キャッシュミスの増加と いった潜在的な問題点を抱えている。次に，この問題点を解決するために，ブロック マルチカラーオーダリング（以下 BMC）を援用した前処理付き解法を開発した。BMC では，行列のグラフにおける節点を数個のグループに分割し，各グループを仮想的に 色分けする。その結果，行列の対角部に正方行列が配置されるので，MCよりもキャッ シュミスが低減される。一方，1 ブロックに含まれる節点の数がパラメータとして追 加されるため，その値によってはMCよりも前進・後退代入における同期（OpenMPに
おけるスレッド間の同期）が増加する恐れがある。そこで，同期回数の削減，パラメ ータ設定の省略を実現するために，申請者はRCMから得られるレベル構造をブロック 化に使用するマルチカラーオーダリング（以下 RBMC）を新たに提案した。RBMCは BMCよりも色数とバンド幅が少ない。一方，ブロック内の未知変数の数が均等でない ため，前進・後退代入におけるロードバランスが悪化する。そこで，ロードバランス の改善を目的として，さらに，節点のブロック化手順を修正したModified RBMCを開発 した。Modified RBMCではロードバランスの改善により計算効率が向上し，RBMCの場 合よりもキャッシュミスの少ない演算を実現することに成功した。以上より，Modified
RBMCはMC，BMCよりも良好な収束特性が実現され，一反復当たりの計算時間は短縮
され，RCM付きブロック化前処理よりも 2 割程度の高速化が達成できた。
本論文は 6 章で構成されており，各章の概要は以下の通りである。
第 1 章の序論では，研究背景と目的をまとめた。
第 2 章では，辺有限要素法の概要，線形方程式の反復解法について詳説した。
第 3 章では，MCとEisenstatの方法を併用した解法の並列性能を示した。提案手法は 並列度数を増やしても収束特性の劣化は少なく，行列ベクトル積の計算時間の削減が 可能である。それゆえ，本章で提案した方法はブロック化前処理以上の高速化を実現 した。
第 4 章では，Modified RBMCを導入した並列化解法の有効性を，モデルの数値計算 により以下の点を確認した。・Modified RBMCはBMCよりも色数が低減された。・RBMC よ り も 前 進 ・ 後 退 代 入 に お け る ロ ー ド バ ラ ン ス が 改 善 さ れ た 。・ そ れ ゆ え ，Modified RBMCは他の手法よりも高速であった。
第 5 章では，Modified RBMCとEisenstatの方法を併用した解法の性能を，他の11種 の並列化解法と比較した。その結果，他のいずれの解法よりも良好な収束特性であっ たため，本章で提案した方法が高速化に効果的であることが確認できた。
第 6 章の結論では，本研究で得られた知見，課題，今後の展望をまとめた。
