Advanced Computer Architecture 02. スーパースカラ･プロセッサの基礎 五島 正裕 2018/11/20

内容 前回までの復習 スーパースカラ･プロセッサの歴史 Out-of-Order スーパースカラ･プロセッサ 今回のまとめ Advanced Computer Architecture 内容 前回までの復習 スーパースカラ･プロセッサの歴史 Out-of-Order スーパースカラ･プロセッサ 今回のまとめ

Advanced Computer Architecture 1. 前回までの復習 RISCと命令パイプライン 2018/11/20

命令パイプライン I0 I1 I2 I3 I4 I5 IF ID EX MEM WB cycle I0 I1 I2 I3 I4 I5 IF Advanced Computer Architecture 命令パイプライン I0 I1 I2 I3 I4 I5 IF ID EX MEM WB cycle I0 IF ID EX MEM WB I1 IF ID EX MEM WB I2 IF ID EX MEM WB I3 IF ID EX MEM WB I4 IF ID EX MEM WB I5 IF ID EX MEM WB

パイプライン・ハザード パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 Advanced Computer Architecture パイプライン・ハザード パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 構造ハザード (structural hazard) HW の資源の不足が原因 非構造ハザード SW の持つ依存関係が原因 データ・ハザード (data hazard) データ依存 制御ハザード (control hazard) 制御依存，分岐命令の実行

インターロック と バブル パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 Advanced Computer Architecture インターロック と バブル パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 パイプライン・インターロック (interlock) 機構によって対処 パイプライン・バブル (bubble) が発生 「パイプラインが乱れる」

アーキテクチャ的対処 インターロックする ⇒ バブルが発生 ⇒ 性能低下 インターロックする機会を減らすことが重要！ 構造ハザード Advanced Computer Architecture アーキテクチャ的対処 インターロックする ⇒ バブルが発生 ⇒ 性能低下 インターロックする機会を減らすことが重要！ 構造ハザード 資源の不足が原因 資源の追加で消える 例えば，メモリ・ポートの場合， 命令キャッシュとデータ・キャッシュの分離 (separate) 非構造ハザード プログラムが原因 原理的に消えない バブルの削減

バブルの削減 （データ・ハザード） cycle add r4 = r1 + r2 add r5 = r4 + r3 add Advanced Computer Architecture バブルの削減 （データ・ハザード） cycle add r4 = r1 + r2 IF ID EX MEM WB add r5 = r4 + r3 IF ID EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB バイパス

IF 100 200 LD 1 2 10 100 5 ID EX 1000 210 MEM WB PC IR Rs Rt Reg File Advanced Computer Architecture IF 100 PC IR Rs 200 LD 1 2 10 100 5 ID Rt Reg File EX 1000 210 MEM DR MDR MA MD Main Memory WB

バイパスによる Forwarding 同じもの： オペランド・バイパス レジスタ・バイパス 結果 (result) バイパス Advanced Computer Architecture バイパスによる Forwarding 同じもの： オペランド・バイパス レジスタ・バイパス 結果 (result) バイパス （データ）フォワーディング (forwarding) 「フウォーディング」

Advanced Computer Architecture 2. スーパースカラ･プロセッサの歴史 2018/11/20

スーパースカラ･プロセッサの着想 命令パイプラインを n 本 並べて，n 命令ずつ実行したら… 「n –way スーパースカラ･プロセッサ」 Advanced Computer Architecture スーパースカラ･プロセッサの着想 命令パイプラインを n 本 並べて，n 命令ずつ実行したら… 「n –way スーパースカラ･プロセッサ」 プロセッサの分類： ベクトル (vector) ex) 地球シミュレータ，富士通 VR マイコン スカラ (scalar) スカラ (scalar) (n = 1) スーパースカラ (super-scalar) (n > 1)

スーパースカラの命令パイプライン I0 I1 I2 I3 I4 I5 IF ID EX MEM WB cycle I0 I1 I2 I3 Advanced Computer Architecture スーパースカラの命令パイプライン I0 I1 I2 I3 I4 I5 IF ID EX MEM WB cycle I0 IF ID EX MEM WB I1 IF ID EX MEM WB I2 IF ID EX MEM WB I3 IF ID EX MEM WB I4 IF ID EX MEM WB I5 IF ID EX MEM WB

IPC スカラ･プロセッサ（パイプライン･マシン）の性能 （性能）＝（クロック速度）÷（CPI） Advanced Computer Architecture IPC スカラ･プロセッサ（パイプライン･マシン）の性能 （性能）＝（クロック速度）÷（CPI） CPI (Cycles Per Instruction) 「1命令を実行するのに何サイクルかかるか」 スーパースカラ･プロセッサの性能 （性能）＝（クロック速度）×（IPC） IPC (Instructions Per Cycle) 「1サイクルに命令を何個 並列に実行できるか」 n –way なら， IPC は最大 n 性能は最大 n 倍！

データ・ハザード cycle add r4 = r1 + r2 add r5 = r4 + r3 add r4 = r1 + r2 add Advanced Computer Architecture データ・ハザード cycle add r4 = r1 + r2 IF ID EX MEM WB add r5 = r4 + r3 IF ID EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB r8 = r6 + r7 add IF OR EX MEM WB r8 = r8 + 1 add IF OR EX MEM WB

