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

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    $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

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

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

---

汇编是从这个 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 )。

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

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 未采用，因此我们确实在第一次迭代时得到了错误预测。