(57)【特許請求の範囲】
【請求項１】
ＬＵ分解を並列で実行する複数のプロセッサのうち第１のプロセッサに、
前記ＬＵ分解の対象である行列において前記第１のプロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列において前記第１のプロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行させるためのプログラム。
【請求項２】
前記行列積を計算する処理において、
前記行列積の計算と並行して、次の行列積の計算に使用される列パネルを、前記複数のプロセッサのうち他のプロセッサに送信又は当該他のプロセッサから受信する通信処理を実行する、
処理を実行させるための請求項１記載のプログラム。
【請求項３】
前記行列積を計算する処理において、
前記行列積の計算と前記通信処理とを複数回に分けて実行する、
処理を実行させるための請求項２記載のプログラム。
【請求項４】
前記第１のプロセッサに、
前記複数の列パネルの列方向の長さが異なる場合、前記複数の列パネルのうち列番号が最も小さい列パネルの先頭ブロックと、前記複数の行パネルのうち行番号が最も小さい行パネルとを用いて行列積を計算する
処理をさらに実行させるための請求項１乃至３のいずれか１つ記載のプログラム。
【請求項５】
前記複数の列パネルのうち列番号が最も小さい列パネルについて行交換を実行する、
処理をさらに実行させるための請求項１乃至４のいずれか１つ記載のプログラム。
【請求項６】
ＬＵ分解を並列で実行する複数のプロセッサ
を有し、
前記複数のプロセッサの各々が、
前記ＬＵ分解の対象である行列において当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列において当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行する並列計算機システム。
【請求項７】
ＬＵ分解を並列で実行する複数のプロセッサの各々が、
前記ＬＵ分解の対象である行列において当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列において当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行する並列計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算技術に関する。
【背景技術】
【０００２】
コンピュータシステムが連立一次方程式を解く際の計算性能を測定するためのベンチマークとして、Ｌｉｎｐａｃｋベンチマークが知られている。ＬｉｎｐａｃｋベンチマークはＴＯＰ５００のランク付けに使用されているため、連立一次方程式をコンピュータシステムによって高速に解く技術が注目されている。なお、Ｌｉｎｐａｃｋ自体は数値計算を行うためのソフトウエアライブラリであり、特に並列計算機システムにおける複数のノード（例えばプロセス或いはプロセッサコア等）が密行列の連立一次方程式を並列で解くためのライブラリがＨＰＬ（High-Performance Linpack）である。
【０００３】
通常、連立一次方程式Ａｘ＝ｂの計算においては、最初に行列Ａが上三角行列及び下三角行列に分解され（この分解はＬＵ分解と呼ばれる。）、その後にｘが求められる。ＨＰＬの場合、行列Ａが幅ＮＢのブロックに分割され、ブロック単位で処理が実行されてＬＵ分解が進行する。複数のノードの各々には１又は複数のブロックが割り当てられる。
【０００４】
図１を用いて、ＬＵ分解について説明する。図１の例では、行列Ａが１０×１０＝１００個のブロックに分割されている。各ブロックに属する要素は１００×１００＝１００００個であるとする。従って、ＮＢ＝１００であり、行列Ａは（１００×１０）×（１００×１０）＝１００００００個の要素を有する。丸印が付されたブロックは行列の対角要素を含むブロックであり、丸印が付されたブロックより上側の部分が上三角に相当し、丸印が付されたブロックより下側の部分が下三角に相当する。
【０００５】
図１の例では、行列Ａのブロックが６つのノードに割り当てられており、同じノードに割り当てられたブロックには同じ色が付けられている。図２を用いて、ブロックの割り当てについて説明する。図２の例では、行列Ａのブロックがノード（０，０）、（０，１）、（１，０）、（１，１）、（２，０）、及び（２，１）に割り当てられ、各ノードに割り当てられた行列Ａの一部がローカル配列としてメモリ等の記憶装置に格納される。ここでは、ノードに割り当てられるブロックの数は不均一である。具体的には、ノード（０，０）及び（０，１）に割り当てられるブロックの数は２０であるが、ノード（１，０）、（１，１）、（２，０）及び（２，１）に割り当てられるブロックの数は１５である。
【０００６】
ＬＵ分解を実行する場合、行列積を計算する際の部分小行列の幅が大きいほど（すなわち、ブロックサイズが大きいほど）行列積の計算効率が高くなり、実行時間が短縮される。しかしながら、ブロックサイズを大きくすると、例えば図２に示したように、各ノードに割り当てられるブロックの数が不均一になりロードバランスが悪くなるため、単純にブロックサイズを大きくすることはできない。従来技術においては、このような問題について十分な検討がなされていない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開第２００８／１３６０４５号
【特許文献２】特開２００８−１７６７３８号公報
【特許文献３】特開２０００−３３９２９５号公報
【特許文献４】特開２００６−８５６１９号公報
【非特許文献】
【０００８】
【非特許文献１】A. Petitet, R. C. Whaley, J. Dongarra, A. Cleary, "HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers", [平成２７年５月１日検索], インターネット
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、本発明の目的は、１つの側面では、並列計算機システムが連立一次方程式を解くのに要する時間を短縮するための技術を提供することである。
【課題を解決するための手段】
【００１０】
本発明に係る並列計算方法は、ＬＵ分解を並列で実行する複数のプロセッサの各々が、ＬＵ分解の対象である行列のパネルのうち当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、行列のパネルのうち当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、第１のパネルと第２のパネルとの行列積を計算する処理を含む。
【発明の効果】
【００１１】
１つの側面では、並列計算機システムが連立一次方程式を解くのに要する時間を短縮できるようになる。
【図面の簡単な説明】
【００１２】
【図１】図１は、ＬＵ分解について説明するための図である。
【図２】図２は、ＬＵ分解について説明するための図である。
【図３】図３は、本実施の形態で使用する記号について説明するための図である。
【図４】図４は、本実施の形態で使用する記号について説明するための図である。
【図５】図５は、本実施の形態で使用する記号について説明するための図である。
【図６】図６は、本実施の形態で使用する記号について説明するための図である。
【図７】図７は、並列計算機システムのシステム概要を示す図である。
【図８】図８は、ノードのハードウエア構成図である。
【図９】図９は、ノードの機能ブロック図である。
【図１０】図１０は、並列計算機システムが実行する処理の処理フローを示す図である。
【図１１】図１１は、パネル分解の処理フローを示す図である。
【図１２】図１２は、グローバル配列について説明するための図である。
【図１３】図１３は、ピボット情報の一例を示す図である。
【図１４】図１４は、パネル及びピボット情報の交換について説明するための図である。
【図１５】図１５は、パネル及びピボット情報の交換について説明するための図である。
【図１６】図１６は、行交換について説明するための図である。
【図１７】図１７は、行交換について説明するための図である。
【図１８】図１８は、行交換について説明するための図である。
【図１９】図１９は、更新計算について説明するための図である。
【図２０】図２０は、残りの処理について説明するための図である。
【図２１】図２１は、Ｌｏｏｋ−ａｈｅａｄを使用してＬＵ分解する処理の処理フローを示す図である。
【図２２】図２２は、パネル更新の処理フローを示す図である。
【図２３】図２３は、パネルの位置関係を示す図である。
【図２４】図２４は、並行実行について説明するための図である。
【図２５】図２５は、Ｌｏｏｋ−ａｈｅａｄを使用したＬＵ分解の具体例を示す図である。
【図２６】図２６は、Ｌｏｏｋ−ａｈｅａｄを使用したＬＵ分解の具体例を示す図である。
【図２７】図２７は、Ｌｏｏｋ−ａｈｅａｄを使用したＬＵ分解の具体例を示す図である。
【図２８】図２８は、Ｌｏｏｋ−ａｈｅａｄを使用したＬＵ分解の具体例を示す図である。
【図２９】図２９は、Ｌｏｏｋ−ａｈｅａｄを使用したＬＵ分解の具体例を示す図である。
【図３０】図３０は、計算量の差について説明するための図である。
【図３１】図３１は、計算量の差について説明するための図である。
【図３２】図３２は、本実施の形態におけるＬＵ分解の処理フローを示す図である。
【図３３】図３３は、行交換及び更新計算の処理フローを示す図である。
【図３４】図３４は、本実施の形態におけるＬＵ分解の処理フローを示す図である。
【図３５】図３５は、行列の統合について説明するための図である。
【図３６】図３６は、行列の再分割について説明するための図である。
【図３７】図３７は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図３８】図３８は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図３９】図３９は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図４０】図４０は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図４１】図４１は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図４２】図４２は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図４３】図４３は、本実施の形態におけるＬＵ分解の具体例を示す図である。
【図４４】図４４は、ＨＰＬによるＬＵ分解について説明するための図である。
【図４５】図４５は、ＨＰＬによるＬＵ分解について説明するための図である。
【図４６】図４６は、ＨＰＬによるＬＵ分解について説明するための図である。
【図４７】図４７は、ＨＰＬによるＬＵ分解について説明するための図である。
【図４８】図４８は、ＨＰＬによるＬＵ分解について説明するための図である。
【図４９】図４９は、ＨＰＬによるＬＵ分解について説明するための図である。
【図５０】図５０は、ＨＰＬによるＬＵ分解について説明するための図である。
【図５１】図５１は、ＨＰＬによるＬＵ分解について説明するための図である。
【発明を実施するための形態】
【００１３】
図３乃至図６を用いて、以下で使用する記号について説明する。図３に、図２のように各ノードにブロックを割り当てた場合においてノード（０，０）が担当するブロック並びにそのブロック内のＵパネル及びＬパネルを示す。図３に示すように、Ｕパネルとは、行列Ａの上三角部分に含まれる、行方向のブロック集合のことである。行列Ａにおけるｋ行目のＵパネルをＵkと表す。Ｕkのうち先頭ブロックに相当する部分をＵ３kと表し、ＵkからＵ３kを除いた場合における残りの部分をＵ２kと表す。以下では、ブロック集合のことを部分行列とも呼ぶ。なお、Ｕパネルは行パネルとも呼ばれ、Ｌパネルは列パネルとも呼ばれる。
【００１４】
Ｌパネルとは、行列Ａの下三角部分及び対角部分（ノードが保持している場合）を含む部分に含まれる、列方向のブロック集合のことである。行列Ａにおけるｋ列目のＬパネルをＬkと表す。Ｌkのうち先頭ブロックに相当する部分をＬ３kと表し、ＬkからＬ３kを除いた場合における残りの部分をＬ２kと表す。
【００１５】
図４に示すように、Ｕkの下の部分に相当する部分行列をＣkと表す。Ｕ２kの下の部分に相当する部分行列もＣkと表す。
【００１６】
図５に示すように、複数の部分行列を結合した行列を括弧で表す。例えば、ＬjとＬj+1とを行方向に結合した行列を［ＬjＬj+1］と表し、ＵjとＵj+1とを列方向に結合した行列を［ＵjＵj+1］Tと表す。
【００１７】
図６に、ＬＵ分解の対象となる行列Ａの全体図を示す。行列Ａは幅ＮＢのブロックに分割され、複数のノードにブロックが分配されるが、全体としては矢印の方向にＬＵ分解が進行する。そのため、ＬＵ分解においては、ノード間で行列の要素を交換するための通信が実行される。
【００１８】
図７に、並列計算機システム１のシステム概要を示す。並列計算機システム１は、複数のノードと、インターコネクト１０とを有する。複数のノードの各々には座標が割り当てられる。但し、座標は必ずしも実際の物理的位置を表すわけではなく、ＬＵ分解の実行時にノードを識別するために付される識別情報である。インターコネクト１０は、図７に示した形態に限られるわけではない。各ノードはインターコネクト１０を介して他のノードと通信を行うことができる。
【００１９】
図８に、ノードのハードウエア構成図を示す。ノードは、プロセッサ１０１と、メモリ１０２とを有する。プロセッサ１０１とメモリ１０２はバスによって接続される。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）である。メモリ１０２は、例えばメインメモリである。なお、ノードはその他のハードウエア（例えば外部記憶装置など）を有する場合もあるが、本実施の形態の主要な部分とは関係が無いので説明を省略する。また、ここではノードが情報処理装置である例を示したが、ノードがプロセッサ、プロセッサコア、或いはプロセス等であってもよい。
【００２０】
図９に、ノードの機能ブロック図を示す。ノードは、計算部１１１と、データ格納部１１２とを含む。プロセッサ１０１は、外部記憶装置等に格納されたプログラムをメモリ１０２にロードして実行することにより、計算部１１１を実現する。データ格納部１１２は、例えばメモリ１０２に設けられる。
【００２１】
［ＨＰＬによるＬＵ分解］
まず、図１０乃至図２０を用いて、通常のＨＰＬによるＬＵ分解について説明する。説明をわかりやすくするため、以下では、図２に示したように行列Ａを６台のノードで処理する例を示す。なお、ここでは本実施の形態の主要部に関係する部分について説明を行い、その他の部分については説明を簡略化又は省略する。通常のＨＰＬによるＬＵ分解の詳細は非特許文献１を参照のこと。
【００２２】
図１０は、全体の処理フローである。なお、並列計算機システム１内で行われる処理は複雑であり（例えば、各ノードはｊの値によって処理を実行する場合と実行しない場合とが有る）、各ノードが実行する処理を説明したとしても処理の全体像を把握することは困難である。そこで、ここでは並列計算機システム１が各ステップの処理を実行するととして説明を行う。但し、各ステップの実際の処理主体はノードの計算部１１１である。
【００２３】
まず、並列計算機システム１は、ブロックを計数するためのカウンタｊをｊ＝１と設定する（図１０：ステップＳ１）。
【００２４】
並列計算機システム１は、Ｌjのパネル分解を実行する（ステップＳ３）。パネル分解とは、列方向のパネルを分解する処理である。Ｌjのパネル分解については、図１１乃至図１３を用いて説明を行う。
【００２５】
まず、図１１のステップＳ２９乃至Ｓ４５の説明をわかりやすくするため、図１２を用いてグローバル配列の定義を行う。ここでは、各列ノードが持つＬjを結合することで得られる元のグローバル配列をＬＧjと表す。最も上に位置するブロックにおける左上隅の要素をＬＧj（ｊｊ，ｊｊ）とする。ここで、ｊｊ＝（ｊ−１）＊ｎｂ＋１である。各ブロックの幅をｎｂとし、列方向の位置をｉとし、ピボット情報をｉｐｉｖjとする。
【００２６】
並列計算機システム１は、ｉ＝ｊｊと設定し（図１１：ステップＳ２９）、ＬＧj（＊，ｉ）のうち絶対値が最大である要素の値Ｗ及び位置ｊｐを特定する（ステップＳ３１）。＊はワイルドカードである。ステップＳ３１においては、列方向のノード間で通信を行うことにより、Ｗ及びｊｐが特定される。
【００２７】
並列計算機システム１は、ピボット情報をｉｐｉｖj（ｉ−ｊｊ＋１）＝ｊｐと設定する（ステップＳ３３）。ピボット情報には、第ｉ行と交換された行の行番号ｊｐが設定される。図１３に示すように、ｉ＝５０の場合、第ｉ行と交換された行の行番号が４２０である場合には、ピボット情報はｉｐｉｖj（５０）＝４２０と設定される。ピボット情報のための領域はデータ格納部１１２に設けられる。
【００２８】
並列計算機システム１は、Ｗ＝０．０が成立するか判断する（ステップＳ３５）。Ｗ＝０．０が成立する場合（ステップＳ３５：Ｙｅｓルート）、ＬＵ分解を行うことができないため、処理は終了する。一方、Ｗ＝０．０が成立しない場合（ステップＳ３５：Ｎｏルート）、並列計算機システム１は、ＬＧj（ｉ，＊）とＬＧj（ｊｐ，＊）とを入れ替える（ステップＳ３７）。ステップＳ３７においては、或るノードがＬＧj（ｉ，＊）及びＬＧj（ｊｐ，＊）を両方有していれば列方向の通信を行うことなく入れ替えを行えるが、ＬＧj（ｉ，＊）及びＬＧj（ｊｐ，＊）を両方有していなければ列方向の通信によって入れ替えを行う。
【００２９】
並列計算機システム１は、ＬＧj（＊，ｉ）の値をＷで割り（ステップＳ３９）、ＬＧj（＊，ｉ）とＬＧj（ｉ，＊）との外積によって、これらの部分行列の右下に相当する部分を更新する（ステップＳ４１）。
【００３０】
並列計算機システム１は、ｉ＝ｊｊ＋ｎｂ−１が成立するか判断する（ステップＳ４３）。ｉ＝ｊｊ＋ｎｂ−１が成立しない場合（ステップＳ４３：Ｎｏルート）、並列計算機システム１は、ｉを１インクリメントし（ステップＳ４５）、処理はステップＳ３１の処理に戻る。一方、ｉ＝ｊｊ＋ｎｂ−１が成立する場合（ステップＳ４３：Ｙｅｓルート）、呼び出し元の処理に戻る。
【００３１】
図１０の説明に戻り、並列計算機システム１における各ノードは、ＬjとＬjのパネル分解時に取得したピボット情報とを他のノードと交換する（ステップＳ５）。ステップＳ５において行われる通信は、行方向の通信である。例えば図１４に示すように、自ノード（ここでは、ノード（０，０）とする）がルートノード（Ｌjパネルを保持しているノード）である場合を考える。この場合には、Ｌjパネル及びＬjのパネル分解時のピボット情報（ｉｐｉｖj）をデータ格納部１１２に含まれる通信バッファにコピーし、次のノード（ここでは、ノード（０，１））に送信する。
【００３２】
一方、自ノード（ここでは、ノード（０，０）とする）がルートノードではない場合、図１５に示すように、Ｌjパネル及びＬjのパネル分解時のピボット情報（ｉｐｉｖj）を他ノード（ここでは、ノード（０，１））から受信して、通信バッファに格納する。そして、ノード（０，０）は、通信バッファに格納されたＬjパネル及びＬjのパネル分解時のピボット情報（ｉｐｉｖj）を、次ノードに送信する。但し、次ノードはルートノードではないとする。このようにすることで、各ノードがＬjパネル及びＬjのパネル分解時のピボット情報（ｉｐｉｖj）を保持するようになる。
【００３３】
並列計算機システム１は、Ｌjのパネル分解時に取得したピボット情報によって、Ｕj及びＣjの行交換を実行する（ステップＳ７）。ステップＳ７においても通信が行われるが、この通信は列方向の通信である。
【００３４】
図１６乃至図１８を用いて、ステップＳ７における行交換について説明する。まず、図１６に示すように、ノード（ノード（０，０）とする）は、Ｕjを同じ列のノード（ここでは、ノード（１，０）及び（２，０））に送信する。但し、Ｕjを他のノードが保持している場合にはＵjを他のノードから受信する。図１６において、Ｃj_(0,0)はノード（０，０）のＣjである。
【００３５】
ｉｐｉｖjには、Ｕjの第ｉ行と交換されるべき行のグローバルな行番号が設定されている。図１７に示すように、ノード（０，０）は、そのうち自ノードが保持する行の要素を集め、ノード（１，０）及び（２，０）に送信する。また、ノード（０，０）は他のノードが保持する交換対象の行の要素を受信する。
【００３６】
そして、図１８に示すように、ノード（０，０）は、交換対象の行とＵjにおける行との間で行交換を実行する。
【００３７】
そして、並列計算機システム１は、Ｕjの更新計算を実行する（ステップＳ９）。なお、ステップＳ９の処理の前には、列方向の通信が行われる。
【００３８】
図１９を用いて、Ｕjの更新計算について説明する。Ｕjの更新計算においては、連立一次方程式Ｌ３LjＸ＝Ｕjを解き、元のＵjをＸで置き換える。ここで、Ｌ３Ljは、Ｌjの先頭ブロックにおける下三角部分を含む下三角行列に相当し、対角部分の要素は１．０に設定されている。Ｌ３Ljは下三角行列であるので、Ｕjの各列について後退代入を行えばよい。
【００３９】
並列計算機システム１は、行列計算Ｃj←Ｃj−ＬjＵjを実行し（ステップＳ１１）、カウンタｊを１インクリメントする（ステップＳ１３）。
【００４０】
並列計算機システム１は、ｊ＞（全ブロック数）が成立するか判断する（ステップＳ１５）。全ブロック数とは、行方向及び列方向のブロック数である。ｊ＞（全ブロック数）が成立しない場合（ステップＳ１５：Ｎｏルート）、次のｊについて処理するため、ステップＳ３の処理に戻る。一方、ｊ＞（全ブロック数）が成立する場合（ステップＳ１５：Ｙｅｓルート）、並列計算機システム１は、行列Ａの残りの部分についての処理を実行する（ステップＳ１７）。そして処理は終了する。
【００４１】
例えば、正方行列である行列Ａの行数及び列数を表すＮをＮＢで割り切ることができないとする。すると、図２０に示すように、行列Ａの残余としてＭ×Ｍ（Ｍ＝ｍｏｄ（Ｎ，ＮＢ））の部分行列が残る。例えばＮが１０５０であり且つＮＢ＝１００である場合、ノード（１，０）に５０×５０の部分行列が残る。ステップＳ１７においては、残りの部分について、図１１のステップＳ２９乃至Ｓ４５の処理によってＬＵ分解を行う。但し、残りの部分行列は１つのノード内に存在するため、ノード間での通信は発生しない。
【００４２】
［Ｌｏｏｋ−ａｈｅａｄを使用した場合のＬＵ分解］
以上がＬＵ分解の基本的な処理内容であるが、さらに「Ｌｏｏｋ−ａｈｅａｄ」と呼ばれる技術を使用してＬＵ分解を実行することも可能である。この方法においては、通信と行列計算とを並行して実行するので、ＬＵ分解の実行時間を短縮することができる。以下では、図２１乃至図２９を用いて、Ｌｏｏｋ−ａｈｅａｄを使用してＬＵ分解を実行する方法について説明する。
【００４３】
まず、並列計算機システム１は、最初のＤ（ＤはＬｏｏｋ−ａｈｅａｄの深さである）個のＬパネルＬ1乃至ＬDをパネル分解し、ノードの間におけるパネルの送受信を行う（図２１：ステップＳ５１）。
【００４４】
並列計算機システム１は、ブロックを計数するためのカウンタｊをｊ＝１と設定する（ステップＳ５３）。
【００４５】
並列計算機システム１は、Ｌj+Dの更新及びパネル分解を実行する（ステップＳ５５）。パネル分解は、ステップＳ３において説明したとおりである。更新については、図２２及び図２３を用いて説明する。
【００４６】
並列計算機システム１は、Ｌj+D-1のパネル分解時に得られたピボット情報によって、Ｕ３j+D-1及びＬj+Dについて行交換を実行する（図２２：ステップＳ２１）。図２３に、Ｌj+D-1、Ｌj+D及びＵ３j+D-1の位置関係を示す。図２３に示すように、Ｕ３j+D-1はＬj+Dの上側に位置するブロックである。行交換は、上で説明したとおりである。
【００４７】
並列計算機システム１は、Ｕ３j+Dの更新計算を実行する（ステップＳ２３）。更新計算は、上で説明したとおりである。
【００４８】
並列計算機システム１は、行列計算Ｌj+D←Ｌj+D−Ｌ２j+D-1Ｕ３j+D-1を実行する（ステップＳ２５）。矢印は代入を表す記号である。そして呼び出し元の処理（図２１）に戻る。
【００４９】
並列計算機システム１は、Ｌjのパネル分解時に取得したピボット情報によって、Ｕj及びＣjの行交換を実行する（ステップＳ５７）。
【００５０】
並列計算機システム１は、Ｕjの更新計算を実行する（ステップＳ５９）。
【００５１】
並列計算機システム１における各ノードは、Ｌj+DとＬj+Dのパネル分解時に取得したピボット情報とを他のノードと交換する（ステップＳ６１）。また、並列計算機システム１は、ステップＳ６１の処理と並行して、行列計算Ｃj←Ｃj−ＬjＵjを実行する（ステップＳ６３）。図２１における破線は、ステップＳ６１とＳ６３とが並行して実行されることを表す。
【００５２】
ステップＳ６３について、図２４に具体例を示す。ここでは、ｊ番目のブロックが処理されており、Ｄ＝２であるとする。この場合には、図２４に示すように、Ｌj+2の通信と並行して、行列計算Ｃj←Ｃj−ＬjＵjが実行される。
【００５３】
並列計算機システム１は、カウンタｊを１インクリメントし（ステップＳ６５）、ｊ＞（全ブロック数−Ｄ）が成立するか判断する（ステップＳ６７）。ｊ＞（全ブロック数−Ｄ）が成立しない場合（ステップＳ６７：Ｎｏルート）、次のｊについて処理するため、ステップＳ５５の処理に戻る。一方、ｊ＞（全ブロック数−Ｄ）が成立する場合（ステップＳ６７：Ｙｅｓルート）、並列計算機システム１は、行列Ａの残りの部分についての処理を実行する（ステップＳ６９）。そして処理は終了する。
【００５４】
さらに、Ｌｏｏｋ−ａｈｅａｄを使用してＬＵ分解を実行する方法について、図２５乃至図２９に処理の具体例を示す。ここでは、ノード（０，０）が実行する処理を例にして、ｊ＝１からｊ＝４までについて説明する。
【００５５】
まず、ノード（０，０）は、Ｌ1のパネル分解を実行し（図２５の（１））、Ｌ1及びＬ1のパネル分解時に得られたピボット情報をノード（０，１）に送信する（図２５の（２））。ノード（０，０）がＬ1を保持しているとする。
【００５６】
次に、Ｌ2のパネル分解が実行される（図２５の（３））。Ｌ2のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【００５７】
ノード（０，０）は、Ｌ2及びＬ2のパネル分解時に得られたピボット情報をノード（０，１）から受信する（図２５の（４））。
【００５８】
図２６の説明に移行し、ノード（０，０）は、Ｌ3のパネル分解を実行し（図２６の（５））、Ｌ1のパネル分解時に取得したピボット情報によってＵ２1及びＣ1について行交換を実行する（図２６の（６））。
【００５９】
ノード（０，０）は、Ｕ２1の更新計算を実行する（図２６の（７））。
【００６０】
ノード（０，０）は、行列計算Ｃ1←Ｃ1−Ｌ２1Ｕ２1を実行しながら、Ｌ3及びＬ3の分解時に得られたピボット情報をノード（０，１）に送信する（図２６の（８））。
【００６１】
図２７の説明に移行し、Ｌ4のパネル分解が実行される（図２７の（９））。Ｌ4のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【００６２】
ノード（０，０）は、Ｌ2のパネル分解時に取得したピボット情報によってＵ2及びＣ2について行交換を実行する（図２７の（１０））。
【００６３】
ノード（０，０）は、Ｕ2の更新計算を実行する（図２７の（１１））。
【００６４】
ノード（０，０）は、行列計算Ｃ2←Ｃ2−Ｌ2Ｕ2を計算しながら、Ｌ4及びＬ4の分解時に得られたピボット情報をノード（０，１）から受信する（図２７の（１２））。
【００６５】
図２８の説明に移行し、ノード（０，０）は、Ｌ5のパネル分解を実行し（図２８の（１３））、Ｌ3のパネル分解時に取得したピボット情報によってＵ２3及びＣ3について行交換を実行する（図２８の（１４））。
【００６６】
ノード（０，０）は、Ｕ２3の更新計算を実行する（図２８の（１５））。
【００６７】
ノード（０，０）は、行列計算Ｃ3←Ｃ3−Ｌ２3Ｕ２3を実行しながら、Ｌ5及びＬ5の分解時に得られたピボット情報をノード（０，１）に送信する（図２８の（１６））。
【００６８】
図２９の説明に移行し、Ｌ6のパネル分解が実行される（図２９の（１７））。Ｌ6のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【００６９】
ノード（０，０）は、Ｌ4のパネル分解時に取得したピボット情報によってＵ２4及びＣ4について行交換を実行する（図２９の（１８））。
【００７０】
ノード（０，０）は、Ｕ２4の更新計算を実行する（図２９の（１９））。
【００７１】
ノード（０，０）は、行列計算Ｃ4←Ｃ4−Ｌ２4Ｕ２4を実行しながら、Ｌ6及びＬ6の分解時に得られたピボット情報をノード（０，１）から受信する（図２９の（２０））。
【００７２】
以上のように、Ｌjのパネル分解及びそのパネルの通信処理を、ループの繰り返しにおけるＤ回前において行うので、ノード間で交換するＬj+Dと行列計算で使用するＬjとが同じではなくなり依存関係がなくなる。これにより、通信と行列計算とを並行して実行することが可能になる。例えば、通信の開始を待つ間に行列計算を行うといったことが可能になる。
【００７３】
なお、ＬＵ分解において行われる処理のうち行列積の計算は、計算量が最も多く時間がかかる処理である。よって、行列積を高速に計算することができれば、実行時間を大幅に短縮することができる。行列積の計算は、ブロックサイズＮＢと同じ幅で実行される。一般に、行列のサイズが大きい方が計算効率が上がるため、行列積の計算だけを考えるのであればＮＢをできるだけ大きくすることが好ましい。
【００７４】
しかし、ロードバランスを良くするためには、ＮＢはできるだけ小さい方がよい。各ノードが処理する行列のサイズは、ＬＵ分解が進行するにつれてＮＢずつ小さくなる。但し、全ノードにおいて同時に行列のサイズが小さくなるのではなく、その時点の計算に関わるノードのみにおいて行列のサイズが小さくなる。よって、ノードが保持する行列のサイズの差がＮＢになる場合がある。この差が行列積の計算量の差をもたらす。ロードバランスが悪い場合、計算量が少ないノードは計算量が多いノードの計算が終わるまで待つことになり、全体として計算時間が長くなる。
【００７５】
図３０及び図３１を用いて、この問題について説明する。図３０におけるグローバル行列Ａは４０００００×４０００００の正方行列であり、ＮＢ＝１０００であり、１０×１０＝１００のノードにブロックが分配される。従って、１台のノードには４００００×４００００のローカル行列が割り当てられる。グローバル行列Ａにおいて斜線が付されたブロックは、ノード（０，０）に割り当てられるブロックである。
【００７６】
図３１に示すように、ノード（０，０）が１ブロック分の処理を完了した場合、ノード（０，０）は次に（３９０００，１０００）と（１０００，３９０００）との行列積を計算する。このときの計算量（加算及び乗算の回数）は３．０４Ｅ＋１２（回）である。このとき、ノード（９，９）は（４００００，１０００）と（１０００，４００００）との行列積を計算する。このときの計算量は３．２０Ｅ＋１２（回）である。よって、ノード（９，９）の計算量はノード（０，０）の計算量よりおおよそ５％多い。ここで、ブロックサイズＮＢ＝５００であるとすると、ノード（０，０）は（３９５００，５００）と（５００，３９５００）との行列積を計算する。このときの計算量は１．５６Ｅ＋１２（回）である。このとき、ノード（９，９）は（４００００，５００）と（５００，４００００）との行列積を計算する。このときの計算量は１．６０Ｅ＋１２（回）である。よって、ノード（９，９）の計算量はノード（０，０）の計算量よりおおよそ２．５％多い。
【００７７】
そこで、ロードバランスが良い比較的小さめのＮＢを使用しつつ、より大きな幅で行列積を計算できるようにするため、複数の行列積計算を統合して大きな幅で行列積計算を行う（例えば、図２６の（８）及び図２７の（１２）を統合する）ことを考える。しかし、この方法には以下のような問題が有る。
【００７８】
第１の問題は、処理順序の問題である。図２６の（８）における行列積と図２７の（１２）における行列積とを統合する場合、図２６の（８）の処理を図２７の（１２）の処理の時点において実行することになる。しかし、図２７の（１０）の処理においてＣ1の領域について行交換が行われて領域が更新されるため、図２７の（１０）の処理を実行した後においてはＣ2の行の位置とＬ1の行の位置とが対応しない。よって、図２６の（８）を図２７の（１０）より後に実行することはできず、図２６の（８）における行列積と図２７の（１２）における行列積とを統合することはできない。
【００７９】
第２の問題は、行列のサイズの問題である。ブロックの処理が進行することに伴い、Ｌj+1のサイズがＬjのサイズより１ブロック分小さくなる場合がある。この場合、Ｌj+1とＬjをそのまま結合することはできない。上で示した具体例においては、図２８の（１６）及び図２９の（２０）が該当する。図２８の（１６）においてはＬ3のサイズが３ブロック分であるが、図２９の（２０）においてはＬ２4のサイズが２ブロック分である。このように、行列のサイズが異なると、これらの行列をそのまま結合することはできず、１回の行列積で処理を完了させることはできない。
【００８０】
第３の問題は、Ｌｏｏｋ−ａｈｅａｄを使用した場合における通信の問題である。Ｌｏｏｋ−ａｈｅａｄを使用する場合、図２６の（８）及び図２７の（１２）に示したように、１回の行列積に対して１回の通信を実行する。複数回の行列積を統合して１回の行列積にする場合、１回分の通信を行列積の計算と並行して実行することはできるものの、残りの通信を行列積の計算と並行して実行することはできない。そのため、実行時間が長くなってしまう。
【００８１】
そこで、以下では、行列積の計算性能とロードバランスとを両立するようにＬＵ分解を実行する方法について説明する。
【００８２】
［本実施の形態のＬＵ分解］
本実施の形態における並列計算機システム１のシステム概要、ノードのハードウエア構成、及びノードの機能ブロックは、図７乃至図９に示したとおりである。
【００８３】
図３２乃至図４３を用いて、本実施の形態のＬＵ分解について説明する。
【００８４】
まず、並列計算機システム１は、最初のＤ（ＤはＬｏｏｋ−ａｈｅａｄの深さである）個のＬパネルＬ1乃至ＬDをパネル分解し、ノード間におけるパネルの送受信を行う（図３２：ステップＳ７１）。
【００８５】
並列計算機システム１は、ブロックを計数するためのカウンタｊをｊ＝１と設定し、処理の回数を計数するためのカウンタｉｄをｉｄ＝０と設定する（ステップＳ７３）。
【００８６】
並列計算機システム１は、Ｌj+Dの更新及びパネル分解を実行する（ステップＳ７５）。本処理はステップＳ３及びＳ５５において説明したとおりである。
【００８７】
並列計算機システム１は、ｉｄ＝＝０が成立するか判断する（ステップＳ７７）。「＝＝」は等価演算子である。ｉｄ＝＝０が成立しない場合（ステップＳ７７：Ｎｏルート）、処理は端子Ｂを介して図３４のステップＳ８３に移行する。一方、ｉｄ＝＝０が成立する場合（ステップＳ７７：Ｙｅｓルート）、並列計算機システム１は、行交換及び更新計算を実行する（ステップＳ７９）。ステップＳ７９における行交換及び更新計算については、図３３を用いて説明する。
【００８８】
まず、並列計算機システム１は、カウンタｋをｋ＝０と設定し（図３３：ステップＳ１０１）、Ｌkのパネル分解時のピボット情報によってＵj+kについて行交換を実行する（ステップＳ１０３）。
【００８９】
並列計算機システム１は、カウンタｋｋをｋｋ＝０と設定し（ステップＳ１０５）、ｋｋ＜ｋが成立するか判断する（ステップＳ１０７）。ｋｋ＜ｋが成立する場合（ステップＳ１０７：Ｙｅｓルート）、並列計算機システム１は、Ｌj+kのパネル分解時のピボット情報によってＬj+kkについて行交換を実行する（ステップＳ１０９）。
【００９０】
並列計算機システム１は、Ｌj+kkの列方向の長さがＬj+kの列方向の長さより長い場合に、行列計算Ｃ３j+kk←Ｃ３j+kk−Ｌj+kkＵj+kkを実行する（ステップＳ１１１）。
【００９１】
並列計算機システム１は、カウンタｋｋを１インクリメントする（ステップＳ１１３）。そしてステップＳ１０７の処理に戻る。
【００９２】
一方、ｋｋ＜ｋが成立しない場合（ステップＳ１０７：Ｎｏルート）、並列計算機システム１は、Ｕj+kの更新計算を実行し（ステップＳ１１５）、ｋを１インクリメントする（ステップＳ１１７）。
【００９３】
並列計算機システム１は、ｋ＜ｄが成立するか判断する（ステップＳ１１９）。ｄは統合される行列の数を表す。ｋ＜ｄが成立する場合（ステップＳ１１９：Ｙｅｓルート）、ステップＳ１０３の処理に戻る。ｋ＜ｄが成立しない場合（ステップＳ１１９：Ｎｏルート）、呼び出し元の処理に戻る。
【００９４】
図３２の説明に戻り、並列計算機システム１は、Ｌj、・・・、Ｌj+d-1をデータ格納部１１２における１つの作業領域にコピーして［Ｌj・・・Ｌj+d-1］を生成し、Ｕj、・・・、Ｕj+d-1をデータ格納部１１２における１つの作業領域にコピーして［Ｕj・・・Ｕj+d-1］Tを生成する（ステップＳ８１）。処理は端子Ｂを介して図３４のステップＳ８３の処理に移行する。
【００９５】
図３４の説明に移行し、並列計算機システム１における各ノードは、Ｌj+DとＬj+Dのパネル分解時に取得したピボット情報とを他のノードと交換する（ステップＳ８３）。
【００９６】
並列計算機システム１は、行列計算「Ｃj+d-1←Ｃj+d-1−［Ｌj・・・Ｌj+d-1］［Ｕj・・・Ｕj+d-1］T」の１／ｄを実行する（ステップＳ８５）。図３４における破線は、ステップＳ８３とステップＳ８５とを並行して実行することを表す。ステップＳ８５においては、Ｌパネルの長さとＵパネルの長さとを比較し、長い方のパネルをｄ個に分割するように行列計算を行うことで、計算効率の低下を抑制する。なお、長さを揃えるため又は行列Ａの対角部分に相当するブロックを取り除くため、ＬパネルについてはＬ２を使用し、ＵパネルについてはＵ２を使用する場合がある。
【００９７】
図３５に、ステップＳ８５の具体例を示す。図３５には、ｊ番目のブロックを処理する際に使用される部分行列が示されており、ｄ＝２であるとする。この場合には、まずＬj+1のパネル分解時のピボット情報によってＬjの行交換が実行される。Ｌjの長さとＬj+1の長さとが異なる場合、Ｌ３jが存在するため、Ｃ３j←Ｃ３j−Ｌ３jＵjが別途計算される。そして、Ｌ２jとＬj+1とが行方向に統合され、ＵjとＵj+1とが列方向に統合され、行列計算が行われる。但し、ｄ＝２である場合には、図３６に示すように、１回のステップＳ８５の処理によって行列計算の１／２が実行される。まず上半分について行列計算が行われ、次に残りである下半分について行列計算が行われる。
【００９８】
並列計算機システム１は、ｊ＝ｊ＋１と設定し、ｉｄ＝ｉｄ＋１と設定する（ステップＳ８７）。但し、ｉｄ＝ｄである場合にはｉｄ＝０と設定する。
【００９９】
並列計算機システム１は、ｊ＞（全ブロック数−Ｄ）が成立するか判断する（ステップＳ８９）。全ブロック数とは、行方向及び列方向のブロック数である。ｊ＞（全ブロック数−Ｄ）が成立しない場合（ステップＳ８９：Ｎｏルート）、処理は端子Ｃを介して図３２のステップＳ７５の処理に戻る。一方、ｊ＞（全ブロック数−Ｄ）が成立する場合（ステップＳ８９：Ｙｅｓルート）、並列計算機システム１は、残りの部分について処理を実行する（ステップＳ９１）。そして処理は終了する。
【０１００】
さらに、図３７乃至図４３に、本実施の形態のＬＵ分解について処理の具体例を示す。ここでは、ノード（０，０）が実行する処理を例にして、ｊ＝１からｊ＝４までについて説明する。
【０１０１】
まず、ノード（０，０）は、Ｌ1のパネル分解を実行し（図３７の（１））、Ｌ1及びＬ1のパネル分解時に得られたピボット情報をノード（０，１）に送信する（図３７の（２））。ここでは、ノード（０，０）がＬ1を保持しているとする。
【０１０２】
次に、Ｌ2のパネル分解が実行される（図３７の（３））。Ｌ2のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【０１０３】
ノード（０，０）は、Ｌ2及びＬ2のパネル分解時に得られたピボット情報をノード（０，１）から受信する（図３７の（４））。
【０１０４】
図３８の説明に移行し、ノード（０，０）は、Ｌ3のパネル分解を実行し（図３８の（５））、Ｌ1のパネル分解時に取得したピボット情報によってＵ２1及びＣ1について行交換を実行する（図３８の（６））。
【０１０５】
ノード（０，０）は、Ｕ２1の更新計算を実行する（図３８の（７））。
【０１０６】
ノード（０，０）は、Ｌ2のパネル分解時に得られたピボット情報によって、Ｕ2及びＣ2について行交換を実行する（図３８の（８））。
【０１０７】
図３９の説明に移行し、ノード（０，０）は、Ｌ2のパネル分解時に得られたピボット情報によって、Ｌ２1について行交換を実行する（図３９の（９））。
【０１０８】
ノード（０，０）は、Ｌ２1がＬ2より長い場合、Ｃ1の先頭行ブロック（ここでは、Ｃ３1とする）を、Ｃ３1←Ｃ３1−Ｌ３1Ｕ1によって計算する（図３９の（１０））。今回はＬ２1の長さがＬ2の長さと同じであるため、処理を省略する。
【０１０９】
ノード（０，０）は、Ｕ2の更新計算を実行する（図３９の（１１））。
【０１１０】
ノード（０，０）は、Ｌパネル及びＵパネルをそれぞれ１つの作業領域にコピーし、行列の統合を行う（図３９の（１２））。
【０１１１】
図４０の説明に移行し、ノード（０，０）は、行列計算Ｃ2←Ｃ2−［Ｌ２1Ｌ2］［Ｕ２1Ｕ2］Tの上半分を実行しながら、Ｌ3及びＬ3のパネル分解時に得られたピボット情報をノード（０，１）に送信する（図４０の（１３））。
【０１１２】
次に、Ｌ4のパネル分解が実行される（図４０の（１４））。Ｌ4のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【０１１３】
ノード（０，０）は、行列計算Ｃ2←Ｃ2−［Ｌ２1Ｌ2］［Ｕ２1Ｕ2］Tの下半分を実行しながら、Ｌ4及びＬ4のパネル分解時に得られたピボット情報をノード（０，１）から受信する（図４０の（１５））。
【０１１４】
図４１の説明に移行し、ノード（０，０）は、Ｌ5のパネル分解を実行し（図４１の（１６））、Ｌ3のパネル分解時に取得したピボット情報によってＵ２3及びＣ3について行交換を実行する（図４１の（１７））。
【０１１５】
ノード（０，０）は、Ｕ２3の更新計算を実行する（図４１の（１８））。
【０１１６】
ノード（０，０）は、Ｌ4のパネル分解時に得られたピボット情報によって、Ｕ２4及びＣ4について行交換を実行する（図４１の（１９））。
【０１１７】
図４２の説明に移行し、ノード（０，０）は、Ｌ4のパネル分解時に得られたピボット情報によって、Ｌ3について行交換を実行する（図４２の（２０））。
【０１１８】
Ｌ3がＬ２4より長い場合、ノード（０，０）は、Ｃ3の先頭行ブロック（ここでは、Ｃ３3とする）を、Ｃ３3←Ｃ３3−Ｌ３3Ｕ２3によって計算する（図４２の（２１））。今回はＬ3がＬ２4より長いため、ノード（０，０）はＣ３3←Ｃ３3−Ｌ３3Ｕ２3を計算する。
【０１１９】
ノード（０，０）は、Ｕ２4の更新計算を実行する（図４２の（２２））。
【０１２０】
ノード（０，０）は、Ｌパネル及びＵパネルをそれぞれ１つの作業領域にコピーし、行列の統合を行う（図４２の（２３））。
【０１２１】
図４３の説明に移行し、ノード（０，０）は、行列計算Ｃ4←Ｃ4−［Ｌ２3Ｌ２4］［Ｕ２3Ｕ２4］Tの上半分を実行しながら、Ｌ5及びＬ5のパネル分解時に得られたピボット情報をノード（０，１）に送信する（図４３の（２４））。
【０１２２】
次に、Ｌ6のパネル分解が実行される（図４３の（２５））。Ｌ6のパネル分解はノード（＊，１）のみが実行するので、ノード（０，０）は実行しない。
【０１２３】
ノード（０，０）は、行列計算Ｃ4←Ｃ4−［Ｌ２3Ｌ２4］［Ｕ２3Ｕ２4］Tの下半分を実行しながら、Ｌ6及びＬ6のパネル分解時に得られたピボット情報をノード（０，１）から受信する（図４３の（２６））。
【０１２４】
以上のような処理を実行すれば、第１乃至第３の問題に対処できるようになる。まず、第１の問題については、図２７の（８）の処理を図２８の（１０）の処理の後に実行できるようにするため、図２８（１０）において実行する行交換をＬ２1についても実行する（図３９の（９））。これにより、Ｌ２1の行とＣ2の行との対応を取ることができるようになり、図２８の（１０）に相当する処理より後に行列計算Ｃ2←Ｃ2−Ｌ２1Ｕ２1に相当する処理を実行できるようになる。
【０１２５】
第２の問題については、図３９の（１０）の処理及び図４２の（２１）の処理によって対処する。これらの処理において、Ｌパネルの長さが異なる場合に別途行列計算を行っておくことで、Ｌ２3の長さとＬ２4の長さとを同じにすることができるようになる。
【０１２６】
第３の問題については、統合した行列をｄ個に再分割することによって対処する。これにより、分割によって生成された行列に基づく行列計算と通信とを並行して実行することができるので、通信時間を隠蔽し実行時間を短縮することができるようになる。
【０１２７】
以上のように、本実施の形態の処理によれば、並列計算機システム１が連立一次方程式を解くのに要する時間を短縮することができるようになる。
【０１２８】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明したノードの機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。また、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【０１２９】
なお、ＤはＤ≧ｄを満たすが、Ｄをｄより大きい値としても性能向上に寄与するとは限らないため、Ｄ＝ｄであることが好ましい。
【０１３０】
［付録］
本付録においては、ＨＰＬによるＬＵ分解について簡単な説明を追加する。
【０１３１】
ここでは、図４４に示すように、グローバル行列Ａを４つのプロセスＰ０乃至Ｐ３に割り当てることを考える。プロセスグリッド（Ｐ，Ｑ）は（２，２）である。各プロセスに割り当てられるブロックを図４５に示す。各プロセスには同じ数（＝９）のブロックが割り当てられる。
【０１３２】
図４６に、パネル分解において行われる通信の一例を示す。パネル分解においては、列方向（縦方向）の通信が、一の位が０であるブロックを有するプロセス間で行われる。パネル分解時にはピボット情報が保存される。
【０１３３】
図４７に、列パネルのブロードキャストの一例を示す。列パネルのブロードキャストにおいては、行方向（横方向）の通信が、行プロセス間で行われる。
【０１３４】
図４８に、行交換において行われる通信の一例を示す。行交換においては、列方向の通信が、列プロセス間で行われる。行交換は、保存されたピボット情報に基づき行われる。
【０１３５】
図４９に、更新計算の対象となるブロックの一例を示す。更新計算においては、十の位が０である行ブロックを有するプロセスにおいて更新計算が行われる。すなわち、プロセスＰ０及びプロセスＰ２が更新計算を実行する。
【０１３６】
図５０に、行パネルのブロードキャストの一例を示す。行パネルのブロードキャストにおいては、列方向の通信が、列プロセス間で行われる。
【０１３７】
図５１に、残行列の更新計算の一例を示す。本更新計算においては、ブロック２０、４０、１０、３０、及び５０を含むブロック集合の行列と、ブロック０２、０４、０１、０３、及び０５を含むブロック集合の行列とを用いて更新計算が行われる。以上で付録を終了する。
【０１３８】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１３９】
本実施の形態に係る並列計算方法は、ＬＵ分解を並列で実行する複数のプロセッサの各々が、（Ａ）ＬＵ分解の対象である行列のパネルのうち当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、（Ｂ）行列のパネルのうち当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、（Ｃ）第１のパネルと第２のパネルとの行列積を計算する処理を含む。
【０１４０】
このようにすれば、行列積の計算効率が上がるため、連立一次方程式を解くのに要する時間を短縮できるようになる。
【０１４１】
また、行列積を計算する処理において、（ｃ１）行列積の計算と並行して、次の行列積の計算に使用される列パネルを、複数のプロセッサのうち他のプロセッサに送信又は当該他のプロセッサから受信する通信処理を実行してもよい。このようすれば、通信時間を隠蔽できるので、連立一次方程式を解くのに要する時間をさらに短縮できるようになる。
【０１４２】
また、行列積を計算する処理において、（ｃ２）行列積の計算と通信処理とを複数回に分けて実行してもよい。このようにすれば、実行すべき通信処理を漏れなく実行できるようになる。
【０１４３】
また、本並列計算方法が、（Ｄ）複数の列パネルの列方向の長さが異なる場合、複数の列パネルのうち列番号が最も小さい列パネルの先頭ブロックと、複数の行パネルのうち行番号が最も小さい行パネルとを用いて行列積を計算する処理をさらに含んでもよい。このようにすれば、列方向の長さが異なる場合にも対処できるようになる。
【０１４４】
また、本並列計算方法が、（Ｅ）複数の列パネルのうち列番号が最も小さい列パネルについて行交換を実行する処理をさらに含んでもよい。複数のパネルを統合した場合に発生する処理順序の問題を解消できるようになる。
【０１４５】
なお、上記方法による処理をプロセッサに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１４６】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１４７】
（付記１）
ＬＵ分解を並列で実行する複数のプロセッサのうち第１のプロセッサに、
前記ＬＵ分解の対象である行列のパネルのうち前記第１のプロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列のパネルのうち前記第１のプロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行させるためのプログラム。
【０１４８】
（付記２）
前記行列積を計算する処理において、
前記行列積の計算と並行して、次の行列積の計算に使用される列パネルを、前記複数のプロセッサのうち他のプロセッサに送信又は当該他のプロセッサから受信する通信処理を実行する、
処理を実行させるための付記１記載のプログラム。
【０１４９】
（付記３）
前記行列積を計算する処理において、
前記行列積の計算と前記通信処理とを複数回に分けて実行する、
処理を実行させるための付記２記載のプログラム。
【０１５０】
（付記４）
前記第１のプロセッサに、
前記複数の列パネルの列方向の長さが異なる場合、前記複数の列パネルのうち列番号が最も小さい列パネルの先頭ブロックと、前記複数の行パネルのうち行番号が最も小さい行パネルとを用いて行列積を計算する、
処理をさらに実行させるための付記１乃至３のいずれか１つ記載のプログラム。
【０１５１】
（付記５）
前記複数の列パネルのうち列番号が最も小さい列パネルについて行交換を実行する、
処理をさらに実行させるための付記１乃至４のいずれか１つ記載のプログラム。
【０１５２】
（付記６）
ＬＵ分解を並列で実行する複数のプロセッサ
を有し、
前記複数のプロセッサの各々が、
前記ＬＵ分解の対象である行列のパネルのうち当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列のパネルのうち当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行する並列計算機システム。
【０１５３】
（付記７）
ＬＵ分解を並列で実行する複数のプロセッサの各々が、
前記ＬＵ分解の対象である行列のパネルのうち当該プロセッサが処理する複数の行パネルを統合して第１のパネルを生成し、
前記行列のパネルのうち当該プロセッサが処理する複数の列パネルを統合して第２のパネルを生成し、
前記第１のパネルと前記第２のパネルとの行列積を計算する、
処理を実行する並列計算方法。
【符号の説明】
【０１５４】
１  並列計算機システム    １０  インターコネクト
１０１  プロセッサ    １０２  メモリ
１１１  計算部    １１２  データ格納部
【図１】
0006503902.tif 000002
【図２】
0006503902.tif 000003
【図３】
0006503902.tif 000004
【図４】
0006503902.tif 000005
【図５】
0006503902.tif 000006
【図６】
0006503902.tif 000007
【図７】
0006503902.tif 000008
【図８】
0006503902.tif 000009
【図９】
0006503902.tif 000010
【図１０】
0006503902.tif 000011
【図１１】
0006503902.tif 000012
【図１２】
0006503902.tif 000013
【図１３】
0006503902.tif 000014
【図１４】
0006503902.tif 000015
【図１５】
0006503902.tif 000016
【図１６】
0006503902.tif 000017
【図１７】
0006503902.tif 000018
【図１８】
0006503902.tif 000019
【図１９】
0006503902.tif 000020
【図２０】
0006503902.tif 000021
【図２１】
0006503902.tif 000022
【図２２】
0006503902.tif 000023
【図２３】
0006503902.tif 000024
【図２４】
0006503902.tif 000025
【図２５】
0006503902.tif 000026
【図２６】
0006503902.tif 000027
【図２７】
0006503902.tif 000028
【図２８】
0006503902.tif 000029
【図２９】
0006503902.tif 000030
【図３０】
0006503902.tif 000031
【図３１】
0006503902.tif 000032
【図３２】
0006503902.tif 000033
【図３３】
0006503902.tif 000034
【図３４】
0006503902.tif 000035
【図３５】
0006503902.tif 000036
【図３６】
0006503902.tif 000037
【図３７】
0006503902.tif 000038
【図３８】
0006503902.tif 000039
【図３９】
0006503902.tif 000040
【図４０】
0006503902.tif 000041
【図４１】
0006503902.tif 000042
【図４２】
0006503902.tif 000043
【図４３】
0006503902.tif 000044
【図４４】
0006503902.tif 000045
【図４５】
0006503902.tif 000046
【図４６】
0006503902.tif 000047
【図４７】
0006503902.tif 000048
【図４８】
0006503902.tif 000049
【図４９】
0006503902.tif 000050
【図５０】
0006503902.tif 000051
【図５１】
0006503902.tif 000052