ｽﾗｲﾄﾞﾀｲﾄﾙなし

タグ比較結果の再利用に基づく
メディア・アプリケーション向け低消費電力キャッシュ
○井上弘士1 V. Moshynaga1 村上和彰2
1福岡大学
工学部
2九州大学大学院システム情報科学研究院
発表手順
• はじめに
• 従来型キャッシュにおける問題点
• ヒストリ・ベース・ルックアップ・キャッシュ
• 定量的評価
• おわりに
はじめに
キャッシュの大容量化
→キャッシュ消費エネルギーが増大！
チップ全体の消費電力において、キャッシュが占める割合
DEC 21164 CPU* StrongARM SA-110 CPU* Bipolar ECL CPU**
25%
43%
50%
* Kamble, et. Al., “Analytical energy Dissipation Models for Low Power Caches”, IＳLPED’97
** Joouppi, et. Al., “A 300-MHz 115-W 32-b Bipolar ECL Microprocessor” ,IEEE Journal
of Solid-State Circuits’93
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
Ｓｔｅｐ３．タグ比較
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Index
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
Ｓｔｅｐ３．タグ比較
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Index
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
Ｓｔｅｐ３．タグ比較
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Index
Tag
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
Ｓｔｅｐ３．タグ比較
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Index
Tag
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
Ｓｔｅｐ３．タグ比較
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー動作と消費エネルギーー
タグ・サブアレイ
ライン・サブアレイ
Way 0 Way 1 Way 2 Way3
Ｓｔｅｐ１．アドレス・デコード
Ｓｔｅｐ２．全ウェイにおけるタグと
ラインを同時読み出し
アクセス当たりの
平均消費エネルギー
タグ読み出しライン読み出し
Ｓｔｅｐ３．タグ比較
Ecache = Etag + Eline
Tnum×Etag_sa
読み出さ
れるタグ数
タグ
サブアレイ
アクセス
Lnum×Eline_sa
読み出され
るライン数
ライン
サブアレイ
アクセス
Ｓｔｅｐ４．不一致の場合、
ラインのリプレイス
従来型4ウェイ・アソシアティブ・キャッシュ
ー問題点ー
Way 0 Way 1 Way 2 Way3
参照データは唯一のウェイに存在する
にも関わらず全てのウェイを活性化
本来データ読み出しのために消費すべきエネルギー
Eline_sa
高速データ検索のために消費する無駄なエネルギー
4×Etag_acc + (4-1)×Eline_acc
提案型4ウェイ・アソシアティブ・キャッシュ
ー本研究の狙いー
ヒストリ・ベース・ルックアップ・キャッシュを提案
 目的：命令キャッシュにおける無駄な消
費エネルギーを削減！
 手段：過去のタグ比較結果を再利用！
 効果：0.2%の性能低下をもたらすだけで、
