第1章 超标量处理器概览 摘录_2. 下列指令序列,各存在什么相关性,在超标量中是如何解决这些相关性的? i1: load

1.1 为什么需要超标量？

如何才能让程序执行得更快？在计算机领域中计算一个程序的执行时间：

影响程序执行时间的因素：
        1. Total Instructions：程序总共需要执行指令的个数；
        2. Cycles/Instructions：执行每条指令所需要的周期数；
        3. Seconds/Cycle：每周期需要的时间；

从上面三个因素可以看出，要加快执行程序的速度，可以采取的策略有如下方式：
        (1) 减少程序中指令的数量，这个主要取决于程序本身要完全的工作量，实现某个功能所需要的算法、编译器强大与否、甚至硬件是否会对某些特殊的功能有扩展。比如x86指令集中的多媒体指令。
        (2) 减少每条指令在处理器中执行所需要的周期数，也就是减少CPI，意味着增加IPC(Instructions Per Cycle)，其中，CPI与IPC互为倒数、CPI表示处理器执行一条指令需要的周期数，而IPC则表示处理器在一个周期内可以执行的指令个数。对于非流水线的处理器而言，需要多个周期才能执行一条指令，而对于普通的流水线处理器，每周期最多执行一条指令，因此IPC最大也就是1。可以使用超标量处理器来提高IPC。
        (3) 减少处理器的周期时间，经过精巧的电路设计、更深的流水线来减少处理器的周期时间。

从三个因素可以看出，在程序确定的情况下，需要处理器有比较大的IPC，以及更快的运行频率。但是实际中这两个因素是相互制约的，更大的IPC要求每周期更多的指令，这样设计复杂度会剧烈上升，导致处理器的周期时间很难降低下来。

虽然可以通过更深的流水线来获得小的周期时间，但是却导致处理器在各种预测失败时，例如分支预测失败(mis-prediction)，有着更大的惩罚(penalty)，严重降低处理器的IPC，并增大了功耗。造成“高频低能”的后果。

每周期可以从I-Cache中取出的n条指令送到处理器的流水线中，处理器在每周期内最少可以同时执行n条指令，这称为n-way的超标量处理器是。

在处理器的发展史中，每周期执行多于一条指令的处理器并非超标量一种，超长指令字(Very Long Instruction Word, VLIW)也是一种每周期可以执行多条指令的处理器架构。

这两种架构本质区别是：超标量处理器是靠硬件自身来决定哪些指令可以并行地执行，而VLIW处理器则是依靠编译器和程序员自身来决定那些指令可以并行执行。

对于通用处理器来说，超标量结构是必须的，程序员可以抛开底层硬件的实现细节，专注于软件本身的功能，而且这个程序可以运行在任何支持该指令集的处理器上。而VLIW则无法实现这个功能。

超标量处理器可以获得比较高的IPC，也伴随着天生的复杂性。导致处理器设计师需要根据实际情况作出各种折中(tradeoff)。例如，实现一个精准的分支预测算法需要复杂的硬件资源，导致其在一个周期无法完成，则处理器无法马上利用预测信息进行连续的取指令，这样处理器的性能就会下降。再比如load/store指令如果按照完全乱序的方式执行虽然会获得最大的IPC，却会导致load/store指令之间的相关性检查变得非常复杂，而且一旦发现相关性违例，还需要复杂的回复机制，导致硬件复杂度和功耗的增加。以及，CheckPoint的个数和硬件的面积，发射队列(issue queue)和仲裁(select)电路的复杂度，每周期可以同时执行的指令个数(issue width)和寄存器堆(register file)的端口个数。

要想获得更好的性能，就需要更复杂的设计和更多硬件资源，由此带来了更高的成本和功耗。注意服务器和桌面PC领域的处理器应该将性能放在第一位。移动领域在保证性能的情况下，尽量降低设计的复杂度，才能获得比较低的功耗。

1.2 普通处理器的流水线

1.2.1 流水线概述

