计算机体系结构

Riicarus大约 48 分钟计算机科学计算机组成结构计算机组成结构

计算机体系结构

概述

分类

Flynn 分类

基于指令流和数据流数量的计算机结构分类.

  • SISD
  • MISD
  • SIMD
  • MIMD

SISD: 串行计算机, 在任何时钟周期, 只有单个指令流在 CPU 执行, 只有单个数据流用作输入. 执行结果是确定的(程序在给定输入条件下多次运行, 执行流程和结果是一致的).

SIMD: 并行计算机, 在任一时钟周期, 所有处理单元执行相同的指令, 但是每个处理单元能对不同数据元素进行操作.

主要用于处理高度规整操作的问题, 如: 图像处理. 执行具有同步性和确定性.

MISD: 单个数据流进入多个处理单元, 每个处理单元用多个指令流对单个数据进行独立操作.

很少有此类必须计算机的实例.

MIMD: 并行计算机: 线程级或任务级并行. 每个处理器可以执行不同的指令流, 可以对不同的数据流进行操作. 各处理器执行可以是同步的或者异步的, 确定性的或者非确定性的.

比 SIMD 更灵活, 适应性更强. 何时何任务级并行, 也可以开发数据级并行, 开销比 SIMD 高.

市场分类

  • 个人/移动设备: 成本/功耗/媒体性能/响应率
  • 桌面计算机: 性价比/图形性能/能耗
  • 服务器: 可靠性/吞吐量/可扩展性, 都是多处理器结构
  • 集群/仓库级计算机: 性价比/吞吐量/能耗/均衡性
  • 嵌入式计算机: 价格/功耗/专门应用的性能

系统结构的定义

计算机系统结构的原始概念是: 由程序员(机器语言)看见的(计算)系统属性, 即概念性结构和功能行为, 以区分数据流动和控制逻辑设计的组成和物理实现.

计算机系统结构的现代定义是: 在满足功能/性能和价格目标的条件下, 设计/选则和互联硬件部件构成计算机. 系统结构覆盖:

  • 指令系统设计
  • 组成: 计算机设计方面的高层次, 如: cpu 内部结构, 存储器, I/O 系统等
  • 硬件: 计算机的具体实现技术

区分:

  • 计算机系统结构: 机器语言/程序员看到的传统机器级所具有的属性.
  • 计算机组成: 计算机系统结构的逻辑实现, 包括五大功能部件组成以及逻辑设计等. 着眼于机器级内各事件的排序方式和控制方式, 各部件的功能以及各部件的联系.
  • 计算机实现: 计算机组成的物理实现, 包括各部件的物理结构, 器件的集成度和速度功耗等.
  • 具有相同计算机系统结构(指令系统相同)的计算机, 因为速度要求不同等因素, 可以采用不同的计算机组成; 一种计算机组成也可以采用不同的计算机实现.

ISA 的 7 个重要特征:

  • ISA 类型
  • 存储器访问
  • 寻址方式
  • 操作数类型和大小
  • 操作类型
  • 控制流指令
  • ISA 编码

性能评价

比较机器性能的指标:

  • 执行时间(响应时间/时延): 桌面机, 反应系统性能, 仅有的各方面都认可的性能测量指标
  • CPU 时间: 设计者考虑, 反应 CPU 性能
  • 吞吐量: 网站服务器
  • MIPS: millions of instructions per second

用程序集比较机器性能:

  • 选择适当的程序评估性能: 基准测试程序套件
  • 不同平均值

量化方法

SPEC Ratio:

SPECRatioA=ExecutionTimeOfReferenceComputerExecutionTimeOfComputerA SPECRatio_A = \frac{ExecutionTimeOfReferenceComputer}{ExecutionTimeOfComputerA}

SM(Spec Mark): 被测试计算机执行 n 个基准测试程序分别得到的 SPECRatio 的集合平均值, 是一个综合指标以衡量不同计算机的性能.

SM=∏i=1nSPECRatioin SM = \sqrt[n]{\prod_{i=1}^{n}SPECRatio_i}

量化原则:

  • 利用并行性: 系统级/指令级/操作级并行
  • 局部性原理:
    • 时间局部性
    • 空间局部性
  • 注重常用事件: 量化该原则的基本定律--Amdahl's law

Amdahl 定律:

SpeedUpRatio=ExecutionTimeOfNotOptimizedComputerExecutionTimeOfOptimizedComputer SpeedUpRatio = \frac{ExecutionTimeOfNotOptimizedComputer}{ExecutionTimeOfOptimizedComputer}

改进比例:

Fe=ExecutionTimeOfCanBeOptimizedImprovedPartExecutionTimeOfWholeNotOptimizedWork F_e = \frac{ExecutionTimeOfCanBeOptimizedImprovedPart}{ExecutionTimeOfWholeNotOptimizedWork}

改进加速比:

Se=ExecutionTimeOfNotOptimizedPartExecutionTimeOfOptimizedPart S_e = \frac{ExecutionTimeOfNotOptimizedPart}{ExecutionTimeOfOptimizedPart}

改进后整个系统的加速比:

Sn=T0Tn=1(1−Fe)+Fe/Se S_n = \frac{T_0}{T_n} = \frac{1}{(1-F_e) + F_e/S_e}

可见, FeF_e 对 SnS_n 影响更大.

指令系统

指令集系统结构分类及特点

指令集系统结构(Instruction Set Architecture, ISA), 即计算机硬件对程序员和编译器开发者可见的部分.

ISA 的分类方面, 不同指令集系统结构最根本的区别在于: 处理器内部数据的存储结构不同.

存储结构包括: 堆栈/累加器/一组寄存器. 操作数可以显式执行或者隐含指定.

  • 堆栈系统结构中操作数隐含的位于栈顶.
  • 累加器系统结构中的一个隐含操作数就是累加器.
  • 通用寄存器结构中只能明确指定操作数, 不是寄存器就是存储器地址.
GPRs
GPRs

通用寄存器系统结构的分类及特点

按照通用寄存器(GPR)访问方式划分:

  • register-memory 系统结构: 一般指令都可以访问存储器.
  • register-register 或 load-store 系统结构: 只能通过 load 和 store 指令来访问内存.
  • memory-memory 系统结构: 现实中不存在.

GPR 出现的原因:

  • 寄存器比存储器快.
  • 编译器使用寄存器很方便, 比使用其他存储形式效率更高.
  • 寄存器用来存放变量可以减少数据流量, 加速程序运行.
  • 改善代码密度, 寄存器地址比存储器地址位数少.

GPR ISA 运算类指令的两个特性:

  • ALU 指令中包括两个或者三个操作数.
    • 两个操作数的格式中, 有一个即使结构操作数也是源操作数.
    • 三个操作数格式中, 指令包含一个结果操作数和两个源操作数.
  • ALU 指令中包括多少个存储器操作数: 从 0 - 3 个不等.

Reg-Reg(0, 3) GPR 优点在于:

  • 具有简单, 定长的指令编码.
  • 具有简单的代码生成模式.
  • 每条指令运行的时钟周期数相近.

