计算机体系结构学习笔记

计算机体系结构学习

一. 处理器的分类

主要依据指令形式和每周期可执行指令数分类

1. CISC，一条指令完成很多事情，尽可能创造更多的指令覆盖各种操作，简化编译器设计。
2. RISC，软件模拟80%的非常用CISC指令以简化硬件设计，方便流水线设计，提高频率，降低功耗和成本。
3. 超标量处理器，一周期执行多条指令，因此指令的源操作数准备好就可以执行，称为乱序执行。乱序执行不可改变程序的原有功能，需要一些方法使得乱序执行的指令看起来仍然按程序制定的顺序更改处理器状态。乱序执行使性能大幅提升，但需要更多的硬件资源和功耗。

二. CACHE

超标量处理器中分支预测和cache直接决定性能。L1-Cache为保证速度，一般采用多端口SRAM实现。L2-Cache则是指令和数据共享，通常以MB为单位，可由多核共享。对于I-Cache，在遇到分支跳转指令时才会对性能造成影响；而D-Cache需要多周期访问，由于数据相关性原因会造成性能下降。L2-Cache不需要多端口设计，延迟也不太重要，但是需要高的命中率。

空间局部性：从主存中取数据时，大概率其附近地址的数据在近期也会被使用。所以会取相邻地址的数据刷新一个cacheline。

时间局部性：近期被访问的主存数据，大概率还会被访问。

cache-miss的频率直接决定处理器的性能，可以分为以下几类：

• Compulsory，第一次被访问的数据或指令缺失；通过增加块的容量，降低访问次数或者通过预取的方式降低。
• Capcity，cache容量限制，增大容量，增大L2-cache(访问时间变长)。
• Conflict，多个数据映射同一个地址。采用多路组相连或者使用Victim cache缓解。

1. cache的常见结构

   直接映射，组相连，全相连映射方式。

   将数据地址分为三个部分来进行cache地址映射，将地址分为三个部分，使用index部分来索引存放的cacheline，offset表示某cacheline内部的偏移地址。使用Tag部分来判断该cacheline缓存数据是否是地址所指向的数据，因为有可能该位置缓存的数据是另一个index部分一样，但是Tag不一样的数据。
   直接映射：硬件实现简单，但是会导致index部分相同的地址挤占同一个cacheline，使得之前缓存的数据被迫清除，降低cache-hit率，可通过组相连的方式缓解这种情况。

   组相连：将index部分所能映射的所有cacheline的集合叫cache-set。取数据的时候需要判断所有可被映射的cacheline中的数据是否有效，且cacheline记录的Tag地址和地址的Tag部分一致。

   全相连：如果数据能存储到任一cacheline中，则为全相连。只有Tag和offset部分，使用Tag寻址。直接映射和全相连是组相连的两个极端。

2. cache的淘汰策略

   LRU(Least Recently Used)和RR(Random Replacement)。LRU通过记录cacheline的年龄来进行淘汰，记录年龄需要更多的硬件，实际设计中使用Pseudo-LRU算法。常见的包括Tree-PLRU和Bit-PLRU。

   Tree-PLRU算法创建一个完美的二叉树，二叉树的叶子节点代表cacheline，非叶子节点使用一个bit的表示年龄位。0表示低路cacheline最近没有被访问，1表示高路数cacheline最近没有被访问。

   因为cache-set的数量通常比可以映射到其中的地址数量少，会出现刚淘汰的数据马上需要使用的情况。实际设计中会使用一个全相连的Victim cache来缓解这个问题，该cache专门保存最近被替换掉的cacheline。Victim cache的容量小，其中的数据和主cache中数据互斥。

3. cache的写策略

   先检查cache中是否有对应数据，

   write-hit：根据write-back和write-through来具体操作。write-back将数据更新到cache，不更新内存。write-through会将数据同时更新cache和内存。

   write-miss：根据write-allocate和write-no-allocate操作。write-allocate会将要写入的内存读到cache，然后按write-hit的策略操作。write-no-allocate不会讲写入的数据写到cache，直接写到内存。

4. 提高cache的band-width

   存在多个load/store指令访问不通地址的cache时，为提高带宽，可以将cache按地址划分为多个bank，每个bank具有读写口。如果一个周期内多条内存访问指令落到不同的bank，则可以并行访问。一般需要避免多个访存指令同时访问同一个bank，减小bank-conflict才能提高利用率。

三. 寄存器重命名

1. 数据相关性

   1.1 Output dependence, 输出相关，WAW, 先写后写，表示两条指令都将结果写到同一寄存器。

   1.2 Anti-dependence, 反相关，WAR, 先读后写，表示一条指令的目的寄存器是另一条指令的源寄存器。

   1.3 True-dependence, 真相关，RAW，先写后读，表示一条指令的源寄存器是另一条指令的目的寄存器，当前指令的源寄存器来自于上一条指令的计算结果。

   数据相关性是和寄存器直接相关的，在译码阶段得到寄存器的名字就可以找到这些相关性。

