キャッシュメモリとは? CPUがメモリを待たずに済むしくみ

身近なところでは

パソコン用のCPUの仕様表には、「L2キャッシュ 16MB」「L3キャッシュ 64MB」のような数字が並びます。これはAMDが2024年に発売したRyzen 9 9950Xの例です。一方、ブラウザの設定画面には「キャッシュを削除」というボタンがあります。

どちらも「よく使うものの写しを、使う場所の近くに置く」という同じ考え方です。この記事ではCPUのキャッシュを中心に説明し、最後にCPUの外のキャッシュにも触れます。

CPUはメモリを「待っている」

CPUは、プログラムの命令とデータをメインメモリ(以下、メモリ)から読みながら仕事をします。メモリには、DRAMという種類のチップが使われています。問題は、CPUの速さに比べて、メモリからの読み出しがとても遅いことです。

メモリに頼んでからデータが届くまでの待ち時間は、製品によって数十〜100ナノ秒ほどです(1ナノ秒は10億分の1秒)。一方、4GHzで動くCPUでは、処理を進める合図(クロック)の間隔は0.25ナノ秒です。メモリを100ナノ秒待つ間に、合図は400回も来てしまいます。

合図1回でいくつもの命令を進められるCPUにとって、これは大きな足踏みです。しかも、CPUの速さの伸びに、メモリの待ち時間の短縮は長年追いついていません。

そこでCPUは、メモリのデータの写しを、自分のすぐそばの小さく速い記憶場所に置きます。これがキャッシュメモリです。今のキャッシュはCPUと同じチップの上にあり、いちばん近い段なら1ナノ秒前後で読めます。

キャッシュには、SRAMという種類の回路が使われます。多くは1ビットを6個のトランジスタで覚え、DRAMより速く読めます。その代わり場所をとるので、大容量にはできません(「DRAMとSRAMの違い」)。

小さな置き場で足りる理由: 局所性

キャッシュの容量は、メモリの数百分の1以下しかありません。それでも役に立つのは、プログラムがデータを使う順番に、決まったくせがあるからです。このくせを「局所性」と呼び、2種類あります。

1つ目は、一度使ったデータを、すぐにまた使いやすいという性質です。これを時間的局所性と呼びます。例えば、くり返しの処理では、回数を数える変数や同じ命令を何度も使います。

2つ目は、あるデータを使うと、その近くのデータもすぐに使いやすいという性質です。これを空間的局所性と呼びます。プログラムの命令はメモリに順に並び、たいてい順番に実行されます。本を1ページ読んだら、次に読むのはたいてい次のページなのと似ています。

64バイトずつまとめて運ぶ: キャッシュライン

空間的局所性を生かすため、キャッシュは、頼まれたデータだけでなく、その周りもまとめてメモリから持ってきます。この運ぶ単位をキャッシュライン(以下、ライン)と呼びます。x86のCPUや多くのArmのCPUでは、1ラインは64バイトです(AppleのMシリーズでは、macOSが128バイトと報告します)。

例えば、8バイトの数がメモリにずらりと並んでいるとします。1ラインには、この数が8個入ります。CPUが1つ目の数を頼むと、キャッシュにはまだないので、メモリまで取りに行きます。このとき、隣の7個も一緒に写されます。

キャッシュに目当てのデータがあることを「ヒット」、ないことを「ミス」と呼びます。上の例で数を順に8個読むと、ミスは最初の1回だけで、残りの7回はヒットです。初めて読むデータでも、8回中7回、つまり87.5%がヒットになります。

実際のCPUは、次に使いそうなラインを先回りして読む工夫(プリフェッチ)もしますが、ここでは省きます。

ヒット率と平均アクセス時間

読み出しのうち、ヒットした割合を「ヒット率」と呼びます。100回読んで95回ヒットなら、ヒット率は95%、残りの5%が「ミス率」です。

キャッシュの効果は、1回の読み出しにかかる時間の平均で比べます。ヒットしたときとミスしたときの時間に、それぞれ起こる割合をかけて足します。基本情報技術者試験では、この平均を「実効アクセス時間」と呼び、次の式で求めます。

