Computer Architecture: A Quantitative Approach¶

第一章 量化设计与分析基础¶

1.5 集成电路中功率和能量的趋势¶

系统设计者考虑三个问题：

• 处理器需要的最大功率是多少？如果供电系统不能满足峰值功率需求，往往会导致电压下降，设备无法正常工作。
• 持续的功率是多少？一般称为 TDP（Thermal Design Power），通常比峰值功耗低，比平均功耗高。一般系统的供电和散热系统都和 TDP 相匹配。

• 能耗和能耗效率。通常以能耗而不是功率作为指标，不论是 PC 还是云服务场景。

  Exmaple

  处理器 A 比 B 功率高 \(20%\)，但只需要 \(70%\) 的时间来完成任务。对于一个相同的任务，A 的能耗为 \(1.2 \times 0.7 = 0.84\)，比 B 少。

处理器内的能耗分为两种：

• 动态能耗（dynamic energy）：切换晶体管开关消耗的能量 \(E_{\text{dynamic}} \propto C \times V^2\)，与电容负载和电压有关。20 年来，处理器的电压从 5V 降到 1V，正是为了降低动态能耗。
• 静态能耗（static energy）：晶体管漏电流消耗的能量 \(E_{\text{static}} \propto I \times V\)，随着晶体管数量的增加而增加。比如一些高性能芯片中使用大量的 SRAM 缓存，将显著增加静态能耗。

1.7 可靠性¶

基础设施服务商提供 SLA（Service Level Agreement）或者 SLO（Service Level Objective）来保证服务的可靠性。在 SLA 中，系统在 Service Accomplishment 和 Service Interruption 两个状态间切换，切换的原因分别为 failure 和 restoration。相应地定义了一下可靠性指标：

• 可靠性指标：

  • MTTF（Mean Time To Failure）：正常运行的平均时间
  • FIT（Failure In Time）：每 \(10^9\) 小时的故障次数

  上面两个指标互为倒数。比如，MTTF 为 \(10^6\) 小时，则 FIT 为 \(\frac{10^9}{10^6} = 10^3\)。

  • MTTR（Mean Time To Repair）
  • MTBF（Mean Time Between Failure）= MTTF + MTTR
  • 可用性指标：
  \[ \text{Availability} = \frac{\text{MTTF}}{\text{MTTF} + \text{MTTR}} \]

要计算多个子系统组成的系统的可靠性（MTTF），一般先计算每个子系统的 FIT，相加得到整个系统的 FIT，取倒数即为 MTTF。

第三章 指令级并行及其利用¶

技术及其总结：TODO

3.1 指令级并行：概念与挑战¶

什么是 ILP（Instruction-Level Parallelism）？¶

• 基本块（basic block）：一段代码，除入口外没有其他转入分支，除出口外没有其他转出分支。

basic block 中的并行度很小，因为这些指令之间的依赖程度比较高。需要跨越多个 basic block 利用 ILP。循环级并行是最简单的 ILP。

• 循环级并行（Loop-Level Parallelism）：一些简单的循环如 x[i] = x[i] + y[i] 的每次迭代之间没有依赖关系，可以并行执行。可以通过编译器静态展开循环或利用硬件动态展开循环。替代方法还有使用向量处理器（第四章）。

数据依赖与冒险¶

判断指令间的依赖关系：

• 数据依赖（真依赖）：指令 \(i\) 的结果被指令 \(j\) 使用，或指令之间存在依赖链。
  • 两种方法：保持依赖但避免冒险（通过调度，可以由硬件或软件完成），通过转换代码来消除依赖。

• 名称依赖：两条指令使用相同的寄存器或内存地址（称为名称），在该名称上没有数据流动时。

  假设指令 \(i\) 位于指令 \(j\) 之前：

  • \(j\) 对 \(i\) 读取的名称执行写操作时，称为反依赖（antidependence）
  • \(i\) 和 \(j\) 都对相同的名称执行写操作时，称为输出依赖（output dependence）

  这两种情况都必须保证指令执行的顺序。但是由于不是真依赖，所以只需要改变这些指令使用的名称，就不再冲突，这些指令可以重排或同时执行。

