ppt - 早稲田大学

キャッシュヒントの自動付加による
数値計算の高速化
早稲田大学理工学研究科情報・ネットワーク専攻
稲垣良一
1 / 48
<[email protected]>
概要
プロセッサの性能を最大限に活かしたソフトウェアを作成
するためには、キャッシュの有効活用が不可欠である．
Itanium プロセッサに搭載されているキャッシュヒント機
能は、適切に使用することでキャッシュ有効活用への期
待が持てるが，既存のコンパイラはキャッシュヒントを使
用したプログラムを生成しない．
本発表では Itanium プロセッサのキャッシュヒントを紹介
し，既存のコンパイラを使用してキャッシュヒントを自動的
に付加する手法について述べる．また，FFT などの数値
計算に対してキャッシュヒントを付加した場合の性能評価
についても紹介する．
2005/7/29
2 / 48
背景 – ハードウェアの性能向上
計算機の性能は向上を続けている

プロセッサ周波数、メモリ帯域、etc ・・・
しかし、プロセッサとメモリの速度差は拡大


２年で２倍のペース
メモリアクセスコストは相対的に増加
プロセッサの性能を活かしたソフトウェアの構築
一般的な対処方法
メモリアクセス遅延の隠蔽
キャッシュの有効活用
メモリアクセスコストの
相対的な増加
2005/7/29
3 / 48
目次
背景
キャッシュの有効活用
Itanium プロセッサのキャッシュヒント
キャッシュヒントの自動付加手法
キャッシュヒント付加時の性能評価
2005/7/29
4 / 48
キャッシュ
Itanium2 Processor 1.4GHz の場合
slow
fast
Itanium2 Processor
Main Memory
L3: 3 MB
Line Size: 128 Byte
Latency: 12~13 cycle
L2: 256 KB
Line Size: 128 Byte
Latency: 5~6 cycle
Latency: 100~ cycle
キャッシュ階層間帯域:32GB/s
キャッシュ・メモリ間帯域:6.4GB/s
L1D: 16 KB
Line Size: 64 Byte
Latency: 1 cycle
2005/7/29
5 / 48
例：行列積の計算
for(i=0; i<L; i++){
for(j=0; j<N; j++){
for(k=0; k<M; k++){
z[i][j] += x[i][k] * y[k][j];
}
}
Z=X*Y
}
N
M
＝
L
×
L
Z
X
2005/7/29
6 / 48
N
M
Y
例：行列積の計算
特に工夫しないプログラムの性能
• 行列サイズが 512 以上
で性能が急落する
• 特定の行列サイズでも
性能が低下
2005/7/29
7 / 48
メモリアクセスコストを抑える具体的手法
Itanium プロセッサの機能

キャッシュの有効活用
 キャッシュヒント

後述
メモリアクセス遅延の隠蔽
 命令スケジューリング
 アドバンスト・ロード
 プリフェッチ（ハードウェア）
コンパイラががんばる
ソフトウェアレベルでの工夫

キャッシュの有効活用
 データレイアウトの改善


データの再配置
配列に対するブロッキング、パディング
 計算順序の変更


プログラマががんばる
コンパイラもがんばる
ループ変換、結合
メモリアクセス遅延の隠蔽
 プリフェッチ（ソフトウェア）
2005/7/29
8 / 48
例：行列積の計算
データレイアウトの改善

行列の転置
N
L

M
＝
L
M
×
N
Y（転置）
行列のブロッキング
＝
2005/7/29
9 / 48
×
例：行列積の計算
行列の転置
約10倍
2005/7/29
10 / 48
例：行列積の計算
行列の転置+ブロッキング
2005/7/29
11 / 48
キャッシュの有効活用
ソフトウェアレベルでの工夫


キャッシュを意識したプログラミングは重要
ソフトウェアの構築コスト大
 プログラムごと、計算機ごとに検討

キャッシュサイズが異なれば、最適なブロッキングのサイズも異なる
 ボトルネックの解析

プロファイラ (gprof, VTune)
 コンパイラの最適化機能

数値計算ライブラリ
 プロセッサ、キャッシュに対して最適化
 Intel Math Kernel Library, AMD Core Math Library
 ATLAS, FFTE, FFTW
2005/7/29
12 / 48
キャッシュヒント
13 / 48
キャッシュヒント
キャッシュ有効活用のための一機能
キャッシュの制御をソフトウェアレベルで実現す
るための仕組み
⇔ 従来はハードウェアレベルでの制御
「どのキャッシュ階層」に「どのようにデータを配置」するか
 取り込むキャッシュ階層
 LRU bit の更新

メモリアクセス命令単位で適用可能
 データの局所性を意識したキャッシュの有効活用
 多段キャッシュの有効活用

