キャッシュメモリ

キャッシュメモリ (cache memory) は、CPUなど処理装置がデータや命令などの情報を取得/更新する際に主記憶装置やバスなどの遅延／低帯域を隠蔽し、処理装置と記憶装置の性能差を埋めるために用いる高速小容量メモリのことである。略してキャッシュとも呼ぶ。コンピュータは以前から記憶装置や伝送路の性能が処理装置の性能に追いつけず、この差が全体性能に対するボトルネックとされてきた（ノイマンズ・ボトルネック）。そしてムーアの法則に基づく処理装置の加速度的な高性能化により現在ではますますこの差が拡大されている。キャッシュメモリは、記憶階層の観点からこれを解消しようとするものである。

主に、主記憶装置とCPUなど処理装置との間に構成される。この場合、処理装置がアクセスしたいデータやそのアドレス、状態、設定など属性情報をコピーし保持することで、本来アクセスすべき記憶装置に代わってデータを入出力する。通常はキャッシュメモリが自動的にデータ保存や主記憶装置の代替を行うため、基本的にCPUのプログラムなど処理装置側がキャッシュメモリを意識する必要はない。

キャッシュの一般的な概念はキャッシュ (コンピュータシステム)を参照のこと。

意義

データ帯域

キャッシュメモリは再利用データのキャッシングによる実効データ帯域の増加という意義をもつ。

例えば SGEMV（単精度浮動小数点の行列ベクトル積）を考える。2.0 GHzで動作する Haswell CPUのシングルコアはピーク時に128GB/sのデータアクセスを要求する^[1] (8 [FMA/inst.] ÷ 0.5 [CPI=cycle/inst.]^[2] * 2.0G [Hz=cycle/sec] * 4 [Byte/FP32])。一方プロセッサ-メインメモリ間のレイテンシは数百サイクルであり、並列ロードをおこなっても高々5GB/sしかデータを読み出せない^[3]。すなわちメモリ律速でCPU性能の5%以下しか引き出すことができない^[4]。もし行列をキャッシュに載せきることが出来れば、よりレイテンシの小さいキャッシュメモリからデータを供給し高いデータ帯域を確保できる。

構成

キャッシュメモリは、通常は下位レベルの記憶装置より小容量で高速なスタティックRAMを用いて構成される。データ本体の一部とそのアドレス、フラグなど属性情報のセットを固定容量のメモリに格納する構造で、データ格納構造、ライン入替え、データ更新方式、キャッシュ階層などに多数のアーキテクチャが存在する。以前はCPUチップの外部に接続されていたが、LSIの集積度の向上や要求速度の上昇に伴いCPUチップ内部に取り込まれることが普通となった。

キャッシュ階層

記憶階層をもつキャッシュメモリをマルチレベルキャッシュ（英: multi level caches）という^[5]。CPUとメモリの性能差の拡大、マルチスレッドなどアクセス範囲の拡大に対応するために導入される。CPUに近い側からL1キャッシュ（レベル1）、L2キャッシュ（レベル2）と呼ばれ^[6]、2013年時点ではL4キャッシュまでCPUに内蔵する例も存在する。CPUから見て一番遠いキャッシュメモリの事をLLC（Last Level Cache）と呼ぶ事もある。

データ格納構造

キャッシュメモリはデータをライン(ブロック)と呼ぶある程度まとまった単位で管理する(例えばIntel Pentium 4の8kByte L1キャッシュはラインサイズ64Byte)が、データのアクセス要求があった時にそのデータがキャッシュに存在しているか、あるならどのラインかなどを瞬時(多くの場合1サイクルのスループット)に検索する必要がある。そのためデータ格納アドレスの一部、具体的にはライン単位アドレスの下位数ビット(エントリアドレス)によりある程度の格納位置を限定することで検索速度を高める。各ラインにはライン単位アドレスの上位ビット、即ちフレームアドレスを格納しておき、キャッシュ検索時には検索アドレスのフレームアドレス部と、キャッシュ内に格納されている検索エントリアドレス位置（エントリアドレス部をデコードしラインが1つ選択される）に対応したフレームアドレスとを比較することでキャッシュのヒットを検出する。このフレームアドレス格納バッファが（図中）タグである。複数セットのタグを持てば同じエントリアドレスでも複数データの格納を行うことが可能となる。このタグのセット数(ウエイ)を連想度と呼ぶ。データ格納構造の相違は連想度の相違でもある。