流水线是现代处理器获得高性能的重要法宝，通过流水线可以降低处理器的周期时间(cycle time)，从而获得更快的执行频率。

当处理器没有使用流水线时，它的周期时间是D，也就是频率是1/D；使用n级流水线后，周期时间变为“D/n+S”，其中S表示流水线寄存器的延迟。

在加入流水线后，处理器所需硬件也有了变化。

当处理器没有使用流水线时，需要消耗的硬件面积为G；当使用了n级流水线后，消耗的硬件可以表示为G+n*L；

则假如流水线后的Cost/Performance = （G+n*L）/(1/(D/n+S)) = GD/n + SL*n + GS；从上式可以看出，当G、D、L和S都已知的情况下，可以得到最优化的流水线级数。当然，还要考虑其他因素，例如分支预测的准确度，load/store指令的处理方式。而且不同的处理器有不同的定位，有些处理器面向高性能计算，有些面向低功耗的嵌入式应用。

1.2.2 流水线的划分

在理想情况下，流水线的划分需要满足下面一个条件：
        (1)流水线中每个阶段所需要的时间都近似相等，其中最长的流水段所需要的时间决定了整个处理器的周期时间。
        (2)流水线中每个阶段的操作都会被重复地执行。
        (3)流水线中每个阶段的操作都和其他流水段相互独立、互不相干。这一条由于存在指令之间的相关性，例如写后读。因此这一条最难满足，也是影响流水线执行效率的关键因素。

对于CISC指令级而言，指令的长度不等，并且执行时间也不等，所以直接实现流水线是比较复杂的。而对于RISC而言，由于指令的长度相等，并且每条指令所完成的任务比较规整，易于使用流水线实现。一个典型的RISC处理器的流水线如下图所示：

 流水线每个阶段完成的任务如下表所示：

下面的这个流水线未必是最优化的，因为每个阶段所需要的时间相差很多，比如

 则不使用流水线时，处理器的周期时间近似为 T = 7 + 11 + 5 + 10 + 3 = 36ns；

使用流水线后，周期时间近似为T =max(Ti) = 11ns；

使用上图的流水线可以使处理器的速度提高36/11倍，但是在上面的流水线中，各个阶段所占时间是很不平衡的，要想获得更优化设计，需要对流水线中的各个阶段进行平衡，有两种方法可以进行这个工作。

        方法一：合，将两个或多个流水段合并成一个流水段。

 

 使得流水线从五级降为三级，每个流水段所占据的时间也比较均衡，此时处理器的周期时间为13ns，这种办法适用于对性能要求不高的低功耗嵌入式处理器。

        方法二：拆，将流水线的一个阶段拆成多个更小的阶段。如下图所示：

 这种方法适合高性能处理器，可以获得比较高的主频，但是这种比较深的流水线会导致硬件消耗的增大，例如需要更多的流水线寄存器和控制逻辑；寄存器堆的端口数也需要增加，以支持多个流水段同时读写；存储器(D-Cache)端口数量也需要随之增加，用来支持更多的流水段同时访问存储器。随着芯片面积的增大和主频的提高，处理器的功耗也会随之增大，制约了这种方法的方式。而且，深流水线对于分支预测的影响也是非常大的，会导致预测失败时的惩罚(mis-prediction penalty)增大，从而影响处理器的执行效率。因此这种方法无法无限制使用下去。

 1.2.3 指令间相关性

指令之间的存在的相关性是阻碍程序并行执行的关键因素。概括来说，指令之间存在三种类型的相关性。

        (1)先写后读(Read After Write, RAW)，也称true dependence，一条指令的操作数如果来自之前指令的结果，那么这条指令必须等到之前的指令的到的结果，才可以继续执行。这种类型的相关性是无法回避的，举例如下;

指令A：R1 = R2 + R3;
指令B：R5 = R1 + R4；

        指令B的一个操作数来自于指令A的结果，所以就必须等待指令A将结果计算出来，指令B才可以继续执行。

        (2) 先读后写(Write After Read, WAR)，也称anti-dependence，一条指令要将结果写到某个寄存器中，但是这个寄存器还在被其他指令读取，所以不能马上写入。具体如下;

