极客时间已完结课程限时免费阅读

25 | 冒险和预测（四）：今天下雨了，明天还会下雨么？

25 | 冒险和预测（四）：今天下雨了，明天还会下雨么？-极客时间

25 | 冒险和预测（四）：今天下雨了，明天还会下雨么？

2019-06-21 徐文浩 来自北京
《深入浅出计算机组成原理》
课程介绍

讲述：徐文浩

时长12:15大小11.18M

过去三讲，我主要为你介绍了结构冒险和数据冒险，以及增加资源、流水线停顿、操作数前推、乱序执行，这些解决各种“冒险”的技术方案。
在结构冒险和数据冒险中，你会发现，所有的流水线停顿操作都要从指令执行阶段开始。流水线的前两个阶段，也就是取指令（IF）和指令译码（ID）的阶段，是不需要停顿的。CPU 会在流水线里面直接去取下一条指令，然后进行译码。
取指令和指令译码不会需要遇到任何停顿，这是基于一个假设。这个假设就是，所有的指令代码都是顺序加载执行的。不过这个假设，在执行的代码中，一旦遇到 if…else 这样的条件分支，或者 for/while 循环，就会不成立。
回顾一下第 6 讲的条件跳转流程
我们先来回顾一下，第 6 讲里讲的 cmp 比较指令、jmp 和 jle 这样的条件跳转指令。可以看到，在 jmp 指令发生的时候，CPU 可能会跳转去执行其他指令。jmp 后的那一条指令是否应该顺序加载执行，在流水线里面进行取指令的时候，我们没法知道。要等 jmp 指令执行完成，去更新了 PC 寄存器之后，我们才能知道，是否执行下一条指令，还是跳转到另外一个内存地址，去取别的指令。
这种为了确保能取到正确的指令，而不得不进行等待延迟的情况，就是今天我们要讲的控制冒险（Control Harzard）。这也是流水线设计里最后一种冒险。

分支预测：今天下雨了，明天还会继续下雨么？

在遇到了控制冒险之后，我们的 CPU 具体会怎么应对呢？除了流水线停顿，等待前面的 jmp 指令执行完成之后，再去取最新的指令，还有什么好办法吗？当然是有的。我们一起来看一看。

缩短分支延迟

第一个办法，叫作缩短分支延迟。回想一下我们的条件跳转指令，条件跳转指令其实进行了两种电路操作。
第一种，是进行条件比较。这个条件比较，需要的输入是，根据指令的 opcode，就能确认的条件码寄存器。
第二种，是进行实际的跳转，也就是把要跳转的地址信息写入到 PC 寄存器。无论是 opcode，还是对应的条件码寄存器，还是我们跳转的地址，都是在指令译码（ID）的阶段就能获得的。而对应的条件码比较的电路，只要是简单的逻辑门电路就可以了，并不需要一个完整而复杂的 ALU。
所以，我们可以将条件判断、地址跳转，都提前到指令译码阶段进行，而不需要放在指令执行阶段。对应的，我们也要在 CPU 里面设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路。
这种方式，本质上和前面数据冒险的操作数前推的解决方案类似，就是在硬件电路层面，把一些计算结果更早地反馈到流水线中。这样反馈变得更快了，后面的指令需要等待的时间就变短了。
不过只是改造硬件，并不能彻底解决问题。跳转指令的比较结果，仍然要在指令执行的时候才能知道。在流水线里，第一条指令进行指令译码的时钟周期里，我们其实就要去取下一条指令了。这个时候，我们其实还没有开始指令执行阶段，自然也就不知道比较的结果。

分支预测

