x86高性能编程笺注(2)-流水线
性能优化，关键在于伺候好CPU。作为一个追求性能极致的程序员，了解CPU的内部机制是一个不可回避的话题。这是一个需要日积月累的持续的过程，但也并不需要深入到数字电路的程度，就像一个设计CPU的专家并不一定精通软件设计一样，你也并不需要成为一个CPU专家才能写出高性能的软件。
作为一小撮人类精英送给普罗大众的珍贵礼物，能在市场上随意购买到的CPU其实和买不到的核武器一样代表了人类最尖端的科技水平。即便是一位x86 CPU专家也只能无一遗漏地讲清楚他所专攻的那一部分内容。对于我们来说，虽然不可能尽懂，但有三个部分的内容十分关键：流水线、缓存和指令集。这三个部分之中，“流水线”可以作为一条贯穿的线索。因此，承接上一篇文章中的示例，我们先来了解一下流水线。
基本概念
CPU的主要工作是依据指令执行对数据的操作。这句话基本上解释了什么是流水线。我知道能点开这篇文章的人都不可能对“流水线”这个概念一无所知，我也不想一上来就铺陈大段大段教科书式的文本，罗列各个概念的定义，这完全是在一心一意地舍本逐末。技术的发展只是事物矛盾的一种运动形式，这次我们将尝试从CPU的历史沿革的角度切入对流水线各个组件的介绍。
从40年前Intel生产第一颗8086处理器直到今天，CPU的变化已经让你觉得以前的处理器都只能叫做“单片机”。但即便真的是淘宝上几毛钱一个的单片机，也有和今天的i7处理器相通的地方。8086处理器有14个今天仍在使用的寄存器：4个通用寄存器(General Purpose Register)，4个段寄存器(Segment Register)，4个索引寄存器(Index Register)，1个标志位寄存器(EFLAGS Register)用于标示CPU状态，以及最后一个，指令指针寄存器(Instruction Pointer Register)，用来保存下一个需要执行的指令的地址。这个指令指针寄存器，就直接涉及到流水线的操作过程，它的持续存在，也表明了流水线基本原理的时间一致性。
从40年前到现在，所有CPU执行过的指令都遵循以下的流程：CPU首先依据指令指针取得(Fetch)将要执行的指令在代码段的地址，接下来解码(Decode)地址上的指令。解码之后，会进入真正的执行(Execute)阶段，之后会是“写回”(Write Back)阶段，将处理的最终结果写回内存或寄存器中，并更新指令指针寄存器指向下一条指令。这基本上是一个完全符合人类逻辑的设计方案。
最初，也是最自然地，CPU会一个接一个地处理全部指令。每一个指令都按上面的过程执行完毕，然后执行下一个指令。那个时候的主要矛盾还是软件日益增长的性能需求同落后的CPU处理速度之间的矛盾。在摩尔定律的正确指导下，CPU建设工作取得了历史性成果，主要矛盾发生了转移：CPU的执行速度慢慢快过了内存读写的速度。所以每次都去内存读取指令越来越成为不能承受之重，因此在1982年，处理器中引入了指令缓存。
当CPU的速度越来越快，数据缓存作为矛盾双方互相妥协的产物也引入到处理器之中。但这些都不是治本之法。矛盾的主要方面在于，CPU并没有以饱和的状态运转。于是在1989年，i486处理器建设性地引入了五级流水线。其思路就是以拉动内需的方式消化CPU的过剩产能：改一次只能处理一条指令为一次处理五条。
从网上以“CPU pipeline”为关键字搜索总会找到类似下图的图片：
我不知道诸位怎么看，反正我对着这幅图理解起来总是有困难。提供一个简单的理解：将每条指令都想象为一个待加工的产品，在一条有5个加工工序的流水线上鱼贯而入。这样可以让CPU的每一道工序始终保持工作量饱和，也就从根本上提升了指令的吞吐和程序的性能。
流水线引入的问题
考虑一个简单的交换变量值的代码：
a = a ^ b;
b = a ^ b;
a = b ^ a;
如果简单地将每一行代码抽象为一个XOR指令，按上图i486流水线的示意，第一条指令进入流水线Fetch阶段，然后进入D1阶段，此时第二条指令进入Fetch。在下一个机器周期，第一条指令进入D2，第二条进入D1，同时Fetch第三条指令。到此为止一切正常，但下一个机器周期，当第一条指令进入Execute阶段的时候，第二条指令并不能继续进入下一阶段，因为它所需要的变量a的最终结果，必须在第一条指令执行完毕之后才能获得。所以第二条指令会阻塞在流水线之上，等第一条指令执行完毕才会继续。而在第二条指令执行的过程中，第三条指令也会有类似的遭遇。当出现了流水线阻塞的情况，指令的流水线式执行就会与单独执行之间拉开距离，这被称为流水线“气泡”(bubble)。
Side Notes:
时钟周期：也叫震荡周期。是时钟频率（主频）的倒数，是最小的时间周期
机器周期：流水线中的每个阶段称为一个基本操作，完成一个基本操作所需要的时间为机器周期
指令周期：执行一条指令所需要的时间，一般由多个机器周期组成
除了上面的情况，还有一种常见的原因导致气泡的产生。执行每条指令所需要消耗的时间（指令周期）是不同的。当一条简单指令前面是一条耗时较长的复杂指令的时候，简单指令不得不等待复杂指令。另外，如果程序里出现if这类分支呢？这些情况都会导致流水线不能满负荷工作，从而导致性能的相对下降。
在面对问题的时候，人总是会倾向于引入一个更复杂的机制来解决问题，多级流水线就是一个例子。复杂可以反映出技术的改良，但“复杂”本身就是一个新的问题。这也许就是矛盾永远不会消失，技术也不会停止进步的原因。但“为学日益，为道日损”，愈发复杂的机制总会在某个时机之下发生大破大立，但可能现在时机还没有到来:D面对“气泡”问题，处理器又引入了一个更复杂的解决方案——1995年Intel发布Pentium Pro处理器时，加入了乱序执行核心(Out-of-order core, OOO core)。
乱序执行核心（OOO core)
其实乱序执行的思想很简单：当下一条指令被阻塞的时候，从后面的指令里再找一条能执行的就好了嘛。但要完成这个工作却相当复杂。首先要保证程序的最终结果与顺序执行一致，同时要识别各类数据依赖。要达到理想的效果，除了并行执行之外，还需要对指令的粒度进一步细化，以达到以无厚入有间的效果，这样就引入了“微操作”(micro-operations, μ-ops)的概念。在流水线的Decode阶段，汇编指令又被进一步拆解，最终的产物就是一系列的微操作。
上图就是引入乱序处理核心之后的指令μ-ops处理流程。不同颜色的模块对应第一张图中不同颜色的流水线处理阶段。
Fetch阶段没有太多变化，在Decode阶段，可以并行对四条指令解码，解码的最终产物就是上面提到的μ-ops。后面的Register Alias Table和Reorder Buffer可以当做是乱序执行核心的预处理阶段。
对于并行执行的微操作，或者乱序执行的操作，很有可能会同时读写同一个寄存器。所以在处理器内部，原始的寄存器便被“别名”(aliased)为内部对软件工程师不可见的寄存器，这样原本在同一个寄存器上执行的操作便可以在临时性的不同的寄存器上执行，无论读写，互不干扰(注意：这里要求两个操作没有数据依赖)。而对应的微操作的操作数也变为了临时性的别名寄存器，相当于一种空间换时间的策略，并且同时对微指令进行了一次基于别名寄存器的转译。
之后微操作进入Reorder Buffer。至此，微指令已经准备就绪。它们会被放入Reservation Station(RS)并被并行执行。从图中可以看到相当多的执行单元(Port X)。每一个执行单元都执行一个特定的任务，比如读取(Load)，写入(Store)，整数计算（ALU, SEE）等等。而每一条相关的微指令都可以在它所需要的数据准备好之后执行。这样耗时较长的指令和有数据依赖关系的指令，虽然单从其自身的角度看，并没有任何变化，但它们所带来的阻塞的开销，被后续指令的并行及乱序（提前）执行所分摊，化整为零，带来整体吞吐的提升。
乱序执行核心的神奇之处就在于，它能够最大限度地提升这套机制的效率，并且在外界看来，指令是在顺序执行。这里面的详细细节不在本文的讨论范畴。但乱序执行核心是如此成功，以至于引入该机制的CPU即便是在大工作负载的情况下乱序执行核心仍会在大部分时间处于空闲的状态，远未饱和。因此，又引入了另外一个前端(Front-end,包括Fetch和Decode)给该核心输送μ-ops，在系统看来，便可以抽象为两个处理核心，这也就是超线程(Hyper-thread)N个物理核心，2N个逻辑核心的由来。
Side Note:乱序执行也并不一定100%达到顺序执行代码的效果。有些时候确实需要程序员引入内存屏障来确保执行的先后顺序。
但复杂的事物总会引入新的问题，这次矛盾转移到了Fetch阶段。如何在面对分支的时候选取正确的路？如果指令选取错误，整条流水线需要首先等待剩余指令执行完毕，清空之后再重新从正确的位置开始。流水线的层次越深，造成的伤害越大。后续的文章，将会介绍一些在编程层面优化的方法。
