JPH08227405A

JPH08227405A - 反復処理の並列実行方法

Info

Publication number: JPH08227405A
Application number: JP3209995A
Authority: JP
Inventors: Teruo Tanaka; 輝雄田中; Yusaku Yamamoto; 有作山本; Yoshiaki Hojo; 芳章北城; Yoshiko Tamaoki; 由子玉置; Tadayuki Sakakibara; 忠幸榊原; Machiko Asaya; 真知子朝家; Yoshiko Yasuda; 淑子保田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1995-02-21
Filing date: 1995-02-21
Publication date: 1996-09-03

Abstract

(57)【要約】【目的】ＬＵ分解処理などの反復処理を並列計算機でよ
り短時間に実行可能にする。【構成】Ｋ回目の反復処理が、並列化不可能な処理Ｐ
（Ｋ）と並列化可能な処理Ｑ（Ｋ）とから構成され、処
理Ｑ（Ｋ）は、処理Ｐ（Ｋ）の結果を利用し、かつ、Ｋ
＋１回目の処理Ｐ（Ｋ＋１）はＫ回目の処理Ｑ1（Ｋ）
中の一部の処理Ｑs（Ｋ）の結果を利用する時、処理Ｑ
（Ｋ）を、プロセッサの台数 Pと同数の処理Ｑ1（Ｋ）
からＱP（Ｋ）に分解し、かつ、処理Ｑ1（Ｋ）には、処
理ＱS（Ｋ）を含ませる。処理Ｑ1（Ｋ）と処理Ｐ（Ｋ＋
Ｍ）を同一のプロセッサで順次実行し、これと並行し
て、他の処理Ｑ2（Ｋ）からＱn（Ｋ）を他のP-1台のプ
ロセッサで実行する。以後、全プロセッサの処理が終了
する毎に以上の処理を繰り返す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、Ｎ次元連立一次方程式
の係数行列を下三角行列と上三角行列に分解するＬＵ分
解処理のように、同じ処理を異なるデータに対して反復
して実行する反復処理を、複数のプロセッサを持つ並列
計算機で実行させる方法に関する。

【０００２】

【従来の技術】各種の工業用製品の開発に数値シミュレ
ーションが実用に供されている。このような数値シミュ
レーションでよく使用される処理は、Ｎ次元連立方程式
ＡＸ＝Ｂをガウスの消去法で解く処理である。ここで、
ＡはＮ行Ｎ列の係数行列、ＸとＢはＮ列のベクトルであ
る。このガウスの消去法により上記方程式を解く処理の
主要な部分は、係数行列Ａを下三角行列Ｌと上三角行列
Ｕの積である行列ＬＵに分解するＬＵ分解処理である。

【０００３】大規模行列のＬＵ分解処理の実用化は進ん
でおり、特にスーパコンピュータ向けには、多段同時展
開法が一般的である。これらの手法は、文献：村田、小
国、唐木著スーパコンピュータ、丸善、９１〜１０３
頁、１９８５や文献：ブロッキングＬＵ分解法のＶＰ２
０００シリーズ向けチューニングについて、情報処理学
会第４２回（平成３年前期）全国大会予稿集第１分冊７
１〜７２頁、特開平４−２５９０６４および特開平６−
７５９８８などに開示されている。

【０００４】とくに最近は、並列計算機の進歩に伴い、
並列計算機を数値シミュレーションに応用する研究が盛
んである。

【０００５】近年実用化されている並列計算機は、一般
的に次のような３種類の形態をとる。図１は、複数台の
プロセッサ２ないし４が主記憶１を共有する主記憶共有
型並列計算機である。これは、現在のベクトル型スーパ
コンピュータの主流であり、スーパコンピュータの場
合、各プロセッサ２ないし４は多数のデータをベクトル
データとしてまとめ、そのベクトルデータに同一の処理
をパイプライン演算器を使用して連続的に施すベクトル
プロセッサとなる。

【０００６】図２は、各々が演算処理装置１０と専用の
主記憶９を持つ独立したを計算機６ないし８である。こ
こで、計算機６ないし８をプロセッサと呼ぶ。これらの
プロセッサ６ないし８を相互結合網５で接続する。現在
は、各プロセッサはスーパスカラなどの高性能マイクロ
プロセッサとメモリで構成されることが多い。

【０００７】図３は、主記憶１５および複数台のプロセ
ッサ１６ないし１７から構成される主記憶共有型並列計
算機１２ないし１４（図１と同様）をさらに相互結合網
１１で接続した構成を持つ。これは、たとえば、特開平
６−９６０３２で開示されている。図３の構成における
各々の主記憶共有型計算機１２ないし１４をクラスタと
呼ぶ。

【０００８】図２の形式の並列計算機でＬＵ分解処理を
実行させる方法の例は、文献：星野著ＰＡＸコンピュー
タ、オーム社、１９８５や特開平３−１０５６９４など
に開示されている。

【０００９】ＬＵ分解処理の概要および図１に示した並
列計算機でＬＵ分解処理を実行させる従来の方法を図
４、図５を用いて説明する。

【００１０】図４は、行列Ａに対するＬＵ分解処理のＫ
回目のループ処理を説明するための図である。すなわ
ち、行列Ａの各要素ａ（ｉ，ｊ）（すなわち、第ｉ行第
ｊ列番目の要素）を、異なる処理を受ける要素群に分け
て、それらの要素群を領域の形で示している。図中、Ｎ
は行列サイズである。ここでは、第１行から第Ｋ−１行
および第１列から第Ｋ−１列までのＬＵ分解処理は終了
している。各反復回では、高速化のために、一度にＭ列
をまとめてＬＵ分解処理を行なういわゆる多段同時消去
方法が使用される。このためには、Ｍは複数であるが、
原理的にはＭは１でもよい。

【００１１】以下の説明のため、行列Ａの第Ｋ列から第
Ｎ列ないし第Ｋ行から第Ｎ行の領域を５つに分け、それ
ぞれに次のような名称を付ける。

【００１２】（１）Ｌ１（Ｋ）２２：第Ｋ列から第Ｋ＋
Ｍ−１列および第Ｋ行から第Ｋ＋Ｍ−１行で構成される
左下三角領域（２）Ｕ１（Ｋ）２１：第Ｋ列から第Ｋ＋Ｍ−１列およ
び第Ｋ行から第Ｋ＋Ｍ−１行で構成される右上三角領域（３）Ｌ２（Ｋ）２３：第Ｋ列から第Ｋ＋Ｍ−１列およ
び第Ｋ＋Ｍ行から第Ｎ行で構成される矩形領域（４）Ｕ２（Ｋ）２４：第Ｋ＋Ｍ列から第Ｎ列および第
Ｋ行から第Ｋ＋Ｍ−１行で構成される矩形領域（５）Ａ（Ｋ）２５：第Ｋ＋Ｍ列から第Ｎ列および第
Ｋ＋Ｍ行から第Ｎ行構成される矩形領域図５に、図１の並列計算機で実行可能な、従来技術によ
るＬＵ分解処理プログラムを示す。この図において、Ｌ
Ｕ分解プログラムは、２重のＤＯループで構成されてい
る。

【００１３】外側のループ２０は、Ｍ列づつまとめて処
理するために、行列のサイズＮをＭで割ったＭ／Ｎ回だ
け繰り返す。

【００１４】内側は２つＤＯループで構成され、それら
の処理は以下のとおりである。なお、外側ループ２０の
繰返し回数はＫとする。

【００１５】まず、最初の内側ループ（ＤＯ１）の処
理では、第Ｋ列から第Ｋ＋Ｍ−１列番目まで、つまりＵ
１（Ｋ）２１、Ｌ１（Ｋ）２２およびＬ２（Ｋ）２３の
領域に対して、各列ごとに、部分軸選択（いわゆるピボ
ット処理）およびそれに対する消去更新処理を繰り返し
て行なう。これらの処理の概要は以下のとおりである。
最初の内側ループ（ＤＯ１）のループ繰返し回数はＫ
Ｍとする。但し、ＫＭはＫ、Ｍとは関係のない値であ
る。

【００１６】（１）ピボット処理：ＫＭ列の第ＫＭ行か
ら第Ｎ行までの要素から最大値を検索し、検索した最大
値を含む行と第ＫＭ行との行交換を行なう。すなわち、
それらの行の第ＫＭ列から第Ｋ＋Ｍ−１列番目の要素を
交換する。

【００１７】（２）消去更新処理：第ＫＭ＋１列から第
Ｋ＋Ｍ−１列および第ＫＭ＋１行から第Ｎ行により構成
される矩形領域内の各要素ａ（ｉ,ｊ）に対して、消去
更新処理ａ（ｉ,ｊ）＝ａ（ｉ,ｊ）−ａ（ＫＭ,ｊ）×
ａ（ｉ,ＫＭ）を行なう。

【００１８】このＤＯループの処理を、以下では、処理
Ｐ（Ｋ）と呼ぶ。このＤＯループの処理では、最大値検
索という逐次処理を繰り返して行なう必要があるため、
このループ自体を並列化してもあまり性能が向上しな
い。

【００１９】次に、第２の内側ＤＯループ（ＤＯ２）
では、領域Ｕ２（Ｋ）および領域Ａ（Ｋ）に対して、次
の処理を行なう。

