JP6810380B2 - ソースプログラム変換システム、ソースプログラム変換方法、及びソースプログラム変換プログラム - Google Patents

Description

本発明は、ソースプログラムを入力として、計算機向けに最適化された、別のソースプログラムを作成する装置、方法およびプログラムに関する。

高級言語により作成されたプログラムに含まれるループを、ループアンローリングすることによって、計算機上での実行性能の向上を目的とした プログラムの最適化技術が知られている。高級言語プログラムに含まれるループは、言語毎に定まっており、例えばＣ言語やＣ＋＋言語ではｆｏｒループ、ＦＯＲＴＲＡＮ言語ではＤＯループである。

ループアンローリングは、同じ計算処理を何回も繰り返し実行する場合に、もともと ループ１回で処理していた計算のＮ倍の演算処理を、ループ１回で処理するようにループを展開する技術である。ループアンローリングには、ループ１回での処理量を増やすことにより、ループ内の命令のスケジューリングの幅が広がる効果があったり、また、ループの回数が減るため、ループを制御するオーバーヘッドが減る効果があったりする。

例えば、元のソースプログラムが以下のようであったとする。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
for ( i = 0 ; i < n ; i++ ) {
a[i] = b[i] * c[i] ;
}
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ここで、アスタリスク記号“ * ”は乗算を表わす。
このプログラムについて、ループアンローリングをした結果は、次のようになる。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
for ( i = 0 ; i < n ; i+=2 ) {
a[i] = b[i] * c[i] ;
a[i+1] = b[i+1] * c[i+1] ;
}
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
このループアンローリングでは、配列bと配列c の乗算結果を配列aに代入する処理を、ループ内で２要素分処理することによって、ループ回数を半減させている。

ある種のプログラムをループアンローリングした場合、却って実行速度が低下することがある。例えば、ベクトルプロセッサで実行させるソースプログラムをループアンローリングしたプログラムを ベクトルプロセッサ用のコンパイラでコンパイルした場合、メモリアクセスが１要素とびのメモリアクセス、いわゆるストライドアクセスになる可能性がある。

このベクトル計算機に対する一つの対策が特許文献１に記載されている。特許文献１には、高級言語で書かれたソースプログラムについてベクトル化を行い、条件が満たされた場合に、ベクトル演算命令を含む命令列について多重に展開するような、データ処理装置が記載されている。このデータ処理装置は、所定の条件により、ベクトル化されたベクトル演算命令を含む命令列に関する分割処理を行うか否かを判定し、条件が満たされた場合に、ベクトル演算命令を含む命令列について多重に展開する。

また、特許文献２から４にも関連する技術が開示されている。特許文献２から４には、ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係などを解析して、各ループを展開するか判定する手法が開示されている。

特開平２−４１５６２号公報 特開昭６３−３１４６７５号公報 特開平４−３０７６２４号公報 特開平４−３４４５３５号公報

特許文献１のデータ処理装置では、ベクトル化により命令列を作成した後に、展開処理を行うため、メモリアクセスがストライドアクセスになるということがなくなる。このため、特許文献１のデータ処理装置は、ベクトル計算機において効率的なメモリアクセスをするベクトル命令列を作成できる。

しかしながら、特許文献１のデータ処理装置では、ベクトル化により命令列を作成した後に展開処理を行う。このため、高級言語で記述されたソースコードレベルのループアンロールを実現できない問題が残る。特許文献２にも同様の問題がある。したがって、ソースコードレベルにてアンロールできないため、アンロールに伴って出現する重複計算除去や、ソースコードコンパイル時の命令スケジューリングの効果を得難いという欠点を指摘できる。

特許文献３及び特許文献４に関しては、制約や目的、展開手法の違いから下で説明する発明ほどのベクトル計算機に適したループアンロール効果を得られない。

本発明は、上記課題に鑑みて成されたものであり、ベクトル計算機に最適なループ展開を施したプログラムを作成できるソースプログラム変換システムの提供を目的とする。

本発明の一実施形態に係るソースプログラム変換システムは、変換対象とするソースプログラムを受け付けるプログラム入力部と、前記プログラム入力部に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定部と、前記展開可否判定部が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定部と、前記展開パラメタ決定部が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成部と、を含み成る。

本発明の一実施形態に係る情報処理システムによるソースプログラム変換方法は、変換対象とするソースプログラムを受け付け、前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定し、展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数を導出処理すると共に、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理し、導出したループ展開段数とループ展開幅に基づいて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する。