所以，这个时候，我们就引入了一个新的解决方案，叫作分支预测（Branch Prediction）技术，也就是说，让我们的 CPU 来猜一猜，条件跳转后执行的指令，应该是哪一条。
最简单的分支预测技术，叫作“假装分支不发生”。顾名思义，自然就是仍然按照顺序，把指令往下执行。其实就是 CPU 预测，条件跳转一定不发生。这样的预测方法，其实也是一种静态预测技术。就好像猜硬币的时候，你一直猜正面，会有 50% 的正确率。
如果分支预测是正确的，我们自然赚到了。这个意味着，我们节省下来本来需要停顿下来等待的时间。如果分支预测失败了呢？那我们就把后面已经取出指令已经执行的部分，给丢弃掉。这个丢弃的操作，在流水线里面，叫作 Zap 或者 Flush。CPU 不仅要执行后面的指令，对于这些已经在流水线里面执行到一半的指令，我们还需要做对应的清除操作。比如，清空已经使用的寄存器里面的数据等等，这些清除操作，也有一定的开销。
所以，CPU 需要提供对应的丢弃指令的功能，通过控制信号清除掉已经在流水线中执行的指令。只要对应的清除开销不要太大，我们就是划得来的。

动态分支预测

第三个办法，叫作动态分支预测。
上面的静态预测策略，看起来比较简单，预测的准确率也许有 50%。但是如果运气不好，可能就会特别差。于是，工程师们就开始思考，我们有没有更好的办法呢？比如，根据之前条件跳转的比较结果来预测，是不是会更准一点？
我们日常生活里，最经常会遇到的预测就是天气预报。如果没有气象台给你天气预报，你想要猜一猜明天是不是下雨，你会怎么办？
有一个简单的策略，就是完全根据今天的天气来猜。如果今天下雨，我们就预测明天下雨。如果今天天晴，就预测明天也不会下雨。这是一个很符合我们日常生活经验的预测。因为一般下雨天，都是连着下几天，不断地间隔地发生“天晴 - 下雨 - 天晴 - 下雨”的情况并不多见。
那么，把这样的实践拿到生活中来是不是有效呢？我在这里给了一张 2019 年 1 月上海的天气情况的表格。
我们用前一天的是不是下雨，直接来预测后一天会不会下雨。这个表格里一共有 31 天，那我们就可以预测 30 次。你可以数一数，按照这种预测方式，我们可以预测正确 23 次，正确率是 76.7%，比随机预测的 50% 要好上不少。
而同样的策略，我们一样可以放在分支预测上。这种策略，我们叫一级分支预测（One Level Branch Prediction），或者叫 1 比特饱和计数（1-bit saturating counter）。这个方法，其实就是用一个比特，去记录当前分支的比较情况，直接用当前分支的比较情况，来预测下一次分支时候的比较情况。
只用一天下雨，就预测第二天下雨，这个方法还是有些“草率”，我们可以用更多的信息，而不只是一次的分支信息来进行预测。于是，我们可以引入一个状态机（State Machine）来做这个事情。
如果连续发生下雨的情况，我们就认为更有可能下雨。之后如果只有一天放晴了，我们仍然认为会下雨。在连续下雨之后，要连续两天放晴，我们才会认为之后会放晴。整个状态机的流转，可以参考我在文稿里放的图。
这个状态机里，我们一共有 4 个状态，所以我们需要 2 个比特来记录对应的状态。这样这整个策略，就可以叫作 2 比特饱和计数，或者叫双模态预测器（Bimodal Predictor）。
好了，现在你可以用这个策略，再去对照一下上面的天气情况。如果天气的初始状态我们放在“多半放晴”的状态下，我们预测的结果的正确率会是 22 次，也就是 73.3% 的正确率。可以看到，并不是更复杂的算法，效果一定就更好。实际的预测效果，和实际执行的指令高度相关。
如果想对各种分支预测技术有所了解，Wikipedia里面有更详细的内容和更多的分支预测算法，你可以看看。

为什么循环嵌套的改变会影响性能？