【００２０】（１）領域Ｕ２（Ｋ）および領域Ａ（Ｋ）
の行交換：前述のピボット処理において行交換処理を施
したＭ組の行の第Ｋ＋Ｍ列から第Ｎ列の要素に対して、
行交換処理を行なう。

【００２１】（２）領域Ｕ１（Ｋ）、領域Ｌ１（Ｋ）を
用いた領域Ｕ２（Ｋ）の消去更新処理：この領域Ｕ２
（Ｋ）内の各要素ａ（ｉ,ｊ）に対して、消去更新処理
ａ（ｉ,ｊ）＝ａ（ｉ,ｊ）−ａ（ｋ,ｊ）×ａ（ｉ,ｋ）
を行なう。ここで、ｋをＫからＫ＋Ｍ−１に順次変化さ
せて、この計算を合計Ｍ回行なう。なお、ｉは、Ｋ＋１
からＫ＋Ｍ−１の一つを１取り、ｊはＫ＋ＭからＮの一
つの値を取る。したがって、この計算は、領域Ｕ１
（Ｋ）、Ｌ１（Ｋ）内の要素を使用して、領域Ｕ２
（Ｋ）内の要素を更新している。

【００２２】（３）領域Ｕ２（Ｋ）、Ｌ２（Ｋ）を用い
た領域Ａ（Ｋ）内の要素の消去更新処理：消去更新処理
ａ（ｉ,ｊ）＝ａ（ｉ,ｊ）−ａ（ｋ,ｊ）×ａ（ｉ,ｋ）
を行なう。ここで、ｋをＫからＫ＋Ｍに順次変えて、こ
の計算を合計Ｍ回行なう。ここで、ｉはｋ＋ＭからＮの
一つであり、ｊはＫ＋ＭからＮの一つである。

【００２３】この第２の内側ループの処理を、以下で
は、処理Ｑ（Ｋ）と呼ぶ。

【００２４】これらの計算（１）から（３）は、領域Ｕ
２（Ｋ）、Ａ（Ｋ）の各列ごとに独立に計算可能であ
る。すなわち、各列毎に、上記処理（１）から（３）を
実行する処理が基本の処理であり、処理Ｑ（ｋ）は、こ
の単位処理を複数の列に対して集めたものとなってい
る。このため、このような各列毎の処理は、処理Ｑ
（Ｋ）を構成する、互いに並列に実行可能な部分処理と
言える。したがって、Ｑ（Ｋ）２８を列を単位に均等に
ｐ個にグループで分け、それぞれをＱ1（Ｋ）、Ｑ2
（Ｋ）、、、ＱP（Ｋ）とし、ｐ台のプロセッサに分割
して処理を行なうことにより、ｐ倍に近い台数効果を得
ることができる。

【００２５】このようなＬＵ分解処理のフローチャート
は、図７の通りである。図７では、パラメタＫの初期値
設定３５に続き、処理Ｐ（Ｋ）３６の実行後、並列化可
能な処理Ｑ（Ｋ）の並列化３７を行ない、ｐ個の処理Ｑ
1（Ｋ）３８ないし処理Ｑp（Ｋ）４０に分け、ｐ台のプ
ロセッサでそれぞれの処理を分担し、並列に実行する。
このとき、並列化された処理Ｑ（Ｋ）のあとに、処理を
逐次にもどして、Ｋの更新処理４１と収束判定４２を行
ない、次のＫ＋Ｍ回目の反復ループである処理Ｐ（Ｋ＋
Ｍ）、さらに処理Ｑ（Ｋ＋Ｍ）を実行する。

【００２６】このように処理Ｑ（Ｋ）を複数の並列実行
可能な処理に分けて実行するプログラムを得るには、最
適化コンパイラの自動並列化機構を使用してソースプロ
グラムの内の並列実行可能な部分を検出し、かつ、それ
らを自動的に並列実行可能なオブジェクトプログラムに
変換する方法あるいはソースプログラムに並列指示行を
追加し、これをコンパイラにより並列実行可能なオブジ
ェクトプログラムに変換する方法が取られる。図５に示
したプログラムは、ＤＯＡＬＬタイプの並列化指示行
２９を有する例である。このプログラムの場合、処理Ｑ
（Ｋ）２８の並列化は並列指示行２９により各反復回ご
とに毎回行なわれる。

【００２７】以上の説明から明かな通り、ＬＵ分解処理
の基本的な処理の流れは、図６に示すように、パラメタ
Ｋの初期値設定３０およびそのパラメータの更新処理３
３により制御し、処理Ｐ（Ｋ）３１と、処理Ｑ（Ｋ）３
２を指定した条件３４（収束条件あるいは反復回数な
ど）が成立するまで繰返し実行することである。図５の
プログラムは、この処理を、図７に示す手順にしたがっ
て図１の形式の並列計算機で実行可能にし、それでもっ
てＬＵ分解処理の高速化を図っている。

【００２８】数値シミュレーションでは、ＬＵ分解処理
に限らず、ほぼ同一の処理を、図６に示す手順にしたが
って繰り返す反復処理が多く見受けられる。その場合
は、Ｍは１でもよい。このような他の反復処理でも、処
理Ｐが本来逐次的にしか実行できないとしても、図７に
示す処理手順にしたがって処理Ｑを並列に実行すること
により、このような他の反復処理も高速に実行できる。

【００２９】

【発明が解決しようとする課題】ＬＵ分解処理を図７に
示した手順で処理した場合、処理Ｑ（Ｋ）が並列計算機
を構成する複数のプロセッサにより並列に実行されるた
め、その処理の実行時間は、プロセッサ数が多いほど短
縮される。しかし、各反復回ごとに処理Ｐ（Ｋ）は並列
計算機を構成する一つのプロセッサにより実施されるた
め、この処理Ｐ（Ｋ）の実行時間が、プロセッサ数を多
くしても、ＬＵ分解処理全体の処理時間を短縮するのを
妨げている。

【００３０】いま仮に、対象とする行列のサイズＮを１
０００としたとき、上記処理Ｑ（Ｋ）と処理Ｐ（Ｋ）
は、それぞれＬＵ分解処理の総演算量の処理のおおよそ
９８％および２％程度の演算量を占める。しかし、処理
Ｐ（Ｋ）、処理Ｑ（Ｋ）の実行時の演算器の使用率が大
幅に異なる。

【００３１】たとえば、図１の並列計算機が４台のプロ
セッサからなり、各プロセッサがベクトルプロセッサの
場合、この処理Ｑ（Ｋ）は並列処理可能であり、この処
理のために異なるベクトルプロセッサ内のパイプライン
演算器も使用される上に、処理Ｑ（Ｋ）の計算処理は積
和計算のため、各ベクトルプロセッサ内のパイプライン
演算器の使用率が高い。一方、処理Ｐ（Ｋ）は、一台の
ベクトルプロセッサ内の演算器しか使用しない上に、こ
の処理の主たる部分は最大値検索処理であり、必要とす
るデータ量に対して相対的に演算量が少なく、この一つ
のベクトルプロセッサ内の一部のパイプライン演算器し
か使用せず、演算器の使用率は高くない。このため、上
述の４台のベクトルプロセッサからなる並列計算機に対
する推定例では、処理Ｑ（Ｋ）に対する処理Ｐ（Ｋ）の
演算器利用率は約１／１０程度と低い。このため、処理
Ｐ（Ｋ）と処理Ｑ（Ｋ）の処理時間の比は、約１０：１２（＝２：９８／（１０×４））となり、わずか２％の演算量の処理Ｐ（Ｋ）がＬＵ分解
処理全体の処理時間の約半分を占める。したがって、４
台のプロセッサを使用しているにもかかわらず最大２台
分の性能向上しか得られない。

【００３２】また、図１のプロセッサ１等が、スーパー
スカラプロセッサからなり、かつプロセッサの総数が１
００台程度である場合の推定例では、処理Ｑ（Ｋ）に対
する処理Ｐ（Ｋ）の演算器利用率は約１／２である。こ
のため、処理Ｐ（Ｋ）と処理Ｑ（Ｋ）の処理時間の比
は、約４：１（＝２：９８／（２×１００））となり、わずか２％の演算量の処理Ｐ（Ｋ）が演算時間
の約８０％を占めることがわかる。したがって、１００
台のプロセッサを使用しているにもかかわらず１０台強
の性能向上しか得られない。

【００３３】したがって、処理Ｐ（Ｋ）の実行時間が、
ＬＵ分解処理の全体の処理時間に及ぼす影響をさらに減
じることが望まれる。

【００３４】同じような問題は、ＬＵ分解処理に限ら
ず、処理Ｐ（Ｋ）で例示される第１の処理と、その処理
の実行後に実行すべき、処理Ｑ（Ｋ）で例示される並列
実行可能な第２の処理とを繰返するとともに、この繰返
しに当たっては、第２の処理の実行後に第１の処理を実
行するように第１、第２のの処理を実行するときに生じ
る。

【００３５】言い替えると、従来の方法では、複数のプ
ロセッサの内、一部のプロセッサは処理をしないで、他
のプロセッサでの処理待ちの状態にある時間が長いこと
になる。

【００３６】したがって、本発明の目的は、本来は逐次
処理されるべき第１の処理とその後に実行されるべき、
並列実行可能な第２の処理とを有し、第２の処理の完了
を待って再度第１、第２の処理を実行するように、第
１、第２の処理を反復して実行すべき反復処理を、並列
計算機で実行させる場合に、この反復処理全体の処理時
間を軽減することが可能な反復処理の並列実行方法を提
供することである。