命令の実行順序 プログラム･オーダ (program order) ISA のセマンティクスが規定する，命令の逐次的な実行順序 Advanced Computer Architecture 命令の実行順序 プログラム･オーダ (program order) ISA のセマンティクスが規定する，命令の逐次的な実行順序 全順序 (total order) In-Order プログラム･オーダの逆順に処理することを許さない 「同時」までは In-Order Out-of-Order プログラム･オーダの逆順に処理することを許す

In-Order vs. Out-of-Order Advanced Computer Architecture In-Order vs. Out-of-Order In-Order : ex.) SPARC (esp. UltraSPARC) 簡単，クロック 高速 IPC 低 「最適化コンパイラでカバーできる」？ Out-of-Order : ex.) SPARC 以外 IPC 高 「複雑」，クロック 低速 インターロックの延長で Out-of-Order は極めて困難 （性能）＝ （クロック速度）× （IPC） 高性能なのはどっち？ 古い議論！

In-Order vs. Out-of-Order Advanced Computer Architecture In-Order vs. Out-of-Order 古い議論！ 「最適化コンパイラでカバーでき」なかった？ 少なくとも，商売上はダメだった（SW 遺産） クロックで差がつかなかった (esp. UltraSPARC) Out-of-Order の高効率な実装法 インターロックの延長で In-Order を実現するのも困難 「複雑」の意味 本講義： Out-of-Order の special case として In-Order を議論する

2. Out-of-Order スーパースカラ･プロセッサ Advanced Computer Architecture 2. Out-of-Order スーパースカラ･プロセッサ 2018/11/20

スーパースカラ･プロセッサの基本構造 RF 命令 ウィンドウ リネーム ロジック フロントエンド front-end バックエンド Advanced Computer Architecture スーパースカラ･プロセッサの基本構造 RF RF フェッチ幅 ディスパッチ幅 発行幅 命令 キャッシュ 命令 ウィンドウ リネーム 演算器 ロジック 発行 Issue ディスパッチ Dispatch フェッチ Fetch 実行 Exec 書戻 WB リネーム Rename スケジュール Schedule フロントエンド front-end バックエンド back-end

基本的なパラメタ ディスパッチ幅（＝フェッチ幅） 2～4命令/サイクル 発行幅 2～6命令/サイクル Advanced Computer Architecture 基本的なパラメタ ディスパッチ幅（＝フェッチ幅） 2～4命令/サイクル 発行幅 2～6命令/サイクル ディスパッチ幅 ＝ 発行幅なら，ウェイ数と言ってよい（？） 命令ウィンドウ･サイズ 16～32命令 ウェイ数の8倍？

命令スケジューリング add r4 = r1 + r2 add r5 = r4 + r3 sub r4 = r1 - r2 sla Advanced Computer Architecture 命令スケジューリング バックエンド： スケジュールされた命令を実際に実行 命令ウィンドウ 　（スケジューリング･ウィンドウ）： 命令をスケジュール ＝ 実行可能な命令を見つける 実行可能 ＝ 制約を満たす フロントエンド： 命令ウィンドウを下流に拡大 add r4 = r1 + r2 add r5 = r4 + r3 sub r4 = r1 - r2 sla r5 = r5 << 1 sla r4 = r1 << 2 add r5 = r5 + 1 bz r4

命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 「演算器など，計算資源が空いていなければ実行できない」 Advanced Computer Architecture 命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 「演算器など，計算資源が空いていなければ実行できない」 命令間の依存：「実行されるプログラム側の問題」 先行制約：命令間の先行関係の制約 制御依存 (control dependence) 「分岐命令があると，後の命令は先に実行できない」 データ依存 (data dependence) 「2つの命令が同一のロケーションを定義/参照していると， 　後の命令は先に実行できない」 パイプライン･ハザードと同じ だが 「どの命令にインターロックかけるか？」より，簡潔

データ依存 Write add r4 = r1 + r2 add r5 = r4 + r3 Read Advanced Computer Architecture データ依存 制御駆動型 (control-driven) （⇔ データ駆動，data-driven） 命令間のデータの授受は， プログラム･オーダ上で，先行/後続の関係にある2命令が， 同一のロケーションを参照する ことで表現 ロケーション：レジスタとメモリ Write add r4 = r1 + r2 add r5 = r4 + r3 Read

データ依存 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is Advanced Computer Architecture データ依存 後 続 命 令 Read Write 先行命令 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is time time Ip Ip Is Is time time

真のデータ依存，偽のデータ依存 フロー依存：真の (true) データ依存 データの授受のため 先行制約を生じる 入力依存 Advanced Computer Architecture 真のデータ依存，偽のデータ依存 フロー依存：真の (true) データ依存 データの授受のため 先行制約を生じる 入力依存 一般に，複数の読み出しがあるため 先行制約を生じない 逆依存，出力依存：偽の (false) データ依存 ロケーションの再利用のため 原理的には，先行制約を生じない リネーミングにより解消