ダイレクトマップ方式 (Direct Mapped): 1組のタグにより構成（連想度1）されるデータ格納構造。アドレスにより一意に配置が決まるため、タグの構造が非常に単純。だが、同一エントリに異なるフレームアドレスが転送されると必ずラインの入れ替えが発生する。ラインの入れ替えが頻発しスループットが落ちることをキャッシュスラッシングというが、この状態が起こりやすくヒット率は他の方式に比べ高くない。
セットアソシアティブ方式 (Set Associative): 複数のタグにより構成(連想度2以上)されるデータ格納構造。同一エントリに異なるフレームアドレスのデータを複数格納することができる。連想度が上がるほどキャッシュヒット率は上昇するが製造は困難になっていくため、システムによりバランスのよい実装が異なる。n個のタグにより構成された場合、nウエイセットアソシアティブ方式と呼ぶ。最近はCAM (連想メモリ：Content Addressable Memory)がタグとして使われ出し、32など非常に高い連想度を実装できるようになってきた。ダイレクトマップ方式や下記のフルアソシアティブ方式はこの方式の特殊な場合である。
フルアソシアティブ方式 (Fully Associative): エントリアドレスによる振り分けはなく、全てのラインが検索対象となる構造。従って連想度はライン数分となる。キャッシュスラッシングは起こり難くヒット率は最も優れているが、実装コストや複雑度の面から通常用いられることはない。

ライン入替え方式 (Refill)

ラインの入替え(リフィル)は該当エントリの全ラインにデータが格納されてなお同一エントリ新規フレームアドレスが入力されてキャッシュミスした（ヒットしなかった）場合に発生する。その場合どのラインを掃出して新規アドレスと入替えるかのアルゴリズムによってキャッシュのヒット率が変動する。代表的なアルゴリズムを記す。

ラウンドロビン (Round Robin): リフィル対象となるラインを順番に交代させる方法。各ラインのアクセス頻度に拘らず順番にリフィルを行うため、あまりヒット率が高くない。
LRU (Least Recently Used): 最も古くアクセスされたラインをリフィルする方法。時間的局所性に鑑みれば、過去最もアクセスのなかったラインは将来にわたってもアクセスされる可能性は少ないと言える。従ってこの方法はヒット率がかなり高い方法としてよく採用されている。ただし各ラインごとにアクセス順履歴を持ちアクセスがある度に頻繁に履歴を入替えるため、複雑な構成となりアクセス性能に影響が出る場合がある。
ランダム (Random): リフィルラインの選択をランダムに行う方式。各ライン毎にリフィル用機構を持つ必要がなくなるため構成が簡易になる。ヒット率はラウンドロビンよりは良いとされる。

データ更新方式 (Replacement policy)

CPUキャッシュは命令キャッシュとデータキャッシュの2種類が搭載されている場合が多い。命令キャッシュはプログラムという静的なデータを扱うのでデータ更新は存在しないが、データキャッシュはメモリへのライト動作があるためデータ更新が存在する。更新されたデータはいずれかのタイミングで下位レベルのメモリにも反映される必要があり、そのタイミングの相違により2つのアルゴリズムが存在する。

ライトスルー方式 (Write Through Algorithm)

CPUがメモリ書き込みを行ったら、キャッシュにストアすると同時に下位レベルのメモリにも書き戻す方式。必ず下位レベルのバスが活性化するため、バスの競合や下位レベルの低いスループットに律速されるなどの制約はあるが、単純な構成で実現でき、またデータのコヒーレンシを保つことが容易である。出力段にライトバッファを設けることにより、単一CPUであればライトバック方式に比べ遜色のない性能が期待できる。そのためCPUのL1キャッシュなどに実装される場合が多い。

