HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

A concrete explanation of how a cache works (parksb.github.io)

24 pointsby parksb2 コメント

要約

キャッシュはCPU内部にある小容量・高速なメモリで、CPUとメインメモリの速度差を埋め、頻繁に使用されるデータを保持することでシステム全体の高速化を図ります。その効果は、過去にアクセスしたデータやその周辺データに再びアクセスする傾向(局所性)に基づいています。キャッシュはハッシュテーブルのようにアドレスの一部を使ってデータを特定し、タグマッチングによってデータの一致を確認することで動作します。

全文翻訳

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

ハードウェアで実装されたハッシュテーブル

30.03.2019

KO | EN

技術の進歩に伴い、プロセッサの速度は急速に向上しましたが、メモリの速度は追いついていません。プロセッサがいかに高速であっても、メモリの応答が遅ければシステム全体が遅くなります。これを解決するデバイスがキャッシュです。

キャッシュは、CPUチップの内部にある小さく高速なメモリです。(高価でもあります。)毎回メインメモリにデータを取りに行くのは遅いため、キャッシュは頻繁に使用されるデータを保持し、プロセッサがメインメモリではなくキャッシュからそのデータにアクセスできるようにすることで、処理速度を向上させます。

局所性の原理

「頻繁に使用される」データを判断する基準は、局所性の原理に従います。これは時間的局所性と空間的局所性に分けられます。

時間的局所性とは、最近アクセスされたデータに再びアクセスする傾向のことです。例えば、ループのインデックスとして機能する変数 i は、短い期間内に数回アクセスされます。

for (i = 0; i < 10; i += 1) {
  arr[i] = i;
}

空間的局所性とは、最近アクセスされたデータの近くにあるデータに再びアクセスする傾向のことです。上記のループでは、配列 arr の各要素にアクセスする際に、次々とメモリ上の近い位置にあるアドレスにアクセスします。これは、配列の要素がメモリ上で連続して割り当てられるためです。

単一のプロセス内でも、一部の領域は頻繁に使用され、他の領域はそうでないため、オペレーティングシステムはプロセスをページと呼ばれる単位に分割して管理します。上の図はページ参照のトレースです。横軸は実行時間、縦軸はメモリのアドレスです。横方向の参照の連続は、同じメモリアドレスが長期間参照されたことを意味し、縦方向の連続は、近いメモリアドレスが同時に参照されたことを意味します。ページアクセスにも局所性の原理が当てはまることがわかります。

キャッシュ

CPUチップには複数のキャッシュが含まれており、それぞれが独自の目的と役割を持っています。

+-------------+------+------+     +---------------+     +--------+
|             |  I$  |      | <-- |               | <-- |        |
+  Processor  +------+  L2  |     |  Main Memory  |     |  Disk  |
|             |  D$  |      | --> |               | --> |        |
+-------------+------+------+     +---------------+     +--------+
  • L1キャッシュ: プロセッサに最も近いキャッシュです。速度のために、I$とD$に分割されています。
    • 命令キャッシュ (I$): メモリのTEXTセグメントのデータを扱うキャッシュです。
    • データキャッシュ (D$): TEXTセグメント以外のすべてのデータを扱うキャッシュです。
  • L2キャッシュ: より大容量のキャッシュです。サイズを考慮して、L1キャッシュのように分割されていません。
  • L3キャッシュ: マルチコアシステムで複数のコアによって共有されるキャッシュです。

[画像: Intel Core i7 クアッドコアチップのダイマップ。]

今日、キャッシュは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)オーダーで高速であることにもあります。

A cache is made up of blocks. Each block holds data and can be accessed using an address as a key. The number of blocks and the block size determine the cache’s size.

インデックス

アドレス全体をキーとして使用するのではなく、その一部が使用されます。例えば、1,024個のブロックと32バイトのブロックサイズの場合、32ビットのアドレスは次のようにインデックス付けできます。

[画像: インデックスを介したデータアクセス。]

ここでは、フルアドレスの下位5ビットがオフセットとして使用され、次の10ビットがブロックにアクセスするためのインデックスとして使用されます。インデックスが10ビットなのは、2^n個のブロックの各インデックスを表すには log2(blocks) ビットが必要だからです。ここでは 2^10 = 1024 個のブロックがあるため、log2(1024) = 10 となり、10ビットがインデックスビットとして使用されます。(オフセットビットについては後で説明します。)

