CPUキャッシュは階層構造となっており、CPUとメインメモリの速度差を埋める重要な役割を担っています。
現代のCPUでは、レジスタのアクセスが1サイクル未満なのに対し、メインメモリへのアクセスには数百サイクルが必要です。この速度差を緩和するために、CPUとメインメモリの間に高速な小容量メモリ（キャッシュ）を配置します。
本記事の内容
- メモリ階層の設計思想
- 局所性の原理
- キャッシュの動作原理（ダイレクトマップ・セットアソシアティブ）
- Pythonでのキャッシュ効果の実験
メモリ階層
メモリ階層は、速度・容量・コストのトレードオフに基づいて設計されています。
| 階層 | 容量 | アクセス時間 | 帯域幅 |
|---|---|---|---|
| レジスタ | ~1KB | ~0.3ns | – |
| L1キャッシュ | 32-64KB | ~1ns | ~1TB/s |
| L2キャッシュ | 256KB-1MB | ~3-10ns | ~200GB/s |
| L3キャッシュ | 4-64MB | ~10-30ns | ~100GB/s |
| メインメモリ | 8-128GB | ~50-100ns | ~50GB/s |
| SSD | 0.5-4TB | ~100us | ~5GB/s |
各レベルで容量が増加する代わりにアクセス時間が増加するという関係があります。
局所性の原理
キャッシュが有効に機能する根拠は、プログラムのメモリアクセスパターンに見られる局所性（Locality）にあります。
時間的局所性
最近アクセスされたデータは、近い将来再びアクセスされる可能性が高いという性質です。ループ内の変数アクセスがこれに該当します。
空間的局所性
アクセスされたアドレスの近傍のデータも、近い将来アクセスされる可能性が高いという性質です。配列の順次アクセスがこれに該当します。
キャッシュの動作原理
キャッシュライン
キャッシュのデータ転送単位をキャッシュライン（Cache Line）と呼びます。典型的には64バイトです。空間的局所性を活用するため、1ワードだけでなく周辺のデータもまとめて転送します。
キャッシュヒットとミス
CPUがデータを要求したとき、
- キャッシュヒット: キャッシュにデータが存在 → 高速にアクセス
- キャッシュミス: キャッシュにデータが不在 → 下位のメモリから転送（遅い）
ヒット率 $h$ を用いた平均メモリアクセス時間（AMAT）は次のように表されます。
$$ \text{AMAT} = t_{\text{hit}} + (1 – h) \times t_{\text{miss}} $$
ここで $t_{\text{hit}}$ はキャッシュヒット時のアクセス時間、$t_{\text{miss}}$ はミスペナルティです。
多段キャッシュのAMAT
L1, L2の2段キャッシュの場合、
$$ \text{AMAT} = t_{L1} + (1 – h_{L1}) \times \left[ t_{L2} + (1 – h_{L2}) \times t_{\text{mem}} \right] $$
例えば、$t_{L1} = 1$ns, $h_{L1} = 0.95$, $t_{L2} = 10$ns, $h_{L2} = 0.8$, $t_{\text{mem}} = 100$nsの場合、
$$ \text{AMAT} = 1 + 0.05 \times [10 + 0.2 \times 100] = 1 + 0.05 \times 30 = 2.5 \text{ ns} $$
キャッシュなしの100nsと比較して40倍の高速化です。
ダイレクトマップキャッシュ
最も単純なキャッシュ方式で、メモリアドレスから一意にキャッシュ内の格納位置が決まります。
アドレスの分解は次の通りです。
$$ \text{Address} = \underbrace{\text{Tag}}_{\text{上位ビット}} \mid \underbrace{\text{Index}}_{\text{中間ビット}} \mid \underbrace{\text{Offset}}_{\text{下位ビット}} $$
- Offset: キャッシュライン内のバイト位置（$\log_2(\text{ラインサイズ})$ ビット）
- Index: キャッシュセットの番号（$\log_2(\text{セット数})$ ビット）
- Tag: 残りの上位ビット（一致判定に使用）
セットアソシアティブキャッシュ
$n$-way セットアソシアティブキャッシュでは、各セットに $n$ 個のキャッシュラインを格納できます。ダイレクトマップ（$n=1$）と比べて、コンフリクトミスが減少します。
Pythonでキャッシュの効果を実験
import numpy as np
import matplotlib.pyplot as plt
import time
def measure_access_time(array_size, stride):
"""配列アクセスの時間を測定"""
arr = np.zeros(array_size, dtype=np.float64)
indices = np.arange(0, array_size, stride)
# ウォームアップ
for idx in indices:
arr[idx] = 1.0
# 計測（複数回の平均）
n_repeats = 100
start = time.perf_counter()
for _ in range(n_repeats):
total = 0.0
for idx in indices:
total += arr[idx]
elapsed = time.perf_counter() - start
n_accesses = len(indices) * n_repeats
return elapsed / n_accesses * 1e9 # ns per access
# 配列サイズを変化させた実験
sizes = [2**k for k in range(10, 24)] # 1KB ~ 16MB (float64)
access_times = []
print("=== 配列サイズ vs アクセス時間 ===")
for size in sizes:
t = measure_access_time(size, stride=1)
access_times.append(t)
size_kb = size * 8 / 1024
print(f" {size_kb:10.0f} KB: {t:.2f} ns/access")
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 配列サイズ vs アクセス時間
sizes_kb = [s * 8 / 1024 for s in sizes]
axes[0].semilogx(sizes_kb, access_times, 'bo-', linewidth=2, markersize=6)
axes[0].set_xlabel('Array Size [KB]')
axes[0].set_ylabel('Access Time per Element [ns]')
axes[0].set_title('Memory Access Time vs Array Size')
axes[0].grid(True)
# キャッシュヒット率のモデル
for label, color in [('L1 (32KB)', 'green'), ('L2 (256KB)', 'orange'), ('L3 (8MB)', 'red')]:
size = float(label.split('(')[1].split(')')[0].replace('KB', '').replace('MB', ''))
if 'MB' in label:
size *= 1024
axes[0].axvline(x=size, color=color, linestyle='--', alpha=0.7, label=label)
axes[0].legend()
# ヒット率とAMATの関係
hit_rates = np.linspace(0.5, 1.0, 100)
t_hit = 1.0 # ns
t_miss = 100.0 # ns
amat = t_hit + (1 - hit_rates) * t_miss
axes[1].plot(hit_rates * 100, amat, 'r-', linewidth=2)
axes[1].set_xlabel('Cache Hit Rate [%]')
axes[1].set_ylabel('AMAT [ns]')
axes[1].set_title('Average Memory Access Time')
axes[1].grid(True)
axes[1].axhline(y=t_hit, color='green', linestyle='--', label='Hit time (1ns)')
axes[1].axhline(y=t_miss, color='gray', linestyle='--', alpha=0.5, label='Miss penalty (100ns)')
axes[1].legend()
plt.tight_layout()
plt.show()
まとめ
本記事では、CPUキャッシュの仕組みについて解説しました。
- メモリ階層は速度・容量・コストのトレードオフに基づいて設計されている
- キャッシュは局所性の原理（時間的・空間的）を利用して性能を向上させる
- 平均メモリアクセス時間は $\text{AMAT} = t_{\text{hit}} + (1-h) \times t_{\text{miss}}$ で計算できる
- セットアソシアティブキャッシュにより、コンフリクトミスを削減できる
- 配列アクセスのパターンを工夫することで、キャッシュの効果を最大化できる