(57)【要約】【課題】毎回シフト通信次元やシフト通信方向、シフト通信対象の配列が変化するような場合、またはシフト通信が異なる手続中で発生する場合でも、通信の高速化を図る。【解決手段】配列の分割配置方法に１対１に対応する多次元シフト通信スケジュールテーブル中に、通信スケジュールを各次元、各方向独立に生成、保存するとともに、多次元シフト通信パターンテーブルに、当該次元、当該方向のシフト幅、および当該次元より小さな次元の上下方向のシフト幅を保存しておくことにより、多次元シフト通信時の通信スケジュールが部分的に独立に再利用可能となり、通信スケジュール生成のコストを削減することにより、通信の高速化を図る。【選択図】図１
2008181388.tif 000002
【特許請求の範囲】
【請求項１】
分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置であって、
多次元シフト通信を行う配列の分割配置方法の解析をする手段と、
前記解析の結果に基づき、同一の分割配置に対する多次元シフト通信スケジュールを多次元シフト通信スケジュールテーブルより検索する手段と、
前記検索を行い、同一の分割配置に対する多次元シフト通信スケジュールが存在する場合には、多次元シフトパターンテーブルを検索しシフトパターンの一致を判定する手段と、
シフトパターンの一致する多次元シフト通信スケジュールが存在する場合には、該一致する多次元シフト通信スケジュールを再利用する手段と、
前記多次元シフト通信に必要な多次元通信スケジュールを、多次元シフト通信スケジュールテーブルに格納する手段と、
前記多次元シフト通信に必要な多次元通信スケジュールのシフトパターンを多次元シフトパターンテーブルに格納する手段と、
前記再利用される通信スケジュールを参照して、多次元シフト通信を行う手段を備えることを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置。
【請求項２】
請求項１記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置であって、
前記シフトパターンの一致を判定する手段及び多次元シフト通信スケジュールを再利用する手段は、各次元、方向を単位とし、単位毎に独立して前記多次元シフト通信スケジュールの再利用を行うことを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置。
【請求項３】
請求項１記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置であって、
前記多次元シフト通信スケジュールテーブルに格納する手段及び前記多次元シフトパターンテーブルに格納する手段は、各次元、方向を単位とし、単位毎に独立して前記多次元通信スケジュールおよび多次元通信スケジュールのシフトパターンを格納することを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置。
【請求項４】
請求項１乃至３の何れか１項に記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置であって、
前記シフト通信時に、前記多次元シフトスケジュールテーブルに一致する多次元シフト通信スケジュールが存在しない場合には、新たに通信スケジュールの生成が必要となった部分についてのみ、新規に多次元シフト通信スケジュールを生成する手段を更に備えることを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置。
【請求項５】
請求項４に記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置であって、
前記多次元シフト通信に必要な多次元通信スケジュールを、多次元シフト通信スケジュールテーブルに格納する手段と、
前記多次元シフト通信に必要な多次元通信スケジュールのシフトパターンを多次元シフトパターンテーブルに格納する手段は、
新たに通信スケジュールの生成がされた部分についてのみを対象として実行することを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置。
【請求項６】
分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法であって、
多次元シフト通信を行う配列の分割配置方法を解析するステップと、
前記解析結果にもとづき、同一の分割配置に対する多次元シフト通信スケジュールを多次元シフト通信スケジュールテーブルより検索するステップと、
前記検索を行い、同一の分割配置に対する多次元シフト通信スケジュールが存在する場合には、多次元シフトパターンテーブルを検索しシフトパターンの一致を判定するステップと、
シフトパターンの一致する多次元シフト通信スケジュールが存在する場合には、該一致する多次元シフト通信スケジュールを再利用するステップと、
前記多次元シフト通信に必要な多次元通信スケジュールを、多次元シフト通信スケジュールテーブルに格納するステップと、
前記多次元シフト通信に必要な多次元通信スケジュールのシフトパターンを多次元シフトパターンテーブルに格納するステップと、
前記再利用される通信スケジュールを参照して、多次元シフト通信を行うステップを備えることを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法。
【請求項７】
請求項６記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法であって、
前記シフトパターンの一致を判定するステップ及び多次元シフト通信スケジュールを再利用するステップは、各次元、方向を単位とし、単位毎に独立して前記多次元シフト通信スケジュールの再利用を行うことを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法。
【請求項８】
請求項６記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法であって、
前記多次元シフト通信スケジュールテーブルに格納するステップ及び前記多次元シフトパターンテーブルに格納するステップは、各次元、方向を単位とし、単位毎に独立して前記多次元通信スケジュールおよび多次元通信スケジュールのシフトパターンを格納することを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法。
【請求項９】
請求項６乃至８の何れか１項に記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法であって、
前記シフト通信時に、前記多次元シフトスケジュールテーブルに一致する多次元シフト通信スケジュールが存在しない場合には、新たに通信スケジュールの生成が必要となった部分についてのみ、新規に多次元シフト通信スケジュールを生成するステップを更に備えることを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法。
【請求項１０】
請求項９に記載の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法であって、
前記多次元シフト通信に必要な多次元通信スケジュールを、多次元シフト通信スケジュールテーブルに格納するステップと、
前記多次元シフト通信に必要な多次元通信スケジュールのシフトパターンを多次元シフトパターンテーブルに格納するステップは、
新たに通信スケジュールの生成がされた部分についてのみを対象として実行することを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方法。
【請求項１１】
分散メモリ型マルチプロセッサシステムに請求項６乃至１０の何れか１項に記載の方法を行わせるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元シフト通信を行う分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置、その方法及びそのプログラムに関し、特に通信スケジュールの再利用を行う分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化装置、その方法及びそのプログラムに関する。
【背景技術】
【０００２】
図１のような構成を有する分散メモリ型マルチプロセッサシステムにおいて、同一の多次元シフト通信が繰り返される場合、通信スケジュールを保存し、これを再利用することにより、通信を高速化する手法は従来から行われていた。（例えば、特許文献１参照）。
【０００３】
ここで、シフト通信とは各プロセッサが隣接するプロセッサに対し、一定方向にデータを送信する通信形態のことをいう。また、多次元シフト通信とは配列データの複数次元に沿った隣接要素間の通信をいう。
【０００４】
この点、多次元方向にシフト通信が行われる場合、次元や方向が毎回変化することがある。図５のＨＰＦ言語によるプログラム例を参照し説明する。
【０００５】
図５では、大きさ６４のプロセッサ構成Ｐ（４，４，４）の各要素がそれぞれ１つの計算ノードに対応するとする。
【０００６】
プロセッサＰ（ｉ，ｊ，ｋ）（１＜＝ｉ，ｊ，ｋ＜＝４）に対応する計算ノード１０１の記憶部１０３上には、
【０００７】
【数１】
2008181388.tif 000003
がそれぞれ分割配置されている。時間発展ループ中で起動されるサブルーチンＳＵＢ１中のループを計算ノード１０１上で配列Ａに対するオーナーコンピュートルール（配列Ａの要素が配置されている計算ノード上で演算を行う）により並列計算する場合、
配列Ａに対して、配列Ｂの参照Ｂ（Ｉ＋１，Ｊ＋１，Ｋ）において、１次元目の添字が上方向に１要素、２次元目の添字が上方向に１要素、ずれており、
また配列Ｂの参照Ｂ（Ｉ＋１，Ｊ−１，Ｋ）において、１次元目の添字が上方向に１要素、２次元目の添字が下方向に１要素、ずれているため、
配列Ｂの隣接する要素が分割配置されている計算ノード１０１間で、
配列Ｂの１次元目の上方向に幅１、
２次元目の下方向に幅１、上方向に幅１、
１次元目の上方向および２次元目の上方向（斜め方向）へ幅１、
１次元目の上方向および２次元目の下方向（斜め方向）へ幅１、
分の通信が必要となる。このような配列データの複数次元に沿った隣接要素間の通信を多次元シフト通信という。
【０００８】
同様に、時間発展ループ中で起動されるサブルーチンＳＵＢ２中のループを計算ノード１０１上で配列Ａに対するオーナーコンピュートルール（配列Ａの要素が配置されている計算ノード上で演算を行う）により並列計算する場合、
配列Ａに対して、配列Ｃの参照Ｃ（ｉ−１，ｊ，ｋ＋１）において、１次元目の添字が下方向に１要素、３次元目の添字が上方向に１要素、ずれているため、
配列Ｃの１次元目の上方向に幅１、下方向に幅１、
３次元目の下方向に幅１、上方向に幅１、
１次元目の上方向および３次元目の下方向（斜め方向）へ幅１、
１次元目の下方向および３次元目の上方向（斜め方向）へ幅１、
分の通信が必要となる。
【０００９】
上記の例のように、多次元方向にシフト通信が行われる場合、次元や方向が毎回変化することがある。
【特許文献１】特開平０９−３３０３０４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
多次元方向にシフト通信が行われる場合であって上記で図５を用いて説明したように次元や方向が毎回変化するような場合には、前記の通信スケジュールを保存し、これを再利用する従来技術には問題点があった。すなわち、多次元方向にシフト通信が行われる場合、次元や方向が毎回変化すると、通信スケジュールの再利用が行えず、前回の通信スケジュールを破棄して、新たに再生成する必要がある点である。
【００１１】
これにより、通信スケジュールの生成というコストが発生することとなり、シフト通信の高速化を阻害するという問題を生じていた。
【００１２】
そこで、本発明は、毎回シフト通信次元やシフト通信方向、シフト通信対象の配列が変化するような場合、またはシフト通信が異なる手続中で発生する場合でも、通信の高速化を図る装置、その方法、そのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方式であって、多次元シフト通信を行う配列の分割配置方法を解析する手段と、前記解析結果にもとづき、同一の分割配置に対する多次元シフト通信スケジュールを多次元シフト通信スケジュールテーブルより検索する手段と、前記検索を行い、同一の分割配置に対する多次元シフト通信スケジュールが存在する場合は、多次元シフトパターンテーブルを検索しシフトパターンの一致を判定する手段と、シフトパターンの一致する多次元シフト通信スケジュールが存在する場合には、該一致する多次元シフト通信スケジュールを再利用する手段と、前記多次元シフト通信に必要な多次元通信スケジュールを、多次元シフト通信スケジュールテーブルに格納する手段と、前記多次元シフト通信に必要な多次元通信スケジュールのシフトパターンを多次元シフトパターンテーブルに格納する手段と、前記再利用される通信スケジュールを参照して、多次元シフト通信を行う手段を備えることを特徴とする分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方式が提供される。
【００１４】
上記の分散メモリ型マルチプロセッサシステムの多次元シフト通信高速化方式において、
前記シフトパターンの一致を判定する手段及び多次元シフト通信スケジュールを再利用する手段は、各次元、方向を単位とし、単位毎に独立して前記多次元シフト通信スケジュールの再利用を行うようにしてもよい。
【発明の効果】
【００１５】
本発明によれば、配列の分割配置方法に１対１に対応する多次元シフトテーブル中に、通信スケジュールを各次元、方向を単位とし、単位毎に独立に生成、保存することにより、多次元シフト通信時の通信スケジュールが部分的に独立に再利用可能となり、毎回シフト通信次元やシフト通信方向、シフト通信対象の配列が変化するような場合、またはシフト通信が異なる手続中で発生する場合でも分割配置方法が同じであれば、通信スケジュール生成コストの削減を行うことが可能となる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の最良の形態について図面を用いて説明する。
【００１７】
まず、図１および図２を用い、構成を説明する。
【００１８】
図１において、分散メモリ型マルチプロセッサシステム１００上で、配列データが、計算ノード１０１の記憶部１０３上に分割配置されている。該配列データを利用・定義するプログラムが計算部１０２上で実行される際に、配列の隣接する要素が分割配置されている計算ノード１０１間で、計算ノード間通信手段を経由した多次元方向へのシフト通信が行われる。
【００１９】
次に、図２において、多次元シフト通信手段２００は、マッピング解析手段２０１、通信スケジュール再利用手段２０２、多次元シフトパターンマッチング手段２０３、通信スケジュール生成手段２０４、多次元シフト通信実行手段２０５を備える。
【００２０】
図２において、多次元シフト通信手段２００は、上記マッピング解析手段２０１によって検出された分割配置と同一の分割配置に対する通信スケジュールが多次元シフト通信スケジュールテーブル３００に存在するか否かを検索する。
【００２１】
同一の分割配置に対する多次元シフト通信スケジュールテーブル３００が存在しない場合、通信スケジュール再利用手段２０２は、多次元シフト通信スケジュールテーブル３００および多次元シフト通信パターンテーブル４００を生成する。
【００２２】
次に、多次元シフトパターンマッチング手段２０３が、今回シフト通信が必要である各次元、各方向のための多次元シフトパターンを、多次元シフトパターンテーブル４００の、対応する方向、次元の多次元シフト通信パターンテーブルに保存し、通信スケジュール生成手段２０４の処理にすすむ。
【００２３】
同一の分割配置に対する多次元シフト通信スケジュールテーブル３００が存在する場合、多次元シフトパターンマッチング手段２０３が、多次元シフト通信パターンテーブル４００の、今回シフト通信が必要である各次元、各方向のための多次元シフト通信パターンテーブルを検索し、今回必要な多次元シフト通信の、各次元、各方向の多次元シフト通信パターンが、前回行った多次元シフト通信の対応する次元、方向の多次元シフトパターンと一致するかどうかを判定する。
【００２４】
一致する場合は当該一致する次元、当該一致する方向用の多次元シフト通信スケジュールは当該一致する次元、方向毎に再利用される。
【００２５】
一致しない場合は多次元シフトパターンマッチング手段２０３が、多次元シフト通信パターンテーブル４００の、当該次元、当該方向用の多次元シフト通信パターンテーブに、
今回の当該次元、当該方向のための多次元シフト通信パターンを保存し、
通信スケジュール生成手段２０４の処理に進む。
【００２６】
通信スケジュール生成手段２０４は、新たに通信スケジュールの生成が必要となった多次元シフト通信の次元、方向についてのみ、通信スケジュールを生成し、多次元シフト通信スケジュールテーブル３００の当該次元、当該方向のシフト通信スケジュールテーブルに登録する。
【００２７】
最後に、シフト通信実行手段２０５が、生成された通信スケジュール、または再利用される通信スケジュールを参照して、必要なシフト通信を行う。
【００２８】
次に、本実施例の全体の動作について、詳細に説明する。
【００２９】
基本的構成は、前記、図１を用いて説明した構成と同様であり、分散メモリ型マルチプロセッサシステム１００上で、配列データが、計算ノード１０１の記憶部１０３上に分割配置されている。該配列データを利用・定義するプログラムが計算部１０２上で実行される際に、配列の隣接する要素が分割配置されている計算ノード１０１間で、計算ノード間通信手段を経由した多次元方向へのシフト通信が行われるとする。
【００３０】
図５のＨＰＦ言語によるプログラム例を参照すると、 時間発展ループ中で、シフト通信を含むサブルーチンＳＵＢ１、ＳＵＢ２が繰り返し呼び出されている。 
ここで、図５に出現する配列Ａ、Ｂ、Ｃは、大きさ６４のプロセッサ構成P（４，４，４，）の各要素が、それぞれ１つの計算ノードに対応すると考えると、 プロセッサP(ｉ，ｊ，ｋ) (１＜＝ｉ，ｊ，ｋ＜＝４)に対応する計算ノード１０１の記憶部１０３上には、
【００３１】
【数２】
2008181388.tif 000004
が、それぞれ分割配置されている。
【００３２】
ここで、図５のサブルーチンＳＵＢ１中のループを計算手段上で配列Ａに対するオーナーコンピュートルール(配列Ａの要素が配置されている計算ノード上で演算を行う)により並列計算する場合について説明する。
【００３３】
配列Ａに対して、配列Ｂの参照Ｂ（Ｉ＋１，Ｊ＋１，Ｋ）において、１次元目の添字が上方向に１要素、２次元目の添字が上方向に１要素、ずれており、
また配列Ｂの参照Ｂ（Ｉ＋１，Ｊ−１，Ｋ）において、１次元目の添字が上方向に１要素、２次元目の添字が下方向に１要素、ずれている。
【００３４】
よって、配列Ｂの隣接する要素が分割配置されている計算ノード１０１間で、配列Ｂの
１次元目の上方向に幅１、
２次元目の下方向に幅１、上方向に幅１、
１次元目の上方向および２次元目の上方向（斜め方向）へ幅１、
１次元目の上方向および２次元目の下方向（斜め方向）へ幅１、分の通信が必要となる。
【００３５】
同様に、時間発展ループ中で起動されるサブルーチンＳＵＢ２中のループを計算ノード１０１上で配列Ａに対するオーナーコンピュートルール（配列Ａの要素が配置されている計算ノード上で演算を行う）により並列計算する場合、
配列Ａに対して、配列Ｃの参照Ｃ（ｉ−１，ｊ，ｋ＋１）において、１次元目の添字が下方向に１要素、３次元目の添字が上方向に１要素、ずれている。
よって配列Ｃの１次元目の上方向に幅１、下方向に幅１、３次元目の下方向に幅１、上方向に幅１、１次元目の上方向および３次元目の下方向（斜め方向）へ幅１、１次元目の下方向および３次元目の上方向（斜め方向）へ幅１、分の通信が必要となる。
【００３６】
図５のサブルーチンＳＵＢ１が初めて起動された時、その中のループが並列実行される直前に起動される図２のシフト通信手段２００のマッピング解析手段２０１は、シフト対象の配列データＢの分割配置方法を解析する。
【００３７】
次に、通信スケジュール再利用手段２０２は、 マッピング解析手段２０１により特定された配列データＢの分割配置に対応する多次元シフト通信スケジュールテーブル３００が生成されておらず、従って、配列データＢに対して必要な、シフト通信スケジュールも生成されていないことを認識し、多次元シフト通信スケジュールテーブル３００および多次元シフト通信パターンテーブル４００を生成して、多次元シフトパターンマッチング手段２０３を起動する。
【００３８】
該多次元シフトパターンマッチング手段２０３は、上方向多次元シフト通信パターンテーブル４０１の、１次元目多次元シフト通信パターンテーブル４０３に、１次元目の上方向シフト幅１を保存し、２次元目多次元シフト通信パターンテーブル４０４に、２次元目の上方向シフト幅１、および１次元目の上下方向のシフト幅１、０をそれぞれ保存する。
【００３９】
また、下方向多次元シフト通信パターンテーブル４０２の、２次元目多次元シフト通信パターンテーブル４１１に、２次元目の下方向シフト幅１、および１次元目の上下方向のシフト幅１、０をそれぞれ保存する。
【００４０】
次に、通信スケジュール生成手段２０４は、配列データＢに対して必要な、１次元目の上方向に幅１、２次元目の下方向に幅１、上方向に幅１、分のシフト通信スケジュールをそれぞれ生成する。
【００４１】
その際、１次元目の上方向および２次元目の上方向（斜め方向）へ幅１のシフト通信は、まず、１次元目シフト通信を行った後、１次元目の上方向シフト通信時に受信側となったプロセッサが、２次元目の上方向のシフト通信時に併せて送信するため、２次元目の上方向用の通信スケジュールに組込まれる。
【００４２】
また、１次元目の上方向および２次元目の下方向（斜め方向）へ幅１のシフト通信は、まず、１次元目シフト通信を行った後、１次元目の上方向シフト通信時に受信側となったプロセッサが、２次元目の下方向のシフト通信時に併せて送信するため、２次元目の下方向用の通信スケジュールに組込まれる。
【００４３】
更に、生成した通信スケジュールを、配列データＢの分割配置方法と同一の分割配置方法を持つ配列に対する多次元シフト通信スケジュールテーブル３００の、１次元目の上方向シフト通信スケジュールテーブル３０１、２次元目の上方向シフト通信スケジュールテーブル３０３、２次元目の下方向シフト通信スケジュールテーブル３０４、に登録する。
【００４４】
加えて、シフト通信実行手段２０５は、生成された多次元通信スケジュールテーブル３００中の、１次元目上方向シフト通信スケジュール３０３、に基づいて、１次元目方向のシフト通信を行った後、２次元目上方向シフト通信スケジュール３０３および２次元目下方向シフト通信スケジュール３０４、に基づいて、２次元目方向のシフト通信、および１次元目の上方向および２次元目の上方向（斜め方向）へ幅１、１次元目の上方向および２次元目の下方向（斜め方向）へ幅１のための通信を併せて行うことにより、配列データＢに対する多次元シフト通信を完了する。
【００４５】
次に、図５のサブルーチンＳＵＢ２が初めて起動された時、ループが並列実行される直前に図２のシフト通信手段２００のマッピング解析手段２０１が起動される、そしてマッピング解析手段２０１は、シフト対象の配列データＣの分割配置方法を解析する。
【００４６】
次に、通信スケジュール再利用手段２０２は、マッピング解析手段２０１により特定された配列データＣの分割配置方法と同一の分割配置方法に対する多次元シフト通信スケジュールテーブル３００を検索し、図５のサブルーチンＳＵＢ１が初めて起動された時に生成された多次元シフト通信スケジュールテーブル３００と多次元シフト通信パターンテーブル４００が、Ｃと同一の分割配置方法に対応するものであることを検出する。
【００４７】
一方、多次元シフト通信パターンマッチング手段２０３は、上記多次元シフト通信パターンテーブル４００の、上方向多次元シフト通信パターンテーブル４０１の、１次元目多次元シフト通信パターンテーブル４０３に保存されている１次元目上方向のシフトパターンは幅１である。
【００４８】
よって、今回必要な１次元目上方向のシフトパターンと一致する。
【００４９】
このため、多次元シフト通信スケジュールテーブル３００の１次元目上方向シフト通信スケジュールテーブル３０１に保存されている１次元目上方向の通信スケジュールが再利用可能であることを検出する。
【００５０】
また、３次元目多次元シフト通信パターンテーブル４０５には、前回のシフトパターンは登録されていないため、今回必要な多次元シフト通信パターンである３次元目の上方向シフト幅１、２次元目の上下方向のシフト幅０、０、および１次元目の上下方向のシフト幅０、１をそれぞれ保存する。
【００５１】
加えて、下方向多次元シフト通信パターンテーブル４０２の、１次元目多次元シフト通信パターンテーブル４１１には、前回のシフトパターンは登録されていないため、今回必要な多次元シフト通信パターンである１次元目下方向のシフトパターン１を保存する。
【００５２】
更に、３次元目多次元シフト通信パターン記憶手段４１３に、前回のシフトパターンは登録されていないため、今回必要な多次元シフト通信パターンである３次元目の下方向シフト幅１、２次元目の上下方向のシフト幅０、０、および１次元目の上下方向のシフト幅１、０をそれぞれ保存する。
【００５３】
次に、通信スケジュール生成手段２０４は、再利用可能な通信スケジュールが存在しない１次元目の下方向に幅１、３次元目の下方向に幅１、上方向に幅１のシフト通信スケジュールをそれぞれ生成する。
【００５４】
その際、１次元目の上方向および３次元目の下方向（斜め方向）へ幅１のシフト通信は、まず、１次元目方向のシフト通信を行った後、１次元目の上方向のシフト通信時に受信側となったプロセッサが、３次元目の下方向のシフト通信時に併せて送信するため、３次元目の下方向用の通信スケジュールに組込まれる。
【００５５】
また、１次元目の下方向および３次元目の上方向（斜め方向）へ幅１のシフト通信は、まず、１次元目方向のシフト通信を行った後、１次元目の下方向のシフト通信時に受信側となったプロセッサが、３次元目の上方向のシフト通信時に併せて送信するため、３次元目の上方向用の通信スケジュールに組込まれる。
【００５６】
一方、今回新たに生成した通信スケジュールを、配列データＣの分割配置方法と同一の分割配置方法を持つ配列に対する多次元シフト通信スケジュールテーブル３００の、１次元目の下方向シフト通信スケジュールテーブル３０２、３次元目の上方向シフト通信スケジュールテーブル３０５、３次元目の下方向シフト通信スケジュールテーブル３０６に登録する。
【００５７】
次に、シフト通信実行手段２０５は、多次元シフト通信スケジュールテーブル３００中の、１元目上方向シフト通信スケジュールテーブル３０１、１元目下方向シフト通信スケジュールテーブル３０２に基づいて、１次元目の上下方向のシフト通信を行った後、３元目上方向シフト通信スケジュールテーブル３０５、３元目下方向シフト通信スケジュールテーブル３０６に基づいて、３次元目の上下方向のシフト通信、および１次元目の上下方向および３次元目の上方向（斜め方向）へ幅１、１次元目の上下方向および３次元目の下方向（斜め方向）へ幅１のための通信を併せて行うことにより、配列データＣに対するシフト通信を実行する。
【００５８】
図５のサブルーチンＳＵＢ１が２回目以降起動され、ループが並列実行される際には、ループ直前に起動されるシフト通信手段２００のマッピング解析手段２０１がシフト対象の配列データＢの分割配置方法を解析することにより、通信スケジュール再利用手段２０２は、マッピング解析手段２０１により特定された配列データＢの分割配置方法と同一の分割配置方法に対する多次元シフト通信スケジュールテーブル３００と多次元シフト通信パターンテーブル４００が存在することを検出する。
【００５９】
多次元シフトパターンマッチング手段２０３は、上記多次元シフト通信パターンテーブル４００に登録されている１次元目上方向用の多次元シフト通信パターン、２次元目上方向用の多次元シフト通信パターン、２次元目下方向用の多次元シフト通信パターンが、今回必要な多次元シフト通信パターンと一致することを検出する。すなわち、上方向多次元シフト通信パターンテーブル４０１の、１次元目シフト通信パターンテーブル４０３に、１次元目上方向のシフト幅１が設定されている。
【００６０】
更に、２次元目多次元シフト通信パターンテーブル４０４に、２次元目上方向のシフト幅１、１次元目上方向のシフト幅１、１次元目下方向のシフト幅０が設定されている。
【００６１】
加えて、下方向多次元シフト通信パターンテーブル４０２の、２次元目多次元シフト通信パターンテーブル４１１に２次元目下方向のシフト幅１、１次元目上方向のシフト幅１、１次元目下方向のシフト幅０が設定されている。
【００６２】
以上より、多次元シフト通信スケジュールテーブル３００に保存されている通信スケジュールが、各次元、方向を単位とし単位毎に１対１に対応する、今回必要なシフト通信と同一のシフトパターンであることが検出される。
【００６３】
次に、シフト通信実行手段２０５は、多次元シフト通信スケジュールテーブル３００に保存されている１次元目上方向シフト通信スケジュールテーブル３０１に基づいて、１次元目方向のシフト通信を行った後、２次元目上方向シフト通信スケジュールテーブル３０３および２次元目下方向シフト通信スケジュールテーブル３０４に基づいて、２次元目方向のシフト通信、および１次元目の上方向および２次元目の上方向（斜め方向）へ幅１、１次元目の上方向および２次元目の下方向（斜め方向）へ幅１のための通信を併せて行うことにより、配列データＢに対して必要な多次元シフト通信を行う。
【００６４】
その後、図５のサブルーチンＳＵＢ２が２回目以降起動され、ループが並列実行される際には、ループ直前に起動されるシフト通信手段２００のマッピング解析手段２０１がシフト対象の配列データＣの分割配置方法を解析することにより、通信スケジュール再利用手段２０２は、マッピング解析手段２０１により特定された配列データＣの分割配置方法と同一の分割配置方法に対するシフト通信スケジュールテーブル３００と多次元シフト通信パターンテーブル４００が存在することを検出する。
【００６５】
次に、多次元シフト通信パターンマッチング手段２０３は、上記多次元シフト通信パターンテーブル４００を検索する。
そして、１次元目上方向用の多次元シフト通信パターン、１次元目下方向用の多次元シフト通信パターン、３次元目上方向用の多次元シフト通信パターン、３次元目下方向用の多次元シフト通信パターンが、今回必要な多次元シフト通信パターンと一致することを検出する。
【００６６】
すなわち、上記多次元シフト通信パターンテーブル４００の、上方向多次元シフト通信パターンテーブル４０１の、１次元目多次元シフト通信パターンテーブル４０３に保存されている前回の１次元目上方向のシフトパターンが、シフト幅１であるため、今回の多次元シフトパターンと一致することを検出する。
【００６７】
更に、３次元目多次元シフト通信パターンテーブル４０５に保存されている前回の３次元目上方向のシフトパターンが、３次元目上方向のシフト幅１，２次元目上方向のシフト幅０、２次元目下方向のシフト幅０、１次元目上方向のシフト幅０、１次元目下方向のシフト幅１、であるため、今回の多次元シフトパターンと一致することを検出する。
【００６８】
また、下方向多次元シフト通信パターンテーブル４０２の、１次元目多次元シフト通信パターンテーブル４１０に保存されている前回のシフト通信パターンが、１次元目下方向のシフト幅が１であるため、今回の多次元シフトパターンと一致することを検出する。
そして、３次元目多次元シフト通信パターンテーブル４１２に保存されている、前回の３次元目の下方向のシフトパターンが、３次元目下方向のシフト幅１、２次元目上方向のシフト幅０、２次元目下方向のシフト幅０１次元目上方向のシフト幅１、１次元目下方向のシフト幅０であるため、今回の多次元シフトパターンと一致することを検出する。
【００６９】
したがって、今回の多次元シフト通信において、全ての次元、方向において、必要な多次元シフト通信スケジュールが既に生成されていることを検出することとなる。
【００７０】
次に、シフト通信実行手段２０５は、多次元通信スケジュールテーブル３００中の、１元目上方向シフト通信スケジュール３０１、１元目下方向シフト通信スケジュール３０２に基づいて、１次元目方向のシフト通信を行った後に、３元目上方向シフト通信スケジュール３０５、３元目下方向シフト通信スケジュール３０６に基づいて、配列データＣに対する３次元目方向のシフト通信、および１次元目の上下方向および３次元目の上方向（斜め方向）へ幅１、１次元目の上下方向および３次元目の下方向（斜め方向）へ幅１のための通信を併せて実行する。
【００７１】
以後、図５のサブルーチンＳＵＢ１、サブルーチンＳＵＢ２が繰り返し起動された際は、多次元シフト通信パターンテーブル４００に保存されている前回の多次元シフト通信パターンが、今回必要な多次元シフト通信パターンと常に一致することとなる。
【００７２】
そのため、多次元シフト通信スケジュールテーブル３００に保存されているシフト通信のスケジュールは常に再利用可能であることがわかり、スケジュール生成を改めて行うことなくシフト通信を実行することができる。
【００７３】
このように、必要なシフト通信の対象配列、対象次元や方向が毎回変化したり、異なる手続にまたがっていても、分割配置方法が同じであれば、通信スケジュールを各次元、方向を単位とし、単位毎に独立して生成し、多次元シフト通信スケジュールテーブル３００中に、通信スケジュールを各次元、各方向独立に単位毎に保存すると共に、多次元シフト通信パターンテーブル４００に、各次元、各方向独立に前回の多次元シフト通信パターンを保存しておくことにより、各次元、各方向毎に、通信スケジュールの再利用を行うことが可能になる。これにより、通信スケジュール生成のコストを削減し、高速にシフト通信を行うことができる。
【００７４】
以上より得られる本発明の効果は、多次元方向へのシフト通信の対象配列、対象次元や方向が毎回変化する場合や、異なる手続にまたがっている場合でも、分割配置方法が同じであれば、シフト通信を高速化できることである。
【００７５】
その理由は上述のように、配列の分割配置方法に１対１に対応する多次元シフト通信スケジュールテーブル中に、通信スケジュールを各次元、各方向独立に生成、保存するとともに、多次元シフト通信パターンテーブルに、当該次元、当該方向のシフト幅、および当該次元より小さな次元の上下方向のシフト幅を保存しておくことにより、多次元シフト通信時の通信スケジュールが部分的に独立に再利用可能となり、該再利用により通信スケジュール生成のコストを削減できるためである。
【図面の簡単な説明】
【００７６】
【図１】本発明の構成例を示す図である。
【図２】多次元シフト通信手段の構成例を示す図である。
【図３】多次元シフト通信スケジュールテーブルを示す概念図である。
【図４】多次元シフト通信パターンテーブルを示す概念図である。
【図５】HPF言語によるプログラム例を示す図である。
【符号の説明】
【００７７】
１００  分散メモリ型マルチプロセッサシステム
１０１  計算ノード
１０２  計算部
１０３  記憶部
２００  多次元シフト通信手段
２０１  マッピング解析手段
２０２  通信スケジュール再利用手段
２０３  多次元シフトパターンマッチング手段
２０４  通信スケジュール生成手段
２０５  多次元シフト通信実行手段
３００  多次元シフト通信スケジュールテーブル
３０１  １次元目上方向シフト通信スケジュールテーブル
３０２  １次元目下方向シフト通信スケジュールテーブル
３０３  ２次元目上方向シフト通信スケジュールテーブル
３０４  ２次元目下方向シフト通信スケジュールテーブル
３０５  ３次元目上方向シフト通信スケジュールテーブル
３０６  ３次元目下方向シフト通信スケジュールテーブル
３０７  ４次元目上方向シフト通信スケジュールテーブル
３０８  ４次元目下方向シフト通信スケジュールテーブル
３０９  ５次元目上方向シフト通信スケジュールテーブル
３１０  ５次元目下方向シフト通信スケジュールテーブル
３１１  ６次元目上方向シフト通信スケジュールテーブル
３１２  ６次元目下方向シフト通信スケジュールテーブル
３１３  ７次元目上方向シフト通信スケジュールテーブル
３１４  ７次元目下方向シフト通信スケジュールテーブル
４００  多次元シフト通信パターンテーブル
４０１  上方向多次元シフト通信パターンテーブル
４０２  下方向多次元シフト通信パターンテーブル
４０３  １次元目多次元シフト通信パターンテーブル
４０４  ２次元目多次元シフト通信パターンテーブル
４０５  ３次元目多次元シフト通信パターンテーブル
４０６  ４次元目多次元シフト通信パターンテーブル
４０７  ５次元目多次元シフト通信パターンテーブル
４０８  ６次元目多次元シフト通信パターンテーブル
４０９  ７次元目多次元シフト通信パターンテーブル
４１０  １次元目多次元シフト通信パターンテーブル
４１１  ２次元目多次元シフト通信パターンテーブル
４１２  ３次元目多次元シフト通信パターンテーブル
４１３  ４次元目多次元シフト通信パターンテーブル
４１４  ５次元目多次元シフト通信パターンテーブル
４１５  ６次元目多次元シフト通信パターンテーブル
４１６  ７次元目多次元シフト通信パターンテーブル
【図１】
2008181388.tif 000005
【図２】
2008181388.tif 000006
【図３】
2008181388.tif 000007
【図４】
2008181388.tif 000008
【図５】
2008181388.tif 000009