スライド 1

レジスタ間接分岐ターゲット・フォワーディング
豊島隆志†,☆, 入江英嗣‡,†, 五島正裕†, 坂井修一†
† 東京大学大学院情報理工学系研究科
‡ 科学技術振興機構
☆ 現在，富士通研究所
MTL
坂井・五島研究室
発表の流れ

背景
– 背景と目的
– 仮想関数

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


評価
関連研究
– 仮想関数呼び出しの削減
– 分岐予測精度の改善

まとめ
1
背景
MTL
坂井・五島研究室
背景と目的

分岐命令による遅延はプロセッサ性能に大きく影響
要検討
• 直接分岐
• レジスタ間接分岐
… 予測で遅延を隠蔽する多くの研究
… 有効な研究はない
遅延無しのレジスタ間接分岐を提供し、プロセッサ性能向上を実現
性能に影響を与える程，レジスタ間接分岐の利用頻度は高くなかった
ところが，近年・・・
オブジェクト指向の普及により，利用頻度が急激に上昇
• オブジェクト指向言語では仮想関数を多用
• 仮想関数の実装にはレジスタ間接分岐を使用
• オブジェクト指向言語ではレジスタ間接分岐を多用
2
背景
MTL
坂井・五島研究室
仮想関数における分岐予測
Drawable *d = square1
Drawable
…
+Draw()
+Next()
+Move()
Square *square1
Square *square2
Circle *circle1
Circle
…
+Draw()
+Move()
Square
…
+Draw()
+Move()
while (NULL != d) {
d->Draw();
d = d->Next();
}
Square *square3
Circle *circle2
呼び出されるDraw()は
dのクラスにより異なる
分岐ターゲットは履歴にはよらず
オブジェクトの所属するクラスのみに依存する
BTBによる分岐予測は不可能
3
背景
MTL
坂井・五島研究室
仮想関数アドレスの動的解決
1.
2.
3.
Load
Load
Call
$2 = [$1 + 0]
$3 = [$2 + 0]
$3
レジスタ間接分岐
Circle
Drawable *d
vtable ptr
var foo
var bar
…
Square
vtable ptr
var foo
var bar
…
Virtual Function Table
void (*Draw(void))
void (*Move(Point))
・
・
・
Virtual Function Table
void (*Draw(void))
void (*Move(Point))
・
・
・
void
Circle::Draw(void)
{
…
…
…
}
void
Square::Draw(void)
{
…
…
…
}
4
背景
MTL
坂井・五島研究室
分岐予測ミス時のパイプライン

分岐予測ミス後，正しい命令のフェッチが再開されるのは…
– 分岐ターゲットが確定する（分岐が実行される）タイミングに依存
– つまり，仮想関数呼び出しに関わる命令は即座に発行・実行したい
F
1st load
F
N
D
S
I
R
A
1
2nd load
F
N
D
S
S
I
R
A
1
F
N
D
S
S
S
I
R
Branch (Call)
Instructions F
in
The Predicted Function
F:Fetch
S:Sched.
X:Exec.
X
・
・
・
N:Rename
D:Dispatch Correct Next Instruction
I:Issue
R:Reg.Read
A:Addr.Calc. 1:L1 Cache
F
5
MTL
坂井・五島研究室
発表の流れ

背景
– 背景と目的
– 仮想関数

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


評価
関連研究
– 仮想関数呼び出しの削減
– 分岐予測精度の改善

まとめ
6
提案手法
MTL
坂井・五島研究室
静的最適化と分岐ターゲット・フォワーディング
1st load
F
N
D
S
I
R
A
1
W
F
2nd load
・
・
・
F
N
D
S
I
R
A
1
W
I
R
X
F
Branch
・
・
・
F
N
Forwarding
D
S
F:Fetch
N:Rename
D:Dispatch
S:Sched.
I:Issue
R:Reg.Read
X:Exec.
A:Addr.Calc.
1:L1 Cache
W:Write Back
Correct
F Next Instruction
Instructions
in
・
The Predicted Function
・
・
レジスタ間接分岐ターゲット
Correct Next Instruction F
フォワーディング
7
提案手法
MTL
坂井・五島研究室
フォワーディングを実現する3つのハードウェア機構

Indirect Jump Target Producer Table (IJT-PT)
– 分岐ターゲットを生成する命令か否かを判定するためのテーブル
– フォワード先のレジスタ間接分岐命令を判定するためのテーブル

