计算机系统结构复习笔记 - 第四、五、六章

转载自 BakaNetwork/ComputerArchitecture - GitHub，有少量修改。

• 向量处理机
• 指令级并行及其开发

第四章 向量处理机

重点

向量处理方法：横向处理、纵向处理、纵横处理

向量流水处理机结构：

• 存储器-存储器结构：纵向处理
• 寄存器-寄存器结构：纵横处理

提高向量处理机性能的方法：

• 多功能部件的并行操作
• 链接技术 WD 相关
• 分段开采
• 多处理机系统结构

向量处理机性能的主要参数：

• 一条向量指令的处理时间
• 一组向量指令的处理时间
• 向量处理机的性能评估（MFLOPS 或一个浮点运算的时间）

向量基本概念和处理方法

向量处理机：设置了向量数据表示和向量指令的流水线处理机。

向量处理机方式：

• 横向处理方式：向量按 column 的方式从左到右横向进行。适用于一般处理机，不适用于向量处理机的并行处理。
• 纵向处理方式：向量按 row 的方式从上到下纵向进行。将整个向量按相同运算处理完之后，再进行别的运算。不产生数据相关，对向量长度 N 没有限制。
• 纵横处理方式：把向量分成若干组，组内按纵向方式处理，依次处理各组。对向量长度 N 没有限制，但以每 n 个元素分一组处理，n 的值固定。

向量处理机结构

存储器-存储器结构：适合纵向处理方式。

• 源向量和目的向量都存放在存储器中，运算的中间结果需要送回存储器。
• 对应的向量分量能并发访问，计算结果能并行地保存。
• 普通存储器的 3 倍带宽：3 条独立数据通路，一个时钟周期读出两个操作数并写回一个结果。

寄存器-寄存器结构：适合纵横处理方式。

• 若干级中间存储器形成有层次结构的存储系统，相当于寄存器。
• 访问中间存储器速度更快。
• 通过中间存储器形成新的数据结构，高效。
• 中间存储器高带宽、多种寻址方式、支持流水线链接技术。

向量流水线并行条件：

• 功能部件不冲突
• 源寄存器不冲突
• 结果寄存器不冲突
• 数据不相关

提高向量流水处理机性能

• 设置多个功能部件并行
• 链接技术：向量运算输出可直接作为输入使用，结果寄存器立即成为后继指令操作数寄存器。是定向技术的发展，利用 RAW 数据相关性。数据进（出）每个功能部件需 1 个时钟周期。
• 分段（循环）开采：向量长度大于向量寄存器长度时，对向量进行分段处理，系统完成，对程序员透明。
• 多处理机

链接技术：

• 链接条件：

  • 空间：无向量寄存器、功能部件冲突
  • 时间：
    • 仅上一指令的第 1 个结果分量送入结果向量寄存器的时钟周期可链接。
    • 若后一指令源操作数分别是前两指令的结果寄存器，前两指令产生结果时间必须相等。向量长度必须相等。

• 链接运算时间：

  例题

  

  

  （其实应该是 24+64-1）

  

  

  

  

  

• 分段开采技术：当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。

向量处理机性能评价

向量处理指令特点：

• 一条指令得到若干运算结果。
• 执行时间与向量长度有关。
• 向量处理中包含标量指令。
• CPI、MIPS 不能反映向量处理性能。

向量处理机性能参数：

• 向量指令处理时间：

  • 一条向量指令执行时间：\(T_{vp} = (T_{start}+n) T_c\)，\(T_{start}\) 为从第一条指令开始执行，到还差一个时钟周期就产生第一个结果所需时钟周期数，\(T_c\) 为流水线时钟周期时间。

    例题

    

    

  • 一组向量指令总执行时间：把能在同一个时钟周期内一起开始执行的几条向量称为一个编队。同一个编队中的向量指令之间一定不存在流水功能部件的冲突或数据相关性。\(T_{all} = (T_{start} + mn) T_c\)，\(\space T_{start} = \sum_{i=1}^m T_{start}^{(i)}\) 为总的启动时间，\(T_{start}^{(i)}\) 为第 \(i\) 编队中最大的启动时间，\(m\) 为编队个数，\(n\) 为向量长度。

    例题

    

  • 分段开采时：\(T_{all}=\lceil \frac n{MVL}\rceil \times (T_{start}+T_{loop}) + mn\)， \(T_{loop}\) 为循环所引入的额外时间，\(MVL\) 为向量寄存器长度。

    例题

    

    

    在链接的时候，编队的含义就不是并行了，而是编队内的指令可以连接。

    

    

    链接执行（两个编队，LV 和 SV 部件冲突）：\(T=4\times(15+31)+2\times 200=584\)

