cpu流水线(处理器流水线技术)

今天我们来说一个硬核话题。这篇文章大约需要15分钟。仔细看完，会有收获。我们走吧！

通过本文，您将了解以下内容:

stackoverflow的有趣问题CPU流水线机制和内部数据流转CPU流水线的三大冒险CPU分支预测大揭秘有趣的问题

前几天钓鱼的时候，在stackoverflow里发现了一个有趣的问题:

https://stack overflow . com/questions/11227809/为什么处理已排序的数组比处理未排序的数组快

提问者用C++写了一个数组求和函数，数组排序后求和与无序求和的计算性能相差6倍，很奇怪。

让我们看一下代码:

# include & lt算法& gt# include & ltctime & gt# include & ltiostream & gtint main(){//Generate data const unsigned array size = 32768；int data[array size]；for(无符号c = 0；c & ltarraySize++ c)data[c]= STD::rand()% 256；// !！！有了这个，下一个循环运行得更快。std::sort(data，data+array size)；//测试clock _ t start = clock()；long long sum = 0；for(无符号I = 0；我& lt100000;++i) { for(无符号c = 0；c & ltarraySize++c) { //主循环if(data[c]& gt；= 128)sum+= data[c]；} } double elapsed time = static _ cast & lt；double & gt(clock()-start)/CLOCKS _ PER _ SEC；STD::cout & lt；& ltelapsedTime & lt& lt'\ n & # 39；STD::cout & lt；& lt"sum = & # 34& lt& ltsum & lt& lt'\ n & # 39；代码比较简单，先做一个大数组，然后数组的元素在256以内取模，所有元素落在0-256以内，然后在循环中用条件判断求和。

为了防止出现单个错误，提问者做了10w个循环，发现运行时间相差很大:

无序求和 累计耗时 11.54秒排序求和 累计耗时 1.93秒

是的，按理说加入std:sort()会增加时间消耗，但性能还是那么优秀。真是奇怪！

提问者用Java又做了一遍。现象和C++不完全一样，但几乎完全一样。

到底是怎么回事？在这里看书的笔友一定是个技术娴熟的人。来吧，让我们找出答案。

洗车房的故事

前阵子开着我的捷达去洗车，车还挺多的，一辆接一辆。

我发现洗车的流程是这样的:喷水、起泡、刷洗、擦拭、吹干。

车辆在外面排队，后面是奥迪A6L，宝马X5，奔驰C200L，捷达vs5。

这样一个流程完成后，车辆移动到下一个流程，另一个车辆添加到当前流程。

我以为是一辆车进去完成所有流程再出来，下一辆车去完成所有流程，以此类推。没想到洗车是流水线作业。

为什么是流水线？增加洗车次数，也就是吞吐量，单位时间多赚点硫胺素！

如果你完成了所有的流程，然后得到下一个，那么在某个时刻，五个流程中只有一个在做，其他四个流程都在等待。工人们已经开始捕鱼了，还没赚到钱，所以顾客还有很长的等待时间。

生活中有很多智慧。看到这里，我不禁要问，这和我面前的数组求和有什么关系？别担心，这真的很重要。

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的五段流水线，这个流程和洗车的流水线很像:

没错，CPU内部处理指令的过程和洗车很像。让我们继续深入挖掘！

总结:CPU流水线技术是将指令分解成多个步骤，使不同指令的步骤重叠，从而实现多条指令并行处理，加速程序运行进程的技术。指令的每一步都有自己独立的电路来处理。每一步完成后都会进入下一步，而前一步会处理后续的指令，属于CPU硬件电路级的并发。

相关视频推荐

进程和CPU的未知故事

C/C++Linux服务器开发/后台架构师【零音教育】-学习视频教程-腾讯课堂

【文章福利】:边肖整理了一些我个人觉得比较好的学习书籍和视频资料，分享在群档案里。如果有需要，可以自己添加！~点击加入(832218493需要自己拿)

CPU流水线吞吐量和延迟

我们来看看引入管道后吞吐量的变化:

不使用流水线时，各执行部分形成组合逻辑，执行完成后，写入寄存器。整个时间包括:组合逻辑时间300ps，寄存器写20ps，类似于洗车场一次完成一辆车五个流程的情况。

这种模式下的吞吐量为1/(300+20)ps = 3.125GIPS(每秒千兆指令数)

