JPH10320212A - キャッシュ向け最適化方法 - Google Patents

Abstract

(57)【要約】 【課題】正確なキャッシュミス率予測に基づくキャッシ
ュ向け最適化を行う。 【解決手段】ステップ２０２で、本コンパイルが第１段
階のコンパイルであるかを調べる。第１段階のコンパイ
ルである場合はステップ２０３に進み、キャッシュシミ
ュレーションコード埋め込み処理を行う。第１段階のコ
ンパイルでない場合は、ステップ２０４に進み、キャッ
シュ向け最適化処理を行う。コード生成処理２０３で
は、中間コード３０７を入力とし、機械語またはアセン
ブリ言語で記述されたオブジェクトプログラム３０９ま
たは３１３を生成する。（第１段階のコンパイルではキ
ャッシュシミュレーション用オブジェクトプログラム３
０９を、第２段階のコンパイルでは最終的なオブジェク
トプログラム３１３を生成する。）

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】計算機の利用技術において、
オブジェクトプログラムの実行時間を削減する、コンパ
イル方法に関する。特に、キャッシュミスに起因する性
能の低下を削減するための、コンパイラによる最適化方
法に関する。

【０００２】

【従来の技術】コンパイラの生成するオブジェクトプロ
グラムの実行時間を削減するための方法は、これまで数
多く開発されている。その中の１つに、コンパイラによ
るキャッシュ向けの最適化がある。

【０００３】キャッシュ向け最適化方法の１つとして、
ソフトウェアプリフェッチ最適化がある。ソフトウェア
プリフェッチ最適化は、データを主記憶装置（メモリ）
からキャッシュに移動する命令（プリフェッチ命令）
を、コンパイラがオブジェクトプログラムに挿入するこ
とにより、キャッシュミス時に発生する待ち時間（キャ
ッシュミスペナルティ）を削減（隠蔽）する最適化方法
である。ソフトウェアプリフェッチ最適化の方法につい
ては例えば「Bernstein他：Compiler Techniquesfor Da
ta Prefetching on the PowerPC, PACT '95, 1995, pp.
19-26」に記載がある。

【０００４】ソフトウェアプリフェッチ最適化では、コ
ンパイラが、キャッシュミスを起こす可能性の高いデー
タのアクセス（ロードまたはストア）に対して、そのア
クセスの前にプリフェッチ命令を発行するようなコード
を生成する。すなわち、プリフェッチ命令でデータをメ
モリからキャッシュに移動し、実際のアクセス命令では
キャッシュミスを起こらないようにしておく。（プリフ
ェッチ命令とロードまたはストア命令の間には別の無関
係の命令を挿入することにより、待ち時間を隠蔽す
る。）つまり、１回のデータアクセスに対し、プリフェ
ッチ命令とアクセス命令の２つの命令を実行する必要が
ある。したがって、キャッシュミスを起こさないデータ
のアクセスに対してソフトウェアプリフェッチを行う
と、プリフェッチ命令の発行が無駄（オーバーヘッド）
になり、その分性能が低下してしまうという問題点があ
った。

【０００５】この問題点を解決するため、従来のコンパ
イラでは、ソースプログラムを解析して、キャッシュミ
スを起こす可能性の高いデータのアクセスについてのみ
キャッシュ向け最適化（例えばソフトウェアプリフェッ
チ）を行うようにしている。キャッシュミスを起こす可
能性を静的に解析する方法として、「Wolf他：A DataLo
cality Optimizing Algorithm, ACM SIGPLAN '91, 199
1, pp.30-40」がある（リユース解析と呼ばれる）。こ
の方法では、プログラム中のループネスト（ループの入
れ子）の中に出現する配列参照コードの添字部分を調べ
ることにより、そのデータが再利用されるかどうか、ま
た再利用されるまでの時間的インターバルを解析する。
あるデータが比較的短いインターバルの間に再利用され
ることがわかれば、そのデータはキャッシュ上に残って
いると推定される。

【０００６】

