(57)【特許請求の範囲】
【請求項１】
ソースプログラムのベクトル化時に展開数の最適化を行うコンパイラにおいて、
上記ソースプログラムをベクトル化する手段と、
上記ソースプログラムを解析してループの繰り返し回数を検出、あるいはループの繰り返し回数を検出して不明と判定する手段と、
上記ループの繰り返し回数が検出された場合に、検出されたループの繰り返し回数から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数するを算出し、一方、上記ループの繰り返し回数が不明と判定された場合に、ループで使用している配列のベクトル次元から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数を算出する手段と、
上記算出された仮想展開数について、上記ベクトル化されたプログラムのデータ依存関係をもとに展開数を算出する手段と、
上記算出された展開数をもとに上記ベクトル化されたプログラムを展開する手段と
を備えたことを特徴とするコンパイラ。
【請求項２】
上記プログラムを展開した後に、重複するメモリアクセス命令がある場合に、レジスタ間移動命令に変更する手段を備えたことを特徴とする請求項１記載のコンパイラ。
【請求項３】
デフォルトで上記展開数の最大値を設定しておき、当該最大値を超えない範囲内で展開数を算出することを特徴とする請求項１あるいは請求項２記載のコンパイラ。
【請求項４】
コンピュータに、
入力されたソースプログラムをベクトル化する手段と、
上記ソースプログラムを解析してループの繰り返し回数を検出、あるいはループの繰り返し回数を検出して不明と判定する手段と、
上記ループの繰り返し回数が検出された場合に、検出されたループの繰り返し回数から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数するを算出し、一方、上記ループの繰り返し回数が不明と判定された場合に、ループで使用している配列のベクトル次元から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数を算出する手段と、
上記算出された仮想展開数について、上記ベクトル化されたプログラムのデータ依存関係をもとに展開数を算出する手段と、
上記算出された展開数をもとに上記ベクトル化されたプログラムを展開する手段と
して機能させるプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ソースプログラムのベクトル化時に展開数の最適化を行うコンパイラおよび記録媒体に関するものである。
【０００２】
【従来の技術】
従来、ソースプログラムをベクトル化する場合に、ループの繰り返し回数を減らして高速化を図るアンローリング処理が行われている。この従来のアンローリング処理における展開数は下記のようにして決めていた。
【０００３】
（１）  コンパイラディレクティブに指定された展開数とする。
（２）  外側ループの繰り返し回数が陽に判る場合には、その値を展開数とする。
【０００４】
（３）  上記以外で、展開後の命令数が許容範囲（例えばレジスタ不足にならない範囲）を越えなければｎ重展開とする。
【０００５】
【発明が解決しようとする課題】
上記従来の展開数では、演算数が多い場合は良いが、演算数が少ないループではレジスタを有効に使わないオブジェクトが生成されてしまうという問題があった。
【０００６】
また、アンローリング数の増加によりオブジェクト量が多量になってしまう危険性を持つという問題もあった。
本発明は、これらの問題を解決するため、ソースプログラムをベクトル化するときにループの繰り返し回数などをもとに最適化したアンローリング処理を行うと共に重複するメモリアクセスを削除し、オブジェクトプログラムの実行性能の向上を図ることを目的としている。
【０００７】
【課題を解決するための手段】
図１を参照して課題を解決するための手段を説明する。
図１において、ソースプログラム１は、ベクトル化する際に展開数の最適化を行う対象のプログラムである。
【０００８】
コンパイラ２は、ソースプログラム１を入力とし、実行可能形式のオブジェクトプログラム１０を生成するものであって、ここでは、最適化手段４などから構成されるものである。
【０００９】
最適化手段４は、ソースプログラム１をベクトル化して最適化を行うものであって、ここでは、ベクトル化手段５、およびベクトル最適化手段６などから構成されるものである。
【００１０】
ベクトル最適化手段６は、ベクトル化する際に展開数の最適化を行うものであって、ここでは、アンローリング手段７およびメモリアクセス削除手段８などから構成されるものである。
【００１１】
アンローリング手段７は、ベクトル化する際に最適な展開数で展開したりなどするものである。
メモリアクセス削除手段８は、最適な展開数で展開した後の重複するメモリアクセスをレジスタ間転送命令に変更し、削除するものである。
【００１２】
次に、動作を説明する。
ベクトル化手段５がソースプログラム１をベクトル化し、アンローリング手段７がソースプログラム１を解析して検出されたループの繰り返し回数から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数を算出し、算出した仮想展開数について、ベクトル化されたプログラムのデータ依存関係をもとに展開数を算出して展開し、メモリアクセス削除手段８が展開後のベクトル命令列から重複するメモリアクセス命令がある場合にレジスタ間移動命令に変更するようにしている。
【００１３】
また、ベクトル化手段５がソースプログラム１をベクトル化し、アンローリング手段７がソースプログラムを解析して検出されたループの繰り返し回数が不明の場合に、ループで使用している配列のベクトル次元から求めたレジスタ個数および演算に必要な最大レジスタ数をもとに仮想展開数を算出し、算出した仮想展開数についてベクトル化されたプログラムのデータ依存関係をもとに展開数を算出し、算出した展開数をもとにベクトル化されたプログラムを展開し、メモリアクセス削除手段８が展開後のベクトル命令列から重複するメモリアクセス命令がある場合にレジスタ間移動命令に変更するようにしている。
【００１４】
これらの際に、デフォルトで展開数の最大値を設定しておき、最大値を越えない範囲内で展開数を算出するようにしている。
従って、ソースプログラム１をベクトル化するときにループの繰り返し回数などをもとに最適化したアンローリング処理を行うと共に重複するメモリアクセスを削除することにより、オブジェクトプログラム１０の実行性能の向上を図ることが可能となる。
【００１５】
【発明の実施の形態】
次に、図１から図４を用いて本発明の実施の形態および動作を順次詳細に説明する。
【００１６】
図１は、本発明のシステム構成図を示す。
図１において、ソースプログラム１は、ベクトル化する際に展開数の最適化を行う対象のプログラムであって、例えば後述する図４の（ａ）に示すような、ループの存在するプログラムである。
【００１７】
コンパイラ２は、ソースプログラム１を入力とし、実行可能形式のオブジェクトプログラム１０を生成するものであって、ここでは、ソースプログラム解析手段３、最適化手段４、およびコード生成手段９などから構成されるものである。
【００１８】
ソースプログラム解析手段３は、ソースプログラム１を形態素解析、構文解析などを行い、中間言を生成するものである。ここで、実際は、形態素解析および構文解析などを行った情報を付加した中間言をもとに以降説明するベクトル化、アンローリング処理などを行うが、説明を分かり易くするために、ソースプログラム１をベクトル化、アンローリング処理するなどとして説明を行う。
【００１９】
最適化手段４は、ソースプログラム１の最適化を行うものであって、ここでは、ベクトル化手段５、およびベクトル最適化手段６などから構成されるものである。
【００２０】
ベクトル化手段５は、ソースプログラム１をベクトル化するものであって、例えば後述する図３の（ａ）のソースプログラム１を（ｂ）に示すプログラム（ベクトル計算機で動作するベクトル命令を使ったプログラム）にするものである。
【００２１】
ベクトル最適化手段６は、ベクトル化されたプログラムを最適化するものであって、ここでは、アンローリング手段７およびメモリアクセス削除手段８などから構成されるものである。
【００２２】
アンローリング手段７は、ベクトル化されたプログラムについて、最適な展開数で展開してループの繰り返し回数を削減したりなどするものである。
メモリアクセス削除手段８は、最適な展開数で展開した後のプログラム中で重複するメモリアクセスをレジスタ間転送命令に変更し、削除したりするものである。
【００２３】
コード生成手段９は、最適化後のプログラムを、実行可能形式のオブジェクトプログラム１０にするものである。
次に、図２のフローチャートの順番に従い、図１の構成の動作を詳細に説明する。
【００２４】
図２は、本発明の動作説明フローチャートを示す。
図２において、Ｓ１は、コンパイラディレクティブ指定があるか判別する。ＹＥＳの場合には、その指定に従いＳ６以降の処理に進む。一方、ＮＯの場合には、Ｓ２に進む。
【００２５】
Ｓ２は、ループの繰り返し回数が不明か判別する。これは、ソースプログラム１のループの回数が不明、例えば後述する図３の（ａ）のソースプログラム１ではループの回数が判明と判別し、図４の（ａ）のソースプログラム１ではループの回数が不明と判別する。ＹＥＳの場合には、Ｓ３に進む。ＮＯの場合には、Ｓ９に進む。
【００２６】
Ｓ９は、Ｓ２のＮＯでループの繰り返し回数が不明でないと判別されたので、
仮想展開数＝（ループ内の繰り返し回数から見積もったレジスタ個数）／（必要なレジスタ数の最大値）
を求める。例えば後述する図３の（ｂ）のベクトル化した後のプログラムにおいて、当該プログラムの場合には（ループ内の繰り返し回数から見積もったレジスタ個数）＝２５６、必要なレジスタ数の最大値＝１であるので、仮想展開数＝２５６となるが、実行させるベクトル計算機の各種性能を考慮してデフォルトで最大が例えば４と設定されているので、仮想展開数を４と決定する。
【００２７】
Ｓ１０は、メモリアクセスの削除が可能か判別する。これは、例えば後述する図３の（ｃ−１）に示すように、展開（この場合には４重展開）した場合に重複するメモリアクセスがあって当該メモリアクセスを削除して変りにレジスタ間移動命令で置き換えることが可能か判別する。ＹＥＳの場合には、Ｓ１１に進む。一方，ＮＯの場合には、Ｓ６に進む。
【００２８】
Ｓ１１は、Ｓ１０のＹＥＳでメモリアクセス削除可能と判明したので、正式展開数を、データ依存関係を見て補正する。例えば後述する図３の（ｂ）のベクトル化したプログラムの場合には、２重展開からメモリアクセス命令の削除が可能であるので、Ｓ９で決めた仮想展開数４をそのまま正式展開数として決定する。そして、Ｓ６に進む。
【００２９】
Ｓ６は、ループアンローリングの展開処理を行う。これは、Ｓ９で決定した正式展開数、ここでは４をもとに、例えば図３の（ｂ）を図３の（ｃ−１）に示すように４重展開する。
【００３０】
Ｓ７は、メモリアクセスの削除が可能か判別する。ＹＥＳの場合には、Ｓ８に進む。ＮＯの場合には、終了する。
Ｓ８は、Ｓ７のＹＥＳでメモリアクセスの削除が可能と判明したので、メモリアクセスの削除処理を行う。例えば図３の（ｃ−１）の４重展開した後のプログラム中の重複するメモリアクセスをレジスタ間移動命令（例えばＶＭＯＶＥ命令）に置き換え、重複するメモリアクセスを削除し、図３の（ｃ−２）に示すプログラムに修正する。
【００３１】
以上のＳ１のＮＯ，Ｓ２のＮＯ，Ｓ９からＳ１１、Ｓ６からＳ８の手順によって、プログラムのループの繰り返し回数が判明する場合に、内部のループについて多重展開を行ってループの繰り返し回数を削減および重複したメモリアクセスをＶＭＯＶＥ命令に置き換えてメモリアクセスを必要最小限とし、オブジェクトプログラム１０の実行性能を向上させることが可能となる。
【００３２】
次に、ループの繰り返し回数が不明の場合について以下説明する。
図２において、Ｓ３は、Ｓ２のＹＥＳでループの繰り返し回数が不明と判明したので、
仮想展開数＝（ループ内で使用している配列のベクトル次元の添字に現れた要素数から見積もったレジスタ個数）／（必要なレジスタ数の最大値）
を求める。例えば後述する図４の（ｂ）のベクトル化した後のプログラムにおいて、当該プログラムの場合には（ループ内の繰り返し回数から見積もったレジスタ個数）＝２５６、（必要なレジスタ数の最大値）＝１．３であるので、仮想展開数＝２５６／１．３＝１９６と決定する。
【００３３】
Ｓ４は、データ依存関係から最大展開数を見積もる。例えば図４の（ｂ）のプログラムの場合には、２重展開以上してもメモリアクセスの削除は見込めないので、最大展開数＝２と決定する。
【００３４】
Ｓ５は、正式展開数が最大展開数を越えない範囲で決定する。ここでは、例えば図４の（ｂ）の場合には、上記したように、最大展開数＝２であるので、これを越えない正式展開数を２と決定する。
【００３５】
Ｓ６は、ループアンローリングの展開処理を行う。これは、Ｓ５で決定した正式展開数、ここでは２をもとに、例えば図４の（ｂ）を図４の（ｃ）に示すように２重展開する。
【００３６】
Ｓ７は、メモリアクセスの削除が可能か判別する。ＹＥＳの場合には、Ｓ８に進む。ＮＯの場合には、終了する。
Ｓ８は、Ｓ７のＹＥＳでメモリアクセスの削除が可能と判明したので、メモリアクセスの削除処理を行う。
【００３７】
以上のＳ１のＮＯ，Ｓ２のＹＥＳ，Ｓ３からＳ８の手順によって、プログラムのループの繰り返し回数が不明の場合に、内部のループで使用している配列のベクトル次元の添字に現れる要素数、必要なレジスタ数の最大値などをもとに展開数を決定して多重展開を行い、ループの繰り返し回数を削減および重複したメモリアクセスをＶＭＯＶＥ命令に置き換えてメモリアクセスを必要最小限とし、オブジェクトプログラム１０の実行性能を向上させることが可能となる。
【００３８】
図３は、本発明の説明図（その１、ループの繰り返し回数判明）を示す。ここでは、ループの繰り返し回数が判明するプログラムについて以下説明する。
図３の（ａ）は、ソースプログラム１の例を示す。このソースプログラム１は、図示のように、２重ループからなるプログラムである。
【００３９】
図３の（ｂ）は、アンローリング展開前のプログラムの例を示す。これは、図３の（ａ）のソースプログラム１をベクトル化した後のプログラムであって、図示のように、アンローリング展開前の１重展開したものである。
【００４０】
図３の（ｃ）は、アンローリング展開後のプログラムを示す。ここでは、図３の（ｂ）のアンローリング展開前のプログラムを、４重展開して（ｃ−１）のプログラムを作成し、次に、（ｃ−１）のプログラム中の重複したメモリアクセス命令を削除してレジスタ間移動命令（ＶＭＯＶＥ命令）に置き換えてメモリセスを必要最小限に削減して（ｃ−２）のプログラムを作成する。
【００４１】
図３の（ｃ−１）は、図３の（ｂ）のプログラムを４重展開（既述した図２のＳ３からＳ５で決定した展開数４）したプログラムの例を示す。尚、４重展開の場合には、ループの繰り返しに対して４で割った余りの処理に関しては、別のループを生成している（図３の（ｃ−１）の末尾のＤＯループ参照）。ここでは、図示したように、３つの重複したメモリアクセスが存在するので、これら重複するメモリアクセスを削除し、変わりにＶＭＯＶＥ命令に置き換えて図３の（ｃ−２）に示すプログラムとし、実行性能を向上させている。
【００４２】
図３の（ｃ−２）は、メモリアクセスを削除した場合のプログラムの例を示す。これは、図３の（ｃ−１）のプログラム中の重複するメモリアクセスの一方を削除し他方はＶＭＯＶＥ命令でレジスタ間転送して処理を行うように修正したものである。
【００４３】
尚、図３のプログラムの場合の展開数の決定について説明する。
図３の（ａ）のプログラムはループの繰り返し回数が判明し、ループの繰り返し回数から見積もったレジスタ個数がここでは２５６となり、必要なレジスタ数の最大値が１となるので、仮想展開数＝２５６／１＝２５６となるが、デフォルトで通常最大仮想展開数＝４と設定しているので、仮想展開数＝４と決定する。次に、メモリアクセスの削除が可能かの観点より、データ依存関係を見ると、２重展開からメモリアクセスの削除が可能と判明するので、正式展開数をそのまま４と決定する。決定された４重展開する場合には、４で割り切れる部分を図３の（ｃ−１）の上段のループ（４重展開のループ）とし、余りの部分を図３の（ｃ−１）の下段のループ（１重展開のままのループ）とする。更に、重複するメモリアクセスをレジスタ間移動命令（ＶＭＯＶＥ命令）に置き換えると図３の（ｃ−２）のプログラムを生成することが可能となる。
【００４４】
図４は、本発明の説明図（その２、ループの繰り返し回数不明）を示す。ここでは、ループの繰り返し回数が不明なプログラムについて以下説明する。
図４の（ａ）は、ソースプログラム１の例を示す。このソースプログラム１は、図示のように、２重ループからなるプログラムである。
【００４５】
図４の（ｂ）は、アンローリング展開前のプログラムの例を示す。これは、図４の（ａ）のソースプログラム１をベクトル化した後のプログラムであって、図示のように、アンローリング展開前の１重展開したものである。
【００４６】
図４の（ｃ）は、アンローリング展開後のプログラムを示す。ここでは、図４の（ｂ）のアンローリング展開前のプログラムを２重展開して作成する。
尚、図４のプログラムの場合の展開数の決定について説明する。
【００４７】
図４の（ａ）のプログラムはループの繰り返し回数が不明であるので、ループ内で使用している配列のベクトル次元の添字に現れた要素数から見積もったレジスタ個数がここでは２５６となり、必要なレジスタ数の最大値が１．３となるので、仮想展開数＝２５６／１．３＝１９６となる。データの依存関係から最大展開数を見積もると、２展開以上してもメモリアクセスの削除が見込めないので最大展開数を２と決定する。正式展開数は最大展開数を越えない範囲で決まるので、この場合には正式展開数が２と決定され、図４の（ｃ）のプログラムに示すように、２重展開する。
【００４８】
【発明の効果】
以上説明したように、本発明によれば、ソースプログラム１をベクトル化するときにループの繰り返し回数などをもとに最適化したアンローリング処理を行うと共に重複するメモリアクセスを削除する構成を採用しているため、オブジェクトプログラム１０の実行性能の向上を図ることができる。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の動作説明フローチャートである。
【図３】本発明の説明図（その１）である。
【図４】本発明の説明図（その２）である。
【符号の説明】
１：ソースプログラム
２：コンパイラ
３：ソースプログラム解析手段
４：最適化手段
５：ベクトル化手段
６：ベクトル最適化手段
７：アンローリング手段
８：メモリアクセス削除手段
９：コード生成手段
１０：オブジェクトプログラム
【図１】
0003953697.tif 000002
【図２】
0003953697.tif 000003
【図３】
0003953697.tif 000004
【図４】
0003953697.tif 000005