【００３７】本発明の他の目的は、このような処理の実
行時に、プロセッサが待ち状態にある時間を軽減するこ
とである。

【００３８】本発明のより具体的な目的は、ＬＵ分解処
理を並列計算機で実行させる場合に、この処理全体の処
理時間を軽減することが可能なＬＵ分解処理の並列実行
方法を提供することである。

【００３９】本発明の他のより具体的な目的は、このＬ
Ｕ分解処理を実行しているときのプロセッサが待ち状態
にある時間を減少させることである。

【００４０】

【課題を解決するためにの手段】上に説明したＬＵ分解
処理では、外側ループの繰返し回数Ｋのときに、処理Ｐ
（Ｋ）の結果を使用して実行される処理Ｑ（Ｋ）では、
領域Ｕ２（Ｋ）と領域Ａ（Ｋ）の要素の更新後の値が計
算される。これらの要素のうち、外側ループの次の繰返
し時に実行される処理Ｐ（Ｋ＋Ｍ）の計算に使用する要
素は、このＫ＋１回目における領域Ｕ１（Ｋ）、Ｌ１
（Ｋ）、Ｌ２（Ｋ）に属すべき要素のみである。すなわ
ち、図４において、第Ｋ＋Ｍ行から第Ｎ行と第Ｋ＋Ｍ列
から第Ｋ＋２＊Ｍ−１列により構成される領域２６内の
要素である。したがって、処理Ｐ（Ｋ＋Ｍ）は、この領
域２６内の要素に関する処理Ｑ（Ｋ）（これをＱS
（Ｋ）と呼ぶことにする）が終了後に実行を開始しなけ
ればならない。しかし、処理Ｐ（Ｋ＋Ｍ）は、領域Ａ
（Ｋ）の内、この領域２６以外の領域内の要素に対する
処理Ｑ（Ｋ）とは、並列に実行可能である。

【００４１】本発明では、このことを利用して、本来は
逐次処理されるべき第１の処理（例えば、Ｐ（Ｋ）、以
下括弧内は例示である）とその後に実行されるべき、並
列実行可能な第２の処理（Ｑ（Ｋ））とを有し、第２の
処理の完了を待って再度第１、第２の処理を実行するよ
うに、第１、第２の処理を反復して実行すべき反復処理
を、並列計算機で実行させる場合に、ある繰返し（Ｋ回
目）で実行される第２の処理（Ｑ（Ｋ））の内、次の繰
返し（Ｋ＋Ｍ回目）で実行されるべき第１の処理（Ｐ
（Ｋ＋Ｍ））が使用する処理結果を生成する部分処理
（Ｑs（Ｋ））と、次の繰返し時の第１の処理（Ｐ（Ｋ
＋Ｍ））とを同じプロセッサに割り当て、この第１の処
理（Ｐ（Ｋ＋Ｍ））を、この部分処理（ＱS（Ｋ））に
続いてそのプロセッサで実行させる。第２の処理（Ｑ
（Ｋ））の内、この部分処理（ＱS（Ｋ））以外の部分
を、残りのプロセッサの数P−１に等しい数の、並列に
実行可能な処理（Ｑ2（Ｋ）からＱP（Ｋ））に分割し、
それらの残りのプロセッサにより並列に実行させる。

【００４２】この際、上記部分処理（Ｑs（Ｋ））と第
１の処理（Ｐ（Ｋ＋Ｍ））とを実行するプロセッサの処
理時間が、他のプロセッサのそれより小さいときには、
前者の処理時間が他のプロセッサのそれとほぼ同じにな
るように、第２の処理（Ｑ（Ｋ））の内、部分処理（Ｑ
S（Ｋ））以外の一部もこの部分処理（ＱS（Ｋ））を割
り当てたプロセッサに割り当てることがより望ましい。
すなわち、第２の処理処理（Ｑ（Ｋ））を実施するのに
必要な第１の処理（Ｐ（Ｋ））を、いずれかのプロセッ
サにより予め実行した後、上記のごとくにして各プロセ
ッサに割り当てるべき第２の処理（Ｑ（Ｋ））の一部を
決定し、決定された処理の割り当てに従って、各プロセ
ッサで、部分処理（ＱS（Ｋ）もしくはＱi（Ｋ）（ｉ＝
２からｐ−１））を実行させる。

【００４３】部分処理（ＱS（Ｋ））を割り当てられた
プロセッサでは、この処理が終了すると、第１の処理
（Ｐ（Ｋ＋Ｍ））を実行させる。この部分処理（ＱS
（Ｋ）と第１の処理（Ｐ（Ｋ＋Ｍ））および他の部分処
理（Ｑ2（Ｋ）からＱP（Ｋ））の実行の終了を待って、
以上の処理を繰り返す。

【００４４】なお、本発明は、図２、図３の形式の並列
計算機でも実施可能である。

【００４５】

【作用】次の反復回（（Ｋ＋Ｍ））の第１の処理（Ｐ
（Ｋ＋Ｍ））は、第２の処理（Ｑ（Ｋ））の内、その第
１の処理（Ｐ（Ｋ＋Ｍ））に先立って実行する必要があ
る部分処理（ＱS（Ｋ））以外の処理と並列に実行され
るので、並列計算機内のプロセッサが待ち状態にある時
間を軽減することが出来、計算機資源の有効な利用を図
ることが出来る。それにより、この反復処理全体の処理
時間を軽減することが可能になる。又、従来のごとく、
第１の処理（Ｐ（Ｋ＋Ｍ））を第２の処理（Ｑ（Ｋ））
と逐次に実行する従来の場合に比べて、この第１の処理
（Ｐ（Ｋ＋Ｍ））の実行時間が、繰返し処理全体に及ぼ
す影響を減少できる。なお、第１の処理（Ｐ（Ｋ＋
Ｍ））は、部分処理（ＱS（Ｋ））を割り当てられたプ
ロセッサ内で、この処理の後に実行されるので、正常な
結果を出力する。

【００４６】

【実施例】以下、本発明に係る反復処理の並列実行方法
を図面に示したいくつかの実施例を参照してさらに詳細
に説明する。なお、以下においては、同じ参照番号は同
じものもしくは類似のものを表わすものとする。

【００４７】＜実施例１＞本実施例では、図１の主記憶
共有型の並列計算機を使用した、ＬＵ分解処理の並列実
行方法を示す。図８は本実施例で使用するプログラムの
例であり、図９はそのプログラムを図１の装置で実行す
る手順を示すフローチャートである。

【００４８】以下、本実施例を、図９のフローチャート
に基づいて、従来例で示した図７と異なる部分について
主に説明する。

【００４９】図５に関して説明した通り、ＬＵ分解処理
での次反復回の処理Ｐ（Ｋ＋Ｍ）は、図４に示す行列Ａ
において、点線で囲った領域２６に対して処理を実行す
る。したがって、前反復回の処理Ｑ（Ｋ）のうち、図４
の行列Ａ内の領域２６である第Ｋ＋Ｍ列から第Ｋ＋２＊
Ｍ−１列の更新処理ＱS（Ｋ）を処理Ｑ（Ｋ）から除い
た残りの処理（Ｑ（Ｋ）−ＱS（Ｋ））と処理Ｐ（Ｋ＋
Ｍ）は並列に実行可能である。処理Ｐ（Ｋ＋Ｍ）は処理
ＱS（Ｋ）を終了すればいつでも実行可能となる。した
がって、図９において、処理Ｑ（Ｋ）を並列化する処理
６３を実行し、処理ＱS（Ｋ）を含む処理Ｑ1´（Ｋ）６
４、処理Ｑ2´（Ｋ）６５ないし処理ＱP´（Ｋ）６６の
ｐ個に分割し、そのうち、処理Ｑ1´（Ｋ）６４を処理
Ｐ（Ｋ＋Ｍ）６７と同じプロセッサで、その処理より前
に実行することにより、処理Ｑ2´（Ｋ）６５ないし処
理ＱP´（Ｋ）６６と処理Ｐ（Ｋ＋Ｍ）とを並列に実行
することができるようになる。

【００５０】処理Ｐ（Ｋ＋Ｍ）６７をＫ回目の反復回で
実行するために、６１、６８および６９で制御される反
復ループに入る前に、Ｋ＝１のときの処理Ｐ（１）６０
を１度だけ実行する必要がある。

【００５１】処理Ｑ1´（Ｋ）６４、処理Ｑ2´（Ｋ）６
５ないし処理ＱP´（Ｋ）６６の分割は、処理Ｐ（Ｋ＋
Ｍ）６７を含めて、全体の処理が均等になるように分割
する必要がある。処理Ｑ（Ｋ）の分割は、各プロセッサ
に割り付ける列の数を変更することにより自由に扱うこ
とができる。ここでは、処理Ｑ1´（Ｋ）６４で扱う列
をＫ＋ＭからＫ１とし、処理Ｑ2´（Ｋ）６５で扱う列
をＫ１＋１からＫ２とし、処理ＱP´（Ｋ）６６で扱う
列をＫ（p-1）からＮとする。

【００５２】この処理の均等分割によるＫ１、Ｋ
２、、、Ｋ（p-1）の決定６２の手順を説明する。

