计组-理论-MIPS处理器设计

处理器概述

对于CPU而言，其本质也是一个抽象的状态机，其体系结构状态对程序员可见。随着时钟周期指令的执行，CPU进行状态转移。组合逻辑进行功能的处理，时序逻辑进行状态的转移

• 状态=程序员可见的状态
• 次态=指令执行的规范
• 没有中间状态，每条指令对应一个状态转换

CPU的功能

CPU的功能：控制指令执行

指令的四种基本操作：取数、存数、传送、运算

• 取数：读取某主存单元的数据，并传送至某个寄存器；
• 存数：将某个寄存器中的数据存入主存某个单元之中；
• 传送：将某个寄存器中的数据传送至ALU或另一个寄存器；
• 运算：进行某种算术或逻辑运算，结果保存到某个寄存器中。

指令周期：CPU从指令寄存器中读出并执行指令功能的全部时间

• 取指周期：完成取指令操作和分析指令的所需时间
• 取数周期：从数据存储器读出操作所需的时间
• 执行周期：完成指令所规定的运算的所需时间

CPU的组成

分为数据通路、控制单元、总线

数据通路

数据通路（执行单元）：包含了运算单元和寄存器单元

• 运算单元：ALU、译码器、多路选择器等
• 存储器、寄存器：通用寄存器组GPRs、标志寄存器FR、临时寄存器TR

控制单元

• 指令地址部件：程序计数器PC

• 指令寄存部件：指令寄存器IR

• 译码部件：指令译码器ID

• 时序部件：产生时序信号

• 控制信号生成部件：产生计算机及其他部件所需要的所有微操作的控制信号

  控制信号是CPU的灵魂，对于不同的指令，数据通路都是相同的，指令执行的区别就在于生成的控制信号的不同

单周期CPU

对于一条指令，通常的执行流程为：（这也是MIPS处理器的5级分割法）

• 取指令：根据PC，访问指令存储器获得PC，然后PC=PC+4
• 读寄存器：根据指令格式，读取相应寄存器获取操作数
• ALU运算：通过ALU完成相应的算术逻辑运算
• 数据存取：lw、sw访问数据存储器
• 写寄存器：进行写回操作

对于单周期处理器，所有指令的执行都在一个周期内完成，CPI=1。其间的操作可以认为是组合逻辑操作，没有时序逻辑，没有回路

数据通路设计

采用哈弗体系结构：使用指令存储区IM和数据存储区DM

先为每类指令设计单独的数据通路，再考虑合并，利用控制信号满足不同指令的个性化需求

多周期设计

单周期最长的数据通路是lw的数据通路，但是极少有指令会有这么长的数据通路。不同类型的指令有着不同的指令周期，单周期的时钟周期去最长的指令的运行时间，造成了性能的浪费。

若采用可变时钟周期，性能提高，但是控制比单周期复杂困难，得不偿失。尝试采用多周期的设计方案。

多周期的方案将单周期中隐式的状态机转变为了显式的状态机，当前正在工作的部件即为当前的状态。

多周期处理器的CPI<1。下一个周期的控制信号可以在上一个周期生成，多周期通过这样的overlap隐藏延迟

流水线

流水线的核心思想是复用硬件，在每个时钟周期内数据通路上实际在执行多条指令，实现了指令的并行。

理想的加速比，是流水线的级数，称这种情况是线性加速比。一般情况随着级数增加加速效果增加下降

MIPS处理器分为5级：取指令、译码、执行运算、访存、写回。在不同级之间增加流水寄存器，当前指令的状态保留在寄存器中，随着时钟周期在数据通路中进行流动。指令执行的数据来源只能是流水寄存器/转发。

在下一个时钟沿到来的$t_{\text{setup}}$之前，需要准备好全部的数据

对同一个内存空间的访问，其实是一种通信方式

流水线冒险

也成为依赖或相关：在下一个时钟周期妨碍下一条指令执行的状况，指令之间有序的关系

• 结构冒险：多个阶段都会用到某个硬件资源
• 数据冒险：等待之前的指令完成数据读写
• 控制冒险：指令依赖之情分支执行的指令，无法确定执行哪一条指令

结构冒险