缺点在于:

  • 目标代码指令数比直接访问存储器的系统结构多.
  • 质量你个多和指令密度低使程序变得很大.

Reg-Mem(1, 2) GPR 优点在于:

  • 数据不需要专门的载入指令就可以直接访问.
  • 指令格式更加易于编码, 代码密度高.

缺点在于:

  • 源操作数在二元操作中被破坏了, 操作数不等价.
  • 一体哦啊指令中同时对存储器地址和寄存器号码进行编码, 使得寄存器数量被限制.
  • 操作数位置不同使得每条指令执行所需的时钟周期不同.

存储器寻址

我们讨论的所有指令系统都是字节寻址的, 都提供了字节(8 位), 半字(16 位), 和字(32 位) 寻址, 大多数计算机还提供了双字(64 位)寻址.

对于 Intel 系列指令系统, 一个字是 2 个字节, 而对于 MIPS 来说, 一个字是 4 个字节.

一个字的地址用其最低地址表示, 在 MIPS 中, 字的起始地址必须是 4 的倍数, 称为对齐限制.

取数指令(Load Word, LW): 将数据从存储器拷贝到寄存器的指令.

存数指令(Store Word, SW): 将数据从寄存器拷贝到存储器的指令.

注意数据存储的大小端, 同时, 对齐限制也会带来一些优化:

  • 字或者双字整数倍对齐访问存储器: 简化硬件实现的复杂性.
  • 一次不对齐的存储器访问可能会导致多次对齐存储器访问, 对齐访问的程序会运行得比较快.

寻址方式

寻址方式即指令中如何指定所要访问的操作数的地址. 寻址方式需要指定常量/寄存器/存储器操作数的位置.

注意:

  • 立即数通常也被认为是一种存储器寻址方式.
  • 寄存器不属于存储器寻址.
  • 分离出依赖于程序计数器的 PC相对寻址.

常见寻址方式:

  • 寄存器寻址
  • 立即数寻址
  • 位移量寻址
  • 寄存器间接寻址
  • 间接寻址
  • 索引寻址
  • 存储器间接寻址
  • 自动递增寻址
  • 自动递减寻址
  • 比例寻址

一般 ISA 支持的基本寻址方式:

  • 立即数寻址
  • 位移量寻址
  • 寄存器间接寻址
  • 立即数为 8 - 16 位, 位移量为 13 - 16 位

MIPS 寻址模式总结

立即数寻址: 操作数是指令中的常数.

ImmediateAddressing
ImmediateAddressing

寄存器寻址: 操作数是寄存器.

RegisterAddressing
RegisterAddressing

基址寻址: 操作数在内存中, 其地址是指令中基址寄存器和常数的和.

BaseAddressing
BaseAddressing

PC 相对寻址: 地址是 PC 和指令中常数的和.

BaseAddressingOfPC
BaseAddressingOfPC

伪直接寻址: 跳转地址由指令中 26 位字段和 PC 高位相连而成.

BaseAddressing_PseudoDirect
BaseAddressing_PseudoDirect

操作数

指定操作数类型有两种方法:

  • 通过操作码的编码来指定, 最常用.
  • 用硬件解释的字段表示类型.

指令系统的操作

大多数指令集系统支持的操作:

  • 算数和逻辑运算: 定点算数与逻辑操作, 如: 加/减/乘/除/与/或/非.
  • 数据传输: Load-Store 指令.
  • 控制: 条件转移/跳转/过程调用和返回/陷阱
  • 系统: 操作系统调用/虚拟存储器管理指令.
  • 浮点: 浮点数操作.
  • 十进制
  • 字符串
  • 图像

指令系统有一个共同的规律: 使用最多的都是一些简单的指令. 一般来说, 所有的计算机都应该支持前三种指令, 而对后几类指令的支持可能为 0, 也可能有大量的特殊指令.

控制流指令

控制流指令包括:

  • 条件转移
  • 跳转
  • 过程调用
  • 过程返回

控制流指令的寻址方式中, 一般要知名转移的目标地址, 但返回过程是个例外, 因为编译时不知道返回地址.

如果使用 PC 相对寻址, 即使用基于程序计数器的位移量来指定目标地址, PC 相对寻址有如下优点:

  • 目标指令与当前指令距离不远, 使用相对偏移地址可以缩减指令长度.
  • 使用相对寻址的程序可以载入到主存的任何位置, 称为位置无关, 对在链接时才执行的程序可以减少工作量.

如果使用寄存器间接跳转, 由于编译时不知道目标的位置, 为了实现返回和间接跳转, 需要使用寄存器进行间接跳转: 给出包含目标地址的寄存器名称.

寄存器间接跳转还支持:

  • 分支选择语句 case 或者 switch
  • 面向对象语言中的虚拟函数或者方法
  • 高阶函数或者函数指针
  • 动态共享库

对于条件转移来说, 实现方案有如下三种:

  1. 条件码
  2. 条件寄存器
  3. 比较并转移

过程调用的实现方案有两种基本/传统的方法, 用来保存子程序使用的寄存器:

  1. 调用者保存: 调用者调用其他过程时, 必须保存在调用过程后还要使用的寄存器, 被调用者无需维维护这些寄存器.
  2. 被调用者保存: 被调用的过程需要保存它使用的寄存器, 调用者不受这些限制.

有时候, 如果两个调用者都需要访问相同的全局变量时, 必须使用调用者保存方法. 大多数时机编译器会综合两种方法使用.

指令系统的编码

指令编码包括: 操作/寄存器地址/寻址方式编码, 指令编码会影响处理器的实现和编译后程序的大小.

如何将寻址方式和操作通过编码结合到一起?

  • 独立寻址标识符字段(显式).
  • 寻址方式由操作码隐含指定, 如 Load-Store 指令.

编码主要有三种方式:

  1. 变长编码: 允许所有的操作使用所有的寻址方式, 适合寻址方式和操作比较多的情况. 译码复杂, 不适合流水线.
  2. 定长编码: 把操作和寻址方式组合在操作码中, 通常所有的指令长度都相同. 适合寻址方式和操作较少的情况. 译码简单, 适合流水线, 代码量大.
  3. 混合编码: 减少过多的指令, 以减轻多种结构的指令带来的工作负担, 但是仍然提供多种长度指令以减少代码长度.

如果注重性能, 就选择定长编码; 如果关注代码量大小, 就使用变长编码; 折中可以选择混合编码.

MIPS 系统结构指令和寻址特点

MIPS 是一种简单 64 位 Load-Store 系统结构, 使用固定长度编码, 译码简单, 有利于实现高效流水线, 也可以使编译器产生更高效的目标代码.

MIPS 有 32 个 64 位通用寄存器(GPR), 名称为 R0, R1, ..., R31, 也称为寄存器, 其中, R0 的值始终为 0; MIPS 还有 32 个浮点寄存器(FPR), 名称为 F0, F1, ..., F31, 既可以作为 32 个 32 位单精度寄存器来使用, 也可以作为 32 个 64 位双精度寄存器来使用.

MIPS 的数据类型包括主要分为两类: 定点类型和浮点类型. 定点数据类型有 8 位字节, 16 位半字, 32 位字和 64 位双字; 浮点数有 32 位单精度和 64 位双精度浮点数.