しかし、これだけでは、異なるデータが同じインデックスを共有するリスクが大きすぎます。

タグマッチング

インデックスの衝突を減らすために、アドレスの一部がタグとして使用されます。1,024個のブロック、32バイトのブロックサイズがあり、32ビットアドレス 0x000c14B8 にアクセスするとします。

[画像: インデックスとタグを介したデータアクセス。]

  1. まず、インデックス(0010100101)に対応するタグ配列のフィールドにアクセスします。
  2. 次に、そのタグフィールドの有効ビット(valid bit)を確認します。
  3. 有効ビットが 1 の場合、タグフィールド(00000000000011000)とアドレスのタグ(00000000000011000)が等しいか比較します。
  4. 比較結果(true、1)と有効ビット(1)を論理積(AND)します。

有効ビットが 1 であることは、そのブロックに有効な値が存在することを意味します。タグフィールドとアドレスのタグが一致し、有効ビットが 1 であるため、上記の例の結果はヒットです。ヒットした場合、データ配列からそのインデックスのデータが参照されます。(参考までに、データ配列とタグ配列はどちらもハードウェアです。)

有効ビットが 0 の場合、そのブロックには値がないか無効な値であるため、ミスが発生します。その場合、アドレスのタグがタグフィールドに書き込まれ、上位レベルのキャッシュまたはメモリから要求された値が取得されてデータフィールドに書き込まれ、有効ビットが 1 に変更されます。

有効ビットが 1 であっても、タグが一致しない場合はミスが発生します。その場合、どのように処理されるかは、置換ポリシーによって異なります。FIFO(First-In First-Out)ポリシー、つまり最初に入ってきたデータが最初に置き換えられるポリシーを使用する場合、既存のブロックは常に置き換えられます。タグ配列のフィールドはアドレスのタグに変更され、上位レベルのキャッシュまたはメモリから要求されたデータが取得されてデータフィールドの値が新しいデータに置き換えられます。(実際には、要求されたデータだけでなく、その周辺のデータも取得されます。)既存のデータは上位レベルのキャッシュに押し上げられます。

アドレスの上位15ビットがタグビットとして使用される理由は、タグビット数は アドレスビット数 - (log2(ブロックサイズ) + インデックスビット数) で決まるからです。この場合、32 - (5 + 10) = 17 ビットがタグビットとして使用され、残りの5ビットがオフセットビットとして使用されます。

タグのオーバーヘッド

タグ配列を追加すると、より多くのスペースが必要になります。しかし、「32KBキャッシュ」とは、依然として32KBのデータを格納できるキャッシュを意味します。これは、タグ用のスペースがブロックサイズとは独立したオーバーヘッドとして扱われるためです。

1,024個の32Bブロックで構成される32KBキャッシュのタグオーバーヘッドを計算してみましょう。

17ビットタグ + 1ビット有効ビット = 18ビット
18ビット × 1024 = 18Kb タグ = 2.25KB

つまり、7%のタグオーバーヘッドが発生します。

スペースコストだけでなく、時間コストもあります。ヒットを確認するためにタグ配列にアクセスし、その後データ配列にアクセスしてデータを取得するため、ヒットレイテンシが増加します。

そのため、2つのステップは並列で実行されます。タグ配列がヒットの確認中に、データ配列は事前にアクセスされます。これによりヒットレイテンシは減少しますが、ミスが発生した場合の無駄なリソースを許容する必要があります。

アソシアティブキャッシュ

2つの異なるアドレスが同じインデックスを持つ場合、衝突が発生し、置換ポリシーに従ってブロックが置き換えられます。しかし、衝突ごとにキャッシュの内容を変更すると、ミスが増加し、単一のスロットの内容が無限にスワップされる「ピンポン問題」を引き起こす可能性があります。

この問題は、複数のタグ配列とデータ配列を作成することで改善できます。つまり、インデックスは複数のブロックを指すようになります。インデックスが指すブロックの数によってキャッシュを分類すると、次のようになります。

  • ダイレクトマップ(Direct mapped): インデックスは単一のスロットを指します。処理は高速ですが、衝突が頻繁に発生します。
  • フルアソシアティブ(Fully associative): インデックスはすべてのスロットを指します。衝突は少ないですが、すべてのブロックを検索する必要があるため遅いです。
  • セットアソシアティブ(Set associative): インデックスは2つ以上のスロットを指します。これはn-wayセットアソシアティブキャッシュと呼ばれます。