【発明が解決しようとする課題】上記従来技術（リユー
ス解析方法）を用いたキャッシュ向け最適化方法では、
キャッシュミス予測にどうしても間違いが生じるという
問題があった。たとえば従来方法では、キャッシュミス
を予測する際には、プログラム中の配列のサイズやルー
プの繰り返し回数などを手がかりして解析を進めること
が多いが、これらの値は実行時に決まる（静的な解析で
は求められない）ことが多いため、結果としてキャッシ
ュミス予測がはずれてしまうことが多い。

【０００７】このようなプログラムの例を図４に示す。
図４はＦortran言語で書かれたプログラムであり、ＦＵ
ＮＣというサブルーチンを定義している。パラメタ宣言
部４０１から、ＦＵＮＣはＡ，Ｂ，Ｃ，Ｎ，Ｍという４
つのパラメタ（引数）を入力とすることが示され、変数
宣言部４０２〜４０３から、Ａ，Ｂ，Ｃは配列であり、
Ｍ，Ｎが整数であることが示される。また２次元配列Ａ
のサイズは第１次元が１からＮ、第２次元が１からＭ、
１次元配列Ｂ，Ｃのサイズは１からＮである。このよう
にプログラムで使われる配列のサイズは入力パラメタ
Ｍ，Ｎによって決まるので、コンパイラ側では判断でき
ない。また、プログラム実行部４０３〜４０７は２重ル
ープになっており、ループの範囲はＪが１からＭ，Ｉが
１からＮと、やはり入力パラメタＭ，Ｎによって決ま
る。このようなプログラムにおけるキャッシュミス率を
推測する場合、ループの範囲および配列のサイズが重要
な手がかりとなるので、これらが静的にわからないと予
測は不確かなものになってしまう。

【０００８】また、従来の方法では競合性のキャッシュ
ミスを予測することが困難であるという問題点もあっ
た。競合性のキャッシュミスとは、ダイレクトマップ方
式またはセット連想方式のキャッシュで生じるキャッシ
ュミスであって、キャッシュの容量が十分大きいにもか
かわらず、２つ以上のデータのキャッシュアドレス（キ
ャッシュに格納するアドレス）が偶然一致してしまうた
めに生じるものである。このようなキャッシュミスはプ
ログラムの静的な解析では予測することが困難である。

【０００９】このようにプログラムの静的解析に基づい
てキャッシュミスを予測した場合は、その予測が外れや
すいので、本当にキャッシュ向け最適化が必要なところ
に最適化が適用されない、または必要のない（すなわち
キャッシュミス率が低い）部分に無駄な最適化を行わ
れ、それがオーバーヘッドになるという問題点があっ
た。

【００１０】本発明の目的は、プログラム中の各データ
アクセスに対するキャッシュミス率をより正確に求め、
それを利用してコンパイラによる無駄のない効率的キャ
ッシュ向け最適化を行う方法を与えることである。

【００１１】

【課題を解決するための手段】前記目的は、次のように
フィードバックを用いる２段階からなるコンパイル方法
によって解決される。

【００１２】第１段階のコンパイルでは、ソースプログ
ラム中の各メモリ参照コードに対して、そのメモリ参照
におけるキャッシュの動作をシミュレートするコードを
挿入し、オブジェクトプログラムを生成する。次に第１
段階のコンパイルで生成されたオブジェクトプログラム
を実行することにより、各メモリ参照のキャッシュミス
率を記録したデータ（キャッシュミス率記録ファイル）
を作成する。次に第２段階のコンパイルでは、前記キャ
ッシュミス率記録ファイルと元のソースプログラムを入
力として最終的なオブジェクトプログラムを生成する。
第２段階のコンパイルでは各メモリ参照でのキャッシュ
ミス率がわかるので、ソフトウェアプリフェッチ等のキ
ャッシュ向け最適化を適用するメモリ参照を適切に選択
することができ、効果的な最適化が行える。

【００１３】またキャッシュシミュレーションでは、静
的解析では予測不能な競合性のキャッシュミスも正しく
シミュレートできるので、競合性キャッシュミスに対す
るキャッシュ向け最適化ももれなく適用可能となる。