【００５３】まず、処理Ｐ（Ｋ＋Ｍ）に先だって実行す
る必要のある処理ＱS（Ｋ）は、最低、処理Ｑ1´（Ｋ）
６４に含テまれている必要がある。したがって、Ｋ１は
Ｋ＋２＊Ｍ−１以上となる（条件１）。今仮に、処理Ｐ
（Ｋ＋Ｍ）６７の演算量を処理Ｑ（Ｋ）における列の演
算量に換算した時の列数をProwとする。処理Ｑ1´
（Ｋ）６４と処理Ｐ（Ｋ＋Ｍ）６７の演算量の和を全体
の１／ｐにし、かつ条件１を満たすためには、Ｋ１の値
は次の式、

【００５４】

【数１】Ｋ１=MAX（Ｋ+２Ｍ−１、Ｋ＋Ｍ＋（Ｎ−（Ｋ＋Ｍ）＋１−Prow）/p） (1) であらわすことができる。ここで、MAXは最大値を求め
る関数である。

【００５５】さらに、Ｋ２ないしＫ（p-1）は処理Ｑ
（Ｋ）から処理Ｑ1´（Ｋ）６４を除いた処理を、残り
のｐ−１台のプロセッサで均等に分割すれば良い。した
がって、Ｋ２ないしＫ（p-1）は次の式、

【００５６】

【数２】Ｋｉ=Ｋ１＋（ｉ−１）／（p−１）*（Ｎ-Ｋ１）＋１ (2) であらわすことができる。ここで、ＫｉはＫ２ないしＫ
（p-1）をあらわす。

【００５７】処理の均等分割によるＫ１、Ｋ２、、、Ｋ
（p-1）の決定処理６２は、各反復回ごとに行なえば効
率が良いが、対象とする行列は徐々に小さくなるので、
数回の反復回ごとに値を更新するようにすることもでき
る。

【００５８】図８に示すプログラムは、プロセッサ台数
Pが４の場合である。

【００５９】まず、Ｋ＝１のときの処理Ｐ（１）４５を
実行し、ＤＯ９ループ４６で指示された反復処理を実行
する。次に前述した式（式１）および（式２）により、
処理を均等に分割するためにＫ１、Ｋ２、Ｋ３を決定４
７する。

【００６０】プログラムの並列化記述は、ひとつのプロ
セッサのみに処理Ｐ（Ｋ＋Ｍ）５８を割り付けるので、
ＳＥＣＴＩＯＮタイプの並列化指示行４８ないし５３を
用いる。各プロセッサの処理は、各SECTON（）文で区切
られた範囲を実行する。

【００６１】ＳＥＣＴＩＯＮ（1）４９では、処理Ｑ1´
（Ｋ）５４と処理Ｐ（Ｋ＋Ｍ）５８をこの順番に実行す
る。ここで、処理Ｑ1´（Ｋ）５４は行列Ａの第Ｋ＋Ｍ
列から第Ｋ１列までを担当する。ここで、Ｋ１は（式
１）を用いて求める。（式１）のＫ１の定義により、処
理Ｑ1´（Ｋ）５４は前述した処理ＱS（Ｋ）を含むこと
を保障することができる。

【００６２】ＳＥＣＴＩＯＮ（2）５０では、処理Ｑ2´
（Ｋ）５５を実行する。処理Ｑ2´（Ｋ）５５は行列Ａ
の第（Ｋ１＋１）列から第Ｋ２列までを担当する。ここ
で、Ｋ２は（式２）を用いて求める。

【００６３】ＳＥＣＴＩＯＮ（3）５１では、処理Ｑ3´
（Ｋ）５６を実行する。処理Ｑ3´（Ｋ）５６は行列Ａ
の第（Ｋ２＋１）列から第Ｋ３列までを担当する。ここ
で、Ｋ３も（式２）を用いて求める。

【００６４】ＳＥＣＴＩＯＮ（4）５２では、処理Ｑ4´
（Ｋ）５７を実行する。処理Ｑ4´（Ｋ）５７は行列Ａ
の第（Ｋ３＋１）列から第Ｎ列までを担当する。ここ
で、Ｋ３は（式２）を用いて求める。

【００６５】図８に示したプログラムをコンパイルする
ことにより、図９に示した手順で実行されるオブジェク
トプログラムが生成される。このコンパイルにより、図
８に示す各部分に対応するオブジェクト部分が生成され
るとともに、これらのオブジェクト部分の実行を制御す
るために、並列化処理６３と同期処理６９を実行するコ
ードがこのオブジェクトプログラムに追加される。この
ような目的のためのコンパイラはすでに知られている。

【００６６】この実施例により、処理Ｐを実質上、並列
処理の中に組み込むことが可能となるために、処理Ｐの
実行時間が実質的に（１−１／ｐ）に短縮される。この
結果ＬＵ分解処理全体の処理時間が短縮される。例え
ば、図１の形式の並列計算機が４台のプロセッサを有
し、かつ、各プロセッサがベクトルプロセッサの場合、
行列のサイズＮを１０００で、処理Ｐと処理Ｑの実行時
間がほぼ同程度の場合は、本実施例を用いることによ
り、ＬＵ分解処理の実行時間を最大３５％程度低減する
ことができる。

【００６７】＜実施例２＞本実施例は、図１の主記憶共
有型の並列計算機を使用した、、ＬＵ分解処理の並列実
行方法の他の例を提供する。図１０は本実施例で使用す
るプログラムの例であり、図１１はこのプログラムを図
１の装置で実行させるときの実行手順を示すフローチャ
ートである。

【００６８】実施例１においては、図９で示したごと
く、各反復ごとに毎回並列化処理６３を行なうことによ
り、処理Ｐ（Ｋ＋Ｍ）と次の反復回の処理Ｑ1´（Ｋ＋
Ｍ）ないし処理ＱP´（Ｋ＋Ｍ）との順序関係を保証し
ている。しかし、毎回行なう並列化処理６３はすべての
プロセッサ間の同期を取るために性能低下の要因となる
可能性がある。本実施例では、きめ細かくＰｏｓｔ処理
やＷａｉｔ処理を用いた同期処理を用いて順序保障処理
を行ない、並列化処理を制御変数Ｋの反復ループの外側
に移動させる方法を説明する。ここで用いるＰｏｓｔ処
理やＷａｉｔ処理は、ＯＳの発行するＰｏｓｔ／Ｗａｉ
ｔマクロではなく、コンパイラの並列制御ライブラリの
ひとつであるＰｏｓｔ／Ｗａｉｔライブラリであり、コ
ストが小さい処理である。

【００６９】この処理手順を図１１を用いて図９と比較
して説明する。まず、図９と同様に、処理Ｐ（１）１０
１を実行する。次に、制御変数Ｋにより指示される反復
ループの外側に並列化処理１０２を移動する。このた
め、処理の均等分割処理１０３ないし１０５、反復ルー
プの制御変数Ｋの更新処理１１７ないし１１９および反
復ループの判定処理１２０ないし１２２は、並列化され
た後、各プロセッサごとに実行させる。さらに、他のプ
ロセッサの次の反復回の処理との順序関係を保障するた
めに、プロセッサ間でＰｏｓｔ処理およびＷａｉｔ処理
を実行する必要がある。

【００７０】Ｐｏｓｔ処理およびＷａｉｔ処理の設定す
べき位置について説明する。基本的な方針はＰｏｓｔ処
理をできるかぎり早く実行し、Ｗａｉｔ処理をできるか
ぎり遅く実行することである。このことにより、各プロ
セッサの実行の独立性を高め、動的な要因（たとえば、
主記憶アクセス競合など）によるＷａｉｔ処理時の不要
な同期待ちを軽減することができる。

【００７１】まず、処理Ｐ（Ｋ＋Ｍ）１０７を担当する
プロセッサの実行順序を説明する。このプロセッサで実
行する消去更新処理Ｑ1´（Ｋ）を処理ＱS（Ｋ）１０６
と処理（Ｑ1´（Ｋ）−ＱS（Ｋ））１０８の２つに分解
する。ここで、処理ＱS（Ｋ）１０６は、処理Ｐ（Ｋ＋
Ｍ）１０７に先だって行なう行列Ａ内の第Ｋ＋Ｍ行から
第Ｋ＋２＊Ｍ−１行の更新処理である。処理（Ｑ1´
（Ｋ）−ＱS（Ｋ））１０８は、このプロセッサが担当
する処理Ｑ（Ｋ）に関する残りの処理である。処理Ｐ
（Ｋ＋Ｍ）１０７を実行することにより、他のプロセッ
サの次の反復ループの処理Ｑ2´（Ｋ＋Ｍ）１０９ない
し処理ＱP´（Ｋ＋Ｍ）１１０を実行することができる
ので、ここで、Ｐｏｓｔ処理１１１およびＷａｉｔ処理
１１５ないし１１６を実行する。ここで、Ｐｏｓｔ処理
１１１は他のｐ−１台のプロセッサのＷａｉｔ処理と対
応することとする。次に、処理（Ｑ1´（Ｋ）−Ｑ1S
（Ｋ））１０８を実行する。次反復回の処理Ｐ（Ｋ＋２
＊Ｍ）を実行するためには、その前に他のプロセッサの
処理Ｑ2´（Ｋ）１０９ないし処理ＱP´（Ｋ）１１０を
実行する必要があるので、ここで、Ｐｏｓｔ処理１１３
ないし１１４およびＷａｉｔ処理１１２を実行する。こ
こで、Ｗａｉｔ処理１１２はｐ−１台のプロセッサから
のＰｏｓｔ処理をすべて受けて成立することとする。

