1 冯·诺依曼体系架构

  今天我们谈及CPU的架构，往往会说起X86架构，ARM架构，MIPS架构等等，其实这些CPU架构都属于冯·诺依曼体系架构（也称普林斯顿体系架构）。

  **从功能上看，一般CPU的内部结构可分为：控制单元(Control Unit)、逻辑运算单元(ALU)、片内存储单元（on-chip memory）三大部分。

  控制单元：控制单元是整个CPU的指挥控制中心，由指令寄存器IR（Instruction Register）、指令译码器ID（Instruction Decoder）和操作控制器OC（Operation Controller）等，对协调整个电脑有序工作极为重要。它根据用户预先编好的程序，依次从存储器中取出各条指令，放在指令寄存器IR中，通过指令译码（分析）确定应该进行什么操作，然后通过操作控制器OC，按确定的时序，向相应的部件发出微操作控制信号。操作控制器OC中主要包括节拍脉冲发生器、控制矩阵、时钟脉冲发生器、复位电路和启停电路等控制逻辑。

  运算单元：是运算器的核心。可以执行算术运算（包括加减乘数等基本运算及其附加运算）和逻辑运算（包括移位、逻辑测试或两个值比较）。相对控制单元而言，运算器接受控制单元的命令而进行动作，即运算单元所进行的全部操作都是由控制单元发出的控制信号来指挥的，所以它是执行部件。

   存储单元：包括CPU片内缓存和寄存器组，是CPU中暂时存放数据的地方，里面保存着那些等待处理的数据，或已经处理过的数据，CPU访问寄存器所用的时间要比访问内存的时间短。采用寄存器，可以减少CPU访问内存的次数，从而提高了CPU的工作速度。但因为受到芯片面积和集成度所限，寄存器组的容量不可能很大。寄存器组可分为专用寄存器和通用寄存器。专用寄存器的作用是固定的，分别寄存相应的数据。而通用寄存器用途广泛并可由程序员规定其用途，通用寄存器的数目因微处理器而异。

2 CPU运行原理

   我们将上图细化一下，可以得出CPU的工作原理图如下：

  CPU的运行原理如下：

（1）取指令阶段：
  取指令（Instruction Fetch，IF）阶段是将一条指令从主存中取到指令寄存器的过程。程序计数器PC中的数值，用来指示当前指令在主存中的位置。当一条指令被取出后，PC中的数值将根据指令字长度而自动递增。

   指令的格式一般是这个样子滴：

  操作码就是汇编语言里的mov，add，jmp等符号码；操作数地址说明该指令需要的操作数所在的地方，是在内存里还是在CPU的内部寄存器里。
（2）指令译码阶段
  取出指令后，计算机立即进入指令译码（Instruction Decode，ID）阶段。在指令译码阶段，指令译码器按照预定的指令格式，对取回的指令进行拆分和解释，识别区分出不同的指令类别以及各种获取操作数的方法。
（3）执行指令阶段
  在取指令和指令译码阶段之后，接着进入执行指令（Execute，EX）阶段。此阶段的任务是完成指令所规定的各种操作，具体实现指令的功能。为此，CPU的不同部分被连接起来，以执行所需的操作。
（4）访存取数阶段
  根据指令需要，有可能要访问主存，读取操作数，这样就进入了访存取数（Memory，MEM）阶段。此阶段的任务是：根据指令地址码，得到操作数在主存中的地址，并从主存中读取该操作数用于运算。

（5）结果写回阶段
  作为最后一个阶段，结果写回（Write Back，WB）阶段把执行指令阶段的运行结果数据“写回”到某种存储形式。结果数据经常被写到CPU的内部寄存器中，以便被后续的指令快速地存取；在有些情况下，结果数据也可被写入相对较慢、但较廉价且容量较大的主存。许多指令还会改变程序状态字寄存器中标志位的状态，这些标志位标识着不同的操作结果，可被用来影响程序的动作。在指令执行完毕、结果数据写回之后，若无意外事件（如结果溢出等）发生，计算机就接着从程序计数器PC中取得下一条指令地址，开始新一轮的循环，下一个指令周期将顺序取出下一条指令。