本発明の一実施形態に係るソースプログラム変換プログラムは、情報処理リソースを、変換対象とするソースプログラムを受け付けるプログラム入力手段と、前記プログラム入力手段に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定手段と、前記展開可否判定手段が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定手段と、前記展開パラメタ決定手段が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成手段、として動作させる。

本発明の一実施形態に係る記録媒体は、上記ソースプログラム変換プログラムをコンピュータ読取可能に非一時的に保持する。

本発明によれば、ベクトル計算機に最適なループ展開を施したプログラムを作成できるソースプログラム変換システムを提供できる。

本発明の一実施形態のソースプログラム変換システムの構成を示すブロック図である。 動作説明に用いるソースプログラムのプログラムリスト例を示した説明図である。 展開パラメタ決定部の動作を示すフローチャートである。 展開プログラム作成部の動作を示すフローチャートである。 一実施形態のソースプログラム変換システムにおいて作成された展開済みプログラムを示した図である。 一実施形態のソースプログラム変換システムにおいて作成された別の展開済みプログラムを示した図である。 展開パラメタ決定部の別の動作を示すフローチャートである。 図７に示したフローチャートを用いて作成された展開済みプログラムを示した図である。 図７に示したフローチャートを用いて作成された別の展開済みプログラムを示した図である。 本発明の一実施形態のソースプログラム変換システムの構成例を示すブロック図である。

本発明の実施形態を図面に基づいて説明する。

［第１の実施形態］
［構成の説明］
図１は、第１の実施形態に係るソースプログラム変換システムを示すブロック図である。ループ展開装置１０は、記憶装置２０に格納されたソースプログラム２１に含まれたループ内のループアンロール可能なループに関してループアンロールを実施し、ループアンロールしたプログラムを展開済みプログラム２２として記憶装置２０に格納する装置である。記憶装置２０は、ループ展開装置１０に内蔵される場合もある。

本実施形態に係るループ展開装置１０は、以下の構成を備えている。
・プログラム入力部１１
・展開可否判定部１２
・展開パラメタ決定部１３
・展開プログラム作成部１４
プログラム入力部１１、展開可否判定部１２、展開パラメタ決定部１３、展開プログラム作成部１４は、コンピュータプログラムとそのコンピュータプログラムに従って動作するプロセッサーによって実現してもよいし、一部或いは全部の構成要素を電子回路で形成してもよい。

図２は、本実施形態においてループアンロールの対象となるソースプログラム２１の例である。

プログラム入力部１１は、記憶装置２０に格納されたソースプログラム２１の入力を受け付け、該プログラムに構文解析、字句解析、意味解析を実施して、その結果を展開可否判定部１２に受け渡す。これらの構文解析、字句解析、意味解析は、既存技術を用いて実施すればよい。

展開可否判定部１２は、渡されたソースプログラム中のループについて、展開可否かどうかの判定を行う。展開可否かどうかの判定には、ループ内のデータの依存関係の有無、および、ループのカウンタ変数が線形に変化するかどうかの判定を行えばよい。ループ内のデータの依存関係が無く 且つ ループのカウンタ変数が線形に変化する場合、展開可否判定部１２は、ループ展開可能と判定する。このループ内のデータの依存解析は、既存の技術を用いる実施すればよい。また、ループのカウンタ変数の増加値（以降、Ｌと表記）は、後述の展開パラメタ決定部１３と展開プログラム作成部１４にて利用される。

図２で示すようなソースプログラムの例の場合、配列Ａ、Ｂ、Ｃは異なる配列であるため、データの依存関係はない。また、ループのカウンタ変数ｉは、ループ１回転ごとに１ずつ増加するため、線形の増加である。したがって、図２で示すようなソースプログラムは、ループ展開可と判定される。また、ループカウンタ変数の増加値Ｌは１である。

展開パラメタ決定部１３は、ループ展開可と判定されたループに関して、ループ中の配列カウンタ変数 や ループ中の計算式の計算量 に基づく所定の条件を用いて、ループ展開のための２種類のパラメタ、すなわちループ展開幅とループ展開段数を導出する。

このループ展開幅（以降Ｍとも表記）は、展開前のループの何回転離れた計算処理を、同じループに展開するか否かを表す。また、ループ展開段数（以降、Ｎとも表記）は、展開前のループの何回転分の計算処理を、展開後のループ１回転で計算するかを表す。例えば、ループ展開前の１回転目の計算は、Ｍ＋１回転目、２Ｍ＋１回転目、・・・（Ｎ−１）×Ｍ＋１回転目の計算と、同じループで計算されるように展開される。