【００１４】このため、コンパイラは現在のコンパイル
が第１段階のコンパイルであるかどうかを調べ、第１段
階のコンパイルである場合はキャッシュシミュレーショ
ンコード埋め込み処理を行い、そうでない場合は、キャ
ッシュ向け最適化処理を行うようし、キャッシュ向け最
適化処理では、キャッシュミス率データを利用してキャ
ッシュ向け最適化を適用する部分を選択する。

【００１５】

【発明の実施の形態】以下、本発明の一実施例を説明す
る。

【００１６】図３は、本発明に係る計算機システムの構
成図である。図示するように、計算機システムはＣＰＵ
３０１、主記憶装置３０２、外部記憶装置３０３、ディ
スプレイ装置３０４、キーボード３０５より構成されて
いる。外部記憶装置３０３にはソースプログラム３０
８、キャッシュシミュレーション用オブジェクトプログ
ラム３０９、キャッシュシミュレーション用ライブラリ
３１０、キャッシュシミュレーション用ロードモジュー
ル３１１、オブジェクトプログラム３１２、キャッシュ
ミス率記録ファイル３１３が格納される。主記憶装置３
０２には、コンパイラ３０６と、コンパイル処理過程で
必要となる中間コード３０７が保持される。コンパイル
処理はＣＰＵ３０１がコンパイラプログラム３０６を実
行することにより行われる。キーボード３０５はユーザ
からのコマンドをコンパイラ３１１に与えるのに用い
る。ディスプレイ装置３０４はコンパイルの終了または
エラーをユーザに知らせる。

【００１７】図１は、本実施例に係るコンパイラにおい
て、ユーザによるコンパイル処理の手順を示したもので
ある。コンパイル処理は、第１段階のコンパイル１０
１、リンク１０２、実行１０３、第２段階のコンパイル
１０４の４つの手順からなる。第１段階のコンパイル１
０１により、ソースプログラム３０６に対して、そのプ
ログラムの実行時のキャッシュの動作をシミュレートす
るコードを埋め込んだオブジェクトプログラム（キャッ
シュシミュレーション用オブジェクトプログラム）３０
７を作成する。次にリンク１０２で、キャッシュシミュ
レーション用オブジェクトプログラム３０７とキャッシ
ュシミュレーション用ライブラリ３０９をリンクするこ
とにより、キャッシュシミュレーション用ロードモジュ
ール３１０を作成する。リンク処理は公知の技術である
ので、ここでは詳しく説明しない。次に実行１０３で、
キャッシュシミュレーション用ロードモジュール３１０
を実行することにより、キャッシュミス率記録ファイル
３１３を作成する。最後に第２段階のコンパイル１０４
で、キャッシュミス率記録ファイル３１３を用いて、ソ
ースプログラム３０６に対してキャッシュ向け最適化を
行ったオブジェクトプログラム３１２を作成する。第１
段階および第２段階のコンパイルにおけるコンパイラ処
理の流れは図２を用いて説明する。

【００１８】図２は、コンパイル処理の流れを示したフ
ローチャートである。コンパイラの処理は、まずステッ
プ２０１で、構文解析２０１を行う。構文解析はソース
プログラム３０６を読み出し、コンパイラ内部で処理可
能な中間コード３０７を作成する。構文解析処理につい
ては、たとえば「エイホ、セシィ、ウルマン著：コンパ
イラＩ（サイエンス社、１９９０年）３０頁〜７４頁」
に記載されているので、ここでは詳しく説明しない。次
にステップ２０２で、本コンパイルが第１段階のコンパ
イルであるかを調べる。コンパイルが第１段階であるか
どうかはユーザからのコンパイルコマンドにより判定す
る。第１段階のコンパイルである場合はステップ２０３
に進み、キャッシュシミュレーションコード埋め込み処
理を行う。この処理では、この処理については図６のフ
ローチャートを用いて後で詳しく説明する。第１段階の
コンパイルでない場合は、ステップ２０４に進み、キャ
ッシュ向け最適化処理を行う。キャッシュ向け最適化処
理については図１０を用いて後ほど説明する。コード生
成処理２０３では、中間コード３０７を入力とし、機械
語またはアセンブリ言語で記述されたオブジェクトプロ
グラム３０９または３１３を生成する。（第１段階のコ
ンパイルではキャッシュシミュレーション用オブジェク
トプログラム３０９を、第２段階のコンパイルでは最終
的なオブジェクトプログラム３１３を生成する。）コー
ド生成については、同様に「エイホ、セシィ、ウルマン
著：コンパイラII（サイエンス社、１９９０年）６２４
頁〜７０７頁」に記載があるので、ここでは詳しく説明
しない。