3 CPU流水线

3.1 流水线概念

   流水线的概念来源于工业制造领域，以汽车装配为例来解释流水线的工作方式，假设装配一辆汽车需要四个步骤：

   第一步冲压：制作车身外壳和底盘等部件。

   第二步焊接：将冲压成形后的各部件焊接成车身。

   第三步涂装：将车身等主要部件清洗、化学处理、打磨、喷漆和烘干。

   第四步总装：将各部件（包括发动机和向外采购的零部件）组装成车。

   汽车装配则同时对应需要冲压、焊接、涂装和总装四个工人。最简单的方法是一辆汽车依次经过上述四个步骤装配完成之后，下一辆汽车才开始进行装配，最早期的工业制造就是采用的这种原始的方式，即同一时刻只有一辆汽车在装配。不久之后人们发现，某个时段中一辆汽车在进行装配时，其它三个工人都处于闲置状态，显然这是对资源的极大浪费，于是思考出能有效利用资源的新方法，即在第一辆汽车经过冲压进入焊接工序的时候，立刻开始进行第二辆汽车的冲压，而不是等到第一辆汽车经过全部四个工序后才开始，这样在后续生产中就能够保证四个工人一直处于运行状态，不会造成人员的闲置。这样的生产方式就好似流水川流不息，因此被称为流水线。

   在工业制造中采用流水线可以提高单位时间的生产量，同样在处理器中采用流水线设计也有助于提高处理器的性能。以上述的五级流水线为例，由于前一条指令在完成了“取指”进入“译码”阶段后，下一条指令马上就可以进入“取指”阶段，依次类推，如图2所示，如果流水线没有停顿，理论上可以取得每个时钟周期都完成一条指令的性能。

  流水线是一种指令级并行技术。

3.2 停顿问题

   首先看个停顿的列子：

                                                          a = b + c;                                                          d = e - f;

   根据流水线的概念，上述代码在CPU内执行示意图如下所示，途中红色框代表停顿。那么为什么会出现停顿呢” />

   为了减少停顿，我们只需要将LW Re, e和LW Rf, f移动到前面执行，如下图所示。

  由此可见，指令重排序对提高CPU性能十分必要，但是要遵循happens-before规则：

（1）同一个线程中的每个Action都happens-before于出现在其后的任何一个Action。

（2）对一个监视器的解锁happens-before于每一个后续对同一个监视器的加锁。

（3）对volatile字段的写入操作happens-before于每一个后续的同一个字段的读操作。

（4）Thread.start()的调用会happens-before于启动线程里面的动作。

（5）Thread中的所有动作都happens-before于其他线程检查到此线程结束或者Thread.join（）中返回或者Thread.isAlive()==false。

（6）一个线程A调用另一个另一个线程B的interrupt（）都happens-before于线程A发现B被A中断（B抛出异常或者A检测到B的isInterrupted（）或者interrupted()）。

（7）一个对象构造函数的结束happens-before与该对象的finalizer的开始

（8）如果A动作happens-before于B动作，而B动作happens-before与C动作，那么A动作happens-before于C动作。

3.3 乱序执行

   现在的CPU一般采用流水线来执行指令。一个指令的执行被分成：取指、译码、访存、执行、写回、等若干个阶段。然后，多条指令可以同时存在于流水线中，同时被执行。
