計算機アーキテクチャ特論 後半第 2 回 アウトオブオーダー実行 Out-of-Order Execution 講師加藤真平 本資料は授業用です 無断で転載することを禁じます
前回の理解度クイズ 問 1 マルチコア (CMP) 化が進んだ理由を簡潔に述べよ 答え消費電力や発熱の問題により 単一プロセッサの動作周波数を上げることができなくなったため 複数のプロセッサコアを並べることで性能を改善するようになった 単一プログラムの命令レベル並列性 (ILP) を抽出することが限界を迎えたため 複数のプログラムからスレッドレベル並列性 (TLP) を抽出する方式が採用されるようになり マルチコアの効果が一層高くなった
前回の理解度クイズ 問 2 CMP と SMT が同一チップ上に混在するプロセッサアーキテクチャを 1 つ挙げよ 答え Intel Nehalem など
前回の理解度クイズ 問 3 CMP と SMT が同一チップ上に混在するプロセッサアーキテクチャを 1 つ挙げよ 答え Apple A6(iPhone 5) のアーキテクチャ Intel SandyBridge など
前回の理解度クイズ 問 4 VLIW や SMT に対する CMP の利点を簡潔に述べよ 答え VLIW や SMT はスレッドレベル並列性を利用するがハードウェア資源を共有するため スレッド間の資源競合が発生する CMU ではメモリ以外のハードウェア資源がコアごとに提供されるため スレッド間の資源競合が少ない
前回の理解度クイズ 問 5 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 3 4 r1 r5 r6 r8 2 5 6 r4 インオーダー実行 1 2 3 4 5 6 インオーダー実行 ( スーパースカラ方式 ) 1 アウトオブオーダー実行 1 2 3 4 5 6 3 5 2 6 4
アウトオブオーダー実行の概要 Fetch & Decode In-order Instruction pool Execute Out-of-order Commit In-order 命令フェッチと命令デコードはインオーダー 実行はアウトオブオーダー 結果の確定 ( レジスタに反映など ) はインオーダー
データ依存関係の問題 (1) r1 r5 / r4 /* 20 サイクルかかると仮定 */ (2) r3 r1 + r8 (3) r8 r5 + 1 (4) r3 r7-2 (5) r6 r6 + r7 1 5 2 < データハザード > RAW (Read after Write) WAR (Write after Read) WAW (Write after Write) 3 4 命令 (1) と (2) は RAW 命令 (2) と (3) は WAR 命令 (2) と (4) は 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 この 2 つは偽の依存関係である なぜなら 同じレジスタを使う必要ないのに アウトオブオーダー実行を阻害する
レジスタリネーミング (Resister Renaming) アーキテクチャ上のレジスタ (Architectural Resisters) ISAが使うレジスタ 物理レジスタ (Physical Resisters) プロセッサ内に含まれるレジスタユーザプログラムからは見えない 複数のアーキテクチャ上のレジスタを物理レジスタに割当て 命令が結果の書き込みを行う時 値を物理レジスタに書き込む命令がデータを読み込む必要がある時 同じアーキテクチャ上のレジスタに書き込みを行った最後の命令に割当てられた物理レジスタからデータを読み込む そのような命令がない場合はアーキテクチャ上のレジスタから直接読む命令の完了が確定する時 物理レジスタからアーキテクチャ上のレジスタにデータを移す
レジスタリネーミングの例 WAW WAW WAR (1) r1 mem1 r1 mem1 cycle 1 cycle 2 (2) r2 r2 + r1 r2 r2 + r1 WAR (3) r1 mem2 r1 mem2 (4) r3 r3 + r1 r3 r3 + r1 WAR (5) r1 mem3 r1 mem3 (6) r4 r5 + r1 r4 r5 + r1 (7) r5 2 r5 2 (8) r6 r5 + 2 r6 r5 + 2 利点 偽の依存性の排除レジスタ数の制限を排除
リザベーションステーション (Reservation Station) フェッチした命令を一時的にバッファし 全てのオペランドが揃うのを待ち合わせる機構 レジスタリネーミングではレジスタ名の代わりにリザベーションステーションの名前を使用 演算器 (FP 加算 FP 乗算など ) ごとに用意
Tomasulo のアルゴリズム
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
L.D L.D MUL.D SUB.D DIV.D ADD.D F6, 34(R2) F2, 45(R3) F0,F2, F4 F8, F2, F6 F10, F0, F6 F6, F8, F2 SUB.D DIV.D ADD.D MUL.D F2, F8, F10, F6, F0,F2, 45(R3) F2, 34(R2) F8, F6 F2 F4 F6 decode & register read or rename FP registers 0 1 01 0 1 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 34 R2 45 R3 0 1 2 3 1 0 0 0 1 2 3 1 0 LOAD/STORE 01 FP ADD 0 FP MUL/DIV
Tomasulo アルゴリズム ( 詳細 ) From Mem FP Op Queue Load Buffers FP Registers Load1 Load2 Load3 Load4 Load5 Load6 Store Buffers Add1 Add2 Add3 Mult1 Mult2 FP adders Reservation Stations FP multipliers To Mem Common Data Bus (CDB)
リザベーションステーション ( 詳細 ) 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 アルゴリズムの 3 ステージ ( 詳細 ) 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 0 FU
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 1 FU Load1
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 2 FU Load2 Load1
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 3 FU Mult1 Load2 Load1
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 4 FU Mult1 Load2 M(A1) Add1
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 5 FU Mult1 M(A2) M(A1) Add1 Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 6 FU Mult1 M(A2) Add2 Add1 Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 7 FU Mult1 M(A2) Add2 Add1 Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 8 FU Mult1 M(A2) Add2 (M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 9 FU Mult1 M(A2) Add2 (M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 10 FU Mult1 M(A2) Add2 (M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 11 FU Mult1 M(A2) (M-M+M(M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 12 FU Mult1 M(A2) (M-M+M(M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 13 FU Mult1 M(A2) (M-M+M(M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 14 FU Mult1 M(A2) (M-M+M(M-M) Mult2
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 MULTD M(A2) R(F4) Mult2 Yes DIVD M(A1) Mult1 Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 15 FU Mult1 M(A2) (M-M+M(M-M) Mult2
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 16 FU M*F4 M(A2) (M-M+M(M-M) Mult2
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 55 FU M*F4 M(A2) (M-M+M(M-M) Mult2
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 56 FU M*F4 M(A2) (M-M+M(M-M) Mult2
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) Register result status: Clock F0 F2 F4 F6 F8 F10 F12... F30 56 FU M*F4 M(A2) (M-M+M(M-M) Result
分岐の問題 分岐命令があるとその先の実行が不確定 分岐はおよそ 5 命令に 1 度現れる どうする? 例えば以下の場合 : (1) r1 r4 / r7 (2) r2 r2 + r1 (3) r3 r2-5 (4) beq r3,0,300 beq が Not Taken(NT) と予測できれば (5) r8 r8 + 1 命令 (5) は実行してもよい このように分岐の先を実行したい しかし もし命令 (5) を実行したあとに命令 (4) が Taken だった ( つまり予測が外れた ) らどうする?
投機実行 (Speculative Execution) 分岐予測したパスからの命令実行 分岐予測は外れる可能性もある 実装 分岐予測したパスからの命令をフェッチしてプール すべてのオペランドが確定した命令のみ実行可能 命令の確定 (Commit) は安全に 先行する全ての命令が確定した場合のみ命令の確定を許可 ( 命令の確定はインオーダーに行う ) 分岐命令の後に続く命令は その分岐命令が確定した場合のみ確定 分岐予測が外れたらすべての後続命令をフラッシュ
Speculative Execution WAW WAW WAR 投機実行の例 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) jmp cond L2 predicted taken to L2 (6)L2 r1 mem3 r1 mem3 (7) r4 r5 + r1 r4 r5 + r1 (8) r5 2 r5 2 (9) r6 r5 + 2 r6 r5 + 2 命令 (6) から (9) は投機的に実行 もし分岐予測が外れたら全ての命令をフラッシュ もし分岐命令 (5) がNot Takenと予測されたら? Not Takenと予測したほうのパスの命令を投機実行
リオーダバッファ (Reorder Buffer) 投機実行したものを分岐が確定 (commit) するまで溜めておく場所 リザベーションステーションとは異なり FIFO のように順番に予約解放 4 つのフィールド instruction type(branch, store, load, ALU) destination( 結果を書き込むレジスタ名 ) value( 投機実行結果 ) ready( 実行が終わっていることを示す )
Tomasulo アルゴリズムとリオーダバッファ
アウトオブオーダー実行の詳細 < 参考書 > ( 注 ) 本講義では詳細よりも概念に焦点を充てています
基本アウトオブオーダーのまとめ ストールを減らしてスループットを改善 命令の実行順序を動的に入れ替え 実行結果は不変 ( 当たり前 ) レジスタリネーミングにより WAR と WAW を解決 必要なデータがそろった命令から実行 投機実行により分岐命令の先も実行可能 命令の発行や確定はインオーダー
当日配布 理解度クイズ