Advanced Computer Architecture 06. 分岐予測器とトレース・キャッシュ 五島 正裕 2015/10/1 Advanced Computer Architecture 内容 1. 分岐予測の復習 2. 分岐予測器 3. トレース・キャッシュ 2 Advanced Computer Architecture 分岐予測の復習 2015/10/1 Advanced Computer Architecture 4 投機のフェーズ 1. 予測 (prediction) 2. 実行 (execution) 3. 確認 (verification, confirmation) 4. キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 Advanced Computer Architecture 5 分岐予測 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) Advanced Computer Architecture 6 分岐予測 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 7 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB L0: ld r1 == r2, L0 r8 = *(r6) sla r9 = r8 << 1 IF OR IF OR EX MEM WB IF OR IF OR EX MEM WB add r9 = r9 + 1 IF IF OR EX M sub r8 = r9 - 1 IF IF OR EX M ミス･ペナルティ (= H, M = 0) Advanced Computer Architecture 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは1～２サイクル長くなってもよい 8 Advanced Computer Architecture 分岐命令の出現頻度 Run Length : 分岐から次の分岐までの命令数 3～5命令 フェッチ幅 2～4 だと… ほとんど毎サイクル，分岐命令をフェッチ 9 Advanced Computer Architecture 分岐予測の効果 （予測ミスによるレイテンシの増加） ＝（予測率） ×（予測ミス率） ×（ミス･ペナルティ） ＝（平均ラン・レングス）÷（フェッチ幅）×（予測率 = 1）× （予測ミス率） ×（ミス･ペナルティ） ≒ （予測ミス率） ×（ミス･ペナルティ） 10 Advanced Computer Architecture 11 分岐予測ミスの影響 実行時間 ペナルティ 20 cycles ペナルティ 10 cycles 2 ペナルティ 5 cycles 1.5 1 O ミス率 (%) 5 10 Advanced Computer Architecture 分岐予測器 2015/10/1 Advanced Computer Architecture 13 制御命令 （分岐命令） （条件）分岐命令 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 14 インターロックの排除（制御ハザード） cycle I0 IF be ID EX MEM WB IF ID EX MEM WB I1 I0 IF IF be ID EX MEM IF nPC EX MEM WB IF OR I1 be I0 I1 IF nPC IF EX OR IF ID EX WB EX MEM WB MEM WB EX OR MEM WB EX MEM WB 遅延分岐 MEM W Advanced Computer Architecture スーパースカラの場合 遅延分岐では救えない 毎サイクル，フェッチするためには， 命令をフェッチしてから next PC を求めるのでは遅い 「fetch PC だけから next PC を！」 15 Advanced Computer Architecture 分岐方向予測 分岐予測： bool pred_taken = branch_dir_pred(fetch_PC); addr_t taken_PC = btb_lookup(fetch_PC); addr_t untaken_PC = fetch_PC + 4 * FETCH_WIDTH; addr_t next_PC = taken_PC && pred_taken ? taken_PC : untaken_PC; 16 Advanced Computer Architecture 17 BTB : Branch Target Buffer fetch PC tag valid taken PC selector taken PC Advanced Computer Architecture 分岐方向予測の原理 その1 ローカル分岐履歴 (local branch history) 基本的には，前回と同じだろう ヒステリシスを持たせ，発振を防ぐ 18 Advanced Computer Architecture 19 2-bit 飽和形カウンタ (2-bit saturating counter) fetch PC PHT (Pattern History Table) 10 taken 11 strongly taken 10 weakly taken 01 weakly untaken 00 strongly untaken untaken Advanced Computer Architecture PHT (Pattern History Table) タグ，有効ビットがない 「ミス」がない コンフリクト（衝突）が起こる あまり気にしなくてもよい どうせ，そこそこ外れるものだから エントリ数が十分多ければ（数K），確率は低い 20 Advanced Computer Architecture 分岐方向予測 分岐予測： bool pred_taken = branch_dir_pred(fetch_PC); addr_t taken_PC = btb_lookup(fetch_PC); addr_t untaken_PC = fetch_PC + 4 * FETCH_WIDTH; addr_t next_PC = taken_PC && pred_taken ? taken_PC : untaken_PC; 21 Advanced Computer Architecture 22 分岐方向予測の原理 その2 グローバル分岐履歴 (global branch history) ローカルは，自身の履歴 グローバルは，すべての分岐 最近実行された分岐，12回程度の結果を記録 たとえば： for (int i = 0; i < N; ++i) if (i % 2) even(); else odd(); Advanced Computer Architecture 23 gshare (McFarling ‘93) fetch PC 0001 PHT 00 XOR 0010 01 11 0 0 1 1 01 Global History Register 01 同じ分岐でも， グローバル履歴が異なれば， 別のカウンタを使用． ただし，コンフリクトが多発 数十パタン／分岐 01 01 01 コンフリクトを軽減する研究 「要は，圧縮」 Advanced Computer Architecture 24 分岐命令のプロファイル 分岐の方向には，偏りがある 利用して，テーブルを圧縮 taken 率 1.0 分岐命令 （taken 率でソート） 0.0 always untaken always taken Advanced Computer Architecture トレース・キャッシュ 2015/10/1 Advanced Computer Architecture 26 命令キャッシュ fetch PC 31 5 2 0 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 Cache Lines Rotator Advanced Computer Architecture 27 命令キャッシュ 通常 fetch PC 010 31 5 2 0 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 Cache Lines Rotator Advanced Computer Architecture 28 命令キャッシュ ラインを跨ぐ fetch PC 110 31 5 2 0 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 Cache Lines Rotator Advanced Computer Architecture 29 命令キャッシュ 分岐を含む fetch PC 010 31 5 2 0 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 Cache Lines Rotator Advanced Computer Architecture 30 命令キャッシュ 分岐を含む fetch PC 0 1 10 31 5 2 0 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 Cache Lines Rotator 2 3 4 5 Advanced Computer Architecture フェッチ・グループ フェッチ・グループ 同時にフェッチされる命令のグループ fetch PC： フェッチ・グループの先頭命令の PC next PC： 次の fetch PC フェッチ・グループに分岐命令が含まれている場合， その分岐命令の予測された飛び先の PC 31 Advanced Computer Architecture 困難 フェッチ・グループが： キャッシュ・ラインを跨ぐ場合： キャッシュ・ヒット/ミス判定器が複数必要 分岐を含む場合： その分岐の予測先のフェッチは困難 – もう1サイクル前に予測しておく必要があった – 次の次の分岐予測器 予測できても，バンク・コンフリクトが発生 分岐を複数含む ？ 32 Advanced Computer Architecture 33 トレース・キャッシュ fetch PC 31 2 XOR dir pred 0 2 3 4 5 2 3 4 3 6 7 0 1 Traces Advanced Computer Architecture トレース・キャッシュ トレース： 分岐先 (branch target) アドレスから始まる， ある（予測）パスに沿った命令の列 トレース・キャッシュ： トレース単位でキャッシング HW が単純に ただし，アレイの利用効率が悪い 34 Advanced Computer Architecture 35 トレース・キャッシュの位置 I$ T$ I$ T$ Insn Pipe Insn Pipe タンデム （Pentium 4) パラレル Advanced Computer Architecture 今日のまとめ 2015/10/1 Advanced Computer Architecture 分岐予測器 taken PC BTB (branch target buffer) 分岐方向予測器 ローカル履歴 グローバル履歴 37 Advanced Computer Architecture トレース・キャッシュ トレース・キャッシュ： トレース単位でキャッシング ある種のバイナリ変換 個々の命令ではなく，トレースをフェッチしているように見える トレース ＝ 長命令？ VLIW？ 38 Advanced Computer Architecture 今後の予定 次週 値予測 39
© Copyright 2024 ExpyDoc
