计算机体系结构----计分板（scoreboard）算法

计分板算法简介

计分板记录着所有必要的信息，用来控制以下事情：

1. 每条指令何时可以读取操作数并投入运行（对应着RAW冲突的检测）
2. 每条指令何时可以写入结果（对应着WAR冲突的检测）
3. 在计分板中，WAW冲突是在issue阶段检测的，因此仍会导致整个流水线的停顿（另一篇博文提到的Tomasulo算法提供了一种更优美的解决方案）

需要强调的是，计分板算法和普通的流水线是不一样的，一般我们讨论的普通的五级流水线只有一个ALU，所以当一条指令在使用ALU时，其它指令是没法进入EXE阶段的，但是计分板算法不一样，它有多个功能部件，如果指令使用的是不同的功能部件，是能同时进入EXE阶段的。同理，计分板算法对寄存器堆的读取也是可以多条指令同时进行的，但是普通流水线是只有一条指令能访问，普通流水线和计分板算法一样的是一个cycle最多发射一条指令。下面的计分板示例流程会说明计分板算法的特点。

动态调度核心思想回顾

1. 允许就绪指令越过前面的停顿指令，率先投入运行，即乱序执行
2. 为了支持乱序执行，需要对ID阶段进行改造，因为就绪指令就是在ID阶段被阻塞的
3. 为了改造ID，需要分析ID阶段的约束条件和存在的问题：

• 约束条件：ID阶段必须按序执行，因为，如果前一条指令还未译码，后续的指令就无法进行冲突检测
• 存在的问题：在一个必须按序执行的阶段，执行了过多的检测，导致停顿增加

4. 解决方案：将ID阶段拆分为两个阶段：

• Issue：对应之前的ID阶段，但精简操作，只做最必要的事：如指令译码、资源冲突检测
  – 这一阶段仍是按序执行的，并且，在这一阶段停顿的指令，同样会阻塞后面的所有指令（比如下面例子中因为资源冲突而未能发射的第二个LD阻塞了后面所有的指令）
  – 但这一阶段不再检测所有数据冲突，因此不管就绪还是非就绪的指令，都有机会发射出去
• Read operands：等待数据冲突消除，然后读取操作数
  – 这一阶段检测数据冲突，也是乱序执行实际发生的位置：非就绪指令会停顿在这一阶段，就绪指令会直接投入运行

5. 不管是什么样的动态调度流水线，都要将ID做这样的拆分，差别主要是如何管理已发射、未就绪的指令：计分板算法使用计分板，Tomasulo算法使用保留站

每条指令的执行阶段

Issue阶段通过停顿整个流水线所有级解决WAW冲突。
Read operands通过监控源操作数是否可获得（available）来判定这个指令是否能执行以解决RAW冲突，这只会造成单条指令的停顿，流水线还是能继续
Write result阶段如果有数据需要写回，计分板会先判断是否有先前的指令在读这个数据且还没读完，通过引入停顿的方式解决WAR冲突，这只会造成单条指令的停顿，流水线还是能继续

计分板算法标记简介

计分板算法运行示例

注意cycle1阶段，发射的时候就已经知道源和目标操作数以及源和目标操作数是否准备好，并不需要等到Read operands阶段。

Cycle2时，因为Read oprands操作，读取完操作数后把Rj从Yes变成No，使得其他指令没法对R2进行写，这样可以避免WAR冲突。同时由于Interger部件被占用，第二条指令及后面的流水线全部停顿直至第一条指令执行完毕。

注意：cycle5阶段，虽然第一个条指令已经过了excution阶段到了write result阶段，但是第二条load指令并不会发射，只能在下一个周期发射。且注意write result阶段会把计分板中和这条指令相关的所有功能部件状态及寄存器状态清空

注意：cycle11是可以一次读取两个oprands的，MUL和SUB指令同时在这个时钟周期读取了操作数。

注意：cycle12、cycle13中不同的指令可以利用不同的功能部件同时执行，MUL和SUB指令同时在这两个时钟周期处理了操作数。

注意，cycle14阶段，最后一条ADD指令只会在SUB写回的下一个周期才开始发射






注：cycle23阶段，DIV读完操作数ADD就可以写回了。

计分板算法性能分析

1. 计分板算法没有处理控制冲突，乱序执行仅局限在一个基本块内
2. 没有消除WAR/WAW冲突，这些冲突仍会导致停顿

• 上述例子中的ADD.D的写回操作就被DIV.D给阻塞而停顿了。这属于WAR冲突。
• WAW冲突在上述例子中没有显示出来，但是很显然计分板算法没解决这个问题，只能通过停顿解决。