当处于两个流水段的指令需要同一个资源时会发生冲突

• 方案一：复制资源或提高资源的吞吐能力
  • 将指令存储器和数据存储器分开：将普林斯顿结构改为了哈弗结构
  • 对于GRF的读写问题，可以在时钟周期的前半段读，后半段写；也可以增加端口，使得能够同时实现读写
• 方案二：检测资源争用，使其中一个争用流水线的指令阻塞

数据冒险

共有三种指令间的数据依赖关系：

1. 写后读。又叫流相关，关于值的相关性，真相关
2. 读后写。又叫换相关，关于寄存器名的相关性，伪相关
3. 写后写。又叫输出相关，关于寄存器名的相关性，伪相关

读后写和写后读只要保证在前半周期读，后半周期写，也就是阻塞赋值，则不会出现问题。写后读才是真相关，是需要处理的问题。五种处理读后写的方法为：

1. 等待并阻塞直到值在寄存器堆中可以访问
2. 检测并转发/旁路数据给相关指令：变相解决了数据传递的问题
3. 检测并消除相关性：软件层面，由编译器操作，进行指令重排等拉开距离
4. 检测需要的值，“投机”执行，并进行验证
5. 其它：细粒度多线程
   • 切换线程，执行其他线程的不相干的指令

怎么检测：增加score boarding机制：

• 给GRF添加一个表项，用于标明当前指令是否要写该寄存器
• 如果下一条指令想要读被标记的寄存器，则延缓
• 在指令写后讲表项恢复，指令继续执行

解决策略：旁路/转发

数据已经在数据通路中被计算完成，但还没有写入目的地中，于是进行转发。（写回是流水线的最后一级）。增加数据通路，使得提前将运算得到的数据转发到需要处。

转发的对象应该是数据，数据流回到之前会带来风险，转发的来源只能是流水寄存器，这样可以避免毛刺等现象。对于无法转发的数据，则进行阻塞。判断依据为AT法

AT法和阻塞

对于阻塞操作，是所需要的数据还没又被计算出来，没法进行转发，于是进行阻塞，等待数据被计算出来。

判断数据什么时候被算出来使用AT法，即Address-Time，按照数据的目的地-时间进行区分。

对与流水线中的数据，是和指令相关的，流水线中各级执行的指令至多向寄存器堆中写回一个数据，这个数据有两个基本性质：写入和地址和产生的时间。而对于指令而言，其当下（在这个级中）需要的数据也有两个属性：读出的地址和需要的时间。

如果写入地址和读出地址相同，那么说明出现了数据冲突，需要尽可能地使用转发来解决。如果需要的时间>生成的时间，那么说明在需要之前就可以生成，可以进行转发，否则就需要阻塞。注意这里说的生成和需要，数据的对象都是流水寄存器，只有写入寄存器才算生成，来源也只能是流水寄存器。

则对于某一个指令的某一个数据需求，我们定义需求时间$T_{use}$为：这条指令位于 D 级的时候，再经过多少个时钟周期就必须要使用相应的数据。例如，对于beq指令，立刻就要使用数据，所以$T_{use}=0$。对于 add 指令，等待下一个时钟周期它进入 E 级才要使用数据，所以$T_{use}=1$。而对于sw指令，在 E 级它需要GPR[rs]的数据来计算地址，在 M 级需要GPR[rt]来存入值，所以$rs\_T_{use}=1$ ，$rt\_T_{use}$。

我们可以归纳出$T_{use}$的两条性质：

• $T_{use}$是一个定值，每个指令的$T_{use}$是一定的；
• 一个指令可以有两个$T_{use}$值。

对于某个指令的数据产出，我们定义供给时间$T_{new}$为：当前位于某个流水级的某个指令，它经过多少个时钟周期可以算出结果并且存储到流水级寄存器里。例如，对于 add 指令，当它处于 E 级，此时结果还没有存储到流水级寄存器里，所以此时它的，$T_{new}=1$，而当它处于 M 或者 W 级，此时结果已经写入了流水级寄存器，所以此时$T_{new}=1$。

我们可以归纳出$T_{new}$的两条性质：