プログラムの振る舞いには影響を与えない
2005/7/29
14 / 48
キャッシュヒントの振る舞い
通常のストア命令によるキャッシュの変化
.nta ヒントを付加したストア命令によるキャッシュの変化
cf. ストリーミングストア (Pentium3~)
2005/7/29
15 / 48
Itanium プロセッサのキャッシュヒント
Itanium プロセッサのキャッシュヒント

全部で４種類
 .t1, .nt1, .nt2, .nta

通常のメモリアクセス命令にヒントを付加する形で実現
 Itanium 命令のコンプリケータ
 ストア命令、ロード命令、プリフェッチ命令
例） st8 → st8.nta, ld4 → ld4.nt1, lfetch → lfetch.nt2
cf. Pentium 系プロセッサのキャッシュヒント

プリフェッチ命令のみヒントを指定できる（異なる命令）
 prefetcht0, prefetcht1, prefetcht2, prefetchnta
2005/7/29
16 / 48
キャッシュヒントの種類と振る舞い
インテル® Itanium®2
プロセッサリファレン
ス・マニュアルより引
用
2005/7/29
17 / 48
.nta ヒント
.nta ヒント
(Non-Temporal locality in All levels)
 データを L2 キャッシュにのみ配置
 キャッシュの LRU bit を更新しない
⇒ データをキャッシュ内に最も残さないヒント
.nta ヒントの有用性
１度使うだけで再利用のないメモリアクセスをキャッ
シュに残さない
 他の再利用される（かもしれない）データがキャッシュ
から追い出されにくくなる
⇒ キャッシュヒット率の向上

2005/7/29
18 / 48
.nta ヒントの振る舞い
通常のストア命令によるキャッシュの変化
.nta ヒントを付加したストア命令によるキャッシュの変化
cf. ストリーミングストア (Pentium3~)
2005/7/29
19 / 48
キャッシュヒントとコンパイラ
現状
既存のコンパイラはキャッシュヒント
を使用したコードを生成しない！
Intel Compiler
 GCC
で確認

2005/7/29
20 / 48
キャッシュヒントとコンパイラ
コンパイラがキャッシュヒントを使用しない理由？

性能低下の可能性
 キャッシュヒントの選択次第では、本来キャッシュに残ってい
て欲しいデータを残さないようにすることもできる
→ キャッシュヒット率低下の可能性
 触らぬ神に祟りなし
 ハードウェアのキャッシュ制御に任せる


ヒントの選択が難しい？
命令スケジューリング≫キャッシュヒント？
 Itanium では命令スケジューリングが性能を最も左右
2005/7/29
21 / 48
キャッシュヒントとコンパイラ
それでもキャッシュヒントを使いたい

ハードウェアに実装されている機能を使い切っていな
いのは勿体無い（←貧乏性？）
 キャッシュヒントを使用する方法があってもいいのでは？

キャッシュヒントの付加についての先行研究
 Beyls (Gent Univ) らの研究



K.Beyls and E.D'Hollander. Compile-Time Cache Hint Generation for EPIC
Architectures, In Proc. EPIC2, pp.19--29, Nov 2002.
Reuse Distance という尺度に基づいてキャッシュヒントを選択
することで、ソフトウェアの性能が向上する場合がある
Open Research Compiler 上に実装・・・
2005/7/29
22 / 48
キャッシュヒントとコンパイラ
既存のコンパイラにキャッシュヒント付加機能を
付加できないだろうか？

キャッシュヒント自動付加手法へ
2005/7/29
23 / 48
キャッシュヒントの自動付加手法
24 / 48
キャッシュヒントの自動付加手法
Source Program
(C, C++, Fortran, etc…)
Binary Program
Compiler/Assembler/Linker
Assembly Program
Assembly Program
（annotated Cachehint）
Cachehint Annotation Unit
(CHSU-core)
・・・
CacheHint Supply Utility
(CHSU)
従来のコード生成
・・・提案する手法
2005/7/29
25 / 48
本手法の特徴
1. プログラミング言語に依存しない


アセンブリプログラムを生成できるコンパイラがあれば、本手法
は適用可能
使用するコンパイラも選択可能
2. 自動実行


既存のコンパイラのラッパーとして動作
$ icc –O3 –o foo foo.c
Intel Compiler の場合
$ chsu –O3 –o foo foo.c
本手法の場合
既存のコンパイラの最適化機能を活かした上で、キャッシュヒン
トを付加
2005/7/29
26 / 48
CHSUの設計・実装
Java で実装


Source Program
フロントエンド
CHSU-core
Compiler/Assembler/Linker
Assembly Program
フロントエンド

コマンドラインの解析
 ファイル、オプション

Binary Program
Assembly Program
（annotated Cachehint）
Cachehint Annotation Unit
(CHSU-core)
設定ファイルの解析
 プログラミング言語（拡張子）と使用するコンパイラ、アセンブ
