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

问题描述

我在网上寻找一些关于 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），总共 1000 倍，1 次未命中外循环 999x（因为从内循环末端将预测循环为 NT）。这使得 1999, + 1 在开始时错过了。总共有2000个。我注意到，几乎每次我从真正的解决方案中循环一次（在其他示例中也是如此）。我还尝试开发未在每个循环中检查每个条件的计数器，但它只确认了我的结果（如果预测器设置为 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; 
}

标签： cassemblybranchprediction

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

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

问题描述

解决方案

推荐阅读