Advanced Computer Architecture 06. 分岐予測器とトレース・キャッシュ 五島 正裕 2019/2/21

Advanced Computer Architecture 内容 分岐予測の復習 分岐予測器 トレース・キャッシュ

Advanced Computer Architecture 分岐予測の復習 2019/2/21

投機のフェーズ cycle 予測 (prediction) 実行 (execution) Advanced Computer Architecture 投機のフェーズ 予測 (prediction) 実行 (execution) 確認 (verification, confirmation) キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 4. 再実行 B B 2. 実行

分岐予測 cycle add r5 = r4 + r3 be r1 == r2 r8 = r6 + r7 add r8 = r8 + 1 Advanced Computer Architecture 分岐予測 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, L0 r8 = *(r6) ld r9 = r9 + 1 Advanced Computer Architecture 分岐予測 cycle 確認 add r5 = r4 + r3 IF OR EX MEM IF WB OR IF be r1 == r2, L0 r8 = *(r6) ld r9 = r9 + 1 add r9 = r8 << 1 sla r8 = r9 - 1 sub L0: r8 = r6 + r7 add r8 = r8 + 1 r9 = r6 - r7 sub r8 = *(r9) ld IF OR IF OR IF EX OR EX MEM WB MEM PC 予測 フェッチ WB 再フェッチ

分岐予測 cycle add r5 = r4 + r3 be r1 == r2, L0 r8 = *(r6) ld r9 = r9 + 1 Advanced Computer Architecture 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM IF WB OR IF be r1 == r2, L0 r8 = *(r6) ld r9 = r9 + 1 add r9 = r8 << 1 sla r8 = r9 - 1 sub L0: IF OR EX OR EX MEM WB MEM WB ミス･ペナルティ (= H, M = 0)

投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ Advanced Computer Architecture 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは1～２サイクル長くなってもよい

分岐命令の出現頻度 Run Length : 分岐から次の分岐までの命令数 3～5命令 フェッチ幅 2～4 だと… Advanced Computer Architecture 分岐命令の出現頻度 Run Length : 分岐から次の分岐までの命令数 3～5命令 フェッチ幅 2～4 だと… ほとんど毎サイクル，分岐命令をフェッチ

分岐予測の効果 （予測ミスによるレイテンシの増加） ＝（予測率） ×（予測ミス率） ×（ミス･ペナルティ） Advanced Computer Architecture 分岐予測の効果 （予測ミスによるレイテンシの増加） ＝（予測率） ×（予測ミス率） ×（ミス･ペナルティ） ＝（平均ラン・レングス）÷（フェッチ幅）×（予測率 = 1）× （予測ミス率） ×（ミス･ペナルティ） ≒ （予測ミス率） ×（ミス･ペナルティ）

分岐予測ミスの影響 実行時間 ペナルティ 20 cycles ペナルティ 10 cycles 2 ペナルティ 5 cycles 1.5 1 Advanced Computer Architecture 分岐予測ミスの影響 実行時間 ペナルティ 20 cycles ペナルティ 10 cycles 2 ペナルティ 5 cycles 1.5 1 ミス率 (%) O 5 10

Advanced Computer Architecture 分岐予測器 2019/2/21

制御命令 （分岐命令） op Rs Rt immediate （条件）分岐命令 if (cond) PC = PC + immediate; Advanced Computer Architecture 制御命令 （分岐命令） （条件）分岐命令 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 Rs Rt immediate 31 25 20 15

インターロックの排除（制御ハザード） cycle I0 be I1 I0 be I1 be I0 遅延分岐 I1 IF ID EX MEM Advanced Computer Architecture インターロックの排除（制御ハザード） cycle I0 IF ID EX MEM WB be IF ID EX MEM WB I1 IF ID EX MEM WB I0 IF ID EX MEM WB be IF nPC EX MEM WB I1 IF OR EX MEM WB be IF nPC EX MEM WB I0 IF OR EX MEM WB 遅延分岐 I1 IF OR EX MEM WB

スーパースカラの場合 遅延分岐では救えない 毎サイクル，フェッチするためには， 命令をフェッチしてから next PC を求めるのでは遅い Advanced Computer Architecture スーパースカラの場合 遅延分岐では救えない 毎サイクル，フェッチするためには， 命令をフェッチしてから next PC を求めるのでは遅い 「fetch PC だけから next PC を！」

分岐方向予測 分岐予測： bool pred_taken = branch_dir_pred(fetch_PC); 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;

BTB : Branch Target Buffer Advanced Computer Architecture BTB : Branch Target Buffer tag valid taken PC fetch PC selector taken PC

分岐方向予測の原理 その1 ローカル分岐履歴 (local branch history) 基本的には，前回と同じだろう Advanced Computer Architecture 分岐方向予測の原理 その1 ローカル分岐履歴 (local branch history) 基本的には，前回と同じだろう ヒステリシスを持たせ，発振を防ぐ

2-bit 飽和形カウンタ (2-bit saturating counter) Advanced Computer Architecture 2-bit 飽和形カウンタ (2-bit saturating counter) fetch PC PHT (Pattern History Table) 11 strongly taken 10 10 weakly taken 01 weakly untaken 00 strongly untaken taken untaken

PHT (Pattern History Table) Advanced Computer Architecture PHT (Pattern History Table) タグ，有効ビットがない 「ミス」がない コンフリクト（衝突）が起こる あまり気にしなくてもよい どうせ，そこそこ外れるものだから エントリ数が十分多ければ（数K），確率は低い

分岐方向予測 分岐予測： bool pred_taken = branch_dir_pred(fetch_PC); 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;