说完了分支预测，现在我们先来看一个 Java 程序。
public class BranchPrediction {
public static void main(String args[]) {
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
for (int j = 0; j <1000; j ++) {
for (int k = 0; k < 10000; k++) {
}
}
}
long end = System.currentTimeMillis();
System.out.println("Time spent is " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
for (int j = 0; j <1000; j ++) {
for (int k = 0; k < 100; k++) {
}
}
}
end = System.currentTimeMillis();
System.out.println("Time spent is " + (end - start) + "ms");
}
}
这是一个简单的三重循环，里面没有任何逻辑代码。我们用两种不同的循环顺序各跑一次。第一次，最外重循环循环了 100 次，第二重循环 1000 次，最内层的循环了 10000 次。第二次，我们把顺序倒过来，最外重循环 10000 次，第二重还是 1000 次，最内层 100 次。
事实上，这段代码在这个专栏一开始的几讲里面，就有同学来提问，想要弄明白这里面的关窍。
你可以先猜一猜，这样两次运行，花费的时间是一样的么？结果应该会让你大吃一惊。我们可以看看对应的命令行输出。
Time spent in first loop is 5ms
Time spent in second loop is 15ms
同样循环了十亿次，第一段程序只花了 5 毫秒，而第二段程序则花了 15 毫秒，足足多了 2 倍。
这个差异就来自我们上面说的分支预测。我们在前面讲过，循环其实也是利用 cmp 和 jle 这样先比较后跳转的指令来实现的。如果对 for 循环的汇编代码或者机器代码的实现不太清楚，你可以回头去复习一下第 6 讲。
这里的代码，每一次循环都有一个 cmp 和 jle 指令。每一个 jle 就意味着，要比较条件码寄存器的状态，决定是顺序执行代码，还是要跳转到另外一个地址。也就是说，在每一次循环发生的时候，都会有一次“分支”。
分支预测策略最简单的一个方式，自然是“假定分支不发生”。对应到上面的循环代码，就是循环始终会进行下去。在这样的情况下，上面的第一段循环，也就是内层 k 循环 10000 次的代码。每隔 10000 次，才会发生一次预测上的错误。而这样的错误，在第二层 j 的循环发生的次数，是 1000 次。
最外层的 i 的循环是 100 次。每个外层循环一次里面，都会发生 1000 次最内层 k 的循环的预测错误，所以一共会发生 100 × 1000 = 10 万次预测错误。
上面的第二段循环，也就是内存 k 的循环 100 次的代码，则是每 100 次循环，就会发生一次预测错误。这样的错误，在第二层 j 的循环发生的次数，还是 1000 次。最外层 i 的循环是 10000 次，所以一共会发生 1000 × 10000 = 1000 万次预测错误。
到这里，相信你能猜到为什么同样空转次数相同的循环代码，第一段代码运行的时间要少得多了。因为第一段代码发生“分支预测”错误的情况比较少，更多的计算机指令，在流水线里顺序运行下去了，而不需要把运行到一半的指令丢弃掉，再去重新加载新的指令执行。

总结延伸

好了，这一讲，我给你讲解了什么是控制冒险，以及应对控制冒险的三个方式。
第一种方案，类似我们的操作数前推，其实是在改造我们的 CPU 功能，通过增加对应的电路的方式，来缩短分支带来的延迟。另外两种解决方案，无论是“假装分支不发生”，还是“动态分支预测”，其实都是在进行“分支预测”。只是，“假装分支不发生”是一种简单的静态预测方案而已。
在动态分支预测技术里，我给你介绍了一级分支预测，或者叫 1 比特饱和计数的方法。其实就是认为，预测结果和上一次的条件跳转是一致的。在此基础上，我还介绍了利用更多信息的，就是 2 比特饱和计数，或者叫双模态预测器的方法。这个方法其实也只是通过一个状态机，多看了一步过去的跳转比较结果。
这个方法虽然简单，但是却非常有效。在 SPEC 89 版本的测试当中，使用这样的饱和计数方法，预测的准确率能够高达 93.5%。Intel 的 CPU，一直到 Pentium 时代，在还没有使用 MMX 指令集的时候，用的就是这种分支预测方式。
这一讲的最后，我给你看了一个有意思的例子。通过交换内外循环的顺序，我们体验了一把控制冒险导致的性能差异。虽然执行的指令数是一样的，但是分支预测失败得多的程序，性能就要差上几倍。

