计算机体系结构 | fufu酱のNoteBook

type

status

slug

summary

Intro

D-Cache 缺失有两种情况：

Load 缺失 - 此时需要从memory中取得数据，并在D-Cache中找到一个Cache Line写入。如果被写入的Cache Line是Dirty的，那么还需要先将这个Cache Line写到memory中去。

Store 缺失 - 此时需要也需要从memroy中取得数据，并在D-Cache中找到一个Cache Line合并写入

这样引出了一个问题，即当发生D-Cache缺失而正在处理时，再次发生缺失该怎么办？

一个简单的做法是在D-Cache发生且还未被解决时，锁定Cache与内存间的数据通路，只处理当前缺失的数据，这样处理器就无法处理其他L/S指令了。但这样会大大减少程序执行时可以寻找的并行性，导致处理器性能无法提高，这个过程如下所示：

这种做法也称为 Blocking Cache

Non Blocking Cache

如果在发生缺失之后，仍然可以执行后续的L/S指令，则称为 Non Blocking Cache，其对于处理器性能的提升非常有效果，如下所示：

在这种情况下，L/S指令的D-Cache被处理完的时间可能与原始指令的顺序已经不一样了，为了处理这个问题，就需要保存发生缺失的L/S指令的信息，这样当D-Cache处理完后，才能正确的处理之前的数据。

处理这种情况的部件被称为 Miss Status/Information Holding Register MSHR，其包括两个部分：

左侧为MSHR的本体，用来保存所有首次产生缺失的L/S指令信息，包括：

V - valid位，用来指示当前的表项是否被占用，当首次发生缺失时，MSHR中一个表项会被占用。当所需要的Cache Line被取回时会释放一个占用的表项。

Block Address - 缺失Cache Line中数据块的公共地址。每当L/S指令发生缺失时，都会在MSHR中查找其需要的数据块是否在取回中。这样同一个块缺失只需要被处理一次，避免存储器带宽的浪费。

Issued - 表示首次发生缺失的L/S指令是否已经开始处理。由于存储器贷款有限，有些首次缺失并不一定马上就被处理，而是等到条件满足时才向内存发出读取请求。

右侧为Load/Store Table，每一个发生缺失的L/S指令，都会将自身的信息写到表中，其包括

V - valid位，表示表项是否被占用。

MSHR entry - 指示发生缺失的L/S指令属于MSHR中的哪一个表项，不同缺失指令可能指向同一个表项，因为他们需要的Cache Line可能是相同的。

Dest Register - 对于Load来说，该部分记录了要载入数据的目的寄存器，当需要的数据被取回时，就可以把数据写入到该寄存器中。对于store指令来说，其指向了要写入数据在Store Buffer中的位置，当块被取回时，可以找到要写入的数据在Buffer中的位置并写入到块中，同时释放掉这条数据在Buffer中占用的空间。

Type - 记录访问存储器指令的类型，如LD LW等，以便正确执行指令。

Offset - 记录缺失指令访问的地址在块中的偏移量，从而能够正确找到数据地址。

通过MSHR本体和Load/Store Table的合作可以完成Non Blocking Cache的功能，当一条访存指令发生缺失时，会将发生缺失的地址与MSHR中的Block Address进行比较：

如果发现了相同的表项，表明是再次缺失，此时只需要将指令信息写到Load/Store Table中即可。

否则是首次缺失，需要同时填写MSHR和Load/Store Table的信息。

当MSHR或Table的任意一个满了的时候，应该暂停流水线，等待之前的D-Cache缺失被处理完后，会空出新的表项，允许流水线继续执行。

Store Buffer

Store指令在顺利离开流水线之前是不可以改变处理器状态的，只有当其retire的时候才允许将其携带的数据写入到D-Cache中，在此之前即使Store计算完毕，也需要将结果暂存在一个Buffer中，也就是Store Buffer。

此时所有的Load指令不仅要访问D-Cache，还需要访问Store Buffer，如果Buffer中有相同地址的store指令，且该store指令在load之前进入流水线，那么就需要把Store的数据给load，而不是Cache中的数据。

Buffer中一条Store指令有三个状态：

Un-complete - 没有执行完成

Complete - 执行完毕

retire - 顺利离开流水线

当store指令在流水线的Dispatch分发阶段时，会按照顺序占据Store Buffer的空间，此时为Un-complete的状态。