• $T_{new}$ 是一个动态值，每个指令处于流水线不同阶段有不同的$T_{new}$值；
• 一个指令在一个时刻至多有一个$T_{new}$值（一个指令至多写一个寄存器）。

在阐述完所有的数学概念后，我们就可以利用这些概念来描述转发的条件：

• 当$T_{use}>=T_{new}$，说明需要的数据可以及时算出，可以通过转发来解决。
• 当$T_{use}<=T_{new}$，说明需要的数据不能及时算出，必须阻塞流水线解决。

对于阻塞，由于计算$T_{use}$都是D级的指令，故阻塞的对象最晚也只能是D级中的指令。当阻塞时，给D级提供数据的流水寄存器维持原先值，即D即不载入新的指令；E级流水寄存器清空，D级的指令不往前走；F级无流水寄存器，来源是IFU提供的PC值，也维持不变。由于清空E级后，相当于指令变为了nop，故阻塞相当于在指令流中插入nop

控制冒险

控制相关/控制依赖：指令流依赖之前的指令

下一拍从PC中取出来的值是下一条指令的地址，所有的指令都和之前的指令存在控制相关

不同类型的分支处理的方式不同，分支的类型：

类型	取指令阶段能否判断是否跳转	下一个可能地址的数量	何时能解析出下一个取址的地址
条件分支	不知道	2（PC+4或者跳转的地址）	执行（寄存器相关）
无条件分支	总是发生跳转	1	译码：PC+offest
调用	总是发生跳转	1	译码：PC+offest
返回	总是发生跳转	多	执行：寄存器相关
间接分支	总是发生跳转	多	执行：寄存器相关

处理控制冒险：关键在于使流水线保持充满正确的动态指令序列

当指令是控制指令的可能的解决方案：

1. 停顿流水线直到得到下一条指令的取值地址

2. 猜测下一条指令的取址地址：分支预测

   • 猜错的可能性是多大？猜错的损失是多大？预期等待，不如塞入PC+4的指令，猜测继续执行指令
     • 猜对了，没有乘法；猜错了，两个气泡
     • 20%的控制指令，70%的控制指令发生跳转，CPI=1+0.2*0.7=1.28
   1. 去掉不必要的控制指令
   2. 分支判断提前：提前处理分支条件和获得目标地址
   • 但是CPI减小了，时钟周期却可能拉长了

3. 采用延迟技术：分支延迟槽。无论是否跳转，总是执行下N条指令

   • 插入延迟槽的操作由编译器实现，往往插入nop
   • 目前的操作就是引入延迟槽，在D级即引入单元判断是否跳转，F级已经取出的指令继续执行。看似解决了问题，但是如果判断需要的数据无法转发，需要进行阻塞，则还是没有办法，不是解决问题根本方法

4. 其他：细粒度多线程

5. 消除控制指令：推断执行

6. 从所有可能的方向取址：多路径执行

分支预测

分支预测是时刻在进行的，不是只有出现分支指令后才开始进行。在取指阶段进行三件事：

1. 是否为分支指令
2. 分支的方向
3. （如果跳转）分支的目标地址

分支目标缓冲BTB

一种朴素的思路：每次跳转到地址可能是相同的（如循环）。存储当前实例的目标地址，由PC访问之。

静态分支预测

• 总是不发生
  • 实现简单：不需要BTB，不需要进行分支预测，只需要阻塞
  • 准确率低：只有30~40%
  • 编译器可以重新布局代码，使可能路径成为不发生的路径
• 总是发生
  • 无方向预测：反向/正向
  • 准确率较高，反向分支通产会发生
• 反向发生，正向不发生：BTFN
  • 预测loop反向分支发生，其他不发生
• 基于剖析（可能的方向）
  • 编译器通过运行分析代码为每个分支决定可能的方向。分支指令编码增加一位代表可能的分支方向
  • 分析代码如果有代表性则预测的比较准确，依赖于分支的动态行为
• 基于程序分析（可能的方向）
  • 使用基于程序分析的启发式方法来确定静态预测的分支方向
• 基于程序员：程序员手动提供静态分支的预测方向，通过pragma著名
  • 程序员对程序更熟悉，但会增加程序员负担
  • 现代编译器和CPU的预测能力好于程序员

动态分支预测

