GShare分岐予測器で解決すべき問題設定

自作CPUにおいて、GShareb分岐予測器の実装をしようとしている。自分が実装しているものが本当に正しいのか検証したくて、いろいろモデルを作りながらまとめている。そのメモ。

---

実験

以下のプログラムを考える。要するに、両方の引数が偶数か奇数かで値を設定し、その結果に基づいて比較を行う。

このプログラムでは、3つの分岐命令が使用されている。

• 引数0の偶数・奇数をチェック
• 引数1の偶数・奇数をチェック
• 上記2つの結果が異なっているかをチェック

つまり最後の比較は、上記の2つの比較に大きく依存する形式となっている。

.global branch_count

 branch_count:
     andi    a0, a0, 1
     beqz    a0, .cut_aa
     li      a0, 0
     j       .bb_check
 .cut_aa:
     li      a0, 1

     .bb_check:
     andi    a1, a1, 1
     beqz    a1, .cut_bb
     li      a1, 0
     j       .final_check
 .cut_bb:
     li      a1, 1

 .final_check:
     bne     a0, a1, .ret_true
     li      a0, 0
 .ret_true:
     li      a0, 1
     ret

このbranch_count()を引数のパタンでひたすら回していく。

 int result_count = 0;

 extern int branch_count(int aa, int bb);

 int main ()
 {
   for (int a = 0; a < 10; a++) {
     for (int b = 0; b < 10; b++) {
       if (branch_count (a, b)) {
         result_count ++;
       }
     }
   }

   return 0;
 }

これで、現状において分岐予測の結果をシミュレーションで取得する。

grep 80002014 bru_detail.log                                        
               15778 : (09,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 0000000000000000, NotTaken, bim=1, Succ, DASM(0x00b51363)
               16014 : (11,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 0000000000000000, Taken   , bim=0, Miss, DASM(0x00b51363)
               16178 : (14,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               16302 : (13,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               16462 : (14,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               16586 : (13,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               16746 : (14,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               16870 : (13,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               17030 : (14,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               17154 : (13,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               17498 : (14,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)
               17702 : (03,1) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=2, Miss, DASM(0x00b51363)
               17874 : (07,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)
               18038 : (09,1) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=2, Miss, DASM(0x00b51363)
               18210 : (13,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)
               18374 : (15,1) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=2, Miss, DASM(0x00b51363)
               18546 : (03,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)
               18710 : (05,1) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=2, Miss, DASM(0x00b51363)
               18882 : (09,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)
               19046 : (11,1) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=2, Miss, DASM(0x00b51363)
               19310 : (06,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               19466 : (07,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               19626 : (08,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               19750 : (07,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               19910 : (08,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               20034 : (07,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               20194 : (08,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               20318 : (07,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               20478 : (08,2) pc_vaddr = 0000000080002014, target_addr = 0000000080002018, pred_target_addr = 000000008000201a, NotTaken, bim=1, Succ, DASM(0x00b51363)
               20602 : (07,1) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=0, Miss, DASM(0x00b51363)
               20866 : (01,2) pc_vaddr = 0000000080002014, target_addr = 000000008000201a, pred_target_addr = 000000008000201a, Taken   , bim=1, Miss, DASM(0x00b51363)

TakenとNotTakenが連続で入れ替わるような結果になっている。これを改善していくことになる。