Register Producer Table (R-PT)
– 各レジスタの値を最後に更新した命令を保持するテーブル

Indirect Jump Target Buffer (IJT-B)
– フォワードされた分岐ターゲットを保持するためのバッファ
1. Load
$2 = [$1 + 0]
…
2. Load
$3 = [$2 + 0] ←分岐ターゲットを生成する命令
…
＝Indirect Jump Target Producer
3. Call
$3
←フォワード先の
レジスタ間接分岐命令
8
提案手法
MTL
坂井・五島研究室
Indirect Jump Target Producer Table (IJT-PT)

レジスタ間接分岐を処理する際に・・・
– Register Producer Tableを用いて
– Indirect Jump Target Producerとレジスタ間接分岐の対応を学習

学習後は・・・
– IJT-PTがヒットした場合は、対となるレジスタ間接分岐に対応した
Indirect Jump Target Bufferにフォワードする
…0080
…0088
…0090
…0098
…00a0
…00a8
…00b0
・
・
load $3 = 0($3)
Indirect Jump Target
load $6 = 8($3)
Producer Table
Register
・
Producer Table
・
6
…0098
call ($6)
…00b0
…0098
9
提案手法
MTL
坂井・五島研究室
Register Producer Table (R-PT)


各レジスタを最後に更新した命令（のアドレス）を保持
サイズはアドレス幅×レジスタ数
– ここで言うレジスタ数はとは，レジスタ間接分岐に利用可能なレジス
タの数であるため，実際の全レジスタ数より少なくて済む
Register
Producer Table
…0070
…0078
…0080
…0088
…0090
…0098
…00a0
…00a8
…00b0
・
・
move
alu
load
load
alu
・
・
…0080
$1
$3
$3
$6
$4
=
=
=
=
=
$2
$4 + $6
[$3 + 0]
[$3 + 8]
$4 + 8
…0090
…0088
…00a0
…0098
・
・
・
10
提案手法
MTL
坂井・五島研究室
Indirect Jump Target Buffer (IJT-B)


分岐予測時に利用できるプログラムカウンタ値を用いてバッファ検索
サイズはアドレス幅×１～４エントリ程度で十分
…0050
…0058
…0060
…0068
…0070
…0078
…0080
・
・
・
Call
・
・
・
Indirect Jump Target Buffer
$3
…0068
forwarded
$3 value
11
提案手法
MTL
坂井・五島研究室
処理の流れ
PC
Instruction
Register Producer Table
…0018
load
$2 = 0($1)
2
3
…0030
load
…0018
…0030
Registerfile
$3 = 0($2)
3
…
Indirect Jump Target Producer Table
…0030
…0068
…0068
call
Hit
($3)
Indirect Jump Target Buffer
…0068
…
…0068
Jump Target
12
MTL
坂井・五島研究室
発表の流れ

背景
– 背景と目的
– 仮想関数

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


評価
関連研究
– 仮想関数呼び出しの削減
– 分岐予測精度の改善

まとめ
13
評価
MTL
坂井・五島研究室
評価環境

シミュレータ
– SimpleScalar 3.0d Alpha



提案手法に含まれる3ユニットを実装
sim-outorderによるアウト・オブ・オーダ実行の詳細なシミュレーション
コンパイラ
– GNU Compiler Collection 4.0.2



評価時におけるg++の最新リリース
仮想関数呼び出しにおけるLoadを優先的にスケジューリングする修正
ベンチマーク
– C++言語で記述されている必要があり，SPECでは意味が無い
– OOCSB: A C++ Benchmark Suite + α
14
評価
MTL
坂井・五島研究室
レジスタ間接分岐における予測・フォワード成功率
フォワーディング
IJT-P学習
100
90
80
70
60
50
40
30
20
10
0
分岐予測
N
O
OF
FP
richards
Ｎ：最適化・フォワーディングなし
ＯＦ：最適化・フォワーディングあり
deltablue
ray
Ｏ：最適化あり・フォワーディングなし
ＦＰ：フォワーディング全成功（理想）
15
評価
MTL
坂井・五島研究室
全分岐における予測・フォワード成功率
100
90
80
70
60
50
40
30
20
10
0
+4.1%
+4.7%
N
O
OF
FP
richards
Ｎ：最適化・フォワーディングなし
ＯＦ：最適化・フォワーディングあり
deltablue
ray
Ｏ：最適化あり・フォワーディングなし
ＦＰ：フォワーディング全成功（理想）
16
評価
MTL
坂井・五島研究室
パフォーマンスの変化
1.2
+13.2%
+6.4%
1
0.8
N
O
OF
FP
0.6
0.4
0.2
0
richards
Ｎ：最適化・フォワーディングなし
ＯＦ：最適化・フォワーディングあり
deltablue
ray
Ｏ：最適化あり・フォワーディングなし
ＦＰ：フォワーディング全成功（理想）
17
MTL
坂井・五島研究室
発表の流れ