実効アクセス時間 = ヒット率 × キャッシュの時間 + (1 − ヒット率) × メモリの時間

計算してみよう

キャッシュの読み出しが1ナノ秒、メモリが100ナノ秒、ヒット率が95%とします。

• ヒットの分: 0.95 × 1ナノ秒 = 0.95ナノ秒
• ミスの分: 0.05 × 100ナノ秒 = 5ナノ秒
• 平均: 0.95 + 5 = 5.95ナノ秒

キャッシュがなければ毎回100ナノ秒なので、平均は約17分の1です。ただし、5.95ナノ秒のうち5ナノ秒は、わずか5%のミスから来ています。

教科書には、平均メモリアクセス時間(AMAT)という別の形もあります。「ヒットの時間+ミス率×ミスで余分にかかる時間」です。ミスのときは、キャッシュを調べる1ナノ秒に、メモリの100ナノ秒が加わると考えます。上の例では1+0.05×100=6ナノ秒です。

0.05ナノ秒の差は、ミスの時間にキャッシュを調べる分を含めるかどうかの違いです。試験では、問題文が示す式と前提に合わせて計算します。数字を変えて試すなら「平均アクセス時間の計算ツール」が使えます。

L1・L2・L3: 速さと大きさで段を分ける

キャッシュを大きくすれば、ヒット率は上がります。しかし、大きな記憶場所ほど、目当てのデータを探して取り出すのに時間がかかります。

そこで、キャッシュも何段かに分けます。計算する回路にいちばん近く、小さく速い段を「L1キャッシュ」と呼びます。次がL2、その次がL3で、番号が大きいほど大きく、遅くなります。CPUはL1から順に探し、どこにもなければメモリへ取りに行きます。

2024年に発売されたパソコン用の上位のCPUで、大きさの目安を見てみます。段の分け方や呼び方は製品によって違います。

9950XのL1は、仕様の合計1,280KBを16コアで割った値です。各段の違いは「L1・L2・L3キャッシュの違い」で表にまとめています。

どこに置くか: ダイレクトマップとセットアソシアティブ

キャッシュは小さいので、メモリのどのラインをキャッシュのどこに置くかを決める必要があります。

いちばん単純なのは、メモリの住所(番地)から、置き場所を1か所に決めてしまう方法です。例えば4か所のキャッシュなら、ラインの番号を4で割った余りで場所を決めます。これをダイレクトマップ方式と呼びます。探すのは1か所だけなので速く、回路も簡単です。

弱点は、同じ場所に決まった2つのラインを交互に使うと、互いに追い出し合うことです。下の図のライン0と4がその例で、ほかの場所が空いていてもミスが続きます。

そこで今のCPUの多くは、置き場所を「セット」という組に分けます。番地からはセットだけを決め、その中の数か所のどこに置いてもよいことにします。これをセットアソシアティブ方式と呼びます。セットの中は同時に調べるので、探す時間はあまり増えません。

どこにでも置ける方式(フルアソシアティブ方式)もありますが、全部を同時に調べる回路が大きくなります。3つの方式は「置き方の3方式の違い」で比べています。

いっぱいになったら: 追い出すラインを選ぶ

セットの中がいっぱいなら、新しいラインを入れるためにどれか1つを追い出します。代表的なのは、いちばん長い間使われていないものを追い出す方式で、LRUと呼びます。時間的局所性から考えると、しばらく使っていないものは、この先も使われにくいはずだからです。実際のCPUでは、順番を正確に覚えるのが大変なので、LRUに近い簡単な方式もよく使われます。

OSがメモリの中身をストレージへ移すときも、同じ考え方を使います(「OSとは?」)。

書き込むとき: ライトスルーとライトバック

読むだけなら、キャッシュの写しとメモリの元は同じです。しかし、CPUがデータを書き換えると、写しと元が食い違います。いつメモリに反映するかで、大きく2つの方式があります。