展開プログラム作成部１４は、展開パラメタ決定部１３が決定した ループ展開幅、ループ展開段数に従って、対象のループを展開したプログラム（展開済みプログラム２２）を生成し、生成した展開済みプログラム２２を記憶装置２０に出力する。なお、展開済みプログラム２２の出力先は、必ずしもソースプログラム２１が記憶されていた記憶装置２０に限定される必要は無く、例えばネットワークを介して接続されたストレージに記録するように構成しても良い。また、展開済みプログラム２２の出力先は、ディスプレイに一時的に表示することや、プリンタへの印字することであっても構わない。

［動作の説明］
次に、展開パラメタ決定部１３及び展開プログラム作成部１４の動作を説明する。

まず、図３を用い、展開パラメタ決定部１３の動作を説明する。図３は、展開パラメタ決定部１３の動作を表すフローチャートである。

展開パラメタ決定部１３（ループ展開装置１０）は、ソースプログラム２１のループの回転数（Ｚ）、および、カウンタ変数の初期値（Ｋ）を導出する（Ｓ３０１）。

図２で示したソースプログラム２１のループの場合、カウンタ変数 i は、１００から１００００まで１ずつ増える。したがって、展開パラメタ決定部１３は、回転数Ｚを“９９０１”、カウンタ変数の初期値Ｋを“１００”と導出する。

次に、展開パラメタ決定部１３は、ソースプログラム２１のループ１回転のコスト（Ｃ）を導出する（Ｓ３０２）。本実施形態では、ループ１回転のコストを、ループ内の演算の回数であるとする。図２で示されるソースプログラム２１のループの場合、加算が１回であるので、展開パラメタ決定部１３は、コストＣ＝１と導出する。
なお、本実施形態では、ループ１回転のコストを演算の回数としたが、ループ内の配列データへのメモリアクセス回数（ロード回数やストア回数）など、他の要因を用いてコストを決定してもよい。ループ１回転のコストの決定方法は、特に限定するものではない。例えば、ループ内の演算の回数とメモリアクセス回数を組み合わせてもよい。

次に、展開パラメタ決定部１３は、最小コスト閾値（Ｃ_min）を参照し、Ｃ_min ≦ Ｃ × Ｎ_ｃ となる最小の整数Ｎ_ｃを導出する（Ｓ３０３）。最小コスト閾値（Ｃ_min）は、ループ展開装置１０ごと もしくは ソースプログラム２１をコンパイルした命令列を実行するベクトル計算機ごと にあらかじめ定めておく定数値である。なお、設定方法に関しては特に制限するものではない。本実施形態では、Ｃ_min＝３２と定まっているものとする。Ｃ_min＝３２であり、Ｃ＝１である場合、Ｃ_min ≦ Ｃ ×Ｎ_ｃを満たす最小の整数Ｎ_ｃ＝３２となる。

次に、展開パラメタ決定部１３は、ループ展開段数の最大値（Ｎ_max）を参照し、先に計算したＮ_ｃとループ展開段数の最大値（Ｎ_max）との小さい方を、ループ展開段数Ｎと決定する（Ｓ３０４）。このループ展開段数の最大値（Ｎ_max）は、ループ展開装置１０ごと、もしくは、ソースプログラム２１をコンパイルした命令列を実行するベクトル計算機ごとにあらかじめ定めておく定数値である。なお、設定方法に関しては特に制限するものではない。本実施形態では、Ｎ_max＝４と定まっているものとする。Ｎ_ｃ＝３２とＮ_max＝４の小さい方の値である“４”がループ展開段数Ｎに決定される。

次に、展開パラメタ決定部１３は、先に計算したループの回転数Ｚとループ展開段数Ｎとを参照し、Ｍ×Ｎ＜Ｚとなる最大の整数Ｍを、ループ展開幅Ｍとして決定する（Ｓ３０５）。本例では、Ｚ＝９９０１、Ｎ＝４であるので、Ｍ＝２４７５と決定される。

次に、図４を用い、展開プログラム作成部１４の動作を説明する。図４は、展開プログラム作成部１４の動作を表すフローチャートである。