指令流水线并不是串行的，并不会因为一个耗时很长的指令在“执行”阶段呆很长时间，而导致后续的指令都卡在“执行”之前的阶段上。

   相反，流水线是并行的，多个指令可以同时处于同一个阶段，只要CPU内部相应的处理部件未被占满即可。比如说CPU有一个加法器和一个除法器，那么一条加法指令和一条除法指令就可能同时处于“执行”阶段, 而两条加法指令在“执行”阶段就只能串行工作。

   相比于串行+阻塞的方式，流水线像这样并行的工作，效率是非常高的。然而，这样一来，乱序可能就产生了。比如一条加法指令原本出现在一条除法指令的后面，但是由于除法的执行时间很长，在它执行完之前，加法可能先执行完了。再比如两条访存指令，可能由于第二条指令命中了cache而导致它先于第一条指令完成。

   一般情况下，指令乱序并不是CPU在执行指令之前刻意去调整顺序。CPU总是顺序的去内存里面取指令，然后将其顺序的放入指令流水线。但是指令执行时的各种条件，指令与指令之间的相互影响，可能导致顺序放入流水线的指令，最终乱序执行完成。这就是所谓的“顺序流入，乱序流出”。

   指令流水线除了在资源不足的情况下会卡住之外（如前所述的一个加法器应付两条加法指令的情况），指令之间的相关性也是导致流水线阻塞的重要原因。
  CPU的乱序执行并不是任意的乱序，而是以保证程序上下文因果关系为前提的。有了这个前提，CPU执行的正确性才有保证。

   举个例子：

                                                            a++;                                                            b = a * 1000;                                                            c--;

   由于b = a * 1000这条指令依赖于前一条指令a++的执行结果，所以b = a * 1000将在“执行”阶段之前被阻塞，直到a++的执行结果被生成出来；而c–跟前面没有依赖，它可能在b = a * 1000之前就能执行完。

   像这样有依赖关系的指令如果挨得很近，后一条指令必定会因为等待前一条执行的结果，而在流水线中阻塞很久，占用流水线的资源。而编译器的乱序，作为编译优化的一种手段，则试图通过指令重排将这样的两条指令拉开距离, 以至于后一条指令进入CPU的时候，前一条指令结果已经得到了，那么也就不再需要阻塞等待了。比如将指令重排为：

                                                           a++;                                                           c--;                                                            b = a * 1000;

   相比于CPU的乱序，编译器的乱序才是真正对指令顺序做了调整。但是编译器的乱序也必须保证程序上下文的因果关系不发生改变。

3.4 指令重排

   重排序通常是编译器或运行时环境为了优化程序性能而采取的对指令进行重新排序执行的一种手段。重排序分为两类：编译期重排序和运行期重排序，分别对应编译时和运行时环境。

   在并发程序中，程序员会特别关注不同进程或线程之间的数据同步，特别是多个线程同时修改同一变量时，必须采取可靠的同步或其它措施保障数据被正确地修改，这里的一条重要原则是：不要假设指令执行的顺序，你无法预知不同线程之间的指令会以何种顺序执行。

   但是在单线程程序中，通常我们容易假设指令是顺序执行的，否则可以想象程序会发生什么可怕的变化。理想的模型是：各种指令执行的顺序是唯一且有序的，这个顺序就是它们被编写在代码中的顺序，与处理器或其它因素无关，这种模型被称作顺序一致性模型，也是基于冯·诺依曼体系的模型。当然，这种假设本身是合理的，在实践中也鲜有异常发生，但事实上，没有哪个现代多处理器架构会采用这种模型，因为它是在是太低效了。而在编译优化和CPU流水线中，几乎都涉及到指令重排序。

3.4.1 编译期重排序

   编译期重排序的典型就是通过调整指令顺序，在不改变程序语义的前提下，尽可能减少寄存器的读取、存储次数，充分复用寄存器的存储值。

   假设第一条指令计算一个值赋给变量A并存放在寄存器中，第二条指令与A无关但需要占用寄存器（假设它将占用A所在的那个寄存器），第三条指令使用A的值且与第二条指令无关。那么如果按照顺序一致性模型，A在第一条指令执行过后被放入寄存器，在第二条指令执行时A不再存在，第三条指令执行时A重新被读入寄存器，而这个过程中，A的值没有发生变化。通常编译器都会交换第二和第三条指令的位置，这样第一条指令结束时A存在于寄存器中，接下来可以直接从寄存器中读取A的值，降低了重复读取的开销。