ライトバック方式 (Write Back Algorithm)

CPUがメモリ書き込みを行っても、条件が整わない限りキャッシュに留まりメモリへの書き戻しを行わない方式。書き戻す条件は対象エントリにウエイ数以上のフレームアドレスのリード／ライトが行われる、他のバスマスタが対象エントリが保持しているアドレスに対しアクセスを行った時にコヒーレンシを保つために行うなどがある。ライトスルー方式に対し下位レベルのバスが競合を起こしにくく、マルチCPU構成に向くため、記憶階層の同一レベルに複数のキャッシュが接続されているようなL2キャッシュに実装される。ライトミス時に2つのアプローチがある。一つは、Write allocate であり、もうひとつが No-write allocate である。

Write allocate は fetch on write とも呼ばれる。ライトミスしたアドレスを含むラインがキャッシュにロードされた後、ライトが実行される。このアプローチでは、ライトミスとリードミスは同様の動作となる。
No-write allocate は write-no-allocate または write around と呼ばれる。ライトミスしたアドレスのデータはキャッシュにロードされず、データは下位の記憶階層に書き込まれる。このアプローチでは、データロードは、リードミス時にのみ発生する。

キャッシュコヒーレンシ (Cache Coherency)

マルチCPU/キャッシュ構成など複数のバスマスタが存在し、各々がデータ更新を行った場合でも最新の正しいデータにアクセスできるよう保つべきデータの一貫性のことをキャッシュコヒーレンシもしくはキャッシュコンシステンシ (Cache Consistency) という。データ更新に上記ライトバック方式を用いた場合など、キャッシュに更新されたデータが滞留して主記憶装置など下位レベルのメモリには最新のデータが存在しない可能性がある。この時に複数のCPUが同一の記憶領域を参照／更新しようとすると、データの不整合が起こり正しい結果が得られないため、これを解決しどのCPUも必ず最新のデータにアクセスできるようにする必要がある。このための代表的なアルゴリズムにスヌープ方式やディレクトリ方式、共有キャッシュがある。

スヌープ方式 (Cache Snooping)

キャッシュコヒーレンシのアルゴリズムにおいて、特に各キャッシュ自身に搭載される方法としてスヌープ方式（スヌープキャッシュ）がある。これは各々のキャッシュが自身や他CPUのキャッシュのライン更新状態を把握／管理し、他のキャッシュと更新状態の情報を交換することで、どのキャッシュに最新のデータが存在するかを知り、各キャッシュが必要なときに最新のデータを取得できるように自身の状態を変更したりラインのパージを行う。この情報交換は共通のデータバスを介して行われるため、情報の通知と実際のデータ転送との順序が保たれ、破綻を起こすことはない。逆に共通バスを持たない分散型メモリシステムには用いることが困難などの制約もある。このプロトコルとして下記のものが知られている。

無効型プロトコル (Invalidate Protocol): 複数のキャッシュから参照があるアドレスに対しあるキャッシュが更新を行う場合、そのアドレスはダーティであるとして参照中の全キャッシュの該当ラインを無効化する。これにより更新されたラインがありながら他のキャッシュで古いデータをキャッシングしている状態がなくなり、コヒーレンシが保たれる。MESI(Illinoisプロトコル)、MOSI(Berkeleyプロトコル)などがある。
更新型プロトコル (Update Protocol): 複数のキャッシュが参照しているアドレスに対してデータ更新を行うときはライトスルー型となり、単独でアクセスしている場合はライトバック型となるような制御を行うことで更新データを行き渡らせコヒーレンシを保つ。MEI(Fireflyプロトコル)、MOES(DRAGONプロトコル)などがある。

ディレクトリ方式 (Directory-based Protocol)

スヌープ方式と異なり、メモリの一貫性をディレクトリと呼ぶ専用領域にて一元管理する方式。この領域は実装上の各メモリ領域に分散してよく、分散メモリ型システムに適している。

共有キャッシュ (Shared Cache)

