(57)【要約】【課題】分散メモリ型マルチプロセッサシステムにおける並列処理を向上させるオブジェクトプログラムを生成するプログラム変換装置等を提供する。【解決手段】プログラム変換装置等１０は、定義判定部１１、割り当て判定部１２、繰り返し判定部１３、更新判定部１４、及び、境界判定部１５が、所定の条件に適合するプログラムであると判定する場合に、２つの通信を１度に処理するオブジェクトプログラム１８を生成するコード生成部１６を有する。【選択図】      図１
2014191682.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定部と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定部と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定部と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定部と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定部と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定部と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成部と
を備えるプログラム変換装置。
【請求項２】
前記更新判定部は、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定部と、
前記更新範囲が、前記定義判定部が特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定部とを有し、
前記更新判定部は、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
請求項１に記載のプログラム変換装置。
【請求項３】
前記コンピュータプログラムが前記第５プログラムである場合に、前記端点処理が前記第２配列の前記更新範囲の要素を更新しない第６プログラムであるか否かを判定する境界範囲判定部を更に備え、
前記コード生成部は、前記コンピュータプログラムが前記第６プログラムである場合に、前記オブジェクトプログラムを生成する
請求項２に記載のプログラム変換装置。
【請求項４】
前記コード生成部は、
前記第１通信処理において通信する値を一時的に記憶するバッファ領域を作成する第１命令を生成するバッファ生成部と、
前記バッファ領域における値を参照しながら、複数の計算ノードが前記更新処理を並列に行う第２命令を生成する並列コード生成部と、
前記第１通信処理における通信と、前記第２通信処理における通信と、前記第２通信処理における通信において授受した値を更新する処理とを一度に実行する第３命令を生成する通信コード生成部と、
を有し、
前記第１乃至３命令を含む前記オブジェクトプログラムを生成する
ことを特徴とする請求項１乃至請求項３のいずれかに記載のプログラム変換装置。
【請求項５】
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定ステップと、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定ステップと、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定ステップと、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定ステップと、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定ステップと、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定ステップと、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成ステップと
を含むことを特徴とするプログラム変換方法。
【請求項６】
前記更新判定ステップは、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定ステップと、
前記更新範囲が、前記定義判定ステップが特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定ステップとを含み、
前記更新判定ステップは、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
請求項５に記載のプログラム変換方法。
【請求項７】
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定処理と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定処理と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定処理と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定処理と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定処理と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定処理と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成処理とを
をコンピュータに実行させることを特徴とするプログラム変換プログラム。
【請求項８】
前記更新判定処理は、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定処理と、
前記更新範囲が、前記定義判定処理が特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定処理とを含み、
前記更新判定処理は、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
請求項７に記載のプログラム変換プログラム。
【請求項９】
前記コンピュータプログラムが前記第５プログラムである場合に、前記端点処理が前記第２配列の前記更新範囲の要素を更新しない第６プログラムであるか否かを判定する境界範囲判定処理を更に含み、
前記コード生成処理は、前記コンピュータプログラムが前記第６プログラムである場合に、前記オブジェクトプログラムを生成する
請求項８に記載のプログラム変換プログラム。
【請求項１０】
前記コード生成処理は、
前記第１通信処理において通信する値を一時的に記憶するバッファ領域を作成する第１命令を生成するバッファ生成処理と、
前記バッファ領域における値を参照しながら、複数の計算ノードが前記更新処理を並列に行う第２命令を生成する並列コード生成処理と、
前記第１通信処理における通信と、前記第２通信処理における通信と、前記第２通信処理における通信において授受した値を更新する処理とを一度に実行する第３命令を生成する通信コード生成処理と、
を含み、
前記第１乃至３命令を含む前記オブジェクトプログラムを生成する
ことを特徴とする請求項７乃至請求項９のいずれかに記載のプログラム変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム変換装置、プログラム変換方法及びプログラム変換プログラムに関し、特に、分散メモリ型マルチプロセッサシステムにおける並列処理を向上させるプログラム変換装置、プログラム変換方法及びプログラム変換プログラムに関する。
【背景技術】
【０００２】
複数の計算ノードを備えた分散メモリ型マルチプロセッサシステム８１は、それら複数の計算ノードを相互に協調させながら動作させることにより、所望の演算処理を高速に処理する。
【０００３】
図１５は、分散メモリ型マルチプロセッサシステム８１の構成を示すブロック図である。
【０００４】
図１５を参照すると、分散メモリ型マルチプロセッサシステム８１は、複数の計算ノード８３及び計算ノード８４等と、これら複数の計算ノードを相互に接続する通信ネットワーク８２（以下、単に「ネットワーク」と言う。）とを有する。各計算ノード８３及び計算ノード８４等は、演算処理を行う計算部（計算部８３−２、及び、計算部８４−２等）と、データを記憶する記憶部（記憶部８３−１、及び、記憶部８４−１等）とを有する。
【０００５】
分散メモリ型マルチプロセッサシステム８１においては、プログラムにおける配列データを記憶する場合に、該配列データが計算ノードの数と同数に分割され（以下、このように分割された各データを「分割データ」と言う。）、それらの分割データが複数の計算ノード内の記憶部に分散して記憶される。
【０００６】
各計算ノード８３及び計算ノード８４等における計算部は、主に、自計算ノードにおける記憶部が記憶する分割データについて、計算処理を行う。
【０００７】
その計算処理において、各計算ノードは、他計算ノードにおける記憶部が記憶する分割データを参照しなければならない場合もある。その場合、各計算ノードは、他計算ノードとネットワーク８２を介して通信することにより、当該データを参照する。
【０００８】
例えば、数値計算を行うプログラムにおいて、上述した計算処理と同様の処理を行う場合がある。数値計算プログラムを分散メモリ型マルチプロセッサシステム８１にて効率的に処理する場合、計算する領域を複数の小領域に分割し、それぞれの小領域における処理を各計算ノードに割り当てる領域分割法が採用されることもある。
【０００９】
数値計算において、差分法は、偏微分方程式を離散化する方法の１つのである。例えば、周期的境界条件における偏微分方程式を差分法により離散化し、その結果、得られる連立一次方程式の解を求める問題に領域分割法を適用すると、各計算ノードは、自計算ノードにおける記憶部内の分割データを更新する。その後、周期的境界条件に関する処理を担当する複数の計算ノードは、ネットワーク８２を介して、相互に参照するデータを読み取ることにより、周期的境界条件に対応するデータを更新する。
【００１０】
特許文献１乃至３は、上述した処理を行う一般的な分散メモリ型マルチプロセッサ技術を開示する。
【００１１】
特許文献１は、分散メモリ型マルチプロセッサにおける通信処理を削減する技術について開示する。特許文献１が開示する通信処理抑制方法においては、各計算ノードが他計算ノードに対して行うアクセスパタンと、アクセスするデータとが関連付けて記憶され、該アクセスパタンに合致する場合に、記憶したデータが参照される。
【００１２】
また、特許文献２が開示するマスク付き逆シフト通信方法においては、通信するデータを授受するバッファを設けることにより、ループ処理が高速に行われる。
【００１３】
さらに、特許文献３は、通信処理に関するスケジュール情報を管理し、該スケジュール情報に応じて通信処理を行う方法を開示する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１１−２３２９６６号公報
【特許文献２】特開２００９−３０１４５３号公報
【特許文献３】特開２００６−２８５５８８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
しかしながら、図１５に示した分散メモリ型マルチプロセッサシステム８１は、各計算ノードがネットワーク８２を介して他計算ノードとデータをやり取りするたびに、通信処理を行わなければならない。その通信処理に係るオーバヘッド（以下、「通信オーバヘッド」と言う。）は、分散メモリ並列処理の効率の低下を招く。従って、計算処理における通信オーバヘッドを削減することにより、分散メモリ型マルチプロセッサシステム８１の処理性能は向上する。
【００１６】
例えば、分散メモリ型マルチプロセッサシステム８１において、上述したような連立一次方程式の解を反復解法により求める場合、計算ノードは、１反復ごとに、自計算ノードが記憶する分割データに連続する要素を記憶する計算ノードと通信することにより、参照すべき値を自計算ノードに複製する。さらに、周期的境界条件における偏微分方程式を求解する場合には、上記通信に加え、１反復ごとに、周期的境界条件を処理する通信が必要である。
【００１７】
すなわち、周期的境界条件における偏微分方程式を求解する場合には、１反復ごと、複数回の通信が必要である。一般的なプログラム変換装置は、上述した処理を行うプログラムを、複数回の通信処理を逐次的に行うオブジェクトプログラムに変換する。その結果、分散メモリ型マルチプロセッサシステム８１が該オブジェクトプログラムを実行する場合には、通信オーバヘッドは顕著になり、そのため、図１５に示した分散メモリ型マルチプロセッサシステム８１は、処理性能を十分に発揮することができないという問題がある。
【００１８】
特許文献１乃至３が開示する処理方法は、周期的境界条件を満足させるために必須の通信処理を削減することはできない。従って、該処理方法は、上述した２回の通信処理における通信オーバヘッドを削減することはできない。そのため、一般的なプログラム変換装置と同様に、該処理方法によれば、分散メモリ型マルチプロセッサシステム８１は、処理性能を十分に発揮することができないという問題がある。
【００１９】
本発明の目的は、分散メモリ型マルチプロセッサシステム８１における並列処理を向上させることができるオブジェクトプログラムを生成するプログラム変換装置を提供することにある。
【課題を解決するための手段】
【００２０】
本発明に係るプログラム変換装置は、
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定部と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定部と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定部と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定部と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定部と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定部と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成部と
を備えることを特徴とする。
【００２１】
また、本発明に係るプログラム変換方法は、
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定ステップと、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定ステップと、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定ステップと、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定ステップと、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定ステップと、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定ステップと、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成ステップと
を含むことを特徴とする。
【００２２】
さらに、本発明のプログラム変換プログラムは、
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定処理と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定処理と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定処理と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新すること、及び、前記第２配列の第（・・・、ｐ＋１、・・・）乃至（・・・、２×ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、Ｋｊ−ｐ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する端点処理を実施する第４プログラムであるか否かを判定する境界判定処理と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定処理と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定処理と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成処理とを
をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２３】
本発明には、分散メモリ型マルチプロセッサシステムにおける並列処理を向上させるオブジェクトプログラムを生成することができるという効果がある。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１の実施形態に係るプログラム変換装置が有する構成を示すブロック図である。
【図２】本発明の第１の実施形態に係るプログラム変換装置における処理の流れを示すフローチャートである。
【図３】ＨＰＦ言語により記述されたプログラムの一例を示す図である。
【図４】分散メモリ型マルチプロセッサシステムにおいて、本発明の第１の実施形態に係るプログラム変換装置が、第１及び２配列をブロック状に各計算ノードに割り当てる例を示す図である。
【図５】本発明の第１の実施形態に係るプログラム変換装置により、各計算ノードが更新する処理を分担する例を表す概念図である。
【図６】各計算ノードがネットワークを介してデータを参照する一例を表す図である。
【図７】端点処理において必要な通信処理を表す一例を表す概念図である。
【図８】小領域間におけるデータを参照する通信処理と、端点処理を処理する通信処理とを一度に処理する例を表す一例を表す概念図である。
【図９】本発明の第２の実施形態に係る第１判定部が有する構成を示すブロック図である。
【図１０】本発明の第２の実施形態に係る第１判定部における処理の流れを示すフローチャートである。
【図１１】本発明の第３の実施形態に係るプログラム変換装置が有する構成を示すブロック図である。
【図１２】本発明の第３の実施形態に係るプログラム変換装置における処理の流れを示すフローチャートである。
【図１３】本発明の第４の実施形態に係るコード生成部が有する構成を示すブロック図である。
【図１４】本発明の第４の実施形態に係るコード生成部における処理の流れを示すフローチャートである。
【図１５】分散メモリ型マルチプロセッサシステムが有する構成を示すブロック図である。
【発明を実施するための形態】
【００２５】
次に、本発明について図面を参照して詳細に説明する。
【００２６】
＜第１の実施形態＞
図１は、本発明の第１の実施形態を示すブロック図である。
【００２７】
図１を参照すると、本実施形態は、プログラム変換装置１０と、記憶装置（図示せず）に記憶されたコンピュータプログラム（以下、単に「プログラム」と言う。）１７と、上記記憶装置に記憶されるオブジェクトプログラム１８とから構成される。プログラム変換装置１０は、定義判定部１１と、割り当て判定部１２と、繰り返し判定部１３と、更新判定部１４と、境界判定部１５と、コード生成部１６とを有する。
【００２８】
図２は、プログラム変換装置１０における処理の流れを示すフローチャートである。次に、図２も参照して本実施形態の動作について説明する。
【００２９】
まず、定義判定部１１は、入力されたプログラム１７における変数定義を解析する等の処理により、プログラム１７が、同じ大きさを有する２つの配列を参照もしくは更新するプログラムであるか否かを判定する（ステップＳ１）。
【００３０】
例えば、定義判定部１１は、図３に示すようなプログラム１７において、「ｒｅａｌ＿ｏｌｄ（２０），ｎｅｗ（２０）」という変数定義を参照することにより、上述した処理を行う。図３は、ハイパフォーマンスフォートラン（「Ｈｉｇｈ＿Ｐｅｒｆｏｒｍａｎｃｅ＿Ｆｏｒｔｒａｎ」。以下、単に「ＨＰＦ」とも言う。）言語により記述されたプログラム１７の一例を示す図である。この例においては、ｏｌｄとｎｅｗという２つの配列がそれぞれ２０個の要素を有するため、定義判定部１１は、該プログラム１７が同じ大きさを有する２つの配列を更新もしくは参照すると判定する（ステップＳ１にてＹＥＳと判定）。
【００３１】
以下の説明においては、配列ｏｌｄを第１配列、配列ｎｅｗを第２配列とする。
【００３２】
例えば、プログラムが第１配列と第２配列とを利用しているとする。第１配列が、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有するとする。その場合、第２配列が、例えば、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する場合に、定義判定部１１は、該プログラムが同じ大きさを有する２つの配列を参照もしくは更新するプログラムであると判定する（ステップＳ１にてＹＥＳと判定）。
【００３３】
以下では説明を簡単にするため、プログラム１７において、配列が１次元配列にて定義されている場合を例にして処理を説明する。配列が多次元配列にて定義されている場合には、それぞれの次元に以下に説明する処理を適用できるため説明を省略する。
【００３４】
さらに、プログラム１７においては、多次元配列を１次元配列として記述することもある。しかしながら、この場合には、プログラム１７における１次元配列を、多次元配列とみなすことができる。また、プログラム１７は、ＨＰＦ言語にて記述されている必要はなく、他の仕様を持つプログラム言語にて記述されていても良く、このことは、後述する他の実施形態についても同様である。
【００３５】
次に、割り当て判定部１２は、プログラム１７における２つの配列を複数の計算ノードに記憶させるか、否かを判定する（ステップＳ２）。例えば、図３におけるプログラムにおいては、計算ノード数は４台（図３における「ｐｒｏｃｅｓｓｏｒｓ  ｐ（４）」）である。プログラム１７は、第１配列と第２配列とを所定のブロック状に割り当てる方法に基づいて、各計算ノード３２乃至３５に割り当てる指示をする（図３における「ｄｉｓｔｒｉｂｕｔｅ  （ｂｌｏｃｋ）  ｏｎｔｏ  ｐ：：ｏｌｄ，ｎｅｗ」）。
【００３６】
所定のブロック状に割り当てる方法の例として、図４に示すように、（配列の添え字―１）の値を計算ノード数で割った商の値に応じて割り当てる方法がある。図４は、分散メモリ型マルチプロセッサシステム３１において、第１及び２配列をブロック状に各計算ノード３２乃至３５に割り当てる例を示す図である。例えば、第１計算ノードは第１及び２配列の第ｉ（１≦ｉ≦５）要素を、第２計算ノードは第１及び２配列の第ｉ（６≦ｉ≦１０）要素を、第１計算ノードは第１及び２配列の第ｉ（１１≦ｉ≦１５）要素を、及び、第４計算ノードは第１及び２配列の第ｉ（１６≦ｉ≦２０）要素をそれぞれ記憶する。例えば、図３のようなプログラムである場合、割り当て判定部１２は、ステップＳ２にてＹＥＳと判定する。
【００３７】
次に、繰り返し判定部１３は、コンピュータプログラムが第１繰り返し処理において、第２繰り返し処理を実施するか否かを判定する（ステップＳ３）。例えば、図３のプログラムにおいて、２つの繰り返し処理（「ｄｏ  ｉ＝２，１９・・・ｅｎｄｄｏ」及び「ｄｏ  ｉｔｅｒ＝１，  ｉｔｍａｘ・・・ｅｎｄｄｏ」）が入れ子構造であるため、繰り返し判定部１３は、ステップＳ３にてＹＥＳと判定する。以下では、説明のため、内側の繰り返し処理を第２繰り返し処理、外側の繰り返し処理を第１繰り返し処理とする。
【００３８】
次に、境界判定部１５は、
（ａ）コンピュータプログラムが、第１繰り返し処理において、第２配列の第Ｉｊ次元における要素に対して、第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新するか否かを判定する。
【００３９】
あるいは、境界判定部１５は、
（ｂ）コンピュータプログラムが、第１繰り返し処理において、第２配列の第Ｉｊ次元における要素に対して、第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）の値を参照することにより第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新するか否かを判定する（ステップＳ４）。
【００４０】
境界判定部１５は、（ａ）または（ｂ）の少なくとも一方を満たす場合に、条件を満たすと判定する（ステップＳ４）。以下の説明に於いては、ステップＳ４にてＹＥＳと判定された更新処理を、特に、端点処理と表す。
【００４１】
また、境界判定部１５は、コンピュータプログラムが、第１繰り返し処理において、第２配列に値を保存する処理は上述した端点処理及び第２繰り返し処理のみであるか否かを判定してもよい。その場合、境界判定部１５が、第１繰り返し処理において、第２配列に値を保存する処理は上述した端点処理及び第２繰り返し処理のみであると判定する場合（ステップＳ４においてＹＥＳに相当）、プログラム変換装置１０は以降の処理を行う。
【００４２】
例えば、境界判定部１５は、まず、プログラム１７においてデータ配列が定義される添え字の範囲を参照する。次に、境界判定部１５は、プログラム１７が、データ配列の第（添え字の最大値−１）要素を参照することにより、データ配列の第（添え字の最小値）要素を更新するとともに、データ配列の第（添え字の最小値＋１）要素を参照することにより、データ配列の第（添え字の最大値）要素を更新する処理を行うことを見出す（ステップＳ４にてＹＥＳと判定）。
【００４３】
例えば、図３におけるプログラムにおいて、境界判定部１５は、「ｎｅｗ（１）＝ｎｅｗ（１９）」及び「ｎｅｗ（２０）＝ｎｅｗ（２）」の命令が上述した条件を満たすと判定することにより、該プログラム１７が上述した２つの処理を実施すると判定する（ステップＳ４にてＹＥＳと判定）。
【００４４】
次に、更新判定部１４は、コンピュータプログラムが上述した端点処理を実施すると判定する場合に、第２繰り返し処理（図３の例で、「ｄｏ  ｉ＝２，１９・・・ｅｎｄｄｏ」）において、プログラム１７が少なくとも１つのｊ（１≦ｊ≦ｎ）について、第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新するか否かを判定する（ステップＳ５）。
【００４５】
また、更新判定部１４は、第２繰り返し処理が上述した更新処理以外の処理を実施するか否かを更に判定しても良い。その場合、更新判定部１４が、第２繰り返し処理が上述した更新処理のみを実施すると判定する場合に（ステップＳ５においてＹＥＳに相当）、プログラム変換装置１０は以降の処理を行う。
【００４６】
例えば、図３のプログラム例において、プログラムが、第１配列を参照しながら、更新した値を第２配列に記憶させる処理を行う（図３における「ｎｅｗ（ｉ）＝ｏｌｄ（ｉ）＋ｖ×（ｏｌｄ（ｉ−１）−２．０×ｏｌｄ（ｉ）＋ｏｌｄ（ｉ＋１））」）ため、更新判定部１４は、ステップＳ５においてＹＥＳと判定する。
【００４７】
また、ステップＳ４とステップＳ５とにおいて、ステップＳ５を先に処理しても良い。
その場合、境界判定部１５は、上述した更新処理において要素番号が大きい順に処理する場合に、（ａ）を判定し、上述した更新処理において要素番号が小さい順に処理する場合に、（ｂ）を判定してもよい。
【００４８】
次に、代入判定部１９は、上述した条件をすべて満たす場合（ステップＳ５にてＹＥＳと判定）に、第２配列における各要素を、第１配列に保存するか否かを判定する（ステップＳ６）。
【００４９】
また、さらに、プログラム変換装置１０において、コンピュータプログラムがステップＳ３乃至ステップＳ６にてＹＥＳと判定される処理を繰り返し実行すること、該繰り返し実行する処理において、第２配列における各要素を第１配列に保存する場合に、必ず、ステップＳ４における判定処理においてＹＥＳと判定する処理を実施し、かつステップＳ４における判定処理においてＹＥＳと判定する処理以降に第２配列を更新しないこと、及び、該繰り返し実行する処理において、第１配列に値を保存する処理は、ステップＳ６にてＹＥＳと判定される処理だけであることを判定しても良い。この場合には、上記の判定条件を満たす場合に、コード生成部１６が後述の処理を行う。
【００５０】
次に、プログラム１７上述した条件をすべて満たす場合に（ステップＳ６にてＹＥＳと判定）、コード生成部１６が行う処理について説明する。
【００５１】
まず、コード生成部１６は、上述した更新処理を各計算ノードで分担することにより処理するオブジェクトプログラム１８を生成する。
【００５２】
図５は、各計算ノード３２乃至３５が更新する処理を分担する例を表した概念図である。例えば、計算ノード３２は、プログラム１７の繰り返し処理（ｄｏ  ｉ＝２，１９  ｎｅｗ（ｉ）＝ｏｌｄ（ｉ）＋ｖ×（ｏｌｄ（ｉ−１）−２．０×ｏｌｄ（ｉ）＋ｏｌｄ（ｉ＋１））  ｅｎｄｄｏ）において、第２乃至５要素を処理する。同様に、計算ノード３３は第６乃至１０要素を、計算ノード３４は第１１乃至１５要素を、および、計算ノード３５は第１６乃至１９要素をそれぞれ処理する。コード生成部１６は、例えば、上述したような処理を行うオブジェクトプログラム１８を生成する。
【００５３】
上述したような処理において、各計算ノード３２乃至３５は、ネットワーク３６を介して、他の計算ノードが有するデータを相互に参照する必要がある。
【００５４】
図６は、各計算ノード３２乃至３５がネットワーク３６を介してデータを参照する一例を表す図である。例えば、計算ノード３２は、計算ノード３３が記憶する第１配列の第６要素の値を、ネットワーク３６を介して参照する。同様に、計算ノード３３は、計算ノード３２が記憶する第１配列の第５要素の値を、ネットワーク３６を介して参照する。
【００５５】
また、境界判定部１５がＹＥＳと判定した端点処理を実施するためには、図７に示すような通信が必要である。図７は、端点処理において必要な通信処理を表す一例である。例えば、計算ノード３２は、計算ノード３５が記憶する第２配列の第１９要素の値を、ネットワーク３６を介して参照する。同様に、計算ノード３５は、計算ノード３２が記憶する第２配列の第２要素の値を、ネットワーク３６を介して参照する。
【００５６】
コード生成部１６は、プログラム１７を、ステップＳ５においてＹＥＳと判定された処理において必要な通信処理（例えば、図６）と、端点処理において必要な通信処理（例えば、図７）とを一度に処理するオブジェクトプログラム１８を生成する（ステップＳ７）。
【００５７】
図８は、上述した２つの通信処理を一度に処理する例を表す一例である。例えば、計算ノード３２は、計算ノード３３が記憶する第１配列の第６要素の値を参照するとともに、計算ノード３５が記憶する第１配列の第１９要素の値を参照する。コード生成部１６は、上述したような処理を実施するオブジェクトプログラム１８を生成する。
【００５８】
また、コード生成部１６は、ステップＳ６においてＹＥＳと判定する処理に対し、計算ノードｐ（１）が「ｏｌｄ（１：５）＝ｎｅｗ（１：５）」（すなわち、第２配列の第１乃至５要素を、第１配列の第１乃至５要素に保存する）ではなく、「ｏｌｄ（１：６）＝ｎｅｗ（１：６）」（すなわち、第２配列の第１乃至６要素を、第１配列の第１乃至６要素に保存する）を実行し、計算ノードＰ（２）が「ｏｌｄ（６：１０）＝ｎｅｗ（６：１０）」（すなわち、第２配列の第６乃至１０要素を、第１配列の第６乃至１０要素に保存する）ではなく、「ｏｌｄ（５：１１）＝ｎｅｗ（５：１１）」（すなわち、第２配列の第５乃至１１要素を、第１配列の第５乃至１１要素に保存する）を実行する等のオブジェクトプログラム１８を生成しても良い。
【００５９】
以上、本実施形態には、分散メモリ型マルチプロセッサシステムにおける並列処理を向上させることができるオブジェクトプログラムを生成できるという効果がある。
【００６０】
その理由は、プログラム変換装置により生成されたオブジェクトプログラムが上述した２つの通信処理を一度に実施することができ、その結果、２つの通信処理を行う時間が短くなるためである。
【００６１】
＜第２の実施形態＞
次に、上述した第１の実施形態を基本とする第２の実施形態について説明する。
【００６２】
以下では、本実施形態における特徴的な部分を中心に説明する。
【００６３】
本実施形態では、更新判定部の構成が第１の実施形態の更新判定部１４の構成と異なり、他の各構成要素の構成は第１の実施形態のそれらと同じである。
【００６４】
図９は、本実施形態における更新判定部２０の構成を示し、図１０は更新判定部２０における処理の流れを示す。
【００６５】
図９および図１０を参照しながら、本実施形態における更新判定部２０が有する構成と、図３が表すプログラムの一例において、更新判定部２０が行う処理とについて説明する。
【００６６】
更新判定部２０が処理するプログラムは、必ずしも図３におけるプログラムである必要はなく、処理を分割する同様なプログラムであっても良い。
【００６７】
図９を参照すると、更新判定部２０は、参照処理特定部１２０と、参照範囲判定部１２１とを有する。
【００６８】
まず、参照処理特定部１２０は、プログラム１７が、上述した第２繰り返し処理において更新する第２配列の更新範囲を特定する（ステップＳ１０）。例えば、参照処理特定部１２０は、図３におけるプログラムが、「ｄｏ  ｉ＝２，１９・・・ｅｎｄｄｏ」という第２繰り返し処理において、「ｎｅｗ（ｉ）＝ｏｌｄ（ｉ）＋ｖ×（ｏｌｄ（ｉ−１）−２．０×ｏｌｄ（ｉ）＋ｏｌｄ（ｉ＋１））」（ただし、図においては「＊」は掛け算を表す）という更新処理を実施することを見つけ出す。次に、参照処理特定部１２０は、プログラムが、第２配列における第２乃至１９要素を更新することを特定する（ステップＳ１０）。
【００６９】
次に、参照範囲判定部１２１は、参照処理特定部１２０が特定した更新範囲が、定義判定部１１（図１）が特定した第２配列の範囲内であるか否かを判定する（ステップＳ１１）。例えば、図３が示すプログラム１７においては、上記処理の範囲が２乃至１９（図３における「ｄｏ  ｉ＝２，１９」と「ｎｅｗ（ｉ）＝ｏｌｄ（ｉ）＋ｖ×（ｏｌｄ（ｉ−１）−２．０×ｏｌｄ（ｉ）＋ｏｌｄ（ｉ＋１））」との処理）であり、第１配列の定義域が１乃至２０（図３における「ｒｅａｌ  ｎｅｗ（２０）」）であるため、参照範囲判定部１２１は、ＹＥＳと判定する。
【００７０】
ステップＳ１１にてＹＥＳである場合に、更新判定部２０は、上述したステップＳ５における処理を実施する（ステップＳ１２）。
【００７１】
本実施形態は、第１の実施形態が有する効果に加え、プログラム１７が誤りを含むのか否かを判定する効果がある。その理由は、参照範囲判定部１２１が、繰り返し処理における更新範囲と、第２配列を定義する範囲とを比較するためである。
【００７２】
以上、本実施形態には、第１の実施形態と同様の効果がある。
【００７３】
その理由も、第１の実施形態と同様である。
【００７４】
＜第３の実施形態＞
次に、上述した第２の実施形態を基本とする第３の実施形態について説明する。
【００７５】
以下の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第２の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【００７６】
図１１に本実施形態におけるプログラム変換装置１３２が有する構成を示し、図１２は、プログラム変換装置１３２における処理の流れを示すフローチャートである。
【００７７】
図１１を参照すると、プログラム変換装置１３２は、定義判定部１１と、割り当て判定部１２と、繰り返し判定部１３と、更新判定部１４と、境界判定部１５と、境界範囲判定部１３０と、コード生成部１３１とを有する。
【００７８】
まず、境界範囲判定部１３０は、上述した端点処理（図１、ステップＳ４）が、上述した更新範囲（図１０、ステップＳ１０）の要素を更新するか否かを判定する（ステップＳ２１）。
【００７９】
例えば、図３におけるプログラムにおいて、境界範囲判定部１３０は、「ｎｅｗ（１）＝ｎｅｗ（１９）、ｎｅｗ（２０）＝ｎｅｗ（２）」が端点処理であり、更新範囲が第２乃至１９要素であるため、ステップＳ２１にてＹＥＳと判定する。
【００８０】
ステップＳ２１にてＹＥＳと判定される場合、コード生成部１３１は、ステップＳ７（図２）と同様の処理を行う（ステップＳ２２）。
【００８１】
本実施形態は、第２の実施形態と同様の効果を有するのに加え、端点処理が正しく行われるか否かを判定することができる。その理由は、境界範囲判定部１３０が、端点処理における範囲と、更新範囲（図１０、ステップＳ１０）とを比較することにより、検証を行うためである。
【００８２】
以上、本実施形態には、第１の実施形態と同様の効果がある。
【００８３】
その理由も、第１の実施形態と同様である。
【００８４】
＜第４の実施形態＞
次に、上述した第１の実施形態を基本とする第４の実施形態について説明する。
【００８５】
以下では、本実施形態における特徴的な部分を中心に説明する。
【００８６】
本実施形態では、コード生成部４０の構成が第１の実施形態のコード生成部１６の構成と異なり、他の各構成要素の構成は第１の実施形態のそれらと同じである。
【００８７】
図１３は本実施形態におけるコード生成部４０の構成を示し、図１４はコード生成部４０における処理の流れを示す。
【００８８】
図１３および図１４を参照しながら、本実施形態に係るコード生成部４０が有する構成と、コード生成部４０が行う処理とについて説明する。
【００８９】
図１３を参照すると、コード生成部４０は、バッファ生成部１４０と、並列コード生成部１４１と、通信コード生成部１４２とを有する。
【００９０】
バッファ生成部１４０は、他の計算ノードにおける配列の値を一時的に記憶する記憶領域（バッファ）を作成するオブジェクトプログラム１８を生成する。例えば、プログラム１７が、第１配列における第ｉ＋１乃至ｉ＋ｍ要素（ｍは正整数）の値を参照する場合に、バッファ生成部１４０は、（ｍ＋計算ノードに割り当てられた記憶領域の大きさ）を有する記憶領域を確保するオブジェクトプログラム１８を生成する。
【００９１】
例えば、図３におけるプログラム１７において、更新処理が、第１配列における第ｉ＋１及びｉ−１要素を参照するため、バッファ生成部１４０は、７（＝１＋５（第１乃至５要素）＋１）の大きさを持つ記憶領域を確保するオブジェクトプログラム１８を生成する（ステップＳ３１）。
【００９２】
次に、並列コード生成部１４１は、ステップＳ５にてＹＥＳと判定された処理を、各計算ノード３２乃至３５が分担して行うオブジェクトプログラム１８を生成する（ステップＳ３２）。例えば、図３におけるプログラム１７において、各計算ノード３２乃至３５が、上述した処理を、図５に示すように分担して処理するオブジェクトプログラム１８を生成する。
【００９３】
次に、通信コード生成部１４２は、ステップＳ４にてＹＥＳと判定されたプログラムに対して、図８に示すように、端点処理を実施するために必要なデータを通信する処理と、該データを記憶部に記憶させる処理と、更新処理において他の計算ノードが有するデータを参照する通信処理とを、一度に処理するオブジェクトプログラム１８を生成する（ステップＳ３３）。
【００９４】
図８を参照すると、オブジェクトプログラム１８は、他の計算ノードが有するデータを参照する通信処理（計算ノード３２、３３間、計算ノード３３、３４間及び計算ノード３４、３５間）と、端点処理を実施するために必要なデータを通信する処理、及び、該データを記憶部に記憶させる処理（計算ノード３２、３５間）とを、一度に処理する。
【００９５】
以上、本実施形態には、第１の実施形態と同様の効果がある。
【００９６】
その理由も、第１の実施形態と同様である。
【００９７】
なお、第１および第４の実施形態におけるプログラム変換装置は、プログラム制御により動作するコンピュータシステムにより実現しても良いし、専用のハードウェアにより実現しても良い。
【００９８】
尚、上述した各実施形態の一部又は全部は、以下の付記のようにも記載されうる。しかしながら、上述した各実施形態により例示的に説明した本発明は、以下には限られない。即ち、
（付記１）
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定部と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定部と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定部と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定部と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定部と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定部と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成部とを
備えるプログラム変換装置。
【００９９】
（付記２）
前記更新判定部は、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定部と、
前記更新範囲が、前記定義判定部が特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定部とを有し、
前記更新判定部は、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
付記１に記載のプログラム変換装置。
【０１００】
（付記３）
前記コンピュータプログラムが前記第５プログラムである場合に、前記端点処理が前記第２配列の前記更新範囲の要素を更新しない第６プログラムであるか否かを判定する境界範囲判定部を更に備え、
前記コード生成部は、前記コンピュータプログラムが前記第６プログラムである場合に、前記オブジェクトプログラムを生成する
付記２に記載のプログラム変換装置。
【０１０１】
（付記４）
前記コード生成部は、
前記第１通信処理において通信する値を一時的に記憶するバッファ領域を、作成する第１命令を生成するバッファ生成部と、
前記バッファ領域における値を参照しながら、複数の計算ノードが前記更新処理を並列に行う第２命令を生成する並列コード生成部と、
前記第１通信処理における通信と、前記第２通信処理における通信と、前記第２通信処理における通信において授受した値を更新する処理とを一度に実行する第３命令を生成する通信コード生成部と、
を有し、
前記第１乃至３命令を含む前記オブジェクトプログラムを生成する
ことを特徴とする付記１乃至付記３のいずれかに記載のプログラム変換装置。
【０１０２】
（付記５）
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定ステップと、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定ステップと、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定ステップと、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定ステップと、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定ステップと、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定ステップと、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成ステップと
を含むことを特徴とするプログラム変換方法。
【０１０３】
（付記６）
前記更新判定ステップは、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定ステップと、
前記更新範囲が、前記定義判定ステップが特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定ステップとを含み、
前記更新判定ステップは、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
付記５に記載のプログラム変換方法。
【０１０４】
（付記７）
前記コンピュータプログラムが前記第５プログラムである場合に、前記端点処理が前記第２配列の前記更新範囲の要素を更新しない第６プログラムであるか否かを判定する境界範囲判定ステップを更に含み、
前記コード生成ステップは、前記コンピュータプログラムが前記第６プログラムである場合に、前記オブジェクトプログラムを生成する
付記６に記載のプログラム変換方法。
【０１０５】
（付記８）
前記コード生成ステップは、
前記第１通信処理において通信する値を一時的に記憶するバッファ領域を作成する第１命令を生成するバッファ生成ステップと、
前記バッファ領域における値を参照しながら、複数の計算ノードが前記更新処理を並列に行う第２命令を生成する並列コード生成ステップと、
前記第１通信処理における通信と、前記第２通信処理における通信と、前記第２通信処理における通信において授受した値を更新する処理とを一度に実行する第３命令を生成する通信コード生成ステップと、
を含み、
前記第１乃至３命令を含む前記オブジェクトプログラムを生成する
ことを特徴とする付記５乃至付記７のいずれかに記載のプログラム変換方法。
【０１０６】
（付記９）
コンピュータプログラムが、（Ｉ１、Ｉ２、・・・、Ｉｊ、・・・、Ｉｎ）（ただし、ｎは正の整数、１≦Ｉ１≦Ｋ１、１≦Ｉ２≦Ｋ２、・・・、１≦Ｉｎ≦Ｋｎ、１≦ｊ≦ｎ）の大きさを有する第１配列と、前記第１配列と同じ大きさを有する第２配列を参照もしくは更新する第１プログラムであるか否かを判定する定義判定処理と、
前記コンピュータプログラムが前記第１プログラムである場合に、前記コンピュータプログラムが、前記第１配列及び前記第２配列を、それぞれ、所定のブロック状に割り当てる方法に基づいて、複数の計算ノードに記憶させる第２プログラムであるか否かを判定する割り当て判定処理と、
前記コンピュータプログラムが前記第２プログラムである場合に、前記コンピュータプログラムが、第１繰り返し処理において、第２繰り返し処理を実施する第３プログラムであるか否かを判定する繰り返し判定処理と、
前記コンピュータプログラムが前記第３プログラムである場合に、前記コンピュータプログラムが、前記第１繰り返し処理において、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、Ｋｊ−２×ｐ＋１、・・・）乃至（・・・、Ｋｊ−ｐ、・・・）要素の値を参照することにより前記第２配列の第（・・・、１、・・・）乃至（・・・、ｐ、・・・）要素の値を更新する処理、あるいは、前記第２配列の前記第Ｉｊ次元における要素に対して、前記第２配列の第（・・・、ｑ＋１、・・・）乃至（・・・、２×ｑ、・・・）要素の値（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数、必ずしもｐ＝ｑであるとは限らない）を参照することにより前記第２配列の第（・・・、Ｋｊ−ｑ＋１、・・・）乃至（・・・、Ｋｊ、・・・）要素の値を更新する処理の少なくとも一方を実施する端点処理を実施する第４プログラムであるか否かを判定する境界判定処理と、
前記コンピュータプログラムが前記第４プログラムである場合に、前記コンピュータプログラムが、前記第２繰り返し処理において、少なくとも１つのｊ（１≦ｊ≦ｎ）について、前記第１配列の第（・・・、Ｉｊ＋１、・・・）乃至（・・・、Ｉｊ＋ｑ、・・・）（ただし、１≦ｑ≦ｎ−ｊかつ１≦ｑ≦ｊ−１を満たす整数）要素または前記第１配列の第（・・・、Ｉｊ―ｐ、・・・）乃至（・・・、Ｉｊ―１、・・・）要素の値の少なくともいずれか一方を参照することにより、前記第２配列の第（・・・、Ｉｊ、・・・）要素の値を更新する更新処理を実施する第５プログラムであるか否かを判定する更新判定処理と、
前記コンピュータプログラムが前記第５プログラムである場合に、前記第１配列における各要素を、前記第２配列における各要素の値を用いて更新する第６プログラムであるか否かを判定する代入判定処理と、
前記コンピュータプログラムが前記第６プログラムである場合に、前記第２繰り返し処理を、前記複数の計算ノードに割り振る処理に応じて生じる第１通信処理と、前記端点処理における第２通信処理とを一度にコンピュータに処理させるオブジェクトプログラムを生成するコード生成処理とを
をコンピュータに実行させることを特徴とするプログラム変換プログラム。
【０１０７】
（付記１０）
前記更新判定処理は、
前記コンピュータプログラムが前記第３プログラムである場合に、前記第２繰り返し処理において更新される前記第２配列の更新範囲を特定する参照処理特定処理と、
前記更新範囲が、前記定義判定処理が特定した前記第２配列の範囲内であるか否かを判定する参照範囲判定処理とを含み、
前記更新判定処理は、前記更新範囲が前記第２配列の範囲内であると判定する場合に、前記コンピュータプログラムが前記第４プログラムであるか否かを判定する
付記９に記載のプログラム変換プログラム。
【０１０８】
（付記１１）
前記コンピュータプログラムが前記第５プログラムである場合に、前記端点処理が前記第２配列の前記更新範囲の要素を更新しない第６プログラムであるか否かを判定する境界範囲判定処理を更に含み、
前記コード生成処理は、前記コンピュータプログラムが前記第６プログラムである場合に、前記オブジェクトプログラムを生成する
付記１０に記載のプログラム変換プログラム。
【０１０９】
（付記１２）
前記コード生成処理は、
前記第１通信処理において通信する値を一時的に記憶するバッファ領域を作成する第１命令を生成するバッファ生成処理と、
前記バッファ領域における値を参照しながら、複数の計算ノードが前記更新処理を並列に行う第２命令を生成する並列コード生成処理と、
前記第１通信処理における通信と、前記第２通信処理における通信と、前記第２通信処理における通信において授受した値を更新する処理とを一度に実行する第３命令を生成する通信コード生成処理と、
を含み、
前記第１乃至３命令を含む前記オブジェクトプログラムを生成する
ことを特徴とする付記１０乃至付記１２のいずれかに記載のプログラム変換プログラム。
【符号の説明】
【０１１０】
１０    プログラム変換装置
１１    定義判定部
１２    割り当て判定部
１３    繰り返し判定部
１４    更新判定部
１５    境界判定部
１６    コード生成部
１７    プログラム
１８    オブジェクトプログラム
１９    代入判定部
３１    分散メモリ型マルチプロセッサシステム
３２    計算ノード
３３    計算ノード
３４    計算ノード
３５    計算ノード
３６    ネットワーク
２０    更新判定部
１２０    参照処理特定部
１２１    参照範囲判定部
１３０    境界範囲判定部
１３１    コード生成部
１３２    プログラム変換装置
４０    コード生成部
１４０    バッファ生成部
１４１    並列コード生成部
１４２    通信コード生成部
８１    分散メモリ型マルチプロセッサシステム
８２    ネットワーク
８３    計算ノード
８３−１    記憶部
８３−２    計算部
８４    計算ノード
８４−１    記憶部
８４−２    計算部
【図１】
2014191682.tif 000003
【図２】
2014191682.tif 000004
【図３】
2014191682.tif 000005
【図４】
2014191682.tif 000006
【図５】
2014191682.tif 000007
【図６】
2014191682.tif 000008
【図７】
2014191682.tif 000009
【図８】
2014191682.tif 000010
【図９】
2014191682.tif 000011
【図１０】
2014191682.tif 000012
【図１１】
2014191682.tif 000013
【図１２】
2014191682.tif 000014
【図１３】
2014191682.tif 000015
【図１４】
2014191682.tif 000016
【図１５】
2014191682.tif 000017