分岐予測と TC

Advanced Computer Architecture
06. 分岐予測器とトレース・キャッシュ
五島正裕
2015/10/1
Advanced Computer Architecture
内容
1. 分岐予測の復習
2. 分岐予測の効果
3. 分岐予測器
4. トレース・キャッシュ
2
Advanced Computer Architecture
分岐予測の復習
2015/10/1
Advanced Computer Architecture
4
投機のフェーズ
1. 予測 (prediction)
2. 実行 (execution)
3. 確認 (verification, confirmation)
4. キャンセル，回復，再実行 (cancellation, recovery, re-execution)
cycle
A
1. 予測
3. 確認
2. 実行
B 4. 再実行
Advanced Computer Architecture
5
分岐予測
cycle
3. 確認
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
r1 == r2
add r8 = r6 + r7
IF
OR
EX
MEM WB
PC 予測
add r8 = r8 1.
+ 1
IF
OR
EX
MEM WB
2. フェッチ
sub r9 = r6 - r7
IF
OR
EX
MEM WB
ld
IF
OR
EX
MEM WB
r8 = *(r9)
Advanced Computer Architecture
6
分岐予測
cycle
3. 確認
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
r1 == r2, L0
L0: ld
add r8 = *(r6)
r6 + r7
PC
add r9
r8 = r8 1.
+ 1
sla
<<
1 予測
IF
OR
IF
OR
EX
MEM WB
IF
OR
IF
OR
EX
MEM WB
2. フェッチ
add
sub r9 = r9
r6 +
- 1
r7
ld r8 = r9
*(r9)
sub
- 1
4. 再フェッチ
IF
IF
OR
EX
M
IF
IF
OR
EX
M
Advanced Computer Architecture
7
分岐予測
cycle
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
L0: ld
r1 == r2, L0
r8 = *(r6)
sla r9 = r8 << 1
IF
OR
IF
OR
EX
MEM WB
IF
OR
IF
OR
EX
MEM WB
add r9 = r9 + 1
IF
IF
OR
EX
M
sub r8 = r9 - 1
IF
IF
OR
EX
M
ミス･ペナルティ (= H, M = 0)
Advanced Computer Architecture
投機の効果
 「毎回かかるレイテンシを，ミス時のペナルティに」
 （予測ミスによるレイテンシの増加）＝
（予測率） ×（予測ミス率） ×（ミス･ペナルティ）
 予測ミス率が十分小さければ (ex. 1%)，

ミス･ペナルティは1～２サイクル長くなってもよい
8
Advanced Computer Architecture
分岐予測の効果
2015/10/1
Advanced Computer Architecture
分岐命令の出現頻度
 Run Length :

分岐から次の分岐までの命令数

3～5命令
 フェッチ幅 2～4 だと…

ほとんど毎サイクル，分岐命令をフェッチ
10
Advanced Computer Architecture
11
分岐予測の効果 (1/4)
 プログラム

n ：プログラムの命令数

b ：そのうち，分岐命令の割合
 プロセッサ：

p ：分岐予測ミス・ペナルティ
 プログラム on プロセッサ
 i0 ：分岐予測ミス率

β ：分岐予測ミス率
0% の時の IPC
Advanced Computer Architecture
分岐予測の効果 (2/4)
分岐予測ミス率 0% の時のプログラムの実行サイクル数：
n / i0
分岐予測ミスによる実行サイクル数の増加：
nbpβ
分岐予測ミス率 β の時の IPC：
n / {n / i0 + n b p β} = 1/ {1 / i0 + b p β}
12
Advanced Computer Architecture
13
分岐予測の効果 (3/4)
分岐予測ミス率 β の時の IPC：
1/ {1 / i0 + b p β}
i0 = 2，b = 0.2，p = 10 とすると，
1/ {1 / i0 + b p β} = 1 / { 0.5 + 0.2 ×10× β} = 1 / (0.5 + 2β)
β
0%
1%
3%
5%
10%
50%
100%
IPC
2.0
1.92
1.79
1.67
1.43
0.67
0.4
IPC 低下率
−0%
−4%
−11%
−16%
−29%
−66%
−80%
Advanced Computer Architecture
14
分岐予測の効果 (4/4)
1 / (0.5 + 2β)
i0 = 2
0.4
O
β
1.0
Advanced Computer Architecture
分岐予測器
2015/10/1
Advanced Computer Architecture
17
制御命令（分岐命令）
 （条件）分岐命令

