Advanced Computer Architecture 03. スーパスカラ･プロセッサの基礎 五島 正裕 2019/1/18

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

Advanced Computer Architecture 1. スーパスカラ･プロセッサの歴史 2019/1/18

スーパスカラ･プロセッサの着想 命令パイプラインを 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 I4 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 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 add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB add r8 = r6 + r7 IF OR EX MEM WB add r8 = r8 + 1 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 スーパスカラ･プロセッサ 2019/1/18

スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 ウィンドウ 演算器 フロントエンド Front-end バックエンド Advanced Computer Architecture スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ 命令 ウィンドウ リネーム ロジック 演算器 フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB フロントエンド 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 今日のまとめ 2019/1/18

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

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

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

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