Microsoft PowerPoint - No14…L………b…V…–…†…‡…−.ppt

Transcription

1 メモリ アーキテクチャ2 キャッシュメモリ 計 算 機 アーキテクチャ ( 第 14 回 目 ) 今 井 慈 郎 ([email protected])

2 キャッシュメモリ(cache memory) CPU 内 部 (or 周 辺 )に 設 けられた 高 速 小 容 量 メモリ キャッシュメモリに 使 用 頻 度 の 高 いデータを 格 納. 低 速 な 主 記 憶 へのアクセスを 低 減. 結 果 として, CPU 処 理 を 高 速 化 最 近 のCPUでは,キャッシュメモリをn 段 階 (n 種 類 ) 搭 載.CPUが,まず,i 次 キャッシュにデータを 読 み に 行 き,もしデータがなければ,(i+1) 次 キャッシュ へアクセス(i=1,2, n=2,3). i 次 キャッシュの 速 度 > (i+1) 次 キャッシュの 速 度 i 次 キャッシュの 容 量 < (i+1) 次 キャッシュの 容 量

3 キャッシュ(cache) 使 用 頻 度 の 高 いデータを 高 速 アクセス 可 能 な 記 憶 装 置 に 蓄 えておくことで,いちいち 低 速 な 装 置 から 読 み 出 す 無 駄 を 省 いて 高 速 化 すること.また,その 際 に 使 われる 高 速 な 記 憶 装 置. ( 例 ) 主 記 憶 はハードディスクと 比 較 すれば 高 速 デー タアクセスが 可 能. 使 用 頻 度 の 高 い( 入 出 力 )データ をメモリ 内 に 保 持.ハードディスク 上 にデータ 総 て 置 いた 場 合 よりも 処 理 を 高 速 化 : 主 記 憶 がハードディス クのキャッシュとして 動 作 ( 例 ) 通 信 では, 低 速 な 通 信 回 線 による 読 込 み 済 み データをハードディスクに 蓄 積 : 次 からはハードディ スクをキャッシュとして 高 速 データ 閲 覧 可 能

4 キャッシュ(cache) 但 し, 単 に キャッシュ と 表 記 した 場 合,コンピュータ 内 の 主 記 憶 (メインメモリ)よりもさらに 高 速 アクセスが 可 能 な CPU 内 部 に 用 意 された キャッシュメモリ を 指 す 場 合 が 一 般 的 である. ここでは, キャッシュ = キャッシュメモリ として 話 を 進 める.

5 キャッシュメモリとは No1 メモリシステムの 高 速 化 技 法 の1つであるキャッシン グ(caching)に 使 われるメモリ データを 遣 り 取 りする2つのデバイス 間 に 速 度 差 が 存 在 すると, 遅 いほうのデバイスがボトルネックにな り, 速 いほうのデバイスが 本 来 の 性 能 を 発 揮 できな い( 相 手 の 動 作 を 待 つため). この 速 度 差 を 緩 衝 するのがキャッシュメモリの 役 目

6 キャッシュメモリとは No2 メインメモリに 使 われているDRAMの 速 度 はCPUに 比 べて 遅 く,CPUの 命 令 実 行 速 度 を 下 げる 原 因 問 題 解 決 のため,CPU メインメモリ 間 にキャッシュメ モリと 呼 ばれる 高 速 & 小 容 量 メモリを 配 置 CPUがアクセスする 頻 度 の 高 いコード&データを 可 能 な 限 りキャッシュメモリに 格 納 CPUがメインメモリのあるアドレスからデータを 読 み 込 む 時,キャッシュにそのデータを 蓄 積.その 後, CPUが 再 び 同 じアドレスからデータを 読 み 込 もうとし たら,メインメモリの 代 わりにキャッシュからデータを 供 給.CPUは 低 速 なメインメモリに 待 たされることなく, 必 要 なデータを 読 み 込 める