1つのキャッシュに対し複数のCPUが参照できるような構成を持つキャッシュ。1チップに集積された複数のCPUを扱うなど限定的な場面ではキャッシュコヒーレンシを根本的に解決するが、キャッシュ自体の構造が非常に複雑となる、もしくは性能低下要因となり、多くのCPUを接続することはより困難となる。

その他機構

プリフェッチ (Pre-fetch): CPUが専用命令などによりあらかじめデータをキャッシュに汲んでおく動作。データの流れがある程度予測できるような特定のソフトウエアアルゴリズムは、先んじてプリフェッチを行うことで実際にデータが必要な場面で余分なレイテンシがかかることなくスムーズに処理を行うことができる。例えばストリーミング処理のようなデータの流れや処理量などが単純で予測しやすい処理などは、プリフェッチを行うことで大幅に性能向上する場合がある。

目的別分類

命令キャッシュ: プログラムなどCPUの命令を格納するキャッシュ。命令は静的なデータなため、書き換えが発生せず(x86を除く最近のCPUは命令の自己書き換えなどには対応していない場合が多い)コヒーレンシを保つ必要がないと想定し、CPUからの入力はアドレスのみでデータ更新ユニットなどを省いている。
データキャッシュ: CPUが処理するデータを格納するキャッシュ。上述の構成をフルサポートしている場合が多い。命令キャッシュとデータキャッシュが分離され、命令バスとデータバスの2種類のバスがCPUに接続されているCPUをハーバードアーキテクチャと言う。現在のCPUはハーバードアーキテクチャが主流である。
実行トレースキャッシュ: インテルのPentium 4などは、インストラクション・セット・アーキテクチャ(ISA)はCISCであるが、内部でRISC的なマイクロ命令に変換し実行するアーキテクチャとなっている。単純な命令キャッシュと異なり、変換済みのマイクロ命令を再利用すれば命令デコーダの使用頻度を減らすことができる。Pentium 4ではL1命令キャッシュの代わりに約12000語の命令を格納できる8 ウェイ・セット・アソシエイティブの実行トレースキャッシュが搭載されている。
トランスレーションキャッシュ: x86(Pentiumなどに用いられているISA)の互換CPUメーカであるトランスメタが、そのコア技術として開発したコードモーフィングソフトウェア(CMS)用に主記憶装置上に確保している領域。Crusoeで16メガバイトの容量がある。CMSはx86命令を動的にCPUコアのネイティブ命令に変換し、変換後の命令を実行させる機構だが、このネイティブ命令に変換したプログラムを格納するキャッシュとして用いる。
スタックトップキャッシュ: コールスタックをハードウェアで実装したアーキテクチャでは、スタックトップの数バイトから数十バイトにアクセスが集中する。この部分をキャッシュするのがスタックトップキャッシュである。ISAからは存在に気づけない実装（トランスピュータなど）と、積極的にレジスタとして使用できる実装（AMD Am29000など）がある。後者の概念を発展させたものがレジスタ・ウィンドウである。

ソフトウェアへの影響

コヒーレンシの明示的な制御が必要となるような場合を除き、キャッシュメモリの存在はソフトウェアの挙動に対しては透過的である。一方、性能面ではキャッシュメモリの存在や仕様を意識することにより向上が図れることが知られている。

Solaris 2.4カーネルにて採用されたスラブアロケーション（英語版）では、構造体の特定のメンバにアクセスが集中する傾向を利用し、各スラブにてオブジェクト領域の先頭に異なるスラブ先頭からのオフセットを与えることにより、キャッシュライン内で頻繁にアクセスされる位置を分散させている。^[7]当時サンが販売していた製品ではメモリインターリーブに併せてキャッシュライン内をさらに複数のメモリバスに分割して割り当てていた。このためキャッシュライン内でアクセスが頻繁な箇所が特定の位置に集中するとキャッシュラインだけでなくメモリバスの負荷も分散されなくなってしまうことが問題となっており、スラブアロケーションはその解決策として使用された。

