一般に、プロセッサは主記憶アクセス時間よりも1桁程度高速に オペランドを処理できます。 プロセッサ並の高速動作が可能なメモリも存在はしますが、 主記憶を全てこのような高速メモリで構成するのは コストの点で非現実的です。 そのため、 主記憶とプロセッサの間にキャッシュ(cache、小量の高速メモリ)を 置くことで、アクセス速度の違いから起きる問題を軽減します。
キャッシュとは高速のRAMです。 プロセッサは主記憶中のプログラムやデータにアクセスするときに、 もしキャッシュ上にコピーが存在すればキャッシュだけにアクセスします。 データを変更する場合は、キャッシュのデータだけではなく、 メモリ上のデータも直す必要があります。
キャッシュがうまく動作するのは、プログラムには一般に 局所性原理(Principle of Locality) が当てはまるからです。
1回目の参照でキャッシュに読み込んだワードがずっとキャッシュ上にあり、 n回参照される場合は、平均アクセス時間は以下のようになると考えられます。
平均アクセス時間 = ( n * tc + tm) / n = tc + tm / n
tc: キャッシュのアクセス時間
tm: メモリ(主記憶)のアクセス時間
n: 参照回数
(例) tc=25ns, tm=200ns, n=10回 とすると
平均アクセス時間 = 25 + 200/10 = 45 (ns)
nが増加すれば、平均アクセス時間はキャッシュのアクセス時間に近づきます。 時間的局所性を多く持つプログラムもあれば、そうでないプログラムもあるので 高速化の程度はプログラムに依存します。
空間的局所性を利用するためには、連続した場所のかたまり (ライン line または ブロック blockと呼びます)を主記憶と キャッシュの間でまとめて移動します。 ラインの転送では、幅の広いバスを使って複数のメモリモジュールから 同時に転送することが高性能のために必要です(図3.2)。
モジュール数mは、主記憶とキャッシュメモリの速度が適切になるように 選ばれます。 ここで m * tc = tm となるように m を決めると完全に整合がとれます。
mワードのデータを全部でn回参照する場合は
平均アクセス時間 = (tm + tc * m * n) / (m * n)
= tm / (m * n) + tc
(例) tc = 25ns, tm = 200ns, m = 8, n=10回 とすると
平均アクセス時間 = (200 + 25 * 8 * 10) / (8 * 10)
= 27.5 ns
(参考) (m*tc=tmの時の平均アクセス時間) = tc * (n+1)/n
キャッシュ中に必要なデータが存在する(これを『キャッシュがヒットする』 といいます)確率は、プログラム、キャッシュのサイズ、キャッシュの マッピング方法に依存します。 約80〜90%はヒットすると考えるのは妥当な仮定です。
キャッシュ中に必要なデータがなく主記憶へのアクセスが必要な時は、 『キャッシュをミスした』といいます。 キャッシュのヒット率(hit ratio, hit rate)を h とすると以下のように 定義されます。
h = キャッシュ中に必要なワードが見つかる回数 ／ 総参照回数
キャッシュの研究にはヒット率 h そのものよりもミス率 (miss ratio) である 1-h の方がよく用いられます。 ヒット率を考慮すると、平均アクセス時間 ta は以下のように 表されます。
ta = tc + (1-h) * tm
ただし、あるワードにアクセスするには、まずキャッシュにアクセスすると
仮定しています(tc)。ミスした場合に主記憶にアクセスすることによって
アクセス時間は (1-h) * tm だけ増加します。
(例) tc= 25ns, tm = 100ns, h=0.85 とすると
ta = 25 + (1-0.85) * 100 = 40 (ns)
ここの説明では、データを主記憶からキャッシュに持ってきたときには 再度キャッシュを読まなくてもプロセッサがデータを利用できる (主記憶とプロセッサの間は直接バスでつながっている)ものと仮定しています。
主記憶上の情報をキャッシュ上にマップする方法はいろいろ考えられます。 高速化のためにはハードウェア化する必要があります。
アドレスとデータの組をキャッシュの中に保持します。 プロセッサから入力されたメモリアドレスを、連想メモリの 内部論理を使ってキャッシュに格納されている全てのアドレスと 同時に比較します。 もし一致するものが見つかればそのアドレスに対応するデータを読み出します (図3.3)。 見つからない場合は、主記憶からキャッシュに読み込みます。
多数の比較器を利用する特殊なメモリが必要なため実現には コストがかかります。 そのため、完全連想マッピングが用いられるのは 小規模なキャッシュを持つマイクロプロセッサだけとなります。
どの方式でも、連続した数ワードのラインをキャッシュすることもできます (図3.4は、4ワード／ラインの完全連想マッピングの例です)。 主記憶とキャッシュの間に十分な幅のデータパスがあれば1回で ライン全体を転送できます。 1ワード分の幅のデータパスしかない場合はラインを何回かに分けて 転送します。 このときはキャッシュの中のデータが有効かどうか示 すために有効ビットが使われることが多いです。
アクセスすべき主記憶上のアドレスの下位ビットを使ってキャッシュに アクセスする方式です。 キャッシュ上のデータがアクセスすべきデータと同一であるかどうかは、 キャッシュ内のタグとアドレスの上位ビットを比較して判断します。 タグが一致しない場合は、キャッシュミスですので主記憶上の データにアクセスします。 このときキャッシュのデータも更新します。
利点キャッシュのサイズが大きくなると、直接マッピングと連想マッピングの ヒット率の差は減少し、わずかになります。 最近はキャッシュサイズが大きくなる傾向があるので、 直接マッピングが有利になっています。
直接マッピングでは、キャッシュに格納される全てのワードは、 異なるインデックスを持たなければなりませんでした。 また、完全連想マッピングではラインをキャッシュの中のどの場所 にでも入れることができますが、容量をあまり大きくできませんでした (大容量の連想マッピングキャッシュは高価かつ低速ですので)。
n-wayセット連想マッピングとは、同じインデックスを持つデータをn組 キャッシュ中に保持できるようにしたものです(図 3.7 は 4-wayの場合)。 同一インデックスにおけるデータ(ワードまたはライン)の数を、 連想度(associativity) またはセットサイズ (set size) と呼びます。
セット中の各ラインにはタグが設けられていて、タグと インデックス(セット番号)でラインを一意に特定します。
セット連想マッピングキャッシュはマイクロプロセッサの内部キャッシュとして よく使われています。
(例) Motorola MC68040, Intel 486, Intel i860 --- 4-way set associative
Intel Pentium --- 2-way set associative
主記憶からキャッシュへデータを(ワードまたはライン単位で)フェッチする 戦略には3種類あります。
キャッシュはプロセッサチップの中に組み込まれることが多く なってきました。 Pentium や MC68040は分離キャッシュを採用しています。
分離キャッシュでは、コードを書き換えるようなプログラムでは 問題が生じます。 コードを書き換えた場合は、命令キャッシュとデータキャッシュに 同じラインがキャッシュされていて、データキャッシュの 方が書き換わっていることになります。 これでは不整合が生じますので、命令キャッシュ中のラインを 無効にする機構を使う必要があります。
キャッシュに書き込みを行なうときは、キャッシュ上のデータと 主記憶上のデータで不整合を生じるおそれがあります。 データの一貫性を保つためには、キャッシュから主記憶に データを書き戻す必要があります。
キャッシュへ書き込むと同時に主記憶にも書き込む方式です。 キャッシュの書き込み時間と比較して主記憶への書き込み時間ははるかに 大きいので、主記憶への書き込み時間がアクセス時間を左右します。
しかし一般には、読み出し動作に比べて書き込み動作は稀にしか 発生しません(Smith 1982 によれば参照の5%から34%、平均で16%が 書き込み操作)ので、ライトスルー方式でもそれなりのアクセス速度が 期待できます。
読み出しや書き込みの時にキャッシュミスが生じると必ず 主記憶からキャッシュへラインを転送すると仮定すると、 平均アクセス時間は以下のようになります。
ta = tc + (1 - h) tb + w (tm - tc)
= (1 - w) tc + (1 - h) tb + w tm
= (1 - w) tc + (1 - h - w) tm if tb = tm
ただし
tc : キャッシュを調べ、そのデータが存在するかどうかを判断し、
あれば取り出すまでの時間
tm : そのワードがないときに主記憶からワードをCPUにフェッチする
(キャッシュにそのワードを転送する時間も含む)時間
tb :ブロックをキャッシュへ転送する時間
w: 書き込みの割合
(例) tc = 25ns, tm = 200ns, h=99%, w=20% , tb = tm のとき
ta = 25 + (1 - 0.99) * 200 + 0.2 * (200 - 25)
= 25 + 2 + 35
= 62 (ns)
(例2) tc = 25ns, tm = 200ns, h=99%, w=20% , tb = 16 tm のとき
ta = 25 + (1 - 0.99) * 200 * 16 + 0.2 * (200 - 25)
= 25 + 32 + 35
= 92 (ns)
項(tm - tc)は、書き込み時に(キャッシュにヒットしようが ミスしようが)ワードを主記憶に書き込むのに必要な時間です。 キャッシュと主記憶への書き込みは同時に起きますが、主記憶への 書き込み動作は次のキャッシュへの読み出し／書き込み操作が 行われるよりも前に完了していなければなりません。 キャッシュと主記憶の間にライトバッファを入れる、すなわち キャッシュから主記憶に書き込む情報をいったんライトバッファに 入れておきキャッシュへの次のアクセスを許すことによって 速度を改善することができます(図3.9)。
ライトスルー方式では、ノーフェッチオンライト方式を取るのが普通です。 ノーフェッチオンライト方式のヒット率は、フェッチオンライト方式よりも 一般に低くなります(書き込んだデータにすぐ後でアクセスする場合があるため)。
ラインの置換のときにだけ主記憶のデータを書き換える方式です。 書き込みミス時には一般にフェッチオンライト方式を用います。
キャッシュから追い出されるラインを(変更されているか否かによらず) 主記憶へ必ず書き戻す方法を単純ライトバック方式 (simple write-back) と呼びます。
ライトバック方式では、一般には変更したラインだけを書き戻します。 そのために各ラインに1ビットのフラグを用意しておき、ラインが 変更されたときにこのフラグをセットします。
ライトバック方式では、ブロック中の1ワードだけが変更されても 全ブロックを主記憶に書き直す必要が生じます。 これに対してライトスルー方式では変更されたデータだけが主記憶上で 書き直されます。 しかしライトスルー方式では、データが変更されるたびに トラフィックが生じるので、全体として見れば ライトバック方式が有利であると考えられます。
キャッシュが一杯のときに新しいラインをキャッシュに持ってくる ためには、どれかのラインをキャッシュから追い出す必要があります。 追い出すラインを選びだす方法を置換アルゴリズムと呼びます。
直接マッピングでは追い出すラインは一意に決まるので 置換アルゴリズムは必要ありません。 完全連想マッピングでは、全てのキャッシュデータ中から 置き換えるデータを選ぶ必要があります。 セット連想マッピングでは、同じセット中に含まれるキャッシュ データの中から置き換えるデータを選ぶことになります。
キャッシュの置換アルゴリズムはハードウェアで実装されなくては いけません。 置換アルゴリズムには
どの方式のキャッシュでもサイズが大きくなるとミス率が減り 性能が向上します。 実際のミス率は、プログラムや全体の負荷、キャッシュの実現方法 (書き込み戦略、置換アルゴリズムなど)によっても変わります。
キャッシュをプロセッサに組み込む時に、キャッシュサイズを十分に 大きくとれず性能が上がらないことが起こりえます。 そのような場合は、1次キャッシュと主記憶の間にサイズの大きな (1次キャッシュの10倍以上が一般的)キャッシュを挿入することがあります (2次キャッシュ, second-level cache, secondary cache)。
1次キャッシュと2次キャッシュの置換戦略は通常どちらもLRUです。 またキャッシュの間のデータの一貫性を保つために、ライトスルー方式 がとられるのが普通です。
ほとんどのマイクロプロセッサでは、外部のキャッシュコントローラを 用いて2次キャッシュを利用できます(486->8291, Pentium->82491など)。 プロセッサと2次キャッシュの間は高速性が必要です。 主記憶とのバス(フロントサイドバス, frontside bus)とは独立した 2次キャッシュバス(バックサイドバス, backside bus)を用意することが あります (例 Intel P6)。
主記憶とディスクの間にRAMをディスクキャッシュとして置くことが あります。 これにより20〜30msかかる入出力時間が2〜5ms程度に短縮されます。
[問題1] 3レベルのメモリ (キャッシュ、主記憶、ディスク)の平均アクセス時間を 求めて下さい。各メモリのアクセス時間は, 20ns, 200ns, 2ms、 キャッシュのヒット率は 80%, 主記憶のヒット率は99% とします。
[問題2] 32ビット/ワード、32ビットアドレッシング で、8Kbyteのキャッシュを 持っている計算機を考えます。以下の各マッピングを行なうときのアドレスの 各フィールド長を決定して下さい。 ただしタグは上記の8Kbyte以外の場所に置かれるものとします。
[問題3] ディスクキャッシュを導入したところ、アクセス時間が 20ms から 6.3ms へ 短縮されました。キャッシュのヒット率を 70% とすると、ディスクキャッシュの アクセス時間はどれだけと考えられますか。