2. 存储器数据相关性

   表示访问存储器的指令，即load/store之间的相关性，这些相关性和访存地址有关。可以分为先写后写(WAW)，先读后写(WAR)和先写后读(RAW)。例如一条load指令的地址和前一条store指令地址相等就存在RAW相关性。

3. 控制相关性

   由分支指令引起的相关性，使用分支预测可以解决。

4. 结构相关性

   指令必须等处理器中的某些部件空闲才能继续执行。

数据相关性中只有RAW是真相关（必须按顺序计算才能得到正确的结果，与寄存器名称无关）。WAW、WAR都是由乱序引发的假相关，可通过更换寄存器名字解决。这主要是由于通用寄存器数据有限，循环体（总是写同一寄存器），代码重用（重复调用函数）造成的。

1. 寄存器重命名的方式

   5.1 使用ROB（re-order-buffer）

   5.2 将ARF扩展为PRF

   5.3 使用同一的PRF

   需要考虑的问题：

   • 什么时候占用PR，PR来自哪里？
   • 什么时候释放PR，PR去何处？
   • 发生分支预测失败时怎么处理？
   • 发生异常时怎么处理？

四. 虚拟存储器

虚拟存储器使得程序，数据和堆栈可超出实际物理内存，操作系统可把当前使用内容放在物理内存，其他的放在下一级存储器/硬盘或闪存等。程序运行在虚拟存储器空间，地址范围由处理器位数决定（处理器内部以字节为基本单位）。虚拟地址需要经过MMU进行地址转换才可对物理存储器寻址。

1. 地址转换

   虚拟存储器有多种实现方式。目前常用基于分页的虚拟存储器，典型页大小有4kB，大页内存的有64kB。页的大小和多级页表转换与效率相关。

   load/store指令计算出VA，有MMU转换为PA再寻址物理内存。如果MMU发现VA所在的Page未映射到物理内存则会产生Page Fault异常。该异常送给处理器，处理器跳转到对应的处理程序（缺页中断，将该页load进内存）。

   硬盘访问的时间为毫秒级别，因此需要降低Page Fault发生的频率。使用比较灵活的页替换算法可以有效降低Page Fault发生的频率。

   在使用虚拟存储器的系统中，都是使用一张表格来存储虚拟地址到物理地址的映射，称之为页表。页表内容实际也存储在内存中。每个程序都有自己的页表，当前运行程序的页表在物理内存中的其实地址呗存储在页表寄存器中，每个进程都有自己的页表。处理器中一个程序对应的页表，指令地址PC和通用寄存器组成了该程序的状态。一个程序可以有多个进程，打开一个进程时需要操作系统分配物理内存空间，创建页表和堆栈。每个进程都拥有全部的VA空间，操作系统可把不同进程分配到物理内存的不通位置，使用store指令将映射信息更新到页表中。页表也有cache，页表存储在内存中，页表cache也会存在miss。

   多级页表的缺点是增加了内存访问次数，对于二级页表则需要三次内存访问才能得到数据，一般使用TLB和cache来加快。

2. 虚拟内存的优点

   2.1 让每个程序有独立的遍及全部VA地址范围的地址空间，而且可以对程序进行保护和共享

   2.2 将不连续PA空间映射为连续的VA空间，减少碎片，最大限度利用物理内存。

   2.3 为多个进程分配的物理内存之和可能大于实际物理内存。

   2.4 利用虚拟内存可以管理每个页的访问权限，单纯物理内存不具备权限属性，权限管理可以通过页表实现。

3. TLB和cache

   TLB(translation lookside buffer，地址变换高速缓存)即快表。TLB为页表cache，具备时间相关性。空间相关性弱，即未必会访问当前页的相邻页，因此预取等方法无法使用到TLB中。现代处理器一般使用两级TLB，第一级分为I-TLB和D-TLB，采用全相连结构。第二级指令数据共用，采用组相连。

   现代处理器中一般支持大小可变的页，由操作系统进行管理，很久不同应用选择不同大小的页，最大限度利用TLB。页太小，多级页表转换效率低。页太大，如果程序数据较小，则容易造成页浪费，整体效率低。DPDK数据转发中，由于转发数据比较规律且数据量大，使用大页内存。

   3.1 TLB缺失

   TLB容量小，发生缺失频率高。出现缺失的情况主要分为VA对应的页不在物理内存中，VA对应页的PTE位于物理内存中但不在TLB中（发生概率高，TLB小于页表大小）。解决TLB缺失的本质是从页表中找到映射关系并写入TLB，可以使用软件和硬件状态机实现。
   1

   3.2 TLB写入
   TLB中记录的所有页都不允许从物理内存中被替换。
   操作系统在PageFault时，如果从物理内存中选出的要被替换的页是脏的状态，那么首先需要将这个页的内容写回到硬盘中，然后才能够将其覆盖。但是，如果在系统中使用了D-Cache，那么在物理内存中每个页的最新内容都可能存在于D-Cache中，要将一个页的内容写回到硬盘，首先需要确认D-Cache中是否保留着这个页中的数据。按照前面的说法，TLB中记录的页都是安全的，操作系统不可能将这些页进行替换，如果在D-Cache中保存的数据都属于TLB 记录的范围，那么操作系统在进行页替换时就不需要理会D-Cache。但D-Cache中的数据未必就一定在TLB记录的范围之内，例如，当发生TLB缺失时，需要从页表中将一个新的PTE写到TLB中，如果TLB此时已经满了，那么就需要替换掉TLB中的一个表项，也就不再记录这个页的映射关系，但是这个页的内容在D-Cache中仍旧是存在的，当然操作系统此时可以选择同步地将这个页在D-Cache中的内容也写回到物理内存中，但是这不是必需的。这样就导致操作系统在物理内存中选择一个页进行替换时，如果这个页是脏的状态，那么它最新的内容不一定在物理内存中，而是有可能在D-Cache中，此时操作系统就必须能从D-Cache中找出这个页的内容，并将其写回到物理内存中，这要求操作系统有控制D-Cache的能力。

