データ値の局所性を利用した ライン共有キャッシュの提案 九州大学大学院 岡慶太郎 福本尚人 井上弘士 村上和彰 1
キャッシュメモリの大容量化 マルチコア プロセッサが主流 メモリウォール問題の深刻化 メモリアクセス要求増加 IOピンの制限 大容量の LL(Last Level) キャッシュを搭載 8MB の L3 キャッシュを搭載 Core i7 のチップ写真 * * http://www.atmarkit.co.jp/fsys/zunouhoudan/102zunou/corei7.html 2
キャッシュメモリの大容量化の問題点 リーク消費電力増加 容量 1MB 8MB で 8 倍 * アクセスレイテンシ増加 容量 1MB 8MB で 2.1 倍 * 大幅な面積増加を伴わず, オフチップメモリアクセス回数を削減する手法が必要 * CACTI によりブロックサイズ 64B, 連想度 8 で実験した結果 3
目次 研究背景 着目点 : データ値の局所性 ライン共有キャッシュ 評価 ミス率, 面積,L1ミスペナルティ まとめ 今後の課題 4
従来型キャッシュメモリは 容量を無駄遣い!? 従来型キャッシュメモリのキャッシング方法 参照アドレスに基づいてブロックの格納場所を決定 データ値の局所性が高い 仮説 データ値の局所性 : メモリアドレスが異なる多数のデータが同一の値を有する性質 キャッシュ内に同一データ値を有するブロックが多数存在 LL キャッシュメモリ参照アドレスブロックの格納場所インデックスタグラインタグインデックス 000 0100 001 ブロック : 001 0100 A 書込みブロック 010 キャッシュのレベル間で 011 取り交わすデータ A 100 101 データ値 : 110 ブロックのデータの値 111 B 5
従来型キャッシュメモリは 容量を無駄遣い!? 従来型キャッシュメモリのキャッシング方法 参照アドレスに基づいてブロックの格納場所を決定 データ値の局所性が高い 仮説 データ値の局所性 : メモリアドレスが異なる多数のデータが同一の値を有する性質 キャッシュ内に同一データ値を有するブロックが多数存在 LL キャッシュメモリ参照アドレスブロックの格納場所インデックスタグラインタグインデックス 000 0000 101 ブロック : 001 0100 A 書込みブロック 010 キャッシュのレベル間で 011 取り交わすデータ A 100 101 0000 A データ値 : 110 ブロックのデータの値 111 B 6
従来型キャッシュメモリにおけるデータ値の局所性分析 キャッシュメモリ内のデータ値の局所性を平均圧縮率を用いて分析 n: ブロック置き換え回数 平均圧縮率が低い程, キャッシュメモリ内のデータ値の局所性が高い キャッシュ容量 :1MB 0.8 0.6 0.4 0.2 0 平均圧圧縮率 ブロックサイズ 64B 32B 16B 8B キャッシュメモリ A B A C B 多くのプログラムでキャッシュメモリ内のデータ値の局所性が高い 7
研究概要 着目点 キャッシュメモリ内に同一値を有するデータが多く存在 研究目的 LL キャッシュメモリの面積を大きく増加することなく LLキャッシュミス率を削減 提案手法 同一データ値を有するラインを共有し, 容量を効率的に利用 同容量の従来型キャッシュと比較し最大でミス率を 同容量の従来型キャッシュと比較し, 最大でミス率を 18 ポイント削減可能 8
目次 研究背景 着目点 : データ値の局所性 ライン共有キャッシュ 評価 ミス率, 面積,L1ミスペナルティ まとめ 今後の課題 9
ライン共有キャッシュの概念 LSC(Line Sharing Cache) 従来型キャッシュ 参照アドレスに基づきブロックを格納するラインを決定 ライン共有キャッシュ 同一データ値を有するブロックを格納するラインを 1 箇所に限定 タグアレイデータアレイタグアレイデータアレイ A A A A タグのエントリ数増加 従来型キャッシュに比べ, より多くのデータ値をキャッシュメモリに格納可能 10
解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり 問題点 : 各タグに対応するラインを特定不可能 解決策 : 行番号によるラインの区別と各タグに行ポインタ配置 タグアレイ タグ データアレイ ライン 0100 0110?? 11111 各タグは対応するラインを特定できない 11
解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり 問題点 : 各タグに対応するラインを特定不可能 解決策 : 行番号によるラインの区別と各タグに行ポインタ配置 タグアレイ タグ 0100 0110?? 行番号 000 001 010 011 100 101 110 111 データアレイ ライン 11111 各タグは対応するラインを特定できない 12
解決すべき課題その 1 ~ 如何にしてタグとラインを紐付けるか?~ タグに対応するラインを特定する必要あり 問題点 : 各タグに対応するラインを特定不可能 解決策 : 行番号によるラインの区別と各タグに行ポインタ配置 タグ ポインタアレイタグアレイ タグ 0100 0110 行ポインタ 100 100 行番号 000 001 010 011 100 101 110 111 データアレイ ライン 11111 13
解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ 問題点 : 検索コストが大 解決策 : データ値を用いたハッシング インデックス参照アドレス 0000 0001 タグインデックス 0010 0100 0001 0011 書込みブロック 11111 1001 1011 1100 1101 1110 タグ ポインタアレイタグ行ポインタ 0100 0110 111 行番号 データアレイ 000 001 み010 011 = 100 11111 タ101 一致 110 111 書き込ライン デー値の検索1111 14
解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ 問題点 : 検索コストが大 解決策 : データ値を用いたハッシング タグ ポインタアレイデータアレイ行番号書インデックスタグ行ポインタき参照アドレス 0000 000 込ライン 0001 0100 001 みタグインデックス 0010 010 デ0100 0001 0011 011 ー100 タ11111 値書込みブロック 1001 0110 111 101 行番号の11111 1011 110 のサイズ検1100 111 11111 索1101 1110 行番号とデータ値の下位 3ビット 1111 を対応付けてブロックを配置 15
解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ 問題点 : 検索コストが大 解決策 : データ値を用いたハッシング タグ ポインタアレイデータアレイ行番号インデックスタグ行ポインタ参照アドレス 0000 000 0001 0100 001 みタグインデックス 0010 010 0100 0001 0011 011 = 100 値書込みブロック 1001 一致 101 11111 1011 行番号のサイズ 110 1100 111 11111 1101 1110 書込みデータ値の下位 3ビット書込みデータ値がラインに存在 1111 に対応する行番号にアクセス ( データ値ヒット ) 書き込ライン データ0110 111 の検11111 索16
解決すべき課題その 2 ~ 如何にして効率の良いデータ検索を実現するか?~ 書込み動作 : データアレイの全ラインを探索する必要ありイ 問題点 : 検索コストが大 解決策 : データ値を用いたハッシング タグ ポインタアレイ データアレイ インデックスタグ行ポインタライン参照アドレス 0000 000 0001 0100 111 行番号を行ポインタに 001 タグインデックス 0010 010書込み 0100 0001 0011 011 100 書込みブロック 1001 0110 111 101 11111 1011 行番号のサイズ 110 1100 111 11111 1101 1110 書込みデータ値の下位 3ビット書込みデータ値がラインに存在 1111 に対応する行番号にアクセス ( データ値ヒット ) 17
解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 タグ ポインタアレイデータアレイインデックスタグ行ポインタ行番号ライン参照アドレス 0000 000 0001 0100 001 tag index 0010 010 0100 0001 0011 011 = 100 書込みブロック 1001 0110 111 一致 101 1011 110 00111 1100 111 11111 1101 1110 1111 18
解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 タグ ポインタアレイ インデックスタグ行ポインタ行番号参照アドレス 0000 000 0001 0100 001 tag index 0010 010 0100 0001 0011 011 100 書込みブロック 1001 0110 111 101 00111 1011 行番号のサイズ 110 1100 111 1101 1110 書込みデータ値の下位 3ビット 1111 に対応する行番号にアクセス データアレイ ライン ブロックの追出しが必要 11111 書込みデータ値がラインに非存在 ( データ値ミス ) 19
解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 タグ ポインタアレイデータアレイインデックスタグ行ポインタ行番号ライン参照アドレス 0000 000 0001 0100 001 tag index 0010 010 0100 0001 0011 011 100 書込みブロック 1001 0110 111 101 110 00111 1011 1100 111 11111 1101 1110 1111 20
解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 インデックス参照アドレス 0000 0001 tag index 0010 0100 0001 0011 タグ ポインタアレイタグ行ポインタ 0100 行番号ライン 00 01 10 11 11111 データアレイ ライン 書込みブロック 00111 1001 1011 1100 1101 1110 1111 0110 111 各行番号に複数のラインを対応付け 21
解決すべき課題その3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 インデックス参照アドレス 0000 0001 tag index 0010 0100 0001 0011 タグ ポインタアレイタグ行ポインタ 0100 行番号ライン 00 01 10 11 11111 データアレイ ライン 書込みブロック 00111 1001 0110 111 列番号 0 列番号 1 1011 1100 1101 行番号, 列番号により 1110 ラインを区別 1111 22
解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 インデックス タグ 参照アドレス 0000 0001 tag index 0010 0100 0001 0011 0100 タグ ポインタアレイ 行ポインタ 列ポインタ 行番号ライン 00 01 10 11 11111 データアレイ ライン 書込みブロック 00111 1001 0110 11 1 列番号 0 列番号 1 1011 1100 列番号を格納するために列ポインタの導入 1110 1111 23
解決すべき課題その 3 ~ 如何にしてデータアレイでの書込み競合を回避するか?~ データアレイ : 各行番号に 1ラインを対応付け 問題点 : ブロックの追出しが頻発 解決策 : データアレイの水平分割と列ポインタの導入 インデックス参照アドレス 0000 0001 tag index 0010 0100 0001 0011 タグ ポインタアレイ タグ 0100 行ポインタ 列ポインタ 行番号ライン 00 01 10 11 11111 データアレイ ライン 書込みブロック 1001 0110 11 1 一致データ値ミス列番号 0 列番号 1 00111 1011 行番号のサイズ 1100 ブロックを追い出すことなく 1101 書込み 1110 書込みデータ値の下位 2ビット 1111 24 に対応する行番号にアクセス = 00111
読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し 読み出し動作 タグ ポインタアレイ インデックスタグ行ポインタ参照アドレス 0000 0001 0100 01 0 tag index 0010 0100 0001 0011 列ポインタ 行番号ライン 00 01 11101 10 11 データアレイ ライン 1001 0110 11 1 1011 1100 1101 1110 1111 列番号 0 列番号 1 25
読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し 読み出し動作 タグ ポインタアレイ インデックスタグ行ポインタ参照アドレス 0000 0001 0100 01 0 tag index 0010 0100 0001 0011 1001 0110 11 1 1011 1100 1101 1110 1111 列ポインタ 行番号ライン 00 01 11101 10 11 = 一致 データアレイ ライン 列番号 0 列番号 1 26
読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し 読み出し動作 同時に動作可能 タグ ポインタアレイ インデックスタグ行ポインタ参照アドレス 0000 0001 0100 01 0 tag index 0010 0100 0001 0011 列ポインタ 行番号ライン 00 01 11101 10 11 データアレイ ライン 1001 0110 11 1 1011 1100 1101 1110 1111 01 0 列番号 0 列番号 1 27
読出し要求発行後の動作 1. インデックスアクセス 2. タグ比較 3. ポインタ読出し 4. ブロック読出し 読み出し動作 同時に動作可能 タグ ポインタアレイ インデックスタグ行ポインタ参照アドレス 0000 0001 0100 01 0 tag index 0010 0100 0001 0011 列ポインタ 行番号ライン 00 01 11101 10 11 データアレイ ライン 1001 0110 11 1 1011 1100 1101 1110 1111 01 0 列番号 0 列番号 1 11101 28
従来型キャッシュ VS ライン共有キャッシュ LSC の従来型キャッシュに対する違い 理由 ミス率 減少 データアレイ容量を有効利用 読出しレイテンシ 変化なし タグとポインタを同時に読み出し 書込み 書込みデータ値の探索増加レイテンシ 追出しの動作が複雑化 データアレイに対する書込み回数 減少 データ値ヒットの場合データアレイに対する書込みを行わない 29
目次 研究背景 データ値の局所性 ライン共有キャッシュ 評価 ミス率, 面積,L1ミスペナルティ まとめ 今後の課題 30
面積 評価指標と求め方 実装に必要な SRAM ビット数で評価 L1 ミスペナルティ モデルにより評価 L2 アクセスレインテンシ キャッシュメモリシミュレータ CACTI キャッシュミス率 従来型キャッシュのミス率と平均圧縮率からの見積もりにより評価 LSC のミス率の評価方法 従来型キャッシュのミス率 マルチコアシミュレータ M5 ベンチマーク プログラム splash2 M5によるシミュレーション L2 アクセストレース 従来型キャッシュの L2 ミス率 ミスス率 容量 平均圧圧縮率 平均圧縮率 容量 LSCのミス率に換算 31
評価方法 面積 : ミス率を従来型キャッシュ 8MB における値に固定 ミス率 : データアレイ容量を1MBに固定 L1ミスペナルティ : データアレイ容量を1MBに固定従来型キャッシュ L2 キャッシュュミス率 LSC の容量 LSC 従来型キャッシュ L2 キャッシュサイズ 8MB L2 キャッシシュミス率 従来型キャッシュのミス率 LSC のミス率 必要ビット数 面積の比較ミス率および L1ミスペナルティの比較 LSC データメモリ :1MB M5の評価環境 コア数 8 L1キャッシュ サイズ :32KB, 連想度 :2, ブロックサイズ :64B L2キャッシュ 連想度 :8ブロックサイズ:64B 32
キャッシュミス率一定とした場合の面積削減効果 ブロックサイズ 64B, 従来型キャッシュ容量 8MB 圧縮率 0.21 0.69 0.43 0.48 0.86 0.55 必要メモモリ容量 [MB] 12 10 8 6 4 2 0 データアレイ容量 ポインタアレイ容量 タグ容量 52% 面積削減 base LSC base LSC base LSC base LSC base LSC base LSC Cholesky Barnes FFT FMM LUCon OceanCon ベンチマーク プログラム 圧縮率が低い程, 面積を大幅に削減 33
キャッシシュミス率 データアレイ容量を一定とした場合の 0.9 1 08 0.8 0.7 0.6 0.5 0.4 0.3 0.2 01 0.1 0 ミス率削減効果ブロックサイズ64B, データアレイ容量 1MB base LSC 圧縮率 0.21 L2 キャッシシュミス率 08 0.8 0.6 04 0.4 ミス率を大幅に削減できない 0.2 0 18 ポイント削減 1 8 16 32 L2キャッシュ容量 [MB] 容量を増加した場合容量を増加するとミス率がすぐに飽和, ミス率の減少幅小 ベンチマーク プログラム すべてのプログラムでミス率を削減 34
L2 キャッシシュミス率キャッシシュミス率 データアレイ容量を一定とした場合の ミス率削減効果ブロックサイズ64B, データアレイ容量 1MB 0.9 1 base LSC 0.8 圧縮率 08 0.8 055 0.55 0.60.7 0.6 0.4 0.5 ミス率を 18 ポイント削減 0.2 0.4 0.3 00.2 01 0.1 1 8 16 32 0 L2キャッシュ容量 [MB] 容量を増加する場合, ミス率の減少幅大 ベンチマーク プログラム すべてのプログラムでミス率を削減 35
ィ比 L1 ミスペペナルテ 1.2 1 0.8 0.6 04 0.4 0.2 0 データアレイ容量一定とした場合の L1 ミスペナルティ削減効果 ブロックサイズ64B, データアレイ容量 1MB 従来型キャッシュの L1 ミスペナルティで正規化 L1ミスペナルティ 30% 削減 ベンチマーク プログラム アクセス時間を考慮した場合でも L1ミスペナルティを大幅に削減 36
まとめ データ値の局所性を利用したライン共有キャッシュを提案 ミス率一定条件において 面積 : 最大 52% 削減 容量一定条件において ミス率 : 最大 18ポイント削減 L1ミスペナルティ : 最大 30% 削減 ライン共有キャッシュの有効性を確認 37
今後の課題 ライン共有キャッシュの詳細な評価 キャッシュミス率 アクセスレイテンシ アクセスあたりの消費電力 ライン共有キャッシュの適用範囲を拡張 LSC はデータアレイへの書込み回数を削減 不揮発性メモリに利用 既存研究との比較 38
ご清聴ありがとうございました 39