まず、展開プログラム作成部１４（ループ展開装置１０）は、二重ループ構造を作成する（Ｓ４０１）。外側ループのカウンタ変数は、入力のソースプログラム２１のループのカウンタ変数と同じ変数に設定する。図２で示されるソースプログラム２１の場合、外側ループのカウンタ変数はカウンタ変数 ｉ が展開プログラム作成部１４によって設定される。このカウンタ変数の初期値は“０”と設定する。また、ループ１回転ごとのカウンタ変数の増加値は、上記展開パラメタ決定部１３で決定したループ展開幅Ｍ、ループ展開段数Ｎを用い、Ｎ×Ｍとする。また、ループの終了条件は、ソースプログラムのループ回転数Ｚを用い、ｉ＜Ｚ−Ｍ×Ｎ＋１とする。内側ループのカウンタ変数は、ソースプログラム２１に現れない任意の変数を用いる。ここでは内側ループのカウンタ変数を ｊ と表す。この内側ループのカウンタ変数の初期値は０に設定する。また、内側ループのループ１回転ごとのカウンタ変数の増加値は、ソースプログラム２１のループのカウンタ変数の増加値Ｌに設定する。内側ループのループ終了条件は、ｊ＜Ｍ に設定する。

次に、展開プログラム作成部１４は、作成した２重ループ構造のループ内での計算式を作成する（Ｓ４０２）。まず、展開プログラム作成部１４は、ソースプログラム２１のループ内の計算式を、ループ展開段数分（すなわちＮ個分）に並べる。次に、展開プログラム作成部１４は、ループ内ループ変数ｉを、（ｉ＋Ｋ＋ｊ＋０×Ｌ×Ｍ）、（ｉ＋Ｋ＋ｊ＋１×Ｌ×Ｍ）、（ｉ＋Ｋ＋ｊ＋２×Ｌ×Ｍ）、…、（ｉ＋Ｋ＋ｊ＋（Ｎ−１）×Ｌ×Ｍ）のＮ種類の項に置換する。Ｋは、先述の通り、元のソースコード２１のループのカウンタ変数の初期値である。

次に、展開プログラム作成部１４は、余りループを作成する（Ｓ４０３）。余りループは、ループ展開した際に展開段数に満たない回転数分のループを処理するループである。余りループのカウンタ変数は、上記二重ループのカウンタ変数を引き継ぐ。展開プログラム作成部１４は、余りループのカウンタ変数の初期値を、上記二重ループのカウンタ変数のループ終了時の値ｉを用い、Ｌ×ｉ＋Ｋに設定する。また、展開プログラム作成部１４は、余りループのカウンタ変数の増加値を Ｌ 、終了条件をｉ＜Ｌ×Ｚ＋Ｋに設定する。そして、展開プログラム作成部１４は、余りループのループ内計算式に、ソースプログラムのループ内の計算式をそのまま１個分配置する。

ここで、展開プログラム作成部１４の動作を、図２のソースプログラム２１を入力とした場合を実例として説明する。図５は、展開プログラム作成部１４が図２のソースプログラム２１の入力を受けて出力するプログラム（展開済みプログラム２２）である。

まず、展開プログラム作成部１４は、二重ループ構造を作成する（二重ループ構造作成工程；Ｓ４０１）。外側ループのカウンタ変数は、ソースプログラムと同じ ｉ に設定する。また、カウンタ変数初期値は“０”、カウンタ変数の増加値は、ループ展開幅Ｍが“２７４５”、ループ展開段数が“４”であるので、“２７４５×４”に設定する。ループの終了条件は、ソースプログラムのループの回転数Ｚが“９９０１”であるので、“ｉ<９９０１−２４７５×４＋１”となる。展開プログラム作成部１４は、これらを統合して、図５の１行目の for文を作成する。次に、展開プログラム作成部１４は、内側ループについて、カウンタ変数をソースプログラム上に出現しないｊに設定する。ｊの初期値は“０”、増加値は、ソースプログラム２１のカウンタ変数の増加値Ｌである“１”を設定する。また、ループの終了条件は、ループ展開幅Ｍの“２７４５”に設定する。このように、展開プログラム作成部１４は、図５の２行目の for文 を作成する。

次に、展開プログラム作成部１４は、内側ループ計算式を作成する（内側ループ計算式作成工程；Ｓ４０２）。ソースプログラムの計算式は、図２の２行目の１式だけである。展開プログラム作成部１４は、この式を、ループ展開段数Ｎである４個分配置する。このとき、展開プログラム作成部１４は、計算式内に現れるカウンタ変数ｉを、それぞれ（ｉ＋１００＋ｊ＋０×１×２４７５），（ｉ＋１００＋ｊ＋１×１×２４７５），（ｉ＋１００＋ｊ＋２×１×２４７５），（ｉ＋１００＋ｊ＋０×１×２４７５）の４種類の項に置換する。その結果が、図５の３行目から６行目の式である。そして、内側ループの終了を示す括弧（図５、７行目）と外側ループの終了を示す括弧（図５、８行目）が続く。