MIPS 数据传输的寻址方式有三种, 使用 16 位立即数:

  • 16 位位移量方式(基址寻址): 操作数地址是一个存放在寄存器中的基址与相对该基址的 16 位偏移量相加获得.
  • 位移量为 0 -- 寄存器间接寻址.
  • R0 作为基址寄存器 -- 16 位绝对寻址.

MIPS 的存储器是使用 64 位地址字节寻址的.

MIPS 指令格式如下:

  • 指令长度为 32 位, 其中 6 位是基本操作码, 可以使机器更容易进行流水线操作和译码.
  • 两种存储器寻址方式被编码到操作码中.

具体如下:

  • I 型指令: I-StructInstruction
    • 加载/存储字节/半字/字/双字
    • 立即数-寄存器运算: rt <- rs, OP 立即数
    • 条件分支指令: rs 表示寄存器, rt 表示未使用
    • 跳转寄存器/跳转并链接寄存器: rt = 0, rs 表示目标, 立即数为 0
  • R 型指令: R-StructInstruction
    • 寄存器-寄存器 ALU 操作: rd <- rs funct rt
    • funct 编码数据通路操作: Add, Sub, ...
    • 移位, 读/写专用寄存器和数据移动
  • J 型指令: J-StructInstruction
    • 跳转, 跳转并链接
    • 陷阱, 从异常中返回

MIPS 的操作大致分为 4 类:

  1. 载入和存储
  2. ALU 操作
  3. 分支和跳转
  4. 浮点操作

所有的通用寄存器与浮点数寄存器都可以被载入或存储, 唯一的例外是载入 R0 无效.

所有的 ALU 指令都是 Reg-Reg 指令, 包括算数和逻辑操作, 并且, 都支持立即寻址方式.

流水线技术

基本概念

流水线是利用执行指令操作之间的并行性, 实现多条指令重叠执行的技术. 当今, 流水线是实现更快 CPU 的基本和关键技术.

机器周期(流水线周期): 指令沿流水线移动一个流水段的时间. 长度取决于最慢的流水段, 一般是一个时钟周期(有时是两个).

每个流水线周期从指令流水线流出一条指令.

吞吐量: 单位时间从流水线流出的指令数.

流水线重叠方式需要解决一些问题:

  1. 为了实现取指/分析指令/执行指令同时进行, 需要对应的独立部件(并且暂存中件结果, 如: 流水线锁存器).
  2. 尽量缩短各功能部件的运行速度, 使其大致相等, 避免在重叠中相互等待.
  3. 主存访问冲突.

访存冲突解决方式:

  1. 将主存分为两个独立编制的存储器: 指令存储器和数据存储器, CPU 可以分别独立访问.
  2. 低位交叉存取方式: 可并行访问不在同一个存储体中的指令或者数据.
  3. 指令预取: 在重叠操作中, 当前一条指令在执行过程中就需要提前去除后面的指令进行相应处理, 称为先行(预取).

流水线分类:

  • 按照各过程段用时是否相等分: 均匀流水线/非均匀流水线
  • 按处理数据类型分: 标狼流水处理机/向量流水处理及
  • 按流水线规模分: 操作流水线/指令流水线/宏流水线
  • 按功能分: 单功能流水线/多功能流水线
  • 按工作方式分: 静态流水线/动态流水线
    静态流水线需要等待一类任务执行完成才能执行下一类任务, 而动态流水线不需要(见下图).
  • 按连接方式: 线性流水线/非线性流水线
StaticAndDynamicAssemblyLine
StaticAndDynamicAssemblyLine

流水线的特点:

  • 流水线处理的最好是连续任务, 只有连续任务才能发挥流水线的效率.
  • 流水线是将一个大的功能部件分解为多个子过程.
  • 流水线中每个功能部件的后面都要有一个缓冲寄存器, 也成为锁存器, 用于平滑各个功能段延时的不一致.
  • 流水线中各段时间应尽可能相等, 避免过长导致相互等待.
  • 流水线有装入时间和排空时间.

流水线时空图及性能分析

时空图

时空图从时间和空间两个方面描述了流水线的工作过程. 横轴代表时间, 纵轴代表流水线的各个段.

各段时间相等的时空图
AssemblyLine
AssemblyLine

吞吐率: 单位时间内, 流水线完成的任务数量或输出结果的数量.

TP=nTk TP = \frac{n}{T_k}

nn 是任务数, TkT_k 是处理完成 nn 个任务所需的时间.

AssemblyLineTimeUsage
AssemblyLineTimeUsage

假设流水线为 kk 段流水线, 完成 nn 个任务所需的时间为:

Tk=kΔt+(n−1)Δt=(k+n−1)Δt T_k = k \Delta t + (n - 1) \Delta t = (k + n - 1) \Delta t

流水线实际吞吐率为:

TP=n(k+n−1)Δt TP = \frac{n}{(k + n - 1) \Delta t}

最大吞吐率为:

TPmax=lim⁡n→∞n(k+n−1)Δt=1Δt TP_{max} = \lim_{n \to \infty} \frac{n}{(k + n - 1) \Delta t} = \frac{1}{\Delta t}

各段时间不同的流水线
AssemblyLineWithNotSameTime
AssemblyLineWithNotSameTime

流水线中时间最长的段称为流水线的瓶颈段.

解决瓶颈问题的方法:

  1. 细分瓶颈段
  2. 重复设置瓶颈段

细分瓶颈段:

BottleneckStageSubdivision
BottleneckStageSubdivision

重复设置瓶颈段:

控制逻辑更复杂, 需要增加硬件.

BottleneckStageRepeat
BottleneckStageRepeat

性能分析

衡量流水线性能主要有三个指标: 吞吐率, 加速比, 效率.

加速比

S=TSTK S = \frac{T_S}{T_K}

TST_S 为不使用流水线所用时间, TKT_K 为使用流水线所用时间.

对于各段时间相等的流水线:

S=nkk+n−1 S = \frac{nk}{k + n - 1}

最大加速比为:

Smax=lim⁡n→∞nkk+n−1=k S_{max} = \lim_{n \to \infty} \frac{nk}{k + n - 1} = k

效率

流水线效率 EE 指 流水线的设备利用率. 在时空图上, 流水线的效率定义为 nn 个任务占用的时空区与 kk 个功能段总的时空区之比.

E=T0k∗Tk E = \frac{T_0}{k * T_k}

nn 个任务占用的时空区即顺序执行 nn 个任务所需的时间 T0T_0, 一条 kk 段流水线完成 nn 个任务所用的总时空区为 k∗Tkk * T_k, TkT_k 是流水线完成 nn 个任务所用的总时间.

一条 kk 段流水线的效率为:

E=nk+n−1 E = \frac{n}{k + n - 1}

最大效率为:

Emax=lim⁡n→∞nk+n−1=1 E_{max} = \lim_{n \to \infty} \frac{n}{k + n - 1} = 1

RISC 指令系统特点

RISC 系统有如下关键特点:

  1. 所有参加运算的数据来自寄存器, 结果也写入寄存器, 寄存器为 32/64 位.
  2. 访存只有 load/store 指令.
  3. 指令数量较少, 所有指令长度相同.

