高性能コンピューティング学講座 三輪 忍 miwa@is.uec.ac.jp 高性能コンピューティング論２ 高性能コンピューティング論２ 第4回 投機 高性能コンピューティング学講座 三輪　忍 miwa@is.uec.ac.jp

高性能コンピューティング論２ 本日の講義内容 スーパスカラプロセッサとバブル 投機

高性能コンピューティング論２ スーパスカラプロセッサとバブル

パイプライン・ハザード パイプライン・ハザード (hazard)： 分類： パイプライン動作を妨げる要因 * 高性能コンピューティング論２ 07/16/96 パイプライン・ハザード パイプライン・ハザード (hazard)： パイプライン動作を妨げる要因 分類： 構造ハザード (structural hazard) ハードウェアの資源不足が原因 ハードウェア資源の追加により解消可能 非構造ハザード ソフトウェア内の依存関係が原因 原理的に解消不可能 *

非構造ハザード データ・ハザード 制御ハザード 命令間のデータ依存 分岐命令の実行 cycle add r4 = r1 + r2 add * 高性能コンピューティング論２ 07/16/96 非構造ハザード データ・ハザード 命令間のデータ依存 制御ハザード 分岐命令の実行 cycle IF ID EX MEM WB add r4 = r1 + r2 IF ID EX MEM WB ID add r5 = r4 + r3 cycle IF ID EX MEM WB BE IF ID EX MEM WB IF I1 *

分岐命令 C ソース アセンブリ s = 0; for (i = 1; i <= 10; ++i) s = s + i; 高性能コンピューティング論２ 分岐命令 C ソース アセンブリ s = 0; for (i = 1; i <= 10; ++i) s = s + i; set r1 = 0; # s = 0; set r2 = 1; # i = 1; set r3 = 11; LOOP: beq r2 == r3, EXIT; add r1 = r1 + r2; add r2 = r2 + 1; b LOOP; EXIT: ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

条件分岐命令 if (cond) PC = PC + immediate; op Rs Rt immediate 高性能コンピューティング論２ 条件分岐命令 if (cond) PC = PC + immediate; PC 相対 (relative) 命令だけから（レジスタを読まなくても）飛び先アドレスが計算できる op Rs Rt immediate 31 25 20 15 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

条件分岐 branch on register compare & branch 分岐 条件 1つのレジスタ値が， 0，正，負， 高性能コンピューティング論２ 条件分岐 branch on register compare & branch 分岐 条件 1つのレジスタ値が， 0，正，負， 0 以上，0 以下 2つの値（レジスタ値，即値）の一致比較 2つの値（レジスタ値，即値）の大小比較 R[Rs] == 0, R[Rs] > 0, … R[Rs] == R[Rt], R[Rs] != R[Rt], R[Rs] == imm, R[Rs] != imm R[Rs] > R[Rt], R[Rs] >= R[Rt], 判定に 必要な 処理 レジスタの読み出し 一致比較 大小比較（減算） 備考 レジスタに，ｚero フラグを付加しておくと楽． signフラグは msb． 一部の RISC は持つ RISC は普通持たない ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

IF 100 LD 1 2 10 100 200 ID 5 1000 210 EX MEM WB IR PC Rs Rt Reg File 高性能コンピューティング論２ IF 100 IR PC Rs LD 1 2 10 100 200 ID Rt 5 Reg File 1000 210 EX DR MEM MA MD Main Memory WB MDR ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

バブルの量とバックエッジ長 バックエッジ バブルの量 ＝ バックエッジ長 逆向きの信号の流れ cycle be I1 IF ID EX 高性能コンピューティング論２ バブルの量とバックエッジ長 バックエッジ 逆向きの信号の流れ バブルの量 ＝ バックエッジ長 cycle IF ID EX MEM WB be IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB I1

バブルの削減（制御ハザード） cycle I0 be I1 I0 be I1 be I0 遅延分岐 I1 OR : Operand Read * 高性能コンピューティング論２ 07/16/96 バブルの削減（制御ハザード） cycle I0 IF ID EX MEM WB be IF ID EX MEM WB I1 IF ID EX MEM WB I0 IF OR EX MEM WB OR : Operand Read be IF OR 　EX MEM WB nPC : next PC 選択 nPC I1 IF OR EX MEM WB be IF OR EX MEM WB nPC I0 IF OR EX MEM WB 遅延分岐 I1 IF OR EX MEM WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より *

遅延分岐とスーパスカラプロセッサ 遅延分岐 スーパスカラプロセッサ（＝ローエンドではないプロセッサ） における遅延分岐 * 高性能コンピューティング論２ 07/16/96 遅延分岐とスーパスカラプロセッサ 遅延分岐 「分岐命令の遅延スロットに置かれた命令は（分岐の成立/不成立にかかわらず）必ず実行」 遅延スロット（分岐命令の次の命令）を埋めた分だけ性能向上 埋まらなかった分だけ nop が増加 スーパスカラプロセッサ（＝ローエンドではないプロセッサ） における遅延分岐 分岐に関するバックエッジ長は， 最近は10ステージ前後 埋める必要のある遅延スロットが 多すぎて非現実的 [ Intel社 Silvermont アーキテクチャの命令パイプライン ] （http://www.tomshardware.com/reviews/atom-silvermont-architecture, 3499-2.html より） *