推荐阅读

想要进一步了解控制冒险和分支预测技术，可以去读一读《计算机组成与设计：硬件 / 软件接口》的 4.8 章节。
如果想对各种分支预测技术有所了解，Wikipedia里面有更详细的内容和更多的分支预测算法。

课后思考

我在上面用一个三重循环的 Java 程序，验证了“分支预测”出错会对程序带来的性能影响。你可以用你自己惯用的语言来试一试，看一看是否会有同样的效果。如果没有的话，原因是什么呢？
欢迎留言和我分享你的疑惑和见解。你也可以把今天的内容，分享给你的朋友，和他一起学习和进步。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 26

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
24 | 冒险和预测（三）：CPU里的“线程池”
下一篇
26 | Superscalar和VLIW：如何让CPU的吞吐率超过1？
unpreview
 写留言

精选留言(35)

  • 鱼向北游
    2019-07-02
    徐老师 这个for循环的原理是对的，但是例子可能不恰当，因为这个例子耗时最长的不是cpu分支冒险，而是最后一层循环的临时变量创建次数，属于栈的问题，如果要测试分支预测，需要int i，j，k在循环外初始化好，但是这样的话目前100，1000，10000次的循环是几乎看不到差异的，甚至得出的结果会相反，在最大的循环扩充到1000万次(总量为10万亿次，才能感受到冒险的差异)。希望老师能看到，顺便改下例子
    共 22 条评论
    94
  • 焰火
    2019-07-20
    以后写代码的时候养成良好习惯，按事件概率高低在分支中升序或降序安排，争取让状态机少判断
    共 5 条评论
    26
  • 韩俊臣
    2019-09-18
    ”在这样的情况下，上面的第一段循环，也就是内层 k 循环 10000 次的代码。每隔 10000 次，才会发生一次预测上的错误。而这样的错误，在第二层 j 的循环发生的次数，是 1000 次。” 求老师和各位大佬指点下，这句没太看明白，为啥每隔10000次才出现一次预测错误

    作者回复: 韩俊臣同学， 你好，最内层的循环，要执行10000次，前面的9999次都是继续执行下一次循环指令，最后一次是结束循环。预测的话，前面9999次都会预测会继续执行指令，到最后一次的预测会出错。

    共 2 条评论
    14
  • test
    2020-05-30
    实验结果，首先是根据与“鱼向北游”同学的一致，把i j k放在循环外面，必须增大一万倍才有明显的性能差距（10倍左右）； 其次是那个循环的解释，我理解是，最内层的错误预测是一次，但是“底层循环”因为中层执行了1000次，所以是1000次错误判断，而中层的错误判断是一次，但是因为最外层循环导致“中层循环”执行了100次，所以是100次错误判断。
    共 3 条评论
    12
  • 许先森
    2020-01-14
    “要等 jmp 指令执行完成，去更新了 PC 寄存器之后，我们才能知道，是否执行下一条指令，还是跳转到另外一个内存地址，去取别的指令。” 这一段说错了吧？应该是cmp执行完，更新条件码寄存器，才能知道是否执行下一条还是跳转到另一个内存地址，取别的指令

    作者回复: 许先森同学， 你好，这里没有错哦。 cmp指令执行完之后，仍然是顺序执行下一条jmp指令。 但是jmp指令执行完之后，不一定是顺序执行jmp后面的指令，而是要看跳转是否发生，发生的话，执行的就是跳转地址之后的指令了。如果跳转没有发生，才是继续执行jmp后面地址的指令。

    共 2 条评论
    7
  • 喜欢吃鱼
    2019-06-21
    哈哈，之前问今天这个程序问题的是我，明白了，谢谢老师的讲解。
    7
  • 七色凉橙
    2020-04-16
    可以对比陈皓博客里面CPU cache这篇文章一起理解一下：https://coolshell.cn/articles/10249.html
    6
  • 小白
    2019-06-21
    package main import ( "fmt" "time" ) func main() { start := time.Now() for i := 0; i < 100; i++ { for j := 0; j < 1000; j++ { for k := 0; k < 10000; k++ { } } } fmt.Println(time.Since(start)) start = time.Now() for i := 0; i < 10000; i++ { for j := 0; j < 1000; j++ { for k := 0; k < 100; k++ { } } } fmt.Println(time.Since(start)) } 417.9044ms 544.5435ms
    展开
    共 3 条评论
    4
  • pebble
    2019-06-21
    你的机子好厉害，第一个例子语言五毫秒，我测试，c语言需要4337跟4492毫秒，c#需要5367跟5585毫秒，看来cpu的分支预测机制有大的改进了，不知道是什么机制
    共 1 条评论
    4
  • 树军
    2020-08-05
    用Java来解释分支预测是不是不太合适，中间有一层虚拟机，和机器码完全对不上，影响性能的可能根本不是分支预测。
    共 1 条评论
    3
  • 易飞
    2021-09-24
    python，第一个例子60s,第二个例子53s

    作者回复: 哈哈，这还真在我意料之外，不过作为解释性语言，也的确有可能发生这样的事情，回头我研究研究。

    共 2 条评论
    2
  • 开心
    2019-06-26
    如何检查是否执行错了指令，以及执行错指令如何处理还讲吗？
    2
  • haer
    2019-06-22
    用Python实验的结果分别是165秒，139秒，后者的速度更快，为什么呢？ “许童童”的js实验，第二个循环的k应该<100而不是<1000
    共 1 条评论
    2
  • 人什么人
    2021-10-13
    老师，这句话我不太理解：不过只是改造硬件，并不能彻底解决问题。跳转指令的比较结果，仍然要在指令执行的时候才能知道。我们都已经在译码阶段做了比较了，为什么还是不知道结果？那译码阶段比较有啥意义？？？出不来结果的？
    1
  • 吴贤龙
    2020-05-13
    我用js和c#测试，怎么测出来的结果跟老师说的相反啊？ 而且再加多嵌套循环，相差越大，也还是跟老师说的相反呢？
    共 2 条评论
    1
  • learn more
    2019-10-25
    这个循环优化和数据库优化的小表驱动大表好像，原理应该不同哈！
    1
  • djfhchdh
    2019-07-02
    分支预测的状态流转图最左侧那个指向自身的箭头旁边的文字应该是Not Taken
    1
  • 许童童
    2019-06-21
    用js写了一下，分别是343和3345毫秒，差了10倍 let prev = Date.now() for (let i = 0; i < 100; i ++) { for (let j = 0; j < 1000; j ++) { for (let k = 0; k < 10000; k ++) { } } } console.log(Date.now() - prev) prev = Date.now() for (let i = 0; i < 10000; i ++) { for (let j = 0; j < 1000; j ++) { for (let k = 0; k < 1000; k ++) { } } } console.log(Date.now() - prev)
    展开
    共 2 条评论
    1
  • Linuxer
    2019-06-21
    第一种，是进行条件比较。这个条件比较，需要的输入是，根据指令的 opcode，就能确认的条件码寄存器。这里的确认条件码寄存器不太理解，是不是比较确定条件码寄存器的值?
    1
  • woodie
    2022-09-29 来自北京
    冒险包括：结构冒险(资源层面解决)，数据冒险(停顿、操作数前推、乱序执行)，控制冒险(分之预测)