ダイレクトマップキャッシュとフルアソシアティブキャッシュの長所と短所は極端であるため、通常はセットアソシアティブキャッシュが使用されます。

セットアソシアティブキャッシュの組織構造

2-wayセットアソシアティブキャッシュがどのように機能するかを簡単に見てみましょう。

[画像: 2-wayセットアソシアティブキャッシュの仕組み。]

アドレスのインデックスを使用してブロックにアクセスする方法は、これまで見てきたダイレクトマップキャッシュと同じです。違いは、2つのウェイがあるため、データがキャッシュされているかどうかの確認は、1つだけでなく両方のブロックを確認する必要があることです。最後に、2つのウェイの結果を論理和(OR)することで最終結果が得られます。すべてのウェイでミスが発生した場合、置換ポリシーに従ってデータがいずれか一方のブロックに書き込まれます。

ダイレクトマップキャッシュと比較して、衝突の可能性を減らす代わりにヒットレイテンシが増加します。

具体的な例

2バイトのキャッシュブロックで構成される8バイトの2-wayキャッシュがあり、4ビットのアドレスが与えられたとします。

[画像: 0001 を参照。]

メモリのアドレス 0001 を参照する命令が実行されます。インデックスビットは log2(2) = 1 で、タグビットは 4 - (log2(2) + 1) = 2 です。最後に、オフセットビットは1になります。したがって、アドレス 0001 のインデックスは0で、タグは00です。これは、そのメモリ位置のデータがインデックス 0 を持つ2つのスロットのいずれかにキャッシュできることを意味します。

[画像: 0001 と 0010 をキャッシュ。]

Way 0 のブロックは空いているため、データは Way 0 のインデックス 0 を持つブロックに格納されました。キャッシュヒット率を上げるために、参照されたデータ(0001)の隣にあるメモリ位置 0010 のデータも、完全なキャッシュブロック(2B)単位で取得されて同時にキャッシュされました。(これは空間的局所性を利用しています。)

[画像: 0101 を参照。]

メモリのアドレス 0101 を参照する命令が実行されます。再び、インデックスが 0 である2つのスロットのいずれかに入ることができます。

[画像: 0101 と 0110 をキャッシュ。]

しかし、Way 0 のインデックス 0 を持つブロックには既にデータが格納されているため、新しいデータは空いている Way 1 にキャッシュされます。ここでも、隣接する 0110 のデータが一緒にキャッシュされました。Way 0 の2つのブロックのLRU(Least Recently Used)値も増加しました。LRUは、最近最も使用されていないデータを優先的に置き換えるポリシーであり、オペレーティングシステムのプロセススケジューリングやページ置換アルゴリズムでも使用されます。LRU値が高いほど、キャッシュミスが発生した場合に最初に置き換えられる可能性が高くなります。

[画像: 1000 を参照。ミスが発生。]

次に、メモリのアドレス 1000 を参照する命令が実行されます。インデックス 0 を持つ両方のブロックがチェックされましたが、タグ 10 を持つデータは存在しなかったため、キャッシュミスが発生しました。

[画像: 0111 と 1000 をキャッシュ。]

そのため、キャッシュされたデータが置き換えられます。2つのスロットのうち、Way 0 のブロックはLRU値が高いため、Way 0 の最初のブロックが置き換えられ、参照されたため、そのLRU値は 0 にリセットされました。(LRU値はキャッシュヒット時にもリセットされます。)同じ原理で、参照されたデータの隣にある 0111 のデータもキャッシュされました。Way 1 の2つのブロックは今回参照されなかったため、LRU値は増加しました。

キャッシュへの書き込み処理

操作が読み取りではなく書き込みであり、データが変更されるアドレスが既にキャッシュされている場合(書き込みヒット)、メモリ内のデータではなくキャッシュブロック内のデータが更新されます。ここで、「キャッシュで更新されたデータをいつメモリに書き込むべきか?」という疑問が生じます。書き込みポリシーには2つあります。

1つはライトスルー(write-through)方式です。データがキャッシュに書き込まれるたびに、メモリ内のデータも更新されます。これにより多くのトラフィックが発生しますが、メモリとキャッシュのデータは常に同一に保たれます。