使用流水线时，组合逻辑被拆分成三个部分，但每个部分都需要写寄存器，这使得整个过程的时间从320ps增加到360ps。

再拆分两个逻辑和两个寄存器写，多40ps。

此时的吞吐量为1/(100+20)ps = 8.333GIPS(每秒千兆指令数)，整体吞吐量是未使用流水线的2.67倍。

从上面的对比来看，增加一些硬件和延迟带来了吞吐量的提升，但是一味的增加硬件并不是万能的，单纯的写寄存器延迟是很明显的。

管道的水平也称为深度。目前英特尔的酷睿i7采用了16级深度的流水线。在一定范围内增加流水线深度可以提高CPU的吞吐量，但也给硬件设计带来了很大的挑战，甚至降低了吞吐量。

CPU流水线冒险

通过流水线设计提高CPU吞吐量是一把双刃剑，我们在提高吞吐量的同时也在承担风险。

所谓的冒险是一条坎坷的路，流水线也不是一帆风顺的。

提出了管道设计中需要解决的三种风险:结构风险、数据风险和控制风险。

结构冒险

结构冒险本质上是一种硬件冲突。让我们以5级管道为例。指令读取IF级和提取操作MEM都需要读取内存数据。但是存储器中只有一个地址解码器，一个时钟周期只能读取一条数据。

换句话说，这就像一条洗车线上，水管是用来喷水和刷洗的，但是只有一条水管，于是就产生了冲突，导致只有一条喷水或刷洗。

对于MEM级和中频级的冲突，一种解决方案是将内存分为存储指令的内存和存储数据的内存两部分，让它们有自己的地址译码器，通过增加硬件资源来解决冲突。

没错，指令和数据存储的分离就是著名的哈佛架构，冯诺依曼架构/普林斯顿架构就是指令和数据的结合。

这两种架构各有优缺点。现代CPU借鉴使用了混合架构，并引入了cache来降低CPU和内存的速度不匹配，如图:

这种混合结构很好的解决了流水线结构的风险问题，但是硬件结构比较复杂，属于硬件级的优化。

数据冒险

数据冒险就是指令之间存在数据依赖，就像这段代码:

int a = 10int b = a+10；//语句2 int c = b+ a；//语句3语句3的计算依赖于B的值，在语句2中计算的是B，也就是语句3依赖于语句2，但是每条语句都会被翻译成很多条指令，也就是其中两条是依赖的。

例如，在进行到EX阶段之前，指令3-3需要等待指令2-2完成WB阶段。不等到结果，就错了。

一种解决方案是引入NOP操作，该操作在该时钟周期内不做任何事情，而是等待相关数据完成后再继续。这种通过流水线停顿来解决数据风险的解决方案被称为流水线泡沫。

管道冒泡虽然简单，但是效率下降了。经过大量的实践，我们发现第一条指令的结果数据可以传输到下一条指令的ALU，下一条指令可以在不插入NOP级的情况下继续正常运行。

这种直接传递结果的技术称为操作数转发/转发操作数转发，可以和流水线冒泡NOP一起使用，因为单纯的操作数转发并不能完全避免使用NOP。

总结:操作数前推是指通过在硬件级创建旁路，可以将一条指令的计算结果直接传递给下一条指令，而不需要指令1写回寄存器，指令2再次读取寄存器，这是多余的。

ADD指令不需要等待WB结束后再执行EX，而是通过操作数转发将LOAD指令直接传递给ADD指令，减少了一次NOP操作，只需要一次NOP操作，提高了流水线效率。

控制冒险

在流水线中，多条指令并行执行。当执行指令1时，后续的指令2和3可能已经完成了要执行的IF和ID两个阶段。这时候如果指令1一下子跳到别的地方，指令2和指令3的IF和ID就没用了。

在这种情况下，处理器需要先将空指令2和指令3对应的流水线排队，然后跳转到指令1的新目标位置进入新的流水线。这部分被称为传输开销，也是造成性能损失的重要原因。

分支指令本身的模式和流水线的模式是冲突的，因为分支指令会改变指令的方向，而流水线希望依次取指令，填满流水线。但是分支指令在实际程序中是很常见的，这也是CPU流水线必须面对的问题。

分支指令可以分为无条件分支和条件分支。

无条件分支是一定会发生的，跳转地址可以在取阶段获得。我们在CPU中设计相应的fibrechannel，并将计算结果提前反馈给流水线。这种硬件方案被称为缩短分支延迟。

