Microsoft PowerPoint - ARC-SWoPP2011OkaSlides.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - ARC-SWoPP2011OkaSlides.pptx"

てるえつちかね
5 years ago
Views:

1 データ値の局所性を利用したライン共有キャッシュの提案九州大学大学院岡慶太郎福本尚人井上弘士村上和彰 1

8MB の L3 キャッシュを搭載 Core i7 のチップ写真 * * http://www.

2 キャッシュメモリの大容量化マルチコアプロセッサが主流メモリウォール問題の深刻化メモリアクセス要求増加 IOピンの制限大容量の LL(Last Level) キャッシュを搭載 8MB の L3 キャッシュを搭載 Core i7 のチップ写真 * * 2

3 キャッシュメモリの大容量化の問題点リーク消費電力増加容量 1MB 8MB で 8 倍 * アクセスレイテンシ増加容量 1MB 8MB で 2.1 倍 * 大幅な面積増加を伴わず, オフチップメモリアクセス回数を削減する手法が必要 * CACTI によりブロックサイズ 64B, 連想度 8 で実験した結果 3

4 目次研究背景着目点 : データ値の局所性ライン共有キャッシュ評価ミス率, 面積,L1ミスペナルティまとめ今後の課題 4

5 従来型キャッシュメモリは容量を無駄遣い!? 従来型キャッシュメモリのキャッシング方法参照アドレスに基づいてブロックの格納場所を決定データ値の局所性が高い仮説データ値の局所性 : メモリアドレスが異なる多数のデータが同一の値を有する性質キャッシュ内に同一データ値を有するブロックが多数存在 LL キャッシュメモリ参照アドレスブロックの格納場所インデックスタグラインタグインデックスブロック : A 書込みブロック 010 キャッシュのレベル間で 011 取り交わすデータ A データ値 : 110 ブロックのデータの値 111 B 5

6 従来型キャッシュメモリは容量を無駄遣い!? 従来型キャッシュメモリのキャッシング方法参照アドレスに基づいてブロックの格納場所を決定データ値の局所性が高い仮説データ値の局所性 : メモリアドレスが異なる多数のデータが同一の値を有する性質キャッシュ内に同一データ値を有するブロックが多数存在 LL キャッシュメモリ参照アドレスブロックの格納場所インデックスタグラインタグインデックスブロック : A 書込みブロック 010 キャッシュのレベル間で 011 取り交わすデータ A A データ値 : 110 ブロックのデータの値 111 B 6

7 従来型キャッシュメモリにおけるデータ値の局所性分析キャッシュメモリ内のデータ値の局所性を平均圧縮率を用いて分析 n: ブロック置き換え回数平均圧縮率が低い程, キャッシュメモリ内のデータ値の局所性が高いキャッシュ容量 :1MB 平均圧圧縮率ブロックサイズ 64B 32B 16B 8B キャッシュメモリ A B A C B 多くのプログラムでキャッシュメモリ内のデータ値の局所性が高い 7

8 研究概要着目点キャッシュメモリ内に同一値を有するデータが多く存在研究目的 LL キャッシュメモリの面積を大きく増加することなく LLキャッシュミス率を削減提案手法同一データ値を有するラインを共有し, 容量を効率的に利用同容量の従来型キャッシュと比較し最大でミス率を同容量の従来型キャッシュと比較し, 最大でミス率を 18 ポイント削減可能 8

9 目次研究背景着目点 : データ値の局所性ライン共有キャッシュ評価ミス率, 面積,L1ミスペナルティまとめ今後の課題 9

10 ライン共有キャッシュの概念 LSC(Line Sharing Cache) 従来型キャッシュ参照アドレスに基づきブロックを格納するラインを決定ライン共有キャッシュ同一データ値を有するブロックを格納するラインを 1 箇所に限定タグアレイデータアレイタグアレイデータアレイ A A A A タグのエントリ数増加従来型キャッシュに比べ, より多くのデータ値をキャッシュメモリに格納可能 10

11 解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり問題点 : 各タグに対応するラインを特定不可能解決策 : 行番号によるラインの区別と各タグに行ポインタ配置タグアレイタグデータアレイライン ?? 各タグは対応するラインを特定できない 11

12 解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり問題点 : 各タグに対応するラインを特定不可能解決策 : 行番号によるラインの区別と各タグに行ポインタ配置タグアレイタグ ?? 行番号データアレイライン各タグは対応するラインを特定できない 12

