キャッシュヒントの自動付加による数値計算の高速化 早稲田大学 理工学研究科 情報・ネットワーク専攻 稲垣 良一 <inagaki@ueda.info.waseda.ac.jp> 1 / 48

概要 プロセッサの性能を最大限に活かしたソフトウェアを作成するためには、キャッシュの有効活用が不可欠である．Itanium プロセッサに搭載されているキャッシュヒント機能は、適切に使用することでキャッシュ有効活用への期待が持てるが，既存のコンパイラはキャッシュヒントを使用したプログラムを生成しない． 本発表では Itanium プロセッサのキャッシュヒントを紹介し，既存のコンパイラを使用してキャッシュヒントを自動的に付加する手法について述べる．また，FFT などの数値計算に対してキャッシュヒントを付加した場合の性能評価についても紹介する． 2005/7/29 2 / 48

背景 – ハードウェアの性能向上 計算機の性能は向上を続けている しかし、プロセッサとメモリの速度差は拡大 プロセッサ周波数、メモリ帯域、etc ・・・ しかし、プロセッサとメモリの速度差は拡大 ２年で２倍のペース メモリアクセスコストは相対的に増加 プロセッサの性能を活かしたソフトウェアの構築 プロセッサとメモリの速度差・・・二年で二倍？ このときプロセッサの処理速度とメモリのアクセス速度に差がある場合には、 全体の速度は低速な側のデバイスに支配されてしまう。 メモリアクセスコストいかに抑えるか キャッシュをいかに有効に活用できるか メモリアクセス遅延の隠蔽 キャッシュの有効活用 一般的な対処方法 メモリアクセスコストの 相対的な増加 2005/7/29 3 / 48

目次 背景 キャッシュの有効活用 Itanium プロセッサのキャッシュヒント キャッシュヒントの自動付加手法 キャッシュヒント付加時の性能評価 2005/7/29 4 / 48

キャッシュ Itanium2 Processor 1.4GHz の場合 Main Memory fast slow Latency: 100~ cycle L3: 3 MB Line Size: 128 Byte Latency: 12~13 cycle L2: 256 KB Line Size: 128 Byte Latency: 5~6 cycle キャッシュ階層間帯域:32GB/s キャッシュ・メモリ間帯域:6.4GB/s L1D: 16 KB Line Size: 64 Byte Latency: 1 cycle 2005/7/29 5 / 48

例：行列積の計算 Z=X*Y ＝ × Z X Y 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 L N L M M N 配列の一要素を計算するために行列yのすべての範囲にアクセス ＝ × Z X Y 2005/7/29 6 / 48

例：行列積の計算 特に工夫しないプログラムの性能 行列サイズが 512 以上で性能が急落する 特定の行列サイズでも性能が低下 2005/7/29 7 / 48

メモリアクセスコストを抑える具体的手法 Itanium プロセッサの機能 ソフトウェアレベルでの工夫 キャッシュの有効活用 キャッシュヒント メモリアクセス遅延の隠蔽 命令スケジューリング アドバンスト・ロード プリフェッチ（ハードウェア） ソフトウェアレベルでの工夫 データレイアウトの改善 データの再配置 配列に対するブロッキング、パディング 計算順序の変更 ループ変換、結合 プリフェッチ（ソフトウェア） 後述 コンパイラががんばる プログラマががんばる コンパイラもがんばる 計算順序の変更・・・プログラムの局所性を引き出す 2005/7/29 8 / 48

例：行列積の計算 データレイアウトの改善 行列の転置 行列のブロッキング ＝ × ＝ × Y（転置） L N L M N M 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 の更新 メモリアクセス命令単位で適用可能 データの局所性を意識したキャッシュの有効活用 多段キャッシュの有効活用 プログラムの振る舞いには影響を与えない 「どのキャッシュ階層」に「どのようにデータを配置」するか ソフトウェア、つまりプログラムでレベルで実現するための仕組み ⇔ RISC系アーキテクチャはハードウェアレベル 2005/7/29 14 / 48

キャッシュヒントの振る舞い 通常のストア命令によるキャッシュの変化 .nta ヒントを付加したストア命令によるキャッシュの変化 cf. ストリーミングストア (Pentium3~) 2005/7/29 15 / 48

Itanium プロセッサのキャッシュヒント 全部で４種類 .t1, .nt1, .nt2, .nta 通常のメモリアクセス命令にヒントを付加する形で実現 Itanium 命令のコンプリケータ ストア命令、ロード命令、プリフェッチ命令 cf. Pentium 系プロセッサのキャッシュヒント プリフェッチ命令のみヒントを指定できる（異なる命令） prefetcht0, prefetcht1, prefetcht2, prefetchnta 例） st8 → st8.nta, ld4 → ld4.nt1, lfetch → lfetch.nt2 2005/7/29 16 / 48

キャッシュヒントの種類と振る舞い インテル® Itanium®2 プロセッサ リファレンス・マニュアル より引用 2005/7/29 （ここは軽く流す） インテル® Itanium®2 プロセッサ リファレンス・マニュアル より引用 2005/7/29 17 / 48

