(57)【要約】【課題】ループの繰り返し数が、最大ベクトル長よりも小さな２重ループであっても、実行効率の高いベクトルプロセッサ向けの目的プログラムを制限なく生成する。【解決手段】外側ループと内側ループとの２重ループを有するソースプログラムの内側ループの繰り返し数Ｎがソースプログラムの最大ベクトル長ＶＬの１/２以下である場合、２重ループを、Ｎの要素の演算を行うベクトル演算をループ本体とし、外側ループの繰り返し数Ｍを、ＶＬをＮで割った値とＭとのどちらか小さな値で割った余りの値を繰り返し数とするループと、ＶＬをＮで割った値とＭとのどちらか小さな値にＮを乗じた値の要素の演算を行うベクトル演算をループ本体とし、Ｍを、ＶＬをＮで割った値とＭとのどちらか小さな値で割った値を繰り返し数とするループとの２重ループにループ変換部２３にて変換する。【選択図】図１
2009070070.tif 000002
【特許請求の範囲】
【請求項１】
外側ループと内側ループとの２重ループを有するソースプログラムを目的プログラムに変換するコンパイラであって、
前記外側ループの繰り返し数をＭとし、前記内側ループの繰り返し数をＮとし、前記ソースプログラムの最大ベクトル長をＶＬとし、前記Ｎが前記ＶＬの１/２以下である場合、
前記２重ループを、
前記Ｎの要素の演算を行うベクトル演算をループ本体とし、前記Ｍを、前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値で割った余りの値を繰り返し数とするループと、
前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値に前記Ｎを乗じた値の要素の演算を行うベクトル演算をループ本体とし、前記Ｍを、前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値で割った値を繰り返し数とするループとの２重ループに変換するコンパイラ。
【請求項２】
請求項１に記載のコンパイラにおいて、
前記変換した２重ループに基づいて前記目的プログラムを生成することを特徴とするコンパイラ。
【請求項３】
内側ループと外側ループとの２重ループを有するソースプログラムを目的プログラムに変換するコンパイル方法であって、
前記外側ループの繰り返し数をＭとし、前記内側ループの繰り返し数をＮとし、前記ソースプログラムの最大ベクトル長をＶＬとし、前記Ｎが前記ＶＬの１/２以下である場合、
前記ＶＬを前記Ｎによって除算する第１の除算処理と、
前記Ｍを前記第１の除算処理の結果と前記Ｍとのどちらか小さな値によって除算する第２の除算処理と、
前記第１の除算処理の結果と前記Ｍとのどちらか小さな値に前記Ｎを乗ずる乗算処理と、
前記Ｎの要素の演算を行うベクトル演算をループ本体とし、前記第２の除算処理の結果の余りの値を繰り返し数とするループと、前記乗算処理の結果の値の要素の演算を行うベクトル演算をループ本体とし、前記第２の除算処理の結果の値を繰り返し数とするループとの２重ループに変換する処理とを有するコンパイル方法。
【請求項４】
請求項３に記載のコンパイル方法において、
前記変換した２重ループに基づいて前記目的プログラムを生成する処理を有することを特徴とするコンパイル方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＦｏｒｔｒａｎやＣ言語となどの高級言語を入力し、ベクトルプロセッサ向けの目的プログラムを生成するコンパイラ及びコンパイル方法に関する。
【背景技術】
【０００２】
ＦｏｒｔｒａｎやＣ言語などの高級言語からベクトルプロセッサ向けの目的プログラムを生成するコンパイラは、一般にソースプログラム中のループを、ベクトル処理を行うベクトル命令列に変換するベクトル化機能を備える。このベクトル化において生成される１個のベクトル命令が処理するデータ要素数は、ループの繰り返し数以下となる。
【０００３】
ここで、ループの繰り返し数が、ベクトルプロセッサの最大ベクトル長よりも小さな場合、ベクトルプロセッサの備える演算器などのハードウェア資源に空きが生じてしまう。そのため、生成された目的プログラムの実行効率が低くなってしまう。
【０００４】
そこで、ベクトル化するループの繰り返し数を大きくする手法として、ループを一重化する技術が考えられている（例えば、特許文献１参照。）。
【０００５】
また、多重ループのループ交換により、ベクトル化するループの繰り返し数を大きくする技術が考えられている（例えば、非特許参考文献１参照。）。
【０００６】
また、ループ内の複数の同一演算に対して１個のベクトル命令を生成する方法が考えられている（例えば、特許文献２参照。）。
【特許文献１】特開平６−４３００号公報
【特許文献２】特開平２−２３６７７５号公報
【非特許文献１】Hans Zima/Barbara Chapman共著、村岡洋一訳、「スーパーコンパイラ」、オーム社、１９９５年４月、ｐ．２２３−２３０、２６２
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献１に記載された技術を用いたループ一重化は、多重ループ内で使用されているすべての配列が連続でなければならないという条件がある。そのため、適用できる多重ループがかなり限定されてしまうという問題点がある。
【０００８】
また、非特許文献１に記載された技術を用いたループ交換においては、多重ループを構成するループ中の最大の繰り返し数以上にはできない。そのため、すべてのループの繰り返し数が最大ベクトル長よりも小さな場合は、実行効率を改善することが困難であるという問題点がある。
【０００９】
また、特許文献２に記載された技術においては、同一演算を複数含むループにしか適用することができないという問題点がある。
【００１０】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、ループの繰り返し数が、ベクトルプロセッサの最大ベクトル長よりも小さな２重ループであっても、実行効率の高いベクトルプロセッサ向けの目的プログラムを制限なく生成することができるコンパイラ及びコンパイル方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために本発明は、
外側ループと内側ループとの２重ループを有するソースプログラムを目的プログラムに変換するコンパイラであって、
前記外側ループの繰り返し数をＭとし、前記内側ループの繰り返し数をＮとし、前記ソースプログラムの最大ベクトル長をＶＬとし、前記Ｎが前記ＶＬの１/２以下である場合、
前記２重ループを、
前記Ｎの要素の演算を行うベクトル演算をループ本体とし、前記Ｍを、前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値で割った余りの値を繰り返し数とするループと、
前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値に前記Ｎを乗じた値の要素の演算を行うベクトル演算をループ本体とし、前記Ｍを、前記ＶＬを前記Ｎで割った値と前記Ｍとのどちらか小さな値で割った値を繰り返し数とするループとの２重ループに変換する。
【発明の効果】
【００１２】
以上説明したように本発明においては、ソースプログラムが有する２重ループのうち、外側ループの繰り返し数をＭとし、内側ループの繰り返し数をＮとし、ソースプログラムの最大ベクトル長をＶＬとし、ＮがＶＬの１/２以下である場合、２重ループを、Ｎの要素の演算を行うベクトル演算をループ本体とし、Ｍを、ＶＬをＮで割った値とＭとのどちらか小さな値で割った余りの値を繰り返し数とするループと、ＶＬをＮで割った値とＭとのどちらか小さな値にＮを乗じた値の要素の演算を行うベクトル演算をループ本体とし、Ｍを、ＶＬをＮで割った値とＭとのどちらか小さな値で割った値を繰り返し数とするループとの２重ループに変換する構成としたため、ループの繰り返し数が、ベクトルプロセッサの最大ベクトル長よりも小さな２重ループであっても、実行効率の高いベクトルプロセッサ向けの目的プログラムを制限なく生成することができる。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１４】
図１は、本発明のコンパイラの実施の一形態を示す図である。
【００１５】
本形態は図１に示すように、ソースプログラム記憶装置１と、コンパイラ２と、目的プログラム記憶装置３とから構成されている。
【００１６】
ソースプログラム記憶装置１は、ＦｏｒｔｒａｎやＣ言語などの高級言語で記述されたソースプログラムを記憶する。
【００１７】
コンパイラ２は、ソースプログラム記憶装置１に記憶されているソースプログラムからコンピュータが実行できる形式であるオブジェクトコード（目的プログラム）を生成する。つまり、ソースプログラムを目的プログラムに変換する。そして、生成した目的プログラムを目的プログラム記憶装置３へ送信する。
【００１８】
目的プログラム記憶装置３は、コンパイラ２から送信されてきた目的プログラムを記憶する。
【００１９】
さらに、コンパイラ２は、ソースプログラム解析部２１と、ループ解析部２２と、ループ変換部２３と、目的プログラム生成部２４と、第１中間テキスト記憶部２５と、ループ情報記憶部２６と、第２中間テキスト記憶部２７とから構成されている。
【００２０】
ソースプログラム解析部２１は、ソースプログラム記憶装置１に記憶されているソースプログラムを入力し、解析処理および変換処理で使用するための第１中間テキストを生成する。そして、生成した第１中間テキストを第１中間テキスト記憶部２５に記憶させる。
【００２１】
第１中間テキスト記憶部２５は、ソースプログラム解析部２１にて生成された第１中間テキストを記憶する。
【００２２】
ループ解析部２２は、ソースプログラム解析部２１にて生成されて第１中間テキスト記憶部２５に記憶された第１中間テキストを入力し、ループの入れ子構造およびループの繰り返し回数、ループインデックス、ループ内の文のデータ依存、制御依存情報を含むループ情報を生成する。そして、生成したループ情報をループ情報記憶部２６に記憶させる。
【００２３】
ループ情報記憶部２６は、ループ解析部２２にて生成されたループ情報を記憶する。
【００２４】
ループ変換部２３は、ループ解析部２２にて生成されてループ情報記憶部２６に記憶されたループ情報に基づいて第２中間テキストを生成する。具体的には、内側ループがベクトル化可能かつ繰り返し数Ｎ（Ｎは１以上の整数）が最大ベクトル長ＶＬ（ＶＬは１以上の整数）の１/２以下で外側ループの繰り返し数Ｍ（Ｍは１以上の整数）が２以上かつ変換可能条件を満たす２重ループを選択する。ここで、最大ベクトル長とは、１つのベクトル命令で処理できる最大要素数である。第１中間テキスト記憶部２５から入力した第１中間テキスト中の選択された２重ループを、Ｎ要素の演算を行うベクトル演算をループ本体とする繰り返し数mod(M, min(M, VL/N))のループと、Ｎにmin(M, VL/N)を乗算するN*min(M, VL/N)要素の演算を行うベクトル演算をループ本体とする繰り返し数M/min(M, VL/N)のループとに変換した第２中間テキストを生成する。そして、生成した第２中間テキストを第２中間テキスト記憶部２７に記憶させる。ここで、mod(x,y)は、ｘをｙで割った（除算した）余りの値を示す。また、min(x,y)は、ｘとｙとのどちらか小さな値を示す。また、VL/Nを第１の除算処理、M/min(M, VL/N)を第２の除算処理とする。
【００２５】
第２中間テキスト記憶部２７は、ループ変換部２３にて生成された第２中間テキストを記憶する。
【００２６】
目的プログラム生成部２４は、第２中間テキスト記憶部２７からループ変換部２３にて生成された第２中間テキストを入力し、目的プログラムを生成して、目的プログラム記憶装置３へ送信する。この入力は、目的プログラム生成部２４によって第２中間テキスト記憶部２７から第２中間テキストが読み出されることによるものであっても良い。
【００２７】
以下に、図１に示したコンパイラ２におけるコンパイル方法について説明する。
【００２８】
図２は、図１に示したコンパイラ２におけるコンパイル方法を説明するためのフローチャートである。
【００２９】
まず、ソースプログラム解析部２１に、ソースプログラム記憶装置１に記憶されているソースプログラムが入力する。ソースプログラム解析部２１は、入力したソースプログラムの字句解析および構文解析などを行い、解析処理および変換処理で使用するための第１中間テキストを生成する。そして、生成した第１中間テキストを第1中間テキスト記憶部２５に記憶させる。
【００３０】
その後、ループ解析部２２に、第１中間テキスト記憶部２５に記憶された第１中間テキストが入力する。この入力は、ループ解析部２２によって第１中間テキスト記憶部２５から第１中間テキストが読み出されることによるものであっても良い。
【００３１】
ループ解析部２２は、入力した第１中間テキストについて、当該第１中間テキストのプログラム中に現れる全ループ構造を解析し、ループインデックス、ループの繰り返し数、ループ間の入れ子関係、ループ内の文のデータ依存および制御依存関係を調査する。そして、調査した結果の情報を有するループ情報を生成する。生成されたループ情報をループ情報記憶部２６に記憶させる。
【００３２】
その後、ループ変換部２３は、ループ情報記憶部２６に記憶されているループ情報を読み出す。読み出されたループ情報に基づいて、変換対象となる２重ループを選択する。ループ変換部２３の動作は以下に示す通りである。
【００３３】
まず、ループ内の文のデータ依存および制御依存がベクトル化可能条件を満たすループを選択する（ステップＳ１０１）。
【００３４】
ステップＳ１０１にて選択されたループの中から、ループの繰り返し数Ｎがベクトルプロセッサの最大ベクトル長ＶＬの１/２以下であるものを選択する（ステップＳ１０２）。
【００３５】
ステップＳ１０２にて選択されたループが別のループの内側ループとなっているものを選択する（ステップＳ１０３）。
【００３６】
ステップＳ１０３にて選択されたループの外側ループの繰り返し数が２以上であるものを選択する（ステップＳ１０４）。
【００３７】
ステップＳ１０４にて選択されたループの外側ループ内の文の間でデータ依存および制御依存が存在しないものを選択する（ステップＳ１０５）。
【００３８】
以上のステップＳ１０１からステップＳ１０５で選択されたループおよびそのループの外側ループから構成される２重ループに対応する第１中間テキストを変換し、第２中間テキストとして生成する（ステップＳ１０６）。そして、生成した第２中間テキストを第２中間テキスト記憶部２７に記憶させる。
【００３９】
なお、３重以上入れ子になった多重ループの場合でも、それを構成している最内側の２重ループがステップＳ１０１からステップＳ１０５の条件を満たしていれば、その内側の２重ループ部分を変換対象とすることができる。
【００４０】
変換処理では、繰り返し数mod(M, min(M, VL/N))の第１のループと、それに続く、ループインデックスＪ２の始値がmod(M, min(M, VL/N))+1、限界値がＭ、増分値ＩＮＣがmin(M, VL/N)の第２のループとを生成する。
【００４１】
第１のループのループ本体は、もとの２重ループの内側ループのループ本体中で参照されている外側ループのループインデックスＪを第１のループのループインデックスに置換し、内側ループのループインデックスＩの始値から限界値の範囲の要素の演算を行うベクトル演算とする。
【００４２】
第２のループのループ本体は、２種類のベクトル転送と１種類のベクトル演算とから構成される。１つ目のベクトル転送は、もとの２重ループの内側ループのループ本体で参照されている各配列Xn(I,J)に対し、Xn(1:N, J2)を大きさN*INCの作業用配列ＷＸｎの１からＮ番目の要素であるWXn(1:N)に、Xn(1:N,J2+1) をWXn(N+1:2*N)に、・・・、Xn(1:N, J2+INC-1) をWXn((INC-1)*N+1:INC*N)にそれぞれ転送するベクトル転送である。また、ベクトル演算は、内側ループ内の演算のオペランドの配列Xn(I,J)を対応する作業配列WXn(1:N*INC)に置換し、演算結果の格納先の配列Yn(I,J)を大きさN*INCの作業配列WYn(1:N*INC)に置換したベクトル演算である。また２つ目のベクトル転送は、ループ本体内で定義されている各配列Yn(I,J)に対し、対応する作業配列WYn(1:N)をYn(1:N,J2)に、WYn(N+1:2*N)をYn(1:N,J2+1)に、・・・、WYn((INC-1)*N+1:INC*N)をYn(1:N,J+INC-1)にそれぞれ転送するベクトル転送である。
【００４３】
そして、目的プログラム生成部２４は、第２中間テキスト記憶部２７から第２中間テキストを読み出し、読み出した第２中間テキストに基づいてベクトルプロセッサの目的プログラムを生成して目的プログラム記憶装置３へ送信する。
（実施例）
以下に本発明の実施例を示す。
【００４４】
図３は、Ｆｏｒｔｒａｎ言語で記述された２重ループを含むソースプログラムの一例を示す図である。
【００４５】
図３に示すソースプログラムは、配列Ｂと配列Ｃとの加算を行い、結果を配列Ａに求めるものである。このソースプログラムを入力し、最大ベクトル長ＶＬが１００であるベクトルプロセッサの目的プログラムを生成する場合を例に挙げる。
【００４６】
ループ解析部２２は、ソースプログラム解析部２１が図３に示したソースプログラムから生成した第１中間テキストを解析し、ループ情報を生成する。生成されるループ情報は、ループＬ１の繰り返し数が１０、ループＬ２の繰り返し数が３０、ループＬ１，Ｌ２ともにデータ依存と制御依存なし、ループＬ１がループＬ２の外側ループとなっているという情報である。
【００４７】
次に、ループ変換部２３は、ループ解析部２２が生成したループ情報から、ループＬ２がベクトル化可能であること、また３０である繰り返し数が最大ベクトル長１００の１/２以下であること、またループＬ２の外側にループＬ１が存在すること、ループＬ１の繰り返し数が２以上であることを判断する。そして、ループＬ１とループＬ２とから構成される２重ループを変換対象として選択し、第２中間テキストを生成する。
【００４８】
図４は、図１に示したループ変換部２３にて生成された第２中間テキストの一例を示す図である。
【００４９】
図４に示した第２中間テキストは、ループ変換部２３にて変換されたループＬ１１及びループＬ１２を有する。
【００５０】
ループＬ１１は、繰り返し数mod(10, min(10, 100/30))=mod(10, 3)=1でループインデックスがＪ１とする。ループＬ１１のループ本体は、ループＬ２内の文中に現れる外側ループＬ１のループインデックスＪをループＬ１１のループインデックスＪ１に置換し、ループＬ２のループインデックスＩを１から３０の要素のアクセスに置換したベクトル演算A(1:30,J1)←B(1:30,J1)+C(1:30,J1)とする。
【００５１】
ループＬ１２は、始値がmod(10, min(10, 100/30))+1=mod(10, 3)+1=2、限界値がループＬ１１と同じ１０、増分値がmin(10, 100/30)=3であり、ループインデックスはＪ２である。ループＬ１２のループ本体は、３種類のベクトルと１種類のベクトル加算とから構成される。
【００５２】
１つ目のベクトル転送は、配列B(1:30,J2) を大きさ30*3=90の作業用配列ＷＸ１の先頭３０の要素に、またB(1:30,J2+1)をＷＸ１の３１から６０の要素に、またB(1:30,J2+2)をＷＸ１の６１から９０の要素にそれぞれ格納する３個のベクトル転送である。２つ目のベクトル転送は、C(1:30,J2) を作業用配列ＷＸ２の先頭３０の要素に、またC(1:30,J2+1)をＷＸ２の３１から６０の要素に、またC(1:30,J2+2)をＷＸ２の６１から９０の要素にそれぞれ転送する３個のベクトル転送である。ベクトル加算は、ＷＸ１とＷＸ２との９０の要素の加算結果を一時配列ＷＹ１に求めるベクトル加算である。３つ目のベクトル転送は、ＷＹ１の先頭３０の要素をA（1:30,J2）に、またＷＹ１の３１から６０の要素をA(1:30,J2+1)に、またＷＹ１の６１から９０の要素をA（1:30,J2+2）にそれぞれ転送する３個のベクトル転送である。
【００５３】
ループ変換部２３は、変換した第２中間テキストを、第２中間テキスト記憶部２７に記憶させる。
【００５４】
そして、目的プログラム生成部２４は、第２中間テキスト記憶部２７から第２中間テキストを読み出し、読み出した第２中間テキストに基づいてベクトルプロセッサの目的プログラムを生成して目的プログラム記憶装置３へ送信する。この第２中間テキストに基づいて目的プログラムを生成する方法については、一般的な方法を用いるもので良い。
【００５５】
以上説明したように本発明においては、最大ベクトル長をＶＬ、外側ループの繰り返し数をＭ、内側ループの繰り返し数をＮとした場合、従来技術ではＮ要素の演算を行うmin(m,VL/N) 個のベクトル演算命令で処理していたのと同等の処理を、ループ変換部２３により、N*min(M, VL/N)要素の演算を行うベクトル演算命令１個で処理できる目的プログラムを生成できる。
【００５６】
これにより、プログラム中の内側ループの繰り返し数が最大ベクトル長の１/２以下である２重ループに対して、実効効率の高いベクトルプロセッサ向けの目的プログラムを生成できる。
【図面の簡単な説明】
【００５７】
【図１】本発明のコンパイラの実施の一形態を示す図である。
【図２】図１に示したコンパイラにおけるコンパイル方法を説明するためのフローチャートである。
【図３】Ｆｏｒｔｒａｎ言語で記述された２重ループを含むソースプログラムの一例を示す図である。
【図４】図１に示したループ変換部にて生成された第２中間テキストの一例を示す図である。
【符号の説明】
【００５８】
１    ソースプログラム記憶装置
２    コンパイラ
３    目的プログラム記憶装置
２１    ソースプログラム解析部
２２    ループ解析部
２３    ループ変換部
２４    目的プログラム生成部
２５    第１中間テキスト記憶部
２６    ループ情報記憶部
２７    第２中間テキスト記憶部
Ｌ１，Ｌ２，Ｌ１１，Ｌ１２    ループ
【図１】
2009070070.tif 000003
【図２】
2009070070.tif 000004
【図３】
2009070070.tif 000005
【図４】
2009070070.tif 000006