7 キャッシュメモリとは No3 書 き 込 みの 場 合 は, ライトスルー や ライトバック といったアルゴリズムによりキャッシュの 性 能 は 変 化 メモリシステムの 高 速 化 のため,キャッシュメモリを2 段,3 段 と 重 ねて 実 装 する 場 合 あり. 486 以 降 のx86 CPUは1K~16Kbytes 程 度 の1 次 キャッ シュをCPU 内 部 に 内 蔵 IBM-PC 互 換 機 では, 高 速 SRAMを 用 いて64K~ 1Mbytes 程 度 の2 次 キャッシュを 実 装 CPUに 内 蔵 されているキャッシュ: 内 部 キャッシュ CPUの 外 部 に 実 装 されるキャッシュ: 外 部 キャッシュ

8 キャッシュメモリとは No4 ( 少 し 学 術 的 に 表 現 すると)CPUなど 処 理 装 置 が 命 令 やデータなどの 情 報 を 取 得, 更 新 する 際 に 主 記 憶 やバスなどの 遅 延 あるいは 低 帯 域 を 隠 蔽 化 させ, 処 理 装 置 と 記 憶 装 置 の 性 能 差 を 埋 めるために 用 いる 高 速 小 容 量 メモリ これを キャッシュメモリ と 呼 ぶ コンピュータはデバイスの 性 能 上, 記 憶 装 置 の 性 能 が 処 理 装 置 の 性 能 に 追 いつけず,この 差 が 全 体 性 能 に 対 するボトルネックとなる.これを ノイマンズ ボトルネック (von Neumann Bottle Neck)と 呼 ぶ.こ れは 拡 大 の 傾 向 あり. キャッシュメモリは, 記 憶 階 層 の 観 点 からこのボト ルネックを 解 消 しようとするもの

9 キャッシュメモリとは No5 CPUと 主 記 憶 との 間 に 構 成 されることが 一 般 的 CPUがアクセスしたいデータやそのアドレス, 状 態, 設 定 など 属 性 情 報 をコピーし 保 持 することで, 本 来 アクセスすべき 主 記 憶 に 代 わってデータの 入 出 力 を 行 う. 通 常,キャッシュメモリが 自 動 的 にデータ 保 存 や 主 記 憶 の 代 替 を 行 うため, 基 本 的 にCPUのプログラムが キャッシュを 意 識 する 必 要 なし. 特 定 のデバイスの 処 理 速 度 を 高 速 化 させる 場 合 に 利 用 される 場 合 もある.

10 キャッシュメモリの 構 造 No1 キャッシュメモリはデータをライン(ブロック)と 呼 ぶま とまった 単 位 で 管 理 ( 例 えばIntel Pentium4の8k Byte L1キャッシュはラインサイズ64Byte) データのアクセス 要 求 があった 時 にそのデータが キャッシュに 存 在 しているか,あるならどのラインかな どを 瞬 時 ( 一 般 に,1サイクルのスループット)に 検 索 する 必 要 あり. そのため,データ 格 納 アドレスの 一 部, 具 体 的 にはラ イン 単 位 アドレスの 下 位 数 ビット(エントリアドレス)に より,ある 程 度 の 格 納 位 置 を 限 定 することで 検 索 速 度 を 向 上

11 キャッシュメモリの 構 造 No2 各 ラインにはライン 単 位 アドレスの 上 位 ビット(フレー ムアドレス)を 格 納 キャッシュ 検 索 時 には 検 索 アドレスのフレームアドレ ス 部 と,キャッシュ 内 に 格 納 されている 検 索 エントリア ドレス 位 置 に 対 応 したフレームアドレスとを 比 較 これにより,キャッシュのヒット( 望 みのデータがキャッ シュ 内 に 存 在 )を 検 出 この フレームアドレス 格 納 バッファ をタグと 呼 ぶ. 複 数 セットのタグを 持 てば 同 じエントリアドレスでも 複 数 データの 格 納 を 行 うことが 可 能 このタグのセット 数 (ウエイ)を 連 想 度 と 呼 ぶ.データ 格 納 構 造 の 相 違 は 連 想 度 の 相 違

