(57)【要約】      （修正有）【課題】ＮＵＭＡアーキテクチャを採用した共有メモリ型マルチプロセッサ計算機システムを使用するプログラマがソースコードを書き換えることなく、ローカルメモリへアクセスする並列化プログラムを生成するコンパイラを提供する。【解決手段】ローカルメモリにアクセスさせたい配列名と並列化させたい配列の次元がコンパイルオプションとして指定されていた場合に、配列名と配列の次元を配列テーブルに格納し、ソースコード内に配列テーブルに格納されている指定した配列をアロケートする処理がある場合に、アロケート処理の直後に指定した配列の初期化ループを追加し、ソースコード内にあるループに指定した配列がある場合に、指定した次元に使用されている変数と同じ変数をループ制御変数として使用しているループを並列化する。【選択図】図６
2012221135.tif 000002
【特許請求の範囲】
【請求項１】
計算機によるＮＵＭＡアーキテクチャ向け並列化プログラムの生成方法であって、前記計算機は、ソースコードを格納する記憶装置と、オプション解析部と、初期化処理追加部と、解析部とを備え、前記オプション解析部は、前記記憶装置からソースコードが入力される際に、ローカルメモリにアクセスさせたい配列名と並列化させたい配列の次元がコンパイルオプションとして指定されていた場合に、前記配列名と配列の次元を配列テーブルに格納し、前記初期化処理追加部は、前記ソースコード内に前記配列テーブルに格納されている指定した配列をアロケートする処理がある場合に、アロケート処理の直後に指定した配列の初期化ループを追加し、前記解析部は、前記ソースコード内にあるループに指定した配列がある場合に、指定した次元に使用されている変数と同じ変数をループ制御変数として使用しているループを並列化するＮＵＭＡアーキテクチャ向け並列化プログラムの生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＮＵＭＡ(Non-Uniform Memory Access）アーキテクチャを採用した共有メモリ型マルチプロセッサ計算機システムで効率よく動作させるための並列化プログラムの生成方法及びコンパイラに関する。
【背景技術】
【０００２】
共有メモリ型マルチプロセッサ計算機システムでは、ループを並列に処理させることで効率よく計算機システムを使用している。例えば、前記したループの並列に処理させる既存の技術として、特開２００９−１０４４２２号公報（特許文献１）がある。この公報には、「キャッシュメモリまたは主記憶を共有する複数の演算器から構成される計算機システムに対して、ソースコードより最適な並列コードを生成する方法を提供する。」と記載されている（要約参照）。また、特開２００９−１４０４５１号公報（特許文献２）がある。この公報には、「リスト構造ループの処理を高速化することを課題とする。」と記載されている（要約参照）。非特許文献１には、コンパイラの具体的な実装方法などが記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１０４４２２号公報
【特許文献２】特開２００９−１４０４５１号公報
【非特許文献１】Hans Zima and Barbara Chapman共著、村岡洋一訳、「スーパーコンパイラ」、オーム社、１９９５年
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＮＵＭＡアーキテクチャを採用した共有メモリ型マルチプロセッサ計算機システムでは、ローカルメモリへのアクセスとリモートメモリへのアクセスではアクセス時間が異なる。ローカルメモリアクセスとリモートメモリアクセスの一例を図１で説明する。ローカルメモリアクセス１０１とは、同じCPUカード１０２内にある演算器１  １０３からメモリスイッチ１０４、メモリコントローラ１０５を通し主記憶装置１１０６へアクセスすることであり。リモートメモリアクセス１０７とは、演算器２  １０７がメモリスイッチ１０８からチップ間バス１０９を通して違うCPUカード１０２内の主記憶装置１  １０６へアクセスすることである。並列化プログラムを生成するコンパイラは、ソースコード内にあるループの依存関係のみを判定して並列化するため、ループで使用する配列データのメモリ配置まで意識していない。これによりリモートメモリへのデータアクセスが発生し、性能低下を招くことがある。
【０００５】
例えば、図２に示す並列化プログラムの最初の２重ループ２０１では、内側２０２で並列化される。よって、配列aにおける1次元目の１から１００までは演算器１  １０３で計算される。この際、ファーストタッチルールにより、配列aにおける1次元目の１から１００までは主記憶装置１  １０６にアロケートされる。ファーストタッチルールとは、データを初めにアクセスする演算器と同じCPUカード内の主記憶装置にメモリ配置することである。配列aにおける1次元目の１０１から２００までは演算器２  １０７で計算される。この際、ファーストタッチルールにより、配列aにおける1次元目の１０１から２００までは主記憶装置２  １１０にアロケートされる。図３に最初の２重ループ２０１の配列aにおける演算器と主記憶装置への配置の関係を示す。
【０００６】
２つ目の２重ループ２０３では、外側２０４で並列化される。よって、配列aにおける２次元目の１から１００までは演算器１  １０３で参照される。配列aにおける２次元目の１０１から２００までは演算器２  １０７で参照される。図４に２つ目の２重ループ２０３の配列aにおける演算器と主記憶装置への配置の関係を示す。図４では４０１と４０２はローカルアクセスとなり、４０３と４０４についてはリモートアクセスが発生していることが判る。
【０００７】
現在、ローカルメモリへのデータアクセスを意識した並列化プログラムを生成するには、ソースコードに指示行等をプログラマが書き加える必要がある。
【課題を解決するための手段】
【０００８】
本発明は、計算機によるＮＵＭＡアーキテクチャ向け並列化プログラムの生成方法であって、前記計算機は、ソースコードを格納する記憶装置と、オプション解析部と、初期化処理追加部と、解析部とを備え、前記オプション解析部は、前記記憶装置からソースコードが入力される際に、ローカルメモリにアクセスさせたい配列名と並列化させたい配列の次元がコンパイルオプションとして指定されていた場合に、前記配列名と配列の次元を配列テーブルに格納し、前記初期化処理追加部は、前記ソースコード内に前記配列テーブルに格納されている指定した配列をアロケートする処理がある場合に、アロケート処理の直後に指定した配列の初期化ループを追加し、前記解析部は、前記ソースコード内にあるループに指定した配列がある場合に、指定した次元に使用されている変数と同じ変数をループ制御変数として使用しているループを並列化する。
【発明の効果】
【０００９】
本発明により生成された並列化プログラムを用いると、演算器からのメモリアクセスがローカルメモリアクセスとなり性能が向上する。また、コンパイラが自動で最適な並列化プログラムを生成するためプログラマによるソースコードの書き換えが不要となる。
【図面の簡単な説明】
【００１０】
【図１】ローカルメモリアクセスとリモートメモリアクセスの違いを示した説明図である。
【図２】本発明の課題となる並列化プログラム内のループの一例を示した図である。
【図３】図２で示した最初の２重ループの演算器と主記憶装置の配置を示す図である。
【図４】図２で示した２つ目の２重ループの演算器と主記憶装置の配置を示す図である。
【図５】本発明の実施例によるコンパイルを実行するための計算機システムの一例を示した構成図である。
【図６】図１の計算機システムにおいて、その並列化プログラムを生成する機能の詳細な一例を示した構成図である。
【図７】プログラマがコンパイル時に指定するコンパイルオプションの具体例を示す説明図である。
【図８】図３における配列テーブルの一例を示す説明図である。
【図９】図３における初期化処理追加部の処理内容を示すフロー図である。
【図１０】図３における解析部の処理内容を示すフロー図である。
【図１１】本実施例によりコンパイルした並列化プログラムの一例を示した図である。
【図１２】図１１で示した２重ループの演算器と主記憶装置の配置を示す図である。
【発明を実施するための形態】
【００１１】
以下、実施例を図面を用いて説明する。
【００１２】
図５は、本発明の実施例によるコンパイルを実行する計算機システムの構成図を示す。この計算機システムは、ディスプレイ装置５０１、キーボード５０２、演算器５０３、主記憶装置５０４、外部記憶装置５０５から構成される。並列化プログラム５０６を生成する際は、キーボード５０２から並列化プログラム生成のためのコマンドとコンパイルオプションを入力する。コンパイルオプションの指定方法は、図７で説明する。並列化プログラムの生成状況及びエラーメッセージや終了メッセージはディスプレイ装置５０１に表示される。外部記憶装置５０５には、ソースコード５０７と最終的に生成される並列化プログラム５０６が格納される。主記憶装置５０４には、オプション解析部５０８、初期化処理追加部５０９、解析部５１０、配列テーブル５１１が格納される。演算器５０３は、並列化プログラムの生成処理を制御する。
【００１３】
図５のソースコードから並列化プログラムを生成する際の処理内容を図６に示す。ソースコード６０１とコンパイルオプション６０２をコンパイラ６０３に入力することで並列化プログラムを生成する。コンパイラ６０３は、オプション解析部６０４でプログラマが入力したコンパイルオプション６０２の解析する。図７で説明するコンパイルオプションが入力されている場合、配列テーブル６０５にコンパイルオプションで指定した配列名と次元を登録する。配列テーブル６０５の詳細について図８で説明する。初期化処理追加部６０６では、コンパイルオプションで指定した配列の初期化処理を追加する。解析部６０７は並列化について解析する。初期化処理追加部６０６の詳細については図９で、解析部６０７の詳細については図１０で説明する。コンパイラ６０３は解析部６０７の結果を元に並列化プログラム６０８を生成する。
【００１４】
図７に、図６のコンパイルオプション６０２の指定方法を示す。プログラマが入力するコンパイルオプションの指定方法を示す。本実施例で並列化プログラムを生成する際は、並列化方針のオプション７０１を入力し、その後に配列名７０２と次元７０３を指定する。配列名７０２はローカルメモリアクセスさせる配列名である。配列名と次元は７０４で示すように、複数指定することを可能とする。複数の配列を指定した場合は先に指定した配列名を優先して並列化する。
【００１５】
図８に、図６の配列テーブル６０５の一例を示す。配列テーブルには、コンパイルオプションで先に指定した順に番号８０１を付け、８０２に配列名、８０３の配列の次元を登録する。
【００１６】
図９に、図６の初期化処理追加部６０６のフロー図を示す。まず９０１の処理で開始する。９０２の処理では、配列テーブルにコンパイルオプションに指定した配列名が登録されているか解析する。配列名が登録されている場合は９０３の処理で、配列名を読み込む。９０３の処理で読み込む配列名は、コンパイルオプションで先に指定した順に読み込む。９０４の処理は読み込んだ配列がソースコード内でアロケート処理がある場合は、９０５の処理で、配列のアロケート処理の直後に配列の初期化ループを追加する。９０５の処理が終了したら９０２の処理に戻る。９０４の処理で、読み込んだ配列のアロケート処理が無い場合は９０２の処理に戻る。配列テーブルに登録されている全ての配列について解析するまで、９０２の処理から９０５の処理を繰り返す。
【００１７】
図１０に、図６の解析部６０７のフロー図を示す。まず１００１で処理を開始する。１００２の処理はソースコードにループがあるか解析する。ループがある場合は１００３の処理に移動する。１００３の処理は配列テーブルからコンパイルオプションに指定した配列名と次元を読み込む。１００３の処理で読み込む配列名と次元は、コンパイルオプションで先に指定した順に配列名と次元を読み込む。１００４の処理は読み込んだ配列名がループにあるか解析する。読み込んだ配列名がある場合は１００５の処理に移動する。１００５の処理で配列の次元に使用している変数がループ制御変数に使用している場合、１０６の処理でループを並列化する。ループの並列化については、図１１及び図１２で説明する。１００６の処理が終了したら１００２の処理に戻る。
【００１８】
１００４の処理で読み込んだ配列名がループ内に無い場合は、１００７の処理に移動する。１００７の処理は配列テーブルに読み込んだ配列以外に配列名が登録されているか解析する。他の配列が登録されている場合は、１００８の処理で配列テーブルから他の配列名と次元を読み込む。１００８の処理が終了したら１００４の処理に戻る。１００７の処理で他の配列名が、配列テーブルに登録されていない場合は１００２の処理に戻る。１００５の処理で配列の次元に使用している変数がループ制御変数に使用していない場合、１００７の処理に移動する。ソースコード内の全てのループを解析するまで、１００２から１００６の処理を繰り返す。１００２の処理でソースコード内にループが無い場合は、１００９で解析部を終了する。
【００１９】
本実施例によりコンパイルした並列化プログラムの一例を図１及び図１１、図１２を使用して説明する。まず、本実施例に示す、コンパイルオプションで、配列aと配列の次元に２を指定する。指定したコンパイルオプションに従い、コンパイラは配列ａの初期化ループとして２重ループ１１０１を追加する。２重ループ１１０１の配列aの２次元目では、変数jが使用されている。変数jは外側１１０２の制御変数となるので、２重ループ１１０１は外側１１０２で並列化される。よって、配列ａにおける２次元目の１から１００までは、演算器１  １０３で計算される。この際、ファーストタッチルールにより、配列aにおける２次元目の１から１００までは、主記憶装置１  １０６にアロケートされる。配列aにおける２次元目の１０１から２００までは演算器２  １０７で計算される。この際、ファーストタッチルールにより配列aにおける２次元目の１０１から２００までは、主記憶装置２  １１０にアロケートされる。図１２に追加した２重ループ１１０１の配列aにおける演算器と主記憶装置への配置の関係を示す。
【００２０】
２つ目の２重ループ１１０３では、コンパイルオプションの指定により外側ループ１１０４で並列化される。よって、配列aにおける２次元目の１から１００までが演算器１  １０３で計算される。配列aにおける１０１から２００までが演算器２  １０７で計算される。
【００２１】
３つ目の２重ループ１１０４においても、コンパイルオプションの指定により外側ループ１１０６が並列化される。よって、配列aにおける２次元目の１から１００までが演算器１  １０３で参照され、配列aにおける１０１から２００までが演算器２  １０７で参照される。したがって、２つ目の２重ループ１１０３及び３つ目の２重ループ１１０５の配列aにおける演算器と主記憶装置への配置の関係についても図１２と同じになり、配列aにおいてはリモートメモリアクセスが発生しなくなる。
【符号の説明】
【００２２】
１０１  ローカルメモリアクセス
１０２  CPUカード
１０３，１０７，５０３  演算器
１０４，１０８  メモリスイッチ
１０５  メモリコントローラ
１０６，１１０，５０４  主記憶装置
１０７  リモートメモリアクセス
１０９  チップ間バス
５０１  ディスプレイ装置
５０２  キーボード
５０５  外部記憶装置
５０６，６０８  並列化プログラム
５０７，６０１  ソースコード
５０８，６０４  オプション解析部
５０９，６０６  初期化処理追加部
５１０，６０７  解析部
５１１，６０５  配列テーブル
６０２  コンパイルオプション
６０３  コンパイラ
【図１】
2012221135.tif 000003
【図２】
2012221135.tif 000004
【図３】
2012221135.tif 000005
【図４】
2012221135.tif 000006
【図５】
2012221135.tif 000007
【図６】
2012221135.tif 000008
【図７】
2012221135.tif 000009
【図８】
2012221135.tif 000010
【図９】
2012221135.tif 000011
【図１０】
2012221135.tif 000012
【図１１】
2012221135.tif 000013
【図１２】
2012221135.tif 000014