3.4.2 重排序对于流水线的意义

   现代CPU几乎都采用流水线机制加快指令的处理速度，一般来说，一条指令需要若干个CPU时钟周期处理，而通过流水线并行执行，可以在同等的时钟周期内执行若干条指令，具体做法简单地说就是把指令分为不同的执行周期，例如读取、寻址、解析、执行等步骤，并放在不同的元件中处理，同时在执行单元EU中，功能单元被分为不同的元件，例如加法元件、乘法元件、加载元件、存储元件等，可以进一步实现不同的计算并行执行。

   流水线架构决定了指令应该被并行执行，而不是在顺序化模型中所认为的那样。重排序有利于充分使用流水线，进而达到超标量的效果。

3.4.3 确保顺序性

   尽管指令在执行时并不一定按照我们所编写的顺序执行，但毋庸置疑的是，在单线程环境下，指令执行的最终效果应当与其在顺序执行下的效果一致，否则这种优化便会失去意义。

通常无论是在编译期还是运行期进行的指令重排序，都会满足上面的原则。

3.5 旁路bypass

   五级流水线整体图示：

  某些指令执行的流水线级数

   由上面两幅图可知，流水线的第四级是Data Memory，用于数据的存入和读取，但是CPU的指令集中除了LOAD指令和STORE指令在第四级流水线使用了Data Memory里的数据，其他的指令并没有在这一级流水线进行了任何的操作（并没有使用Data Memory里的数据），也就是说，流水线第四级对除LOAD指令和STORE指令之外的指令并没有实质意义，但却导致了不必要的功率损耗。因此，对于LOAD、STORE之外的指令，四级流水线（将WB级提前一级）的采用可以减少不必要的功率损耗。

   但是由于某些指令需要五级流水线，而某些只需四级流水线（将WB阶段提前一级），但在实现的过程中要注意冲突问题。

   为更清晰的表达利用旁路实现低功耗的原理和讨论冲突问题，先将25条指令（27条指令除去NOP和HALT指令）分为四类：

（1）第一类指令：LOAD

IFIDEXMEMWB

（2）第二类指令：STORE，JMPR，BZ，BNZ，BN，BNN，BC，BNC

IFIDEXMEMNOP

（3）第三类指令：LDIH、ADD、ADDI、ADDC、SUB、SUBI、SUBC、OR、AND、SLL、SRL、SLA、SRA

IFIDEXNOPWB

（4）第四类指令：CMP，JUMP

IFIDNOPNOPNOP

   由上面的分类可知：第一类指令必须采用五级流水线；第二类指令，空操作NOP处于流水线第五级（流水线最后一级），没有办法对流水线提前一级；第四类指令，空操作NOP处于流水线第四第五级，也没有办法对流水线提前一级；第三类指令，空操作NOP只处于流水线第四级，可提前一级流水线，但当前指令为第三类中的指令时，上一条指令的WB阶段不为NOP时，若把当前指令的WB阶段提前一级，会出现冲突，也就是说把当前指令的WB阶段提前一级的前提是上一条指令是第二类或者第四类指令，不能为第一类指令。

   算术类指令并没有使用到流水线第四阶段，data memory. 同时,STORE指令并不需要WB这一级流水线，而LOAD指令通过了五级流水线。在无用的阶段中的转化会造成额外的功率消耗，这些不必要的转化可以通过在无用的阶段中旁路来实现减少。在算术类指令中不需要访问内存，因此由EX阶段得到的数据可以直接传给第五阶段WB。

