今日インターネットの発達により,それを用いた情報検索が重要になってきている。このような情報検索処理は従来,数値計算とは別の非数値計算処理であると考えられてきた。ところが近年,M.Berryらによりこの情報検索処理において検索情報から知識を抽出するために,固有値計算が必要となることが指摘された。この例のように,固有値計算は従来の数値計算に限定された科学技術計算だけではなく,幅広い意味での情報処理全般において基本的な処理であるといえる。また必要となる固有値計算の規模は,インターネット上の検索対象のデーターベースが非常に膨大になってきていることや,数値計算が必要な問題は常に計算機性能の限界まで大規模な計算を要求することから,演算量とメモリ使用量の観点から非常に大規模となる。したがって実行時間に関しての高速化や,非常に多くのメモリを利用したいという要求は尽きることがない。この一方で近年,スーパーコンピュータに代表される大規模計算を高速に行うための計算機は,そのほとんどが分散メモリ型並列計算機である。このことから,アルゴリズムやメモリ使用の観点からの並列化が必須となっている。

　これらの要求から本論文では第一部として,固有値計算のために必要な各種アルゴリズムの提案と実装評価を行う。次に第二部として,開発された並列プログラムに関する各種の応用を行う。その応用に関して,まず始めにプログラムをライブラリ化する場合において多種の並列計算機環境で高い性能を達成する必要がある,という要求がある。この要求を満たすため,固有値計算用の並列数値計算ライブラリにおいて始めて実行前最適化機能を付加することを提案し,複数の並列計算機を用いてその並列ライブラリの性能評価を行う。また現在,多数の数値計算ルーチンを自動的にチューニングをするソフトウエアが開発されてはいるが,最適化時間が大きな問題となっている。本論文では第二部において,この最適化時間の問題を解決するためのいくつかの方法を議論し,実機による評価を行う。さらに最適化された性能に関するパラメタを利用することで,従来よりも高効率な数値計算ルーチンが構築可能と考えられる新しい数値計算基本ルーチン(BLAS)の分類を提案する。また性能評価から,従来のBLASよりも効率がよい例を確認した。

　本論文の第一部としてまず始めに,対称密行列の固有値問題を解く場合で必要になるHouseholder-Bisection法を取り上げる。このアルゴリズムではHouseholder三重対角化が必要になるが,従来ではプロセッサ台数が増加すると通信時間も増加するという問題が生じていた。そこで本論文では,プロセッサ台数が増加しても通信時間が減少するアルゴリズムを提案する。またこの三重対角化において,演算性能を向上させる技法であるブロック化という技法(アルゴリズムブロッキング)が逐次処理においては利用されていた。一方でブロック化アルゴリズムを分散メモリ型並列計算機上に実装する場合に行列データの分散をしなくてはならないが,あるまとまった単位で行列データをプロセッサに分散する(データ分散ブロッキング)。従来のアルゴリズムでは,このアルゴリズムブロッキングのブロック幅とデータ分散ブロッキングのブロック幅を同一にしていた。このことから問題サイズが小さい場合や超並列環境では負荷バランスが劣化し,高性能なアルゴリズムを構築できないという問題が生じていた。そこで本論文では,アルゴリズムブロッキングのブロック幅とデータ分散ブロッキングのデータ幅を区別してアルゴリズムを設計する概念を提案し,実際の並列計算機にそのアルゴリズムを実装して評価を行った。その結果,現在標準的に使われているScaLAPACKの同種ルーチンに対して,最大で5倍程度の速度向上を得ることができた。

　次に固有値計算に限らず線形計算をする場合で必須な,Gram-Schmidt法を用いた直交化処理を取り上げる。固有値問題において,この直交化処理は重複固有値に対する固有ベクトルを計算する際に必要となる。従来ではこの直交化処理において精度と並列性能のトレードオフが問題となっていた。その解決のため,本論文ではまず直交化処理を「QR分解」と「再直交化」という二つの処理に分類し,並列計算機上でのデータ分散と並列アルゴリズムの関係をはじめて明らかにした。またQR分解においては,超並列計算機環境での負荷分散の劣化を改善する新しいデータ分散方式を提案する。この新しいデータ分散方式を用いることで,超並列処理環境でのQR分解において負荷バランスを改良できる例を確認した。一方で再直交化において,直交化処理にソート機能を付加することで並列性能と直交精度を改善できる可能性がある新しい並列直交化アルゴリズムを提案する。このアルゴリズムを実際の固有ベクトル計算ルーチンに実装した結果,従来の直交化を用いた場合に比べて直交精度と収束までの反復回数が改善される場合があることを数値実験から確認した。この結果は,本直交化アルゴリズムにより並列性能と精度のトレードオフを解決できる可能性があることを示唆しているだけでなく,実際の固有ベクトル計算ルーチンでの速度向上も達成できる可能性があることも示唆している。