• 数据冒险：假设指令 \(i\) 位于指令 \(j\) 之前，\(j\) 可能发生的冒险有：

  • RAW 写后读：\(j\) 必须在 \(i\) 写入之后读取，对应真依赖。
  • WAW 写后写：\(j\) 必须在 \(i\) 写入之后写入，对应输出依赖。
  • WAR 读后写：\(j\) 必须在 \(i\) 读取之后写入，对应反依赖。对于大多数流水线，所有读操作都比写操作早一些，所以不会发生 WAR。
  • 没有 RAR 冒险。

控制依赖¶

• 控制依赖：控制依赖并不是一个必须保持的关键特性。在不影响程序正确执行的情况下，可以执行一些还不应当执行的指令。

  • 通常要求保护异常行为，即改变指令的执行顺序不得导致程序引发任何新异常。

    比如：

        add x2, x3, x4
        beq x2, x0, L1
        ld  x1, 0(x2)
    L1:
    

    beq 和 ld 之间没有数据依赖，只有控制依赖。可以调换这两条指令的顺序，但是可能导致 ld 触发异常（段错误）。可能需要在执行分支操作时忽略该异常。投机执行（speculation）可以解决这一异常。

3.1 动态调度¶

顺序发射和执行的最大问题在于：如果当前指令 stall，那么后续指令都无法继续。在硬件具有多个功能单元（Functional Unit，FU）的情况下，其他功能单元可能空闲。我们可以通过动态调度将其利用起来。

与前文编译器执行的静态调度相比：

• 静态调度通过隔离相互依赖的指令，尝试尽可能消除 stall。
• 动态调度尝试在依赖存在时，通过调度抵消 stall。

fadd.d  f6, f0, f8
fsub.d  f8, f10, f14
fmul.d  f6, f10, f8

fadd.d  f6, f0, f8
fsub.d  S, f10, f14
fmul.d  f6, f10, S

与 scoreboard 相比，Tomasulo 使用重命名解决了反依赖和输出依赖，并且可以改进实现后文将介绍的投机执行。

3.2 利用 ILP 的基本编译器技术¶

基本流水线调度和循环展开¶

为了避免 stall，相关指令要在流水线中拉开距离。编译器根据流水线中可用的功能单元（Functional Unit）来执行调度。

for (i = 999; i >= 0; i = i-1)
    x[i] = x[i] + s;

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

Loop:   fld     f0, 0(x1)
        addi    x1, x1, -8
        fadd.d  f4, f0, f2
        stall
        stall
        fsd     f4, 8(x1)
        bne     x1, x2, Loop

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, -8(x1)
        fld     f0, -16(x1)
        fadd.d  f12, f0, 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     f0, -16(x1)
        fld     f14, -24(x1)
        fadd.d  f4, f0, f2
        fadd.d  f8, f6, f2
        fadd.d  f12, f0, f2
        fadd.d  f16, f14, f2
        fsd     f4, 0(x1)
        fsd     f8, -8(x1)
        fsd     f12, -16(x1)
        fsd     f16, -24(x1)
        addi    x1, x1, -32
        bne     x1, x2, Loop

循环展开和调度总结¶

• 确保循环迭代是独立的，没有依赖关系。
• 使用不同的寄存器避免名称依赖。
• 调整循环测试、跳转指令。

此外有一些限制因素需要考虑：

• 展开得越多，效果逐渐减弱。
• 代码体积增加，需要考虑 I-cache 的影响。
• 造成寄存器压力，需要考虑寄存器分配。

3.2 分支预测¶

对于分支跳转指令，PC 在分支指令的 ID 阶段末尾确定，此时完成地址计算和比较。在此之前，我们需要预测分支的结果，以便在 IF 阶段就开始取指。

if (aa == 2)
    aa = 0;
if (bb == 2)
    bb = 0;
if (aa != bb)

上面几个重要的分支预测技术示意图如下：

3.3 基于硬件的投机执行¶

本讲内容对应书本 3.6 节

对于宽发射（wide-issue）处理器来说，分支预测、动态调度仍不足以充分利用 ILP，可能每个周期都需要执行分支指令，这就需要投机执行（speculative execution）。

在使用分支预测和动态调度时，我们总是假设分支预测是正确的，从而进行取指和发射。这样做只能部分地将基本块重叠，还需要等待分支结果才能执行下一基本块。投机执行在此之上更进一步，将分支预测推入执行阶段。

为了实现提交步骤，需要添加 reorder buffer（ROB）用于存放完成执行但没有提交的指令的结果，并起到 bypass 的作用。

