JP4077252B2 - コンパイラプログラムおよびコンパイル処理方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は，ソースプログラムの翻訳において，プログラム中のループ部分の実行時の性能を向上させる技術に関し，特にベクトル化処理を利用するプログラムのコンパイラ技術に関する。
【０００２】
【従来の技術】
コンピュータの科学技術計算分野において，プログラムの実行性能は，ハードウェアとソフトウェア（コンパイラ）の最も重要な価値基準である。また，科学技術計算分野のプログラムはプログラム中のループ部分に実行コストが高いことが知られている。
【０００３】
プログラム中のループ部分を高速化するためのハードウェアとして，ＳＩＭＤ (Single Instruction stream Multiple Data stream) 機構を装備した計算機がある。ＳＩＭＤ機構とは，複数の演算装置にそれぞれ個々に与えたデータに対して同一の命令を並列実行させる演算方式であり，ベクトル演算機構ともいう。その命令をＳＩＭＤ命令またはベクトル命令という。
【０００４】
ＳＩＭＤ機構を装備したハードウェアとして，ベクトル型スーパーコンピュータのＶＰＰシリーズ（富士通株式会社）やＳＸシリーズ（日本電気株式会社）がある。また，Ｐｅｎｔｉｕｍ３／Ｐｅｎｔｉｕｍ４チップ（米国Ｉｎｔｅｌ社）にもＳＳＥ／ＳＳＥ２等のＳＩＭＤ機構がある。さらに，近年の組み込み向けの小型ＣＰＵチップにも高速化に向けたＳＩＭＤ機構が装備されてきた。
【０００５】
これらのＳＩＭＤ機構向けのコンパイラは自動ベクトル化機能により，ＳＩＭＤ命令を生成している。一般に自動ベクトル化機能は，プログラム中のループ構造を対象にＳＩＭＤ命令を生成する。しかし，プログラムのループ中に対象ＣＰＵに装備されたＳＩＭＤ命令として表現できない演算が現れた場合，そのままベクトル化することはできなかった。
【０００６】
そこで，従来は，プログラムのループ中にベクトル化が不可能な演算が出現した場合に，ループ全体をベクトル化不可能とするか，または，ループをベクトル化可能な部分とベクトル化不可能な部分とに分けていた。ベクトル化可能な部分とベクトル化不可能な部分とに分けることを，部分ベクトル化という。
【０００７】
図１３は，従来技術における部分ベクトル化の例を示す図である。図１３のプログラムは，理解しやすいようにソースイメージで示している。また，配列の添字のないものは配列の全要素を示すものとする（以下，本明細書およびすべての図面について同様である）。
【０００８】
図１３（ａ）は，部分ベクトル化を行う前のプログラムの例である。図１３（ａ）のプログラムにおいて，１回目の配列要素Ａ（Ｉ）の演算では，Ｂ（Ｉ）とＣ（Ｉ）の和を求め，２回目の配列要素Ａ（Ｉ）の演算では，Ｂ（Ｉ）とＣ（Ｉ）の積を求め，それぞれの演算結果をＰｒｉｎｔ文により出力している。すなわち，処理▲１▼では１回目の配列要素Ａ（Ｉ）を求める演算を行い，処理▲２▼では１回目の配列要素Ａ（Ｉ）をＰｒｉｎｔ文で出力し，処理▲３▼では２回目の配列要素Ａ（Ｉ）を求める演算をし，処理▲１▼〜▲３▼をＤｏループによりＩ＝１からＩ＝１００まで繰り返した後，処理▲４▼で２回目の配列要素Ａを一度にすべて出力している。このプログラムのループ部分のベクトル化を行いたくとも，ループ内にあるＰｒｉｎｔ文はベクトル化不可能な部分であるため，このままループ部分全体をベクトル化することは不可能である。
【０００９】
そこで，従来のコンパイラで行っていた部分ベクトル化方式では，図１３（ａ）のプログラムのループ部分をベクトル化可能な部分とベクトル化不可能な部分とに分離し，図１３（ｂ）のようなプログラムに展開する。図１３（ｂ）は，図１３（ａ）のプログラムを部分ベクトル化したプログラムの例である。
【００１０】
図１３（ｂ）のプログラムでは，図１３（ａ）のプログラムのループ部分（処理▲１▼〜▲３▼）からベクトル化不可能な部分であるＰｒｉｎｔ文（処理▲２▼）をループ外に出して，ベクトル化可能な部分である処理▲１▼′と，ベクトル化不可能な部分である処理▲２▼′と，ベクトル化可能な部分である処理▲３▼′とに分けている。２回目の配列要素Ａ（Ｉ）の定義については，処理▲１▼′において一時的な作業領域（Ｔｅｍｐ）に結果を格納し，処理▲３▼′において配列Ｔｅｍｐから配列Ａへのデータの受け渡しを行っている。図１３（ｂ）では，処理▲１▼′および処理▲３▼′がベクトル化可能な部分であり，処理▲２▼′および処理▲４▼′（図１３（ａ）における処理▲４▼）がベクトル化不可能な部分である。
【００１１】
【発明が解決しようとする課題】
以上のような従来の部分ベクトル化では，ベクトル化可能な部分とベクトル化不可能な部分とを分けてしまうため，その間のデータのやり取りは一時的な作業領域を必要とする場合があり（上記従来例参照），実行時間に影響を及ぼすことがあった。
【００１２】
また，ＳＩＭＤ機構が装備されていないハードウェアで実行させるプログラムのコンパイルでは，プログラムのベクトル化処理が行われていないため，演算レイテンシの隠蔽，ループの繰り返しによる間接的な時間に関するオーバヘッドの削減ができないという問題があった。演算レイテンシとは，演算命令間の（隠れた）待ち時間のことである。
【００１３】
本発明は，上記問題点の解決を図り，ＳＩＭＤ機構が装備されているハードウェア，または，ＳＩＭＤ機構が装備されていないハードウェア上で動作させるプログラムのコンパイラにおいて，プログラムのベクトル化処理により，特にプログラム中のループ部分の実行性能を向上させることを目的とする。
【００１４】
【課題を解決するための手段】
本発明は，上記課題を解決するため，従来のベクトル化不可能であった演算または部分ベクトル化で処理を行っていたベクトル化不可能な演算を含むループを，擬似的なベクトル演算の表現を使うことにより，ベクトル化可能なループとみなしてコンパイル処理することを特徴とする。
【００１５】
これにより，ＳＩＭＤ機構が装備されたハードウェアでは，ループ全体がベクトル化可能となることで全体としてＳＩＭＤ機構を有効利用でき，大幅な実行性能改善が可能となる。また，ＳＩＭＤ機構が装備されていないハードウェアでは，演算レイテンシの隠蔽やループの繰り返しによる間接的な時間に関するオーバヘッドの削減が実現され，実行性能改善が可能となる。
【００１６】
【発明の実施の形態】
以下，図面に従って本発明の実施の形態を説明する。
【００１７】
図１は，本発明の実施の形態におけるシステムの構成例を示す図である。データ処理装置１は，ＣＰＵおよびメモリからなるコンピュータである。コンパイラ１０は，高級言語で記述されたソースプログラム２０を，機械語の命令列からなるオブジェクトプログラム３０に翻訳（コンパイル）するソフトウェアプログラムであり，コンピュータにインストールされることで，ソースプログラム解析部１１，ベクトル化部１２，ベクトル演算展開部１３，命令スケジューリング部１４，コード生成部１５として機能する。なお，本ソフトウェアプログラムは，ＣＤ−ＲＯＭ，ＭＯ (Magneto Optical disk) ，ＤＶＤ (Digital Versatile Disk) などの媒体や，ネットワークを通して供給することができる。
【００１８】
ソースプログラム解析部１１は，ソースプログラム２０を解析し，中間プログラム（中間言語で記述されたテキスト）を作成する。ベクトル化部１２は，ソースプログラム解析部１１から中間プログラムを受け取り，そのプログラムからベクトル化可能であるループを抽出し，ベクトル化処理を実行する。このとき，オブジェクトプログラム３０を動作させるターゲットとなるコンピュータ（以下，ターゲットマシンという）に，対応するＳＩＭＤ命令がない演算が，抽出するループ内に含まれていてもかまわないものとし，単純に，論理的にベクトル化可能なループはすべてベクトル化可能なループであるとみなして処理する。
【００１９】
ベクトル演算展開部１３は，ベクトル化部１２でベクトル化処理がほどこされた中間プログラムに対し，ＳＩＭＤ化不可部分（対応するＳＩＭＤ命令がない演算部分）の展開，アンローリング展開，または，最適なベクトル長の選択などの処理をほどこす。命令スケジューリング部１４は，ベクトル演算展開部１３の処理がほどこされた中間プログラムを最適化する。コード生成部１５は，命令スケジューリング部１４で最適化された中間プログラムを解析し，オブジェクトプログラム３０を作成する。
【００２０】
以下では，オブジェクトプログラム３０を動作させるターゲットマシンがＳＩＭＤ機構を持つ場合を実施の形態１，ＳＩＭＤ機構を持たない場合を実施の形態２として，特に本発明に関係するベクトル化部１２，ベクトル演算展開部１３の処理を中心に説明する。なお，以下で説明する図２に示すベクトル化部１２の処理は，実施の形態１も実施の形態２も同様である。ベクトル演算展開部１３は，実施の形態１の場合，図３に示す処理を行い，実施の形態２の場合，図５に示す処理を行う。
【００２１】
〔実施の形態１〕
実施の形態１は，オブジェクトプログラム３０のターゲットマシンがＳＩＭＤ機構を装備している場合の例である。ただし，ターゲットマシンは，必ずしもすべての演算命令についてのＳＩＭＤ機構を備えている必要はない。
【００２２】
実施の形態１では，ベクトル化部１２でＳＩＭＤ命令として表現できない部分を擬似的にベクトル化可能であるとしてベクトル化し，その部分をベクトル演算展開部１３で局所的に逐次演算命令に置き換える。このため，ＳＩＭＤ命令とスカラ命令とを並列実行することができ，オーバヘッドを削減することが可能となる。
【００２３】
図２は，本実施の形態１におけるベクトル化処理フローチャートである。ベクトル化部１２は，ソースプログラム解析部１１から受け取った中間プログラムからループを順に１つ抽出し（ステップＳ１），ベクトル化可能であるかを判定し（ステップＳ２），可能でないと判定されればステップＳ４の処理に進む。ここで，ステップＳ２の処理では，ループ内に対応するＳＩＭＤ命令がない演算が含まれているかどうかは問わず，論理的にベクトル化可能なループであるかどうかだけを判断する。例えば，変数の値の定義，参照の依存関係により，並列に演算できない命令があれば，ベクトル化不可能と判断する。
【００２４】
ステップＳ２の処理において可能であると判定された場合，そのループに対してベクトル化処理を実行する（ステップＳ３）。抽出されたループが中間プログラムの中で最後のループであるかどうかを判定し（ステップＳ４），最後のループでなければステップＳ１の処理に戻り，最後のループであれば処理を終了する。
【００２５】
図３は，本実施の形態１におけるベクトル演算展開処理フローチャートである。ベクトル演算展開部１３において，まず，ベクトル化部１２でベクトル化処理がほどこされたプログラムからループを順に１つ抽出し（ステップＳ１０），その抽出されたループが，ベクトル化部１２においてベクトル化されたループかどうかを判定し（ステップＳ１１），ベクトル化されたループでなければステップＳ１８の処理に進む。
【００２６】
ステップＳ１１の処理においてベクトル化されたループと判定された場合，ＳＩＭＤ命令に対応したベクトル長を選択して決定し（ステップＳ１２），抽出されたループからテキストを順に１つ抽出する（ステップＳ１３）。その抽出されたテキストに対応するＳＩＭＤ命令が，ターゲットマシンにあるかどうかを判定し（ステップＳ１４），対応する命令があればステップＳ１７の処理に進む。
【００２７】
ステップＳ１４の処理において対応する命令がないと判定された場合，抽出されたテキストのベクトル命令を逐次命令に変換し（ステップＳ１５），ステップＳ１２の処理で決定されたベクトル長要素分の逐次命令展開を行う（ステップＳ１６）。ここで，ステップＳ１５の処理では，例えば，ＶＬＯＡＤというベクトル命令をＬＯＡＤという逐次命令に変換する。また，ステップＳ１６の処理では，例えばベクトル長が２と決定されている場合，１要素目のＬＯＡＤ，２要素目のＬＯＡＤといったように，ベクトル長要素分だけ逐次命令を並べる。
【００２８】
抽出されたテキストが抽出されたループ内で最後のテキストであるかどうかを判定し（ステップＳ１７），最後のテキストでなければステップＳ１３の処理に戻る。ステップＳ１７の処理において最後のテキストであると判定された場合，抽出されたループがプログラムの中で最後のループであるかどうかを判定し（ステップＳ１８），最後のループでなければステップＳ１０の処理に戻り，同様に処理を繰り返し，最後のループであれば処理を終了する。
【００２９】
図４は，従来の部分ベクトル化と本実施の形態１のベクトル化との違いを比較して説明する図である。図４（Ａ）に示す配列の演算において，ａ（ｉ）＝ｂ（ｉ）／ａ（ｉ）の演算は，ターゲットマシンに除算のＳＩＭＤ命令がないため，ＳＩＭＤ命令として表現できない部分であり，ｃ（ｉ）＝ｂ（ｉ）＋ａ（ｉ）の演算は，ＳＩＭＤ命令として表現できる部分であるとする。
【００３０】
図４（Ｂ）は，図４（Ａ）の演算を，従来の方法により部分ベクトル化した例である。従来は，ベクトル化可能な部分（ＳＩＭＤ命令として表現できる部分）と不可能な部分（ＳＩＭＤ命令として表現できない部分）を分割していた。図４（Ｂ）の例では，ベクトル化不可能な除算部分は逐次ループで処理しており，ベクトル化可能な加算部分はベクトル化ループで分けて処理している。
【００３１】
図４（Ｃ）は，図４（Ａ）の演算を本実施の形態１の方法によりベクトル長をｎ＋１としてベクトル化した例を，中間言語イメージで示している。図中，ｖｔｄは，ベクトルテンポラリ領域（要素の長さ分のデータを一時的に保持するレジスタまたは領域）である。
【００３２】
本実施の形態１の方法では，ＳＩＭＤ命令として表現できない部分である図４（Ａ）のａ（ｉ）＝ｂ（ｉ）／ａ（ｉ）の配列演算部分の中でも，特にベクトル化不可能である除算部分のみを逐次命令展開し，メモリロードやメモリストアなどのベクトル化可能な部分に関してはベクトル命令（ＳＩＭＤ命令）によって実行する。また，逐次命令展開部分もベクトル長分の展開を行うためベクトル命令部分と合わせて１つのループとすることが可能である。図４（Ｃ）の例では，ベクトル長がｎ＋１であるので，逐次命令展開部分もｎ＋１並列で展開されている。
【００３３】
よって，本実施の形態１の方法では，従来の部分ベクトル化と異なり，除算と加算の２つの演算が１つのループ内に収まるので，オーバヘッドが軽減される。
【００３４】
〔実施の形態２〕
本実施の形態２は，ターゲットマシンがＳＩＭＤ機構を装備していない場合の実施形態である。ターゲットマシンがＳＩＭＤ機構を装備していない場合には，従来のコンパイラでは，ベクトル化処理は一切考慮されなかったが，本実施の形態２では，ベクトル化部１２において論理的にベクトル化可能である部分をすべて擬似的にベクトル化し，そのベクトル化部分をベクトル演算展開部１３で逐次演算命令に展開することを行う。
【００３５】
すなわち，本実施の形態２では，ＳＩＭＤ機構を装備しないハードウェアにおいて，擬似的にベクトル化されたループに対してベクトル演算１つを局所的に展開することにより，演算アンローリングの手法を用いて逐次演算に展開する。この結果，ループの演算レイテンシの隠蔽が実現された命令列の生成が行われることになる。後段の命令スケジューリング部１４においても，演算レイテンシの隠蔽を考慮した最適化が可能であるが，特に本実施の形態２によれば，ループの演算レイテンシの隠蔽を効率よく行うことが可能になる。
【００３６】
ここで，ループの演算レイテンシの隠蔽とは，メモリアクセス命令とそのオペランドを使用する演算，または，演算とその演算の結果を直接参照する演算同士が連続すると遅れが出るため，両者を離すこと（依存性のない命令を間に挟むこと）により命令同士の依存性をなくし，待ちを発生させないで実行性能を改善することをいう。
【００３７】
実施の形態２におけるベクトル化部１２の処理は，実施の形態１と同様である。ベクトル演算展開部１３の処理が実施の形態１と実施の形態２とで異なる。
【００３８】
図５は，本実施の形態２におけるベクトル演算展開処理フローチャートである。ベクトル演算展開部１３において，まず，ベクトル化部１２でベクトル化処理がほどこされたプログラムからループを順に一つ抽出し（ステップＳ２０），その抽出されたループが，ベクトル化部１２においてベクトル化されたループかどうかを判定し（ステップＳ２１），ベクトル化されていなければステップＳ２７の処理に進む。
【００３９】
ステップＳ２１の処理においてベクトル化されたループと判定された場合，ＳＩＭＤ命令に対応したベクトル長を選択してベクトル長を決定する（ステップＳ２２）。次に，抽出されたループからテキストを順に１つ抽出する（ステップＳ２３）。抽出されたテキストのベクトル命令を，ステップＳ２２の処理で決定されたベクトル長要素分のアンローリング展開をし（ステップＳ２４），ベクトル命令を逐次命令に変換する（ステップＳ２５）。ここで，ステップＳ２４の処理では，例えばベクトル長が２と決定されている場合，１要素目のＶＬＯＡＤ，２要素目のＶＬＯＡＤといったように，ベクトル長要素分だけ命令を展開する。また，ステップＳ２５の処理では，例えば，ＶＬＯＡＤというベクトル命令をＬＯＡＤという逐次命令に変換する。
【００４０】
抽出されたテキストが抽出されたループ内で最後のテキストであるかどうかを判定し（ステップＳ２６），最後のテキストでなければステップＳ２３の処理に戻る。ステップＳ２６の処理において最後のテキストであると判定された場合，抽出されたループがプログラムの中で最後のループであるかどうかを判定し（ステップＳ２７），最後のループでなければステップＳ２０の処理に戻り，最後のループであれば処理を終了する。
【００４１】
図６は，従来のアンローリング展開と本実施の形態２のアンローリング展開との違いを比較して説明する図である。図６（Ａ）のプログラムで示す配列の演算に関して，従来の手法と本実施の形態２の手法とを比較する。図中，ｔｍｐはテンポラリ領域（一時的にデータを保持する領域）である。
【００４２】
図６（Ｂ）は，従来の手法で図６（Ａ）を２重のアンローリング展開した例である。また，図６（Ｃ）は，図６（Ｂ）の命令展開イメージである。従来のアンローリング展開では，メモリアクセス命令とそのオペランドを使用する演算，または，演算とその演算の結果を直接参照する演算同士が連続するため，命令実行時に命令毎の待ちが発生する。図６（Ｃ）において枠で囲まれたｔｍｐが連続して使用されているテンポラリ領域である。
【００４３】
図６（Ｄ）は，本実施の形態２の手法により図６（Ａ）をベクトル長２でベクトル化した例である。また，図６（Ｅ）は，図６（Ｄ）の命令展開イメージである。本実施の形態２のアンローリング展開では，まず演算を擬似的にベクトル化し，メモリアクセス命令ごと，オペランドを使用する演算ごとにまとめてアンローリング展開するため，依存性のある命令同士が自動的に離れることになる。よって，本実施の形態２の手法では，命令同士の依存性がなくなるため待ちが発生しなくなり，演算レイテンシの隠蔽が可能となる。
【００４４】
〔実施の形態３〕
本実施の形態３として，ループ中にＩＦ文等の条件文が含まれる場合に，ＳＩＭＤ化が可能な条件をループ内部で判定することによりベクトル化を行う実施形態を説明する。例えば，ループ中にＩＦ文が存在する場合，ＩＦ文で制御される部分は条件によって実行されたり，されなかったりする。ＳＩＭＤ命令は連続した要素を処理する命令であるため，従来は，ＳＩＭＤ機構向けのコンパイラにおいてＩＦ文等の条件文のベクトル化が不可能であった。
【００４５】
図７は，本実施の形態３によるベクトル化を説明する図である。図７（Ａ）はＩＦ文を含むループのプログラム例である。図７（Ａ）のプログラムをベクトル長２で連続２要素の処理としたものの展開イメージが，図７（Ｂ）のプログラム例である。図７（Ｂ）において，連続する２要素が共に“真”の場合のみＳＩＭＤ命令で対応することができる。
【００４６】
図７（Ｂ）のプログラムの処理を簡単に説明すると，まず最初の要素が“偽”ではなく（“真”である），２要素目も“偽”ではない（“真”である）場合，２つの要素に対してＳＩＭＤ命令で対応する。最初の要素が“真”であり，２要素目が“偽”である場合，最初の要素の逐次展開処理を行う。最初の要素が“偽”であり，２要素目が“真”である場合，２要素目の逐次展開処理を行う。最初の要素が“偽”であり，２要素目も“偽”である場合，どちらの要素も処理を行わない。
【００４７】
〔実施の形態４〕
本実施の形態４として，ベクトル長を外部から指示する手段を持つ場合の例を説明する。本実施の形態４では，ベクトル長をユーザが指定することができる。一般にベクトル長は長いほど並列効率が良くなるが，弊害として使用レジスタが足りなくなる場合がある。本実施の形態４では，ユーザが最適と思われるベクトル長を指定することにより，より実行効率を改善することができる。例えば，ベクトル長を外部から指示させるために，ソースプログラムに対してコンパイラ起動時のパラメータによるオプションの指定手段と解析手段とを設ける。または，ソースプログラムもしくはループに対してベクトル長をユーザが指示するためのソースプログラム中に記述可能な文（最適化制御行）を用意する。
【００４８】
【実施例】
以下，本発明の実施例を図面を用いて説明する。
【００４９】
〔実施例１〕
実施例１は，ＳＩＭＤ機構は装備されているが，ループ中の一部の演算が対象ハードウェア上でＳＩＭＤ表現できない場合の例である。
【００５０】
図８は，本実施例１におけるベクトル演算展開の中間言語イメージの例を示す。図中，ＳＴＤは通常のテンポラリ領域を示し，ＶＴＤはベクトルテンポラリ領域を示す。図８（Ａ）は，ソースプログラムの例である。図８（Ａ）のソースプログラムは，ソースプログラム解析部１１で解析され，その後，ベクトル化部１２でベクトル化処理がほどこされる。
【００５１】
図８（Ｂ）は，図８（Ａ）のソースプログラムを解析し，ベクトル化処理がほどこされた後の中間プログラムの例である。図８（Ｂ）の処理の例では，ベクトル化部１２でベクトル長が決定されている。処理▲１▼ではベクトル長が４と決定されており，以降ベクトル処理は４要素ずつ行われる。処理▲２▼では配列要素ｌｉｓｔをベクトルテンポラリ領域ＶＴＤ１にロードし，処理▲３▼では配列要素ｃをベクトルテンポラリ領域ＶＴＤ２にロードし，処理▲４▼では処理▲２▼の結果にしたがって配列要素ｂをベクトルテンポラリ領域ＶＴＤ３にロードする。処理▲５▼では４要素分のベクトル演算による加算を行い，ベクトルテンポラリ領域ＶＴＤ４に格納し，処理▲６▼では演算結果のベクトルテンポラリ領域ＶＴＤ４の値を配列要素ａにストアする。
【００５２】
しかし，処理▲４▼において配列要素ｂは連続する要素ではなく配列要素ｌｉｓｔに依存する要素であるので，処理▲４▼に対応するＳＩＭＤ命令は存在しない。よって，このままではプログラムが実行不可能である。そこで，ベクトル演算展開部１３により，ベクトル化不可能な部分の逐次命令展開を行う。
【００５３】
図８（Ｃ）は，図８（Ｂ）の中間プログラムにベクトル演算展開処理をほどこした中間プログラムの例である。ＳＩＭＤ命令で表現できない処理▲４▼に関して，それに付随する処理▲２▼をも含めてテンポラリ領域（ＳＴＤ）を用いてベクトル長要素分（ここでは４要素分）の逐次命令展開を行い，その逐次演算結果をベクトルテンポラリ領域（ＶＴＤ）に転送し，ベクトル演算処理を行っている。
【００５４】
〔実施例２〕
実施例２は，対象ハードウェア上にＳＩＭＤ機構を持たない場合の擬似ベクトル化処理の例である。
【００５５】
図９は，本実施例２におけるベクトル演算展開の中間言語イメージの例を示す。図中，ＳＴＤは通常のテンポラリ領域を示し，ＶＴＤはベクトルテンポラリ領域を示す。図９（Ａ）は，ソースプログラムの例である。図９（Ａ）のソースプログラムは，ソースプログラム解析部１１で解析された後，ベクトル化部１２でベクトル化処理がほどこされる。
【００５６】
図９（Ｂ）は，図９（Ａ）のソースプログラムを解析し，ベクトル化処理がほどこされた中間プログラムの例である。この図９（Ｂ）の例では，ベクトル化部１２でベクトル長が決定されている。処理▲１▼ではベクトル長が４と決定されており，以降ベクトル処理は４要素ずつ行われる。処理▲２▼では配列要素ｃをベクトルテンポラリ領域ＶＴＤ１にロードし，処理▲３▼では配列要素ｂをベクトルテンポラリ領域ＶＴＤ２にロードする。処理▲４▼では４要素分のベクトル演算による加算を行い，演算結果をベクトルテンポラリ領域ＶＴＤ３に格納し，処理▲５▼では演算結果のベクトルテンポラリ領域ＶＴＤ３の値を配列要素ａにストアする。
【００５７】
しかし，図９（Ｂ）では，プログラムが擬似的にベクトル化されているだけであるので，ＳＩＭＤ機構を持たないハードウェア上ではプログラムが実行不可能である。そこで，ベクトル演算展開部１３で逐次命令展開を行う。
【００５８】
図９（Ｃ）は，図９（Ｂ）の中間プログラムにベクトル演算展開処理をほどこした中間プログラムの例である。図９（Ｂ）のベクトル命令ごとにアンローリング展開（ベクトル長は４と決定されているので，４並列のアンローリング展開）して逐次命令に変換している。ベクトル化部１２によりベクトル化した命令列をもとに展開しているため，同じテンポラリ領域（ＳＴＤ）が連続して使用されないように命令が配列されている。
【００５９】
〔実施例３〕
実施例３は，ループ中にＩＦ文を含み，ベクトル化処理としてマスク処理を実施する場合の例である。この例では，ターゲットマシンは，ＳＩＭＤ機構を装備していないものとする。ＳＩＭＤ機構を装備しているターゲットマシンの場合にも，ベクトル演算展開処理の部分を除き，同様に処理される。
【００６０】
図１０および図１１は，本実施例３におけるベクトル化処理後およびベクトル演算展開の中間言語イメージの例を示す。図中，ＳＴＤは通常のテンポラリ領域を示し，ＶＴＤはベクトルテンポラリ領域を示す。図１０（Ａ）は，ソースプログラムの例である。図１０（Ａ）のソースプログラムは，ソースプログラム解析部１１で解析された後，ベクトル化部１２でベクトル化処理がほどこされる。
【００６１】
図１０（Ｂ）は，図１０（Ａ）のソースプログラムを解析し，ベクトル化処理がほどこされたの中間プログラムの例である。この図１０（Ｂ）の例では，ベクトル化部１２でベクトル長が決定されている。処理▲１▼ではベクトル長が２と決定されており，以降ベクトル処理は２要素ずつ実行される。処理▲２▼では配列要素ｍをベクトルテンポラリ領域ＶＴＤ１にロードし，処理▲３▼では処理▲２▼でロードした配列要素ｍの中で“５．０”以上の要素のマスクをベクトルテンポラリ領域ＶＴＤ２に生成する。処理▲４▼では配列要素ｂをベクトルテンポラリ領域ＶＴＤ４にロードし，処理▲５▼では配列要素ｃをベクトルテンポラリ領域ＶＴＤ５にロードする。処理▲６▼では処理▲３▼で生成されたＶＴＤ２のマスク要素に対応するＶＴＤ４およびＶＴＤ５の加算を行い，演算結果をベクトルテンポラリ領域ＶＴＤ６に格納する。処理▲７▼では処理▲３▼で生成されたマスク要素の演算結果を配列要素ａにストアする。
【００６２】
以上のように，図１０（Ｂ）において，処理▲３▼では“５．０”以上の配列ｍの要素のマスクを生成し，処理▲６▼および▲７▼においてマスク要素のみの処理を行うように記述されている。しかし，図１０（Ｂ）のようなベクトル処理の記述では実際にはプログラムが実行不可能であるので，ベクトル演算展開部１３により，逐次命令展開を行う。
【００６３】
図１１は，図１０（Ｂ）の中間プログラムにベクトル演算展開処理をほどこした中間プログラムの例である。図１１では，図１０（Ｂ）の処理▲１▼でベクトル長が２と決定されているので，配列ｍの連続する２要素の“真”と“偽”の組合せごとに展開されている。連続する２要素が“真”である場合のみ，２連続で演算処理が実行される。どちらか一方が“真”である場合には，“真”である方の要素のみ演算処理が実行される。連続する２要素が“偽”である場合には，演算処理は実行されない。
【００６４】
〔実施例４〕
実施例４は，ベクトル長を外部から指示する（ユーザが指示する）手段を持つ場合の例である。
【００６５】
図１２は，本実施例４における中間言語イメージの例を示す図である。図中，ＳＴＤは通常のテンポラリ領域を示し，ＶＴＤはベクトルテンポラリ領域を示す。図１２（Ａ）は，ソースプログラムの例である。図１２（Ａ）に示すように，外部からベクトル長（図１２ではベクトル長は４）を指示する文（最適化制御行）がソースプログラムに記述されている。図１２（Ａ）のソースプログラムは，ソースプログラム解析部１１で解析された後，ベクトル化部１２でベクトル化処理がほどこされる。
【００６６】
図１２（Ｂ）は，図１２（Ａ）のソースプログラムを解析し，ベクトル化処理がほどこされた中間プログラムの例である。処理▲１▼では図１２（Ａ）の指示からベクトル長が４と決定されており，以降ベクトル処理は４要素ずつ行われる。処理▲２▼では配列要素ｃをベクトルテンポラリ領域ＶＴＤ１にロードし，処理▲３▼では配列要素ｂをベクトルテンポラリ領域ＶＴＤ２にロードする。処理▲４▼では４要素分のベクトル演算を行い，処理▲５▼では演算結果を配列要素ａにストアする。
【００６７】
しかし，図１２（Ｂ）では，プログラムが擬似的にベクトル化されているだけであるので，例えば，ハードウェアがＳＩＭＤ機構を持たない場合などには，プログラムが実行不可能である。そこで，ベクトル演算展開部１３で逐次命令展開を行う。
【００６８】
図１２（Ｃ）は，図１２（Ｂ）の中間プログラムにベクトル演算展開処理をほどこした中間プログラムの例である。図１２（Ｂ）のベクトル命令ごとにアンローリング展開（ベクトル長は４と決定されているので，４並列のアンローリング展開）して逐次命令に変換している。ベクトル化部１２によりベクトル化した命令列をもとに展開しているため，同じテンポラリ領域（ＳＴＤ）が連続して使用されないように命令が配列されている。
【００６９】
本実施の形態１〜４および本実施例１〜４の特徴を列挙すると以下のとおりである。
【００７０】
（付記１） ＳＩＭＤ機構が装備されているコンピュータ上で動作させるプログラムをコンパイルするコンパイラプログラムにおいて，
ソースプログラムを入力して解析する処理と，
ソースプログラムの解析結果について，ループ中の一部の演算が前記コンピュータ上でＳＩＭＤ命令として表現できない場合に，その部分を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理と，
前記ベクトル化可能なループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理とを，
コンピュータに実行させるためのプログラムを含む
ことを特徴とするコンパイラプログラム。
【００７１】
（付記２） ＳＩＭＤ機構が装備されていないコンピュータ上で動作させるプログラムをコンパイルするコンパイラプログラムにおいて，
ソースプログラムを入力して解析する処理と，
ソースプログラムの解析結果について，前記コンピュータがＳＩＭＤ機構を持つものとして，ループ中の演算を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理と，
前記ベクトル化可能なループとしたループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理とを，
コンピュータに実行させるためのプログラムを含む
ことを特徴とするコンパイラプログラム。
【００７２】
（付記３） 付記１または付記２に記載のコンパイラプログラムにおいて，
前記ベクトル化処理における処理対象ループが条件判定によって実行するかしないかが決定される演算を含む場合に，前記条件判定結果に応じてマスク処理する命令表現を出力することにより，そのループをベクトル化可能なループとするベクトル化処理を，
コンピュータに実行させるプログラムを含む
ことを特徴とするコンパイラプログラム。
【００７３】
（付記４） 付記１から付記３までのいずれかに記載のコンパイラプログラムにおいて，
前記ベクトル化処理または前記ベクトル演算展開処理では，外部からの指示によりベクトル長を決定する
ことを特徴とするコンパイラプログラム。
【００７４】
（付記５） ＳＩＭＤ機構が装備されているコンピュータ上で動作させるプログラムをコンパイルするコンパイラプログラムの記録媒体であって，
ソースプログラムを入力して解析する処理と，
ソースプログラムの解析結果について，ループ中の一部の演算が前記コンピュータ上でＳＩＭＤ命令として表現できない場合に，その部分を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理と，
前記ベクトル化可能なループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理とを，
コンピュータに実行させるためのプログラムを記録した
ことを特徴とするコンパイラプログラムの記録媒体。
【００７５】
（付記６） ＳＩＭＤ機構が装備されていないコンピュータ上で動作させるプログラムをコンパイルするコンパイラプログラムの記録媒体であって，
ソースプログラムを入力して解析する処理と，
ソースプログラムの解析結果について，前記コンピュータがＳＩＭＤ機構を持つものとして，ループ中の演算を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理と，
前記ベクトル化可能なループとしたループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理とを，
コンピュータに実行させるためのプログラムを記録した
ことを特徴とするコンパイラプログラムの記録媒体。
【００７６】
（付記７） ＳＩＭＤ機構が装備されているコンピュータ上で動作させるプログラムをコンパイルするコンパイル処理方法において，
ソースプログラムを入力して解析する処理過程と，
ソースプログラムの解析結果について，ループ中の一部の演算が前記コンピュータ上でＳＩＭＤ命令として表現できない場合に，その部分を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理過程と，
前記ベクトル化可能なループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理過程と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理過程とを有する
ことを特徴とするコンパイル処理方法。
【００７７】
（付記８） ＳＩＭＤ機構が装備されていないコンピュータ上で動作させるプログラムをコンパイルするコンパイル処理方法において，
ソースプログラムを入力して解析する処理過程と，
ソースプログラムの解析結果について，前記コンピュータがＳＩＭＤ機構を持つものとして，ループ中の演算を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理過程と，
前記ベクトル化可能なループとしたループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理過程と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理過程とを有する
ことを特徴とするコンパイル処理方法。
【００７８】
（付記９） ＳＩＭＤ機構が装備されているコンピュータ上で動作させるプログラムをコンパイルするコンパイル処理装置において，
ソースプログラムを入力して解析する処理手段と，
ソースプログラムの解析結果について，ループ中の一部の演算が前記コンピュータ上でＳＩＭＤ命令として表現できない場合に，その部分を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理手段と，
前記ベクトル化可能なループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理手段と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理手段とを備える
ことを特徴とするコンパイル処理装置。
【００７９】
（付記１０） ＳＩＭＤ機構が装備されていないコンピュータ上で動作させるプログラムをコンパイルするコンパイル処理装置において，
ソースプログラムを入力して解析する処理手段と，
ソースプログラムの解析結果について，前記コンピュータがＳＩＭＤ機構を持つものとして，ループ中の演算を疑似的にＳＩＭＤ命令表現することにより，そのループをベクトル化可能なループとするベクトル化処理手段と，
前記ベクトル化可能なループとしたループについて前記疑似的にＳＩＭＤ命令表現された演算部分をループ内で逐次命令に置き換えて展開するベクトル演算展開処理手段と，
前記ベクトル演算展開処理の結果をもとにオブジェクトプログラムを生成する処理手段とを備える
ことを特徴とするコンパイル処理装置。
【００８０】
【発明の効果】
以上説明したように，本発明により，ＳＩＭＤ機能を持たない，またはＳＩＭＤ表現ができないループに対して擬似的なベクトル演算の表現を使うことにより，ベクトル化可能なループとして扱い，そのループ内のテキストをＳＩＭＤ命令の有無に応じて命令展開することにより，より実行性能が向上されたオブジェクトプログラムを生成することができるようになる。
【００８１】
また，ターゲットマシンがＳＩＭＤ機構を装備する場合のコンパイラと，ＳＩＭＤ機構を装備しない場合のコンパイラとで，ベクトル化処理の考慮により処理を共通化できる部分が多くなるので，コンパイラ開発の工程を短縮することが可能になり，各種のターゲットマシンに応じたコンパイラの開発が容易になる。
【図面の簡単な説明】
【図１】本発明におけるシステムの構成例を示す図である。
【図２】本実施の形態１におけるベクトル化処理フローチャートである。
【図３】本実施の形態１におけるベクトル演算展開処理フローチャートである。
【図４】従来の部分ベクトル化と本実施の形態１のベクトル化との違いを比較して説明する図である。
【図５】本実施の形態２におけるベクトル演算展開処理フローチャートである。
【図６】従来のアンローリング展開と本実施の形態２のアンローリング展開との違いを比較して説明する図である。
【図７】本実施の形態３によるベクトル化を説明する図である。
【図８】本実施例１におけるベクトル演算展開の中間言語イメージの例を示す図である。
【図９】本実施例２におけるベクトル演算展開の中間言語イメージの例を示す図である。
【図１０】本実施例３におけるベクトル化処理後の中間言語イメージの例を示す図である。
【図１１】本実施例３におけるベクトル演算展開の中間言語イメージの例を示す図である。
【図１２】本実施例４におけるベクトル演算展開の中間言語イメージの例を示す図である。
【図１３】従来技術における部分ベクトル化の例を示す図である。
【符号の説明】
１ データ処理装置（ＣＰＵ／メモリ）
１０ コンパイラ
１１ ソースプログラム解析部
１２ ベクトル化部
１３ ベクトル演算展開部
１４ 命令スケジューリング部
１５ コード生成部
２０ ソースプログラム
３０ オブジェクトプログラム