　本論文の第二部としてまず始めに,並列数値計算ソフトウエアにおける実行前最適化機能を提案する。その有効性を示すため,実行前最適化機能を始めて付加した並列固有値計算ソルバを日立の分散メモリ型並列計算機に実装し,性能評価を行った。この固有値ソルバにおける実行前最適化の方法は,大域的なリダクション演算の実装方式の選択,行列一ベクトル積や行列更新の実装におけるアンローリング段数,および通信処理のブロック化におけるブロック幅の調整などである。具体的には,Hoseholder三重対角化,Householder逆変換,および修正Gram-Schmidt法による直交化処理にこの実行前最適化機能を付加したのであるが,これらの処理はBLAS1,BLAS2,およびBLAS3と呼ばれる異なる種類の数値計算における基本的な演算カーネルにて構成されている。したがってこの実験用の固有値ソルバはある意味で実用ソフトウエアの良いベンチマークとなっている。この論文で著者が提案する最適化の方法は,極めて単純な方法である。すなわちそれは,用意されているルーチンをそれぞれ実行して最も高速となる組合せを選択するものであるが,すべての組合せについて調べることをしない。なぜならば原理的に,物理的に離れているルーチンが性能に影響する可能性は低いことを利用しているからである。このような単純な最適化方法を利用しても,結果として日立SR2201,SR8000の各分散メモリ型並列計算機において約1.1-2.3倍の性能向上を得ることができた。この結果は,いかに実行前最適化機能の付加が有用であるかを示している。

　次に第二部では,本論文で提案された実行前最適化機能を付加した数値計算ライブラリのような自動チューニングソフトウエアをどのように実現したらよいかを議論する。そのため「高性能な」自動チューニングソフトウエアとは何かを定義する。それは(1)プログラムを高速に実行できるパラメタを高速に見つけることができること,(2)その高速なパラメタを見つける時間もまた高速であること,そして(3)最適化時間を増やせばよりよいパラメタを発見できること,である。このような高性能な自動チューニングソフトウエアを実現するため,4種の方法を議論した。実機による性能評価の結果から,数値計算ソフトウエアにおいては「不完全な分解」による方法を利用する方法が良いことが明らかになった。この「不完全な分解」による方法とは,多くの線形代数計算はいくつかの基本演算からなる分解処理により構成されていることを利用したものである。実機による実験の結果,同じ性能を達成できるパラメタを発見するまでの最適化時間を約1/74.1にできることが判明した。これは約33時間の最適化時間が,1591秒程度に削減されることを意味している。この一方で著者は,Intelligent BLAS(IBLAS)とよばれる新しいBLASにおける分類を提案する。このIBLASの概念は,実行前最適化機能の概念を自然に拡張することによって得られたものであり,実行前最適化の概念なしには得られることはできなかった。実機による評価の結果,従来のBLASは最適ではないことが判明した。なぜならばIBLASの方がより高速である場合が存在したからである。具体的にはIBLASを利用することで,従来のBLASを利用した場合に比べ,約1.02-1.26倍程度の高速化を達成する場合があった。BLASを利用しているソフトウエアは容易にIBLASを利用できる。このことから本論文で提案されるIBLASの適用性は広く,高性能な数値計算ルーチンを構築するために非常に有用であることが期待される。

　本論文は4部より成り、第一部では,上記で指摘した「大規模」な固有値計算に関して,分散メモリ型並列計算機利用の観点と,ライブラリの作成と利用の観点からの問題点を指摘している。第二部では,固有値計算のために必要な各種アルゴリズムの提案と実装評価を行った。第二部の前半では,超並列環境に向く高性能な相似変換アルゴリズムの提案と評価を行い、後半では,密集固有値に対する固有ベクトル計算で必須な並列直交化アルゴリズムの提案と評価を行った。第三部では,固有値計算用の並列数値計算ライブラリにおいてはじめて実行前最適化機能を付加することを提案し,複数の並列計算機を用いてその有用性を示した。第四部では,第二部で提案したアルゴリズムの適用範囲に関して,演算効率と通信量の観点からの検討を行っし、第二部と第三部において得られた知見のまとめを示した。さらにこれらの知見から,対称密行列用固有値ソルバの利用者に対して,利用上の問題およびどのような解法を利用すべきかを述べた。