12 キャッシュメモリの 構 造 No3 ダイレクトマップ 方 式 (Direct Mapping) 1 組 のタグにより 構 成 ( 連 想 度 1)されるデータ 格 納 構 造.アドレスにより 一 意 に 配 置 が 決 まるため,タグの 構 造 が 非 常 に 単 純. 同 一 エントリに 異 なるフレームアドレスが 転 送 される と 必 ずラインの 入 れ 替 えが 発 生 ラインの 入 れ 替 えが 頻 発 し,スループットが 落 ちる(こ れをキャッシュスラッシングという)と,ヒット 率 が 低 下 他 の 方 式 に 比 べて 効 率 (ヒット 率 )は 高 くない.

13 キャッシュメモリの 構 造 No4 セットアソシアティブ 方 式 (Set Associative) 複 数 タグにより 構 成 ( 連 想 度 2 以 上 ). 同 一 エントリに 異 なるフレームアドレスのデータを 複 数 格 納 することが 可 能. 連 想 度 が 上 がるほどキャッシュのヒット 率 は 上 昇 する が 実 装 は 困 難 になっていくため,システムによりバラ ンスのよい 実 装 が 必 要. n 個 のタグにより 構 成 された 場 合,nウエイセットアソ シアティブ 方 式 と 呼 ぶ. 最 近 はCAM ( 連 想 メモリ: Content Addressable Memory)がタグとして 使 用 32など 非 常 に 高 い 連 想 度 を 実 装 できるようになる.

14 キャッシュメモリの 構 造 No5 フルアソシアティブ 方 式 (Fully Associative) エントリアドレスによる 振 り 分 けはなく, 全 ての ラインが 検 索 対 象 となる 構 造. 従 って 連 想 度 はライン 数 分. キャッシュスラッシングは 起 こり 難 くヒット 率 は 最 も 優 れている. 実 装 コストや 複 雑 度 の 面 から 通 常 用 いられる ことはない.

15 キャッシュメモリの 構 造 No6 ヒット 率 フルアソシアティブ 方 式 セットアソシアティブ 方 式 ダイレクトマップ 方 式 検 索 速 度 ダイレクトマップ 方 式 セットアソシアティブ 方 式 フルアソシアティブ 方 式 ヒット 率 も 検 索 速 度 もある 程 度 を 確 保 : セットアソシアティブ 方 式 が 無 難!?

16 キャッシュメモリの 実 装 No1 ライン 入 替 え 方 式 (Refill) ラインの 入 替 え(これを リフィル と 呼 ぶ)は 該 当 エン トリの 全 ラインにデータが 格 納 されて,なお 同 一 エン トリ 新 規 フレームアドレスが 入 力 されて,キャッシュの ミスヒットが 生 じた 場 合 に 起 きる. その 場 合,どのラインを 掃 き 出 して 新 規 アドレスと 入 替 えるか,はアルゴリズムによるが,それによって キャッシュのヒット 率 が 変 動. アルゴリズムとして, 代 表 例 は, ラウンドロビン LRU あるいは ランダム などがある.

17 キャッシュメモリの 実 装 No2 ラウンドロビン (Round Robin) 方 式 リフィル 対 象 となるラインを 順 番 に 交 代 させる 方 法. 各 ラインのアクセス 頻 度 に 拘 らず 順 番 にリフィ ルを 実 行. あまりヒット 率 は 高 くない.

18 キャッシュメモリの 実 装 No3 LRU (Least Recently Used) 方 式 最 も 古 くアクセスされたラインをリフィルする 方 法. 時 間 的 局 所 性 に 基 づき, 過 去 最 もアクセスのなかっ たラインは 将 来 にわたってもアクセスされる 可 能 性 は 少 ない と 言 える. 従 って,この 方 法 はヒット 率 がかなり 高 い 方 法 として よく 採 用 される. 但 し, 各 ラインごとにアクセス 履 歴 を 持 ち,アクセスが ある 度 に 履 歴 を 入 替 える 必 要 があるため, 複 雑 な 履 歴 を 反 映 させる 構 成 が 必 要 結 果 として,アクセス 速 度 を 低 下 させるなどの 負 の 影 響 も 懸 念 される 場 合 がある.

