计算机体系结构

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 算法的原理和算法流程。

结构：

指令状态表

功能部件的状态表

结果寄存器的状态表

issue 发射

read operands 读操作数

Execution 执行通知记分板已经执行成功了

write result 写结果，写入到目标寄存器中

Tomasulo算法与记分牌

计算结果通过专用通道直接从功能部件进入到保留战进行缓冲，而不是写入到寄存器中

公共数据总线CDB

issue 从指令队列中取出指令

execution

write back

本文重点关注下面几个问题：

假数据冒险是什么？如何去消除？

Tomasulo算法是什么？如何工作？

Tomasulo算法的优点在哪里

Tomasulo算法有什么缺点，应该如何改正

一、消除假数据冒险

Tomasulo算法最大的特点和优势就是通过借助寄存器重命名的思想消除了假数据冒险，从而提高了处理器的乱序性能。

根据判断结果，SocreBoard采用停滞发射、tag广播和停滞写回机制解决了三种数据冒险，从而在逻辑上支持了乱序执行。

重要的是“读后写”、“写后写”两个冒险是“假的冒险”

总结

总结和补充一下Tomuasulo调度流程中的要点：

一条指令能否发射，要看对应配置通路的保留站是否有空余，只要有空余，就可以发射到保留站中等待执行；发射的同时会把能读取的数据直接拷贝到保留站，这样做就不用考虑读后写冒险，后续的指令只要完成就可以写回，不用顾虑是否会有前序指令需要读取寄存器，换句话说，每一条被发射到保留站中的指令都不再需要读取寄存器堆。

指令在发射的时候会更新寄存器状态表，如果后序指令和前序指令的目的寄存器重合了，就用后序指令的写信息标志寄存器，表示只会把后序指令的计算结果写进寄存器，这样可以解决写后写冒险；

如果执行单元中有指令正在执行，其他指令就在保留站中等待；如果指令缺少源数据，就留在保留站中，时刻监听CDB总线，如果CDB总线广播了需要的数据，就立马拷贝下来，然后准备执行。

一条指令在源数据全部准备好之后就可以执行，执行可能是多周期的。

一条指令只要完成计算，就可以写回，写回的数据通过CDB总线直通寄存器堆和各个保留站。但是要注意的一点是指令的结果未必会写进寄存器堆，因为寄存器结果状态表中总是存有最新的状态，即如果发生写后写冒险，Tomasulo算法会记录下最新的写指令，而抛弃前序的写指令结果，前序写指令的结果不会写回到寄存器堆，这样的做法很符合数据流思维。

但是Tomasulo也不是完美的，它也存在一些问题，图7的PPT显示了Tomasulo算法的一系列问题。Tomasulo算法中每一个执行单元对应一个保留站，保留站中缓冲多条指令，所以有可能在同一周期有多条指令准备好数据，但是执行单元同时只能执行一条指令，所以就需要从中选择一条指令，简单的解决办法是为保留站的每一行增加一个年龄位，每次出现冲突，就选择最老的指令送到执行单元。在前文的举例中，电路里的CDB总线只有一组，这意味着每一个周期只能写回一条指令，如果同时有多条指令完成，那就只能选择一条指令进行广播，别的指令等待；第二种办法是增加CDB总线，支持多指令广播，但是这会让电路面积大增，包括增加寄存器堆写口、增加保留站tag和CDB总线的比较电路、增加保留站写口。

Tomasulo成功地解决了三种冒险，实现了指令的乱序执行，且性能比记分牌更好，具体优化的地方有三：

记分牌每条通路只能存一条指令，导致经常有指令因为结构冒险而不能发射，而Tomasulo引入保留站之后每条通路可以缓冲下多条指令，这样的做法平缓了指令发射的速度；

写后写冒险时，记分牌过度纠结寄存器名字，会把所有指令的结果都写进寄存器堆，会因为写后写冒险阻塞指令发射，而Tomasulo只保存最新的写入值，这样即保证了正确的结果，又减少了无谓的工作；

读后写冒险时，记分牌过度纠结寄存器名字，指令在执行之前一直检测的是寄存器堆，一旦数据准备好，就会从寄存器堆中取数，这样的后果就是后序指令即使计算完结果也可能不能立刻写回寄存器堆，而Tomasulo则在发射时就拷贝数据，贯彻数据流的思想——“寄存器名字不重要，寄存器里的数据才重要”。

在写后读冒险中两者都用CDB总线实现了逻辑上的正确，都解决了写后读冒险。

最后还有最为重要的一点，Tomasulo算法没办法实现精确中断，精确中断是指在指令和指令之间如果出现了中断/异常，那么处理器要确保中断/异常之前的所有指令都执行完毕，而中断/异常之后的所有指令都没有执行，然后处理器把中断发生时的处理器状态给保存下来或是呈现给程序员看。这样的精确中断保证了程序的正确执行，也提供程序员调试程序的手段，是现代处理器必不可少的能力，而Tomasulo并不支持。要支持精确中断，就要确保指令按序提交。在记分牌和Tomasulo两篇文章的举例中，我始终没有提到分支指令，这是因为这两个算法不支持按序提交，如果指令没办法按序提交，那就很难处理分支指令，如果有分支预测且分支预测失败的话，这两个算法很难恢复处理器状态。基于此，设计人员提出了重排序缓冲的概念，利用这一概念，可以改进Tomasulo算法，从而实现处理器的按序发射-乱序执行-按序提交。重排序缓冲的知识会另开一文。