(57)【要約】【課題】データのプリフェッチを効率的に行うことを可能にしたプリフェッチ制御方法及びコンパイル装置を得る。【解決手段】コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、コンパイル時に判定したディスタンスが繰り返し毎に不変か否かを調べ、不変であり一定であった場合、そのディスタンスがキャッシュライン長以上の場合、プリフェッチ命令を生成し、コンパイル時に判定したディスタンスが繰り返し毎に不変でなく変動する場合、条件付きプリフェッチ命令を生成する（ステップ３０７、３０４、３０６、３０８）。【選択図】図３
2008071128.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置のプリフェッチ制御方法において、
前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、実行時にデータアクセスパターンの条件によって、プリフェッチを実行するか否かを切り替える分岐命令のオブジェクトコードを生成することを特徴とするプリフェッチ制御方法。
【請求項２】
ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置のプリフェッチ制御方法において、
前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、ユーザが指示文によって特定の箇所またはプログラム全体に対してプリフェッチを行う条件を明示することによって、実行時にプリフェッチを実行するか否かを切り替える分岐命令のオブジェクトコードを生成することを特徴とするプリフェッチ制御方法。
【請求項３】
ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置のプリフェッチ制御方法において、
前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、オブジェクトファイルを生成して前記情報システムシステムに一旦実行させ、実行結果としてのアクセスパターンのプロファイルを保持させ、再コンパイル時に、前記プロファイルを入力し、プリフェッチの実行の可否を決定することを特徴とするプリフェッチ制御方法。
【請求項４】
ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置において、
前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、実行時にデータアクセスパターンの条件によって、プリフェッチを実行するか否かを切り替える分岐命令のオブジェクトコードを生成することを特徴とするコンパイル装置。
【請求項５】
ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイルプログラムであって、
前記コンパイルプログラムは、プリフェッチ生成ステップを含み、該プリフェッチ生成ステップは、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、実行時にデータアクセスパターンの条件によって、プリフェッチを実行するか否かを切り替える分岐命令のオブジェクトコードを生成するステップを実行させることを特徴とするコンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリフェッチ制御方法及びコンパイル装置に係り、特に、情報処理システムで利用されるコンパイル装置がメモリからキャッシュへのデータのプリフェッチを効率的に行うことを可能にしたプリフェッチ制御方法及びコンパイル装置に関する。
【背景技術】
【０００２】
一般に、情報処理システムにおいて、主メモリの処理性能は、プロセッサの処理性能に比較して著しく低いため、プロセッサは、主メモリ上のデータのアクセスが終了するまでその処理が待ち状態になり、稼働率が低下してしまう。このようなプロセッサの稼働率の低下を防止するため、情報処理装置は、高速なデータアクセスが可能であるキャッシュメモリを実装し、データアクセス時間を短縮することができるように構成されている。しかし、キャッシュメモリは、高価であり、また、実装上、搭載することができるメモリ容量が限られることが多い。このため、キャッシュメモリは、プログラム上のデータの局所性を利用して性能の向上を図ることができるように利用されている。
【０００３】
一方、データのアクセスは、例えば、ループ内でのデータの配列に対して、要素１から要素１００までを順番にアクセスしたり、要素１から要素１００までを２つずつ飛びとびにアクセスしたり等の様々なパターンが存在する。このパターンのことをアクセスパターンと呼ぶ。
【０００４】
前述のアクセスパターンがキャッシュメモリのライン長内に収まっている場合、プロセッサは、常にキャッシュメモリを通してデータにアクセスすれば必要なデータを得ることができるため、主メモリを通してデータをアクセスする場合と比べて、高速に必要なデータを取得することができ、これにより、高速に処理の実行を行うことが可能になる。
【０００５】
前述したキャッシュメモリを利用する従来技術は、データのアクセスパターンがコンパイル時に確定している場合、プログラム上の意味を変更しない程度にアクセスパターンを変更したりして、データの局所性を向上させている（以下、アクセスパターン変更方式と呼ぶ）。しかし、大規模科学技術計算等を実行する場合、データアクセスパターンが複雑になり、コンパイル時に確定不可能なものも多く見られている。
【０００６】
また、前述したキャッシュメモリを利用する従来技術は、プリフェッチ機構の使用または抑止を指示する機能を有するのが一般的であるが、条件付でプリフェッチ命令の使用または抑止を指示する機能は備えられていない（以下、アクセスパターン指示方式と呼ぶ）。
【０００７】
なお、前述したデータの局所性を向上させるアクセスパターン変更方式の他に、参照の局所性が厳密な意味で保障されないプログラムであっても、キャッシュメモリによる性能向上効果を得ることができるキャッシュ制御に関する従来技術として、例えば、特許文献１等に記載された技術が知られている。
【特許文献１】特開２００２−２３６６１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前述したアクセスパターン変更方式による従来技術は、コンパイル時にアクセスパターンが確定可能な場合にのみ適用することが可能であり、アクセスパターンがコンパイル時に確定不可能な場合には適用することができないという問題点を有している。
【０００９】
また、アクセスパターン変更方式による従来技術は、アクセスパターンがコンパイル時に確定不可能な場合、ユーザがプリフェッチ機構を使用するか否かを指示することが可能であるが、入力データや実行プロセッサ数等の実行時のパラメータによっては、期待する性能向上が得られないという問題点を有している。
【００１０】
本発明の目的は、前述した従来技術の問題点、すなわち、アクセスパターンがコンパイル時に確定不可能である問題点と、ユーザが条件付でプリフェッチ機構を使用する手段が存在しないという問題点とを解決し、データのプリフェッチを効率的に行うことを可能にしたプリフェッチ制御方法及びコンパイル装置を提供することにある。
【課題を解決するための手段】
【００１１】
本発明によれば前記目的は、ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置のプリフェッチ制御方法において、前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、実行時にデータアクセスパターンの条件によって、プリフェッチを実行するか否かを切り替える分岐命令のオブジェクトコードを生成することにより達成される。
【００１２】
また、前記目的は、ソースプログラムをオブジェクトファイルにコンパイルして実行する情報処理システムで利用されるコンパイル装置のプリフェッチ制御方法において、前記コンパイル装置は、プリフェッチ生成部を含み、該プリフェッチ生成部は、コンパイル時に前記ソースプログラムのデータアクセスパターンが不明なプログラムに対して、オブジェクトファイルを生成して前記情報システムシステムに一旦実行させ、実行結果としてのアクセスパターンのプロファイルを保持させ、再コンパイル時に、前記プロファイルを入力し、プリフェッチの実行の可否を決定することにより達成される。
【発明の効果】
【００１３】
本発明によれば、コンパイル時にアクセスパターンを確定することが不可能なプログラムの実行時に、プリフェッチを実行するか否かを切り替えてプリフェッチ実行することができ、プログラムの実行性能を向上させることが可能になる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明によるプリフェッチ制御方法及びコンパイル装置の実施形態を図面により詳細に説明する。
【００１５】
図１は本発明の一実施形態によるプリフェッチ制御方法を適用したコンパイル装置の構成を示すブロック図、図２はコンパイル装置が構築される情報処理システムの構成を示すブロック図である。図１、図２において、１０１はソースファイル、１０２はコンパイル装置、１０３は構文解析部、１０４はアクセスパターン解析部、１０５はプリフェッチ生成部、１０６はオブジェクト生成部、１０７はオブジェクトファイル、１０８はアクセスパターンデータファイル、２０１は情報処理システム、２０２はプロセッサ、２０３はキャッシュメモリ、２０４はメインメモリ、２０５はハードディスクドライブである。
【００１６】
一般に、コンパイル装置は、高級言語で記述されたソースプログラムを、情報処理装置が実行可能なプログラムであるオブジェクトファイルに変換するために、プログラムの実行時に利用されるものであり、本発明の実施形態によるコンパイル装置１０２は、図１に示すように、ソースファイル１０１が入力され、ソースファイルを中間語や辞書等のコンパイラ内部表現に変換する構文解析部１０３と、データの要素長、アクセスするアドレス等のアクセスパターンを解析するアクセスパターン解析部１０４と、アクセスパターン解析部１０４からの情報を元にして、プリフェッチを使用するか、使用しないか、あるいは、一定の条件の下で使用するか、の３つのいずれかにするか決定するプリフェッチ生成部１０５と、ターゲットマシン上で実行可能なオブジェクトファイル１０７を生成するオブジェクト生成部１０６とにより構成される。
【００１７】
なお、後述するが、オブジェクトファイル１０７を実行した結果として得られたアクセスパターンデータは、アクセスパターンデータファイル１０８に格納されて、アクセスパターン解析部１０４により利用される。
【００１８】
前述したようなコンパイル装置が構築される情報処理システム２０１は、図２に示すように、それぞれがキャッシュメモリ２０３を有する１または複数のプロセッサ２０２と、メインメモリ２０４と、ハードディスクドライブ２０５とがバス等の通信路を介して接続されて構成されてる。そして、図１に示して説明したコンパイル装置１０２は、コンパイルプログラムとしてメインメモリ２０４に格納され、プロセッサ２０２により実行されることによりその機能が実現される。また、ハードディスクドライブ２０５内には、ソースファイル１０１、オブジェクトファイル１０７、アクセスパターンデータファイル１０８が格納される。
【００１９】
そして、図２に示す情報処理システム２０１のメインメモリ２０４上にコンパイルプログラムとして構築されている本発明の実施形態によるコンパイル装置１０２は、ハードディスクドライブ２０５に格納されているソースファイル１０１を入力し、コンパイルし、変換したオブジェクトファイル１０７をハードディスクドライブ２０５に出力する。また、オブジェクトファイル１０７の実行によって得られるアクセスパターンデータは、ハードディスクドライブ２０５内のアクセスパターンデータファイル１０８に出力される。
【００２０】
前述したコンパイル装置において生成したオブジェクトファイル１０７は、図２に示す情報処理システム２０１上で次のようにして実行される。すなわち、プロセッサ２０２は、オブジェクトファイル１０７のプログラムの実行に必要なデータをアクセスする際、キャッシュメモリ２０３上にアクセスするデータが存在しているか否かを調べ、存在している場合、そのデータを取得してプログラムを実行する。このように、キャッシュメモリ２０３上にアクセスするデータが存在している場合を、キャッシュヒットといい、キャッシュメモリ２０３からデータを高速アクセスすることが可能である。しかし、キャッシュメモリ２０３上にデータが存在しない場合、プログラム２０２は、メインメモリ２０４経由でデータをアクセスすることになる。このように、キャッシュメモリ２０３上にデータが存在しない場合を、キャッシュミスといい、キャッシュメモリ２０３からのデータアクセスと比較して、データをアクセスする時間が非常に多く必要とすることになる。
【００２１】
図４はコンパイル装置１０２のアクセスパターン解析部１０４が、コンパイラ管理テーブル４０２を使用してソースファイル１０１のソースプログラム４０１中のアクセスパターンを解析する例を説明する図である。
【００２２】
ソースプログラム４０１中でアクセスするデータは、アドレスa(i)とa(i+α) とのデータであるので、コンパイラ管理テーブル４０２の２つのレコード４０５、４０６のアドレス４０３の欄に、 a(i)とa(i+α)とをそれぞれ記録する。また、配列ａは、real*8（実数８バイト型）と宣言しているため、要素長が８バイトであると判断し、コンパイラ管理テーブル４０２の前述の各レコード４０５、４０６の要素長４０４の欄に８を格納する。また、ｉループにおいて、ｉ＝１のとき、実行時のメインメモリのイメージ４０７上に格納されている１つ目のアドレスa(1)のデータの配列参照点４０８と２つ目のアドレスa(1+α) のデータの配列参照点４０９との間のディスタンス４１０は、コンパイラ管理テーブル４０２のレコード４０５と４０６とのアドレス４０３がｉ＝１のときのアドレスの差であり、計算すると、{(1+α)-1}*要素長＝α*要素長となる。要素長は、コンパイラ管理テーブル４０２から８であることが判る。このディスタンス４１０が、キャッシュライン長より大きい場合、アドレスa(1)とa(1+α) との両方に対してそれぞれプリフェッチ命令を生成するとプログラム実行性能が向上するが、ディスタンス４１０が、キャッシュライン長より小さい場合は、アドレスa(1)とa(1+α) との両方に対してそれぞれプリフェッチ命令を生成すると、重なった部分に対して、冗長なプリフェッチ処理が行われることになる。本発明の実施形態では、このような冗長なプリフェッチを排除するため、一定のサイズ以上重なった場合、アドレスa(1+α) に対するプリフェッチ命令を実行しないコードを含むオブジェクトファイル１０７を生成することとしている。
【００２３】
このようなプリフェッチを実行するか否かを切り替える条件付プリフェッチ命令である分岐命令のオブジェクトコードを生成することにより、本発明の実施形態は、冗長なプリフェッチ処理を防止して、プログラムの処理性能の向上を図ることが可能となる。
【００２４】
図３はアクセスパターン解析部１０４がアクセスパターンを解析し、プロフェッチ生成部１０５がプリフェッチ命令または条件付プリフェッチ命令を生成する一連の処理動作を説明するフローチャートであり、次に、これについて説明する。ここでの処理動作は、ソースファイル１０１に記載されているソースプログラムの中の全ての箇所について行われる。
【００２５】
（１）処理が開始されると、プログラムの中に配列参照が存在するか否かを調べ、存在しない場合、プリフェッチ命令を生成せずに、ここでの処理を終了する（ステップ３０１、３０５）。
【００２６】
（２）ステップ３０１の判定で、配列参照が存在した場合、配列を繰り返して参照するか否かを調べ、繰り返して参照しない場合、プリフェッチ命令を生成せずに、ここでの処理を終了する（ステップ３０２、３０５）。
【００２７】
（３）ステップ３０２の判定で、配列を繰り返して参照する場合、ディスタンスが、ソースプログラムの中で定められている定数であるか否かを調べる（ステップ３０３）。
【００２８】
（４）ステップ３０３の判定で、ディスタンスが定数であった場合、ディスタンスがキャッシュライン長以上か否かを調べ、キャッシュライン長を越えていた場合、プリフェッチ命令を生成して、ここでの処理を終了する（ステップ３０４、３０６）。
【００２９】
（５）ステップ３０４の判定で、ディスタンスがキャッシュライン長以上でなかった場合、プリフェッチ命令を生成せずに、ここでの処理を終了する（ステップ３０５）。
【００３０】
（６）ステップ３０３の判定で、ディスタンスが定数でなかった場合、コンパイル時に判定したディスタンスが繰り返し毎に不変か否かを調べ、不変であり一定であった場合、ステップ３０４からの処理に戻って、プリフェッチ命令を生成するか否かを判定する処理からの処理を繰り返す（ステップ３０７）。
【００３１】
（７）ステップ３０７の判定で、コンパイル時に判定したディスタンスが繰り返し毎に不変でなく変動する場合、条件付きプリフェッチ命令を生成して、ここでの処理を終了する（ステップ３０８）。
【００３２】
図５は条件付プリフェッチ命令の生成例を、従来技術（従来方式）と本発明の実施形態（新方式）とを対比して説明する図である。
【００３３】
従来、ソースプログラム５０１を含むソースファイル１０１は、コンパイル装置１０２において、コードイメージ５０２を含むオブジェクトファイル１０７に変換されていた。これに対して、本発明の実施形態では、ソースプログラム５０１を含むソースファイル１０１は、コンパイル装置１０２のアクセスパターン解析部１０４において、コードイメージ５０５を含むオブジェクトファイル１０７に変換される。
【００３４】
従来のコードイメージ５０２の場合、ディスタンスがキャッシュライン長よりも小さい場合、アドレスa(i)に対するプリフェッチ命令５０３でキャッシュインしたデータを再び、アドレス a(i+α)に対するプリフェッチ命令５０４により再度キャッシュメモリに読み込むことになるため、プログラム実行効率が低下する。
【００３５】
これに対して本発明の実施形態でのコードイメージ５０５の場合、ディスタンスがキャッシュライン長以上の場合のみ、すなわち、５０７として示すように、if(α＞Ｌ)の場合のみ、アドレス a(i+α)に対するプリフェッチ命令５０８を生成して実行させることとする。このような方法を採用することにより、アドレスa(i)に対するプリフェッチ命令５０６で既にキャッシュインしたデータを再度キャッシュに取り込むような非効率な処理を防止することが可能になる。なお、前述のＬは、キャッシュメモリのライン長である。
【００３６】
図６はユーザがアクセスパターンを指示文によって、特定の箇所においてプリフェッチを実行するか否かの使用条件を明示する例を説明する図である。
【００３７】
ソースファイル１０１のソースプログラム６０１の中に指定した指示文６０２は、コンパイル装置１０２のアクセスパターン解析部１０４において、実際にプリフェッチ命令を生成するか否かを決める判定文として利用される。ソースプログラム６０１を含むソースファイル１０１は、プリフェッチ命令を生成するか否かを決める判定文として利用される指示文を含むことによって、オブジェクトコード６０３を含むオブジェクトファイル１０７に変換される。そして、オブジェクトコード６０３内のユーザが指示した指示文から生成されたif(α＞Ｌ)の判定文６０５が真の場合、アドレス a(i+α)に対するプリフェッチ命令６０６を実行するようにされる。
【００３８】
このような方法を用いることにより、アドレスa(i)に対するプリフェッチ命令６０４で既にキャッシュインしたデータを再度キャッシュに取り込むような非効率な処理を防止することが可能になる。なお、前述のＬは、キャッシュメモリのライン長である。
【００３９】
図７はオブジェクトファイルの実行時にアクセスパターンを記録し、プリフェッチを実行するか否かを決定する方法を説明する図である。
【００４０】
ソースプログラム７０１を含むソースファイル１０１は、コンパイル装置１０２において、オブジェクトファイル１（１０７−１）に変換される。オブジェクトファイル１（１０７−１）は、ソースプログラム７０１の中のディスタンスが不変で定数でない配列参照及び同一配列の参照に対して、コンパイルプログラム１０２のアクセスパターン解析部１０４において、アクセスパターンを外部ファイルのアクセスパターンデータファイル１０８に書き出す命令を含んでいる。作成したオブジェクトファイル１（１０７−１）を実行すると、図１に示すファイルアクセスパターンデータファイル１０８の中に、アクセスコードアドレス７０３とアクセスデータアドレス７０４とを記録するアクセスパターンテーブル７０２が作成される。アクセスコードアドレス７０３には、ソースプログラム７０１の中の配列を繰り返しアクセスするループのコードの先頭アドレスが格納され、アクセスデータアドレス７０４には、アクセスする配列の先頭アドレスが格納される。
【００４１】
再コンパイル時に、コンパイル装置１０２は、ソースプログラム７０１を含むソースファイル１０１及びアクセスパターンデータファイル１０８を読み込み、オブジェクトファイル２（１０７−２）に変換する。その際、コンパイル装置１０２のアクセスパターン解析部１０４は、同一アクセスコードアドレスのアクセスデータアドレス（７０５と７０６）の差から、ディスタンスを求め、求めたディスタンスがキャッシュライン長以上の場合、アドレスa(i)に対するプリフェッチ命令及びアドレス a(i+α)に対するプリフェッチ命令を生成し、求めたディスタンスがキャッシュライン長より小さい場合、アドレスa(i)に対するプリフェッチ命令のみを生成する。
【００４２】
図８はオブジェクトファイルの実行時にディスタンスからプリフェッチを行うか否かを決定する方法を説明する図である。
【００４３】
コンパイル装置１０２のアクセスパターン解析部１０４は、ソースファイル１０１のソースプログラム８０１の中のディスタンスが不変で定数でない配列参照に対して条件付プリフェッチ命令８０６に、同一の配列に対してプリフェッチ命令８０６に変換したコードイメージ８０４を含むオブジェクトファイル１０７を生成する。すなわち、ソースプログラム８０１内の８０２として示すアドレスa(i)と８０３として示すアドレス a(i+α)がディスタンスが不変で定数でない配列である場合、プリフェッチ命令８０６として、prefetch cond(a(i+α),α>Ｌ)を生成する。このプリフェッチ命令は、命令中のオペランドに指定したディスタンスがキャッシュライン長よりも大きい場合、アドレス a(i+α)に対するプリフェッチを実行させる命令である。
【００４４】
このような方法を用いることにより、アドレスa(i)に対するプリフェッチ命令８０５により既にキャッシュインしたデータを再度キャッシュに取り込むような非効率な処理を防止することが可能になる。なお、前述のＬは、キャッシュメモリのライン長である。
【００４５】
前述した本発明の実施形態での各処理は、プログラムにより構成し、情報処理システムが備えるプロセッサ上で実行することができ、また、それらのプログラムは、ＦＤ、ＣＤ、ＭＯ、ＤＶＤ等の記録媒体に格納して提供することができ、また、ネットワークを介してディジタル情報により提供することができる。
【００４６】
なお、前述で説明した本発明の実施形態は、ソースプログラムとしてＦＯＲＴＲＡＮ言語を用いる例であったが、本発明は、例えば、ソースプログラムとしてＣ言語等の任意のプログラミング言語が使用される場合にも適用することが可能である。
【図面の簡単な説明】
【００４７】
【図１】本発明の一実施形態によるプリフェッチ制御方法を適用したコンパイル装置の構成を示すブロック図である。
【図２】コンパイル装置が構築される情報処理システムの構成を示すブロック図である。
【図３】アクセスパターン解析部がアクセスパターンを解析し、プロフェッチ生成部がプリフェッチ命令または条件付プリフェッチ命令を生成する一連の処理動作を説明するフローチャートである。
【図４】コンパイル装置のアクセスパターン解析部が、コンパイラ管理テーブルを使用してソースファイルのソースプログラム中のアクセスパターンを解析する例を説明する図である。
【図５】条件付プリフェッチ命令の生成例を、従来技術と本発明の実施形態とを対比して説明する図である。
【図６】ユーザがアクセスパターンを指示文によって、特定の箇所においてプリフェッチを実行するか否かの使用条件を明示する例を説明する図である。
【図７】オブジェクトファイルの実行時にアクセスパターンを記録し、プリフェッチを実行するか否かを決定する方法を説明する図である。
【図８】オブジェクトファイルの実行時にディスタンスからプリフェッチを行うか否かを決定する方法を説明する図である。
【符号の説明】
【００４８】
１０１  ソースファイル
１０２  コンパイルプログラム
１０３  構文解析部
１０４  アクセスパターン解析部
１０５  プリフェッチ生成部
１０６  オブジェクト生成部
１０７  オブジェクトファイル
１０８  アクセスパターンデータファイル
２０１  情報処理システム
２０２  プロセッサ
２０３  キャッシュメモリ
２０４  メインメモリ
２０５  ハードディスクドライブ
【図１】
2008071128.tif 000003
【図２】
2008071128.tif 000004
【図３】
2008071128.tif 000005
【図４】
2008071128.tif 000006
【図５】
2008071128.tif 000007
【図６】
2008071128.tif 000008
【図７】
2008071128.tif 000009
【図８】
2008071128.tif 000010