ラの関連付け


コンパイラ、アセンブラを外部プロセスとして起動
アセンブリプログラムを CHSU-core に渡す
2005/7/29
27 / 48
CHSUの設計・実装
CHSU-core
Source Program
アセンブリプログラムの
解析
 キャッシュヒントの付加
 キャッシュヒント付加済
プログラムの出力
Binary Program

Compiler/Assembler/Linker
Assembly Program

字句解析
アセンブリプログラムの構造を抽出
2005/7/29
28 / 48
（annotated Cachehint）
Cachehint Annotation Unit
アセンブリプログラムの解析

Assembly Program
(CHSU-core)
アセンブリプログラムの解析
３種類のデータ構造

Program
 プログラム

Procedure
Block
Procedure
Block
Block
 アセンブリプログラム中のラベルで
区切られる部分 (Procedure内)
 ディレクティブ等、解析上関係ない
部分 (Procedure外)

Program
Block
 プロシージャ（関数）

Block
Procedure 外の Block は以降の
解析では無視する
2005/7/29
29 / 48
Block
Block
Block
Block
Block
Procedure
アセンブリプログラムの解析
Block の区切り方

.....
nop.i 0 ;;
ラベルを基準に区切る
Block が保持する情報




アセンブリプログラム原文
Block のラベル名
命令の種類・数
分岐命令の分岐先
 br.call, br.ret 以外