指令A：R1 = R2 + R3;
指令B：R2 = R5 + R4；

        指令A在读取寄存器R2之前，指令B不能将结果写到寄存器R2中，这种类型的相关性是可以避免的，只需要将指令B的结果写到其他寄存器就可以了。

        (3) 先写后写(Write After Write, WAW)，也称output dependence，如果两条指令都要将结果写到同一个寄存器中，那么后面的指令必须等待前面的指令写完之后，自己才能执行写操作，举例如下：

指令A：R1 = R2 + R3;
指令B：R1 = R5 + R4；

        指令A和指令B都将结果写到目的寄存器R1中，指令B应该在指令A之后进行写入，这种相关性也可以避免，只要后续的指令B将结果写到其他寄存器就可以了。

还有一种类型的相关性称为控制相关性(control dependence)，它是由分支指令引起的，只有当分支指令的结果被计算出来的时候，才知道从那里取得后续的指令来执行，由于分支指令需要一段时间才可以得到结果(跳转或不跳转，跳转的目标地址)。一段典型的MIPS汇编程序：

WAR、RAW和WAW这三种相关性不仅对寄存器之间的关系适用，对于存储器地址之间的相关性也适用，只不过寄存器之间的相关性可以通过指令直接表现出来，而存储器地址之间的相关性则很难看出来。

sw    r1,    0(r5)    // 将寄存器r1的值保存到MEM[r5]中
lw    r2,    0(r6)    // 将MEM[R6]的值读取到寄存器r2中

当寄存器r5和r6的值相等时，这两条指令之间存在RAW的相关性。比较隐蔽。

对于标量处理器而言，WAW和WAR这两种相关性并不会引起问题，而RAW相关性可以通过旁路(bypass)的方式来解决；对于超标量处理器来说，WAW、WAR和RAW这三种相关性会阻碍指令的乱序执行，都需要在流水线中进行特殊的处理。

1.3 超标量处理器的流水线

简单地说，如果一个处理器每周期可以取出多于一条的指令并送到流水线中执行，且使用硬件来对指令进行调度，那么这个处理器就可以被称为超标量处理器。

在这个表格中，Frontened表示流水线中的取指令(Fetch)和解码(Decode)阶段，这两个阶段很难(事实上也没有意义)实现乱序执行；

Issue表示将指令送到对应的功能单元(Function Unit, FU)中执行，这里可以实现乱序执行，因为只要将指令的源操作数准备好了，就可以先于其他指令而执行；

Write back表示将指令的结果写到目的寄存器中，可以在处理器内部使用寄存器重命名，将指令集中定义的逻辑寄存器(Architecture Register File, ARF)动态地转化为芯片内部实际使用的物理寄存器(Physcial Register File, PRF)，从而实现乱序地写回寄存器；

Commit表示一条指令被允许更改处理器的状态(Architecture state，例如D-Cache等)，为了保证程序按照原来的意图得到执行，并且实现精确的异常，这个阶段需要顺序执行，这样才能保证从处理器外部看来，程序是按照串行执行的。

1.3.1 顺序执行

在顺序执行的超标量处理器中，指令的执行必须遵循程序中指定的顺序，这种类型的流水线可以概括地用下图来表示：