スーパスカラプロセッサにおけるバブル 制御ハザード データ・ハザード L1データ・キャッシュにヒットする場合 高性能コンピューティング論２ スーパスカラプロセッサにおけるバブル 命令フェッチ デコード リネーム/スケジュール 実行 制御ハザード データ・ハザード L1データ・キャッシュにヒットする場合 L1データ・キャッシュにミスする場合 L1データ・キャッシュ L2データ・キャッシュ リタイア/コミット cycle I0 be I1 I2 cycle I0 ld r1 = *(r4) add r3 = r1 + r2 I1 cycle I0 ld r1 = *(r4) add r3 = r1 + r2 I1

なぜパイプライン・ステージを増やすのか？ 高性能コンピューティング論２ なぜパイプライン・ステージを増やすのか？ cycle ステージを増やして周波数向上 　　　スループット向上 その反面，バブルは増加 　　　バブルを削減する技術の重要性も増加 スーパスカラ化とは独立した技術 スループット向上を目指した結果， 　　　「スーパスカラ ＋ 多段パイプライン」 　になった 多段？ これでも一時期に比べれば段数が減った（2005年頃は31段） ここ数年は10数段に落ち着いている（消費電力の壁） be I0 I1 ステージ数 x2 周波数 x2 cycle be I0 I1

高性能コンピューティング論２ 投機

投機 投機的実行 (speculative execution) 投機 (speculation)： この分野の投機： 高性能コンピューティング論２ 投機 投機的実行 (speculative execution) 投機 (speculation)： 偶然の利益をねらって行う行為。 将来の価格変動を予想して、価格差から生ずる利益を得ることを目的として行う売買取引。 （三省堂「大辞林 第二版」） この分野の投機： 予測に基づいて，あらかじめ処理を進めておくこと ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

投機のフェーズ cycle 予測 (prediction) 実行 (execution) 高性能コンピューティング論２ 投機のフェーズ 予測 (prediction) 実行 (execution) 確認 (verification, confirmation) キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 4. 再実行 2. 実行 B B ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

投機技術の種類 ○○予測 分岐予測 値予測 レイテンシ予測 キャッシュ･ヒット/ミス予測 etc. 高性能コンピューティング論２ 投機技術の種類 ○○予測 分岐予測 値予測 レイテンシ予測 キャッシュ･ヒット/ミス予測 etc. 粒度 (granularity)：細粒度 (fine-grain) ～粗粒度 (coarse-grain) 命令レベル スレッド･レベル 関数レベル WWW ページのリンクの先読み ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

分岐予測 cycle add r5 = r4 + r3 be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 高性能コンピューティング論２ 分岐予測 cycle 確認 add r5 = r4 + r3 IF IF OR OR IF EX MEM EX OR WB EX MEM be r1 == r2 IF r8 = r6 + r7 add r8 = r8 + 1 WB MEM PC 予測 フェッチ r9 = r6 - r7 sub r8 = *(r9) ld WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

分岐予測 cycle add r5 = r4 + r3 be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 高性能コンピューティング論２ 分岐予測 cycle 確認 add r5 = r4 + r3 IF OR EX MEM IF WB OR IF be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 IF IF OR OR IF EX OR EX MEM WB MEM PC 予測 フェッチ r9 = r6 - r7 sub r8 = *(r9) ld WB 再フェッチ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

IF 100 LD 1 2 10 100 200 ID 5 1000 210 EX MEM WB PredPC IR PC Rs Rt 高性能コンピューティング論２ PredPC IF 100 IR PC Rs LD 1 2 10 100 200 ID Rt 5 Reg File 1000 210 EX DR MEM MA MD Main Memory WB MDR

投機のメリット/ディメリット cycle 予測 Hit 時 あたかも，依存がなくなったかのようになる 実行が省略されるわけではない A 高性能コンピューティング論２ 投機のメリット/ディメリット 予測 Hit 時 あたかも，依存がなくなったかのようになる 実行が省略されるわけではない cycle A 1. 予測 3. 確認 2. 実行 B ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

投機のメリット/ディメリット cycle 予測 Miss 時 非投機時より，確認の分だけ遅くなる 結果の比較：0～1～数サイクル 高性能コンピューティング論２ 投機のメリット/ディメリット 予測 Miss 時 非投機時より，確認の分だけ遅くなる 結果の比較：0～1～数サイクル 使用した計算資源（とエネルギー）を浪費したことになる cycle A 1. 予測 3. 確認 4. 再実行 2. 実行 B ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

