キャッシュの仕組みに関する具体的な解説

キャッシュの仕組みに関する具体的な解説 ハードウェアで実装されたハッシュテーブル 2019.03.30 KO | EN 局所性の原理 キャッシュ キャッシュの指標 キャッシュの構成 インデックス タグマッチング タグのオーバーヘッド 連想キャッシュ セット連想キャッシュの構成 具体例 キャッシュへの書き込みの処理 ソフトウェアのリファクタリング 参考文献 技術が進歩するにつれて、プロセッサの速度は急速に向上しましたが、メモリの速度はそれに追いついていません。プロセッサがいかに高速であっても、メモリの応答が遅ければシステム全体が遅くなります。これを解決するのがキャッシュです。 キャッシュはCPUチップの内部にある、小さくて高速なメモリです（高価でもあります）。毎回メインメモリにデータを取りに行くのは遅いため、キャッシュは頻繁に使用されるデータを保持し、プロセッサがメインメモリではなくキャッシュからそのデータにアクセスできるようにすることで、処理速度を向上させます。 局所性の原理 「頻繁に使用される」データの判断は、局所性の原理に従います。これは時間的局所性と空間的局所性に分けられます。 時間的局所性とは、最近アクセスしたデータに再びアクセスする傾向のことです。例えば、ループのインデックスとして使われる変数iは、短い期間内に数回アクセスされます。 for (i = 0; i < 10; i += 1) { arr[i] = i; } 空間的局所性とは、最近アクセスしたデータの近くにあるデータに再びアクセスする傾向のことです。上記のループでは、配列arrの各要素にアクセスする際に、次々とメモリ上の近いアドレスにアクセスします。これは、配列の要素がメモリ上で連続して割り当てられるためです。 単一のプロセス内でも、頻繁に使われる部分とそうでない部分があるため、オペレーティングシステムはプロセスをページと呼ばれる単位に分割して管理します。上の図はページ参照のトレースです。横軸は実行時間、縦軸はメモリアドレスです。横方向に長い参照の列は、長期間にわたって同じメモリアドレスが参照されたことを意味し、縦方向に長い列は、短時間で近接したメモリアドレスが参照されたことを意味します。ページアクセスにも局所性の原理が当てはまることがわかります。 キャッシュ CPUチップにはいくつかのキャッシュが含まれており、それぞれが独自の目的と役割を持っています。 +-------------+------+------+ +---------------+ +--------+ | | I$ | | <-- | | | Disk | | + Processor +------+ L2 | | <-- | + Main Memory | | | | | D$ | | --> | | | | +-------------+------+------+ +---------------+ +--------+ L1キャッシュ: プロセッサに最も近いキャッシュです。速度を重視するため、I$とD$に分割されています。 命令キャッシュ (I$): メモリのTEXTセグメントのデータを扱うキャッシュです。 データキャッシュ (D$): TEXTセグメント以外のすべてのデータを扱うキャッシュです。 L2キャッシュ: より大容量のキャッシュです。サイズを考慮して、L1キャッシュのように分割されていません。 L3キャッシュ: マルチコアシステムで複数のコアによって共有されるキャッシュです。 今日、キャッシュはCPUチップ面積の30%から70%を占めています。1989年に製造されたシングルコアプロセッサi486には、8KBのI/Dキャッシュが1つしかありませんでした。一方、Intel Core i7クアッドコアチップのダイマップを見ると、4つのコアそれぞれに256KBのL2キャッシュがあり、さらに全コアで共有される8MBのL3キャッシュがあります（L2キャッシュの上にある領域はL1キャッシュのように見えますが、確信が持てなかったためラベル付けしていません）。 キャッシュの指標 キャッシュのパフォーマンスを測定する際には、ヒットレイテンシとミスレイテンシが重要な要因として考慮されます。 CPUが要求するデータがキャッシュ内に存在する場合、それをキャッシュヒットと呼びます。ヒットレイテンシは、ヒット時にキャッシュされたデータを取得するのにかかる時間です。要求されたデータがキャッシュ内に存在しない場合、それをキャッシュミスと呼び、ミスレイテンシは、ミス時に上位レベルのキャッシュ（例えば、L1キャッシュにデータがなくL2キャッシュで検索する場合）またはメモリからデータを取得するのにかかる時間です。 平均アクセス時間は次のように計算されます。 Miss rate = Cache misses / Cache accesses Average access time = Hit latency + Miss rate × Miss latency ミス率 = キャッシュミス数 / キャッシュアクセス数 平均アクセス時間 = ヒットレイテンシ + ミス率 × ミスレイテンシ キャッシュのパフォーマンスを向上させるには、ヒットレイテンシを減らすためにキャッシュを縮小する、ミス率を減らすためにキャッシュを拡大する、またはレイテンシを減らすために高速なキャッシュを使用するという方法があります。 キャッシュの構成 キャッシュは、高速応答性のSRAM（Static Random Access Memory）で構成されています。アドレスをキーとして与えると、対応する場所を即座にアクセスできます。DRAM（Dynamic Random Access Memory）も同様の特性を持ちますが、ハードウェア設計上、DRAMはSRAMよりも遅いです。「メインメモリ」と言う場合、通常はDRAMを指します。 アドレスをキーとして与えられたときに場所を即座にアクセスできるということは、キャッシュは本質的にハードウェアで実装されたハッシュテーブルであることを意味します。キャッシュが高速である理由は、頻繁に使用されるデータのみを保持しているからだけでなく、ハッシュテーブルの時間計算量がO(1)オーダーで高速であるためでもあります。 キャッシュはブロックで構成されています。各ブロックはデータを保持し、アドレスをキーとしてアクセスできます。ブロックの数とブロックサイズがキャッシュのサイズを決定します。 インデックス アドレス全体をキーとして使用するのではなく、その一部が使用されます。例えば、1,024個のブロックと32バイトのブロックサイズの場合、32ビットのアドレスは次のようにインデックス付けできます。 ここで、フルアドレスの下位5ビットがオフセットとして使用され、次の10ビットがブロックにアクセスするためのインデックスとして使用されます。インデックスが10ビットである理由は、2^n個のブロックの各インデックスを表すにはlog2(ブロック数)ビットが必要だからです。ここでは2^10 = 1024個のブロックがあるため、log2(1024) = 10となり、10ビットがインデックスビットとして使用されます（オフセットビットについては後ほど説明します）。 しかし、これだけでは異なるデータが同じインデックスを共有するリスクが大きすぎます。 タグマッチング インデックスの衝突を減らすために、アドレスの一部がタグとして使用されます。1,024個のブロック、32バイトのブロックサイズがあり、32ビットアドレス0x000c14B8にアクセスすると仮定します。 まず、インデックス（0010100101）に対応するタグ配列のフィールドにアクセスします。 次に、そのタグフィールドの有効ビット（valid bit）を確認します。 有効ビットが1の場合、タグフィールド（00000000000011000）とアドレスのタグ（00000000000011000）が等しいかどうかを比較します。 比較結果（真、1）と有効ビット（1）をAND演算します。 有効ビットが1であることは、そのブロックに有効な値が存在することを意味します。タグフィールドとアドレスのタグが一致し、有効ビットが1であるため、上記の例の結果はヒットです。ヒットした場合、そのインデックスのデータはデータ配列から参照されます（参考までに、データ配列とタグ配列はどちらもハードウェアです）。 有効ビットが0の場合、そのブロックには値がないか無効な値があることを意味するため、ミスが発生します。その場合、アドレスのタグがタグフィールドに書き込まれ、上位レベルのキャッシュまたはメモリから要求された値がフェッチされ、データフィールドに書き込まれ、有効ビットが1に変更されます。 有効ビットが1であっても、タグが一致しない場合はミスが発生します。その場合、どのように処理されるかは、置換ポリシーに依存します。FIFO（First-In First-Out）ポリシーを使用する場合、最初に格納されたデータが最初に置き換えられるため、既存のブロックは常に置き換えられます。タグ配列のフィールドはアドレスのタグに変更され、上位レベルのキャッシュまたはメモリから要求されたデータがフェッチされ、データフィールドの値が新しいデータに置き換えられます（実際には、要求されたデータだけでなく、その周辺のデータもフェッチされます）。既存のデータは上位レベルのキャッシュに押し出されます。 アドレスの上位15ビットがタグビットとして使用される理由は、タグビットの数は「アドレスビット数 - (log2(ブロックサイズ) + インデックスビット数)」によって決まるからです。この場合、32 - (5 + 10) = 17ビットがタグビットとして使用され、残りの5ビットがオフセットビットとして使用されます。 タグのオーバーヘッド タグ配列を追加すると、より多くのスペースが必要になります。しかし、「32KBキャッシュ」とは、依然として32KBのデータを格納できるキャッシュを意味します。Tha