【００７２】このように、処理Ｑ1´（Ｋ）を処理ＱS
（Ｋ）１０６と処理（Ｑ1´（Ｋ）−Ｑ1S（Ｋ））１０
８の２つに分解することにより、Ｐｏｓｔ処理１１１は
処理Ｐ（Ｋ＋Ｍ）１０７の直後に実行可能となり、処理
（Ｑ1´（Ｋ）−Ｑ1S（Ｋ））１０８の時間だけｐｏｓ
ｔ処理１１１を他のプロセッサのＷａｉｔ処理１１５な
いし１１６より早く実行することが可能となる。

【００７３】図１０に示すプログラムでは、ＳＥＣＴＩ
ＯＮタイプの並列化７０ないし７５は１回だけ行なう。
各ＳＥＣＴＩＯＮ（）文とＳＥＣＴＩＯＮ（）文の間に
各プロセッサで各々実行する制御変数Ｋの反復ループ７
６ないし７９がある。それぞれの反復ループの中に各演
算処理８０ないし８９がある。複数のＰｏｓｔ処理とＷ
ａｉｔ処理を対応させるために、ここでは、イベント変
数を引数とする。複数のイベント変数を持つＰｏｓｔ処
理９０は、設定した数のイベントを発行し、Ｗａｉｔ処
理９５ないし９７と対応する。複数のイベント変数を持
つＷａｉｔ処理９４は、設定した数のイベントを対応す
るＰｏｓｔ処理９１ないし９３から受けることにより成
立する。

【００７４】図１０に示したプログラムをコンパイルす
ることにより、図１１に示した手順で実行されるオブジ
ェクトプログラムが生成される。このことは、実施例１
の場合と同様である。

【００７５】＜実施例３＞本実施例は、図２の主記憶分
散型の並列計算機を使用した、ＬＵ分解処理の並列実行
方法を提供する。図１３は本実施例で使用するプログラ
ムの例であり、図１４はこのプログラムを図２の装置で
実行させるときの実行手順を示すフローチャートであ
る。

【００７６】このような並列計算機では、図２に示すよ
うに、相互結合網５を介して、プロセッサ６ないし８間
でのデータの送受信処理が必要となる。このデータの送
受信処理を用いて順序保証を行なう。以下では、メッセ
ージ交換型の並列計算機を例に説明する。

【００７７】分散記憶型の並列計算機では、まず、デー
タを分割配置する必要がある。ここでは、図１２に示す
ように、行列Ａを多段展開の幅Ｍごとに行を分割して、
順次各プロセッサに分割する。このような分割では、各
プロセッサが、順番にピボット処理Ｐを担当することに
なる。

【００７８】この処理手順を図１４を用いて説明する。
図１１と比較して、図１４で異なっている部分は、
（１）同期処理のＰｏｓｔ／Ｗａｉｔ処理の代わりに、
データの送信／受信処理を伴うＳｅｎｄ処理およびＲｅ
ｃｅｉｖｅ処理を用いること、（２）図１４の実施例で
は、つねに一つのプロセッサがピボット処理Ｐを担当し
ていたのに対して、実施例３では、負荷をできるだけ均
等にするために、各プロセッサが交互にピボット処理を
担当することである。図１４では、２台のプロセッサ
（ＰＥａとＰＥｂ）で処理を実行する場合を示す。もち
ろん、３台以上のプロセッサの場合も同様である。処理
Ｑ（Ｋ）は、プロセッサ数である２つに均等に分割され
る。それぞれのプロセッサの担当する処理を処理Ｑa
（Ｋ）および処理Ｑb（Ｋ）とする。

【００７９】このとき、もし、データを送信するＳｅｎ
ｄ処理とデータを受信するＲｅｃｅｉｖｅ処理が非同期
に実行可能な場合は、Ｓｅｎｄ処理を可能なかぎり先行
させて、Ｒｅｃｅｉｖｅ処理を同様に可能なかぎり遅ら
せて実行する必要がある。これは、図１１のＰｏｓｔ／
Ｗａｉｔ処理を用いた時のスケジューリング方針と同様
であり、処理Ｑa（Ｋ）を処理Ｑs（Ｋ）１７０と処理
（Ｑa（Ｋ）−Ｑs（Ｋ））１７２とに分解することによ
り、実現可能である。

【００８０】まず、それぞれのプロセッサでは、１６
０、１６１において自プロセッサがどちらのプロセッサ
であるかを判断する。これは、一般にたとえばＵＮＩＸ
コマンドのWHOAMIなどのような判別ライブラリを事前に
用意しておく。ここでは、それぞれ自プロセッサである
と判断した１６２および１６３とする。

【００８１】次に、プロセッサＰＥａで、処理Ｐ（１）
１６６を行ない、生成した領域Ｌ２（図４）のデータを
プロセッサＰＥｂに送信するためにＳｅｎｄ処理１６７
を行なう。

【００８２】一方、プロセッサＰＥｂは、このデータを
受信するＲｅｃｅｉｖｅ処理１６８を実行する。以下、
各プロセッサはそれぞれ制御変数Ｋの反復ループに入
る。

【００８３】まず、プロセッサＰＥｂは、処理ＱS
（Ｋ）１７３を実行し、引き続き、処理Ｐ（Ｋ＋Ｍ）１
７４を実行する。これにより、Ｋ＋Ｍ回目の消去処理に
用いる領域Ｌ２の生成が可能となるために、ただちにプ
ロセッサＰＥａにＳrｅｎｄ処理１７８を実行する。そ
の後、残りの処理（Ｑb（Ｋ）−Ｑs（Ｋ））１７５を実
行し、次反復回であるＫ＋Ｍステップに手順を進める。

【００８４】一方、プロセッサＰＥａでは、まず処理Ｑ
a（Ｋ）１６９で担当するＱの領域の更新処理を行な
い、その後に、Ｋ＋Ｍステップに必要なＬ２のデータを
Ｒｅｃｅｉｖｅ処理１７７で受け取る。このとき、プロ
セッサＰＥｂ側のＳｅｎｄ処理１７８は可能なかぎり早
く実行されているため、Ｒｅｃｅｉｖｅ処理１７７での
受信待ちはあまりなく、すぐにデータ受信が可能とな
る。

【００８５】次にＫ＋Ｍステップに進む。今度は、プロ
セッサＰＥａ側がピボット処理Ｐ（Ｋ＋２＊Ｍ）１７１
を担当する。以下の処理は、プロセッサＰＥｂのＫステ
ップの手順と同等である。他方のプロセッサＰＥｂでも
Ｋ＋Ｍステップの処理は、プロセッサＰＥａのＫステッ
プの処理と同様に行なう。

【００８６】まず、処理ＱS（Ｋ＋Ｍ）１７０を実行
し、引き続き、処理Ｐ（Ｋ＋２＊Ｍ）１７１を実行す
る。これにより、Ｋ＋２＊Ｍ回目の消去処理に用いる領
域Ｌ２の生成が可能となるために、ただちにプロセッサ
ＰＥｂにＳｅｎｄ処理１７９を実行する。その後、残り
の処理（Ｑa（Ｋ＋Ｍ）−Ｑs（Ｋ＋Ｍ））１７２を実行
し、次反復回であるＫ＋２＊Ｍステップに手順を進める
ために、制御変数Ｋの更新処理１８１、判定処理１８３
を行なう。

【００８７】一方、プロセッサＰＥｂでは、まず処理Ｑ
b（Ｋ）１７６で担当するＱの領域の更新処理を行な
い、その後に、Ｋ＋２＊Ｍステップに必要なＬ２のデー
タをＲｅｃｅｉｖｅ処理１８０で受け取る。このとき、
プロセッサＰＥａ側のＳｅｎｄ処理１７９は可能なかぎ
り早く実行されているため、Ｒｅｃｅｉｖｅ処理１８０
での受信待ちはあまりなく、すぐにデータ受信が可能と
なる。その後、制御変数Ｋの更新処理１８２、判定処理
１８４を行なう。

【００８８】図１３に示すプログラムでは、まず１３０
では自プロセッサがどちらのプロセッサであるかを判断
する。これは、一般にたとえばＵＮＩＸコマンドのWHOA
MIなどのような判別ライブラリを事前に用意しておく。
それぞれのプロセッサの処理は、条件文１３１ないし１
３３で判別される。図１３においては、１３６以下１３
２の直前までがプロセッサＰＥａの処理で、１４８以下
１３３の直前までがプロセッサＰＥｂの処理である。

【００８９】各プロセッサで交互にピボット処理を担当
するために、まず、１回だけ、プロセッサＰＥａで、処
理Ｐ（１）１３６を行ない、その結果をＳＥＮＤ処理１
４５で送信し、プロセッサＰＥｂにおいてＲＥＣＥＩＶ
Ｅ処理１４８で受信する。その後、各プロセッサは、反
復ループに入る。各反復ループＤＯ９１およびＤＯ９２
は制御変数Ｋに関して、２回分の処理を行なっている。
そのために、ＤＯ９１およびＤＯ９２ループの間隔の指
定が、図１３の１３４、１３５に示すように、第１、２
の実施例に比べて２倍となっている。