当store指令已经取到地址和数据的时候，就成为Complete状态

当store指令成为流水线中最旧的指令时，就会retire，此时该指令可以离开ROB；硬件会自动将Store Buffer中处于retire状态的store指令写到D-Cache中：

01-Fundamentals of Computer Design

Quantitative Approaches

Latency (Response Time) - 从开始到结束的时间是多少

Throughput - 在给定的时间内所做的工作量是多少

Elapsed Time - 总的响应时间，包括所有方面的处理（I/O, OS开销，空闲时间）

CPU Time - 处理给定作业所花费的时间

Classical CPU Time

Instructions - 指令数

CPI - Clock Cycle Per Instruction, 每条指令的平均时钟数；

Frequency - 时钟频率

Performance Factor

Algorithm - affects IC, possibly CPI Programming language - affects IC, CPI Compiler - affects IC, CPI ISA - affects IC, CPI, Frequency

Amdahl Law

📌

Make the common case fast!

计算机体系结构的8个主要思想

面向摩尔定律的设计

使用抽象简化设计

加速经常性事件

通过并行提高性能

通过流水线提高性能

通过预测提高性能

存储层次化 - Register → Cache → Memory → Disk → Tape

通过冗余提高可靠性

计算机体系结构—cache 高速缓存

主要介绍了cache的基本常识、基本组成方式、写入方法和替换策略，在基本组成方式和替换策略两节给出了较为详细的硬件实现方法，并不流于空泛，并且补充了SRAM和三态门等与硬件实现息息相关的知识。更高阶的cache优化方法和cache设计实例会在将来更新。

cache与多层次存储结构

理想情况下，我们肯定希望拥有无限大的内存容量，这样就可以立刻访问任何一个特定的机器字，但我们不得不认识到有可能需要构建分层结构的存储器，每一层次容量都要大于前一层次，但其访问速度也要更慢一些。

影响现代处理器性能的两个至关重要的部件是分支预测器和cache（快速缓存），cache参与构成现代处理器的多层次存储结构（参考下图，CPU寄存器--L1 cache--L2--L3--主存--磁盘等大容量存储器），是除寄存器外最靠近CPU核的存储单元，通常由SRAM组成（SRAM的补充知识见2.4节）。

cache的目的和用途

计算机在运行程序时首先将程序从磁盘读取到主存，然后CPU按规则从主存中取出指令、数据并执行指令，但是直接从主存（一般用DRAM制成）中读写是很慢的，所以我们引入了cache。

在执行程序前，首先会试图把要用到的指令、数据从主存移到cache中，然后在执行程序时直接访问cache。如果指令、数据在cache中，那么我们能很快地读取出来，这称为“命中（hit）”；如果指令、数据不在cache中，我们仍旧要从主存中拿指令、数据，这称为“不命中（miss）”。命中率对于cache而言是很重要的。

现代处理器一般有三层cache，分别称为L1 cache、L2 cache、L3 cache。L1 cache离CPU核最近，存储信息的读取速度接近CPU核的工作速度，容量较小，一般分成I-cache和D-cache两块，分别存储指令和数据；L2 cache比L1更远，速度慢一些，但是容量更大，不分I-cache和D-cache；L3更慢、更大，现在流行多核处理器，L3一般由多个处理器核共享，而L1、L2是单核私有的。

实际上cache是一个广义的概念，可以认为主存是磁盘的cache，而CPU内cache又是主存的cache，使用cache的目的就是伪造出一个容量有低层次存储器（如磁盘）那么大，而速度又有寄存器（如通用寄存器）那么快的存储器，简单来说就要让存储单元看起来又大又快。

cache的理论基础

cache之所以能work，主要基于两个认识，即程序运行时数据具有时间局部性和空间局部性。

时间局部性是指一个数据如果当前被使用到，那么接下去一段时间它很可能被再次用到；空间局部性是指一个数据如果当前被使用到，那么接下去一段时间它周围的数据很可能也会被用到，比如数组。

Cache的组成方式

cache容量较小，所以数据需要按照一定的规则从主存映射到cache。一般把主存和cache分割成一定大小的块，这个块在主存中称为data block，在cache中称为cache line。举个例子，块大小为1024个字节，那么data block和cache line都是1024个字节。当把主存和cache分割好之后，我们就可以把data block放到cache line中，而这个“放”的规则一般有三种，分别是“直接映射”、“组相联”和“全相联”。