3.6 分支预测和分支断定

   当包含流水线技术的处理器处理分支指令时就会遇到一个问题，根据判定条件的真/假的不同，有可能会产生跳转，而这会打断流水线中指令的处理，因为处理器无法确定该指令的下一条指令，直到分支执行完毕。流水线越长，处理器等待的时间便越长，因为它必须等待分支指令处理完毕，才能确定下一条进入流水线的指令。

   分支预测(Branch Prediction)：从P5时代开始的一种先进的，解决处理分支指令（if-then-else)导致流水线失败的数据处理方法，由CPU来判断程序分支的进行方向，能够加快运算速度。

   分支预测技术包含编译时进行的静态分支预测和硬件在执行时进行的动态分支预测。

3.6.1 静态分支预测

   要进行分支预测，就要预测分支跳还是不跳。最朴素的想法是预测一直跳或者一直不跳，这样的方法虽然简单，但是也比完全不预测要高明。完全不预测是100%地要阻断流水线，而预测一直跳或者预测一直不跳还有机会预测对，预测到就是赚到。预想一个1000次的for循环，这个循环前999次都是跳转而最后一次不跳转，如果处理器设置为预测一定跳转，那么在执行这段指令的时候其准确率高达99.9%，性能远远高于不做预测的处理器。

   最简单的静态分支预测方法就是任选一条分支。更精确的办法是根据原先运行的结果进行统计从而尝试预测分支是否会跳转。

   静态分支预测有如下特点：

（1）编译时进行，不需要额外的CPU的支持；

（2）任选一条分支：认为branch一定token或者一定不token；

（3）平均命中率50%。

3.6.2 动态分支预测

   动态分支条件预测是指硬件单元收集一些过去的程序运行时的信息，通过这些信息来动态的预测分支条件。

一种非常经典的动态分支条件预测器结构如下图所示：

  程序过去执行时分支的信息被存放在一个长度为 的表中，表中的每一项为 2 bit。该表通过指令 PC 的最低 n bits 来索引。每一项的 2 bits 都构成一个有限状态机，用来预测分支跳转条件。

这种预测器被称作局部分支预测器（local branch predictor）。这是因为该预测器在进行预测时，每个分支指令只使用自己过去的跳转状态来进行预测。对于 highly biased 的分支_（不知道该咋翻了，大概意思就是分支在一定时间内要么经常跳转，要么经常不跳转，总之会偏向一边）_，该分支预测器表现很好。如果分支条件经常是 not taken，那么状态机的状态会是 00；而如果分支条件经常是 taken，那么状态机的状态会是 11；即使分支条件 taken or not taken 发生变化，只要在一定时间内不要频繁波动，状态机也会跟随这分支条件的变化而有效变化。

当然，两个分支指令的最低 n bits 有可能是完全一样的，因此会映射到同一个表项中，这种情况被称为 aliasing。一般来说，aliasing 会降低这类预测器的性能_（毕竟会互相干扰嘛）_

2-bit 局部分支预测器一般可以达到 >80% 的预测精度，在一些特殊的程序上可以达到 99%。但是对于高性能的处理器来说，由于预测错误带来的性能损失，即使只有 10% 的预测错误也会造成很大的性能影响。预测错误会导致流水线被 flush，取指单元需要重新从正确的分支地址中取出指令，重新填充流水线，这一过程至少需要 10+ 周期。这对于分支较多的程序来说影响会非常大。如果处理器是一个超标量处理器的话，一次分支预测错误带来的损失则会更大。例如处理器重新填充流水线需要 10 个周期，每个周期可以 4 发射的话，一次错误的分支预测相当于损失了 40 条指令的执行。

为了进一步提升分支条件预测器的精度，目前的处理器会引入一种叫关联预测器（correlating predictor，或被称为 two-level branch predictor）的硬件单元。不同于局部预测器，关联预取器不仅会根据当前分支指令的历史信息来预测，还会根据它的“邻居”的历史信息来预测。

一种最简单的关联预测器结构如下：

   硬件用一个叫 branch global history 的寄存器，来存储最近几次分支的条件结果（每个分支用 1 bit 存储即可）。一般 10~20 个 bit 就足够了。这个寄存器跟指令 PC 做 hash 后，得到的 index 用来从表中选取状态机。更新分支预测结果时，也用同样的方法从表中找到对应的状态机并更新。这种预测器也被称为 gshare。

