投機的ウェイ選択による 高性能セット･アソシアティブ･キャッシュ方式とその性能評価 井上 弘士 発表手順 １． はじめに ２． 従来型キャッシュ ３． ウェイ予測セット・アソシアティブ・キャッシュ •基本概念 •基本原理 •ウェイ予測アルゴリズム •内部構成と基本動作 ４． 評価 ５． おわりに 1 はじめに -背景 トランジスタ技術の進歩 マイクロプロセッサ → 高性能/高機能化 主記憶 (DRAM) → 大容量化 しかしながら･･･ コンピュータ･システム高速化の阻害要因 プロセッサ-主記憶(DRAM)の性能差拡大 メモリアクセス･レイテンシの隠蔽 キャッシュの高性能化が必要！！ 従来型キャッシュ -ダイレクト･マップ方式データ格納のためのキャッシュ内ロケーションが一意に決定 利点：高速アクセスが可能 欠点： キャッシュ･コンフリクトによる低ヒット率 タグ・アレイ ライン・アレイ Ｓｔｅｐ１． アドレス・デコード Ｓｔｅｐ２．タグ読み出し Ｓｔｅｐ２．ライン読み出し Ｓｔｅｐ３． タグ比較 Ｓｔｅｐ３．参照データ選択 Ｓｔｅｐ４． ヒット/ミス ドライブ Ｓｔｅｐ４．参照データ ドライブ 2 従来型キャッシュ -セット･アソシアティブ方式データ格納のためのキャッシュ内ロケーションが複数存在 利点：キャッシュ･コンフリクト回避による高ヒット率 欠点：ウェイ選択に伴う低速アクセス Ｓｔｅｐ１． アドレス・デコード ウェイ０ ウェイ１ Ｓｔｅｐ２．タグ読み出し Ｓｔｅｐ２．ライン読み出し Ｓｔｅｐ３． タグ比較 Ｓｔｅｐ４．参照データ選択 Ｓｔｅｐ４． ヒット/ミス ドライブ Ｓｔｅｐ５．参照データ ドライブ 問題点 -キャッシュ性能 実行時間 ＝ CPU実行時間 ＋ メモリ･アクセス時間 平均メモリア･クセス時間＝キャッシュ･アクセス時間 ＋ ミス率 × ミス･ペナルティ メモリアクセス時間の削減 高速アクセス、かつ、高ヒット率を達成する必要あり！ アクセス時間 ヒット率 ダイレクト･マップ方式 〇 セット･アソシアティブ方式 × × 〇 いづれかの要求を犠牲に! 3 解決策 - 提案キャッシュ セット･アソシアティブ方式の高ヒット率を維持したまま、 ダイレクト･マップ方式の高速アクセスを可能に！ ウェイ予測型キャッシュを提案 平均メモリ･アクセス時間 100% 従来型 ダイレクト 113% 90% 従来型 セット ウェイ 予測型 ウェイ予測型キャッシュ - 基本原理 タグ比較とは独立に ウェイを選択 Ｓｔｅｐ０．ウェイ予測 Ｓｔｅｐ１． 参照アドレスのデコード Ｓｔｅｐ２．予測されたウェイに対応する タグとラインの同時読み出し フェーズ1 Ｓｔｅｐ３． タグ比較 不一致 一致（予測ヒット） Ｓｔｅｐ４．終了 Ｓｔｅｐ４．残りウェイのタグと ラインの同時読み出し Ｓｔｅｐ５． タグ比較 フェーズ2 一致（予測ミス） Ｓｔｅｐ６．終了 不一致（キャッシュ・ミス） Ｓｔｅｐ６．終了後、リプレイス 4 ウェイ予測型キャッシュ - アクセス時間 - ダイレクト マップ方式 セット･アソシ アティブ方式 ウェイ予測型キャッシュのアクセス時間 予測ヒット時：MuxSidePathが存在しない → ダイレクト･マップ方式 予測ミスまたはキャッシュ･ミス時： → ダイレクト･マップ方式 ＋ セット･アソシアティブ方式 ウェイ予測型キャッシュ - ウェイ予測アルゴリズム ウェイ予測型キャッシュの有効性は予測ヒット率に依存 多くのプログラムには高いメモリ参照局所性 ウェイ予測に MRU(Most Recently Used)アルゴリズムを採用 参照 予測ウェイ セット S セット S ウェイ２ ウェイ２ T T+n 時間 各セットにおいて、前回のアクセスが •予測ヒットもしくは予測ミス → 参照データが存在したウェイ •キャッシュ・ミス → リプレイス対象となったウェイ を次回の予測ウェイとする 5 ウェイ予測型キャッシュ - 内部構成 - 評価 - 概要 評価対象 従来型ダイレクト 従来型4ウェイ ウェイ予測型4ウェイ •キャッシュ・サイズ → 16KB D-Cache •ライン・サイズ → 32B 評価項目 平均メモリアクセス時間（MAT） MAT＝キャッシュ･アクセス時間 ＋ ミス率 × ミス･ペナルティ 評価方法 CACTI*を用いたキャッシュ･アクセス時間の測定 シミュレータを用いた予測ヒット率の測定 *Wilton, et. Al., “CACTI:An Enhanced Cache Access and Cycle Time Model,” IEEE Journal of Solid-State Circuits. 6 評価 - 実験環境 - SPECint95 Benchmarks 099.go, 124.m88ksim, 126.gcc, 129.compress, 130.li, 132.ijpeg, 134.perl, 147.vortex SPECfp95 101.tomcatv, 102.swim, 103.su2cor, 104.hydro2d 評価 -キャッシュ･アクセス時間 従来型ダイレクト LineSidePath = 3.852 ns 従来型4ウェイ MuxSidePath = 5.958 ns ウェイ予測型4ウェイ 予測ヒット時：128バイトライン従来型ダイレクトの アクセス時間 = LineSizePath = 3.476 ns 予測ミス時：（128バイトライン従来型ダイレクトでのタグ比較まで ＋ 従来型4ウェイのデコード以降）の遅延時間 3.476 * 予測ヒット率 + 8.030 * (1 − 予測ヒット率) ＝ 8.030 ns 7 評価 - 予測ヒット率 従来型ダイレクト 平均キャッシュ･ミス率 → 5.84 % 従来型4ウェイ 平均キャッシュ･ミス率 → 4.25 % ウェイ予測型4ウェイ 半分のベンチマーク → 9.41% 90%程度の予測ヒット率を達成 4.25% 86.3% 予測ヒット率 予測ミス率 キャッシュ・ミス率 Average of all benchmarks 評価 - 平均メモリ･アクセス時間 Normalized Results (%) Average Memory Access Time 140 66.2% 100 63.2% 従来型 4ウェイ 60 0 従来型 ダイレクト 099.go 101.tomcatv ウェイ予測型 4ウェイ DRAM access time = 40 ns Bandwidth = 1GB/S Average of All Benchmarks 従来型D 従来型４way ウェイ予測型4way 100.0% 112.8% 89.2% 8 MDLへの適用 - ウェイ予測型キャッシュの有効性 DRAM/Logic混載LSIの高オンチップ･メモリバンド巾 ミス･ペナルティを増加する事なく、ラインサイズを拡大可能 コンフリクト･ミスの増加に伴う性能低下 セット･アソシアティブ方式を採用し、ラインサイズ拡大による プリフェッチ効果を最大限活用！ ウェイ予測型キャッシュの採用が有効では？ ラインサイズ拡大によるウェイ予測型キャッシュ性能の評価 MDLへの適用 - ラインサイズ拡大による影響 30% 46% 出力ﾊﾞｽ負荷容量の増大 出力ドライブ タグ比較遅 延時間 ＜ 遅延時間 連想度 トレードオフを考慮 ラインサイズ 予測ヒット時のアクセス時間 （出力ドライバ遅延） 9 おわりに - 本発表のまとめ ウェイ予測セット・アソシアティブ・キャッシュの提案 セット･アソシアティブ方式の高ヒット率を維持しつつ、 ダイレクト･マップ方式の高速アクセスを実現 定量的評価（１2種類のベンチマークを使用） 従来型4ウェイと比較して、 平均メモリアクセス時間を20%削減 DRAM/Logic混載LSIへの適用可能性を検討 「ラインサイズ」、「連想度」、「予測ヒット時アクセス時間」の トレードオフを考慮する事で大幅な性能向上を達成可能 おわりに - 今後の課題 従来型キャッシュ アクセス毎に全てのウェイを活性化 ウェイ予測型キャッシュ 予測ヒット時には、唯一のウェイだけを活性化 「高性能/低消費エネルギー化を実現する ウェイ予測セット･アソシアティブ･キャッシュ方式の提案と評価」 デザインガイア‘９８ in 福岡 ウェイ予測型キャッシュによる 高性能/低消費エネルギー効果 の総合評価 10 質問用OHP 評価 -定量的評価 （消費エネルギー･オーバヘッド） ウェイ予測回路の動作 単純な組み合わせ回路で実現でき、消費エネルギーは極めて小さい ウェイ予測テーブルへのアクセス •デコード → アドレス・デコーダによるオーバヘッドは無視できるほど小さい •書込み → 予測ヒットの場合は書込みが発生しない •読み出し → アクセス毎にウェイ予測フラグの読み出しが発生 ウェイ予測テーブルから読み出される信号線の遷移確立を測定 I-Cacheで平均0.4ビット D-Cacheで平均0.8ビット 消費エネルギー・オーバヘッドは無視できるほど小さい 11 評価 -定量的評価 （性能オーバヘッド） ウェイ予測フラグを読み出すための遅延時間 参照アドレス生成 + ウェイ予測フラグ読み出し 命令キャッシュ → 通常、PCは専用インクリメンタを搭載しており、 参照アドレスが高速に計算される。 データキャッシュ → ALUによる参照アドレス計算と ウェイ予測フラグ読み出しの逐次処理 性能オーバヘッドは回避可能 従来型 段階型 ウェイ予測型 Average of all benchmarks （Etag = 0.07Elineと換算） 149.4% 160 I-Cache 62.5% 100 28.1% 0 Normalized Results (%) Normalized Results (%) 評価 - 定量的評価 （性能と消費エネルギー） 146.0% 160 D-Cache 100 72.0% 35.2% 0 Ecache Delay Ecache Delay Ecache * Delay (I-Cache/D-Cache平均) 従来型 100.0% 段階型 ウェイ予測型 43.4% 22.2% 12 評価 - アクセス時間 ウェイ予測型4ウェイ アクセス時間 3.476 * 予測ヒット率 + 8.030 * (1 − 予測ヒット率) 最善ケース→従来型ダイレクトより10 %高速 最悪ケース→従来型ダイレクトの2倍のアクセス時間 評価 - 平均メモリ･アクセス時間 Normalized Results (%) Average Memory Access Time 135.9% 140 100 66.2% 63.2% 60 0 099.go 101.tomcatv 102.swim 従来型 ダイレクト 従来型 4ウェイ ウェイ予測型 4ウェイ DRAM access time = 40 ns Bandwidth = 1GB/S Average of All Benchmarks 従来型D 従来型４way ウェイ予測型4way 100.0% 112.8% 89.2% 13
© Copyright 2024 ExpyDoc
