スライド 1

Advanced Computer Architecture
05. Out-of-Order 実行機構
五島正裕
2015/10/1
Advanced Computer Architecture
内容
1. レジスタ・リネーミングの復習
2. 分岐予測の復習
3. レジスタ・リネーミングと分岐予測
2
Advanced Computer Architecture
レジスタ･リネーミングの復習
2015/10/1
Advanced Computer Architecture
4
論理レジスタ，物理レジスタ
 論理レジスタ (logical register)

命令のフィールドで指定する r0 ～ r31

「データ･フローを表現するための名前，タグ」


必ずしも，物理的に存在している必要はない
高級言語で言えば「変数」
 物理レジスタ (physical register)

「データの物理的な格納場所」

高級言語で言えば「物理メモリ（のロケーション）」
op
31
Rs
25
Rt
20
Rd
15
shamt func
10
0
Advanced Computer Architecture
物理レジスタの管理
 空き物理 Reg のプール
1. 割り当て (allocation)：

空き物理 Reg を取得，デスティネーションに割り当てる

論理→物理マッピングを確立
2. 解決 (resolution)：

ソースの論理 Reg にマップされている物理 Reg を見つける
3. 解放 (free)：

不要になった物理 Reg をプールに返す
5
Advanced Computer Architecture
6
レジスタ･リネーミング ― 割り当てと解決
RFRF
命令
キャッシュ
フェッチ
Fetch
リネーム
命令
ウィンドウ
ロジック
リネーム
Rename
ディスパッチ
Dispatch
スケジュール
Schedule
演算器
発行
Issue
実行
Exec
書戻
WB
Advanced Computer Architecture
7
レジスタ･リネーミング― 割り当てと解決
 命令は，リネーム･ロジックを In-Order に通過する

プログラム・オーダが分かる

ld
物理 Reg
プール
データ依存が分かる
r1
p11
=
*($sp)
sla
r2
p12
=
r1 << 1
p11
sla
r3
p13
=
r1 << 2
p11
add
r4
p14
=
r3 + r2
p13 p12
Reg マップ
テーブル
p0
p11
p12
p13
p14
p10
p11
p12
p13
p14
r1
r2
r3
r4
r31
p63
Advanced Computer Architecture
分岐予測の復習
2015/10/1
Advanced Computer Architecture
9
投機のフェーズ
1. 予測 (prediction)
2. 実行 (execution)
3. 確認 (verification, confirmation)
4. キャンセル，回復，再実行 (cancellation, recovery, re-execution)
cycle
A
1. 予測
3. 確認
2. 実行
B 4. 再実行
Advanced Computer Architecture
10
分岐予測
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
11
分岐予測
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
12
分岐予測
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～２サイクル長くなってもよい
13
Advanced Computer Architecture
14
分岐予測とフロントエンド/バックエンド
RFRF
命令
キャッシュ
フェッチ
Fetch
リネーム
命令
ウィンドウ
ロジック
リネーム
Rename
フロントエンド
front-end
ディスパッチ
Dispatch
スケジュール
Schedule
演算器
発行
Issue
実行
Exec
バックエンド
back-end
書戻
WB
Advanced Computer Architecture
分岐予測とフロントエンド/バックエンド
 フロントエンド

分岐予測に基づいて自律的に，命令を命令ウィンドウに詰める
 バックエンド

命令ウィンドウ内から発行された命令を，実際に実行する

分岐予測の結果を確かめる
 BE ⇒ FE のインタラクション

分岐予測ミスのみ
15
Advanced Computer Architecture
4.レジスタ・リネーミングと分岐予測
2015/10/1
Advanced Computer Architecture
分岐予測ミス時の回復
 予測した分岐命令の，プログラム・オーダ上で下流の命令：

投機的に実行された命令
 予測がミスであった場合，

投機的に実行された命令の実行を取り消す，具体的には，

デスティネーション・レジスタ（論理）の内容を元に戻す
 書き潰すと OUT！
 投機的に実行した命令は，
マシン・ステートを不可逆的に更新してはいけない
17
Advanced Computer Architecture
18
サンプル・コード
int i = 3;
do {
i--;
} while (i > 0)
C ソース・コード
li
L0: sub
bgtz
r1 = 3
r1 = r1 - 1
r1 > 0, L0
アセンブリ・コード
Advanced Computer Architecture
19
分岐予測に基づいてフェッチ
li
L0: sub
bgtz
r1 = 2
r1 = r1 - 1
r1 > 0, L0
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
アセンブリ・コード
予測したパス (taken) に沿って
フェッチされた命令の列
Advanced Computer Architecture
論理 Reg の可逆的な更新
 Reg リネーミング

各命令のデスティネーションに1つずつ物理 Reg を割り当てる

すべての命令の結果が保存してある

書き潰される心配はない
 要は，マルチ・バージョンの管理：

最新のバージョンを読む

不要なバージョンを捨てる

ミス時には，適切なバージョンに戻す
20
Advanced Computer Architecture
論理 Reg の可逆的な更新
 データベース，ファイル・システムの回復 (recovery) に類似
 基本は：
1.
ロギング
2.
チェックポインティング
 ただし，対象は fault ではなく，予測ミス
21
Advanced Computer Architecture
1. ロギング
 リオーダ・バッファ (reorder buffer)：

論理 Reg に対する書き込みログを保存
 論理 Reg ファイル (logical register file)：

