艦長日誌・私的記録 DS9

　コンピュータ基礎の基礎，第2回目はキャッシュメモリです。

　CPUの速度はドンドン速くなっているのに，メモリの速度は絶望的に速くなっていません。

　もちろんDRAMだってSDRからDDR，DDR2，DDR3と世代を経るごとに速度は上がっていますが，実はDRAMというのはコンデンサを使って電気をためることで記憶する仕組み自身に速度的な限界があって，DDRだのDDR2だのという速度向上の工夫は，そのアクセスの方法に工夫を行って高速化を試みたものに過ぎません。

　だから，高速化されたとはいえ，例えば連続でアクセスした時だけとか，そういう特定の条件の時だけ速度がアップするようになっているので，悪い条件でアクセスすると，昔のDRAMに比べて劇的に高速化されるというわけではありません。

　そんなですから，数GHzという超高速で動作するCPUの足を引っ張っているのがメモリということになります。もっとも，こういう状況はコンピュータが生まれてからずっと続いている問題ですので，なんとかこれを工夫して，遅いメモリに足を引っ張られないようにCPUを動かす方法が昔から考えられてきました。

　それがキャッシュメモリです。

　プログラムやデータには時間的あるいは空間的な局所性があり，ある命令の次に実行される命令は，その近所にあるという性質があります。また一度読み出したプログラムやデータは，もう一度使われることもあるし，その前後にあるものが使われることも多いことが経験的にわかっています。

　そこで，一度メインメモリから読み出したデータを，メインメモリよりもずっと高速なメモリに蓄えておき，以後はこれを使うようにすると遅いメモリにいちいち取りに行くことがなくなります。

　ただし，高速なメモリというのはとても高価ですから，たくさん用意することができません。そこで，出来るだけ少ない容量で性能改善が行われるように，様々な方式が考えられてきました。

　また，アドレス1つに対してキャッシュに蓄えられるデータの大きさは1ワードとは限らず，最近は4ワードや8ワードを蓄えるものも多くなってきました。

　キャッシュの大きさは有限ですから，1アドレスごとにたくさんのデータを蓄えておけば，アドレス情報が少なくて済むので有効利用が出来そうですが，なにせ格納できるアドレス情報が少ないですから，プログラムがあちこちをアクセスするようになると，キャッシュにちっともヒットしなくなります。

　かといって，1ワードごとにアドレスを割り振っていたら，アドレス情報の格納のためにメモリが使われてしまうので，無駄遣いになります。このあたりはそのCPUやどんなプログラムを走らせるのかによって最適解が変わってきますので，良く検討されなければなりません。

　ところで，メインメモリの遅さというのは，なにも読み出しの時だけではありません。結果を書き込む際にも遅いわけですが，これもキャッシュメモリに一時的に蓄えておけば，CPUは書き戻しを待たずに次の処理にとりかかれます。つまり，キャッシュメモリというのは，読み出しと書き戻しの2つの動きがあるということです。

----

問題:ダイレクトマップ方式のキャッシュにおいて，アドレスA，Bは同一のキャッシュブロックアドレスに割り当てられているため，アクセス時にコンフリクトミスを生じる。このキャッシュに接続されたプロセッサが，次に示す順にアクセスを行った。

a)アドレスAから読み出し
b)アドレスBに書き込み
c)アドレスBから読み出し
d)アドレスAに書き込み
e)アドレスBに書き込み

　ライトスルーキャッシュは，書き込み時にキャッシュと同時に主記憶を書き換える方式であり，この中で，書き込みミス時に直接主記憶のみを更新する方式をNo-write allocate(direct write)方式のライトスルーキャッシュと呼ぶ。

　一方，ライトバックキャッシュは書き込みの度に主記憶を更新せず，書き戻しの際にまとめて更新する方式である。

　今，この2つの方式について，上のa)からe)までのアクセスを順に行った際ヒットするかどうかを示した組み合わせの中で正しいものを選べ。ただし，Hがヒット，Mがミスヒットを示す。

1.
ライトスルー　ＭＭＨＭＨ
ライトバック　ＭＭＨＨＨ

2.
ライトスルー　ＭＭＭＭＨ
ライトバック　ＭＭＨＭＭ

3.
ライトスルー　ＨＨＭＨＭ
ライトバック　ＨＭＨＭＭ

