キャッシュの容量、ラインサイズ、連想度を入れると、アドレスがタグ・インデックス・オフセットの3つにどう分かれるかを、ビット数と帯グラフで示します。あわせて、ヒット時間、ミス率、ミスペナルティから平均メモリアクセス時間(AMAT)を計算し、キャッシュの構成が性能にどう効くかを確かめられます。
アドレスの分割(左が上位ビット)
容量・ラインサイズ・連想度には2のべき乗を入れ、容量がラインサイズ × 連想度で割り切れるようにしてください。オフセットとインデックスのビット数の合計がアドレス幅を超える場合も計算できません。
ほかの入力は今の値のまま、選んだ入力だけを今の値の1/4〜4倍の範囲で変えたときの結果です。赤い点が今の値です。
キャッシュは主記憶のデータをライン(ブロック)という単位で保持します。ライン数は 容量 ÷ ラインサイズ、セット数は ライン数 ÷ 連想度 です。アドレスの下位から、ライン内の位置を表すオフセットが log₂(ラインサイズ) ビット、セットを選ぶインデックスが log₂(セット数) ビットで、残りの上位ビットがタグになります。既定値の32ビット、32 KB、64 B、8ウェイでは、ライン数は512、セット数は64で、オフセット6ビット、インデックス6ビット、タグは 32 − 6 − 6 = 20ビットです。
容量とラインサイズを同じにしたまま連想度を2倍にすると、セット数は半分になり、インデックスが1ビット減ってタグが1ビット増えます。1ウェイがダイレクトマップ方式で、連想度にライン数(既定値なら512)を入れると、セットが1つだけのフルアソシアティブ方式になり、インデックスは0ビットです。連想度を上げると、同じセットにアドレスが集中して起こる競合ミスは減りますが、並列に比べるタグの数が増えるため、比較器の面積や消費電力、ヒット時間が増えます。
キャッシュの性能は、ミス率だけでなく平均メモリアクセス時間で比べます。AMAT = ヒット時間 + ミス率 × ミスペナルティ で、既定値では 4 + 0.05 × 100 = 9サイクルです。ミス率がわずか5%でも、ミスペナルティが大きいため平均は2倍以上に延びます。容量や連想度を増やしてミス率を下げても、ヒット時間が延びればすべてのアクセスが遅くなるので、両方を合わせて評価します。多段のキャッシュでは、L1のミスペナルティを L2のヒット時間 + L2のミス率 × L2のミスペナルティ に置き換えて計算します。
ラインサイズを大きくすると空間的局所性を生かせてミス率が下がりますが、1回のミスで運ぶデータが増えてミスペナルティが大きくなり、ライン数が減るぶん競合も増えます。現在の多くのCPUは64 Bを使っています。L1キャッシュでは、仮想アドレスでセットを引きながらTLBで変換する仮想インデックス・物理タグ(VIPT)方式がよく使われます。インデックスとオフセットをページ内に収めるため、容量はページサイズ × 連想度(4 KB × 8ウェイなら32 KB)以下に制限されます。タグのビット数は、タグを保存するメモリの大きさにも直結します。
正解：C. 17ビット
ラインサイズ64バイト = 2⁶ なのでオフセットは6ビットです。ライン数は 32 KB ÷ 64 B = 32768 ÷ 64 = 512 = 2⁹ で、ダイレクトマップではライン数がそのままセット数なのでインデックスは9ビットです。残りがタグで、32 − 9 − 6 = 17ビットになります。19ビットは4ウェイのセットアソシアティブにしてインデックスが2ビット減ったときの値で、ダイレクトマップには当てはまりません。
正解：A. 128
ライン数は 32 KB ÷ 64 B = 512 です。4ウェイでは1つのセットに4ラインが入るので、セット数は 512 ÷ 4 = 128 = 2⁷ となり、インデックスは7ビット、タグは 32 − 7 − 6 = 19ビットになります。512はライン数そのもので、ダイレクトマップのときのセット数です。連想度を上げるとセット数が減り、その分タグのビット数が増えて比較器も増えます。32はラインサイズの64を誤ってウェイ数で割った値です。
正解：A. 8サイクル
平均メモリアクセス時間 = ヒット時間 + ミス率 × ミスペナルティ = 2 + 0.04 × 150 = 2 + 6 = 8サイクルです。ヒット時間はすべてのアクセスでかかり、ミスしたときだけミスペナルティが加わると考えます。6サイクルはミスの分だけを計算してヒット時間を足し忘れた値です。152サイクルはミスしたアクセス1回にかかる時間で、平均ではありません。ミス率がわずか4%でも、平均が4倍になることが分かります。
正解：C. 8
オフセットは 64 = 2⁶ で下位6ビット、インデックスはセット数 64 = 2⁶ でその上の6ビットです。0x1234 = 4660 を64で割ると 4660 ÷ 64 = 72 余り52なので、ライン番号は72です。セット番号はライン番号をセット数で割った余りで、72 mod 64 = 8 になります。52は64で割った余りで、ライン内の位置(オフセット)を表す値です。4はアドレスの16進数の下1桁を取り出しただけの値で、セットとは関係ありません。
オフセットは log₂64 = 6ビット、ライン数は 32 KB ÷ 64 B = 512 なのでインデックスは9ビット、タグは 32 − 9 − 6 = 17ビットです。8ウェイにするとセット数が64に減り、インデックスは6ビット、タグは20ビットになります。
0ビットです。セットが1つしかないので、オフセット以外のすべてのビットがタグになり、すべてのラインのタグと比べます。このツールでは、連想度にライン数と同じ値を入れると確かめられます。
既定値(ヒット時間4サイクル、ミス率5%、ミスペナルティ100サイクル)では、ミス率を2.5%にすると AMAT は9から6.5サイクルに、ヒット時間を3サイクルにすると8サイクルになり、ミス率の改善のほうが効きます。ミスペナルティが小さい場合は逆になることもあるので、AMATの式で比べてください。
キャッシュメモリ キャッシュライン ダイレクトマップ方式 セットアソシアティブ方式 フルアソシアティブ方式 平均メモリアクセス時間(AMAT) ミスペナルティ 競合ミス