commit された書き込みログを書き出す
22
Advanced Computer Architecture
23
2. ロギング
論理 Reg ファイル
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
r1
r1
r1
r1
Src
r1
r1
r1
r1
r1
r1
命令ウィンドウ
r1
r31
r1
r1
r1
r1
2
1
0
-1
予測したパス (taken) に沿って
フェッチされた命令の列
リオーダ・バッファ
Advanced Computer Architecture
24
2. ロギング
論理 Reg ファイル
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
r1
r1
r1
r1
Src
r1
r1
r1
r1
r1
r1
命令ウィンドウ
r1
2
r31
r1
r1
r1
r1
2
1
0
-1
予測したパス (taken) に沿って
フェッチされた命令の列
リオーダ・バッファ
Advanced Computer Architecture
25
2. ロギング
論理 Reg ファイル
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
r1
r1
r1
r1
Src
r1
r1
r1
r1
r1
r1
r1
2
1
r31
r1
r1
r1
1
0
-1
命令ウィンドウ
予測したパス (taken) に沿って
フェッチされた命令の列
リオーダ・バッファ
Advanced Computer Architecture
1. ロギング
 最新のバージョンを読む

リオーダ・バッファから，順に探す

無ければ，論理 Reg ファイルを読む
 不要なバージョンを捨てる

分岐予測が確認されたら，論理 Reg ファイルに書き出す
 ミス時に，適切なバージョンに戻す

リオーダ・バッファのエントリを捨てる
26
Advanced Computer Architecture
2. チェックポインティング
 チェックポイント＝分岐ごとに，論理 Reg の内容をバックアップ
 予測ミス時に，対応するバックアップをレストア
 最適化：

論理 Reg 全体（64b x 64本？）ではなく，

Reg マップ・テーブル（５b x 32本）をバックアップ．
27
Advanced Computer Architecture
28
2. チェックポインティング
r1 p11
p12
p13
命令
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
Dst
li p11
sub p12
bgtz
sub p13
bgtz
Src
r31
p11
p12
p12
p13
命令ウィンドウ
Reg マップ・テーブル
p11
p12
p13
p14
予測したパス (taken) に沿って
フェッチされた命令の列
物理 Reg ファイル
Advanced Computer Architecture
29
2. チェックポインティング
p12
r1 p13
p14
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
p11
p12
p13
p14
Src
r31
p11
p12
p12
p13
p13
p14
命令ウィンドウ
Reg マップ・テーブル
p11
p12
p13
p14
予測したパス (taken) に沿って
フェッチされた命令の列
物理 Reg ファイル
Advanced Computer Architecture
30
2. チェックポインティング
p12
p13
r1 p14
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
p11
p12
p13
p14
Src
r31
p11
p12
p12
p13
p13
p14
命令ウィンドウ
Reg マップ・テーブル
p11
p12
p13
p14
予測したパス (taken) に沿って
フェッチされた命令の列
物理 Reg ファイル
Advanced Computer Architecture
31
2. チェックポインティング
p12
p13
p14
r1 p13
p11
p14
p12
li
L0: sub
bgtz
L0: sub
bgtz
L0: sub
bgtz
r1
r1
r1
r1
r1
r1
r1
=
=
>
=
>
=
>
2
r1
0,
r1
0,
r1
0,
- 1
L0
- 1
L0
- 1
L0
命令
Dst
li
sub
bgtz
sub
bgtz
sub
bgtz
p11
p12
p13
p14
Src
r31
p11
p12
p12
p13
p13
p14
命令ウィンドウ
Reg マップ・テーブル
p11
p12
p13
p14
2
1
0
-1
予測したパス (taken) に沿って
フェッチされた命令の列
物理 Reg ファイル
Advanced Computer Architecture
1. チェックポインティング
 最新のバージョンを読む

Reg マップ・テーブルの最新のバージョンを使用する
 不要なバージョンを捨てる（Reg マップ・テーブル）

分岐予測が確認されたら，対応するバージョンを捨てる
 不要なバージョンを捨てる（物理 Reg）

同一 Reg に上書きする命令が commit されたら，古いバージョン
を捨てる
 ミス時に，適切なバージョンに戻す

Reg マップ・テーブルを適切なバージョンに戻す
32
Advanced Computer Architecture
正確な割り込み

例外 (exception)

トラップ (trap)

割り込み (interruption)
 正確な割り込み (precise interruption)

例外を発生した命令

より前の命令はすべて完了，

以降の命令はすべて未実行
 分岐予測と類似
 ロギングが必要

すべての命令に対してバックアップを取るわけにはいかない
33
Advanced Computer Architecture
今日のまとめ
2015/10/1
Advanced Computer Architecture
レジスタ・リネーミング＋分岐予測
 投機的に実行し，予測ミス時に元に戻す
 「論理 Reg の可逆的な更新」
 要は，マルチ・バージョンの管理：

最新のバージョンを読む

不要なバージョンを捨てる

ミス時には，適切なバージョンに戻す
35
Advanced Computer Architecture
論理 Reg の可逆的な更新
 データベース，ファイル・システムの回復 (recovery) に類似
 基本は：
1.
ロギング
2.
チェックポインティング
 ただし，対象は fault ではなく，予測ミス
36
Advanced Computer Architecture
今後の予定
 次週

分岐予測器，トレース・キャッシュ
37

Download Report