(57)【特許請求の範囲】
【請求項１】
計算手段と記憶手段とを有する計算ノードを複数備え、前記複数の記憶手段は部分配列データを記憶し、前記計算手段は前記部分配列データを使用・定義するプログラムの並列ループ処理を実行する、分散メモリ型マルチプロセッサシステムであって、
前記並列ループの処理を実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出するアクセスパタン検出手段と、
前記検出した並列ループネストに対して、当該並列ループネスト中に出現するデータの配列を解析し、前記プログラムにおける並列化の基準配列と同一のマッピングを有する配列を抽出するデータマッピング解析手段と、
前記データマッピング解析手段で抽出された配列のアクセスパタンを選択するアクセスパタン選択手段と、
前記検出した並列ループネストに対して、前記並列化の基準配列の分散次元における基準アクセスパタンの添字と、前記選択したアクセスパタンの前記分散次元と対応する次元の添字とに基づいて、計算手段が前記並列ループの処理における制御変数の変動範囲で前記選択したアクセスパタンによりアクセスした場合、翻訳時に所定の条件に基づいて他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できるか否か不明と判断したアクセスパタンについては、実行時に前記所定の条件に基づいて他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できないと判断したアクセスパタンについては、前記計算ノード間で部分配列データをコピーするための通信を行う通信生成手段と、
を備える、分散メモリ型マルチプロセッサシステム。
【請求項２】
計算手段と記憶手段とを有する計算ノードを複数備え、前記複数の記憶手段は部分配列データを記憶し、前記計算手段は前記部分配列データを使用・定義するプログラムの並列ループ処理を実行する、分散メモリ型マルチプロセッサシステムの通信抑制方法であって、
前記並列ループの処理を実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出するステップと、
前記検出した並列ループネストに対して、当該並列ループネスト中に出現するデータの配列を解析し、前記プログラムにおける並列化の基準配列と同一のマッピングを有する配列を抽出するステップと、
前記抽出された配列のアクセスパタンを選択するステップと、
前記検出した並列ループネストに対して、前記並列化の基準配列の分散次元における基準アクセスパタンの添字と、前記選択したアクセスパタンの前記分散次元と対応する次元の添字とに基づいて、計算手段が前記並列ループの処理における制御変数の変動範囲で前記選択したアクセスパタンによりアクセスした場合、翻訳時に所定の条件に基づいて他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できるか否か不明と判断したアクセスパタンについては、実行時に前記所定の条件に基づいて他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できないと判断したアクセスパタンについては、前記計算ノード間で部分配列データをコピーするための通信を行うステップと、
を有する、分散メモリ型マルチプロセッサシステムの通信抑制方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散メモリ型マルチプロセッサシステム及び分散メモリ型マルチプロセッサシステムの通信抑制方法に関する。
【背景技術】
【０００２】
複数の計算ノードを有する分散メモリ型マルチプロセサシステムが知られている。この分散メモリ型マルチプロセサシステム内の複数の計算ノードには、それぞれ記憶手段及び計算手段が設けられている。各記憶手段には配列データが分割して配置される。また、各計算手段は、各記憶手段に分割して配列されたデータを使用・定義するプログラム中のループを並列実行するようになっている。このループが並列実行される際には、特定の配列（ループ並列化の基準配列）の特定のアクセスパタン（ループ並列化の基準アクセスパタン）を基準として処理が行われる。
【０００３】
より詳細には、各計算ノードで参照される配列要素のアクセスパタンが基準配列と異なっている場合には、並列ループを処理する直前に、参照される配列全体がテンポラリ配列にコピーされ、並列ループの処理中は、テンポラリ配列に対して参照が行われ、並列ループ実行後に、テンポラリ配列から元の定義される配列へコピーして値が書き戻される、という処理が行われている。
【０００４】
また、分散メモリ型プロセッサシステムにおいて、ループの繰り返し処理時にアクセスされる配列要素のアクセス方法を調査し、その調査結果に応じてデータ転送処理を挿入する位置を決定することにより、ループの並列化において発生するデータ転送を削減しオーバヘッドを減らすことでデータ分散プログラムの実行性能を上げる技術が知られている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−３２８８７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記分散メモリ型プロセッサシステムでは、各計算ノードで参照される配列要素のアクセスパタンが基準配列と異なっている場合には、テンポラリ配列を利用するためのメモリ容量が必要になると共に、並列ループ実行の前後において、ループ中で参照される配列とテンポラリ配列との間で通信を伴うコピーを行う必要がある。
【０００７】
例えば、図６に示すように、基準アクセスパタンとアクセスパタンが異なる配列ａ（：，２：１００：５０），ｂ（：，２：１００：５０）を並列ループ直前にそれぞれテンポラリ配列ｔ＿ａ，ｔ＿ｂにコピーし、並列ループ中では、テンポラリ配列ｔ＿ａ，ｔ＿ｂに対して参照を行い、並列ループ実行後に、テンポラリ配列ｔ＿ａから定義される元の配列ａ（：，２：１００：５０）へコピーして値を書き戻す、という方法で並列処理が行われる。
【０００８】
このため、テンポラリ配列ｔ＿ａ，ｔ＿ｂを利用するためのメモリ容量が必要になると共に、並列ループ処理を実行する前後において、配列ａ（：，２：１００：５０），ｂ（：，２：１００：５０）とテンポラリ配列ｔ＿ａ，ｔ＿ｂとの間で通信を伴うコピーを必要とする。したがって、分散メモリ型プロセッサシステムでは、メモリ領域が余分に必要になると共に並列ループ処理を高速に実行できないという問題が生じていた。
【０００９】
一方、上記特許文献１の技術では、ループの繰り返し処理において、アクセスされる配列要素のアクセス方法の調査結果に応じてデータ転送処理を挿入する位置を決定するものであるため、既述の問題を解決することができない。
【００１０】
本発明は、上記事情に鑑みてなされたものであり、その目的は、分割配置された配列データを使用・定義するプログラム中のループが並列実行される際に、メモリ領域を節約すると共に並列ループ処理を高速に実行することができる分散メモリ型マルチプロセッサシステム及び分散メモリ型マルチプロセッサシステムのデータ処理方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明は、計算手段と記憶手段とを有する計算ノードを複数備え、前記複数の記憶手段は部分配列データを記憶し、前記計算手段は前記部分配列データを使用・定義するプログラムの並列ループ処理を実行する、分散メモリ型マルチプロセッサシステムであって、前記並列ループの処理を実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出するアクセスパタン検出手段と、前記検出した並列ループネストに対して、当該並列ループネスト中に出現するデータの配列を解析し、前記プログラムにおける並列化の基準配列と同一のマッピングを有する配列を抽出するデータマッピング解析手段と、前記データマッピング解析手段で抽出された配列のアクセスパタンを選択するアクセスパタン選択手段と、前記検出した並列ループネストに対して、前記並列化の基準配列の分散次元における基準アクセスパタンの添字と、前記選択したアクセスパタンの前記分散次元と対応する次元の添字とに基づいて、計算手段が前記並列ループの処理における制御変数の変動範囲で前記選択したアクセスパタンによりアクセスした場合、他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できないと判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行う通信生成手段と、を備えるものである。
【発明の効果】
【００１２】
本発明によると、分割配置された配列データを使用・定義するプログラム中のループが並列実行される際に、メモリ領域を節約すると共に並列ループ処理を高速に実行することができる分散メモリ型マルチプロセッサシステム及び分散メモリ型マルチプロセッサシステムのデータ処理方法を提供できる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態に係る分散メモリ型マルチプロセッサシステムの構成を示す図である。
【図２】同実施の形態に係る通信抑制手段を説明するための図である。
【図３】同実施の形態に係る通信抑制の判定の条件を説明するための図である。
【図４】同実施の形態に係るＨＰＦ言語のプログラムの一例を示す図である。
【図５】同実施の形態に係る分散配置された配列の一例を示す図である。
【図６】従来例におけるプログラムの並列実行方法の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら本発明の実施の形態について説明する。
【００１５】
図１は、分散メモリ型マルチプロセッサシステム１００の構成を示す図である。図１に示すように、分散メモリ型マルチプロセッサシステム１００は、複数の計算ノード１０１を有している。また、各計算ノード１０１は、計算手段１０２と、記憶手段１０３とをそれぞれ有している。さらに、各計算ノード１０１は、計算ノード間通信手段１０４により相互に通信可能となるように接続されている。
【００１６】
分散メモリ型マルチプロセッサシステム１００で実行されるプログラムで用いる配列データは、各計算ノード１０１の記憶手段１０３に部分配列データとして分割配置されている。
【００１７】
また、分散メモリ型マルチプロセッサシステム１００内のある計算ノード１０１の計算手段１０２が演算を実行する場合、当該計算手段１０２は必要に応じて演算に必要な部分配列データを他の計算ノード１０１の記憶手段１０３から計算ノード間通信手段１０４を経由した通信により取得しながら演算を行う。
【００１８】
図２は、計算手段１０２が計算ノード間通信手段１０４を経由した通信を行って演算を行う際に実行される通信抑制手段２００の構成を説明するための図である。
【００１９】
図２に示すように、分散並列プログラムの通信抑制手段２００は、アクセス検出手段である並列化基準アクセスパタン解析手段２０１と、データマッピング解析手段２０２と、アクセスパタン選択手段であるアクセスパタン解析手段２０３と、通信生成手段２０４とを有している。
【００２０】
通信抑制手段２００は、分散メモリ型マルチプロセッサシステム１００上で実行されるプログラム中に、並列化の基準配列の基準アクセスパタンに基づいて並列化される並列化対象ループを含む並列ループネストが複数存在する場合に実行される。より詳細な説明を以下にする。
【００２１】
並列化基準アクセスパタン解析手段２０１は、並列化対象ループを実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出する。
【００２２】
より詳細には、並列化基準アクセスパタン解析手段２０１は、並列ループネストに対して、並列化の基準配列の各分散次元における基準アクセスパタンの添字ｓが、図３における条件３０１を満たすかどうかを検査し、以下の条件３０１を満たす並列ループネストのみを通信抑制の対象となる並列ループネストとして検出する。
【００２３】
条件３０１は、図３に示すように、次の通りである。
並列化の基準配列の分散次元における、分散ブロック幅をＤ、基準アクセスパタンの添字をｓとする。
並列ループネスト中に、並列化対象ループが存在し、その制御変数をＩ、ループ初期値をＬ、ループ増分値Ｓとするとき、以下の条件を全て満たす。
添字ｓが、Ｉの一次式ｓ＝ｃ＊Ｉ＋ｏと表現でき、かつ一次式の係数ｃと、０次の項ｏは、並列ループネスト中の各ループに対して不変な式である。
分散ブロック幅Ｄは、ｃ＊Ｓの倍数である。
【００２４】
次に、データマッピング解析手段２０２は、並列化基準アクセスパタン解析手段２０１が検出した通信抑制の対象となる並列ループネストに対して、並列ループネスト中に出現する各配列のデータマッピングを解析し、分散並列プログラムにおける並列化の基準配列と同一のマッピングを持つ配列を抽出する。
【００２５】
次に、アクセスパタン解析手段２０３は、データマッピング解析手段２０２で抽出された配列のアクセスパタンを選択する。
【００２６】
より詳細には、アクセスパタン解析手段２０３は、アクセスパタン解析手段２０１が検出した通信抑制の対象となる並列ループネストに対して、次の処理を行う。アクセスパタン解析手段２０３は、データマッピング解析手段２０２が抽出した並列化の基準配列と同一のマッピングを持つ各配列の並列ループネストにおける各出現について、通信抑制対象のアクセスパタンとして選択できるか否かを、並列化の基準配列の分散次元に対応する全ての次元の添字ｓ’が、以下の条件３０２を満たすか否かを判定することにより行う。このとき、図３における条件３０２を満たす次元を通信抑制対象次元と称することとする。
【００２７】
条件３０２は、図３に示すように、次の通りである。
並列化の基準配列の分散次元における、基準アクセスパタンの添字ｓが、条件３０１を満たすとき、
並列化の基準配列の分散次元に対応する、配列の各次元の添字ｓ´に対して、以下の条件が全て成り立つ。
ｓ´＝ｃ＊Ｉ＋ｏ´と表現でき、ｏ´は、並列ループネスト中の各ループに対して不変な式である。
【００２８】
次に、通信生成手段２０４は、並列化基準アクセスパタン解析手段２０１が検出した通信抑制の対象となる並列ループネストに対し、並列化の基準配列の分散次元における基準アクセスパタンの添字と、アクセスパタン解析手段２０３が選択した各通信抑制対象アクセスパタンの通信抑制対象次元の添字とに基づいて、以下の条件３０３により翻訳時又は実行時に既述の選択したアクセスパタンの計算ノード１０１間の部分配列データをコピーするための通信の抑制が実行できるか否かを判定する。
【００２９】
条件３０３は、計算手段１０２が並列ループの処理における制御変数の変動範囲で、アクセスパタン解析手段２０３が選択したアクセスパタンによりアクセスした場合、他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断するための条件である。
【００３０】
条件３０３は、より詳細には、図３に示すように、次の通りである。
並列化の基準配列の分散次元における、基準アクセスパタンの添字ｓが、条件３０１を満たし、
並列化の基準配列の分散次元に対応する各次元の添字ｓ´が、条件３０２を満たすとする。
並列化の基準配列の分散次元は、
ｎ個のプロセッサＰ１，Ｐ２，・・・Ｐｎに分割配置されており、プロセッサＰｉに割付けられる添字の範囲が（ｌｂｉ：ｕｂｉ）であるとするとき（ｕｂｉ−ｌｂｉ＋１＝Ｄ）、
ｏ´−ｏ≧；０の場合
各プロセッサＰｉに関して、ｕｂｉ≧ｋ＊ｃ＊Ｓ＋ｃ＊Ｌ＋ｏを満たす最大の整数ｋに対して、
ｕｂｉ−（ｋ＊ｃ＊Ｓ＋ｃ＊Ｌ＋ｏ）≧ｏ´−ｏが成立する。
ｏ´−ｏ＜０の場合
各プロセッサＰｉに関して、ｌｂｉ≧ｋ＊ｃ＊Ｓ＋ｃ＊Ｌ＋ｏを満たす最小の整数ｋに対して、
（ｋ＊ｃ＊Ｓ＋ｃ＊Ｌ＋ｏ）−ｌｂｉ≧ｏ−ｏ´が成立する。
【００３１】
通信生成手段２０４は、翻訳時に全ての通信抑制対象次元において条件３０３が成り立つアクセスパタンに対しては、計算ノード１０１間の部分配列データをコピーするための通信の生成を抑制する。具体的には、通信生成手段２０４は、計算ノード１０１間の部分配列データをコピーする処理を行わないように制御する。
【００３２】
一方、通信生成手段２０４は、翻訳時には条件３０３が成り立つか否かが不明の場合には、実行時に条件３０３が成り立つかどうかを判定し、実行時に条件３０３が成り立たない場合のみ、必要な部分配列データを計算ノード１０１間でコピーするためのコードを出力する。
【００３３】
さらに、通信生成手段２０４は、以上の条件が成り立たない出現に対しては従来通り、必要な部分配列データを計算ノード１０１間でコピーするためのコードを出力する。
【００３４】
以上説明したように、分散メモリ型マルチプロセッサシステム１００は、並列化基準アクセスパタン解析手段２０１と、データマッピング解析手段２０２と、アクセスパタン解析手段２０３と、通信生成手段２０４をと備えることにより、並列ループ実行中に、各計算ノード１０１で参照される配列要素のアクセスパタンが、ループ並列化の基準配列の基準アクセスパタンと異なっている場合でも、通信を抑制可能な条件を翻訳時または実行時に判定し、翻訳時又は実行時に当該条件を満たす場合、通信を伴うコピーにより部分配列データを取得することを抑制するため、メモリ領域を節約すると共に並列ループ処理を高速に行うことができる。
【００３５】
次に、本実施の形態における分散メモリ型マルチプロセッサシステム１００の処理の一例について、詳細に説明する。なお、図４のＨＰＦ言語によるプログラム４００の一例を用いて当該処理を説明する。
【００３６】
分散メモリ型マルチプロセッサシステム１００上で実行される図４のＨＰＦ言語によるプログラムのデータａ、ｂが、計算ノード１０１の記憶手段１０３上に分割配置されている。そして、既述のように、ある計算ノード１０１の計算手段１０２が演算を実行する場合、必要に応じて演算に必要な部分配列データを他の計算ノード１０１の記憶手段１０３から計算ノード間通信手段１０４を経由した通信により取得しながら演算が行われる。
【００３７】
分散メモリ型マルチプロセッサシステム１００上で実行されるプログラム４００は、並列化の基準配列ａの基準アクセスパタンａ（：,２＊ｊ−１）に基づいて並列化される並列化対象ループ「ｄｏ  ｊ」を含むとともに、「ｄｏ  ｊ」と「ｄｏ  ｉ」の並列ループネストを含む。このため、通信抑制手段２００は、以下のように動作する。
【００３８】
なお、プログラム４００では、並列化の基準配列と基準アクセスパタンは、ＯN指示文により明示的に指定されているが、これはユ−ザによるオプション指定によって指定されるようにしても良いし、コンパイラが自動的に決定するようにしても良い。
【００３９】
図５に示すように、各配列ａ，ｂは５台のプロセッサプロセッサＰ（ｍ）（ｍ＝１，２，３，４，５）上に分割配置されている。また、各プロセッサＰ（ｍ）は、図１における計算手段１０２に対応している。さらに、並列化対象ループ「ｄｏ  ｊ」のｊ＝１〜１０をプロセッサＰ１，ｊ＝１１〜２０をプロセッサＰ２，ｊ＝２１〜３０をプロセッサＰ３，ｊ＝３１〜４０をプロセッサＰ４，ｊ＝４１〜５０をプロセッサＰ５が並列して処理するように構成されている。また、並列化対象ループ「ｄｏ  ｊ」は、並列化の基準配列ａの基準アクセスパタンａ（：,２＊ｊ−１）の要素が配置されているループのみが各プロセッサＰ（ｍ）で実行される。
【００４０】
先ず、並列化基準アクセスパタン解析手段２０１は、「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる並列ループネストに対して、並列化の基準配列ａの分散次元である２次元目において、基準アクセスパタンａ（：,２＊ｊ−１）の添字が、図３における条件３０１を満たすか否かを判定する。
【００４１】
より詳細には、並列化の基準配列ａの分散次元である２次元目において、分散ブロック幅は２０、基準アクセスパタンａ（：,２＊ｊ−１）の添字は「２＊ｊ−１」であり、「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる並列ループネスト中に、制御変数が「ｊ」である並列化対象ループ「ｄｏ  ｊ」が存在し、そのループ初期値は「１」、増分値は「１」である。したがって、以下のように条件３０１を全て満たす。
【００４２】
すなわち、基準アクセスパタンａ（：,２＊ｊ−１）の分散次元である２次元目の添字は「ｊ」の一次式として「２＊ｊ−１」と表現でき、かつ一次式の係数「２」と、０次の項「−１」は、並列ループネスト中の各ループに対して不変な式であり、また、分散ブロック幅２０が、「２＊１」の倍数である。
【００４３】
したがって、並列化基準アクセスパタン解析手段２０１は、「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる並列ループネストを、通信抑制の対象となる並列ループネストとして検出する。
【００４４】
次に、データマッピング解析手段２０２は、並列化基準アクセスパタン解析手段２０１が検出した「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる通信抑制の対象となる並列ループネストそれぞれに対し、並列ループネスト中に出現する各配列のデータマッピングを解析し、並列化の基準配列と同一のマッピングを持つ配列として、各配列ａ、ｂを抽出する。
【００４５】
次に、アクセスパタン解析手段２０３は、並列化基準アクセスパタン解析手段２０１が検出した「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる通信抑制の対象となる並列ループネストそれぞれに対し、データマッピング解析手段２０２が抽出した、並列化の基準配列と同一のマッピングを持つ各配列ａ、ｂの、並列ループネスト中における各出現ａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）が、図３に示す条件３０２に基づいて通信抑制の対象となるアクセスパタンとして選択できるか否かを判定する。
【００４６】
より詳細には、アクセスパタン解析手段２０３は、並列化の基準配列ａの分散次元である２次元目において、基準アクセスパタンａ（：,２＊ｊ−１）の添字を、並列ループネスト中の並列化対象ループの制御変数ｊの一次式として見たとき、
ａ（ｉ,２＊ｊ−１）の場合、
並列化の基準配列の分散次元に対応する２次元目の添字が、「２＊ｊ−１」であり、「−１」は並列ループネスト中の各ループに対して不変な式である。
ａ（ｉ,２＊ｊ）の場合、
並列化の基準配列の分散次元に対応する２次元目の添字が、「２＊ｊ」であり、「０」は並列ループネスト中の各ループに対して不変な式である。
ｂ（ｉ,２＊ｊ）の場合、
並列化の基準配列の分散次元に対応する２次元目の添字が、「２＊ｊ」であり、「０」は並列ループネスト中の各ループに対して不変な式である。
【００４７】
以上のように、各出現ａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）は、図３における条件３０２を満たすと判定される。
【００４８】
このため、アクセスパタン解析手段２０３は、これら出現ａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）を通信抑制の対象となるアクセスパタンとして選択する。このとき、ａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）の２次元目を通信抑制対象次元と称することにする。
【００４９】
次に、通信生成手段２０４は、並列化基準アクセスパタン解析手段２０１が検出した通信抑制の対象となる並列ループネストである「ｄｏ  ｊ」と「ｄｏ  ｉ」からなる並列ループネストそれぞれに対して、並列化の基準配列の基準アクセスパタンａ（：,２＊ｊ−１）の分散次元における添字「２＊ｊ−１」と、アクセスパタン解析手段２０３が選択した各通信抑制の対象となるアクセスパタンａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）の通信抑制の対象となる２次元目の添字と、図３における通信を抑制する条件３０３とに基づいて、翻訳時又は実行時に既述の選択したアクセスパタンの通信抑制が可能か否かを判定する。
【００５０】
なお、並列化の基準配列の分散次元は、図５に示すように、５個のプロセッサＰ（ｍ）（ｍ＝１，２，３，４，５）に分割配置されており、各プロセッサＰ（ｍ）に割付けられる添字の範囲は、（２０＊（ｍ−１）＋１：２０＊ｍ）である。
【００５１】
ａ（ｉ,２＊ｊ−１）の場合、通信生成手段２０４は、
ｏ−ｏ＝−１−（−１）＝０＞＝０であり、各プロセッサＰ（ｉ）毎に、２０＊ｉ≧；ｋ＊２＊１＋２＊１＋（−１）を満たす最大の整数１０＊ｉ−１に対して、２０＊ｉ−（（１０＊ｉ−１）＊２＊１＋２＊１＋（−１））＝１≧０が成立する（ｉ＝１，２，３，４，５）と判定する。
【００５２】
ａ（ｉ,２＊ｊ）の場合、通信生成手段２０４は、
ｏ’−ｏ＝０−（−１）＝１＞＝０であり、各プロセッサＰ（ｉ）毎に、２０＊ｉ≧；ｋ＊２＊１＋２＊１＋（−１）を満たす最大の整数１０＊ｉ−１に対して、２０＊ｉ−（（１０＊ｉ−１）＊２＊１＋２＊１＋（−１））＝１≧１が成立する（ｉ＝１，２，３，４，５）と判定する。
【００５３】
ｂ（ｉ,２＊ｊ）の場合、通信生成手段２０４は、
ｏ’−ｏ＝０−（−１）＝１＞＝０であり、各プロセッサＰ（ｉ）毎に、２０＊ｉ≧；ｋ＊２＊１＋２＊１＋（−１）を満たす最大の整数１０＊ｉ−１に対して、２０＊ｉ−（（１０＊ｉ−１）＊２＊１＋２＊１＋（−１））＝１≧１が成立する（ｉ＝１，２，３，４，５）と判定する。
【００５４】
以上のように、並列化の基準配列の基準アクセスパタンａ（：,２＊ｊ−１）の分散次元における添字「２＊ｊ−１」と、アクセスパタン解析手段２０３が選択した各通信抑制対象アクセスパタンａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）の通信抑制の対象となる２次元目（通信抑制対象次元）の添字との関係は、上記条件３０３の条件を満たすと判定される。このため、アクセスパタンａ（ｉ,２＊ｊ−１）、ａ（ｉ,２＊ｊ）、ｂ（ｉ,２＊ｊ）について、計算ノード１０１間の部分配列データをコピーするための通信は抑制される。
【００５５】
したがって、通信抑制の対象となる並列ループネストである「ｄｏ  ｊ」と「ｄｏ  ｉ」は、他の計算ノードの記憶手段から部分配列データをコピーするための通信を行わずに並列処理を実行することができる。このため、通信生成手段２０４は並列ループネストである「ｄｏ  ｊ」と「ｄｏ  ｉ」を処理する場合、部分配列データをコピーするための通信を抑制することができる。
【００５６】
以上の説明のように、分散メモリ型マルチプロセッサシステム１００は、並列ループ実行中に、各計算ノード１０１で参照される配列要素のアクセスパタンが、ループ並列化の基準配列の基準アクセスパタンと異なっている場合でも、翻訳時または実行時に通信を抑制できるか否かを判定し、この判定結果に基づいて配列データをコピーするための通信を抑制することができる。
【００５７】
したがって、分散メモリ型マルチプロセッサシステム１００は、分割配置された配列データを使用・定義するプログラム中のループが並列実行される際に、必要なメモリ領域を節約すると共に並列ループ処理を高速に実行することができる。
【００５８】
より詳細には、分散メモリ型マルチプロセッサシステム１００は、ループ並列化の前後に従来生成されていた配列とテンポラリ配列間の通信やコピーのオ−バヘッドを削減できるため、従来の技術と比較して、並列ループの実行速度を高速化できる。
【００５９】
また、分散メモリ型マルチプロセッサシステム１００は、ループ並列化時に従来生成されていたテンポラリ配列のメモリ領域を削減できるため、従来の技術と比較して使用メモリ量を削減できる。
【００６０】
なお、本発明は上述の実施の形態に限定されるものではなく、その実施に際して様々な変形が可能である。
【００６１】
上記実施の形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６２】
（付記１）
計算手段と記憶手段とを有する計算ノードを複数備え、前記複数の記憶手段は部分配列データを記憶し、前記計算手段は前記部分配列データを使用・定義するプログラムの並列ループ処理を実行する、分散メモリ型マルチプロセッサシステムであって、
前記並列ループの処理を実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出するアクセスパタン検出手段と、
前記検出した並列ループネストに対して、当該並列ループネスト中に出現するデータの配列を解析し、前記プログラムにおける並列化の基準配列と同一のマッピングを有する配列を抽出するデータマッピング解析手段と、
前記データマッピング解析手段で抽出された配列のアクセスパタンを選択するアクセスパタン選択手段と、
前記検出した並列ループネストに対して、前記並列化の基準配列の分散次元における基準アクセスパタンの添字と、前記選択したアクセスパタンの前記分散次元と対応する次元の添字とに基づいて、計算手段が前記並列ループの処理における制御変数の変動範囲で前記選択したアクセスパタンによりアクセスした場合、他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できないと判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行う通信生成手段と、
を備える、分散メモリ型マルチプロセッサシステム。
【００６３】
（付記２）
計算手段と記憶手段とを有する計算ノードを複数備え、前記複数の記憶手段は部分配列データを記憶し、前記計算手段は前記部分配列データを使用・定義するプログラムの並列ループ処理を実行する、分散メモリ型マルチプロセッサシステムの通信抑制方法であって、
前記並列ループの処理を実行する場合、計算ノード間における通信抑制の対象となる並列ループネストを検出するステップと、
前記検出した並列ループネストに対して、当該並列ループネスト中に出現するデータの配列を解析し、前記プログラムにおける並列化の基準配列と同一のマッピングを有する配列を抽出するステップと、
前記抽出された配列のアクセスパタンを選択するステップと、
前記検出した並列ループネストに対して、前記並列化の基準配列の分散次元における基準アクセスパタンの添字と、前記選択したアクセスパタンの前記分散次元と対応する次元の添字とに基づいて、計算手段が前記並列ループの処理における制御変数の変動範囲で前記選択したアクセスパタンによりアクセスした場合、他の計算ノードの記憶手段に記憶している部分配列データを使用せずに当該処理が実行できるか否かを判断し、実行できると判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行わず、実行できないと判断したアクセスパタンについては前記計算ノード間で部分配列データをコピーするための通信を行うステップと、
を有する、分散メモリ型マルチプロセッサシステムの通信抑制方法。
【産業上の利用可能性】
【００６４】
並列ループの処理を実行する分散メモリ型マルチプロセッサシステム及び分散メモリ型マルチプロセッサシステムの通信抑制方法に広く適用可能である。
【符号の説明】
【００６５】
１００・・・分散メモリ型マルチプロセッサシステム
１０１・・・計算ノード
１０２・・・計算手段
１０３・・・記憶手段
１０４・・・計算ノード間通信手段
２００・・・通信抑制手段
２０１・・・並列化基準アクセスパタン解析手段
２０２・・・データマッピング解析手段
２０３・・・アクセスパタン解析手段
２０４・・・通信生成手段
３０１〜３０３・・・条件
４００，５００・・・プログラム
【図１】
0005549861.tif 000002
【図２】
0005549861.tif 000003
【図３】
0005549861.tif 000004
【図４】
0005549861.tif 000005
【図５】
0005549861.tif 000006
【図６】
0005549861.tif 000007