关联预测器的核心思路是：对于同一个分支指令，根据不同的全局分支条件结果，选用不同的状态机来预测当前分支的条件结果。当然，关联预测器也无法完全避免 aliasing 的问题。如果每一种分支条件结果、每一个分支都有对应的状态机的话，虽然 aliasing 的问题被避免了，但表项会过大。因此为了保证硬件设计的高效，aliasing 还是不可避免的，但从性能角度上能一定程度上容忍。

branch global history 有很多种跟 PC 做 hash 的方式。例如前面提到的 gshare，两者通过 bitwise OR 操作来作为 index 就能取得不错的效果。当然也可以像下图一样，用多个寄存器来存储全局的历史分支信息。预测时，先通过 PC 选择用哪个寄存器，再通过该寄存器与 PC 的 hash 后得到的 index 从表中选择状态机：

  现代处理器通常采用动态分支预测，即硬件（CPU front end）有单独的分支预测逻辑（对软件透明）。总的来说，动态分支预测的核心就是根据分支历史信息来预测当前分支的方向。其中历史信息可以包含很多architectural state，比如PC，相同PC下branch的历史结果（local history），全局branch历史结果（global history），等等。下面介绍几个经典的分支预测器以及现代的分支预测器。

   影响关联预测器预测分支条件精度的因素有：

  • global history register 的数量

  • 有限状态机表的项数

  • 有限状态机状态数量_（比如 3-bit、4-bit 有限状态机有更多的状态数）_

  • PC 到状态机的映射方法_（例如 hash 函数是怎样的，多个 global history register 如何选择等等）_

   没有适合所有程序的预测器。有的程序可能更适合使用全局分支信息来进行预测，而有的程序可能恰恰相反。因此，一些处理器会集成多种预测器，并进行混合。

   混合分支预测器（hybrid branch predictors）除了有多个预测器外，还有一个额外的单元用来选择具体采用哪个预测器的结果（selector），其结构如下图所示：

   selector 也是根据 PC 和一些全局信息，选定有限状态机来决定使用哪一个预测器的结果。当分支执行的结果出来后，根据多个预测器的表现，来更新选择的策略_（当然预测错误的预测器本身也需要更新）。

   混合分支预测器不仅仅可以适应不同的程序，它的另一项作用在于：不同的预测器 warm-up 时间不同，因此需要 selector 在程序执行的不同时间点选择合适的预测器。当程序刚刚启动，或 CPU 刚刚从别的线程切换回来时，预测器里面存储的信息是与当前程序无关的，无法用来准确预测分支条件，需要运行一段时间进行 warm-up 来将预测准确率提升到较高水平。局部预测器因为只使用当前分支的历史跳转情况，因此能够很快的完成 warm-up；而关联预测器虽然最终预测精度较高，但需要更长的时间 warm-up。因此当发生程序刚启动或线程切换的情况时，selector 会先选择 warm-up 较快的局部预测器，一段时间后选择精度更高的关联预测器。

   动态分支预测有如下特点：

（1）运行时进行；

（2）根据同一条转移指令过去的转移情况来预测未来的转移情况：分支预测缓冲区和分支历史表；

3.6.3 利用分支预测提高效率

3.6.1 避免分支预测开销

   优化前：

if (a > b) {   return a - b;} else {   return b - a;}

   优化后：

return (a > b) " />
4 参考文献
cpu的基本结构及其工作原理 - 知乎 (zhihu.com)
CPU流水线 - myseries - 博客园 (cnblogs.com)
https://www.zhihu.com/question/486239354/answer/2129757853
https://www.zhihu.com/question/486239354/answer/2500054973
https://blog.csdn.net/Betsy69/article/details/44020699
https://blog.csdn.net/wangeen/article/details/8154788