高性能コンピューティング論２ 1 高性能コンピューティング論２ 第３回 スーパスカラプロセッサ 高性能コンピューティング学講座 三輪 忍 [email protected] 高性能コンピューティング論２ 本日の講義内容 • 復習： 命令パイプライン • スーパスカラプロセッサ • Out-of-Order スーパスカラプロセッサ 2 高性能コンピューティング論２ 復習： 命令パイプライン 3 高性能コンピューティング論２ 命令パイプライン • 命令の実行フェーズ： ５フェーズ • IF： 命令フェッチ • ID： 命令デコード/レジスタ読み出し • EX： 実行 • MEM： メモリアクセス • WB： レジスタ書き戻し • 命令パイプライン • 各フェーズを流れ作業で処理 • スループット（単位時間ああたりの実行命令数）の向上 4 高性能コンピューティング論２ 5 命令パイプラインの表現 IF IF ID EX MEM WB cycle ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より 高性能コンピューティング論２ 6 パイプライン・ハザード • パイプライン・ハザード (hazard)： • パイプライン動作を妨げる要因 • 分類： 1. 構造ハザード (structural hazard)： ハードウェアの資源不足が原因 2. 非構造ハザード： ソフトウェア内の依存関係が原因 a. b. データ・ハザード (data hazard)： 制御ハザード (control hazard)： データ依存 制御依存，i.e. 分岐命令の実行 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より 高性能コンピューティング論２ 7 構造ハザードの例 • メモリのポートの不足 cycle IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM IF ID EX ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より W M 高性能コンピューティング論２ 8 データ・ハザード • 命令間のデータ依存 cycle add r4 = r1 + r2 add r5 = r4 + r3 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より 高性能コンピューティング論２ 9 制御ハザード • 分岐命令の実行 cycle IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より 高性能コンピューティング論２ ハザードに対する一般的な対処 • 対処： • パイプライン・インターロック (interlock) 「止める機構」 • パイプライン・ストール (stall) 「止まる現象」 • パイプライン・バブル (bubble) が発生 • 「パイプラインが乱れる」 • その結果，性能が低下 10 高性能コンピューティング論２ 11 ハザードへのアーキテクチャ的対処 • 方針： インターロック，ストールする機会を減らす • インターロック，ストールするとバブルが発生し，性能が低下 • 構造ハザード • 資源の不足が原因 • 資源の追加で消える • 非構造ハザード • プログラムが原因 • 原理的に消えない • バブルの削減 高性能コンピューティング論２ スーパスカラプロセッサ 12 高性能コンピューティング論２ スーパスカラプロセッサ • スーパスカラプロセッサ • 命令パイプラインを n 本並べて n 命令ずつ実行 • （理想的には）スループット n 倍 • n=1 の時： スカラプロセッサ • ベクトルプロセッサとの違い • ベクトル • 1つの命令が複数データに対して演算を並列に実行 • 例） 地球シミュレータ • スーパスカラ • 複数命令が演算を並列に実行 • 例） Core, Xeon (Intel), Cortex-A7以降 (ARM) など多数 13 高性能コンピューティング論２ 14 スーパスカラの命令パイプライン I0 I2 IF I3 ID EX MEM WB I1 cycle I0 I1 I2 I3 I4 I5 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 15 スーパスカラプロセッサとハザード cycle [ スカラプロセッサの場合 ] add r4 = r1 + r2 IF add r5 = r4 + r3 OR IF EX OR MEM WB EX MEM WB [ スーパスカラプロセッサの場合 ] add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB • 同時にフェッチされた命令間に依存関係が存在すると，命令 を同時に実行できない（＝スループットの低下） 高性能コンピューティング論２ 命令の実行順序 16 順序① I0: r4 = r1 + r2 • プログラム･オーダ (program order) • 実行バイナリに記載された命令の処理順序 • コンパイラによって決定された順序 • In-Order • プログラム･オーダの逆順に処理することを許さない • 「同時」までは In-Order • Out-of-Order • プログラム･オーダの逆順に処理することを許す I1: r5 = r4 + r3 I2: r8 = r6 + r7 I3: r8 = r8 + 1 順序② I0: r4 = r1 + r2 I2: r8 = r6 + r7 I1: r5 = r4 + r3 I3: r8 = r8 + 1 • 順序①と②の実行結果 はどちらも同じ • コンパイラは，同一の 実行結果となる順序の 中からある順序を選択 高性能コンピューティング論２ 17 Out-of-Order スーパスカラプロセッサ cycle [ In-Order スーパスカラプロセッサの場合 ] add r4 = r1 + r2 IF 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 OR EX プログラム・ オーダを遵守 MEM WB [ Out-of-Order スーパスカラプロセッサの場合 ] add r4 = r1 + r2 IF add r5 = r4 + r3 IF add r8 = r6 + r7 IF add r8 = r8 + 1 IF OR EX MEM WB OR OR EX EX MEM WB MEM WB OR EX プログラム・ オーダを無視 MEM WB • 依存関係のない命令をハードウェアが検出 • プログラム・オーダを無視して実行可能な命令から実行 高性能コンピューティング論２ 18 In-Order か？ Out-of-Order か？ • 性能： Out-of-Order ＞ In-Order • 命令パイプラインの数が同じなら，Out-of-Order の方が 1.X～ 倍高速 • ただし，n 倍速くなることはほとんどない • プログラム・オーダのままでも同時に実行できる命令が存在 • 並び変えても実行できない命令は存在 • エネルギ効率： In-Order ＞ Out-of-Order • 命令パイプラインの数が同じなら，In-Order の方が数倍 低消費電力 • Out-of-Order スーパスカラプロセッサには，Out-of-Order 実行のための複 雑なハードウェア（消費電力：大）が必要なため • 性能を重視する（ハイエンド）か，エネルギを重視する（組込み）か によって使い分け 高性能コンピューティング論２ 19 Out-of-Order スーパスカラ プロセッサ 高性能コンピューティング論２ 20 スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ リネーム ロジック 命令キュー フェッチ Fetch リネーム Rename ディスパッチ スケジュール Dispatch Schedule フロントエンド Front-end 演算器 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB バックエンド Back-end ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 21 基本的なパラメタ • ディスパッチ幅（＝フェッチ幅） • 2～4命令/サイクル • 発行幅 • 2～6命令/サイクル • ウェイ数 古い概念！ • 「ディスパッチ幅＝発行幅」な プロセッサの幅 • 最近のプロセッサはほとんどが 「発行幅 ＞ ディスパッチ幅」 • 命令ウィンドウ･サイズ • 16～32命令 • 発行幅の8倍？ [ ARM Cortex-A15 アーキテクチャのブロック図 ] （http://www.extremetech.com/computing/139393-arm-cortexa15-explained-intels-atom-is-down-but-not-out より） 高性能コンピューティング論２ 22 命令スケジューリング • 命令スケジューリング • 命令キューの中から実行可能な命令を発見 • 実行可能 ＝ 制約（次スライド）を満たす • 実行可能な命令の中から次に実行すべき命令を選択 add r4 = r1 + r2 • バックエンド： add r5 = r4 + r3 • スケジュールされた命令を実際に実行 • 命令ウィンドウ （スケジューリング･ウィンドウ）： • スケジュール対象の命令の集合 • 命令キュー内の全命令 • フロントエンド： • 命令ウィンドウを下流に拡大 命令ウィンドウ add r8 = r6 + r7 add r8 = r8 + 1 sub r5 = r5 – r8 bz r5 高性能コンピューティング論２ 23 命令スケジューリングの制約 • 計算資源 ：「実行するハードウエア側の問題」 • 「演算器など，計算資源が空いていなければ実行できない」 • 命令間の依存：「実行されるプログラム側の問題」 • 先行制約：命令間の先行関係の制約 • 制御依存 (control dependence) • 「分岐命令があると，後の命令は先に実行できない」 • データ依存 (data dependence) • 「2つの命令が同一のロケーションを定義/参照していると， 後の命令は先に実行できない」 • パイプライン･ハザードと同じ だが • 「どの命令にインターロックかけるか？」より，簡潔 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 24 データ依存 • 制御駆動型 (control-driven) （⇔ データ駆動，data-driven） • 命令間のデータの授受は， • プログラム･オーダ上で，先行/後続の関係にある2命令が， • 同一のロケーションを参照する ことで表現 • ロケーション：レジスタとメモリ Write add r4 = r1 + r2 add r5 = r4 + r3 Read ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 25 データ依存 後続命令 Read Read Ip Ip Is Is time 先 行 命 令 Write time 入力依存 (input) 逆依存 (anti) Write Ip Ip Is Is time time フロー依存 (flow) 出力依存 (output) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 26 真のデータ依存，偽のデータ依存 • フロー依存：真の (true) データ依存 • データの授受のため • 先行制約を生じる • 入力依存 • 一般に，複数の読み出しがあるため • 先行制約を生じない • 逆依存，出力依存：偽の (false) データ依存 • ロケーションの再利用のため • 原理的には，先行制約を生じない • リネーミングにより解消 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 27 リネーミングによる偽のデータ依存の解消 後続命令 Read Read Ip Ip Is Is time 先 行 命 令 Write time 入力依存 (input) 逆依存 (anti) Write Ip Ip Is Is time time フロー依存 (flow) 出力依存 (output) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 28 データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 29 データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r1 = r1 << 2 add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 30 データ依存の具体例 ld r1 = sla r2 = *($sp) r1 << 1 逆依存 sla r1 r3 = r1 << 2 add r4 = r1 + r2 r3 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 31 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r1 r3 = r1 << 2 定義 add r4 = r3 r1 + r2 参照 time • 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 32 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r3 = r1 << 2 定義 add r4 = r3 + r2 参照 time • 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 33 理想リネーミングと無限のロケーション • 「1つのデータに1つのロケーション」が理想だが… • ロケーションが無限に必要！ • 解決法は次回 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 34 レジスタ･リネーミングとデータ依存 • リネーミングは，メモリにも適用可能 だが… • 以降しばらくはレジスタに関して • メモリ ―― ロードとストアの依存に関しては，そのうち… • 偽の依存：逆依存，出力依存 • レジスタ･リネーミングで解消 • 真の依存：フロー依存 • レジスタ･リネーミングで簡単 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 35 レジスタ･リネーミングとフロー依存 • 「1つのデータに1つのロケーション（レジスタ）」 • 「1つの命令（のデスティネーション）に1つのレジスタ」 • 1つの命令のデスティネーションは普通1つだから • データと命令は同一視してよい ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 36 レジスタ･リネーミングとフロー依存 • 各命令のデスティネーションに割り当てるとき， • レジスタは「空 (empty)」にしておく • 命令が実行され，結果が書かれたら， • レジスタは「一杯 (full)」 になる • フロー依存による先行制約を満たす ＝ • 依存元の命令が実行されたら，依存先の命令を実行する • ソースが full になったら，実行する ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 37 レジスタ･リネーミングとフロー依存 ld r1 = *($sp) sla r2 = r1 << 1 sla r3 = r1 << 2 add r4 = r3 + r2 r1 r2 r3 r4 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より ピ ュ ー テ ィ ン グ 論 ２ 38 本日のまとめ 高性能コンピューティング論２ まとめ • 復習： 命令パイプライン • スーパスカラプロセッサ • Out-of-Order スーパスカラプロセッサ 39 高性能コンピューティング論２ 次回 • 10/5（木） 10:40～ • 「投機」について解説 40
© Copyright 2024 ExpyDoc
