配線遅延を考慮したキャッシュメモリ高速化手法の提案

(1)

2004 年度卒業論文

配線遅延を考慮した

キャッシュメモリ高速化手法の提案

提出日： 2005 年 2 月 2 日指導：山名早人助教授

早稲田大学理工学部情報学科学籍番号： 1G01P092-5

増田渓介

(2)

概要

近年の計算機においては，CPUの高速化に対して主記憶(メインメモリ)アクセスの高速化が追いついていないため，メインメモリアクセスのレイテンシがシステム全体のボトルネックとなっている。そのため，高速・小容量のキャッシュメモリをプロセッサとメインメモリの間に設け，メモリの一部をコピーしておくことによってこのボトルネックを緩和している。

一方，プロセスの微細化に伴い，配線遅延の影響が大きくなりつつある。配線遅延とは，配線自身の抵抗・容量や隣接する配線との容量などにより生じる遅延である。配線遅延は，キャッシュメモリのアクセスレイテンシの増大にもつながる。とりわけ，微細化に伴い大容量化していくキャッシュメモリは，チップ上に占める物理的面積も相対的に増加し，配線遅延の影響をより受けやすくなる。キャッシュメモリにおけるアクセスレイテンシの増加は，システム全体のパフォーマンス低下を意味する。

従来，キャッシュメモリの研究は，いかにヒット率を上げるか，という点に重点が置かれており，キャッシュラインの物理的な配置はアーキテクチャの側面からの研究では殆ど取り扱われていない。しかし，配線遅延の増加により，キャッシュヒット/ミスだけではなく，ヒットした場合の配線遅延によるペナルティを考慮したアクセスレイテンシというパラメータを取り入れたキャッシュ機構を考案することが望まれていると考える。

そこで本論文では，配線遅延の影響を考慮して，アーキテクチャ的観点からキャッシュメモリの高速化手法を提案する。提案手法は，アクセスするラインまでの物理的距離が短くなるようなライン配置アルゴリズムを考え，アクセス時に配線遅延によるレイテンシを最小限に抑えることによって高速化を図っている。SimpleScalarに実装し，SPECint95を用いてシミュレーションした結果，

容量が4MBである2次キャッシュ機構での実験では，既存の2次キャッシュ機構と比較して，全ベンチマークプログラムで高速化でき，最高で約1.66倍，平均で1.43倍の高速化を達成した。

(3)

はじめに

現在の計算機において，システムのボトルネックとなっているのが，主記憶(メインメモリ)アクセスのレイテンシである。メインメモリには一般的にはDRAMが使用されるが，CPUの処理速度にDRAMのアクセスレイテンシが追いついていないのが現状である。

その緩和策として，キャッシュメモリが広く利用されている。キャッシュメモリとは，主に SRAMによってオンチップ領域に実装された高速メモリであり，小容量だがメインメモリよりも高速にアクセスできる。メインメモリの内容の一部をキャッシュメモリに置くことにより，メモリアクセスレイテンシを事実上削減することができる。

一方，プロセスの微細化は年々進んでいるため，その影響で将来，配線遅延が急速に増加すると考えられる。配線遅延とは，配線自身の抵抗や容量，また隣接配線間容量などによって生じるもので，微細化の2乗に比例して増大する。そして，配線遅延はキャッシュメモリのアクセスレイテンシにも影響する。特に，微細化によって大容量のキャッシュメモリを搭載できるようになると，アクセスするラインまでの物理的距離もその分増加し，遅延は増大する。結果，アクセスレイテンシが増加し，システム全体の性能低下につながる。一方で，大規模科学技術計算などの分野では，依然としてキャッシュミスによるメインメモリアクセスのレイテンシが，プログラム実行時間に占める割合が大きく，キャッシュメモリの容量増加に対する要望は大きい[14]。よって，容量を増やしつつも，同時に増加する配線遅延によるアクセスレイテンシを低下させる手法が望まれる。

キャッシュに関する研究では，ロード命令の参照アドレスを予め計算しプリフェッチする手法[7]，ヒット/ミスを予測して命令発行レイテンシを削減する手法[18]，ソフトウェア・コンパイラレベルでうまくデータがキャッシュに収まるように工夫する手法[19] [20]，といったものが提案されている。しかし，いずれもキャッシュの物理的な構造を考慮に入れてはいない。つまり，

キャッシュの大容量化や配線遅延によって増加するアクセスレイテンシが大きくなれば，上記の手法による性能向上率は小さくなってしまう。

このような背景のもとで，今後は配線遅延の影響を考慮したキャッシュメモリの設計を行うことが，システムの性能向上に有効であると考えられる。そこで本論文では，キャッシュメモリの物理

(5)

的配置に着目し，配線遅延の影響を緩和してキャッシュメモリのアクセスレイテンシの低減を図る手法を提案する。

以下，第2章でキャッシュメモリの基本原理，研究動向，問題点について述べる。第3章では配線遅延をモデリングし，キャッシュメモリに与える影響について述べる。第4章で本論文の提案手法の解説，ならびに実装について述べる。第5章で実験環境を説明し，実験結果をもとに考察を行う。第6章は本論文のまとめとし，今後の課題を述べる。

(6)

第 2 章

記憶階層とキャッシュメモリ

本章では，記憶の階層化，キャッシュメモリの基本原理，関連研究，問題点について述べる。

プログラムの実行においては，命令やデータを主記憶(メインメモリ)から頻繁に読み書きする必要があり，メモリアクセス速度の向上はコンピュータシステム全体の性能にとって非常に重要である。

まず記憶の階層化について述べる。記憶の階層化は，参照の局所性を利用し，低速・安価・大容量のメインメモリと，高速・高価・小容量のキャッシュメモリを組み合わせることによって，コストパフォーマンスの優れたシステムを実現することができる。しかし，キャッシュミスが発生すると，メインメモリアクセスにより多大なレイテンシを被る。

よって，高速化を達成するためには，まず，キャッシュミス率を下げることが重要である。また，

キャッシュメモリ自身のアクセスレイテンシを小さくするために，キャッシュメモリ内での回路構成をできるだけ単純化することも重要である。

次に，以上を鑑み，従来から用いられているキャッシュメモリの方式，既存の高速化手法，問題点の考察などを述べる。

なお，本論文では，「メインメモリ(=主記憶)」，「キャッシュメモリ」に対して，「メモリ」と単に書く場合は任意の記憶装置を指すものとする。また，キャッシュメモリをキャッシュと書く場合がある。

2.1 記憶の階層化

プログラムのメモリアクセスには，参照の局所性という性質がある。参照の局所性には，時間的局所性と空間的局所性の2つがある。時間的局所性とは，ある項目がアクセスされたとき，その項目が近い将来に再度アクセスされる確率が高いことを表す。空間的局所性は，ある項目がアクセスされたとき，その項目の近くにある項目が近い将来にアクセスされる確率が高いことを表す。

