レジスタ間接分岐ターゲット・フォワーディング 豊島隆志†,☆, 入江英嗣‡,†, 五島正裕†, 坂井修一†

発表の流れ 背景 提案手法 評価 関連研究 まとめ 背景と目的 仮想関数 レジスタ間接分岐ターゲット・フォワーディング 仮想関数呼び出しの削減 分岐予測精度の改善 まとめ

背景と目的 分岐命令による遅延はプロセッサ性能に大きく影響 直接分岐 … 予測で遅延を隠蔽する多くの研究 要検討 　直接分岐 …　予測で遅延を隠蔽する多くの研究 　レジスタ間接分岐 …　有効な研究はない 遅延無しのレジスタ間接分岐を提供し、プロセッサ性能向上を実現 性能に影響を与える程，レジスタ間接分岐の利用頻度は高くなかった ところが，近年・・・ オブジェクト指向の普及により，利用頻度が急激に上昇 　オブジェクト指向言語では仮想関数を多用 　仮想関数の実装にはレジスタ間接分岐を使用 　オブジェクト指向言語ではレジスタ間接分岐を多用

オブジェクトの所属するクラスのみに依存する 仮想関数における分岐予測 Drawable *d = square1 Drawable … +Draw() +Next() +Move() Square *square1 Square *square2 Circle *circle1 Circle … +Draw() +Move() Square … +Draw() +Move() Square *square3 Circle *circle2 呼び出されるDraw()は dのクラスにより異なる 分岐ターゲットは履歴にはよらず オブジェクトの所属するクラスのみに依存する BTBによる分岐予測は不可能 while (NULL != d) { d->Draw(); d = d->Next(); }

仮想関数アドレスの動的解決 Load $2 = [$1 + 0] Load $3 = [$2 + 0] Call $3 レジスタ間接分岐 Circle vtable ptr var foo var bar … Virtual Function Table void (*Draw(void)) void (*Move(Point)) void Circle::Draw(void) { … } ・ Drawable *d Square vtable ptr var foo var bar … Virtual Function Table void (*Draw(void)) void (*Move(Point)) void Square::Draw(void) { … } ・

分岐予測ミス時のパイプライン 分岐予測ミス後，正しい命令のフェッチが再開されるのは… 分岐ターゲットが確定する（分岐が実行される）タイミングに依存 つまり，仮想関数呼び出しに関わる命令は即座に発行・実行したい F 1st load F N D S I R A 1 2nd load F N D S S I R A 1 図のように、最初のロードと2つ目のロード、そして最後のコール命令の間には依存があり、それぞれ発行が遅れてしまう。 この隙間は本来、スーパースカラのアウト・オブ・オーダのメカニズムにより、後続命令の中から実行可能な命令が選択され、遅延は隠蔽される。 しかし、分岐命令よりも後ろの命令に限っては、予測に基づきフェッチした命令になる。 そのため、分岐予測が当たらない状況では、いくら後続命令で穴埋めをしたところで意味がない。 つまり、斜線部分はまるまる無駄な処理となり、大きなペナルティになる。 最終的に、正しい命令のフェッチが再開されるのは、コール命令が実行された直後のタイミングになる。 よって、コール命令は可能な限り即座に発行される必要があり、そのためには直前のロード命令はコール命令に対して十分に先行している必要があり、これはコンパイラによる静的なスケジューリングに頼らざるを得ない。 Branch (Call) F N D S S S I R X Instructions in The Predicted Function F ・・・ F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache Correct Next Instruction F

発表の流れ 背景 提案手法 評価 関連研究 まとめ 背景と目的 仮想関数 レジスタ間接分岐ターゲット・フォワーディング 仮想関数呼び出しの削減 分岐予測精度の改善 まとめ

静的最適化と分岐ターゲット・フォワーディング ・・・ N D S I R A 1 F 1st load W 2nd load F:Fetch N:Rename D:Dispatch S:Sched. I:Issue R:Reg.Read X:Exec. A:Addr.Calc. 1:L1 Cache W:Write Back レジスタ間接分岐ターゲット フォワーディング Forwarding コンパイラによる静的な最適化でこのようにロード命令を十分に先行させる事で、分岐予測ミス時のペナルティを最小にできる。 しかし、さらにロード命令を先行させる事で、ロード結果＝分岐ターゲットをフロントエンドにフォワーディングし、レジスタ間接分岐の分岐ターゲットを予測せずとも確実に取得する事が可能となる。このメカニズムをレジスタ間接分岐ターゲット・フォワーディングと呼ぶ事にする。 F N D S I R X Branch F Correct Next Instruction Instructions in The Predicted Function Correct Next Instruction ・・・

フォワーディングを実現する3つのハードウェア機構 Indirect Jump Target Producer Table (IJT-PT) 分岐ターゲットを生成する命令か否かを判定するためのテーブル フォワード先のレジスタ間接分岐命令を判定するためのテーブル Register Producer Table (R-PT) 各レジスタの値を最後に更新した命令を保持するテーブル Indirect Jump Target Buffer (IJT-B) フォワードされた分岐ターゲットを保持するためのバッファ 最初に下の図でIndirect Jump Target Producerについて説明を行う Load $2 = [$1 + 0] Load $3 = [$2 + 0] Call $3 … ←分岐ターゲットを生成する命令 　＝Indirect Jump Target Producer … ←フォワード先の 　　　レジスタ間接分岐命令

