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