分岐方向予測の原理 その2 グローバル分岐履歴 (global branch history) ローカルは，自身の履歴 Advanced Computer Architecture 分岐方向予測の原理 その2 グローバル分岐履歴 (global branch history) ローカルは，自身の履歴 グローバルは，すべての分岐 最近実行された分岐，12回程度の結果を記録 たとえば： for (int i = 0; i < N; ++i) if (i % 2) even(); else odd();

Global History Register Advanced Computer Architecture gshare (McFarling ‘93) 同じ分岐でも， グローバル履歴が異なれば， 別のカウンタを使用． ただし，コンフリクトが多発 数十パタン／分岐 コンフリクトを軽減する研究 「要は，圧縮」 fetch PC 0001 PHT 00 XOR 01 0010 11 1 1 01 01 Global History Register 01 01 01

分岐命令のプロファイル 1.0 0.0 分岐の方向には，偏りがある 利用して，テーブルを圧縮 taken 率 分岐命令 Advanced Computer Architecture 分岐命令のプロファイル 分岐の方向には，偏りがある 利用して，テーブルを圧縮 taken 率 1.0 　分岐命令 （taken 率でソート） 0.0 always untaken always taken

Advanced Computer Architecture トレース・キャッシュ 2019/2/21

命令キャッシュ fetch PC 1 2 3 4 5 6 7 Cache Lines 1 2 3 4 5 6 7 Rotator 31 5 Advanced Computer Architecture 命令キャッシュ fetch PC 31 5 2 1 2 3 4 5 6 7 Cache Lines 1 2 3 4 5 6 7 Rotator

命令キャッシュ 通常 fetch PC 1 1 2 2 3 3 4 4 5 5 6 7 Cache Lines 1 2 3 4 5 6 7 Advanced Computer Architecture 命令キャッシュ 通常 fetch PC 1 31 5 2 1 2 2 3 3 4 4 5 5 6 7 Cache Lines 1 2 3 4 5 6 7 Rotator

命令キャッシュ ラインを跨ぐ fetch PC 1 1 1 2 3 4 5 6 6 7 7 Cache Lines 1 1 2 3 4 5 Advanced Computer Architecture 命令キャッシュ ラインを跨ぐ fetch PC 1 1 31 5 2 1 2 3 4 5 6 6 7 7 Cache Lines 1 1 2 3 4 5 6 7 Rotator

命令キャッシュ 分岐を含む fetch PC 1 1 2 2 3 3 4 4 5 5 6 7 Cache Lines 1 2 3 4 5 6 Advanced Computer Architecture 命令キャッシュ 分岐を含む fetch PC 1 31 5 2 1 2 2 3 3 4 4 5 5 6 7 Cache Lines 1 2 3 4 5 6 7 Rotator

命令キャッシュ 分岐を含む fetch PC 1 1 1 2 3 4 5 6 7 Cache Lines 1 2 3 3 4 4 5 5 6 Advanced Computer Architecture 命令キャッシュ 分岐を含む fetch PC 1 1 31 5 2 1 2 3 4 5 6 7 Cache Lines 1 2 3 3 4 4 5 5 6 6 7 Rotator 2 3 4 5

フェッチ・グループ フェッチ・グループ 同時にフェッチされる命令のグループ fetch PC： フェッチ・グループの先頭命令の PC Advanced Computer Architecture フェッチ・グループ フェッチ・グループ 同時にフェッチされる命令のグループ fetch PC： フェッチ・グループの先頭命令の PC next PC： 次の fetch PC フェッチ・グループに分岐命令が含まれている場合， その分岐命令の予測された飛び先の PC

困難 フェッチ・グループが： キャッシュ・ラインを跨ぐ場合： キャッシュ・ヒット/ミス判定器が複数必要 分岐を含む場合： Advanced Computer Architecture 困難 フェッチ・グループが： キャッシュ・ラインを跨ぐ場合： キャッシュ・ヒット/ミス判定器が複数必要 分岐を含む場合： その分岐の予測先のフェッチは困難 もう1サイクル前に予測しておく必要があった 次の次の分岐予測器 予測できても，バンク・コンフリクトが発生 分岐を複数含む ？

トレース・キャッシュ fetch PC 2 3 4 5 Traces 2 3 4 3 6 7 1 dir pred XOR 31 2 Advanced Computer Architecture トレース・キャッシュ fetch PC 31 2 2 3 4 5 XOR Traces 2 3 4 3 6 7 1 dir pred

トレース・キャッシュ トレース： 分岐先 (branch target) アドレスから始まる， ある（予測）パスに沿った命令の列 Advanced Computer Architecture トレース・キャッシュ トレース： 分岐先 (branch target) アドレスから始まる， ある（予測）パスに沿った命令の列 トレース・キャッシュ： トレース単位でキャッシング HW が単純に ただし，アレイの利用効率が悪い

トレース・キャッシュの位置 I$ T$ I$ T$ Insn Pipe Insn Pipe タンデム （Pentium 4) パラレル Advanced Computer Architecture トレース・キャッシュの位置 I$ T$ I$ T$ Insn Pipe Insn Pipe タンデム （Pentium 4) パラレル

Advanced Computer Architecture 今日のまとめ 2019/2/21

分岐予測器 taken PC BTB (branch target buffer) 分岐方向予測器 ローカル履歴 グローバル履歴 Advanced Computer Architecture 分岐予測器 taken PC BTB (branch target buffer) 分岐方向予測器 ローカル履歴 グローバル履歴

トレース・キャッシュ トレース・キャッシュ： トレース単位でキャッシング ある種のバイナリ変換 Advanced Computer Architecture トレース・キャッシュ トレース・キャッシュ： トレース単位でキャッシング ある種のバイナリ変換 個々の命令ではなく，トレースをフェッチしているように見える トレース ＝ 長命令？ VLIW？

Advanced Computer Architecture 今後の予定 次週 値予測