【００１９】図５は本実施例におけるコンパイラの中間
コードの例である。中間コードは構文解析２０１の処理
により作成される。図５の中間コードは図４のソースプ
ログラムに対応している。図５の中間コードは、基本ブ
ロック（Ｂａｓｉｃ Ｂｌｏｃｋ，ＢＢと略される）を
エッジで結んだグラフで表現されている。（このような
グラフは制御フローグラフと呼ばれている。）５０１か
ら５０７は基本ブロックである。これらの基本ブロック
には、ＢＢ１からＢＢ７までの番号がそれぞれ付けられ
ている。基本ブロックは途中で分岐や飛び込みのない、
一連のコード列を表している。エッジ（矢印）は基本ブ
ロック間の遷移を表している。たとえば基本ブロック５
０１から５０２にエッジが張られているので、５０１が
終った後で、５０２へ制御が移ることを示している。基
本ブロックの解析方法や制御フローグラフの構成方法に
ついては前著（コンパイラII）６４２頁〜６４８頁に記
載されているので、ここでは詳しく述べない。各基本ブ
ロック中に書かれているものは実行文であり、その基本
ブロックに制御が移ったときに実行される。ただし、実
行文の中には、ソースプログラム中に陽に表れていない
ものもある。例えばＢＢ５（５０５）中の最後の文「Ｉ
＝Ｉ＋１」はソースプログラム中にはないが、コンパイ
ラがソースプログラムの意味を表すために加えたもので
ある。基本ブロック中の各実行文には、コンパイラによ
って一意的な番号（実行文番号）が付けられている。こ
れを各実行文の左側の[]の中に示している。なお、ここ
では１つの文にはメモリ参照は１つしか現われないよう
にしているので、実行文番号によって対応するメモリ参
照が一意に決まる。

【００２０】図６はシミュレーションコード挿入処理２
０２の流れを示したフローチャートである。まずステッ
プ６０１で、中間コード中の未処理の実行文を取り出
す。未処理の実行文がなければステップ６０４へ進む。
ステップ６０２で、取り出した実行文がメモリ参照文で
あるかを調べる。メモリ参照文はたとえば配列要素参照
を含むような文である。メモリ参照文であれば、ステッ
プ６０３で、 sim(メモリアドレス、実行文番号) という関数呼び出し文を作成し、現在処理中の実行文の
直前に挿入する。ここで「メモリアドレス」は、参照し
ようとするメモリのアドレスを表す式である。関数si
m()はキャッシュの動作をシミュレートするためにコン
パイラが用意するライブラリ関数である。その動作につ
いては図８を用いて後ほど説明する。最後にステップ６
０４で、プログラムの先頭にキャッシュシミュレーショ
ン初期化関数を、プログラムの最後にキャッシュシミュ
レーション結果出力関数を挿入する。これらの関数、お
よび関数sim()はいずれもキャッシュシミュレーション
用ライブラリ３０７に含まれる。

【００２１】図７はシミュレーションコード挿入処理後
の中間コードを示した図である。図７では実行文番号
４，５，７にそれぞれ「B(I)」「C(I)」「A(I,J)」とい
うメモリ参照があるので、これらの文の直前にシミュレ
ーションコードが挿入されている。たとえば実行文４の
前には「sim(&B(I),4)」という文が挿入されている。こ
こで「&B(I)」というのは、配列要素Ｂ(I)のアドレスを
表す式である。同様に実行文５の前には「sim(&C(I),
5)」という文が、実行文７の前には「sim(&A(I,J),7)」
という文が挿入されている。