次に、展開プログラム作成部１４は、余りループを作成する（余りループ作成工程；Ｓ４０３）。余りループのカウンタ変数は、先の二重ループのカウンタ変数である ｉ を用いる。そして、カウンタ変数の初期値は、ソースプログラムのカウンタ変数の増加値Ｌである“１”、ソースプログラムのカウンタ変数の初期値Ｋである“１００”を用い、“１×ｉ＋１００”となる。また、カウンタ変数の増加値はＬである“１”、ループの終了条件は、ソースプログラムのループの回転数Ｚである“９９０１”を用い、“ｉ<１×９９０１＋１００”となる。図５の９行目が、余りループのループ構造を示す for文 である。そして次に、ソースプログラム２１のループの計算式をそのまま配置し（図５、１０行目）、ループの終了を示す括弧が続く（図５、１１行目）。

このようにして、展開プログラム作成部１４は、展開ループを作成する。

また、展開ループ中の定数を用いた項は、図６のように、計算後の値としてもよい。

図５および図６を参照してわかるように、上記一連のループ展開処理によって、元のソースプログラムではループ中の計算式数が１個であったが、４個の計算式を持つループ構造のプログラム（展開済みプログラム２２）が作成されている。すなわち、展開済みプログラム２２は、ソースプログラムレベルで、ソースプログラム２１をループアンロールできていることがわかる。

また、この展開後プログラム２２をベクトル計算機で実行できるようにコンパイルして実行した場合、それぞれのベクトル演算のメモリアクセスは、連続アクセスとなり効率のよいメモリアクセスを行うベクトル演算となる。

すなわち、本発明によれば、ベクトル計算機に最適なループ展開を施したプログラムを作成できるソースプログラム変換システムを提供できる。

ここで、ループ展開装置１０（展開パラメタ決定部１３）の追加及び置換機能を説明する。上記展開パラメタ決定部１３は、ループ展開幅を、（ループ回転数÷ループ展開段数）以下となる整数としている。これに対して、本追加及び置換機能を具備する展開パラメタ決定部１３は、ループ展開幅に、展開済みプログラム２２を実行するベクトル計算機（ソースプログラム２１を実行する計算機）のベクトル長（以降ＶＬと表記）を設定する。

以下の説明では、ソースプログラムを実行するベクトル計算機が決まっており、その計算機のベクトル長がループ展開装置１０内またはソースプログラム内のどちらかで保持されているものとする。また、操作者（プログラマ）がループ転回装置１０にベクトル長を手入力するようにしてもよい。

また、ループ転回装置１０（展開パラメタ決定部１３）がソースプログラムを実行させるベクトル計算機のベクトル長 又は 機種 がソースコード中に記載されているか前処理で判別する構成としてもよい。機種を特定できた際には、あらかじめ準備されている機種−ベクトル長データベースを参照してその機種のベクトル長の値を取得すればよい。

図７は、本動作例にかかる展開パラメタ決定部１３の動作を示すフローチャートである。ループ展開段数Ｎを決定するまでの工程（Ｓ３０１からＳ３０４）は、先に説明した図３のフローチャートと同じであるため、説明を省略する。展開パラメタ決定部１３は、ループ展開段数Ｎの決定後（Ｓ３０４の実行後）、ループ展開幅Ｍを決める。このループ展開幅Ｍは、ソースプログラムを実行する計算機のベクトル長ＶＬを、ループ展開幅Ｍとして決定する（Ｓ７０５）。

本変形例にかかるソースプログラム２１の例として、先述の図２で示したループを用いて動作を説明する。また、ソースプログラムを実行する計算機のベクトル長ＶＬが“２５６”であるとする。ループ展開段数Ｎを決定するまでの工程は、先に説明した図３のフローチャートと同じであるため、展開パラメタ決定部１３によって、ソースプログラムのループの回転数Ｚは“９９０１”、カウンタ変数初期値Ｋは“１００”、ループ展開段数Ｎは“４”と決定される。最後に、ループ展開幅Ｍは、ソースプログラムを実行する計算機のベクトル長ＶＬである“２５６”と決定される。

図８は、上記展開パラメタ決定部で決定したパラメタを用い、展開プログラムで作成したプログラム（展開済みプログラム２２）を示したものである。図９は、さらに定数値が複数含まれる項を計算して、項を単純化した場合の展開済みプログラム２２である。

図８および図９を参照してわかるように、上記一連のループ展開処理によって、元のソースプログラムではループ中の計算式数が１個であったが、４個の計算式を持つループ構造のプログラム（展開済みプログラム２２）が作成されている。すなわち、展開済みプログラム２２は、ソースプログラムレベルで、ソースプログラム２１をループアンロールできていることがわかる。