例えば，図2.1に示すように，プログラム内にループが含まれているとき，ループ内の命令列や

(7)

図2.1 時間的局所性・空間的局所性のforループでの例

その命令列がアクセスするデータは，ループの実行中に繰り返しアクセスされる可能性が高い。これは時間的局所性を表している。また，命令は通常，メモリに格納されている順にアクセスされ，

配列データも格納されている順にアクセスされることが多く，空間的局所性が存在する。

参照の局所性を利用することにより，高速・小容量のメモリと低速・大容量のメモリを組み合わせて，アクセスされる可能性の高い命令やデータを高速メモリに配置することによって高速・大容量のメモリシステムを実現することができる。このような構成を，記憶階層という。記憶階層では，高速・小容量のメモリを上位メモリ，低速・大容量のメモリを下位メモリと呼ぶ。

記憶階層は，レジスタとキャッシュメモリ，キャッシュメモリとメインメモリ，メインメモリと

外部記憶(HDD)などシステム中に多く存在するが，本論文で対象とするのは，キャッシュメモリ

(上位)とメインメモリ(下位)の記憶階層である。

2.2 キャッシュメモリの概要

キャッシュメモリはメインメモリより容量が小さいので，参照の局所性を利用して，アクセスされる可能性の高い命令及びデータを厳選してメインメモリからキャッシュメモリにコピーすることになる。そこで，限られた資源で，どのようにデータ及び命令をキャッシュメモリにマッピングするか，どのようにキャッシュメモリを検索するか，また，キャッシュメモリの容量制限により中身を置き換える必要が生じた場合に，どのような戦略で置き換えるか，といった点を考慮し，最も効率のよい方式を選択するべきである。本節では以上のような観点から，現在までに考案されている主要な方式を述べる。

なお，記憶階層において，上位メモリと下位メモリの間のデータ転送単位をブロックと呼ぶ (キャッシュメモリではしばしばキャッシュライン，またはラインとも呼ぶ。本論文ではキャッシュについては(キャッシュ)ラインと呼び，メインメモリなど主記憶以外ではブロックと呼ぶことに

(8)

する)。また，CPUから要求された命令及びデータが上位メモリに存在することをヒットと呼び，

存在しないことをミスと呼ぶ(キャッシュメモリの場合特にキャッシュヒット，キャッシュミスとも呼ぶ)。

ラインサイズが大きいと空間的局所性を活かしやすいが，半面不要なデータが増え，結果としてキャッシュミスを招く可能性が高くなる。逆にラインサイズが小さいと，転送のオーバヘッドが増えて階層化の利点が損なわれる恐れがある。

2.2.1 キャッシュメモリの方式

キャッシュメモリの中身はメインメモリのコピーであるが，メインメモリのブロックとキャッシュラインをマッピングする方式には，ダイレクトマップ方式，nウェイ-セットアソシアティブ方式，フルアソシアティブ方式の3つがある。以下，この3つを説明する。一般的な性質としては，

ヒット率を可能な限り向上させようとすれば，その分回路が複雑になりアクセスレイテンシが増加するというトレードオフが存在する。

ダイレクトマップ方式(図2.2)

ダイレクトマップ方式は，CPUがメインメモリへアクセスするとき，そのアクセスするブロックから，保持している可能性のあるキャッシュラインが一意的に決まる方式である。

キャッシュにヒットしているかどうかは，アクセスするアドレスからただ1つ決まるラインを調べればよいので，最も高速な方式であり，また，回路が単純ですむ。

半面，同じラインが別のデータで上書きされる可能性が高く，3つの手法の中では，ヒット率は最も低い。例えば，容量4096バイト，ラインサイズ64バイトのキャッシュメモリを考えると，ダイレクトマップ方式では，メモリアクセスの参照アドレスが0〜63，4096〜4159，8192〜8255などの場合，全て同じキャッシュラインにデータを格納する。そのため，連続してこれらの同じラインへのアクセスが行われると，その度に競合し，キャッシュの役割を果たさないことになる。

フルアソシアティブ方式(図2.3)

フルアソシアティブ方式は，CPUがメインメモリへアクセスするとき，あらゆるキャッシュラインが当該キャッシュデータを保持している可能性のある方式である。

ダイレクトマップ方式のような競合は，キャッシュ容量に余裕がある限り生じないため，ラインの使い方としては最も効率のよい方式である。そのためヒット率は高い。しかし，アドレスを受け取ってからキャッシュにヒットするかどうかが判明するまで，全てのラインを検索しなければならないため，キャッシュの容量に比例して検索時間が増加する。また，比較するための回路規模が膨大になる。

(9)

図 2.2 ダイレクトマップ方式。アドレスに応じてラインが一意に決定する。

図2.3 フルアソシアティブ方式。

アドレスと全ラインのタグ部を比較する。

nウェイ-セットアソシアティブ方式(図2.4)

nウェイ-セットアソシアティブ方式は，CPUがメインメモリへアクセスするとき，そのアクセスするブロックから，保持している可能性のあるキャッシュラインがn通り(n個のウェイの中に) 存在する方式である。このときのnを，連想度とも呼ぶ。

ダイレクトマップ方式とフルアソシアティブ方式の中間的な方式で，そのため様々な性質のプログラムを実行する汎用プロセッサにおいては，どんな参照局所性を持ったプログラムに対しても安定した性能を発揮するので現実的である。なおn = 1のときがダイレクトマップ方式，n =キャッシュ中のライン総数のときがフルアソシアティブ方式といえる。

最近の一般的なプロセッサでは，nウェイ-セットアソシアティブ方式が用いられることが多い (ウェイ数は2〜8程度の場合が多い)。そのため本論文でも，キャッシュメモリの方式は基本的に nウェイ-セットアソシアティブ方式であるという立場で進める。

各方式でのキャッシュメモリの効率の考察

以上の各方式，言い換えればキャッシュメモリのウェイ数n (ダイレクトマップ方式はn = 1，フルアソシアティブ方式はn =ライン総数とみなす)をどうするかは，設計時の重要な問題である。

例えば，容量が1024バイト，ラインサイズ16バイトのnウェイ-セットアソシアティブ方式のキャッシュを考えてみる。キャッシュ全体のライン数は64であり，ウェイ毎のライン数は64/nである。つまり，アドレスの下位10ビットをもとにキャッシュアクセスを行い，うち下位4ビット

(10)

図2.4 nウェイ-セットアソシアティブ方式(n = 4)

がライン内バイトのインデックス，上位のlog₂nビットがウェイ数を表し，残った中間のビットが各ウェイでのラインへのインデックスとなる。仮にアドレス空間を16ビットとすると，例えば4 ウェイ-セットアソシアティブ方式の場合は以下のようになる。