.nta ヒント .nta ヒント (Non-Temporal locality in All levels) .nta ヒントの有用性 キャッシュの 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

キャッシュヒントの自動付加手法 Binary Program Compiler/Assembler/Linker Assembly Program （annotated Cachehint） Cachehint Annotation Unit (CHSU-core) Compiler/Assembler/Linker CacheHint Supply Utility (CHSU) Source Program (C, C++, Fortran, etc…) Binary Program ・・・ 従来のコード生成 ・・・ 提案する手法 2005/7/29 25 / 48

本手法の特徴 プログラミング言語に依存しない 自動実行 アセンブリプログラムを生成できるコンパイラがあれば、本手法は適用可能 使用するコンパイラも選択可能 自動実行 既存のコンパイラのラッパーとして動作 既存のコンパイラの最適化機能を活かした上で、キャッシュヒントを付加 $ icc –O3 –o foo foo.c Intel Compiler の場合 コンパイラの使用者側からみて透過的に動作する $ chsu –O3 –o foo foo.c 本手法の場合 2005/7/29 26 / 48

CHSUの設計・実装 Java で実装 フロントエンド CHSU-core コマンドラインの解析 設定ファイルの解析 ファイル、オプション 設定ファイルの解析 プログラミング言語（拡張子）と使用するコンパイラ、アセンブラの関連付け コンパイラ、アセンブラを外部プロセスとして起動 アセンブリプログラムを CHSU-core に渡す Assembly Program （annotated Cachehint） Cachehint Annotation Unit (CHSU-core) Compiler/Assembler/Linker Source Program Binary Program 2005/7/29 27 / 48

CHSUの設計・実装 CHSU-core アセンブリプログラムの解析 アセンブリプログラムの 解析 キャッシュヒントの付加 　解析 キャッシュヒントの付加 キャッシュヒント付加済 　プログラムの出力 アセンブリプログラムの解析 字句解析 アセンブリプログラムの構造を抽出 Assembly Program （annotated Cachehint） Cachehint Annotation Unit (CHSU-core) Compiler/Assembler/Linker Source Program Binary Program 2005/7/29 28 / 48

アセンブリプログラムの解析 ３種類のデータ構造 Program Procedure Block プロシージャ（関数） Block アセンブリプログラム中のラベルで区切られる部分 (Procedure内) ディレクティブ等、解析上関係ない部分 (Procedure外) Procedure 外の Block は以降の解析では無視する Program Procedure Block 2005/7/29 29 / 48

アセンブリプログラムの解析 Block の区切り方 Block が保持する情報 ラベルを基準に区切る アセンブリプログラム原文 命令の種類・数 分岐命令の分岐先 br.call, br.ret 以外 実行サイクル数 命令、ストップの数で判断 ..... nop.i 0 ;; } 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: 分岐命令の分岐先・・・プロシージャ内のフロー解析に使用することができる 2005/7/29 30 / 48

キャッシュヒントの付加方針 本研究での方針・・・プログラムの局所性に注目 再利用しない（再利用しなそうな）メモリアクセス命令をアセンブリプログラム中から発見して、ヒントを付加すればよい 本研究での方針・・・プログラムの局所性に注目 （数値計算を含む）多くのソフトウェアは、データのストア・ロードのほとんどを for ループなどの局所性が高い部分で実行 メモリアクセスの振る舞いを仮定 キャッシュヒント付加の基準に .nta ヒント・・・１度使うだけで再利用しないメモリアクセスに有効 性能を左右させるという意味で最も重要な部分 性能が必ず向上する、という方針はない？ for(i=0; i<L; i++){ z[i] = x[i] * y[i]; } store load 2005/7/29 31 / 48

キャッシュヒントの付加方針 局所性の高い部分のメモリアクセス命令 ストア命令 ロード命令 同じメモリアドレスにデータを何度もストアすることはない ⇒再利用しないメモリアクセス命令と仮定 ロード命令 同じメモリアドレスからデータを何度もロードすることはない しかし、同じキャッシュライン上にある別のメモリアドレスからデータがロードされる可能性はある ⇒キャッシュラインが再利用される ⇒再利用されるメモリアクセス命令と仮定 for(i=0; i<L; i++){ z[i] = x[i] * y[i]; } store load 2005/7/29 32 / 48

キャッシュヒントの付加方針 局所性の低い部分のメモリアクセス命令 プログラムの局所性と.nta ヒント付加の関係 他の部分に比べて実行回数が相対的に少ない ⇒再利用しないメモリアクセス命令と仮定 プログラムの局所性と.nta ヒント付加の関係 どちらにも該当しなければ、ヒントは付加しない 局所性の高い部分 局所性の低い部分 ストア命令 ○ ロード命令 × ストア命令は再利用の可能性が低い ⇒ .nta 付加 ○ ロード命令は再利用の可能性が高い ⇒ .nta 付加 × 2005/7/29 33 / 48

