キャッシュ・ミス頻発命令 が性能に与える影響

キャッシュ・ミス頻発命令
が性能に与える影響
福岡大学
○堂後靖博
2004/09/08
井上弘士
1
発表内容

はじめに

実験環境

キャッシュ・ミス頻発命令の特徴解析

考察

おわりに
2004/09/08
2
はじめに
性
能
向
上
比
(
基
準
は
1
9
8
0
年
)
~メモリ・ウォール問題~
10
5
10
4
CPU
55%/年
10
3
10
2
10
1
10
0
性能向上差
48%/年
1980
1990
memory 2000
7%/年
2005 (年)
マイクロプロセッサと主記憶との
性能向上差を埋める技術が必要
出典:J.L.Hennessy, D.A.Patterson, “Computer Architecture: A Quatitative Approach 3rd Edition”
2004/09/08
3
メモリ・ウォール問題を解決する手段


キャッシュ・メモリの導入
キャッシュ・プリフェッチ
•データの対象は?
•データの再利用性は?
•いつするか?
解決手段は
1つだけではない!
キャッシュ・ミス頻発命令
(Troublesome命令:TS命令)
TS命令に着目したメモリ性能向上技術
2004/09/08
4
TS命令に着目したメモリ性能向上技術

プログラム実行中、処理内容に応じてTS命令専用
最適化を施し高い性能向上を実現
1.
TS命令の動的検出
2.
最適化手法、最適化適用範囲の決定
3.
TS命令専用最適化回路の生成

TS命令専用プリフェッチ回路

TS命令専用キャッシュ

etc
2004/09/08
重要!
5
目的


TS命令動的検出の可能性の検討

TS命令の存在とその出現率

TS命令の生存期間

TS命令のアクセス・パターン
TS命令が性能へ与える影響を考察
2004/09/08
6
実験環境

シミュレータ

Simplescalar 3.0d

キャッシュ・メモリ



L1:32KB(32B,4way,256lines)

L2:256KB(32B,4way,2048lines)
命令発行:out-of-order
対象アプリケーション

SPEC CPU 95 ベンチマーク

整数演算 8種類(入力にはtrainを使用)
2004/09/08
7
実験方法
TS命令の存在調査
ベンチマーク
SPECint95
Simplescalar
3.0d
トレース
ファイル
キャッシュ・ミス
を引起す命令
TS命令の生存期間,アクセス・パターン
ベンチマーク
SPECint95
トレース
ファイル
TS命令上位10個
2004/09/08
Simplescalar
3.0d
トレース
ファイル
TS命令の
•生存期間
•アクセス・パターン
8
キャッシュ・ミス頻発命令の特徴解析


TS命令動的検出の可能性の検討

TS命令の存在とその出現率

TS命令の生存期間

TS命令のアクセス・パターン
TS命令が性能へ与える影響を考察
2004/09/08
9
TS命令の出現頻度
TS
ミ 全 100%
ス ミ 90%
数ス
( 数 80%
10 に
個 占 70%
60%
)
のめ
割 る 50%
合
40%
命
令 30%
2004/09/08
x
ort
e
14
7.v
erl
13
4.p
pe
g
13
0.li
13
2.ij
12
4.m
09
9.g
88
ksi
m
12
6.g
cc
12
9.c
om
pre
ss
20%
10%
0%
o
L1Cache
L2Cache
10
TS命令は存在するか?
129.compress
126.gcc
23%
2.6%
1.8%
1.7%
TS1
22%
21%
上位3命令で66%
ミスを引起す命令の
局所性が高い!
2004/09/08
上位3命令で6%
TS2
TS3
ミスを引起す命令の
局所性が低い!
11
キャッシュ・ミス頻発命令の特徴解析


TS命令動的検出の可能性の検討

TS命令の存在とその出現率

TS命令の生存期間

TS命令のアクセス・パターン
TS命令が性能へ与える影響を考察
2004/09/08
12
TS命令の生存期間
TS命令が長時間に渡って実行
一定間隔でミスを引起している
~129.compress(L1cache)~
TS命令専用最適化
の効果が期待できる
ミ
ス
頻
発
命
令
上
位
10
個
2004/09/08
実行サイクル(1万サイクルを1)
13
キャッシュ・ミス頻発命令の特徴解析


TS命令動的検出の可能性の検討

TS命令の存在とその出現率

TS命令の生存期間

TS命令のアクセス・パターン
TS命令が性能へ与える影響を考察
2004/09/08
14
メモリ・アクセス・パターン①(局所集中型)
TS4
300000000
298000000
メモリアドレス
296000000
294000000
292000000
アクセスが集中!!
290000000
288000000
286000000
284000000
282000000
0
500
2000
1500
1000
実行サイクル
2500
3000
動的特徴抽出が容易!!
2004/09/08
15
メモリ・アクセス・パターン②(中域集中型)
メモリアドレス
メモリアドレス
268650000
268600000
268550000
268500000
TS2
0
500
1000 1500 2000
実行サイクル
2500
3000
268950000
268900000
268850000
268800000
268750000
268700000
268650000
268600000
268550000
268500000
268450000
0
500
TS3
1000 1500 2000
実行サイクル
2500
3000
集中した範囲でアクセス
2004/09/08
動的特徴抽出が可能!
16
メモリ・アクセス・パターン③(均一分散型)
TS1
268800000
メモリアドレス
268750000
268700000
参照アドレスの幅が等しい
268650000
268600000
268550000
動的特徴抽出が可能!
268500000
268450000
0
500
2004/09/08
1000 1500 2000
実行サイクル
2500
3000
17
考察