13 解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり問題点 : 各タグに対応するラインを特定不可能解決策 : 行番号によるラインの区別と各タグに行ポインタ配置タグポインタアレイタグアレイタグ行ポインタ行番号データアレイライン

14 解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ問題点 : 検索コストが大解決策 : データ値を用いたハッシングインデックス参照アドレスタグインデックス書込みブロックタグポインタアレイタグ行ポインタ行番号データアレイみ = タ101 一致書き込ラインデー値の検索

15 解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ問題点 : 検索コストが大解決策 : データ値を用いたハッシングタグポインタアレイデータアレイ行番号書インデックスタグ行ポインタき参照アドレス込ラインみタグインデックスデー100 タ11111 値書込みブロック行番号ののサイズ検索行番号とデータ値の下位 3ビット 1111 を対応付けてブロックを配置 15

16 解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ問題点 : 検索コストが大解決策 : データ値を用いたハッシングタグポインタアレイデータアレイ行番号インデックスタグ行ポインタ参照アドレスみタグインデックス = 100 値書込みブロック 1001 一致行番号のサイズ書込みデータ値の下位 3ビット書込みデータ値がラインに存在 1111 に対応する行番号にアクセス ( データ値ヒット ) 書き込ラインデータの検11111 索16

17 解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ問題点 : 検索コストが大解決策 : データ値を用いたハッシングタグポインタアレイデータアレイインデックスタグ行ポインタライン参照アドレス行番号を行ポインタに 001 タグインデックス書込み書込みブロック行番号のサイズ書込みデータ値の下位 3ビット書込みデータ値がラインに存在 1111 に対応する行番号にアクセス ( データ値ヒット ) 17

18 解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入タグポインタアレイデータアレイインデックスタグ行ポインタ行番号ライン参照アドレス tag index = 100 書込みブロック一致

19 解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入タグポインタアレイインデックスタグ行ポインタ行番号参照アドレス tag index 書込みブロック行番号のサイズ書込みデータ値の下位 3ビット 1111 に対応する行番号にアクセスデータアレイラインブロックの追出しが必要書込みデータ値がラインに非存在 ( データ値ミス ) 19

20 解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入タグポインタアレイデータアレイインデックスタグ行ポインタ行番号ライン参照アドレス tag index 書込みブロック

21 解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入インデックス参照アドレス tag index タグポインタアレイタグ行ポインタ 0100 行番号ラインデータアレイライン書込みブロック各行番号に複数のラインを対応付け 21

22 解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入インデックス参照アドレス tag index タグポインタアレイタグ行ポインタ 0100 行番号ラインデータアレイライン書込みブロック列番号 0 列番号行番号, 列番号により 1110 ラインを区別

23 解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入インデックスタグ参照アドレス tag index タグポインタアレイ行ポインタ列ポインタ行番号ラインデータアレイライン書込みブロック列番号 0 列番号列番号を格納するために列ポインタの導入

24 解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け問題点 : ブロックの追出しが頻発解決策 : データアレイの水平分割と列ポインタの導入インデックス参照アドレス tag index タグポインタアレイタグ 0100 行ポインタ列ポインタ行番号ラインデータアレイライン書込みブロック一致データ値ミス列番号 0 列番号行番号のサイズ 1100 ブロックを追い出すことなく 1101 書込み 1110 書込みデータ値の下位 2ビットに対応する行番号にアクセス = 00111

25 読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し読み出し動作タグポインタアレイインデックスタグ行ポインタ参照アドレス tag index 列ポインタ行番号ラインデータアレイライン列番号 0 列番号 1 25

26 読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し読み出し動作タグポインタアレイインデックスタグ行ポインタ参照アドレス tag index 列ポインタ行番号ライン = 一致データアレイライン列番号 0 列番号 1 26

27 読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し読み出し動作同時に動作可能タグポインタアレイインデックスタグ行ポインタ参照アドレス tag index 列ポインタ行番号ラインデータアレイライン列番号 0 列番号 1 27

28 読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し読み出し動作同時に動作可能タグポインタアレイインデックスタグ行ポインタ参照アドレス tag index 列ポインタ行番号ラインデータアレイライン列番号 0 列番号

29 従来型キャッシュ VS ライン共有キャッシュ LSC の従来型キャッシュに対する違い理由ミス率減少データアレイ容量を有効利用読出しレイテンシ変化なしタグとポインタを同時に読み出し書込み書込みデータ値の探索増加レイテンシ追出しの動作が複雑化データアレイに対する書込み回数減少データ値ヒットの場合データアレイに対する書込みを行わない 29