投機のメリット/ディメリット cycle （平均レイテンシ短縮）≒（予測率）× （ ＋（予測ヒット率） × H 高性能コンピューティング論２ 投機のメリット/ディメリット （平均レイテンシ短縮）≒（予測率）× （ ＋（予測ヒット率） × H －（予測 ミ ス 率） × M ） cycle A 1. 予測 3. 確認 4. 再実行 2. 実行 B H M ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

予測ミスの影響 cycle （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） A 1. 予測 高性能コンピューティング論２ 予測ミスの影響 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） cycle A 1. 予測 3. 確認 4. 再実行 2. 実行 B ミス･ペナルティ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

分岐予測 cycle add r5 = r4 + r3 be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 高性能コンピューティング論２ 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM IF WB OR IF be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 IF OR EX OR EX MEM WB MEM r9 = r6 - r7 sub r8 = *(r9) ld WB ミス･ペナルティ (= H, M = 0) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ 高性能コンピューティング論２ 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは1～２サイクル長くなってもよい バック･エッジは， 1～２サイクル長くなってもよい ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より

値予測 すべての命令の結果を予測 データ依存（フロー依存）による先行制約を緩和 ヒットした場合，あたかも依存がなくなったかのようになる 高性能コンピューティング論２ 値予測 すべての命令の結果を予測 データ依存（フロー依存）による先行制約を緩和 ヒットした場合，あたかも依存がなくなったかのようになる 実行が省略されるわけではない cycle r1の結果を予測 add r1 = r2 + r3 IF OR EX MEM WB add r4 = r1 + 2 IF OR OR EX MEM WB r6 = r4 + r5 add r7 = r6 + 1 IF IF IF IF

値予測 すべての命令の結果を予測 データ依存（フロー依存）による先行制約を緩和 詳細は次回以降（時間があれば） 高性能コンピューティング論２ 値予測 すべての命令の結果を予測 データ依存（フロー依存）による先行制約を緩和 ヒットした場合，あたかも依存がなくなったかのようになる 実行が省略されるわけではない 詳細は次回以降（時間があれば） cycle r1の結果を予測 add r1 = r2 + r3 IF OR EX MEM WB r6の結果を予測 add r4 = r1 + 2 IF OR EX MEM WB r6 = r4 + r5 add r7 = r6 + 1 IF IF OR OR EX MEM WB IF IF OR OR EX MEM WB

投機 と キャッシュ・アクセス キャッシュ・アクセスも投機の一種 キャッシュ･ヒット/ミス予測 「キャッシュにある」と予測してアクセス 高性能コンピューティング論２ 投機 と キャッシュ・アクセス キャッシュ・アクセスも投機の一種 「キャッシュにある」と予測してアクセス さもないと，まったく効果がない キャッシュ・アクセスを行い，データがキャッシュにあるか否かを確認 キャッシュになければ諸々の処理をやり直す キャッシュ･ヒット/ミス予測 普通のキャッシュは，always hit と予測している キャッシュ・ミスを予測できると命令スケジューリングの効率が向上 詳細は次回以降（時間があれば）

プリフェッチ（通常アクセスの場合） 近い将来にアクセスされると予測したデータをあらかじめキャッシュに移動 高性能コンピューティング論２ プリフェッチ（通常アクセスの場合） ④ データ取得 近い将来にアクセスされると予測したデータをあらかじめキャッシュに移動 ロード命令に依存する命令の先行制約を緩和 ① アクセス コア *(r4) ② ミス L1D キャッシュ *(r4) ③ アクセス L2 キャッシュ *(r4) cycle I0 ld r1 = *(r4) add r3 = r1 + r2 I1

プリフェッチ（プリフェッチを行った場合） 高性能コンピューティング論２ プリフェッチ（プリフェッチを行った場合） ⑤ データ取得 近い将来にアクセスされると予測したデータをあらかじめキャッシュに移動 ロード命令に依存する命令の先行制約を緩和 ④ アクセス コア *(r4) ③ 移動 ① 予測 L1D キャッシュ *(r4) ② アクセス L2 キャッシュ *(r4) cycle I0 ld r1 = *(r4) add r3 = r1 + r2 I1

投機に関するまとめ この分野の投機 性能面では ローリスク ＆ ハイリターン とは言え，ある程度成功してくれないと困る 高性能コンピューティング論２ 投機に関するまとめ この分野の投機 予測に基づいて処理を進めること 一般的な意味とは違って，「あやしい」ことではない 性能面では ローリスク ＆ ハイリターン 失敗しても投機を行わなかった場合とあまり違いがない 成功すれば丸儲け とは言え，ある程度成功してくれないと困る ミス・ペナルティによる性能低下 計算資源とエネルギーの浪費 結局，総合的に考えて得か否か？ 分岐予測やプリフェッチは，かなりおいしいケース

高性能コンピューティング論２ 本日のまとめ

* 高性能コンピューティング論２ 07/16/96 まとめ スーパスカラプロセッサとバブル 投機 *

高性能コンピューティング論２ 次回 11/12（木） 10:40～ 「アウトオブオーダ実行機構」について解説