　本論文の第一部では,まず分散メモリ型計算機利用の観点からの問題点が述べられている。具体的には,以下の三種の事項:

(1)逐次ブロック化アルゴリズムの並列化による負荷分散の劣化;

(2)対称性の利用による通信の発生;

(3)二次元分散に伴う通信削減方式;

が問題であり,これらの事項を考慮すべきである。これらの問題を解決するため,本論文では第二部で各種のアルゴリズムの提案を行った。この一方で,ライブラリの作成と利用の観点の問題がある。それらは,

(1)高性能を達成するためのコード量の増加;

(2)利用者が設定する誤ったパラメタ;

の問題である。この問題を解決するため,本論文では第三部において自動最適化機能の提案を行た。

　本論文の第二部としてまず始めに,対称密行列の固有値問題を解く場合で必要になるHouseholder-Bisection法を取り上げた。このアルゴリズムではHouseholder三重対角化が必要になるが,従来ではプロセッサ台数が増加すると通信時間も増加するという問題が生じていた。そこで本論文では,プロセッサ台数が増加しても通信時間が減少するアルゴリズムを提案した。またこの三重対角化において,演算性能を向上させる技法であるブロック化という技法(アルゴリズムブロッキング)が逐次処理においては利用されていた。一方でブロック化アルゴリズムを分散メモリ型並列計算機上に実装する場合に行列データの分散をしなくてはならないが,あるまとまった単位で行列データをプロセッサに分散する(データ分散ブロッキング)。従来のアルゴリズムでは,このアルゴリズムブロッキングのブロック幅とデータ分散ブロッキングのブロック幅を同一にしていた。このことから問題サイズが小さい場合や超並列環境では負荷バランスが劣化し,高性能なアルゴリズムを構築できないという問題が生じていた。

　そこで本論文では,アルゴリズムブロッキングのブロック幅とデータ分散ブロッキングのデータ幅を区別してアルゴリズムを設計する概念を提案し,実際の並列計算機にそのアルゴリズムを実装して評価を行った。さらに従来から利用されていた行列の対称性を利用することを取り止めることで,従来法に比べさらに通信量を削減できるようになった。これらの手法を利用した結果,現在標準的に使われているScaLAPACKの同種ルーチンに対して,最大で5倍程度の速度向上を得ることができた。また実際のある応用ソフトウエアにおいては,572次元という非常に小さなサイズの固有値問題を6000回以上も解く必要がある。このような応用ソフトウエアにおいて本アルゴリズムを適用することで,8台のPCクラスタで90%以上という高い並列化効率をはじめて達成できるようになった。

　次に固有値計算に限らず線形計算をする場合で必須な,Gram-Schmidt法を用いた直交化処理を取り上げた。固有値問題において,この直交化処理は重複固有値に対する固有ベクトルを計算する際に必要となる。従来ではこの直交化処理において精度と並列性能のトレードオフが問題となっていた。その解決のため,本論文ではまず直交化処理を「QR分解」と「再直交化」という二つの処理に分類し,並列計算機上でのデータ分散と並列アルゴリズムの関係をはじめて明らかにした。またQR分解においては,超並列計算機環境での負荷分散の劣化を改善する新しいデータ分散方式を提案する。この新しいデータ分散方式を用いることで,超並列処理環境でのQR分解において負荷バランスを改良できる例を確認した。一方で再直交化において,直交化処理にソート機能を付加することで並列性能と直交精度を改善できる可能性がある新しい並列直交化アルゴリズムを提案する。このアルゴリズムを実際の固有ベクトル計算ルーチンに実装した結果,従来の直交化を用いた場合に比べて直交精度と収束までの反復回数が改善される場合があることを数値実験から確認した。

　この結果は,本直交化アルゴリズムにより並列性能と精度のトレードオフを解決できる可能性があることを示唆しているだけでなく,実際の固有ベクトル計算ルーチンでの速度向上も達成できる可能性があることも示唆している。また「計算を分割すること」により,精度向上が得られる場合があることがわかった。したがって実行速度,メモリ利用率,および精度の観点から大規模計算は並列計算機で実行すべきであることを示した。