同一のキャッシュライン内に頻繁に更新されるデータとほとんど更新されないデータが共存していると、システム全体ではメインメモリへの書き戻しが必要なキャッシュライン数が増えてしまう。両者がキャッシュライン上で分離されるようにデータを配置すると、書き戻しが必要なキャッシュラインの数を減らして効率を上げることができる。LinuxカーネルやFreeBSDなど、GNU ldないしはその互換リンカをビルドに用いているOSでは、ほとんど更新されないデータをELFのある特定のセクションに定義することにより、そのようなデータだけを集めた上でキャッシュライン境界に整列させている。なお、上記のセクションに対してそのようなアドレス配置を実際にさせているのは、カーネルのリンク時に使用するリンカスクリプトである。^[8]^[9]

脚注

^ "to sustain Haswell’s CPU peak (e.g., 16 multiply-adds per cycle), a core must access 16 matrix elements (= 64 bytes) per cycle, all from memory ... assuming 2.0GHz processor, it requires memory bandwidth of: ≈ 64 × 2.0 GHz = 128 GB/s" 田浦. (2016). What You Must Know about Memory, Caches, and Shared Memory. 並列分散プログラミング, 東京大学.
^ "__m256 _mm256_fmadd_ps ... Throughput (CPI) ... Haswell ... 0.5" Intel Intrinsics Guide. 2022-04-03閲覧.
^ "A simple memcpy experiment ... 4.575611 GB/sec ... an almost proportional improvement up to 10 lists" 田浦. (2016). What You Must Know about Memory, Caches, and Shared Memory. 並列分散プログラミング, 東京大学.
^ "it requires memory bandwidth ... ≈ 20× more than it provides" 田浦. (2016). What You Must Know about Memory, Caches, and Shared Memory. 並列分散プログラミング, 東京大学.
^ "multi level caches ... recent processors have multiple levels of caches" 田浦. (2018). What You Must Know about Memory, Caches, and Shared Memory. 並列分散プログラミング, 東京大学.
^ "multiple levels of caches (L1, L2, . . . )" 田浦. (2018). What You Must Know about Memory, Caches, and Shared Memory. 並列分散プログラミング, 東京大学.
^ Bonwick, Jeff (6 June 1994). "The Slab Allocator: An Object-Caching Kernel". USENIX Summer 1994 Technical Conference. USENIX.
^ Torvalds, Linus. “arch/x86/kernel/vmlinux.lds.S at master”. GitHub. 2024年5月26日閲覧。 Linux カーネル、x86のリンカスクリプト。セクション.data..read_mostlyが該当、マクロREAD_MOSTLY_DATA()を用いて間接的に定義。
^ The FreeBSD Project. “sys/conf/ldscript.amd64 at main”. GitHub. 2024年5月26日閲覧。 FreeBSD カーネル、amd64のリンカスクリプト。セクション.data.read_mostlyが該当。

参考文献

ヘネシー, ジョン・L、パターソン, デイビッド・A 著、富田眞冶 / 村上和彰 / 新實治男訳『コンピュータ・アーキテクチャ　設計・実現・評価の定量的アプローチ』日経BP社、1993年5月。ISBN 4-8222-7152-8。
ヘネシー, ジョン・L、パターソン, デイビッド・A 著、成田光彰訳『コンピュータの構成と設計　ハードウエアとソフトウエアのインタフェース』上（第2版）、日経BP社、1999年5月。ISBN 4-8222-8056-X。
ヘネシー, ジョン・L、パターソン, デイビッド・A 著、成田光彰訳『コンピュータの構成と設計　ハードウエアとソフトウエアのインタフェース』下（第2版）、日経BP社、1999年5月。ISBN 4-8222-8057-8。
中森, 章『マイクロプロセッサ・アーキテクチャ入門　RISCプロセッサの基礎から最新プロセッサのしくみまで』CQ出版社〈TECHI Vol.20〉、2004年4月。ISBN 4-7898-3331-3。
インテル株式会社『IA-32 インテルアーキテクチャソフトウェア・デベロッパーズ・マニュアル』。

意義