第四章 向量、SIMD 和 GPU 体系结构中的数据级并行¶

4.1 向量体系结构¶

核心优化原理：单次向量访存操作产生的较长的延迟分散到多个元素上。

这种设计的能量要求和复杂度不会增加太多，同时能提高简单标量处理器的性能。

第五章 线程级并行¶

5.1 多处理器¶

• 费林分类法（Flynn's Taxonomy）对计算模式做分类：
  • SISD：单指令单数据流，传统的单处理器
  • MISD：多指令单数据流，很少见
  • SIMD：单指令多数据流，如向量处理器（第四章）
  • MIMD：多指令多数据流，多处理器系统（本章内容）

多处理器架构主要根据主存的组织方式分类。关心的问题有两个：

• 物理上是否集中：所有处理器对所有内存的访存延迟是否一致？
• 逻辑上是否共享：所有处理器是否都能透明地访问所有内存？

这两个维度是正交的。比如 DSM（Distributed Shared Memory）系统指物理上分布式内存，但逻辑上是共享内存。

• 物理上集中：SMP（Symmetric Multiprocessor）/UMA（Uniform Memory Access）。

  UMA 理论上很美好，但在现实中受到内存总线带宽的限制。随着系统规模的增加，延迟也会增加。因此 UMA 只适用于小规模 SMP，难以扩展。

• 物理上分布：NUMA（Non-Uniform Memory Access）

  • 逻辑上共享：DSM（Distributed Shared Memory）。

  • 逻辑上分布：由多个独立私有的地址空间组成，处理器不能直接访问远端内存。

    一般指集群，需要使用消息传递（Message Passing）进行通信。

并行编程范式梳理如下：

• 编程模型：
  • 多道程序设计（Multiprogramming）：任务之间没有通信。
  • 共享内存空间（Shared Memory）
  • 消息传递（Message Passing）
  • 数据并行（Data Parallelism）：多个 agent 在多个数据集上并行，同时交换数据。

• 通信抽象：

  • 共享内存空间

    这种通信方式的重点是保证一致性。

  • 消息传递

    需要了解基本原理。消息传递本质上就是通过 Send 和 Receive 操作进行内存间的拷贝，各端提供自己的缓冲区（本地地址），并且相互同步。

    Send 需要指定本地缓存和远端需要接收的进程，Receive 需要指定本地缓存和远端发送的进程。所谓指定“进程”，实际上是给消息打 Tag，接收方根据 Tag 来接收消息。同步一般发生在 Send 完成、缓冲区释放、Receive 等待等时刻。

    直接内存访问（DMA）出现后实现了无阻塞的消息传递。

  这两种通信机制的对比：

  方面	共享内存	消息传递
  特点	地址空间共享	地址空间独立，显式通信
  同步	需要显式做同步	消息传递收发时隐式同步
  编程难度	低	高
  硬件实现难度	高	低

本节最后总结了多处理器中的基础性问题：

1. 命名。可以联系第三章的 Tomasulo 算法，命名影响数据的存放、访问和传递。
2. 内存空间布局。涉及全局和分段式内存、物理和虚拟内存。
3. 同步。
4. 延迟和带宽。

5.2 一致性¶

在多处理器系统中，每个处理器有自己的缓存，可能产生不同处理器看到的同一内存位置的数据不一致的问题。

我们将缓存的数据区分为两类：

• 私有数据（private）：只有一个处理器使用。此时数据只在一个处理器的缓存中，不需要一致性。
• 共享数据（shared）：多个处理器使用。此时多个处理器的缓存持有数据的副本，需要保证一致性。对于共享数据，缓存提供：
  • 迁移（migration），即将数据移动到本地缓存，减小延迟。
  • 复制（replication），同时减小内存带宽，用于并行程序。

书本从两个方面描述共享内存系统的一致性：

• coherence：
  • 程序顺序：处理器 P 向 X 写入值后读取，期间没有其他处理器写入 X，返回 P 写入的值。
  • 保证一致：处理器 P1 向 X 写入值后，处理器 P2 读取，期间没有对 X 的写入。只要写入和延迟的间隔足够，返回 P1 写入的值。
  • 对同一内存位置的写入操作是串行化（serialize）的，即被看见的顺序相同。
• consistency：
  • 定义一个写操作何时被看见。