【００９０】Ｋ回目のステップでは、プロセッサＰＥｂ
において、処理ＱS（Ｋ）１４１、処理Ｐ（Ｋ＋Ｍ）１
４２および処理（Ｑb（Ｋ）−Ｑs（Ｋ））１４３を行な
い、ＳＥＮＤ処理１４９でプロセッサＰＥａにピボット
値を送信する。プロセッサＰＥａでは、平行して処理Ｑ
a（Ｋ）１３７を行ない、ＲＥＣＥＩＶＥ処理１４６で
ピボット値を受信する。

【００９１】Ｋ＋Ｍ回目のステップでは、プロセッサＰ
Ｅａにおいて、処理ＱS（Ｋ＋Ｍ）１３８、処理Ｐ（Ｋ
＋２＊Ｍ）１３９および処理（Ｑa（Ｋ＋Ｍ）−Ｑs（Ｋ
＋Ｍ））１４０の演算処理を行ない、ＳＥＮＤ処理１４
７でプロセッサＰＥｂにピボット値を送信する。プロセ
ッサＰＥｂでは、平行して処理Ｑb（Ｋ）１４４を行な
い、ＲＥＣＥＩＶＥ処理１５０でピボット値を受信す
る。

【００９２】図１３に示したプログラムをコンパイルす
ることにより、図１４に示した手順で実行されるオブジ
ェクトプログラムが生成される。このことは、実施例１
の場合と同様である。

【００９３】＜実施例４＞本実施例は、図３に示した、
複数のクラスタにより構成された主記憶分散型の並列計
算機を使用した、ＬＵ分解処理の並列実行方法を提供す
る。図１５は本実施例で使用するプログラムの例であ
り、図１６はこのプログラムを図３の装置で実行させる
ときの実行手順を示すフローチャートである。

【００９４】このような並列計算機では、実施例３のよ
うに、データの送受信処理をもとに順序保証を行ない、
さらに、各反復回ごとに、クラスタ内のプロセッサ間で
第１、第２の実施例のような並列処理を実施する。

【００９５】実施例４の実施例３と異なる点は、各ステ
ップ実行内で、クラスタ内のプロセッサ間の並列処理を
実行することである。このときの手順は、ここでは図９
を用いて説明した実施例１で示した方法を用いる。もち
ろん、実施例２で示した図１１の手順も利用することが
可能である。

【００９６】本実施例では、２つのクラスタＣＬａとＣ
Ｌｂ、および各クラスタ内のプロセッサ数がｐ台と仮定
する。以下、本実施例での処理手順を図１６を用いて説
明する。

【００９７】図１４と比較して、図１６で異なる点は、
（１）図１４におけるプロセッサＰＥａおよびＰＥｂが
それぞれ図１６のクラスタＣＬａおよびＣＬｂに対応す
ること、（２）各クラスタ内の各ステップの処理におい
て、クラスタ内のｐ台のプロセッサにおいて、並列処理
が行なわれることの２点である。図１６では、２台のク
ラスタ（ＣＬａとＣＬｂ）で処理を実行する場合を示
す。もちろん、３台以上のクラスタの場合も同様であ
る。

【００９８】このとき、もし、データを送信する送信Ｓ
ｅｎｄ処理とデータを受信するＲｅｃｅｉｖｅ処理が非
同期実行可能な場合は、Ｓｅｎｄ処理を可能なかぎり先
行させて、Ｒｅｃｅｉｖｅ処理を同様に可能なかぎり遅
らせて実行する必要がある。これは、図１４におけるＳ
ｅｎｄ処理／Ｒｅｃｅｉｖｅ処理を用いた時のスケジュ
ーリング方針と同様である。

【００９９】最初に、クラスタＣＬａでピボット処理Ｐ
（１）２５２を行ない、生成した領域Ｌ２（図４参照）
のデータをクラスタＣＬｂに送信するためにＳｅｎｄ処
理２５３を実行する。

【０１００】一方、クラスタＣＬｂはこのデータを受信
するＲｅｃｅｉｖｅ処理２５４を実行する。以下、各ク
ラスタは、それぞれ制御変数Ｋの反復ループに入る。制
御変数Ｋの制御は、２７９ないし２８２で行なう。処理
Ｑ（Ｋ）は、クラスタ数である２つに均等に分割され
る。それぞれのクラスタの担当する処理を処理Ｑa
（Ｋ）および処理Ｑb（Ｋ）とする。

【０１０１】まず、クラスタＣＬｂは、Ｋ回目の反復処
理において、クラスタ内のｐ台のプロセッサを用いて並
列処理２５６を行なう。このときの並列処理の分割の方
法は、実施例１から実施例３にしてしたのと同一の方法
で可能である。

【０１０２】ピボット処理Ｐ（Ｋ＋Ｍ）２６３を担当す
るプロセッサでは、処理ＱS（Ｋ）２６２を実行し、引
き続き、ピボット処理Ｐ（Ｋ＋Ｍ）２６３を実行する。
これにより、Ｋ＋Ｍ回目の消去処理に用いる領域Ｌ２の
生成が可能となるために、ただちにクラスタＣＬａにＳ
ｅｎｄ処理２６８を実行する。その後、残りの処理（Ｑ
b（Ｋ）−Ｑs（Ｋ））２６４を実行する。クラスタＣＬ
ｂ内の他のプロセッサは、並列にそれぞれ処理Ｑb2
（Ｋ）２６５および処理Ｑbp（Ｋ）２６６を実行する。
Ｋステップ内でクラスタ内でのプロセッサ間の同期は、
並列化処理２５６で行なわれる。その後、Ｋ＋Ｍステッ
プに手順を進める。

【０１０３】一方、クラスタＣＬａでは、まず処理Ｑa1
（Ｋ）２５９で担当するＱの領域の更セ新処理を行な
い、その後に、Ｋ＋Ｍステップに必要なＬ２のデータを
Ｒｅｃｅｉｖｅ処理２６７で受け取る。このとき、クラ
スタＣＬｂ側のＳｅｎｄ処理２６８は可能なかぎり早く
実行されているため、Ｒｅｃｅｉｖｅ処理２６７での受
信待ちはあまりなく、すぐにデータ受信が可能となる。
クラスタＣＬａ内の他のプロセッサは、並列にそれぞれ
処理Ｑa2（Ｋ）２６０および処理Ｑap（Ｋ）２６１を実
行する。Ｋステップ内でクラスタ内でのプロセッサ間の
同期は、並列化処理２５５で行なわれる。その後、Ｋ＋
Ｍステップに手順を進める。

【０１０４】次にＫ＋Ｍステップに進む。今度は、クラ
スタＣＬａ側がピボット処理Ｐ（Ｋ＋２＊Ｍ）２７０を
担当する。以下の処理は、クラスタＣＬｂのＫステップ
の手順と同等である。

【０１０５】処理ＱS（Ｋ＋Ｍ）２６９を実行し、引き
続き、ピボット処理Ｐ（Ｋ＋２＊Ｍ）２７０を実行す
る。これにより、Ｋ＋２＊Ｍ回目の消去処理に用いる領
域Ｌ２の生成が可能となるために、ただちにクラスタＣ
ＬｂにＳｅｎｄ処理２７７を実行する。その後、残りの
処理（Ｑa1（Ｋ＋Ｍ）−Ｑs（Ｋ＋Ｍ））２７１を実行
する。クラスタＣＬａ内の他のプロセッサは、並列にそ
れぞれ処理Ｑa2（Ｋ）２７２および処理Ｑap（Ｋ）２７
３を実行する。Ｋ＋Ｍステップ内でクラスタ内でのプロ
セッサ間の同期は、並列化処理２５７で行なわれる。そ
の後、Ｋ＋２＊Ｍステップに手順を進める。

【０１０６】一方、クラスタＣＬｂでは、まず処理Ｑb1
（Ｋ＋Ｍ）２７４において、担当する領域の更新処理を
行ない、その後に、Ｋ＋２＊Ｍステップに必要なＬ２の
データをＲｅｃｅｉｖｅ処理２７８で受け取る。このと
き、クラスタＣＬａ側のＳｅｎｄ処理２７７は可能なか
ぎり早く実行されているため、Ｒｅｃｅｉｖｅ処理２７
８での受信待ちはあまりなく、すぐにデータ受信が可能
となる。クラスタＣＬｂ内の他のプロセッサは、並列に
それぞれ処理Ｑb2（Ｋ）２７５および処理Ｑbp（Ｋ）２
７６を実行する。Ｋ＋Ｍステップ内でクラスタ内でのプ
ロセッサ間の同期は、並列化処理２５８で行なわれる。
その後、Ｋ＋２＊Ｍステップに手順を進める。

【０１０７】図１５に示すプログラムでは、２台のクラ
スタ（ＣＬａとＣＬｂ）でかつ各クラスタ内のプロセッ
ササ数がそれぞれ２台の場合を示す。もちろん、３台以
上のクラスタの場合、あるいは、クラスタ内のプロセッ
サ台数を３台以上にすることに可能である。図１５中、
２０６以下２０２の直前までがクラスタＣＬａの処理
で、２０８以下２０３の直前までがクラスタＣＬｂの処
理である。ここでは、まず２００では自クラスタがどち
らのクラスタであるかを判断する。これは、一般にたと
えばＵＮＩＸコマンドのWHOAMIなどのような判別ライブ
ラリを事前に用意しておく。

