01 基本知识

SISD、SIMD、MIMD、向量处理器的基本概念

向量处理器意思是一条指令可以同时处理多个数据元素（SIMD）（就类似于这几个数据元素组成了一个向量）；多发射处理器可以同一时间并行多条指令。
发射与流出

在计算机体系结构中，”发射”和”流出”是与指令执行有关的两个重要概念，它们描述了处理器在执行指令时的不同阶段和行为。
1. 发射（Issue）：
  - “发射”指的是将指令从指令流中发送到处理器的执行部件或执行单元，以进行实际的执行。
  - 发射阶段通常是在取指令和解码指令之后，将指令发送到执行单元的过程。
  - 多发射处理器意味着多条指令可以同时进入执行阶段，通过并行执行提高处理器的性能。
2. 流出（Out-of-Order Execution）：
  - “流出”是指处理器在执行过程中允许指令乱序执行，即不按照它们在程序中的原始顺序执行。在乱序执行的情况下，处理器会通过重新排序指令来填充执行单元的空闲周期，以提高整体性能。
  - 多流出处理器采用乱序执行的方式，允许在执行单元空闲时执行无关的指令，以最大程度地利用执行单元的并行性。
这两个概念都涉及到提高指令级并行性，但它们描述了处理器在执行阶段的不同方面。发射强调在同一时钟周期内同时发送多条指令，而流出强调在执行过程中的乱序执行策略。
tensor 张量

sparse tensor 稀疏张量
异构计算

指的是在同一系统中集成多种不同体系结构或架构的处理器和计算设备，以便更有效地处理各种类型的任务。这包括集成不同类型的中央处理单元（CPU）、图形处理单元（GPU）、加速器、协处理器等。异构计算的目标是充分发挥各种处理器的优势，以提高整体系统性能和能效。

其关键概念有协处理器等等等。

02 现代处理器体系结构

例题

题型1 生成指令序列，分析时间

1

注意几点：

变量需要通过LD指令载入到寄存器

2

注意，它的意思是LD、SD、DADDIU都只占1个时钟周期，ADD占2个

感觉这么个例题下来，我就懂了循环展开的作用了

题型2 换名/消除WAR WAW

1

2

题型3 记分牌

这里的结构相关值得注意

做这种题的套路是，需要明确它要求的时刻时的情况，并且依照以下规则判断即可：

指令状态表
1. 流出
  
  无结构冲突、无WAW冲突
  
  如① 当MULT准备写回时，此时前两条L必定流出，然后后面的SUB、DIV、ADD都没有结构冲突和WAW冲突，所以全部流出。只不过ADD和DIV会卡在读操作数阶段
  
  ② 由①可知全部流出
2. 读操作数
  
  操作数可用时完成该阶段
  
  如① 此时前三条必定完成。并且SUB也完成了，所以ADD也完成了读数阶段。只有DIV还在等待mul的结果
  
  ② 此时大伙差不多都结了，没什么好说的
3. 执行
  
  纯纯的算术
  
  如① 除了除法别的都完了，没什么好说的
  
  ② 全部都结了
4. 写结果
  
  不存在WAR则写入
  
  如① 前两个肯定完成了，然后SUB也结了，ADD存在WAR，所以最后是ADD和MUL没完成。
  
  ② 除了DIV全部结了
功能部件状态表

记住这些字母的含义即可：
- Busy：yes/no
- Op：操作编码
- Fi：目的寄存器编号
- Fj，Fk：源寄存器编号
- Qj，Qk：正在计算Fj和Fk的功能部件
- Rj，Rk：Fj和Fk是否就绪且还没被取走
寄存器状态表

每个寄存器有一项，用于指出哪个功能部件将把结果写入

题型4 Tomasulo算法

3段流水

流出
1. 没有结构冲突就流出，填进保留站
  
  一般有ADD1，ADD2，ADD3（加减），MUL1，MUL2（乘除），LD1，LD2（SL）
2. 具体填什么看操作数有没有就绪
保留站有以下字段：
- Op：操作
- Qj，Qk：操作数保留站号
- Vj，Vk：源操作数值
  
  load的Vk保存偏移量
- Busy
- A：存放立即数字段 or 有效地址，仅用于load和store缓冲器
- Qi：寄存器状态表
  
  存放要写入它的保留站ID
执行

两个操作数就绪后就执行
写结果

计算完毕后由CDB传送

例题

这里不知道为什么LD2没有跟LD1同时完成？限制了一个时钟周期只流出一条指令吗

这里可以注意其特点是结果一经算出全部写回

通过换名避免了WAR，而不是像记分牌那样通过等待

题型5 Tomasulo+前瞻执行

4段流水

流出
1. 保留站&ROB都有空闲才流出
  
  一般有ADD1，ADD2，ADD3（加减），MUL1，MUL2（乘除），LD1，LD2（SL）
2. 具体填什么看操作数有没有就绪
保留站有以下字段：
- Op：操作
- Qj，Qk：操作数保留站号
- Vj，Vk：源操作数值
  
  load的Vk保存偏移量
