动态分支预测未命中计数 - 不正确

Question

我在互联网上寻找一些关于 dbp 的例子，我找到了这个。来源：http://faculty.cse.tamu.edu/djimenez/614-spring14/bpexample.html（包括解决方案）

代码：

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    , %edx            ; j++
        addl    , %eax            ; %eax++
        movl    %eax, c             ; c = %eax
        cmpl    , %edx            ; if j < 4 then goto L3
        jne     .L3                 ; INNER LOOP BRANCH

        addl    , %ecx         ; i++
        cmpl    00, %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

对于从零开始的 1 位预测器，结果应为 2002。在我的逻辑中，内循环将有 1 次未命中（因为它来自具有预测 T 的外循环 returns） , 总共 1000x，外循环 999x 有 1 次未命中（因为从内循环结束开始循环会被预测为 NT）。这使得 1999, + 1 开始时未命中。总共是2000。我注意到，几乎每次我都与真正的解决方案相差 1 个循环（在其他示例中也是如此）。我还尝试开发未命中计数器来检查每个循环的每个条件，但它只确认了我的结果（如果预测器设置为 T，则为 2000 或 1999），所以要么我没有正确理解它，要么我的计数逻辑有问题.

你能解释一下我做错了什么吗？

asm 是从这个 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 00, c).

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

There will be 1 miss at the inner loop (as it returns from the outer loop with prediction T),

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

内循环的最后一次迭代每次都预测错误，预测为在循环分支失败时采用。（1000 次预测错误）。

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

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

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

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

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

动态分支预测未命中计数 - 不正确

Dynamic branch prediction miss count - incorrect

c

assembly

branch

prediction