Claims (5)

1. 複数の演算装置にそれぞれ個々に与えたデータに対して同一の命令を並列実行させるＳＩＭＤ機構が装備されている第１のコンピュータ上で動作させるプログラムをコンパイルする処理を，第２のコンピュータに実行させるためのコンパイラプログラムであって，
   前記第２のコンピュータを，
   入力されたソースプログラムを解析し，中間言語で記述されたテキストを作成するソースプログラム解析手段と，
   前記ソースプログラム解析手段から中間言語で記述されたテキストを受け取り，ループ中の一部の演算が前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できない場合であっても，論理的にベクトル化可能なループはすべてベクトル化可能なループであるとみなして，その部分をＳＩＭＤ命令表現の中間言語で記述されたテキストに変換するベクトル化処理を行うベクトル化手段と，
   前記ベクトル化手段により変換されたＳＩＭＤ命令表現の中間言語で記述されたテキスト部分について，前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できる場合には，その中間言語テキスト部分をＳＩＭＤ命令に置き換え，前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できない場合には，その中間言語テキスト部分を，前記ベクトル化手段におけるベクトル化処理で用いられたベクトル長要素分の逐次命令の並びに置き換えて展開するベクトル演算展開手段と，
   前記ベクトル演算展開手段により展開された結果をもとにオブジェクトプログラムを生成する手段として，
   機能させるためのコンパイラプログラム。