また、本実施形態の第１の変形例のループ展開装置１０でループ展開した展開プログラムをベクトル化した場合、ループ内の複数のベクトル演算でアクセスするメモリー領域は連続になる。例えば、図８および図９の３行目計算式と４行目の計算式を考えた場合、３行目の計算式中の“B[i+j+100] ”という項は、ベクトル化すると、“B[i+j+100]”から“B[i+j+355]”とメモリー上に連続な２５６要素である。４行目の“B[i+j+356] ”という項は、ベクトル化すると、“B[i+j+356] ”から“B[i+j+611]”と メモリー上に連続な２５６要素である。これら５１２要素は全てメモリー上に連続である（５行目、６行目の項も同様で全てメモリー上に連続である）。

また、この展開後プログラム２２を該当ベクトル計算機で実行できるようにコンパイルして実行した場合、該当ベクトル計算機での それぞれのベクトル演算のメモリアクセスは、連続アクセスとなり より効率のよいメモリアクセスを行うベクトル演算となる。

他方、先に示した展開方法は、汎用的なベクトル計算機向けのループアンローリングを実施できる利点を有る。

以上説明したように、本発明を適用したソースプログラム変換システムは、ベクトル計算機に最適なループ展開を施したプログラムを作成できる。

尚、ソースプログラム変換システムの各部は、図１０に例示するようなコンピュータシステムのハードウェアとソフトウェアの組み合わせを用いて実現すればよい。このコンピュータシステムは、所望形態に合わせた、１ないし複数のプロセッサーとメモリーを含む。また、このコンピュータシステムの形態では、各部は、上記メモリーにソースプログラム変換プログラムが展開され、このプログラムに基づいて１ないし複数のプロセッサー等のハードウェアを実行命令群やコード群で動作させることによって、実現すればよい。この際、必要に応じて、このプログラムは、オペーレティングシステムや、マイクロプログラム、ドライバなどのソフトウェアが提供する機能と協働して、各部を実現することとしてもよい。

メモリーに展開されるプログラムデータは、プロセッサーを１ないし複数の上述した各部として動作させる実行命令群やコード群、テーブルファイル、コンテンツデータなどを適宜含む。

また、このコンピュータシステムは、必ずしも一つの装置として構築される必要はなく、複数のサーバやコンピュータ或いは仮想マシンなどが組み合わさって、所謂、シンクライアントや、分散コンピューティング、クラウドコンピューティングで構築されてもよい。また、コンピュータシステムの一部或いは全ての各部をハードウェアやファームウェア（例えば、一ないし複数のLSI：Large-Scale Integration，FPGA：Field Programmable Gate Array，電子素子の組み合わせ）で置換することとしてもよい。同様に、各部の一部のみをハードウェアやファームウェアで置換することとしてもよい。

また、このプログラムは、記録媒体に非一時的に記録されて頒布されても良い。当該記録媒体に記録されたプログラムは、有線、無線、又は記録媒体そのものを介してメモリーに読込まれ、プロセッサー等を動作させる。

尚、本明細書では、記録媒体には、類似するタームの記憶媒体やメモリー装置、ストレージ装置なども含むこととする。この記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリー装置、ハードディスク装置、テープメディアなどが挙げられる。また、記録媒体は、不揮発性であることが望ましい。また、記録媒体は、揮発性モジュール（例えばRAM：Random Access Memory）と不揮発性モジュール（例えばROM：Read Only Memory）の組み合わせを用いることとしてもよい。

上記形態を別の表現で説明すれば、プロセッサーを、ループ展開装置として動作させる情報処理リソースを、メモリーに展開されたソースプログラム変換プログラムに基づき、図１に示した、プログラム入力部、展開可否判定部、展開パラメタ決定部、展開プログラム作成部として動作させることで、その結果ソースプログラム変換システムを実現できる。各構成要素は、ソフトウェアプログラムの機能単位（ソフトウェアモジュール）と捉えることも可能である。ただし、これらの図面に示した各部の区分けは、説明の便宜上の構成であり、実装に際しては、様々な構成が想定され得る。

同様に、上記形態を更に別の表現で説明すれば、記録媒体は、メモリーに展開されて情報処理リソースで動作するソースプログラム変換プログラムを含み、情報処理リソースに、プログラム入力工程、展開可否判定工程、展開パラメタ決定工程、展開プログラム作成工程を適時実行させることで、ソースプログラム変換システム（ループ展開装置）を構築できる。