　本論文の第三部としてまずはじめに,並列数値計算ソフトウエアにおける実行前最適化機能を提案した。その有効性を示すため,実行前最適化機能をはじめて付加した並列固有値計算ソルバを日立の分散メモリ型並列計算機に実装し,性能評価を行った。この固有値ソルバにおける実行前最適化の方法は,大域的なリダクション演算の実装方式の選択,行列一ベクトル積や行列更新の実装におけるアンローリング段数,および通信処理のブロック化におけるブロック幅の調整などである。具体的には,Hoseholder三重対角化,Householder逆変換,および修正Gram-Schmidt法による直交化処理にこの実行前最適化機能を付加したのであるが,これらの処理はBLAS1、BLAS2,およびBLAS3と呼ばれる異なる種類の数値計算における基本的な演算カーネルにて構成されている。したがってこの固有値ソルバはある意味で実用ソフトウエアの良いベンチマークとなっている。この論文で著者が提案する機能は,従来の自動チューニングソフトウエアで用いられていたBLASを単位とする局所最適化とは異なり,固有値計算の基本処理の単位で最適化する「大域的な」最適化方式を利用する。この「大域的な」最適化により,従来では扱えなかった並列化に関するパラメタも容易に最適化が可能となり,かつ従来の局所最適化方式と比較して高い性能を達成できる可能性をもつ。一方で著者が提案する最適化方法は,極めて単純な方法である。すなわちそれは,用意されているルーチンをそれぞれ実行して最も高速となる組合せを選択するものであるが,すべての組合せについて調べることをしない。なぜならば原理的に,物理的に離れているルーチンが性能に影響する可能性は低いことを利用しているからである。このような単純な最適化方法を利用しても,結果として日立SR2201,SR8000の各分散メモリ型並列計算機において約1.1--2.3倍の性能向上を得ることができた。この結果は,本論文で提案する実行前最適化機能の付加がいかに有用であるかを示している。

　次に第三部では,本論文で提案された実行前最適化機能を付加した数値計算ライブラリのような自動チューニングソフトウエアをどのように実現したらよいかを議論する。そのため「高性能な」自動チューニングソフトウエアとは何かを定義する。それは

(1)プログラムを高速に実行できるパラメタを見つけることができること,

(2)その高速なパラメタを見つける時間もまた高速であること,そして

(3)最適化時間を増やせばよりよいパラメタを発見できること,である。

このような高性能な自動チューニングソフトウエアを実現するため,4種の方法を議論した。実機による性能評価の結果から,数値計算ソフトウエアにおいては「不完全な分解」による方法を利用する方法が良いことが明らかになった。

　この「不完全な分解」による方法とは,多くの線形代数計算はいくつかの基本演算からなる分解処理により構成されていることを利用したものである。実機による実験の結果,同じ性能を達成できるパラメタを発見するまでの最適化時間を約1/74.1にできることが判明した。これは約33時間の最適化時間が,1591秒程度に削減されることを意味しており,非常に有効な方法であることが示された。

この一方で著者は,Intelligent BLAS(工BLAS)とよばれる新しいBLASにおける分類を提案した。このIBLASの概念は,実行前最適化機能の概念を自然に拡張することによって得られたものであり,実行前最適化の概念なしには得られることはできなかった。具体的にIBLASとは,従来のBLASに比べ問題サイズに応じて多数の実装方式を動的に選択することができる柔軟なBLASである。実機による評価の結果,従来のBLASは最適ではないことが判明した。なぜならば,IBLASの方がより高速である場合が存在したからである。IBLASを利用することで,従来のBLASを利用した場合に比べ約1.02--1.26倍程の局速化を達成する場合があった。BLASを利用しているソフトウエアは容易にIBLASを利用できる。このことから本論文で提案されるIBLASの適用性は広く,高性能な数値計算ルーチンを構築するための有用な手法になることが期待される。

　最後に第四部は,第二部と第三部で得られた知見を総括する。第二部の前半から得られた知見は,

(1)通信量削減手法の利用;

(2)ブロック化とデータ分散に関するパラメタの分離による負荷分散の改善;

(3)対称性の利用の取り止めによる通信量の削減;

により,従来法では達成不可能な高速化を実現する並列二重対角化処理が構築可能ということである。特に本論文で提案されたアルゴリズムは,行列サイズが小さい場合や超並列環境でも高速である。このことから小さい問題サイズの固有値問題を多数回解く場合に有効であり,多くの応用ソフトウエアでの利用が期待される。

　本研究は、黒田久泰、大澤清、金田康正との共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文堤出者の寄与が十分であると判断する。

　したがって、博士(理学)の学位を授与できると認める。