直接映射

直接映射采用“取模”的方式进行一对一映射。举个例子，如果cache中共有8个cache line，那么0、8、16、24...号data block会被映射到0号cache line中，同理1、9、17....号data block会被映射到1号cache line中，具体可以参考下面的关系图。

注意到上图中的cache除了数据之外还有“标记”位，“标记”可以显示出当前的cache line对应的是主存中的哪一组data block。举个例子，0、8、16.....号data block都可能存入0号cache line，此时标记位可以显示0号cache line到底是哪个data block。

再具体一点，直接映射中cache line一般有三个组成部分，分别是有效位V，标志位Tag，和数据位Data block。实现的电路结构如下。

CPU送来的地址按高低位被分成三部分，tag、index和offset。index用来指定选中哪一个cache line，tag用来与cache line的tag作比较以生成hit信号，而offset则从选择的cache line中选中部分数据进行输出。

要注意的是，index会首先经过一个译码器，译码器生成一段独热码，独热码只会选中SRAM中的某一行，所以在读取data的时候只有对应的cache line会被读出，其他cache不会被读出。

组相连

直接映射中主存中的每一个data block都有一个确定的cache line进行映射，这是有缺陷的。当程序连续读取0、8、0、8号data block的数据时，因为只有一个cache line供映射，所以当第二次读取0号block时，第一次读到cache中的0号block早被顶替出去了，这时候又会产生miss，miss会极大地影响执行效率。

为了解决上面的问题，提出使用“组相联”的方式。组相联的主存-cache对应关系见下图。

根据上图我们很容易发现比起直接映射，组相联翻倍了block可以映射的cache line的数量，图上数量为2，我们称每两个cache line为一个cache set。组相联的实现电路如下。

实现电路和直接映射很相似，不同的地方在于直接映射中index只选出一个cache line，而这里选出了两个cache line。两组data根据tag的比较结果来输入到选择器，实现方式是令两组data直接通过三态门连到一组数据线上。不熟悉这个操作的朋友可以先查阅2.5节内容。

在真实场景中组相联cache的tag和data往往被分开存储，因为分开存储，组相联实现电路分化成了并行和串行实现方式。

下图是并行实现方式。index同时送到tag ram和data ram，同时译码，同时读取tag和data，并根据tag比较的结果来选择一组data进行输出，aligner是字节选择器。这里关键的地方在于我们看起来就像把cache set中的两路cache line横向拼接起来，然后根据index的译码结果选中某一行，这一行包含两个cache line中data。

下图是串行实现方式。相比于并行，这里的关键地方是我们把两路cache line纵向拼接了，这样cache line的数量翻倍，通过tag比较和index译码的综合结果，我们最终只会选中一个cache line，选中的cache line中的数据直接送往aligner。这样的工作过程有明显的串行特征，即首先tag比较，然后才选中某一cache line。

比较串行和并行实现，并行实现因为比串行多一个多路选择器，工作时间会变长，对应的时钟频率会下降，而且每次同时选中多个cache line，功耗较大；而串行实现在用流水线来实现cache时会明显增加所需时钟周期数（多一个时钟周期）。

全相连

全相联是极端的组相联，即cache只有一个cache set。每一个data block都可以存进任何一个cache line。下图是对应关系。

容易想到，全相联不需要index了，下图是实现电路。我们直接对照每一个cache line的tag并由此控制data的三态门输出。这个实现方法是很简单的，但是这里因为需要做大量的比较电路，所以工作延时也是巨大的。(why？因为CPU给出的地址的tag部分需要支持所有的比较电路，负载很大，负载可以简单化成一堆电容，负载很大相当于电容很大，电容很大，充电时间就长，相应的工作时间就长)

SRAM由于其读写速度快的特性，常常被拿来制作CPU内的cache。

下图是SRAM的电路结构，其中T1、T2用于保持A、B点状态，T5、T6构成T1、T2的负载管，T3、T4是选通管。

信息保持 当字选择线W没有被选中时，选通管关断，内部电路与外界隔绝，内部状态得以保持。值得注意的是在保持过程中内部电路一直有电流，这会产生功耗。