运行时采集信息，基于动态信息进行预测。预测能力更强，但需要额外的硬件

• Last time预测器：总是预测上一次的方向，每个分支1bit代表方向

  • 类似于一个状态机，进行发生-不发生之间的预测转换

  • 为了应对可能的转换太快的效果，为预测器增加滞后效果，多次同分支后才改变预测方向

    

    

全局分支相关

全局分支相关：一个分支的结果可能和其他分支的结果相关

将分支结果和所有分支的全局T/NT历史关联，根据上一次相同全局分支历史的分支结果做出预测

• 使用全局历史寄存器GHR跟踪所有分支的全局T/NT历史
• 将GHR索引为一张表，记录过去和GHR中相应的分支的结果->模式历史表

本地分支相关

本体分支相关：一个分支的结果可能和同一个分支过去的结果相关

本地分支预测器：每个分支都有一个历史寄存器，记录该分支过去历史发生/不发生的关联

混合分支预测器

使用不止一种类型的预测器，采用多种算法，选择最佳的预测

流水线工程化方法

流水线：以性能为目标的标准流水线

• 数据冒险：转发、阻塞
• 控制冒险：分支比较迁移，转发、阻塞

三控制架构：

1. 功能部件控制：译码单元
2. 暂定（阻塞）控制器
3. 转发控制器

中断和异常

IO的速度差异很大：

处理器要为IO做什么：

• 输入：读字节序列
• 输出：写字节序列

有些处理器有单独的输入输出指令。在MIPS中用load实现输入，store实现输出，以一部分的地址空间作为输入输出谁被的通信通道，这部分内存被关联到设备的寄存器（控制寄存器、数据寄存器）（共享地址的读写是一种通信的手段）。

通向设备的数据通路上通常有两个寄存器：控制寄存器和数据寄存器。分别用来确认是否读写和暂存数据。处理器周期性查询控制寄存求（轮询），等待设备置位（ready bit 0->1），接着load或store数据到数据寄存器中。

当外部设备增加后，处理器频繁的轮询会使得处理器陷入一种“自旋等待”状态，因而可以改为当IO设备准备就绪时调用相关的过程：异常。通过异常机制触发IO，然后在IO进行数据传输时中断程序

• 异常：处理器内部产生，一旦检测出来立即处理（如溢出、系统调用、为定义的op）
• 中断：来自外部IO设备，“方便的时候处理”（除非高优先级）

处理异常

MIPS中异常由系统控制协处理器CP0处理，保存出问题或被中断的的指令的PC内容。

• 保存出问题或被中断的指令的PC的内容
• 保存问题的描述：MIPS中保存到特殊的cause寄存器中，编码为问题类型
• 跳转到异常处理的代码，起始地址为0x8000_0180
• 通知OS：杀掉程序或者切换到另一个进程

可重启的异常

可重启的异常：流水线能够清空指令，处理程序的执行，执行完毕返回指令，以重新取址和执行。PC+4保存在EPC寄存器，用于识别导致异常的指令（使用PC+4是因为是流水线数据通路中可以获得的指令）。

处理程序的动作

读cause寄存器，传递给相应的处理程序

• 如果异常可重启，执行正常的操作然后使用EPC返回程序
• 否则结束程序并使用EPC、cause寄存器等信息报告错误

IO中断

IO中断是异步的，随时可能发生，和指令无关。异常是相对指令执行的，中断可以在任何指令执行的过程中发生。

异常一定要处理，中断可以不处理，也不会阻止任何指令的执行

中断驱动的数据传输：

1. IO引发的程序中断
2. 保存当前指令执行的PC+4
3. 跳转到中断处理程序的地址
4. 执行中断相应的数据传输程序
5. 跳转回到用户执行的程序指令

协处理器

共有4个协处理器：SR,cause,EPC,PRId，寄存器编号分别为12,13,14,15

• SR：用于对系统进行控制，指令可读可写

  • IM7-2[15:10]：6位中断屏蔽位，分别对应6个外部中断：1/0表示是否允许中断

  • IE：全局中断使能：是否允许中断

  • EXL：异常级：1表示进入异常，不允许再中断，0表示允许中断。重新进入需要OS的配合，尤其是堆栈

    