2. 複数の演算装置にそれぞれ個々に与えたデータに対して同一の命令を並列実行させるＳＩＭＤ機構が装備されていない第１のコンピュータ上で動作させるプログラムをコンパイルする処理を，第２のコンピュータに実行させるためのコンパイラプログラムであって，
   前記第２のコンピュータを，
   入力されたソースプログラムを解析し，中間言語で記述されたテキストを作成するソースプログラム解析手段と，
   前記ソースプログラム解析手段から中間言語で記述されたテキストを受け取り，前記第１のコンピュータがＳＩＭＤ機構を持つものと仮定した場合に論理的にベクトル化可能なすべてのループの部分をＳＩＭＤ命令表現の中間言語で記述されたテキストに変換するベクトル化処理を行うベクトル化手段と，
   前記ベクトル化手段により変換されたＳＩＭＤ命令表現の中間言語で記述されたテキスト部分について，メモリアクセス命令ごと，オペランドを使用する演算ごとにまとめて前記ベクトル化手段におけるベクトル化処理で用いられたベクトル長要素分の逐次命令の並びに置き換えて展開するベクトル演算展開手段と，
   前記ベクトル演算展開手段により展開された結果をもとにオブジェクトプログラムを生成する手段として，
   機能させるためのコンパイラプログラム。