五. 分支预测

5.1 概述

在取指令阶段，需要从I-Cache中取出多条指令，同时还需要决定下个周期取指令的地址，也就是PC值。如果只是简单的顺序取指令，那么预测所有的分支指令是不执行的。在执行阶段，如果发现一条可以执行的分支指令时，就需要冲刷执行阶段之前的取指流水线，并从分支指令处重新取正确地址的指令。这些被冲刷的指令浪费了处理器，造成性能下降。如果在取指阶段就可以预测分支指令，并知道是否跳转以计算正确的PC，那么就不会对流水线产生影响，提高了执行效率，这就是分支预测的意义。但，如果在执行阶段发现分支预测失败，那么也需要冲刷执行之前的所有取指流水线，并计算正确的PC，重新取指。分支预测失败也将降低执行效率。

5.1.1 分支方向和目标地址

对于超标量处理器，需要在取指阶段决定下一周期的取指地址，因此需要在该阶段判断是否存在分支指令。分支指令包含两个要素：方向和目标地址。

• 方向

  对于分支指令，其只有两个方向，一种是发生跳转，一种是不发生跳转。有些分支指令是无条件跳转，例如jump；有些是条件跳转，例如jumpcmp。

• 目标地址

  如果预测指令跳转，那么久需要知道要跳转的地址，即目标地址。目标地址分为直接跳转和间接跳转。

  直接跳转：该地址可由当前PC赫尔指令携带的立即数(ofst)相加得到。

  间接跳转：该地址来自通用寄存器，该寄存器的值一般是其他指令的处理结果，等待时间较长，增大了分支预测失败的惩罚；由于寄存器的值是容易变化的，所以增加了预测难度。不过一般间接跳转指令都用来调用子程序或者返回（call & ret），规律性强，容易预测。

5.1.2 静态与动态分支预测

对于一般流水线较短（多短算短？？）的处理器，一般使用静态分支预测，即总是预测不执行跳转。由于流水线较短，就算执行阶段发现需要跳转，冲刷流水线的代价也小。

随着处理器并行度的提高和流水线深度加深，需要动态的分支预测，根据分支指令过去的执行情况来决定预测结果。编译器可使用关键字进行提示（likely & unlikely）。

5.1.3 分支指令的识别

主要有两种方式，一种是解码指令后识别，另一种是根据PC值来预测。

在进行分支预测前，需要从指令组中找出分支指令。最容易想到的办法是对指令组快速解码，识别解码后的指令是否是分支指令，找到分支指令的PC值，送到分支预测器。但这往往不能在一个时钟周期内完成。

为解决该问题，可在指令从L2-Cache写入I-Cache之前进行预解码，将指令和是否是分支指令的信息一起写入I-Cache中，这样可以去掉快速解码电路。但是这样取指令的周期也比较长。

分支预测越靠前越好，分支预测的最好时机是在取指令的同时进行预测，这样在下周期就可以根据预测的结果继续取指令。对于一条指令来说PA会变化，但是VA相对固定。程序一旦开始运行，每条指令对应的取指地址就固定，可以根据一条指令的PC值来判断是否是分支指令，只要这条分支指令第一次被执行完成后，再次遇到此PC值，就可以知道当前要取的指令是分支指令。即使程序发生了自修改，也会将分支预测器清空，重新预测。

在核进行进程切换的时候需要将预测器清空，保证不同进程间的分支预测不会相互干扰。

5.2 分支指令的方向预测

分支指令方向分为taken & not-taken，很多分支是有规律可循的。最简单的动态预测即根据上一次执行结果预测，但分支方向发生变化频繁时准确度就不高，所以引入两位饱和计数器预测。

5.2.1 基于两位饱和计数器的分支预测

基于两位饱和计数器的分支预测方法并不会马上使用分支指令上一次的结果，而是根据一条分支指令前两次的执行结果来预测本次的方向。可用一个四状态的状态机实现。饱和的意思是方向不变则留在原来的状态。

状态机如图，因此只有两次预测失败才改变方向。对于状态机的初始状态，其实可能是这四种状态之一，根据实际情况决定。**可使用格雷码对状态机编码，每次只改变一位减小出错概率，降低功耗。**对于for循环来说，第一次和最后一次仍会预测失败。一般来说，饱和计数器都是以Strongly not taken，Weakly not taken作为初始状态。