读出当字选择线W为高电平，T3、T4同时开启，A、B点是两个反馈点，简单地说A、B点电平是相反的，所以当T3、T4同时开启，因为A、B点的电平状态不同，位线D0、D1上产生的电流会有差异，根据电流的产生情况我们就能知道这一个六管SRAM存储的信息。再具体地说，如果A点是高电平，即六管SRAM存储“1”，则B点是低电平，位线D0会产生电流，位线D1不会产生电流。

写入若要写入一位信息，首先选中字选择线W，然后选择性选通位线D0、D1，如果要写入信息“1”，则令位线D0为高电平，令位线D1为低电平，反之则写入信息“0”.

ceche中每一cache set都包含多个cache line，当index确定之后，对应cache set中的每一个cache line内的数据都可能被取出，这时候我们有两种方法把正确的数据送到字节选择器中，一个方法是用多路选择器，多路选择器的复杂程度取决于我们设计的cache是几路cache，另一种方法是使用三态门。

三态门通常是用来驱动总线的，它允许我们把多个三态门的输出直接连到一根信号线上，条件是连到信号线上的多个输出在同一时刻只能有一个是有效值，其余的输出都应该是高阻态（z），高阻态可以阻断输出线与信号线的联系。

三态门的逻辑门表达，E是使能信号，当E有效，三态门根据输入进行输出；当E无效，三态门输出高阻态。图（b）是三态门的电路结构，当E有效时，这是一个正常的输出缓冲门；当E无效时，两个MOS管（M表示）都是断开的，于是输出高阻态，输出阻抗极大。

cache的写入

第二节主要介绍了cache的基本组成方式，电路实现也主要关注数据的读出，除此之外，cache还需要关注“写数据”的问题。

“写数据”关乎到两种情况：

1、将被改写的数据在cache中；

2、将被改写的数据不在cache中。

针对情况1，我们又有两种策略来写数据：

1、只改写cache中对应的cache line，这被称为“写回”；

2、改写cache line和主存，这被称为“写穿”。

第一种策略的优点是速度快，因为不用访问速度较慢的主存，缺点是只改写cache的话，cache line和主存中的数据不再一致，这会产生“一致性”问题，如果有别的核来访问主存中对应的block，那么它将会读到错误的数据。另外，在cache line被替换出去的时候，数据应该被写进主存，这就要求我们能够辨别哪些cache line是被改写过的，反映在电路上就需要增加一个“脏”位，当一个被标记为脏的cache line被替换出去，其内容需要被写入对应的主存。

第二种策略的优点是时刻保持存储器数据一致，缺点是每次store指令都需要往主存写入数据，这个延时代价是高昂的。

针对情况2，我们也有两种策略：

1、直接把数据写入主存，此被称为“写不分配”；

2、先把data block放进cache line，然后“写回”或是“写穿”，此被称为“写分配”。

一般情况下，“写回”和“写分配”组合，“写穿”和“写不分配组合”。下面两幅图是本节的重点！重点！重点！两幅图依次展示了“写穿”“写不分配”组合的工作流程、“写回”“写分配”组合的工作流程。

cache的替换策略

不论是读数还是写数，一旦碰及miss，就可能需要做替换。读miss时需要从主存调入data block，而这个block可能需要顶替某个cache line，这时候需要替换算法来决定顶替谁。写的时候如果使用“写分配”，那也需要从主存调入data block。cache有很多替换策略，包括FIFO（先进先出）、LRU（近期最少使用）和随机替换等等，本节介绍LRU和随机替换这两种常用的替换方法。

4.1、近期最少使用

LRU的基本思想是选择最近一段时间使用次数最少的cache line进行替换，因此我们需要对一个cache set中的每一个cache line的使用情况进行跟踪，实现方法可以是为每一个cache line都设置一个“年龄位”。

如果是2路cache（即每一个cache set只有两个cache line），那么只需要一位“年龄位”。当一个cache line被使用，那么它的年龄为1，另一个line年龄为0。如果是多路cache，那么就需要多位“年龄位”，当一个cache line被使用，那么它对应的年龄就应该被设置为最大，其他cache line的年龄按照之前的顺序排在它之后，这个过程就好像是把单向链表中的某一节点拿出来放到链表的头，其余节点按照之前的顺序连接在头节点之后。替换的时候总是替换年龄最小的那个cache line，在链表中也就是把表尾去掉，然后把新的块放到表头。

年龄位是通俗易懂的，但是当cache set越来越大，如八路，那么年龄位的实现会变得很复杂，这时候我们有一个简单的方式来实现，首先来大略看看下面一幅图，重点看文字部分。

