Advanced Computer Architecture 03. 投機 五島 正裕 2015/10/1 Advanced Computer Architecture 内容 1. 前々回（RISC と命令パイプライン）の復習 2. スーパースカラ･プロセッサと分岐 3. 投機 4. 余談 2 Advanced Computer Architecture 1. 前々回の復習 RISCと命令パイプライン 2015/10/1 Advanced Computer Architecture 4 命令パイプライン I1 I0 IF ID EX MEM WB 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 Advanced Computer Architecture パイプライン・ハザード パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 構造ハザード (structural hazard) HW の資源の不足が原因 非構造ハザード SW の持つ依存関係が原因 データ・ハザード (data hazard) データ依存 制御ハザード (control hazard) 制御依存，分岐命令の実行 5 Advanced Computer Architecture インターロック と バブル パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 パイプライン・インターロック (interlock) 機構によって対処 パイプライン・バブル (bubble) が発生 「パイプラインが乱れる」 6 Advanced Computer Architecture アーキテクチャ的対処 インターロックする ⇒ バブルが発生 ⇒ 性能低下 インターロックする機会を減らすことが重要！ 構造ハザード 資源の不足が原因 資源の追加で消える 例えば，メモリ・ポートの場合， 命令キャッシュとデータ・キャッシュの分離 (separate) 非構造ハザード プログラムが原因 原理的に消えない バブルの削減 7 Advanced Computer Architecture 8 バブルの削減 （制御ハザード） cycle I0 be I1 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM W Advanced Computer Architecture 9 分岐命令 （条件）分岐命令 if (cond) PC = PC + immediate; branch on register cond: R[Rs] == 0, R[Rs] > 0, … compare and branch cond: R[Rs] == R[Rt], R[Rs] != R[Rt] op 31 Rs 25 Rt 20 immediate 15 0 Advanced Computer Architecture IF 10 100 PC ID IR 0 200 5 Reg File Rs LD 1 2 10 100 Rt EX MEM WB 1000 DR MDR MA MD Main Memory 210 Advanced Computer Architecture 11 インターロックの排除（制御ハザード） cycle I0 IF be ID EX MEM WB IF ID EX MEM WB I1 I0 IF IF be ID EX IF OR nPC I1 be I0 I1 IF OR nPC IF EX OR IF MEM ID EX WB EX MEM WB IF OR EX next PC 計算器 MEM WB MEM WB EX OR MEM MEM WB EX MEM WB 遅延分岐 W Advanced Computer Architecture レポート：遅延分岐と Compare & Branch，Jump Branch on Register 遅延分岐で O.K. Compare & Branch 遅延分岐で O.K. ？ next PC ： O.K. 分岐方向：レジスタ内容の比較が必要 レジスタ間接 Jump 遅延分岐で O.K. ？ next PC：レジスタ内容が必要 実際，どうなってるのか？ 12 Advanced Computer Architecture 13 インターロックの排除（Compare & branch） add r5 = r4 + 1 be r1 == r2 ld r8 = *(r6) add r5 = r4 + 1 be r1 == r2 ld r8 = *(r6) add r5 = r4 + 1 be r1 == r2 ld r8 = *(r6) IF ID EX MEM WB IF ID EX MEM WB IF IF ID EX IF OR nPC MEM EX WB MEM WB IF IF OR nPC IF EX OR OR EX M MEM WB EX MEM WB IF OR EX MEM WB Advanced Computer Architecture レポート：遅延分岐と Compare & Branch，Jump Branch on Register 遅延分岐で O.K. Compare & Branch 遅延分岐で O.K. ？ next PC ： O.K. 分岐方向：レジスタ内容の比較が必要 レジスタ間接 Jump 遅延分岐で O.K. ？ next PC：レジスタ内容が必要 実際，どうなってるのか？ 14 Advanced Computer Architecture バック・エッジ もろもろの元凶は，パイプラインのバック・エッジ バック・エッジ 逆向きの信号の流れ 15 Advanced Computer Architecture IF 16 100 PC ID IR 0 200 5 Reg File Rs LD 1 2 10 100 Rt EX MEM WB 1000 DR MDR MA MD Main Memory 210 Advanced Computer Architecture 17 バック・エッジ長 と バブルの量 cycle be I1 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB Advanced Computer Architecture 2. スーパースカラ･プロセッサと分岐 2015/10/1 Advanced Computer Architecture 19 スーパースカラの命令パイプライン 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 Advanced Computer Architecture 20 制御ハザード cycle add r5 = r4 + r3 IF bz IF r1 OR nPC EX MEM WB EX MEM WB add r8 = r6 + r7 IF OR EX MEM WB add r8 = r8 + 1 IF OR EX MEM WB Advanced Computer Architecture 3. 投機 2015/10/1 Advanced Computer Architecture 22 投機 投機的実行 (speculative execution) 投機 (speculation)： 1. 偶然の利益をねらって行う行為。 2. 将来の価格変動を予想して、価格差から生ずる利益を得ることを 目的として行う売買取引。 （三省堂「大辞林 第二版」） この分野の投機： 予測に基づいて，あらかじめ処理を進めておくこと Advanced Computer Architecture 23 投機のフェーズ 1. 予測 (prediction) 2. 実行 (execution) 3. 確認 (verification, confirmation) 4. キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 Advanced Computer Architecture 投機技術の種類 ○○予測 分岐予測 値予測 レイテンシ予測 キャッシュ･ヒット/ミス予測 etc. 粒度 (granularity)：細粒度 (fine-grain) ～粗粒度 (coarse-grain) 命令レベル スレッド･レベル 関数レベル WWW ページのリンクの先読み 24 Advanced Computer Architecture 25 分岐予測 cycle 3. 確認 add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2, L0 add r8 = r6 + r7 IF OR EX MEM WB PC 予測 add r8 = r8 1. + 1 IF OR EX MEM WB 2. フェッチ sub r9 = r6 - r7 IF OR EX MEM WB ld IF OR EX MEM WB r8 = *(r9) Advanced Computer Architecture 26 分岐予測 cycle 3. 確認 add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2, L0 L0: ld add r8 = *(r6) r6 + r7 PC add r9 r8 = r8 1. + 1 sla << 1 予測 IF OR IF OR EX MEM WB IF OR IF OR EX MEM WB 2. フェッチ add sub r9 = r9 r6 + - 1 r7 ld r8 = r9 *(r9) sub - 1 4. 再フェッチ IF IF OR EX M IF IF OR EX M Advanced Computer Architecture 27 投機のメリット/ディメリット 予測 Hit 時 あたかも，依存がなくなったかのようになる 実行が省略されるわけではない cycle A 1. 予測 3. 確認 2. 実行 B Advanced Computer Architecture 28 投機のメリット/ディメリット 予測 Miss 時 非投機時より，確認の分だけ遅くなる 結果の比較：0～1～数サイクル 使用した計算資源（とエネルギー）を浪費したことになる cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 Advanced Computer Architecture 29 投機のメリット/ディメリット （平均レイテンシ短縮）≒（予測率）× （ ＋（予測ヒット率） × H －（予測 ミ ス 率） × M ） cycle A 1. 予測 3. 確認 2. 実行 H B M 4. 再実行 Advanced Computer Architecture 30 予測ミスの影響 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） cycle A 1. 予測 3. 確認 2. 実行 ミス･ペナルティ B 4. 再実行 Advanced Computer Architecture 31 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2 add r8 = r6 + r7 IF OR IF OR EX MEM WB add r8 = r8 + 1 IF OR IF OR EX MEM WB sub r9 = r6 - r7 IF IF OR EX M ld IF IF OR EX M r8 = *(r9) ミス･ペナルティ (= H, M = 0) Advanced Computer Architecture 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは1～２サイクル長くなってもよい 32 Advanced Computer Architecture IF 33 100 PC ID IR 0 200 5 Reg File Rs LD 1 2 10 100 Rt EX MEM WB 1000 DR MDR MA MD Main Memory 210 Advanced Computer Architecture 34 バック・エッジ長 と ミス･ペナルティ cycle be I1 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB Advanced Computer Architecture 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは，1～２サイクル長くなってもよい バック･エッジは， 1～２サイクル長くなってもよい ⇒ クロックの高速化 35 Advanced Computer Architecture 投機 と キャッシュ キャッシュも，投機の一種？ 「キャッシュにある」と予測してアクセス さもないと，まったく効果がない 投機的性質を含む キャッシュ･ヒット/ミス予測 普通のキャッシュは，always hit と予測している 36 Advanced Computer Architecture 余談 2015/10/1 Advanced Computer Architecture 投機と日常 この分野の投機 「あやしい」ことではない この分野の投機 vs. 経済の投機 ギャンブル性 低い，ばくち ではない low risk, high return 日常的投機 リスクが十分低いときには，予測に基づいて行動するのが当然 「信号が青なので進む」 38 Advanced Computer Architecture 投機と日常 「あらかじめやっておくと早く終わる」例は少ない 仕事の量は減らない むしろ，予測ミスの分だけ増える よい例 募集 39 Advanced Computer Architecture 細粒度の投機 と HW 「SW でできることは HW でやってはいけない」 「ハード屋」というものは，何でもかんでも HW 化したがる 性能が n 倍違わないなら，SW のほうがよいに決まってる 疑わしい ○○専用 HW リコンフィギュアラブル 細粒度（命令レベル, etc）の投機： HW でやるべき，数少ないことのひとつ 40 Advanced Computer Architecture 次回 Out-of-Order スーパースカラ ＋ 分岐予測 ＋ レジスタ･リネーミング 41
© Copyright 2024 ExpyDoc