Indirect Jump Target Producer Table (IJT-PT) レジスタ間接分岐を処理する際に・・・ Register Producer Tableを用いて Indirect Jump Target Producerとレジスタ間接分岐の対応を学習 学習後は・・・ IJT-PTがヒットした場合は、対となるレジスタ間接分岐に対応したIndirect Jump Target Bufferにフォワードする …0080 　・ …0088 　・ …0090 load　$3 = 0($3) …0098 load　$6 = 8($3) …00a0 　・ …00a8 　・ …00b0 call　 ($6) Indirect Jump Target Producer Table Register Producer Table 6 …0098 …00b0 …0098

Register Producer Table (R-PT) 各レジスタを最後に更新した命令（のアドレス）を保持 サイズはアドレス幅×レジスタ数 ここで言うレジスタ数はとは，レジスタ間接分岐に利用可能なレジスタの数であるため，実際の全レジスタ数より少なくて済む Register Producer Table …0080 …0088 …00a0 …0098 ・ …0070 　・ …0078 　・ …0080 move $1 = $2 …0088 alu $3 = $4 + $6 …0090 load $3 = [$3 + 0] …0098 load $6 = [$3 + 8] …00a0 alu $4 = $4 + 8 …00a8 　・ …00b0 　・ …0090

Indirect Jump Target Buffer (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 + α

レジスタ間接分岐における予測・フォワード成功率 フォワーディング IJT-P学習 分岐予測 分岐が当たらない物についてはフォワーディングによって完全にカバーできる フォワーディングが間に合わない場合でも、分岐予測が当たっている場合ならば、そちらを採用すれば良い Ｎ　： 最適化・フォワーディングなし Ｏ　： 最適化あり・フォワーディングなし ＯＦ： 最適化・フォワーディングあり ＦＰ： フォワーディング全成功（理想）

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

パフォーマンスの変化 +13.2% +6.4% Ｎ ： 最適化・フォワーディングなし Ｏ ： 最適化あり・フォワーディングなし 予測が当たっていない場合はコンパイラの最適化だけでも性能向上が見られる。 これは、分岐ミスペナルティが小さくなっているためである。 Ｎ　： 最適化・フォワーディングなし Ｏ　： 最適化あり・フォワーディングなし ＯＦ： 最適化・フォワーディングあり ＦＰ： フォワーディング全成功（理想）

発表の流れ 背景 提案手法 評価 関連研究 まとめ 背景と目的 仮想関数 レジスタ間接分岐ターゲット・フォワーディング 仮想関数呼び出しの削減 分岐予測精度の改善 まとめ

仮想関数呼び出しの削減 Virtual Function Elimination (Type Feedback) *1 Virtual Function Elimination (Type Feedback) Devirtualization Java用のJITにおける最適化手法 派生クラスが唯一ならば通常の関数呼び出しに書き換える クラスローダ・実行時プロファイルの情報を動的に適用 if (p->class == CartesianPoint) { // inline CartesianPoint case (most likely case) x = p->x; } else { x = p->get_x(); // dynamically-dispatched call } *2 *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. *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.

分岐予測精度の改善 Dependence-Based Pre-Computation 間接分岐予測器 (Pentium M) 間接分岐へ依存がある命令を選択的に先行計算 大量の追加資源（レジスタファイルのポート数，追加の演算器など） 先行計算が分岐予測に間に合わない事が多い 複雑なプリフェッチャの利用 配列・構造体を見抜き，次に呼ばれる仮想関数を予測 非常に複雑であり，現実的ではない 間接分岐予測器 (Pentium M) 1つの分岐命令に対して複数の分岐ターゲットを保持できるよう，グローバル履歴を加味した値でBTBにアクセス 複数の分岐ターゲットが保持できる 履歴に依らない分岐ターゲットには無力 *3 *4 *3) 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. *4) 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.

発表の流れ 背景 提案手法 評価 関連研究 まとめ 背景と目的 仮想関数 レジスタ間接分岐ターゲット・フォワーディング 仮想関数呼び出しの削減 分岐予測精度の改善 まとめ

まとめ レジスタ間接分岐 提案手法 結果 分岐履歴に基づいた既存の分岐予測では，仮想関数呼び出しにおける分岐ターゲットの予測は困難である （予測のはずれる）分岐命令の遅延はアウト・オブ・オーダ実行では隠蔽できない 提案手法 レジスタ間接分岐ターゲット・フォワーディング 予測ではなく、フォワーディングを行う事で確実に分岐ターゲットを得る IJT-PT, R-PT, IJT-Bの3つの機構を提案 静的スケジューリングによる最適化 動的スケジューリングでは対応できない分岐命令の遅延について解決 分岐ターゲットのフォワーディングを可能にする 結果 最大で13.2%の性能向上を達成した

質疑・応答

予備資料

最適化アルゴリズム オブジェクトの検出 move $1 = $4 確定地点の特定 load $N = 0($1) レジスタ間接分岐命令を探し出し，仮想関数呼び出しならオブジェクトを指すレジスタを特定する 確定地点の特定 前述の3つのケースに照らし合わせて，仮想関数が確定する地点を特定する 分岐ターゲット生成コード複製 仮想関数呼び出し手順1・2を複製する 使用レジスタの変更 この地点で利用可能，かつ分岐までに破壊されないレジスタに変更する 呼び出しコードの変更 レジスタの変更に合わせて分岐命令を修正する 重複するコードの除去 後続命令に対して依存が無ければ、元の手順1・2に当たるコードを除去する move $1 = $4 load $2 = 0($1) load $3 = 0($2) call ($3) call ($N) load $N = 0($1) load $N = 0($N) ・ ・ ・ ・ ・ ・

コンパイラによる最適化 クラス内の仮想関数 引数オブジェクトの仮想関数 返値オブジェクトの仮想関数 つまり… 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

実行された全命令中の各分岐命令の割合 1～3%の間接分岐命令 ペナルティは10～20命令相当分発生するため、性能に１割近い影響を与えるという結果は妥当と言える