キャッシュヒット率（局所性で変わる）

📌

キャッシュヒット率とは

キャッシュヒット率（hit rate）とは、全メモリアクセスのうち、キャッシュの中で見つかった（ヒットした）割合のことです。CPUがデータを要求するたびに、それがキャッシュにあれば「ヒット」、無ければ「ミス」と数え、ヒットの割合を求めます。

身近な例で考えると、冷蔵庫の中を探すのに似ています。料理のたびに必要な食材が冷蔵庫（＝キャッシュ）にあれば、すぐ取り出せます（ヒット）。無ければスーパー（＝主記憶）まで買いに行くことになります（ミス）。よく使う食材ほど冷蔵庫に常備しておけば、買い物に行く回数が減り、料理が早く進みます。この「冷蔵庫で済んだ割合」がヒット率です。

上のツールでアクセスパターンを選んで▶ボタンを押すと、1回ずつヒット/ミスを判定しながら累計ヒット率が変化していく様子が見られます。同じ番地を繰り返すパターンと、毎回バラバラに飛ぶパターンで、最終的なヒット率がどれだけ違うか比べてみてください。

📐

計算式の意味

ヒット率の計算式は、とてもシンプルです。

ヒット率 = ヒット回数 ÷ 全アクセス回数

式の各部分の意味は次の通りです。
・ヒット回数：要求したデータがキャッシュにあった回数
・全アクセス回数：CPUがメモリにアクセスした合計回数
・割り算の結果は 0〜1（または 0〜100%）の値になり、1（100%）に近いほどキャッシュがよく効いている

ヒットしなかった分がミス率です。ヒット率とミス率を足すと必ず 1（100%）になります。

例: 100回アクセスして90回ヒット
ヒット率 = 90 ÷ 100 = 0.9 = 90%
ミス率 = 1 − 0.9 = 0.1 = 10%

ヒット率は、次のページで学ぶ実効アクセス時間（平均アクセス時間）を求めるための重要な材料になります。ヒット率が高いほど、遅い主記憶へのアクセスが減り、平均的なメモリアクセスが速くなるためです。

📌

局所性の原理

キャッシュが効くのは、プログラムのメモリアクセスに局所性（locality）という偏りがあるからです。局所性とは「一度使った場所や、その近くの場所が、また使われやすい」という性質のことです。

局所性には2種類あります。
・時間局所性：一度アクセスした場所は、近いうちにまた同じ場所がアクセスされやすい（例: ループの中で同じ変数を何度も使う）
・空間局所性：ある場所をアクセスすると、その近くの場所も続けてアクセスされやすい（例: 配列を先頭から順に処理する）

この性質があるからこそ、「一度使ったデータとその近くをキャッシュに残す」戦略が当たり、ヒット率が高くなります。逆に、上のツールの「局所性が低い（バラバラに飛ぶ）」パターンでは、毎回新しい場所にアクセスするため予測が外れ続け、ほとんどがミスになります。局所性が高いプログラムほどキャッシュが効く、というのがキャッシュ設計の大前提です。

📐

実効アクセス時間の計算

実効アクセス時間（＝平均的なメモリアクセスにかかる時間）は、ヒット率を使って次の式で求められます。

実効アクセス時間 = h × Tc + (1−h) × Tm

式の各記号の意味は次のとおりです。
・h：ヒット率（0〜1の小数、または0〜100%）
・Tc：キャッシュのアクセス時間（速い方）
・Tm：主記憶のアクセス時間（遅い方）
・(1−h)：ミス率（ヒットしなかった割合）

なぜこの式になるかというと、アクセス全体の中でヒットする割合とミスする割合を、それぞれの時間で重み付けして足すからです。「全体の中のヒット部分の平均」＋「全体の中のミス部分の平均」＝「全体の平均」という考え方です。

計算例：Tc = 10 ns、Tm = 100 ns、h = 0.9（90%）の場合
実効アクセス時間 = 0.9 × 10 + (1 − 0.9) × 100
= 9 + 10
= 19 ns

ヒット率 90%（h=0.9）のとき、実効アクセス時間は19 nsになります。キャッシュがなく毎回主記憶（100 ns）に行く場合と比べると、約5分の1の時間でアクセスできる計算です。ヒット率が上がるほど実効アクセス時間はキャッシュ時間（10 ns）に近づき、下がるほど主記憶時間（100 ns）に近づきます。

📌

ヒット率を上げる工夫（プリフェッチ）

ヒット率を高める代表的な技術がプリフェッチ（prefetch＝先読み）です。CPUが実際にデータを要求する前に、「次はきっとこのデータが必要になる」と予測して、あらかじめ主記憶からキャッシュに転送しておく仕組みです。

なぜプリフェッチが効くかというと、空間局所性（近くのデータも続けて使われやすい）という性質があるからです。配列を先頭から順に処理するプログラムでは、今 A[0] を使っているなら次は A[1]、A[2]… と続くことが予測できます。だから A[0] を読んだタイミングで、その近くの A[1]〜A[7] などをまとめてキャッシュに先読みしておけば、次のアクセスがヒットしやすくなります。

この技術の効果を日常の例で表すと、図書館員が「この本を借りた人は次にあの本を借りることが多い」と学習して、あらかじめカウンターに出しておくサービスに似ています。借りに来るたびにすぐ渡せるので、待ち時間（ミス）がぐっと減ります。プリフェッチはハードウェアが自動で行うため、プログラムを変えなくても効果が得られる点が優れています。