計算機アーキテクチャ

キャッシュとメモリ階層

配列の走査を例に、時間的・空間的局所性、キャッシュライン、ヒット率、連想度、書込み方式を理解し、メモリ待ちを説明します。

学習の目安 約10分 · 更新 2026-10-29

情報の確認基準日:2026-10-26

学習目標

  • レジスタ、キャッシュ、主記憶、ストレージからなるメモリ階層と、局所性が必要な理由を説明できる。
  • アクセス列からヒット・ミスを予測し、キャッシュライン、連想度、書込み方式が実測性能へ与える影響を分析できる。

同じ回数の足し算でも、データを読む順番で実行時間が変わることがあります。CPUが計算する速さと、大容量のメモリから値を運ぶ速さには差があるためです。キャッシュは、よく使うデータの一部をCPUに近い場所へ置き、この差を埋めます。

小さく速い場所を段階的に置く

一般的なCPUでは、レジスタ、L1・L2・L3などのキャッシュ、主記憶という階層を使います。容量、アクセス時間、共有範囲は機種によって違います。レジスタの値をどれにするかはコンパイラや命令が指定し、CPUキャッシュは通常ハードウェアが管理します。アプリが普段指定する配列のアドレスと、何段目にコピーがあるかは別の話です。

キャッシュが効く根拠は局所性です。同じ値を短い間隔で再び使う性質を時間的局所性、近いアドレスの値を続けて使う性質を空間的局所性と呼びます。ループの集計変数は前者、配列の順番の走査は後者を利用しやすい例です。

容量とアクセス時間で見るメモリ階層上からレジスタ、L1、L2、L3、主記憶、SSDを配置する。L1は数十KBで約1ns、主記憶は数GB以上で約100ns、SSDは数百GB以上で数十から数百マイクロ秒の桁。SSDとの移動はストレージI/Oとして区別する。データの置き場所容量の桁時間の桁レジスタ数百B〜数KB約1ns以下L1数十KB約1nsL2数百KB〜数MB約数nsL3数MB〜数十MB約数十ns主記憶数GB〜約100nsストレージI/OSSD数百GB〜数TB約数十〜数百µs下ほど容量が大きく、アクセス時間も長い傾向
容量とアクセス時間で見るメモリ階層

機種により異なる目安です。容量はレジスタとL1・L2がコア単位、L3が共有領域、主記憶とSSDが機器単位の例です。レジスタは命令のオペランドで、キャッシュのようなミス判定はありません。SSDのデータはストレージI/Oで主記憶へ読み込みます。

1要素でなくラインごと運ぶ

仮にキャッシュラインが64バイトで、整数が4バイトなら、連続した16要素が1ラインに入ります。先頭要素でミスしてラインを取り込めば、続く要素は同じラインから読める可能性があります。以下はアクセス順の違いだけを見るための例です。実測では最適化、プリフェッチ、配列の大きさなども影響します。

/* 連続した領域を読む */
for (size_t i = 0; i < n; ++i)
    sum += a[i];

/* 16要素ごとに飛ぶ。総読取り数も異なる */
for (size_t i = 0; i < n; i += 16)
    sum += a[i];

後半は、各ラインから1要素だけ使って次へ進む例です。二つのコードは読取り数が違うので、そのまま時間だけを比べて優劣を決められません。1要素あたりの時間やキャッシュミス数を測ると、「運んだ64バイトのうち何バイトを利用したか」が見えます。

64バイトのラインで使う要素を比べる64バイト境界に整列した4バイト整数16個を横並びにする。連続アクセスでは16個全てを使い、16要素ごとのストライドアクセスでは各ラインの先頭1個を使う。1ライン = 64バイト = 4バイト整数 × 16個連続アクセス:a[0]、a[1]、…、a[15] を読む0123456789101112131415使う要素:16 / 16個ストライド16要素:a[0]、a[16]、a[32]、… を読む0123456789101112131415このラインで使う要素:1 / 16個次のラインa[16]を読む次のラインa[32]を読む枠内の数字は、最初のライン内の配列添字
64バイトのラインで使う要素を比べる

4バイト整数の配列が64バイト境界から始まる例です。連続アクセスは1ラインの16要素を使います。ストライド16要素(64バイト)ではa[0]、a[16]、a[32]と次のラインへ進み、各ラインの1要素を使います。実行速度の比率を示す図ではありません。