这种结构可以有效简化流水线.

MIPS 系统是默认的 RISC 系统.

非流水线下 RISC 指令系统的实现

单周期

RISC_SingleCycleImplementation
RISC_SingleCycleImplementation

单周期, CPI=1CPI = 1, 很少使用.

多周期

RISC_MultiCycleImplementation
RISC_MultiCycleImplementation

上图有五个周期:

  1. 取指(InstructionFetch, IF)
    • 按照 PC 内容访问指令寄存器, 取出指令.
    • PC+4→NPCPC + 4 \to NPC, 为条指令地址.
  2. 译码(InstructionDecode, ID)
    • 指令译码.
    • 读寄存器.
    • 如果需要, 符号扩展指令中的位移量.
  3. 执行(Execution, EX)
    • Load/Store: 计算数据存储器有效地址.
    • R-R/R-I: 执行计算操作.
    • Branch: 做相等测试, 如果相等计算目标地址送 PC.
  4. 访存(MemoryAccess, MEM)
    • Load: 送有效地址到数据存储器, 取数据.
    • Store: 写 ID 读出数据到有效地址单元中.
  5. 写回(WriteBack, WB)
    • Load/ALU: 写结果到寄存器堆.

数据路径中的暂存器易于实现流水线.

注意, Branch/Store 指令只花费 4 个时钟周期.

若 Branch 执行概率为 %p_{branch}%, Store 执行概率为 pstorep_{store}, 整体 CPI 为:

CPI=4∗(pbranch+pstore)+5∗(1−pbranch−pstore) CPI = 4 * (p_{branch} + p_{store}) + 5 * (1 - p_{branch} - p_{store})

如此实现没有优化.

多周期性能改进

  1. 对于 Branch 指令, 将相等测试和计算可能的转移目标地址提前到 ID, 如此 Branch 指令只占用两个时钟周期.
  2. 完成 ALU 指令提前到 MEM, 如此 ALU 指令只占用 4 个时钟周期.

改进后, CPI 为:

CPI=2∗pbranch+4∗(pstore+palu)+5∗pload CPI = 2 * p_{branch} + 4 * (p_{store} + p_{alu}) + 5 * p_{load}

RISC_OptimizedMultiCycleImplementation
RISC_OptimizedMultiCycleImplementation

还可以改进硬件冗余, 将 ALU 共享, 数据和指令存储器可以合并, 因为访问发生在不同的时钟周期.

经典 5 段流水线 RISC 处理器

5 个段构成一个流水线, 一条指令经过每一个段. 由此, CPI 减少到 1, 因为每个时钟周期发射或者完成一条指令. 同时, 在任一时钟周期, 每个流水段正执行一条指令的部分.

Classic5StageAssemblyLineRISC
Classic5StageAssemblyLineRISC
5StageMIPSDatapath
5StageMIPSDatapath

流水线减少执行时间的方法:

  1. 对于每条指令执行用一个时钟周期的机器(单周期实现), 流水线减少时钟周期.
  2. 对于每条指令执行用多个时钟周期的机器(多周期实现), 流水线减少 CPI.

流水线寄存器

由于流水线每个周期都要取出一条指令, 那么先前取出正在执行的指令会被覆盖, 我们需要使用流水线寄存器来保存从存储器中取出的指令. 同时, 每级都要保存目的寄存器编号.

引入流水线后, 会出现一些问题:

同一时钟周期内, 不同操作不能使用同一数据通路资源(结构冒险, Structure Hazard).

引入后, 会出现访问存储器冲突, 解决方式为使用分开的指令 Cache 和数据 Cache. 如果时钟周期不变, 流水线存储系统的带宽必须是非流水线的 5 倍.

5StageMultiAssemblyLineRISC_StructureHazard_MEM
5StageMultiAssemblyLineRISC_StructureHazard_MEM
5StageMultiAssemblyLineRISC_StructureHazard_MEM_Solution
5StageMultiAssemblyLineRISC_StructureHazard_MEM_Solution

同时, 也可能发生寄存器冲突, 同一时钟周期可能会有读/写寄存器操作, 发生冲突. 解决方式为允许在同一个时钟周期 WB 段先写, ID 段后读.

如果是在同一时钟周期内, 针对同一个寄存器的读写, 就会发生数据冒险(Data Hazard).

5StageMultiAssemblyLineRISC_StructureHazard_Register
5StageMultiAssemblyLineRISC_StructureHazard_Register
5StageMultiAssemblyLineRISC_StructureHazard_Register_Solution
5StageMultiAssemblyLineRISC_StructureHazard_Register_Solution

更新 PC 时, 也可能发生冲突, 由于每个时钟周期都需要增量 PC 并存储到 PC, 如果遇到转移指令, 需要改变 PC 的值, 但是条件转移地址需要等到 ID 段才能获得, 如果转移发生, 那么会取出并执行一条无效的指令. 这称为控制冒险(Control Hazard).

流水线寄存器用于保证不同段的指令不会相互干扰. 任何后面段需要的值都必须放到流水线寄存器中, 并且会复制到后面的寄存器中, 直到不需要为止.

流水线冒险

冒险分类与有停顿流水线性能

冒险分类如下:

  • 结构冒险: 指令重叠执行时, 发生硬件资源冲突.
  • 数据冒险: 指令重叠执行时, 一条指令依赖前一条指令的执行结果但是没有准备好.
  • 控制冒险: 下一个时钟周期取指令时, 转移条件和转移 PC 是不可用的.

冒险总是可以用停顿解决的. 停顿会为某些指令暂停一定时钟周期, 当一条指令被停顿后, 其后的所有指令都会被停顿, 该指令之前的指令会继续执行. 停顿时, 也不会有任何新的指令被取到流水线. 流水线停顿也被称为流水线气泡.

结构冒险: 流水段竞争

解决方式:

  • 停顿.
  • 资源重复.
    • 多重访问寄存器堆.
    • 多重访问存储器.
    • 充分流水功能部件.

对于寄存器读写冲突:

  1. 插入停顿, 但会降低加速比.
  2. 采用 WB 先写, ID 后读的方式.

对于存储访问冲突:

  1. 插入停顿.
  2. 提供另一个存储器端口.
  3. 使用分开的指令存储器和数据存储器.
  4. 使用指令缓冲器.

数据冒险

对于同一周期内对同一寄存器的读写, 同样使用 WB 先写, ID 后读的方式解决.

对于不同周期内对同一寄存器的数据依赖, 解决思路为: 不让指令在数据冒险时重叠执行.

不让有冒险的指令流过流水线, 即: 流水线停顿. 实现方式可以通过软件方式, 由编译器插入 nop 指令; 也可以通过硬件方式, 增加硬件互锁(Interlock), 增加硬件检测需要停顿的情况, 增加硬件放"气泡(暂停)"到流水线.

5StageMultiAssemblyLineRISC_DataHazard_Solution_Nop
5StageMultiAssemblyLineRISC_DataHazard_Solution_Nop
5StageMultiAssemblyLineRISC_DataHazard_Solution_Interlock
5StageMultiAssemblyLineRISC_DataHazard_Solution_Interlock