但是对于条件分支，我们在IF阶段无法得到跳转位置，只能在EX阶段知道，这就导致了分支预测。

换句话说，分支预测就是:流水线的最后一级还没有完成，但是下一条指令是什么就看这个结果了。为了效率，流水线不能停。你必须做出选择。向左或向右，选择要执行的下一条指令。即使是错的，也比等待好。如果你猜对了呢！

CPU分支预测

分支预测包括静态分支预测和动态分支预测。

静态分支预测就是每次选择一个结果，就像每次抛硬币猜人头一样。对于CPU流水线，如果猜测指令不跳转，会有50%的正确率。这种预测方法简单，但效率不够高。

动态分支预测会根据之前的选择和正确率来预测当前的情况，做出是顺序分支还是跳转分支的判断，所以还是会有成功和失败两种情况。

例如，在分支预测选择跳转分支后:

预测成功时，尽快找到分支目标指令地址，避免控制相关造成流水线停顿。预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

最简单的动态分支预测器是1bit和2bit，其中2bit表示有2 bit标记，分别记录上次预测状态和上次预测结果。至此，很多文章只是路过，给出了一个状态机迁移图，就草草结束了:

说实话，看到这张图的时候，我好像明白了，其实没有，所以我决定研究一下这个2-2位分支预测器的一些原理。让我们继续:

两种决策 not taken代表选择顺序分支 taken代表跳转分支四种状态 00 代表strongly not taken 强顺序分支 01 代表weakly not taken 弱顺序分支 10 代表weakly taken 弱跳转分支 11 代表strongly taken 强跳转分支

让我们继续看看状态机迁移后的2-2位动态分支预测:

当前状态处于00 强顺序分支时 必然预测下一次也是顺序分支，此时会有两种结果，预测成功了，下一次状态仍然是00，预测失败了，最终程序选择了跳转分支，下一次状态变为01。

当前状态处于01 弱顺序分支时 必然预测下一次也是顺序分支，此时会有两种结果，预测成功了，下一次状态调整为00，预测失败了，最终程序选择了跳转分支，下一次状态变为10。

当前状态处于10 弱跳转分支时 必然预测下一次也是跳转分支，此时会有两种结果，预测成功了，下一次状态调整为11，预测失败了，最终程序选择了顺序分支，下一次状态变为01。

当前状态处于11 强跳转分支时 必然预测下一次也是跳转分支，此时会有两种结果，预测成功了，状态不变仍然是11，预测失败了，最终程序选择了顺序分支，下一次状态变为10。

这里的坚持，说明你真的是一个学习者。让我们画一张完整的迁移图:

从这个图可以看出，从顺序分支变成跳转分支需要连续两次预测失败，同一个跳转分支变成顺序分支，也需要连续两次预测失败:

标记分支状态和分支历史的内存部分称为BTB。这部分内存只存储分支指令地址、预测目标地址和预测位。这部分比较复杂，这里就不展开了。

通过前面的分析可以看出，动态分支预测器具有一定的容错性，并且其波动性较小。只有连续两次预测失败才会改变选择结果，整体准确率会有明显提高。

根据一些文章的数据，2-2位预测器的准确率在大多数情况下可以达到95%以上:

回顾问题

经过前面的分析，我们再回到stackoverflow，数组排序和无序的耗时问题。这个问题有两个关键因素:

数组元素是完全随机的，本次结果和上次结果是独立分布的大量循环结构和条件判断的存在

没错，随机+循环+条件完全击中了CPU流水线的软肋。

数组排序之后的分支预测

数组未排序的分支预测

数组排序后，动态分支预测会结合之前的结果做出判断，准确率很高。当数组没有排序时，完全随机和静态的分支预测几乎一样，所以精度一般。

分支预测失败意味着流水线将排队空，丢弃已经IF和ID的指令，然后选择正确的指令。整个过程会在当前CPU上浪费10-20个时钟周期，很费时间。

总结

本文从一个关于stackoverflow上随机数组排序和未排序求和的问题开始。

进一步用最简单的5级CPU流水线来说明基本原理和流水线存在的三种风险，以及各自的解决方案，特别是控制风险。

进一步阐述了控制风险中的分支预测技术，分析了双模动态分支预测器的基本原理。

最后，结合stackoverflow问题，揭示了循环结构下流水线分支预测和随机数组排序/未排序的不同决策结果的巨大耗时影响。