記憶階層・キャッシュ
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
これまでパイプラインなどを通して制御の流れに着目してきた。今回は記憶装置であるメモリに焦点を当てる。
命令パイプラインとメモリ
上図のパイプラインにおいて、命令メモリからの命令のフェッチと、データメモリへの読み書きが同じ1クロックで行われている。
メモリはレジスタと異なり、アクセスに時間がかかる。メモリへのアクセス時間が長くなる場合、全体のスループットは最も長いステージの処理時間で決定されるので、メモリへのアクセス時間の短縮が大きな課題となる。
- 理想的なメモリ
- 容量は無限大の大容量
- アクセス時間は最短で高速アクセス
- 単純なアドレシングでアクセスできる
- 現実のメモリ
- 大容量と高速アクセスは両立しない（容量が大きくなればなるほど、アクセス時間が長くなってしまう。）
上記に示すように、メモリの理想と現実には乖離がある。そのため、「高速小容量のメモリ」と「低速大容量のメモリ」を組み合わせる、記憶階層を用いることで実質的に「高速大容量メモリ」の機能を実現する。
記憶階層
記憶システムは、上図のような階層構造をとる。すなわち、CPUに近い方のレベルをその下のレベルの部分集合とする。一番下のレベルには全てのデータを格納する。CPUに近い方のレベルを上位レベルといい、CPUから遠い方のレベルを下位レベルという。上位レベルのメモリは下位レベルのメモリよりも小さくて高速である。両レベル間で取り交わすデータの最小単位をブロックまたはラインと呼ぶ。下位レベルのメモリでよく使われる命令やデータを上位のメモリにコピー（データ転送）しておく。CPUから取り出しの命令があった場合には、まず上位のメモリを調べてそこにデータがあればそのデータをCPUに取り出す。
- レジスタ：CPU内部にある、演算や実行状態の保持に用いる記憶装置。
- キャッシュメモリ（L1, L2）：主記憶装置より高速にアクセス可能な記憶装置。使用頻度の高いデータや命令を保持しておくことで、相対的に低速な主記憶装置へのアクセスを減らすことができ、処理を高速化することができる。
- 主記憶装置（メインメモリ、RAM）：CPUの命令によって直接読み書きが可能な記憶装置。実行中の命令やデータを保持しておく。
- ディスクキャッシュ：補助記憶装置より高速にアクセス可能な記憶装置。キャッシュメモリ同様に、使用頻度の高いデータを複製して格納しておくことで、処理を高速化することができる。
- 補助記憶装装置：ハードディスク、フラッシュメモリなどの記憶装置。
局所性
記憶階層がアクセス時間の短縮（高速化）に有効なのは、命令やデータに局所性（locality）があるためである。
- 空間局所性（Spacial Locality）
- あるロケーションにあるデータが参照されると、そのアドレスの近傍にあるデータが間もなく参照される傾向がある、という局所性の法則
- 通常プログラムの上から下に順番に実行される、命令アクセス
- 配列要素の逐次アクセス
- 入れ子構造の引数、ローカル変数など
- 時間局所性（Temporal Locality）
記憶階層と機械語プログラム
メモリには各階層があり、それぞれにアドレスが存在し、各階層間でデータのやり取り（データ転送、読み取り、書き込み）が発生する。この記憶階層を意識して、最良のメモリの利用方法を考えて、全てプログラムするのはかなり骨が折れる作業である。プログラマとしては、高速で大容量のメモリが一つだけあるものとしてプログラムを書き、ハードウェアの機構でどの階層のメモリをどう使って局所性を活かすかを決めることが望ましい。
単純に命令セットだけを意識してプログラムを書いておけば、効率や安全性はハードウェアが勝手に面倒を見てくれる。この性質を透過性（transparency）と呼ぶ。
キャッシュメモリ
キャッシュメモリは、レジスタと主記憶装置との間にあるメモリである。
- CPUが主記憶装置からデータを読み込もうとする。
- キャッシュメモリにデータがないので、主記憶装置からデータをキャッシュメモリに転送する。この際、必要なデータのみでなく、空間的局所性を考慮して、まとまった単位でデータ転送を行う。
- キャッシュメモリからCPUにデータが読み出される。
- 再度、同じデータを読み込もうとした際には、すでにキャッシュメモリにデータがあるので、主記憶装置にアクセスすることなく、キャッシュメモリのみが参照されデータが読み出される。
用語整理
- ヒット：CPUから要求されたデータが上位レベルのどこかのブロックの中に存在すること
- ミス：上位レベルのどこにも求めるデータが見つからないこと
- ヒット率：記憶階層のあるレベルでメモリへのアクセスがヒットする割合。記憶階層の性能の測定値として使われることが多い。
- ミス率：記憶階層のあるレベルでメモリへのアクセスがヒットしない割合。1－(ヒット率)で求めることができる。
- ヒット時間：記憶階層のあるレベルにアクセスするのに要する時間。この時間にはアクセスがヒットするかミスするかの判定に必要な時間を含む。
- ミス・ペナルティ：記憶階層のあるレベルでキャッシュ・ミスが発生したときに、その下位のレベルからブロックを取り出すのにかかる時間。該当のブロックにアクセスし、それを記憶階層間で転送し、 該当のレベルに収め、ブロックを要求元に引き渡すのにかかる時間が含まれる。
次に、複数のデータを参照し、キャッシュメモリがいっぱいになった場合を考える。
- キャッシュメモリにないデータの読み出し命令があり、主記憶装置からキャッシュメモリにデータを転送しようとした場合に、キャッシュメモリにデータが入らない場合、衝突が発生する。
- 衝突が発生すると、古いデータがキャッシュから追い出される。（追い出し）
- キャッシュメモリの空いたメモリに、新しいデータが転送される。（再コピー）
衝突が発生した場合に、主記憶装置へのデータ転送（書き戻し）を行う必要があるか否かは、CPUの書き込み命令（store）の対応方法によって決定される。
ライトスルー方式とライトバック方式
キャッシュメモリは主記憶装置のデータをコピーしているので、データの読み出し命令（load）に対して主記憶装置の操作は不要である。しかしながら、データの書き込み命令（store）に対しては、新しいデータを主記憶装置にも書き込む必要がある。この書き戻しのタイミングによって、以下の2つに分類される。
- ライトスルー方式（write through）
- ストア命令がくる度に、キャッシュメモリだけでなく、主記憶装置にもデータを書き込む。
- 主記憶装置はキャッシュの10倍以上は遅いので、実行効率が落ちる。
- 主記憶装置への書き込み速度の問題は、ライトバッファ（write buffer）と呼ばれる高速のメモリを別途設けることで解決するのが一般的である。
- キャッシュから追い出される際のメモリへの書き戻しが不要。よって、新たにキャッシュラインを主記憶装置から読み出す時のコストが低い。
- ストア命令がくる度に、キャッシュメモリだけでなく、主記憶装置にもデータを書き込む。
- ライトバック方式（write back）
キャッシュのマッピング
キャッシュのブロックをどのようにキャッシュメモリに配置するかで、以下の3つの方式がある。
- ダイレクトマップ方式
- あるインデックスに対して一意にラインのキャッシュの位置が決まる
- フルアソシアティブ方式
- インデックスが存在せず、全てのキャッシュラインのタグと比較する
- セットアソシアティブ方式
ダイレクトマップ方式
ダイレクトマップ方式では、あるインデックスに対して一意にラインのキャッシュの位置が決まる。キャッシュ上の位置が特定されても、ここにあるキャッシュラインが求めるものかどうかは以下の条件を満たす必要がある。
また、キャッシュラインの大きさが4語なので、キャッシュライン内オフセットの2ビット（00, 01, 10, 11）を使用しMUXに入力し、キャッシュラインからいずれか一つのデータ語を選択する。ただし、MIPSアーキテクチャでは、各アドレスの最下位2ビットは語内のバイト・オフセット指定に使用される。そのため、最下位2ビットをキャッシュラインの選択用に使用することはできない。
もしタグが等しくない場合は、キャッシュミス（cache miss）が起こったという。キャッシュミスが起こった場合は、アクセスしているキャッシュラインを、タグとインデックスの値を見て主記憶装置に書き戻し、代わりに求めるキャッシュラインを主記憶装置からキャッシュメモリに読み出す。
キャッシュミス（3C）
キャッシュミスには、以下の3種類があり、「三つのC」と呼ばれることもある。
- 初期参照ミス（compulsory miss, cold start miss）
- まだキャッシュに読み込まれていないキャッシュラインを最初にアクセスした時に発生するミス
- コールド・スタート・ミスとも呼ぶ
- [対策]キャッシュラインの大きさを大きくする
- キャッシュラインの数が減るので、初期参照の数が少なくなる
- 空間的局所性に起因するミス率が低下する
- キャッシュラインを大きくしすぎると、ミスが発生した場合のペナルティが大きくなり、性能低下に繋がる可能性がある
- 競合性ミス（conflict miss, collision miss）
- 同じインデックスを持つ異なるキャッシュラインにアクセスすることで起こるミス
- コリジョン・ミスとも呼ぶ
- [対策]連想度を上げることで競合性ミスは軽減される
- 連想度とは任意のインデックスで複数のキャッシュラインの集合にアクセスできる場合のラインの数である
- 連想度を上げることでアクセス速度が遅くなるので、全体的な性能の低下を招く可能性がある
- 容量性ミス（capacity miss）
キャッシュミスが発生すると、CPUでの演算の実行を一時止め、メモリとキャッシュの間でキャッシュラインの交換をしてから実行を再開することになる。
フルアソシアティブ方式
フルアソシアティブ方式には、インデックスは存在せず、参照されるごとに全てのキャッシュラインのタグがメモリアドレス内のタグと比較される。どれか一つのタグが等しければヒットであり、対応するラインの語が読み出される。一致するタグがない場合、キャッシュメモリの空いている任意の場所に主記憶装置からキャッシュラインが読み込まれ、その上で読み書きが行われる。
メリット
- インデックスが存在しないので、競合性ミスは発生しない。
デメリット
- キャッシュ上のタグの容量が大きくなり、タグ比較などの回路が膨大になってしまい、ハードウェアのコストが増大する。
- すべてのキャッシュラインを検索するので、ゲート遅延が大きくなり、パイプライン動作時のクロックの長さを伸ばしてしまう可能性が高い。
以上のことから、フルアソシアティブ方式は小規模のキャッシュに用いられることが多い。
セットアソシアティブ方式
セットアソシアティブ方式は、ダイレクトマップ形キャッシュでインデックスの指す先に複数のキャッシュラインを格納するものである。一つのインデックスに対応するキャッシュラインの集合をセットと呼ぶ。セットの大きさを"A"とするとき、Aを連想度（associativity）と言い、このキャッシュをAウェイ・セットアソシアティブ形のキャッシュと呼ぶ。上図の場合は、1つのインデックスで2つのキャッシュラインを指し示すので、2ウェイ・セットアソシアティブ形キャッシュである。
セットアソシアティブ方式は、フルアソシアティブ方式と比較して、タグ比較回路などの回路が小さくてすみ、ゲート遅延も小さい。また、ダイレクトマップ方式と比較して、整合性ミスが少なくなる。
# (ライン数) = (セット数) × (連想度) L = S × A # ダイレクトマップ方式 A = 1 # フルアソシアティブ方式 A = L
キャッシュの入ったCPU
これまでメモリで実装していた部分にキャッシュメモリを追加する。一般的に命令用のキャッシュとデータ用のキャッシュは別々に設ける。
- 命令キャッシュ（instruction cache）
- 読み出しのみ
- 書き込みを行わないため、書き戻しの機構が不要
- データキャッシュ（data cache）
- 読み出しと書き込みの両方を行う
別々に分ける理由は、パイプライン動作時に命令フェッチとデータのロード・ストアの間でキャッシュアクセスの競合を発生させないためである。
まとめ
Webブラウザのキャッシュはなんとなく理解できていたが、今回CPUのキャッシュメモリに関して整理することができた。
| ダイレクトマップ | セットアソシアティブ | フルアソシアティブ | |
|---|---|---|---|
| 連想度 | 1 | A(2,4,..) | =ライン数 |
| セット数 | =ライン数 | S | 1 |
| ハードウェア | 少 | 中 | 多 |
| ゲート遅延 | 小 | 中 | 大 |
| 競合性ミス | 多 | 少 | なし |
