今天去洗车，我居然发现CPU的···
The following article is from 后端研究所 Author 大白所长
来源 | 后端研究所（ID：byte0706）
如若转载请联系原公众号
有趣的问题
前几天摸鱼的时候，我在stackoverflow发现一个有趣的问题：
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
提问者用C++写了一个数组求和的函数，把数组排序后求和和无序求和的计算性能竟然相差6倍，十分诡异。
我们来看下代码：
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned c = 0; c < arraySize; ++c)
{ // Primary loop
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
代码比较简单，先搞了个大数组，然后数组的元素是256以内取模，所有元素都落在0-256之内，接着在循环里面使用条件判断求和。
提问者为了防止有单次误差，做了10w次循环，发现运行时间差别很大：
无序求和 累计耗时 11.54秒 排序求和 累计耗时 1.93秒
对呀，按理说加了个std:sort()耗时会增加，但是性能还是这么优秀，真是奇怪呀!
提问者又用Java搞了一遍，现象和C++不能说一模一样，但几乎也是分毫不差。
究竟是咋回事呢？读到这里的盆友，一定是个技术人儿，来吧，让我们一探究竟。
洗车房的故事
前阵子我开着自己的捷达去洗车，车还挺多，排着队一个个搞。
我发现洗车流程是这样的：喷水、打泡沫、刷洗、擦拭、吹干。
车辆在外面排队，依次是奥迪A6L、宝马X5、奔驰C200L、捷达vs5。
就这样一个工序完成后，车辆向下一个工序移动，当前工序又补进来一辆车。
我原来以为是一辆车进去 完成所有工序再出来，下一辆进行完成全部工序，依次类推，没想到洗车房还是流水线作业。
为啥是流水线呢？提高洗车数量，也就是吞吐量，单位时间赚取更多噻！
如果是完成所有工序再搞下一辆，这样某个时刻5个工序只有1个在做，其他4共工序都是等待状态，工人们都开始摸鱼了，钱也没赚到，客户等待时间还长。
生活中的智慧还真是不少呀，看到这里不禁要问，这和前面的数组求和有啥关系呢？别急，还真有关系。
CPU的内部的那些事儿
我们先从一个宏观角度去看下CPU内部的结构：
从两个图上，我们可以得到如下信息：
CPU内部的核心组件有各类寄存器、控制单元CU、逻辑运算单元ALU、高速缓存 CPU和外部交互的交通大动脉就是三种总线：地址总线、数据总线、控制总线 I/O设备、RAM通过三大总线和CPU实现功能交互
程序经过编译器处理成机器码来执行，程序会被翻译成一条条的指令，为了简化问题，我们选择5级流水线的CPU来说明问题：
取指令IF
取指令（Instruction Fetch，IF）阶段是将一条指令从主存中取到指令寄存器的过程。指令译码ID
取出指令后，计算机立即进入指令译码（Instruction Decode，ID）阶段。
在指令译码阶段，指令译码器按照预定的指令格式，对取回的指令进行拆分和解释，识别区分出不同的指令类别以及各种获取操作数的方法。指令执行EX
在取指令和指令译码阶段之后，接着进入执行指令（Execute，EX）阶段。
此阶段的任务是完成指令所规定的各种操作，具体实现指令的功能。为此，CPU的不同部分被连接起来，以执行所需的操作。访存取数阶段MEM
根据指令需要，有可能要访问主存读取操作数，这样就进入了访存取数（Memory，MEM）阶段，此阶段的任务是：根据指令地址码，得到操作数在主存中的地址，并从主存中读取该操作数用于运算。结果回写WB
作为最后一个阶段，结果写回（Writeback，WB）阶段把执行指令阶段的运行结果数据写回到某种存储形式。
上面的IF、ID、EX、MEM、WB就是CPU的5级流水线，这个流程和洗车房的流水线很相似：
没错，CPU内部处理一条条指令的过程和洗车房就非常相似，我们继续深挖！
小结：CPU流水线技术是一种将指令分解为多步，并让不同指令的各步操作重叠，从而实现几条指令并行处理，以加速程序运行过程的技术。
指令的每步有各自独立的电路来处理，每完成一步，就进到下一步，而前一步则处理后续指令，属于CPU硬件电路层面的并发。
CPU流水线吞吐量和延迟
我们来看下引入流水线之后吞吐量的变化：
该模式下的吞吐量是1/(300+20)ps = 3.125GIPS(每秒千兆条指令)
使用流水线时，组合逻辑被拆分为3个部分，但是每个部分都需要写寄存器，这样就增加了整个流程的时间从320ps提高到了360ps。
拆分多出两个逻辑和两个寄存器写，额外多出40ps。
此时的吞吐量是1/(100+20)ps = 8.333GIPS(每秒千兆条指令)，整个吞吐量是未使用流水线的2.67倍。
从上面的对比来看，增加了一些硬件和延迟带来了吞吐量的提升，但是一味增加硬件不是万金油，单纯的写寄存器延迟就很明显。
流水线的级数也被称为深度，当前intel的酷睿i7采用了16级深度的流水线，在一定范围内提高流水线深度可以提高CPU的吞吐量，但是也为硬件设计带来很大的挑战，甚至降低吞吐量。
CPU流水线冒险
通过流水线设计来提升 CPU 的吞吐率，是一把双刃剑，在提高吞吐量的同时我们也在冒险。
所谓的冒险就是一帆风顺路上的磕磕绊绊，坑坑洼洼，流水线也并非一帆风顺的。
提到流水线设计需要解决的三大冒险：结构冒险（Structural Hazard）、数据冒险（Data Hazard）以及控制冒险（Control Hazard）。
结构冒险
结构冒险本质上是一种硬件冲突，我们以5级流水线为例来说，指令读取IF阶段和取数操作MEM，都需要进行内存数据的读取，然而内存只有一个地址译码器，只能在一个时钟周期里面读取一条数据。
换句话说就像洗车流水线的喷水和刷洗都要用到水管，但是只有一根水管，这样就存在冲突，导致只能满足一个喷水或者刷洗。
对于MEM阶段和IF阶段的冲突，一个解决方案就是把内存分成两部分：存放指令的内存和存放数据的内存，让它们有各自的地址译码器，从而通过增加硬件资源来解决冲突。
没错，这种将指令和数据分开存储就是著名的哈佛结构Harvard Architecture，指令和数据放在一起的就是冯诺依曼结构/普林斯顿结构Princeton Architecture。
这两种结构有各自优缺点，现代CPU借鉴了两种架构采用一种混合结构，并且引入高速缓存，来降低CPU和内存的速度不匹配问题，如图：
这种混合结构就很好地解决了流水线结构冒险问题，只是硬件结构更复杂了，属于硬件层面的优化。
数据冒险
数据冒险是指令之间存在数据依赖关系，就像这段代码：
int a = 10;
int b = a + 10;//语句2
int c = b + a;//语句3
语句3的计算依赖于b的值，在语句2对b进行了计算，也就是语句3依赖于语句2，但是每一个语句都会被翻译成很多的指令，也就是其中两个指令存在依赖关系。
比如说指令3-3需要等待指令2-2完成WB阶段才可以进行EX阶段，如果不等待得到的结果就是错误的。
一种解决方案就是引入NOP操作，这个时钟周期啥也不做，等到依赖的数据完成再继续，这种通过流水线停顿解决数据冒险的方案称为流水线冒泡(Pipeline Bubble)。
流水线冒泡虽然简单，但是效率却下降了，经过大量的实践发现，我们完全可以在第一条指令的结果数据传输给到下一条指令的 ALU，下一条指令不需要再插入NOP 阶段，就可以继续正常进行了。
这种将结果直接传输的技术称为操作数前推/转发Operand Forwarding，它可以和流水线冒泡NOP一起使用，因为单纯的操作数前推也无法完全避免使用NOP。
小结：操作数前推，就是通过在硬件层面制造一条旁路，让一条指令的计算结果，可以直接传输给下一条指令，而不再需要指令 1 写回寄存器，指令 2 再读取寄存器,这样多此一举的操作。
控制冒险
在流水线中，多个指令是并行执行的，在指令1执行的时候，后续的指令2和指令3可能已经完成了IF和ID两个阶段等待被执行，此时如果指令1一下子跳到了其他地方，那么指令2和指令3的IF和ID就是无用功了。
遇到这种指令转移情况，处理器需要先排空指令2和指令3对应的流水线，然后跳转到指令1的新的目标位置进入新的流水线，这部分称为转移开销，这也是产生性能损失的重要原因。
转移指令本身和流水线的模式是冲突的，因为转移指令会改变指令的流向， 而流水线则希望能够依次地取回指令，将流水线填满的，但是转移指令在实际程序中非常普遍，这也是CPU流水线必须要面对的问题。
转移指令可以分为无条件转移和条件转移。
无条件转移是确定发生的，并且跳转地址在取指阶段就能得到，我们在 CPU 里面设计对应的旁路电路，把计算结果更早地反馈到流水线中，这种属于硬件方案称为缩短分支延迟。
但是，对于条件转移我们在IF阶段并不能获得跳转位置，只能等EX阶段才知道，这就引出了分支预测。
分支预测换句话说就是：流水线的上一个阶段还没有完成，但是下一个指令是啥要依赖于这个结果，为了效率，流水线不能停顿住，必须要做个选择，向左走还是 向右走，选择出下一条要执行的指令，哪怕错了，也比等待好，万一猜对了呢！
CPU分支预测
分支预测有：静态分支预测和动态分支预测。
静态分支预测就是每次都选择一个结果，就像抛硬币每次都猜正面，对于CPU流水线来说都猜指令不跳转，也就有50%的正确率了，这种预测方式简单但是不够高效。
动态分支预测会根据之前的选择情况和正确率来预测当前的情况，做出判断是顺序分支还是跳转分支，因此仍然会有成功和失败两种情况。
比如分支预测选择了跳转分支之后：
预测成功时，尽快找到分支目标指令地址，避免控制相关造成流水线停顿。 预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。
最简单的动态分支预测器有1bit和2bit，其中2bit表示有2位标记，分别记录上一次预测状态和上次预测结果，讲到这里很多文章就一带而过，给了一个状态机迁移图，就草草收尾了：
说实话，看到这图，我仿佛懂了，又仿佛没懂，于是我决定好好研究一下这个2bit分支预测器的一些原理，我们继续：
两种决策
not taken代表选择顺序分支
taken代表跳转分支四种状态
00 代表strongly not taken 强顺序分支
01 代表weakly not taken 弱顺序分支
10 代表weakly taken 弱跳转分支
11 代表strongly taken 强跳转分支
我们继续看2bit动态分支预测是如果进行状态机迁移的：
当前状态处于00 强顺序分支时
必然预测下一次也是顺序分支，此时会有两种结果，预测成功了，下一次状态仍然是00，预测失败了，最终程序选择了跳转分支，下一次状态变为01。当前状态处于01 弱顺序分支时
必然预测下一次也是顺序分支，此时会有两种结果，预测成功了，下一次状态调整为00，预测失败了，最终程序选择了跳转分支，下一次状态变为10。当前状态处于10 弱跳转分支时
必然预测下一次也是跳转分支，此时会有两种结果，预测成功了，下一次状态调整为11，预测失败了，最终程序选择了顺序分支，下一次状态变为01。当前状态处于11 强跳转分支时
必然预测下一次也是跳转分支，此时会有两种结果，预测成功了，状态不变仍然是11，预测失败了，最终程序选择了顺序分支，下一次状态变为10。
坚持看到这里，说明你真是个爱学习的人儿啊，我们来画一张完整的迁移图：
从这张图可以看到从顺序分支改变为跳转分支，需要连续两次预测失败，同样的跳转分支变为顺序分支，也需要连续两次预测失败：
标记分支状态以及分支历史的一段内存被称为BTB，这段内存只存储了分支指令地址，以及预测的目标地址以及预测的位，这一块内容比较复杂，我们在此不展开了。
经过前面的分析可以看到动态分支预测器具有一定的容错性，并且波动性较小，只有连续两次预测失败才会转变选择结果，整体正确率提升明显。
从一些文章的数据显示，大部分情况下2bit预测器准确率可以达到95%以上：
回顾问题
经过前面的一番分析，我们回到stackoverflow那个数组排序和无序耗时的问题上来，这个问题有两个关键因素：
数组元素是完全随机的，本次结果和上次结果是独立分布的 大量循环结构和条件判断的存在
没错，随机+循环+条件就彻底命中了CPU流水线的软肋。
数组排序之后的分支预测
数组未排序的分支预测
数组排序后，动态分支预测会结合之前的结果做出判断准确率非常高，未排序时完全随机和静态分支预测差不多了，因此准确率一般。
分支预测失败就意味着流水线排空，废弃已经进行IF和ID的指令，然后再选择正确的指令，整个过程在目前CPU来说要来浪费10-20个时钟周期，这样耗时就上来了。
总结
本文先从stackoverflow上一个关于随机数组排序和未排序求和的问题来切入。
进一步采用最简单的5级CPU流水线讲述基本原理和流水线中存在的三者冒险，及其各自的解决方法，特别是控制冒险。
进一步阐述了控制冒险中的分支预测技术，并展开了对双模动态分支预测器基本原理的剖析。
最后结合stackoverflow的问题，揭露流水线分支预测和随机数组排序/未排序在循环结构下的不同决策结果带来的巨大耗时影响。
本文先到这里，感谢朋友们的耐心阅读，我们下期见！
<END>
【新产品上架】 🕚
推荐阅读：
每日打卡赢积分兑换书籍入口