【００２２】図８は関数sim()の動作を摸式的に示した
図である。以降この関数を便宜的にキャッシュシミュレ
ータと呼ぶことにする。キャッシュシミュレータはキャ
ッシュシミュレーション用ロードモジュール３１１を実
行するときに動作する。キャッシュシミュレータ８０１
は、大きく分けて制御部８０２、キャッシュテーブル８
０３、キャッシュミス率記録テーブル８０４からなる。
またキャッシュシミュレータへの入力となるのはメモリ
アドレス８０５と実行文番号８０６である。（これは関
数simの２つの引数に対応する。）キャッシュモデルテ
ーブル８０３は実際のキャッシュをソフトウェア的にシ
ミュレートしたものである。制御部８０２は与えられた
メモリアドレスを基に、そのアドレスがキャッシュ上に
存在するか（キャッシュヒットしているか）をキャッシ
ュモデルテーブルを使って調べ、もしミスしていれば必
要に応じてキャッシュモデルテーブルの内容を変更する
とともに、その結果をキャッシュミス率記録テーブル８
０４に登録する。登録するときには実行文番号を用い、
その実行文番号に対応するエントリに記録していく。な
お、キャッシュモデルテーブルおよびキャッシュミス率
記録テーブルはキャッシュシミュレーション初期化関数
の実行時（プログラムの最初）初期化される。また、キ
ャッシュミス率記録テーブルの内容はキャッシュシミュ
レーション結果出力関数の実行時（プログラムの最後）
キャッシュミス率記録ファイル３１３に出力される。キ
ャッシュモデルテーブル等を用いてキャッシュシミュレ
ーションを行う方法については例えば「T.M.Conte, C.
E.Gimac著：Fast Simulationof Computer Architectur
e, pp87-108, Kluwer, 1995」などに記載があるので、
ここでは詳しく説明しない。

【００２３】図９はキャッシュミス率記録テーブル８０
４の内容（の例）を示した図である。キャッシュミス率
記録テーブルは、実行文番号９０１、アクセス回数９０
２、キャッシュヒット回数９０３、キャッシュミス回数
９０４、キャッシュミス率９０５の５つのフィールドか
らなる。実行文番号９０１はメモリ参照のある実行文の
番号を表す。アクセス回数９０２はメモリ参照回数を表
すもので、これはキャッシュヒット回数９０３とキャッ
シュミス回数９０５の和となる（したがって９０２〜９
０４の３つのうち、１つは他から計算できるので省略可
能）。キャッシュミス率９０５は「キャッシュミス回数
／アクセス回数」を表す（これも他から計算できるので
省略可能）。キャッシュミス率記録ファイル３１３の内
容もキャッシュミス率テーブル８０４と同じ構成であ
る。

【００２４】図１０はキャッシュ向け最適化処理２０４
の流れを示したフローチャートである。本実施例ではキ
ャッシュ向け最適化処理としてソフトウェアプリフェッ
チを行うものとする。まずステップ１００１で、中間コ
ード中の未処理の実行文がまだあるか調べる。未処理の
実行文がなければ終了する。ステップ１００２で、それ
がメモリ参照文であるかを調べる。メモリ参照文であれ
ば、ステップ１００３で、キャッシュミス率記録ファイ
ルからその実行文に対応するエントリがあるかを調べ
る。エントリがなければその実行文は実行されなかった
ということであるので、スキップしてステップ１００１
へ進む。エントリがあればステップ１００４で、その実
行文のキャッシュミス率を取り出し、それが一定値以上
であるかを調べる。キャッシュミス率が一定値以上であ
れば、キャッシュ向け最適化の効果があるメモリ参照と
いうことなので、ステップ１００５でキャッシュプリフ
ェッチ命令を挿入する。

