(57)【要約】【課題】プロセス並列プログラムの最適化処理の効果を高くする。【解決手段】並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、を有する処理をコンピュータに実行可能なコンパイルプログラム。【選択図】図６
2018081592.tif 000002
【特許請求の範囲】
【請求項１】
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有する処理をコンピュータに実行可能なコンパイルプログラム。
【請求項２】
前記処理は、更に、
他のプロセスの前記イメージ番号に依存する所定情報への参照を含む命令に前記所定情報の定数を設定する第２の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程を有する、請求項１に記載のコンパイルプログラム。
【請求項３】
前記処理は、更に、
前記第１の最適化処理を繰り返し行う工程の前に、前記ソースプログラム内の前記イメージ番号を表す関数及び変数を任意の固定値に置換し、定数伝搬し、前記条件文が定数になる条件付き分岐命令を削除可能分岐命令として抽出する工程を有し、
前記削除可能分岐命令それぞれについて、前記第１の最適化処理を実行する、請求項１に記載のコンパイルプログラム。
【請求項４】
前記処理は、更に、
前記削除可能分岐命令抽出工程後且つ前記最適化対象プログラム生成工程前に、前記ソースプログラム内の前記削除可能分岐命令の前記条件文の判定結果が一致する複数のイメージ番号を同じプロセスグループにグループ化するプロセスグループ化工程を有し、
前記最適化対象プログラムの生成工程では、前記グループ化された複数のイメージ番号に対して共通の最適化対象プログラムを生成する、請求項３に記載のコンパイルプログラム。
【請求項５】
前記最適化対象プログラム生成工程と前記第１の最適化処理工程を、前記プロセスグループ毎に実行し、
前記第１の最適化処理は、単一のイメージ番号に対応する最適化対象プログラムにおいて、前記イメージ番号を表す関数及び変数を前記単一のイメージ番号で定数化することを含む、請求項４に記載のコンパイルプログラム。
【請求項６】
前記第１の最適化処理は、前記条件付き分岐命令の削除後、定数伝搬を含む汎用最適化処理と、繰り返し処理をSIMD化する処理とを行う、請求項１に記載のコンパイルプログラム。
【請求項７】
前記所定情報が参照する他のプロセスの動的領域の大きさであり、
前記第２の最適化処理工程は、前記動的領域の大きさが定数の場合、前記大きさに定数を設定することを含む、請求項２に記載のコンパイルプログラム。
【請求項８】
前記所定情報が参照する他のプロセスの共配列の値であり、
前記第２の最適化処理工程は、前記共配列の値が定数の場合、前記共配列の値に定数を設定することを含む、請求項２に記載のコンパイルプログラム。
【請求項９】
前記第２の最適化処理工程は、前記定数を設定した後、定数伝搬を含む汎用最適化処理と、SIMD化が可能な場合繰り返し処理をSIMD化する処理とを行う、請求項２に記載のコンパイルプログラム。
【請求項１０】
前記処理は、更に、
前記イメージ番号それぞれに生成した複数の最適化対象プログラムそれぞれを変換し、複数の実行プログラムを生成する工程を有する請求項１に記載のコンパイルプログラム。
【請求項１１】
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有するコンパイル方法。
【請求項１２】
メモリと、
前記メモリに接続されたプロセッサを有し、
前記プロセッサは、
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有する処理を実行するコンパイル装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，コンパイルプログラム、コンパイル方法、およびコンパイル装置に関する。
【背景技術】
【０００２】
並列プログラミング言語で記述されたプログラム（以下プロセス並列プログラム）は、複数の情報処理装置（以下コンピュータ）により並列に実行される。複数のコンピュータが並列に実行する処理を、本明細書ではプロセスと称する。
【０００３】
プロセス並列プログラムの1つに、区分化グローバルアドレス空間（PGAS：Partitioned Global Address Space）を採用する並列プログラミング言語がある。例えば、フォートラン２００８（Fortran 2008）の共配列(coarray)や、UPC（Unified Parallel C）などである。このPGASを採用する並列プログラミング言語で記述されたプログラムは、複数のコンピュータが並列に実行する。そして、複数のコンピュータは、それぞれ、プロセッサ（CPU：Central Processing Unit）と、各プロセッサがアクセス制御するメインメモリを有する。この複数のメインメモリはグローバルアドレス空間を構成し、グローバルアドレス空間が各プロセッサに区分された分散メモリである。
【０００４】
そして、プロセス並列プログラムは、実行時にプロセス毎に動的に異なる大きさのメモリ領域を割り当て、各プロセスから他のプロセスのメモリ領域を参照することができる。但し、自分のプロセスのメモリ領域を参照するよりも、他のプロセスのメモリ領域を参照するほうが、参照コスト（例えばアクセス時間）が大きい。これが区分化グローバルアドレス空間の概略である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−１９９５２０号公報
【特許文献２】特開平０６−２５０９８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の複数のプロセスで実行されるプロセス並列プログラムは、逐次実行のプログラムと比較して、コンパイラによる最適化処理の効果が低い場合がある。例えば、プロセス毎に異なるメモリサイズを動的に割当可能な変数や配列の演算処理は、SIMD（Single Instruction Multiple Data）化やループアンローリングによる最適化処理に不向きである。その理由は、最適化時はプロセス毎に異なる演算処理の繰り返し回数に対応する必要があるため、コンパイラはSIMD化処理で多くの比較命令（割り当てサイズに達したかの判定を行う比較命令）を生成するからである。また、ループアンローリングを行う最適化処理でも同様の理由で多くの比較命令を生成する。したがって、比較命令によるオーバーヘッドによって、最適化の効果は低くなる。
【０００７】
さらに、例えば、プロセス毎に異なるサイズを動的に割り当て可能な変数や配列を異なるプロセス間でコピーする場合、コピー先のプロセスがコピー元のプロセスにサイズを問い合わせる。そして、コピー元とコピー先のサイズが異なる場合、コピー先のプロセスは、コピー先のメモリ領域を解放し、コピー元と同じサイズのメモリ領域を確保した後に、コピーを実行する。この場合、プロセス間のサイズの確認のための参照処理は高いコストを要するため、最適化の効果が低い。
【０００８】
また、例えば、汎用の最適化処理の1つである定数伝搬と分岐命令の削除を行う場合、以下の理由で最適化の効果が低い。すなわち、プロセス並列プログラムの実行時のプロセス番号は、実行中に変化しない実行時定数であり、実行時に各プロセスにおいてそのプロセス番号が確定する。しかし、コンパイル時は最適化プログラムを複数のプロセス番号に対応可能にしておく必要がある。その結果、コンパイル時ではプロセス番号を定数化することができず、定数伝搬を利用できない。
【０００９】
そして、例えば、プロファイリング結果を反映した静的コンパイルでは、プロセス番号に関連する条件付き分岐命令の条件判定がプロセス毎に異なりまたは逆になり、分岐命令の削除などの最適化処理が困難である。
【００１０】
そこで，本実施の形態の第1の側面の目的は，プロセス並列プログラムの最適化処理の効果を高くするコンパイルプログラム、コンパイル方法、およびコンパイル装置を提供することにある。
【課題を解決するための手段】
【００１１】
本実施の形態の第１の側面は，並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、を有する処理をコンピュータに実行可能なコンパイルプログラムである。
【発明の効果】
【００１２】
第１の側面によれば，プロセス並列プログラムの最適化の効果が高くなる。
【図面の簡単な説明】
【００１３】
【図１】本実施の形態におけるコンパイルされたプログラムを実行する実行コンピュータの構成例を示す図である。
【図２】ＰＧＡＳを採用している並列プログラミング言語で記述されたソースプログラムの一例を示す図である。
【図３】図２の共配列co(100)[*]を示す図である。
【図４】区分化されたグローバルアドレス空間（PGAS：Partitioned Global Address Space）を示す図である。
【図５】コンパイラがソースプログラムを単一の実行プログラムに翻訳（変換）し複数のプロセスで並列に実行することを示す図である。
【図６】本実施の形態におけるコンパイルプログラムの概略処理のフローチャートを示す図である。
【図７】本実施の形態における実行プログラムの各プロセスへのロードと実行を示す図である。
【図８】第１の実施の形態におけるコンパイラの処理のフローチャートを示す図である。
【図９】削除可能な分岐特定処理のフローチャートを示す図である。
【図１０】図２のソースプログラムを例にして削除可能な分岐特定処理を具体的に示す図である。
【図１１】イメージ番号固有化処理のフローチャートを示す図である。
【図１２】包括的最適化処理のフローチャートを示す図である。
【図１３】図８に基づいて図９、図１１、図１２を結合したコンパイラの最適化処理の全体のフローチャートを示す図である。
【図１４】イメージ１，２，３〜ｎに対して生成され、図１１の最適化処理がされた最適化対象プログラムを示す図である。
【図１５】１８行目の演算命令をＳＩＭＤ化したコード例を示す図である。
【図１６】１８行目の演算命令をＳＩＭＤ化したコード例を示す図である。
【図１７】２５行目の演算命令をＳＩＭＤ化したコード例を示す図である。
【図１８】２５行目の演算命令をＳＩＭＤ化したコード例を示す図である。
【図１９】他のプロセスの共配列への参照を有するプログラム例と包括的最適化処理を示す図である。
【図２０】図８の実行プログラム生成処理のフローチャートを示す図である。
【図２１】プロセス並列プログラムを実行するときに行われる実行プログラムのロード処理のフローチャートを示す図である。
【図２２】ロード処理プログラムが添付された実行プログラム群を示す図である。
【図２３】第２の実施の形態におけるコンパイラの処理のフローチャートを示す図である。
【図２４】プロセスグループ決定処理のフローチャートを示す図である。
【図２５】プロセスグループ表の一例を示す図である。
【図２６】第２の実施の形態における実行時のロード処理のフローチャートを示す図である。
【図２７】第２の実施の形態における実行プログラムのロードと実行を示す図である。
【図２８】中間表現のプログラム例とそのフローチャートとを示す図である。
【発明を実施するための形態】
【００１４】
図１は、本実施の形態におけるコンパイルされたプログラムを実行する実行コンピュータの構成例を示す図である。また、図１の実行コンピュータ20_1は、本実施の形態におけるコンパイル装置でもある。
【００１５】
本実施の形態では、コンパイラが、並列プログラミング言語で記述されたソースプログラム（プロセス並列プログラム）を最適化し、実行プログラムを生成する。そして、図１に示される実行コンピュータが実行プログラムを実行する。すなわち、複数の実行コンピュータ20_1,20_2が、実行プログラムを並列に実行する。例えば、２つの実行コンピュータが、それぞれのプロセスで実行プログラムを並列に実行する。但し、単一の実行コンピュータが複数のプロセスで実行プログラムを並列に実行してもよい。
【００１６】
実行コンピュータは、複数の演算コアＣＯＲＥとＬ２キャッシュＬ２＿ＣＡＣＨＥとメモリコントローラＭＡＣとを有するＣＰＵ（Central Processing Unit、以下プロセッサと称する）１０と、ＣＰＵのメモリコントローラＭＡＣによりアクセス制御されるメインメモリ１２と、補助記憶装置であるストレージ１４とを有する。さらに、実行コンピュータは、ネットワークＮＷに接続されるネットワークインターフェース１３と、外部との入出力を制御する入出力制御部１１と、それらを接続するバス１８とを有する。
【００１７】
ストレージ１４は、ＯＳ（Operating System）１５と、実行プログラム１６とを格納する。また、左側の実行コンピュータ20_1のストレージ１４は、OSと実行プログラムに加えて、コンパイルプログラム１７も格納する。ＯＳ１５，実行プログラム１６、コンパイルプログラム１７は、メインメモリ１２に展開されＣＰＵ１０により実行される。
【００１８】
図２は、ＰＧＡＳを採用している並列プログラミング言語で記述されたソースプログラムの一例を示す図である。図２のソースプログラムは、フォートラン（Fortran）２００８の共配列（coarray）の機能を有する。以後、このソースプログラムを具体例にして実施の形態の説明を行う。
【００１９】
このソースプログラムを簡単に説明すると、以下のとおりである。
・２行目：変数ｘの１次元の大きさが動的に割り付けされることを定義する。
・５行目：共配列coが大きさ１００の配列であることを定義する。「＊」はイメージ番号であり、イメージは実行単位（実行時のプロセス）に対応する。また、イメージ番号は[]内に指定される。但し、ローカルのイメージ番号を示す[]は省略可能である。
・７行目：イメージ番号が２と等しいという条件文を有する分岐命令、if文である。関数this_image()は、イメージ番号を表し、ローカルのイメージ番号を呼び出す。
・９行目：イメージ番号が２の場合、共配列co(i)の成分ｘが大きさ８になるようメモリ領域を確保する。％は成分を意味する。
・１３行目：イメージ番号が２以外の場合、共配列co(i)の成分ｘが大きさ１０になるようメモリ領域を確保する。
・１８行目：ローカルの共配列coの各要素co(i)の成分ｘの各要素に値０を代入する。したがって、成分ｘのサイズに対応する回数、値０を代入する演算処理を行う。
・２１行目：全プロセスで同期をとる。
・２３行目：イメージ番号が１以外という条件文を有する分岐命令、if文である。
・２５行目：イメージ番号が１以外の場合、ローカルの配列coの各成分ｘに、プロセス１の共配列coの成分ｘの内容をコピーする。この演算を実行する場合次の処理が行われる。すなわち、プロセス１の共配列coの成分ｘの大きさを取得し、ローカルの共配列coの成分ｘの大きさと異なる場合、ローカルの共配列coの成分ｘのメモリ領域を解放し、そして新たにプロセス１と同じ大きさのメモリ領域を確保し、その後、プロセス１の共配列coの成分ｘの値を取得し、ローカルの共配列coの成分ｘに代入する。
【００２０】
図３は、図２の共配列co(100)[*]を示す図である。左側はイメージ番号が２以外の１，３−ｎの場合の、１３行目のメモリ領域確保（allocate(co(i)%x(10))に基づく構成を示す。また、右側はイメージ番号が２の場合の、９行目のメモリ領域確保（allocate(co(i)%x(8))に基づく構成を示す。
【００２１】
左側の例では、配列coが１００の要素co(1)-co(100)を有し、それぞれの要素が１０の要素x(1)-x(10)を有する成分ｘを有する。つまり、成分ｘが大きさ１０（１０の要素）である。一方、右側の例では、配列coが１００の要素co(1)-co(100)を有し、それぞれの要素が８の要素x(1)-x(8)を有する成分xを有する。つまり、成分ｘが大きさ８（８の要素）である。
【００２２】
図４は、区分化されたグローバルアドレス空間（PGAS：Partitioned Global Address Space）を示す図である。図中、円はプロセスＰ１−Ｐ４を示し、矩形は各プロセスがアクセスする共有メモリを示す。メモリのグローバルアドレス空間は、破線により４つのメモリ空間に区分されている。そして、各プロセスは、それぞれのローカルなメモリ空間に低いコストでアクセスＡＣ１を実行可能であり、一方、各プロセスは、異なるプロセスのメモリ空間に高いコストでアクセスＡＣ２を実行可能である。
【００２３】
例えば、図１に示した各実行コンピュータのプロセッサ（ＣＰＵ）は、そのメモリコントローラＭＡＣを経由してそれぞれのメインメモリ１２にアクセスする（ＡＣ１）。一方、各プロセッサ（ＣＰＵ）は、異なる実行コンピュータのプロセッサ（ＣＰＵ）にメッセージを送信し、メッセージを受信したプロセッサがメモリコントローラＭＡＣを経由してそれぞれのメインメモリ１２にアクセスする（ＡＣ２）。したがって、ローカルなメモリ空間へのアクセスコストは低いが、異なるプロセッサのメモリ空間へのアクセスコストは高い。
【００２４】
上記のとおり、フォートラン２００８のイメージ（image）は、プログラム実行時の実行単位、つまりプロセスに対応する。そこで、以下の説明では、フォートランのソースプログラムの局面では「イメージ（image）」と称し、プログラム実行時の局面では「プロセス」と称する。
【００２５】
図５は、コンパイラがソースプログラムを単一の実行プログラムに翻訳（変換）し複数のプロセスで並列に実行することを示す図である。一般に、ＰＧＡＳを採用する並列プログラミング言語で記述されたプログラム、例えば、図２に示したFortran 2008の共配列coarrayの機能を有するプログラムは、通常、コンパイラにより単一の実行プログラムに翻訳され、複数のプロセスに単一の実行プログラムがロードされ、複数のプロセスが実行プログラムを並列に実行する。
【００２６】
複数のプロセスで実行されるプログラムは、逐次実行のプログラムと比較すると、コンパイラによる最適化処理の効果が低い場合がある。最適化効果が低い４つの例について以下説明する。
【００２７】
（１）第１の例は、例えば、図２の１８行目の配列の各要素co(i)の成分ｘに値０を代入する命令（co(i)%x=0）である。この命令を実行すると、成分ｘの大きさの回数、値０を代入する処理が繰り返される。このように処理が複数回繰り返される命令には、通常、コンパイラはSIMD化やループアンローリングによる最適化を行う。例えば、SIMD化により繰り返し回数をSIMD演算器の数（4つのデータを１つの命令文で処理する4SIMDなら４）で除した数の命令に変換できる。またループアンローリングによりループの分岐命令のオーバーヘッドを削減できる。
【００２８】
しかし、図２のプログラムの場合、イメージ番号に依存して成分ｘの大きさが異なり、そのため、繰り返し回数がイメージ番号に依存して異なる。その結果、コンパイラは、最適化処理において、イメージ番号毎に繰り返し回数を異ならせるために複数の比較命令を追加する必要がある。この複数の比較命令によるオーバーヘッドが、SIMD化による最適化効果を超える場合、逆に効率が低下する。ループアンローリングを行っても追加した複数の比較命令によるオーバーヘッドが最適化効果を限定的にする。
【００２９】
（２）第２の例は、例えば、図２の２５行目のイメージ番号毎（プロセス毎）に異なるサイズを動的に割り当て可能な変数や配列の成分を、異なるイメージ番号間（異なるプロセス間）でコピーする命令（co(i)%x=co(i)[1]%x）である。この命令は、コピー先であるローカルのイメージ番号の配列coの各成分（co(i)%x）に、コピー元のイメージ番号「１」の配列coの各成分の値（co(i)[1]%x）をコピーする。さらに、成分ｘはALLOCATABLE属性を有する。そのため、コピー先のイメージ番号の配列coの成分ｘのサイズが、ローカルのイメージ番号が２ならサイズ８、２以外ならサイズ１０と異なっている。一方、コピー元のイメージ番号１の配列coの成分ｘのサイズは１０である。そのため、コピー元とコピー先の成分ｘのサイズが異なる場合、コピー先の成分ｘのサイズをコピー元の成分ｘのサイズに合わせる必要がある。
【００３０】
そこで、上記のコピーする命令は、ローカルのプロセスが、コピー元であるイメージ番号１の配列coの成分ｘのサイズを問い合わせる処理と、コピー先（ローカル）の配列coの成分ｘのサイズがコピー元のイメージ番号１の配列の成分ｘのサイズとが異なる場合に、コピー先のメモリ領域を解放し、コピー元と同じサイズのメモリ領域を確保する処理と、コピー元から成分ｘの値を取得しコピー先の成分ｘにコピーする処理とを伴う。
【００３１】
そのため、コンパイラは実行プログラムに変換するとき、ローカルのプロセスが、異なるプロセスへ成分ｘのサイズを問い合わせる通信を実行するコードを追加する。このような異なるプロセスへ成分ｘのサイズを参照する処理は、高い通信コストを必要とし、最適化効果が抑制される。
【００３２】
（３）第３の例は、例えば、図２の7行目と２３行目のイメージ番号が影響する条件を有する分岐命令である。７行目のif分はイメージ番号が「２」と等しいという条件を有し、２３行目のif分はイメージ番号が「１」以外という条件を有する。
【００３３】
汎用の最適化処理の1つとして、定数伝搬と、伝搬した定数により条件文が真または偽になる場合の分岐命令の削除などがある。プロセス並列プログラムの場合、イメージ番号（プロセス番号）は実行中に変化しない実行時定数であり、定数伝搬の対象になりうる。しかし、プログラム実行時には各プロセスにおいてそのイメージ番号（プロセス番号）が確定し定数になるが、コンパイル時は、未だ各プロセスによる実行状態ではない。そのため、コンパイラは、最適化プログラムを複数のプロセス番号に対応可能に記述する必要がある。その結果、コンパイラは、コンパイル時、プロセス番号を定数化することができず、定数伝搬を利用できない。
【００３４】
（４）第４の例も、第３の例と同じ図１の７行目と２３行目の条件付き分岐命令である。汎用の最適化処理の１つとして、プロファイリング結果を反映して、分岐命令の条件文のプロファイリング結果が全て真の場合は、分岐命令を削除し条件文が偽の場合のコードを削除することが行われる。
【００３５】
しかし、プロセス並列プログラムの場合、各プロセスにおいてイメージ番号が異なるため、プロファイリング結果ではイメージ番号に依存する条件文を持つ分岐命令の条件文が全て真または偽にならず、上記の汎用化処理を行うことができない。７行目のif文は、プロセス１では１００％偽に分岐し、プロセス２では１００％真に分岐する。したがって、このようなプロファイリング結果では、一般に最適化することができない。
【００３６】
［第１の実施の形態］
図６は、本実施の形態におけるコンパイルプログラムの概略処理のフローチャートを示す図である。プロセッサがコンパイラを実行することで、フローチャートの各処理を実行する。プロセッサは、まず原始言語のプログラム（ソースプログラム）Ｓ＿ＰＲＧを入力しストレージ１４に格納する（Ｓ１）。そして、プロセッサは、全プロセスそれぞれについて（Ｓ２，Ｓ５）、ソースプログラムを複製して各プロセスのプログラムを生成し（Ｓ３）、各プロセスのプログラムを最適化処理する（Ｓ４）ことを、繰り返す（Ｓ５）。その結果、プロセス１−ｎのｎ個の実行プログラムＥＸ＿ＰＲＧ＿１〜ＥＸ＿ＰＲＧ＿ｎが生成される。
【００３７】
そして、コンパイラは、プログラム実行時に、各実行プログラムを対応する各プロセスのメモリ空間にロードし、それぞれの実行プログラムを並列に実行する。コンパイラは、そのようなロードプログラムをｎ個の実行プログラムに添付して実行プログラムファイルを生成するようにしてもよい。
【００３８】
図７は、本実施の形態における実行プログラムの各プロセスへのロードと実行を示す図である。図５のロードと実行と異なり、本実施の形態では、プロセス毎に生成しプロセス毎に最適化した実行プログラムＥＸ＿ＰＲＧ＿１〜ＥＸ＿ＰＲＧ＿ｎが、各プロセスを実行するプロセッサのメインメモリにロードされ、各プロセスで実行される。
【００３９】
図６の各プロセスのプログラムの最適化処理（Ｓ４）では、プロセス番号（イメージ番号）を定数化することができる。さらに、イメージ番号に依存する条件文を定数化できる場合がある。したがって、上記した第３の例、第４の例において、プロセッサは、コンパイル時にイメージ番号を定数化して定数伝搬することができ、条件文の判定が定数化され（真または偽のいずれかになり）、その分岐命令を削除し、条件文の判定と逆の場合に実行されるコードを削除できる。
【００４０】
また、各プロセスにおいてサイズが動的に割り当てられる変数は、特定のプロセスの実行プログラムであればそのサイズが確定する。そのため、第１の例に関して、各プロセスの実行プログラムにおける繰り返し回数が確定し、ＳＩＭＤ化やループアンローリングにおいて、複数の比較命令が不要になる。また、第２の例に関して、各プロセスで変数のサイズが確定するので、他のプロセスに変数のサイズを問い合わせる通信命令文などを省略することができる。また、コピー命令文において、他のプロセスの配列の値を定数化できる場合があり、コピー元の値を参照する通信命令文も省略できる場合がある。このコピー命令文の例は図２にないので、後述する図１９で説明する。
【００４１】
［コンパイラの処理］
図８は、第１の実施の形態におけるコンパイラの処理のフローチャートを示す図である。コンパイルプログラムを実行するプロセッサは、原始言語のプログラム（ソースプログラム）を入力しストレージに格納する（Ｓ１０）。図２に示したフォートラン２００８の共配列とALLOCATABEL属性の変数を有するプログラムが、ソースプログラムの一例である。
【００４２】
次に、プロセッサは、ソースプログラムの中間表現のプログラムを生成する（Ｓ１１）。中間表現のプログラムは、ソースプログラムのコードを、コンパイラの中間言語により記述されたコードに置換したプログラムである。プロセッサは、ソースプログラムの最適化効率を高めることを目的として、ソースプログラムを中間表現のプログラムに変換する。
【００４３】
図２８は、中間表現のプログラム例とそのフローチャートとを示す図である。フォートランで記述されたソースプログラム３０は、ローカルのイメージ番号を呼び出す関数this_image()が変数ｘと等しい場合、変数ａに変数ｂとｃの加算値を代入するというコードを有する。これに対して、中間表現のプログラム３１は、まず、変数ｔ１に変数ｘを代入し（３１１）、変数ｔ２に関数this_image()の戻り値（ローカルのイメージ番号）を代入し（３１２）、変数ｔ１と変数ｔ２が等しい場合（３１３）、変数ｔ３に変数ｂとｃの加算値を代入し（３１４）、変数ａに変数ｔ３を代入する（３１５）というコードを有する。
【００４４】
上記のように、変数ｔ１、ｔ２、ｔ３に値を代入してから、その変数で条件文や代入文を記述したプログラムは、最適化処理が容易になるまたは効果が高まる場合がある。
【００４５】
このように、ソースプログラムと中間表現プログラムは実質的には同じソースプログラムであり、中間表現プログラムはオリジナルのソースプログラムの記述を一部変更したにすぎない。そこで、以下、図２のソースプログラムを中間表現プログラムとして説明する。
【００４６】
図８に戻り、プロセッサは、中間表現のプログラムについて、汎用最適化処理を実行する（Ｓ１２）。汎用最適化処理は、例えば、定数伝搬、分岐命令の削除など、実行プログラムを実行するコンピュータのアーキテクチャに依存しない最適化処理である。また、汎用最適化処理に加えて、実行コンピュータのアーキテクチャに依存するＳＩＭＤ化などの最適化処理を行っても良い。ソースプログラムが中間表現のプログラムに変換されているので、上記の汎用最適化処理やＳＩＭＤ化などにより最適化が進むことがある。
【００４７】
次に、プロセッサは、中間表現のプログラム内の削除可能な分岐命令を特定する処理を実行する（Ｓ１３）。削除可能な分岐命令とは、各プロセスでのローカルなイメージ番号が確定すれば分岐命令の条件文が定数（真または偽のいずれか）になる分岐命令である。つまり、ローカルなイメージ番号に依存する条件文を有する分岐命令である。中間表現のプログラムを複写して各プロセスのために生成した中間表現のプログラムでは、それぞれのプロセス番号が確定している。そのため、分岐命令の条件文の判定結果が定数になる場合があり、分岐命令を削除するなどの最適化を行うことができる。
【００４８】
この処理Ｓ１３では、プロセッサは、中間表現のプログラムにおいて、イメージ番号を表す関数や変数を任意の定数値に置換し、定数伝搬し、条件文が定数（真または偽のいずれか）になる分岐命令を削除可能な分岐リストに加える。この処理については、後述する図９にて詳細に説明する。
【００４９】
そして、プロセッサは、全プロセスそれぞれについて（Ｓ１４、Ｓ１６）、イメージ番号の固有化処理を繰り返し実行する（Ｓ１５）。イメージ番号の固有化処理は、中間表現のプログラムの複製を複数のイメージ（複数のプロセス）それぞれに生成し、複製した中間表現のプログラム（最適化対象の中間表現プログラム）において、対応するイメージ番号に基づいて分岐命令の削除、イメージ番号の代入、汎用最適化処理やＳＩＭＤ化処理を実行する。具体的には、図１１で説明する。
【００５０】
さらに、プロセッサは、全プロセスそれぞれについて（Ｓ１７，Ｓ１９）、包括的最適化処理を実行する（Ｓ１８）。イメージ番号の固有化処理Ｓ１５が終了すると、各プロセスの最適化対象の中間表現プログラムが最適化されている。そこで、包括的最適化処理では、プロセッサは、各プロセスの最適化対象の中間表現プログラムにおいて、他のプロセスの動的領域を参照するコードに、参照先のプロセスの動的領域の大きさ（定数）に設定したり、他のプロセスの共配列を参照するコードに、参照先のプロセスの共配列の値を設定したりする。具体的には、図１２で説明する。
【００５１】
最後に、プロセッサは、最適化された最適化対象の中間表現プログラムからコンパイラの目的言語のプログラムコードを生成する（Ｓ２０）。例えば、ソースプログラムがフォートランであれば、目的言語のプログラムは、アセンブリ言語のプログラムや、そのオブジェクト言語の実行プログラムなどである。
【００５２】
［削除可能な分岐特定処理］
図９は、削除可能な分岐特定処理のフローチャートを示す図である。削除可能な分岐特定処理Ｓ１３は、まず、中間表現のプログラムを複製する処理Ｓ１３１を有する。そして、プロセッサは、複製した中間表現のプログラムに対して、以降の処理を実行する。
【００５３】
次に、プロセッサは、中間表現のプログラム中のイメージ番号を表す関数または変数、例えばローカルのイメージ番号を戻り値とする関数this_image()、それぞれについて（Ｓ１３２）、関数（または変数）Ｘを任意の定数、例えば「０」など、で置換する（Ｓ１３３）。図２のソースプログラムにはイメージ番号を表す変数の例は示されていない。
【００５４】
そして、プロセッサは、関数Ｘを任意の定数で置換したことによる定数伝搬を実行する（Ｓ１３４）。これにより、例えば、関数this_image()の演算命令や条件文が定数化される場合がある。そこで、プロセッサは、中間表現のプログラム中の条件付き分岐命令それぞれについて（Ｓ１３６）、条件付き分岐命令の条件文が定数（真または偽のいずれか）になっていないかをチェックし（Ｓ１３６）、定数になっている条件付き分岐命令を削除可能な分岐リストに追加する（Ｓ１３７）。
【００５５】
図１０は、図２のソースプログラムを例にして削除可能な分岐特定処理を具体的に示す図である。プロセッサは、左側のソースプログラムＳ＿ＰＲＧの７行、２３行に記述されているイメージ番号を表す関数this_image()を抽出し、任意の定数、例えば「０」と置換する（Ｓ１３３）。そして、プロセッサは、定数伝搬を実行する（Ｓ１３４）。但し、図１０の左側のソースプログラムＳ＿ＰＲＧでは関数this_image()を定数「０」と置換した後、定数伝搬は発生しない。
【００５６】
定数伝搬が発生するプログラム例は、例えば以下の記述である。
ｔ１＝this_image()
if (t1 == 2) then
このプログラムにおいて、関数this_image()を定数「０」に置換すると、次の通りになる。
ｔ１＝０
if (t1 == 2) then
そして、ｔ１＝０について定数伝搬すると、次のようになる。
ｔ１＝０
if (０ == 2) then
この結果、条件付き分岐文であるif文の条件文（0 == 2）は偽になり定数になる。上記のとおり、定数伝搬によりif文の条件文が定数になる場合がある。
【００５７】
但し、以下のようなプログラムの場合は、分岐命令の条件文に変数ａがあるので、関数this_image()をイメージ番号で置換しても、条件文の判定結果が定数にはならず、削除可能な分岐命令にはならない。
ｔ１＝this_image()
if (t1 == a) then
図１０に戻り、プロセッサは、イメージ番号を表す関数または変数を定数で置換し、定数伝搬した結果、右側のソースプログラムＳ＿ＰＲＧ＿１の７行、２３行の条件付き分岐命令を、削除可能な分岐命令として特定し、削除可能な分岐リストに追加する。
【００５８】
［イメージ番号固有化処理］
図８に示される通り、図９に示した中間表現のプログラムから削除可能な分岐特定処理Ｓ１３を行った後、複数のプロセスそれぞれに対して、イメージ番号固有化処理Ｓ１５を繰り返し実行する。これにより複数のプロセスそれぞれに最適化対象の中間表現プログラムが生成され、その複数の最適化対象の中間表現プログラムそれぞれに対して第１の最適化処理が実行される。
【００５９】
図１１は、イメージ番号固有化処理のフローチャートを示す図である。図１１には、図８の全プロセスＰ（または全プロセスグループＧ）について繰り返し実行する処理Ｓ１４，Ｓ１６も示されている。プロセスグループについては後述する第２の実施の形態で説明する。
【００６０】
コンパイラを実行するプロセッサは、全プロセスそれぞれに対して（Ｓ１４）、工程Ｓ１５１〜Ｓ１５８を繰り返し実行する。すなわち、プロセッサは、中間表現のプログラムを複製して対象のプロセス（イメージ番号）の最適化対象の中間表現のプログラム（以下、簡単のために最適化対象プログラムと称する場合がある。）を生成する（Ｓ１５１）。そして、対象のプロセスの最適化対象プログラムに対して以下の最適化処理を行う。
【００６１】
次に、プロセッサは、最適化対象プログラム内の削除可能な分岐リスト内の各削除可能分岐命令それぞれについて（Ｓ１５２）、イメージ番号を表す関数及び変数を処理対象のイメージ番号に置換し、定数伝搬し、その後、条件文が真か偽かをチェックし（Ｓ１５３）する。プロセッサは、最適化対象プログラムについて、条件文が偽の場合は、分岐命令と条件文が真の場合に実行されるコードとを削除し（Ｓ１５４）、逆に、真の場合は、分岐命令と条件文が偽の場合に実行されるコードとを削除する（Ｓ１５５）。
【００６２】
この処理により、図２のソースプログラム内の７行、２３行の分岐命令が削除され、条件文の値（判定結果）とは異なる場合に実行されるコードが削除される。したがって、７〜１５行目のコードは、プロセス番号が「２」の場合は、７、１１、１５行目の分岐命令と、１２〜１４行目のコード（条件文が偽の場合に実行されるコード）とが削除され、プロセス番号が「２」以外の場合は、７，１１，１５行目の分岐命令と、８〜１０行目のコード（条件が真の場合に実行されるコード）とが削除される。同様に、２３〜２７行目のコードは、プロセス番号が「１」以外の場合は、２３、２７行目の分岐命令が削除され、プロセス番号が「１」の場合は、２３、２７行目の分岐命令と２４〜２６行目のコードが削除される。ソースプログラムには２３行目の分岐命令の条件文が偽の場合に実行されるコードがないので、プロセス番号が「１」の場合は、２３，２７行目の分岐命令が削除されるだけである。
【００６３】
次に、プロセッサは、処理対象のプロセスに属するプロセスが１つの場合（Ｓ１５６のＹＥＳ）、最適化対象プログラム内のイメージ番号を処理対象のプロセス番号で定数化する（Ｓ１５７）。第１の実施の形態では、イメージ番号固有化処理がプロセス毎に実行されるので、工程Ｓ１５６は常にＹＥＳとなり、最適化対象プログラム内のイメージ番号は対象のプロセス番号で定数化される。第２の実施の形態でグループごとに実行される場合は、グループに属するプロセスが単数の場合にイメージ番号が定数化される。
【００６４】
そして、プロセッサは、処理対象のプロセスの最適化対象プログラムに対して、汎用の最適化処理と、ＳＩＭＤ化処理を実行する（Ｓ１５８）。工程Ｓ１５４，Ｓ１５５，Ｓ１５７を行った結果、新たに定数化できる変数が検出され、そのような変数とイメージ番号を定数にすることで定数伝搬などの最適化が促進されることが期待される。
【００６５】
また、イメージ番号を定数にすることで、イメージ番号毎にサイズが異なる変数のサイズが確定する。したがって、そのような変数の演算命令のＳＩＭＤ化する場合、繰り返し回数の判定を行うための比較命令を省略することができる。図２のソースプログラムにおいて１８行目の演算命令（co(i)%x=0）が、このＳＩＭＤ化の対象になる。すなわち、プロセス２では成分ｘのサイズが８であり、プロセス２以外では成分ｘのサイズが１０である。したがって、１８行目の演算命令は、プロセス２では８回繰り返され、プロセス２以外では１０回繰り返される。つまり、１８行目の演算命令は、４ＳＩＭＤ演算器で実行される場合、プロセス２では２つの４ＳＩＭＤ命令（例えばアセンブリコード）に変換され、プロセス２以外では２つの４ＳＩＭＤ命令と１つの２ＳＩＭＤ命令（アセンブリコード）に変換される。
【００６６】
図１５、図１６は、１８行目の演算命令をＳＩＭＤ化したコード例を示す図である。図１５が本実施の形態を適用しない場合のＳＩＭＤ化後のコード例を、図１６が本実施の形態を適用した場合のＳＩＭＤ化後のコード例である。４ＳＩＭＤ演算器で実行されることを前提にしているので、４ＳＩＭＤストア命令は例えば「co%x(1:4)に０を代入」となる。
【００６７】
図１５の本実施の形態を適用しない場合では、プロセス１では成分ｘの大きさが１０であるが、コンパイル時は、図２のソースプログラムでは配列coの成分ｘの大きさがプロセス毎に異なり、いずれのプロセス番号でも実行可能にする必要がある。したがって、プロセス１のＳＩＭＤ化後のコードは、
「配列の成分co%xの大きさと４とを比較する比較命令」で成分の大きさが４以上の場合に、４ＳＩＭＤストア命令の「co%x(1:4)に０を代入」を実行し、
「配列の成分co%xの大きさと８とを比較する比較命令」で成分の大きさが８以上の場合に、４ＳＩＭＤストア命令の「co%x(5:8)に０を代入」を実行し、
「配列の成分co%xの大きさと１２とを比較する比較命令」で成分の大きさが１２以上でない場合に、非ＳＩＭＤストア命令「co%x(9)に０を代入」を実行し、
「配列の成分co%xの大きさと９とを比較する比較命令」で成分の大きさが９を超える場合に、非ＳＩＭＤストア命令の「co%x(10)に０を代入」を実行し、
「配列の成分co%xの大きさと１０とを比較する比較命令」で成分の大きさが１０を超える場合に該当せず、命令コードが終了する。
【００６８】
プロセス２の場合は、成分ｘの大きさが８であるので、図１５に記載されるとおりである。つまり、プロセス１のＳＩＭＤ化後のコード内の「配列の成分co%xの大きさと８とを比較する比較命令」でＹＥＳとなり、その後の処理は行われない。
【００６９】
一方、図１６の本実施の形態を適用した場合、プロセス毎に最適化対象の中間表現プログラムが最適化され、プロセス１のプログラムでは成分ｘの大きさが１０と確定しているので、プロセス１のＳＩＭＤ化後のコードは、比較命令がなく、２つの４ＳＩＭＤストア命令と１つの２ＳＩＭＤストア命令を有するだけである。
【００７０】
同様に、プロセス２のプログラムでは成分ｘの大きさが８と確定しているので、プロセス２のＳＩＭＤ化後のコードは、比較命令がなく、２つの４ＳＩＭＤストア命令を有するだけである。
【００７１】
このように、図１６の場合、ＳＩＭＤ化後のコードに比較命令がないので、実行時間の短縮化に寄与する。
【００７２】
図１４は、イメージ１，２，３〜ｎに対して生成され、図１１の最適化処理がされた最適化対象プログラムを示す図である。図１４に示す３つのプログラムは、後述する包括的最適化処理が行われた結果でも同様になるが、図１４を参照して、図１１の最適化処理を具体的に説明する。
【００７３】
イメージ１（プロセス１）に生成されたプログラムは、図２のプログラムから７−１１行目と２３−２７行目のコードが削除され、１８行目の演算命令がＳＩＭＤ化される。
【００７４】
一方、イメージ２（プロセス２）に生成されたプログラムは、図２のプログラムから７，１１−１５行目と２３、２７行目のコードが削除され、１８行目の演算命令がＳＩＭＤ化される。
【００７５】
そして、イメージ３−ｎ（プロセス３−ｎ）に生成されるプログラムは、図２のプログラムから７−１１行目と２３、２７行目のコードが削除され、１８行目の演算命令がＳＩＭＤ化される。
【００７６】
［包括的最適化処理］
図８に示されるとおり、図１１のイメージ番号の固有化処理（第１の最適化処理）が終了すると、プロセッサは、全プロセスそれぞれについて包括的最適化処理Ｓ１８（第２の最適化処理）を実行する。
【００７７】
図１２は、包括的最適化処理のフローチャートを示す図である。図１２には、図８の全プロセスＰ（または全プロセスグループＧ）について繰り返し実行する処理Ｓ１７，Ｓ１９も示されている。包括的最適化処理は、各プロセスの最適化対象プログラムにイメージ番号の固有化処理（第１の最適化処理）により確定した情報、例えばイメージ毎に異なる動的領域の大きさや各イメージの共配列の値などを、プロセス間で参照しあう命令コードに、定数として設定する。この定数に設定される処理は、他のプロセスの動的領域の大きさについての工程Ｓ１８１−Ｓ１８３、他のプロセスの共配列の値についての工程Ｓ１８４−Ｓ１８６である。さらに、包括的最適化処理は、再度、汎用の最適化及びＳＩＭＤ化処理Ｓ１８７を有する。
【００７８】
コンパイラを実行するプロセッサは、処理対象のプロセスの最適化対象プログラム内で他のプロセスの動的領域への参照を抽出し、その全ての参照について（Ｓ１８１）、参照先の他のプロセスでの動的領域の大きさが定数の場合（Ｓ１８２のＹＥＳ）、その定数を動的領域の大きさに設定する（Ｓ１８２）ことを、他のプロセスの動的領域を参照する命令文それぞれについて、繰り返し実行する。
【００７９】
図２のソースプログラムは、２５行目に、プロセス１の共配列の成分co(i)[1]％xをローカルプロセスの共配列の成分co(i)%xに代入する演算命令を有する。なお、ローカルプロセスの場合共配列coにはプロセス番号を指定するコード[*]を省略できる。成分ｘはALLOCATABE属性を有し動的領域を割り当てられるので、この演算命令は、次の処理に分解される。
【００８０】
すなわち、
（１）プロセス１の共配列の成分co(i)[1]％xの大きさを参照する通信をプロセス１に行い、
（２）ローカルプロセスの共配列の成分co(i)%xの大きさを取得し、
（３）両大きさを比較し、
（４）異なる場合にローカルプロセスの共配列の成分に割り当てられたメモリ領域を解放し、
（５）ローカルプロセスの共配列の成分にプロセス１の共配列の成分の大きさのメモリ領域を割り当て、
（６）プロセス１の共配列の成分の値を参照する通信をプロセス１に行い、ローカルプロセスの共配列の成分に代入する処理に分解される。したがって、２５行目の演算命令が、他のプロセスの動的領域への参照を含む。
【００８１】
そこで、プロセッサは、イメージ番号固有化処理を行ったイメージ１の最適化対象プログラムを調べて、プロセス１の共配列の成分co(i)[1]％xの大きさが定数か否かを調べる。図１４に示したイメージ１の最適化対象プログラムでは、１３行目の共配列の成分co(i)[1]％xの大きさが１０に設定されている。そこで、プロセッサは、イメージ２、イメージ３−ｎの最適化対象プログラムにおいて、２５行目の演算命令の分解処理（１）のプロセス１への通信処理などを削除し、共配列の成分の大きさ「１０」を設定する。
【００８２】
図１７、図１８は、２５行目の演算命令のアセンブリコード例を示す図である。図１７が本実施の形態を適用しない場合のアセンブリコード例を、図１８が本実施の形態を適用した場合のアセンブリコード例である。図１７の場合、コンパイラは、２５行目の演算命令を上記した６つの処理のアセンブリコードに変換する。一方、図１８の場合、コンパイラを実行するプロセッサは、プロセス１の共配列の成分の大きさが１０であり、プロセス２以外の共配列の成分の大きさが１０であり、プロセス２の共配列の成分の大きさが８であることを検出している。そこで、図１７の分解処理（１）〜（３）を削除し、分解処理（４）〜（６）のアセンブリコードだけにする。
【００８３】
図１２に戻り、さらに、プロセッサは、処理対象のプロセスの最適化対象プログラム内で他のプロセスの共配列への参照を抽出し、その全ての参照について（Ｓ１８４）、参照先の他のプロセスでの共配列の値が定数の場合（Ｓ１８５のＹＥＳ）、その定数を共配列に設定する（Ｓ１８６）ことを繰り返し実行する。この他のプロセスの共配列の値への参照は、図１４のプログラムには含まれていない。そこで、図１９に別途プログラムを示して具体的に説明する。
【００８４】
図１９は、他のプロセスの共配列への参照を有するプログラム例と包括的最適化処理を示す図である。プログラムＳ＿ＰＲＧ＿２は、１行目の共配列を定義するコード、３行目のイメージ番号（this_image()）が１に等しいという条件文付き分岐命令（if文）と、４行目のイメージ番号が１に等しい場合にローカルの配列coに「１」を代入する演算命令と、６行目のイメージ番号が１に等しくない場合にローカルの配列coに「１」を代入する演算命令と、そして、９行目の変数ｘにプロセス１の共配列coの値を代入する演算命令とを有する。
【００８５】
このプログラムＳ＿ＰＲＧ＿２の９行目の演算命令が、他のプロセスの共配列の値への参照を有する。この場合、４行目にプロセス１の配列co（co[1]）が「１」であることを示しているので、co[1]=1であることが判明する。または、プロセス１のプログラムＳ＿ＰＲＧ＿２１を参照すると、co[1]=1であることが判明する。そこで、プロセッサは、プロセス１の配列co[1]の値「１」をプロセス１の中間表現プログラムから取得し、各プロセスに生成したプログラムＳ＿ＰＲＧ＿２１，２２，２３の９行目の演算命令、x=co[1]、を、ｘ＝１に変換する（Ｓ１８６）。これにより、４行目の演算命令のアセンブリコードから、プロセス１の共配列の値を参照する通信処理を削除することができる。
【００８６】
図１２に戻り、プロセッサは、処理対象のプロセスの最適化対象プログラムについて、汎用最適化処理とＳＩＭＤ化処理を実行する（Ｓ１８７）。汎用最適化は前述と同様である。またＳＩＭＤ化処理では、２５行目の演算式をＳＩＭＤ化する。そのＳＩＭＤ化では、プロセス１の共配列の成分ｘのサイズが１０であることが図１４に示したプロセス１の最適化対象プログラムから検出できるので、プロセッサは、１８行目の演算命令をＳＩＭＤ化したのと同様に２５行目の演算式をＳＩＭＤ化したアセンブリコードに変換する。つまり、２５行目の演算命令について、プロセッサは、図１８で説明したとおり、工程Ｓ１８１−Ｓ１８３で他のプロセスへの動的領域の大きさの参照とローカルプロセスの大きさとの比較を削除する。さらに、プロセッサは、図１８に示した（６）プロセス１から共配列の成分をコピーする処理を、図１６に示したのと同様に、大きさと繰り返し回数との比較を有しないＳＩＭＤ化アセンブリコードに変換する。
【００８７】
図１３は、図８に基づいて図９、図１１、図１２を結合したコンパイラの最適化処理の全体のフローチャートを示す図である。図１３には、既に説明した最適化処理の対象となるプログラムの行番号などを示している。
【００８８】
すなわち、コンパイラの最適化処理は、削除可能な分岐命令を特定する処理Ｓ１３（図９）と、イメージ番号固有化処理Ｓ１５(第１の最適化処理、図１１)と、包括的最適化処理Ｓ１８（第２の最適化処理、図１２）とを有する。削除可能な分岐命令を特定する処理は、全プロセスに共通の中間表現プログラムについて実行し、イメージ番号固有化処理と包括的最適化処理とは全プロセスそれぞれの最適化対象プログラムについて実行する。
【００８９】
イメージ番号固有化処理Ｓ１５では、各プロセスの最適化対象プログラムではローカルのイメージ番号がそのプロセス番号であるので、プロセッサは、イメージ番号を表す関数にそのプロセス番号を代入し、条件文が定数になる分岐命令を削除し、実行されないコードを削除する。この処理でソースプログラムの７，２３行目の分岐命令が削除され実行されないコードが削除される（図１４参照）。実行されないコードは、プロセス（つまりイメージ番号）に依存して異なる。また、イメージ番号固有化処理内で実行される汎用最適化とＳＩＭＤ化により、１８行目の演算命令がＳＩＭＤ化される（図１６参照）。ALLOCATABLE属性の成分ｘのサイズがプロセス（つまりイメージ番号）に依存して異なるため、ＳＩＭＤ化される演算回数も異なる。しかし、イメージ番号はそのプロセス番号にできるので、演算回数が確定し、ＳＩＭＤ化後のプログラムには成分ｘのサイズと繰り返し回数を比較する比較命令が不要になる。
【００９０】
上記のイメージ番号固有化処理で、各プロセスの最適化対象プログラム内のイメージ番号が対応するプロセス番号で固有化された結果、他のプロセスの動的領域のサイズや、他のプロセスの共配列の値などが確定済みである。そこで、次の包括的最適化処理Ｓ１８では、プロセッサは、最適化対象プログラム内の他のプロセスの動的領域サイズの参照や、他のプロセスの共配列の値の参照などをそれぞれの値に変換する。
【００９１】
前者の処理対象は、プロセス２，３−ｎのプログラム内の２５行目の演算命令である。なお、図１４に示されるように、プロセス１のプログラムでは、２５行目の演算命令は実行されないコードであったため削除されている。一方、後者の処理対象例は、図１９に示したとおりである。
【００９２】
さらに、包括的最適化処理内で実行される汎用最適化とＳＩＭＤ化により、２５行目の演算命令がＳＩＭＤ化されたアセンブリコードに変換される。
【００９３】
次に、削除可能な分岐命令を特定する処理Ｓ１３を各プロセスのイメージ番号固有化処理Ｓ１５内で実行することができることについて説明する。削除可能な分岐命令を特定する処理Ｓ１３では、前述のとおり、プロセッサは、プロセスに共通の中間表現プログラムについて、イメージ番号を表す関数及び変数を任意の定数で置換し、定数伝搬し、条件文が定数になる分岐命令を抽出する。但し、イメージ番号固有化処理Ｓ１５でも、プロセッサは、各プロセスの最適化対象プログラムについて、イメージ番号を表す関数及び変数を対応するイメージ番号（プロセス番号）で置換し、定数伝搬し、条件文が真か偽かをチェックする（Ｓ１５３）。したがって、削除可能な分岐命令を特定する処理Ｓ１３を、各プロセスのイメージ番号固有化処理Ｓ１５それぞれで実行するようにしてもよい。但し、全プロセスで全ての分岐命令をチェックする必要があるので、全プロセスに共通の中間表現プログラムについて削除可能な分岐命令を特定する処理を行うのが望ましい。
【００９４】
図２０は、図８の実行プログラム生成処理のフローチャートを示す図である。図８の目的言語のコードを生成する工程Ｓ２０は、本実施の形態では、各プロセスの最適化された最適化対象の中間表現プログラムを実行プログラムに変換（翻訳）する処理である。実行プログラムとは、例えば機械語に翻訳されたオブジェクトコードである。
【００９５】
実行プログラム生成処理では、プロセッサは、全プロセスについて（Ｓ２０１）、各プロセスの最適化後の最適化対象の中間表現プログラム（一部アセンブリ化済み）から実行プログラムを生成（に翻訳）することを繰り返す（Ｓ２０２）。後述する複数のプロセスがグループ化される場合は、プロセッサは、全プロセスグループについて（Ｓ２０１）、実行プログラムを生成する（Ｓ２０２）。さらに、プロセッサは、プロセスグループとそれに属するプロセス番号の対応表であるプロセスグループ表を出力する。このプロセスグループ表は、プロセスをグループ化した場合に生成され、後述する実行プログラムを各プロセスにロードする時に参照される。
【００９６】
図２１は、プロセス並列プログラムを実行するときに行われる実行プログラムのロード処理のフローチャートを示す図である。ロード処理では、プロセッサは、並列動作する複数のプロセスすべてについて（Ｓ３１）、それぞれのプロセスの実行プログラムを当該プロセスのメモリ空間にロードする（Ｓ３２）。実行時は、実行コンピュータのアーキテクチャに基づいて、プロセス数が設定される。したがって、図７に示したとおり、プロセッサは、設定されたプロセス数ｎ個それぞれに、各プロセスの実行プログラムをロードする。そして、実行コンピュータの複数のプロセスがそれぞれの実行プログラムを実行する。
【００９７】
実行プログラムのロード処理は、コンパイラにその機能として含めたロード処理プログラムにより実現されても良い。この場合、コンパイラを実行するプロセッサが、実行コンピュータの各プロセスのメモリ空間にそれぞれの実行プログラムをロードし、実行コンピュータが並列に実行する。または、実行プログラムのロード処理プログラムを、全プロセスの実行プログラムに添付しても良い。この場合、実行コンピュータが、添付されたロード処理プログラムを各プロセスのメモリ空間にロードし実行する。
【００９８】
図２２は、ロード処理プログラムが添付された実行プログラム群を示す図である。実行プログラムのロード処理を行うロード処理プログラムＬ＿ＰＲＧが、複数のプロセス１〜ｎそれぞれの実行プログラムＥＸ＿ＰＲＧ＿１〜ｎに添付される。そして、実行コンピュータが、ロード処理プログラムを実行して、各プロセスに実行プログラムをロードし、実行コンピュータの各プロセスがそれぞれの実行プログラムを実行する。
【００９９】
以上、第１の実施の形態では、コンパイラを実行するプロセッサが、ソースプログラムから変換された中間表現プログラムを複写して、全プロセスそれぞれの最適化対象の中間表現プログラムを生成し、各最適化対象の中間表現プログラムについて、第１の最適化処理（ローカルのイメージ番号を固有化して最適化するイメージ番号固有化処理）と第２の最適化処理（他のプロセスの情報を定数化して最適化する包括的最適化処理）とを実行する。これにより、並列プログラミング言語で記述されたソースプログラムを最適化するよりも、最適化による効率向上をより高めることができる。
【０１００】
［第２の実施の形態］
第１の実施の形態では、コンパイラを実行するプロセッサが、全プロセスそれぞれの最適化対象プログラムを生成し、イメージ番号を固有化するなどの最適化処理を行い、それぞれの実行プログラムに翻訳する。しかし、プロセス数が多い場合、全プロセスの最適化対象プログラムや実行プログラムを記憶するために大容量のメモリ資源が必要になり、最適化処理の時間工数も増大する。
【０１０１】
そこで、第２の実施の形態では、コンパイラを実行するプロセッサが、削除可能な分岐命令の条件文が同じ値になる複数のプロセスをグループ化し、各プロセスグループにそれぞれの最適化対象プログラムを生成し、プロセスグループの最適化対象プログラムに第１、第２の最適化処理を行う。
【０１０２】
図２３は、第２の実施の形態におけるコンパイラの処理のフローチャートを示す図である。図８に示した第１の実施の形態のフローチャートと異なる処理は、プロセスグループ決定処理Ｓ２１と、イメージ番号の固有化処理Ｓ１５と包括的最適化処理Ｓ１８を、それぞれ、全プロセスグループについて繰り返し実行すること（Ｓ１４＿１，Ｓ１６＿１，Ｓ１７＿１，Ｓ１９＿１）である。それ以外は第１の実施の形態と同様である。
【０１０３】
図２４は、プロセスグループ決定処理のフローチャートを示す図である。コンパイラを実行するプロセッサは、まずプロセスグループ表を作成する（Ｓ２１２）。
【０１０４】
図２５は、プロセスグループ表の一例を示す図である。初期状態のプロセスグループ表ＰＧ＿Ｔ＿０は、プロセス番号１〜ｎそれぞれの要素に、削除可能な分岐命令数に対応するビット数ｍのビット列が割り当てられる。通常、プロセス数はプログラム実行時に設定されるので、プロセスグループ表のプロセス数ｎは、実行時に設定しうる最大プロセス数にする。仮に、設定しうる最大プロセス数をｎ＝８とする。そして、図２のソースプログラムから抽出された削除可能な分岐命令数ｍは２（ｍ＝２）である。したがって、以下の例では、プロセスグループ表ＰＧ＿Ｔは、プロセス番号１〜８それぞれの要素に、２ビットのビット列が割り当てられる。このビット列の初期値は例えば全て０にする（全て１でも良い）。
【０１０５】
図２４に戻り、プロセッサは、ビット列の位置を示すビット位置ｉをｉ＝１に初期化し（Ｓ２１３）、削除可能な分岐リスト内の全分岐命令それぞれについて（Ｓ２１４）、以下の処理を繰り返す。以下の処理では、実行時に並列動作するプロセス群の全プロセスそれぞれについて（Ｓ２１５）、イメージ番号を表す関数及び変数に処理対象のプロセス番号を代入し、定数伝搬し、各プロセスにおいて分岐命令が真に分岐するか、偽に分岐するかをチェックし（Ｓ２１６）、真の場合にビット列のｉビット目を「１」に変更する処理（Ｓ２１７）を繰り返す。これにより、プロセス１〜８の要素のビット列のビット位置ｉ＝１の値が確定する。
【０１０６】
プロセッサは、全プロセスについて処理Ｓ２１５〜Ｓ２１７の繰り返しが完了すると、ビット位置ｉを１インクリメントし（i=i+1）（Ｓ２１８）、次の削除可能な分岐命令について、前述の処理Ｓ２１５〜Ｓ２１７を全プロセスについて繰り返す。削除可能な分岐命令の数だけこの処理を繰り返すると、図２５のプロセスグループ表ＰＧ＿Ｔが生成される。この表では、プロセス１〜８の要素の２ビットのビット列の値が、工程Ｓ２１６，Ｓ２１７により、分岐命令が真の場合に「１」に変更される。
【０１０７】
たとえば、７行目の分岐命令では、プロセス２で真、それ以外のプロセス１，３〜ｎで偽であり、２３行目の分岐命令では、プロセス１で偽、それ以外のプロセス２〜ｎで真である。したがって、プロセス１のビット列は００、プロセス２のビット列は１１、プロセス３〜ｎのビット列は０１になる。
【０１０８】
さらに、プロセッサは、ビット列が同じプロセスでプロセスグループを形成し、各プロセスグループに属するプロセス番号と各プロセスグループ番号とを関連付けたプロセスグループ表を生成する（Ｓ２１９）。ビット列が各プロセスグループの識別番号になる。上記の例によれば、プロセスグループ００（ＰＧ＿００）にはプロセス１のみが属し、プロセスグループ１１（ＰＧ＿１１）にはプロセス２のみが属し、プロセスグループ０１（ＰＧ＿０１）にはプロセス３〜８が属する。これがプロセスグループ表である。
【０１０９】
図２３に示したとおり、プロセッサは、イメージ番号の固有化処理Ｓ１５を全プロセスグループそれぞれについて繰り返し、各プロセスグループの最適化対象プログラムを生成し（Ｓ１５１）、削除可能な分岐命令を削除し分岐で実行されないコードを削除する（Ｓ１５３〜Ｓ１５５）。分岐命令の分岐方向は、プロセスグループ表のビット列を参照して判定する。もしくは、プロセスグループ内の任意のプロセス番号をプロセスを表す関数に設定し、定数伝搬して分岐方向を判定しても良い。そして、プロセッサは、イメージ番号を定数化する処理Ｓ１５７を、プロセスグループに属するプロセスが１つの場合に行う。プロセスグループに複数のプロセスが属する場合、各プロセスによる実行プログラム実行時に各プロセス番号が確定する。
【０１１０】
さらに、プロセッサは、包括的最適化処理Ｓ１８を全プロセスグループそれぞれについて繰り返す。各プロセスグループの最適化対象プログラムは、イメージ番号の固有化処理により、イメージ番号に依存して分岐方向が異なる分岐命令が削除されている。したがって、参照先のプロセスが属するプロセスグループの最適化対象プログラムを参照すれば、その参照先のプロセスでの動的領域のサイズを知ることができる。同様に、参照先のプロセスの共配列の値も知ることができる。そのため、プロセスグループそれぞれについて包括的最適化処理を実行できる。
【０１１１】
以上の通り、第２の実施の形態では、コンパイラを実行するプロセッサは、各プロセスグループにそれぞれ生成した最適化対象プログラムを最適化する。図１４の例で説明すると、イメージ３−ｎの最適化対象プログラムは共通に一つだけ生成される。
【０１１２】
第２の実施の形態における実行プログラム生成処理は、図２０のフローチャートと同じである。図２０に示す通り、プロセッサは、全プロセスグループそれぞれについて、プロセスグループの最適化済みの最適化対象プログラムを実行プログラムに翻訳する。これにより、プロセスグループ毎に実行プログラムが生成される。そして、プロセッサは、プロセスグループ表を出力する（Ｓ２０３）。
【０１１３】
図２６は、第２の実施の形態における実行時のロード処理のフローチャートを示す図である。プロセッサは、まずプロセスグループ表を読み込む（Ｓ３０１）。そして、並列動作するプロセス群の各プロセスそれぞれについて（Ｓ３０２）、プロセスグループ表を参照し対象のプロセスＰのプロセスグループ名ＰＧを読み込み（Ｓ３０３）、読み込んだプロセスグループＰＧの実行プログラムをプロセスＰのメモリ空間にロードする（Ｓ３０４）処理を繰り返す。この結果、全プロセスＰのメモリ空間に実行プログラムがロードされる。
【０１１４】
図２７は、第２の実施の形態における実行プログラムのロードと実行を示す図である。プロセッサは、プロセス１のメモリ空間には実行プログラムＥＸ＿ＰＲＧ＿００をロードし、プロセス２のメモリ空間には実行プログラムＥＸ＿ＰＲＧ＿１１をロードし、そして、プロセス３〜８それぞれのメモリ空間には、それらのプロセスグループ０１の実行プログラムＥＸ＿ＰＲＧ＿０１をロードする。各プロセスでは、それぞれロードされた実行プログラムを実行する。
【０１１５】
以上の通り、第２の実施の形態によれば、削除可能な分岐命令の分岐方向が一致するプロセスを同じプロセスグループに属させ、プロセッサがコンパイラを実行して最適化と実行プログラムへの翻訳を各プロセスグループの最適化対象プログラムについて実行する。したがて、コンパイル時における最適化対象プログラムの数を削減することができ、それに伴いメモリ空間を削減できる。また、コンパイル時間も短縮できる。
【０１１６】
以上の実施の形態をまとめると，次の付記のとおりである。
【０１１７】
（付記１）
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有する処理をコンピュータに実行可能なコンパイルプログラム。
【０１１８】
（付記２）
前記処理は、更に、
他のプロセスの前記イメージ番号に依存する所定情報への参照を含む命令に前記所定情報の定数を設定する第２の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程を有する、付記１に記載のコンパイルプログラム。
【０１１９】
（付記３）
前記処理は、更に、
前記第１の最適化処理を繰り返し行う工程の前に、前記ソースプログラム内の前記イメージ番号を表す関数及び変数を任意の固定値に置換し、定数伝搬し、前記条件文が定数になる条件付き分岐命令を削除可能分岐命令として抽出する工程を有し、
前記削除可能分岐命令それぞれについて、前記第１の最適化処理を実行する、付記１に記載のコンパイルプログラム。
【０１２０】
（付記４）
前記処理は、更に、
前記削除可能分岐命令抽出工程後且つ前記最適化対象プログラム生成工程前に、前記ソースプログラム内の前記削除可能分岐命令の前記条件文の判定結果が一致する複数のイメージ番号を同じプロセスグループにグループ化するプロセスグループ化工程を有し、
前記最適化対象プログラムの生成工程では、前記グループ化された複数のイメージ番号に対して共通の最適化対象プログラムを生成する、付記３に記載のコンパイルプログラム。
【０１２１】
（付記５）
前記最適化対象プログラム生成工程と前記第１の最適化処理工程を、前記プロセスグループ毎に実行し、
前記第１の最適化処理は、単一のイメージ番号に対応する最適化対象プログラムにおいて、前記イメージ番号を表す関数及び変数を前記単一のイメージ番号で定数化することを含む、付記４に記載のコンパイルプログラム。
【０１２２】
（付記６）
前記第１の最適化処理は、前記条件付き分岐命令の削除後、定数伝搬を含む汎用最適化処理と、繰り返し処理をSIMD化する処理とを行う、付記１に記載のコンパイルプログラム。
【０１２３】
（付記７）
前記所定情報が参照する他のプロセスの動的領域の大きさであり、
前記第２の最適化処理工程は、前記動的領域の大きさが定数の場合、前記大きさに定数を設定することを含む、付記２に記載のコンパイルプログラム。
【０１２４】
（付記８）
前記所定情報が参照する他のプロセスの共配列の値であり、
前記第２の最適化処理工程は、前記共配列の値が定数の場合、前記共配列の値に定数を設定することを含む、付記２に記載のコンパイルプログラム。
【０１２５】
（付記９）
前記第２の最適化処理工程は、前記定数を設定した後、定数伝搬を含む汎用最適化処理と、SIMD化が可能な場合繰り返し処理をSIMD化する処理とを行う、付記２に記載のコンパイルプログラム。
【０１２６】
（付記１０）
前記処理は、更に、
前記イメージ番号それぞれに生成した複数の最適化対象プログラムそれぞれを変換し、複数の実行プログラムを生成する工程を有する付記１に記載のコンパイルプログラム。
【０１２７】
（付記１１）
前記複数の実行プログラムそれぞれを、前記イメージ番号に対応するプロセスのメモリ空間それぞれにロードする工程を有する、付記１０に記載のコンパイルプログラム。
【０１２８】
（付記１２）
前記処理は、更に、
前記イメージ番号それぞれに生成した複数の実行プログラムを、前記イメージ番号に対応するプロセスそれぞれにロードするロードプログラムを生成する工程を有する、付記１０に記載のコンパイルプログラム。
【０１２９】
(付記１３)
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有するコンパイル方法。
【０１３０】
(付記１４)
メモリと、
前記メモリに接続されたプロセッサを有し、
前記プロセッサは、
並列プログラミング言語で記述されたソースプログラムを複製して複数のイメージ番号それぞれに対応する複数の最適化対象プログラムを生成する工程と、
前記最適化対象プログラム内のイメージ番号を表す関数及び変数をイメージ番号で置換し、定数伝搬し、条件文が定数になる条件付き分岐命令を削除し、前記削除された分岐命令の前記分岐命令に基づいて実行されないコードを削除する第１の最適化処理を、前記複数の最適化対象プログラムそれぞれについて繰り返し行う工程と、
を有する処理を実行するコンパイル装置。
【符号の説明】
【０１３１】
ＣＰＵ：プロセッサ
Ｓ＿ＰＲＧ：ソースプログラム、中間表現プログラム、最適化対象プログラム
Ｓ１５：イメージ番号固有化処理、第1の最適化処理
Ｓ１８：包括的最適化処理、第２の最適化処理
【図１】
2018081592.tif 000003
【図２】
2018081592.tif 000004
【図３】
2018081592.tif 000005
【図４】
2018081592.tif 000006
【図５】
2018081592.tif 000007
【図６】
2018081592.tif 000008
【図７】
2018081592.tif 000009
【図８】
2018081592.tif 000010
【図９】
2018081592.tif 000011
【図１０】
2018081592.tif 000012
【図１１】
2018081592.tif 000013
【図１２】
2018081592.tif 000014
【図１３】
2018081592.tif 000015
【図１４】
2018081592.tif 000016
【図１５】
2018081592.tif 000017
【図１６】
2018081592.tif 000018
【図１７】
2018081592.tif 000019
【図１８】
2018081592.tif 000020
【図１９】
2018081592.tif 000021
【図２０】
2018081592.tif 000022
【図２１】
2018081592.tif 000023
【図２２】
2018081592.tif 000024
【図２３】
2018081592.tif 000025
【図２４】
2018081592.tif 000026
【図２５】
2018081592.tif 000027
【図２６】
2018081592.tif 000028
【図２７】
2018081592.tif 000029
【図２８】
2018081592.tif 000030