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

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

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

投機のフェーズ 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～２サイクル長くなってもよい

Advanced Computer Architecture 分岐予測の効果 2019/2/24

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

分岐予測の効果 (1/4) プログラム n ：プログラムの命令数 b ：そのうち，分岐命令の割合 プロセッサ： Advanced Computer Architecture 分岐予測の効果 (1/4) プログラム n ：プログラムの命令数 b ：そのうち，分岐命令の割合 プロセッサ： p ：分岐予測ミス・ペナルティ プログラム on プロセッサ i0 ：分岐予測ミス率 0% の時の IPC β ：分岐予測ミス率

分岐予測の効果 (2/4) 分岐予測ミス率 0% の時のプログラムの実行サイクル数： n / i0 分岐予測ミスによる実行サイクル数の増加： Advanced Computer Architecture 分岐予測の効果 (2/4) 分岐予測ミス率 0% の時のプログラムの実行サイクル数： n / i0 分岐予測ミスによる実行サイクル数の増加： n b p β 分岐予測ミス率 β の時の IPC： n / {n / i0 + n b p β} = 1/ {1 / i0 + b p β}

分岐予測の効果 (3/4) 分岐予測ミス率 β の時の IPC： 1/ {1 / i0 + b p β} Advanced Computer Architecture 分岐予測の効果 (3/4) 分岐予測ミス率 β の時の IPC： 1/ {1 / i0 + b p β} i0 = 2，b = 0.2，p = 10 とすると， 1/ {1 / i0 + b p β} = 1 / { 0.5 + 0.2 ×10× β} = 1 / (0.5 + 2β) β 0% 1% 3% 5% 10% 50% 100% IPC 2.0 1.92 1.79 1.67 1.43 0.67 0.4 IPC 低下率 −0% −4% −11% −16% −29% −66% −80%

Advanced Computer Architecture 分岐予測の効果 (4/4) 1 / (0.5 + 2β) i0 = 2 0.4 β O 1.0

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

制御命令 （分岐命令） 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 next PC 計算器 be I1 be 遅延分岐 I0 I1 Advanced Computer Architecture インターロックの排除（制御ハザード） 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 next PC 計算器 be IF OR EX MEM WB 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

スーパスカラ・プロセッサと遅延分岐 cycle I0 be I1 I2 be I0 I1 I2 IF OR EX MEM WB IF OR Advanced Computer Architecture スーパスカラ・プロセッサと遅延分岐 cycle I0 IF OR EX MEM WB be IF OR EX MEM WB nPC I1 IF OR EX MEM WB I2 IF OR EX MEM WB be IF OR EX MEM WB nPC I0 IF OR EX MEM WB I1 IF OR EX MEM WB I2 IF OR EX MEM WB

スーパスカラ・プロセッサと遅延分岐 遅延分岐では救えない 分岐スロットの数 スカラなら1命令で OK だった． 2命令同時フェッチなら？ Advanced Computer Architecture スーパスカラ・プロセッサと遅延分岐 遅延分岐では救えない 分岐スロットの数 スカラなら1命令で OK だった． 2命令同時フェッチなら？ 4命令なら？ 分岐予測が必須

分岐予測に使える情報 毎サイクル，フェッチするためには， 命令をフェッチしてから next PC を求めるのでは遅い Advanced Computer Architecture 分岐予測に使える情報 毎サイクル，フェッチするためには， 命令をフェッチしてから next PC を求めるのでは遅い 「fetch PC だけから次の fetch PC を！」

スーパスカラ・プロセッサの分岐予測 cycle I0 be I1 I2 be I0 I1 I2 fetch PC fetch PC Advanced Computer Architecture スーパスカラ・プロセッサの分岐予測 cycle fetch PC I0 IF OR EX MEM WB fetch PC be IF OR EX MEM WB I1 IF OR EX MEM WB I2 IF OR EX MEM WB fetch PC be IF OR EX MEM WB fetch PC I0 IF OR EX MEM WB I1 IF OR EX MEM WB I2 IF OR EX MEM WB

分岐予測 分岐予測： 分岐方向予測 分岐アドレス予測 Advanced Computer Architecture 分岐予測 分岐予測： 分岐方向予測 分岐アドレス予測 bool pred_taken = branch_dir_pred(fetch_PC); addr_t taken_PC = btb_lookup(fetch_PC); /* BTB ミスなら 0 */ addr_t untaken_PC = fetch_PC + INSN_SIZE * 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），確率は低い タグの分だけ PHT のエントリを増やしたほうが得 PHT: 2b タグ： 10～30ｂ

分岐方向予測 分岐予測： 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(); NNNTNNNT…

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

パーセプトロン分岐予測機 パーセプトロン：ニューラル・ネットワークの一種 今後，流行るかも． Advanced Computer Architecture パーセプトロン分岐予測機 パーセプトロン：ニューラル・ネットワークの一種 今後，流行るかも．

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

命令キャッシュ 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/24

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

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

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