キャッシュヒント自動付加を用いたソフトウェア高速化 早稲田大学 理工学研究科 情報・ネットワーク専攻 稲垣 良一 上田 和紀 FIT2005

研究の背景と目的 プロセッサとメモリの速度差の拡大 キャッシュヒント (Itanium) 研究の目的 適切に使用することでキャッシュの有効活用 既存のコンパイラはキャッシュヒントを使用したメモリアクセス命令を生成しない 研究の目的 ①コンパイル時のキャッシュヒント自動付加 ②キャッシュヒント付加によるソフトウェア高速化 メモリアクセスコストの 相対的な増加 メモリアクセス遅延の隠蔽 キャッシュの有効活用 一般的な対処方法 FIT2005

発表の流れ 背景と目的 キャッシュヒント キャッシュヒント自動付加手法 - CHSU 評価・まとめ FIT2005

キャッシュヒント データを配置するキャッシュ階層を制御 Itanium プロセッサのキャッシュヒント 取り込むキャッシュ階層、 LRU の更新、etc… データの局所性を意識したキャッシュの有効活用 Itanium プロセッサのキャッシュヒント メモリアクセス命令にヒントを付加する形式で表現 ストア・ロード命令に応じて4種類 .nta ヒント データをキャッシュに最も残さないヒント データを L2 キャッシュだけに配置 LRU を更新しない ⇒一度使うだけで再利用しないメモリアクセスに有効 例） ld4.nt1, st8.nta 多段キャッシュの有効活用 データの局所性を意識したキャッシュの有効活用 FIT2005

キャッシュヒント 通常のストア命令によるキャッシュの変化 .nta ヒントを付加したストア命令によるキャッシュの変化 cf. ストリーミングストア (Pentium3~) FIT2005

キャッシュヒントとコンパイラ 現状 関連研究 既存のコンパイラはキャッシュヒントを使用したコードを生成していない！ GCC, Intel Compiler #pragma memref_control (Intel Compiler 9 ～) 関連研究 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 既存のコンパイラはキャッシュヒントを使用したコードを生成していない！ FIT2005

背景と目的 キャッシュヒント キャッシュヒント自動付加手法 - CHSU 評価・まとめ FIT2005

キャッシュヒントの自動付加手法 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 FIT2005

本手法の特徴 プログラミング言語に依存しない 透過性 ヒントの自動付加 アセンブリプログラムを生成できるコンパイラが必要 使用するコンパイラも選択可能 透過性 既存のコンパイラのラッパーとして動作 既存のコンパイラの最適化機能 + キャッシュヒント付加 ヒントの自動付加 ヒントを付加すべきメモリアクセス命令を自動的に選択 $ icc –O3 –o foo foo.c Intel Compiler の場合 $ chsu –O3 –o foo foo.c 本手法の場合 コンパイラの使用者側からみて透過的に動作する FIT2005

CHSUの設計・実装 Java で実装 フロントエンド CHSU-core コマンドラインの解析 設定ファイルの解析 コンパイラ、アセンブラの起動 アセンブリプログラムを CHSU-core に渡す Assembly Program （annotated Cachehint） Cachehint Annotation Unit (CHSU-core) Compiler/Assembler/Linker Source Program Binary Program FIT2005

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

アセンブリプログラムの解析 3階層のデータ構造に分類 Program - プログラム Procedure - プロシージャ Block – アセンブリプログラム中のラベルで区切られる部分 以降の解析は Procedure 単位で行う Program Procedure Block Block 単位で保持する情報 　プログラム原文、命令の種類・数、 　分岐先、etc… FIT2005

キャッシュヒントの付加方針 本研究では .nta ヒントを付加 方針・・・プログラムの局所性に注目 多くのメモリアクセスがループ等の局所性の高い部分で実行されている .nta ヒント・・・１度使うだけで再利用しないメモリアクセスに有効 それぞれの部分について、メモリアクセスの再利用性を仮定し、ヒントの付加方針を導く 1.局所性が高い部分 2.局所性が低い部分 3.（どちらでもない部分） FIT2005

キャッシュヒントの付加方針 (cont’d) 局所性に応じた仮定 局所性が高い部分について 局所性が低い部分について 実行回数が他の部分に比べて相対的に少ない ⇒再利用しないメモリアクセスであると仮定 ストア命令 同じメモリアドレスにデータを何度もストアすることはない ⇒再利用しないメモリアクセスと仮定 ロード命令 同じデータを何度もロードすることはないが、同じキャッシュライン上の別のメモリアドレスからデータがロードされる可能性はある ⇒キャッシュラインは再利用される ⇒再利用されるメモリアクセスと仮定 FIT2005

キャッシュヒントの付加方針 (cont’d) プログラムの局所性と.nta ヒント付加の関係 どちらにも該当しなければ、ヒントは付加しない この方針に基づいてアセンブリプログラムから 局所性が高い部分 局所性が低い部分 　を見つける 局所性の高い部分 局所性の低い部分 それ以外 ストア命令 ○ × ロード命令 FIT2005

.nta ヒントの付加 Procedure 単位で処理 局所性の高い部分 局所性の低い部分 Block 単位で CFG を構築 自Blockへの分岐を持つBlock ループ構造そのもの Block の局所性が高いと判断 → ストア命令に .nta ヒントを付加 局所性の低い部分 実行回数が少ない Block CFG から判断 Block の局所性が低いと判断 → ストア・ロード命令に .nta ヒントを付加 label_b: … br　label_b label_a: br label_p label_q: … br.ret label_r: for文, while文がアセンブリプログラムになった形であると考えられる FIT2005

背景と目的 キャッシュヒント キャッシュヒント自動付加手法 - CHSU 評価・まとめ FIT2005

評価 評価環境 – SGI Altix 350 CHSU を使用してキャッシュヒントを付加、性能比較 Itanium2 1.4GHz L1D:16KB, L2:256KB, L3:3MB 使用コンパイラ Intel Compiler 8.1, GCC 3.2.3 CHSU を使用してキャッシュヒントを付加、性能比較 FFTE 4.0 FFT ライブラリ、キャッシュ内での高速な動作 ATLAS 3.6.0 自動チューニング機構を持つ数値計算ライブラリ NAS Parallel Benchmark 並列計算機用のベンチマーク集 Itanium アーキテクチャでは Intel Compiler の方が GCC 3.2.3 より2倍以上高速 数値計算ソフトウェアにキャッシュヒント付加を適用 FFTE 4.0 FFT ライブラリ、キャッシュ内での高速な動作 行列積計算 ATLAS 3.6.0 NPB 3.2 NAS Parallel Benchmark FIT2005

評価(1) – FFTE 4.0 1次元FFT キャッシュヒントの有無による性能を比較 15%性能向上 データサイズを変化させて性能を測定 Itanium2 L3上限 FIT2005

評価(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 FIT2005

評価(2) – ATLAS 3.6.0 行列積計算 データサイズを変化させて性能を測定 MFLOP ベースで 1%~2% の性能向上 FIT2005

評価(3) – NPB 3.2 NAS Parallel Benchmark 3.2 今回使用したのは逐次実行版 (NPB-SER) Class W, Class A の二種類について評価 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アプリケーション FIT2005

まとめ 既存のコンパイラを使用して、コンパイル時にキャッシュヒントを付加する手法を提案した 今後の課題 高い汎用性 L3 キャッシュのヒット率向上 → 全体性能向上 今後の課題 性能評価の充実 キャッシュヒント付加方針の検討 バイナリプログラムに対するキャッシュヒント付加 CHSU 公開中 http://www.ueda.info.waseda.ac.jp/~inagaki/chsu/ FIT2005