4.
ライトスルー　ＨＭＭＭＨ
ライトバック　ＨＨＭＭＨ

5.
ライトスルー　ＭＭＭＭＭ
ライトバック　ＭＭＨＭＨ

----

回答:

　ダイレクトマップ方式のキャッシュメモリということなので，問題にあるようにアドレスAとアドレスBの内容は同時にキャッシュメモリ内には存在できない。

　また，No-write allocateのライトスルー方式というのは，書き込み時のアドレスがキャッシュに存在した場合（ヒットした場合）はキャッシュとメインメモリの両方を書き換え，キャッシュに存在しない場合（ミスの場合）には，メインメモリだけを更新し，このアドレスをキャッシュには取り込まないものである。

　一方のライトバック方式というのは，書き込み時のアドレスがキャッシュに存在した場合（ヒットした場合）には，キャッシュのみを書き換え，メインメモリには書き込まない。キャッシュに存在しない場合（ミスの場合）には，キャッシュメモリにそのデータを読み込んだ後，キャッシュメモリを書き換える。メインメモリへの書き込みは，キャッシュを追い出されてしまった時に行われる。

　まず，ライトスルーを検証する。

a)ではアドレスAのデータがキャッシュに存在せず，ミス。ここでキャッシュにはアドレスAのデータが入る。

b)ではアドレスBへの書き込みが発生するが，キャッシュに存在するのはアドレスAのデータなので，ミス。アドレスBのデータはメインメモリに書き込まれ，キャッシュはそのまま。

c)ではアドレスBからの読み出しをするが，キャッシュにはアドレスAのデータが入っているため，ミス。ここでキャッシュはアドレスBのデータを格納する。

d)ではアドレスAへの書き込みが発生するが，キャッシュに存在するのはアドレスBのデータなので，ミス。アドレスAのデータはメインメモリに書き込まれ，キャッシュはそのまま。

e)ではアドレスBに書き込みが発生するが，キャッシュにはアドレスBのデータが存在するため，ヒット。キャッシュメモリとメインメモリの両方にアドレスBのデータが書き込まれる。

　次に，ライトバックを検証する。

a)ではアドレスAのデータがキャッシュに存在せず，ミス。ここでキャッシュにはアドレスAのデータが入る。

b)では，アドレスBに書き込みが発生するが，キャッシュに存在するのはアドレスAのデータなので，ミス。アドレスBのデータはキャッシュに書き込まれ，メインメモリには追い出されたアドレスAに書き込みが発生する。

c)ではアドレスBからの読み出しをするが，キャッシュに存在するのはアドレスBのデータなので，ヒット。

d)ではアドレスAに書き込みが発生するが，キャッシュに存在するのはアドレスBのデータなので，ミス。アドレスAのデータはキャッシュに書き込まれ，メインメモリには追い出されたアドレスBに書き込みが発生する。

e)ではアドレスBに書き込みが発生するが，キャッシュに存在するのはアドレスAのデータなので，ミス。アドレスBのデータはキャッシュに書き込まれ，メインメモリには追い出されたアドレスAに書き込みが発生する。

　よって，ライトスルーはＭＭＭＭＨ，ライトバックはＭＭＨＭＭとなり，正解は2.となる。

----

　さて，前述のようにキャッシュメモリにはメインメモリからの読み出しと，メインメモリへの書き戻しの2つ，キャッシュの中身の入れ替えを加えた3つの作業が発生しますが，それぞれの方法によって，いくつかの分類がなされています。

　まず，読み出しの方法による分類です。

・フルアソシアティブ方式

　各ラインにデータを格納する部分と，そのデータの存在するアドレス情報を格納するタグと呼ばれる部分を持ち，CPUが要求したアドレスとタグに書かれたアドレスの一致を確認する方式。
　キャッシュメモリの全ての部分にどのアドレスのデータも格納できるために効率が良く，ヒット率も高いが，総当たりをしなければならないので回路規模も大きくなり，速度も厳しくなる。

・ダイレクトマップ方式

　各ラインにデータの存在するアドレス情報をタグとして持つことは同じであるが，アドレスの中位ビットによって示されるインデックスによってラインが1つに決定される方式。回路規模も小さく，高速動作が可能だが，インデックスが同一でもアドレスが異なる場合はミスヒットとなり，データの入れ替えが頻繁に発生して大幅に速度が低下するという欠点がある。