这个实现方法把八路cache进行分组，第一年龄位把cache set分成两组，一组四个cache line；第二年龄位把四个cache line又分成两组，以此类推。

图上的七个年龄位显示了访问cache line结束后的年龄情况，随着访存的变多，年龄位会慢慢地被填满，然后图中的箭头就会从第一级一路指向某一个way，这个cache line就是最近最少使用的cache line。图中的箭头还没有连完，因为图中只访存了way1和way5。

4.2、随机替换

在处理器中替换算法都是用硬件直接实现的，硬件复杂度可能会很高，有些情况下我们需要简单地实现替换功能，这时候随机替换就派上用场了。

随机替换不需要记录年龄，它只需要一个内置的时钟计数器，每当要替换cache line，就根据计数器的当前计数结果来替换cache line。

这样的方法优点是实现起来很简单，缺点是它不能体现出数据的使用的规律，因为它可能把最近最新使用的数据给替换出去，不过随着cache的容量越来越大，这个缺点所带来的性能损失也越来越小。总的来说，这是一个折中的办法。

小结

本文主要介绍了cache的基本常识、基本组成方式、写入方式和替换策略，在基本组成方式和替换策略两节给出了较为详细的硬件实现方法，并不流于空泛，并且补充了SRAM和三态门等与硬件实现息息相关的知识。更高阶的cache优化方法和cache设计实例会在将来更新。

计算机体系结构—记分牌 ScoreBoard

在高性能应用场景中，顺序执行的 CPU 在上个世纪就被淘汰，现代的高性能处理器基本都支持多发射和乱序执行，但处理器受到数据冒险的影响并不能轻易地实现乱序，所以业界提出了诸如记分牌和 Tomasulo 等算法来控制这个过程。

本文主要回答下面的几个问题：

为什么 CPU 需要乱序执行？

记分牌是什么？

记分牌算法是怎么工作的？

记分牌算法有什么优缺点？

1. 记分牌是什么

要回答记分牌是什么、怎么来的，就要先认识到一个事实：顺序执行的处理器有瑕疵。

顺序执行的处理器有什么瑕疵呢？假想这么一个情况，lw 指令后面紧跟着一连串的计算指令，且这些计算指令和 lw 指令没有关系，在这种情况下，如果lw指令发生 data cache miss，那么它可能会被卡在访存阶段几十上百个周期，而因为处理器是顺序执行的，所以后面的一连串计算指令也都被阻塞住。这里面就出现了一个问题，lw 后面的一连串指令完全不依赖lw指令，但是却因为 lw 指令而没办法继续执行。在理想情况下，我们肯定希望在 lw 指令阻塞的时候，别的可以执行的指令继续执行，不要受 lw 的影响。但是这在一个顺序执行的处理器中是做不到的，顺序执行的处理器只能一个接着一个地执行，如果想要实现“继续执行”，即后面的指令“绕过” lw 指令继续执行，那么就需要处理器支持乱序。

(1) 什么是乱序执行

顺序执行要求指令一条接一条地流过各个流水段，这个过程非常“冯诺依曼”，因为冯诺依曼提出的计算机就是存储指令、一条接一条。这样做有潜在的坏处，就像上面的例子一样，如果一条指令被阻塞，那么它后面的指令也被阻塞，即使后面的指令完全可以继续运算而不受被阻塞指令的影响。所以聪明的设计师想到要开几条“近道”，好让后面的指令能绕过恰过前面的指令，从而继续执行。

乱序的意思也就是指令在执行过程中不按照指令顺序执行，在乱序情况下，只要一条指令所需要的数据准备好了，那么就执行这条指令，而不用像顺序执行一样既要准备好数据，又要前面的指令把“路”让出来。

(2) 多配置流水线

传统的五级流水线中，运算通路只有一条，每一条指令都需要依次通过处理器中的 ALU 、存储器等部件，这个设定有一个言下之意，就是所有指令都按照一个计算流进行工作，但这不是事实。事实是不同类型的指令有不同的计算要求，前面的例子中 lw 指令需要 ALU 和存储器，但是后面的一连串计算指令不需要访问存储器，所以它们完全可以绕过存储器继续执行，但是因为五级流水线中设计每条指令都要经过存储器，所以后面的计算指令不得不等着 lw 把存储器让出来。