1つは、キャッシュに書くと同時に、メモリにも書く方式です。これをライトスルー方式と呼びます。メモリがいつも最新なので、しくみは簡単です。その代わり、書き込みのたびに遅いメモリとのやりとりが発生します。

もう1つは、ひとまずキャッシュだけを書き換えておく方式で、「ライトバック方式」と呼びます。書き換えたラインには印をつけておき、そのラインが追い出されるときに、メモリへ書き戻します。同じ場所を何度書き換えても、メモリに書くのは追い出すときの1回で済みます。その代わり、しばらくはメモリの中身が古いままなので、管理は複雑になります。

今のパソコン用のCPUのデータ用キャッシュでは、ライトバックが一般的です。違いは「ライトスルーとライトバックの違い」で表にまとめています。

順番に読むプログラムが速い理由

ラインのしくみを知ると、同じ計算でも書き方で速さが変わる理由がわかります。例として、1万行×1万列の表(2次元の配列)の数を、すべて足す処理を考えます。数は1つ8バイトとします。

C言語のように、表を行ごとに続けて並べる言語では、1行目の左から右へ、次に2行目へ、という順でメモリに並びます。1行は8万バイト、表全体は800MBで、どのキャッシュよりずっと大きくなります。

行ごとに左から右へ足していくと、メモリを並んだ順に読むことになります。1つのラインで8個の数が手に入るので、ミスは8回に1回で済みます。

一方、列ごとに上から下へ足すと、1つ読むごとに8万バイト先へ飛び、毎回別のラインになります。いちばん小さなL1では、ほとんどがミスです。運んだラインの残り7個は、次の列で使うころにはL1から追い出されています。足し算の回数も答えも同じなのに、かかる時間は大きく違います。

ここでは話を単純にしました。実際の差は、CPUや表の大きさによって変わります。それでも「メモリに並んだ順に読む」は、速いプログラムの基本です。「配列と連結リストの違い」にも、この性質が関係します。

コアが複数あるとき

今のCPUにはコアが複数あり、それぞれが自分のL1やL2を持っています。すると、2つのコアが同じデータの写しを持つことがあります。片方が書き換えると、もう片方の写しは古くなります。そこでCPUは、ほかのコアの写しを無効にするなどの連絡を、回路で自動的に行います。どのコアから見ても同じ値に見えるよう保つこのしくみを、キャッシュコヒーレンシと呼びます。

CPUの外にもあるキャッシュ

「よく使うものの写しを近くに置く」考え方は、CPUの外でも使われています。例えばブラウザは、一度読み込んだページの画像などを端末に保存しておき、次は遠くのサーバまで取りに行かずに手元の写しを使います。これがブラウザのキャッシュです。

名前からIPアドレスを調べるDNSでも、答えをしばらく覚えておくキャッシュが使われます(「DNSとは?」)。動画や画像を配るサービスは、世界各地のサーバに写しを置き、利用者に近いサーバから届けます。このしくみをCDNと呼びます。

写しが古くなる問題がある点も同じです。違うのは対処の仕方と速さです。CPUは回路がナノ秒単位で写しをそろえます。ブラウザやCDNは、写しを使ってよい期限をソフトウェアで決め、ミリ秒(1,000分の1秒)単位の通信の待ちを減らします。

よくある誤解

数字で見る

メモリを1回待つ間に、クロックは数百回進みます。キャッシュは、この待ちの多くをクロック数回分に縮める工夫です。

もっと詳しく学ぶ

• 違いを表で見る: ライトアロケートとノーライトアロケートの違い(書き込みでミスしたときの動き)、MSI・MESI・MOESIの違い(コア間で写しをそろえる手順)
• 次の一歩の用語: ミスペナルティ、競合ミス、容量ミス(ミスの種類)、偽共有(コアどうしでラインを取り合う現象)、TLB(番地の変換のためのキャッシュ)
• メモリの速さがAIの計算をしばる話: 「なぜAIにGPUが使われるの?」