最大68%の消費エネルギーを削減！
HBLキャッシュ
ー基本概念 (1/3) ー
事実1：命令キャッシュのヒット率は極めて高い
→キャッシュ内容の更新は稀にしか発生しない
事実2：プログラムはループ構造に基づく
→多くの命令は繰り返し実行される
Miss!
命令A
参照
命令A
参照
命令A
参照
命令A
参照
命令A
参照
どの
Way?
どの
Way?
どの
Way?
どの
Way?
どの
Way?
Miss!
時刻
キャッシュ・ミス・インターバル
キャッシュの内容は変更されていないにも関わらず
同一命令へのアクセス時、毎回検索を行っているのでは？
HBLキャッシュ
ー基本概念 (2/3) ー
キャッシュ・ミス・インターバル当たりの平均アクセス回数
（無駄なキャッシュ検索はどの程度存在するのか？）
16 KB 4-way set-associative cache with 32 B line size
HBLキャッシュ
ー基本概念 (3/3) ー
1. 時刻 T にてある命令Aを参照
way0 way1 way2 way3
•タグ比較を実行
Index
•タグ比較結果を保存
Hit!
HBLキャッシュ
ー基本概念 (3/3) ー
1. 時刻 T にてある命令Aを参照
way0 way1 way2 way3
•タグ比較を実行
Index
•タグ比較結果を保存
（命令Aのヒット・ウェイ=2）
Hit!
HBLキャッシュ
ー基本概念 (3/3) ー
1. 時刻 T にてある命令Aを参照
way0 way1 way2 way3
•タグ比較を実行
Index
•タグ比較結果を保存
（命令Aのヒット・ウェイ=2）
Hit!
2. キャッシュ・ミスが発生したら記録した全てのタグ比較
結果を無効化
HBLキャッシュ
ー基本概念 (3/3) ー
1. 時刻 T にてある命令Aを参照
way0 way1 way2 way3
•タグ比較を実行
Index
•タグ比較結果を保存
（命令Aのヒット・ウェイ=2）
Hit!
2. キャッシュ・ミスが発生したら記録した全てのタグ比較
結果を無効化
3. 時刻T+ｘにおいて命令Aを再度参照
way0 way1 way2 way3
Index
Hit!
• 有効なタグ比較結果が保存
されていれば再利用
（命令Aのヒット・ウェイ=2）
HBLキャッシュ
ー内部構造ー
前分岐予測結果
検索履歴レジスタ
Tag Check Result
前PC保存用レジスタ
Write Address
検索履歴テーブル
Branch-Inst. Addr.
PC
Target Addr.
BTB (Branch Target Buffer)
Branch-Inst. Addr.
Taken
Not
Taken
I-Cache
Target Addr.
検索履歴テーブル
のエントリ
valid flag
n way pointers
分岐予測
結果
WP
レジスタ
valid
モード
制御
WP
Miss?
HBLキャッシュ
ー動作モードー
検索省略モード：ウェイ・ポインタ（WP)レジスタに格納さ
れたWPの値に従って、キャッシュはウェイ選択を行う．
検索記録モード：従来型キャッシュと同様にウェイ検索
を行う．ただし，検索履歴レジスタ(Look-up History
Reg.)にタグ比較結果（ヒット・ウェイ番号）を記録する．
通常モード：従来型キャッシュと同様にウェイ検索を行う．
タグ比較結果の記録は行わない．
HBLキャッシュ
ー動作モードー
検索省略モード：ウェイ・ポインタ（WP)レジスタに格納さ
れたWPの値に従って、キャッシュはウェイ選択を行う．
検索記録モード：従来型キャッシュと同様にウェイ検索
を行う．ただし，検索履歴レジスタ(Look-up History
Reg.)にタグ比較結果（ヒット・ウェイ番号）を記録する．
通常モード：従来型キャッシュと同様にウェイ検索を行う．
タグ比較結果の記録は行わない．
HBLキャッシュ
ー動作（検索省略モード）ー
前分岐予測結果
検索履歴レジスタ
Tag Check Result
前PC保存用レジスタ
Write Address
検索履歴テーブル
Branch-Inst. Addr.
PC
Target Addr.
BTB (Branch Target Buffer)
Branch-Inst. Addr.
Taken
Not
Taken
I-Cache
Target Addr.
検索履歴テーブル
のエントリ
valid flag
n way pointers
分岐予測
結果
WP
レジスタ
valid
モード
制御
WP
Miss?
HBLキャッシュ
ー動作（検索省略モード）ー
前分岐予測結果
検索履歴レジスタ
Tag Check Result
前PC保存用レジスタ
Write Address
検索履歴テーブル
Branch-Inst. Addr.
PC
Target Addr.
BTB (Branch Target Buffer)
Branch-Inst. Addr.
Taken
Not
Taken
I-Cache
Target Addr.
検索履歴テーブル
のエントリ
valid flag
n way pointers
分岐予測
結果
WP
レジスタ
Valid
== 1
モード
制御
WP
Miss?
HBLキャッシュ
ー動作モードー
検索省略モード：ウェイ・ポインタ（WP)レジスタに格納さ
れたWPの値に従って、キャッシュはウェイ選択を行う．
検索記録モード：従来型キャッシュと同様にウェイ検索
を行う．ただし，検索履歴レジスタ(Look-up History
Reg.)にタグ比較結果（ヒット・ウェイ番号）を記録する．
通常モード：従来型キャッシュと同様にウェイ検索を行う．
タグ比較結果の記録は行わない．
HBLキャッシュ
ー動作（検索記録モード）ー
前分岐予測結果
検索履歴レジスタ
Tag Check Result
前PC保存用レジスタ
Write Address
検索履歴テーブル
Branch-Inst. Addr.
PC
Target Addr.
BTB (Branch Target Buffer)
Branch-Inst. Addr.
Taken
Not
Taken
I-Cache
Target Addr.
検索履歴テーブル
のエントリ
valid flag
n way pointers
分岐予測
結果
WP
レジスタ
Valid
== 0
モード
制御
WP
Miss?
HBLキャッシュ
ー動作（検索記録モード）ー
前分岐予測結果
検索履歴レジスタ
Tag Check Result
前PC保存用レジスタ
Write Address
BTB Hit!
検索履歴テーブル
Branch-Inst. Addr.
PC
Target Addr.
BTB (Branch Target Buffer)
Branch-Inst. Addr.
Taken
Not
Taken
I-Cache
Target Addr.
検索履歴テーブル
のエントリ
valid flag
n way pointers
分岐予測
結果
WP
レジスタ
valid
モード
制御
WP
Miss?
HBLキャッシュ
ー動作モードー
検索省略モード：ウェイ・ポインタ（WP)レジスタに格納さ
れたWPの値に従って、キャッシュはウェイ選択を行う．
検索記録モード：従来型キャッシュと同様にウェイ検索
を行う．ただし，検索履歴レジスタ(Look-up History
Reg.)にタグ比較結果（ヒット・ウェイ番号）を記録する．
通常モード：従来型キャッシュと同様にウェイ検索を行う．
タグ比較結果の記録は行わない．
HBLキャッシュ
ー動作モードー
検索省略モード：ウェイ・ポインタ（WP)レジスタに格納さ
れたWPの値に従って、キャッシュはウェイ選択を行う．
検索記録モード：従来型キャッシュと同様にウェイ検索
を行う．ただし，検索履歴レジスタ(Look-up History
Reg.)にタグ比較結果（ヒット・ウェイ番号）を記録する．
通常モード：従来型キャッシュと同様にウェイ検索を行う．
タグ比較結果の記録は行わない．
(連想度が４の場合)
Ecache = Tnum×Etag_acc + Lnum×Eline_acc
従来型
４
省略
0
記録 / 通常４
４
１
４
HBLキャッシュ
ー動作モード遷移ー
CONDtoNM：
命令キャッシュ・ミス or
BTBリプレースメント or
分岐予測ミスからの復帰 or
RASアクセス
CONDtoNM
省略モード
Valid==1
BTBヒット
WP読出しオーバフロー
WP書込みオーバフロー
Valid==0
記録モード
通常モード
CONDtoNM
 BTBヒット時に省略モードか記録モードかを決定
 キャッシュ・ミス発生時には全てのvalidフラグをリセット
