(57)【要約】【課題】データ通信の遅延を解消するとともに、計算効率を向上することによって、並列計算の処理時間を短縮することを可能とする並列計算装置を提供する。【解決手段】入力した要素を用いて出力配列の要素を計算単位となる要素集合ごとに計算する計算手段と、計算手段で出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントする未受信要素カウント手段と、他の計算装置で参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントする未定義要素カウント手段と、未受信要素カウント手段によるカウントに応じて出力配列の要素を算出する際に参照する要素を受信するとともに、未定義要素カウント手段によるカウントに応じて他の計算装置に参照される要素を送信する送受信手段とを備える複数の計算装置によって構成される並列計算システムとする。【選択図】      図１
2015191442.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力するとともに、前記入力配列の要素から出力配列の要素を算出する際に参照する前記配列に含まれる要素を入力し、入力した要素を用いて前記出力配列の要素を計算単位となる要素集合ごとに計算する計算手段と、
前記計算手段において前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとにカウントする未受信要素カウント手段と、
他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとにカウントする未定義要素カウント手段と、
前記未受信要素カウント手段によるカウントに応じて前記出力配列の要素を算出する際に参照する要素を受信するとともに、前記未定義要素カウント手段によるカウントに応じて前記他の計算装置によって参照される要素を送信する送受信手段とを備える複数の計算装置によって構成される並列計算システム。
【請求項２】
前記計算手段によって算出された前記出力配列の要素と、前記計算手段において前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとに記録するカウンタ集合を含む未受信要素数カウンタと、前記他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとに記録するカウンタ集合を含む未定義要素数カウンタとを格納する記憶手段を備え、
前記未受信要素カウント手段は、
前記出力配列の要素を算出する際に参照する要素を受信するごとに前記未受信要素数カウンタの対応するカウンタの数値を変更し、
前記未定義要素カウント手段は、
前記送信単位となる要素集合を出力するごとに前記未定義要素数カウンタの対応するカウンタの数値を変更する請求項１に記載の並列計算システム。
【請求項３】
前記計算手段は、
前記他の計算装置によって参照される要素のうち算出が完了した要素の位置を前記未定義要素カウント手段に出力し、
前記未定義要素カウント手段は、
前記算出が完了した要素の位置を前記計算手段から入力し、前記未定義要素カウンタにおいて、前記他の計算装置によって参照される要素のうち算出が完了した要素の数を数えるカウンタを減算する請求項２に記載の並列計算システム。
【請求項４】
前記未定義要素カウント手段は、
前記未定義要素数カウンタにおいて数値がゼロになったカウンタが発生した場合、対応する前記送信単位となる要素集合を送信対象となる前記他の計算装置に送信する指示と、前記送信単位となる要素集合に含まれる要素を参照する前記他の計算装置の前記未受信要素数カウンタに含まれるカウンタのうち前記送信単位となる要素集合に含まれる要素の数を記録するカウンタの数値を変更するコマンドを送信する指示とを前記送受信手段に出し、
前記送受信手段は、
前記未定義要素数カウント手段の指示に応じて、前記送信単位となる要素集合を前記送信対象となる他の計算装置に送信するとともに、前記送信対象となる他の計算装置の前記未受信要素数カウンタに含まれるカウンタのうち前記送信単位となる要素集合に含まれる要素の数を記録するカウンタの数値を減算するコマンドを出力する請求項３に記載の並列計算システム。
【請求項５】
前記未受信要素カウント手段は、
前記未受信要素カウンタの対応するカウンタの数値がゼロであるとともに前記計算手段によって計算される要素の算出が完了することによって参照すべき要素が揃った前記計算単位となる要素集合に含まれる要素の計算を前記計算手段に指示する請求項２乃至４のいずれか一項に記載の並列計算システム。
【請求項６】
前記未定義要素カウント手段は、
前記未定義要素カウンタがゼロになった前記送信単位となる要素集合が発生すると、該当する前記送信単位となる要素集合を送信先に送信する指示を前記送受信手段に出し、
前記送受信手段は、
前記未定義要素カウント手段の指示に応じて、前記送信単位となる要素集合に含まれる要素を前記記憶手段の連続領域に再配置し、前記記憶手段に再配置された前記送信単位となる要素集合を前記送信先に送信する請求項５に記載の並列計算システム。
【請求項７】
前記未定義要素数カウント手段は、
前記出力配列と前記要素の位置から前記送信単位となる要素集合と前記送信先のペアの集合を導出するマップを構築するとともに、
前記マップに含まれる前記送信単位となる要素集合と前記送信先のペアを前記送信先に送信する際に、前記送信先の前記未受信要素数カウンタに含まれるカウンタのうちいずれをいくら減算すべきかを示す連想配列を構築し、
前記計算手段から前記要素の位置を取得した際に、前記要素の位置をキーとして前記マップを引くことによって導出した前記送信単位となる要素集合と前記送信先のペアを前記連想配列に当てはめて、対象となる前記カウンタの数値を減算するコマンドを送信する指示を前記送受信手段に出力する請求項６に記載の並列計算システム。
【請求項８】
前記複数の計算装置がネットワークを通じて接続されることを特徴とする請求項１乃至７のいずれか一項に記載の並列計算システム。
【請求項９】
複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力し、
前記入力配列の要素から出力配列の要素を算出する際に参照する前記配列に含まれる要素を入力し、
入力した要素を用いて前記出力配列の要素を計算単位となる要素集合ごとに計算し、
前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとにカウントし、
他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとにカウントし、
前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとにカウントするカウント値に応じて前記出力配列の要素を算出する際に参照する要素を受信し、
前記他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとにカウントするカウンタ値に応じて前記他の計算装置において参照される要素を送信する並列計算方法。
【請求項１０】
複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力する処理と、
前記入力配列の要素から出力配列の要素を算出する際に参照する前記配列に含まれる要素を入力する処理と、
入力した要素を用いて前記出力配列の要素を計算単位となる要素集合ごとに計算し、
前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとにカウントする処理と、
他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとにカウントする処理と、
前記出力配列の要素を算出する際に参照する要素のうち受信する要素の数を前記計算単位となる要素集合ごとにカウントするカウント値に応じて前記出力配列の要素を算出する際に参照する要素を受信する処理と、
前記他の計算装置によって参照される要素のうち算出する要素の数を前記他の計算装置に関して送信単位となる要素集合ごとにカウントするカウンタ値に応じて前記他の計算装置において参照される要素を送信する処理とをコンピュータに実行させる並列計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算装置、並列計算方法および並列計算プログラムに関する。特に、ステンシル計算の遅延を削減する並列計算装置、並列計算方法および並列計算プログラムに関する。
【背景技術】
【０００２】
気象予測などのアプリケーションに用いられる計算方法の一つとして、ステンシル計算という計算方法がある。ステンシル計算では、１以上の行列を参照して新しい１以上の行列を算出し、さらに算出した１以上の行列を参照して新しい１以上の行列を算出するということを繰り返す。ステンシル計算においては、新しい行列の１要素を計算するために、参照する行列の要素を複数用いる。そのため、ステンシル計算の計算量は、１要素を計算するために１要素のみを用いるような通常の計算処理と比較して大きくなる。
【０００３】
例えば、気象予測などのように多くの要素を用いて計算を行うアプリケーションにおいては、ステンシル計算の処理時間を削減できれば予測時間を短縮することができるため、より近い未来を予測することが可能となる。
【０００４】
一般に、ステンシル計算を実行する場合、計算対象となる行列を部分行列に分割し、それぞれの部分行列に含まれる要素の計算を別々に処理する。また、各部分行列の要素を計算する際には、別の部分行列の要素を用いる必要がある。このように、各部分行列自身の要素には含まれないものの、各部分行列の要素の値を計算するために参照しなければならない要素を含む領域は、袖領域と呼ばれる。
【０００５】
ステンシル計算を処理する各計算機には、各計算機が計算を担当する部分行列に加えて袖領域の要素も分配される必要がある。ただし、各計算機においては、各部分行列を計算するために袖領域の要素が必要となるものの、自身では袖領域の要素を計算しない。そのため、各計算機は、部分行列を計算するために用いる袖領域の要素を他の計算機から受信する必要がある。
【０００６】
ステンシル計算を実現する関連技術の一例が非特許文献１に記載されている。非特許文献１の並列計算装置は、計算を行う複数のノードがネットワーク部を通じて接続された構成を持つ。
【０００７】
各ノードは、行列の各要素を計算するのに必要なデータのうち袖領域の要素を他のノードから受信し、自ノードが計算を担当する要素について計算する。また、各ノードは、自ノードで計算した要素のうち、他のノードで行列の各要素を計算する際に袖領域の要素として必要となるデータを他のノードに対して送信する。
【０００８】
このように、非特許文献１によれば、ステンシル計算を行う並列計算装置を実現することができる。しかしながら、非特許文献１の並列計算装置による計算方法には二つの問題点がある。一つ目の問題点は、送信開始のタイミングが遅れるために遅延隠蔽の度合いが小さくなり、処理時間が増大することである。二つ目の問題点は、必要なデータを受信した直後に要素の算出を開始しないため、処理時間の増大することである。
【０００９】
非特許文献１の問題点を解決する技術が特許文献１および２に開示されている。特許文献１および２の並列計算装置は、非特許文献１と同様に、計算を行う複数のノードがネットワーク部を通じて接続された構成を持ち、各ノード間ではトークンと呼ばれる構造体を授受し合う。
【００１０】
特許文献１および２において、各ノードは、データを内包するトークンを受信し、受信したトークンが登録されていたマッチ条件にマッチした場合はデータを受信する。各ノードは、行列の要素の算出に必要なデータを他のノードから全て受け取ると、行列の１要素を算出する。そして、各ノードは、算出結果が他のノードにおいて必要とされる場合、算出された１要素のデータを内包するトークンを作成し、作成したトークンを対象となる他のノードに送信する。
【００１１】
特許文献１および２によれば、非特許文献１の問題点を解決するデータフロー型の並列計算装置を実現することができる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特許２６０２２４１号公報
【特許文献２】特開平１−１０２６４５号公報
【非特許文献】
【００１３】
【非特許文献１】Ｍ．Ｓｎｉｒ、Ｓ．Ｏｔｔｏ、Ｓ．Ｈｕｓｓ−Ｌｅｄｅｒｍａｎ、Ｄ．Ｗａｌｋｅｒ、Ｊ．Ｄｏｎｇｒｒａ、ＭＰＩ：Ｔｈｅ  Ｃｏｍｐｌｅｔｅ  Ｒｅｆｅｒｅｎｃｅ、ＭＩＴ  Ｐｒｅｓｓ、Ｊａｎｕａｒｙ  １、１９９６
【発明の概要】
【発明が解決しようとする課題】
【００１４】
非特許文献１の並列計算装置によれば、ステンシル計算を行う並列計算装置を実現することができる。しかしながら、非特許文献１の並列計算装置では、処理時間が増大するという問題点があった。第１の理由は、出力行列の担当要素集合が全て算出されてから要素集合の送信を開始され、データ通信の遅延隠蔽の度合いが小さいためである。第２の理由は、必要なデータが受信された直後に要素の算出が開始されないためである。
【００１５】
特許文献１および特許文献２の並列計算装置によれば、非特許文献１の問題点を解決するデータフロー型の並列計算装置を実現することができる。しかしながら、特許文献１および２の並列計算装置では、データ通信の遅延が大きいという問題点があった。第１の理由は、袖領域の要素がまとめて送信されずに、一つ一つ送信されるためである。第２の理由は、袖領域の要素の一つ一つにトークン制御用データを付け加えてトークンを作成し、作成したトークンを送信するので、トークン制御用データのオーバーヘッドの分だけデータ通信の遅延が生じるためである。第３の理由は、データ通信時間にトークンマッチの遅延が加わるためである。
【００１６】
本発明はこのような事情に鑑みて提案されたものであり、並列計算の処理時間を短縮することを可能とする並列計算装置を提供することにある。
【課題を解決するための手段】
【００１７】
本発明の並列計算システムは、複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力するとともに、入力配列の要素から出力配列の要素を算出する際に参照する配列に含まれる要素を入力し、入力した要素を用いて出力配列の要素を計算単位となる要素集合ごとに計算する計算手段と、計算手段において出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントする未受信要素カウント手段と、他の計算装置によって参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントする未定義要素カウント手段と、未受信要素カウント手段によるカウントに応じて出力配列の要素を算出する際に参照する要素を受信するとともに、未定義要素カウント手段によるカウントに応じて他の計算装置において参照される要素を送信する送受信手段とを備える複数の計算装置によって構成される。
【００１８】
本発明の並列計算方法においては、複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力し、入力配列の要素から出力配列の要素を算出する際に参照する配列に含まれる要素を入力し、入力した要素を用いて出力配列の要素を計算単位となる要素集合ごとに計算し、出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントし、他の計算装置によって参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントし、出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントするカウント値に応じて出力配列の要素を算出する際に参照する要素を受信し、他の計算装置によって参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントするカウンタ値に応じて他の計算装置において参照される要素を送信する。
【００１９】
本発明の並列計算プログラムは、複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力する処理と、入力配列の要素から出力配列の要素を算出する際に参照する配列に含まれる要素を入力する処理と、入力した要素を用いて出力配列の要素を計算単位となる要素集合ごとに計算し、出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントする処理と、他の計算装置によって参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントする処理と、出力配列の要素を算出する際に参照する要素のうち受信する要素の数を計算単位となる要素集合ごとにカウントするカウント値に応じて出力配列の要素を算出する際に参照する要素を受信する処理と、他の計算装置によって参照される要素のうち算出する要素の数を他の計算装置に関して送信単位となる要素集合ごとにカウントするカウンタ値に応じて他の計算装置において参照される要素を送信する処理とをコンピュータに実行させる。
【発明の効果】
【００２０】
本発明によれば、データ通信の遅延を解消するとともに、計算効率を向上することによって、並列計算の処理時間を短縮することを可能とする並列計算装置を提供することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係る並列計算装置の機能構成を示すブロック図である。
【図２】本発明の実施形態に係る並列計算装置の構成の一例を示す概念図である。
【図３】ステンシル計算によって処理する行列の一例を示す概念図である。
【図４】ステンシル計算によって処理する行列を分割した部分行列を複数の計算機に分散配置した一例を示す概念図である。
【図５】ステンシル計算によって処理する行列を分割した部分行列を袖領域の要素を含めて複数の計算機に分散配置した一例を示す概念図である。
【図６】参照される部分行列から新たなる部分行列を算出することを説明するための概念図である。
【図７】各計算機の間における袖領域の要素の送信状況を説明するための概念図である。
【図８】本発明の実施形態に係るカウンタを説明するための概念図である。
【図９】本発明の実施形態に係る並列計算装置の動作を説明するためのフローチャートである。
【図１０】本発明の実施形態に係る並列計算装置の動作を説明するためのフローチャートである。
【図１１】本発明の実施形態に係る並列計算装置の動作における連想配列Ｒを構築する処理を説明するためのフローチャートである。
【図１２】ステンシル計算で処理する行列を分割した部分行列を袖領域の要素を含めて複数の計算機に分散配置した別の一例を示す概念図である。
【図１３】本発明の実施形態に係る実施例１における行列の算出状況と未受信要素数カウンタの状態とを表した概念図である。
【図１４】本発明の実施形態に係る実施例１における行列の算出状況と未受信要素数カウンタの状態と袖領域要素の送信状況とを表した概念図である。
【図１５】本発明の実施形態に係る実施例２における行列の算出状況を表した概念図である。
【図１６】本発明の実施形態に係る実施例３における行列の算出状況と未受信要素数カウンタの状態とを表した概念図である。
【図１７】本発明の実施形態に係る実施例３における行列の算出状況と未受信要素数カウンタの状態と要素の送信状況と未受信要素数カウンタ操作コマンドの送信状況とを表した概念図である。
【図１８】本発明の実施形態に係る実施例３における行列の算出状況と未受信要素数カウンタの状態と要素の送信状況と未受信要素数カウンタ操作コマンドの送信状況と未受信要素カウント手段の計算開始指示状況とを表した概念図である。
【図１９】本発明の実施形態に係る実施例４における行列Ｂの算出状況と未受信要素数カウンタと未定義要素数カウンタとの状態を表した図である。
【図２０】本発明の実施形態に係る実施例４における行列Ｂの算出状況と未受信要素数カウンタと未定義要素数カウンタとの状態を表した図である。
【図２１】本発明の実施形態に係る実施例４における行列Ｂの算出状況と未受信要素数カウンタと未定義要素数カウンタとの状態を表した図である。
【図２２】非特許文献１に係る並列計算装置の機能構成を示すブロック図である。
【図２３】特許文献１に係る並列計算装置の機能構成を示すブロック図である。
【図２４】特許文献２に係る並列計算装置の機能構成を示すブロック図である。
【図２５】非特許文献１の並列計算装置の動作における問題点を説明するための概念図である。
【図２６】非特許文献１の並列計算装置の動作における問題点を説明するための概念図である。
【発明を実施するための形態】
【００２２】
以下に、本発明を実施するための形態について図面を用いて説明する。ただし、以下に述べる実施形態には、本発明を実施するために技術的に好ましい限定がされているが、発明の範囲を以下に限定するものではない。
【００２３】
（実施形態）
まず、本発明の実施形態に係る並列計算システムについて、図面を参照して詳細に説明する。なお、以下の説明においては、本発明の実施形態に係る並列計算システムとして、複数のノードがネットワーク部を通じて接続された並列計算装置について例示している。本発明の実施形態に係る並列計算システムは、ネットワーク部を構成要素に含めず、複数の計算装置が、任意のアプリケーション・プラットフォーム・インフラストラクチャーを含むクラウドを介して接続された並列計算システムとしても構築することができる。
【００２４】
なお、以下の説明においては、ステンシル計算の対象として主に行列を例に挙げて説明しているものの、本実施形態に係る計算方法は任意のデータ構造を有する配列に対して適用することができる。
【００２５】
（構成）
図１は、本発明の実施形態に係る並列計算装置１０の機能構成を示すブロック図である。なお、図１において、データの流れを実線の矢印で示し、制御の流れを破線の矢印で示す。
【００２６】
並列計算装置１０は、ノード１１と、ネットワーク１７とを備える。並列計算装置１０においては、ノード１１と呼ぶ計算装置がネットワーク１７を経由して接続される。なお、図１においてはノード１１を二つしか描いていないが、図２に示すように、本実施形態に係る並列計算装置１０は任意の数のノード１１を備える。
【００２７】
ステンシル計算においては、第１の配列から第２の配列を算出するために、第１の配列を部分配列（入力配列）に分割し、分割された部分配列（入力配列）を別々に計算処理することによって、第２の配列を構成することになる部分配列（出力配列）を算出する。
【００２８】
これ以降、第１の配列を用いて第２の配列を計算する際に、各ノード１１に入力される第１の配列の部分配列を入力配列と呼び、各ノード１１において入力配列を基に算出される部分配列を出力配列と呼ぶ。なお、配列として行列を扱うときには、入力配列を入力行列と呼び、出力配列を出力行列と呼ぶ。
【００２９】
入力配列から出力配列を算出する際に、各ノード１１は、自身が計算を担当しない要素を他ノード１１から受信する必要がある。このように、各ノード１１の入力配列の要素には含まれないものの、各ノード１１が担当する要素を算出するために必要となる要素を袖領域の要素と呼ぶ。
【００３０】
ノード１１は、配列に対する演算を他のノード１１と分担して処理する計算装置となる。そして、各ノード１１は、ステンシル計算の対象となる配列を分割した部分配列を処理することになる。
【００３１】
ノード１１は、一般的な情報処理装置（コンピュータ）として実現できる。ただし、本実施形態に関する計算を実行できるのであれば、ノード１１はコンピュータに限定されない。
【００３２】
また、ノード１１は、複数のプロセッサコアを持てば並列計算を実行することが可能となる。そのため、ノード１１が複数のプロセッサコアを持てば、一つの部分配列に含まれる複数の計算単位となる要素集合の計算を、複数のプロセッサコアで並列処理する構成とすることができる。また、ノード１１自体が複数の計算を並列処理できるのであれば、並列計算装置１０を単一のノード１１として構成することもできる。
【００３３】
また、一つのプロセッサコアによってある程度の要素集合をまとめて計算を行った方が、キャッシュメモリにおける値の再利用の効果などによって計算時間が短くなる。そのため、計算単位となる要素集合を予め決めておき、計算単位となる要素集合単位でプロセッサコアに並列に計算を開始させることが好ましい。
【００３４】
さらに、要素を送信する際には、複数の要素をまとめた要素集合として送信した方が送信遅延は小さくなる。そのため、本実施形態においては、送信単位となる要素集合（以下、送信すべき要素集合）を決めておき、この送信単位で送信するものとする。送信すべき要素集合に含まれる要素は、他のノード１１において袖領域の要素となるものである。
【００３５】
ここで、１６台のノード１１で並列計算装置１０を構成し、１０２４行１０２４列の２次元配列を入力として、１０２４行１０２４列の２次元配列を出力する例を挙げて、送信すべき要素集合について説明する。ただし、それぞれのノード１１は４個のプロセッサをもつものとする。
【００３６】
まず、１０２４行１０２４列の２次元配列を１６個の２５６行２５６列の部分行列に分割し、分割した２５６行２５６列の部分行列をそれぞれのノード１１に分散させる。そして、２５６行２５６列の部分行列をさらに四つに分解し、１２８行１２８列の部分行列を計算単位として４個のプロセッサで並列計算する。
【００３７】
２５６行２５６列の部分行列を四つに分割する場合、行番号をｉ、列番号をｊとすると、各ノード１１において送信すべき要素集合は、以下のように分割された要素集合を単位としてまとめて送信すればよい。例えば、ｉ＝０およびｉ＝２５５の行のそれぞれに関して、ｊ＝０〜１２７の要素をまとめた要素集合と、ｊ＝１２８〜２５５の要素をまとめた要素集合とを、送信すべき要素集合とすればよい。同様に、ｊ＝０およびｊ＝２５５の列のそれぞれに関して、ｉ＝１〜１２７の要素をまとめた要素集合と、ｉ＝１２８〜２５４の要素をまとめた要素集合とを送信すべき要素集合とすればよい。このように送信すべき要素集合を設定すれば、他のノード１１において袖領域の要素として計算に利用される１２８×８個の要素を、８個の送信すべき要素集合に集約することができる。その結果、送信頻度を１２８分の１に減らすことになるため、送信に起因する遅延を大幅に小さくすることができる。
【００３８】
次に、各ノード１１の内部構成について詳細に説明する。
【００３９】
各ノード１１は、計算手段１２、未定義要素カウント手段１３、送受信手段１４、未受信要素カウント手段１５、記憶手段１６を有する。
【００４０】
（計算手段）
計算手段１２は、複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として入力するとともに、入力配列の要素から出力配列の要素を算出する際に参照する配列に含まれる要素を入力する。そして、計算手段１２は、入力した要素を用いて出力配列の要素を計算単位となる要素集合ごとに計算する。このとき、計算手段１２は、ある決められた要素集合を計算単位として並列に入力配列を参照し、出力配列の要素を算出する。計算手段１２は、算出結果を記憶手段１６に格納する。さらに、計算手段１２は、算出を終えた要素の位置を未定義要素カウント手段１３に送信する。
【００４１】
（未定義要素カウント手段）
未定義要素カウント手段１３は、計算手段１２から送信された要素の位置から、送信単位となる要素集合ごとに未算出の要素の数をカウントする。言い換えると、未定義要素カウント手段１３は、他のノード１１によって参照される要素のうち算出する要素の数を他のノード１１に関して送信単位となる要素集合ごとにカウントする。そして、未定義要素カウント手段１３は、各出力配列に関して、送信単位となる要素集合ごとに未算出の要素の数を記録するカウンタ集合である未定義要素数カウンタの値を、未算出の要素の数に応じて変更する。
【００４２】
未定義要素数カウンタには、各出力配列に関して、送信単位となる要素集合ごとに未算出の要素の数が記録される。各ノード１１には、各出力配列に関して少なくとも一つの未定義要素数カウンタが設けられる。そして、各未定義要素数カウンタには、送信単位となる要素集合ごとに少なくとも一つのカウンタが設けられる。なお、冗長性を持たせるために、各出力配列に関して複数の未定義要素数カウンタが設けられていてもよく、送信単位となる要素集合ごとに複数のカウンタが設けられていてもよい。
【００４３】
また、未定義要素カウント手段１３は、送信すべき要素集合の送信先のノード１１に対して、送信先のノード１１で用いられる袖領域の要素のうち未受信の要素を数えるカウンタの数値を変更するコマンドを送信する。なお、袖領域の要素のうち未受信の要素の数を数えるカウンタ集合を未受信要素数カウンタと呼ぶ。
【００４４】
未受信要素数カウンタは、ある配列（入力配列）から新たなる配列（出力配列）を算出する際に必要となる袖領域の要素のうち、他のノード１１から未だ受信されていない要素の数を、計算単位となる要素集合ごとに記録するカウンタ集合である。すなわち、未受信要素数カウンタは、各入力配列に関して、計算単位となる要素集合のうち袖領域の要素の数をカウントする。未受信要素数カウンタの各カウンタの数値は、他のノード１１からのコマンドによって変更される。
【００４５】
未受信要素数カウンタに含まれる各カウンタは、計算単位となる要素集合に含まれる要素を算出するために参照する要素のうち、他のノードから受信しなければならないが未だ受信されていない要素集合のサイズを持つ。なお、未受信要素数カウンタのサイズは、計算単位となる要素集合に含まれる要素を算出するために必要であるが未受信の要素集合を算出し、その要素集合について計算単位となる要素集合に渡る和を取った和集合のサイズとしてもよい。ただし、集合のサイズとは、集合に含まれる要素の数を意味する。
【００４６】
各ノード１１には、各入力配列に関して少なくとも一つの未受信要素数カウンタが設けられる。そして、各未受信要素数カウンタには、計算単位となる要素集合ごとに少なくとも一つのカウンタが設けられる。なお、冗長性を持たせるために、各入力配列に関して複数の未受信要素数カウンタが設けられていてもよく、計算単位となる要素集合ごとに複数のカウンタが設けられていてもよい。
【００４７】
また、未定義要素カウント手段１３は、出力行列と要素の位置から送信すべき要素集合と送信先のペアの集合を導出するマップを構築する。さらに、未定義要素カウント手段１３は、送信すべき要素集合と送信先のペアを送信先に送信する際に、どの計算単位となる要素集合の未受信要素数カウンタをいくら変更すべきかを示す連想配列を構築する。そして、未定義要素カウント手段１３は、計算手段１２から要素の位置を取得すると、取得した要素の位置をキーとして自らが構築したマップと連想配列を参照し、対応する未受信要素数カウンタの変更値を導出する。
【００４８】
未定義要素カウント手段１３は、ある要素集合の未定義要素数カウンタがゼロになると、カウンタがゼロになった要素集合のアドレスと長さのペアの列と送信先ノードとを送受信手段１４に送信し、対応する送信すべき要素集合を送信する送信指示を出す。
なお、要素集合のアドレスと長さのペアとは、「送信すべき要素が存在するメモリのアドレス」と「送信すべき要素のメモリ上の長さの値と」の組の要素集合のことである。また、未定義要素カウント手段１３は、マップと連想配列を用いて導出したカウンタの変更値を反映させるため、送受信手段１４に対して対応するコマンドを送信する指示を出す。
【００４９】
（送受信手段）
送受信手段１４は、複数の要素を含む配列を構成する部分配列のうち少なくとも一つを入力配列として受信するとともに、入力配列の要素から出力配列の要素を算出する際に参照する配列に含まれる要素を受信する。このとき、送受信手段１４は、未受信要素カウント手段１５によるカウントに応じて出力配列の要素を算出する際に参照する要素を受信する。
【００５０】
送受信手段１４は、未定義要素カウント手段１３からの送信指示を受けて、記憶手段１６から送信対象となる送信すべき要素集合を取り出す。送受信手段１４は、送信対象となる送信すべき要素集合を取り出す際に、必要に応じて記憶手段１６の連続領域に要素集合を再配置する。そして、送受信手段１４は、送信先となるノード１１に送信すべき要素集合を送信する。このとき、送受信手段１４は、未定義要素カウント手段１３によるカウントに応じて他のノード１１によって参照される要素を送信する。
【００５１】
また、送受信手段１４は、送信先のノード１１に対して、送信先のノード１１において出力行列の算出に必要でありながら他のノード１１から受信する必要がある要素（袖領域の要素）のうち、未受信の要素を数えるカウンタの数値を変更するコマンドを送信する。なお、袖領域の要素のうち未受信の要素の数を数えるカウンタ集合を未受信要素数カウンタと呼ぶ。
【００５２】
（未受信要素カウント手段）
未受信要素カウント手段１５は、未受信要素数カウンタを参照し、入力行列から出力行列を算出する際に、袖領域の要素のうち未受信の要素の数を集計する。言い換えると、未受信要素カウント手段１５は、計算手段１２においてｚの要素を算出する際に参照する要素のうち受信すべき要素（受信する要素）の数を計算単位となる要素集合ごとにカウントする。また、未受信要素カウント手段１５は、各入力行列に関して、計算単位となる要素集合ごとの未受信要素数カウンタを初期化する。
【００５３】
未受信要素カウント手段１５は、未受信要素数カウンタがゼロになり、かつ一つ前の入力配列に対する処理のうち参照すべき要素の算出が終了していた場合、該当する計算単位となる要素集合について、要素の算出開始を計算手段１２に指示する。すなわち、未受信要素カウント手段１５は、各出力配列の算出において、計算単位となる要素集合の要素のうち、自ノード１１が計算を担当する要素と袖領域の要素とが全て揃った段階で、計算手段１２に出力配列を計算するように指示する。
【００５４】
（記憶手段）
記憶手段１６は、計算手段１２によって算出された出力配列の要素を格納する。また、記憶手段１６は、未定義要素数カウンタおよび未受信要素数カウンタを格納する。
【００５５】
（ネットワーク）
ネットワーク１７は、複数のノード１１間において、データや操作コマンドを伝達する機能を有する。
【００５６】
例えば、ネットワーク１７が第１のノードと第２のノードという二つのノード１１で構成されている場合、ネットワーク１７は、第１のノードの記憶手段１６のデータを第２のノードの記憶手段１６に伝達する。また、ネットワーク１７は、第１のノード１１からの操作コマンドを第２のノードの記憶手段１６に伝達する。
【００５７】
ネットワーク１７は、例えば、イントラネットやインターネットとして実現することができる。また、並列計算装置１０を単一のコンピュータで構築する場合は、ネットワーク１７をコンピュータ内部のバスとして構成すればよい。
【００５８】
本実施形態に係る並列計算装置では、プロセッサコアを介さずに、異なるノード１１間の通信インターフェース同士がデータや操作コマンドを直接やり取りする構成とすることが好ましい。例えば、ＩｎｆｉｎｉＢａｎｄネットワークによれば、プロセッサを介さずに異なるノード１１間でデータや操作コマンドの授受が可能となる。また、プロセッサコアを介さない構成にすることによって、異なるノード１１間でデータを送受信する際に、記憶手段１６同士でデータを伝達することが可能となる。
【００５９】
以上が、本発明の実施形態に係る並列計算装置１０の構成に関する説明である。なお、本実施形態に係る並列計算装置１０を構成するノード１１の内部構成要素の機能・動作については、動作の説明においてより詳細に説明を加える。
【００６０】
（ステンシル計算）
ここで、一般的な並列計算装置がステンシル計算を処理する例について、図３〜図７を用いて説明する。なお、図３〜図７に示した図は、本発明の実施形態に関する説明においても利用する。また、これ以降は、配列として行列を例に挙げて説明する。
【００６１】
図３には、ステンシル計算で扱う行列の一例として６行６列の行列を示す。なお、図３には、行列を構成する各要素について、列番号と行番号とを併記して要素の位置を示している。
【００６２】
ここで、以下の説明で用いる表記法について明確にする。まず、ａとｂという値の組については、＜ａ，ｂ＞という表記法を用いると定義する（ａ、ｂは任意の整数）。
【００６３】
行列の要素の位置は、＜行番号，列番号＞と表記する。行列の要素は、行列名［行番号］［列番号］と表記する。例えば、行列Ａにおいて、行番号がｉであり、列番号がｊである行列の要素について、要素の位置は＜ｉ，ｊ＞と表され、要素はＡ［ｉ］［ｊ］と表される。さらに、値Ｘと値Ｙのペアは＜Ｘ，Ｙ＞で表し、値Ｘと値Ｙからなる集合を｛Ｘ，Ｙ｝と表す。
【００６４】
ステンシル計算では、参照される行列（入力行列）から新しい行列（以下、出力行列）を算出するプロセスが繰り返される。例えば、ある行列Ａから新しい行列Ｂを計算し、算出された行列Ｂから新しい行列Ｃを計算し、算出された行列Ｃから新しい行列Ｄを計算する・・・というようなプロセスが繰り返される。
【００６５】
ステンシル計算によって出力行列を算出する際には、出力行列を構成する各要素を一つ一つ算出する。例えば、出力行列の要素の位置＜ａ，ｂ＞の要素は、入力行列の要素の位置＜ａ，ｂ＞の要素と、入力行列の要素の位置＜ａ，ｂ＞の周辺に位置する複数の要素とを用いて算出される。
【００６６】
例えば、行列Ａを用いて行列ＢのＢ［ｉ］［ｊ］の値を５要素で算出する際には、Ａ［ｉ−１］［ｊ］、Ａ［ｉ＋１］［ｊ］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ−１］およびＡ［ｉ］［ｊ＋１］の５要素を用いる（ｉ、ｊは整数）。
【００６７】
図４は、図３に示した６行６列の行列を部分行列に分割し、分割された部分行列の要素集合を９台の計算機Ｍ（０，０）〜Ｍ（２，２）に分散配置した例である。
【００６８】
図４のように行列を分散すると、各ノード１１で各要素を計算する際に、他の計算機で算出される袖領域の要素が必要となる。
【００６９】
そのため、図５に示したように、各計算機が担当する要素に加えて、各計算機が担当する要素を計算するために必要となる袖領域の要素を、各計算機に重複させて分配することになる。なお、図５において、袖領域の要素の位置は、枠内に斜線網掛けをして明示している。
【００７０】
例えば、図５において、Ｍ（１，１）では、Ｂ［２］［２］を算出するために必要となるＡ［１］［２］およびＡ［２］［１］が袖領域の要素の一つとなる。
【００７１】
また、行列の端部に位置する要素には、隣接した要素が存在しない箇所がある。そのため、一端部の要素の位置にある要素に対しては、他端部の要素の位置にある要素を折り返して隣接させ、添え字空間で隣り合うものとする。
【００７２】
例えば、Ａ［０］［ｊ］の添え字空間で＜−１，０＞の隣（上隣）はＡ［５］［ｊ］とし、Ａ［ｉ］［０］の添え字空間で＜０，−１＞の隣（左隣）はＡ［ｉ］［５］とする。同様に、例えば、Ａ［ｉ］［５］の添え字空間で＜＋１，０＞の隣（下隣）はＡ［０］［ｊ］とし、Ａ［５］［ｊ］の添え字空間で＜０，＋１＞の隣（右隣）はＡ［ｉ］［０］とする。
【００７３】
図６に示すように、各計算機は、枠内に斜線網掛けをしていない要素の位置（太字）について個別にステンシル計算を実行する。このように、９台の計算機によって行列Ａから新しい行列Ｂが算出されると、９台の計算機は行列Ｂの値の一部を分散して所有する状態になる。
【００７４】
ところで、続けて行列Ｂから行列Ｃを算出しようとする際には、各計算機内において計算に必要となる袖領域の要素が足りなくなる。
【００７５】
例えば、Ｍ（１，１）は、図６において、枠内に斜線網掛けをいない要素の位置（太字）についてのみを算出し、枠内に斜線網掛けをした要素の位置については行列Ｂの要素として計算していない。そのため、行列Ｂから行列Ｃを算出しようとする際には、行列Ｂから行列Ｃを計算するために必要となる袖領域の要素を、他の計算機から通信によって取得することになる。すなわち、行列Ｂから行列Ｃを算出するためには、各計算機における袖領域の要素を他の計算機から受信し、各計算機の袖領域の要素を更新する必要がある。
【００７６】
例えば、図７に示すように、Ｍ（１，１）は、他の計算機において袖領域の要素となるＢ［２］［２］、Ｂ［２］［３］、Ｂ［３］［２］およびＢ［３］［３］の値を、これらの要素を必要とする計算機に送信する。すなわち、Ｍ（１，１）は、Ｂ［２］［２］とＢ［２］［３］の値をＭ（０，１）に、Ｂ［２］［２］とＢ［３］［２］の値をＭ（１，０）に、［２］［３］とＢ［３］［３］の値をＭ（１，２）に、Ｂ［３］［２］とＢ［３］［３］の値をＭ（２，１）に送信する。図７においては、Ｍ（１，１）から各計算機に袖領域の要素を送信する様子を実線の矢印で示している。
【００７７】
また、Ｍ（１，１）は、自身の袖領域の要素となるＢ［１］「２］、Ｂ［１］［３］、Ｂ［２］「１］、Ｂ［３］［１］、Ｂ［２］「４］、Ｂ［３］［４］、Ｂ［４］「２］およびＢ［４］［３］の値を、各計算機から受信する。すなわち、Ｍ（１，１）は、Ｂ［１］「２］とＢ［１］［３］をＭ（０，１）から、Ｂ［２］「１］とＢ［３］［１］をＭ（１，０）から、Ｂ［２］「４］とＢ［３］［４］をＭ（１，２）から、Ｂ［４］「２］とＢ［４］［３］をＭ（２，１）から受信する。図７においては、Ｍ（１，１）が各計算機から袖領域の要素を受信する様子を破線の矢印で示している。
【００７８】
Ｍ（１，１）以外の計算機も、Ｍ（１，１）と同様に、他の計算機との間で袖領域の要素を送受信し合う。各計算機間における袖領域の要素を送受信した後、各計算機は、行列Ｃのうち担当する部分行列の要素を計算する。そして、各計算機は、袖領域の要素を各計算機間で送受信し合い、新たなる行列の計算を繰り返す。
【００７９】
一般的な並列計算装置の各計算機は、出力行列の計算に必要となる袖領域の要素が全て揃った段階で出力行列の計算を開始する。
【００８０】
以上が、一般的な並列計算装置によってステンシル計算を処理する例についての説明である。
【００８１】
（カウンタ）
ここで、本実施形態において用いるカウンタについて、図８の例を参照しながら説明する。図８は、図５のＭ（１，１）に関するカウンタを示す概念図である。なお、実際には、未定義要素数カウンタおよび未受信要素数カウンタは、記憶手段１６の特定の領域に格納されている。
【００８２】
図８においては、行列Ａが入力され、これから行列Ｂの計算が始まるという段階である。そのため、図８の状態においては、未だ行列Ｂの各要素の計算は実行されていない。
【００８３】
Ｍ（１，１）は、行列Ａ（入力行列）から行列Ｂ（出力行列）を算出する際に、＜２，２＞、＜２，３＞、＜３，２＞および＜３，３＞の要素の計算を行う。Ｍ（１，１）は、＜１，２＞、＜１，３＞、＜２，１＞、＜２，４＞、＜３，１＞、＜３，４＞、＜４，２＞および＜４，３＞の要素を袖領域の要素として必要とする。
【００８４】
ここでは、Ｍ（１，１）において、｛＜２，２＞，＜２，３＞，＜３，２＞，＜３，３＞｝という要素集合を計算単位とする。また、Ｍ（１，１）において、｛＜２，２＞｝、｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝という四つの要素集合のそれぞれを送信単位とする。
【００８５】
未受信要素数カウンタは、行列Ａ（入力行列）に関して、他のノード１１から受信すべき要素の数を、計算単位となる要素集合ごとに数える複数のカウンタを含むカウンタ集合である。なお、受信すべき要素とは、行列Ｂ（出力行列）の要素を算出する際に必要となる要素のうち、袖領域の要素として必要な要素である。
【００８６】
図８において、行列Ｂ（出力行列）の＜２，２＞の要素を計算する場合、＜１，２＞および＜２，１＞という２つの位置の要素を袖領域の要素として必要とする。そのため、未受信要素数カウンタ（部分行列の要素の上）には、それぞれの要素の位置に対応するカウンタが設けられている。同様に、他の要素の位置についてもカウンタが設けられている。
【００８７】
図８の例では、未だ行列Ｂの要素の計算に必要となる要素が受信されていないため、全てのカウンタの値は２である。各ノード１１は、他のノード１１から受信すべき要素を受信すると、他のノード１１から対応するカウンタを減算するコマンドを受信することになる。このとき、各ノード１１においては、未受信要素数カウンタのうち対応するカウンタが減算されることになる。
【００８８】
未定義要素数カウンタは、行列Ａ（入力行列）の要素から算出される要素を含む行列Ｂ（出力行列）に関して、送信すべき要素集合のうち未だ算出されていない要素の数を、送信先ごとに数える複数のカウンタを含むカウンタ集合である。なお、送信すべき要素集合とは、他のノード１１において袖領域の要素として必要となる要素を送信単位ごとにまとめた要素集合である。
【００８９】
図８において、｛Ｂ［２］［２］｝が送信すべき要素集合である場合、Ｍ（０，１）とＭ（１，０）の２つのノード１１が送信先となる。そのため、未定義要素数カウンタ（部分行列の要素の下）には、それぞれの送信先に対応するカウンタが設けられている。同様に、他の送信すべき要素集合についても、送信先に対応するカウンタが設けられている。
【００９０】
図８の例では、未だ行列Ｂの要素の計算は開始されていないため、全てのカウンタの値は１である。行列Ｂの要素のうちのいずれかが算出されると、対応するカウンタは、未定義要素カウント手段１３によって減算される。
【００９１】
ただし、図８の未受信要素数カウンタおよび未定義要素数カウンタは一例であり、本実施形態に関するカウンタを図８の例のように限定するわけではない。
【００９２】
（動作）
次に、図９および図１０のフローチャートを参照して、本実施形態に係る並列計算装置１０の動作について説明する。なお、図９と図１０は、一つのフローチャートを分割したものである。図９のフローをたどってＡに至った場合は図１０のＡに進み、図１０のフローをたどってＢに至った場合は図９のＢに戻るものとする。
【００９３】
（マップＳの構築）
まず、図９において、未定義要素カウント手段１３は、出力行列と要素の位置出力行列と要素の位置から送信すべき要素集合と送信先のペアの集合を導出するマップＳを構築する（ステップＳ１１）。
【００９４】
ここで、マップとは、あるキーＫで引いた際に、値Ｖを返す関数のことである。これ以降、マップにおけるキーＫと値Ｖの関係は、Ｋ⇒Ｖと記載する。なお、マップＳは、キーＫと値Ｖへのポインタを木構造で格納する形で実装してもよい。
【００９５】
ここで、図３のような６行６列の２次元配列を入力して、６行６列の２次元配列を出力する例について説明する。ここでは、９台のノード１１で並列計算装置１０を構成し、６行６列の２次元配列を９分割した２行２列の部分行列をそれぞれのノード１１に担当させる。そのため、図４に示すように、各ノード１１は、９個に分割された部分行列のいずれかの計算を担当することになる。これ以降、各部分行列の計算を担当するノード１１を、図４に示すようにＭ（０，０）、Ｍ（０，１）、・・・、Ｍ（２，２）というように記載する。
【００９６】
各ノード１１は、分割された１行１列の部分行列を計算単位とし、計算を担当する１行１列の部分行列を送信単位とする。なお、Ｃ［ｉ］［ｊ］を算出するためには、Ｂ［ｉ−１］［ｊ］、Ｂ［ｉ＋１］［ｊ］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ］［ｊ−１］、Ｂ［ｉ］［ｊ＋１］の５要素を用いるものとする。
【００９７】
例えば、行列Ｂから行列Ｃを算出する際に、Ｍ（１，１）が計算を担当する行列の要素の位置＜２，２＞は、Ｍ（０，１）およびＭ（１，０）にとって袖領域に相当する。そのため、Ｍ（１，１）は、要素の位置＜２，２＞を袖領域とするＭ（０，１）およびＭ（１，０）に対して、Ｂ［２，２］を送信する必要がある。ここでは、１行１列の部分行列が送信単位とする。そのため、ノードＭ（１，１）は、送信すべき要素集合と送信先のペアの集合として｛＜｛｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞｝を送信する。
【００９８】
なお、要素の位置は座標列で表してもよい。また、送信すべき要素集合は、アドレスと長さのペアの集合で表してもよい。
【００９９】
ここで、マップＳは、以下のＢ［２］［２］⇒｛＜｛｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛｛Ｂ［２］［２］｝，Ｍ（１，０）＞｝というエントリを含む。
【０１００】
（連想配列Ｒの構築）
次に、未定義要素カウント手段１３は、送信すべき要素集合と送信先のペアを送信先に送信する際に、どの計算単位となる要素集合の未受信要素数カウンタをいくら減ずるべきかを示す連想配列Ｒを構築する（ステップＳ１２）。
【０１０１】
ここで、連想配列とは、キーＫに対して値Ｖを返す関数である。連想配列の内容についてはＫ→Ｖと表す。例えば、ＡをキーとするとＢが返され、Ｂをキーとして渡すとＣが返ってくるという連想配列の内容は、Ａ→Ｂ→Ｃというように表す。
【０１０２】
図７に示した通り、本実施形態においては、１要素が計算単位であるため、Ｃ［１］［２］の算出にはＢ［２］［２］が必要となり、Ｃ［２］［１］の算出にはＢ［２］［２］が必要となる。そのため、｛Ｂ［２］［２］｝については、｛Ｂ［２］［２］｝，Ｍ（０，１）→｛Ｃ［１］［２］｝→１，｛Ｂ［２］［２］｝，Ｍ（１，０）→｛Ｃ［２］［１］｝→１という連想配列のエントリが連想配列Ｒに含まれる。すなわち、連想配列Ｒは、「送信すべき要素集合と送信先のペア」をキーとして「計算単位となる要素集合」を返し、「計算単位となる要素集合」をキーとして「未受信要素数カウンタをいくら減ずるべきかを示す値（整数）」を返す連想配列である。
【０１０３】
ここで、図９のフローチャートにおける連想配列Ｒの構築処理（ステップＳ１２）について、図１１のフローチャートを用いて詳しく説明する。
【０１０４】
図１１において、まず、送信すべき要素集合と送信先のペアをキーとして計算単位となる要素集合を返し、計算単位となる要素集合をキーとして整数を返す連想配列Ｒを初期化し、送信すべき要素集合と送信先のペアの集合をＸとする（ステップＳ２０１）。
【０１０５】
先述した図７の例のノードＭ（１，１）について、送信すべき要素集合と送信先のペアのＸは、以下のようになる。
Ｘ＝｛＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞，＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞，＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞，＜｛Ｂ［３］［２］｝，Ｍ（２，１）＞，＜｛Ｂ［３］［３］｝，Ｍ（１，２）＞，＜｛Ｂ［３］［３］｝，Ｍ（２，１）＞｝
次に、Ｘが空でなければ（Ｎｏ）ステップＳ２０３に進み、Ｘが空であれば（Ｙｅｓ）ステップＳ２０８に進む（ステップＳ２０２）。
【０１０６】
Ｘが空でない場合（ステップＳ２０２でＮｏ）、Ｘから送信すべき要素集合と送信先のペアを一つ取り出してＹとし、ＹのコピーをＹ’とする（ステップＳ２０３）。
【０１０７】
例えば、上記の例においては、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞を取り出してＹとすると、ＹのコピーがＹ’となる。
【０１０８】
Ｘが空の場合（ステップＳ２０２でＹｅｓ）、連想配列Ｒを出力し、図１１のアルゴリズムを終了する（ステップＳ２０８）。
【０１０９】
次に、Ｙ’の要素集合が空であるか否かを判定し、Ｙ’の要素集合が空でなければ（Ｎｏ）ステップＳ２０５に進み、Ｙ’の要素集合が空であれば（Ｙｅｓ）ステップＳ２０２に戻る（ステップＳ２０４）。
【０１１０】
Ｙ’の要素集合が空でない場合（ステップＳ２０４でＮｏの場合）、Ｙ’の要素集合の集合から要素を一つ取り出し、Ｙの送信先で取り出した要素を参照する計算が属する計算単位となる要素集合の集合をＺとする（ステップＳ２０５）。
【０１１１】
例えば、上記の例において、Ｙ’の要素集合の集合からＢ［２］［２］を取り出した場合、取り出されたＢ［２，２］を参照するのは、Ｍ（０，１）においてはＣ［１］［２］を算出する演算のみである。このとき、計算単位は１要素なので、Ｚは｛｛Ｃ［１］［２］｝｝となる。
【０１１２】
次に、Ｚが空でなければ（Ｎｏ）ステップＳ２０７に進み、Ｚが空であれば（Ｙｅｓ）ステップＳ２０４に戻る（ステップＳ２０６）。
【０１１３】
Ｚが空でない場合（ステップＳ２０６でＮｏ）、Ｚから計算単位となる要素集合Ｗを一つ取り出す。そして、連想配列ＲにおいてＹをキーとして返ってきた連想配列について、要素集合Ｗをキーとして返ってきた値に１を加算し、ステップＳ２０６に戻る（ステップＳ２０７）。ただし、空の連想配列に対し、Ａをキーとして返ってきた値に１を加算した場合、その連想配列にＡ→１のエントリを加える効果があるとする。
【０１１４】
例えば、上記の例では、要素集合Ｗとして｛Ｃ［１］［２］｝が取り出せる。そして、Ｙとして＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞というキーを連想配列Ｒに与えた際に返ってくる連想配列は、空の連想配列となる。この空の連想配列にＷ→１のエントリを追加する。結果として、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］｝→１というエントリが連想配列Ｒに含まれることになる。
【０１１５】
上記の例では、｛Ｂ［２］［２］｝をＭ（０，１）へ送信した場合、Ｍ（０，１）は、｛Ｃ［１］［２］｝の計算において参照すべき要素集合の一つを受信したことになる。そのため、Ｍ（０，１）の｛Ｃ［１］［２］｝の未受信要素カウンタを１減ずる必要がある。また、｛Ｂ［２］［２］｝をＭ（１，０）へ送信した場合、Ｍ（１，０）の｛Ｃ［２］［１］｝のカウンタを１減ずる必要がある。同様に、｛Ｂ［２］［３］｝をＭ（０，１）へ送信した場合はＭ（０，１）の｛Ｃ［１］［３］｝のカウンタを１減ずる必要があり、｛Ｂ［２］［３］｝をＭ（１，２）へ送信した場合はＭ（１，２）の｛Ｃ［２］［４］｝のカウンタを１減ずる必要がある。同様に、｛Ｂ［３］［２］｝および｛Ｂ［３］［３］｝についても、送信すべき要素集合を送信先に送信する度に、対応するカウンタを１減ずる必要がある。このような「送信すべき要素集合が送信先に送信されると、対応するカウンタを１減ずる」という意味の連想配列が連想配列Ｒとして構築されることになる。
【０１１６】
ここで、図９のフローチャートに戻って説明する。
【０１１７】
図９において、未定義要素カウント手段１３は、要素集合送信先のＲＤＭＡ情報（Ｒｅｍｏｔｅ  Ｄｉｒｅｃｔ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ）、未受信要素カウンタ操作情報を他のノード１１の未定義要素カウント手段１３と交換する（ステップＳ１３）。
【０１１８】
要素集合を他のノード１１に送信する際には、ネットワークアドレスや、送信先アドレスなどの他ノード１１のアドレス情報が必要である。例えば、ＩｎｆｉｎｉＢａｎｄネットワークを送信部として用いる場合、グローバルＩＤ（ＧＩＤ）、ローカルＩＤ（ＬＩＤ）、ＱＰ番号、仮想アドレス、キー、といった値が必要となる（ＱＰ：Ｑｕｅｕｅ  Ｐａｉｒ、ＩＤ：Ｉｄｅｎｔｉｆｉｅｒ）。また、他のノード１１の未受信要素カウンタ１３を操作する際にも同様の情報が必要となる。そのため、未定義要素カウント手段１３は、ネットワークアドレスや送信先アドレスなどのアドレス情報とともに、ＧＩＤやＬＩＤ、ＱＰ番号、仮想アドレス、キー、といった他ノード１１の情報も、あらかじめ他のノード１１と交換しておく。
【０１１９】
次に、未定義要素カウント手段１３は、各出力行列に関する送信すべき要素集合の送信先ごとの未定義要素数カウンタを、送信すべき要素集合のサイズに初期化する（ステップＳ１４）。なお、送信すべき要素集合のサイズとは、送信すべき要素集合に含まれる要素の数を意味する。
【０１２０】
例えば、図７の例では、行列Ｂから行列Ｃを計算する場合、ノードＭ（１，１）の未定義要素カウント手段１３は、送信すべき要素集合である｛Ｂ［２］［２］｝の未定義要素数カウンタを１に初期化する。同様に、ノードＭ（１，１）の未定義要素カウント手段１３は、送信すべき｛Ｂ［２］［３］｝、｛Ｂ［３］［２］｝および｛Ｂ［３］［３］｝の未定義要素数カウンタを１に初期化する。
【０１２１】
次に、未受信要素カウント手段１５は、ある要素の算出に必要な要素のうち、袖領域にあるために他のノード１１から受信すべき要素の数を集計し、各入力行列に関して計算単位となる要素集合ごとの未受信要素数カウンタを初期化する（ステップＳ１５）。
なお、一連の行列計算において最初に入力される入力行列では、既に袖領域の要素も受信されている状態にあるため、未受信要素数カウンタは全てゼロに初期化される。
【０１２２】
図７の例では、行列Ｂに関して、計算単位となる要素集合が｛＜２，２＞｝であった場合、すなわち｛Ｃ［２］［２］｝を算出単位とする場合、Ｍ（１，１）においてはＢ［１］［２］とＢ［２］［１］が参照される。そのため、Ｍ（１，１）において、行列Ｂに関する計算単位となる要素集合｛＜２，２＞｝に含まれる要素のうち、未受信の要素をカウントするカウンタは２に初期化される。
【０１２３】
また、行列Ｂに関して、計算単位が｛＜２，２＞，＜２，３＞｝であった場合、すなわち｛Ｃ［２］［２］，Ｃ［２］［３］｝を算出単位とする場合、Ｍ（１，１）においてはＢ［１］［２］、Ｂ［２］［１］、Ｂ［１］［３］およびＢ［２］［４］が参照される。そのため、Ｍ（１，１）において、行列Ｂに関して計算単位となる要素集合｛＜２，２＞，＜２，３＞｝に含まれる要素のうち未受信の要素をカウントするカウンタは４に初期化される。最初の入力行列である行列Ａの袖領域の値は既に用意されているので、行列Ａに関するカウンタはゼロに初期化する。
【０１２４】
例えば、図１２の例にあるように、６行６列の２次元配列を入力として、６行６列の２次元配列を出力するものとする。そして、図１２のように分割した２行２列の部分行列のそれぞれを９台のノード１１に担当させ、１行１列の部分行列を送信単位とする。なお、図１２の例では、Ｃ［ｉ］［ｊ］を算出するためには、９要素を用いるものとする。すなわち、Ｂ［ｉ−１］［ｊ−１］、Ｂ［ｉ−１］［ｊ］、Ｂ［ｉ−１］［ｊ＋１］、Ｂ［ｉ］［ｊ−１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ］［ｊ＋１］、Ｂ［ｉ＋１］［ｊ−１］、Ｂ［ｉ＋１］［ｊ］、Ｂ［ｉ＋１］［ｊ＋１］の９要素を用いる。
【０１２５】
図１２の例では、行列Ｂに関して、計算単位となる要素集合が｛＜２，２＞，＜２，３＞｝であった場合、｛Ｃ［２］［２］，Ｃ［２］［３］｝が算出単位とする。この場合、Ｂ［１］［１］、Ｂ［１］［２］、Ｂ［１］［３］、Ｂ［１］［４］、Ｂ［２］［１］、Ｂ［２］［４］、Ｂ［３］［１］およびＢ［３，４］が袖領域の要素として参照される。そのため、未受信要素数カウンタは６に初期化される。
【０１２６】
次に、未受信要素カウント手段１５は、各入力行列における計算単位となる要素集合ごとの未受信要素のカウンタを調べる（ステップＳ１６）。
【０１２７】
ここで、未受信要素カウント手段１５は、算出対象となる出力行列に関して計算単位となる全ての要素が揃ったか否かを判定し、揃った場合（Ｙｅｓ）は計算手段１２に計算を指示し、揃っていない場合（Ｎｏ）はステップＳ１６に戻る（ステップＳ１７）。
【０１２８】
未受信要素カウント手段１５は、算出対象となる出力行列に関して計算単位となる要素が全て揃った場合（ステップＳ１７でＹｅｓ）、対象入力行列を用いた対象要素集合の計算開始を計算手段１２に指令する（ステップＳ１８）。
【０１２９】
なお、計算単位となる要素が全て揃った場合とは、対象となる未受信要素数カウンタの値がゼロであるとともに、対象要素集合の対象入力行列を用いた算出が参照すべき要素を生成する同一ノードでの処理が終了している場合である。
【０１３０】
例えば、行列Ａを入力として行列Ｂを算出し、行列Ｂを入力として行列Ｃを算出するものとする。このとき、行列Ｃに関して、ある要素集合のカウンタがゼロの場合は、入力行列となる行列Ｂの袖領域の値が全て揃っていることを意味する。また、「対象要素集合の対象入力行列を用いた算出が参照すべき要素を生成する同一ノードでの処理が終了している場合」とは、行列Ｃを算出するために必要となる行列Ｂの要素のうち、自ノード１１で算出する要素の算出処理が終了していることを意味する。
【０１３１】
図７の例では、計算単位となる｛＜２，２＞｝について行列Ｃの算出を開始するには、袖領域のＢ［２］［１］およびＢ［１］［２］、行列Ａを入力として自ノード１１が算出するＢ［２］［２］、Ｂ［２｝［３］およびＢ［３］［２］が必要である。
【０１３２】
未受信要素カウント手段１５は、袖領域のＢ［２］［１］およびＢ［１］［２］を未受信要素カウンタのサイズで検知する。そして、未受信要素カウント手段１５は、Ｂ［２］［２］、Ｂ［２｝［３］およびＢ［３］［２］の値が算出されているか否かを、対象要素集合の対象入力行列を用いた算出が参照すべき要素を生成する同一ノードでの処理が終了しているか否かで検知する。
【０１３３】
対象要素集合の対象入力行列を用いた算出が参照すべき要素を生成する同一ノードでの処理が終了していることの検知は、各出力行列に関して計算単位となる要素集合ごとの処理完了のフラグを設けて、このフラグを参照することによって実現される。また、複数のコアに並列に計算するように指令するように構成してもよい。なお、自ノード１１が算出した要素の値を検知するために、自ノード１１が算出する要素のうち未算出のものを数えるカウンタを設け、そのカウンタの値によって処理の状況を検知するように構成してもよい。
【０１３４】
次に、図１０において、計算手段１２は、出力行列の要素を算出完了したら、算出が完了した出力行列および要素の位置を未定義要素カウント手段１３に送る（ステップＳ１９）。なお、要素の位置は、行列名と行列内の座標で表してもよい。
【０１３５】
次に、未定義要素カウント手段１３は、計算手段１２から取得した要素の位置を基に、マップＳを用いて送信すべき要素集合と送信先のペアの集合を導出し、対象出力行列の対象要素集合の対象送信先の未定義要素数カウンタを１減らす（ステップＳ２０）。
【０１３６】
すなわち、未定義要素カウント手段１３は、送信すべき要素集合に含まれる要素の算出が一つ終了するごとに、各出力行列に関する送信すべき要素集合の送信先ごとの未定義要素数のカウンタを減算していく。
【０１３７】
次に、未定義要素カウント手段１３は、未定義要素数のカウンタがゼロになった送信単位となる要素集合があるか否かを判定し、ＮｏであればステップＳ２５に進み、ＹｅｓであればステップＳ２２に進む（ステップＳ２１）。
【０１３８】
未定義要素数カウンタがゼロになったものがある場合（ステップＳ２１でＹｅｓ）、未定義要素カウント手段１３は、送受信手段１４に対して、該当する要素集合を送信先に送信する指示を出す（ステップＳ２２）。未定義要素カウント手段１３による送受信手段１４への送信指示は、未定義要素数カウンタがゼロになった全ての送信先に対して出される。なお、送信する要素集合は、アドレスと長さのペアの集合として指示してもよい。
【０１３９】
送受信手段１４は、未定義要素カウント手段１３の指示を受け、必要に応じて要素集合を一度記憶手段１６の連続領域に再配置してから、対象要素集合を対象送信先に送信し始める（ステップＳ２３）。送受信手段１４は、指示を受けた分だけステップＳ２３の処理を繰り返す。
【０１４０】
次に、送受信手段１４は、与えられた送信すべき要素集合と送信先をキーとして連想配列Ｒを引き、どの未受信要素数のカウンタをいくら減算すればよいかを決定する。そして、送受信手段１４は、決定した未受信要素数のカウンタの減算値に応じて、減算を行う減算コマンドを送信先となるノード１１に送信する（ステップＳ２４）。送受信手段１４は、指示を受けた分だけステップＳ２４の処理を繰り返す。
【０１４１】
図７の例において、送信すべき要素集合が｛Ｂ［２］［３］、Ｂ［３］［３］｝であった場合、それぞれの要素はメモリ上において連続ではない。その結果、送信を２回に分けると送信遅延が増大してしまう。そのため、算出が完了した一方の要素を一度メモリの連続領域にコピーし、送信すべき要素集合が揃った段階で１回の送信とすることによって、送信遅延を解決する。例えば、並列計算装置１０が送信と計算を並行して実行できる構成になっていれば、より送信遅延の問題を解決できる。
【０１４２】
また、図７の例において、送信すべき要素集合が｛Ｂ［２］［２］｝であったとする。このとき、送受信手段１４は、｛Ｂ［２］［２］｝をＭ（０，１）に送った場合、Ｍ（０，１）の｛Ｃ［１］［２］｝のカウンタを１減算するコマンドをＭ（０，１）に送信する。同様に、送受信手段１４は、｛Ｂ［２］［２］｝をＭ（１，０）に送った場合、Ｍ（１，０）の｛Ｃ［２］［１］｝のカウンタを１減算するコマンドをＭ（１，０）に送信する。
【０１４３】
なお、並列計算装置１０は、送受信手段１４によるコマンド送信および送信先でのコマンド実行と、計算を並行して実行できる構成になっていてもよい。また、要素集合および減算コマンドの送信は、要素集合を送信後に減算コマンドを送信するという順番で実行されるようにすることが好ましい。
【０１４４】
次に、並列計算装置１０は、行列の算出を終了する条件が成立したか否かを判定し、Ｙｅｓの場合はステンシル計算を終了し、Ｎｏの場合はステップＳ１６（図９）に戻る（ステップＳ２５）。なお、行列の算出を終了する条件とは、収束条件が満たされたかどうかなど、アプリケーションごとに固有の条件である。また、行列の算出を終了する条件が成立したか否かを判定する主体は、例えば図示しない制御手段などに負わせてもよいし、並列計算装置１０を外部から制御する制御装置として構成してもよい。
【０１４５】
以上が、本発明の実施形態に係る並列計算装置の動作に関する説明である。
【０１４６】
本実施形態によれば、入力行列から出力行列を計算する際に、送信単位となる要素集合の送信開始タイミングを、その要素集合が算出された直後まで、かつ送信と並行して他の計算単位となる要素集合の算出を実行できるタイミングまで早めることができる。その結果、袖領域通信の遅延隠蔽を増大することによって、処理時間を短縮することができるという効果が得られる。
【０１４７】
また、本実施形態によれば、入力行列から出力行列を計算する際に、計算単位となる要素集合の要素の算出を開始するタイミングを、算出に必要な要素集合の全ての要素が受信されたタイミングにまで早めることができる。その結果、計算にかかる処理時間を短縮することができる。
【０１４８】
以上のように、本実施形態によれば、送信すべき部分行列の定義を検知して袖領域通信を開始し、参照すべき部分行列の受信を検知して計算を開始する。その結果、データ通信の遅延を解消するとともに、計算効率を向上することによって、ステンシル計算の処理時間を短縮することを可能とする並列計算装置を提供することができる。
【０１４９】
なお、本実施形態にかかる並列計算装置においては、任意の行と列とからなる行列を対象とすることができる。また、本実施形態にかかる並列計算装置には、２次元の行列のみならず、３次元以上の任意の次元の行列または配列についてもステンシル計算を処理させることができる。
【０１５０】
（実施例）
次に、本発明の実施形態に係る並列計算装置に関して、具体的な実施例を挙げて説明する。以下の実施例については、図３および図５と、図９〜図１１のフローチャートとを参照しながら説明する。
【０１５１】
以下の実施例は、最初の行列である行列Ａから新しい行列Ｂを算出し、算出した行列Ｂから新しい行列Ｃを算出し、さらに行列Ｃから新しい行列Ｄを算出する、といった計算を繰り返すものである。行列Ａの要素はＡ［ｉ］［ｊ］、行列Ｂの要素はＢ［ｉ］［ｊ］などと表記する（ｉ、ｊは整数）。なお、以下においては、行列Ａ、行列Ｂおよび行列Ｃなどを部分行列として説明する。また、以下の実施例の説明では一部の要素の計算についてのみ説明しているが、実際には行列を構成する全ての要素の計算対象とする。
【０１５２】
（実施例１）
実施例１では、Ｍ（１，１）の動作について、図９〜図１１のフローチャートを参照しつつ、事例を挙げて説明する。
【０１５３】
ただし、実施例１では、Ｂ［ｉ］［ｊ］の算出に、Ａ［ｉ−１］［ｊ］、Ａ［ｉ＋１］［ｊ］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ−１］、Ａ［ｉ］［ｊ＋１］の５要素を用いる。また、Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）の９台のノード１１（計算機）には、図５のように、各行列の部分行列を分散して配置する。
【０１５４】
実施例１において、Ｍ（１，１）の計算単位となる要素集合は、｛＜２，２＞｝，｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝とする。また、Ｍ（１，１）の送信すべき要素集合は、｛＜２，２＞｝、｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝とする。
【０１５５】
図９において、まず、未定義要素カウント手段１３は、出力行列と要素の位置とを基に送信すべき要素集合と送信先のペアの集合を導出するマップＳを構築する（ステップＳ１１）。
【０１５６】
例えば、行列Ａから行列Ｂが算出される過程において、Ｍ（１，１）によってＢ［２］［２］が算出されたとする。Ｍ（１，１）によって算出されたＢ［２］［２］は、Ｍ（０，１）とＭ（１，０）が計算を担当する部分行列に含まれる要素の袖領域にある。そのため、Ｍ（１，１）は、Ｍ（０，１）およびＭ（１，０）にＢ［２］［２］を送る。マップＳには、Ｂ［２］［２］をＭ（０，１）およびＭ（１，０）に送信することを意味する、Ｂ［２］［２］⇒｛＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜Ｂ［２］［２］｝，Ｍ（１，０）＞｝というエントリを持たせる。
【０１５７】
実施例１では、Ｍ（１，１）に関するマップＳとして、以下の四つのエントリを含む。
Ｂ［２］［２］⇒＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞
Ｂ［２］［３］⇒＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞
Ｂ［３］［２］⇒＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞，＜｛Ｂ［３］［２］｝，Ｍ（２，１）＞
Ｂ［３］［３］⇒＜｛Ｂ［３］［３］｝，Ｍ（１，２）＞，＜｛Ｂ［３］［３］｝，Ｍ（２，１）＞
次に、未定義要素カウント手段１３は、送信すべき要素集合と送信先のペアを送信先に送信する際に、どの計算単位となる要素集合の未受信要素数のカウンタをいくら減ずるべきかを示す連想配列Ｒを構築する（ステップＳ１２）。
【０１５８】
例えば、Ｍ（１，１）は、｛Ｂ［２］［２］｝をＭ（１，０）に送信すると、Ｃ［２］［１］を算出する際に参照する袖領域の要素の一つが受信されていることをＭ（１，０）に対して通知する必要がある。すなわち、連想配列Ｒには、Ｍ（１，０）がＣ［２］［１］を受信していることを意味する、「｛Ｂ［２］［２］｝をＭ（１，０）に送ったら｛Ｃ［２］［１］｝の未受信要素数のカウンタを１減らす」、というエントリを持たせる。
【０１５９】
実施例１では、Ｍ（１，１）に関する連想配列Ｒとして、以下の８つのエントリを含む。
＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［１］｝→１
＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］｝→１
＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞→｛Ｃ［２］［４］｝→１
＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［１］［３］｝→１
＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞→｛Ｃ［３］［１］｝→１
＜｛Ｂ［３］［２］｝，Ｍ（１，２）＞→｛Ｃ［４］［２］｝→１
＜｛Ｂ［３］［３］｝，Ｍ（１，２）＞→｛Ｃ［３］［４］｝→１
＜｛Ｂ［３］［３］｝，Ｍ（２，１）＞→｛Ｃ［４］［３］｝→１
ここで、連想配列Ｒの算出過程について、図１１のフローチャートを用いて詳しく説明する。なお、以下の説明においては、Ｍ（１，１）が他のノード１１に対して送信すべき要素集合を送信する例について説明しているが、実際には全ての要素について同様の処理を行う。
【０１６０】
まず、未定義要素カウント手段１３は、送信すべき要素集合と送信先のペアをキーとし、計算単位となる要素集合をキーとして整数を返す連想配列を返す連想配列Ｒを初期化し、送信すべき要素集合と送信先のペアの集合をＸとする（ステップＳ２０１）。
【０１６１】
Ｍ（１，１）について、送信すべき要素集合と送信先のペアの集合は、送信単位が１要素である。そのため、Ｘは以下のように８つの要素集合を含む集合となる。
Ｘ＝｛＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞，＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［３］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞｝，＜｛Ｂ［３］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［３］［３］｝，Ｍ（１，０）＞｝
次に、Ｘは空ではないので（ステップＳ２０２でＮｏ）、Ｘから送信すべき要素集合と送信先のペアを一つ取り出しＹとし、ＹのコピーをＹ’とする（ステップＳ２０３）。
【０１６２】
ステップＳ２０３に関して、Ｍ（１，１）がＭ（０，１）およびＭ（１，０）に対してＢ［２］［２］を送信する例において、未定義要素カウント手段１３は、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞を取りだしてＹとし、ＹのコピーをＹ’とする。
【０１６３】
Ｙ’の要素集合は空ではないので（ステップＳ２０４でＮｏ）、未定義要素カウント手段１３は、Ｙ’の要素集合の集合から要素を一つ取り出す。そして、未定義要素カウント手段１３は、Ｙの送信先において、Ｙ’の要素集合の集合から取り出した要素を参照する計算が属する計算単位となる要素集合の集合をＺとする（ステップＳ２０５）。
【０１６４】
実施例１では、Ｙ’の要素集合からＢ［２］［２］を取り出す。Ｂ［２］［２］がＭ（０，１）に送信されると、Ｍ（０，１）では、Ｃ［１］［２］の算出においてＢ［２］［２］を参照するが、他に参照する算出は存在しない。そこで、計算単位は１要素なので、Ｚは｛｛Ｃ［１］［２］｝｝となる。
【０１６５】
Ｚは空ではないので（ステップＳ２０６でＮｏ）、Ｚから計算単位となる要素集合Ｗを一つ取り出す。そして、連想配列ＲにおいてＹをキーとして返ってきた連想配列について、要素集合Ｗをキーとして返ってきた値に１を加算する（ステップＳ２０７）。
【０１６６】
ここで、｛Ｃ［１］［２］｝を取り出して要素集合Ｗとし、連想配列Ｒについて、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］｝→１というエントリを生成する。Ｚは一つの要素しか持っていなかったため、Ｚは空になっている（ステップＳ２０６でＹｅｓ）。さらに、Ｙ’も一つの要素しかもっていなかったため、Ｙ’は空になっている（ステップＳ２０４でＹｅｓ）。それに対して、Ｘは空ではないので（ステップＳ２０２でＮｏ）、Ｘから送信すべき要素集合と送信先のペアを一つ取り出しＹとし、ＹのコピーをＹ’とする（ステップＳ２０３）。
【０１６７】
次に、未定義要素カウント手段１３は、＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞を取り出してＹとし、ＹのコピーをＹ’とする。
【０１６８】
先程と同様に、未定義要素カウント手段１３は、ステップＳ２０４からＳ２０７までを辿り、＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［１］｝→１のエントリを生成する。そして、ステップＳ２０２まで戻ると、Ｘは空ではないので（ステップＳ２０２でＮｏ）、未定義要素カウント手段１３は、＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞を取り出す（ステップＳ２０３）。さらに、再びステップＳ２０４からＳ２０７までを辿り、未定義要素カウント手段１３は、＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［１］［３］｝→１のエントリを生成する。
【０１６９】
図９のステップＳ１２では、図１１に示したようなエントリの生成フローを、Ｘに含まれる全ての要素集合について繰り返し、連想配列Ｒのエントリを全て生成する。なお、上述の例では、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞の処理をしてから＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞の処理をするように説明したが、処理の順番は任意に設定できる。
【０１７０】
図９に戻ると、未定義要素カウント手段１３は、要素集合送信先のＲＤＭＡ情報と未受信要素カウンタ操作情報とを他ノード１１の未定義要素カウント手段１３と交換する（ステップＳ１３）。
【０１７１】
要素集合送信先のＲＤＭＡ情報と、未受信要素カウンタ操作情報とを他ノード１１と交換することによって、自ノード１１から他ノード１１に袖領域の要素を送ることができるようになる。同時に、自ノード１１から他ノードの未受信要素数カウンタを操作できるようにもなる。
【０１７２】
そして、未定義要素カウント手段１３は各出力行列における送信すべき要素集合の送信先ごとの未定義要素数カウンタを、送信すべき要素集合のサイズに初期化する（ステップＳ１４）。
【０１７３】
ここでは、行列Ｂに関する送信すべき要素集合｛＜２，２＞｝のうちＭ（０，１）を送信先とする一つの要素、すなわちＢ［２］［２］が算出されれば、Ｍ（１，１）からＭ（０，１）に｛＜２，２＞｝を送信することができる。そのため、未定義要素カウント手段１３は、行列Ｂにおける送信すべき要素集合｛＜２，２＞｝のうちＭ（０，１）を送信先とする要素をカウントする未定義要素数カウンタを１に初期化する。
【０１７４】
また、未定義要素カウント手段１３は、行列Ｂにおける送信すべき要素集合｛＜２，２＞｝のうち、Ｍ（１，０）を送信先とする要素をカウントする未定義要素数カウンタを１に初期化する。
【０１７５】
同様に、未定義要素カウント手段１３は、行列Ｂにおける送信すべき要素集合｛＜２，３＞｝のうち、Ｍ（０，１）に送信する要素をカウントする未定義要素数カウンタと、Ｍ（１，２）に送信する要素をカウントする未定義要素数のカウンタとを１に初期化する。
【０１７６】
同様に、未定義要素カウント手段１３は、行列Ｂにおける送信すべき要素集合｛＜３，２＞｝のうち、Ｍ（１，０）に送信する要素をカウントする未定義要素数カウンタと、Ｍ（２，１）に送信する要素をカウントする未定義要素数のカウンタとを１に初期化する。
【０１７７】
同様に、未定義要素カウント手段１３は、行列Ｂにおける送信すべき要素集合｛＜３，３＞｝のうち、Ｍ（１，２）に送信する要素をカウントする未定義要素数カウンタと、Ｍ（２，１）に送信する要素をカウントする未定義要素数のカウンタとを１に初期化する。
【０１７８】
次に、ある要素の算出に必要な要素のうち、袖領域にあるために他のノード１１から受信しなければならない要素の数を集計し、各入力行列に関して計算単位となる要素集合ごとの未受信要素数カウンタを初期化する（ステップＳ１５）。
【０１７９】
行列Ｂに関して、｛＜２，２＞｝の算出、つまりＣ［２］［２］の算出において、袖領域にあるために他ノードから受信しなければならない要素は、Ｂ［１］［２］とＢ［２］［１］である。
【０１８０】
ここで、計算単位が１要素であるため、行列Ｂにおける｛＜２，２＞｝の未受信要素数のカウンタを２に初期化する。同様に、行列Ｂにおける｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝のそれぞれの未受信要素数のカウンタを２に初期化する。なお、行列Ａに関しては、既に袖領域の要素も受信されている状態にあるため、未受信要素数カウンタは全てゼロに初期化される。
【０１８１】
次に、未受信要素カウント手段１５は、各入力行列における計算単位となる要素集合ごとの未受信要素数カウンタを調べる（ステップＳ１６）。
【０１８２】
ここで、未受信要素カウント手段１５は、算出対象となる出力行列に関して計算単位となる全ての要素が揃ったか否かを判定し、揃った場合（Ｙｅｓ）は計算手段１２に計算を指示し、揃っていない場合（Ｎｏ）はステップＳ１６に戻る（ステップＳ１７）。
【０１８３】
未受信要素カウント手段１５は、算出対象となる出力行列に関して計算単位となる要素が全て揃った場合（ステップＳ１７でＹｅｓ）、対象入力行列を用いた対象要素集合の計算開始を計算手段１２に指令する（ステップＳ１８）。
【０１８４】
ここでは、行列Ａのカウンタが全てゼロであり、かつ行列Ｂの算出で参照すべき要素、すなわち行列Ａの要素は全て揃っている。そのため、未受信要素カウント手段１５は、計算手段１２に行列Ａを入力とした｛＜２，２＞｝の計算開始を指示する。すなわち、未受信要素カウント手段１５は、計算手段１２に対して、｛Ｂ［２］［２］｝、｛Ｂ［２］［３］｝、｛Ｂ［３］［２］｝および｛Ｂ［３］［３］｝の計算開始を指示する。
【０１８５】
なお、ノード１１が複数のコアを持っている場合、未受信要素カウント手段１５は、複数の要素集合の計算を並列に処理するように指示してもよい。
【０１８６】
この時点におけるＭ（０，１）、Ｍ（１，０）およびＭ（１，１）の未受信要素数カウンタと、行列Ｂの要素の値の算出状況の概念図を図１３に示す。図１３には、各ノード１１が計算を担当する行列Ｂの部分行列と、部分行列に含まれる各要素の未受信要素数がカウントされる未受信要素数カウンタとを図示している。
【０１８７】
図１３において、未受信要素数カウンタに含まれる各カウンタは、各ノード１１が担当する部分行列の要素を算出する際に必要となる袖領域の要素のうち、未だ受信されていない要素の数を示す。例えば、図１３において、Ｍ（０，１）の未受信要素数カウンタの各カウンタの数値は、要素の位置｛＜０，２＞｝、｛＜０，３＞｝、｛＜１，２＞｝、｛＜１，３＞｝における未受信要素の数を示している。
【０１８８】
次に、計算手段１２は、出力行列の要素の値を算出完了したら、算出が完了した出力行列および要素の位置を未定義要素カウント手段１３に送る（ステップＳ１９）。
【０１８９】
ここで、Ｂ［２］［２］の算出が完了すると、計算手段１２は、行列Ｂと＜２，２＞とを未定義要素カウント手段１３に送る。
【０１９０】
次に、未定義要素カウント手段１３は、要素の位置からマップＳを用いて送信すべき要素集合と送信先のペアの集合を導出し、対象出力行列の対象要素集合の対象送信先の未定義要素数カウンタを１減らす（ステップＳ２０）。
【０１９１】
マップＳには、Ｂ［２］［２］⇒＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞というエントリがある。このエントリは、送信すべき要素集合が｛Ｂ［２］［２］｝であり、送信先がＭ（０，１）およびＭ（１，０）であることを示す。そのため、マップＳによると、｛Ｂ［２］［２］｝をＭ（０，１）とＭ（１，０）へ送ればよいことが分かる。
【０１９２】
また、対象出力行列は行列Ｂであり、対象要素集合は｛Ｂ［２］［２］｝であり、対象送信先はＭ（０，１）およびＭ（１，０）である。そのため、行列Ｂに関する送信すべき要素集合｛＜２，２＞｝の送信先となるＭ（０，１）およびＭ（１，０）のそれぞれの未定義要素数カウンタを１減らす。行列Ｂの送信すべき要素集合｛＜２，２＞｝の送信先となるＭ（０，１）およびＭ（１，０）の未定義要素数カウンタは１に初期化されていたため、減算対象の未定義要素数カウンタはゼロになる。
【０１９３】
次に、未定義要素カウンタを１減ずることによってゼロになったものがあるか否かを判定する（ステップＳ２１）。
【０１９４】
この段階で、行列Ｂの送信すべき要素集合｛＜２，２＞｝の送信先となるＭ（０，１）およびＭ（１，０）の未定義要素数カウンタは共にゼロである。
【０１９５】
そのため、未定義要素カウント手段１３は、該当する要素集合と送信先を送受信手段１４に伝え、該当する要素集合を送信先に送信する指示を送受信手段１４に出す（ステップＳ２２）。未定義要素カウント手段１３による送受信手段１４への送信指示は、未定義要素数カウンタがゼロになった全ての送信先について出される。
【０１９６】
ここでは、未定義要素カウント手段１３は、｛Ｂ［２］［２］｝をＭ（０，１）へ送信する指示を送受信手段１４に出す。そして、未定義要素カウント手段１３は、Ｍ（０，１）の未受信要素数カウンタの減算を送受信手段１４に指示する。同様に、未定義要素カウント手段１３は、｛Ｂ［２］［２］｝のＭ（１，０）への送信を送受信手段１４に指示する。そして、未定義要素カウント手段１３は、Ｍ（１，０）の未受信要素数カウンタの減算を送受信手段１４に指示する。
【０１９７】
次に、送信すべき要素集合と送信先を与えられると、送受信手段１４は、必要に応じて要素集合を一度記憶手段１６の連続領域に再配置してから、対象要素集合を対象送信先に送信し始める（ステップＳ２３）。
【０１９８】
また、送受信手段１４は、送信すべき要素集合と送信先をキーとして連想配列Ｒを引き、どの未受信要素数カウンタをいくら減算すればよいか決定し、決定に応じて減算を行うコマンドを対象送信先に送信し始める（ステップＳ２４）。
【０１９９】
ステップＳ２３およびステップＳ２４の処理は、送受信手段１４が送信指示を受けた全ての対象について実行される。
【０２００】
ここでは、Ｍ（１，１）の送受信手段１４は、｛Ｂ［２］［２］｝をＭ（０，１）に送信し始める。そして、連想配列Ｒには、＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］｝→１というエントリがあるため、Ｍ（０，１）の｛Ｃ［１］［２］｝に対応する未受信要素数カウンタを１減算すればよいことが分かる。そのため、Ｍ（１，１）の送受信手段１４は、「Ｍ（０，１）の｛Ｃ［１］［２］｝に対応する未受信要素数カウンタを１減算する」コマンドをＭ（０，１）へ送る。
【０２０１】
また、Ｍ（１，１）の送受信手段１４は、｛Ｂ［２］［２］｝をＭ（１，０）に送信し始める。連想配列Ｒには、＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［１］｝→１というエントリがあるため、Ｍ（１，０）の｛Ｃ［２］［１］｝に対応するカウンタを１減算すればよいことが分かる。そのため、Ｍ（１，１）の送受信手段１４は、「Ｍ（１，０）の｛Ｃ［２］［１］｝に対応するカウンタを１減算する」コマンドをＭ（１，０）へ送る。
【０２０２】
ステップＳ２３の対象要素集合の送信と、ステップＳ２４のコマンド送信とが完了した時点におけるＭ（０，１）、Ｍ（１，０）およびＭ（１，１）の未受信要素数カウンタと、行列Ｂの要素の値の算出状況を図１４に示す。なお、図１４において、枠内に記された要素の位置を示す数字が太字のものは、算出完了あるいは受信完了していることを示している。
【０２０３】
送受信手段１４のデータ送信が完了してＭ（０，１）に袖領域のＢ［２］［２］が書き込まれ、送受信手段１４によるコマンドが完了すると、行列Ｂに関するＭ（０，１）の｛＜１，２＞｝の未受信要素数カウンタが２から１に減る。同様に、送受信手段１４のデータ送信が完了してＭ（１，０）に袖領域のＢ［２］［２］が書き込まれ、送受信手段１４によるコマンドが完了すると、行列Ｂに関するＭ（１，０）の｛＜２，１＞｝の未受信要素数カウンタが２から１に減る。すなわち、図１４は、Ｍ（１，１）の行列Ｂの要素集合｛Ｂ［２］［２］｝の送信は完了しており、Ｍ（０，１）およびＭ（１，０）は要素集合｛Ｂ［２］［２］｝の受信を完了していることを示している。
【０２０４】
次に、Ｍ（１，１）は、行列の算出を終了する条件が成立しているか否かを判定する（ステップＳ２５）。
【０２０５】
ここでは、行列Ｂの算出は全て終わっていないため、ステップＳ１６へ戻る。そして、Ｍ（１，１）は、ステップＳ１６からステップＳ２４までを繰り返して、担当する行列Ｂの要素の計算を遂行する。
【０２０６】
以上が、本発明の実施形態に係る並列計算装置１０の動作の一例を示す実施例１についての説明である。
【０２０７】
（実施例２）
実施例２では、Ｍ（１，１）とＭ（１，２）の動作について、事例を挙げて説明する。
【０２０８】
ただし、実施例２では、Ｂ［ｉ］［ｊ］の算出に、Ａ［ｉ−１］［ｊ］、Ａ［ｉ＋１］［ｊ］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ−１］およびＡ［ｉ］［ｊ＋１］の５要素を用いる。また、行列Ａを９分割した部分行列は、図５のように、Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）からなる９台のノード１１（計算機）に分散して配置する。
【０２０９】
実施例２において、Ｍ（１，１）の計算単位となる要素集合は｛＜２，２＞，＜２，３＞，＜３，２＞，＜３，３＞｝とする。また、Ｍ（１，１）の送信すべき要素集合は、｛＜２，２＞｝，｛＜２，３＞｝，｛＜３，２＞｝および｛＜３，３＞｝である。
【０２１０】
実施例２では、Ｍ（１，１）に関するマップＳとして、以下の四つのエントリを含む。
Ｂ［２］［２］⇒＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞
Ｂ［２］［３］⇒＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞
Ｂ［３］［２］⇒＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞，＜｛Ｂ［３］［２］｝，Ｍ（２，１）＞
Ｂ［３］［３］⇒＜｛Ｂ［３］［３］｝，Ｍ（１，２）＞，＜｛Ｂ［３］［３］｝，Ｍ（２，１）＞
実施例２では、Ｍ（１，１）に関する連想配列Ｒとして、以下の８つのエントリを含む。
＜｛Ｂ［２］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［０］，Ｃ［２］［１］，Ｃ［３］［０］，Ｃ［３］［１］｝→１
＜｛Ｂ［２］［２］｝，Ｍ（０，１）＞→｛Ｃ［０］［２］，Ｃ［０］［３］，Ｃ［１］［２］，Ｃ［１］［３］｝→１
＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞→｛Ｃ［２］［４］，Ｃ［２］［５］，Ｃ［３］［４］，Ｃ［３］［５］｝→１
＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［０］［２］，Ｃ［０］［３］，Ｃ［１］［２］，Ｃ［１］［３］｝→１
＜｛Ｂ［３］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［０］，Ｃ［２］［１］，Ｃ［３］［０］，Ｃ［３］［１］｝→１
＜｛Ｂ［３］［２］｝，Ｍ（２，１）＞→｛Ｃ［４］［２］，Ｃ［４］［３］，Ｃ［５］［２］，Ｃ［５］［３］｝→１
＜｛Ｂ［３］［３］｝，Ｍ（１，２）＞→｛Ｃ［２］［４］，Ｃ［２］［５］，Ｃ［３］［４］，Ｃ［３］［５］｝→１
＜｛Ｂ［３］［３］｝，Ｍ（２，１）＞→｛Ｃ［４］［２］，Ｃ［４］［３］，Ｃ［５］［２］，Ｃ［５］［３］｝→１
また、未定義要素カウント手段１３は、Ｍ（１，１）の出力行列としての行列Ｂに関する送信すべき要素集合の送信先ごとの未定義要素数カウンタを、以下のように全て１に初期化する。
【０２１１】
すなわち、未定義要素カウント手段１３は、出力行列としての行列Ｂに関する送信すべき要素集合｛＜２，２＞｝の送信先となるＭ（０，１）およびＭ（１，０）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２１２】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，３＞｝の送信先となるＭ（０，１）およびＭ（１，２）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２１３】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，２＞｝の送信先となるＭ（１，０）およびＭ（２，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２１４】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，３＞｝の送信先となるＭ（１，２）およびＭ（２，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２１５】
また、Ｍ（１，２）の計算単位となる要素集合は、｛＜２，４＞，＜２，５＞，＜３，４＞，＜３，５＞｝である。Ｍ（１，２）の計算単位となる要素集合の算出は、袖領域の要素として｛＜１，４＞，＜１，５＞，＜２，３＞，＜３，３＞，＜２，０＞，＜３，０＞，＜４，４＞，＜４，５＞｝を受信しないと実行できない。そのため、Ｍ（１，２）において、入力行列を行列Ｂとし、計算単位となる要素集合を｛＜２，４＞，＜２，５＞，＜３，４＞，＜３，５＞｝とする未受信要素数カウンタは８となる。
【０２１６】
ここで、Ｍ（１，１）がＢ［２］［２］を算出した後に、Ｂ［２］［３］を算出した直後の状態にあるものとする（図１５）。なお、図１５においては、この段階で算出が完了している行列Ｂの要素の位置を示す数字を太字で示している。
【０２１７】
Ｍ（１，１）の計算手段１２は、行列Ｂと＜２，３＞を未定義要素カウント手段１３に送る。
【０２１８】
マップＳには、Ｂ［２］［３］⇒＜｛Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞というエントリがある。そのため、Ｍ（１，１）の未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，３＞｝の送信先となるＭ（０，１）の未定義要素数カウンタを１減算する。
【０２１９】
結果として、行列Ｂに関する送信すべき要素集合｛＜２，３＞｝の送信先Ｍ（０，１）の未定義要素数カウンタを１減算するとゼロになる。そのため、Ｍ（１，１）の送受信手段１４は、Ｂ［２］［３］をＭ（１，２）に送る。
【０２２０】
また、Ｍ（１，１）の連想配列Ｒには、＜｛Ｂ［２］［３］｝，Ｍ（１，２）＞→｛Ｃ［２］［４］，Ｃ［２］［５］，Ｃ［３］［４］，Ｃ［３］［５］｝→１というエントリがある。そのため、Ｍ（１，１）の送受信手段１４は、Ｍ（１，２）の入力行列としての行列Ｂの計算単位となる要素集合｛Ｃ［２］［４］，Ｃ［２］［５］，Ｃ［３］［４］，Ｃ［３］［５］｝の未受信要素数カウンタを１減算するコマンドをＭ（１，２）に送る。
【０２２１】
これと並行して、Ｍ（１，１）の計算手段１２は、まだ計算が完了していないＢ［３］［２］、Ｂ［３］［３］の算出を行う。
【０２２２】
このようにして、Ｍ（１，１）は、Ｂ［２］［３］をＭ（１，２）へ送信する処理を、Ｂ［３］Ｂ［２］およびＢ［３］［３］の算出処理と並行して実行することができる。
【０２２３】
以上のように、本発明の実施形態によれば、Ｍ（１，１）は、Ｂ［２］［３］を算出した直後に、算出した値をＭ（１，２）に送信することができる。そのため、本実施形態によれば、算出が完了したデータの送信処理を、Ｂ［３］［２］、Ｂ［３］［３］の算出処理とオーバーラップすることができる。
【０２２４】
背景技術として示した関連技術では、Ｂ［２］［２］、Ｂ［２］［３］、Ｂ［３］［２］およびＢ［３］［３］を算出した後に、Ｂ［２］［３］をＭ（１，２）に送信することになる。そのため、関連技術においては、算出が完了したデータの送信処理と、算出が完了していないデータの算出処理とをオーバーラップすることができない。そのため、関連技術においては、全ての要素集合のデータの算出処理が完了しない限りデータの送信処理を実行できず、送信完了が遅延することになる。
【０２２５】
すなわち、本実施形態によれば、関連技術における送信処理の遅延を解決することによってステンシル計算の処理時間を短縮することが可能となる。
【０２２６】
（実施例３）
実施例３では、Ｍ（０，１）、Ｍ（１，０）、Ｍ（１，１）の動作について、事例を挙げて説明する。
【０２２７】
実施例３では、Ｂ［ｉ］［ｊ］の算出に、Ａ［ｉ−１］［ｊ］、Ａ［ｉ＋１］［ｊ］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ−１］およびＡ［ｉ］［ｊ＋１］の５要素を用いる。また、Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）の９台のノード１１（計算機）には、図５のように部分行列を分散して配置する。
【０２２８】
実施例３において、Ｍ（１，１）の計算単位となる要素集合は｛＜２，２＞｝、｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝とする。なお、計算単位となる要素集合のうち、｛＜２，２＞｝は｛＜１，２＞，＜２，１＞｝を受信しないと行列Ｃの要素を算出できない。そのため、Ｍ（１，１）において、行列Ｂの計算単位となる要素集合｛＜２，２＞｝の未受信要素数カウンタは２である。同様に、行列Ｂの計算単位となる要素集合である｛＜２，３＞｝、｛＜３，２＞｝および｛＜３，３＞｝の未受信要素数カウンタは２である。また、Ｍ（０，１）の送信すべき要素集合は、｛＜０，２＞｝、｛＜０，３＞｝、｛＜１，２＞｝および｛＜１，３＞｝とする。
【０２２９】
ここで、Ｍ（０，１）の出力行列と要素の位置とを基に送信すべき要素集合と送信先のペアの集合を導出するマップＳのエントリのうち、Ｍ（１，１）に関係するものは以下の二つである。
Ｂ［１］［２］⇒＜｛Ｂ［１］［２］｝，Ｍ（０，０）＞，＜｛Ｂ［１］［２］｝，Ｍ（１，１）＞
Ｂ［１］［３］⇒＜｛Ｂ［１］［３］｝，Ｍ（１，１）＞，＜｛Ｂ［１］［３］｝，Ｍ（０，２）＞
Ｍ（０，１）に関する連想配列Ｒのうち、Ｍ（１，１）に送った場合のもののみ取り出すと、以下のようになる。
【０２３０】
一つは、｛＜１，２＞｝をＭ（１，１）に送ったら｛Ｃ［２］［２］｝の未受信要素数カウンタを１減らす、すなわち＜｛Ｂ［１］［２］｝，Ｍ（１，１）＞→｛Ｃ［２］［２］｝→１という連想配列Ｒである。
【０２３１】
一つは、｛＜１，３＞｝をＭ（１，１）に送ったら｛Ｃ［２］［３］｝の未受信要素数カウンタを１減らす、すなわち＜｛Ｂ［１］［３］］，Ｍ（１，１）＞→｛Ｃ［２］［３］｝→１という連想配列Ｒである。
【０２３２】
また、未定義要素カウント手段１３は、Ｍ（０，１）の出力行列としての行列Ｂに関して、送信すべき要素集合の送信先ごとの未定義要素数カウンタを、以下のように全て１に初期化する。
【０２３３】
すなわち、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜０，２＞｝の送信先となるＭ（０，０）およびＭ（２，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２３４】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜０，３＞｝の送信先となるＭ（０，２）およびＭ（２，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２３５】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜１，２＞｝の送信先となるＭ（０，０）およびＭ（１，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２３６】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜１，３＞｝の送信先となるＭ（０，２）およびＭ（１，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２３７】
ここで、Ｍ（１，０）の送信すべき要素集合は、｛＜２，０＞｝、｛＜２，１＞｝、｛＜３，０＞｝および｛＜３，１＞｝とする。
【０２３８】
このとき、Ｍ（１，０）の出力行列と要素の位置とを基に送信すべき要素集合と送信先のペアの集合を導出するマップＳのエントリのうち、Ｍ（１，１）に関係するものは以下の二つである。
Ｂ［２］［１］⇒＜｛Ｂ［２］［１］｝，Ｍ（０，０）＞，＜｛Ｂ［２］［１］｝，Ｍ（１，１）＞
Ｂ［３］［１］⇒＜｛Ｂ［３］［１］｝，Ｍ（１，１）＞，＜｛Ｂ［３］［１］｝，Ｍ（２，０）＞
Ｍ（１，０）に関する連想配列Ｒのうち、Ｍ（１，１）に送った場合のもののみを取り出すと、以下のようになる。
【０２３９】
一つは、｛＜２，１＞｝をＭ（１，１）に送ったら｛＜２，２＞｝の未受信要素数カウンタを１減らす、すなわち＜｛Ｂ［２］［１］｝，Ｍ（１，１）＞→｛Ｃ［２］［２］｝→１という連想配列Ｒである。
【０２４０】
一つは、｛＜３，１＞｝をＭ（１，１）に送ったら｛＜３，２＞｝の未受信要素数カウンタを１減らす、すなわち＜｛Ｂ［３］［１］｝，Ｍ（１，１）＞→｛Ｃ［３］［２］｝→１という連想配列Ｒである。
【０２４１】
また、未定義要素カウント手段１３は、Ｍ（１，０）の出力行列としての行列Ｂに関して、送信すべき要素集合の送信先ごとの未定義要素数カウンタを、以下のように初期化する。
【０２４２】
すなわち、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，０＞｝の送信先となるＭ（０，０）およびＭ（１，２）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２４３】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，１＞｝の送信先となるＭ（０，０）およびＭ（１，１）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２４４】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，０＞｝の送信先となるＭ（１，２）およびＭ（２，０）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２４５】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，１＞｝の送信先となるＭ（１，１）およびＭ（２，０）のそれぞれに対応する未定義要素数カウンタを１に初期化する。
【０２４６】
この時点におけるＭ（０，１）、Ｍ（１，０）およびＭ（１，１）の未受信要素数カウンタと、行列Ｂの要素の値の算出状況は、図１３の通りである。
【０２４７】
ここで、Ｍ（０，１）はＢ［１］［２］の算出を完了し、Ｍ（１，０）はＢ［２］［１］の算出を完了し、Ｍ（１，１）はＢ［２］［２］、Ｂ［２］［３］およびＢ［３］［２］の算出を完了した状態にあるものを図１６に示す。なお、図１６においては、この段階で算出が完了している行列Ｂの要素の位置を示す数字を太字（太線枠内）で示している。
【０２４８】
Ｍ（０，１）の計算手段１２は、Ｂ［１］［２］を算出すると、行列Ｂと＜１，２＞を未定義要素カウント手段１３に送る。
【０２４９】
マップＳには、Ｂ［１］［２］⇒＜｛Ｂ［１］［２］｝，Ｍ（０，０）＞，＜｛Ｂ［１］［２］｝，Ｍ（１，１）＞というエントリがある。そのため、Ｍ（０，１）の未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜１，２＞｝の送信先となるＭ（１，１）の未定義要素数カウンタを１減算する。
【０２５０】
結果として、行列Ｂに関する送信すべき要素集合｛＜１，２＞｝の送信先となるＭ（１，１）の未定義要素数カウンタがゼロになったため、Ｍ（０，１）の送受信手段１４は、Ｂ［１］［２］をＭ（１，１）へ送る。
【０２５１】
また、Ｍ（０，１）の連想配列Ｒには、＜｛Ｂ［１］［２］｝，Ｍ（１，１）＞→｛Ｃ［２］［２］｝→１というエントリがある。そのため、Ｍ（０，１）の送受信手段１４は、Ｍ（１，１）の入力行列としての行列Ｂの計算単位となる要素集合｛Ｃ［２］［２］｝の未受信要素数カウンタのカウントを１減算するコマンドをＭ（１，１）に送る。その結果、Ｍ（１，１）の未受信要素数カウンタにおける要素の位置＜２，２＞の値が１になる（図１７）。
【０２５２】
Ｍ（１，０）の計算手段１２は、Ｂ［２］［１］を算出すると、行列Ｂと＜２，１＞を自身の未定義要素カウント手段１３に送る。
【０２５３】
マップＳにはＢ［２］［１］⇒＜｛Ｂ［２］［１］｝，Ｍ（０，０）＞，＜｛Ｂ［２］［１］｝，Ｍ（１，１）＞というエントリがある。そのため、Ｍ（１，０）の未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，１＞｝の送信先となるＭ（１，１）の未定義要素数カウンタを１減らす。
【０２５４】
結果として、行列Ｂに関する送信すべき要素集合｛＜２，１＞｝の送信先となるＭ（１，１）の未定義要素数カウンタがゼロになったため、Ｍ（１，０）の送受信手段１４は、Ｂ［２］［１］をＭ（１，１）へ送る。
【０２５５】
また、Ｍ（１，０）の連想配列Ｒには、＜｛Ｂ［２］［１］｝，Ｍ（１，１）＞→｛Ｃ［２］［２］｝→１というエントリがある。そのため、Ｍ（１，０）の送受信手段１４は、Ｍ（１，１）の入力行列としての行列Ｂの計算単位となる要素集合｛Ｃ［２］［２］｝の未受信要素数のカウントを１減算するコマンドをＭ（１，１）に送る。その結果、図１８に示すように、Ｍ（１，１）の未受信要素数カウンタにおける要素の位置＜２，２＞の値がゼロになる。
【０２５６】
そして、Ｍ（１，１）の未受信要素カウント手段１５は、Ｍ（１，１）の未受信要素数カウンタにおける要素の位置＜２，２＞の値がゼロになったことを検知して、Ｃ［２］［２］の計算開始を指令する（図１８）。
【０２５７】
実施例３に示したように、本発明の実施形態によれば、Ｍ（１，１）は、Ｂ［１］［２］およびＢ［２］［１］の値の受信の直後に、Ｃ［２］［２］の算出を開始することができる。
【０２５８】
背景技術に示した関連技術では、Ｂ［１］［２］およびＢ［２］［１］に加えて、Ｂ［１］［３］、Ｂ［３］［１］、Ｂ［２］［４］、Ｂ［３］［４］、Ｂ［４］［２］およびＢ［４］［３］を受信してからＣ［２］［２］の算出を開始する。そのため、関連技術においては、全ての要素集合のデータの受信が完了しない限り対象要素の計算を開始することができず、計算処理が遅延することになる。
【０２５９】
すなわち、本実施形態によれば、関連技術における計算処理の遅延を解決することによってステンシル計算の処理時間を短縮することが可能となる。
【０２６０】
（実施例４）
実施例４では、Ｍ（１，１）の動作について、事例を挙げて説明する。
【０２６１】
実施例４では、Ｂ［ｉ］［ｊ］を算出するためには９要素を用いる。Ａ［ｉ−１］［ｊ−１］、Ａ［ｉ−１］［ｊ］、Ａ［ｉ−１］［ｊ＋１］、Ａ［ｉ］［ｊ−１］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ＋１］、Ａ［ｉ＋１］［ｊ−１］、Ａ［ｉ＋１］［ｊ］およびＡ［Ｉ＋１］［ｊ＋１］の９要素である。また、Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）の９台のノード１１（計算機）には、図１２のように部分行列を配置する。
【０２６２】
まず、Ｍ（１，１）の計算単位となる要素集合は｛＜２，２＞，＜２，３＞｝｛＜３，２＞，＜３，３＞｝とする。
【０２６３】
また、Ｍ（１，１）の計算単位となる要素集合のうち、｛＜２，２＞，＜２，３＞｝は、｛＜１，１＞，＜１，２＞，＜１，３＞，＜１，４＞，＜２，１＞，＜２，４＞｝を受信しないと行列Ｃの要素を算出できない。そのため、Ｍ（１，１）の入力行列としての行列Ｂに関する未受信要素数カウンタにおいて、計算単位となる要素集合｛＜２，２＞，＜２，３＞｝のカウント値は８となる。
【０２６４】
同様に、Ｍ（１，１）の入力行列としての行列Ｂに関する未受信要素数カウンタにおいて、計算単位となる要素集合｛＜３，２＞，＜３，３＞｝のカウント値は８となる。
【０２６５】
Ｍ（１，１）の送信すべき要素集合と送信先のペアは、以下の通りである。二つの要素の位置の要素集合を扱うのは、＜｛＜２，２＞，＜２，３＞｝，Ｍ（０，１）＞、＜｛＜３，２＞，＜３，３＞｝，Ｍ（２，１）＞、＜｛＜２，２＞，＜３，２＞｝，Ｍ（１，０）＞および＜｛＜２，３＞，＜３，３＞｝，Ｍ（１，２）＞である。また、一つの要素の位置の要素集合を扱うのは、＜｛＜２，２＞｝，Ｍ（０，０）＞、＜｛＜２，３＞｝，Ｍ（０，２）＞、＜｛＜３，２＞｝，Ｍ（２，０）＞および＜｛＜３，３＞｝，Ｍ（２，２）＞である。
【０２６６】
Ｍ（１，１）の未定義要素カウント手段１３は、Ｍ（１，１）の出力行列と要素の位置とを基に送信すべき要素集合と送信先のペアの集合を導出するマップＳを構築する。
【０２６７】
例えば、Ｍ（１，１）がＢ［２］［２］を算出したとする。このとき、Ｍ（０，１）に送信すべき要素集合｛Ｂ［２］［２］，Ｂ［２］［３］｝の要素、Ｍ（１，０）に送信すべき要素集合｛Ｂ［２］［２］，Ｂ［３］［２］｝の要素、Ｍ（０，０）に送信すべき要素集合｛Ｍ［２］［２］｝の要素が算出されたことになる。
【０２６８】
このため、マップＳには、Ｂ［２］［２］⇒＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］，Ｂ［３］［２］，Ｍ（１，０）｝＞，＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞というエントリが存在することになる。
【０２６９】
同様に、マップＳには以下のようなエントリが存在することになる。
Ｂ［２］［３］⇒＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］，Ｂ［３］［３］，Ｍ（１，２）｝＞，＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞
Ｂ［３］［２］⇒＜｛Ｂ［３］［２］，Ｂ［３］［３］｝，Ｍ（２，１）＞，＜｛Ｂ［２］［２］，Ｂ［３］［２］，Ｍ（１，０）｝＞，＜｛Ｂ［３］［２］｝，Ｍ（２，０）＞
Ｂ［３］［３］⇒＜｛Ｂ［３］［２］，Ｂ［３］［３］｝，Ｍ（２，０）＞，＜｛Ｂ［２］［３］，Ｂ［３］［３］，Ｍ（１，２）｝＞，＜｛Ｂ［３］［３］｝，Ｍ（２，２）＞
次に、Ｍ（１，１）の未定義要素カウント手段１３は、Ｍ（１，１）の送信すべき要素集合を送信先に送信する際に、どの計算単位となる要素集合の未受信要素数カウンタをいくら減ずるべきかを示す連想配列Ｒを構築する。
【０２７０】
例えば、Ｍ（１，１）が｛Ｂ［２］［２］，Ｂ［２］［３］｝をＭ（０，１）に送信したものとする。このとき、Ｍ（０，１）は、計算単位｛Ｃ［１］［２］，Ｃ［１］［３］｝の算出に必要な８要素のうち２要素を受信したことになる。
【０２７１】
このため、連想配列Ｒには、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］，Ｃ［１］［３］｝→２というエントリが存在する。
【０２７２】
同様に考えると、Ｍ（１，１）に関する連想配列Ｒに存在するエントリは、以下のように列挙される。
＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］，Ｃ［１］［３］｝→２
＜｛Ｂ［３］［２］，Ｂ［３］［３］｝，Ｍ（２，１）＞→｛Ｃ［４］［２］，Ｃ［４］［３］｝→２
＜｛Ｂ［２］［２］，Ｂ［３］［２］｝，Ｍ（１，０）＞→｛Ｃ［２］［０］，Ｃ［２］［１］｝→１
＜｛Ｂ［２］［２］，Ｂ［３］［２］｝，Ｍ（１，０）＞→｛Ｃ［３］［０］，Ｃ［３］［１］｝→１
＜｛Ｂ［２］［３］，Ｂ［３］［３］｝，Ｍ（１，２）＞→｛Ｃ［２］［４］，Ｃ［２］［５］｝→１
＜｛Ｂ［２］［３］，Ｂ［３］［３］｝，Ｍ（１，２）＞→｛Ｃ［３］［４］，Ｃ［３］［５］｝→１
＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞→｛Ｃ［１］［０］，Ｃ［１］［１］｝→１
＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞→｛Ｃ［１］［４］，Ｃ［１］［５］｝→１
＜｛Ｂ［３］［２］｝，Ｍ（２，０）＞→｛Ｃ［４］［０］，Ｃ［４］［１］｝→１
＜｛Ｂ［３］［３］｝，Ｍ（２，２）＞→｛Ｃ［４］［４］，Ｃ［４］［５］｝→１
また、未定義要素カウント手段１３は、Ｍ（１，１）の出力行列としての行列Ｂの送信すべき要素集合の送信先ごとの未定義要素数カウンタを、以下のように初期化する。
【０２７３】
すなわち、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，２＞，＜２，３＞｝の送信先Ｍ（０，１）についての未定義要素数カウンタを２に初期化する。
【０２７４】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，２＞，＜３，３＞｝の送信先Ｍ（２，１）についての未定義要素数カウンタを２に初期化する。
【０２７５】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，２＞，＜３，２＞｝の送信先Ｍ（１，０）についての未定義要素数カウンタを２に初期化する。
【０２７６】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，３＞，＜３，３＞｝の送信先Ｍ（１，２）についての未定義要素数カウンタを２に初期化する。
【０２７７】
また、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，２＞｝の送信先Ｍ（０，０）についての未定義要素数カウンタを１に初期化する。
【０２７８】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜２，３＞｝の送信先Ｍ（０，２）についての未定義要素数カウンタを１に初期化する。
【０２７９】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，２＞｝の送信先Ｍ（２，０）についての未定義要素数カウンタを１に初期化する。
【０２８０】
同様に、未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合｛＜３，３＞｝の送信先Ｍ（２，２）についての未定義要素数カウンタを１に初期化する。
【０２８１】
この時点におけるＭ（１，１）の未受信要素数カウンタと、行列Ｂの要素の値と、未定義要素数カウンタの算出状況の概念図を図１９に示す。図１９においては、Ｍ（１，１）が担当する行列Ｂの部分行列に対して、上方の破線枠内に未受信要素カウンタを示し、下方の一点鎖線枠内に未定義要素カウンタを示している。
【０２８２】
ここで、Ｍ（１，１）は、Ｂ［２］［２］を算出した状態にあるとする。このとき、Ｍ（１，１）の計算手段１２は、行列Ｂと＜２，２＞を未定義要素カウント手段１３に送る。
【０２８３】
マップＳには、Ｂ［２］［２］⇒＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［２］，Ｂ［３］［２］，Ｍ（１，０）｝＞，＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞というエントリがある。そのため、Ｍ（１，１）の未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合と送信先のペアの未定義要素数カウンタを１減らす。ただし、行列Ｂに関する送信すべき要素集合と送信先のペアは、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞、＜｛Ｂ［２］［２］，Ｂ［３］［２］，Ｍ（１，０）｝＞および＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞の三つである。
【０２８４】
その結果、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞および＜｛Ｂ［２］［２］，Ｂ［３］［２］，Ｍ（１，０）｝＞のカウントは１となり、＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞のカウントは０となる。
【０２８５】
そして、Ｍ（１，１）の送受信手段１４は、｛Ｂ［２］［２］｝をＭ（０，０）に送る。
【０２８６】
また、連想配列Ｒには、＜｛Ｂ［２］［２］｝，Ｍ（０，０）＞→｛Ｃ［１］［０］，Ｃ［１］［１］｝→１というエントリがある。そのため、Ｍ（１，１）の送受信手段１４は、Ｍ（０，０）の入力行列としての行列Ｂに関する計算単位となる要素集合｛Ｃ［１］［０］，Ｃ［１］［１］｝の未受信要素数のカウントを１減算するコマンドをＭ（０，０）に送る。
【０２８７】
この段階におけるＭ（１，１）の状態を図２０に示す。なお、図２０において、算出完了あるいは受信完了した要素の位置を示す数字は太字（太線枠内）で示している。
【０２８８】
Ｍ（１，１）の計算手段１２は、Ｂ［２］［３］を算出すると、行列Ｂと＜２，３＞を未定義要素カウント手段１３に送る。
【０２８９】
マップＳにはＢ［２］［３］⇒＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞，＜｛Ｂ［２］［３］，Ｂ［３］［３］，Ｍ（１，２）｝＞、＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞というエントリがある。そのため、Ｍ（１，１）の未定義要素カウント手段１３は、行列Ｂに関する送信すべき要素集合と送信先のペアの未定義要素数カウンタを１減らす。ただし、行列Ｂに関する送信すべき要素集合と送信先のペアは、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞、＜｛Ｂ［２］［３］，Ｂ［３］［３］，Ｍ（１，２）｝＞および＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞の三つである。
【０２９０】
その結果、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞および＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞のカウントは０となり、＜｛Ｂ［２］［３］，Ｂ［３］［３］，Ｍ（１，２）｝＞のカウントは１となる。
【０２９１】
Ｍ（１，１）の送受信手段１４は、｛Ｂ［２］［３］｝をＭ（０，２）へ送る。
【０２９２】
また、連想配列Ｒには、＜｛Ｂ［２］［３］｝，Ｍ（０，２）＞→｛Ｃ［１］［４］，Ｃ［１］［５］｝→１というエントリがある。そのため、Ｍ（１，１）の送受信手段１４は、Ｍ（０，２）の入力行列としての行列Ｂの計算単位となる要素集合｛Ｃ［１］［４］，Ｃ［１］［５］｝の未受信要素数カウントを１減算するコマンドをＭ（０，２）に送る。
【０２９３】
また、Ｍ（１，１）の送受信手段１４は、｛Ｂ［２］［２］，Ｂ［２］［３］｝をＭ（０，１）へ送る。
【０２９４】
また、連想配列Ｒには、＜｛Ｂ［２］［２］，Ｂ［２］［３］｝，Ｍ（０，１）＞→｛Ｃ［１］［２］，Ｃ［１］［３］｝→２というエントリがある。そのため、Ｍ（１，１）の送受信手段１４は、Ｍ（０，１）の入力行列としての行列Ｂの計算単位となる要素集合｛Ｃ［１］［２］，Ｃ［１］［３］｝の未受信要素数カウントを１減算するコマンドをＭ（０，１）に送る。
【０２９５】
この段階におけるＭ（１，１）の状態を図２１に示す。なお、図２０と同様に、図２１において、算出完了あるいは受信完了した要素の位置を示す数字は太字（太線枠内）で示している。
【０２９６】
行列Ｂを構成する全ての要素について以上の動作を実行することによって、行列Ｂから行列Ｃを算出することができる。
【０２９７】
以上のように、本発明の実施形態によれば、５要素のみならず９要素を用いるステンシル計算も可能である。ただし、本発明の実施形態の手法は、５要素や９要素に限らず、任意の数の要素を用いるステンシル計算に使用することができる。
【０２９８】
（関連技術）
ここで、背景技術で示した関連技術に関して補足的な説明を加える。
【０２９９】
図２２には、非特許文献１（Ｍ．Ｓｎｉｒ  ｅｔ  ａｌ、ＭＰＩ：Ｔｈｅ  Ｃｏｍｐｌｅｔｅ  Ｒｅｆｅｒｅｎｃｅ、ＭＩＴ  Ｐｒｅｓｓ、Ｊａｎｕａｒｙ  １、１９９６）の並列計算装置５００に関する構成図を示す。非特許文献１の並列計算装置５００は、複数のノード５０１、ネットワーク部５０５を備える。また、各ノード５０１は、計算部５０２と、送受信部５０３と、メモリ部５０４とを有する。
【０３００】
計算部５０２は、行列の各要素の値を算出するのに必要なデータをメモリ部５０４から取り出してステンシル計算を行い、演算結果をメモリ部５０４に格納する。送受信部５０３は、他のノード５０１に格納され、行列の要素の値を算出するために必要なデータ、すなわち袖領域のデータを他のノード５０１から受信するとともに、他のノード５０１で袖領域のデータとして必要となるデータを他のノード５０１に送信する。メモリ部５０４は、入力行列と出力行列といった行列のデータを格納する。ネットワーク部５０５は、データの送受信を仲介する。
【０３０１】
図２２の非特許文献１の並列計算装置５００では、新たな一つの行列を算出する際に、以下のステップを実行する。
（１）計算部５０２は、出力行列の要素を算出する。計算部５０２は、算出した出力行列の要素を、ノード５０１が計算を担当する出力行列の要素集合（部分行列の要素集合）について繰り返す。
（２）送受信部５０３は、計算部５０２が算出したデータを、そのデータを袖領域のデータとして必要とする他のノード５０１に送信する。
【０３０２】
以上が、非特許文献１に係る並列計算装置５００の構成・動作についての説明である。
【０３０３】
ここで、非特許文献１の並列計算装置５００の問題点について例を挙げて具体的に説明する。なお、以下の例では、新たなる行列Ｂの要素Ｂ［ｉ］［ｊ］を算出するために、参照される行列Ａに含まれるＡ［ｉ−１］［ｊ］、Ａ［ｉ＋１］［ｊ］、Ａ［ｉ］［ｊ］、Ａ［ｉ］［ｊ−１］およびＡ［ｉ］［ｊ＋１］の５要素を用いるものとする。
【０３０４】
まず、データ通信の遅延隠蔽の度合いが小さくなることによって処理時間が増大することについて、図５および図２５を用いて説明する。
【０３０５】
ここで、９台の計算機Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）を用いて、行列Ａを図５のように分散配置する。そして、９台の計算機によって、参照される行列Ａから新たなる行列Ｂを算出する。また、Ｍ（１，１）は、Ｂ［２］［２］、Ｂ［２］［３］、Ｂ［３］［２］、Ｂ［３］［３］の順で要素の計算を実行するものとする。
【０３０６】
図２５の例では、既に算出された要素の位置については、要素の位置を示す数字を太字で示している。すなわち、図２５に示した状態は、Ｂ［２］［３］を算出した直後の状態にある。図２５の状態に遷移した瞬間に、Ｍ（１，１）は、Ｂ［２］［３］をＭ（１，２）に送信開始し、並行して他の要素の算出を実行できるはずである。
【０３０７】
ところが、非特許文献１の並列計算装置５００では、さらにＢ［３］［２］およびＢ［３］［３］を算出した後に、初めてＢ［２］［３］をＭ（１，２）に送信することになる。つまり、図２５に示した時点では、送信開始した後に並行して実行できる処理はない。
【０３０８】
このように、非特許文献１の並列計算装置５００では、送信開始のタイミングが遅れるために遅延隠蔽の度合いが小さくなり、処理時間が増大することになる。
【０３０９】
次に、必要なデータを受信した直後に要素の算出を開始しないために、処理時間が増大することについて、図５および図２６を用いて説明する。
【０３１０】
ここで、９台の計算機Ｍ（０，０）、Ｍ（０，１）、Ｍ（０，２）、Ｍ（１，０）、Ｍ（１，１）、Ｍ（１，２）、Ｍ（２，０）、Ｍ（２，１）およびＭ（２，２）に、行列Ａを図５のように分散配置する。そして、９台の計算機によって、参照される行列Ａから新たなる行列Ｂを算出する。
【０３１１】
図２６に示した状態において、Ｍ（０，１）、Ｍ（１，０）、Ｍ（１，１）は、担当するＢの要素を全て算出した直後の状態にある。この後、理想のケースでは、Ｃ［２］［２］の算出は、矢印で示したＢ［１］［２］、Ｂ［２］［１］の値の受信の直後に開始できるはずである。
【０３１２】
ところが、非特許文献１の並列計算装置５００では、Ｂ［１］［２］およびＢ［２］［１］に加えて、Ｂ［１］［３］、Ｂ［３］［１］、Ｂ［２］［４］、Ｂ［３］［４］、Ｂ［４］［２］およびＢ［４］［３］を受信してから行列Ｃの計算を開始する。すなわち、受信すべき要素を全て受信してから行列Ｃの計算が開始されることになる。そのため、行列Ｃの計算開始は、理想のケースに比較して遅れることになる。
【０３１３】
このように、非特許文献１の並列計算装置５００では、以下のような二つの問題点がある。一つ目の問題点は、送信開始のタイミングが遅れるために遅延隠蔽の度合いが小さくなり、処理時間が増大することである。二つ目の問題点は、必要なデータを受信した直後に要素の算出を開始しないため、処理時間の増大することである。
【０３１４】
特許文献１（特許２６０２２４１号公報）および特許文献２（特開平１−１０２６４５号公報）には、非特許文献１の問題点を解決する技術が開示された技術されている。特許文献１および特許文献２については、図２３および図２４を用いて説明する。なお、図２３および図２４においては、データの流れを実線の矢印で示し、制御の流れを破線の矢印で示す。
【０３１５】
特許文献１の並列計算装置６００は、図２３に示すように、複数のノード６０１、ネットワーク部６０５を備える。また、各ノード６０１は、トークン受信部６０２と、計算部６０３と、トークン送信部６０３とを有する。
【０３１６】
トークン受信部６０２は、他のノード６０１からステンシル計算に必要となるデータを受け取り、必要なデータが全て揃ったか否かの判定を行う。トークン受信部６０２は、データを内包するトークンを受信し、受信したトークンが登録されていたマッチ条件にマッチした場合はデータを受信する。トークン受信部６０２は、行列の要素の算出に必要なデータを他のノード６０１から全て受け取ると、計算部６０３に計算開始の指令を出すとともに、計算に必要となるデータを送る。計算部６０３は、行列の１要素を算出し、結果をトークン送信部６０３に送る。トークン送信部６０３は、計算部６０３から１結果要素を受け取り、そのデータを他のノード６０１が必要としていたら、そのデータを内包するトークンと呼ばれる構造体を作成する。トークン送信部６０３は、そのデータを必要とするノードに作成したトークンを送信する。ネットワーク部６０５は、トークンの送受信を仲介する。
【０３１７】
特許文献１の並列計算装置６００では、行列Ａから行列Ｂ、行列Ｂから行列Ｃを算出する際に、以下のステップを実行する。
（１）トークン受信部６０２には、計算部６０３において新たなる行列の要素の算出に必要となるデータを、トークンのマッチ条件として登録しておく。
（２）トークン受信部６０２は、他のノード６０１から、新たなる行列の要素の算出に必要なデータを受け取り、計算に必要なデータを全て受信したら、新たなる行列の要素の算出開始を計算部６０３に指示する。
（３）計算部６０３は、トークン受信部６０２の指示を受けて、新たなる行列の１要素を算出し、算出した結果要素をトークン送信部６０４に送る。
（４）トークン送信部６０４は、計算部６０３が算出した１結果要素を受け取り、そのデータを必要とする他のノード６０１が存在した場合、そのデータを内包するトークンを作成し、作成したトークンを対象となるノード６０１に送信する。
【０３１８】
以上が、特許文献１に係る並列計算装置６００の構成・動作についての説明である。
【０３１９】
次に、特許文献２の並列計算装置７００は、図２４に示すように、ロード部７０１、ネットワーク部７０５を備える。また、各ノード７０１は、トークン受信部７０２と、タスク実行部７０３と、トークン送信部７０３と、を有する。
【０３２０】
特許文献２の並列計算装置７００は、特許文献１の並列計算装置６００の計算部６０３の替わりにタスク実行部７０３を有する点が異なる。
【０３２１】
トークン受信部７０２は、データを内包するトークンを受信し、受信したトークンが登録されていたマッチ条件にマッチした場合はデータを受信する。トークン受信部７０２は、行列の要素集合の算出に必要なデータを他のノード７０１から全て受け取ると、計算部６０３に計算開始の指令を出すとともに、計算に必要となるデータを送る。タスク実行部７０３は、行列の１要素を算出して１結果要素をトークン送信部７０３に送るというプロセスを、行列の要素集合に対して繰り返す。トークン送信部７０３は、タスク実行部７０３から１結果要素を受け取り、その１結果要素を含むトークンと呼ばれる構造体を作成し、作成したトークンを対象となるノード７０１に送信する。ネットワーク部７０５は、トークンの送受信を仲介する。
【０３２２】
特許文献２の並列計算装置７００では、行列Ａから行列Ｂ、行列Ｂから行列Ｃを算出する際に、以下のステップを実行する。
（１）トークン受信部７０２には、タスク実行部７０３において新たなる行列の要素集合の算出に必要なデータを、トークンのマッチ条件として登録しておく。
（２）トークン受信部７０２は、他のノード７０１から、新たなる行列の要素集合の算出に必要なデータを受け取り、計算に必要な全てのデータを受信したら、新たなる行列の要素集合の算出開始をタスク実行部７０３に指示する。
（３）タスク実行部７０３は、トークン受信部７０２の指示を受けて、新たなる行列の１要素を算出し、算出した結果要素をトークン送信部７０４に送信する。タスク実行部７０３は、算出した結果要素をトークン送信部７０４に送信する処理を、行列要素集合について繰り返す。
（４）トークン送信部７０４は、タスク実行部７０３が算出した１結果要素を受け取り、そのデータを必要とする他のノード７０１が存在した場合、そのデータを含むトークンを作成し、作成したトークンを対象となるノード７０１に送信する。
【０３２３】
以上が、特許文献２に係る並列計算装置７００の構成・動作についての説明である。
【０３２４】
特許文献１および特許文献２の並列計算装置によれば、非特許文献１の問題点を解決できるものの、データ通信の遅延が大きいという問題点が生じてしまう。第１の理由は、袖領域の要素がまとめて送信されずに、一つ一つ送信されるためである。第２の理由は、袖領域の要素の一つ一つにトークン制御用データを付け加えてトークンを作成し、作成したトークンを送信するので、トークン制御用データのオーバーヘッドの分だけデータ通信の遅延が生じるためである。第３の理由は、データ通信時間にトークンマッチの遅延が加わるためである。
【０３２５】
以上のような関連技術の問題点は、本発明の実施形態によって解決されることになる。
【０３２６】
なお、本実施形態に係る並列計算方法は、ソフトウェアによって実現することも可能である。並列計算装置１０を制御するプログラムは、図９から図１１に示したフローチャートに従って機能する。すなわち、並列計算装置１０の各ノード１１が有する計算手段１２、未定義要素カウント手段１３、送受信手段１４、未受信要素カウント手段１５が行う処理を、並列計算装置１０が備えるプロセッサがプログラムを実行することによって実現してもよい。
【０３２７】
上記の並列計算プログラムは、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリ等の半導体記憶装置、光ディスク、磁気ディスク、光磁気ディスク等の媒体に格納されてもよい。
【０３２８】
以上、実施形態および実施例を参照して本発明を説明してきたが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０３２９】
本発明は、長期天気予報アプリケーション、海況変動予測アプリケーション、水産環境予測アプリケーションなどのように、未来を予測するためのアプリケーションに利用することができる。
【符号の説明】
【０３３０】
１０    並列計算装置
１１    ノード
１２    計算手段
１３    未定義要素カウント手段
１４    送受信手段
１５    未受信要素カウント手段
１６    記憶手段
１７    ネットワーク
５００    並列計算装置
５０１    ノード
５０２    計算部
５０３    送受信部
５０４    メモリ部
５０５    ネットワーク部
６００    並列計算装置
６０１    ノード
６０２    トークン受信部
６０３    計算部
６０４    トークン送信部
６０５    ネットワーク部
７００    並列計算装置
７０１    ノード
７０２    トークン受信部
７０３    タスク実行部
７０４    トークン送信部
７０５    ネットワーク部
【図１】
2015191442.tif 000003
【図２】
2015191442.tif 000004
【図３】
2015191442.tif 000005
【図４】
2015191442.tif 000006
【図５】
2015191442.tif 000007
【図６】
2015191442.tif 000008
【図７】
2015191442.tif 000009
【図８】
2015191442.tif 000010
【図９】
2015191442.tif 000011
【図１０】
2015191442.tif 000012
【図１１】
2015191442.tif 000013
【図１２】
2015191442.tif 000014
【図１３】
2015191442.tif 000015
【図１４】
2015191442.tif 000016
【図１５】
2015191442.tif 000017
【図１６】
2015191442.tif 000018
【図１７】
2015191442.tif 000019
【図１８】
2015191442.tif 000020
【図１９】
2015191442.tif 000021
【図２０】
2015191442.tif 000022
【図２１】
2015191442.tif 000023
【図２２】
2015191442.tif 000024
【図２３】
2015191442.tif 000025
【図２４】
2015191442.tif 000026
【図２５】
2015191442.tif 000027
【図２６】
2015191442.tif 000028