背景
– 背景と目的
– 仮想関数

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


評価
関連研究
– 仮想関数呼び出しの削減
– 分岐予測精度の改善

まとめ
18
関連研究
MTL
坂井・五島研究室
仮想関数呼び出しの削減

Virtual Function Elimination (Type Feedback)
*1
if (p->class == CartesianPoint) {
// inline CartesianPoint case (most likely case)
x = p->x;
} else {
x = p->get_x(); // dynamically-dispatched call
}

Devirtualization
*2
– Java用のJITにおける最適化手法

派生クラスが唯一ならば通常の関数呼び出しに書き換える
– クラスローダ・実行時プロファイルの情報を動的に適用
*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.
19
関連研究
MTL
坂井・五島研究室
分岐予測精度の改善

*3
Dependence-Based Pre-Computation
– 間接分岐へ依存がある命令を選択的に先行計算


大量の追加資源（レジスタファイルのポート数，追加の演算器など）
先行計算が分岐予測に間に合わない事が多い
– 複雑なプリフェッチャの利用


配列・構造体を見抜き，次に呼ばれる仮想関数を予測
非常に複雑であり，現実的ではない
*4

間接分岐予測器 (Pentium M)
– 1つの分岐命令に対して複数の分岐ターゲットを保持できるよう，グ
ローバル履歴を加味した値でBTBにアクセス


複数の分岐ターゲットが保持できる
履歴に依らない分岐ターゲットには無力
*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.
20
MTL
坂井・五島研究室
発表の流れ

背景
– 背景と目的
– 仮想関数

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


評価
関連研究
– 仮想関数呼び出しの削減
– 分岐予測精度の改善

まとめ
21
MTL
坂井・五島研究室
まとめ

レジスタ間接分岐
– 分岐履歴に基づいた既存の分岐予測では，仮想関数呼び出しにお
ける分岐ターゲットの予測は困難である
– （予測のはずれる）分岐命令の遅延はアウト・オブ・オーダ実行では
隠蔽できない

提案手法
– レジスタ間接分岐ターゲット・フォワーディング


予測ではなく、フォワーディングを行う事で確実に分岐ターゲットを得る
IJT-PT, R-PT, IJT-Bの3つの機構を提案
– 静的スケジューリングによる最適化



動的スケジューリングでは対応できない分岐命令の遅延について解決
分岐ターゲットのフォワーディングを可能にする
結果
– 最大で13.2%の性能向上を達成した
22
MTL
坂井・五島研究室
質疑・応答
23
MTL
坂井・五島研究室
予備資料
24
予備資料
MTL
坂井・五島研究室
多態性

例
– 非仮想関数の場合

Drawable::Draw();
– 仮想関数の場合


Circle::Draw();
応用
– アルゴリズムと操作対象を分離


Drawableに対して操作する形で
アルゴリズムを実装
操作対象はDrawableを継承して
実装すれば後から任意の操作対
象を追加する事ができる
class Drawable {
public:
void Draw(void);
virtual
void Draw(void);
…
};
class Circle : public Drawable {
public:
void Draw(void);
…
};
Circle circle;
circle.Draw();
Drawable *drawable = &circle;
drawable->Draw();
25
予備資料
MTL
坂井・五島研究室
分岐方向予測

条件分岐が成立するか否かを予測する
– その分岐命令について以前は分岐が成立したか否か（ローカル履
歴）
– この命令に至るまでに通過した分岐郡について，どの分岐が成立し
たか（グローバル履歴）

仮想関数呼び出しにおいて特に問題にはならない
26
予備資料
MTL
坂井・五島研究室
最適化アルゴリズム
1.
オブジェクトの検出

2.
確定地点の特定