（記録したタグ比較結果を無効化）
HBLキャッシュ
ー利点と欠点のまとめー
• 利点：
 タグ比較結果の再利用により無駄なウェイ・アクセ
スを回避して低消費エネルギー化（省略モード時）
• 欠点：
 記録モードや通常モード時には従来型と同じ数の
タグ / ライン・サブアレイを活性化
 BTB拡張に伴う消費エネルギー・オーバヘッド
 記録したタグ比較結果の無効化処理時における
CPUからのBTBアクセス禁止（ストール発生）
 タグ比較結果の検索履歴テーブル書込み時におけ
るCPUからのBTBアクセス禁止（ストール発生）
評価
ー評価環境ー
 SimpleScalarによるサイクル・ベース・シミュレーション
 16KBの4ウェイ・セットアソシアティブ・キャッシュを想定
 ＢＴＢアクセスは分岐（又はジャンプ）実行時のみ発生
 消費エネルギーに関してはKambleのモデル*を使用
 ＢＴＢ拡張に伴う消費エネルギー・オーバヘッドも含む
SPECint95
Benchmark Programs
099.go, 124.m88ksim, 126.gcc, 129.compress,130.li, 132.ijpeg
SPECfp95
102.swim
Mediabench
mpeg2encode, mpeg2decode, adpcm_enc, adpcm_dec
*) M.B.Kamble and K.Ghose, ”Analytical Energy Dissipation Models For Low Power Caches,” ISLPED97
# of WPs = 4
1.2
1.0
62% 0.2%
1.2
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
099.go
126.gcc
130.li
102.swim adpcm(d) mpeg2(d)
124.m88ksim 129.comp. 132.ijpeg adpcm(e) mpeg2(e)
Normalized Exe. Time (cycle)
Normalized Energy (Joule)
評価
ー実験結果ー
Normalized Energy (Joule)
評価
ーWP数が消費エネルギーに与える影響ー
126.gcc
w/o Pre-Decoding
w/ Pre-Decoding
1.0
0.8
0.6
0.4
0.2
0.0
1
2
4
8
16
32
1
2
4
8
16
32
# of Way Pointer
Energy for Cache Access
Energy Overhead at BTB
評価
ー連想度が消費エネルギーに与える影響ー
Energy (Joule)
mpeg2decode
8.E+06
7.E+06
6.E+06
5.E+06
4.E+06
3.E+06
2.E+06
1.E+06
0.E+00
Conventional
1 2
4
8 16 32 64
HBL Cache
1 2
Associativity
4
Eothers
Etag
Edata,bl
Edata,prectl
8 16 32 64
0.8um CMOS* **
*) M.B.Kamble and K.ghose, “Energy-Efficiency of VLSI Caches: A Comparative Study,” 10th Int. Conf. On VLSI Design
**) S.J.E.Wilton and N.P.Jouppi, “An Enhanced Access and Cycle Time Model for On-Chip Caches,” WRL Research Report 93/5
Normalized Tag-Compare Count
評価
ー他方式との比較ー
ITC:Interline Look-up Cache
HBLC:History-Based Look-up Cache
ITC+HBLC
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
099.go
126.gcc
130.li
102.swim adpcm(d) mpeg2(d)
124.m88ksim 129.comp. 132.ijpeg adpcm(e) mpeg2(e)
おわりに
 セット・アソシアティブ命令キャッシュの低消費電力