実行サイクル数
 命令、ストップの数で判断
}
label_a:
{ .mmi
(p17) add r35=0x100, r0
(p17) add r32=-1,r33
(p17) add r39=65474,r0
}
.....
.....
.....
{ .bbb
(p7) br.cond.dptk.many label_i
(p9) br.cond.dptk label_j
br.cond.sptk label_k
}
label_b:
{ .mmi
.....
2005/7/29
30 / 48
キャッシュヒントの付加方針
.nta ヒント・・・１度使うだけで再利用しないメモリアクセスに有効

再利用しない（再利用しなそうな）メモリアクセス命令をアセンブリ
プログラム中から発見して、ヒントを付加すればよい
本研究での方針・・・プログラムの局所性に注目


（数値計算を含む）多くのソフトウェアは、データのストア・ロード
のほとんどを for ループなどの局所性が高い部分で実行
メモリアクセスの振る舞いを仮定
 キャッシュヒント付加の基準に
for(i=0; i<L; i++){
z[i] = x[i] * y[i];
}
store
2005/7/29
31 / 48
load
load
キャッシュヒントの付加方針
局所性の高い部分のメモリアクセス命令

ストア命令
 同じメモリアドレスにデータを何度もストアすることはない
⇒再利用しないメモリアクセス命令と仮定

ロード命令
 同じメモリアドレスからデータを何度もロードすることはない
 しかし、同じキャッシュライン上にある別のメモリアドレスから
データがロードされる可能性はある
⇒キャッシュラインが再利用される
⇒再利用されるメモリアクセス命令と仮定
for(i=0; i<L; i++){
z[i] = x[i] * y[i];
}
store
2005/7/29
32 / 48
load
load
キャッシュヒントの付加方針
局所性の低い部分のメモリアクセス命令
他の部分に比べて実行回数が相対的に少ない

⇒再利用しないメモリアクセス命令と仮定
プログラムの局所性と.nta ヒント付加の関係
局所性の高い部分
局所性の低い部分
ストア命令
○
○
ロード命令
×
○

どちらにも該当しなければ、ヒントは付加しない
2005/7/29
33 / 48
キャッシュヒント付加の実装
アセンブリプログラムの解析


Procedure 単位で処理
Block が保持している情報を利用
 分岐命令の分岐先
① プログラムのループ構造

自Blockへの分岐を持つ Block
 ループ構造そのもの
 for文, while文がアセンブリプログラムに
なった形であると考えられる

Block の局所性が高いと判断
→ ストア命令に .nta ヒントを付加する
2005/7/29
34 / 48
label_a:
…
br label_p
…
label_b:
…
br label_b
キャッシュヒント付加の実装
② リターン命令



プロシージャ・リターン命令(br.ret) を持つ
Block は Procedure 内で最後に実行される
繰り返し実行される可能性は少ない
Block の局所性が低いと判断
→ ストア命令・ロード命令に
.nta ヒントを付加する
2005/7/29
35 / 48
label_q:
…
br.ret
label_r:
…
キャッシュヒント付加の実装
キャッシュヒントの付加


Block が保持しているプログラム原文を書き換える
対象となるメモリアクセス命令の語尾に .nta を付加
{
.mmi
(p16) lfetch.nt1
(p18) stfd.nta
stfd
(p16) add
}
{
.mmi
(p18) stfd.nta
stfd
(p18) stfd.nta
stfd
(p16) add
}
[r34]
[r9]=f61,64
r45=64,r46;;
[r8]=f68,64
[r3]=f60,64
r32=128,r34
2005/7/29
36 / 48
label_b:
…
br label_b
評価
37 / 48
評価環境・内容
評価環境 – SGI Altix 350

Itanium2 1.4GHz
 L1D:16KB, L2:256KB, L3:3MB

使用コンパイラ
 Intel Compiler 8.1, GCC 3.2.3
数値計算ソフトウェアにキャッシュヒント付加を適用

FFTE 4.0
 FFT ライブラリ、キャッシュ内での高速な動作

行列積計算
 ATLAS 3.6.0
 手書きの行列積計算

NPB 3.2
 NAS Parallel Benchmark
2005/7/29
38 / 48
評価(1) – FFTE 4.0
1次元FFT
データサイズを変化させて性能を測定

キャッシュヒントの有無による性能を比較
ストア命令にのみ, ロード命令にのみ, 両方

15%性能向上
120
性能向上率 (%)
115
110
105
100
95
90
14
15
16
17
18
19
20
FFT データ数 (2^m)
Itanium2 L3上限
Store Hint
Load Hint
2005/7/29
39 / 48
Store & Load Hint
21
22
23
評価(1) – FFTE 4.0
N=217
Original
w/Cache Hint
L2 cache hit
0.981
0.982
L3 cache hit
0.401
0.551
IPC
1.703
1.754
Total stalls
0.625
0.605
プロセッサイベントの計測

15%
perfmon
結果から

L3 キャッシュヒット率の向上
N=217の場合で15%

N=220
Original
w/Cache Hint
L2 cache hit
0.979
0.979
L3 cache hit
0.331
0.337
IPC
1.541
1.570
Total stalls
0.668
0.662
2005/7/29
40 / 48

IPC の向上
Total stalls の減少
評価(1) – FFTE 4.0
m≧17 以降、性能は向上しているが、その向上率は小さくなっている
FFTE 内で使用する全データサイズに対する L3 キャッシュの割合が小
さくなっていくため、.nta ヒント付加の効果の割合も小さくなっている

120
性能向上率 (%)
115
110
105
100
95
90
14
15
16
17
18
19
20
FFT データ数 (2^m)
Itanium2 L3上限
Store Hint
Load Hint
2005/7/29
41 / 48
Store & Load Hint
21
22
23
評価(2) – 行列積計算
ATLAS 3.6.0

自動チューニング機構を持つ数値計算ライブラリ
MFLOP ベースで
1%~2% の性能向
上
2005/7/29
42 / 48
評価(2) – 行列積計算
手書きの行列積計算
Q: キャッシュを有効に使っていない、効率の悪いプログラムに対し
てもキャッシュヒント付加は有効か?
2005/7/29
43 / 48
評価(3) – NPB 3.2
NAS Parallel Benchmark


並列計算機用のベンチマーク集
今回使用したのは逐次実行版(NPB-SER)
性能向上率(%)
120
110
100
90
80
70
EP
MG
CG
FT
Class W
2005/7/29
44 / 48
IS
Class A
LU
SP
BT
評価(3) – NPB 3.2
CG
Original
w/Cache Hint
L2 cache hit
0.957
0.957
L3 cache hit
0.044
0.047
IPC
0.779
0.616
Total stalls
0.857
0.886
Original
w/Cache Hint
L2 cache hit
0.958
0.968
L3 cache hit
0.338
0.332
IPC
0.865
0.886
Total stalls
0.735
0.727
(Class W)
IS
(Class W)
2005/7/29
45 / 48
プロセッサイベントの計測
キャッシュヒント付加に関する考察
現在のキャッシュヒント付加方針

性能が上がるもの、下がるもの共に存在
 よくチューニングされているプログラムの方が、性能が向上し
ている傾向がある

今後、キャッシュヒント付加方針の種類を増やしたい
.nta ヒントの付加による性能向上


L3 キャッシュのヒット率向上
プロセッサに載る L3 キャッシュは増量傾向
⇒ ヒット率の向上は有効！
2005/7/29
46 / 48
まとめ
以下の内容について紹介した



キャッシュの有効活用
Itanium プロセッサのキャッシュヒント
キャッシュヒントの自動付加手法、CHSU
 自動実行、汎用性の高い手法

キャッシュヒント付加時の性能評価
 FFT で最高15%の性能向上
 .nta ヒントの付加による L3 キャッシュのヒット率向上
2005/7/29
47 / 48
まとめ
CHSUの今後



キャッシュヒント付加方針の検討・充実
性能評価の充実
バイナリプログラムへの適用
 逆アセンブルなどを行えば可能？
CHSU の実装
http://www.ueda.info.waseda.ac.jp/~inagaki/chsu/
で、近日公開（予定）

2005/7/29
48 / 48

Download Report