对于绝大多数程序来说，使用这种基于两位饱和计数器的分支预测方法，就已经可以获得比较高的正确率了，增加计数器的位宽（例如使用三位的计数器）会引起复杂度的上升和更多存储资源的需求，这些额外开销所带来的负面影响要大于实际可以获得的预测精度的提高，因此主流的处理器一般都是基于两位的饱和计数器来实现分支预测的。

5.2.2 基于局部历史的分支预测

5.2.3 基于全局历史的分支预测

5.2.4 竞争的分支预测

5.3 分支指令的目标地址预测

对于直接跳转的分支目标，由于指令中的ofst是固定的，因此只要第一次执行时记录该分支目标PC即可，当再次遇到这条指令时，如果方向预测发生跳转，那么他的目标地址就可以使用以前记录下的值。对于间接跳转，分支目标PC来自于通用寄存器，一般会经常变化，**不过该类分支一般是处理子程序调用的Call和Return指令，有规律可循可以预测。**大部分超量处理器都会推荐编译器设计者尽量减少使用其他类型的间接跳转指令以提高分支预测准确度。

5.3.1 直接跳转分支的目标PC预测

• BTB

  对于直接跳转分支，不跳转时目标PC为当前PC加上fecth group的size，跳转时目标PC为当前PC加立即数扩展的ofst，需要通过cache记录每条直接跳转的分之目标对应的PC。不可能记录所有分支PC对应的目标PC，因此多个PC共用一个存储位置，该cache被称为BTB(Branch Target Buffer)。

• BTB缺失

  当分支预测为跳转，但BTB发生缺失，此时需要进行缺失处理，一般有两种方案。

  方案一：停止取指。当BTB缺失时，需要停止取指，直到目标PC被计算出来。对于直接跳转分支，发生BTB缺失时，需要访问I-Cache得到指令，解码得到目标地址。该过程会导致流水线暂停，引入气泡。对于间接分支，如果影响目标PC的通用寄存器的值来自D-Cache，同时又发生Cache-miss，耽搁时间就更长了。

方案二：继续执行。对于方向预测会发生跳转的分支指令来说，如果发生BTB缺失，此时可以使流水线继续使用顺序PC值取指。当发现计算出的目标PC与顺序PC不一致时冲刷取指流水线。但是这样会增加功耗，功耗敏感设计不建议采用此方案；好处时有一定概率（小概率）分支不会真正跳转。

5.3.2 间接跳转分支的目标PC预测

• call和return指令的预测

  对于间接跳转的分支指令，他的目标地址来自于通用寄存器，且经常变化。所以无法通过BTB对其目标地址进行准确的预测。大部分间接跳转的分支指令是call和return指令，他们的目标PC非常有规律，容易预测。每条ret指令的目标地址总是上一次call指令的下一条指令；因此可设计一个后进先出存储器（LIFO）保存最近执行Call指令的下一条指令地址，该存储器和堆栈的工作原理一样，称为返回地址堆栈（RAS），如图4.26。现代处理器中BTB和RAS几乎是必须要使用的。每条call指令，每次调用子函数是固定的，对应目标PC可以使用BTB进行预测。

对于子程序3中Return指令进行目标PC预测时使用RAS最新进来的地址返回程序2，同时RAS读指针指向下一个值，因此总结起来就是用BTB预测Call指令目标PC，用RAS预测Return指令目标PC，如图4.27（为什么还需要BTB? BTB负责预测Call函数的分支目标地址，判断该指令是不是Return指令）。

要能使RAS能够正确工作，需要如下两个前提条件：

**a. 需要识别出Call指令才能将Call的下一条PC放入RAS，最好能在分支预测阶段就识别出Call指令，可通过在BTB中增加位来标记分支类型，这样在查询BTB时就可识别出Call指令，**如图4.28所示；

b. 在对Return指令预测时需要把RAS的输出作为目标PC，而不是BTB的输出，因此在分支预测阶段也需识别出Return指令。

在实际中，如果call指令嵌套很深导致RAS满怎么办？

a. 不对新的call指令进行处理，直接让下一条return预测失败，注意RAS指针也不能发生变化。

b. 继续写入RAS，覆盖RAS最旧的内容。（对于递归函数，能返回正确地址）。对递归调用来说，**对于连续执行的Call指令可以把它们的返回地址放在RAS同一地方，使用计数器标记Call指令执行次数，相当于扩大了RAS的容量。**这种带计数器的RAS在写入RAS中Call指令的PC时会与上次写入的对比，如果相同则计数器加1，指针不变，当遇到Return计数器减1，如果已经为0则将指针移向下一个。

• 其他间接分支指令预测

  实际程序中其他类型的间接分支目标地址只有固定的几个，因此可以基于过去执行情况进行预测。例如switch-case语句，其目标分支较固定，可以根据历史信息进行预测。

5.3.3 小结

