キャッシュメモリ
キャッシュメモリ (cache memory) は、CPUなど
キャッシュの
意義 [編集 ]
データ帯域 [編集 ]
キャッシュメモリは
構成 [編集 ]
キャッシュメモリは、
キャッシュ階層 [編集 ]
データ格納 構造 [編集 ]
キャッシュメモリはデータをライン(ブロック)と
- ダイレクトマップ
方式 (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キャッシュは
- ライトスルー
方式 (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 と
呼 ばれる。ライトミスしたアドレスのデータはキャッシュにロードされず、データは下位 の記憶 階層 に書 き込 まれる。このアプローチでは、データロードは、リードミス時 にのみ発生 する。
- Write allocate は fetch on write とも
キャッシュコヒーレンシ (Cache Coherency)[編集 ]
マルチ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カーネルにて
脚注 [編集 ]
- ^ "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 インテル アーキテクチャ ソフトウェア・デベロッパーズ・マニュアル』。