除了上述两种方式, 还有可能的情况: 有数据冒险的指令的结果已经计算出来, 存放在了流水线寄存器中, 只是不在寄存器堆中. 此时, 可以使用前推的方法, 在数据通路上增加数据线(buses) 传送这些结果, buses 在数据通路中总是从后面的流水段连接到前面的流水段.

5StageMultiAssemblyLineRISC_DataHazard_Solution_Forwarding
5StageMultiAssemblyLineRISC_DataHazard_Solution_Forwarding

上图中, 增加了如下数据前推的数据线:

  1. EX/MEM.AluOutput --> AluInput (红色箭头)
  2. MEM/WB.AluOutput --> AluInput (蓝色箭头)
  3. MEM/WB.LMD --> AluInput (紫色箭头)
5StageMultiAssemblyLineRISC_DataHazard_Solution_Forwarding_Others
5StageMultiAssemblyLineRISC_DataHazard_Solution_Forwarding_Others

上图展示了前推可能的其他路径(红色), 主要作用于 Load/Store 指令, 即: MEM/WB.LMD --> DMInput.

当然, 前推也有不能解决的问题, 如: 在同一周期内, 数据的产生在周期结束, 而数据依赖在周期开始, 此时前推无法提供数据. 不过, 可以额外在数据依赖指令处插入停顿来解决.

Load Stall 对 CPI 的影响较大, 很多时候 Load 之后的指令需要 Load 的结果, 就会产生很多 Stall. 对此, 可以在编译阶段, 由编译器进行重排序, 合理避免数据冒险(可以参考 Java 中对 volatile 修饰的变量的读写屏障).

控制冒险

下一个时钟周期取指令时, 转移条件和转移 PC 是不可用的, 即在进入 ID 段时, 转移条件和转移目标地址, 不能按时提供给 IF 段取指令.

控制冒险引起 MIPS 的性能损失比数据冒险大得多.

下图为条件转移的原理图:

5StageMultiAssemblyLineRISC_Transition
5StageMultiAssemblyLineRISC_Transition

可见, 控制冒险发生在 MEM 周期和 IF 周期交接时, 下一个 IF 将 MEM 的跳转结果覆盖, 导致控制冒险.

对于控制冒险, 有四种简单解决方法:

  1. 冻结或冲刷流水线.
  2. 预测转移不发生.
  3. 预测转移发生.
  4. 转移延迟.

但是, 上述方法都会使硬件固定. 编译时, 会根据硬件机制和转移行为对代码进行调度, 来获取最佳性能.

在转移预测中, 通常的改进方法会将转移计算从 EX+MEM 提前到 ID 甚至 EX 阶段.

增加内容流水线处理机及其设计

流水线处理机的指令系统和格式

  • ALU 操作指令: and/or/add/sub
  • 存储器访问指令: load/store
  • 条件转移指令: bne/beq
  • 无条件转移指令: branch

注意:

  • ALU 指令处理把运算结果写入寄存器堆外, 也会把 ZERO 标志写入 Z 寄存器.
  • 条件转移指令使用 Z 标志决定是否转移.
  • 指令长度: 32 位, 地址: 32 位.
  • 设定指令存储器和数据存储器的存储单元为 32 位, 按字寻址.
  • 每次按 PC 取指令后, PC+1→PCPC + 1 \to PC.
ComplexSingleStageProcessorImplementation
ComplexSingleStageProcessorImplementation

一些指令的具体执行流程如下:

Execution_Add
Execution_Add
Execution_Addi
Execution_Addi
Execution_load
Execution_load
Execution_store
Execution_store
Execution_branch
Execution_branch

下面是 5 级流水线中使用的流水线寄存器:

AssemblyLineRegister_PCAndIR
AssemblyLineRegister_PCAndIR
  • PC(32 位): 程序计数器, 程序不转移时, PC+1→PCPC + 1 \to PC; 发生转移时, PC+ExtendedOffset→PCPC + ExtendedOffset \to PC.
  • 指令寄存器 IR(32 位): IF 和 ID 之间的流水线寄存器.
AssemblyLineRegister_ID-EX
AssemblyLineRegister_ID-EX

在 ID 和 EX 段之间:

  • 寄存器堆中读出的 A, B 数据需要保存.
  • 经过符号扩展之后的立即数 I 需要保存.
  • 使用一个 d 寄存器(5 位)来保存目的寄存器号, 因为指令操作的结果要在 WB 级写回寄存器堆, 多以需要同步目的寄存器号.
AssemblyLineRegister_EX-MEM
AssemblyLineRegister_EX-MEM

在 EX 和 MEM 段之间:

  • Z(1 位): 存放 ALU 的 ZERO 标志位, 在执行条件转移指令时, 用 Z 决定是否转移.
  • R(32 位): 存放 ALU 计算结果(ALU/load/store).
  • S(32 位): 专用于 store 指令, 用于存放要写入寄存器的 32 位数据.
AssemblyLineRegister_MEM-WB
AssemblyLineRegister_MEM-WB

在 MEM 和 WB 之间:

  • D(32 位): 存放 load 指令从存储器中独处的数据.
  • C(32 位): 保存前一级的 R, 即 R 型指令的计算结果.
  • 这一级 d 寄存器的数据用于指定写回操作的目的寄存器号, D 或者 C 的数据要写回到对应的寄存器堆中.

下图是完整的数据路径和控制信号:

AssemblyLineProcessorDataPathAndControlSignal
AssemblyLineProcessorDataPathAndControlSignal

ID 级的 MUX 用于 store 指令的参数, 如果是 store 指令, 就选择 IR 中的 rd; 如果不是, 就选择 IR 中的 rs2.

各流水线级控制信号及其意义:

流水线级控制信号注释
IFBTAKEN转移发生
IDSST选择 store(rd)/other(rs2)
EXESIMM选择立即数
EXEALUOPALU 操作码
EXEWZ写 Z 标志
MEMWMEM写存储器
WBSLD选择 load
WBWREG写寄存器堆

流水线转移指令控制

转移指令包括条件转移和无条件转移, 6 位 OP, 26 位偏移量.

  • bne disp: if !Z, PC = PC + disp.
  • beq disp: if Z, PC = PC + disp.
  • branch disp: PC = PC + disp.

转移指令在 ID 级由专用加法器计算转移地址, 条件转移指令同时判断转移条件.

在流水线中, 由编译器插入 nop 指令延迟转移.

TransitionControl_NOP
TransitionControl_NOP

对于条件转移指令来说, 需要 EXE 级结束产生的 Z 标志, 故而需要插入两条 nop.

而对于无条件转移指令来说, 不需要 Z 标志判断, 只需要插入一条 nop.

转移地址的计算比较重要, 流程如下:

如上图 branch 指令第二个时钟周期,

  • ID 级计算目标转移地址, 从 IR 获取偏移量进行符号扩展;
  • IF 级: nop 取出;
  • BTAKEN = 1, 选择符号扩展偏移量 disp;
  • 地址加法器计算转移目标地址, 等时钟上升沿(本周期结束), 将目标地址打入 PC.
