JP3667610B2 - 分散メモリ型並列計算機における分散処理方法及びコンピュータ可読記録媒体 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は分散メモリ型並列計算機における分散処理方法に関し、より具体的には、マスタとなる計算ノードがスレーブとなる計算ノードに初期データを分配し、各計算ノードでは初期データを元にローカルに計算を行い、最後にマスタとなる計算ノードがスレーブとなる計算ノードから計算結果を集めて結果をマージするという一連の動作を高速化する手法に関する。
【０００２】
【従来の技術】
プログラムの処理時間を短縮するために、そのプログラムを複数のCPU で分割実行して最後に結果をマージする手法がよく使われる。各々少なくともCPU とメモリとデータ転送手段とを含む複数のノードがネットワークを通じて相互に接続された分散メモリ型並列計算機でも、このような手法を使って性能を向上させている。また、プログラムとしては、一般にMPI(Message Passing Interface)プログラムが利用される。
【０００３】
複数のノードで仕事を分割して実行する場合は、下記(1) 〜(3) のフェーズから構成されるMPI プログラムが従来利用されている。
(1) マスタノードからスレーブノードへの初期データの転送
(2) 各ノードにおけるローカル計算
(3) スレーブノードからマスタノードへの結果データの転送と結果のマージ
ここで、マスタノードとはまとめ役のノードを言い、スレーブノードとはマスタノードに準じるノードを言い、事前に設定される。
【０００４】
図13〜図15に従来技術によるMPI プログラムの例を示す。図13が(1) のフェーズに、図14が(2) のフェーズに、図15が(3) のフェーズに、それぞれ対応する。以下、各フェーズの概要を説明する。
【０００５】
(1) 初期データ分配（図13)
配列q[N3＿max]を倍精度（8Byte ）データとしてrank0 （マスタノード）からrank1 〜rank3 （スレーブノード）に転送する。
【０００６】
(2) ローカル計算 (図14)
配列q を使って計算をさせる。要素をi とj とに分け、i を外側ループで回し、j を内側ループで回す。このとき、外側ループの単位でスプリット（分散）し、各計算ノードに割り当てる。各ノードの計算結果は、各ノードの配列mEq[i]に格納される。
【０００７】
(3) 結果データのマージ (図15)
各ノードの計算結果（mEq[i]）をマスタノード（rank0 ）に戻し、マスタノードでは、計算結果をマージしてEq[i] に結果を格納し、一連の動作が完了となる。
【０００８】
次に、本発明の実施の形態にかかる分散メモリ型並列計算機の構成例を示す図1 を借りて、図13〜15の各フェーズでマスタノード、スレーブノードがどのような動作を行うかを説明する。なお、rank0 のノードがマスタノードで、図1 ではノード0 に対応し、rank1 〜3 のノードがスレーブノードで、図1 ではノード1,2,3 にそれぞれ対応する。また、図1 中、01,11,21,31 はCPU(中央演算装置:Central Processing Unit) 、02,12,22,32 はMMU(主記憶装置:Main Memory Unit)、03,13,23,33 はRCU(遠隔制御装置:Remote Control Unit) 、4 はネットワーク、41は通信レジスタである。
【０００９】
(1) データ分配
＜rank0 （Node0 ）＞
CPU01 （rank0 ）はMMU02 内にある初期データ（配列q ）をMMU02 からMMU12 に転送するようRCU03 に指示を出す。RCU03 はその指示に従い、配列q をMMU02 からNetwork4経由でRCU13 に転送する（Send操作）。同様に、CPU01 （rank0 ）はMMU02 内にある初期データ（配列q ）をMMU02 からMMU22,32に転送するようRCU03 に指示を出し、RCU03 はその指示に従い、配列q をMMU02 からNetwork4経由でRCU23,33に転送する（Send操作）。
【００１０】
＜rank1 （Node1 ）＞
CPU11 （rank1 ）はRCU03 から送られてくる配列q をMMU12 に格納するようRCU13 に指示を出し、RCU13 は配列q をMMU12 に格納する（Receive 操作）。
【００１１】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）はRCU03 から送られてくる配列q をMMU22 に格納するようRCU23 に指示を出し、RCU23 は配列q をMMU22 に格納する（Receive 操作）。
【００１２】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）はRCU03 から送られてくる配列q をMMU32 に格納するようRCU33 に指示を出し、RCU33 は配列q をMMU32 に格納する（Receive 操作）。
【００１３】
(2) ローカル計算
＜rank0 （Node0 ）＞
CPU01 （rank0 ）は配列q[i=0,4,...] とq[j=i+1,...]間の要素間計算をして結果をMMU02 内の配列mEq[i=0,4,...]に書き込む。
【００１４】
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は配列q[i=1,5,...] とq[j=i+1,...]間の要素間計算をして結果をMMU12 内の配列mEq[i=1,5,...]に書き込む。
【００１５】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は配列q[i=2,6,...] とq[j=i+1,...]間の要素間計算をして結果をMMU22 内の配列mEq[i=2,6,...]に書き込む。
【００１６】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は配列q[i=3,7,...] とq[j=i+1,...]間の要素間計算をして結果をMMU32 内の配列mEq[i=3,7,...]に書き込む。
【００１７】
(3) 結果のマージ
＜rank0 （Node0 ）＞
CPU01 （rank0 ）はMMU02 内にある計算結果（配列mEq ）を最終結果を格納する配列Eqにコピーする。次に、CPU01 （rank0 ）は、MMU12 内の計算結果（配列mEq）をMMU02 内の配列mEq にコピーするために、RCU03 に指示を出す。RCU03 はその指示に従い、RCU13 及びNetwork4経由で、MMU12 内の配列mEq をMMU02 内の配列mEqに転送（コピー）する（Receive 操作）。次に、CPU01 （rank0 ）はMMU02 内のNode1 の計算結果（mEq）を最終結果（Eq）にマージする。同様に、CPU01 （rank0 ）は、MMU22,32内の計算結果（配列mEq）をMMU02 内の配列mEq にコピーするために、RCU03 に指示を出す。RCU03 はその指示に従い、RCU23 及びNetwork4経由、RCU33 及びNetwork4経由で、MMU22,32内の配列mEq をMMU02 内の配列mEqに転送（コピー）する（Receive 操作）。CPU01 （rank0 ）はMMU02 内のNode2 及びNode3 の計算結果（mEq）を最終結果（Eq）にマージして一連の動作が完了となる。
【００１８】
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は、MMU12 内の計算結果（配列mEq）をMMU02 内の配列mEq にコピーするために、RCU13 に指示を出す。RCU13 はその指示に従い、MMU12 内の配列mEqをNetwork4経由でRCU03 に転送する（Send操作）。
【００１９】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、MMU22 内の計算結果（配列mEq）をMMU02 内の配列mEq にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、MMU22 内の配列mEqをNetwork4経由でRCU03 に転送する（Send操作）。
【００２０】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は、MMU32 内の計算結果（配列mEq）をMMU02 内の配列mEq にコピーするために、RCU33 に指示を出す。RCU33 はその指示に従い、MMU32 内の配列mEqをNetwork4経由でRCU03 に転送する（Send操作）。
【００２１】
ここで、各フェーズでの処理時間を後述する本発明の実施例と同様に下記のように定めることにする。但し、T とは本分散メモリ型並列計算機システムの1 マシンクロックに相当するものとする。
1. (1) 、(3) のデータ分配／収集に要する時間（1Node 分） ： 100T
2. (2) のローカル計算に要する時間（Node0 ） ：1000T
3. (2) のローカル計算に要する時間（Node1 ） ：1000T
4. (2) のローカル計算に要する時間（Node2 ） ： 800T
5. (2) のローカル計算に要する時間（Node3 ） ： 900T
このとき、従来技術では図16に示すようなタイムチャートとなり、(1) 〜(3) までの処理時間は1600T となる。
【００２２】
【発明が解決しようとする課題】
上述したように従来技術においては、スレーブノードから計算結果を集めて結果をマージする処理をマスタノードが一手に引き受けている。このため、各ノードに割り当てられた計算量が均等で、(2) の各ノードにおけるローカル計算コストが(1) と(3) に比べて十分大きい場合は、効率の良い並列計算機と見なすことができるが、各ノードに割り当てられた計算量が不均一であったり、計算量は均一ではあるが(2) のコストが(1) と(3) と比べてそれ程変わらない時などは、計算量が最も多いノードの処理時間に全体が引きずられてしまい、効率の悪い並列計算機となってしまう。
【００２３】
本発明はこのような問題を解決したもので、分散メモリ型並列計算機における分散処理の高速化を図ることを目的とする。
【００２４】
【課題を解決するための手段】
本発明にかかる分散メモリ型並列計算機における分散処理方法は、各々少なくともCPU とメモリとデータ転送手段とを含む複数のノードがネットワークを通じて相互に接続された分散メモリ型並列計算機で、複数のノードの１つをマスタノード、残りのノードをスレーブノードに定め、マスタノード及びスレーブノードで処理を分散して実行する方法において、
（ａ）マスタノードからスレーブノードへ初期データを転送するステップと、
（ｂ）各ノードにおいてローカル計算を行うステップと、
（ｃ）ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めるステップと、
（ｄ）結果マージ用マスタノードが他のスレーブノードのローカル計算結果を収集してマージするステップと、
（ｅ）マスタノードが結果マージ用マスタノードでマージされたローカル計算結果を収集して最終結果にマージするステップと、
を含んでいる。
【００２５】
前記ステップｃでは、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の所定のカウンタに対してテストアンドセット命令を実行することで、結果マージ用マスタノードの決定を行うことができる。
【００２６】
前記ステップｄにおいては、結果マージ用マスタノードは、予め定められたスレーブノードの順番に従ってローカル計算結果の収集とマージを行うようにしても良い。また、前記ステップｄにおいては、結果マージ用マスタノードは、ローカル計算を終えたスレーブノードの順番に従ってローカル計算結果の収集とマージを行うようにしても良い。この場合、前記ステップｃに代えて、ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めると共に、他のスレーブノードのローカル計算を終えた順番を決定するステップｃ’が設けられる。そして、このステップｃ’では、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の第１番目のカウンタから第（ノード数−1）番目のカウンタまで順に、テストアンドセット命令が成功するカウンタに至るまで、それぞれテストアンドセット命令を実行することで、結果マージ用マスタノードの決定とローカル計算を終えた順番の決定とを行うことができる。
【００２７】
【作用】
本発明にあっては、計算結果のマージ処理はマスタノードに全て任されるのではなく、ローカル計算を最初に終えたスレーブノードに一部分担させる。マスタノードは全てのスレーブノードへの初期データの分配が完了しなければ自身のローカル計算を開始できないので、一般的にはローカル計算の完了が遅れがちになる。本発明によれば、マスタノードのローカル計算の完了を待たずして、スレーブノード群でマージ処理を開始することができるので、全体的な負荷分散が図れ、分散メモリ型並列計算機における分散処理の高速化が図られる。
【００２８】
【発明の実施の形態】
次に本発明の実施の形態の例について図面を参照して詳細に説明する。
【００２９】
図1 は本発明を適用した分散メモリ型並列計算機の一例を示すブロック図である。この例の分散メモリ型並列計算機は、複数の計算ノード0,1,2,3 と、それらを相互に結ぶネットワーク(Network)4とを有している。計算ノード0 は、CPU （中央演算装置:Central Processing Unit）01、MMU （主記憶装置:Main Memory Unit ）02、RCU （遠隔制御装置:Remote Control Unit）03で構成される。計算ノード1,2,3 も同様に、CPU11,21,31 、MMU12,22,32 、RCU13,23,33 で構成される。また、ネットワーク4 は、テストアンドセット（Test&Set）機能を具備した通信レジスタGCR （Global Communication Register ）41を有している。なお、日本電気株式会社製のSXシリーズのハードウェアでは、通信レジスタ(Communication Register)に対する命令の1 つとして、TSCR(Test&Set CR) 命令がサポートされているので、それを使用することができる。
【００３０】
計算ノード0 において、CPU01 は、MMU02 に対するデータのロードとストアが可能であり、CPU01 ではロードしてきたデータを使って演算をし、結果をMMU02 にストアする。RCU03 は、CPU01 からの計算ノードを跨ぐ他ノードMMU 間のデータ転送命令を受け付け、他ノードのRCU と協調してノード間データ転送を実現する。例えば、CPU01 がRCU03 にMMU02 のデータをMMU12 に転送するよう指示した場合、RCU03 はMMU02 のデータをロードしてNetwork4経由でRCU13 に転送し、RCU13 は転送データをMMU12 にストアする。ここで、RCU03 がRCU13 にデータを送信する動作をSendと呼び、RCU13 がRCU03 からデータを受信する動作をReceive と呼ぶ。このように互いに異なる分散メモリ（ノード）間でデータの授受を行う場合は、Send側のノードとReceive 側のノードが1 対1 で決まる。他のノード1,2,3 も基本的に計算ノード0 と同じ機能を有する。
【００３１】
このような分散メモリ型並列計算機では、プログラムの処理時間を短縮するために、そのプログラムを複数のノードで分割実行して最後に結果をマージする。このとき、まとめ役のノードをマスタノード、それ以外のノードをスレーブノードと呼ぶ。また、この種の分散メモリ型並列計算機では、一般にMPI （Message Passing Interface ）プログラムが利用される。本実施の形態におけるMPI プログラムは、下記３つのフェーズ（(1),(2),(3) ）から構成され、特に(3) の部分の開始時間を早めることで、全体の処理時間を短縮している。
(1) マスタノードからスレーブノードへの初期データの分配
(2) 各ノードにおけるローカル計算
(3) スレーブノードからマスタノードへの結果データの収集と結果のマージ
【００３２】
即ち、(3) は従来はマスタノードが全てを引き受けていたが、本実施の形態では(2) のローカル計算を最初に終えたスレーブノードを動的に結果マージ用マスタノードに定めて集計処理を行わせることにより、(3) の開始時間を早めている。このとき必要となるのが、Network4内に具備されたGCR41 であり、(2) のローカル計算を最初に終えたスレーブノードがGCR41 に(2) 完了の印と自ノード番号を書き込むことにより、(3) の処理において他のスレーブノードが結果を送るべき結果マージ用マスタノードを知ることができ、(3) の動作を可能としている。
【００３３】
図2 に本実施の形態におけるMPI プログラムの前記(1) 、(2) 、(3) に対応する部分の概略を示す。なお、MPI プログラムはコンパイラにかけられてアセンブラコードに変換され、各ノードのMMU に格納されて実行に供される。
【００３４】
先ず、マスタノードからスレーブノードへの初期データの分配(1) では、各ノードは、自ノードがマスタノードなら初期データをスレーブノードへ送り、自ノードがスレーブノードなら初期データをマスタノードから受け取る処理を行う。
【００３５】
各ノードにおけるローカル計算(2) では、各ノードは、初期データを元に自ノードが分担する計算部分をローカルに計算する。
【００３６】
スレーブノードからマスタノードへの結果データの収集と結果のマージ(3) は、本実施の形態では、以下の3 つのフェーズに分けられる。
(3)-1:結果マージ用マスタノードの決定
(3)-2:スレーブノードから結果マージ用マスタノードへの結果データの収集と結果のマージ
(3)-3:結果マージ用マスタノードからマスタノードへのマージ結果の収集と結果のマージ
【００３７】
結果マージ用マスタノードの決定(3)-1 では、(2) のローカル計算を最初に終えたスレーブノードがGCR41 に(2) 完了の印と自ノード番号を書き込むことで行われる。
【００３８】
スレーブノードから結果マージ用マスタノードへの結果データの収集と結果のマージ(3)-2 では、各ノードは、自ノードが結果マージ用マスタノードならスレーブノードからローカル計算結果を収集してマージし、自ノードが結果マージ用マスタノードでないスレーブノードなら、自ノードのローカル計算結果を結果マージ用マスタノードに送る処理を行う。ここで、結果マージ用マスタノードにおけるマージは、予め定められたスレーブノードの順番で固定的に行っても良く（後述の第1 の実施例）、(2) のローカル計算が終わった順番で行っても良い（後述の第2 の実施例) 。
【００３９】
結果マージ用マスタノードからマスタノードへのマージ結果の収集と結果のマージ(3)-3 では、各ノードは、自ノードがマスタノードであれば、結果マージ用マスタノードからマージ結果を受け取って自ノードのローカル計算結果とマージし、自ノードが結果マージ用マスタノードであれば、(3)-2 のマージ結果をマスタノードに送る処理を行う。
【００４０】
【実施例】
次に本発明の実施例について図面を参照して詳細に説明する。
【００４１】
〔第１の実施例〕
〔構成〕
本実施例で使用する分散メモリ型並列計算機は、本発明の実施の形態で説明した図1 のものと同様である。つまり、複数の計算ノード0,1,2,3 と、それらを結ぶネットワーク4 とを有し、各計算ノード0,1,2,3 は、CPU01,11,21,31、MMU01,12,22,32、RCU03,13,23,33で構成され、ネットワーク4 は通信レジスタGCR41 を有している。
【００４２】
本実施例で動作させるMPI プログラム（プログラム１）の一例を図3 〜図7 に示す。なお、MPI プログラムはコンパイラにかけられてアセンブラコードに変換され、各ノードのMMU に格納されて実行に供される。
【００４３】
本発明の実施の形態で説明したように、MPI プログラムの(3) 部分に改良を加えており、(3) を３つのフェーズに分割している（(3)-1 、(3)-2 、(3)-3 ）。以下に、(1) 、(2) 、(3)-1 、(3)-2 、(3)-3 の各フェーズを説明する。
【００４４】
(1) 初期データ分配（図3)
配列q[N3＿max]を倍精度（8Byte ）データとしてrank0 （マスタノード）からrank1 〜rank3 （スレーブノード）に転送する。
【００４５】
具体的には、各ノードは、通信タグtag を1 にセットし、自ノードがrank0 (マスタノード）ならば、配列q[N3＿max]を倍精度（8Byte ）データとして、通信タグtag (=1)をつけてdist1,2,3 (送信先ランク1,2,3:スレーブノード) 宛に順番に送信し、自ノードがrank0 (マスタノード）でないならば、配列q[N3＿max]に、通信tag (=1)がついているrank0 からのデータを受信する。
【００４６】
(2) ローカル計算（図4)
配列q を使って計算をさせる。要素をi とj とに分け、i を外側ループで回し、j を内側ループで回す。このとき、外側ループの単位でスプリット（分散）し、各計算ノードに割り当てる。各ノードの計算結果は、各ノードの配列mEq[i]に格納される。なお、図4 において、sizeはノード数を示し、今の場合は4 である。また、mEqi＝0.D0はmEqiの全要素を0 に初期化する処理を、dRは定数を示す。
【００４７】
(3)-1 結果マージ用マスタノードの決定 (図5)
スレーブノードの中から結果マージ用のマスタノードを決定する。ローカル計算終了後、各スレーブノードは順次に通信レジスタ（counter(0)）をアクセスし、自分が結果マージ用マスタノードなのかどうかをチェックする。最初にアクセスしたスレーブノードが結果マージ用ノードとなる（counter(0)の最上位bit が”0 ”の場合、本bit に”1 ”をSet して（権利を獲得したことを表示する）、下位bit に自Node番号を書き込む）。
【００４８】
具体的には、各ノードは、mask1 に最上位bit のみ”１”のマスクデータを、mask2 に最上位bit のみ”０”のマスクデータをそれぞれセットする。そして、各スレーブノードは、Test&Set機能を使って、通信レジスタ中のcounter(0)をアクセスして最上位bit をflagに置いて0 か否かを検査し、0 であれば、自ノードのrankとmask1 との論理和をsetdata において、このsetdata の値をcounter(0)に書き込むことで、counter(0)の最上位bit を”１”にすると共に下位bit に自Node番号を書き込む。なお、MPI プログラムをコンパイラにかけてアセンブラコードに変換すると、図5 のflag＝counter(0).shiftr.63の文からcounter(0)＝setdata の文までがアセンブラコード1 命令からなるTest&Set命令に変換されるため、実際は各スレーブノードはこのTest&Set命令を実行することになる。
【００４９】
(3)-2 計算結果のマージ（rank0 以外） (図6)
各ノード（rank0 以外）の計算結果（mEq[i]）を結果マージ用マスタノードに転送し、結果マージ用マスタノードでは、計算結果をマージして配列Eq[i] に結果を格納する。この時、マージされる側（スレーブノード）の順番は、結果マージ用マスタノードのノード番号を先頭とした昇順とする（固定）。
【００５０】
具体的には、各ノードは、通信タグtag を2 にセットし、アクセスして得た通信レジスタ41中のcounter(0)とmask2 との論理積をmasterに置き、自ノードのrankがmasterと等しければ、つまり自ノードが結果マージ用マスタノードであれば、以下の処理を実行する。先ず、自ノードのローカル計算結果mEq[i]を配列Eq[i] にコピーする。次に、rank3 、rank1 のノードの順に(slave＝(dist ＋master).mod.size、if(slave.ne.master && slave.ne.0): modはモジュロ演算) 、配列mEq に、通信tag (=2)がついているデータを受信して、配列Eq[i] に格納されているデータとマージする。他方、自ノードが結果マージ用マスタノードでないスレーブノードの場合、配列mEq[N3＿max]を倍精度（8Byte ）データとして、通信タグtag (=2)をつけてmaster(結果マージ用マスタノード) 宛に送信する。
【００５１】
(3)-3 計算結果のマージ（rank0 ） (図7)
最終結果はマスタノード（rank0 ）に戻す必要があるので、結果マージ用マスタノードからマスタノード（rank0 ）に配列Eq[i] を転送して結果のマージをして一連の処理が完了となる。
【００５２】
具体的には、各ノードは、通信タグtag を3 にセットし、自ノードがrank0(マスタノード) であれば、配列Eq[i] に、通信tag (=3)がついているmaster (結果マージ用マスタノード) からのデータを受信し、自ノードのローカル計算結果mEq[i]とマージする。他方、自ノードが結果マージ用マスタノードであれば、配列Eq[i] を、通信タグtag (=3)をつけてrank0(マスタノード) 宛に送信する。
【００５３】
〔動作〕
次に、図1 のブロック図と図3 〜図7 のプログラム1 を元に、本実施例における分散メモリ型並列計算機の一連の動作について説明する。なお、rank2 のノード2 が(2) のローカル計算を最初に完了したものとして説明する。
【００５４】
(1) データ分配
＜rank0 （Node0 ）＞
CPU01 （rank0 ）はMMU02 内にある初期データ（配列q ）をMMU02 からMMU12 に転送するようRCU03 に指示を出す。RCU03 はその指示に従い、配列q をMMU02 からNetwork4経由でRCU13 に転送する（Send操作）。同様に、CPU01 （rank0 ）はMMU02 内にある初期データ（配列q ）をMMU02 からMMU22,32に転送するようRCU03 に指示を出し、RCU03 はその指示に従い、配列q をMMU02 からNetwork4経由でRCU23,33に転送する（Send操作）。
【００５５】
＜rank1 （Node1 ）＞
CPU11 （rank1 ）はRCU03 から送られてくる配列q をMMU12 に格納するようRCU13 に指示を出し、RCU13 は配列q をMMU12 に格納する（Receive 操作）。
【００５６】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）はRCU03 から送られてくる配列q をMMU22 に格納するようRCU23 に指示を出し、RCU23 は配列q をMMU22 に格納する（Receive 操作）。
【００５７】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）はRCU03 から送られてくる配列q をMMU32 に格納するようRCU33 に指示を出し、RCU33 は配列q をMMU32 に格納する（Receive 操作）。
【００５８】
(2) ローカル計算
＜rank0 （Node0 ）＞
CPU01 （rank0 ）は配列q[i=0,4,...] とq[j=i+1,...]間の要素間計算をして結果をMMU02 内の配列mEq[i=0,4,...]に書き込む。
【００５９】
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は配列q[i=1,5,...] とq[j=i+1,...]間の要素間計算をして結果をMMU12 内の配列mEq[i=1,5,...]に書き込む。
【００６０】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は配列q[i=2,6,...] とq[j=i+1,...]間の要素間計算をして結果をMMU22 内の配列mEq[i=2,6,...]に書き込む。
【００６１】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は配列q[i=3,7,...] とq[j=i+1,...]間の要素間計算をして結果をMMU32 内の配列mEq[i=3,7,...]に書き込む。
【００６２】
(3)-1 結果マージ用ノードの決定(rank0以外)
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は、Network4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行するが、今の場合、counter(0)の最上位bit 値はNode2 によって既に”１”にセットされているので、ノーオペレーションとなる。
【００６３】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、Network4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行する。今の場合、counter(0)の最上位bit は”0 ”なので、counter(0)の最上位bit が”1 ”にセットされるのと同時に、counter(0)の下位bit にrank2 のNode番号が書き込まれる。
【００６４】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は、Network4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行するが、今の場合、counter(0)の最上位bit 値はNode2 によって既に”１”にセットされているので、ノーオペレーションとなる。
【００６５】
(3)-2 計算結果のマージ（rank0 以外）
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードがNode2 であることを認識する。次に、MMU12 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU13 に指示を出す。RCU13 はその指示に従い、MMU12 内の配列mEqをNetwork4経由でRCU23 に転送する（Send操作）。
【００６６】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードが自分自身であることを認識する。次に、MMU22 内にある計算結果（配列mEq ）を最終結果を格納する配列Eqにコピーする。次に、CPU21 （rank2 ）は、MMU32 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、RCU33 及びNetwork4経由で、MMU32 内の配列mEq をMMU22 内の配列mEqに転送（コピー）する（Receive 操作）。次に、CPU21 （rank2 ）はMMU22 内のNode3 の計算結果（mEq）を最終結果（Eq）にマージする。同様に、CPU21 （rank2 ）は、MMU12 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、RCU13 及びNetwork4経由で、MMU12 内の配列mEq をMMU22 内の配列mEqに転送（コピー）する（Receive 操作）。CPU21 （rank2 ）はMMU22 内のNode1 の計算結果（mEq）を最終結果（Eq）にマージする。マージの順番は、計算結果マージ用マスタノード（Node2 ）を先頭とした昇順とする（Node3,Node1 の順）。
【００６７】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードがNode2 であることを認識する。次に、MMU32 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU33 に指示を出す。RCU33 はその指示に従い、MMU32 内の配列mEqをNetwork4経由でRCU23 に転送する（Send操作）。
【００６８】
(3)-3 計算結果のマージ（rank0 ）
＜rank0 （Node0 ）＞
CPU01 （rank0 ）は、MMU22 内の最終結果EqをMMU02 内にコピーするために、RCU03 に指示を出す。RCU03 はその指示に従い、MMU22 内の配列EqをRCU23 及びNetwork4経由でMMU02 に転送（Receive 操作）する。次に、CPU01 はMMU02 内のmEq とEqをマージして一連の動作が完了となる。
【００６９】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、MMU22 内の最終結果EqをMMU02 内にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、MMU22 内の配列EqをNetwork4経由でRCU03 に転送する（Send操作）。
【００７０】
以上、Network4にTest&Set機能（最上位ビットが”0 ”ならば”1 ”にして下位ビットにデータを書き込み、最上位ビットが”1 ”ならばノーアクション）を具備したGCR41 を設け、その機能を使って計算結果をマージする順番をプログラム制御することで、マージ処理の開始時間を早めることができ、分散処理全体の実行時間が短縮につながる。
【００７１】
ここで便宜上、各フェーズでの処理時間を下記のように定めることにする。但し、T とは本分散メモリ型並列計算機システムの1 マシンクロックに相当するものとする。
1.(1),(3)-2 ,(3)-3 のデータ分配／収集に要する時間（1Node 分） ： 100T
2.(2) のローカル計算に要する時間（Node0 ） ：1000T
3.(2) のローカル計算に要する時間（Node1 ） ：1000T
4.(2) のローカル計算に要する時間（Node2 ） ： 800T
5.(2) のローカル計算に要する時間（Node3 ） ： 900T
6.(3)-1 のGCR アクセスに要する時間 ： 0T
※GCR アクセスはデータ転送／ローカル計算に比べて無視できる程小さいとする。
このとき、本実施例における構成例では、図8 に示すようなタイムチャートとなり、(1) 〜(3) （(3)-1,(3)-2,(3)-3 ）までの処理時間は1500T となる。
【００７２】
〔効果〕
本実施例によれば、以下のような効果が得られる。
1. 第１の効果は、ローカル計算を最初に完了したスレーブノードに結果のマージ処理の一部を行わせることで結果マージ処理の開始時間を早めることができることである。
2. 第２の効果は、ローカル計算における負荷分散（計算データの割り当て）が均等に行われていない場合でも、ローカル計算の完了順に従って結果のマージ処理を分担するスレーブノードが決定されるので、全体的な負荷分散が図れ、各ノードを効率よく使えることである。
3. 第3 の効果は、上記負荷分散を図ることにより、結果のマージ処理を高速化でき、その結果、プログラム全体の処理時間が短縮されることである。
【００７３】
〔実施例の拡張〕
1. 本実施例では、マスタノードをNode0 として説明したが、マスタノードの選定に制限はない。
2. 本実施例では、計算結果のマージ用マスタノードをNode2 として説明したが、その選定に制限はない。
3. 本実施例では、ネットワークに接続される計算ノードは4 つとして説明したが、これらの数に制限はない。
4. 本実施例では、1 つの計算ノード内は1 つのCPU で構成されるとして説明したが、これらの数に制限はない。つまり、ノード内はマルチCPU による共有メモリ型でもよい。
5. 本実施例の動作説明では、各計算フェーズの処理時間を固定値を用いて説明したが、これらの値に制限はない。
6. 本実施例では、結果マージ用マスタノードにおけるマージ順は、結果マージ用マスタノードを先頭として昇順としたが、rank順(Node番号順）としても良い。rank順とした場合、先の動作例では、結果マージ用マスタノード(Node2) は、Node1(rank1)、Node3(rank3)の順にマージを行うことになる。
【００７４】
〔第２の実施例〕
〔構成〕
本実施例が適用される分散メモリ型並列計算機の構成は、第１の実施例のものと同じである。第１の実施例との相違点は、GCR41 の使い方（MPI プログラムのコーディング）にある。第１の実施例では、(3)-2 の結果マージ処理においてスレーブノードの順番が昇順であったのに対し、本実施例では、スレーブノードの順番を(2) のローカル計算が終わった順とする。そのため、本実施例では、通信レジスタ41として、結果マージ用マスタノードを決定するためのcounter(0)に加えて、(2) のローカル計算の完了順を決定するためにcounter(1)、counter(2)を使用する。従って、本実施例では、合計3 個 (Node数−1)のcounter を使用する。
【００７５】
本実施例で動作させるMPI プログラム（プログラム２）も第１の実施例におけるプログラム１と同様に(1) 、(2) 、(3)-1 、(3)-2 、(3)-3 の各フェーズを有する。その内、(1) と(2) は第１の実施例における図３、図４と同じなので説明は省略し、(3)-1 、(3)-2 、(3)-3 の一例を図9 〜図11に示す。以下、(3)-1,(3)-2,(3)-3 について説明する。なお、MPI プログラムはコンパイラにかけられてアセンブラコードに変換され、各ノードのMMU に格納されて実行に供される。
【００７６】
(3)-1 結果マージ用マスタノードの決定 (rank0 以外) (図9)
結果マージ用のマスタノードを決定する。ローカル計算終了後、各スレーブノードのCPU は順次通信レジスタ（counter(0)）をアクセスし、自分が結果マージ用マスタノードなのかどうかをチェックする。最初にアクセスしたスレーブノードが結果マージ用ノードとなる（counter(0)の最上位bit が”0 ”の場合、本bit に”1 ”をSet して（権利を獲得したことを表示する）、下位bit に自Node番号を書き込む）。
【００７７】
また、2 番目にアクセスしたスレーブノードはcounter(1)の最上位bit に”1 ”をSet して（(2) のローカル計算が完了したことを表示する）、下位bit に自Node番号を書き込む。以下同様に、3 番目のスレーブノードはcounter(2)に同様のアクセスをする。このcounter(1)、(2) に対するアクセスもTest&Set機能により行われる。
【００７８】
具体的には、各ノードは、mask1 に最上位bit のみ”１”のマスクデータを、mask2 に最上位bit のみ”０”のマスクデータをそれぞれセットする。そして、各スレーブノードは、Test&Set機能を使って、通信レジスタ中のcounter(0)をアクセスして最上位bit をflagに置いて0 か否かを検査し、0 であれば、自ノードのrankとmask1 との論理和をsetdata において、このsetdata の値をcounter(0)に書き込むことで、counter(0)の最上位bit を”１”にすると共に下位bit に自Node番号を書き込む。また、counter(0)の最上位bit が既に”１”なら、次には通信レジスタ中のcounter(1)に対して同様の操作を試み、counter(1)の最上位bit が既に”１”なら最後に通信レジスタ中のcounter(2)に対して同様の操作を試みる。なお、MPI プログラムをコンパイラにかけてアセンブラコードに変換すると、図5 のflag＝counter(i).shiftr.63の文からcounter(i)＝setdata の文までがアセンブラコード1 命令からなるTest&Set命令に変換されるため、実際は各スレーブノードはこのTest&Set命令を実行することになる。
【００７９】
(3)-2 計算結果のマージ（rank0 以外） (図10)
各ノード（rank0 以外）の計算結果（mEq[i]）を結果マージ用マスタノードに転送し、結果マージ用マスタノードでは、計算結果をマージして配列Eq[i] に結果を格納する。この時のマージされる側（スレーブノード）の順番は、counter(1)〜counter(2)に格納されているNode番号の順番に従う（(2) のローカル計算が完了した順）。
【００８０】
具体的には、各ノードは、通信タグtag を2 にセットし、アクセスして得た通信レジスタ41中のcounter(0)とmask2 との論理積をmasterに置き、自ノードのrankがmasterと等しければ、つまり自ノードが結果マージ用マスタノードであれば、以下の処理を実行する。先ず、自ノードのローカル計算結果mEq[i]を配列Eq[i] にコピーする。次に、counter(1)、(2) を順に参照して(2) のローカル計算を次に早く終えたrank1、rank3 のノードの順に、配列mEq に、通信tag (=2)がついているデータを受信して、配列Eq[i] に格納されているデータとマージする。他方、自ノードが結果マージ用マスタノードでないスレーブノードの場合、配列mEq[N3＿max]を倍精度（8Byte ）データとして、通信タグtag (=2)をつけてmaster(結果マージ用マスタノード) 宛に送信する。
【００８１】
(3)-3 計算結果のマージ（rank0 ） (図11)
最終結果はマスタノード（rank0 ）に戻す必要があるので、結果マージ用マスタノードからマスタノード（rank0 ）に配列Eq[i] を転送して結果のマージをして一連の処理が完了となる。
【００８２】
〔動作〕
次に、図１のブロック図と図9 〜図11のプログラム2 を元に、本実施例における分散メモリ型並列計算機の一連の動作について説明する。なお、rank2 のノード2 が(2) のローカル計算を最初に完了し、次にrank1 のノード1 が(2) のローカル計算を完了し、次にrank3 のノード3 が(2) のローカル計算を完了し、最後にrank0 のノード0 が(2) のローカル計算を完了したものとして説明する。また、(1) と(2) は第1 の実施例と全く変わらないので説明は省略する。
【００８３】
(3)-1 結果マージ用CPU の決定(rank0以外)
＜rank1 （Node1 ）＞
CPU11 （rank1 ）はNetwork4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行するが、今の場合、counter(0)の最上位bit 値はNode2 によって既に”１”にセットされているので、ノーオペレーションとなる。このため、次にCPU11 （rank1 ）はNetwork4におけるGCR41 中のレジスタ（counter(1)）に対してTest&Set命令を実行し、今の場合、counter(1)の最上位bit は”0 ”なので、counter(1)の最上位bit が”1 ”にセットされるのと同時に、counter(1)の下位bit にrank1 のNode番号が書き込まれる。
【００８４】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）はNetwork4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行し、今の場合、counter(0)の最上位bit 値は”0 ”なので、counter(0)の最上位bit が”1 ”にセットされるのと同時に、counter(0)の下位bit にrank2 のNode番号が書き込まれる。
【００８５】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）はNetwork4におけるGCR41 中のレジスタ（counter(0)）に対してTest&Set命令を実行するが、今の場合、counter(0)の最上位bit 値はNode2 によって既に”１”にセットされているので、ノーオペレーションとなる。このため、次にCPU31 はNetwork4におけるGCR41 中のレジスタ（counter(1)）に対してTest&Set命令を実行するが、今の場合、counter(1)の最上位bit 値はNode1 によって既に”１”にセットされているので、ノーオペレーションとなる。このため、次にCPU31 はNetwork4におけるGCR41 中のレジスタ（counter(2)）に対してTest&Set命令を実行し、その最上位bit 値は”0 ”なので、counter(2)の最上位bit が”1 ”にセットされるのと同時に、counter(2)の下位bit にrank3 のNode番号が書き込まれる。
【００８６】
(3)-2 計算結果のマージ（rank0 以外）
＜rank1 （Node1 ）＞
CPU11 （rank1 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードがNode2 であることを認識する。次に、MMU12 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU13 に指示を出す。RCU13 はその指示に従い、MMU12 内の配列mEqをNetwork4経由でRCU23 に転送する（Send操作）。
【００８７】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードが自分自身であることを認識する。次に、MMU22 内にある計算結果（配列mEq ）を最終結果を格納する配列Eqにコピーする。次に、CPU21 （rank2 ）はマージすべき相手ノードを決定するために、GCR41 のcounter(1)をアクセスし、そのリプライによりマージすべき相手ノードがCPU11 （rank1 ）であることを知ると、MMU12 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、RCU13 及びNetwork4経由で、MMU12 内の配列mEq をMMU22 内の配列mEqに転送（コピー）する（Receive 操作）。次に、CPU21 （rank2 ）はMMU22 内のNode1 の計算結果（mEq）を最終結果（Eq）にマージする。同様に、CPU21 （rank2 ）は、GCR41 のcounter(2)をアクセスし、次にマージすべき相手ノードがCPU31 （rank3 ）であることを知ると、MMU32 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、RCU33 及びNetwork4経由で、MMU32 内の配列mEq をMMU22 内の配列mEqに転送（コピー）する（Receive 操作）。CPU21 （rank2 ）はMMU22 内のNode3 の計算結果（mEq）を最終結果（Eq）にマージする。
【００８８】
＜rank3 （Node3 ）＞
CPU31 （rank3 ）は、GCR41 中のレジスタ（counter(0)）をアクセスし、結果マージ用マスタノードがNode2 であることを認識する。次に、MMU32 内の計算結果（配列mEq）をMMU22 内の配列mEq にコピーするために、RCU33 に指示を出す。RCU33 はその指示に従い、MMU32 内の配列mEqをNetwork4経由でRCU23 に転送する（Send操作）。
【００８９】
(3)-3 計算結果のマージ（rank0 ）
＜rank0 （Node0 ）＞
CPU01 （rank0 ）は、MMU22 内の最終結果EqをMMU02 内にコピーするために、RCU03 に指示を出す。RCU03 はその指示に従い、MMU22 内の配列EqをRCU23 及びNetwork4経由でMMU02 に転送（Receive 操作）する。次に、CPU01 はMMU02 内のmEq とEqをマージして一連の動作が完了となる。
【００９０】
＜rank2 （Node2 ）＞
CPU21 （rank2 ）は、MMU22 内の最終結果EqをMMU02 内にコピーするために、RCU23 に指示を出す。RCU23 はその指示に従い、MMU22 内の配列EqをNetwork4経由でRCU03 に転送する（Send操作）。
【００９１】
以上、Network4にTest&Set機能（最上位ビットが”0 ”ならば”1 ”にして下位ビットにデータを書き込み、最上位ビットが”1 ”ならばノーアクション）を具備したGCR41 を設け、その機能を使って計算結果をマージする順番をプログラム制御することで、マージ処理の開始時間を早めることができ、分散処理全体の実行時間が短縮につながる。
【００９２】
各フェーズでの処理時間を第１の実施例と同様に設定すると、第２の実施例における構成例では、図12に示すタイムチャートとなり、(1) 〜(3) （(3)-1 、(3)-2 、(3)-3 ）までの時間は1400T となる。
【００９３】
〔拡張〕
第２の実施例についても、第１の実施例で説明したものと同様の拡張が可能である。
【００９４】
【発明の効果】
以上説明したように本発明によれば、ローカル計算を最初に完了したスレーブノードを動的に結果マージ用マスタノードに定めて、この結果マージ用マスタノードに結果のマージ処理の一部を分担させたことにより、マスタノードが常にマージ処理の全てを行っていた従来技術に比べて、マージ処理の開始時間を早めることができ、その分、プログラム全体の処理時間を短縮することができる。
【００９５】
また、結果マージ用マスタノードが結果をマージするノードの順番を固定化せずにローカル計算を終えた順とすることにより、プログラム全体の処理時間をより一層短縮することができる。
【図面の簡単な説明】
【図１】本発明を適用した分散メモリ型並列計算機の一例を示すブロック図である。
【図２】本発明の実施の形態におけるMPI プログラムの概要を示すフローチャートである。
【図３】本発明の第１の実施例におけるMPI プログラムの初期データ分配処理部分のプログラム例を示す図である。
【図４】本発明の第１の実施例におけるMPI プログラムのローカル計算部分のプログラム例を示す図である。
【図５】本発明の第１の実施例におけるMPI プログラムの結果マージ用マスタノードの決定部分のプログラム例を示す図である。
【図６】本発明の第１の実施例におけるMPI プログラムの結果マージ用マスタノードによる計算結果のマージ処理部分のプログラム例を示す図である。
【図７】本発明の第１の実施例におけるMPI プログラムのマスタノードによる計算結果のマージ処理部分のプログラム例を示す図である。
【図８】本発明の第１の実施例のタイムチャートを示す図である。
【図９】本発明の第２の実施例におけるMPI プログラムの結果マージ用マスタノードの決定部分のプログラム例を示す図である。
【図１０】本発明の第２の実施例におけるMPI プログラムの結果マージ用マスタノードによる計算結果のマージ処理部分のプログラム例を示す図である。
【図１１】本発明の第２の実施例におけるMPI プログラムのマスタノードによる計算結果のマージ処理部分のプログラム例を示す図である。
【図１２】本発明の第2 の実施例のタイムチャートを示す図である。
【図１３】従来技術におけるMPI プログラムの初期データ分配処理部分のプログラム例を示す図である。
【図１４】従来技術におけるMPI プログラムのローカル計算部分のプログラム例を示す図である。
【図１５】従来技術におけるMPI プログラムのマージ処理部分のプログラム例を示す図である。
【図１６】従来技術のタイムチャートを示す図である。
【符号の説明】
０〜３…ノード
01,11,21,31 …CPU(中央演算装置:Central Processing Unit)
02,12,22,32 …MMU(主記憶装置:Main Memory Unit)
03,13,23,33 …RCU(遠隔制御装置:Remote Control Unit)
4 …ネットワーク
41…通信レジスタ(GCR:Global Communication Register)

Claims (10)

1. 各々少なくともCPU とメモリとデータ転送手段とを含む複数のノードがネットワークを通じて相互に接続された分散メモリ型並列計算機で、複数のノードの１つをマスタノード、残りのノードをスレーブノードに定め、マスタノード及びスレーブノードで処理を分散して実行する方法において、
   （ａ）マスタノードからスレーブノードへ初期データを転送するステップと、
   （ｂ）各ノードにおいてローカル計算を行うステップと、
   （ｃ）ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めるステップと、
   （ｄ）結果マージ用マスタノードが他のスレーブノードのローカル計算結果を収集してマージするステップと、
   （ｅ）マスタノードが結果マージ用マスタノードでマージされたローカル計算結果を収集して最終結果にマージするステップと、
   を含む分散メモリ型並列計算機における分散処理方法。
2. 前記ステップｄにおいて、結果マージ用マスタノードは、予め定められたスレーブノードの順番に従ってローカル計算結果の収集とマージを行う請求項１記載の分散メモリ型並列計算機における分散処理方法。
3. 前記ステップｃは、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の所定のカウンタに対してテストアンドセット命令を実行することで、結果マージ用マスタノードの決定を行う請求項１または２記載の分散メモリ型並列計算機における分散処理方法。
4. 前記ステップｃに代えて、
   （ｃ’）ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めると共に、他のスレーブノードのローカル計算を終えた順番を決定するステップ
   を含み、且つ、
   前記ステップｄにおいて、結果マージ用マスタノードは、ローカル計算を終えたスレーブノードの順番に従ってローカル計算結果の収集とマージを行う請求項１記載の分散メモリ型並列計算機における分散処理方法。
5. 前記ステップｃ’は、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の第１番目のカウンタから第（ノード数−1）番目のカウンタまで順に、テストアンドセット命令が成功するカウンタに至るまで、それぞれテストアンドセット命令を実行することで、結果マージ用マスタノードの決定とローカル計算を終えた順番の決定とを行う請求項４記載の分散メモリ型並列計算機における分散処理方法。
6. 各々少なくともCPU とメモリとデータ転送手段とを含む複数のノードがネットワークを通じて相互に接続された分散メモリ型並列計算機で、複数のノードの１つをマスタノード、残りのノードをスレーブノードに定め、マスタノード及びスレーブノードで処理を分散して実行するプログラムを記録した媒体であって、各ノードに、
   （ａ）マスタノードからスレーブノードへ初期データを転送するステップと、
   （ｂ）各ノードにおいてローカル計算を行うステップと、
   （ｃ）ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めるステップと、
   （ｄ）結果マージ用マスタノードが他のスレーブノードのローカル計算結果を収集してマージするステップと、
   （ｅ）マスタノードが結果マージ用マスタノードでマージされたローカル計算結果を収集して最終結果にマージするステップと、
   を実行させるプログラムを記録したコンピュータ可読記録媒体。
7. 前記ステップｄにおいて、結果マージ用マスタノードは、予め定められたスレーブノードの順番に従ってローカル計算結果の収集とマージを行う請求項６記載のコンピュータ可読記録媒体。
8. 前記ステップｃは、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の所定のカウンタに対してテストアンドセット命令を実行することで、結果マージ用マスタノードの決定を行う請求項６または７記載のコンピュータ可読記録媒体。
9. 前記ステップｃに代えて、
   （ｃ’）ローカル計算を一番早く終えたスレーブノードを結果マージ用マスタノードに定めると共に、他のスレーブノードのローカル計算を終えた順番を決定するステップ
   を実行させ、且つ、
   前記ステップｄにおいて、結果マージ用マスタノードは、ローカル計算を終えたスレーブノードの順番に従ってローカル計算結果の収集とマージを行う請求項６記載のコンピュータ可読記録媒体。
10. 前記ステップｃ’は、各スレーブノードがローカル計算を終えた時点で、ネットワークに設けられた通信レジスタ中の第１番目のカウンタから第（ノード数−1）番目のカウンタまで順に、テストアンドセット命令が成功するカウンタに至るまで、それぞれテストアンドセット命令を実行することで、結果マージ用マスタノードの決定とローカル計算を終えた順番の決定とを行う請求項９記載のコンピュータ可読記録媒体。

Images