計算機アーキテクチャ特論
後半第２回
アウトオブオーダー実行
Out-of-Order Execution
講師 加藤真平
本資料は授業用です。無断で転載することを禁じます。
前回の理解度クイズ
問１
マルチコア（CMP）化が進んだ理由を簡潔に述べよ。
答え
消費電力や発熱の問題により、単一プロセッサの動作
周波数を上げることができなくなったため、複数のプロ
セッサコアを並べることで性能を改善するようになった。
単一プログラムの命令レベル並列性（ILP）を抽出するこ
とが限界を迎えたため、複数のプログラムからスレッド
レベル並列性（TLP）を抽出する方式が採用されるように
なり、マルチコアの効果が一層高くなった。
前回の理解度クイズ
問２
CMPとSMTが同一チップ上に混在するプロセッサアーキ
テクチャを１つ挙げよ。
答え
Intel Nehalemなど
前回の理解度クイズ
問３
CMPとSMTが同一チップ上に混在するプロセッサアーキ
テクチャを１つ挙げよ。
答え
Apple A6（iPhone 5）のアーキテクチャ
Intel SandyBridgeなど
前回の理解度クイズ
問４
VLIWやSMTに対するCMPの利点を簡潔に述べ
よ。
答え
VLIWやSMTはスレッドレベル並列性を利用する
がハードウェア資源を共有するため、スレッド間
の資源競合が発生する。CMUではメモリ以外の
ハードウェア資源がコアごとに提供されるため、
スレッド間の資源競合が少ない。
前回の理解度クイズ
問５
CMPに対するGPUやMICの利点を簡潔に述べよ。
答え
並列度（コア数）を極端に増やすことで、プログ
ラムがうまく並列化できれば電力あたりの性能
を大きく改善できる。
今後の予定
第1回 11月19日（月）
第2回 11月26日（月）
12月3日（月） 休講（出張）
12月10日（月） 休講（工場見学引率）
第3回 12月17日（月）
12月24日（月） 祝日
第4回 12月25日（火） 24日の振替
第5回 1月8日（木）9日（金） 時間は追って連絡
1月14日（月） 祝日
第6回 1月21日（月）
第6回 1月28日（月） 試験期間
今日の講義
• パイプライン処理の実行方式
– インオーダー（In-Order）
– アウトオブオーダー（Out-of-Order）
(1)
r1
r4 / r7
/* 20サイクルかかると仮定 */
(2)
r8
r1
+ r2
(3)
r5
r5 + 1
(4)
r6
r6 - r3
(5)
r4
r5
+
r6
(6) r7
r8
*
r4
インオーダーとアウトオブオーダー
1
2
3
4
5
6
インオーダー実行
1
3
4
5
2
6
アウトオブオーダー実行
1
3
4
5
2
6
インオーダー実行（スーパースカラ方式）
1
3
4
2
5
6
r1
r5
r6
r4
r8
アウトオブオーダー実行の概要
Fetch &
Decode
Instruction
pool
Commit
In-order
In-order
Execute
Out-of-order
命令フェッチと命令デコードはインオーダー
実行はアウトオブオーダー
結果の確定（レジスタに反映など）はインオーダー
データ依存関係の問題
(1)
r1
r5 / r4
/* 20サイクルかかると仮定 */
(2)
r3
r1
+
r8
(3)
r8
r5 + 1
(4)
r3
r7 - 2
(5)
r6
r6 + r7
1
3
4
2
5
＜データハザード＞
RAW (Read after Write)
WAR (Write after Read)
WAW (Write after Write)
命令（１）と（２）はRAW
命令（２）と（３）はWAR
命令（２）と（４）はWAW
偽の依存性
（False Dependency）
＝“Write after”依存関係（WARとWAW）
WAR
(1) r3
r2
+ r1
(2)
r2
r4 + 3
WAW
(1)
r3
r1 + r2
(2)
r3
r4 + 3
この２つは偽の依存関係である。なぜなら、
同じレジスタを使う必要ないのに、
アウトオブオーダー実行を阻害する。
レジスタリネーミング
（Resister Renaming）
アーキテクチャ上のレジスタ（Architectural Resisters）
ISAが使うレジスタ
物理レジスタ（Physical Resisters）
プロセッサ内に含まれるレジスタ
ユーザプログラムからは見えない
複数のアーキテクチャ上のレジスタを物理レジスタに割当て
命令が結果の書き込みを行う時
値を物理レジスタに書き込む
命令がデータを読み込む必要がある時
同じアーキテクチャ上のレジスタに書き込みを行った最後の命令に割当
てられた物理レジスタからデータを読み込む
そのような命令がない場合はアーキテクチャ上のレジスタから直接読む
命令の完了が確定する時
物理レジスタからアーキテクチャ上のレジスタにデータを移す
レジスタリネーミングの例
cycle 1 cycle 2
(1)
r1
mem1
r1’
mem1
(2) r2
r2 +
r1
r2’
r2 + r1’
(3)
r1
mem2
r1”
mem2
(4) r3
r3 +
r1
r3’
r3 + r1”
(5)
r1
mem3
r1”’
mem3
(6) r4
r5
+ r1
r4’
r5 + r1”’
(7)
r5
2
r5’
2
(8) r6
r5 + 2
r6’
r5’ + 2
利点
偽の依存性の排除
レジスタ数の制限を排除
WAW WAW WAR WAR WARリザベーションステーション
（Reservation Station）
フェッチした命令を一時的にバッファし、全て
のオペランドが揃うのを待ち合わせる機構
レジスタリネーミングではレジスタ名の代わり
にリザベーションステーションの名前を使用
演算器（FP加算、FP乗算など）ごとに用意
Tomasuloのアルゴリズム
命令発行
リザベーションステーションを予約
書込み先レジスタをそのリザベーションステーション番号でリネーム
オペランドがレジスタに格納されている場合
命令とオペランドを リザベーションステーションへ送る
オペランドが揃っていない場合
命令と リネームされたレジスタ名をリザベーションステーションへ送る
命令実行
オペランドが揃った命令から発行
リザベーションステーション番号を付けて実行ステージへ移る
ロードとストアの問題
リザベーションステーションはアドレスの競合
を解決しない
アウトオブオーダー実行できない
ロードとストアはインオーダー実行
アドレス計算はアウトオブオーダー実行
リザベーションステーションの状態変化
次のコードを仮定
L.D
F6, 34(R2)
L.D
F2, 45(R3)
MUL.D
F0,F2, F4
SUB.D
F8, F2, F6
DIV.D
F10, F0, F6
ADD.D
F6, F8, F2
FP ADD
FP MUL/DIV
LOAD/STORE
decode &
register read
or rename
FP registers 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 L.D F6, 34(R2) 0 L.D F2, 45(R3) 1 MUL.D F0,F2, F4 0 1 34 R2 45 R3 0 SUB.D F8, F2, F6L.D
F6, 34(R2)
L.D
F2, 45(R3)
MUL.D
F0,F2, F4
SUB.D
F8, F2, F6
DIV.D
F10, F0, F6
ADD.D
F6, F8, F2
1 0 0 DIV.D F10, F0, F6 0 1 1 ADD.D F6, F8, F2 0 1 0Tomasuloアルゴリズム（詳細）
FP adders
Add1 Add2 Add3FP multipliers
Mult1 Mult2From Mem
FP Registers
Reservation
Stations
Common Data Bus (CDB)
To Mem
FP Op
Queue
Load Buffers
Store
Buffers
Load1 Load2 Load3 Load4 Load5 Load6リザベーションステーション（詳細）
Op:
Operation to perform in the unit (e.g., + or –)
Vj, Vk:
Value
of Source operands
– Store buffers has V field, result to be stored
Qj, Qk:
Reservation stations producing source registers (value to be
written)
– Note: No ready flags as in Scoreboard; Qj,Qk=0 => ready
– Store buffers only have Qi for RS producing result
Busy:
Indicates reservation station or FU is busy
Register result status
—Indicates which functional unit will write each
register, if one exists. Blank when no pending instructions that will
write that register.
Tomasuloアルゴリズムの３ステージ
（詳細）
1. Issue
—get instruction from FP Op Queue
If reservation station free (no structural hazard),
control issues instr & sends operands (renames registers).
2. Execute
—operate on operands (EX)
When both operands ready then execute;
if not ready, watch Common Data Bus for result
3. Write result
—finish execution (WB)
Write on Common Data Bus to all awaiting units;
mark reservation station available
• Normal data bus: data + destination (“go to” bus)
• Common data bus
: data +
source
(“
come from
” bus)
– 64 bits of data + 4 bits of Functional Unit
source
address
– Write if matches expected Functional Unit (produces result)
– Does the broadcast
Tomasulo例題
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 Load1 No LD F2 45+ R3 Load2 No MULTD F0 F2 F4 Load3 No SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No Mult2 No
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo Example Cycle 1
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 Load1 Yes 34+R2 LD F2 45+ R3 Load2 No MULTD F0 F2 F4 Load3 No SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No Mult2 No
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 2
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 Load1 Yes 34+R2 LD F2 45+ R3 2 Load2 Yes 45+R3 MULTD F0 F2 F4 Load3 No SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No Mult2 No
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 3
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 Load1 Yes 34+R2 LD F2 45+ R3 2 Load2 Yes 45+R3 MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 Yes MULTD R(F4) Load2
Mult2 No
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 4
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 Load2 Yes 45+R3 MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 DIVD F10 F0 F6 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 Yes SUBD M(A1) Load2
Add2 No
Add3 No
Mult1 Yes MULTD R(F4) Load2
Mult2 No
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 5
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 DIVD F10 F0 F6 5 ADDD F6 F8 F2
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
2 Add1 Yes SUBD M(A1) M(A2)
Add2 No
Add3 No
10 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 6
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
1 Add1 Yes SUBD M(A1) M(A2)
Add2 Yes ADDD M(A2) Add1
Add3 No
9 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 7
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
0 Add1 Yes SUBD M(A1) M(A2)
Add2 Yes ADDD M(A2) Add1
Add3 No
8 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 8
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
2 Add2 Yes ADDD (M-M) M(A2)
Add3 No
7 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 9
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
1 Add2 Yes ADDD (M-M) M(A2)
Add3 No
6 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 10
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
0 Add2 Yes ADDD (M-M) M(A2)
Add3 No
5 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 11
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
4 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 12
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
3 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 13
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
2 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 14
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
1 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 15
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 15 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
0 Mult1 Yes MULTDM(A2) R(F4)
Mult2 Yes DIVD M(A1) Mult1
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 16
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 15 16 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No
40 Mult2 Yes DIVD M*F4 M(A1)
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 55
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 15 16 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No
1 Mult2 Yes DIVD M*F4 M(A1)
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 56
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 15 16 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 56 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No
0 Mult2 Yes DIVD M*F4 M(A1)
Register result status:
Clock
F0
F2
F4
F6
F8
F10
F12
...
F30
Tomasulo例題 Cycle 57
Instruction status:
Exec
Write
Instruction j k
Issue Comp Result
Busy Address
LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MULTD F0 F2 F4 3 15 16 Load3 No SUBD F8 F6 F2 4 7 8 DIVD F10 F0 F6 5 56 57 ADDD F6 F8 F2 6 10 11
Reservation Stations:
S1
S2
RS
RS
Time Name
Busy
Op
Vj
Vk
Qj
Qk
Add1 No
Add2 No
Add3 No
Mult1 No
Mult2 Yes DIVD M*F4 M(A1)