3. 請求項１または請求項２に記載のコンパイラプログラムにおいて，
   前記ベクトル化手段におけるベクトル化処理は，処理対象ループが条件判定によって実行するかしないかが決定される演算を含む場合に，前記条件判定の結果に応じてマスク処理する命令表現を出力することにより，そのループをベクトル化可能なループとするベクトル化処理を含む
   ことを特徴とするコンパイラプログラム。
4. 請求項１から請求項３までのいずれかに記載のコンパイラプログラムにおいて，
   前記ベクトル化手段または前記ベクトル演算展開手段は，外部からの指示によりベクトル長を決定する
   ことを特徴とするコンパイラプログラム。
5. 複数の演算装置にそれぞれ個々に与えたデータに対して同一の命令を並列実行させるＳＩＭＤ機構が装備されている第１のコンピュータ上で動作させるプログラムをコンパイルする，少なくともソースプログラム解析手段とベクトル化手段とベクトル演算展開手段とコード生成手段とを備える第２のコンピュータが実行するコンパイル処理方法であって，
   前記ソースプログラム解析手段が，入力されたソースプログラムを解析し，中間言語で記述されたテキストを作成する処理過程と，
   前記ベクトル化手段が，前記ソースプログラム解析手段から中間言語で記述されたテキストを受け取り，ループ中の一部の演算が前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できない場合であっても，論理的にベクトル化可能なループはすべてベクトル化可能なループであるとみなして，その部分をＳＩＭＤ命令表現の中間言語で記述されたテキストに変換するベクトル化処理を行う処理過程と，
   前記ベクトル演算展開手段が，前記ベクトル化手段により変換されたＳＩＭＤ命令表現の中間言語で記述されたテキスト部分について，前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できる場合には，その中間言語テキスト部分をＳＩＭＤ命令に置き換え，前記第１のコンピュータが実行可能なＳＩＭＤ命令として表現できない場合には，その中間言語テキスト部分を，メモリアクセス命令ごと，オペランドを使用する演算ごとにまとめて前記ベクトル化手段におけるベクトル化処理で用いられたベクトル長要素分の逐次命令の並びに置き換えて展開する処理過程と，
   前記コード生成手段が，前記ベクトル演算展開手段により展開された結果をもとにオブジェクトプログラムを生成する処理過程とを有する
   ことを特徴とするコンパイル処理方法。

Images