19 キャッシュメモリの 実 装 No4 ランダム (Random) 方 式 リフィルするラインの 選 択 をランダムに 行 う 方 式. 各 ライン 毎 にリフィル 用 の 特 殊 な 機 構 を 持 つ 必 要 はない. 従 って,キャッシュの 構 成 が 簡 易. ヒット 率 はラウンドロビンよりは 良 いとされる.

20 キャッシュメモリの 実 装 No5 データ 更 新 方 式 (Purging) CPUキャッシュは 命 令 キャッシュ と データキャッ シュ の2 種 類 が 搭 載 されている 場 合 が 多 い. 命 令 キャッシュ:プログラムという 静 的 なデータを 扱 う のでデータ 更 新 は 存 在 しない. データキャッシュ:メモリへのライト 動 作 があるため, データ 更 新 が 存 在 する. 更 新 されたデータはどこかのタイミングで 下 位 レベル のメモリ( 主 記 憶 あるいは 高 次 キャッシュ)にも 反 映 さ れる 必 要 があり. そのタイミングの 相 違 により2つのアルゴリズムが 存 在 する.

21 キャッシュメモリの 実 装 No6 ライトスルー 方 式 (Write Through Algorithm) CPUがメモリ 書 き 込 みを 行 うと,キャッシュにストアす ると 同 時 に 下 位 レベルのメモリにも 書 き 戻 す 方 式. 必 ず 下 位 レベルのバスが 活 性 化 するため,バスの 競 合 や 下 位 レベルの 低 いスループットに 影 響 されるな どの 制 約 あり. しかし, 単 純 な 構 成 で 実 現 でき,またデータのコヒー レンシを 保 つことが 容 易. 出 力 段 にライトバッファを 設 けると, 単 一 CPUであれ ばライトバック 方 式 と 遜 色 のない 性 能 が 期 待 できる. CPUのL1キャッシュなどに 実 装 される 場 合 が 多 い.

22 キャッシュメモリの 実 装 No7 ライトバック 方 式 (Write Back Algorithm) その1 CPUがメモリ 書 き 込 みを 行 っても, 条 件 が 整 わない 限 り, 書 き 換 えはキャッシュ 内 に 留 まり, 下 位 メモリへの 書 き 戻 しを 同 時 には 行 わない 方 式. 書 き 戻 す 条 件 は 対 象 エントリにウエイ 数 以 上 のフレー ムアドレスのリード/ライトが 行 われる, 他 のバスマ スタが 対 象 エントリが 保 持 しているアドレスに 対 しアク セスを 行 った 時 にコヒーレンシ(Coherency: 一 貫 性 の こと)を 保 つために 行 うなどがある. 要 するにライ ン 入 替 え(リフィル)などが 発 生 しなければ, 書 き 戻 さ ない.

23 キャッシュメモリの 実 装 No8 ライトバック 方 式 (Write Back Algorithm) その2 ライトスルー 方 式 に 対 し, 下 位 レベルのバスが 競 合 を 起 こしにくい( 頻 繁 にメモリアクセスが 発 生 しないの で),マルチCPU 構 成 に 向 く. 従 って, 記 憶 階 層 の 同 一 レベルに 複 数 のキャッシュ が 接 続 されているようなL2キャッシュ(あるいはそれ より 高 次 のメモリ)に 実 装 されることが 一 般 的.

24 キャッシュメモリ( 上 級 編 ) その1 キャッシュ コヒーレンシ(Cache Coherency) その1 マルチCPU&マルチキャッシュ 構 成 など 複 数 のバス マスタが 存 在 し, 各 々がデータ 更 新 を 行 った 場 合 で も 最 新 の 正 しいデータにアクセスできるよう 保 つべき データの 一 貫 性 (あるいは 整 合 性 )のことを キャッ シュ コヒーレンシ もしくは キャッシュ コンシステン シ (cache consistency)という. データ 更 新 にライトバック 方 式 を 用 いた 場 合 など, キャッシュに 更 新 されたデータが 滞 留 して 主 記 憶 装 置 など 下 位 レベルのメモリには 最 新 のデータが 存 在 しない 可 能 性 がある. これは 問 題!!