TransitionControl_Branch
TransitionControl_Branch

对于条件转移, 如上图 bne 流水线操作:

TransitionControl_BNEAndBEQ
TransitionControl_BNEAndBEQ
  • bne/beq 根据 Z 判断是否转移.
  • 如果满足, BTAKEN = 1, 转移地址 = PC + disp.
  • 否则, BTAKEN = 0, PC + 1 计算 nop 下一条顺序指令的位置.
  • 时钟上升沿到来时, 计算出的地址被打入 PC. 如果是转移目标地址, 则从目标地址取出指令; 否则取 nop 之后的顺序指令.
  • 综上: BTAKEN=branch+bneZ‾+beqZBTAKEN = branch + bne\overline{Z} + beqZ.

注意: BTAKEN 在 ID 级产生, 但是产生 Z 的指令要早它两个周期.

流水线数据冒险解决

一条指令进入流水线 ID 级, 检测与前面指令可能有数据相关的基本条件是:

(IDrs1==EXErd)+(IDrs1==MEMrd)+(IDrs2==EXErd)+(IDrs2==MEMrd) (ID_rs1 == EXE_rd) + (ID_rs1 == MEM_rd) + (ID_rs2 == EXE_rd) + (ID_rs2 == MEM_rd)

其他条件:

  • EXE 级和 MEM 级指令的 WREG 信号需要参与检测(区分是写目的寄存器还是 store 指令中的 rd, 因为 store 不会写 rd).
  • ID 级指令的源寄存器号 rs2 与立即数部分重叠, 而立即数不会出现相关的.
  • ID 级的指令不能是转移指令, 转移指令不需要判断数据相关.

以上的后两者都是使用操作码来区分的.

DEPEN 是总的数据是否相关的标志, 可以分为 A_DEPEN 和 B_DEPEN.

DEPEN = A_DEPEN + B_DEPEN
A_DEPEN = (ID_rs1 == EXE_rd)(EXE_WREG == 1)(ID_rs1IsReg) + (ID_rs1 == MEM_rd)(MEM_REG == 1)(ID_rs1IsReg)

B_DEPEN = (ID_rs2 == EXE_rd)(EXE_WREG == 1)(ID_rs2IsReg) + (ID_rd == EXE_rd)(EXE_WREG == 1)(store)
+ (ID_rs2 == MEM_rd)(EXE_WREG == 1)(ID_rs2IsReg) + (ID_rd == MEM_rd)(EXE_WREG == 1)(store)

A_DEPEN 指 ID 级指令的 rs1 与前面指令的 rd 数据相关. A_DEPEN 指 ID 级指令的 rs2 与前面指令的 rd 数据相关.

  • EXE_rd 表示 EXE 级的流水线寄存器 d.
  • (EXE_WREG == 1) 表示 I1 的 rd 确实是目的寄存器, 排除 I1 是 store 指令.
  • ID_rs1IsReg 条件是为了排除转移指令.
  • ID_rs2IsReg 排除立即数运算指令.

再进行细分:

A_DEPEN = EXE_A_DEPEN + MEM_A_DEPEN
B_DEPEN = EXE_B_DEPEN + MEM_B_DEPEN
5StageAssemblyLineDepenImplementation
5StageAssemblyLineDepenImplementation

内部前推

一条指令执行时, 要用到上面指令的计算结果, 但这个结果尚未写入寄存器堆. 而实际上, 此时结果已经被 ALU 计算出来了, 在流水线寄存器 R 和 C 中.

我们可以直接在 ALU 的两个数据输出端各加一个多路器, 使 R 和 C 的数据能被直接送到 ALU 的输入端, 即: 内部前推, 或专用数据相关通路.

5StageAssemblyLineForwardingImplementation
5StageAssemblyLineForwardingImplementation

MUX 的选择信号和 A_DEPEN 与 B_DEPEN 有关, 区别是不排除转移指令, 因为转移指令在 EXE 级不做任何操作; 但是会检查 rs2 是否为立即数, 因为立即数不与前面指令的结果相关.

A_DEPEN1 = (EXE_rs1 == MEM_rd)(MEM_WREG == 1) + (EXE_rs1 == WB_rd)(WB_WREG == 1)
B_DEPEN1 = (EXE_rs2 == MEM_rd)(MEM_WREG == 1)(ID_rs2IsReg) + (EXE_rs2 == WB_rd)(WB_WREG == 1)(ID_rs2IsReg)

B_DEPEN0 = !EXE_rs2IsReg + !(MEM_WREG == 1)(EXE_rs2 == WB_rd)(WB_WREG == 1) + !(EXE_rs2 == MEM_rd)(EXE_rs2 == WB_rd)(WB_WREG == 1)(EXE_rs2IsReg)

上面的方法是在 EXE 级 ALU 操作时才检测数据相关, 我们完全可以在 ID 级完成这项工作, 并把结果(A_DEPEN/B_DEPEN) 作为控制信号打入流水线寄存器.

5StageAssemblyLineDataForwardingImplementation
5StageAssemblyLineDataForwardingImplementation

Load 前推

load 指令在 EXE 结束后需要继续访存, 在 MEM 级结束后, 结果才会出现在流水线 D 中. 这是, 使用内部前推无法消除在 load 和其后的指令之间的第一个气泡.

如下是实现 load 指令暂停的控制信号表达式, 信号在 ID 级产生:

LOAD_DEPEN = EXE_A_DEPEN + EXE_B_DEPEN

EXE_A_DEPEN = (ID_rs1 == EXE_rd)(EXE_SLD == 1)(ID_rs1IsReg)
EXE_B_DEPEN = (ID_rs2 == EXE_rd)(EXE_SLD == 1)(ID_rs2IsReg) + (ID_rd == EXE_rd)(EXE_SLD == 1)(store)

流水线异常

异常是另一种控制冒险. 异常是中断正常程序执行的异常事件, 本文的异常是广义异常, 包括中断和狭义异常.

中断例子:

  • 用户敲击键盘.
  • 网络包到达.

异常例子:

  • 除 0.
  • 溢出.
  • 缺页.

当异常发生时, 控制会传递给 OS.

AssemblyLineExceptionHandling
AssemblyLineExceptionHandling

MIPS 可能产生的异常如下:

  • IF级:
    • 取指时发生缺页.
    • 存储器访问边界未对齐.
    • 违反存储器访问权限.
  • ID 级:
    • 未定义的或非法的操作码.
  • EX 级:
    • 算数异常.
  • MEM 级:
    • 存储数据时缺页.
    • 存储区访问边界未对齐.
    • 违反了存储器访问权限.
  • WB 级:
    • 无.

异常在 MIPS 程序中的处理

异常发生时, 处理器必须要进行的操作是: 在异常程序计数器(EPC)中保存出错指令的地址, 并发控制权转交给 OS 的特定地址.

在完成处理异常所需动作之后, 操作系统可以终止程序, 也可以继续执行程序, 此时由 EPC 决定重新 开始执行的地方.

