適応型ウェイ予測キャッシュの設計とその評価

低消費電力化を目的とした
適応型ウェイ予測キャッシュとその評価
福岡大学大学院 工学研究科 電子工学専攻
田中 秀和
発表手順
キャッシュ消費エネルギーの影響
ウェイ予測型キャッシュとその問題点
履歴に基づく適応型ウェイ予測方式
複数動作モードのサポートと切替
分岐予測技術を応用した予測信頼度の決定
性能/消費エネルギー評価
まとめ
キャッシュ消費エネルギーの影響
+
CPU
DRAM
Cache
Memory
チップ全体の消費エネルギーにおいて、キャッシュが占める割合
DEC 21164 CPU * StrongARM SA-110 CPU *
25%
43%
キャッシュの低消費エネルギー化は重要!
* Kamble, et. Al., “Analytical energy Dissipatiion Models for Low Power Caches”, ISLPED’97
従来型4ウェイ・セットアソシアティブ・キャッシュ
タグ記憶用メモリ
メモリ・アドレス
タグ インデックス
データ記憶用メモリ
参照ウェイ
プロセッサが参照
するデータ
セット
ウェイ
タグ比較回路
•セット・アソシアティブ・キャッシュの特徴
•同一セットであればどのウェイにでもデータを格納可能
•読出し時には全てのウェイにてデータを検索(全ウェイを活性化)
•無駄なエネルギーを消費(無駄なウェイの活性化)
ウェイ予測型キャッシュとその問題点
参照するデータは「ウェイ2」に存在すると仮定
way0
way0
2
3
1st
1
2
ウェイ予測テーブル
予測されたウェイ番号
1
1
2
3
1st
誤ったウェイ予測
2nd
正しいウェイ予測
•特徴
•参照すべきデータが存在するであろうウェイを予測
•予測が正しい場合には無駄なウェイの活性化を回避
•欠点(予測の誤り)
•従来型と比較して全く消費エネルギーを削減できない!
•従来型と比較してアクセス時間が2倍になる!
誤ったウェイ予測時のペナルティを削減するには?
•問題点
•ウェイ予測は常に正しいと期待している!
•全てのアクセスにおいてウェイ予測を実施!
•実際には予測の誤りが発生!
•解決策
•ウェイ予測アクセスに加え従来アクセスもサポート
•理想的には・・・
•予測が正しい場合→ウェイ予測アクセス
•予測を誤る場合→従来アクセス
•現実的には・・・
•どのようにしてモードを切り替えるのか?
履歴に基づく適応型ウェイ予測方式
ウェイ予測が誤りと思われる
場合(=信頼度が低い)
2
3
way0
1
1
2
2
ウェイ予測テーブル
予測されたウェイ番号
•特徴
•ウェイ予測の確からしさ(=信頼度)を動的に判定
•信頼度に基づきアクセス・モードを切り替え
•解決すべき課題
•どのようにして信頼度を決定するのか?
3
1st
1
1st
way0
ウェイ予測が正しいと思われる
場合(=信頼度が高い場合)
分岐予測技術を応用した予測信頼度の決定
•信頼カウンタの実装
•ウェイ予測結果に従い++/-•モード切替アルゴリズム(過去のウェイ予測結果に基づく)
•信頼カウンタ≧2→ウェイ予測アクセス
•信頼カウンタ≦1→従来アクセス
ウェイ予測モード
11
10
正しい予測
誤った予測
00
01
従来モード
2ビット飽和カウンタ
信頼カウンタ
テーブル
way0
1
2
3
ウェイ予測テーブル
分岐予測技術を応用した予測信頼度の決定
•信頼カウンタの実装
•ウェイ予測結果に従い++/-•モード切替アルゴリズム(過去のウェイ予測結果に基づく)
•信頼カウンタ≧2→ウェイ予測アクセス
•信頼カウンタ≦1→従来アクセス
同一セットへのアクセスと仮定
ウェイ予測モード
11
アクセス1
(従来モード)
10
正しい予測
誤った予測
00
正しい予測
T
01
従来モード
2ビット飽和カウンタ
信頼カウンタ
テーブル
way0
1
2
3
ウェイ予測テーブル
分岐予測技術を応用した予測信頼度の決定
•信頼カウンタの実装
•ウェイ予測結果に従い++/-•モード切替アルゴリズム(過去のウェイ予測結果に基づく)
•信頼カウンタ≧2→ウェイ予測アクセス
•信頼カウンタ≦1→従来アクセス
同一セットへのアクセスと仮定
ウェイ予測モード
11
アクセス1
アクセス2
(従来モード) (従来モード)
10
正しい予測
誤った予測
00
正しい予測 正しい予測
01
従来モード
2ビット飽和カウンタ
信頼カウンタ
テーブル
way0
1
2
3
ウェイ予測テーブル
T
分岐予測技術を応用した予測信頼度の決定
•信頼カウンタの実装
•ウェイ予測結果に従い++/-•モード切替アルゴリズム(過去のウェイ予測結果に基づく)
•信頼カウンタ≧2→ウェイ予測アクセス
•信頼カウンタ≦1→従来アクセス
同一セットへのアクセスと仮定
ウェイ予測モード
11
アクセス1
アクセス3
アクセス2
(従来モード) (従来モード)(ウェイ予測モード)
10
正しい予測
誤った予測
00
正しい予測 正しい予測
01
従来モード
2ビット飽和カウンタ
信頼カウンタ
テーブル
way0
1
2
3
ウェイ予測テーブル
正しい予測
T
適応型ウェイ予測キャッシュの構成
Tag
Index
Offset
アクセス・コントローラ
モード制御回路
メモリ・アレイ
ウェイ制御回路
WPテーブル
Control Signal
Tag
Data
消費エネルギー・オーバ・ヘッドの可能性!
信頼カウンタテーブル ウェイ予測テーブル
タグ比較回路
テーブル
更新回路
LRU判定回路
Referenced-Line
性能/消費エネルギー評価
評価目的
• どの程度ウェイ予測方式の性能低下を削減できるか?
• どの程度ウェイ予測方式のエネルギー削減効果を維持できるか?
評価対象
• L1データキャッシュ
• キャッシュ・サイズ:16KB、ラインサイズ:32B、連想度:4
評価項目
• 追加回路による消費エネルギー・オーバ・ヘッド(実設計)
• 平均キャッシュ・アクセス時間(シミュレーション)
• 平均消費エネルギー(シミュレーション)
ベンチマーク
プログラム
(SPEC2000)
キャッシュ
シミュレー
タ
SimpleScalar
(アウト・オブ・オーダ実行)
平均キャッシュ・アクセス時間
平均消費エネルギー
追加回路による消費エネルギーへの影響
自動配置配線
による設計
カスタム設計
Verilogによる
回路記述
論理設計
追加回路
0.9%
論理合成
カスタム
レイアウト
自動配置配線
メモリ・アレイ
95%
回路解析
メモリ・アレイのエネルギーが支配的
16
4.g
zip
17
5.v
p
17 r
6.g
c
18 c
1.m
19
c
7.p f
ar
25 ser
5.v
or
t
25 ex
6.b
z ip
2
17
7.m
es
a
17
18 9.ar
3.e t
qu
ak
18
e
8.a
m
mp
av
er
ag
e
正規化キャッシュ・アクセス時間
平均キャッシュ・アクセス時間
1.6
0.8
0.6
0.4
0.2
ウェイ予測
適応型ウェイ予測
1.4
ベンチマーク・プログラム
21%
26%
1.2
1
最大26%性能向上!
平均7%性能向上
0
16
4.g
zip
17
5.v
pr
17
6.g
c
18 c
1.m
19
c
7.p f
ar
25 ser
5.v
or
t
25 ex
6.b
zi
17 p2
7.m
es
a
17
18 9.ar
3.e t
qu
ak
18
e
8.a
m
mp
av
er
ag
e
正規化消費エネルギー
平均消費エネルギー
0.7
0.4
0.3
0.2
ウェイ予測
適応型ウェイ予測
0.6
15%
0.5
最大15%削減効果の低下
平均7%削減効果の低下
0.1
0
ベンチマーク・プログラム
まとめ
適応型ウェイ予測キャッシュの提案
•全ベンチマークにおいて・・・
•ウェイ予測型キャッシュと比べて・・・
平均7%のエネルギー削減効果の低下
平均7%の性能向上
•最善ケース(188.ammp)において・・・
•ウェイ予測型キャッシュと比べて・・・
1.5%のエネルギー削減効果の低下
26%の性能向上
適応型ウェイ予測キャッシュは有効!
17
5.v
pr
17
6.g
cc
18
1.m
cf
19
7.p
ar
se
r
25
5.v
or
te
x
25
6.b
zip
2
17
7.m
es
a
17
9.a
rt
18
3.e
qu
ak
e
18
8.a
m
mp
av
er
ag
e
zip
16
4.g
WPモード使用率
WPモード使用率
1.2
1
0.8
0.6
0.4
0.2
0
ベンチマーク・プログラム
17
5.v
pr
17
6.g
cc
18
1.m
cf
19
7.p
ar
se
r
25
5.v
or
te
x
25
6.b
zip
2
17
7.m
es
a
17
9.a
rt
18
3.e
qu
ak
e
18
8.a
m
mp
av
er
ag
e
16
4.g
zip
WPモード内ウェイ予測ヒット率
WPモードにおけるウェイ予測ヒット率
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
WP
WP:ウェイ予測型キャッシュ
AWP
ベンチマーク・プログラム
AWP:適応型ウェイ予測キャッシュ
評価式-アクセス時間平均キャッシュ・アクセス時間
WPモード時の平均アクセス時間
WPモード使用率
Nモード時の平均アクセス時間
CATavg =(1 - WPMR)×ATN + WPMR×ATWP
キャッシュ・サイクル時間
テーブル参照時間
ATN=CCTcache + RTtable
ATWP=WPHR×CCTcache
+ (1 - WPHR)×2CCTcache+ RTtable
WPモード使用時のウェイ予測ヒット率
評価式-消費エネルギーキャッシュ・アクセス当たりの
平均消費エネルギー
WPモード時の消費エネルギー
CEavg=(1-WPMR)×EN + WPMR×EWP
Nモード時の消費エネルギー
ウェイ数
テーブル参照に要する
消費エネルギー
1ウェイあたりの消費エネルギー
EN=W×Eway + Etable
EWP=WPHR×Eway + (1 - WPHR)×W×Eway + Etable
カウンタ更新方法
単純アップダウン方式
特徴
動作が単純
WPモード
11
10
00
01
Nモード
予測正しい
分岐予測方式
特徴
モード切替頻度小
回路構成が複雑
予測誤り
WPモード
11
10
01
00
Nモード
カウンタの決定-カウンタ更新方法0.7
0.08
0.6
0.07
消費エネルギー削減率
キャッシュ・アクセス時間増加率
0.09
0.06
0.05
0.04
0.03
0.02
0.5
0.4
0.3
0.2
0.1
0.01
0
単純アップダウン
分岐予測
カウンタ更新方法
0
単純アップダウン
分岐予測
カウンタ更新方法
単純アップダウン方式に決定
カウンタの決定-実装ビット数-
0.086
0.62
0.084
0.61
0.082
エネルギー削減率
キャッシュ・アクセス時間増加率
カウンタに実装するビット数によりモード切り替え頻度が変化
0.08
0.078
0.076
0.074
0.6
0.59
0.58
0.57
0.072
0.56
0.07
0.55
0.068
1ビット
2ビット
3ビット
4ビット
1ビット
実装ビット数
2ビットに決定
2ビット
3ビット
実装ビット数
4ビット
設計方法
 自動配置配線によるレイアウト設計
1.
2.
3.
4.
ハードウェア記述言語(Verilog)による回路記述
論理合成(Design Compiler)
自動配置配線ツール(Apollo)によるレイアウト
回路シミュレーションによる解析(hspice)
 カスタムレイアウト設計
1.
2.
3.
4.
回路設計(Composer)
論理検証(hspice)
カスタムレイアウト
回路シミュレーションによる解析(hspice)
目的の違いによる実装動作モード
<性能重視型>
ウェイ予測(WP)
モード
切り替え
従来型(N)
モード
<消費エネルギー削減重視型>
ウェイ予測(WP)
モード
切り替え
段階型(P)
モード
適応型ウェイ予測方式にする意義
ウェイ予測方式に比べ、平均キャッシュ・アクセス時間を削減
現在のプロセッサでは・・・
キャッシュのアクセス時間がボトル・ネック
⇒キャッシュのアクセス時間がチップ全体の性能に大きく影響
キャッシュの性能を落とさずに低消費エネルギー化を実現する
適応型ウェイ予測方式は有効