【０１０８】各クラスタで交互にピボット処理を行なう
ために、ＤＯ９１ループ２０４およびＤＯ９２ループ２
０５は制御変数Ｋに関して、２回分の処理を行なってい
る。そのために、実施例３と同様に、ＤＯ９１およびＤ
Ｏ９２ループの間隔の指定が、実施例１、２に比べて２
倍となっている。

【０１０９】各クラスタ内では、各反復ステップＫおよ
びＫ＋Ｍごとに、並列処理指示文２０９ないし２２４に
より、並列化の指示を行なう。

【０１１０】図１５の例では、クラスタＣＬａにおいて
は、ステップＫに対しては、２０９から２１２の間の並
列指示行により並列処理が規定されており、演算処理２
２５および２２６、ＲＥＣＥＩＶＥ処理２３７を行な
う。ステップＫ＋Ｍでは、２１３から２１６の間の並列
指示行により並列処理が規定されており、演算処理２２
７ないし２２９および２３０、ＳＥＮＤ処理２３９を行
なう。

【０１１１】クラスタＣＬｂにおいては、ステップＫに
対しても、同様に２１７から２２０の間の並列指示行に
より並列処理が規定されており、演算処理２３１ないし
２３４、ＳＥＮＤ処理２３８を行なう。ステップＫ＋Ｍ
では、２２１から２２４の間の並列指示行により並列処
理が規定されており、演算処理２３５および２３６、Ｒ
ＥＣＥＩＶＥ処理２４０を行なう。

【０１１２】なお、第３および実施例４では、この処理
では、データの送受信のためのＳｅｎｄ処理やＲｅｃｅ
ｉｖｅ処理を他の演算処理と並列に実行することが必要
となる。もちろん、このＳｅｎｄ処理やＲｅｃｅｉｖｅ
処理が専用の通信プロセッサで動作可能である場合は、
それらの通信に要する処理時間を除いたのちに、演算を
担当するプロセッサ内で演算量の処理を均等にする必要
がある。

【０１１３】図１５に示したプログラムをコンパイルす
ることにより、図１６に示した処理手順が実行されるオ
ブジェクトプログラムが生成されることは、実施例１の
場合と同様である。

【０１１４】

【発明の効果】本来は逐次処理されるべき第１の処理と
その後に実行されるべき、並列実行可能な第２の処理と
を有し、第２の処理の完了を待って再度第１、第２の処
理を実行するように、第１、第２の処理を反復して実行
すべき反復処理を、並列計算機で実行させる場合に、プ
ロセッサが待ち状態にある時間を軽減することが出来、
計算機資源の有効な利用を図ることが出来る。それによ
り、この反復処理全体の処理時間を軽減することが可能
になる。

【図面の簡単な説明】

【図１】従来の主記憶共有型並列計算機の概略構造を示
す図。

【図２】従来の主記憶分散型並列計算機の概略構造を示
す図。

【図３】従来のクラスタ結合型並列計算機の概略構造を
示す図。

【図４】従来の多段同時消去ＬＵ分解法の概要を示す
図。

【図５】従来の多段同時消去ＬＵ分解法のプログラム例
を示す図。

【図６】従来の反復計算処理のフローチャート。

【図７】並列化された反復計算処理のフローチャート。

【図８】本発明の実施例１で使用するプログラム例を示
す図。

【図９】実施例１による反復計算処理のフローチャー
ト。

【図１０】実施例２で使用するプログラム例を示す図。

【図１１】本発明の実施例２による反復計算処理のフロ
ーチャート。

【図１２】分散記憶型計算機向けのデータの分割を示す
図。

【図１３】本発明の実施例３で使用するプログラム例を
示す図。

【図１４】実施例３による反復計算処理のフローチャー
ト。

【図１５】本発明の実施例４で使用するプログラム例を
示す図。

【図１６】実施例４による反復計算処理のフローチャー
ト。

【符号の説明】

２０、３４、４２…ループ制御、２７、３１、３６…逐
次的処理Ｐ（Ｋ）、２８、３２…並列化可能処理Ｑ
（Ｋ）、２９…並列指示、３８ないし４０…並列化可能
処理Ｑ（Ｋ）を分割した処理

フロントページの続き (72)発明者玉置由子東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内 (72)発明者榊原忠幸東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内 (72)発明者朝家真知子東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内 (72)発明者保田淑子東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内

Claims

【特許請求の範囲】