• 向量流水线最大性能 \(R_\infty\)：\(\lim\limits_{n \to \infty} \frac{向量指令序列中浮点运算次数 \times 时钟频率}{向量指令序列执行所需时钟周期数}\)

  例题

  

  

  

• 半性能向量长度 \(n_{1/2}\) ：向量处理机性能为其 \(R_\infty\) 一半时所需向量长度。与流水线建立时间有关。

  例题

  

• 向量长度临界值 \(n_v\) ：向量流水方式的处理速度优于标量串行方式的处理速度时，向量长度的临界值。

  例题

  

  

第五章 指令级并行及其开发——硬件方法

重点

指令集并行基础概念

指令的动态调度技术（硬件方法）：

• 乱序执行调度的概念
• 记分牌算法
• Tomasulo 算法
• 基于硬件的前瞻执行

动态分支预测技术：

• 分支历史表 BHT
• 分支目标缓冲器 BTB

多流出技术：超标量、超流水、VLIW、静态指令调度

指令集并行基础概念

指令集并行（ILP）是指令间存在的一种并行性，使计算机可以并行执行两条及以上的指令。

开发 ILP 的途径：① 资源重复（重复设置多个部件同时执行多条指令）② 采用流水线技术使指令重叠并行执行。

开发 ILP 的方法：分为硬件方法和软件方法。本章为硬件方法。

流水线处理机的实际 CPI：\(CPI_{流水线} = CPI_{理想}+停顿_{结构冲突}+停顿_{数据冲突}+停顿_{控制冲突}\)。减少停顿以提高降低 CPI、提高 IPC。

基本程序块：一串连续的代码除了入口和出口之外，没有其他的分支指令和转入点。

循环并行性：循环的不同迭代之间存在的并行性。

相关与指令级并行（概念）：

• 程序顺序：由原来程序确定的在完全串行方式下指令的执行顺序。我们需要尽可能地开发并行性，只有在可能导致错误的情况下，才保持程序顺序。
• 保持异常行为：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。实际使用中：指令执行顺序的改变不导致程序中发生新的异常。
• 数据流：数据值从其产生者指令，到其消费者指令的实际流动。分支指令使得数据流有动态性，分支指令的执行结果决定哪条指令才是所需数据的产生者。 之后讨论的前瞻执行不仅解决异常问题，还能在保持数据流的情况下减少控制相关对开发 ILP 的影响。

指令的动态调度技术（硬件方法）

静态调度：在编译期间，把相关的指令拉开距离来减少可能产生的停顿。

动态调度：能在保持数据流和异常行为的情况下，通过硬件对指令执行顺序重排，减少数据相关导致的停顿：

• 优点：① 能处理编译时情况不明的相关（如存储器访问相关），并简化编译器。② 使同一段代码能在不同流水线上高效地执行。
• 代价：硬件复杂性显著增加。

动态调度基本思想：

• 将流水线的 ID 段分为“IS 流出”、“RO 读操作数”两个阶段。这样使得指令乱序执行，指令的完成也是乱序完成。
• 乱序执行带来新问题：
  • WAR 冲突和 WAW 冲突。
  • 异常处理复杂化。不精确异常：异常时处理机现场与严格按程序顺序执行时现场不同。不精确异常使得异常处理后难以继续执行原有程序。产生不精确异常的原因：当指令 a 导致异常发生时，流水线已经执行程序顺序是 a 之后的指令，还没完成程序顺序是 a 之前的指令。

典型动态调度算法：记分牌算法、Tomasulo 算法。主要考虑的因素：资源（结构）利用效率、三种数据相关。

记分牌算法

记分牌的目标：在没有结构冲突时，尽早执行没有数据冲突的指令。

指令执行的步骤：每条指令的执行过程分为 4 段——IS 流出、RO 读操作数、EX 执行、WB 写结果。（主要考虑浮点操作，运算在浮点寄存器之间进行，不涉及 MEM 段）

