「コンピュータアーキテクチャ」ノート (2012 年度, c 石浦 菜岐佐) http://ist.ksc.kwansei.ac.jp/∼ishiura/arc/ 7 キャッシュと仮想記憶 【教科書 pp. 43–70 第 3 章】 の主に項半 ♣ キャッシュの詳細 ♣ 仮想記憶の詳細 ♣ プログラミングやアルゴリズムとの関係 7.1 キャッシュ 【復習】キャッシュ (cache) – CPU と主記憶の間にある, 高速で小容量のメモリー – 主記憶にアクセスのあったデータを保存し, 同じアクセスがあった場合に再利用 → 主記憶へのアクセスを (見かけ上) 高速化する – アクセスしたデータがキャッシュにある → ヒット; ない → ミス (ヒット) 7.1.1 キャッシュの動作の概要 • キャッシュ ブロック (cache block ) (キャッシュライン (cahce line) とも言う) – キャッシュでは, 1 バイト毎ではなく, 何バイトかをまとめた「ブロック」単位でデータを管理する – 一般的なブロックのサイズは 32B ∼ 256B 程度 – ブロック内で「何バイト目」かをオフセット (offset) という (例) 1 ブロック 64B の場合 ブロック 0 0 番地 1 番地 ··· 76 番地 63 番地 64 番地 ··· ブロック 1 76 番地 ··· 127 番地 → ブロック番号= ← オフセット 12 オフセット = 76/64 = 1 76%64 = 12 • キャッシュの動作 (読み出し) 主記憶の a 番地 (ブロック番号 b, オフセットを f ) に読み出しアクセスがあったとき 1) b 番ブロックがキャッシュ内にあれば, そのブロックのオフセット f のデータを CPU に返す 2) なければ, b 番ブロックを 主記憶 からキャッシュにロード ( その際, もしキャッシュの転送先が埋まっていれば, ブロックを ロードしたブロックのオフセット f のデータを CPU に返す 7–1 転送 追い出 ) する して空きを作る • 写像方式 キャッシュに C ブロックを収容できるとする ☆ 主記憶の b 番ブロックをキャッシュ内の C ブロックの中からどうやって高速に探すか どこ に格納するか full associative ; 完全連想方式) 1 → 主記憶の b 番ブロックをキャッシュの (1) フルアソシアティブ方式 ( – b 番ブロックのキャッシュ内での位置は – キャッシュの利用効率は非常に 高い – 自由度が高すぎてブロックの検索が (2) ダイレクトマッピング方式 ( 困難 → ハードウェアが direct mapping – b 番ブロックのキャッシュ内での位置は – ブロックの検索が 任意 (3) セットアソシアティブ方式 ( 悪い (キャッシュ内で 衝突 set associative; セット連想方式) 1 どれか バランス とすればダイレクトマッピング, S = ∗ S は通常 が起き易い) , あるいは連想度 S と言う2 – S を調節して利用効率と検索の容易性の ☆ S= ; 直接写像方式) 一意 – b 番ブロックのキャッシュ内での位置は S 個の S-way になりすぎる 容易 – キャッシュの利用効率が ∗ 複雑 2か4か8 • ブロック置き換えアルゴリズム (block C を取る とすればフルアソシアティブ 程度 replacement algorithm) ☆ キャッシュ内での衝突時に, どのブロックを追い出すか3 (1) ランダム (random) (2) FIFO ( (3) LRU ( 7.1.2 first-in first-out ) … 一番 最初 に入ったブロックを追い出す least recently used ) … 最後のアクセスが最も 昔 のブロックを追い出す キャッシュの動作の詳細 • ブロックサイズが B のとき, a 番地のデータのブロック番号は a/B, オフセットは a%B → ビット列演算 (∵通常 B は 2 のベキ乗) (例) 論理アドレス空間 232 B, キャッシュブロックサイズ 256B (=28 B) の場合 1 ここでは, associative を「連想」と訳すと分かり難くなる. 意訳になるが「自由」の方が理解し易い. associativity. これも「自由度」と意訳すればわかり易い. 3 直接写像方式ではブロックの入る場所が一意なので選択の余地はないが, フルアソシアティブ方式やセットアソシアティブ方式では, どの ブロックを追い出すか選択しなければならない. 2 「連想度」の元英語は 7–2 番地 (32bit) 1000 0000 0001 1001 0101 0100 0010 1000 ブロック番号 ( 24 オフセット bit) 8 ( メモリーの x80195428 番地のデータのブロック番号は, x bit) 801954 , オフセットは x 28 例題 7.1 フルアソシアティブ方式で, 256B のブロックを 256 個収容できるキャッシュを考える. 次の 1) ∼8) の順に主記憶の番地 (32 ビット) にアクセスがあったとき, キャッシュミスは何回発生するか. また, こ の場合のキャッシュヒット率は何%か. 1) x800002F0, 2) x0C004600, 3) x800002EC, 4) x2A000280, 5) x0C004604, 6) x800002E8, 7) x2A000288, 8) xFFFF0300 (解) キャッシュの内容は次のように変化する ∗ 下線はアクセスされるブロックの番号 番地 1) 800002F0 2) 0C004600 √ √ ミス キャッシュに収容されるブロック 800002 800002 0C0046 800002 0C0046 800002 0C0046 2A0002 5) 0C004604 800002 0C0046 2A0002 6) 800002E8 800002 0C0046 2A0002 800002 0C0046 2A0002 800002 0C0046 2A0002 3) 800002EC 4) 2A000280 7) 2A000288 8) FFFF0300 キャッシュミスは √ √ 4 回発生, キャッシュヒット率は FFFF03 4/8 = 50 % • ダイレクトマッピング方式の詳細 – b 番ブロックは, 通常キャッシュの b%C 番の位置に収容→ ビット列演算 (例) 論理アドレス空間 232 B, ブロックサイズ 256B, キャッシュ収容ブロック数 C = 256 (= 28 ) のとき ブロック番号 オフセット (24 bit) (8 bit) 1000 0000 0000 0000 1100 0000 0001 0101 キャッシュ内位置 ( 8 bit) ∗ x80001580 番地のデータ (ブロック x800015) は, キャッシュの ∗ x0C001524 番地のデータ (ブロック x0C0015) も, 7–3 同じ x15 番目の位置に収容 位置に収容 → 衝突 例題 7.2 ダイレクトマッピング方式で, 256B のブロックを 256 個収容できるキャッシュを考える. 次の 1) ∼8) 順に主記憶の番地 (32bit) にアクセスがあったとき, キャッシュミスは何回発生するか. また, この場合 のキャッシュヒット率は何%か. 1) x800002F0, 2) x0C004600, 3) x800002EC, 4) x2A000280, 5) x0C004604, 6) x800002E8, 7) x2A000288, 8) xFFFF0300 (解) キャッシュの内容は次のように変化する ∗ 下線はアクセスされるブロックの番号, 二重下線はキャッシュ内の位置 番地 ミス 1) 800002F0 √ √ 2) 0C004600 3) 800002EC 4) 2A000280 5) 0C004604 6) 800002E8 7) 2A000288 8) FFFF0300 キャッシュミスは キャッシュに収容されるブロック 00 01 03 ··· 46 ··· FF 800002 √ √ √ √ 6 02 800002 0C0046 800002 0C0046 2A0002 0C0046 2A0002 0C0046 800002 0C0046 2A0002 0C0046 2A0002 FFFF03 回発生, キャッシュヒット率は 0C0046 2/8 = 25 % • セットアソシアティブ方式の詳細 – 各ブロックは, キャッシュ内の S 個の位置のいずれかに入れることができる 連続する S 個の位置 (0 ∼ S − 1, S ∼ 2S − 1, 2S ∼ 3S − 1, · · ·) をひとまとめにし4 , その中な らどこに入れてもいいとする. 例題 7.3 2-way のセットアソシアティブ方式で, 256B のブロックを 256 個収容できるキャッシュを考え る. 次の 1)∼8) 順に主記憶の番地にアクセスがあったとき, キャッシュミスは何回発生するか. また, この場 合のキャッシュヒット率は何%か. ただし, ブロック置き換えアルゴリズムには FIFO を用いるものとする. 1) x800002F0, 2) x0C004600, 3) x800002EC, 4) x2A000280, 5) x0C004604, 6) x800002E8, (解) キャッシュの内容は次のように変化する 7) x2A000288, 8) xFFFF0300 ∗ 下線はアクセスされるブロックの番号, 二重下線はキャッシュ内の位置 4 セット (set) と呼ばれる 7–4 番地 ミス 1) 800002F0 √ √ 2) 0C004600 3) 800002EC 00-01 02-03 ··· 46-47 800002 0C0046 800002 0C0046 800002 2A0002 0C0046 5) 0C004604 800002 2A0002 0C0046 6) 800002E8 800002 2A0002 0C0046 800002 2A0002 0C0046 7) 2A000288 √ 8) FFFF0300 キャッシュミスは 4 ··· FE-FF 800002 √ 4) 2A000280 7.2 キャッシュに収容されるブロック 2A0002 FFFF03 回発生し, キャッシュヒット率は 0C0046 4/8 = 50 % 仮想記憶 【複数】仮想記憶 (virtual memory) とは 主記憶と補助記憶装置の組合せにより, 仮想的に巨大な主記憶が利用できるようにする技術 • 用語 virtual address) … 仮想 (的な巨大) 記憶での番地 実アドレス ( real address) … 現実の主記憶での番地 (物理アドレス) ページ (page) … データの入れ換えの単位 (キャッシュの ブロック – 仮想アドレス ( – – 512KB ∼ 4MB のものもある) fault ) … アクセスしたページが 主記憶 にないこと ∗ 一般的なページのサイズは – ページフォルト (page ∗ 割り込み 4KB 程度 (最近では が発生して, OS がページの 入れ換え – ページテーブル (page table) … 仮想アドレスと実アドレスの 図 3.13】 – スラッシング ( に相当) thrashing を行う 対応 を記憶する表【教科書 p. 63 ) ∗ 仮想記憶への過負荷によって, CPU/OS が ページング 状態 • ページ番号の計算方式 → キャッシュのブロック番号と同じ (例) 論理アドレス空間 232 B, ページサイズ 4KB (=212 B) の場合 7–5 に処理能力のほとんどを費やす 番地 (32bit) 1000 0000 0001 1001 0101 • 写像方式には, 通常 0100 0010 0011 ページ番号 オフセット (20bit) (12bit) フルアソシアティブ 方式が用いられる 例題 7.4 主記憶に仮想記憶の 4 ページを収容できるコンピュータ5 において, 017817461742452634 という (仮想) ページ参照系列があったとき, FIFO と LRU でそれぞれページフォルトは何回発生するか? FIFO の場合 LRU の場合 参照 ページ ページ フォルト √ 0 1 7 8 1 √ √ √ 7 4 6 1 7 4 2 4 5 2 6 3 参照 ページ 主記憶の内容 (入った順) ページ フォルト √ (使われていない順) 0 0 0, 1 0, 1, 7 1 7 0, 1, 7, 8 0, 1, 7, 8 8 √ 1, 7, 8, 4 √ √ √ √ √ √ √ √ ページフォルトは 7 7, 8, 4, 6 4 6 8, 4, 6, 1 4, 6, 1, 7 1 7 4, 6, 1, 7 6, 1, 7, 2 4 2 1, 7, 2, 4 4 7, 2, 4, 5 7, 2, 4, 5 5 2 2, 4, 5, 6 4, 5, 6, 3 6 3 4, 5, 6, 3 4 13 0 √ √ 0, 1 0, 1, 7 √ 0, 1, 7, 8 0, 7, 8, 1 1 0, 1, 7, 8 4 7.3 主記憶の内容 回 0, 8, 1, 7 √ √ 8, 1, 7, 4 1, 7, 4, 6 7, 4, 6, 1 4, 6, 1, 7 6, 1, 7, 4 1, 7, 4, 2 √ 1, 7, 2, 4 √ 7, 2, 4, 5 7, 4, 5, 2 √ √ 4, 5, 2, 6 5, 2, 6, 3 √ 2, 6, 3, 4 ページフォルトは 11 回 キャッシュミス/ページフォルト時の処理の比較 キャッシュ 処理を行うのは 割り込みは 処理の間 CPU は ハード ウェア 発生 しない 完了を 待つ 仮想記憶 ソフト ウェア ( OS 発生 する 他 のプログラムを実行 ) ☆ 各装置の速度から理解できる CPU (数百 ps∼数 ns) 5 キャッシュ (1∼10ns) < 主記憶 ( 50∼100ns 簡単のため 4 ページにしているが, 実際のコンピュータではそんなに少なくない. 念のため. 7–6 ) HDD (数 ms) 7.4 プログラミングやアルゴリズムとの関係 • アルゴリズムの理論における計算量解析では, 通常は記憶 → 理論的に高速な計算法が実際には 遅い 階層 まで考慮しない こともあり得る • 遅くなるアルゴリズム/プログラムの例 – 大きなデータ構造を繰り返し → 狭い 走査 範囲で計算を繰り返すように書き直すと, 速くなることがある – 論理アドレス空間の広い範囲を → • リスト 組込み – する計算は概して遅くなる ランダム にアクセスする計算は概して遅くなる 構造が配列より速いとは限らない システムではキャッシュを敬遠することがある memory mapped – 時間的な振る舞いが I/O がキャッシュに妨害される 予測 しにくい (キャッシュの内容によって, 実行時間が 変動 する) • キャッシュを意識してプログラムを高速化する技法 – 後でアクセスするデータがキャッシュから → ダミー 追い出 されるのを防ぐ のアクセスを挿入 – 配列/構造体, 関数の番地を 調整 する ∗ データ/コードがキャッシュブロックの境界 ∗ キャッシュ内収容位置の 衝突 → リンカーに番地を指示, 宣言の またぎ ( 2 ブロック使用) を防ぐ を防ぐ 順序 変更, ダミー 変数の宣言, etc. Nagisa ISHIURA 7–7
© Copyright 2024 ExpyDoc