・nウェイセットアソシアティブ方式

　フルアソシアティブ方式とダイレクトマップ方式の欠点を補う方式で，ダイレクトマップ式をn個並列に並べたもの。ダイレクトマップ式ではインデックスが同じものは1つしかキャッシュされなかったが，この方式ではn個がキャッシュされる。nは2や4が多いが，例えば各ウェイのラインが1つで，nがライン総数に等しい場合はフルアソシアティブ方式と同じ意味となる。

　とまあ，言葉で書いてもなかなかわかりにくいので，例を挙げてみましょう。アドレスが32ビット，1ワード32ビットのプロセッサを例に取ります。キャッシュの容量は256バイトとし，キャッシュの1ラインあたり1ワードすなわち4バイトを格納するものとして，3つの方式を書き表してみます。

(1)フルアソシアティブ方式の場合
キャッシュラインの構成　タグ部30ビット+データ部4バイト（32ビット）
ラインの本数　256 / 4 = 64本
アドレスの使い道　上位30ビットがタグの30ビットと比較される
　　　　　　　　　残った2ビットは各ラインに入っているバイトを示す

(2)ダイレクトマップ方式の場合
キャッシュラインの構成　タグ部24ビット+データ部4バイト（32ビット）
ラインの本数　256 / 4 = 64本（ということはインデックスは6ビット必要）
アドレスの使い道　上位24ビットをタグの24ビットと比較
　　　　　　　　　続く6ビットがどのラインに入っているかを示す
　　　　　　　　　残った2ビットは各ラインに入っているバイトを示す

(3)2ウェイセットアソシアティブ方式
キャッシュラインの構成　タグ部24ビット+データ部4バイト（32ビット）
ラインの本数　256 / 4 / 2 = 32本が2つ並列に存在，合計64本
アドレスの使い道　上位24ビットをタグの24ビットと比較
　　　　　　　　　続く1ビットがウェイの選択
　　　　　　　　　さらに続く5ビットがラインを示す（インデックス）
　　　　　　　　　残った2ビットは各ラインに入っているバイトを示す

(4)4ウェイセットアソシアティブ方式
キャッシュラインの構成　タグ部24ビット+データ部4バイト（32ビット）
ラインの本数　256 / 4 / 4 = 16本が4つ並列に存在，合計64本
アドレスの使い道　上位24ビットをタグの24ビットと比較
　　　　　　　　　続く2ビットがウェイの選択
　　　　　　　　　さらに続く4ビットがラインを示す（インデックス）
　　　　　　　　　残った2ビットは各ラインに入っているバイトを示す

　こうして具体例を並べてみると，言葉で書いてみるとややこしい話でも，32ビットあるアドレスの各ビットにどんな役割を与えるかという話だけになります。

　フルアソシアティブ方式だと，64本のキャッシュラインにどんなアドレスでも入る代わりに，比較は30ビット行う必要があります。それに，キャッシュの入れ替えを行う対象がキャッシュ全域に及ぶため，その判定に時間がかかります。

　これがダイレクトマップ式だとアドレスの比較は24ビットで済みますし，キャッシュの入れ替えは機械的に判断されますから楽ですが，アドレスの6ビットで入るキャッシュラインが決まっています。言ってみれば6ビットの比較があらかじめ済んでいる，ということでしょうか。

　4ウェイアソシアティブ方式では，ダイレクトマップ式においてキャッシュラインを決めていた6ビットのうち2ビットをウェイの切り替えに使っているので，インデックスは4ビットとなり，16本のラインが決まってしまいます。しかし4ウェイですので，同じインデックスでも4つまで格納できるというわけです。

　続いて，書き戻し方式による分類です。

・ライトスルー方式

　CPUからデータの書き出しを行う際に，キャッシュメモリと同時にメインメモリも逐一書き直す方式。通常はキャッシュにデータが存在しない場合にはメインメモリのみに書き込みを行うNo-write allocate方式を採用する。キャッシュとメインメモリとの間のデータの不一致が起きない代わりに，CPUからのデータ書き戻しには時間がかかってしまう。