30 目次研究背景データ値の局所性ライン共有キャッシュ評価ミス率, 面積,L1ミスペナルティまとめ今後の課題 30

31 面積評価指標と求め方実装に必要な SRAM ビット数で評価 L1 ミスペナルティモデルにより評価 L2 アクセスレインテンシキャッシュメモリシミュレータ CACTI キャッシュミス率従来型キャッシュのミス率と平均圧縮率からの見積もりにより評価 LSC のミス率の評価方法従来型キャッシュのミス率マルチコアシミュレータ M5 ベンチマークプログラム splash2 M5によるシミュレーション L2 アクセストレース従来型キャッシュの L2 ミス率ミスス率容量平均圧圧縮率平均圧縮率容量 LSCのミス率に換算 31

32 評価方法面積 : ミス率を従来型キャッシュ 8MB における値に固定ミス率 : データアレイ容量を1MBに固定 L1ミスペナルティ : データアレイ容量を1MBに固定従来型キャッシュ L2 キャッシュュミス率 LSC の容量 LSC 従来型キャッシュ L2 キャッシュサイズ 8MB L2 キャッシシュミス率従来型キャッシュのミス率 LSC のミス率必要ビット数面積の比較ミス率および L1ミスペナルティの比較 LSC データメモリ :1MB M5の評価環境コア数 8 L1キャッシュサイズ :32KB, 連想度 :2, ブロックサイズ :64B L2キャッシュ連想度 :8ブロックサイズ:64B 32

33 キャッシュミス率一定とした場合の面積削減効果ブロックサイズ 64B, 従来型キャッシュ容量 8MB 圧縮率必要メモモリ容量 [MB] データアレイ容量ポインタアレイ容量タグ容量 52% 面積削減 base LSC base LSC base LSC base LSC base LSC base LSC Cholesky Barnes FFT FMM LUCon OceanCon ベンチマークプログラム圧縮率が低い程, 面積を大幅に削減 33

34 キャッシシュミス率データアレイ容量を一定とした場合のミス率削減効果ブロックサイズ64B, データアレイ容量 1MB base LSC 圧縮率 0.21 L2 キャッシシュミス率ミス率を大幅に削減できないポイント削減 L2キャッシュ容量 [MB] 容量を増加した場合容量を増加するとミス率がすぐに飽和, ミス率の減少幅小ベンチマークプログラムすべてのプログラムでミス率を削減 34

35 L2 キャッシシュミス率キャッシシュミス率データアレイ容量を一定とした場合のミス率削減効果ブロックサイズ64B, データアレイ容量 1MB base LSC 0.8 圧縮率ミス率を 18 ポイント削減 L2キャッシュ容量 [MB] 容量を増加する場合, ミス率の減少幅大ベンチマークプログラムすべてのプログラムでミス率を削減 35

36 ィ比 L1 ミスペペナルテデータアレイ容量一定とした場合の L1 ミスペナルティ削減効果ブロックサイズ64B, データアレイ容量 1MB 従来型キャッシュの L1 ミスペナルティで正規化 L1ミスペナルティ 30% 削減ベンチマークプログラムアクセス時間を考慮した場合でも L1ミスペナルティを大幅に削減 36

37 まとめデータ値の局所性を利用したライン共有キャッシュを提案ミス率一定条件において面積 : 最大 52% 削減容量一定条件においてミス率 : 最大 18ポイント削減 L1ミスペナルティ : 最大 30% 削減ライン共有キャッシュの有効性を確認 37

38 今後の課題ライン共有キャッシュの詳細な評価キャッシュミス率アクセスレイテンシアクセスあたりの消費電力ライン共有キャッシュの適用範囲を拡張 LSC はデータアレイへの書込み回数を削減不揮発性メモリに利用既存研究との比較 38

39 ご清聴ありがとうございました 39

Microsoft PowerPoint - ARC2009HashiguchiSlides.pptx

Microsoft PowerPoint - ARC2009HashiguchiSlides.pptx 3 次元 DRAM プロセッサ積層実装を対象としたオンチップメモリアーキテクチャの提案と評価橋口慎哉小野貴継 ( 現 ) 井上弘士村上和彰九州大学大学院システム情報科学府九州大学大学院システム情報科学研究院発表手順研究背景研究目的ハイブリッドキャッシュアーキテクチャ評価実験まとめと今後の課題 2 3 次元実装技術研究背景グローバル配線長の削減チップ面積縮小異なるプロセスを経て製造されたダイ同士の積層