高性能コンピューティング論２ 1 高性能コンピューティング論２ 第4回 投機 高性能コンピューティング学講座 三輪 忍 [email protected] 高性能コンピューティング論２ 本日の講義内容 • スーパスカラプロセッサとバブル • 投機 2 高性能コンピューティング論２ 3 スーパスカラプロセッサと バブル 高性能コンピューティング論２ パイプライン・ハザード • パイプライン・ハザード (hazard)： • パイプライン動作を妨げる要因 • 分類： 1. 構造ハザード (structural hazard) • • ハードウェアの資源不足が原因 ハードウェア資源の追加により解消可能 非構造ハザード 2. • • ソフトウェア内の依存関係が原因 原理的に解消不可能 4 高性能コンピューティング論２ 5 非構造ハザード • データ・ハザード • 命令間のデータ依存 add r4 = r1 + r2 cycle IF add r5 = r4 + r3 ID EX MEM WB IF ID EX MEM WB • 制御ハザード • 分岐命令の実行 cycle IF ID EX MEM WB IF ID EX MEM WB 高性能コンピューティング論２ 6 分岐命令 C ソース s = 0; for (i = 1; i <= 10; ++i) s = s + i; アセンブリ set r1 = 0; # set r2 = 1; # set r3 = 11; LOOP: beq r2 == r3, add r1 = r1 + add r2 = r2 + b LOOP; EXIT: s = 0; i = 1; EXIT; r2; 1; ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 7 条件分岐命令 • if (cond) PC = PC + immediate; • PC 相対 (relative) • 命令だけから（レジスタを読まなくても）飛び先アドレスが計算できる op 31 Rs 25 Rt 20 immediate 15 0 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 8 条件分岐 branch on register 分岐 条件 判定に 必要な 処理 備考 compare & branch 1つのレジスタ値が， 0，正，負， 0 以上，0 以下 2つの値（レジスタ値， 2つの値（レジスタ値， 即値）の一致比較 即値）の大小比較 R[Rs] == 0, R[Rs] > 0, … R[Rs] R[Rs] R[Rs] R[Rs] 1. レジスタの読み出し レジスタに，ｚero フラグ を付加しておくと楽． signフラグは msb． == != == != R[Rt], R[Rt], imm, imm R[Rs] > R[Rt], R[Rs] >= R[Rt], … 1. レジスタの読み出し 2. 一致比較 1. レジスタの読み出し 2. 大小比較（減算） 一部の RISC は持つ RISC は普通持たない ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ IF 100 PC ID 0 200 5 Reg File IR Rs LD 1 2 10 100 Rt 1000 EX MEM 210 DR MA MD WB 9 Main Memory MDR ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 10 バブルの量とバックエッジ長 • バックエッジ • 逆向きの信号の流れ • バブルの量 ＝ バックエッジ長 be I1 IF cycle ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB 高性能コンピューティング論２ 11 バブルの削減（制御ハザード） cycle IF ID EX MEM WB IF ID EX MEM WB IF IF OR EX IF MEM WB IF WB IF MEM IF OR EX MEM WB nPC : next PC 選択 WB OR EX OR nPC EX MEM OR EX EX OR : Operand Read OR nPC EX MEM IF ID MEM 遅延分岐 WB MEM WB WB ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「命令パイプライン」より 高性能コンピューティング論２ 12 遅延分岐とスーパスカラプロセッサ • 遅延分岐 • 「分岐命令の遅延スロットに置かれた命令は（分岐の成立/不成立にか かわらず）必ず実行」 • 遅延スロット（分岐命令の次の命令）を埋めた分だけ性能向上 • 埋まらなかった分だけ nop が増加 • スーパスカラプロセッサ（＝ローエンドではないプロセッサ） における遅延分岐 • 分岐に関するバックエッジ長は， 最近は10ステージ前後 • 埋める必要のある遅延スロットが 多すぎて非現実的 [ Intel社 Silvermont アーキテクチャの命令パイプライン ] （http://www.tomshardware.com/reviews/atom-silvermont-architecture, 3499-2.html より） 高性能コンピューティング論２ 13 スーパスカラプロセッサにおけるバブル • 制御ハザード 命令フェッチ デコード リネーム/スケジュール 実行 リタイア/コミット L1データ・キャッシュ L2データ・キャッシュ cycle • データ・ハザード • L1データ・キャッシュにヒットする場合 cycle • L1データ・キャッシュにミスする場合 cycle 高性能コンピューティング論２ 14 なぜパイプライン・ステージを増やすのか？ cycle • ステージを増やして周波数向上 スループット向上 • その反面，バブルは増加 バブルを削減する技術の重要性も増加 ステージ数 x2 周波数 x2 cycle • スーパスカラ化とは独立した技術 • スループット向上を目指した結果， 「スーパスカラ ＋ 多段パイプライン」 になった • 多段？ • これでも一時期に比べれば段数が減った（2005年頃は31段） • ここ数年は10数段に落ち着いている（消費電力の壁） 高性能コンピューティング論２ 投機 15 高性能コンピューティング論２ 16 投機 • 投機的実行 (speculative execution) • 投機 (speculation)： 1. 偶然の利益をねらって行う行為。 2. 将来の価格変動を予想して、価格差から生ずる利益を得ることを目 的として行う売買取引。 （三省堂「大辞林 第二版」） • この分野の投機： • 予測に基づいて，あらかじめ処理を進めておくこと ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 17 投機のフェーズ 予測 (prediction) 2. 実行 (execution) 3. 確認 (verification, confirmation) 4. キャンセル，回復，再実行 (cancellation, recovery, re-execution) 1. cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 18 投機技術の種類 • ○○予測 • 分岐予測 • 値予測 • レイテンシ予測 • キャッシュ･ヒット/ミス予測 • etc. • 粒度 (granularity)：細粒度 (fine-grain) ～粗粒度 (coarse-grain) • 命令レベル • スレッド･レベル • 関数レベル • WWW ページのリンクの先読み ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 19 分岐予測 cycle 3. 確認 add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2 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) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 20 分岐予測 cycle 3. 確認 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 PC 予測 add r8 = r8 1. + 1 IF OR IF OR EX MEM WB 2. フェッチ sub r9 = r6 - r7 ld r8 = *(r9) 4. 再フェッチ IF IF OR EX M IF IF OR EX M ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ IF PredPC 100 PC ID 0 200 5 Reg File IR Rs LD 1 2 10 100 Rt 1000 EX MEM DR MA MD WB 21 MDR Main Memory 210 高性能コンピューティング論２ 22 投機のメリット/ディメリット • 予測 Hit 時 • あたかも，依存がなくなったかのようになる • 実行が省略されるわけではない cycle A 1. 予測 3. 確認 2. 実行 B ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 23 投機のメリット/ディメリット • 予測 Miss 時 • 非投機時より，確認の分だけ遅くなる • 結果の比較：0～1～数サイクル • 使用した計算資源（とエネルギー）を浪費したことになる cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 24 投機のメリット/ディメリット • （平均レイテンシ短縮）≒（予測率）× （ ＋（予測ヒット率） × H －（予測 ミ ス 率） × M ） cycle A 1. 予測 3. 確認 2. 実行 H B 4. 再実行 M ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 25 予測ミスの影響 • （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 ミス･ペナルティ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 26 分岐予測 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) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 27 投機の効果 • 「毎回かかるレイテンシを，ミス時のペナルティに」 • （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） • 予測ミス率が十分小さければ (ex. 1%)， • ミス･ペナルティは1～２サイクル長くなってもよい • バック･エッジは， 1～２サイクル長くなってもよい ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 28 値予測 • すべての命令の結果を予測 • データ依存（フロー依存）による先行制約を緩和 • ヒットした場合，あたかも依存がなくなったかのようになる • 実行が省略されるわけではない cycle r1の結果 を予測 add r1 = r2 + r3 IF OR add r4 = r1 + 2 IF OR EX MEM WB EX add r6 = r4 + r5 IF OR add r7 = r6 + 1 IF OR MEM WB EX MEM WB EX MEM WB 高性能コンピューティング論２ 29 値予測 • すべての命令の結果を予測 • データ依存（フロー依存）による先行制約を緩和 • ヒットした場合，あたかも依存がなくなったかのようになる • 実行が省略されるわけではない cycle r1の結果 を予測 add r1 = r2 + r3 r6の結果 を予測add r4 = r1 + 2 IF OR EX MEM WB IF OR EX MEM WB add r6 = r4 + r5 IF OR add r7 = r6 + 1 IF OR • 詳細は次回以降（時間があれば） EX MEM WB EX MEM WB 高性能コンピューティング論２ 30 投機 と キャッシュ・アクセス • キャッシュ・アクセスも投機の一種 • 「キャッシュにある」と予測してアクセス • さもないと，まったく効果がない • キャッシュ・アクセスを行い，データがキャッシュにあるか否かを確認 • キャッシュになければ諸々の処理をやり直す • キャッシュ･ヒット/ミス予測 • 普通のキャッシュは，always hit と予測している • キャッシュ・ミスを予測できると命令スケジューリングの効率が向上 • 詳細は次回以降（時間があれば） 高性能コンピューティング論２ 31 プリフェッチ（通常アクセスの場合） ④ データ取得 • 近い将来にアクセスされると 予測したデータをあらかじめ キャッシュに移動 コア ① アクセス ② ミス *(r4) L1D キャッシュ • ロード命令に依存する命令 の先行制約を緩和 *(r4) ③ アクセス L2 キャッシュ *(r4) cycle 高性能コンピューティング論２ 32 プリフェッチ（プリフェッチを行った場合） ⑤ データ取得 • 近い将来にアクセスされると 予測したデータをあらかじめ キャッシュに移動 コア ④ アクセス ① 予測 *(r4) ③ 移動 L1D キャッシュ • ロード命令に依存する命令 の先行制約を緩和 *(r4) ② アクセス L2 キャッシュ *(r4) cycle 33 高性能コンピューティング論２ 投機に関するまとめ • この分野の投機 • 予測に基づいて処理を進めること • 一般的な意味とは違って，「あやしい」ことではない • 性能面では ローリスク ＆ ハイリターン • 失敗しても投機を行わなかった場合とあまり違いがない • 成功すれば丸儲け • とは言え，ある程度成功してくれないと困る • ミス・ペナルティによる性能低下 • 計算資源とエネルギーの浪費 • 結局，総合的に考えて得か否か？ • 分岐予測やプリフェッチは，かなりおいしいケース ピ ュ ー テ ィ ン グ 論 ２ 34 本日のまとめ 高性能コンピューティング論２ まとめ • スーパスカラプロセッサとバブル • 投機 35 高性能コンピューティング論２ 次回 • 11/12（木） 10:40～ • 「アウトオブオーダ実行機構」について解説 36
© Copyright 2024 ExpyDoc