如果想要计算指令不经过存储器，最好的方式就是为计算指令单独开一条路，这一条路不经过存储器。同理，计算指令也有各种各样的计算要求，加法和乘法指令所需要的计算部件肯定也是不一样的，所以可以为加法、乘法等不同的计算指令开出属于它们自己的路。有了这些路，指令就可以实现超车，从而不会出现上面例子中的尴尬场面。这里说的“开路”就是为各种指令做个性化的配置，在五级流水线中只有一个配置，而乱序执行要求处理器实现“多配置”，实现“多配置”的流水线处理器就是多配置流水的，多配置流水的处理器可以实现乱序执行。

(3) 记分牌算法

记分牌算法是 CDC 公司在上个世纪提出的一个乱序执行算法，合理使用记分牌算法，就可以让多配置流水的处理器实现乱序执行。首个应用记分牌算法的处理器是CDC公司在上个世纪六十年代研发的 CDC 6600，实际上 CDC 6600 不能说是一个处理器，因为 CDC 6600 是一个几吨重的超级计算机。下图是 CDC 6600 的结构示意。

在这个结构示意图中很容易看到 CDC 6600 是多配置的，它有两个浮点乘法模块（FP mult）、一个浮点除法模块、一个浮点加法模块和一个整数模块（用于计算 lw、sw 指令的地址），图中的 Scoreboard 就是记分牌，这个“记分牌”其实是一个信息存储单元，下面用两页PPT来解释记分牌存储了什么：

上图是记分牌的第一部分——功能单元状态。重点看绿色字体和绿色字体后面的解释，这些就是记分牌记下的信息。记分牌是面向功能部件的，在记分牌中每一个功能部件都有一组信息，信息包括部件是否正在忙、部件执行的指令类型、部件现在需要的源寄存器、部件现在的目的寄存器、源寄存器是否准备好（Rj、Rk 表示）和如果源寄存器没准备好部件该向哪里要数据（Qj、Qk 表示，PPT 中有一个表格，表格 Mult1 这一行 Qj 是 Integer，这就表示乘法单元 1 的 F2 源寄存器的数值将由整数部件算出）

上图是记分牌记录的第二块信息——寄存器结果状态。里面主要记录对于某一个寄存器，是否有部件正准备写入数据。例如上图中 F4 对应 Mult1，这就表明乘法单元1的计算结果将要写入 F4.

上面两部分信息就是记分牌存储的全部信息，第二节将会为大家解读 CDC 6600 的工作流程。

工作流程解读

下图是我绘出的记分牌工作流程示意图。在用记分牌实现乱序执行的处理器中（这里特指 CDC 6600 处理器了），一条指令分四个阶段执行，分别是发射、读数、执行、写回。本节会逐阶段解读工作过程。

对示意图做一点补充，黄色方框表示流水段寄存器，分别有指令寄存器、部件寄存器（即 MUL_1 这一列）、操作数寄存器（ OPRAND ）、结果寄存器（ RESULT ）。蓝色部分是解码单元和运算单元。红色部分是寄存器堆。绿色部分是记分牌。解码单元和记分牌的交互是指解码单元要“问”记分牌当前指令是否有“ WAW 冒险”和“ Structure 结构冒险”，如果没有，指令就可以顺利渡过当前的阶段，后面的 RAW、WAR 也都是这个意思。

发射

对指令进行解码，并观察记分牌信息，主要观察各个功能部件的占用情况，和寄存器堆的写情况，以此来判断是否可以把解码得到的信息存进对应的部件寄存器。

如果指令对应的功能部件空闲，且指令要写的目标寄存器没有别的指令将要写（这是为了解决 WAW 冒险），那么阶段结束的时候，就可以把指令信息存进部件寄存器，同时改写记分牌，把指令相关信息进入记分牌。

取数

观察记分牌，了解当前指令需要哪些寄存器的数值、该数值是否准备好、如果数值没有准备好的话数值正在哪个功能部件进行运算。如果数值没有准备好（这是为了解决 RAW 冒险），那么指令就卡在部件寄存器中，无法读取数据。

如果寄存器都可以读取，那么阶段结束的时候，对应的寄存器数值会被存进操作数寄存器中，注意，这里不会改写记分牌。

执行

执行计算过程，计算过程可能维持很多个周期。