为了处理异常, OS 除了要知道哪条指令引起异常之外, 还必须直到引起异常的原因. 主要有两种方法用于表示异常产生的原因:

  1. MIPS 设置一个状态寄存器(Cause 寄存器)
  2. 使用向量中断: 控制权被转移到由异常原因决定的地址处(OS 通过异常向量地址直到异常原因).

流水线如何处理异常?

异常发生时, 流水线必须被安全关闭, 异常处理完后, 重新启动引起异常的指令.

具体过程如下:

  1. 强制一个 trap 指令进入流水吸线.
  2. 禁止异常指令及后面的指令的所有写操作, 直到 trap 指令流出流水线.
  3. 当 trap 指令开始执行, 唤醒 OS, OS 保存异常指令的 PC 值.
  4. OS 处理异常, 然后重新执行出错指令.

精确异常

如果流水线可以停下来使异常指令之前的指令能正常结束, 异常指令之后的指令能重新启动, 则称该流水线异常是精确异常, 意味着:

  • 异常指令之前的所有指令正常完成.
  • 异常指令及其后的指令没有改变机器的状态.

如此, 重新恢复执行就很简单:

  • 重新恢复执行异常指令.
  • 如果它不是一个可恢复执行的指令, 则执行下一条指令.

执行顺序:

MIPS 为每条指令设置了一个异常状态, 如果一个异常发生, 就将其添加到对应的向量中, 并禁止所有影响系统状态的写操作. 当一条指令即将离开流水线, 检查是否有挂起未响应的异常. 如果一条指令产生了多个异常, 先响应最早流水段出现的异常.- 计算机体系结构

非精确异常

当不同指令执行需要的时钟周期数有多种时, 难以实现精确异常. 在某条指令产生异常之前, 后面的指令可能已经执行完毕, 称为非精确异常.

处理器工作在精确异常模式下, 运行速度更慢.

一般来说, 整数操作异常是精确的, 浮点数操作异常是不精确的.

存储层次结构

Cache

Cache 组织的基本单位是块(block, line). Cache 和主存都被分割成相同大小的块, 对 Cache 和主存的访问是以块为基本单位.

Cache 被插入到主存和 CPU 之间, 使用快速 SRAM 实现, 存储程序的指令和数据部分.

Cache 的设计主要考虑如下四个问题:

  1. 块放置: 把一个 block 从主存调入 Cache 时, 可以放到哪些位置上?
  2. 块识别: 如何判断要访问的块命中 Cache?
  3. 块替换: 当访问块不在 Cache 中, 发生失效时, 应该替换哪一块?
  4. 写策略: 对块进行写时， 采用什么策略?

映像规则

映像包括:

  1. 直接映像: 块只能放在 Cache 中的唯一位置: BlockAddress   mod   NumberOfBlocksInCacheBlockAddress \; \bmod \; NumberOfBlocksInCache.
  2. 全相联: 块可以放在 Cache 中的任何位置.
  3. 组相联: 块可以放在 Cache 一组中的任何位置. BlockAddress  mod    NumberOfSetsInCacheBlockAddress \; \mod \; NumberOfSetsInCache, 如果一组有 n 块, 称 Cache 为 n 路组相联.

块识别

Cache 的每一个块都有一个标识 Tag: 存放 CPU 访问数据所在块的主存物理地址的高位部分(主存多块映射到 Cache 一块).

当 CPU 访问 Cache 时, 比较主存地址与Cache Tag, 如果两者相同, 则表示 Cache 命中.

通常, 每个 Cache 还有一个有效位 valid bit, 表示 Cache 内容是否有效.

物理地址的格式:

PhysicalAddress
PhysicalAddress

对于 Index 字段:

  • 在直接映像 Cache 中, 选择块.
  • 在组相联 Cache 中, 选择组.
  • 索引的位数为:
    • log⁡2Nb\log_2N_b -- 直接映像, NbN_b 为块数量.
    • log⁡2Ns\log_2N_s -- 组相联, NsN_s 为组数量.

对于 ByteOffset 字段:

  • 选择块中的某个字节.
  • 位数: log⁡2N\log_2N, NN 为每块的字节数.

对于 Tag 字段:

  • 用于查找在 Cache 或一组中的匹配块.
  • 位数: NphysicalAddress−Nindex−NbyteOffsetN_{physicalAddress} - N_{index} - N_{byteOffset}.

块替换

对于直接映像, 仅有唯一的一块能够被替换. 而对于全相联或者组相联映像, 有 N 块可以替换, N 为相联度.

如下为一些块替换策略:

  • 随机替换: 随机选择替换的一块.
    • 硬件容易实现, 只需要一个随机数发生器.
    • 均匀使用一组中的各块.
    • 可能替换即将被访问的块.
  • 最近最少使用(Lease-Recently-Used, LRU): 选择一组最近最少使用的块作为被替换块.
    • 局部性原理, 假定最近被访问的块可能会被再次访问.
    • Cache 中需要额外的位记录访问历史.
  • 先进先出(First-In-First-Out, FIFO): 选择一组中最先进入 Cache 的块.

写策略

  1. 写直达: 数据写入 Cache 的时候, 也同时写入主存.
    • Cache 中的数据可以随时丢弃--主存中有最新数据.
    • Cache 控制位只需要一位 valid bit.
    • 主存或者其他处理器总是有最新的数据.
  2. 写回: 写 Cache 时, 不写主存.
    • 不能丢弃 Cache 中的数据--可能需要写回到主存.
    • Cache 控制位: 需要 valid bit 和 dirty bit(数据是否被污染).
    • 带宽较小, 因为对同一块的多次写仅需要对主存写一次.

写直达的优点是: 读缺失不会导致替换时的写操作, 保持了数据一致性, 实现简单.

写回的优点是: 写 Cache 速度更快, 主存带宽更低.

对于写直达的 Cache 来说, 会有写停顿的问题: CPU 必须等待写操作完成. 为解决这个问题, 可以使用写缓冲:

  • 一个小的缓冲区, 存放等待写入主存的几个值.
  • 在写操作集中时, 作用较大.
  • 不能完全消除停顿(如: 写的数据量大于缓冲区).

写 Cache 时, 可能出现写缺失问题: 对 Cache 进行写操作时, 要写的块不在 Cache, 这时有两种解决策略:

  1. 写分配: 写失效时, 将所写单元的块调入 Cache, 然后在进行写命中操作, 类似于读失效的操作.
  2. 不按写分配: 写失效时, 直接将值写入下一级存储器, 而不重新调入需要的块到 Cache. 如此, 写的值不会在 Cache 中.

通常, 写回使用写分配, 写直达使用不按写分配. 因为写回策略中, 最新数据一定会有一份在 Cache 中, 而在写直达策略中, 最新数据一定会有一份在主存中, 使用对应的写缺失策略可以保证数据完整性.

Cache 性能

Cache 的性能通过两个参数定义:

缺失率: Cache 访问中, 访问缺失次数占总访问次数的百分比.

MissRate=MissTimeTotalAccessTime MissRate = \frac{MissTime}{TotalAccessTime}

缺失代价: Cache 访问缺失时, 访问下一级存储器所花费的时间, 通常用时钟周期数表示.

存储器系统性能