上述流水线每周期可以从I-Cache中取出两条指令来执行，则称为2-way的超标量处理器，在指令经过解码之后，需要根据自身的类型，将两条指令送到对应的FU中执行，这个过程称为发射(Issue)。如果将发射过程放到指令的解码阶段，会严重影响处理器的周期时间，因此将发射过程单独使用一个流水段，在这个阶段，指令会读取寄存器而得到操作数，同时根据指令的类型，将指令送到对应的FU中进行执行。在执行阶段使用了三个FU：第一个阶段用来执行ALU类型的指令，第二个FU用来执行访问存储器类型的指令，第三个阶段用来执行乘法操作，因为要保证流水线的写回(Write back)阶段是顺序执行的，因此所有FU都需要经历同样周期数的流水线，其中乘法运算需要的时间最长，因此所有第三个FU使用了三级流水线，其他FU也需要更随着使用三级流水线，即使他们在有些流水线什么事情都没有做。ScoreBoard用来记录流水线中每条指令的执行情况，例如一条指令在那个FU中执行，在什么时候这条指令可以将结果计算出来。

 ScoreBoard中记录了指令集中定义的每个逻辑寄存器(R0~R31)的执行情况，在典型的情况中，需要记录的信息如下：
        P：Pending，表示指令的结果还没有写回到逻辑寄存器中。
        F：一条指令在那个FU中执行，在将指令结果进行旁路时会使用这个信息。

        Result Position：记录了一条指令到达FU中流水线的那个阶段，3表示指令处于FU流水线的第一个流水段，1表示指令到达FU流水段的最后一个阶段，0表示指令处于流水线的写回阶段，在流水线的发射阶段，会将指令的信息写到ScoreBoard中。同时，这条指令会查询ScoreBoard来获知自己的源操作数是否都准备好了，在这条指令被送到FU中执行之后的每个周期，都会将这个值右移一位，这样使用这个值就可以表达出指令在FU中执行到那个阶段，对于执行ALU类型指令的第一个FU来说，当指令到达3时，就可以将它的结果旁路了；而对于执行乘法指令的第三个FU来说，只有当指令到达1时，才可以将它的结果进行旁路。指令可以从旁路网络(bypassing network)获得操作数，不需要等待源寄存器的值被写回到通用寄存器中。

在所有的处理器中，RAW相关性都是不可以绕开的，如果一个程序存在过多的RAW相关性，那么这个程序就不能在处理器中被有效执行。

1.3.2 乱序执行

一旦某条指令的操作数准备好了，就可以将其送到FU中执行。

对于一个2-way超标量处理器是，每周期从I-Cache取出两条指令并进行解码，为了乱序执行解决WAW和WAR这两种相关性，需要对寄存器重命名(register renaming)，这个过程可以在流水线的解码(Decode)阶段完成，也可以单独使用一个流水段来完成。处理器需要增加物理寄存器堆(Physical Register File,PRF)来配合完成指令集中定义的寄存器(Architecture Register File, ARF)进行重命名，PRF中的寄存器的个数要多于ARF。

指令在流水线的取指令、解码和寄存器重命名都是按照程序中规定的顺序(in-order)来进行的，直到指令到达流水线的发射(Issue)阶段。在这个阶段，指令被存储在一个缓存中，这个缓存被称为发射对列(Issue Queue)，一旦指令的操作数准备好了，就可以从发射队列中离开，送到相应FU中执行，因此发射队列是流水线从顺序执行到乱序执行的分界点。

每个FU都有自己的流水线级数，如执行ALU类型的指令的FU需要一个周期就可以计算出结果，不在需要像顺序执行的处理器那样被拉长到和乘法FU一样的周期数。在这种流水线中，由于每个FU的执行周期都不相同，所以指令在流水线的写回(Write back)阶段是乱序的。在这个阶段，一条指令只要计算完毕，就会将结果写到PRF，由于分支预测(mis-prediction)和异常(exception) 的存在，PRF的结果未必都会写到ARF中，因此也将PRF成为Future File。

为了保证程序的串行结果，指令需要按照程序中规定的顺序更新处理器的状态，这需要使用一个称为重排序缓存(ROB)的部件配合，流水线中的所有指令都按照程序中规定的顺序存储在重排序缓存中，使用重排序缓存来实现程序对处理器状态的顺序更新，这个阶段称为提交(Commit)阶段，一条指令在这个阶段，会将它的结果从PRF搬到ARF中，同时重排序缓存也会配合完成对异常(exception)的处理，如果不存在异常，那么这个指令就能顺利离开流水线，并对处理器的状态进行更改，此时称这条指令退休了，一条指令一旦退休，它就再也不可能回到之前的状态了。