ヒット率の少しの差が待ちを増やす

目的のデータがあればヒット、なければミスです。単純な1段のモデルでは、平均アクセス時間=ヒット時間+ミス率×追加のミスペナルティと計算します。ヒット時間1ns、ミス率5%、追加待ち100nsなら6nsです。ミス率を1%に下げれば2nsになります。少数の遅いアクセスが平均を押し上げます。

実際のCPUは、複数のミスを並行して処理したり、計算と読取りを重ねたりします。この式をそのままプログラム全体の実行時間にはできません。何が待ち時間を決めているかを整理するモデルとして使います。

空きがあっても衝突する

キャッシュ全体の空きだけでは、データを置けるとは限りません。ダイレクトマップでは、各メモリブロックの置き場所が一つに決まります。違うブロックが同じ場所へ対応すると、交互に追い出し合うことがあります。セット連想方式では、同じセットの複数の場所から選べます。例えば4ウェイなら、そのセットに4ラインを置けます。

セットの全候補が埋まったときは、どれを捨てるかを置換方針で決めます。最も長く使われていないものを選ぶLRUや、その近似などがあります。連想度を上げると衝突を減らせる一方、比較回路などの費用が増えます。キャッシュ容量を増やす方法と、連想度を増やす方法は同じではありません。

書いた値はいつ下の階層へ届くか

ライトスルーは、キャッシュへの変更を下位階層にも伝えます。ライトバックは、変更したラインに印を付け、追い出すときなどにまとめて下位へ書き戻します。後者では、主記憶の内容が一時的に古くても、CPUから見える値はキャッシュ側の新しいものになります。

書込みミスのときにラインを取り込むかどうかは、書込みをいつ伝えるかとは別の方針です。また、CPUキャッシュの書戻しと、ファイルをSSDへ永続化する処理も別です。「メモリに書いた」ことだけで、電源を落としても値が残るとは言えません。

確かめてみよう

問1:同じ要素を何度も使うのは、どちらの局所性でしょうか。

答えを見る

時間的局所性です。次の隣接要素を使うなら、空間的局所性です。

問2:ヒット時間2ns、ミス率2%、追加待ち80nsの平均アクセス時間はいくらでしょうか。

答えを見る

2+0.02×80=3.6nsです。

複数コアやデバイスが同じメモリを使う場合は、割込み・I/O・DMA・マルチコアで扱います。

配列を16回読むと何本のキャッシュラインを使うか

4バイト整数の配列を読みます。64バイトのラインには16要素が入ります。読み方を選び、読み込むラインと使う要素を比べてください。

配列の読み方

読み方を変えると0回から始まります。

16回中0回の読み取りが完了

まだ読み取っていません。「1回進める」を押してください。

最初に読み込むライン:ライン0

要素0〜15・64バイト。1本のラインを折り返して表示しています。

このラインは16要素中0要素を使用しています。

  1. 要素0未使用
  2. 要素1未使用
  3. 要素2未使用
  4. 要素3未使用
  5. 要素4未使用
  6. 要素5未使用
  7. 要素6未使用
  8. 要素7未使用
  9. 要素8未使用
  10. 要素9未使用
  11. 要素10未使用
  12. 要素11未使用
  13. 要素12未使用
  14. 要素13未使用
  15. 要素14未使用
  16. 要素15未使用
読み込んだライン
0本(0バイト)
使った要素
0個(0バイト)
読み込んだ領域の利用率
読み取り前

16回読み取った結果を比べる

読み方読み込むライン領域の利用率
連続アクセス1本
(64バイト)
100%
(16要素を使用)
ストライド1616本
(1024バイト)
6.25%
(16要素を使用)
この演習の条件

配列は256要素で、先頭は64バイト境界にそろっています。最初のキャッシュは空とし、1要素を読むと対応するライン全体を読み込みます。読み込んだラインは保持し、追い出しやプリフェッチは扱いません。どちらも合計16要素を読みます。

利用率は「読んだ要素のバイト数 ÷ 読み込んだラインの合計バイト数」です。実機の処理時間や速度比を示す数値ではありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

公開教材を探す →