• 流出：若流出指令所需的功能部件空闲，并且所有其他执行中的指令的目的寄存器与该指令不同，记分牌就向功能部件流出该指令，并修改记分牌内部的记录表。如果存在结构相关或 WAW 冲突，则该指令不流出。（在流出段解决了 WAW 冲突）
• 读操作数：记分牌检测源操作数的可用性。一旦数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行。否则就等待写完成之后再读出（锁定）（读操作数段动态地解决了 RAW 冲突，并可能导致指令乱序执行）
• 执行：取到操作数后，功能部件开始执行。结果产生后，通知记分牌它已完成执行。这一步相当于五段流水线中的 EX。但在浮点流水线中，这一段可能占用多个时钟周期。其他指令如果不与正在执行或被锁定指令相关，可提前执行或完成。
• 写结果：记分牌知道执行部件完成执行后，检测是否存在 WAR 冲突（前面某条指令的源操作数寄存器，是本指令的目标寄存器）。如果不存在（或已有的 WAR 冲突已消失），记分牌就通知功能部件把结果写入目的寄存器，并释放该指令执行所用的所有资源。否则必须等待。这一步对应五段流水线的 WB。

记分牌记录信息的组成：

• 指令状态表：记录正在执行的各条指令已经进入哪一段。
• 功能部件状态表：记录各个功能部件的状态。每个功能部件有 1 项，每项由 9 个字段组成。
  • Busy：忙标志，功能部件是否正忙。
  • Op：正在或将要执行的操作。
  • \(F_i\)：目的寄存器编号，\(F_j,F_k\)：源寄存器编号。（按指令中的顺序排列）
  • \(Q_j,Q_k\)：向源寄存器 \(F_j/F_k\) 写数据的功能部件。
  • \(R_j,R_k\)：源寄存器标志位，“yes”表示 \(F_j/F_k\) 的操作数可用——就绪且未被取走（产生且未读）。否则“no”。
• 结果寄存器状态表：每个寄存器在该表中有一项，用于指出哪个功能部件（编号）将把结果写入该寄存器。如果正运行的指令全都不以它为目的寄存器，则设置为“no”或 0。

例题

记分牌算法的冲突分析：

• WAW 冲突会导致记分牌在流出阶段停顿。

• WAR 冲突会导致记分牌在写结果阶段停顿。

• 真相关引起的 RAW 冲突会导致记分牌在读操作数阶段停顿。

• 资源冲突会导致记分牌在流出阶段停顿。

Tomasulo 算法

又称公共数据总线法。通过分散控制，处理数据相关和乱序执行。

基于 Tomasulo 算法的 MIPS 处理器浮点部件主要结构：

• 指令队列：存放部件送来的指令，FIFO、顺序流出。
• 保留站：保存流出到本功能部件执行的指令信息（包括操作码、操作数、解决冲突的信息）。每个保留站有一个标识字段，唯一地标识了该保留站。
• 访存部件缓冲器：load 缓冲器和 store 缓冲器存放读/写存储器的数据或地址（类似保留站）。
• 公共数据总线 CDB：重要的数据通路。所有计算结果都送到 CDB，它直接播送到各个需要的地方。多个执行部件且采用多流出的流水线中有多条 CDB。计算结果先送到 CDB 再传送到功能部件，不需要经过寄存器。
• 浮点寄存器 FP：通过总线连接到各功能部件，通过 CDB 连接到 store 缓冲器。
• 运算部件：浮点加法器和浮点乘法器。

核心思想：

• 记录和检测指令相关，把发生 RAW 冲突的可能性减到最小。
• 通过寄存器换名技术消除 WAR 冲突和 WAW 冲突：寄存器换名通过保留站和流出逻辑共同完成。当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。当指令流出到保留站之后，其操作数寄存器号要么换成了数据本身（已就绪状态），要么换成了保留站标识，而不再与寄存器相关。这样消除了 WAR 冲突。

指令执行的步骤：三步。

• 流出：从指令队列头部取指。如果该指令操作所要求的的保留站有空闲的，则把该指令送到该空闲保留站（设为 r）。如果操作数未就绪，则进行寄存器换名。另外，进行目的寄存器预约，将其设置为接收保留站 r 的结果（相当于提前完成了写操作）。由于指令顺序流出，同一个结果寄存器的预约结果肯定是最后一条指令的，消除了 WAW 冲突。如果没有空闲保留站，指令不能留出（发生结构冲突）。
• 执行：如果某个操作数未被计算出来，保留站监视 CDB，结果产生保留站立刻从 CDB 获取数据。操作数都就绪后保留站用相应的功能部件开始执行指令操作。（靠推迟执行的方法解决 RAW 冲突）load 指令执行条件是存储器部件就绪，而 store 指令执行的条件是要存入存储器的数据到达并且存储器部件就绪。
• 写结果：功能部件计算完毕后将结果放到 CDB 上，等待该结果的寄存器和保留站同时从 CDB 获取数据。