**总结前文使用BHR、GHR和饱和计数器配合来预测分支方向，使用BTB、RAS和Target Cache预测目标PC，这些都发在取指阶段且都是基于PC预测的。**汇总就可实现一种完整的分支预测，分支预测方向独立于BTB，这种做法被称为decoupled BTB，所以没有在BTB中的分支指令也会进行分支方向预测，因为BTB记录地址需要硬件资源很多但容量不能太大，因此无法记录很多指令信息。而BHT和PHT可记录更多的指令信息实现对更多指令进行方向预测，被预测跳转但发生BTB缺失时暂停取指即可，这也比发生分支预测失败好。在流水线得到一条分支结果（译码或执行阶段都可能）就会对预测正确性进行检查，失败时进行恢复撤销之前的操作。

5.4 分支预测失败时的恢复

在流水线的很多阶段都可以对分支预测进行检查，包括：

• 在解码阶段可判断是否为分支指令及分支类型，如果是直接跳转还能得到分支地址。也可能在此阶段发现预测的方向错误，但在后续阶段才能得到目标PC，此时可以暂停流水线避免后续指令被冲刷掉浪费功耗。
• 在读取物理寄存器阶段（可在寄存器重命名之后或发射阶段之后），如果读到寄存器的值即可对间接分支预测目标的PC进行检查，如果发现预测错误，仍需冲刷掉后续指令。但这些指令可能已经进入发射队列，发射队列中还有正确的指令，所以需要选择性清除。
• 执行阶段不管什么类型的分支被计算出结果，都需要进行正确性检查。

**可通过重排序缓存（ROB）中记录的原始指令顺序对已处于发射队列或执行阶段的分支失败后的指令进行清除，并进行状态恢复。**当执行阶段发现预测失败时，将这个信息写入ROB对应的表项中，并暂停取指，但让流水线继续执行，当此条指令成为最旧的指令（即此前所有指令均已退休），将整个流水线上的所有指令抹掉，重新取指，如图4.32。这个方法最大的缺点就是需要分支指令在流水线中等待一段时间才能进行处理，并且在分支指令之前存在D-Cache缺失的load指令时，这个等待的时间就会很长，在这段时间内流水线都无法取新的指令来执行，这样就会造成分支预测失败时的惩罚很大降低了处理器的性能。虽然失败的代价很大，但容易实现。

除此之外，很多现代处理器**采用基于Checkpoint的方法进行恢复，即发现分支指令并在此分支之后的指令更改处理器的状态之前把处理器状态（如寄存器重命名的映射表和预测跳转分支指令对应的下一条PC等）保存起来。**一般而言在分支进入寄存器重命名阶段时就进行状态保存，将映射表保存起来。虽然相对于ROB的方式消耗更多资源，但能快速恢复处理器状态，因此效率更高。

采用基于Checkpoint的方法需要抹掉失败路径上的指令，**而不是像ROB方法一样等待错误的分支指令之前所有指令退休后才抹去后续指令。**当分支指令到了执行阶段，发现分支预测失败的时候，此时流水线中仍有一部分指令并没有处于分支预测失败的路径上，这些指令不能够被抹掉。可通过对每一条分支指令编号来实现此方案，如图4.33，这样可以很方便地识别出哪些指令位于这条分支指令的后面，当发现分支预测失败时，就可以马上利用这个编号对流水线中的指令有选择地进行抹掉，而不需要等到这条预测错误的分支指令变为流水线中最旧的指令。
所有处于流水线中分支指令编号值都会保存在一个FIFO中，容量等于处理器最多支持处于流水线的分支指令个数，一旦列表已满就不再向流水线送入分支，因此如果再解码出分支就需要暂停解码之前的流水线，直至有空余的空间。

在具体实现时可采用下面方法，该方法使用两个表格，空闲列表用于存放没有使用过的编号值，每从译码阶段解码一个分支就从空闲列表中送出一个编号值写到编号列表，之后所有被解码指令就被附上这个编号值直至遇到下一个分支被解码。这两个表格本质都是FIFO，一旦预测失败就会把对应编号及其之后的编号的所有指令抹掉，被抹掉的编号值被放回空闲列表。

如果在解码阶段发现预测错误，直接把解码之前顺序执行的指令抹掉即可，当然这条分支的编号也会被分配编号，因为无法确定它前面是否还存在分支失败的指令，所以需要对解码阶段得到的每一条分支都配一个编号值。

在执行阶段发现预测错误需要抹掉之后指令的过程包括：

1）在流水线发射阶段之前的所有指令可以在一个周期内被无差别抹掉，因为在此之前是顺序执行的；

2）在发射阶段及以后的流水段处于乱序执行状态需要通过编号值找出之后抹掉，可能在一个周期无法完成。

如何使用编号值找到错误指令？如图4.35，**如果在执行阶段发现错误分支指令，可将编号列表中所有相关编号值广播，在ROB中的所有指令将自身编号与之对比，如果相等就将ROB中对应指令置为无效，即对ROB完成指令清除。**所以基本无法在一个周期完成清除工作，实际上在执行阶段发现预测失败时，重取指令需要几个周期才能到达发射阶段（该阶段需要使用ROB和发射队列），所以在此之前相关指令被抹掉即可，因此每周期只广播几个编号值即可。如果需要广播的编号过多，则让新到达的指令等待直至所有指令抹掉完成状态恢复才允许新指令进入发射阶段。