if (cond) PC = PC + immediate;

branch on register


cond: R[Rs] == 0, R[Rs] > 0, …
compare and branch

cond: R[Rs] == R[Rt], R[Rs] != R[Rt]
op
31
Rs
25
Rt
20
immediate
15
0
Advanced Computer Architecture
18
インターロックの排除（制御ハザード）
cycle
I0
IF
be
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
I1
I0
IF
IF
be
OR
EX
IF
MEM
OR
nPC
be
I0
I1
OR
nPC
IF
EX
OR
EX
MEM WB
MEM WB
OR
IF
MEM
next PC 計算器
MEM WB
IF
IF
EX
WB
EX
I1
ID
EX
OR
MEM WB
EX
MEM WB
遅延分岐
W
Advanced Computer Architecture
19
スーパスカラ・プロセッサと遅延分岐
cycle
I0
IF
OR
be
IF
OR
EX
nPC
EX
MEM WB
MEM WB
I1
IF
OR
EX
MEM WB
I2
IF
OR
EX
MEM WB
be
IF
OR
I0
IF
OR
nPC
EX
EX
MEM WB
MEM WB
I1
IF
OR
EX
MEM WB
I2
IF
OR
EX
MEM WB
Advanced Computer Architecture
スーパスカラ・プロセッサと遅延分岐
 遅延分岐では救えない

分岐スロットの数

スカラなら1命令で OK だった．

2命令同時フェッチなら？

4命令なら？
 分岐予測が必須
20
Advanced Computer Architecture
分岐予測に使える情報
 毎サイクル，フェッチするためには，

命令をフェッチしてから next PC を求めるのでは遅い
 「fetch PC だけから次の fetch PC を！」
21
Advanced Computer Architecture
22
スーパスカラ・プロセッサの分岐予測
cycle
fetch PC
I0
IF
be
IF
OR
EX
fetch PC
OR
EX
MEM WB
MEM WB
I1
IF
OR
EX
MEM WB
I2
IF
OR
EX
MEM WB
fetch PC
be
IF
I0
IF
OR
EX
fetch PC
OR
EX
MEM WB
MEM WB
I1
IF
OR
EX
MEM WB
I2
IF
OR
EX
MEM WB
Advanced Computer Architecture
23
分岐予測
 分岐予測：

分岐方向予測

分岐アドレス予測
bool pred_taken = branch_dir_pred(fetch_PC);
addr_t taken_PC = btb_lookup(fetch_PC);
/* BTB ミスなら 0 */
addr_t untaken_PC = fetch_PC + INSN_SIZE * FETCH_WIDTH;
addr_t next_PC =
(taken_PC && pred_taken) ? taken_PC : untaken_PC;
Advanced Computer Architecture
24
BTB : Branch Target Buffer
fetch PC
tag
valid
taken PC
selector
taken PC
Advanced Computer Architecture
分岐方向予測の原理その1
 ローカル分岐履歴 (local branch history)

基本的には，前回と同じだろう

ヒステリシスを持たせ，発振を防ぐ
25
Advanced Computer Architecture
26
2-bit 飽和形カウンタ (2-bit saturating counter)
fetch PC
PHT (Pattern History Table)
10
taken
11
strongly taken
10
weakly taken
01
weakly untaken
00
strongly untaken
untaken
Advanced Computer Architecture
PHT (Pattern History Table)
 タグ，有効ビットがない

「ミス」がない

コンフリクト（衝突）が起こる
 あまり気にしなくてもよい

どうせ，そこそこ外れるものだから

エントリ数が十分多ければ（数K），確率は低い
 タグの分だけ PHT のエントリを増やしたほうが得

PHT: 2b

タグ： 10～30ｂ
27
Advanced Computer Architecture
分岐方向予測
 分岐予測：
bool pred_taken = branch_dir_pred(fetch_PC);
addr_t taken_PC = btb_lookup(fetch_PC);
addr_t untaken_PC = fetch_PC + 4 * FETCH_WIDTH;
addr_t next_PC =
taken_PC && pred_taken ? taken_PC : untaken_PC;
28
Advanced Computer Architecture
29
分岐方向予測の原理その2
 グローバル分岐履歴 (global branch history)

