近年、急速に拡大したプロセッサとDRAMの間の速度差は、プログラム実行速度を規定する主要な原因の1つである。プロセッサとDRAM間の速度差を埋めるキャッシュメモリを用いたプロセッサにおいても、超高速プロセッサではキャッシュミスが数百プロセッササイクルの待ち時間を引き起こす。このため、キャッシュミスの削減がコンピュータシステムの実行性能の向上に必須である。キャッシュミスは、(1) 置き換えの判断を誤ったために生じるキャッシュミス、(2) メモリブロックに対する初めての参照によるキャッシュミスや、キャッシュの容量が足りないために起こるキャッシュミスなど、置き換えの判断が正しくても起こるキャッシュミス、の二つに大別される。本論文はそれぞれの種類のキャッシュミスを減らす方法を提案する。

あるデータと別のデータが近い時間に参照されるとき、それらは時間的親和性を持つと言う。このデータの時間的親和性と、データの冗長性を利用して、(2)のキャッシュミスを削減する。数値計算プログラムに関しては、コンパイラはデータの時間的親和性を解析することができる。一方で、再帰的構造体(Recursive Data Structures, RDS)を用いるプログラムにおけるデータの時間的親和性を解析することはコンパイラには難しい。RDSは非数値計算プログラムでは広く用いられている。そこでRDSによって起こされるキャッシュミスを減らすことを目的として、Field Array Compression Technique (FACT)と呼ぶ、ソフトウェアとハードウェアによる方法を提案する。FACTは、時間的親和性を持つデータを、メモリ上での配置を変換することによってメモリの連続領域に集める。その後ポインタフィールドと整数フィールドを圧縮する。結果として、1回のキャッシュフィルが時間的親和性を持つより多くのデータをキャッシュに運ぶことができるようになる。さらに、圧縮によって実効的なキャッシュ容量が増大する。

FACTを実行駆動シミュレーションによって評価する。ポインタを頻繁に用いるOldenベンチマークの8個のプログラムにおいて、FACTはキャッシュミスによる待ち時間を平均41.6％削減する。また、速度を平均37.4％向上する。

次にキャッシュ置き換えアルゴリズムの性能を向上することにより、(1)によるキャッシュミスを削減する。そこでプロセッサのセットアソシアティブ2次キャッシュのための新たな置き換えアルゴリズム、Inter-Reference Gap Distribution Replacement (IGDR) を提案する。IGDRは、メモリブロックに重みを付け、置き換えの際は、最小重みのメモリブロックを選択する。メモリブロックが次に参照される時刻が分かっているとすると、その時刻と現在の時刻との差の逆数が、理想的なメモリブロックの重みである。あるメモリブロックが参照された時刻において、前回参照されてから経過した時間を参照間隔と呼ぶ。提案手法では理想的な重みを参照間隔の逆数を使って近似する。そのために、各メモリブロックの参照間隔の確率分布は一定であると想定する。そして、参照間隔の逆数の統計を取ることによって、参照間隔の逆数の分布を推定する。この分布から参照間隔の逆数の期待値を推定し、この推定値をメモリブロックの重みとする。統計は、参照回数、参照間隔によってメモリブロックをクラスに分類し、クラスごとに取る。SPEC CPU2000の10個のプログラムにおいて、提案手法は最大48.8％、平均17.0％のミス数の削減、最大39.6％、平均9.1％の速度向上を示す。

近年、急速に拡大したプロセッサとメモリ間の速度差は、アプリケーション性能向上を阻害するものである。プロセッサとメモリ間の速度差を埋める目的でキャッシュメモリが使われている。キャッシュミスが生じるとメモリを参照するために、キャッシュミスをなるべく減らす手法が、従来から提案されてきた。本論文は、キャッシュミスの原因を2つに分類し、それぞれの原因に対応するキャッシュミス軽減手法として、Field Array Compression Technique (FACT)およびInter-Reference Gap Distribution Replacement (IGDR)を提案し、有効性をシミュレーションにより明らかにしたものである。

一つめのキャッシュミスの原因として、置換えの判断が正しくても起こるキャッシュミスがある。この原因に対して、データの冗長性と時間的親和性を利用することにより削減する。あるデータと別のデータの参照時間が互いに近いとき、それらのデータが時間的親和性を持つという。再帰的構造体を用いるプログラムではコンパイラにより静的に時間的親和性を検出することは難しい。そこで、再帰的構造体によって起こされるキャッシュミスを減らす方法として、本論文では、FACTと呼ばれる手法を提案している。FACTは、時間的親和性を持つデータを、メモリ上での配置変換を行なうことによって、メモリの連続領域に集める。さらに再帰的ポインタフィールドと整数フィールドを圧縮する。これにより、メモリからキャッシュへの転送容量が減り、かつ、実効的なキャッシュ容量が増大する。提案されたFACTは実行駆動シミュレーションによって評価される。Oldenベンチマークの8個のプログラムにおいて、平均37.4 ％の速度向上が達成されていることを確認する。

二つめのキャッシュミスの原因として、置換えの判断を誤ったために生じるキャッシュミスがある。この原因に対して、本論文では、プロセッサのセットアソシアティブ2次キャッシュのための新たな置換えアルゴリズムであるIGDRを提案している。IGDRは、メモリブロックに重みをつけ、置換えの際は、最小重みのメモリブロックを選択する。メモリブロックの重み付けは、メモリブロックの参照間隔の逆数を使用する。ここで、参照間隔とは、前回参照されてから経過した時間を指す。各メモリブロックに参照間隔の統計情報を保持することは多くのロジックを必要とし、非現実である。そこで、統計は、参照回数、参照間隔によって、メモリをクラスに分類し、クラス単位で統計情報をとる。提案されたIGDRの有効性を、実効駆動シミュレーションにより評価される。SPEC CPU2000ベンチマークの10個のプログラムにおいて、IGDRは、平均17.2 ％のキャッシュミス数を軽減し、平均9.2 ％の速度向上が達成されていることを確認する。

さらに、二つの手法を組み合わせた場合の評価を行なっている。組み合わせた手法では、Oldenベンチマークの8個のプログラムにおいて、FACTだけの性能に比べて、最大13.5 ％、平均 3.2 ％の速度向上を達成していることを示す。

本論文は、このように、メモリ階層におけるプロセッサ内キャッシュとメモリの間のキャッシュミスに対して、その問題点を体系化し、それら問題点に対して、新しい手法を提案している。提案手法は、学位請求者が開発した実行駆動シミュレーションソフトウェアにより評価されている。二つの提案手法による速度向上は、それぞれ、平均 37.4 ％と17.2 ％である。この数値は、当該分野における提案の中では世界レベルにあると認める。

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる。