キャッシュとキャッシュ 技 術 71
定 義 アクセス 要 求 を 発 行 する 機 構 と,その 供 給 に 応 える 機 構 との 中 間 に 位 置 し,すべての 要 求 を 検 知 して 処 理 するよう 構 築 される. キャッシュは 選 択 されたデータの 局 所 的 なコピーを 保 持 し, 可 能 な 場 合 にはアクセス 要 求 にこたえる. 通 常 のメモリ 機 構 より 高 速 に 動 作 するよう 設 計 されている メモリアクセス 時 間 の 短 縮 など, 性 能 向 上 を 目 指 す. メモリ アクセス 時 間 1G 当 たりのコスト SRAM 0.5~2.5nS 2000~5000ドル DRAM 50~70nS 20~75ドル 磁 気 ディスク 5~20mS 0.2~2ドル 72
時 間 的 局 所 性 と 空 間 的 局 所 性 73
キャッシュの 特 徴 小 容 量 メインメモリの10% 程 度 の 小 容 量 常 時 動 作 要 求 されたデータがキャッシュで 利 用 可 能 か 可 能 でないなら,メインメモリからのコピーを 取 り 出 し たり,どのデータをキャッシュ 上 に 保 持 するか 決 定 す る 機 構 透 過 性 要 求 側 から 見 えるインターフェイスは,メインメモリに 示 すインターフェイスと 同 一 自 動 性 どのデータを 保 持 するかなどの 命 令 はない 74
キャッシュ 技 術 の 重 要 性 情 報 を 検 索 するほぼすべてのハードウエアやソフトウエア システムにおいて 利 用 される, 基 本 的 な 最 適 化 技 術 キャッシュ 内 に 保 持 されたデータが 特 定 の 形 式 や,サイズ 制 限 されない 小 規 模 データ(バイトやワードメモリ) 中 規 模 データ(メモリのセグメントやページ) 大 規 模 データ(プログラム 全 体 ) 包 括 的 なデータ(ファイルやディスクブロック) アプリケーションに 特 化 したデータ (Webページやワープロ 文 書,データベース 登 録 データ) 文 書 データ( 電 子 メールなど) 75
キャッシュにおける 用 語 キャッシュヒット メインメモリへのアクセスを 必 要 とせず, 要 求 がキャッシュ によって 満 足 されること キャッシュミス キャッシュによっては, 要 求 が 満 足 されないこと 76
最 善, 最 悪 の 場 合 のキャッシュ 性 能 ヒットした 場 合 のコスト c h ミスヒット 時 のコストc m c m c h 要 求 元 キャッシュ メインメモリ 77
N 個 の 連 続 したアクセス 列 についての, 最 良, 最 悪 の 振 舞 い すべてのアクセスがあらたなデータを 参 照 する 場 合 : 最 悪 時 キャッシュによる 性 能 の 改 善 はない 最 悪 時 のコスト c worst c worst =Nc m アクセスごとの 平 均 コスト= c m 連 続 するすべてのアクセスが, 同 じデータを 指 す 場 合 キャッシュによる 性 能 の 改 善 は 最 良 最 善 時 のコスト c best c worst =c m +(N-1) c h アクセスごとの 平 均 コスト = + : 平 均 コスト キャッシュによる 性 能 は,キャッシュが 存 在 しない 場 合 に 比 べ 悪 くはならない 78
典 型 的 な 連 続 アドレスにおけるキャッシュ 性 能 ヒット 率 = ヒットしたアクセス 数 全 アクセス 数 ミス 率 =1-ヒット 率 データ 記 憶 にアクセスするコスト コスト= + 1 :ヒット 率 キャッシュ 性 能 の 改 善 : ヒット 率 の 向 上 ヒット 時 のコストの 低 減 79
キャッシュ 置 き 換 えポリシー 新 たなデータを 無 視 するのか, 新 たなデータのための 場 所 を 確 保 するために,どの 古 いデータをキャッシュ 上 から 消 去 するのか LRU(Least Recently Used) 置 き 換 え 最 も 長 い 期 間 参 照 されなかったデータを 置 き 換 える キャッシュメカニズムは 現 在 キャッシュ 上 にあるデータ 項 目 のリストを 保 持 データの 参 照 後,リストの 最 前 部 に 移 動 データの 置 き 換 えはリストの 最 後 部 から 80
多 重 レベルキャッシュ 階 層 コスト= 1 + 2 + 1 1 2 1, 2 :ヒット 率 c h1 c h2 c m 要 求 元 キャッシュ #1 キャッシュ #2 メインメモリ 81
先 読 みキャッシュ システム 起 動 時 : キャッシュがメインメモリよりデータを 読 み 出 すため 初 期 ヒット 率 は 極 端 に 低 下 キャッシュの 先 読 み(pre-load)により, 起 動 時 の 負 荷 を 低 減 関 連 するデータを 先 読 み(pre-fech) プロセッサが1バイトアクセスする 際,64バイトプリ フェッチ 2バイト 目 からはキャッシュがヒット 82
メモリシステムにおけるキャッシュ メモリ: 高 価 で 低 速 キャッシュ: 高 速 メモリの 高 いコストをかけずに 性 能 改 善 83
物 理 メモリキャッシュ 同 時 実 行 ( 並 列 処 理 ) リードアク セス 要 求 メインメモリに 対 してリー ドアクセス 要 求 発 行 メインメモリに 対 してメモリ 処 理 の 中 断 要 求 Yes キャッシュ 上 に 存 在 するか 検 索 存 在 No メモリ 処 理 の 完 了 を 待 機 並 列 性 を 実 現 ハードウエアは 複 雑 化 メモリからの データを 保 存 CPUへのデータ 転 送 同 時 実 行 ( 並 列 処 理 ) 84
メモリキャッシュの 実 現 キャッシュのエントリ メモリアドレスとそのアドレスで 示 されるバイト 列 各 エントリごとに 完 全 なアドレスを 保 持 することは 非 効 率 必 要 となる 空 間 の 容 量 削 減 のための 技 術 ダイレクトマッピング セットアソシアティブ 85
ダイレクトマッピングキャッシュ 2つのアドレスはキャッシュ 内 の1つの 空 きスロットを 奪 い 合 う A1への 参 照 は,キャッシュ 内 のA1の 値 を 読 み 出 し,A2への 参 照 はA2の 値 を 読 み 出 す 交 互 に 参 照 すると,すべての 参 照 はキャッシュミス セットアソシアティブキャッシュ A1が2つのキャッシュ 内 の1つに 置 かれ,A2はもう 一 方 に 格 納 することができる 交 互 の 参 照 でも,すべてキャッシュはヒットする 並 列 度 が 増 すと, 性 能 は 向 上 86
セットアソシアティブキャッシュ 複 数 のキャッシュを 管 理 同 時 にそれらすべてを 検 索 できるハードウエア 複 数 のキャッシュを 扱 うため, 同 じ 番 号 を 持 つブロックを1つ 以 上 格 納 可 能 87
ダイレクトマッピング 方 式 のキャッシュ キャッシュはバイトアドレッシング メモリとキャッシュを 同 一 のサイズのブロック 群 に 分 割 ブロックごとのメモリの 取 り 扱 い メモリ ブロック 0 1 2 3 0 タグ 値 4 5 6 7 1 0 8 9 10 11 2 12 13 14 15 3 1 2 3 メモリ ブロック 0 1 2 3 0 1 2 3 0 タグ0 タグ1 88 1
ダイレクトマッピング 方 式 インデックス キャッシュ 000 001 010 011 100 101 110 111 ブロック 数 :8 ブロックの 大 きさ:1ワード 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 メモリ タグ 0 0 0 1 キャッシュ 中 のブロック 番 号 89
ダイレクトマッピング 方 式 のキャッシュの 動 作 例 参 照 先 の10 進 参 照 先 の2 進 割 り 当 てられている ヒット/ミスの 別 アドレス アドレス キャッシュ ブロック 22 10110 ミス 110 26 11010 ミス 010 22 10110 ヒット 110 26 11010 ヒット 010 16 10000 ミス 000 3 00011 ミス 011 16 10000 ヒット 000 18 10010 ミス 010 16 10000 ヒット 000 90
インデックス 有 効 タグ データ 000 N 001 N 010 N 011 N 100 N 110 N 111 N 電 源 投 入 直 後 インデックス 有 効 000 N 001 N 010 N 011 N タグ データ 100 N 110 Y 10 メモリ(10110) 111 N アドレス 10110 のミスを 処 理 した 後 91
アドレスとキャッシュインデックスの 関 係 31 30 29 13 12 タグフィールド 11 10 3 2 1 0 ブロック 数 =2 10 20 10 index 有 効 タグ データ 0 1 1bit 20bit 32bit バイトオフセット アドレス 32bit = 4byte 2bit 1kword=4kbyteキャッシュ 2 データ 32 1023 20 ブロック 数 :1024 : 10bit ブロックの 大 きさ:1ワード = ヒット 92
31 タグフィールド n m 2 0 キャッシュ 容 量 :2 n ブロック キャッシュインデックス:n bit ブロックサイズ: 2 m ワード(= 2 m+2 バイト) ブロッ ク 番 号 有 効 タグ #0ワード #1ワード... #(2 m -1)ワー ド 0 1 32-(n+m+2) bit 32 bit 32 bit 32 bit 32 bit 1... 2 n -1 1ブロック=2 m ワード 2 n ( 有 効 フィールド 長 + タグ 長 + ブロックサイズ) = 2 n ( 1+(32-(n+m+2) +2 m 32) 93
16kバイトのデータを 保 持 するダイレクトマップ 方 式 の キャッシュに 必 要 なビット 数.ブロックサイズは4word, アドレスは32bitとする 94
16kバイトのデータを 保 持 するダイレクトマップ 方 式 の キャッシュに 必 要 なビット 数.ブロックサイズは4word, アドレスは32bitとする 1word=4byte, 16kbyte=4kword, ブロックサイズが4word キャッシュのブロック 数 =1k=2 10 31 0 タグフィールド=32-14 10 2 2 有 効 タグ #0word #1word #2word #3word 0 1 18 32 32 32 32 1 1023 95 1024 (1+18+4 32)=1024 147=147kbit
ブロックサイズが16バイトの64 個 のブロックからなる キャッシュがある.バイトアドレスが1200 番 地 のブロッ ク 番 号 はいくらか 96
ブロックサイズが16バイトの64 個 のブロックからなる キャッシュがある.バイトアドレスが1203 番 地 のブロッ ク 番 号 はいくらか ブロックアドレスは =75 このブロックアドレスに 対 するキャッシュブロック 番 号 は 75を64で 割 った 余 りの11 ちなみにこのブロック 番 号 75のブロックには,1200 番 地 から 1215 番 地 のバイトアドレスに 対 応 有 効 タグ #0 #1 #15 0 1 97 63
ブロックサイズとヒット 率 大 きなブロック ミス 率 を 下 げられる ( 空 間 局 所 性 の 活 用 ) 反 面,キャッシュ 容 量 に 対 する 相 対 的 なブロック 数 を 大 きくするとミス 率 の 上 昇 につながる また,ミス 時 のミスペナルティの 増 大 にもつながる ミ ス 率 10 5 0 32 64 128 ブロックサイズ 4K 16K 64K キ ャ ッ シ ュ 容 量 98
キャッシュミスの 取 り 扱 い 1. 元 のプログラムカウンタ 値 ( 現 在 のPC-4)をメモリ に 転 送 2. 主 記 憶 から 読 み 出 しを 行 うよう 指 示, 完 了 を 待 機 3. キャッシュの 該 当 するブロックに 書 き 込 みを 行 う. その 際, 主 記 憶 から 読 み 出 したデータをキャッシュ のデータ 部 分 に 格 納 し,アドレスの 上 位 4ビットを ALUからタグフィールドへ 収 め, 有 効 ビットをON 4. 実 行 命 令 を 最 初 のステップから 再 開. ( 命 令 をフェッチしなおすことにより,キャッシュ はヒットする) 99
ライトスルーとライトバック キャッシュ: 読 み 出 し 性 能 の 改 善 目 的 書 き 込 み 要 求 のためのものではない ライト 操 作 によって, 元 のメモリの 値 を 変 更 が 必 要 メモリに 転 送 を 要 求 するだけでなく,キャッシュは 当 該 デー タの 有 無 を 探 索.もし 存 在 する 場 合,その 値 も 変 更 が 必 要 ライトスルーキャッシュ: キャッシュはコピーを 保 持.ライト 操 作 をメモリに 転 送 ライトバックキャッシュ: キャッシュがローカルにデータを 保 持, 必 要 時 にメモリに 値 を 書 き 込 む. どのデータを 書 き 戻 すか ダーティビット 100
書 き 込 みの 取 り 扱 い キャッシュと 主 記 憶 の 一 貫 性 の 保 持 ライト スルー 方 式 : キャッシュと 主 記 憶 に 毎 回 書 き 込 む 方 式 例 )メモリへの 書 き 込 み 時 間 :CPUの100サイクル 分 命 令 の10%がストア 命 令, 元 々CPUのCPIが1.0の 場 合 CPI = 1.0+100 10% = 11.0 性 能 が10 分 の1に 低 下 101
書 き 込 み 時 の 取 り 扱 い ライト バッファ 方 式 書 き 込 み 用 のバッファを 用 意 し,CPUはバッファへ の 書 き 込 みで 書 き 込 み 操 作 を 完 了 バッファから 主 記 憶 への 書 き 込 み 速 度 が,CPUの 書 き 込 み 派 生 頻 度 より 低 いと 効 果 ない ライト バック 方 式 書 き 込 み 発 生 時 はキャッシュのみに 書 き 込 み 置 き 換 え 対 象 になった 時 のみ, 主 記 憶 へ 書 き 込 み 複 雑 な 構 造 が 必 要 102
ライトバックキャッシュの 性 能 向 上 の 例 メモリ 内 に 値 を 増 加 させるプログラムにおけるループ ライトスルーキャッシュ: ループ 実 行 ごとに,メモリ 上 のデータを 更 新 する ライトバックキャッシュ: プログラム 実 行 中 は 値 をキャッシュ 上 に 保 持 ループ 終 了 後,メモリ 上 のデータを 更 新 103
キャッシュの 一 貫 性 (コヒーレンス) 2つのプロセッサが,それぞれキャッシュを 用 いてメモリに アクセスする 場 合 キャッシュの 一 貫 性 プロトコル(ハードウエアの 追 加 ) プロセッサ2がアドレスAからデータを 読 むとき, 一 貫 性 プロトコ ルは,キャッシュ2にキャッシュ1に 通 知 を 要 求 キャッシュ1がアドレスAのデータを 保 持 している 場 合,キャッ シュ1はデータを 最 新 のものに 更 新 プロセッサ1 プロセッサ2 キャッシュ1 キャッシュ2 メモリ 104
キャッシュを 支 援 する 記 憶 システム CPU CPU CPU キャッシュ キャッシュ キャッシュ インターリーブ 方 式 メモリバ ンク#0 メモリバ ンク#1 メモリバ ンク#2 メモリバ ンク#3 メモリ メモリ 105
キャッシュを 支 援 する 記 憶 システム キャッシュミス 発 生 時 : 必 要 な 語 は 主 記 憶 から 読 み 出 し 例 )アドレス 送 出 :1メモリバスクロックサイクル DRAMの 一 語 当 たりのアクセス 時 間 :15メモリバスクロックサイクル データの 一 語 の 転 送 :1メモリバスクロックサイクル キャッシュのブロックは4 語 から 構 成 DRAMのバンク 幅 が1 語 の 場 合 ミスペナルティ 1+4 15+4 1=65 メモリバスクロックサイクル メモリのデータ 幅 を2 語 長 1+2 15+2 1=33 メモリバスクロックサイクル バンク 数 4のメモリ 構 成 (インターリーブ) 1+1 15+4 1=20 メモリバスクロックサイクル 106
メモリストールとCPU 時 間 CPU 時 間 =( 実 行 クロック 数 +メモリストールクロック 数 ) クロックサイクル 時 間 キャッシュミスの 増 大 メモリストールクロック 数 の 増 大 メモリストールクロック 数 = 読 み 出 しストールクロック 数 + 書 き 込 みクロックストール 数 読 み 出 しストールクロック 数 =プログラム 当 たりの 読 み 出 し 件 数 読 み 出 しミス 率 読 み 出 しミスペナルティ 書 き 込 みストールクロック 数 =プログラム 当 たりの 読 み 出 し 件 数 書 き 込 みミス 率 書 き 込 みミスペナルティ+ 書 き 込 みバッ ファストール 107
メモリストールとCPU 時 間 メモリストールクロック 数 =プログラム 当 たりのメモリ アクセス 件 数 ミス 率 ミスペナルティ メモリストールクロック 数 =プログラム 当 たりのメモリ アクセス 命 令 件 数 1メモリアクセス 命 令 当 た りのミス 率 ミスペナルティ 108
例 題 1 あるコンピュータ 命 令 のキャッシュミス 率 =2% データのキャッシュミス 率 =4% プロセッサのCPI:メモリのストールなしで2 ミスペナルティ=すべてのミスに 対 して100クロックサイクル ミスのないプロセッサに 対 して,このコンピュータはどの 程 度 の 速 度 となるか.ただし,メモリアクセス 命 令 の 出 現 頻 度 は 36%に 想 定 109
解 答 例 命 令 数 を I とすると, 命 令 のミスクロック 数 =I 2% 100=2.0 I メモリアクセス 命 令 数 は36%なので データのミスクロック 数 =I 36% 4% 100=1.44 I よって1 命 令 当 たりのメモリストールの 合 計 クロック 数 は3.44 以 上 より メモリストールのあるCPU 時 間 完 全 キャッシュを 備 えたマシンのCPU 時 間 = 2+3.44 2 = 5.44 2 よってメモリストールがあると, 完 全 なキャッシュを 備 えるコン ピュータに 比 べその 性 能 は2.72 分 の1となる 110
例 題 2 例 題 1とクロック 周 波 数 も 含 め 同 一 条 件 下 でプロセッサを 高 速 なものにした 場 合 どうなるか プロセッサの 速 度 を 例 1の2CPIのものから,その 速 度 を2 倍 に 向 上 させCPIが1になったとする.この 場 合,メモリストールに 対 する 合 計 のクロック 数 は3.44と 変 化 はないので メモリストールのあるCPU 時 間 完 全 キャッシュを 備 えたマシンのCPU 時 間 = 1+3.44 1 = 4.44 1 となる.この 場 合,メモリストールに 要 する 時 間 の 割 合 は, 3.44/5.44=63%から3.44/4.44=77%へ 増 大 することになる 111
キャッシュミスの 影 響 例 題 2で 示 したように, 記 憶 システムを 変 えずにプロセッサの 速 度 のみを 向 上 させると,キャッシュミスによる 性 能 低 下 を 大 きくす る. このことは, 記 憶 システムを 変 えずにクロック 周 波 数 を 引 き 上 げ ても 同 様 に,キャッシュミスによる 性 能 低 下 を 大 きくする. また,ヒット 時 間 が 大 きくなると, 記 憶 システムからの 語 アクセス に 要 する 合 計 時 間 が 長 くなり, 結 果 としてプロセッサのクロックサ イクル 時 間 が 増 大 する 可 能 性 がある.このことは,キャッシュ 容 量 を 大 きくした 場 合 に, 注 意 が 必 要 である. キャッシュ 容 量 を 単 に 増 大 するのではなく, 多 段 階 のキャッ シュの 構 成 につながる 112
L1,L2,L3キャッシュ 多 くのコンピュータメモリシステム 背 景 2レベル 以 上 のキャッシュ 階 層 1. 伝 統 的 なメモリキャッシュは,メモリ,プロセッサ 双 方 から 独 立 していた 2. キャッシュへのアクセスには,プロセッサチップと 接 続 する 接 続 する 信 号 線 が 必 要 3. 外 部 ハードウエアに 信 号 線 を 使 うのは,チップ 内 の 機 能 ユニットにアク セスするのに 比 べ,アクセス 遅 延 大 4. 半 導 体 技 術 の 進 歩 により,チップ 内 に 搭 載 できるトランジスタ 数 増 大 プロセッサチップ 内 に2 次 キャッシュ 搭 載 L1キャッシュ:プロセッサチップ 内 (オンチップ) L2,L3キャッシュ:プロセッサチップ 外 (オフチップ) 113
平 均 メモリアクセス 時 間 AMAT ヒットした 場 合 とミスした 場 合 の 両 方 を 考 慮 したメモリアクセス 時 間 の 平 均 値 AMAT=ヒットした 場 合 のアクセス 時 間 +ミス 率 ミスペナルティ クロックサイクル 時 間 が1ns,ミスペナルティが20クロックサイク ル. 命 令 当 たりのミス 率 が0.05,キャッシュへのアクセス 時 間 が 1クロックサイクルであるプロセッサのAMATはいくらか.ただし, 読 み 出 しと 書 き 込 みのミスペナルティは 等 しいものとし,その 他 の 書 き 込 みストールは 無 視 する. AMAT=1+0.05 20=2 クロックサイクル,すなわち,2nsとなる 114
柔 軟 性 の 高 いブロックの 配 置 によるミスの 削 減 ダイレクトマッピング 方 式 メモリ ブロックを 配 置 するキャッシュの 場 所 が 特 定 フル アソシアティブ 方 式 メモリ ブロックを 配 置 するキャッシュの 場 所 が 任 意 セット アソシアティブ 方 式 メモリ ブロックを 配 置 するキャッシュの 場 所 が,あるきまった 数 n (セット 数 )に 定 められている nウエイ セット アソシアティブ 方 式 ダイレクトマッピング 方 式 1ウエイ セットアソシアティブ 方 式 フル セットアソシアティブ 方 式 (キャッシュがm 個 のブロック) 1ウエイ セットアソシアティブ 方 式 連 想 度 :1セットのブロック 数 115
ダイレクトマッピング 方 式 におけるブロックの 場 所 ブロック 番 号 をキャッシュ 内 のブロック 数 で 割 った 剰 余 フル アソシアティブ 方 式 キャッシュ 内 の 任 意 の 位 置 にブロックを 配 置 ブロックの 位 置 :キャッシュ 内 のすべての 要 素 の 探 索 が 必 要 セット アソシアティブ 方 式 におけるブロックが 含 まれるセットの 位 置 ブロック 番 号 をキャッシュ 内 のセット 数 で 割 った 剰 余 ブロックの 位 置 :セット 内 のすべての 要 素 の 探 索 が 必 要 ダイレクトマッピング ブロック 番 号 2ウエイセットアソシアティブ セット 番 号 0 1 2 3 4 5 6 7 0 1 2 3 フルセットアソシアティブ アドレス12のブロックが 格 納 される( 可 能 性 のある)キャッシュ 内 の 位 置 キャッシュは8ブロック 116
8ブロックのキャッシュがとりうる 形 態 ブロック 0 1 2 3 4 5 6 7 タグ データ ダイレクトマッピング 方 式 セット 0 1 2 3 タグ データ タグ データ 2ウエイ セットアソシアティブ 方 式 ほかに8ウエイセットアソシアティブ (フルアソシアティブ 方 式 )がある セット タグ データ タグ データ タグ データ タグ データ 0 1 4ウエイ セットアソシアティブ 方 式 117
キャッシュにおける 連 想 度 とミス セットアソシアティブ 方 式 連 想 度 を 増 やす 利 点 ミス 率 の 低 減 その 欠 点 ヒット 時 間 の 増 大 例 題 ) 連 想 度 とミス 1 語 のブロック4つからなるキャッシュを 想 定 し,ブロックアドレス が0,8,0,6,8の 順 にアクセスするとき, 以 下 の 方 式 における キャッスミスの 発 生 数 1 フルアソシアティブ 方 式 2 2ウエイセットアソシアティブ 方 式 3 ダイレクトマッピング 方 式 118
ダイレクトマッピング 方 式 各 ブロックアドレスとキャッシュブロックの 対 応 ブロックアドレス キャッシュブロック 0 0mod 4 = 0 6 6 mod 4 = 4 8 8 mod 4 = 0 各 ブロックアドレスを 参 照 した 後 のキャッシュの 内 容 参 照 したメモリブ ロックのアドレス ヒット/ミス 参 照 後 の 各 キャッシュブロックの 内 容 0 1 2 3 0 ミス メモリ[0] 8 ミス メモリ[8] 0 ミス メモリ[0] 6 ミス メモリ[0] メモリ[6] 8 ミス メモリ[8] メモリ[6] 119
セット アソシアティブ 方 式 各 ブロックアドレスとキャッシュブロックの 対 応 ブロックアドレス キャッシュのセット 0 0mod 2 = 0 6 6 mod 2 = 0 8 8 mod 2 = 0 セット 内 はLRU(least recently used) により 置 換 ブロックを 決 定 各 ブロックアドレスを 参 照 した 後 のキャッシュの 内 容 参 照 したメモリブ ロックのアドレス ヒット/ミス 0 ミス メモリ[0] 8 ミス メモリ[0] メモリ[8] 0 ヒット メモリ[0] メモリ[8] 6 ミス メモリ[0] メモリ[6] 8 ミス メモリ[8] メモリ[6] 参 照 後 の 各 キャッシュブロックの 内 容 セット0 セット0 セット1 セット1 120
フル アソシアティブ 方 式 各 ブロックアドレスとキャッシュブロックの 対 応 各 ブロックアドレスを 参 照 した 後 のキャッシュの 内 容 参 照 したメモリブ ロックのアドレス ヒット/ミス 参 照 後 の 各 キャッシュブロックの 内 容 ブロック0 ブロック1 ブロック2 ブロック3 0 ミス メモリ[0] 8 ミス メモリ[0] メモリ[8] 0 ヒット メモリ[0] メモリ[8] 6 ミス メモリ[0] メモリ[8] メモリ[6] 8 ヒット メモリ[0] メモリ[6] メモリ[6] 121
連 想 度 とミス 率 連 想 度 とミス 率 の 関 係 を 示 す 実 験 結 果 1ブロック16 語 からなる64Kバイトのデータキャッシュを 例 連 想 度 ミス 率 1 10.3% 2 8.6% 4 8.3% 8 8.1% 122
キャッシュ 内 のブロックの 見 つけ 方 セット アソシアティブ 方 式 キャッシュ 中 の 各 ブロックには,そのブロックのアドレスを 示 すアドレスタグを 付 加 タグ インデックス ブロック 内 のオフセット アドレスの3つの 部 分 インデックスはセットの 選 択 に,タグはセット 中 の 全 ブ ロックと 比 較 してブロックを 選 択 するために 使 用 される. ブロック 内 オフセットはブロック 中 の 求 めるデータのアド レス 123
セット 中 の 全 ブロックの 探 索 は 並 列 的 に 実 行 される キャッシュの 全 容 量 を 一 定 に 保 つ 場 合 連 想 度 (1セット 当 たりのブロック 数 )を2 倍 に 増 やすと,セット 数 は 半 分 に 減 少 インデックスは1ビット 減 少 し,タグ 長 が1ビット 増 加 フルアソシアティブ 方 式 :セット 数 は1(インデックスは 不 要 ) すべてのブロックを 並 列 的 に 照 合 が 必 要 性 124
4ウエイセットアソシアティブ 方 式 125
置 き 換 え 対 象 ブロックの 選 択 ダイレクトマッピング 方 式 ブロックの 格 納 場 所 は1つ アソシアティブ 方 式 ブロックの 格 納 場 所 を 選 択 可 能 どのブロックを 置 き 換 えるかを 決 定 する 必 要 がある 一 般 的 な 方 法 LRU 法 使 用 されずにいた 時 間 が 最 も 長 いブロックを 選 択 2ウエイセットアソシアティブ 方 式 の 場 合, 要 素 が 参 照 される たびにどちらが 使 用 されたか 記 録 1ビット 126
タグのサイズと 連 想 度 連 想 度 を 上 げるとそれに 応 じて 比 較 器 が 増 加 するとともに, キャッシュブロック 当 たりのタグのビット 数 が 増 加.4Kブロッ クのキャッシュがあり,そのブロックサイズが4 語 である.ま たそのアドレスは32ビットとする.ダイレクトマッピング 方 式, 2ウエイおよび4ウエイセットアソシアティブ 方 式,フルアソシ アティブ 方 式 のキャッシュについて,セットの 総 数 とタグビッ トの 総 数 を 求 めよ. 127
ブロック 当 たりのバイト 数 は2 4 =16 アドレス 長 が32ビット インデックスとタグに32-4=28ビット 使 用 ダイレクトマッピング 方 式 セット 数 =ブロック 数 4K= 2 12 より,インデックスは12ビット タグの 総 数 は (28-12) 4K=64K 128
2ウエイセットアソシアティブ 方 式 連 想 度 を1つ 上 げると,セット 数 が 半 分 になる インデックスが1ビット 減 り,タグ 中 のビット 数 が1ビット 増 加 セット 数 は2K タグビットの 総 数 (28-11) 2 2K=68K ビット 2ウエイセットアソシアティブ 方 式 セット 数 は1K タグビットの 総 数 (28-10) 4 1K=72K ビット フルアソシアティブ 方 式 セット 数 は1つ,ブロック 数 は4K タグの 総 ビット 数 は28 4K=112Kビット 129
キャッシュとしてのTLB( 変 換 側 付 きバッファ) デマンドページングシステムで 利 用 されているTLB 劇 的 にデマンドページングシステムの 性 能 を 向 上 さ せている 小 規 模 かつ 高 速 なハードウエア 機 構 から 構 成 TLB:キャッシュそのもの 130
マルチレベルキャッシュ DRAMにアクセスに 要 する 時 間 と,CPUのクロック 周 波 数 とのギャップの 解 消 のため CPUと 同 一 のチップ 上 に,2 次 キャッシュを 実 装 131
L1,L2,L3キャッシュの 容 量 プロセッサ L1キャッシュ L2キャッシュ Itanium2 32KB 256KB L3キャッシュ 3MB,4MBor 6MB Itanium 32KB 96KB 2MB or 4MB Xeon MP 8KB 256KB or 512KB 512KB,1MB or 2MB P4 8KB 512KB 132
マルチレベルキャッシュの 性 能 基 本 CPIが1.0のCPU,クロック 周 波 数 は4GHz. 主 記 憶 へのアクセス 時 間 は,キャッシュミスに 関 する 処 理 も 含 め100nS.1 次 キャッシュにおける 命 令 あたりのミス 率 は2%. 2 次 キャッシュを 追 加 したとき,それへのアクセス 時 間 は, 5ns.2 次 キャッシュは, 主 記 憶 へのミス 率 を0.5%に 下 げら れるだけの 容 量 があると 仮 定. CPUの 速 度 の 向 上 はどの 程 度 か 133
主 記 憶 へのミスペナルティは 100ns 0.25ns/クロックサイクル=400クロックサイクル キャッシュが1レベルの 場 合, 実 行 CPIは 実 行 CPI= 基 本 CPI+ 命 令 あたりのメモリストールサイクル 数 =1.0+2% 400=9.0 2 次 キャッシュを 追 加 すると,2 次 キャッシュに 対 するミスペナルティは 5ns 0.25ns/クロックサイクル=20クロックサイクル 2 次 キャッシュにより 主 記 憶 へのミス 率 は0.5%となるので, 実 行 CPI=1.0+2% 20+0.5% 400=3.4 2 次 キャッシュを 参 照 するだけで 済 んだ,ストールサイクル 数 + 主 記 憶 までアクセスし たときのストールサイクル 数 (2 次 キャッシュへのアクセスも 加 算 ) (2%-0.5%) 20=0.3,0.5% (20+400)=2.1 1.0+0.3+2.1=3.4 134
マルチレベルキャッシュ 単 一 レベルキャッシュに 比 べ, 1 次 キャッシュ: ミスペナルティの 低 減 がねらい 容 量 は 小 さく,ブロックサイズも 小 さい 2 次 キャッシュ: ミス 率 の 低 下 が 目 的 容 量 は 大 きく,より 大 きなブロックサイズ 1 次 キャッシュに 比 べ, 連 想 度 も 高 い 135
キャッシュ 技 術 としてのデマンドページング 概 念 的 にキャッシュ 技 術 の 一 つの 形 メインメモリ, キャッシュ 外 部 記 憶 装 置 メインメモリ デマンドページング キャッシュシステム 仮 想 空 間 をメインメモ リより 広 くとることがで きる キャッシュはページ 全 体 の 一 部 を 保 持 136
仮 想 アドレス 使 用 MMUが 仮 想 アドレスを 物 理 アドレスに 変 換 前 にキャシュ が 応 答 可 能 メモリ 応 答 速 度 向 上 MMUがプロセッサチップ 外 にある 場 合,L1キャッシュは 仮 想 アドレスを 使 わねばならない キャッシュが 仮 想 メモリシステムと 相 互 に 作 用 することを 可 能 とするハードウエアの 追 加 が 必 要 137
仮 想 メモリキャッシュ 技 術 とキャッシュフラッシュ キャッシュ 技 術 と 仮 想 メモリの 併 用 時 : キャッシュは,プロセッサとMMUの 間? MMUと 物 理 メモリの 間? キャッシュのデータを 指 定 するとき, 仮 想 アドレスか, 物 理 アドレスか 138
仮 想 メモリシステムが, 通 常 アプリケーションプログラム に 同 一 アドレス 空 間 を 提 供 時 アプリケーションプログラムは0 番 地 から 開 始 OSがアプリケーションをスイッチする 時 アプリケーションは 新 しい 値 を 参 照 するのに 同 じアドレスを 使 用 キャッシュのデータ 取 り 替 え 必 要 複 数 のアプリケーションが 同 一 アドレスを 使 用 時 の,あ いまい 性 の 克 服 方 法 キャッシュフラッシュ 命 令 OSが 新 しい 仮 想 アドレス 空 間 に 変 わるごとにキャッシュをフ ラッシュ あいまい 性 を 排 除 した 認 証 アドレス 空 間 を 認 証 するためのビットを 使 用 ID 仮 想 アドレス キャッシュが 使 用 するアドレス 139
プログラマにとっての 重 要 性 プログラム 中 のループ: 繰 り 返 し 小 さな 命 令 集 合 へのアクセス 同 じデータの 参 照 大 規 模 配 列 の 各 要 素 に, 何 度 も 繰 り 返 し 処 理 するプログラム 次 の 要 素 に 移 行 する 前 に, 配 列 の 一 要 素 にすべての 演 算 を 実 行 する その 要 素 がキャッシュに 残 っているので, 高 速 処 理 が 可 能 140
141
142
命 令 とデータキャッシュ 命 令 : 連 続 性 が 高 く, 高 い 局 所 性 データ:ランダム 性 があり, 局 所 性 は 低 い ランダムな 参 照 を 連 続 したアクセスに 挿 入 すると,キャッ シュの 性 能 を 悪 化 ランダムな 参 照 数 を 低 減 させることで,キャッシュ 性 能 は 向 上 143