25 キャッシュメモリ( 上 級 編 ) その1 キャッシュ コヒーレンシ(Cache Coherency) その2 この 時 に 複 数 のCPUが 同 一 の 記 憶 領 域 を 参 照 / 更 新 しようとすると,データの 不 整 合 が 起 こり, 正 しい 結 果 が 得 られない. これを 解 決 し,どのCPUも 必 ず 最 新 のデータにアク セスできるようにする 必 要 がある. このための 代 表 的 なアルゴリズムとして,1)スヌー プ 方 式,2)ディレクトリ 方 式 あるいは3) 共 有 キャッシュ などがある.

26 キャッシュメモリ( 上 級 編 ) その2 スヌープ 方 式 (Cache Snooping) その1 キャッシュコヒーレンシのアルゴリズムにおいて, 特 に 各 キャッシュ 自 身 に 搭 載 される 方 法 としてスヌープ 方 式 がある. これは 各 々のキャッシュが 自 身 や 他 CPUのキャッシュ のライン 更 新 状 態 を 把 握 管 理 し, 他 のキャッシュと 更 新 状 態 の 情 報 を 交 換 することで,どのキャッシュに 最 新 のデータが 存 在 するかを 知 り, 各 キャッシュが 必 要 なときに 最 新 のデータを 取 得 できるように 自 身 の 状 態 を 変 更 したりラインのパージなどを 行 う.

27 キャッシュメモリ( 上 級 編 ) その2 スヌープ 方 式 (Cache Snooping) その2 この 情 報 交 換 は 共 通 のデータバスを 介 して 行 われる ため, 情 報 の 通 知 と 実 際 のデータ 転 送 との 順 序 が 保 たれ, 破 綻 を 起 こすことはない. 逆 に 共 通 バスを 持 たない 分 散 型 メモリシステムには 用 いることが 困 難 などの 制 約 もある.

28 キャッシュメモリ( 上 級 編 ) その2 スヌープ 方 式 (Cache Snooping) その3 1) 無 効 型 プロトコル (Invalidate Protocol) 複 数 のキャッシュから 参 照 があるアドレスに 対 しある キャッシュが 更 新 を 行 う 場 合,そのアドレスはダーティ であるとして 参 照 中 の 全 キャッシュの 該 当 ラインを 無 効 化 する. これにより 更 新 されたラインがありながら 他 のキャッ シュで 古 いデータをキャッシングしている 状 態 がなく なり,コヒーレンシが 保 たれる.

29 キャッシュメモリ( 上 級 編 ) その2 スヌープ 方 式 (Cache Snooping) その4 2) 更 新 型 プロトコル (Update Protocol) 複 数 のキャッシュが 参 照 しているアドレスに 対 してデー タ 更 新 を 行 うときはライトスルー 型 となり, 単 独 でアク セスしている 場 合 はライトバック 型 となるような 制 御 を 行 う. 従 って, 更 新 データを 他 にも 行 き 渡 らせ,コヒーレン シを 保 つ.

30 キャッシュメモリ( 上 級 編 ) その2 ディレクトリ 方 式 (Directory-based Protocol) スヌープ 方 式 と 異 なり,メモリの 一 貫 性 をディレクトリ と 呼 ぶ 専 用 領 域 にて 一 元 管 理 する 方 式. この 領 域 は 実 装 上 の 各 メモリ 領 域 に 分 散 してよく, 分 散 メモリ 型 システムに 適 する.

31 キャッシュメモリ( 上 級 編 ) その2 共 有 キャッシュ (Shared Cache) 1つのキャッシュに 対 し 複 数 のCPUが 参 照 できるよう な 構 成 を 持 つキャッシュ. 1チップに 集 積 された 複 数 のCPUを 扱 うなど 限 定 的 な 場 面 ではキャッシュコヒーレンシを 根 本 的 に 解 決 可 能. しかし,キャッシュ 自 体 の 構 造 が 非 常 に 複 雑,もしく は 性 能 低 下 の 要 因 多 くのCPUを 接 続 することは 困 難