【請求項１】第１の処理と、その実行結果を使用する第
２の処理とを反復して実行する反復処理であって、第２
の処理は、並列に実行可能な複数の部分処理からなり、
第１の処理は、該反復処理のある繰返し時における第２
の処理の実行結果をその反復処理の次の繰返し時に使用
するものを並列計算機で実行させる方法であって、（ａ）該並列計算機を構成する複数のプロセッサのいず
れか一つにより、該反復処理の第１の繰返しに対して第
１の処理を実行させ、（ｂ）一つの処理群が、第２の処理に含まれる上記複数
の部分処理の内、第１の処理が次の繰返し時に使用する
データを生成する一部の複数の部分処理と該第１の処理
とを少なくとも含むように、かつ、他の処理群が、第２
の処理に含まれる上記複数の部分処理の内、該一部の複
数の部分処理以外の他の複数の部分処理の一部を含むよ
うに、該第１の処理と第２の処理に含まれた上記複数該
複数の部分処理とを、上記複数のプロセッサの数に等し
い数の複数の処理群に分割し、（ｃ）該第１の繰返しに対して、該ステップ（ａ）の実
行結果を使用して該一部の複数の部分処理を実行し、該
次の繰返しに対して、該一部の複数の部分処理のこの実
行結果を使用して第１の処理を実行するように、該一部
の複数の部分処理と該第１の処理を少なくとも含む上記
一つの処理群を、該複数のプロセッサのいずれか一つに
より実行し、（ｄ）該他の複数のプロセッサの各々により、該複数の
処理群の一つを、該第１の繰返しに対して該ステップ
（ａ）の実行結果を使用して、かつ、該一つのプロセッ
サによるステップ（ｃ）での上記実行と並行して実行
し、（ｅ）各プロセッサによる、ステップ（ｃ）または
（ｄ）の実行の終了後、上記ステップ（ｃ）から（ｅ）
を繰返し、その繰返しにおいては、（ｅ１）該第２の処
理を該次の繰返し以降の繰返しに対して実行され、か
つ、該第１の処理を該次の繰返し以降の繰返しの次の繰
返しに対して実行されるように、ステップ（ｃ）から
（ｄ）を実行し、（ｅ２）上記繰返しをする前にステッ
プ（ｃ）の実行の結果得られた、第１の処理の実行結果
を、上記繰返しをした後に実行されるステップ（ｄ）に
おいて第２の処理により利用する反復処理の並列実行方
法。
【請求項２】ステップ（ｅ）による繰返しのときに、ス
テップ（ｂ）も実行した上で繰り返す請求項１記載の反
復処理の並列実行方法。
【請求項３】ステップ（ｂ）は、該一部の複数の部分処
理に付加して該一つのプロセッサにより実行すべき他の
一部の複数の部分処理が、該一つの処理群に属するよう
に、該分割を実行するステップを有する請求項１記載の
反復処理の並列実行方法。
【請求項４】ステップ（ｂ）は、上記一部の複数の部分
処理と上記第１の処理の実行に必要な第１の処理時間
と、該他の複数の部分処理の各々の実行に必要な第２の
処理時間とに基づいて、該複数の処理群の実行時間がほ
ぼ等しくなるように、上記分割を行なうステップを有す
る請求項１記載の反復処理の並列実行方法。
【請求項５】上記反復処理は、Ｎ次元連立一次方程式の
係数行列をＬＵ分解する処理であり、上記第１の処理は
ピボット処理を含み、上記第２の処理は係数行列の消去
更新処理を含む請求項１から４のいずれか一つに記載の
反復処理の並列実行方法。
【請求項６】ステップ（ｅ）は、各プロセッサにおける
処理の終了を検出した後、該一つのプロセッサによるス
テップ（ｃ）の繰返しおよび該他の複数のプロセッサの
各々によるステップ（ｄ）の繰返しを同時に起動するス
テップを有する請求項１記載の反復処理の並列実行方
法。
【請求項７】ステップ（ｅ）は、各プロセッサにより、そのプロセッサでの処理の終了後
に、他の複数のプロセッサの各々での処理の終了を判別
し、各プロセッサにより、他のプロセッサの各々での処理の
終了が検出されたときに、そのプロセッサでの、ステッ
プ（ｃ）または（ｄ）の繰返しを起動するステップを有
する請求項１記載の反復処理の並列実行方法。
【請求項８】該並列計算機は該複数のプロセッサにより
共有された主記憶をさらに有し、該方法は、（ｆ）各プロセッサが該ステップ（ｃ）または（ｄ）の
実行を終了したとき、その終了を示す情報をそのプロセ
ッサにより該主記憶に書き込むステップをさらに有し、該ステップ（ｅ）は、各プロセッサから該主記憶に書き
込まれた、そのプロセッサでの処理の終了を示す情報に
基づいて行なわれる請求項７記載の反復処理の並列実行
方法。
【請求項９】ステップ（ｆ）は、ステップ（ｃ）の実行の終了後、該一つのプロセッサに
よりそのプロセッサでの処理の終了を示す情報を該主記
憶に書き込み、該他の複数のプロセッサの各々により、ステップ（ｄ）
による、いずれかの部分処理群の実行の終了後に、その
プロセッサでの処理の終了を示す情報をその各プロセッ
サにより該主記憶に書き込むステップを有し、ステップ（ｅ）は、該一つのプロセッサにより、上記終了を示す情報を書き
込んだ後に、該他の複数のプロセッサの各々による、終
了を示す情報が該主記憶に書き込まれたか否かを該第一
つのプロセッサにより監視し、該他の複数のプロセッサの各々による、上記終了を示す
情報の書き込みの後に、該他の複数のプロセッサの以外
のプロセッサの各々による、終了を示す情報が該主記憶
に書き込まれたか否かを、該他の複数のプロセッサの各
々により監視することにより、該複数のプロセッサの各
々により、他のプロセッサでのステップ（ｃ）または
（ｄ）での処理の実行が終了したか否かを判別するステ
ップとを有し、ステップ（ｅ）は、該ステップ（ｅ）による各プロセッ
サ別の、他プロセッサの終了の判別結果に基づいて、各
プロセッサ毎に、ステップ（ｃ）から（ｄ）の繰返しの
開始時期を決定するステップを有する請求項８記載の反
復処理の並列実行方法。
【請求項１０】第１の処理と、その実行結果を使用する
第２の処理とを反復して実行する反復処理であって、第
２の処理は、並列に実行可能な複数の部分処理からな
り、第１の処理は、該反復処理のある繰返し時における
第２の処理の実行結果をその反復処理の次の繰返し時に
使用するものを並列計算機で実行させる方法であって、（ａ）該並列計算機を構成する複数のプロセッサのいず
れか一つにより、該反復処理の第１の繰返しに対して第
１の処理を実行させ、（ｂ）一つの処理群が、第２の処理に含まれる上記複数
の部分処理の内、第１の処理が次の繰返し時に使用する
データを生成する一部の複数の部分処理と該第１の処理
とを少なくとも含むように、かつ、他の処理群が、第２
の処理に含まれる上記複数の部分処理の内、該一部の複
数の部分処理以外の他の複数の部分処理の一部を含むよ
うに、第２の処理に含まれた上記複数該複数の部分処理
と第１の処理とを上記複数のプロセッサの数に等しい数
の複数の処理群に分割し、（ｃ）該第１の繰返しに対して、該ステップ（ａ）の実
行結果を使用して該一部の複数の部分処理を実行し、該
次の繰返しに対して、該一部の複数の部分処理のこの実
行結果を使用して第１の処理を実行するように、該一部
の複数の部分処理と該第１の処理を少なくとも含む上記
一つの処理群を、該複数のプロセッサのいずれか一つに
より実行し、（ｄ）該他の複数のプロセッサの各々により、該複数の
処理群の一つを、該第１の繰返しに対して、該ステップ
（ａ）の実行結果を使用して、かつ、該一つのプロセッ
サによるステップ（ｃ）での上記実行と並行して実行
し、（ｅ）各プロセッサにおいて、そのプロセッサによるス
テップ（ｃ）または（ｄ）の実行が終了した時点で、そ
のプロセッサにより上記（ｃ）または（ｄ）を繰返し、
その繰返しにおいては、（ｅ１）ステップ（ｃ）または
（ｄ）で実行した処理群とは異なる他の一つの理群をそ
のプロセッサで実行するように、ステップ（ｃ）または
（ｄ）を実行し、（ｅ２）当該他の処理群が第２の処理
の部分処理群を含んでいるときには、それらの部分処理
群を該次の繰返し以降の繰返しに対して実行し、当該他
の処理群が第１の処理を含んでいるときには、その第１
の処理を該次の繰返し以降の繰返しの次の繰返しに対し
て実行し、（ｅ３）そのプロセッサがステップ（ｃ）ま
たは（ｄ）で実行した処理群が第１の処理を含んでいな
いときには、他のプロセッサから通知される、第１の処
理の実行結果の通知を確認した後に、上記繰返しを開始
するステップを有する反復処理の並列実行方法。
【請求項１１】ステップ（ｅ）による該繰返しは、各プ
ロセッサがステップ（ｅ）による繰返し毎に、順次異な
る処理群を実行するように行なわれる請求項１０記載の
反復処理の並列実行方法。
【請求項１２】いずれか一つのプロセッサによりステッ
プ（ｃ）によりいずれかの繰返しに対して上記一つの処
理群を実行したときに、その実行結果を他の複数のプロ
セッサに通知し、他の複数のプロセッサの各々は、上記実行結果が、該一
つのプロセッサから通知されたのを確認してから、その
繰返しに対する、該複数の処理群の内のいずれかの他の
一つの処理群を実行し、該一つの処理群を上記繰返しの次の繰返しに対して実行
する、さらに他のプロセッサに、該他の複数のプロセッ
サの各々により該他の処理群の実行結果を通知し、該さらに他のプロセッサでは、そのプロセッサ以外の複
数のプロセッサから上記繰返しに対する上記複数の処理
群の実行結果の受信を、当該さらに他のプロセッサによ
り確認してから、上記さらに次の繰返しに対して、該一
つの処理を開始するステップをさらに有する請求項１０
記載の反復処理の並列実行方法。
【請求項１３】該並列計算機は、該複数のプロセッサを
相互に接続するセットワークと、各プロセッサに対応し
て設けられ、そのプロセッサで実行されるプログラムと
データを保持するローカルメモリとを有する分散記憶型
並列計算機であり、上記一つの処理の実行結果の通知と上記他の処理群の実
行結果の通知は、このネットワークを介して行なわれる
請求項１２記載の反復処理の並列実行方法。
【請求項１４】第１の処理と、その実行結果を使用する
第２の処理とを反復して実行する反復処理であって、第
２の処理は、並列に実行可能な複数の部分処理からな
り、第１の処理は、該反復処理のある繰返し時における
第２の処理の実行結果をその反復処理の次の繰返し時に
使用するものを、それぞれ複数のプロセッサとそれらの
プロセッサで共有される、プログラムとデータを保持す
るためのローカルメモリとを有する複数のクラスタと、
それらを結合するネットワークからなる分散記憶型の並
列計算機で実行させる方法であって、（ａ）該複数のクラスタ内のいずれか一つに含まれた複
数のプロセッサのいずれか一つにより、該反復処理の第
１の繰返しに対して第１の処理を実行させ、（ｂ）一つの処理群が、第２の処理に含まれる上記複数
の部分処理の内、第１の処理が次の繰返し時に使用する
データを生成する一部の複数の部分処理と該第１の処理
とを少なくとも含むように、かつ、他の処理群が、第２
の処理に含まれる上記複数の部分処理の内、該一部の複
数の部分処理以外の他の複数の部分処理の一部を含むよ
うに、該第１の処理と第２の処理に含まれた上記複数該
複数の部分処理とを、上記複数のクラスタの数に等しい
数の複数の処理群に分割し、（ｃ）該複数のクラスタの各々により、該複数の処理群
の一つを他のクラスタによる他の処理群の実行と並行し
て実行し、各クラスタによる、一つの処理群の実行に当
たっては、（ｃ１）その一つの処理群に上記一部の複数
の部分処理と該第１の処理とが含まれているときには、
その一部の複数の部分処理と第１の処理とを少なくとも
含む一つの部分処理群と、第２の処理に含まれる上記複
数の部分処理の内、該一部の複数の部分処理以外の他の
複数の部分処理の一部をそれぞれ含む複数の他の部分処
理群とに、該一つの処理群の処理を分割し、該一つの処
理群に上記一部の複数の部分処理と第１の処理が含まれ
ていないときには、第２の処理に含まれる上記複数の部
分処理の内、該一部の複数の部分処理以外の他の複数の
部分処理の一部をそれぞれ含む複数の他の部分処理群
に、該一該一つの処理群の処理を分割し、（ｃ２）その
クラスタ内の複数のプロセッサにより、ステップ（ｃ
１）による分割で得られた複数の部分処理群の一つを、
そのクラスタ内の他のプロセッサによる他の部分処理群
の実行と並行して実行し、（ｃ３）そのクラスタで実行
した上記一つの処理群に上記第１の処理が含まれている
場合、その第１の処理が属する一つの部分処理群を実行
した一つのプロセッサから、他のクラスタに第１の処理
の実行結果を通知し、（ｄ）各クラスタにおいて、そのクラスタ内の各プロセ
ッサによるステップ（ｃ１）の実行が終了した時点で上
記（ｃ）を繰返し、その繰返しにおいては、（ｄ１）該
複数の処理群のうち、そのクラスタによりステップ
（ｃ）で実行した処理群とは異なる他の処理群をそのク
ラスタで実行するように、ステップ（ｃ）を繰返し、
（ｄ２）ステップ（ｃ）でそのクラスタが実行した処理
群の中に、該第１の処理が含まれていない場合には、他
のクラスタから通知されるその第１の処理の実行結果の
通知を確認した後、該他の処理群の実行を開始し、（ｄ
３）その繰返しにおいて実行する該他の処理群が、第２
の処理に属する部分処理群を含んでいる場合には、該次
の繰返し以降の繰返しに対してその部分処理群を実行
し、かつ、該他の処理群が、第１の処理を含んでいると
きには、該次の繰返し以降の繰返しの次の繰返しに対し
て第１の処理を実行するように、該他の処理群を実行す
る反復処理の並列実行方法。