Dynamic branch prediction miss count - incorrect

Question

I was looking over internet for some exaples about dbp and I found this one. Source: http://faculty.cse.tamu.edu/djimenez/614-spring14/bpexample.html (including solution)

Code:

main:
        leal    4(%esp), %ecx       ; function overhead
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ecx         ; gcc stack alignment at the top of main

        xorl    %ecx, %ecx      ; i = 0 (%ecx)
.L2:                                       ; top of outer loop
        xorl    %edx, %edx      ; j = 0 (%edx)
.L3:                                             ; top of inner loop
        movl    c, %eax             ; %eax = c
        addl    $1, %edx            ; j++
        addl    $1, %eax            ; %eax++
        movl    %eax, c             ; c = %eax
        cmpl    $4, %edx            ; if j < 4 then goto L3
        jne     .L3                 ; INNER LOOP BRANCH

        addl    $1, %ecx         ; i++
        cmpl    $1000, %ecx      ; if i < 1000 then goto L2
        jne     .L2              ; OUTER LOOP BRANCH

        movl    c, %eax          ; return c

        popl    %ecx             ; function overhead
        leal    -4(%ecx), %esp
        ret

For a 1-bit predictor starting at zero, the result should be 2002. In my logic, there will be 1 miss at the inner loop (as it returns from the outer loop with prediction T), 1000x in total, and 1 miss at the outer loop 999x (because the loop will be predicted as NT from the inner loop end). That makes 1999, + 1 miss at the beginning. That makes 2000 in total. I noticed, almost every time I'm about 1 loop off the real solution (in other examples too). I also tried to develop miss counter that checks every condition every loop, but it only confirmed my result (2000 or 1999 if predictor is set to T), so either I don't understand it properly or there is something wrong with my counting logic.

Could you please explain to me what am I doing wrong?

---

The asm was compiled from this C.

int c;
int main ()
{
  int i, j;
  for (i=0; i<1000; i++) {
     for (j=0; j<4; j++) {
       c++;
     } 
  } 
  return c; 
}

Answer 1

您似乎正在分析 1 位全局预测器，状态在两个循环分支之间共享。（或者假设两个分支在 BHT 中彼此别名。） 但是您的作业要求假设分支在 BHT 中没有别名。

您正在谈论根据外循环分支所做的事情来预测内循环。1 位预测器每个条目使用 1 位，而不是全局的！那未免有点太琐碎了。 https://danluu.com/branch-prediction/

更高级的真实预测器确实会考虑全局历史记录与每个分支历史记录，但通常会记录全局预测或本地预测对于特定分支是否效果更好，并基于此选择要使用的预测。

不幸的是，即使您假设的 1 位全局状态，您的分析也有错误。

在第一次迭代中，内部循环分支是函数中的第一个分支，因为 C 被编译为do{}while(--i)asm 循环（具有一定程度的 gcc 优化，但显然不足以将其转换为add $4000, c）。

您的分析没有提及根据初始状态的第一次外部迭代的第一次内部迭代。（并且两个分支都有单独的状态，第一个外循环分支的准确性也取决于初始预测）。

内循环将出现 1 次缺失（因为它从外循环返回预测 T），

内循环分支执行前 3 次，它被采用，因此T预测是正确的。也许您的分析着眼于 C 抽象机，其中if (!i<1000) goto loop_bottom在第一次迭代之前，循环顶部有一个条件分支？就像您可能会得到未优化的编译器输出一样？

内部循环的最终迭代每次都会错误预测，预测循环分支失败时的情况。（1000 次错误预测）。

对于全局状态，那么外循环分支对除最后一次迭代之外的所有迭代都会做出错误预测，因此我认为 1999 年的错误预测对于具有 1 位全局状态的机器来说是正确的。

对于每个分支的独立 1 位预测器

在内循环分支上有 2000 次错误预测（每个内循环的第一次和最后一次迭代各 1 次 = 外循环体）。

外循环分支有 2 次错误预测（外循环的第一次和最后一次迭代各 1 次）。

初始预测 = 0 未被采用，因此我们确实在第一次迭代中得到了错误预测。