【００２５】図１１は、図５の入力中間コードおよび図
９のキャッシュミス率記録ファイルのデータを基に、ソ
フトウェアプリフェッチ最適化を行った結果の中間語で
ある。図５のプログラムでは実行文番号４，５，７の３
箇所にメモリ参照があるが、そこに対応するキャッシュ
ミス率はそれぞれ０.１９％，０.１９％，２５.０％で
あることがキャッシュミス率記録ファイルからわかる。
ここで、キャッシュミス率３％以上の参照にのみキャッ
シュ向け最適化を行うとすると、実行文７のメモリ参照
に対してのみプリフェッチ命令を挿入すればよい。した
がって図１２の中間語では、実行文７に対するプリフェ
ッチ命令である実行文１０「prefetch(&A(I+3,J)」が新
たに挿入されている。なお、プリフェッチ命令の挿入方
法については、例えば前記文献「Bernstein他：Compile
r Techniques for Data Prefetching on the PowerPC,
PACT '95, 1995, pp.19-26」に記載されているのでここ
では詳しく述べない。

【００２６】なお本実施例では、キャッシュ向け最適化
としてソフトウェアプリフェッチを行うコンパイラの構
成を示したが、本発明はこれに限定されるものではな
く、ループブロッキングあるいはタイリングと呼ばれる
他のキャッシュ向け最適化にも同様に適用可能である。
また本発明では、キャッシュミス率記録ファイルでは主
にキャッシュミス率のみを記録したが、これに加えてキ
ャッシュミスの種類（初期ミス、容量性ミス、競合性ミ
ス）を記録することにより、適用するキャッシュ最適化
をより細かく選択することも可能である。

【００２７】

【発明の効果】本発明によれば、静的解析ではキャッシ
ュミス率が予測できないプログラムに対しても、プログ
ラム中の各データアクセスに対するキャッシュミス率を
より正確に求め、それを利用してコンパイラによる無駄
のない効率的キャッシュ向け最適化を行うことができ
る。

【図面の簡単な説明】

【図１】ユーザによるコンパイル処理の手順である。

【図２】コンパイラの処理の流れである。

【図３】計算機システムの構成図である。

【図４】ソースプログラム例である。

【図５】中間コードの例である。

【図６】キャッシュシミュレーションコード埋め込み処
理の流れである。

【図７】キャッシュシミュレーションコード挿入後の中
間コードである。

【図８】キャッシュシミュレーション関数simの動作モ
デル図である。

【図９】キャッシュミス率記録テーブルである。

【図１０】キャッシュ向け最適化処理の流れである。

【図１１】キャッシュ向け最適化処理後の中間コードで
ある。

【符号の説明】

３０１…ＣＰＵ、 ３０２…主記憶装置、 ３
０３…外部記憶装置、３０４…ディスプレイ装置、３０
５…キーボード。

Claims (7)

【特許請求の範囲】
1. 【請求項１】コンパイラにおけるキャッシュ向け最適化
   方法であって、 コンパイルが第１段階のコンパイルであるか否かを判定
   するステップと、 第１段階のコンパイルであるときに、プログラム中のメ
   モリ参照に対してキャッシュシミュレーションを行うコ
   ードを挿入するステップと、 第２段階のコンパイルであるときに、プログラム中のメ
   モリ参照に対してキャッシュ向け最適化を行うステップ
   とを有し、 上記キャッシュ向け最適化処理では、該メモリ参照にお
   けるキャッシュ特性データを用いて処理を行うことを特
   徴とするキャッシュ向け最適化方法。
2. 【請求項２】請求項１のキャッシュ向け最適化方法であ
   って、上記キャッシュ特性データは、キャッシュミス率
   を含むことを特徴とするキャッシュ向け最適化方法。
3. 【請求項３】請求項１のキャッシュ向け最適化方法であ
   って、上記キャッシュ特性データは、キャッシュミスの
   種類を含むことを特徴とする、キャッシュ向け最適化方
   法。
4. 【請求項４】請求項１のキャッシュ向け最適化方法であ
   って、上記キャッシュ特性データは、該データがプログ
   ラム中のどの参照に対するものであるかを示す情報を含
   むことを特徴とする、キャッシュ向け最適化方法。
5. 【請求項５】請求項１のキャッシュ向け最適化方法であ
   って、上記キャッシュ向け最適化はソフトウェアプリフ
   ェッチを行うことを特徴とする、キャッシュ向け最適化
   方法。
6. 【請求項６】請求項１のキャッシュ向け最適化方法を用
   いたコンパイラ。
7. 【請求項７】請求項６のコンパイラを格納した記憶媒
   体。