リネーミングによる偽のデータ依存の解消 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Advanced Computer Architecture リネーミングによる偽のデータ依存の解消 後 続 命 令 Read Write 先行命令 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is time time Ip Ip Is Is time time

データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r1 = r1 << 2 Advanced Computer Architecture データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2

データ依存の具体例 ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = Advanced Computer Architecture データ依存の具体例 ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = add r4 = r1 + r2

データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r3 r1 = r1 Advanced Computer Architecture データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 逆依存 sla r3 r1 = r1 << 2 add r4 = r3 r1 + r2

リネーミングの真髄 データの寿命 r1 r2 r3 r4 ld r1 = *($sp) sla r1 << 1 = r2 sla Advanced Computer Architecture リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r1 << 1 = r2 sla r3 r1 = r1 << 2 定義 add r4 = r3 r1 + r2 参照 time 要は，「1つのデータに1つのロケーション」

リネーミングの真髄 データの寿命 r1 r2 r3 r4 ld r1 = *($sp) sla r1 << 1 = r2 sla Advanced Computer Architecture リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = r3 定義 add r2 = r4 + r3 参照 time 要は，「1つのデータに1つのロケーション」

理想リネーミングと無限のロケーション 「1つのデータに1つのロケーション」が理想だが… ロケーションが無限に必要！ 解決法は次回 Advanced Computer Architecture 理想リネーミングと無限のロケーション 「1つのデータに1つのロケーション」が理想だが… ロケーションが無限に必要！ 解決法は次回

レジスタ･リネーミングとデータ依存 リネーミングは，メモリにも適用可能 だが… 以降しばらくはレジスタに関して Advanced Computer Architecture レジスタ･リネーミングとデータ依存 リネーミングは，メモリにも適用可能 だが… 以降しばらくはレジスタに関して メモリ ―― ロードとストアの依存に関しては，そのうち… 偽の依存：逆依存，出力依存 レジスタ･リネーミングで解消 真の依存：フロー依存 レジスタ･リネーミングで簡単

レジスタ･リネーミングとフロー依存 「1つのデータに1つのロケーション（レジスタ）」 「1つの命令（のデスティネーション）に1つのレジスタ」 Advanced Computer Architecture レジスタ･リネーミングとフロー依存 「1つのデータに1つのロケーション（レジスタ）」 「1つの命令（のデスティネーション）に1つのレジスタ」 1つの命令のデスティネーションは普通1つだから データと命令は同一視してよい

レジスタ･リネーミングとフロー依存 各命令のデスティネーションに割り当てるとき， レジスタは「空 (empty)」にしておく Advanced Computer Architecture レジスタ･リネーミングとフロー依存 各命令のデスティネーションに割り当てるとき， レジスタは「空 (empty)」にしておく 命令が実行され，結果が書かれたら， レジスタは「一杯 (full)」 になる フロー依存による先行制約を満たす ＝ 依存元の命令が実行されたら，依存先の命令を実行する ソースが full になったら，実行する

レジスタ･リネーミングとフロー依存 ld r1 = *($sp) r1 sla r2 = r1 << 1 r2 r3 sla Advanced Computer Architecture レジスタ･リネーミングとフロー依存 ld r1 = *($sp) r1 sla r2 = r1 << 1 r2 r3 sla r3 = r1 << 2 r4 add r4 = r3 + r2

Advanced Computer Architecture 今日のまとめ 2018/11/20

スーパースカラ･プロセッサの基本構造 基本構造 フロントエンド 命令ウィンドウ バックエンド 命令スケジューリング： Advanced Computer Architecture スーパースカラ･プロセッサの基本構造 基本構造 フロントエンド 命令ウィンドウ バックエンド 命令スケジューリング： 命令ウィンドウ内から，実行可能な命令を見つける 実行可能 ＝ 制約を満たす

命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 命令間の依存：「実行されるプログラム側の問題」 Advanced Computer Architecture 命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 命令間の依存：「実行されるプログラム側の問題」 先行制約：命令間の先行関係の制約 制御依存 データ依存 パイプライン･ハザードと同じ だが， 「どの命令にインターロックかけるか？」より，簡潔

データ依存 と レジスタ･リネーミング レジスタ･リネーミング： 「1つの命令に1つのレジスタ」 偽の依存：逆依存，出力依存 Advanced Computer Architecture データ依存 と レジスタ･リネーミング レジスタ･リネーミング： 「1つの命令に1つのレジスタ」 偽の依存：逆依存，出力依存 リネーミングで解消 真の依存：フロー依存 リネーミングで簡単 レジスタが「空 (empty)」⇒「一杯 (full)」になったら実行

Advanced Computer Architecture 次回 レジスタ･リネーミングの実際 レジスタは無限にはない 制御依存 分岐予測

クロック速度と IPC クロック速度 と IPC はトレードオフ? “Speed Demon vs. Brainiac” Advanced Computer Architecture クロック速度と IPC クロック速度 と IPC はトレードオフ? “Speed Demon vs. Brainiac” AMD Athlon XP 2000＋ (1.67GHz) Intel Pentium 4 2GHz と同等の性能（？） 2/1.67 = 1.20 倍の IPC