• cause：指令读取，硬件控制写入

  • IP7-2[15:10]：对应外部的6个中断源，记录当前哪些硬件中断正在有效

  • ExcCode[6:2]：异常/中断类型编码值，共32种

    

• EPC：用于保存异常/中断发生时的PC

  • eret：中断/异常服务程序返回指令

    

• PRId：处理器ID，可以用于实现个性的编码

流水线的异常处理

在流水线的每一级，都可能发生异常

• F：PC地址异常
• D：op非法
• E：运算过程种溢出
• M：数据地址异常

流水线的收益来自于指令执行开销的重叠，当指令流突然中断的时候（发生异常）会产生错误。

许多的异常必须是精确的，当一个异常是精确的时(同步并且可在断点处恢复)。所有在出错指令之前的指令必须完成，出错指令和它之后的所有指令必须被销毁（清空），异常处理程序必须开始执行。

通常不适宜在异常发生的周期中立即处理异常，因为

• 同一个周期内可能发生多个异常
• 在不同的流水段处理异常会比较复杂
• 异常处理必须按程序处理的序而不是时间序

通常，当异常发生时标记它并记录导致异常的原因，保持“安静”直到指令流水到写回阶段再处理，以尽量不影响流水线整体的执行。

对于五级流水线，异常处理的步骤为：

1. 在流水线种保持异常标志知道提交点（W级）

2. 前级的异常优先级>本级的异常优先级。通过硬件MUX实现异常的传递

   

3. 中断的优先级高于异常

4. 异常到达提交点时，更新cause寄存器和EPC寄存器，清空所有流水段（在提交点，之前的指令都已经执行完毕，之后的指令由于异常发生不能执行），向取指令阶段注入处理程序的PC

5. 对于PC段，在异常发生时，注入异常处理程序段的PC值

   • 系统复位时：0xBFC0_0000
   • 硬件中断时：0xBFC0_0400
   • 其他异常时输出：0xBFC0_0380

软件实现的中断服务程序

基本框架结构：保存现场、中断处理、恢复现场、中断返回

• 保存现场：将所有的寄存器数据都保存到堆栈中
• 中断处理：读取特殊寄存器了解具体的中断类型并执行相应的处理策略
• 恢复现场：从堆栈中恢复所有寄存器的值
• 中断返回：执行eret指令，从中断处理程序返回用户程序执行的指令

中断相应机制

保存PC、跳转、关中断，需要在同一周期内完成

• 保存：将PC（实际储存的是PC+4）和ExcCode保存在EPC和cause中
• 跳转：跳转到异常处理程序段
• 关中断：EXL置位，防止再次进入

恢复PC、开中断，需要在一个周期内完成

• 恢复PC：将EPC写入PC
• 开中断：清除EXL，允许再次产生

CP0模块

指令mfc0,mtc0可以读取、写入CP0寄存器，获取相应的信息

MFC0：读取CP0寄存器至通用寄存器

• SR：获取处理器的控制信息
• Cause：获取处理器当前所处的状态
• EPC：获取被异常/中断的指令地址
• PRId：读取处理器ID（可以读取你的个性签名）

MTC0：通用寄存器值写入CP0寄存器

• SR：对处理器进行控制，例如关闭中断
• EPC：操作系统中用于多任务切换

精确异常

流水线的收益来自于指令的叠加，许多异常必须是精确的：

• 在出错之前的指令必须完成
• 出错指令和之后的指令必须消费，不得提交结果
• 异常处理程序必须开始执行

经过封装，使得在程序员看来，CPU是冯诺依曼结构，流水线和单周期不应该有功能上的区别，只应该有速度上的区别。在准备处理异常/中断时，体系结构状态应该是一致的（回收=提交=执行完毕并更新体系结构状态）

1. 所有之前的指令必须完全回收
2. 之后的指令一律不得回收

对于多周期：不是所有指令花费时间相同：如cache缺失等。有多个不同的功能单元，会花费不同数量的时钟周期

• 能够独立的指令在不同的功能单元上，在前序的长延时指令执行完毕之前就开始执行
• 但是这样在指令角度会出现后进入的指令先执行完的情况，在程序员角度是不可接受的