- Busy
- A：存放立即数字段 or 有效地址，仅用于load和store缓冲器
- Qi：寄存器状态表
  
  存放要写入它的保留站ID
执行

两个操作数就绪后就执行
写结果
1. 写入ROB，CDB传送ROB编号到保留站
2. 释放产生该结果的保留站
ROB字段：
- 指令类型
- 目标地址
  
  目标寄存器/存储器单元地址
- 数据值字段
  
  前瞻结果
- 就绪字段
  
  结果是否就绪
指令确认

分支结果出来后确认
1. 猜测对写入寄存器/存储器，释放ROB
2. 猜测错从另一条路径开始重新执行，清空ROB

例题

题型6 超标量实现

例题

注意，SD指令的0和R1有了就开始执行，不必等到F4有了再执行。。。

题型7 循环展开

具体步骤：

依题意展开
去除多余的BNE、合并所有DADDUI
寄存器换名消除名相关
重排序消除数据相关

1

2

题型8 VIEW技术

例题

看起来大概可能就有点类似树的概念，什么都不依赖的就放前面，然后依赖1层的依赖2层的之类的

题型9 软流水

例题

指令级并行

概念

开发指令级并行ILP的方法
1. 基于硬件的动态开发
2. 基于软件的静态开发
流水线CPI

实际CPI = 理想CPI + 停顿（结构/数据/控制冲突引起）
理想CPI是衡量流水线最高性能
IPC：每个时钟周期完成的指令数

CPI：每个指令所需时钟周期数
基本程序块：一串没有分支和跳转转入点的指令块

解决冲突的方法之一是序列调度，不过对于跨块的调度（也即jump指令）会有影响

调度

动态调度

基本思想

这里可能意思是引出了多流出，所以会导致DIV和ADD同时流出，从而发生WAW。同理，可能的阻塞也会导致WAR。

记分牌动态调度算法

基本思想

在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令
基本结构

三张表：指令执行状态、功能部件状态、寄存器状态及数据相关关系
1. 指令状态表
  
  记录正在执行的各条指令的状态
2. 功能部件状态表
  
  记录各个功能部件状态，每项有以下字段：
  - Busy：yes/no
  - Op：操作编码
  - Fi：目的寄存器编号
  - Fj，Fk：源寄存器编号
  - Qj，Qk：Fj和Fk的功能部件
  - Rj，Rk：Fj和Fk是否就绪且还没被取走
3. 结果寄存器状态表
  
  每个寄存器有一项，用于指出哪个功能部件将把结果写入
  
  大概是这样的结果：n(寄存器数量) X m(功能部件数量) 的值为0 or 1的矩阵
执行流程

每条指令的执行过程分为4段（只考虑浮点计算）
1. 流出
  
  如果①所需功能部件空闲（结构冲突） ②其他正在执行指令目的寄存器与当前不同（WAW冲突），则流出
2. 读操作数
  
  记分牌监测操作数可用性，可用时通知功能部件从寄存器中读出源操作数开始执行（RAW冲突）
3. 写结果
  
  记分牌监测是否完成执行，若不存在or已消失WAR，则写入；存在，等待
性能分析

Tomasulo算法

核心思想

记录和检测指令相关，操作数一旦就绪立刻执行，把发生RAW的可能减到最小；

通过寄存器换名消除WAR和WAW（上面的记分牌是通过等待）
基本结构
1. 保留站
  
  每个保留一条已经流出并且等待到本功能部件执行的指令的相关信息。包括操作数、操作码以及各种元数据。
  
  故而，需要有以下字段：
  - Op：操作
  - Qj，Qk：操作数保留站号
  - Vj，Vk：源操作数值
    
    load的Vk保存偏移量
  - Busy
  - A：存放立即数字段 or 有效地址，仅用于load和store缓冲器
  - Qi：寄存器状态表
    
    存放把结果写入该寄存器的保留站ID
2. 公共数据总线CDB
  
  用于发送各个功能部件的计算结果。如果具有多个执行部件且采用多流出流水线，则需要采用多条CDB。
3. load缓冲器和store缓冲器
  1. load缓冲器
    1. 存放用于计算有效地址的分量
    2. 记录正在进行的load访存
    3. 保存buffer等待CDB传输
  2. store缓冲器
    1. 存放用于计算有效地址的分量
    2. 记录正在进行的store访存，如目标地址以及是否已有数据
    3. 保存buffer等待CDB传输
4. 浮点寄存器FP
5. 指令队列
  
  FIFO
6. 运算部件
  
  浮点加法器、浮点乘法器
寄存器换名实现

当指令流出，如果操作数缺失，则将指令数据换名为保留站编号
特点
1. 冲突检测与指令执行是分布的
  
  通过保留站和CDB实现
  
  计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，无需经过寄存器
2. 消除了WAW和WAR
执行步骤

3段流水
1. 流出
  
  如果操作要求的保留站空闲（结构冲突），则送到保留站r。如果操作数已就绪，填入；否则，填入产生该操作数的保留站ID（寄存器换名，消除WAW、WAR）。
2. 执行
  
  两个操作数就绪后，就可以用保留站对应功能部件执行
3. 写结果
  
  计算完毕后由CDB传送