情報理工学系研究科 電子情報学専攻 46424 豊島隆志 レジスタ間接分岐の高速化手法 情報理工学系研究科 電子情報学専攻 46424 豊島隆志

発表の流れ 背景 分岐予測 アウト・オブ・オーダ実行 関連研究 提案手法 レジスタ間接分岐ターゲット・フォワーディング 評価 まとめ

オブジェクト指向による大規模アプリケーションの増加 概要 オブジェクト指向による大規模アプリケーションの増加 仮想関数の利用 レジスタ間接分岐の増加 既存の履歴を利用した分岐予測では分岐先を予測できない 分岐前後でアウト・オブ・オーダ実行では隠蔽できない遅延が発生 性能の低下

既存の分岐予測手法 分岐方向予測 … 問題なし 分岐ターゲット予測 … 問題あり 分岐命令後の命令フェッチアドレスを予測する BTB (Branch Target Buffer) の利用 過去の分岐ターゲットを記録したバッファ 通常は分岐命令のPCをキーにしてバッファを検索 各分岐命令に対して高々１エントリ 分岐ターゲットが複数存在するレジスタ間接分岐には未対応 cf.) 間接分岐予測器（Pentium M，他） PCと分岐履歴の組み合わせを用いてBTBを検索 各分岐に対して複数のエントリを保持できる 分岐ターゲットが分岐履歴に依存している必要がある