保留站字段：

• Op：对源操作数进行的操作。
• \(Q_j,Q_k\)：将产生源操作数的保留站号。0 表示操作数已就绪且在 \(V_j/V_k\) 中，或者不需要操作数。
• \(V_j,V_k\)：源操作数的值，如Reg[F4]​。对于每一个操作数来说，V 或 Q 字段只有一个有效。
• Busy：“yes”表示本保留站或缓冲单元正忙。
• A：仅 load 和 store 缓冲器有该字段。开始先存放指令中的立即数字段，地址计算后存放有效地址。

例题

Tomasulo 算法的优点：

• 冲突检测逻辑和指令执行控制是分布的（通过保留站和 CDB 实现）。
• 通过寄存器换名和预约，消除了 WAW 冲突和 WAR 冲突导致的停顿。
• 通过延迟执行解决 RAW 冲突。
• 保留站、寄存器组均有附加信息，用于检测和消除冲突。

动态分支预测技术

开发的 ILP 越多，控制相关的制约就越大：① 在 \(n\) 流出（每个时钟周期流出 \(n\) 条指令）处理机中，遇到分支指令的可能性增加 \(n\) 倍。② 根据 Amdahl 定律，机器 CPI 越小，控制停顿的相对影响越大。

动态分支预测技术目的：① 预测分支是否成功。② 尽快找到分支目标地址或指令。

动态分支预测技术需要解决的问题：① 如何记录分支的历史信息。② 如何根据这些信息预测分支去向，甚至提前取出分支目标指令。

分支历史表 BHT

记录分支指令最近几次的执行情况（成功或失败），并据此预测。使用两个 bit 存储历史分支信息。

BHT 两个步骤：

• 分支预测：当分支指令到达 ID 时，从 BHT 读出的信息进行分支预测。若正确就继续处理后续指令。若错误就作废预取指令，恢复现场，并从另一条分支路径重新取指。
• 状态修改：修改 BHT 状态。

分支目标缓冲器 BTB

分支目标缓冲器 Branch-Target Buffer 作用：

• 将分支成功的分支指令的地址，和它的分支目标地址都放到一个缓冲区中保存。
• 缓冲区以分支指令的地址作为标识，得到转移目标指令地址信息。
• 在 IF 段访问 BTB，将分支的开销降为 0。

（延迟两个周期：预测失败需要更新 BTB 的项，花费 1 个周期。对 BTB 项进行更改时需要停止取值，又花费 1 个周期）

例题

基于硬件的前瞻执行*

基本思想：对分支结果预测，按预测结果继续取指、流出、执行后续指令，但结果不写回寄存区或存储器，而是写入再定序缓冲器 ROB，等到指令“确认”之后再写回寄存器或存储器。

基于硬件的前瞻执行结合了 3 种思想：

• 动态分支预测。用来选择后续执行的指令。
• 在控制相关的结果尚未出来之前，前瞻地执行后续指令。
• 用动态调度对基本块的各种组合进行跨基本块的调度。

把 Tomasulo 算法的写结果和指令完成加以区分，分成两个不同的段：写结果，指令确认。

允许指令乱序执行，但必须顺序确认。在指令被确认之前，不允许它进行不可恢复的操作。

ROB 中的每一项由以下 4 个字段组成：

• 指令类型：指出该指令是分支指令、store 指令或寄存器操作指令。
• 目标地址：给出指令执行结果应写入的目标寄存器号（如果是 load 和 ALU 指令）或存储器单元的地址（如果是 store 指令）。
• 数据值字段：用来保存指令前瞻执行的结果，直到指令得到确认。
• 就绪字段：指出指令是否已经完成执行并且数据已就绪。

指令执行的步骤：四步。

• 流出：从浮点指令队列的头部取一条指令。如果有空闲的保留站（设为 r）且有空闲的 ROB 项（设为 b），就流出该指令，并把相应的信息放入保留站 r 和 ROB 项 b。如果保留站或 ROB 全满，便停止流出指令，直到它们都有空闲的项 。