TS命令が存在(099.go,126.gccを除く全てのベンチマーク)

TS命令の生存期間が比較的長い


キャッシュ・ミスの回避

ミス・ペナルティの隠蔽
性能向上を達成可能!
TS命令の種類によりアクセス・パターンが異なる

TS命令の特徴に応じた手段を用いる

局所集中型TS命令 → 小容量TS命令専用キャッシュ

中域分散型TS命令 → 大容量TS命令専用キャッシュ

均一分散型TS命令 → ストライド・プリフェッチ
2004/09/08
18
おわりに

TS命令動的検出の可能性についての検討

TS命令は存在するか?
存在する

TS命令の生存期間は?
比較的長い

TS命令のアクセス・パターンは?
種類により異なる
TS命令を動的に検出することが可能!!

今後の課題

TS命令の動的検出・特徴抽出の手法確立と性能評価
2004/09/08
19
2004/09/08
20
TS命令が性能に与える影響
TS命令の削除による性能向上評価
2004/09/08
21
評価環境(1/2)


シミュレータ

Simplescalar3.0

命令発行:out-of-order
使用アプリケーション

SPEC CPU 2000 ベンチマーク

整数ベンチマーク


浮動小数ベンチマーク


164.gzip, 175.vpr, 176.gcc, 197.parser, 256.bzip2
177.mesa, 179.art, 183.equake
入力データ:small input
2004/09/08
22
評価環境(2/2)
プロセッサの構成
命令フェッチ
命令フェッチ/デコード/発行幅:8
RUUエントリ数:64
LSQエントリ数:32
分岐予測
分岐予測:PHT8Kエントリ/履歴長6のgshare
分岐先アドレス予測:BTB2Kエントリ4ウェイ、RAS32エントリ
演算ユニット
int-ALU数/実行レイテンシ/発行レイテンシ:4/1/1
int-MUL-DIV数:1(MUL→実行/発行レイテンシ:3/1)
(DIV→実行/発行レイテンシ:20/19)
fp-ALU数/実行レイテンシ/発行レイテンシ:4/2/1
Fp-MUL-DIV数:1(MUL→実行/発行レイテンシ:4/1)
(DIV→実行/発行レイテンシ:12/12)
(SQRT→実行/発行レイテンシ:24/24)
キャッシュ
L1命令 サイズ/連想度/ポート数/レイテンシ/ラインサイズ:64KB/2/1/1/64B
L1データ サイズ/連想度/ポート数/レイテンシ/ラインサイズ:64KB/2/1/2/64B
L2命令データ統合 サイズ/連想度/ポート数/レイテンシ/ラインサイズ:2MB/4/1/16/64B
オフチップ・アクセス・メモリバス幅/レイテンシ(L2ミスペナルティ):8B/250
TLB
命令 エントリ数/連想度/ミス・ペナルティ:1K/4/30
データ エントリ数/連想度/ミス・ペナルティ:1K/4/30
2004/09/08
23
本実験での実行命令数、コミット数
(シミュレーション結果による)
7,000,000,000
6,000,000,000
5,000,000,000
4,000,000,000
実行命令数
コミット数
3,000,000,000
2,000,000,000
1,000,000,000
rt
18
3.e
qu
ak
e
17
9.a
25
6.b
zip
2
17
7.m
es
a
se
r
19
7.p
ar
2004/09/08
17
6.g
cc
pr
17
5.v
16
4.g
zip
0
24
全ミス数に占めるTS命令(L2ミス)の割合
100%
全
ミ 80%
ス
数
に
占 60%
め
る
40%
命
令
の
割 20%
合
TS
TS_8
TS_16
TS_32
TS_64
ak
e
18
3.e
qu
rt
17
9.a
17
7.m
es
a
25
6.b
zip
2
19
7.p
ar
se
r
2004/09/08
17
6.g
cc
pr
17
5.v
16
4.g
zip
0%
25
18
3.e
qu
ak
e
rt
17
9.a
17
7.m
es
a
25
6.b
zip
2
0.08%
0.08%
0.08%
0.08%
19
7.p
ar
se
r
15%
3.90%
3.90%
3.90%
3.89%
17
6.g
cc
10.81%
pr
30%
TS
17
5.v
17.67%
16.74%
14.13%
14.00%
11.93%
TS_8
TS_16
TS_32
TS_64
19.57%
18.70%
17.20%
15.65%
20%
26
2004/09/08
2.56%
1.96%
1.29%
1.21%
0.07%
0.07%
0.06%
0.06%
1.49%
1.49%
1.47%
1.47%
5%
25.32%
22.66%
25%
10%
0%
命
令
削
除
に
よ
る
実
行
サ
イ
ク
ル
数
削
減
率
16
4.g
zip
TS命令削除による実行サイクル数の削減の割合