保证精确异常：思路为使每个操作花同样的时间

缺点：访存操作可能不知道花多少时间（cache缺失）

现代CPU简介

现代CPU引入了多种特性，包括分支预测、乱序执行等等，达到了可怕的信念

重排序缓冲

乱序执行指令，在产生体系结构可见状态之前按照PC执行进行重排序。

在指令译码时在ROB中预留一个条目，在指令执行完成后，将结果写入ROB的相应条目。类似队列，当指令成为最旧且执行完的一条，则出队，将结果移动到寄存器或存储器。

寄存器的值可能在寄存器中、数据通路中，也可能在ROB中。在访问数据时，先访问寄存器堆，如果其中数据无效，则寄存器堆存储ROB中包含相应值的条目ID，将寄存器映射到ROB中，再访问ROB

使用ROB的按序执行流水线：

• 译码：访问寄存器堆/ROB，检查指令是否可执行，是则分发指令
• 执行：可以按照完全的乱序执行
• 完成：将结果写入ROB
• 回收/提交：检查异常，如果没有则将结果写入体系结构寄存器/存储器；若有，则清空流水线并启动异常处理程序

按需分发/执行，乱序完成，按需回收

可以较简便地解决精确异常，但是访问ROB会增加延时和复杂性

历史缓冲

指令执行完成后更新寄存器堆，有异常发生时撤销更新

• 译码时保留一个HB条目
• 当指令执行完毕后，将目标地址的旧值存在HB中
• 当指令时HB中最旧的一条且没有发生异常/中断，丢弃该HB条目（和重排序最大的不同）
• 当指令时HB中最旧的一条且有异常需要处理，则将HB中保存的旧值依次写回到体系结构状态

和重排序相比，都是乱序执行，最后根据指令的先后更新体系结构的状态，一个是写（更新）值，用了队的思想；一个是只保留最新的改变，否则利用栈思想复原

好处是寄存器堆中保留有最新的值，访问HB不在关键路径上。坏处是需要读目的寄存器的旧值，在异常时需要回滚HB，增加异常/中断处理的时延。

未来寄存器堆FF+ROB

维护两个寄存器堆：投机的和体系结构的。两个寄存器堆更新寄存器堆的状态的策略不同，一个是最旧，一个是最新

• 体系结构的寄存器堆：按程序序更新以获取精确异常，使用ROB来保证按序更新
  • 用于恢复当异常发生时的状态恢复
• 未来的寄存器堆FF：如果一条指令是最新的一条写入寄存器的指令，则执行完毕后立即更新
  • 可以用来快速访问最近的寄存器值（投机的状态）

好处是不需要从ROB中取值，坏处是使用了多个寄存器堆，发生异常时需要从一个堆向另一个堆复制数据

• 译码(D)：访问FF，在ROB中分配条目，检查指令是否可以执行，是则分发指令
• 执行(E)：指令可以完全的乱序执行
• 完成®：将结果写入ROB和FF
• 回收/提交(W)：检查异常；如果没有，将结果写入体系结构寄存器堆或者存储器；如果有，清空流水线并启动异常处理程序

按序分发/执行，乱序完成，按序回收

当最旧的准备回收的指令被检查出导致了异常, 控制逻辑

• 恢复体系结构状态(寄存器堆, IP/PC, 存储器)
• 清空流水线中所有比该指令新的指令
• 保存IP/PC和寄存器堆(ISA指定)
• 重定向取指引擎指向异常处理子程序
  • 异常向量

存储器和寄存器的区别

• 寄存器的相关是静态可知的– 存储器的相关是动态决定的
• 寄存器的状态空间小– 存储器的状态空间大
• 寄存器状态对其它线程/处理器不可见– 存储器状态在线程/处理器之间是共享的(共享存储多处理器)

乱序执行：动态指令调度

一个真正数据相关会使流水线停止分发（将指令送入功能单元的动作）新的指令到功能单元

取址译码不能停，但有些指令无法执行，乱序执行的思想是找一个指令让指令阻塞在那，独立的指令先在流水线上执行

监控休息区中每条指令的数据来源，当数据可用时，则分发该指令执行，指令按照数据流序（非控制流序）执行