化を目的としたキャッシュ・アーキテクチャを提案
 ２％の性能低下をもたらすだけで最大６２％の
キャッシュ・アクセス消費エネルギーを削減
 性能ならびに消費エネルギーに関する詳細な評
価・解析
今後の予定
実設計に基づくより詳細な消費エネルギーの評価
Backup Slides
Normalized Energy (Joule)
評価
ーWP数が消費エネルギーに与える影響 (1/2)ー
132.ijpeg
w/o Pre-Decoding
w/ Pre-Decoding
1.0
0.8
0.6
0.4
0.2
0.0
1
2
4
8
16
32
1
2
4
8
16
32
# of Way Pointer
Energy for Cache Access
Energy Overhead at BTB
3
2.5
2
126.gcc
Cache Miss
Penalty
1.5
BTB Replacement
Cache Miss
099.go
1
mpeg2(d) 132.ijpeg
0.5
0
1
2
4
8
16
32
WP Invalidation Penalty (cycle)
Breakdown of
WP invalidations
Normalized Exe. Time (cycle)
評価
ーWP無効化が性能に与える影響ー
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
099.go 126.gcc 130.li 102.swim adpcm(d) mpeg2(d)
124.m88ksim 129.comp.132.ijpeg adpcm(e) mpeg2(e)
評価
ー連想度が消費エネルギーに与える影響ー
Eothers
Etag
Edata,bl
Edata,prectl
099.go
Energy (Joule)
3.E+07
3.E+07
Conventional
2.E+07
HBL Cache
2.E+07
1.E+07
5.E+06
0.E+00
1 2
4
8 16 32 64
1 2
Associativity
4
8 16 32 64
0.8um CMOS* **
*) M.B.Kamble and K.ghose, “Energy-Efficiency of VLSI Caches: A Comparative Study,” 10th Int. Conf. On VLSI Design
**) S.J.E.Wilton and N.P.Jouppi, “An Enhanced Access and Cycle Time Model for On-Chip Caches,” WRL Research Report 93/5
評価
ー連想度が消費エネルギーに与える影響ー
132.ijpeg
Energy (Joule)
6.E+07
5.E+07
Conventional
HBL Cache
Eothers
Etag
Edata,bl
Edata,prectl
4.E+07
3.E+07
2.E+07
1.E+07
0.E+00
1 2
4
8 16 32 64
1 2
Associativity
4
8 16 32 64
0.8um CMOS* **
*) M.B.Kamble and K.ghose, “Energy-Efficiency of VLSI Caches: A Comparative Study,” 10th Int. Conf. On VLSI Design
**) S.J.E.Wilton and N.P.Jouppi, “An Enhanced Access and Cycle Time Model for On-Chip Caches,” WRL Research Report 93/5
評価
ー連想度が消費エネルギーに与える影響ー
126.gcc
Energy (Joule)
7.E+07
6.E+07
5.E+07
Conventional
HBL Cache
Eothers
Etag
Edata,bl
Edata,prectl
4.E+07
3.E+07
2.E+07
1.E+07
0.E+00
1 2
4
8 16 32 64
1 2
Associativity
4
8 16 32 64
0.8um CMOS* **
*) M.B.Kamble and K.ghose, “Energy-Efficiency of VLSI Caches: A Comparative Study,” 10th Int. Conf. On VLSI Design
**) S.J.E.Wilton and N.P.Jouppi, “An Enhanced Access and Cycle Time Model for On-Chip Caches,” WRL Research Report 93/5
評価
ーWP数が消費エネルギーに与える影響 (1/2)ー
Normalized Energy (Joule)
w/ Pre-Decoding
(BTB access occurs only at branch, or jump, executions)
1.0
126.gcc
132.ijpeg
0.8
0.6
0.4
0.2
0.0
1
2
4
8
16
32
1
2
4
8
16
32
# of Way Pointer
Energy for Cache Access
Energy Overhead at BTB
評価
ーWP数が消費エネルギーに与える影響 (2/2)ー
Normalized Energy (Joule)
w/o Pre-Decoding
(BTB access occurs for all instructions)
1.0
126.gcc
132.ijpeg
0.8
0.6
0.4
0.2
0.0
1
2
4
8
16
32
1
2
4
8
16
32
# of Way Pointer
Energy for Cache Access
Energy Overhead at BTB

Download Report