ローカルは，自身の履歴

グローバルは，すべての分岐

最近実行された分岐，12回程度の結果を記録

たとえば：
for (int i = 0; i < N; ++i)
if (i % 2)
even();
else
odd();

NNNTNNNT…
Advanced Computer Architecture
30
gshare (McFarling ‘93)
fetch PC
0001
PHT
00
XOR
0010
0 0 1 1
Global History Register
01
11
01
01
 同じ分岐でも，
グローバル履歴が異なれば，
別のカウンタを使用．
 ただし，コンフリクトが多発

数十パタン／分岐
01
01
01
 コンフリクトを軽減する研究

「要は，圧縮」
Advanced Computer Architecture
31
分岐命令のプロファイル
 分岐の方向には，偏りがある

利用して，テーブルを圧縮
taken 率
taken 率
1.0
1.0
0.0
0.0
分岐命令
（taken 率でソート）
always untaken
always taken
Advanced Computer Architecture
パーセプトロン分岐予測機
 パーセプトロン：ニューラル・ネットワークの一種
 今後，流行るかも．
32
Advanced Computer Architecture
トレース・キャッシュ
2015/10/1
Advanced Computer Architecture
34
命令キャッシュ
fetch PC
31
5
2
0
0
4
1
5
2
6
3
7
0
4
1
5
2
6
3
7
Cache
Lines
Rotator
Advanced Computer Architecture
35
命令キャッシュ通常
fetch PC
010
31
5
2
0
0
4
1
5
2
6
3
7
0
4
1
5
2
6
3
7
Cache
Lines
Rotator
Advanced Computer Architecture
36
命令キャッシュラインを跨ぐ
fetch PC
110
31
5
2
0
0
4
1
5
2
6
3
7
0
4
1
5
2
6
3
7
Cache
Lines
Rotator
Advanced Computer Architecture
37
命令キャッシュ分岐を含む
fetch PC
010
31
5
2
0
0
4
1
5
2
6
3
7
0
4
1
5
2
6
3
7
Cache
Lines
Rotator
Advanced Computer Architecture
38
命令キャッシュ分岐を含む
fetch PC
0 1 10
31
5
2
0
0
4
1
5
2
6
3
7
0
4
1
5
2
6
3
7
Cache
Lines
Rotator
2
3
4
5
Advanced Computer Architecture
フェッチ・グループ
 フェッチ・グループ

同時にフェッチされる命令のグループ
 fetch PC：

フェッチ・グループの先頭命令の PC
 next PC：

次の fetch PC

フェッチ・グループに分岐命令が含まれている場合，

その分岐命令の予測された飛び先の PC
39
Advanced Computer Architecture
困難
 フェッチ・グループが：

キャッシュ・ラインを跨ぐ場合：


キャッシュ・ヒット/ミス判定器が複数必要
分岐を含む場合：

その分岐の予測先のフェッチは困難
– もう1サイクル前に予測しておく必要があった
– 次の次の分岐予測器


予測できても，バンク・コンフリクトが発生
分岐を複数含む

？
40
Advanced Computer Architecture
41
トレース・キャッシュ
fetch PC
31
2
XOR
dir pred
0
2
3
4
5
2
3
4
3
6
7
0
1
Traces
Advanced Computer Architecture
トレース・キャッシュ
 トレース：

分岐先 (branch target) アドレスから始まる，

ある（予測）パスに沿った命令の列
 トレース・キャッシュ：

トレース単位でキャッシング

HW が単純に

ただし，アレイの利用効率が悪い
42
Advanced Computer Architecture
43
トレース・キャッシュの位置
I$
T$
I$
T$
Insn
Pipe
Insn
Pipe
タンデム
（Pentium 4)
パラレル
Advanced Computer Architecture
今日のまとめ
2015/10/1
Advanced Computer Architecture
分岐予測器
 taken PC

BTB (branch target buffer)
 分岐方向予測器

ローカル履歴

グローバル履歴
45
Advanced Computer Architecture
トレース・キャッシュ
 トレース・キャッシュ：

トレース単位でキャッシング
 ある種のバイナリ変換

個々の命令ではなく，トレースをフェッチしているように見える

トレース＝長命令？

VLIW？
46
Advanced Computer Architecture
今後の予定
 次週

値予測
47

Download Report