使用分支指令的编号列表对流水线中的其他部件如发射队列的处理过程类似，指令抹掉之后就需要对处理器状态恢复，主要是对寄存器重命名阶段中的映射表进行恢复，这部分内容在后文中介绍。在超标量处理器中，如果在一个周期内解码的多条指令都是分支，则空闲列表需要在一个周期内提供多个编号值，这样就需要多端口FIFO，但不太值得，因为出现这种状况的概率较小，因此如果在解码阶段发现从指令缓存（IB）读出多条分支，则第二条及以后分支被延迟到下一周期。

在执行阶段对分支预测结果进行检查时，需要知道预测值，因此需要在解码阶段把每个分支预测结果写到一个缓存，在缓存中的地址随着分支在流水线中流动，这样在执行阶段检测时就可从缓存中读取预测值。

预测为跳转的分支（预测不跳转的分支不需要在这里记录）写入PTAB时将valid位置1，完成检测后清0。超标量处理器中不能保证对所有分支都进行了预测，预测了也不能保证结果正确，所以在执行阶段得到分支指令实际结果时，会有以下几种情况：

1）实际不跳，PTAB中无对应内容，那么就表示被预测为不跳，预测正确；

2）实际不跳，但在PTAB中找到对应内容，预测错误，Next_PC为正确目标PC；

3）实际跳，PTAB中无对应内容，预测错误，使用计算出的目标PC；

4）实际跳，在PTAB中找到对应内容，将预测PC与计算PC对比，相等则正确不相等使用计算出的目标PC。

一般情况写PTAB过程在取指阶段完成，注意还可能出现非分支指令预测为跳转的情况，如果存在自修改代码，而没将分支预测器清空就会出现这类错误情况，但这个情况在解码阶段就能检测并释放PTAB相应位置。

六. 指令译码

RISC指令长度固定，解码难度远低于指令长度变化需要识别指令边界的CISC。RISC指令集有些指令需要在解码的时候特殊处理，例如乘累加。条件执行的指令在解码时也需要特殊处理，解码之后变成普通指令，后续流水线按一般指令处理即可。

6.1 指令缓存

为减少I-Cache的影响，在取指阶段取出的指令个数可以多于每周期可以解码的个数，可在取指阶段和解码阶段之间加入指令缓存。当取指地址落在cacheline最后三个字或指令组存在被预测跳转的分支指令，可通过有效位告诉缓存哪些指令是有效的。对于地址落在后三个字中，无法取到更多的指令；对于预测为分支跳转的指令，可以取到相同数目的指令，但是分支指令后的指令被置为无效，无法被写入）。

指令缓存本质是一个FIFO实现顺序解码，并便于找到指令相关性。此外，解码阶段可能需要处理特殊指令导致每周期可解码指令数下降。指令缓存需要每周期写入或者读出多条指令，一般通过交叠的方式使用多个单端口SRAM来实现该功能。

优点：存储单周期无法全部解码的多余指令，发生cache-miss时，有多余的指令可以继续被执行，不至于流水线全部暂停。

6.2 一般情况

指令寄存器个数直接决定重命名阶段的映射表个数或指令相关性检查的复杂度。还需要注意从指令缓存中读取的多条指令未必是四字对齐的，需要将这些指令按照原始顺序进行排列送到解码电路进行解码。由于RISC指令比较规整，解码过程一般在一个周期就能完成。

总体来看，在一般情况下，RISC处理器在解码阶段完成任务可以概括为三个what，它们分别解释如下。

1）What type，例如指令是算术指令，访问存储器的指令还是分支指令等；

2）What operation，例如当指令是算术指令时进行何种算术运算，当指令是分支指令时它的条件是什么样的，当指令是访问存储器的指令时是load指令还是store指令等；

3）What resource，例如对于算术指令来说，源寄存器和目的寄存器是哪些，指令中是否有立即数等；

6.3 特殊情况

6.3.1 分支指令的处理

为方便分支预测失败时对处理器进行状态恢复，一般每周期只能解码一个分支，在解码阶段只要遇到分支就改变指令缓存的读指针即可将本周起多余的分支放在后面处理。使用Checkpoint的方法对分支预测失败时的处理器进行状态恢复，还需要在解码阶段完成分支指令的编号分配工作，这在分支预测部分已经阐述过。对于基于ROB恢复处理器状态的方法，则不再需要编号的分配工作，因此就不需要在解码阶段限制分支指令的个数。

对于分支指令，解码阶段还需要计算出实际的目标地址并进行正确性检查（对于直接跳转类型，解码阶段就可以计算出目标地址（PC+offset）），一旦预测失败即从正确地址取指。当然，分支指令在解码阶段是无法得到实际方向的（除了jump指令，但是因为它总是跳转的，一般不会预测错误），因此在解码阶段也就无法对分支预测的方向进行检查，这需要等到后续的流水线阶段才可以完成。

七.发射

发射，简单来说就是讲操作数准备好且满足发射条件的指令从发射队列中选出了送到执行单元中执行的过程。发射队列也称为保留站(IQ/RS)。超标量处理器由于发射队列需要乱序送出指令，所以发射队列硬件比较复杂。