なお、実施形態を例示して本発明を説明した。しかし、本発明の具体的な構成は前述の実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の変更があってもこの発明に含まれる。例えば、上述した実施形態のブロック構成の分離併合、手順の入れ替えなどの変更は本発明の趣旨および説明される機能を満たせば自由であり、上記説明が本発明を限定するものではない。

また、上記の実施形態の一部又は全部は、以下のようにも記載されうる。尚、以下の付記は本発明をなんら限定するものではない。
［付記１］
変換対象とするソースプログラムを受け付けるプログラム入力部と、
前記プログラム入力部に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定部と、
前記展開可否判定部が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定部と、
前記展開パラメタ決定部が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成部と、
を含み成るソースプログラム変換システム。

［付記２］
上記付記１に記載のソースプログラム変換システムにおいて、
前記プログラム入力部は、ベクトル計算機で用いるソースプログラムを受け付け、
前記展開プログラム作成部は、前記展開パラメタ決定部によって決定された、ループ展開段数とループ展開幅に基づいて、前記ベクトル計算機向けに展開したループを有するプログラムを生成処理して、前記展開済みプログラムを出力する
請求項１記載のソースプログラム変換システム。

［付記３］
上記付記１又は２に記載のソースプログラム変換システムにおいて、
前記展開パラメタ決定部は、受け付けた前記ソースプログラムの中の展開するループの中の、計算回数 および メモリアクセス回数 の少なくとも一方に基づいて、ループ処理コスト（Ｃ）を算出し、所定の閾値（Ｃmin）を用いて、Ｃmin ≦ Ｃ×Ｎ を満たす最小の整数Ｎを、ループ展開段数に決定するソースプログラム変換システム。

［付記４］
上記付記１から３の何れか一項に記載のソースプログラム変換システムにおいて、
前記展開パラメタ決定部は、受け付けた前記ソースプログラムの展開するループのループ回転数を計算し、決定したループ展開段数を参照して、ループ展開幅に、（ソースプログラムのループ回転数÷ループ展開段数）以下となる正整数を設定するソースプログラム変換システム。

［付記５］
上記付記１から３の何れか一項に記載のソースプログラム変換システムにおいて、
前記展開パラメタ決定部は、ループ展開幅に、展開済みプログラムを実行するベクトル計算機のベクトル長を設定するソースプログラム変換システム。

［付記６］
上記付記１から３の何れか一項に記載のソースプログラム変換システムにおいて、
前記展開パラメタ決定部は、前記ソースプログラムを実行させるベクトル計算機のベクトル長 又は 機種 が前記ソースコード中に記載されているか判別し、ベクトル長 又は 機種 が記載されていた場合、該記載されていたベクトル長 又は 機種から定まるベクトル長 を識別して、ループ展開幅に識別したベクトル長を設定するソースプログラム変換システム。

［付記７］
上記付記１から６の何れか一項に記載のソースプログラム変換システムにおいて、
前記展開プログラム作成部は、外側ループが、カウンタ変数が、初期値０から、ループ１回転ごとに、前記ループ展開幅と前記ループ展開段数の積ずつ増加し、ソースプログラムのループの回転数と前記積の値の差以下であるまでループし、内側ループが、カウンタ変数が、初期値０から、ループ１回転ごとに、ソースプログラムのループのカウンタ変数のループ１回転ごとの増加値ずつ増加し、前記ループ展開幅より小さい間ループするような、２重ループを作成し、
当該２重ループの中に、ソースプログラムのループ中の計算式を、前記ループ展開段数分展開する
ソースプログラム変換システム。

［付記８］
変換対象とするソースプログラムを受け付け、
前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定し、
展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数を導出処理すると共に、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理し、
導出したループ展開段数とループ展開幅に基づいて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する
情報処理システムによるソースプログラム変換方法。

［付記９］
情報処理リソースを、
変換対象とするソースプログラムを受け付けるプログラム入力手段と、
前記プログラム入力手段に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定手段と、
前記展開可否判定手段が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定手段と、
前記展開パラメタ決定手段が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成手段、
として動作させるソースプログラム変換プログラム。

［付記１０］
上記付記９に記載のソースプログラム変換プログラムであって、前記情報処理リソースは、プロセッサーとメモリーとバスの組み合わせを用いるソースプログラム変換プログラム。

［付記１１］
上記付記９又は１０に記載のソースプログラム変換プログラムをコンピュータ読取可能に非一時的に保持する記録媒体。

本発明によれば、ソフトウェアプログラムを入力として、対象のベクトル計算機向けに最適化されたソフトウェアプログラムを作成するソフトウェア最適化装置といった用途に適用できる。

