(57)【要約】【課題】並列化への寄与が大きい重要ループに対する並列化を最適なものにすることにより、性能の高い並列プログラムを生成する。【解決手段】プログラマは、共有メモリ向け並列プログラム２の作成時に、並列化への寄与が大きい重要ループ（例えば、演算時間が長いループ等）を、特定ループとして指示するAFFINITY指示行を挿入しておく。コンパイラ装置１にプログラム２が入力されると、先ず、ループ並列化方法決定部12が、プログラム２中の並列化の対象となるループそれぞれについて、ループ並列化方法162を決定し、記憶装置16に登録する。次いで、データ分散方法決定部131が、記憶装置16に登録されているループ並列化方法162の内のAFFINITY指示行によって指示されている特定ループに対応するループ並列化方法と、特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、データ分散方法を決定する。【選択図】図１
2007226493.tif 000002
【特許請求の範囲】
【請求項１】
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置であって、
記憶装置と、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部と、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定部と、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成部とを備えたことを特徴とするコンパイラ装置。
【請求項２】
請求項１記載のコンパイラ装置において、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定部が、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録する構成を有することを特徴とするコンパイラ装置。
【請求項３】
請求項１または２記載のコンパイラ装置において、
前記データ分散方法決定部が、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てる構成を有することを特徴とするコンパイラ装置。
【請求項４】
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置であって、
記憶装置と、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部と、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定部と、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成部とを備えたことを特徴とするコンパイラ装置。
【請求項５】
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置における並列プログラム生成方法であって、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として記憶装置に登録するループ並列化方法決定ステップと、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定ステップと、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成ステップとを含むことを特徴とする並列プログラム生成方法。
【請求項６】
請求項５記載の並列プログラム生成方法において、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定ステップが、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録することを特徴とする並列プログラム生成方法。
【請求項７】
請求項５または６記載の並列プログラム生成方法において、
前記データ分散方法決定ステップが、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てることを特徴とする並列プログラム生成方法。
【請求項８】
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置における並列プログラム生成方法であって、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として記憶装置に登録するループ並列化方法決定ステップと、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定ステップと、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成ステップとを含むことを特徴とする並列プログラム生成方法。
【請求項９】
記憶装置を備えたコンピュータを、並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置として機能させるためのプログラムであって、
前記コンピュータを、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定部、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成部として機能させるためのプログラム。
【請求項１０】
請求項９記載のプログラムにおいて、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定部が、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録する構成を有することを特徴とするプログラム。
【請求項１１】
請求項９または１０記載のプログラムにおいて、
前記データ分散方法決定部が、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てる構成を有することを特徴とするプログラム。
【請求項１２】
記憶装置を備えたコンピュータを、並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置として機能させるためのプログラムであって、
前記コンピュータを、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定部、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを生成する並列プログラム生成技術に関し、特に、並列化への寄与が大きい重要ループに対するデータの分散方法及びループの並列化方法を最適なものとすることにより、性能の高い並列プログラムを生成する並列プログラム生成技術に関する。
【背景技術】
【０００２】
複数のプロセッサがメモリを共有する共有メモリ型並列計算機では、分散共有メモリ型並列計算機に比べ、並列プログラム（共有メモリ向け並列プログラム）を作成することが容易である。現在、共有メモリ向けプログラミング手段としては、OpenMP が広く用いられている。
【０００３】
一方、分散共有メモリ型並列計算機では、各プロセッサは個別のローカルメモリを持つが、ハードウェアないしはオペレーティングシステムによって、それら個別のローカルメモリを全体として一つの共有メモリとして利用する手段が提供される。共有メモリ型並列計算機と比較して、分散共有メモリ型並列計算機はコストの点で優れている。分散共有メモリを利用して、プログラマは、データの分散方法(どのデータがどのローカルメモリに配置されるか)を意識することなく並列プログラムを作成することができる。しかし、ローカルメモリアクセスとリモートメモリアクセスの性能は一般に異なることから、高い並列性能を得るためにはデータのローカリティを高く保つ必要がある。従って、実際にはデータの分散方法を意識して並列プログラムを作成することが不可欠となる。
【０００４】
ところで、分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを生成する従来のコンパイラ装置としては、従来、次のようなものが知られている（例えば、特許文献１、２参照）。
【０００５】
特許文献１に記載されている従来のコンパイラ装置では、次のようにして並列プログラムを生成するようにしている。
【０００６】
逐次プログラムが入力されると、ループ中に存在する配列を順次対象にして、その配列の配列要素が、分散共有メモリ型並列計算機を構成する各プロセッサに、ページ単位でサイクリックに分散されるようにするデータ分散指示文を生成して中間テキストに挿入する。その後、各ループを順次処理対象にしてそのループ分散形状を、該当するデータ分散指示文によって指示されているデータ分散形状と一致したものにするループ分散指示文を生成して中間テキストに挿入する。そして、最後に、並列化ループを含むネストループをマルチスレッド化することにより並列プログラムを生成する。
【０００７】
特許文献２に記載されている従来のコンパイラ装置では、次のようにして並列プログラムを生成するようにしている。
【０００８】
ソースプログラムが入力されると、先ず、プログラムにおいて宣言されている各配列のどの配列要素を、分散共有メモリ型並列計算機を構成する複数のプロセッサのどのプロセッサに分散させるかを決定する（データ分散方法の決定）。
【０００９】
その後、ソースプログラム中のデータ依存関係の無いループを順次処理対象にして、次のような処理を行う。先ず、処理対象にしているループの各イタレーションをどのプロセッサに割り当てるかを決定する（ループ並列化方法の決定）。その際、既に決定されているデータ分散方法に基づいてループ並列化方法を決定する。次いで、イタレーションでアクセスする配列要素の内、そのイタレーションを実行するプロセッサに割り当てられていない配列要素を検出し、そのアクセス方法を調べる。そして、アクセス方法が参照だけの場合は、処理対象にしているループの直前に、更新だけの場合は、ループの直後に、配列要素をプロセッサ間で転送するデータ転送処理を挿入する。以上の処理をデータ依存関係の無い全てのループに対して行うと、各プロセッサにイタレーションを割り当てるべくループを変形し、これにより、並列プログラムが生成される。
【００１０】
【特許文献１】特開２００１−２９７０６８号公報
【特許文献２】特開平８−３２８８７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
特許文献１に記載されている従来の技術によれば、データのローカリティを高く保つことが可能になる。しかしながら、この従来の技術では、ページ単位で配列要素を各プロセッサに割り当てているため、配列要素を単位とする厳密な（最適な）データ分散を行うことができないという問題がある。
【００１２】
特許文献２に記載されている従来の技術によれば、プログラムのループの並列化時に必要なプロセッサ間データ転送回数を削減することが可能になる。更に、配列要素を単位とするデータ分散を行うことができるため、特許文献１の問題点を解決することもできる。しかしながら、この従来の技術では、データ分散方法を決定した後、そのデータ分散方法に基づいて各ループのループ並列化方法を決定するようにしているため、ループ並列化方法がデータ分散方法によって制限されてしまい、性能の高い並列プログラムを生成できない場合があるという問題がある。即ち、プログラム中に並列化への寄与が大きい重要ループ（例えば、演算時間が長いループ等）があった場合、そのループがうまく並列化されないと、性能の高い並列プログラムを生成することはできないが、特許文献２に記載されている従来の技術では、重要ループを考慮せずにデータ分散方法に基づいて各ループの並列化方法を決定するようにしているため、重要ループがうまく並列化されない場合があり、このような場合、性能の高い並列プログラムを生成することができないという問題がある。
【００１３】
〔発明の目的〕
そこで、本発明の目的は、並列化への寄与が大きい重要ループに対する並列化を最適なものにできるようにすることにより、性能の高い並列プログラムを生成できるようにすることにある。
【課題を解決するための手段】
【００１４】
本発明にかかる第１のコンパイラ装置は、
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置であって、
記憶装置と、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部と、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定部と、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成部とを備えたことを特徴とする。
【００１５】
本発明にかかる第２のコンパイラ装置は、第１のコンパイラ装置において、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定部が、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録する構成を有することを特徴とする。
【００１６】
本発明にかかる第３のコンパイラ装置は、第１または第２のコンパイラ装置において、
前記データ分散方法決定部が、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てる構成を有することを特徴とする。
【００１７】
本発明にかかる第４のコンパイラ装置は、
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置であって、
記憶装置と、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部と、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定部と、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成部とを備えたことを特徴とする。
【００１８】
本発明にかかる第１の並列プログラム生成方法は、
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置における並列プログラム生成方法であって、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として記憶装置に登録するループ並列化方法決定ステップと、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定ステップと、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成ステップとを含むことを特徴とする。
【００１９】
本発明にかかる第２の並列プログラム生成方法は、第１の並列プログラム生成方法において、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定ステップが、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録することを特徴とする。
【００２０】
本発明にかかる第３の並列プログラム生成方法は、第１または第２の並列プログラム生成方法において、
前記データ分散方法決定ステップが、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てることを特徴とする。
【００２１】
本発明にかかる第４の並列プログラム生成方法は、
並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置における並列プログラム生成方法であって、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として記憶装置に登録するループ並列化方法決定ステップと、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定ステップと、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成ステップとを含むことを特徴とする。
【００２２】
本発明にかかる第１のプログラムは、
記憶装置を備えたコンピュータを、並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置として機能させるためのプログラムであって、
前記コンピュータを、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部、
前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録するデータ分散方法決定部、
前記記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成するデータ割付けコード生成部として機能させる。
【００２３】
本発明にかかる第２のプログラムは、第１のプログラムにおいて、
前記指示行が、前記特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報を含み、
前記データ分散方法決定部が、前記記憶装置に登録されているループ並列化方法の内の前記特定ループに対応するループ並列化方法と、前記指示行に含まれている対応関係情報とに基づいて、どの配列要素をどのプロセッサに割り当てるかを決定し、決定した内容をデータ分散方法として前記記憶装置に登録する構成を有することを特徴とする。
【００２４】
本発明にかかる第３のプログラムは、第１または第２のプログラムにおいて、
前記データ分散方法決定部が、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てる構成を有することを特徴とする。
【００２５】
本発明にかかる第４のプログラムは、
記憶装置を備えたコンピュータを、並列化の対象になるループと、並列化の対象になるループの内の特定ループを指示する第１の指示行と、並列化の対象となるループの内の前記特定ループとは異なるループを指示する第２の指示行とが含まれた共有メモリ向け並列プログラムを入力して分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを出力するコンパイラ装置として機能させるためのプログラムであって、
前記コンピュータを、
前記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として前記記憶装置に登録するループ並列化方法決定部、
前記記憶装置に登録されているループ並列化方法の内の、前記第１の指示行によって指示されている前記特定ループに対応するループ並列化方法と、前記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容を第１のデータ分散方法として前記記憶装置に登録すると共に、前記記憶装置に登録されているループ並列化方法の内の、前記第２の指示行によって指示されているループに対応するループ並列化方法と、該第２の指示行によって指示されているループのイタレーションと参照する配列要素との対応関係に基づいて、どの配列要素をどのプログラムに割り当てるかを決定し、決定した内容を第２のデータ分散方法として前記記憶装置に登録するデータ分散方法決定部、
前記記憶装置に登録されている第１のデータ分散方法を実現するデータ割付けコードを生成して、実行文の先頭に挿入すると共に、前記記憶装置に登録されている第２のデータ分散を実現するデータ割付けコードを生成して、前記第２の指示行が指示しているループの直前に挿入するデータ割付けコード生成部として機能させる。
【００２６】
〔作用〕
プログラマは、共有メモリ向け並列プログラム作成時に、並列化への寄与が大きい重要ループ（例えば、演算時間が長いループ等）を、特定ループとして指示する指示行を挿入しておく。コンパイラ装置に共有メモリ向け並列プログラムが入力されると、先ず、ループ並列化方法決定部が、上記共有メモリ向け並列プログラム中の並列化の対象となるループそれぞれについて、そのループの各イタレーションをどのプロセッサに割り当てるかを決定し、決定した内容をループ並列化方法として記憶装置に登録する。次いで、データ分散方法決定部が、記憶装置に登録されているループ並列化方法の内の上記特定ループに対応するループ並列化方法と、上記特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、どの配列要素をどのプロセッサに割り当てるのかを決定し、決定した内容をデータ分散方法として記憶装置に登録する。その後、データ割付けコード生成部が、記憶装置に登録されているデータ分散方法を実現するデータ割付けコードを生成する。
【発明の効果】
【００２７】
本発明によれば、性能の高い並列プログラムを、プログラマに余り負担をかけることなく生成することができるという効果を得ることができる。その理由は、ループ並列化方法決定部によって決定された各ループに対するループ並列化方法の内の、指示行によって指示されている特定ループについてのループ並列化方法と、上記指示行によって指示されている特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、データの分散方法を決定するようにしているからである。即ち、特定ループとして並列化への寄与が大きい重要ループ（演算時間が長いループなど）を指定しておけば、並列化への寄与が大きい重要ループに対するループ並列化方法及びデータ分散方法を最適なものとすることができ、その結果、性能の高い並列プログラムを生成することが可能になる。また、プログラマは、重要ループを特定ループとして指示する指示行を挿入するだけで良いので、プログラマに負担がかかることはない。
【発明を実施するための最良の形態】
【００２８】
次に、発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００２９】
〔第１の実施の形態の構成の説明〕
図１を参照すると、本発明の第１の実施の形態にかかるコンパイラ装置１は、AFFINITY指示行付き共有メモリ向け並列プログラム２（単にプログラム２と記す場合もある）を入力し、分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラム３（単にプログラム３と記す場合もある）を出力するものであり、構文解析部11と、ループ並列化方法決定部12と、データ分散方法決定部131及びデータ割付けコード生成部132から構成されるデータ分散部13と、並列化部14と、コード生成部15と、記憶装置16とを備えている。
【００３０】
AFFINITY指示行付き共有メモリ向け並列プログラム２は、OpenMP等の共有メモリ向け並列プログラミング手段によって記述された並列プログラムに、後述するAFFINITY指示行を追加したものである。
【００３１】
構文解析部11は、入力されたAFFINITY指示行付き共有メモリ向け並列プログラム２の構文解析を行い、中間テキスト161を生成して記憶装置16に格納する。
【００３２】
ループ並列化方法決定部12は、並列化の対象になるループの並列化方法、すなわち当該ループの各イタレーションをどのプロセッサが実行するかを決定し、決定した内容をループ並列化方法162として記憶装置16に登録する。
【００３３】
データ分散部13は、データ分散方法決定部131及びデータ割付けコード生成部132からなり、プログラマがAFFINITY指示行によって指定したループで参照するデータ（配列）の最適な分散を実現するコードを生成する。
【００３４】
データ分散方法決定部131は、ループ並列化方法決定部12によって記憶装置16に登録されているループ並列化方法162の内の、AFFINITY指示行によって指示されてるループのループ並列化方法162を参照し、AFFINITY指示行の指定に従って当該ループにおける最適なデータ分散方法を決定し、決定した内容をデータ分散方法163として記録する。
【００３５】
データ割付けコード生成部132は、データ分散方法決定部131によって決定されたデータ分散方法163を実現するデータ割付けコードを生成し、挿入する。
【００３６】
並列化部14は、ループ並列化方法決定部12によって記憶装置16に登録されたループ並列化方法162に従ってループを並列化する他に、同期や集計操作などの並列化に必要な種々の変形を加える。
【００３７】
コード生成部15は、分散共有メモリ向け並列プログラム３を出力する。
【００３８】
分散共有メモリ向け並列プログラム３は、各プロセッサのローカルメモリへデータを分散配置する方法を含み、分散共有メモリ型並列計算機上での実行において高い性能を達成できる。
【００３９】
このような機能を有するコンパイラ装置１は、コンピュータによって実現可能なものであり、コンピュータによって実現する場合には、例えば、次のようにする。コンピュータをコンパイラ装置１として機能させるためのプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意し、上記プログラムをコンピュータに読み取らせる。コンピュータは、読み取ったプログラムに従って自身の動作を制御することにより、自コンピュータ上に、構文解析部11、ループ並列化方法決定部12、データ分散部13、並列化部14及びコード生成部15を実現する。
【００４０】
〔AFFINITY指示行の説明〕
次に、AFFINITY指示行について説明する。
【００４１】
AFFINITY指示行は、配列データの宣言時（初期化時）の分散方法を決定するために使用するループ並列化方法を、プログラム中に存在するどのループに対応するループ並列化方法とするのかを指示するためにプログラム２に挿入された指示行であり、その挿入位置の直後に現れるループのループ並列化方法がデータ分散方法を決定するために使用される。プログラマは、プログラム２に存在するループの内の、並列化への寄与が大きい重要ループの直前にAFFINITY指示行を挿入しておく。
【００４２】
図２は、AFFINITY指示行の一例を示す図である。この例のAFFINITY指示行では、配列の一つの次元に対する、ブロック・サイクリック分散を表現することができる(ブロック・サイクリック分散の特殊な場合と考えられるブロック分散およびサイクリック分散を表現することもできる)。
【００４３】
AFFINITY指示行の直後には、OpenMPのDO指示行またはPARALLEL DO指示行が続かなくてはならない。また、対象の並列ループの並列化方法はコンパイル時に決定できなくてはならない。すなわち、当該DO指示行またはPARALLEL DO指示行は、SCHEDULE(STATIC[, chunk_size])節を伴っていなくてはならない。
【００４４】
AFFINITY指示行の文字列「AFFINITY」に続く括弧内には、データ分散を指定する配列データの、配列要素または部分配列または配列名の並びを指定することができる。配列要素または部分配列または配列名として指定できる配列データは、当該手続きが主手続きでない限り、局所データでなければならない。ここで、局所データとは、当該配列において、宣言および割付けが行われるデータとする。さらに、一つの手続きにおいて、ある局所配列データは高々一つのAFFINITY指示行にしか現れることができない。
【００４５】
さらに、括弧内に配列要素または部分配列が指定される場合、その添字並びのうち、ただ一つだけが当該並列ループの制御変数の線形式であり、それ以外は「:」でなければならない。ここで、「:」は当該次元を分散しないことを表す。
【００４６】
線形式で表される添字は、当該次元に関し、並列ループのあるイタレーションを実行するプロセッサに割り当てる要素の下限または上限を表す。すなわち、当該並列ループの制御変数をI、その増分値をm、当該次元に指定された線形式をF(I) = a*I+b とすると、イタレーションiを実行するプロセッサのローカルメモリへ割り当てる要素の、当該次元の下限LB(i)と上限UB(i)は次のようになる。
【００４７】
・mとaが同符号の場合LB(i) = F(i), UB(i) = F(i+m)-1
・mとaが異符号の場合LB(i) = F(i+m)+1, UB(i) = F(i) 
【００４８】
ここで、連続するn個のイタレーションi, i+m, …, i+m*(n-1)に対応するn個の配列領域は連続である。したがって、このn個のイタレーションから成る集合Ipに対応する配列領域の下限LB(Ip)と上限UB(Ip)は、
・mとaが同符号の場合LB(Ip) = LB(i), UB(Ip) = UB(i+m*(n-1))
・mとaが異符号の場合LB(Ip) = LB(i+m*(n-1)), UB(Ip) = UB(i)
と書ける。
【００４９】
上の例の括弧内に現れる部分配列A(:,a*I+b)は、a > 0のとき、並列ループのイタレーションiを実行するプロセッサのローカルメモリへ、A(:,a*i+b:a*(i+1)+b-1)で表される配列Aの領域を割り当てることを意味する。
【００５０】
括弧内に配列名が指定される場合、すなわち添字並びが省略されている場合、並列ループ中に現れる当該配列の参照の添字並びから、当該ループの制御変数が一度だけ現れるものを選び、当該次元以外の添字を「:」に置き換えて得られる添字並びが指定されているものと見なす。
【００５１】
〔第１の実施の形態の動作の説明〕
次に、本実施の形態の動作について詳細に説明する。なお、以下の説明では、図３に示すAFFINITY指示行付き共有メモリ向け並列プログラム２（単にプログラム２と記す場合もある）が入力された場合を例に挙げて、コンパイラ装置１の動作を説明する。このプログラム２では、OpenMPのDO指示行によって並列実行を指示された二重ループにおいて、AFFINITY指示行によって配列Aおよび配列Bの分散方法が指定されている。配列Aに関しては、添字並びの指定が省略されている。また、図３の例では、並列ループ（OpenMPのDO指示行やPARALLEL DO指示行によって並列化することが指示されている、並列化の対象になるループ）を１つしか示していないが、並列ループが複数含まれていても構わない。
【００５２】
コンパイラ装置２に図３に示すプログラム２が入力されると、先ず、構文解析部11が構文解析を行い、中間テキスト161を生成する。この中間テキスト161は、記憶装置16に格納される。
【００５３】
その後、ループ並列化方法決定部12が、共有メモリ向けプログラムが記述される共有メモリ向けプログラミング手段の仕様に従い、プログラム２中に存在する各並列ループそれぞれについてループ並列化方法162を決定する。図３に図示されている２重ループを処理対象にしているとすると、DO指示行のSCHEDULE節によってSTATICスケジューリングが指定されているため、当該ループのイタレーション範囲を等幅にｋ分割（ｋはプログラム３を実行する分散共有メモリ型並列計算機が備えているプロセッサの台数）して得られる各ブロックを各プロセッサがそれぞれ実行するように並列化方法を決定する。
【００５４】
例えば、プログラム３を実行する分散共有メモリ型並列計算機が、図４に示すように、４台のプロセッサP(0)〜P(3)を有しており、図示を省略した入力装置からプロセッサ数「４」が入力されているとすると、ループ並列化方法決定部12は、プロセッサP(0),P(1),P(2),P(3)が、それぞれJループのイタレーション1〜25, 26〜50, 51〜75, 76〜100を実行するループ並列化方法を決定し、決定した内容をループ並列化方法162として記憶装置16に登録しておく。
【００５５】
ループ並列化方法決定部12は、プログラム２中に存在する各並列ループを処理対象にして上述した処理を行い、各並列ループのループ並列化方法162を記憶装置16に登録しておく。
【００５６】
続いて、データ分散部13の動作を説明する。
(1) データ分散方法の決定
図５のフローチャートを参照して、１つのAFFINITY指示行における一つの配列指定に対するデータ分散方法決定部131の動作を説明する。
【００５７】
データ分散方法決定部131は、プログラム２を先頭から検索し、AFFINITY指示行を検出すると、そのAFFINITY指示行によって指定されている各配列それぞれについて図５のフローチャートに示す処理を行い、AFFINITY指示行によるユーザ（プログラマ）の指示と、記憶装置16に登録されている各並列ループのループ並列化方法162の内の、AFFINITY指示行の挿入位置の直後に存在する並列ループのループ並列化方法162とから、データの分散方法を決定する。あるプロセッサに割り当てるべきデータは、AFFINITY指示行によって、そのプロセッサが実行する各イタレーションと対応付けられる配列要素の和集合である。
【００５８】
今、図３に示すAFFINITY指示行を検索したとすると、データ分散方法決定部131は、このAFFINITY指示行によって指定されている配列A,Bそれぞれに対して、図５のフローチャートに示す処理を行う。
【００５９】
今、配列Aを処理対象にしたとすると、配列Aに対するAFFINITY指示行の指定では、添字並びが省略されているため（ステップＳ51がNo）、ループ中から選んだ参照を元に添字並びを補う(ステップＳ52がNo，Ｓ53)。例えば、参照 A(I,J)を元にして添字並び(:,J)を補えば、A(:,J)が得られる。
【００６０】
添字並びが省略された配列の参照がループ中に存在しない場合（ステップＳ52がYes）、メッセージを出力して(ステップＳ54)、当該配列に対する指定を無視する。
【００６１】
配列Aの二次元目に関し、プロセッサP(0)が実行するJループのイタレーションJ0= {1, 2, …, 25}に対応する領域の上下限は、
LB(J0) = LB(1) = 1
UB(J0) = UB(25) = 25
であるから、プロセッサP(0)には配列Aの領域A(:,1:25)が割り当てられることになる。プロセッサP(1)にはA(:,26:50)が、プロセッサP(2)にはA(:,51:75)が、プロセッサP(3)には A(:,76:100)が、それぞれ割り当てられる(ステップＳ55)。
【００６２】
さらに、配列Aの要素A(0)とA(101)は、AFFINITY指示行によって割り当て方法を指示されないため（ステップＳ56がYes）、それらの要素に隣接する要素(ここではA(1)とA(100))を割り当てられたプロセッサに割り当てる（ステップＳ57）。従って、最終的には、プロセッサ(0)にはA(:,0:25)が、プロセッサP(3)にはA(76:101)を割り当てる(ステップＳ57)。
【００６３】
最後に、決定したデータ分散方法を、データ分散方法163として記憶装置16に登録しておく(ステップＳ58)。
【００６４】
配列Aに対する処理が終了すると、データ分散方法決定部131は、配列Bを処理対象にして図５のフローチャートに示す処理を行う。配列Bの場合は、添え字が存在するので（ステップＳ51がYes）、直ちに、ステップＳ55以降の処理が行われ、プロセッサP(0)にはB(:,1:50)が、プロセッサP(1)にはB(:,51:100)が、プロセッサP(2)にはB(:,101:150)が、プロセッサP(3)にはB(:,151:200)が、それぞれ割り当てられる。
【００６５】
(2) データ割付けコードの生成
データ割付けコード生成部132は、データ分散方法決定部131で決定されたデータ分散方法163を実現するデータ割付けコードを生成し、先頭の実行文の直前に挿入する。
【００６６】
例えば、各プロセッサP(0)〜P(3)のローカルメモリに対してメモリ割付けを行う処理をL ALLOCATE文によって表現するなら、図６に示すようなデータ割付けコードを生成すればよい。ここで、iはプロセッサ番号である。このL ALLOCATE文は、自プロセッサ番号iに関して各プロセッサP(0)〜P(3)によって実行される。
【００６７】
その後、並列化部14は、ループ並列化方法決定部12が記憶装置16に登録したループ並列化方法162を参照して各並列ループを並列化し、コード生成部15は、分散共有メモリ向け並列プログラム３を出力する。
【００６８】
〔第１の実施の形態の効果〕
本実施の形態によれば、性能の高い並列プログラムを、プログラマに余り負担をかけることなく生成することができるという効果を得ることができる。その理由は、ループ並列化方法決定部12によって決定された各ループに対するループ並列化方法の内の、AFFINITY指示行によって指示されている特定ループについてのループ並列化方法と、上記AFFINITY指示行によって指示されている特定ループのイタレーションと参照する配列要素との対応関係とに基づいて、データ分散方法決定部131で、データの分散方法を決定するようにしているからである。即ち、特定ループとして並列化への寄与が大きい重要ループ（演算時間が長いループなど）を指定しておけば、並列化への寄与が大きい重要ループに対するループ並列化方法162及びデータ分散方法163を最適なものとすることができ、その結果、性能の高い並列プログラムを生成することが可能になる。また、プログラマは、重要ループを特定ループとして指示するAFFINITY指示行を挿入するだけで良いので、プログラマに負担がかかることはない。
【００６９】
また、本実施の形態では、AFFINITY指示行に、特定ループのイタレーションと参照する配列要素との対応関係を示す対応関係情報が含まれているので、データ分散方法決定部131において、迅速にデータ分散方法163を決定することが可能になる。
【００７０】
更に、本実施の形態では、データ分散方法決定部131が、未割り当ての配列要素が存在すると判断した場合、予め定められている規則に従って、未割り当ての配列要素をプロセッサに割り当てる構成を有しているので、全ての配列要素を確実にプロセッサに割り当てることができる。
【００７１】
〔第２の実施の形態〕
次に、本発明の第２の実施の形態について説明する。本実施の形態は、AFFINITY指示行に加え、REAFFINITY指示行によりデータの分散方法を指定できるようにしたことを特徴とする。
【００７２】
REAFFINITY指示行は、AFFINITY指示行と同じ文法仕様を持つが、AFFINITY指示行とは異なり、任意の配列データに対して使用することができる。また、一つの手続き内で、同一の配列データに対して複数回のREAFFINITY指示行を指定することもできる。
【００７３】
AFFINITY指示行が配列データの割付け時の分散方法を指定するのに対し、REAFFINITY指示行は、既に割付けられている配列データの分散方法をプログラム実行時に変更することを指定する。
【００７４】
AFFINITY指示行に加え、REAFFINITY指示行を含むプログラム２がコンパイラ装置１に入力されると、構文解析部11及びループ並列化方法決定部12は、第１の実施の形態で説明した処理と同様の処理を行う。
【００７５】
データ分散方法決定部131は、プログラム２を先頭から検索し、AFFINITY指示行を検出した場合には、第１の実施の形態で説明した処理と同様の処理を行う。また、REAFFINITY指示行を検出した場合は、そのREAFFINITY指示行によって指定されている各配列それぞれについて図５のフローチャートに示す処理を行い、REAFFINITY指示行によるユーザ（プログラマ）の指示と、記憶装置16に登録されている各並列ループのループ並列化方法162の内の、上記REAFFINITY指示行の挿入位置の直後に存在する並列ループのループ並列化方法162とから、データの分散方法を決定する。
【００７６】
データ割付けコード生成部132では、記憶装置16に登録されているデータ分散方法163の内、AFFINITY指示行に対応するデータ分散方法163については、第１の実施の形態と同様の処理を行う。REAFFINITY指示行に対応するデータ分散方法163については、そのデータ分散方法163を実現するコードを生成し、当該REAFFINITY指示行が指定されている並列ループの直前に挿入する。より具体的には、配列データの再分散後の領域を割付け、既存の領域からデータをコピーした後、既存の領域を解放するコードを生成する。
【００７７】
〔第２の実施の形態の効果〕
本実施例では、配列データの再分散を可能にすることにより、最適なデータ分散方法が実行中に変わるようなプログラムにおいても、高い並列性能を得ることができる。
【００７８】
〔第３の実施の形態〕
次に、本発明の第３の実施の形態について説明する。本実施の形態では、ある手続きの局所配列データに対してAFFINITY指示行が指定されていない場合、当該手続き内の並列ループから、当該配列の参照が出現するものを一つ選び、当該配列の配列名が指定された(添字並びが省略された)AFFINITY指示行が当該並列ループに指定されているものと見なす。以降の処理は、本発明の第一の実施例に従う。当該配列の参照が出現する並列ループを選ぶ方法については、例えばそのような並列ループのうち、プログラムの文面上で最初に現れるものを選ぶ方法が考えられる。
【００７９】
〔第３の実施の形態の効果〕
本実施の形態では、プログラマがAFFINITY指示行を指定しなくても、すなわち通常の共有メモリ向け並列プログラムを変更しなくても、効率の良い分散共有メモリ向け並列プログラムを得ることができる。
【産業上の利用可能性】
【００８０】
本発明は、共有メモリ向け並列プログラムから、分散共有メモリ型並列計算機上で動作する分散共有メモリ向け並列プログラムを生成するコンパイラ装置に適用すると好適である。
【図面の簡単な説明】
【００８１】
【図１】本発明にかかるコンパイラ装置の第１の実施の形態の構成例を示すブロック図である。
【図２】AFFINITY指示行を説明するための図である。
【図３】AFFINITY指示行付き共有メモリ向け並列プログラム２の一例を示す図である。
【図４】分散共有メモリ向け並列プログラム３を実行する分散共有メモリ型並列計算機の一例を示すブロック図である。
【図５】データ分散方法決定部131の処理例を示すフローチャートである。
【図６】データ割付けコード生成部132で生成されるデータ割付けコードの一例を示す図である。
【符号の説明】
【００８２】
１…コンパイラ装置
11…構文解析部
12…ループ並列化方法決定部
13…データ分散部
131…データ分散方法決定部
132…データ割付けコード生成部
14…並列化部
15…コード生成部
16…記憶装置
161…中間テキスト
162…ループ並列化方法
163…データ分散方法
２…AFFINITY指示行付き共有メモリ向け並列プログラム
３…分散共有メモリ向け並列プログラム
【図１】
2007226493.tif 000003
【図２】
2007226493.tif 000004
【図３】
2007226493.tif 000005
【図４】
2007226493.tif 000006
【図５】
2007226493.tif 000007
【図６】
2007226493.tif 000008