发射阶段的部件有以下几种：

• 发射队列(IQ/RS)： 用来存储已经被寄存器重命名，但没有送到执行单元执行的指令。
• 分配电路：从发射队列中找到空闲空间，将寄存器重命名后的指令写入发射队列中。
• 仲裁电路：选择发射队列中最合适的指令送到执行单元，是发射阶段比较关键的电路，直接影响处理器执行效率。
• 唤醒电路：当指令经过执行单元得到结果后，负责通知发射队列中所有等待这个数据的指令所对应的源寄存器(RAW相关)就会被设置为有效状态，指令的所有有源操作数有效即为rdy状态。此时可向仲裁电路发出申请。发射队列的结构可分为集中式/分布式、数据捕捉/非数据捕捉、压缩/非压缩，相互组合就决定了发射阶段的实现方式。

7.1 集中式&分布式

所有执行单元共用一个IQ则为集中式(Centralized IQ, CIQ)，每个执行单元都有单独的IQ则为分布式IQ(Distributed IQ, DIQ)。

CIQ：容量大，不浪费每一个空间；但是需要从数据巨大的指令队列中选择出几条可以被执行的指令，选择电路和唤醒电路复杂。

DIQ：容量小，但特定的指令只能放在特定的IQ中，因此无法尽可能的利用空间；如某一个DIQ满就需要暂停发射签名所有指令的流水线，因此效率较低。选择电路简单，单唤醒电路比较分散，布线复杂度高。

7.2 数据捕捉&非数据捕捉

• 数据捕捉

在流水线发射阶段之前读取寄存器，称为数据捕捉。经过寄存器重命名后的指令首先读取PRF，然后将读到的值一起写入发射队列，如果某些寄存器还没被计算出则将寄存器编号写到发射队列供唤醒电路使用，被标记为non-available状态，在之后的时间通过旁路网络得到这些寄存器的值，而不再需要读取PRF。

IQ中存放指令操作数的地方称为payload RAM，指令被仲裁电路选中后就可直接从中读出对应的源操作数并送到FU中。当该指令被选中时，它的目的寄存器编号会被广播，发射队列其他指令将自身源寄存器编号与广播的目的寄存器编号进行比较，一旦相等则在payload RAM对应位置进行标记，被选中指令计算完毕后结果通过旁路网络写到payload对应位置，即通过旁路降低RAW相关的影响。这种方式像payload RAM在捕捉FU中的计算结果，所以称为数据捕捉结构，IQ负责比较寄存器编号是否相等，payload RAM负责存储源操作数并捕捉FU的计算结果。

超标量处理器中，用machine width来标记每周期可解码和重命名指令个数，用issue width标记每周期可在FU中并行执行的指令个数（也就是每周期最多可发射指令个数）。在一般的CISC处理器中，在处理器内部将一条CISC指令转化为几条RISC指令，而存储到发射队列中的是RISC指令，只有使issue width大于machine width，才能够使处理器的流水线比较平衡，避免出现“进的多，出的少”的情况；而在RISC处理器中，一般情况下这两个值都是相等的。但由于指令间存在相关性等原因，在很多时候，即使每周期解码和重命名多条指令，但并不能将所有译码的指令送到FU执行。因此，issue width一般要大于machine width，才能最大限度寻找在FU中可并行执行的指令，现代处理器一般都会采用很多FU使得每周期可并行执行的指令尽可能多。这种方法在发射阶段前读取PRF，因此PRF需要的读端口个数为machine width X 2。

• 非数据捕捉

在发射阶段后读取PRF，称为非数据捕捉，当IQ中的指令被选择电路选中才读取PRF，将读取到的值送入执行单元，IQ中不需要payload RAM，增加处理速度，PRF需要的读端口个数为issue-width x 2，因此需要的读端口个数增加。

• 总结对比

数据捕捉的方式的源操作数需要经历两次读和一次写，即从PRF读出，写到IQ，再读出送到FU，因此功耗更大；此外，由于payload RAM的存在，面积也会更大一点。

非数据捕捉的方式的PRF的读端口数目更大，但是不需要在发射队列中存储源操作数，因此发射队列面积和速度会好一些。此外，由于只需要读一次PRF，所以功耗更低。Intel的P6架构采用数据捕捉，而MIPS R10000和Alpha 21264采用非数据捕捉。

注意，当使用ROB进行寄存器重命名一般需要搭配使用数据捕捉的发射方式，因为当指令退休结果写入ARF时，采用数据捕捉不用关心指令结果位置变化，而采用非数据捕捉指令结果位置变化会带来非常麻烦的事情（why？）。

答：由于使用ROB进行寄存器重命名，当指令退休时需要将值存入ARF中，则正确的值可能存在ROB或者ARF中，因此不好利用非数据捕捉的方案进行读取。而数据捕捉的方式由于进入IQ之前就读了源操作数，并通过旁路将运算数据写回到payload RAM中，所以不用担心后续指令是否在ROB或者ARF中。

7.3 压缩&非压缩