b₁₅b₁₄· · ·b₁₁b₁₀|

(ウェイ)

z}|{

b₉b₈ |

z }| {ライン

b₇b₆b₅b₄|

z }| {バイト

b₃b₂b₁b₀

また，ダイレクトマップ方式の場合は10ビット中上位6ビットが全てラインインデックスであり，フルアソシアティブ方式の場合はラインインデックスは存在しない(全て同じラインインデックスと見なすともいえる)。

ここで，アドレス中のラインインデックスが同じだった場合，キャッシュラインの競合が生じる。同一アドレスのラインはウェイの数nだけ同時に保持可能で，それを超えるとキャッシュミス時にラインの入れ替えが生じる。

一例として，アクセスパターンとして，例えばアドレスが000000|0000000000，000001|0000000000， 000010|0000000000，000011|0000000000というメモリアクセスがあったとする(図2.5 左)。このとき，ダイレクトマップ方式(n=1)の場合，ラインのインデックスが4つとも全て等しいため，

2つ目〜4つ目のアクセスでラインの入れ替えが生じ，1つ目〜3つ目のデータをキャッシュできない。一方，n≥4の場合は，同じラインインデックスに対してn個までデータを保持できるので，

4つのデータ全てを保持できる。

一方，000000|0000000000，000000|0000010000，000000|0000100000，000000|0000110000というメモリアクセスがあった場合を考える(図2.5右)と，それぞれラインのインデックスが違うた

(11)

図2.5 アクセスパターンによるキャッシュ効率の違い(ダイレクトマップ方式の場合)

め，ダイレクトマップ方式(n=1)でも4つのデータ全てを保持することができる。勿論，n≥2以上でも同様に4つ全てを保持することができる。

以上のような点から，同じ容量でウェイ数の違うキャッシュメモリを比較した場合，次のことが言える。

1. キャッシュにヒットする確率は，そのキャッシュのウェイ数に対して単調増加である。

2. 広いアドレス空間を使用し，メモリアクセスの局所性が予測しにくいようなプログラムでは，ウェイ数が少ないとミスしやすく，ウェイ数が多いほどミスしにくい。

3. メモリアクセスが狭いアドレス空間内に限られるプログラムでは，ヒット率とウェイ数はあまり関係ない。

1. は，ウェイ数を増やしても(増やしすぎても)ヒット率の観点では損をすることはない，ということになるが，前述のとおり，ウェイ数が多いほどハードウェアが複雑になりタグの検索時間もかかるため，ウェイ数はむやみに増やさないほうが望ましい。2.については，例えばマルチスレッド処理などが想定される場合，それぞれのスレッドで，別々のある程度広い局所性を持つことが多いため，ウェイ数を増やすことの効果はあると考えられる。3.については，シングルスレッド処理の場合や，特にデータ参照が限られたプログラムを実行する場合などは，ウェイ数はヒット率にあまり影響しないため，レイテンシやハードウェアの観点ではむしろウェイ数が少ないほうがよい，

という場合が想定できる。

まとめると，結局，アクセスするアドレス範囲が完全にランダムであれば，キャッシュのヒット率は方式によらない(キャッシュ容量のみに依存する)といえるが，現実には完全にランダムということはなく，何らかの局所性が存在する。

ある程度アクセスの局所性が見込める場合，例えばマルチスレッド環境などの複数の独立したア

(12)

ドレス空間に対する局所性が存在する場合には，その局所性の数だけウェイ数を増やすのが理想的である。現実には経験的に，4ウェイ-セットアソシアティブ程度が最も効率的と考えられている[1] [2]。

2.2.2 ライン置換アルゴリズム

本節では，キャッシュミスが生じてメインメモリから新しいデータをキャッシュに挿入する際，

既存のどのキャッシュラインを置換するかを決めるアルゴリズムを説明する。

キャッシュメモリが存在する理由は，データに高速にアクセスするためである。しかし，キャッシュメモリの容量は限られているため，プログラムで使用するメモリ領域のデータを全てキャッシュメモリに載せておくことは一般にできない。そのため，途中で既にキャッシュに存在するデータを追い出す必要がある。

なお，ダイレクトマップ方式の場合は，アクセスするアドレスから一意に置換対象が決まるため，考慮する必要がない。これはダイレクトマップの高速性に寄与する理由の1つである。

現在のキャッシュメモリでは，一般にLRUという置換アルゴリズムが使用される。また，LRU 以外でよく知られたアルゴリズムとしては，FIFOとRandomがある。

FIFO

FIFOは，最も過去にキャッシュに挿入されたラインを置換対象とするものである。時間的局所性を利用しているが，このアルゴリズムでは，頻繁にアクセスされているラインでも，競合が発生すると置換されてしまうことがあるため，断続的に同じラインにアクセスするような流れのアプリケーションでは無駄がある。ただ，キューを使えば簡単に置換対象ラインが割り出せるため，機構は比較的簡素である。

Random

Randomは，置換対象ラインをランダムに決めてしまうものである。そのため機構は簡素であ

る。局所性があまり存在しないと想定されるアプリケーションでは，このアルゴリズムで十分であり，回路規模の制約の厳しい組み込みプロセッサなどでは利用されることがある[3]。

LRU

LRUは，Least Recently Usedの略で，最も長い時間アクセスされなかったラインを置換対象と

する。

LRUはメモリアクセスの時間的局所性を最大限活かしたアルゴリズムである。

ただし，LRUを実現するためには，キャッシュメモリの各ラインへのアクセスの履歴を取らな

(13)

ければならない。例えば参照ビットを使う方法では，nウェイ-セットアソシアティブ方式の場合，

log₂n個の参照ビットが各ライン毎に必要になる。また，FIFOと違い，ラインの置換がなくても，

キャッシュヒットする毎にそれらを更新しなければならない。

2.3 従来の高速化手法

本節では，従来よりキャッシュメモリの高速化に有効であると考えられている手法である，多階層キャッシュ，ハーバードアーキテクチャ，プリフェッチについて述べる。

2.3.1 _{多階層キャッシュ} [4]

多階層キャッシュとは，キャッシュメモリをいくつかの記憶階層に分割する手法である。

近年，プロセッサの周波数向上により，プロセッサとメインメモリのアクセスレイテンシのギャップはますます増大している。一方，キャッシュメモリの容量を増やせばヒット率を上げることができ，メインメモリへアクセスする機会を減らせる。しかし，容量を増やすほどレイテンシが増加する。特に命令キャッシュ(次節で述べる)は，プロセッサから次々に命令をフェッチされるため，1サイクルアクセスが基本である。そのため，容量は自ずと限られてくる。

そこで，超高速・小容量のキャッシュメモリ(1次キャッシュメモリ)と，1次キャッシュより低速だが容量は大きくできるキャッシュメモリ(2次キャッシュメモリ)の2つに階層化することで，

1次キャッシュでミスした場合のレイテンシを抑えることができる。2次キャッシュは1次キャッシュとメインメモリとの間の緩衝材的な役割を果たすといえる。このように，キャッシュメモリをいくつかの記憶階層に分割する手法を多階層キャッシュと呼ぶ。

2.3.2 ハーバードアーキテクチャ [2]

ハーバードアーキテクチャは，キャッシュを命令キャッシュとデータキャッシュに分ける手法である。

命令キャッシュは，パイプラインの命令フェッチユニットに命令を供給する専用のキャッシュで，データキャッシュはロード・ストア命令を始め，実行ユニットがメモリアクセスを行う場合に参照される。

キャッシュを2つに分けることによって，パイプライン動作で命令とデータに同時にアクセスすることによる競合を防ぐことができる。また，互いにラインを書き換えることがないため，それぞれ独立した空間的局所性を最大限利用できる。

なお，実際のプロセッサでは，特にアクセス頻度が高くなる1次キャッシュにおいてハーバードアーキテクチャが用いられ，2次キャッシュ以上では，従来のキャッシュ(統合キャッシュ)が用いられることが多い。

(14)

2.3.3 プリフェッチ [5]

プリフェッチとは，近いうちにアクセスすると思われる命令及びデータがキャッシュにない場合，予め上位メモリからキャッシュに載せておく手法である。プリフェッチが成功すれば，メインメモリアクセスによるレイテンシを低減できる。

プリフェッチは，アクセスレイテンシは大きいが，バンド幅(スループット)も大きい，というメインメモリの性能を活かしている。

2.4 研究動向

本節では，キャッシュメモリに関する最近の研究を取り上げる。最近の研究の傾向としては，マルチスレッド環境を想定したキャッシュ機構の研究が多い。また，消費電力をテーマにした研究も散見される。マルチスレッドと消費電力は，いずれもキャッシュに留まらずプロセッサアーキテクチャ全体で見ても注目されている分野であり，今後もこれらの点を考慮したキャッシュ機構設計が求められると考えられる。一方，配線遅延を考慮している研究は殆どない。

2.4.1 マルチスレッド環境を想定した研究

背景

プロセッサの速度向上の基本は並列処理である。1サイクルで複数命令を実行することによって，同一動作周波数でもスループットが向上し，速度向上につながる。

数年前までのプロセッサでは，並列化を命令レベルで(ILP : Instruction Level Parallelism)行っていた。しかしILPは，結局は1つの命令流でスケジューリングするものであり，他の命令との相互依存性などの問題によって，限界に達したと見られている。

そこで，現在では並列化をスレッドレベルで(TLP : Thread Level Parallelism)追求する研究が盛んである。TLPでは，スレッドという複数の命令流でスケジューリング可能なため，相互依存関係による制約がILPに較べて少なくできる。

研究

本田らは，IntelのHyper-Threading Technology [6]を用い，空きスレッド(Helperスレッド)を使って将来参照するデータのアドレスを計算し，予め2次キャッシュにプリフェッチする手法を提案した[7]。本田らの手法では，キャッシュミスを頻発するロード命令を予め選別し，実行時にメインスレッドが該当ロード命令を実行する前に，Helperスレッドが先にキャッシュに載せておくことによって，キャッシュミスを防ぐ。

滝田らは，キャッシュ-メインメモリ間を流れるデータを圧縮し，メモリバンド幅を仮想的に拡

(15)

大させる手法を提案した[8]。CMP (Chip Multi-Processor)内の一部のプロセッサをデータ圧縮・

展開に特化し，2次キャッシュからメインメモリへライトバックする際に圧縮，メインメモリから 2次キャッシュへフェッチする際に(データが圧縮されていれば)展開を行うことによって，実質的にバンド幅拡大を達成している。

佐藤らは，リアルタイム処理を意識し，スレッドの優先度を用いてキャッシュブロックの置換を行うことで，優先度の高いスレッドのアクセスレイテンシを低減する手法を提案した[9]。リアルタイム処理はデッドラインまでに処理を終了させる必要がある。しかし，(キャッシュを共有した) マルチスレッド環境では，あるスレッドがキャッシュにフェッチしたデータを他のスレッドが入れ替えてしまうという事態が発生する。そこで，佐藤らの手法ではキャッシュブロック置換の際，スレッドの優先度を考慮し，優先度の高いスレッドのデータをキャッシュから置換させないことで，

スレッド間競合によるキャッシュミスのアクセスレイテンシ増加を防いでいる。

佐々木らは，オンチップマルチプロセッサ環境における共有キャッシュの実現方式の検討を行っている[10]。オンチップマルチプロセッサ環境でのキャッシュには，分散キャッシュと共有キャッシュがあり，前者はデータの重複やコヒーレンシ制御などの問題点がある。一方，後者には容量当たりの面積が大きくなってしまうという問題点が指摘されている。佐々木らの研究は，共有キャッシュを，マルチポートメモリセル方式と，マルチバンクメモリ方式に分け，さらにマルチバンクメモリ方式の実現方法，面積，速度に関して詳細な検討を行っている。

以上のように，マルチスレッド環境を考慮したキャッシュの研究は，マルチスレッド特有のアクセスの局所性に着目したものや，空きスレッドをランタイム的に使用してメインスレッドのキャッシュアクセスを補助するものなど，非常に多岐に渡っている。

2.4.2 消費電力を考慮した手法

背景

プロセッサの消費電力は増加傾向にある。基本的には，CPUの動的消費電力は動作周波数に比例し，動作電圧の2乗に比例する。従来は，CPUの周波数を上げるとともに，ゲートの閾値電圧 (サブスレッショルド電圧)も下げて，動作電圧を低くすることにより消費電力を抑えてきた。

しかし，最近では回路非動作時に流れるリーク電流が問題になってきている。まず，サブスレッショルド電圧を低下させることにより，回路の非動作時にも電流が発生するサブスレッショルドリークが大きくなってきた。また，微細化とともにゲート絶縁膜が薄くなり，トンネル効果で電流が流れるゲートリークも今後より一層増加すると考えられている[11]。

一方，プロセッサにおけるキャッシュメモリは，チップ面積の大部分を占めるものもあり，キャッシュの消費電力も，例えばDECのAlpha チップにおいてはチップ全体の25%の電力を消費する[12]。

(16)

以上により，低消費電力を実現可能なキャッシュアーキテクチャに対する要請は非常に大きく，

今後さらに大きくなっていくと考えられる。

研究

石原らは，キャッシュを幾つかのブロックに分割し，過去の履歴情報から少数のブロックのみを低閾値電圧で動作させることにより，高速かつ低リーク電流のキャッシュ動作を実現する手法を提案した[12]。閾値電圧が高いと，リーク電流を軽減できるが動作は遅くなり，逆に閾値電圧が低いと，動作は速くなるがリーク電流が増大する。よって，実際に使用する回路のみを低閾値電圧で動作させるのは理に適っている。石原らの手法では，履歴情報にブロック毎の予測テーブルを使用している。なお，同様の動的に閾値電圧を変化させる手法は，TransmetaがLongRun2として発表している[13]。

Huらは，アクセスされる見込みの少ないキャッシュラインの電源供給をオフにすることで，リーク電流を低減する手法を提案した[21]。Huらの手法では，最後のアクセスから一定サイクル経過したらラインをオフにする，という戦略を取っている。

2.4.3 _{その他の研究}

中村らは，チップ上に実装するメモリとして，アドレス指定可能な主記憶の一部をSRAMとして載せるアーキテクチャSCIMA (Software Controlled Integrated Memory Architecture)を提案した[14]。データセットの大きな大規模科学技術計算などのHPC分野のアプリケーションでは，

キャッシュが有効に機能しないことが多い。そこで，データのアロケーションや置換を，ソフトウェアで行うことによって，ハードウェア制御のキャッシュで起こりがちである不要な競合を減らし，高速化が達成できるとしている。また，SMP構成においても，SCIMAが有効であるとしている[17]。

福田らは，ライン・バッファを搭載したプロセッサにおけるスケジューリングミスによる性能低下を低減するために，ライン・バッファ・ヒット/ミス予測を用いたスケジューリング手法を提案した[18]。ライン・バッファとは，最近アクセスされたキャッシュラインを保持する完全連想の小さなバッファであり，0次キャッシュともいえる。しかしヒット/ミスが判明してからライン・バッファにアクセスすると，命令の発行レイテンシは増大する。そこで福田らの手法では，ライン・

バッファのヒット/ミスを予測してアクセスと同時に命令発行を行い，レイテンシを削減できるとしている。この手法の背景には，キャッシュ大容量化によるアクセスレイテンシの増大が挙げられており興味深い。

近藤らは，3次元PDE solverについて，キャッシュラインを考慮し，主記憶アクセス時のデータトラフィックを少なく抑えることができるブロックサイズ選択法を提案した[19]。HPC分野では

PDE (偏微分方程式)を高速に解くことは非常に重要であるが，近年の3次元PDEでは時間的局所

(17)

性のあるデータへのアクセスの時間間隔が長くなることから，メモリアクセスによる性能低下が著しい。そこで近藤らの手法では，キャッシュラインを考慮した新しいコスト関数を提案し，それによって最適なブロックサイズを選択することで，キャッシュミス回数を削減できるとしている。

橋本らは，命令キャッシュミスを削減するために，基本ブロック単位でコードの再配置を行う手法を提案した[20]。コード再配置手法は，将来再度アクセスされそうな命令群をブロック化し，

キャッシュに配置することによって，メモリアクセスレイテンシを防ぐ手法である。従来は主に関数単位で再配置を行っていたが，一般に関数内でもさらに局所性が存在する。そこで橋本らの手法では，時間的局所性があると予想される基本ブロックを複数まとめて，キャッシュラインに近い大きさのブロックにし，このブロックを単位として再利用のアルゴリズムを適用している。

2.4.4 _{従来の手法の問題点}

本節では，従来のキャッシュメモリに関する手法で，解決されていないと思われる点を挙げる。

従来のキャッシュメモリの性能向上に関する手法は，基本的にキャッシュヒット率を上げるためのものである。しかし，最近，配線遅延の増大が問題になってきている。配線遅延については次章で述べる。配線遅延によって，キャッシュのアクセスレイテンシが増加する。その結果，仮にキャッシュヒットしても，キャッシュアクセスレイテンシ自体がメインメモリのアクセスレイテンシと相対的に近くなってしまい，キャッシュの有効性が低下してしまう。

配線遅延の影響を受ける要因は，キャッシュコントローラとアクセスするキャッシュラインとの間の距離である。そのため，両者の距離を短くするような手段を考えることが今後は有効であると考える。

(18)

第 3 章

配線遅延

本章では，配線遅延について述べる。配線遅延とは，配線抵抗や配線容量によって生じる，配線を伝わる電気信号の遅延である。配線遅延が大きくなると，データ転送レイテンシの増加，クロック同期の困難など，LSIに対して大きな影響を与える。

本章では，まず，実際に配線に生じる遅延をモデリングする。次に，プロセスの微細化が進むにつれて配線遅延の影響が増加することを説明する。そして，配線遅延がキャッシュメモリに与える影響について述べる。

3.1 配線遅延モデル

配線遅延は，電気信号が配線を伝わる際に生じる遅延である。ここでは回路における配線遅延計算のモデルを示す。遅延モデルは，半導体チップ設計のための重要な情報となりうる。

図3.1はLSI配線の単純なRCモデルである。このRCモデルは，配線の単位長あたりの抵抗，

負荷容量で表されている。

キルヒホッフの電流則から，

v_s−v₁

R =Cdv₁

dt (3.1)

となる。vs(t)を振幅v_dd のステップ関数とし，v1(0) =0と仮定すると，式(3.1)の微分方程式を v1について解くことができ，

v1=v_dd(1−e^(−t/RC)) (3.2)

が得られる。

式(3.2)から，出力遅延はRC定数に比例するということができる。

正確な値は，論理しきい電圧によって決定される。論理しきい電圧を電源電圧の50%と仮定すると，出力遅延は次の式から計算できる。

1−e^(−t^0.5^/RC)=0.5 (3.3)

(19)

図3.1 単純なRCモデル

図3.2 配線抵抗モデル(A_wireは配線アスペクト比(配線幅に対する高さの比率) ) [11]

したがって，出力遅延は次のようになる。

t_0.5=ln 2×RC=0.69RC (3.4)

次に，図3.1の配線抵抗Rと配線容量Cを個別に考える。図3.2は配線を抵抗として見るためにモデリングしたものである。図3.2より，単位長あたりの配線抵抗Rは，

R=ρwire

1

W_wire×H_wire (3.5)

と表せる。ここでρwireは配線の抵抗率を表す。また，W_wireおよびH_wireはそれぞれ配線の幅と高さである。

図3.3は配線を容量として見るためにモデリングしたものである。図3.3から，単位長あたりの配線容量Cは，

C=Kε0(Wwire

D_via ×2+ Hwire

P_wire−W_wire×2) (3.6)

(20)

図3.3 配線容量モデル(Awireは配線アスペクト比，Aviaはviaのアスペクト比) [11]

と表せる。ここで，Kは配線間の絶縁材料の比誘電率，ε0は真空誘電率，W_wireは配線幅，H_wireは配線の高さ，Dviaは上下の配線間の距離，Pwire は配線間の水平方向のピッチを表している。

3.2 プロセス微細化との関係

本節では，前節で挙げた遅延モデルが，プロセスの微細化によってどのように影響を受けるかを述べる。

3.2.1 単位長あたりの配線抵抗の増加

式(3.4)より配線遅延は配線抵抗Rと配線容量Cの積に比例するが，式(3.5)よりRはρwire (抵抗率)に比例し，配線の幅・高さに反比例する。この幅・高さはプロセスの微細化と同じ割合で減少していくと仮定できる。したがって，単位長あたりの配線抵抗Rはプロセス微細化の2乗に反比例して増加する。

一方，ρwire(抵抗率)は，従来のアルミニウム配線に変えて銅配線を採用するなど，改善策はとられている。

3.2.2 隣接配線間容量の増加

式(3.6)を見ると，どの項も分子と分母で次元を打ち消しあうため，式の上では，プロセスの微

細化が進んでも，配線容量は微細化の影響を受けない。しかし，現実には，配線間距離の微小化により，影響を受ける対象の配線の数の増加などにより配線間容量の値は増加していくと考えられている[11]。

3.2.1節と合わせて，配線遅延は微細化の2乗に反比例していくといえる。

(21)

図3.4 技術世代推移に対するゲート遅延と配線遅延( [22]の図1を引用)

3.2.3 ゲート遅延の減少

プロセスの微細化に比例して，ゲート遅延は減少している(トランジスタのスイッチング速度は上昇していく)。その結果，配線遅延の影響は相対的に増大してしまう。

特に，プロセッサの動作周波数は，従来はゲート遅延に依存していたので，プロセスの微細化が進むにつれて周波数を向上することができた。しかし，今後は，配線遅延の方が支配的になるため，クロック同期のボトルネックが配線遅延に移り，高速化が困難になると考えられる。

図3.4に示すように，ゲート遅延は微細化に伴って順調に減少している一方，配線遅延は近年劇的に増加しており，アルミ配線+ S_iO₂ 技術では0.25µm世代以降，銅配線+ low k技術でも 0.18µm世代以降はゲート遅延を配線遅延が上回っている。さらに遅延全体も，今後増加の一途を辿ると見られている。

3.3 キャッシュメモリに与える影響

2章では，キャッシュメモリについて述べたが，本章で取り上げている配線遅延は，キャッシュメモリのアクセスレイテンシにも影響を与える。本節では，配線遅延がどのようにキャッシュメモリに影響を与えるかについて述べる。

プロセスの微細化が進むと，従来と同じ面積のチップ上に，より多くのトランジスタを載せることができる。したがって，キャッシュメモリに関しても，より大容量のものを載せることができる。

従来のキャッシュメモリは，いかにヒット率を上げるか，という点に重点を置いて研究されて

(22)

きた。

しかし，3.1節で述べたように，単位長当たりの配線遅延は微細化の2乗に反比例して今後急激に増大する。したがって，今後は，大容量化にともなって，配線遅延によるアクセスレイテンシが無視できなくなると考えられる。つまり，いくらキャッシュヒット率が高くなっても，キャッシュアクセスレイテンシ自体が大きくなってしまうので，従来のままではシステム全体のパフォーマンスは相対的に低下するのである。

だが一方で，さらなるキャッシュヒット率向上のために，大容量キャッシュメモリを搭載することに対する要望もあると考えられる。例えば，大規模科学技術計算では，扱うデータの単位が巨大なため，今もってキャッシュミスが頻発している[14]。また，今後TLP (Thread Level Parallelism) を向上させるためにマルチスレッドやマルチコアのプロセッサが増えると考えられる。その場合，

一般にスレッド毎にデータの局所性が異なるため，スレッド毎に別々のキャッシュ空間を所有できると理想的である。そのためにはキャッシュ容量の増加は欠かせない。

従来，配線遅延はデバイス側の問題としてとらえられ，アーキテクチャ側としてはあまり重視されてこなかった。しかし，現在のままでは，65nmプロセスの立ち上がる2007年には，単位長当たりの配線遅延は130nmプロセスを基準として約4倍，45nmプロセスの立ち上がる2010年には約 8倍にまで増加する[15]。さらに周波数向上，キャッシュ大容量化が進むと，キャッシュアクセスのサイクル数は相対的により増加し，配線遅延によるキャッシュアクセスレイテンシへの影響は，

45nm世代では現在の10倍を超えると予想される。

図3.5は，キャッシュ設計ツールCacti [16] (5.1節で詳説) を用いて，現在のPentium Mプロ

図3.5 130nmプロセスでのアクセスサイクル数を1とした場合の，微細化によるキャッシュ

アクセスサイクル数の増加率(予想)。グラフのノードにはプロセスルールと，キャッシュ容量を示している。

(23)

表3.1 プロセス微細化とキャッシュアクセスサイクル数増加(予想)

年プロセス CPU 動作周波数

2次キャッシュ容量

アクセスサイクル数

増加率(130nmを 1とした場合)

2001 130nm 1.5GHz 1MB 4 1

2004 90nm 3GHz 2MB 9 2.25

2007 65nm 6GHz 4MB 20 5

2010 45nm 12GHz 8MB 64 16

2013 32nm 24GHz 16MB 104 26

セッサを基準として求めた，将来の2次キャッシュアクセスサイクル数の増加を予想したもので

ある。Cactiで得られる2次キャッシュアクセスレイテンシ(ナノ秒)を元に，CPUの動作周波数

が1プロセス微細化される毎に2倍になると仮定してサイクル数に直し，130nmを1とした2次キャッシュアクセスサイクル数の増加率を示した。表3.1がその元データである。キャッシュ容量は，面積がほぼ同じになるように増加させている。

このように，配線遅延の影響を考慮した2次キャッシュアクセスサイクル数は，今後劇的に増加する。この例では，デバイス技術の進歩を考慮しておらず，またキャッシュ容量を単純に増やしている。その上，今後，動作周波数がどこまで伸びるかはやや不透明なため，現実にはアクセスサイクル数がここまで増加することはないと考えられるが，それでも無視できない影響を受けると予想される。

ゆえに，配線遅延の影響を被ることを前提とし，アーキテクチャレベルで，できるだけ影響を少なくするような努力が今後必須であると考える。

(24)

第 4 章

提案手法

本章では，本論文の主題である，配線遅延を考慮したキャッシュメモリ高速化手法の提案を行う。

第2章では，キャッシュメモリの仕組みと，現状の課題について述べた。また，第3章では，配線遅延について触れ，プロセスの微細化のため，今後配線遅延によるキャッシュメモリへの影響がますます大きくなることを述べた。

そこで，本章では，配線遅延の影響を考慮し，アクセスするキャッシュラインまでの平均距離が短くなるようなキャッシュアーキテクチャを提案する。ラインまでの距離が短くなれば，配線遅延は少なくて済み，アクセスレイテンシも少なくて済む。結果として，プロセッサの高速化を達成できる。

提案手法の骨子は，いかにアクセスするラインまでの物理的距離を少なくするか，という点である。配線遅延により，キャッシュコントローラからの距離が近いラインには速くアクセスできる一方，遠くにあるラインへアクセスするにはその分多くのサイクル数が必要である。つまり，頻繁にアクセスするデータを近くに配置すれば，配線遅延の影響を平均的に小さくすることができる。

以下，本提案手法で用いた以下の3つの手法：

1. キャッシュのサブバンク化

2. LRUによるラインの整列

3. 動的なラインの移動

を説明し，本提案手法が配線遅延の影響を緩和できることを示す。実験による評価結果は次章で述べる。

なお，本論文での提案手法は，2次キャッシュを対象としている。そのため，以降で単にキャッシュと書いた場合，2次キャッシュを指すものとする。

(25)

図4.1 左が従来の1バンクキャッシュ。レイテンシは最も遅いものにタイミングを合わせる。

右がサブバンク化したキャッシュ。コントローラからの距離に応じてレイテンシが決まる。

4.1 キャッシュのサブバンク化

キャッシュのサブバンク化[10]は，キャッシュを複数の小さな領域(バンク)に分割することである。

旧来のサブバンク化されていないキャッシュでは，複数のパイプラインから同時にキャッシュアクセスがあった場合に，ポート数による制限による待ちが発生し，パフォーマンスの低下の要因となっている。

さらに，タグの検索，データの出力といった処理の実現のための回路は，最も遅いものにタイミングを合わせる。つまり，距離的に近く配線遅延の影響が少ないラインのデータへのアクセスにも，配線遅延を最も受ける，最も遠いラインにタイミングを合わせなければならない。

そこで，キャッシュをいくつかのサブバンクに分割するという手法がある(図4.1)。こうすることにより，複数のパイプラインから同時にキャッシュアクセスがあった場合でも，同じサブバンクに対するアクセスでなければ，競合が発生することはない。

また，回路も各サブバンクで閉じたものとなるため，近くて速いラインにアクセスする際に，遠くて遅いラインの回路にタイミングを合わせる必要がない。したがって，頻繁にアクセスするラインが，近くのサブバンクに存在するようにすれば，配線遅延の影響を緩和できる。

4.2 LRU によるラインの整列

2.2.2節で述べたように，キャッシュラインの置換アルゴリズムには，LRUが広く用いられてい

る。LRUはメモリアクセスの時間的局所性を利用した非常に優れたアルゴリズムである。本節では，LRUを利用してアクセスするキャッシュラインまでの距離を最適化する方法を述べる。

(26)

図4.2 LRU情報を用いたライン配置

LRUは，置換アルゴリズムとしては，一番最後にアクセスされたラインを置換対象とするものである。この操作のためにLRUを用いた機構では，キャッシュのウェイ数分，アクセスされたラインの履歴を残さなければならない。

そこで，本提案手法では，LRUの履歴情報をもとに，キャッシュラインを物理的に並べる。つまり，一番最近アクセスされ次にアクセスされる可能性が最も高いラインが一番近くに，一番最後にアクセスされ次のアクセスされる可能性が最も低いラインが一番遠くに配置されるように並べる (図4.2)。

以上により，頻繁にアクセスされるラインはキャッシュコントローラから近い場所に配置されるため，アクセスの際に配線遅延の影響が少なく，高速化を達成できると考える。

4.3 動的なラインの移動

前節で，LRUの情報をキャッシュラインの物理的配置に応用することを述べた。本節ではその具体的な実装方法を述べる。

2.2.1節で，nウェイ-セットアソシアティブ方式では，メモリアドレスから保持している可能性

があるキャッシュラインがn通り存在すると述べた。本提案手法では，このnウェイ-セットアソシアティブ方式において，データをLRU順にキャッシュコントローラから配置する。

キャッシュアクセスやキャッシュミスが生じた際にも，LRUに準じた並び替えを行う。つまり，

n個のラインで，アクセスされたらそのラインを最も近い場所に移動し，他のラインは1つずつ遠くへずれることになる。また，キャッシュミスによりラインの置換が生じた場合，最も遠いラインが置換対象になり，新たにメモリからフェッチされてきたデータを最も近いラインに配置するようにする。具体的には，キャッシュヒットした場合は図4.3のようになる。また，キャッシュミスした場合は，ウェイn-1のデータがメインメモリのデータと置換された後は図4.3と同様になる。

(27)

図4.3 動的なラインの移動。➀_ウェイkのラインがヒットしたら，➁_ウェイ0〜k-1のラインを1つずつ遠くへずらしつつ，ウェイkのラインをウェイ0に送り，➂ウェイ0からデータを出力する。

(28)

4.4 提案手法のまとめ

ここに，従来のキャッシュが抱える問題点と，本提案手法によって解決される点をまとめる。

表4.1 提案手法のまとめ

従来のキャッシュの問題点提案手法での対応策アクセスレイテンシは，物理的に最も遠い

ラインへのアクセス時間で決まっていた

サブバンク化により，物理的に近いラインにはその分速くアクセスできる

ラインの物理的配置を考慮しておらず，コントローラからラインまでの距離はランダムで決まっていた

LRUの情報を用いて，頻繁にアクセスするラインをコントローラの近くに配置することで配線遅延の影響を最小限にするさらに，ラインを動的に移動することで，

時間的局所性を最大限利用する

図4.4 提案手法のまとめ

(29)

第 5 章

提案手法の評価

本章では，前章で提案した手法の評価を，CPUのシミュレータを用いて行った結果を示す。また，結果を元に考察を行う。

実験結果より，本提案手法は2次キャッシュアクセスの比率が大きいプログラムほど，性能向上率も大きいことが分かった。

5.1 実験環境

本節では，第4章で述べた提案手法を検証した実験環境を述べる。

まず，CPUシミュレータとして，SimpleScalar 3.0d/PISA [23]を用いた。SimpleScalar は，命令セットアーキテクチャ以上のレベルをシミュレートしたソフトウェアである。本論文では

SimpleScalarスイートの中から，キャッシュメモリ，命令パイプライン，スーパースカラ，アウト

オブオーダ，分岐予測による投機的実行などが予め実装されている，sim-outorderプログラムを，前節で述べた提案手法に基づいて改変し，実験を行った。

SimpleScalar上で動作させるプログラムには，SPECint95の，099.go，124.m88ksim，126.gcc， 129.compress，130.li，132.ijpeg，134.perlを用いた。入力にはrefセットを用いた。

また，配線遅延によるアクセスレイテンシを求めるため，キャッシュ設計ツールであるCacti [16]

を用いた。Cactiは，キャッシュメモリのプロセスルール，キャッシュ容量，ラインサイズ，ウェイ数(連想度)，サブバンク数などを入力とすることにより，キャッシュアクセスレイテンシや，

キャッシュメモリの面積，消費電力などを計算する。

本論文では，将来の65nmプロセスを想定した。まず現在のCPUとして，IntelのPentium Mプロセッサを想定し，130nmプロセスで，容量1MB，ラインサイズ64KB，8ウェイ-セットアソシアティブ方式の2次キャッシュのものをサンプルとして，Cactiで面積を導き出した。次に，65nm プロセスで，130nmプロセスのサンプルとほぼ同程度になる2次キャッシュの面積という条件で

Cactiを用いて計算したところ，65nmプロセスでの2次キャッシュの容量は4MBが妥当であると

(30)

いう実験結果が得られた。

以上より，本論文では65nmプロセスで，4MBの2次キャッシュを対象として，

(1)従来手法

(2)提案手法(ライン移動によるオーバヘッドなし) (3)提案手法(ライン移動によるオーバヘッドを考慮)

の3通りについて実験を行った。なお，ラインサイズなど他の条件は130nmプロセスと変えていない。

ここで，(1)従来手法と(2)(3)提案手法の違いについてまとめておく。

• 従来手法では，キャッシュラインの物理的な配置場所は，メモリアドレスから一意に決まる。一方，提案手法では，キャッシュコントローラの近くからLRU順に配置される。

• 従来手法では配置は静的に決まるが，提案手法ではキャッシュラインの動的な移動を行う。

今回の実験では，LRUによるライン配置アルゴリズムの効果の検証に重点を置いたため，従来手法でもサブバンク化はされているものと仮定した。また，提案手法では，アクセスレイテンシの計算を，ヒットしたウェイ番号(= LRU順位)から計算するが，従来手法では，ラインアクセスのレイテンシに関してはランダムと考えてよいので，簡単のために一律平均レイテンシを用いた。

また，(2)提案手法のオーバヘッドを考慮しない場合と(3)オーバヘッドを考慮する場合の違いは，以下の通りである。

• オーバヘッドを考慮しない場合は，動的なラインの入れ替えによって生じるコストを無しとみなしてレイテンシを算出するが，オーバヘッドを考慮する場合は，ラインの入れ替えによるコストを追加する。

• オーバヘッドを考慮する場合は，ラインの入れ替え中は当該ラインをロックし，他命令のキャッシュアクセスをブロックする。

Cactiより得られた実験時のパラメータ(65nmプロセス)と，比較のための130nmプロセスでの

各数値を表5.1に示す。

表5.1 Cactiにより得られたキャッシュメモリのアクセスレイテンシ

半導体プロセス容量(MB) 最短lat (cycle) 最長lat (cycle) 平均lat (cycle) メインメモリlat (cycle)

130nm 1 3 6 4 150

65nm 4 10 31 20 337

また，今回の実験でのプロセッサモデルを表5.2に示す。この内容は，2次キャッシュに関する

(31)

もの以外はSimpleScalarのデフォルトを使用し，各実験方法で共通である。

表5.2 実験でのプロセッサモデルフェッチ幅/デコード幅/発行幅 4/4/4

機能ユニット整数演算4 整数乗除算1 浮動小数点演算4 浮動小数点乗除算1 1次命令キャッシュ容量16kB

ラインサイズ32B ダイレクトマップ方式レイテンシ：1サイクル 1次データキャッシュ容量16kB

ラインサイズ32B

4ウェイ-セットアソシアティブ方式レイテンシ：1サイクル

2次統合キャッシュ容量4MB ラインサイズ64B

8ウェイ-セットアソシアティブ方式レイテンシ：表5.3を参照

分岐予測 bimod

表5.3 各実験方法での2次キャッシュアクセスレイテンシの算出方法キャッシュアクセスレイテンシ従来手法 ”平均lat”

提案手法(OHなし) ”最短lat”+α 提案手法(OHあり) ”最短lat”+α+β

また，各実験方法での2次キャッシュアクセスレイテンシの算出方法は，表5.3の通りである。

ここでα は，(データが存在するウェイによって決まる)キャッシュコントローラからの距離による配線遅延を考慮したレイテンシで，(アクセスするウェイ番号)×^最長_ウェイ数^lat−^最短^lat で算出した(ウェイ番号はコントローラの近くから0，1，. . .となる，図4.2参照) 。今回の65nmにおける実験では，表5.1よりα={(アクセスするウェイ番号)×3}サイクルとなる。β は，ライン置換のオーバヘッドとラインのロックに伴うレイテンシであり，今回の実験では，置換対象となる全ラインを15 サイクル(隣り合うラインのデータ移動時間を，Cactiの結果より概算)ロックした。

(32)

5.2 実験結果

ベンチマーク別の実験結果を以下の表に記す。なお，各項目の意味は，表5.4の通りである。

本提案手法は，2次キャッシュアクセスレイテンシ低減が目的である。そのため，実験では2次キャッシュ関係の統計を重点的に取り，解析の手助けとした。また，IPCは総合的な性能指標として用いている。

結果を見ると，いずれのベンチマークプログラムについても，提案手法は従来手法より高いIPC を達成できているのが分かる。従来手法→提案手法(オーバヘッドあり)のIPC向上率が最も大きいのは，126.gccで，約1.66倍に向上している。一方で，IPC向上率が最も小さい132.ijpegでは，

約1.03倍の向上に留まっている。

また，提案手法でも，オーバヘッドを考慮しない場合と考慮した場合の2通りを実験したが，当然だが考慮したほうが遅くなっている。ただ，今回の実験では，オーバヘッドによるIPCの低下は意外に小さいことが見て取れる。

表5.4 実験結果の各項目の説明

項目名意味

sim num insn 発行された命令の総数

sim cycle プログラム実行に要した総サイクル数

sim IPC 1サイクルあたりの命令実行数

ul2.accesses 2次キャッシュアクセスの総回数

ul2.hits 2次キャッシュヒットの総回数

ul2.misses 2次キャッシュミスの総回数

ul2.miss rate 2次キャッシュミス率

ul2.accesses / sim num insn 発行命令数に占める2次キャッシュアクセス回数の比率

表5.5 099.goの実行結果

従来提案(OHなし) 提案(OHあり) sim num insn 36,263,280,993 36,262,944,911 36,262,944,911 sim cycle 71,093,711,784 43,840,942,952 44,029,356,622

sim IPC 0.5101 0.8271 0.8236

ul2.accesses 3,048,458,288 3,049,539,544 3,049,658,689 ul2.hits 3,048,442,967 3,049,524,211 3,049,643,354

ul2.misses 15,321 15,333 15,335

ul2.miss rate 0.000005 0.000005 0.000005

ul2.accesses / sim num insn 0.084064602 0.084095198 0.084098484

配線遅延を考慮した キャッシュメモリ高速化手法の提案

2004 年度卒業論文