１０ ループ展開装置（情報処理装置、情報処理リソース）
１１ プログラム入力部
１２ 展開可否判定部
１３ 展開パラメタ決定部
１４ 展開プログラム作成部
２０ 記憶装置
２１ ソースプログラム
２２ 展開済みプログラム（最適化ソースプログラム）

Claims (9)

1. 変換対象とするソースプログラムを受け付けるプログラム入力部と、
   前記プログラム入力部に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定部と、
   前記展開可否判定部が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定部と、
   前記展開パラメタ決定部が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成部と、
   を含み成るソースプログラム変換システム。
2. 前記請求項１に記載のソースプログラム変換システムにおいて、
   前記プログラム入力部は、ベクトル計算機で用いるソースプログラムを受け付け、
   前記展開プログラム作成部は、前記展開パラメタ決定部によって決定された、ループ展開段数とループ展開幅に基づいて、前記ベクトル計算機向けに展開したループを有するプログラムを生成処理して、前記展開済みプログラムを出力する
   請求項１記載のソースプログラム変換システム。
3. 前記請求項１又は２に記載のソースプログラム変換システムにおいて、
   前記展開パラメタ決定部は、受け付けた前記ソースプログラムの中の展開するループの中の、計算回数 および メモリアクセス回数 の少なくとも一方に基づいて、ループ処理コスト（Ｃ）を算出し、所定の閾値（Ｃmin）を用いて、Ｃmin ≦ Ｃ×Ｎ を満たす最小の整数Ｎを、ループ展開段数に決定するソースプログラム変換システム。
4. 前記請求項１から３の何れか一項に記載のソースプログラム変換システムにおいて、
   前記展開パラメタ決定部は、受け付けた前記ソースプログラムの展開するループのループ回転数を計算し、決定したループ展開段数を参照して、ループ展開幅に、（ソースプログラムのループ回転数÷ループ展開段数）以下となる正整数を設定するソースプログラム変換システム。
5. 前記請求項１から３の何れか一項に記載のソースプログラム変換システムにおいて、
   前記展開パラメタ決定部は、ループ展開幅に、展開済みプログラムを実行するベクトル計算機のベクトル長を設定するソースプログラム変換システム。
6. 前記請求項１から３の何れか一項に記載のソースプログラム変換システムにおいて、
   前記展開パラメタ決定部は、前記ソースプログラムを実行させるベクトル計算機のベクトル長 又は 機種 が前記ソースコード中に記載されているか判別し、ベクトル長 又は 機種 が記載されていた場合、該記載されていたベクトル長 又は 機種から定まるベクトル長 を識別して、ループ展開幅に識別したベクトル長を設定するソースプログラム変換システム。
7. 前記請求項１から６の何れか一項に記載のソースプログラム変換システムにおいて、
   前記展開プログラム作成部は、外側ループが、カウンタ変数が、初期値０から、ループ１回転ごとに、前記ループ展開幅と前記ループ展開段数の積ずつ増加し、ソースプログラムのループの回転数と前記積の値の差以下であるまでループし、内側ループが、カウンタ変数が、初期値０から、ループ１回転ごとに、ソースプログラムのループのカウンタ変数のループ１回転ごとの増加値ずつ増加し、前記ループ展開幅より小さい間ループするような、２重ループを作成し、
   当該２重ループの中に、ソースプログラムのループ中の計算式を、前記ループ展開段数分展開する
   ソースプログラム変換システム。
8. 変換対象とするソースプログラムを受け付け、
   前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定し、
   展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数を導出処理すると共に、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理し、
   導出したループ展開段数とループ展開幅に基づいて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する
   情報処理システムによるソースプログラム変換方法。
9. 情報処理リソースを、
   変換対象とするソースプログラムを受け付けるプログラム入力手段と、
   前記プログラム入力手段に入力された前記ソースプログラムに含まれる各ループを識別し、各ループに対して展開に関連するデータ依存関係を解析して、各ループの展開の可否を判定する展開可否判定手段と、
   前記展開可否判定手段が展開可と判定したループについて、展開後のループにて、展開前のループの何回転分の計算処理をするかを示す正整数であるループ展開段数、および、展開前のループの何回転とびのループの計算処理を、展開後のループ一回転において計算するかを示す正整数であるループ展開幅を導出処理する展開パラメタ決定手段と、
   前記展開パラメタ決定手段が決定した、ループ展開段数とループ展開幅を受けて、展開したループを有するプログラムを生成処理して、展開済みプログラムとして出力する展開プログラム作成手段、
   として動作させるソースプログラム変換プログラム。

Images