根据发射队列的工作方式又可分为压缩和非压缩两种结构，直接影响发射阶段其他部件的设计难易和功耗。

• 压缩的发射队列

每当一条指令离开发射队列则上面所有指令都会下移一格填满空隙，新的指令从上面的空闲空间写入。要实现这种压缩方式，需要IQ中每个表项都能下移，因此需要多路选择器用来在其上面表项和原来表项中选择一各。

压缩IQ的优点如下：

分配电路简单，IQ中空闲电路总是处于上部，只要使用发射队列的写指针，指向第一个空闲空间即可；

选择电路简单，指令从上到下按最新到最旧的顺序排好，很容易使用优先级编码器选择最旧的准备好的指令，一般说来和最旧指令存在RAW相关的指令也最多，先执行也可以先释放与它存在RAW相关的指令，增加并行度。

缺点：

浪费硅片面积，如一个IQ对应两个FU，每周期要从IQ中选择两条指令送入FU中，则IQ需要支持两个表项的压缩，多路选择器导致硬件复杂度增加；

功耗大，每周期都要将IQ中的很多指令进行移动。

• 非压缩的发射队列

没有压缩过程，不能根据指令位置判断新旧，不过仍可使用上面方法中的选择电路从IQ最下面的指令开始寻找直到遇到第一条准备好的指令，不过选择的并不一定是准备好的指令中最旧的，因此性能可能会受到影响。

优点如下：

不需要每个周期都对指令进行移动，降低了功耗，减小了多路选择器和布线的面积；

缺点如下：

要实现oldest-first功能的电路，需要更复杂的逻辑电路；

分配电路也非常复杂，需要扫描所有空间而且要找出多个空闲位置存放新指令，这并不容易。

7.4 发射过程的流水线

7.4.1 非数据捕捉结构的流水线

非数据捕捉结构发射阶段的简单流水线中指令被计算出才进行唤醒操作，但这样两条存在RAW相关的指令它们的执行相差了3个周期，显然这样执行效率太低，所以对该流水线进行了优化，通过处理器中的旁路网络，能够使唤醒的过程提前。注意指令A的仲裁和指令B的唤醒操作在同一个周期内是串行的，接近现实的处理器流水线，仲裁和唤醒这两个操作也被称为原子操作。如果将这两个操作分为两个周期执行，则指令B还需要再等待一个周期才能执行，但需要注意原子操作可能会导致周期时间加长。

如果将唤醒和选择分为两个周期，虽然能提高运行频率，但由于增加了一级流水线，所以会带来以下影响：

• 分支预测失败时，惩罚增加；
• Cache访问的时间是固定的，周期时间变小，耗费的周期数增加；
• 频率变高，功耗升高；

因此，最后还是选择将唤醒和选择放在一个周期内执行。

上述描述是假定FU在一个周期内就可得到结果，但不同FU的执行周期数不一样即便是同一FU不同指令的执行时间也不一定相同，如很多处理器的乘法器可提前将16位乘法结果输出。因此可能需要将指令B的wake-up过程延迟一个或多个周期，才能得到运算出的结果。

7.4.2 数据捕捉结构的流水线

该结构离开发射队列时可直接从payload RAM得到操作数，而不用读取PRF，流水线如图8.11，注意在仲裁操作完成后，读取payload RAM和唤醒其他指令是并行进行的，而且在该流水段也可能需要把前面指令的计算结果捕捉进payload RAM，因此该周期既要读取又要写入payload RAM，可能会增加周期时间。

所以可对流水线进一步细分，将多端口payload RAM单独放一个流水段，当指令结果被计算出会被旁路网络送到payload RAM和FU的输入端。

一些更激进的流水线可能会把的仲裁和唤醒这两个操作放到两个周期，这样可以进一步减少处理器的周期时间，但是带来的代价就是相关指令之间不能背靠背地执行了，这会对处理器最大可以获得的并行度产生一定的负面影响。

7.4 仲裁

当采用非压缩的方式设计IQ，则需要分配电路扫描整个IQ在一个周期给出多个空闲表项，并将多个指令写入IQ。分配电路扫描每个表项的标志信号free，可以采用拆分方法从发射队列找到4个空闲表项，查找4个空闲表项的过程是并行执行的，但仍需要多级（取决于IQ容量）处理电路延时。为了更快在一个周期完成上述查找功能，考虑借鉴空闲列表的方案，将空表表项写入到空闲列表中，按FIFO的方式管理，每周期读出4个编号，这样其实延迟也不小，因此考虑更折中的方法如图8.13，将发射队列分为4部分，每周期从每个部分找出一个空闲表项，每部分使用一个分配电路。但如果一个部分没有空间即使其他段还有空间就会导致该周期所有指令都无法写入，这是因为指令在重命名阶段是按程序指定顺序进行的，如果指令A无法写入，那么本周期的BCD都无法写入。可考虑采用缓存的方式将不能写入到发射队列的指令暂存起来，使它们不至于阻碍后续指令写到IQ的过程。
参考：
Superscalar处理器 - 知乎 (zhihu.com)
https://www.zhihu.com/column/c_1488196584454598656