(57)【要約】【課題】ＯｐｅｎＭＰのｐｒｉｖａｔｅ指示文が使用できない擬寸法配列を含むプログラムを並列化し、高速化すること。【解決手段】配列のデータフロー解析により、擬寸法配列が参照される可能性のある添字範囲を解析し、この参照範囲から上記擬寸法配列の宣言を作成することにより、上記擬寸法配列を整合配列にできる。これにより配列に対するＯｐｅｎＭＰ仕様によるｐｒｉｖａｔｅ化指示が可能となる。【選択図】    図１
2004157893.tif 000002
【特許請求の範囲】
【請求項１】
逐次プログラムまたは並列化指示文を含むプログラムを入力して並列化指示文を含むプログラムを出力するコンパイラにおいて、擬寸法配列が参照される可能性のある添字範囲を解析し、該添字範囲から上記擬寸法配列の宣言を作成することを特徴とする擬寸法配列の整合配列化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、逐次プログラムまたは指示文により並列化されたプログラムを入力して、指示文により並列化されたプログラムを出力するコンパイラにおける配列の参照範囲の解析方法および配列の宣言方法の変更に関する。
【０００２】
【従来の技術】
従来、逐次プログラムをＯｐｅｎＭＰ指示文を使った並列プログラムへ自動的に変換するトランスレータ技術として、配列の寸法が確定している配列に対してプライベート化可能か否かをデータフロー解析により判定し、可能であればその配列に対してＯｐｅｎＭＰのプライベート化指示節を生成するものがあった（例えば非特許文献１参照）。
【０００３】
【非特許文献１】
Ａｌａｎ  Ｊ．  Ｗａｌｌｃｒａｆｔ，  ”ＳＰＭＤ  ＯｐｅｎＭＰ  ｖｓ．  ＭＰＩ  ｆｏｒ  Ｏｃｅａｎ  Ｍｏｄｅｌｓ”，  Ｆｉｒｓｔ  Ｅｕｒｏｐｅａｎ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ＯｐｅｎＭＰ  （ＥＷＯＭＰ’９９），  （１９９９）
【０００４】
【発明が解決しようとする課題】
上記従来技術は、配列の寸法が確定しない擬寸法配列をプライベート化できないという問題点がある。これは、文献Ｒｏｈｉｔ  Ｃｈａｎｄｒａ，  Ｌｅｏｎａｒｄｏ  Ｄａｇｕｍ，  Ｄａｖｅ  Ｋｏｈｒ，  Ｄｒｏｒ  Ｍａｙｄａｎ，  Ｊｅｆｆ  ＭｃＤｏｎａｌｄ，  Ｒａｍｅｓｈ  Ｍｅｎｏｎ，  “Ｐａｒａｌｌｅｌ  Ｐｒｏｇｒａｍｍｉｎｇ  ｉｎ  ＯｐｅｎＭＰ”，  Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ（２００１）で述べられているように、ＯｐｅｎＭＰの仕様では、プライベート指示する配列は、その寸法が確定している必要があるためである。
【０００５】
本発明の目的は、データフロー解析の結果、プライベート化可能と判定された擬寸法配列をＯｐｅｎＭＰのｐｒｉｖａｔｅ指示節を用いてプライベート化することである。
【０００６】
【課題を解決するための手段】
上記目的を達成するために、本発明によるコンパイラは、擬寸法配列が参照される可能性のある添字範囲を解析し、添字範囲から上記擬寸法配列の宣言を作成するものである。
【０００７】
【発明の実施の形態】
以下、本発明の第１の実施例を図１から図４を用いて詳細に説明する。
【０００８】
図１は、本発明によるコンパイラシステムの構成図である。本発明のコンパイラ１００、入力プログラム１０７、出力プログラム１０８は記憶装置７に格納され、ＣＰＵ２が記憶装置から順次読み出して実行することとでコンパイル処理が実行される。ＣＰＵ２がワークメモリとして利用するメモリ３、ユーザからの指示等の入力を受け付けるキーボード４、コンパイル結果等をユーザに可視出力するディスプレイ５が内部バス６で相互通信可能に接続する。
【０００９】
コンパイラ１００は、入力プログラム１０７を入力し中間語１０９と変数の情報を持つ変数辞書１１０を出力する構文解析部１０１、中間語１０９と変数辞書１１０を入力し制御フローグラフ１１１を作成する制御フロー解析部１０２、中間語１０９と変数辞書１１０と制御フローグラフ１１１を入力し配列参照範囲情報１１２を出力するデータフロー解析部１０３、配列参照範囲情報１１２と変数辞書１１０を入力し変数辞書１１０を更新する擬寸法配列変換部１０４、中間語１０９と変数辞書１１０と制御フローグラフ１１１と配列参照範囲情報１１２を入力し中間語１０９と変数辞書１１０を更新する並列化変換部１０５、中間語１０９と変数辞書１１０を入力し出力プログラム１０８を生成する出力コード生成部１０６からなる。
【００１０】
構文解析部１０１、制御フロー解析部１０２、および、データフロー解析部１０３、は、コンパイラがもつ一般的な機能であるため、説明を省略する。
【００１１】
図２は、擬寸法配列変換部１０４のアルゴリズムである。まず、２０１で、プログラム内に未処理の配列がある場合、２０２の処理へ進む。２０２では、変数辞書１１０を調べ、配列の寸法を得て、２０３へ進む。２０３では、２０２で得た配列の寸法の上限が指定されているかを調べ、“＊”であれば、２０１へ進む。“＊”でなければ、２０４へ進む。２０４では、配列参照範囲情報１１２から解析対象となっている配列の参照範囲の情報を取り出す。取り出す配列の参照情報には、定義の参照範囲と使用の参照範囲がある。２０５では、２０４で得られた配列の定義の参照範囲と使用の参照範囲から、それぞれの上限の大きい方を求める。２０６では、２０５で求めた上限値が、解析対象の配列を宣言している関数や手続きの仮引数となる変数や、定数、および、それらを用いた式で表現できているかを調べる。表現できていないときは不定とし、２０１へ進む。不定でなければ２０７へ進む。２０７では、２０５で求めたものを配列の寸法の上限として変数辞書１１０を更新し、２０１へ進む。
【００１２】
図３は、入力プログラムの具体例である。図４は、図３の入力プログラム例をコンパイラ１００に入力したときに得られる出力プログラムの具体例である。以下、擬寸法配列変換部１０４の動作を、図３の入力プログラム例を入力した場合について述べる。
【００１３】
まず、２０１で、プログラム内の配列Ａ、配列Ｂ、配列Ｃに対して、２０２からの処理を行う。まず、配列Ａに対して２０２の処理を行う。２０２で、変数辞書１１０を調べて、配列Ａの寸法“＊”を得る。配列Ａの宣言文（図３の行番号３）の配列の寸法は、“＊”となっているため、変数辞書１１０でも同様に“＊”となっている。２０３で、配列Ａの配列の寸法が“＊”となっているので、２０４へ進む。２０４で、配列参照範囲情報１１２から配列Ａの定義の参照範囲として“１からＮ”と、使用の参照範囲として“１からＮ”を得る。２０５で、配列Ａの定義と使用の上限から大きい方を求め、Ｎを得る。２０６で、２０５で求めたＮは、仮引数として与えられているため、不定ではないので２０７へ進む。２０７で、Ｎを配列Ａの上限として変数辞書１１０を更新し、２０１へ進む。
【００１４】
図４の行番号３のように配列Ａの寸法がＮに変更される。２０１で、配列Ｂについて２０２からの処理を行う。２０２で、変数辞書１１０を調べ、配列Ｂの寸法Ｎを得る。２０３で、配列Ｂの寸法はＮで、不定ではないので、２０１へ進む。２０１で、配列Ｃについて２０２からの処理を行う。２０２で、変数辞書１１０を調べ、配列Ｃの寸法Ｎを得る。２０３で、配列Ｃの寸法はＮで、不定ではないので、２０１へ進む。２０１で、調べる配列がないので処理を終了する。
【００１５】
並列化変換部１０５では、中間語１０９、変数辞書１１０、制御フローグラフ１１１、配列参照範囲情報１１２から、入力プログラム中の並列化可能な部分を見つけ出し、中間語１０９を更新し、変数辞書１１０に並列化のための情報を追加する。
【００１６】
図３の入力プログラム例をコンパイラ１００に入力した場合、並列化変換部１０５は、並列化可能な部分として、図３の行番号５のループを見つけ出す。また、図３の行番号５のループを並列化するためには、配列Ａをプライベート化する必要があることも検出する。
【００１７】
配列Ａは、擬寸法配列変換部１０４において擬寸法配列から整合配列に変換されているため、ＯｐｅｎＭＰのｐｒｉｖａｔｅ指示節でプライベート化可能である。よって、図３の行番号５のループは、ＯｐｅｎＭＰ指示文で並列化可能となり、図４の行番号５、６、１３、１４にあるＯｐｅｎＭＰ指示文を作成し、中間語１０９を更新する。変数辞書１１０における配列Ａの情報にプライベート化の情報を付加する。コード生成部１０６では、中間語１０９と変数辞書１１０からＯｐｅｎＭＰ指示文で並列化されたプログラムをファイルに出力する。図３の入力プログラム例をコンパイラ１００へ入力した場合、コード生成部１０６は、図４の出力プログラム例を出力する。
【００１８】
以下、第２の実施例を図５、図６を用いて示す。コンパイラの構成は、図１と同じなので省略する。また、アルゴリズムも図２と同じなので省略する。
図５は、入力プログラムの具体例である。図６は、図５の入力プログラムをコンパイラ１００に入力したときの出力プログラムの具体例である。配列Ａの配列の寸法の宣言文に式が用いられている点が第１の実施例と異なる。以下、擬寸法配列変換部１０４の動作を、図５の入力プログラム例を入力した場合について述べる。
【００１９】
まず、２０１で、プログラム内の配列Ａ、配列Ｂ、配列Ｃに対して、２０２からの処理を行う。まず、配列Ａに対して２０２の処理を行う。２０２で、変数辞書１１０から配列Ａの寸法を調べて、“＊”を得る。２０３で、配列Ａの寸法が“＊”で不定となっているので、２０４へ進む。２０４で、配列参照範囲情報１１２から配列Ａの定義の参照範囲として“１からＮ”と“Ｘ”、使用の参照範囲として“１からＮ”を得る。２０５で、配列Ａの定義と使用の参照範囲の上限から大きい方を求める。定義の参照範囲の上限は、ＮまたはＸの大きい方となり、ＭＡＸ（Ｎ，Ｘ）となる。使用の参照範囲の上限はＮとなる。よって定義と使用の参照範囲の上限の大きい方は、ＭＡＸ（Ｎ，Ｘ）となる。
２０６で、２０５で求めたＭＡＸ（Ｎ，Ｘ）の式で使用されている変数は、変数Ｎも変数Ｘも仮引数の変数であるので不定ではない。よって２０７へ進む。２０７で、ＭＡＸ（Ｎ，Ｘ）を配列Ａの上限として変数辞書１１０を更新し、２０１へ進む。
【００２０】
図６の行番号３のように配列の寸法がＭＡＸ（Ｎ，Ｘ）に変更される。２０１で、配列Ｂについて２０２からの処理を行う。２０２で、変数辞書１１０を調べ、配列Ｂの寸法Ｎを得る。２０３で、配列Ｂの寸法はＮで、不定ではないので、２０１へ進む。２０１で、配列Ｃについて２０２からの処理を行う。２０２で、変数辞書１１０を調べ、配列Ｃの寸法Ｎを得る。２０３で、配列Ｃの寸法はＮで、不定ではないので、２０１へ進む。２０１で、調べる配列がないので処理を終了する。
【００２１】
図５の入力プログラム例をコンパイラ１００に入力した場合、並列化変換部１０５では、並列化可能な部分として、図５の行番号５のループを見つけ出す。また、図５の行番号５のループを並列化するためには、配列Ａをプライベート化する必要があることも検出する。
【００２２】
配列Ａは、擬寸法配列変換部１０４において擬寸法配列から整合配列に変換されているため、ＯｐｅｎＭＰのｐｒｉｖａｔｅ指示節でプライベート化可能である。よって、図５の行番号５のループは、ＯｐｅｎＭＰ指示文で並列化可能となり、図６の行番号５、６、１３、１４にあるＯｐｅｎＭＰ指示文を作成し、中間語１０９を更新する。変数辞書１１０における配列Ａの情報にプライベート化の情報を付加する。図３の入力プログラム例をコンパイラ１００へ入力した場合、コード生成部１０６では、図４の出力プログラム例を出力する。
【００２３】
【発明の効果】
本発明により、擬寸法配列が整合配列になることにより、この擬寸法配列のＯｐｅｎＭＰ仕様によるプライベート化が可能になり、従来、プライベート化ができないために並列化不可能であったプログラムを並列化可能にし、プログラムを高速に実行することができる。
【図面の簡単な説明】
【図１】本発明の一実施例のコンパイラを有するシステム構成図。
【図２】擬寸法配列解析部のアルゴリズムを示したフローチャート。
【図３】入力プログラムの例１を示した図。
【図４】図３の入力プログラムに対する出力プログラムの例１を示した図。
【図５】入力プログラムの例２を示した図。
【図６】図５の入力プログラムに対する出力プログラムの例２を示した図。
【符号の説明】
１００…コンパイラ、１０１…構文解析部、１０２…制御フロー解析部、１０３…データフロー解析部、１０４…擬寸法配列変換部、１０５…並列化変換部、１０６…出力コード生成部、１０７…入力プログラム、１０８…出力プログラム、１０９…中間語、１１０…変数辞書、１１１…制御フローグラフ、１１２…配列参照範囲情報。
【図１】
2004157893.tif 000003
【図２】
2004157893.tif 000004
【図３】
2004157893.tif 000005
【図４】
2004157893.tif 000006
【図５】
2004157893.tif 000007
【図６】
2004157893.tif 000008