3.
load
load
$N = 0($1)
$N = 0($N)
前述の3つのケースに照らし合わせて，
仮想関数が確定する地点を特定する
・
・
・
・
・
・
仮想関数呼び出し手順1・2を複製する
この地点で利用可能，かつ分岐までに
破壊されないレジスタに変更する
呼び出しコードの変更

6.
$1 = $4
使用レジスタの変更

5.
move
分岐ターゲット生成コード複製

4.
レジスタ間接分岐命令を探し出し，仮想
関数呼び出しならオブジェクトを指すレ
ジスタを特定する
レジスタの変更に合わせて分岐命令を
修正する
重複するコードの除去

後続命令に対して依存が無ければ、元
の手順1・2に当たるコードを除去する
load
load
call
call
$2 = 0($1)
$3 = 0($2)
($3)
($N)
27
予備資料
MTL
坂井・五島研究室
コンパイラによる最適化
1.
クラス内の仮想関数

2.
引数オブジェクトの仮想関数

3.
関数の入り口
関数の入り口
返値オブジェクトの仮想関数

値が返される場所
つまり…
仮想関数呼び出し手順1・2に該当する
2つのLoad命令は
最大でこれらの地点まで移動する事が可能
class A {
public:
virtual void Foo(void);
A *Next();
void Bar(A *a) {
…
Foo();
a->Foo();
A *next = Next();
…
next->Foo();
};
};
1. Load $2 = [$1 + 0]
2. Load $3 = [$2 + 0]
3. Call $3
28
予備資料
MTL
坂井・五島研究室
仮想関数における分岐予測

分岐ターゲットが履歴に依らない
Drawableオブジェクトのリスト
Drawable *d = square1;
Square *square1
while (NULL != d) {
d->Draw();
d = d->Next();
}

グローバル履歴を用いたBTBでも・・・
Square *square2
Circle *circle1
– オブジェクトに依らず、毎回同じエントリを参照
Square *square3
– 古典的なBTB以上の効果は得られない
Circle *circle2
29
予備資料
MTL
坂井・五島研究室
なぜレジスタ間接分岐が必要なのか？

通常の関数

Drawable
仮想関数
Drawable
Draw / Move / …
Draw / Move / …
継承
Circle
Draw / Move / …
継承
Circle
Draw / Move / …
Virtual Function Table による動的な呼び出し関数アドレスの解決
30
予備資料
MTL
坂井・五島研究室
理想的な状態（コンパイラ等による最適化）
1st load
F
N
D
S
I
R
A
1
W
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
N
D
S
I
R
X
F
Branch
Instructions
in
The Predicted Function
F
・
・
・
Correct Next Instruction
F
31
予備資料
MTL
坂井・五島研究室
さらに一歩推し進めると・・・
1st load
F
N
D
S
I
R
A
1
W
F
・
・
・
N
D
S
I
R
A
F
2nd load
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
1
W
Forwarding
・
・
・
Branch
F
Correct Next Instruction
N
D
F
レジスタ間接分岐ターゲット
フォワーディング
32
予備資料
MTL
坂井・五島研究室
実行された全命令中の各分岐命令の割合
25
20
15
復帰
間接分岐
直接分岐
10
5
0
richards
deltablue
ray
33
予備資料
MTL
坂井・五島研究室
評価におけるハードウェア機構の各サイズ

Indirect Jump Target Producer Table (IJT-PT)
– 16kBytes (64bit x 4k Entries / 2-way)

Register Producer Table (R-PT)
– 128Bytes (64bit x 32 Entries)

Indirect Jump Target Buffer (IJT-B)
– 8Bytes (64bit x 2 Entries)
34
予備資料
MTL
坂井・五島研究室
スーパースカラにおける仮想関数呼び出しの問題点

分岐ターゲット予測の困難性
– 前述の通り，分岐予測は全く当たらない！！

例外的な“遅延に対する耐性”の欠如
– 本来スーパースカラは，長い遅延に対して耐性がある
– しかし，分岐が外れる場合に限っては，分岐命令及びその直前の
命令における遅延が，そのままペナルティの大きさに影響する
1. Load
2. Load
3. Call


$2 = [$1 + 0]
$3 = [$2 + 0]
$3
メモリ読み出しを伴う，連鎖したデータ依存
最終的に分岐ターゲット（制御）へ依存
– 仮想関数呼び出しにおいて発生する長い遅延は，分岐予測が当た
らないため，隠蔽されず大きなペナルティを生じる
35

Download Report