指令一旦退休之后，就不可以再从流水线中清除了。这給store 指令带来了额外的麻烦，因为store指令需要写存储器，如果在write back阶段就将结果写到存储器中，那么一旦由于分支预测失败或者异常等原因，需要将这条store指令从流水线中抹掉时，就没有办法将存储器的状态进行恢复了，因为存储器中原来的值已经被覆盖了。于是，上图使用了一个缓存，称为Store Buffer(SB)，来存储store指令没有退休之前的结果，store指令在流水线的写回阶段，会将它的结果写到Store Buffer中，只有一条store指令从流水线中退休的时候，才可以将它的值从Store Buffer写回到存储器中。使用了这个部件之后，Load指令此时除了从D-Cache中寻找数据，还需要从Store Buffer进行查找，这样在一定程度上增加了设计的复杂度。

本节重点关注乱序执行的超标量处理器，下面对某个流水线中的各个阶段做一个粗略的介绍：

        (1)Fetch(取指令)：从I-Cache中取指令，主要由两大部件组成，I-Cache负责存储最近常用的指令；分支预测器则用来决定下一条指令的PC值。

        (2)Decode(解码)：识别出指令的类型、指令所需操作数以及指令的一些控制信号等。这部分的设计和指令集是息息相关的，对于RISC指令集来说，由于比较简洁，解码部分相对比较简单。对于CISC指令集来说，由于比较复杂，所以解码部分需更多的逻辑电路来对这些指令进行识别。

        (3)Register Renaming(寄存器重命名)：在流水线解码阶段，可以得到指令的源寄存器和目的寄存器，这些寄存器都是逻辑寄存器，在指令集中已被定义。为了解决WAW，WAR这两种“伪相关性”，需要使用寄存器重命名的方法，将指令集中定义的逻辑寄存器重命名为处理器内部使用的物理寄存器，物理寄存器的个数要多于逻辑寄存器，通过寄存器重命名，处理器可以调用更多可以并行执行的指令。在进行重命名时，通常使用一个表格来存储当前逻辑寄存器到物理寄存器的对应关系，同时在其中还存储中那些物理寄存器还没有被使用的信息，提供一些电路来分析当前周期被重命名的指令之间的RAW相关性，将那些存在RAW相关性的指令加以标记，这些指令会通过后续的旁路(bypassing network)来解决它们之间存在的“真相关性”。由于寄存器重命名阶段花费时间比较长，现实当中处理器都会将其单独使用一级流水线，而不是和解码阶段放在一起。

        (4)Dispatch(分发)：被重命名之后的指令会按照程序中规定的顺序，写到发射对列(Issue Queue)、重排序缓存(ROB)和Store Buffer等部件中，如果这些部件中没有合适的空间可以容纳当前的指令，那么这些指令就需要在流水线的重命名阶段进行等待，这就相当于暂停了寄存器重命名以及之前的所有流水线，直到这些部件有空闲的空间为止。分发阶段可以和寄存器重命名阶段放在一起，在一些对周期时间比较紧的处理器汇总，也可以将这个不分单独使用一个流水段。

        (5)Issue(发射)：经过流水线分发(Dispatch)阶段之后，指令被写到发射队列(Issue Queue)中，仲裁(select)电路会从这个部件中挑选出合适的指令送到FU中执行，这个仲裁电路可繁可简。对于顺序发射发射(in-order issue)的情况，只需要判断发射队列中最旧的那条指令是否准备好就可以了。而对于乱序进行发射(out-of-order issue)，仲裁电路会变得会变得比较复杂，它需要对发射队列中所有指令进行判断，并从所有准备好的指令中找出最合适的那条指令，送到FU中执行、对于乱序处理器而言，这个阶段是从顺序执行到乱序执行的分界点，指令在这个阶段之后，都是按照乱序的方式来执行，直到流水线的提交(Commit)阶段，才会重新变成顺序执行的状态。在发射队列中还存在唤醒(wake-up)电路，他可以将发射队列中对应的源操作数置为有效的状态，仲裁电路和唤醒电路互相配合进行工作，是超标量处理器中的关键路径。

        (6)Register File(读取寄存器):被仲裁电路选中的指令需要从物理寄存器堆(PRF)中读取操作数。一般情况下，被仲裁电路选中的指令可以从PRF得到源操作数。当然还有不一般的情况，那就是指令不能从PRF中得到操作数，事实上很大一部分指令都是通过旁路网络获得操作数的。这也为减少PRF的读端口提供了可能。由于超标量处理器每周期需要执行好几条指令，PRF所需要的端口数也是比较多的，多端口的寄存器堆的访问速度一般都不是特别快。因此在现实世界的处理器中，这个阶段都会单独使用一个流水段。

        (7) Execute(执行)：指令得到了它所需要的操作数之后，马上就可以送到对应的FU中执行了，在超标量处理器中，这个阶段通常有很多不同类型的FU。例如负责普通运算的FU，负责乘加运算的FU，负责分支指令运算的FU，负责load/store指令的FU等。现在处理器还会加入一些多媒体运算的FU，例如SIMD运算的FU。

        (8) Wirte back(写回)：将FU计算的结果写回物理寄存器堆中，同时通过旁路网络将这个计算结果送到需要的地方，一般都是送到FU的输入端。由FU的输入端的控制电路在决定最终需要的数据，在现代处理器中，旁路网络是影响速度的关键因素，因为这部分需要大量的布线，而随着硅工艺尺寸的减少，连线的延迟甚至超过门电路的延迟，因此旁路网络会严重影响处理器的周期时间。为了解决这个问题，很多处理器都采用了Cluster结构，将FU分成不同的组，在一个组内FU，布局布线时会紧挨在一起，这样此组内的旁路网络由于经过的路径比较短，一般都可以在一个周期内完成。当旁路网络跨越不同的组时，就需两个甚至更多的周期了。

        (9) Commit(提交)：主要部件是重排序缓存ROB，它会将乱序执行的指令拉回到程序中规定的顺序，之所以能完成这样的任务，是因为指令在流水线的分发(Dispatch)阶段，按照程序中规定in-order写到了重排序缓存中。处理器执行的结果要和程序中原始的顺序是一样的，但是在超标量处理器中，指令是按照乱序的方式在内部执行的，最后需要这样一个阶段，将这些乱序执行的指令变回到程序规定的原始顺序。在重排序缓存中，如果上一条指令的指令还没有执行完，那么即使这条指令已经执行完了，它也不能离开重排序缓存，必须等待它之前的所有指令都执行完成。在这个阶段也会对指令产生的异常进行处理，指令在流水线的很多阶段都可以发生异常，但是所有的异常都必须等到指令到达流水线的提交Commit阶段才能进行处理，这样保证异常的处理按照程序中规定的顺序进行，并且能够保证实现精确异常。一条指令一旦从重排序缓存中离开而退休retrie，那么就对处理器的状态进行了修改，再也无法返回到之前的状态了。

        在超标量处理器中，还有一个非说不可的话题就是处理器的状态恢复，现代处理器在很多地方使用了预测技术。因为超标量处理器的流水线一般比较深，不使用预测技术是没有办法获得高性能的。一般情况下，预测能够有效工作的前提就是有规律可循，一个很明显的例子就是分支预测。分支指令在执行过程中表现出规律性，使分支预测成为了可能。但是，只要是预测，就会存在失败的可能，这时候就需要一种办法，将处理器的状态恢复到正确的状态，这就是恢复电路的工作。它不但要将错误的指令从流水线中抹去，还需要将这些错误指令在流水线中造成的“痕迹”进行消除。例如错误的指令可能已经修改了重命名映射表，或者将结果写到了物理寄存器中等。恢复电路和预测技术是天生一对，只要有预测，就必然有状态恢复。激进的预测技术会提高处理器的性能，但是代价就是更复杂的恢复电路。