(57)【特許請求の範囲】
【請求項１】
入力装置と、それぞれがキャッシュメモリを備えた複数のプロセッサからなる処理装置と、出力装置とからなる並列計算機を用いてＮ次元の行列Ａに対して線形計算を行う方法であって、
計算対象の行列Ａおよび２つの異なるブロックサイズＬＢ，ＭＢを入力し、
係数行列Ａを大きさＬＢ×ＬＢの複数個のブロックに分割し、分割したブロックを上記複数のプロセッサに分散して割り当て、
前記線形演算を前記分割したブロックのブロック段ごとに順次実施し、
該順次実施の第Ｋ段（１≦Ｋ≦Ｎ／ＬＢ）の計算は、
前記ブロック段のそれぞれのブロックが割り当てられたプロセッサにて各々演算を担当し、且つ、
ａ．第Ｋブロック枢軸列および第Ｋブロック枢行を作成するために必要な前処理演算と、
ｂ．第Ｋブロック枢軸列の作成と、
ｃ．第Ｋブロック枢軸行の作成と、
ｄ．第Ｋブロック枢軸列と第Ｋブロック枢軸行とを用いて更新すべき行列Ａの部分のうち、次の数段分のブロック枢軸列とブロック枢軸行を作成するのに必要な範囲の消去演算と、
ＫがＭＢ／ＬＢの倍数であるか否かを判定して倍数であるときには上記に加えて、
ｅ．行列Ａの更新すべき部分の第（Ｋ−ＭＢ／ＬＢ＋１），第（Ｋ−ＭＢ／ＬＢ＋２），・・・，第Ｋブロック枢軸列・ブロック枢軸行によるＭＢ／ＬＢ段分の同時更新演算を実行する、
との方法で並列実行することを特徴とする線形計算方法。
【請求項２】
請求項１の線形計算方法であって、上記入力する処理は、演算に使われるデータを単位にして計った上記キャッシュメモリのサイズをＷ語とするとき、ＭＢ×ＭＢ≦Ｗ≦４×ＭＢ×ＭＢを満たすように上記ＭＢを決める処理を含む線形計算方法。
【請求項３】
請求項１の線形計算方法であって、上記前処理演算は、Ｎ次元の連立一次方程式Ａｘ＝ｂにおける係数行列Ａの第（Ｋ，Ｋ）ブロックのＬＵ分解を行う演算である線形計算方法。
【請求項４】
請求項１の線形計算方法であって、上記前処理演算は、Ｎ次元の行列Ａの第（Ｋ，Ｋ）ブロックのＱＲ分解を行う演算である線形計算方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は並列計算機を用いて例えば連立一次方程式の求解，固有値計算などの線形計算を高速に行う方法に関する。
【０００２】
【従来の技術】
構造解析，流体計算などの科学技術計算では，数万次元から数百万次元に上る大規模行列を係数行列とする連立一次方程式の求解，固有値計算などの線形計算が必要となる。このような計算を高速に行う手段としては，並列計算機が有力である。並列計算機は数十個から数万個に上る多数の高速プロセッサをネットワークで結んだシステムであり，問題を適切に分割して各プロセッサに割り当て，同時に処理を行わせることにより，１台のプロセッサによる実行と比べて飛躍的な実行速度の向上が可能となる。
【０００３】
問題の分割と部分問題のプロセッサへの割り当てにおいては，（１）  プロセッサの単体性能を発揮させること，（２）  並列化効率（プロセッサを１台からｐ台に増やしたときの理想的な性能向上であるｐ倍に対し，実際にどの程度の性能向上が達成できたかの比）を高めること，の２つを考慮することが必要である。（１）の単体性能に関しては，高性能な並列計算機に使われるプロセッサはキャッシュを備えたＲＩＳＣ型プロセッサであることが多いため，キャッシュを有効に利用できる分割法が必要となる。また，（２）の並列化効率に関しては，プロセッサ間通信の回数とデータ量とを減らして通信時間を削減すること，およびプロセッサ間の負荷を均等にして負荷不均等によるプロセッサの待ち時間を削減することが必要となる。
【０００４】
連立一次方程式を解くために使われるガウス消去法（ＬＵ分解法）の場合，従来はこの２つの課題を解決するために並列化ブロックガウス法（たとえばインテル・コーポレーション：”並列処理コンピュータで超大規模連立一次方程式を解く方法”，特開平５−２５０４０１（１９９１年１２月２０日出願）参照）と呼ばれる手法が使われてきた。これは図２の係数行列４を大きさＬＢ×ＬＢ（ＬＢ：ブロックサイズ）のブロック５，６，７などに分割し，各ブロックを実数のようにみなして，通常のガウス消去法を適用する手法である。並列化にあたっては各ブロックを図２のように１６台のプロセッサ０〜１５に割り当て，各ブロックに対する消去演算を担当のプロセッサに行わせる。
【０００５】
通常のガウス消去法と比べた場合，並列化ブロックガウス法の利点は次の通りである。まず，消去演算における実数どうしの乗算が，並列化ブロックガウス法ではＬＢ×ＬＢの行列どうしの乗算になる。一般に行列乗算では，データがキャッシュ中にある間に何回も演算を行うため，キャッシュの有効利用が可能となり，ＲＩＳＣ型プロセッサ上での単体性能を向上させることが可能となる。さらに，プロセッサ間でのデータ通信もブロック単位となるため，通常のガウス消去法に比べて通信回数は減少し，通信時間の削減により並列化効率の向上が可能となる。これらの利点のため，並列化ブロックガウス法は，並列計算機上でガウス消去法により連立一次方程式を解くためのもっとも一般的な手法となっている。
【０００６】
【発明が解決しようとする課題】
並列化ブロックガウス法では，ブロックサイズＬＢは２つの異なる要請から決定される。まず（１）  単体性能の向上という面からは，消去演算で現われる  Ｃ  ←  Ｃ  −  Ａ×Ｂ  という形の行列乗算において，行列Ａ，Ｂ，Ｃのすべてがキャッシュに入るという条件の下で，ＬＢはできるだけ大きいことが望ましい。ＬＢが大きいほど，データがキャッシュ中にある間に多数回の演算が行われることになり，キャッシュの有効利用が計られるからである。一方，（２）  並列化効率の向上という面からもＬＢの最適値がある。ＬＢが大きくなるとデータ通信の単位となるブロックは大きくなり，通信回数の減少により通信時間が減る一方，各プロセッサの担当するブロックの個数のばらつきが大きくなり，負荷の不均等による待ち時間は増大する。ＬＢが小さくなるとデータ通信回数は増加するが，各プロセッサの負荷は均等になる。したがって，これら２つの均衡により，並列化効率を最大にするＬＢが定まる。以上で述べた（１）  単体性能を最大にするＬＢの値と（２）  並列化効率を最大にするＬＢの値とは，一般には一致しない。例として，１６台のプロセッサで並列化ブロックガウス法を実行する場合を図３に示す。この例では単体性能を最大にするようにＬＢを決めた結果，プロセッサ０の担当ブロック５は４個，プロセッサ１５の担当ブロック７は１個と，担当ブロック数に大きな差が生じている。このため，高い並列化効率は期待できない。このように従来の並列化ブロックガウス法では，単体性能，並列化効率の一方あるいは両方を犠牲にしつつ総合的に見てもっとも高い性能を達成するようにＬＢを決める必要があったため，並列計算機の持つ性能を十分に引き出せないという問題があった。
【０００７】
本発明は，並列化ブロックガウス法を改良することにより，この問題を解決し，単体性能と並列化効率の両方を高めることにより，線形計算において並列計算機の持つ性能を十分に引き出すことを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため，本発明では並列化ブロックガウス法を改良し，２種の異なるブロックサイズを導入した。従来の並列化ブロックガウス法が単体性能と並列化効率とを同時に高められないのは，この２つの目的のそれぞれに対し，最適なブロックサイズが異なるからである。そこで本発明では，まず並列化効率の面から最適なブロックサイズＬＢを決定し，このサイズにより行列をブロックに分割して，各ブロックをプロセッサに割り当てる。これにより，並列化効率の最適化が可能となる。次に消去演算においては，各ブロック段において毎回行列全体の消去を行うのではなく，ある段数ｋ段分のブロックピボット行とブロックピボット列とを作成しておき，ｋ段に一回，まとめて消去を行う。これにより，消去演算はＭＢ＝ｋ＊ＬＢの大きさの行列乗算として処理できることになり，ｋを適当に取ることにより，単体性能の最適化が可能となる。
【０００９】
【作用】
１６台のプロセッサでガウス消去法を実行する場合を例にとり，本発明により高い並列化効率と高い単体性能とが同時に達成される様子を説明する。
【００１０】
まず，図４（ａ）が全体行列の消去演算を示す。行列はブロックに分割されており，各ブロックのサイズはＬＢ×ＬＢである。行列中の影の付いたブロックは，プロセッサ０の担当ブロックを示す。ＬＢを十分小さく取ることにより，各プロセッサの担当ブロック数はほぼ均等になり，並列化効率を高めることができる。図４（ａ）では４段分のブロックピボット列とブロックピボット行とを作成しておき，まとめて４段分の消去を行う場合を示している。この場合，プロセッサ０では，ブロックピボット行・列のうちの影の付いたブロックを用いて消去演算を行う。プロセッサ０の行う演算のみを取り出して表示したのが図４（ｂ）である。図から明らかなように，４ブロック段分の消去をまとめて行うことにより，プロセッサ０での消去演算はサイズＭＢ＝４＊ＬＢの行列どうしの乗算として処理できる。これにより，従来の並列化ブロックガウス法に比べて行列乗算のサイズを大きくすることができ，キャッシュの有効利用により単体性能を高めることができる。
【００１１】
以上により，本発明の手法では並列化効率の向上と単体性能の向上とを同時に達成することができる。
【００１２】
【実施例】
（実施例１）
以下，本発明の原理および実施例を，図面により詳細に説明する。ここで実施例として挙げるのは，並列計算機を用いてガウス消去法により連立一次方程式を解く方法である。図１に示すように，本方法を適用する並列計算機システムは行列データ，右辺ベクトルなどのデータを入力するための入力装置１，  それぞれがキャッシュメモリを備えたｐ台のプロセッサ３１を持つ連立一次方程式求解装置２，解を出力するための出力装置３から構成される。本実施例における処理を図５に示す。まず入力装置から係数行列Ａ，右辺ベクトルｂ，行列の次元Ｎ，２つのブロックサイズＬＢ，ＭＢを入力し（処理１３），行列データおよび右辺ベクトルのプロセッサへの割り当てを行い（処理１４），Ｋ＝１からＫ＝Ｎ／ＬＢまでの各ブロック段について消去演算を行って係数行列のＬＵ分解を求める（処理１５）。次に，得られたＬＵ分解を用いて前進消去演算（処理２２），後退代入演算（処理２３）を行って解を求め，最後に各プロセッサに分散して格納されている解を収集し（処理２４），出力する（処理２５）。本発明のもっとも大きな特徴は，処理１４のデータ割り当て部分，および処理１５の消去演算部分にあるので，以下，これらの部分について説明する。
【００１３】
（１）  プロセッサへのデータ割り当て
入力ステップ（処理１３）で入力したプロセッサ割り当てのためのブロックサイズＬＢを用いて，図２のように係数行列を大きさＬＢ×ＬＢのブロックに分割し，各ブロックをプロセッサに割り当てる。図２の５，６，７はそれぞれプロセッサ０，１，１５に割り当てられたブロックを示す。ＬＢが大きいと通信の単位が大きくなるため，通信回数が減少して通信オーバーヘッドは減少するが，各プロセッサの担当ブロック数のばらつきが大きくなり，プロセッサ間の負荷不均等によりアイドル時間が増大する。一方ＬＢが小さいと負荷は均等になるが，通信の回数が多くなって通信オーバーヘッドが増大する。本発明では，これら２つの兼ね合いから，並列化効率を最大にするようにＬＢをあらかじめ決める。
【００１４】
（２）  消去演算
本発明における消去演算の特徴は，各ブロック段ごとに行列全体の消去演算を行わず，ｋ本のブロックピボット列・行を予め作成してからｋブロック段分の消去を行い，これにより消去演算を大きさＭＢ＝ｋ＊ＬＢの大きな行列の演算として処理してキャッシュの有効利用を計ることにある。そこで，図５の処理１５から処理２１により，消去演算の各過程を説明する。
【００１５】
まず，第Ｋブロック段の最初では第（Ｋ，Ｋ）ブロックのＬＵ分解を行う（処理１６）。これは従来の並列化ブロックガウス法と同じである。次に，今作成したＵの逆行列を第Ｋブロック列に右からかけることにより第Ｋブロックピボット列を作成し（処理１７），Ｌの逆行列を第Ｋブロック行に左からかけることにより第Ｋブロックピボット行を作成する（処理１８）。そして第Ｋブロックピボット列と第Ｋブロックピボット行とにより，消去演算を行う（処理１９）。ただし，ここでの消去は行列全体に対しては行わず，次のｋ本のブロックピボット列・行となる部分に対してのみ行う。ｋ段分のブロックピボット列・行を作成するためには，この範囲の消去で十分である。この後，Ｋがｋ＝ＭＢ／ＬＢの倍数でなければ，第Ｋ＋１ブロック段に進む（処理２０）。Ｋがｋ＝ＭＢ／ＬＢの倍数の場合には，それまでに作成したｋ本のブロックピボット列・行を用いて，行列全体の消去を行う（処理２１）。この消去演算での処理を図４（ａ）に示す。この例ではｋ＝４であり，４本のブロックピボット列８，４本のブロックピボット行１０による消去演算を行っている。図４（ａ）は全体の係数行列４に対する演算であるが，このうちプロセッサ０の担当ブロック５（それぞれの大きさはＬＢ×ＬＢ）に対する演算を抜き出したものを図４（ｂ）に示す。図から明らかなように，ブロックピボット列のうちでプロセッサ０の演算で使われる部分９，ブロックピボット行のうちでプロセッサ０の演算で使われる部分１１を用いて，消去演算は大きさＭＢ＝４＊ＬＢの行列に対する乗算として処理できる。この結果，ｋを適当に選んでＭＢ×ＭＢの行列３個がちょうどキャッシュに入るようにすれば，キャッシュを最大限に利用することができ，単体性能が向上する。一方，従来の並列化ブロックガウス法では各ブロック段ごとに行列全体の消去演算を行うので，消去演算はＬＢ×ＬＢの行列乗算となるが，ＬＢの範囲は並列化効率の最適化との兼ね合いにより決められてしまい，単体性能を十分に発揮させることが難しい。本発明では、この点が大きく改良されている。
【００１６】
（実施例２）
実施例１では線形計算の一つであるガウス消去法の場合について説明したが、これ以外にも、ピボット列とピボット行とを用いて行列を消去していくという線形計算に対しては，本発明が適用可能である。このような線形計算の例としては、最小二乗法などに使われる行列のＱＲ分解や、固有値計算に使われるＨｏｕｓｅｈｏｌｄｅｒ変換などがある。本実施例では，最小二乗法への本発明の適用例を述べる。
【００１７】
最小二乗法の問題例として，実験により与えられたｍ個のの入力データと出力データの組（ｘ１，  ｙ１），（ｘ２，  ｙ２），．．．  ，（ｘｍ，  ｙｍ）に基づき，入力ｘと出力ｙの関係をｎ−１次式  ｙ  ＝  ｆ（ｘ）  で近似する問題を考える。求めたいのは，ｆ（ｘ）におけるｘの０次，１次，．．．  ，ｎ−１次の項の係数ａ１，ａ２，．．．  ，ａｎ  である。これを求めるには，最小二乗法の標準的な手続きにより，まず第ｉ番目の入力データｘｉのｊ−１乗を第（ｉ，  ｊ）要素とする行列Ａを求め，これを  Ａ  ＝  ＱＲとＱＲ分解してから，Ｒを係数行列とし，（Ｑの転置行列）×（ｙ１，  ｙ２，  ．．．  ，  ｙｍ）を右辺ベクトルとする連立一次方程式を解けばよい。この一連の処理のうち，もっとも計算量が多いのはＡのＱＲ分解の部分であり，これを並列機上で実行する場合に本発明が利用できる。
【００１８】
本発明の手法を用いて，このＱＲ分解を並列機上で実行する場合の処理を図６に示す。ＱＲ分解の場合も，並列化効率を最大にするように選んだブロックサイズＬＢにしたがって行列をブロックに分割し，プロセッサに割り当てる部分（処理２７）は実施例１のガウス消去法と同様である。ただし次の消去演算において，第Ｋブロックピボット行・列を作成するための前処理演算が，ガウス消去法の場合のＬＵ分解処理（図５の処理１６）からＱＲ分解処理（図６の処理２８）へと置き替わっている。また，第Ｋブロックピボット行・列の作成（図６の処理１６，１７）の詳細もガウス消去法の場合とは異なる。しかし，あらかじめ数本のブロックピボット行・列を作成しておき，ＭＢ／ＬＢ段に１回まとめて消去演算を行うという本発明の手法（処理２１）は全く同様に適用できる。また，この手法により得られる効果も，ガウス消去法の場合と同様である。
【００１９】
本実施例では他の線形演算に対する適用例として最小二乗法などに使われるＱＲ分解の場合を示したが，Ｈｏｕｓｅｈｏｌｄｅｒ変換など，さらに他の線形計算アルゴリズムに対しても，本手法は同様に適用できる。
【００２０】
【発明の効果】
以上説明したように，本発明によれば，並列計算機上でのガウス消去法などの線形計算において，単体性能と並列化効率とを共に高めることができ，並列計算機の性能を十分に引き出した計算が可能となる。
【図面の簡単な説明】
【図１】並列計算機による線形計算システムの全体を示す図である。
【図２】従来の並列化ブロックガウス法でのブロックへのプロセッサ割り当てを示す図である。
【図３】従来の並列化ブロックガウス法において，単体性能を高めるためにブロックサイズを大きく取った結果，各プロセッサの担当ブロック数が不均等になったことを示す図である。
【図４】本発明により，プロセッサ割り当てのためのブロックサイズを小さくとっても，消去演算のためのブロックサイズが大きく取れるようになったことを示す図である。
【図５】本発明をガウス消去法による連立一次方程式解法に適用した場合の手続き全体を示す図である。
【図６】本発明を行列のＱＲ分解に適用した場合の手続き全体を示す図である。
【符号の説明】
１：入力装置，２：連立一次方程式求解装置，３：出力装置，４：係数行列の全体，５：プロセッサ０の担当するブロック，６：プロセッサ１の担当するブロック，７：プロセッサ１５の担当するブロック，８：４段分のブロックピボット列の全体，９：ブロックピボット列のうちプロセッサ０の計算に使われる部分，１０：４段分のブロックピボット行の全体，１１：ブロックピボット行のうちプロセッサ０の計算に使われる部分，１２：スタート，１３：データの入力，１４：係数行列および右辺ベクトルのプロセッサへの割り当て，１５：最外側の繰り返しループ，１６：第（Ｋ，Ｋ）ブロックのＬＵ分解，１７：第Ｋブロックピボット列の作成，１８：第Ｋブロックピボット行の作成，１９：第Ｋブロックピボット列・行による部分的な消去演算，２０：ＫがＭＢ／ＬＢの倍数か否かの判定，２１：Ｋ段分の同時消去演算，２２：前進消去演算，２３：後退代入演算，２４：解ベクトルの収集，２５：解ベクトルの出力，２６：終了，２７：行列データのプロセッサへの割り当て，２８：第（Ｋ，Ｋ）ブロックのＱＲ分解，２９：解行列の収集，３０：解行列の出力，３１：プロセッサ，３２：キャッシュメモリ。
【図１】
0003542184.tif 000002
【図２】
0003542184.tif 000003
【図３】
0003542184.tif 000004
【図４】
0003542184.tif 000005
【図５】
0003542184.tif 000006
【図６】
0003542184.tif 000007