キャッシュヒント付加の実装 アセンブリプログラムの解析 ① プログラムのループ構造 Procedure 単位で処理 Block が保持している情報を利用 分岐命令の分岐先 ① プログラムのループ構造 自Blockへの分岐を持つ Block ループ構造そのもの for文, while文がアセンブリプログラムになった形であると考えられる Block の局所性が高いと判断 → ストア命令に .nta ヒントを付加する label_b: … br　label_b label_a: br label_p 2005/7/29 34 / 48

キャッシュヒント付加の実装 ② リターン命令 プロシージャ・リターン命令(br.ret) を持つ Block は Procedure 内で最後に実行される 繰り返し実行される可能性は少ない Block の局所性が低いと判断 → ストア命令・ロード命令に .nta ヒントを付加する label_q: … br.ret label_r: … 2005/7/29 35 / 48

キャッシュヒント付加の実装 キャッシュヒントの付加 Block が保持しているプログラム原文を書き換える 対象となるメモリアクセス命令の語尾に .nta を付加 　{ .mmi (p16) lfetch.nt1 [r34] (p18) stfd.nta [r9]=f61,64 (p16) add r45=64,r46;; } { .mmi (p18) stfd.nta [r8]=f68,64 (p18) stfd.nta [r3]=f60,64 (p16) add r32=128,r34 　{ .mmi (p16) lfetch.nt1 [r34] (p18) stfd [r9]=f61,64 (p16) add r45=64,r46;; } { .mmi (p18) stfd [r8]=f68,64 (p18) stfd [r3]=f60,64 (p16) add r32=128,r34 label_b: … br　label_b なんかよくわからない表現になっている・・・ 2005/7/29 36 / 48

評価 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 Itanium アーキテクチャでは Intel Compiler の方が GCC 3.2.3 より2倍以上高速 2005/7/29 38 / 48

評価(1) – FFTE 4.0 15%性能向上 1次元FFT キャッシュヒントの有無による性能を比較 データサイズを変化させて性能を測定 ストア命令にのみ, ロード命令にのみ, 両方 15%性能向上 Itanium2 L3上限 2005/7/29 39 / 48

評価(1) – FFTE 4.0 プロセッサイベントの計測 結果から 0.981 0.982 0.401 0.551 1.703 1.754 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 プロセッサイベントの計測 perfmon 結果から L3 キャッシュヒット率の向上 N=217の場合で15% IPC の向上 Total stalls の減少 15% N=220 Original w/Cache Hint L2 cache hit 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

評価(1) – FFTE 4.0 m≧17 以降、性能は向上しているが、その向上率は小さくなっている FFTE 内で使用する全データサイズに対する L3 キャッシュの割合が小さくなっていくため、.nta ヒント付加の効果の割合も小さくなっている この点からも .nta ヒントの付加はL3キャッシュのヒット率に影響を与えていると考えられる Itanium2 L3上限 2005/7/29 41 / 48

評価(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) EP 乗算合同法による一様乱数、正規乱数の生成 MG 簡略化されたマルチグリッド法のカーネル CG 正値対称な大規模疎行列の最小固有値を求めるための共役勾配法 FT FFTを用いた３次元偏微分方程式の解法 IS 大規模整数ソート Simulated CFD Application Benchmarks LU Synmetric SOR iterationによるCFDアプリケーショ SP Scalar ADI iterationによるCFDアプリケーション BT 5x5 block size ADI iterationによるCFDアプリケーション 2005/7/29 44 / 48

評価(3) – NPB 3.2 プロセッサイベントの計測 0.957 0.044 0.047 0.779 0.616 0.857 0.886 CG (Class W) Original w/Cache Hint L2 cache hit 0.957 L3 cache hit 0.044 0.047 IPC 0.779 0.616 Total stalls 0.857 0.886 プロセッサイベントの計測 IS (Class W) 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 2005/7/29 45 / 48

キャッシュヒント付加に関する考察 現在のキャッシュヒント付加方針 .nta ヒントの付加による性能向上 性能が上がるもの、下がるもの共に存在 よくチューニングされているプログラムの方が、性能が向上している傾向がある 今後、キャッシュヒント付加方針の種類を増やしたい .nta ヒントの付加による性能向上 L3 キャッシュのヒット率向上 プロセッサに載る L3 キャッシュは増量傾向 ⇒ ヒット率の向上は有効！ あるソフトウェアに対しては×でも別のソフトウェアに対しては○かもしれない 2005/7/29 46 / 48

まとめ 以下の内容について紹介した キャッシュの有効活用 Itanium プロセッサのキャッシュヒント キャッシュヒントの自動付加手法、CHSU 自動実行、汎用性の高い手法 キャッシュヒント付加時の性能評価 FFT で最高15%の性能向上 .nta ヒントの付加による L3 キャッシュのヒット率向上 2005/7/29 47 / 48

まとめ CHSUの今後 キャッシュヒント付加方針の検討・充実 性能評価の充実 バイナリプログラムへの適用 CHSU の実装 逆アセンブルなどを行えば可能？ CHSU の実装 http://www.ueda.info.waseda.ac.jp/~inagaki/chsu/ で、近日公開（予定） 2005/7/29 48 / 48