　書き込み時に，そのアドレスのデータがキャッシュに存在した場合はヒットとなり，キャッシュとメインメモリの両方に書き込まれる。そのアドレスのデータがキャッシュに存在しない場合はミスとなり，メインメモリのみに書き込まれる。write allocate方式の場合には，ここでキャッシュにも書き込まれるが，その根拠である書かれたデータは次に読まれるはずというのは案外あてにならず，一般的ではない。

・ライトバック方式

　CPUからデータの書き出しを行う際に，キャッシュメモリだけを書き換える方式。当然キャッシュメモリとメインメモリの不一致が発生するが，不一致であるという事をとりあえず記録しておき，キャッシュの内容が入れ替えのために捨てられるときに，メインメモリにラインごと一括して書き込む。ライトバック方式では，write allicate方式が採用される。

　書き込み時に，そのアドレスのデータがキャッシュに存在した場合はヒットとなり，キャッシュのみに書き込まれ，メインメモリは更新されない。その代わり両者が不一致であることがタグに書き込まれ，このデータがキャッシュから追い出されるタイミングでメインメモリに書き込まれることを示しておく。

　そのアドレスのデータがキャッシュに存在しない場合はミスとなるが，まず最初にキャッシュのリフィル（入れ替え）を行い，そのアドレスの内容をキャッシュに取り込む。続けてキャッシュのデータを新しいデータで上書きし，不一致をタグに記録する。

　メインメモリへの書き込みは，そのアドレスがリフィルによってキャッシュから消されてしまう時で，この結果時間のかかる書き込みの回数が少なくできる。

　どちらが良いかは使い道に寄るところがあって，ライトスルー方式でもライトバッファを入れれば速度的な問題は起きにくい上に，回路も簡単でキャッシュとメモリとの不一致が原理的に起きませんから，小容量のキャッシュならメリットがあります。例えばCPUに内蔵される1次キャッシュに使うとおいしいです。

　これに対してライトバック方式ですが，なんと言ってもメモリへのアクセス回数が減りますから，例えばマルチプロセッサなどバスマスタが複数ある場合にはバスが効率よく使えるので有利です。

　最後に，キャッシュの入れ替えに関する分類です。

・LRU方式

　Least Recently Used方式の略で，最も古くアクセスされたデータを捨てて入れ替える方法。新しいものほど良く使われるだろうという局所性を根拠としている。効率の良い方法ではあるが，アクセスの履歴を取らねばならず，タイミングが厳しい。

・ラウンドロビン方式
　データを履歴によらず，順番に捨てて入れ替える方式。取り込みの古いデータから捨てるという根拠による。回路が簡単というメリットがある一方，使用頻度が考慮されず，ヒット率の高いデータでも捨てられることになってしまうので，効率は悪い。

・ランダム方式
　捨てるデータをランダムに選ぶ方式であるが，これはどのデータも平均的に使われる（使われない）だろうという根拠に基づく。効率はそれほど良くないがなんといっても回路が簡単である。

　注目すべき点は，ダイレクトマップ式の場合には，同じインデックスのデータが来たら無条件にそのラインを捨てて書き換えるので，こうした入れ替えの仕組みを持つ必要がないということです。

　しかし，nウェイセットアソシアティブ方式ではn個あるウェイのうちどちらを捨てるのか決めねばなりませんし，フルアソシアティブ方式に至ってはたくさんあるラインの内どれを捨てるか決めねばなりません。

　当然，良くヒットしているものを捨ててしまっては効率が落ちますから，それなりの理由で捨てるものを選ぶ必要があるわけですが，それが複雑になってしまってはCPUの処理速度全体の足を引っ張ってしまいます。

　一方，ダイレクトマップ式では捨てるデータが決まっていることから一見すると合理的ですが，同じインデックスで異なるアドレスを交互にアクセスするようなケースでは，毎回キャッシュの入れ替えが起こってしまうという最悪の事態が起こります。

　このように，キャッシュメモリというのはなかなか複雑で，データの読み込み方，データの捨て方，データの書き戻し方の3つの分類による組み合わせで，様々なものが考え出されます。データと命令をそれぞれ別のキャッシュ取り込むことや，キャッシュの容量，キャッシュの階層を分けることなど，さらにたくさんのバリエーションが存在するのは，それだけキャッシュメモリにはお金がかかり，メインメモリ全部がCPUと同じ速度で動作するという理想にほど遠いことを示していると言えるかも知れません。