• 执行：如果有操作数尚未就绪，就等待，并不断地监测 CDB（检测 RAW 冲突）。当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。

• 写结果：当结果产生后，将该结果连同本指令在流出段所分配到的 ROB 项的编号放到 CDB 上，经 CDB 写到 ROB 以及所有等待该结果的保留站。释放产生该结果的保留站。

  store 指令在本阶段完成，其操作为：

  • 如果要写入存储器的数据已经就绪，就把该数据写入分配给该 store 指令的 ROB 项。
  • 否则，就监测 CDB，直到那个数据在 CDB 上播送出来，才将之写入分配给该 store 指令的 ROB 项。

• 确认：对分支指令、store 指令以及其它指令的处理不同：

  • 其它指令（除分支指令和 store 指令）：当该指令到达 ROB 队列的头部而且其结果已经就绪时，就把该结果写入该指令的目的寄存器，并从 ROB 中删除该指令。
  • store 指令处理与上面的类似，只是它把结果写入存储器。
  • 分支指令：当预测错误的分支指令到达 ROB 队列的头部时，清空 ROB，并从分支指令的另一个分支重新开始执行。当预测正确的分支指令到达 ROB 队列的头部时，该指令执行完毕。

例题

前瞻执行的特点：

• 通过 ROB 实现了指令的顺序完成。
• 能够实现精确异常。
• 很容易地推广到整数寄存器和整数功能单元上。
• 主要缺点：所需的硬件太复杂。

多流出技术

一个时钟周期内流水线流出指令条数称为 ILP。

在每个时钟周期内流出多条指令，CPI<1。

两种多流出处理机：

• 超标量：
  • 每个时钟周期流出的指令条数不固定，但有上限 n。这种处理机称为 n 流出（n 发射）处理机。
  • 可以通过编译器静态调度，也可以基于 Tomasulo 算法进行动态调度。
• 超长指令字 VLIW（Very Long Instruction Word）：
  • 单一的流或控制器：在每个周期流出指令条数固定，这些指令构成一个长指令（指令包），通常大于 100 位。
  • 指令包中的指令之间并行性通过指令显式地表示出来。
  • 大量的数据通路和功能部件：设置多个功能部件。
  • 超长指令字包含多个控制字段：指令字被分割成一些字段，每个字段称为一个操作槽，直接独立控制一个功能部件。
  • 超长指令字的生成由编译器完成：指令调度由编译器静态完成，流出时无需复杂冲突检测。

静态调度的多流出技术：

• 每个时钟周期流出 n 条指令。称为流出包。
• 指令按序流出，在流出时由流出部件进行冲突检测：
  • 第一阶段：进行流出包内的冲突检测，选出初步判定可以流出的指令。
  • 第二阶段：检测选出的指令与正在执行的指令是否冲突。

超流水线处理机：每 1/n 个时钟周期流出一条指令。

例题

第六章 指令级并行及其开发——软件方法

基本指令调度和循环展开

例题

循环展开：把循环体的代码复制多次并按顺序排放，然后相应调整循环的结束条件。

例题

跨越基本块的静态指令调度

全局指令调度：

• 目标：在保持原有数据相关和控制相关不变的前提下，尽可能地缩短包含分支结构的代码段的总执行时间。
• 基本思想：在循环体内的多个基本块间移动指令，扩大那些执行频率较高的基本块的体积。

踪迹调度：

• 踪迹 (trace)：程序执行的指令序列，通常由一个或多个基本块组成，trace 内可以有分支，但一定不能包含循环。
• 踪迹调度会优化执行频率高的 trace，减少其执行开销。由于需要添加补偿代码以确保正确性，那些执行频率较低的 trace 的开销反而会有所增加。
• 步骤：踪迹选择和踪迹压缩
  • 踪迹选择：从程序的控制流图中选择执行频率较高的路径，每条路径就是一条 trace。处理转移成功与失败概率相差较大的情况；循环结构：循环展开；分支结构：根据典型输入集下的运行统计信息。
  • 踪迹压缩：对已生成的 trace 进行指令调度和优化，尽可能地缩短其执行时间；跨越 trace 内部的入口或出口调度指令时必须非常小心，有时还需要增加补偿代码。
• 超块调度：超块是只能拥有一个入口，但可以拥有多个出口的结构。通过尾复制技术构造。