在第一个计算周期结束时，记分牌的读取寄存器部分内容（即 Rj、Rk ）会被修改，表明指令不再需要读寄存器。至于为什么不在读取阶段结束时就这么修改，我也不清楚。

在得到计算结果的那个周期结束时，结果会被存进结果寄存器。

写回

此时需要观察记分牌，如果别的指令不需要读当前计算结果即将写入的寄存器（这是为了解决 WAR 冒险，需要观察所有 Rj、Rk，如果相关寄存器的 Rj、Rk 是 Yes ，那就说明有指令要读当前要写入的寄存器，如此一来就要先等前序指令读完寄存器再写回），那么周期结束时，就会把结果写回到寄存器堆，同时会清空记分牌中的信息。

工作流程演示

第一个周期，记分牌是空的，功能部件也都是空闲的，因此第一条指令顺利渡过发射阶段，并在周期结束的时候更新了记分牌。

注意看更新内容。整数部件现在显示忙碌，而 LD 指令的操作数不存在冒险，Rk 显示 Yes，在寄存器状态里标记 F6 即将被整数部件改写。

第二个周期，因为整数部件被占用了，所以第二条 LD 指令不能发射。同时第一条 LD 顺利渡过读数阶段。

第二条 LD 在周期结束时不会更新记分牌。

第三个周期，在流程解读一节，我们已经看到 INST 寄存器只有一个，所以发射阶段是阻塞的、顺序的。因为第二条 LD 没法发射，后面的指令都没办法发射。

第一条 LD 顺利渡过执行阶段，并在周期结束时改写了记分牌，这里主要是解放了 Rk（从 Yes 变为 No ），即表示自己不再要读取寄存器 R2.

要点总结和补充（重点）

总结和补充一下记分牌工作流程中的要点：

一条指令能否发射，一看是否有功能部件空闲可用，这个信息包含在功能状态中；二看指令要写的寄存器是否正要被别的指令写，这个信息包含在寄存器状态中，观察这个信息是为了解决 WAW 冒险。

一条指令能否读数，要看记分牌是否提示源寄存器不可读，如果不可读，就说明该寄存器将要被别的前序指令改写，现在的指令要等待前序指令写回，观察这个信息是为了解决 RAW 冒险。

一条指令一旦读数完成，就必然可以进行运算，运算可以是多周期的，在第一个周期结束时应该改写功能状态，表明自己不再需要读寄存器。

一条指令能否写回，要看是否有指令需要读即将被改写的这个寄存器，具体一点来说，就是要观察标记 Yes 的Rj、Rk 对应的寄存器里是否有当前指令的目的寄存器，如果有，就说明有指令需要读取寄存器的旧值，这样一来我们就要等指令读完旧值之后再写回，观察这个信息是为了解决 WAR 冒险。

记分牌的优缺点

记分牌算法是 CDC 公司提出的一个优秀的乱序执行算法，不过记分牌本身还是有一些不小的缺点，所以在 IBM 提出 Tomasulo 算法之后，业界普遍更青睐 Tomasulo 算法。

上图显示了记分牌算法的一些优缺点，第一行文字揭示了记分牌算法的两个特点：顺序发射和乱序执行。

记分牌算法的优点是实现了指令的乱序执行，解决了乱序执行过程中的数据冒险问题，实现了指令的数据流式运行（即数据一旦准备好就开始运行，这区别于传统五级流水线中控制运行方式），并且实现起来并不复杂。

但是记分牌算法还是会因为 WAR 和 WAW 冒险而产生阻塞，且一旦产生阻塞，后续相同类型的指令就没办法继续发射（在乱序执行过程中，记分牌规定每一条配置路线都只能同时存在一条指令），即图中所列的“ Limited waiting space at functional units ”，如果后续相同类型的指令没法发射，那么更后面的也许可以立马执行的指令也会被阻塞到，这对性能有很大的影响。

而且记分牌算法在指令完成时不是顺序的（即写回的时候不按顺序），不按顺序完成指令会对程序的调试提出挑战。

💡

记分牌算法由 CDC 公司在上个世纪六十年代提出，是一个实现方式简单的乱序执行算法，应用多配置流水和记分牌算法，就可以实现一个乱序执行的处理器。但是记分牌又有一些缺点，这些缺点给了 IBM 提出的 Tomasulo 算法后来居上的机会。随着学习的深入，需要掌握 Tomasulo 算法的原理和算法流程。