计算机体系结构-期末复习
计算机体系结构-期末复习
第一章 量化设计与分析基础
| 1.2.6 并行度与并行体系结构的分类
应用程序中主要有两种并行：
- 数据级并行：同时操作许多数据项实现的并行
- 任务级并行：创建能够单独处理并大量采用并行方式执行的工作任务
所有计算机可以根据指令流及数据流的并行情况划分为：
- SISD(单指令流单数据流)：单处理器，但可以利用指令级并行
- SIMD(单指令流多数据流)：同一指令由多个使用不同数据流的处理器执行，可开发数据级并行
- MISD(多指令流单数据流)：暂时不存在
- MIMD(多指令流多数据流)：每个处理器提取自己的指令，对自己的数据进行操作，针对的是任务级并行
| 1.3 计算机体系结构
见附录A
| 1.4.1 带宽胜过延迟
带宽提升的速度远大于延迟改进的速度
| 1.9 计算机设计的量化原理
计算机设计的三个基本原则：
- 充分利用并行
- 局部性原理
- 重点关注常见情形：Amdahl定律
加速比
=
原执行时间
采用改进后的执行时间
加速比 = frac{原执行时间}{采用改进后的执行时间}
加速比=采用改进后的执行时间原执行时间
新执行时间
=
原执行时间
×
[
(
1
−
升级比例
)
+
升级比例
升级加速比
]
新执行时间 = 原执行时间 times [(1-升级比例)+frac{升级比例}{升级加速比}]
新执行时间=原执行时间×[(1−升级比例)+升级加速比升级比例]
总加速比
=
原执行时间
新执行时间
=
1
(
1
−
升级比例
)
+
升级比例
升级加速比
总加速比 = frac{原执行时间}{新执行时间}=frac{1}{(1-升级比例)+frac{升级比例}{升级加速比}}
总加速比=新执行时间原执行时间=(1−升级比例)+升级加速比升级比例1
第三章 指令级并行
| 3.1 指令级并行
现代处理器通过流水线来实现指令级并行(ILP)，提高性能。流水化处理器的CPI为：
流水线
C
P
I
=
理想流水线
C
P
I
+
结构化冒险停顿
+
数据冒险停顿
+
控制冒险停顿
流水线CPI=理想流水线CPI+结构化冒险停顿+数据冒险停顿+控制冒险停顿
流水线CPI=理想流水线CPI+结构化冒险停顿+数据冒险停顿+控制冒险停顿
停顿的单位是每条指令。主要的ILP技术有：
| 技术 | 降低CPI的哪一部分 | 基于硬件/软件 |
|---|---|---|
| 转发 | 数据冒险停顿 | 硬件 |
| 基本动态调度(记分牌) | 数据冒险停顿 | 硬件 |
| 采用重命名的动态调度(Tomaluso) | 数据冒险停顿 | 硬件 |
| 延迟分支和基本分支预测 | 控制冒险停顿 | 硬件 |
| 动态分支预测 | 控制冒险停顿 | 硬件 |
| 循环展开 | 控制冒险停顿 | 软件 |
| 编译器流水线调度 | 数据冒险停顿 | 软件 |
流水线中最常见的冒险就是数据冒险，数据冒险是由相关性(依赖)导致的，三种相关性：
- 当前指令的操作数是之前指令的结果，真数据依赖，可能导致写后读(RAW)冒险。
- 当前指令的结果写入之前指令的操作数，反依赖，可能导致读后写(WAR)冒险。
- 当前指令和之前指令写入相同位置，输出依赖，可能导致写后写(WAW)冒险。
相关只是指令之间的关系，不一定在流水线中产生冒险，取决于流水线的具体实现结构。
| 3.2 循环展开
循环展开是一种提高指令级并行度的技术，采用循环展开时要进行以下的决策和变换：
- 确认迭代循环不相关，这样循环展开才是有用的
- 使用不同寄存器，避免由于不同运算使用相同寄存器导致的约束(使用多个变量)
- 去除多余的测试和分支指令
- 观察不同迭代的载入和存储指令是否不相关，不引用同一地址，才能进行交换位置的调度
- 对代码进行调度
|循环展开-例
考虑以下代码段：
for(i=999;i>=0;i--){
x[i] = x[i] + s;
}
其相应的RISC-V 64 位指令如下，假设x[i]和s都是浮点数：
Loop:
fld f0,0(x1) #x1是x[999]的地址
fadd.d f4,f0,f2 #f2存储s
fsd f4,0(x1)
addi x1,x1,-8 #双精度浮点数数组，i--相当于地址-8
bne x1,x2,Loop
对于RISC-V流水线，假设浮点运算延迟如下，整型运算延迟为0：
则可得到流水线执行序列：
Loop: fld f0,0(x1)
stall
fadd.d f4,f0,f2
stall
stall
fsd f4,0(x1)
addi x1,x1,-8
bne x1,x2,Loop
以上指令序列的完成需要8个周期，可以通过调度减少一个停顿：
Loop: fld f0,0(x1)
addi x1,x1,-8
fadd.d f4,f0,f2
stall
stall
fsd f4,0(x1)
bne x1,x2,Loop
由于这段代码，迭代之间是不相关的，对这个循环进行四次展开，前三次的分支跳转指令都可以删除，i–可以转变为i=i-4，尽量使用不同寄存器，避免约束，得到新的指令序列为：
Loop: fld f0,0(x1)
fadd.d f4,f0,f2
fsd f4,0(x1)
fld f6,-8(x1)
fadd.d f8,f6,f2
fsd f8,0(x1)
fld f10,-16(x1)
fadd.d f12,f10,f2
fsd f12,-16(x1)
fld f14,-24(x1)
fadd.d f16,f14,f2
fsd f16,-24(x1)
addi x1,x1,-32
bne x1,x2,Loop
载入和运算之间是会有停顿的，运算和存储之间也会有停顿，因此要对这个指令序列进行调度，由于使用了不同的寄存器，载入和载入，运算和运算之间都不会有停顿，因此将其都调度到一起：
Loop: fld f0,0(x1)
fld f6,-8(x1)
fld f10,-16(x1)
fld f14,-24(x1)
fadd.d f4,f0,f2
fadd.d f8,f6,f2
fadd.d f12,f10,f2
fadd.d f16,f14,f2
fsd f4,0(x1)
fsd f8,0(x1)
fsd f12,-16(x1)
fsd f16,-24(x1)
addi x1,x1,-32
bne x1,x2,Loop
现在整个序列都不会有停顿了，14个周期就可以完成这4次循环的计算，平均每个循环3.5个周期，明显比不使用循环展开更快。
| 3.4-3.5 动态调度&Tomasulo算法
动态调度方式更加灵活，允许指令以不同的顺序执行，减少停顿。由硬件重新安排指令的执行，可以允许代码在不同流水线上高效执行，并可以处理编译时不知道的相关性(涉及存储器引用的)，以及缓存缺失等情况。
在附录C中介绍的记分牌算法是一种动态调度算法，允许指令乱序执行。记分牌会在指令的各个阶段分别检查各种数据冒险和结构冒险，通过停顿避免冒险。
Tomasulo算法与记分牌算法采用类似的思想，记录指令的执行状态，检查冒险。不同之处是Tomasulo采用寄存器重命名消除了WAR和WAW这两种假数据依赖，消除了相应的两种数据冒险。并且Tomasulo算法中，一个功能部件有多个缓冲，使用同一个功能单元的指令可以在功能单元被占用时在保留站等待，减少了结构冒险带来的停顿。
Tomasulo算法的实现结构
Tomasolu算法的实现结构如下图：
- FP OP Queue：指令队列，指令从这里发射
- Reservation Stations：保留站，保留已经发射的指令信息和缓冲下来的数据
- Address Unit：地址计算单元，存储指令在执行前会计算存储地址
- Memory Unit：存储单元
- CDB：数据广播总线，直达寄存器堆、保留站，传输数据
保留站、寄存器结果状态表、指令状态表
Tomasulo算法中，指令的执行有三个阶段：发射，执行，写回。指令状态表如下图：
- 指令发射：Tomasulo算法顺序发射指令，判断能否发射的条件是指令对应通路的保留站有空余位置。指令一旦发射，就会占用保留站中的条目，更新保留站和寄存器结果状态表。在发射的同时，会将可以读取到的数据读取到保留站。更新寄存器结果状态表时，总是在表中保留后序指令的最新的写信息，将后序指令写入目的寄存器，前序指令的结果不写入，需要前序指令的值的指令可以直接通过监听CDB来得到数据。
- 执行：源数据就绪后，开始执行，执行器件功能单元被占用。
- 写回：通过CDB总线将数据直通到寄存器堆和各个保留站，并根据寄存器结果状态表来更新寄存器堆，并清除保留站和寄存器结果状态表的信息。
在记分牌中，每一条配置通路只能存放一条指令，Tomasulo算法为每一条通路配置了一组缓冲，对于同一个运算单元，可以缓冲多条指令，在运算单元被占用时，后续指令可以在保留站等待。保留站可以将能读取的数据直接记录在保留站中，并且对于未就绪的数据，只要计算结束就捕捉广播数据，用保留站的编号而不是寄存器编号来标记数据源，从而实现了寄存器重命名。
图2：保留站
和记分牌一样，Tomasulo算法也要记录寄存器结果状态，并记录寄存器更新的数据来源。数据来源选择最新的指令的数据。
Tomasulo算法的缺陷
- 实现复杂
- 要求有高速CDB
- 性能受限于CDB
|Tomasulo算法填表
Tomasulo算法在填表时，要注意操作数直接填写可以读取到的值。并且如果当前周期操作数op在写回，当前周期发射的指令如果需要op，就直接在保留站中读入op，而不是像记分牌那样要下一周期才可以读。写回后(写回的那个周期时刻的表)，寄存器结果状态表也要记录相应的值。与记分牌相同，在指令写回周期，保留站关于这一条指令的信息在填表时就可以删除了。
第五章 线程级并行
|5.4 目录一致性协议与监听一致性协议
多核处理器可能既有共享级别的缓存，又有专用级别的缓存。多个处理器如果共享存储器上的数据，就可能在自己专有的缓存上缓存共享数据，不同的处理器在自己的缓存中可能存有同一数据的不同值，这就是缓存一致性问题。
保证缓存一致性的方式是使用一致性协议，共有两种一致性协议：
- 目录式：将物理存储器块的共享状态保存在一个称为目录的位置
- 监听式：如果一个缓存有一个物理存储器块的副本，则跟踪该块的共享状态。所有缓存都可以通过某种广播介质访问，所有缓存控制器都监听这一介质。
这两种协议都是写入失效协议，处理器执行写入操作时使其他副本失效。
监听一致性协议通常是通过有限状态控制器实施的，控制器可以改变所选缓存块的状态，并使用总线访问数据或使其失效。通过向总线发送信号使其他CPU的该块失效，也通过发送信号告知其他CPU自己发生读写缺失。
目录式一致性协议中，每个处理器都有一个目录，目录中保存了每个可缓存块的状态，信息包括哪些缓存拥有这个块的副本，是否需要更新等等。存储器的每一块都在目录中有对应的一项，每个目录项由访问状态和位向量组成，位向量记录了各个处理器是否有这个块的副本。目录一致性协议不通过广播告知其他处理器一个块失效，而是根据位向量，通知相应的CPU该块失效或完成更新该块的工作。并且由块所在的存储器所属的CPU作为宿主与需要沟通的处理器沟通，完成写失效通知和写回的操作。
两种方法的比较
监听法基于总线，通过广播信号来实现写失效，优点是不需要额外的存储空间维护一致性信息，缺点是可扩展性差，处理器数量越多，总线通信的压力就越大。
目录法采用集中式的目录维护一致性信息，增加了存储开销。但一致性信息是集中式的存储在目录中，目录结构本身是分布式的，因此具有可拓展性。目录法最大的优点是可以实现在分布式的系统中，不需要总线，具有扩展性。
附录A
|A.2 指令集体系结构的分类
根据存储类型分类，有三类指令集体系结构：
- 栈式体系结构
- 累加器式体系结构
- 通用寄存器体系结构：操作数是寄存器或存储器位置
- 寄存器-存储器体系结构：操作数可以是存储器地址，程序规模小，但是会使指令的复杂度不同，完成需要的时钟周期不同
- 载入-存储体系结构(寄存器-寄存器体系结构)：只有载入存储指令可以访存。指令执行所需要的时钟数相似，便于指令的流水化，但是程序规模大
|A.3-A.6 指令集体系结构的特征
- 解释地址&寻址方式：地址有大端法小端法两种表示。对于数据的寻址通常是对齐的。寻址的方式有寄存器寻址，立即数寻址，位移量寻址，直接寻址等。一种体系结构应该至少支持最常用的寄存器间接寻址，位移量寻址和立即数寻址
- 操作数的类型和大小
- 指令集中的操作：一般至少支持算数与逻辑操作，数据传送操作，控制操作，系统操作
- 控制流指令：条件分支，跳转，过程调用，过程返回
- 指令集编码：允许尽可能多的寄存器和寻址方式，并要控制指令长度，希望指令能够便于流水线处理
- 变长编码：允许对所有操作使用所有方式。代码规模重要于性能
- 定长编码：寻址方式与操作数较少时效果好，将操作和寻址方式合并到操作码中。性能重要于代码规模
- 混合编码
|RISC-V体系结构
以RISC-V64G为例，介绍该指令集体系结构的上述特征。
-
寄存器：RV64G有32个64位通用寄存器，还有32个64位的浮点寄存器，以及一些特殊用途的寄存器。
-
操作数：RV64G支持字节，半字，字，双字和单/双精度的浮点。
-
寻址方式：数据寻址的方式只有立即数寻址和偏移量寻址。偏移量为0时实现的即为寄存器间接寻址。RV64G使用64位的地址，小端法存储。访存不需要对齐，不过使用不对齐的访存会很慢。
-
指令集编码：定长编码。相应的汇编格式为OP rd rs1 rs2。
- 操作：载入存储，ALU运算，分支和跳转，浮点操作。
- 控制流指令：分支和跳转指令。
附录B
|B.2 评价缓存性能
缓存性能
评价缓存性能常使用存储器停顿时间：
存储器停顿周期 = 缺失数 x 缺失代价 = IC(指令数) x 存储器访问 / 指令 x 缺失率 x 缺失代价
另外一个度量方式是使用存储器平均访问时间：
存储器平均访问时间 = 命中时间 + 缺失率 x 缺失代价
计算缓存带来的加速比时，可以计算使用缓存和不使用缓存的CPI，然后得到加速比。CPI执行公式只考虑存储器停顿，不使用缓存则缺失率为100%。
缓存考虑的四个问题
- 缓存组织方式：全相联/组相联/直接映射
- 缓存查找：将物理地址划分为TAG|INDEX|BLOCK OFFSET
- 缓存替换策略：随机/LRU(一般只实现伪LRU)/FIFO
- 读写策略：
- 写入：直写/写回。写回的写入速度更快，只需要对缓存进行写入，并且存储器带宽使用较少。直写更容易实现，下一级存储器总是有最新副本，简化了数据一致性。
- 写入缺失：写入分派/无写入分派。写回缓存常采用写入分派，希望后续写入能被缓存捕获，直写缓存常使用无写入分派。
|B.3 评价缓存性能
6种基本的缓存优化方式：
- 增大块大小以降低缺失率：较大的块会降低冷不命中，并且充分利用了空间局部性，但是太大的块会增加缺失代价，增加其他两种缺失。块大小的选择有赖于低级存储器的带宽和延迟，对于高带宽的高延迟存储器，采用大块很少增加缺失代价，鼓励采用大块，若低级处理器是低延迟低带宽的，则鼓励采用小块
- 增大缓存以降低缺失率：可降低容量缺失，缺点是可能延长命中时间，增加成本和功耗
- 提高相联度以降低缺失率：经验规律是采用八路组相联和全相联是一样有效的。但是提高相联度会提高缺失代价
- 采用多级缓存降低缺失代价：使用多级缓存可以加快缓存的速度，同时扩大缓存的容量。为了有效衡量多级缓存的缺失情况，使用局部缺失率(当前缓存级别的缺失率)和全局缺失率(整体缓存的缺失率)。第一级缓存的速度影响处理器的时钟频率，第二级缓存的速度仅影响一级缓存的缺失代价。二级缓存的缺失率更高，因此重心偏向减少缺失，采用更高相联度和更大的块
- 读取缺失的优先级高于写入缺失-降低缺失代价：对写后读问题，如果写入尚未完成，还在写入缓冲区，可以让读取缺失先检查写入缓冲区的内容
- 索引缓存时避免地址转换-降低命中时间：系统可以在缓存中使用虚拟地址，缩短命中时间。由于保证地址空间保护和其他一些原因，一种方案是使用一部分页偏移量来索引缓存，而标志匹配仍采用物理地址，这样就可以在使用索引读取缓存的同时，进行地址的转换。
附录C
|C.1 流水化的基本实现
将指令的执行过程划分为5个周期，在每个周期开始一条新的指令来实现指令的流水化，并采用以下几点：
- 采用分离的指令缓存和数据缓存，避免访存冲突。
- 在时钟周期的前半写寄存器，后半读寄存器。
- 递增程序计数器，并且要计算分支目标地址。
- 在连续的流水级中引入流水线寄存器传递数据，保证各级的数据不会相互干扰。
流水化可以提高CPU指令吞吐量，但不能缩短单条指令执行时间。因为时钟速度必须大于最慢的流水级，并且流水线寄存器引入了延迟。
|C.2 流水化的阻碍-流水线冒险
流水线化的指令执行主要受到流水线冒险的阻碍，包含以下三种冒险，相应的解决方式有：
- 结构冒险：资源冲突导致的冒险。
- 停顿
- 增加硬件(需要衡量是否值得)
- 指令重排序
- 数据冒险：数据相关导致的流水线冒险。
- 转发
- 停顿
- 指令重排序
- 控制冒险：分支指令导致的冒险。
- 基本预测机制：预测选中/未选中，分支延迟，静态分支预测
- 动态分支预测：2位分支预测器
|C.3 流水化的实现
MIPS将分支计算和检测移动到ID阶段，期望减少分支冒险导致的停顿。
如果在ID阶段就完成分支计算，会导致一些数据冒险产生更多停顿，因此RISC-V设计在EX阶段完成分支判断，这样如果没有分支预测，会浪费两条指令，相当于产生两个停顿。RISC-V使用动态分支预测，不使用延迟槽，因为分支延迟并不总是可行，并且分支判断在EX阶段完成，在ID阶段根据预测的结果进行跳转，EX阶段进行验证。
|C.7 基本动态调度-记分牌
动态调度流水线中，指令按序发射，乱序执行，实现方式是使用记分牌。记分牌全面负责指令发射与执行，包括所有冒险检测任务。乱序执行会导致原来顺序执行流水线中不存在的WAR和WAW冒险出现，这些冒险都由记分牌来检测和处理。每条指令都会进入记分牌，有一条记录，记分牌会判断什么时候能读取操作数并执行，还会控制指令什么时候能写回目标寄存器。每个功能部件在记分牌中有一条数据通路(一个记录的位置)。
指令在流水线中完成有四个步骤：
- 发射：如果指令的一个功能单元空闲，没有其他活动指令以同一寄存器为目标寄存器，则向功能单元发射指令。如果存在WAW冒险或结构冒险，则指令发射停顿。
- 读取操作数：记分牌监视源操作数的可用性，如果先前发射的指令都不写入源操作数，则该源操作数可用，这一步解决了RAW冒险。
- 执行：功能单元收到操作数后开始执行，结果就绪后，通知记分牌已经完成了执行。
- 写结果：记分牌知道了功能单元完成执行，则检查WAR冒险，并在必要时停止正在完成的指令。
记分牌有三个部分：
- 指令状态：指出该指令处于四个步骤中的哪一步
- 功能单元状态：指出功能单元的状态，Fj和Fk为源寄存器编号，Fi为目标寄存器，Qj，Qk为生成源寄存器的功能单元，Rj和Rk表示操作数是否已准备就绪
- 寄存器结果状态：指出哪个功能单元将写入哪个寄存器，写入完成后字段为空
|记分牌填表
填表时，在指令读取阶段，Rj，Rk仍为准备好读取的状态，进入执行阶段后，设置为已读取。进入写回阶段时，记分牌中该指令的功能单元状态表，寄存器结果状态表的相应位置清空(但使用该功能部件的下一条指令还不能在这一周期就发射，尽管在表中这一条目是空的)，同时需要读取该部件的操作数的指令的Qj，Qk也清空，Rj，Rk转为YES状态，表示准备好可以读取，但是要下一时刻才可以读取。填表的时候要注意，clki的表中是clki结束时的状态，所以不能一个指令写回时清空了功能单元状态，下一个使用该功能单元的指令在同一个周期就发射。
如下图例，第一条LD在clk4就写回了，此时Integer部件条目已经空了，但是下一条LD在clk4不能发射，因为clk4第一条LD写回，并清空条目是这一周期发生的事情。
此外，指令在写回前一定要检查是否存在WAR冒险，如下图例：