仮想関数と分岐履歴 一般的に分岐ターゲットは分岐履歴に依らない drawableのクラスのみが実際の分岐ターゲットに影響する 既存の分岐予測は当たらない class Drawable { virtual void Draw(void) = NULL; … }; class Circle : public Drawable { class Square : public Drawable { void DrawObjects(void) { Drawable *drawable = bottomObject; for (; NULL != drawable; drawable = drawable->Next()) { drawable->Draw(); }

パイプライン処理 cycle Fetch Decode Execute Memory Write Back i0 i1 i2 i3 i4

Branch target prediction パイプライン処理と分岐予測 Branch check & Branch target prediction cycle branch Validation Fetch Decode Execute Memory Write Back i0 Fetch Decode Execute Memory i1 i2 i3 i4 Write Back

仮想関数の呼び出し手順 Load $2 = [$1 + 0] Load $3 = [$2 + 0] Call $3 Circle Virtual Function Table (this) void Circle::Draw(void) { … } vtable ptr void (*Draw(void)) var foo ・ var bar ・

アウト・オブ・オーダ実行による遅延の隠蔽 パイプラインを複数用意して実行可能な命令から並列実行 依存のない，もしくは解消した命令 必要とするハードウェアが割り当て可能な命令 依存による遅延に対して，耐性がある F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache W:Write Back Load $1=[$2] F N D S I R A 1 W Alu $3=$1+$3 F N D S S S I R X W Alu $5=$4+$5 F N D S I R X W Load $1=[$3] F N D S S I R A 1 W Alu $3=$1+$3 F N D S S S I R X W ・・・

分岐予測ミスからの復帰 分岐予測ミス後，正しい命令のフェッチが再開されるのは… 分岐ターゲットが確定する（分岐が実行される）タイミングに依存 つまり，分岐命令はフェッチ後，可能な限り即座に発行・実行したい F N D S I R X ・・・ Branch Instructions in The Predicted Function Correct Next Instruction F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache

仮想関数呼び出しにおける分岐命令発行の遅延 F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache Load $2 = [$1 + 0] Load $3 = [$2 + 0] Call $3 F 1st load F N D S I R A 1 2nd load F N D S S I R A 1 Branch (Call) F N D S S S I R X Instructions in The Predicted Function F ・・・ Correct Next Instruction F

遅延に対する対策 遅延を無くす事はできない これが通常の命令であれば・・・ が，（分岐予測のはずれる）分岐命令では・・・ 先ほどの例がアウト・オブ・オーダ実行による最善の例であり，動的スケジューリングでは，これ以上分岐命令の遅延を小さくできない これが通常の命令であれば・・・ アウト・オブ・オーダ実行により，遅延の間に他の命令を実行できるため，遅延の影響は隠蔽できる が，（分岐予測のはずれる）分岐命令では・・・ 分岐命令以降の命令郡の中から，適切な命令を選んでアウト・オブ・オーダ実行する事はできない 従って，分岐命令の遅延がそのまま性能に影響する

理想的な状態 1st load F N D S I R A 1 W F ・・・ 2nd load F N D S I R A 1 W F F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache W:Write Back F ・・・ 2nd load F N D S I R A 1 W F ・・・ Branch F N D S I R X Instructions in The Predicted Function F ・・・ Correct Next Instruction F

発表の流れ 背景 分岐予測 アウト・オブ・オーダ実行 関連研究 提案手法 レジスタ間接分岐ターゲット・フォワーディング 評価 まとめ

Virtual Function Elimination (Type Feedback) *1 頻出クラスから呼び出す場合についてコンパイラで展開 IF文追加のコスト　＜　毎回仮想関数呼び出しを行うコスト 仮想関数呼び出しは，純粋に命令数が多い IF文の分岐予測は当たるがレジスタ間接分岐は当たらない if (p->class == CartesianPoint) { // inline CartesianPoint case (most likely case) x = p->x; } else { x = p->get_x(); // dynamically-dispatched call } *1） H. D. Pande and B. G. Ryder. Static Type Determination and Aliasing for C++. Technical Report LCSR-TR-250, Department of Computer Science, Rutgers University, 1995.

Devirtualization Java用のJITにおける最適化手法 派生クラスが唯一ならば通常の関数呼び出しに書き換える *2 Java用のJITにおける最適化手法 派生クラスが唯一ならば通常の関数呼び出しに書き換える クラスローダ・実行時プロファイルの情報を動的に適用 *2) K. Ishizaki, M. Kawahito, T. Yasue, H. Komatsu, and T. Nakatani. A Study of Devirtualization Techniques for Java Just-In-Time compiler. In OOPSLA'00 Object-Oriented Programming Systems, Languages and Applications, pages 294~310, 2000.

間接分岐予測器 *3 Pentium M 1つの分岐命令に対して複数の分岐ターゲットを保持できるよう，分岐命令のPCに加えて，グローバル履歴を加味した値で分岐ターゲットバッファにアクセス 確かに複数の分岐ターゲットは保持できる 履歴に依らない大多数の仮想関数呼び出しに対しては無力 *3) S. Gochman, R. Ronen, I. Anati, A. Berkovits, T. Kurts, A. Naveh, A. Saeed, Z. Sperber, and R. C. Valentine. The Intel Pentium M Processor: Microarchitecture and Performance. Intel Technology Journal, 7(2):21–36, 2003.

Dependence-Based Pre-Computation *4 間接分岐へ依存がある命令を選択的に先行計算 大量の追加資源（レジスタファイルのポート数，追加の演算器など） 先行計算が分岐予測に間に合わない事が多い 複雑なプリフェッチャの利用 配列・構造体を見抜き，次に呼ばれる仮想関数を予測 非常に複雑であり，現実的ではない *4) A. Roth, A. Moshovos, and G. S. Sohi. Improving Virtual Function Call Target Prediction via Dependence-Based Pre-Computation. In International Conference on Supercomputing, pages 356–364, 1999.

既存手法の限界 コンパイラでは アーキテクチャでは 仮想関数呼び出しの頻度を削減するための研究が中心 本質的に除去不可能な仮想関数呼び出しに対して無力 アーキテクチャでは 仮想関数呼び出に対して有効かつ現実的な手法は提案されていない

発表の流れ 背景 分岐予測 アウト・オブ・オーダ実行 関連研究 提案手法 レジスタ間接分岐ターゲット・フォワーディング 評価 まとめ

コンパイラとアーキテクチャの協調 コンパイラによる静的スケジューリング レジスタ間接分岐ターゲット・フォワーディング レジスタ間接分岐が即座に発行できるよう，連鎖するLoad命令を優先的にスケジューリングする アウト・オブ・オーダで隠蔽できなかった分岐命令の遅延を最小限にする レジスタ間接分岐ターゲット・フォワーディング コンパイラによりLoad命令を優先的にスケジューリングする事で，分岐ターゲットを予測ではなくフォワーディングで得る事ができる 分岐予測精度の問題も解決できる

パイプライン図 レジスタ間接分岐ターゲット フォワーディング 1st load F N D S I R A 1 W F ・・・ 2nd load F N D S I R A 1 W F Forwarding F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache W:Write Back ・・・ Branch F N D Correct Next Instruction F

フォワーディング用バッファの利用 Indirect Jump Target Buffer (IJT-B) 分岐予測時に利用できるプログラムカウンタの値を用いてバッファを検索 必要な値をどのような手順でIJT-Bにフォワードするか Indirect Jump Target Buffer …0050 　・ …0058 　・ …0060 　・ …0068 call ($3) …0070 　・ …0078 　・ …0080 　・ …0068 forwarded $3 value

全体構成 PC Instruction Register Producer Table …0018 load $2 = 0($1) …0068 call ($3) 2 …0018 …0030 3 Registerfile 3 … Indirect Jump Target Producer Table …0030 …0068 Hit Indirect Jump Target Buffer …0068 …0068 … Jump Target

発表の流れ 背景 分岐予測 アウト・オブ・オーダ実行 関連研究 提案手法 レジスタ間接分岐ターゲット・フォワーディング 評価 まとめ

評価環境 シミュレータ コンパイラ ベンチマーク SimpleScalar 3.0d Alpha 提案手法に含まれる3ユニットを実装 Sim-outorderによるアウト・オブ・オーダ実行の詳細なシミュレーション コンパイラ GNU Compiler Collection 4.0.2 現時点におけるg++の最新リリース 仮想関数呼び出しにおけるLoadを優先的にスケジューリングする修正 ベンチマーク C++言語で記述されている必要があり，SPECでは意味が無い OOCSB: A C++ Benchmark Suite + α

コンパイラによる最適化 クラス内の仮想関数 引数オブジェクトの仮想関数 返値オブジェクトの仮想関数 つまり… class A { public: virtual void Foo(void); 　　A *Next(); void Bar(A *a) { … Foo(); a->Foo(); A *next = Next(); next->Foo(); }; クラス内の仮想関数 関数の入り口 引数オブジェクトの仮想関数 返値オブジェクトの仮想関数 値が返される場所 つまり… 仮想関数呼び出し手順1・2に該当する 2つのLoad命令は 最大でこれらの地点まで移動する事が可能 Load $2 = [$1 + 0] Load $3 = [$2 + 0] Call $3

レジスタ間接分岐における予測成功率の変化 Ｎ　： 最適化・フォワーディングなし Ｏ　： 最適化あり・フォワーディングなし ＯＦ： 最適化・フォワーディングあり ＦＰ： フォワーディング全成功（理想）

全分岐における予測成功率の変化 +4.1% +4.7% Ｎ ： 最適化・フォワーディングなし Ｏ ： 最適化あり・フォワーディングなし Ｎ　： 最適化・フォワーディングなし Ｏ　： 最適化あり・フォワーディングなし ＯＦ： 最適化・フォワーディングあり ＦＰ： フォワーディング全成功（理想）

パフォーマンスの変化 +13.2% +6.4% Ｎ ： 最適化・フォワーディングなし Ｏ ： 最適化あり・フォワーディングなし Ｎ　： 最適化・フォワーディングなし Ｏ　： 最適化あり・フォワーディングなし ＯＦ： 最適化・フォワーディングあり ＦＰ： フォワーディング全成功（理想）

発表の流れ 背景 分岐予測 アウト・オブ・オーダ実行 関連研究 提案手法 レジスタ間接分岐ターゲット・フォワーディング 評価 まとめ

まとめ レジスタ間接分岐 提案手法 結果 分岐履歴に基づいた既存の分岐予測では，仮想関数呼び出しにおける分岐ターゲットの予測は困難である （予測のはずれる）分岐命令の遅延はアウト・オブ・オーダ実行では隠蔽できない 提案手法 レジスタ間接分岐ターゲット・フォワーディング 分岐予測精度の問題を解決 コンパイラによる最適化 動的スケジューリングでは対応できない分岐命令の遅延について解決し，分岐ターゲットのフォワーディングも可能にした 結果 最大で13.2%の性能向上を達成した

質疑・応答

発表文献 主著論文 Cache Organization for Memory Speculation Takashi Toyoshima 卒業論文, 東京大学工学部 (Feb. 2004) メモリ投機を支援するCMP キャッシュコヒーレンスプロトコルの検討 豊島隆志, 田代大輔, バルリニコデムス, 坂井修一 情報処理学会研究会報告ARC 2005-ARC-160 (Dec. 2004) レジスタ間接分岐ターゲット・フォワーディング 豊島隆志, 入江英嗣, 五島正裕, 坂井修一 先進的計算基盤シンポジウムSACSIS 2006 (投稿中)