CPU执行时间=(CPU时钟周期数+存储器停顿周期数)∗时钟周期时间存储器停顿周期数=指令数∗每条指令访存次数∗缺失率∗缺失代价CPU时钟周期数=CPI执行 CPU 执行时间 = (CPU 时钟周期数 + 存储器停顿周期数) * 时钟周期时间 \\ 存储器停顿周期数 = 指令数 * 每条指令访存次数 * 缺失率 * 缺失代价 \\ CPU 时钟周期数 = CPI_{执行}

CPI执行CPI_{执行} 是没有考虑存储器停顿的理想 CPI, 包括 ALU 指令和存储器指令.

平均存储器访问时间=总访存时间存储器访问次数  =总访问命中时间+总访问缺失时间存储器总访问次数  =总命中访问时间存储器总访问次数+总缺失次数∗缺失代价存储器总访问次数  =命中时间一次访存+缺失率∗缺失代价 平均存储器访问时间 = \frac{总访存时间}{存储器访问次数} \\ \; \\ = \frac{总访问命中时间 + 总访问缺失时间}{存储器总访问次数} \\ \; \\ = \frac{总命中访问时间}{存储器总访问次数} + \frac{总缺失次数 * 缺失代价}{存储器总访问次数} \\ \; \\ = 命中时间_{一次访存} + 缺失率 * 缺失代价

Cache 性能改善方法

  1. 减少缺失率:
    1. 增加块大小.
    2. 增大 Cache 容量.
    3. 更高相联度.
    4. 编译优化.
  2. 减少缺失代价:
    1. 多级 Cache.
    2. 关键字优化.
    3. 读缺失优于写缺失.
    4. 合并写缓冲.
    5. 牺牲缓冲.
  3. 通过并行减少缺失代价和缺失率:
    1. 非阻塞 Cache.
    2. 硬件预取.
    3. 编译预取.
  4. 减少 Cache 的命中时间:
    1. 小而简单的 Cache.
    2. 避免地址转换.
    3. 流水线 Cache 访问.
    4. 路预测.
    5. 踪迹 Cache.

减少 Cache 缺失率

缺失分类:

  1. 强制缺失: 第一次访问某个块, 一定不在 Cache 中, 也称作冷启动缺失或者首次访问缺失.
  2. 容量缺失: Cache 容纳不了一个执行程序的所有块, 一些块被替换出去之后, 又要被访问, 引起容量缺失.
  3. 冲突缺失: 对于组相联映像或者全相联映像, 如果太多的块被映射到一组, 一块被替换后可能又要访问, 引起冲突缺失. 也成为碰撞缺失或者干涉缺失.
  4. 一致性缺失: 由于一致性 Cache 引起的脏数据.

解决方法:

  1. 增大 Cache 容量:
    • 可以解决容量缺失和冲突缺失.
    • 缺点是更长的命中时间和更高的价格.
  2. 增大块容量:
    • 可以解决强制缺失.
    • 可能增加缺失代价, 基本会增加冲突缺失, 在小容量 Cache 中, 可能增加容量缺失.
  3. 更高的相联度:
    • 减少了冲突缺失.
  4. 编译器优化:
    • 合并数组.
    • 循环交换.
    • 循环融合.
    • 分块.

减少 Cache 缺失代价

  1. 使用多级 Cache: 一级 Cache 减少命中时间, 二级 Cache 减少缺失代价, 同时增大二级 Cache 的相联度.
  2. 关键字优先和提前重启动:
  3. 读缺失优先于写缺失: 可能会有读写冲突.
  4. 合并写缓冲: 合并写多个字代替写一个字, 改善写缓冲效率.
  5. 牺牲缓存: 用一组小的全相联 Cache 来存放最近被替换出的几个块.

通过并行减少

  1. 非阻塞 Cache: 等待数据返回的同时, Cache 并不停止, 可以继续提供指令和数据.
  2. 硬件预取.
  3. 编译器控制预取.

减少 Cache 命中时间

  1. 小而简单的 Cache
  2. 在 Cache 索引时, 避免地址转化: 使用 TLB; 或者 Cache 也使用虚拟地址.
    TLB
  3. 流水线 Cache 访问.
  4. 路预测: 针对组相联, 在 Cache 中预留特殊的位, 预测下一次访问 Cache 可能在组中会用到的路或者块.
  5. 踪迹 Cache

主存储器性能优化

主存储器通常采用 DRAM, 主存的性能由延迟和带宽决定.

主存储器优化主要有两种方式:

  1. 增加带宽.
  2. 交叉访问存储器.

增加带宽

使用 n 倍于 Cache 与主存之间的带宽, 主存带宽也将增加 n 倍.

SingleBandwidthMemoryMultiwordBandwidthMemory

此方法的缺点是:

  • 为了提供字访问, 关键路径需要多路开关.
  • 增加用户购买的最小存储器容量.
  • 复杂的纠错结构.

单体多字存储器的性能:

定义带宽为:

带宽=Cache块容量缺失代价 带宽 = \frac{Cache 块容量}{缺失代价}

增加 Cache 和主存之间的带宽到 n 倍, 缺失代价不变, 带宽变为:

n∗Cache块容量缺失代价=n∗原带宽 \frac{n * Cache 块容量}{缺失代价} = n * 原带宽

交叉访问存储器

利用存储系统中具有多个 DRAM 潜在的并行性, 这种主存组织对连续访问的写直达策略尤其重要.

存储器芯片按多个体组织以便同时读或者写多个字. 每个个体通常是 1 个字宽度, 因此总线与 Cache 宽度不需要改变. 但是, 要分时发送地址到多个体, 使得他们几乎都同时读数据.

MultibodyInterleavedMemory
MultibodyInterleavedMemory
InterleavedMemoryAccessPattern
InterleavedMemoryAccessPattern

此方法对带宽的提升在于减少缺失代价.

虚拟存储器

页式虚拟存储器

Cache 中的块对应虚存中的页. 缺失即页失效, 需要有从虚存到主存的存储器映射.

虚存的映射策略采用全相联策略: 允许块放在主存的任意位置.

页式虚存依赖数据结构表, 包含了块的物理地址, 按照页号对块进行查找. 映射方式为: 在物理页地址后, 简单拼接偏移地址.

页表的大小即虚拟地址空间的页数.

PageTableSize=2BitsOfVirtualAddressPageSize∗PageItemSize PageTableSize = \frac{2^{BitsOfVirtualAddress}}{PageSize} * PageItemSize

PageVirtualAddressTransition
PageVirtualAddressTransition

页表同样可以进行优化, 如:

  • 减小页表大小: 对虚拟地址应用一个散列函数, 允许页表长度仅为主存中的物理页的数目.
  • 减少地址转换时间: 增加一个 Cache 进行虚-实地址转换, 即变换旁路缓冲器(Translation Look-aside Buffer, TLB).

虚存中, 页的替换策略一般都使用 LRU, 通过为每一页提供一位使用位或参考位.

写策略使用写回方式, 因为写磁盘的速度太低, 写直达效率非常低. 同时, 设置 dirty-bit, 只有在块被更改后, 才会写回磁盘.