もう1つはライトバック(write-back)方式で、ブロックが置き換えられるときにのみメモリ内のデータが更新されます。データが変更されたかどうかを確認するために、各キャッシュブロックにdirtyビットを追加し、データが変更されたときに1に設定する必要があります。後でそのブロックが置き換えられる際に、dirtyビットが1であればメモリ内のデータが更新されます。

変更されるデータのアドレスがキャッシュされていない場合(書き込みミス)、ライトアロケート(write-allocate)方式が使用されます。当然ながら、ミスが発生したときにデータはキャッシュされます。ライトアロケートをスキップすると、その時点ではリソースを節約できますが、キャッシュの目的は達成されません。

ソフトウェアのリファクタリング

これまでは低レベルでのキャッシュの構造と動作を見てきましたが、コードレベルでもキャッシュ効率を向上させることができます。以下のネストされたループを見てみましょう。

for (i = 0; i < columns; i += 1) {
  for (j = 0; j < rows; j += 1) {
    arr[j][i] = pow(arr[j][i]);
  }
}

このループは2次元配列の各要素を二乗します。一見問題なさそうですが、空間的局所性の観点からは非効率なコードです。なぜなら、配列 arr の要素はメモリ上に連続して格納されていますが、アクセスはシーケンシャルではないからです。

0          4          8          12         16         20         24
+----------+----------+----------+----------+----------+----------+
|  [0, 0]  |  [0, 1]  |  [0, 2]  |  [1, 0]  |  [1, 1]  |  [1, 2]  |
+----------+----------+----------+----------+----------+----------+
  1. i = 0, j = 0: 最初のスロット [0, 0] にアクセスします。
  2. i = 0, j = 1: 4番目のスロット [1, 0] にアクセスします。
  3. i = 1, j = 0: 2番目のスロット [0, 1] にアクセスします。

ご覧のように、アクセスはメモリ上を飛び回ります。したがって、以下のコードのように、外側のループは rows を、内側のループは columns をイテレートするようにすべきです。

for (i = 0; i < rows; i += 1) {
  for (j = 0; j < columns; j += 1) {
    arr[i][j] = pow(arr[i][j]);
  }
}

時間的局所性を活用する同様の例があります。以下のループを見てみましょう。

for (i = 0; i < n; i += 1) {
  for (j = 0; j < len; j += 1) {
    arr[j] = pow(arr[j]);
  }
}

これは、配列 arr の各要素を二乗する操作を n 回繰り返すネストされたループです。このままでは、データをキャッシュした後、次のアクセスでキャッシュされたデータに到達するという保証はありません。データセット全体がキャッシュサイズより大きい場合、配列のイテレーションは以下の図のようになります。

[画像: キャッシュブロックが、キャッシュされたデータが再度アクセスされる前に置き換えられる。]

ループの前半でデータがキャッシュされますが、ループが終わる頃には、後半でアクセスされたデータでキャッシュが上書きされています。そのため、2回目のパスでは、前半のデータを再度キャッシュする必要があります。キャッシュされたデータが再びアクセスされる前に、キャッシュブロック全体が置き換えられてしまいます。これを解決するには、配列のイテレーションサイクルをキャッシュサイズのチャンクに分割します。

[画像: キャッシュされたデータに連続してアクセスする。]

ループの繰り返し回数は増えましたが、キャッシュヒット率は向上しました。3回目のパスまで、最初の半分しか処理されず、その後は後半のデータのみが処理されます。コードで実装すると、トリプルループになります(!)。

for (i = 0; i < len; i += CACHE_SIZE) {
  for (j = 0; j < n; j += 1) {
    for (k = 0; k < CACHE_SIZE; k += 1) {
      arr[i + k] = pow(arr[i + k]);
    }
  }
}

もちろん、最近ではコンパイラがこれらの最適化をすべて処理してくれるため、アプリケーション開発者はこのようなことを気にする必要はありません。低レベルで「コードがこのように最適化できる」ということを知っておくだけで十分でしょう。

参考文献
  • David Patterson, John Hennenssy, “Computer Organization and Design 5th Ed.”, MK, 2014.
  • Abraham Silberschatz, Peter Galvin, Greg Gagne, “Operating System Concepts 9th Ed.”, Wiley, 2014.
  • K. G. Smitha, “Para Cache Simulator”.