CA7 指令级并行性 (1)
概念
-
指令之间的重叠执行
-
开发指令级并行性的两类主要方法
- 依靠硬件来动态发现和利用并行性
- 用于服务器和台式机处理器
- 在个人移动设备中的处理器
- 在 IoT，成本和功耗的约束，利用较低层次的指令级并行性
- 依靠软件在编译时静态地发现并行性
- 上世纪 80 年代开始尝试，1989年用于Intel安腾系列
- 特定领域或带有明显数据级并行性的科学应用
- 局限性
- 直接导致了多喝处理器
-
了解局限性 以平衡指令级并行性与线程级并行性
-
Pipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control stalls
| 方法 | 解决问题 |
|---|---|
| 向前和旁路 | 潜在的数据危害 |
| 简单的分支指令调度和预测 | 控制危害 |
| 基本编译流水调度 | 数据危害 |
| 基本动态调度 | 真实依赖中的数据危害 |
| 循环展开 | 控制危害 |
| 高级分支预测 | 控制危害 |
| 重命名动态调度 | 输出依赖、数据危害 |
| 硬件推测技术 | 数据危害和控制危害 |
| 动态存储器消除二义性 | 涉及存储器的数据危害 |
| 每个周期发出多条指令 | 理想 CPI |
| 编译器相关分析、软件流水线、跟踪调度 | 理想 CPI、数据危害 |
| 硬件支持的编译器推测 | 理想 CPI、数据危害、分支危害 |
指令级并行性
- 挖掘指令级并行性的所有技术都利用指令之间的并行性
- 基本块
- 一段直线代码序列
- 除了入口没有分支传入且除了出口没有分支转出
- 并行性
- 基本块一般长度为3~6条指令，基本块内可利用的并行度很小
- 提高性能必须跨分支指令（跨基本块）并行化
相关与危害
- 程序的本性：指令间存在相关
- 流水线结构的性质：
- 相关是否导致检测到实际危害：不一定
-
危害是实际上引起的停顿
- 停顿（阻塞、拖延和暂停）将直接造成流水线性能下降。
-
确定一条指令如何依赖另一条指令是关键的，它决定着程序中
- 存在多少并行性
- 如何开发并行性
- 三种类型的相关
- 数据相关：先写后读
- 名称相关
- 反相关：先读后写
- 输出相关：先写后写
-
控制相关
-
指令 i 和 j 数据相关的条件是
- 指令 i 产生的结果被指令 j 使用 或者 指令 j 与指令 k 数据相关，而指令 k 与 i 数据相关（相关链）
数据相关
- 必须按序执行，不能同时执行或完全重叠执行
- 数据相关表示
- 危害的可能性
- 必须遵守的计算顺序
- 可能利用指令级并行性的上限
- 解决方法
- 维持数据相关，避免数据危害
- 调度代码是在不改变数据相关的情况下避免数据危害，由编译器和硬件完成
- 通过转换代码来消除数据相关
- 难点：存在于内存中的数据相关难以检测
名称相关
- 两条指令使用相同的寄存器或内存位置，但关联指令不存在数据流
- 假设 i 在 j 之前
- 反相关：j 写入和 i 读取的寄存器或内存位置相同
-
输出相关：指令 i 和指令 j 写入的寄存器或内存位置是相同的
-
不是真正的数据相关，但在调度指令时会发生问题
- 通过改变指令的名称，使得指令不再冲突
- 寄存器重命名技术解决名称相关问题
- 可以通过编译器静态完成，也可以通过硬件动态地实现
寄存器重命名
- 通过重命名消除WAR和WAW的危害：需要更多的寄存器资源
- 寄存器
- 逻辑寄存器：名称，编程模型中使用的寄存器
- 物理寄存器：位置，硬件设备中存在的寄存器
数据危害
目标：影响程序执行结果的覅放维持程序顺序来开发并行性
程序顺序：源程序所确定的指令逐条执行的顺序
数据危害依赖于指令中读和写的顺序
- RAW：写后读，真正的数据相关
- WAW：顺序写，输出相关
- 若流水线中有多个流水段可写 或 允许指令乱序执行 可能会导致WAW危害
- RAW
- 指令在流水线早期写结果，在晚期读结果，或指令被重排序
控制相关
- 控制相关：if 语句 then 部分终端指令对分支指令的相关
- 控制相关施加两条约束
- 与分支指令存在的控制相关的指令不能移动到分支指令之前，以使得它的执行不再受分支指令的控制
- 与分支指令不存在控制相关的指令不能移动到分支指令之后，以使得它的执行受分支指令的影响
- 因为违反控制相关不一定影响程序的正确性，故
- 控制相关不是必须维持的
- 中断行为和数据流是必须维持的
- 中断行为：改变指令执行顺序不能改变程序中引发中断的方式
-
指令执行的重新排序不能在程序中引起任何新的中断
-
违反控制相关可能不会影响中断行为或数据流
- 通过完成对引起控制停顿的控制危害的检测来维持控制相关
- 控制停顿可以通过硬件或软件技术消除或减少
利用指令级并行性的基本编译技术
基本流水线调度
- 为了防止流水线停顿，相关指令的执行必须与源指令相距一定的周期
- 相距的周期数等于指令流水线中源指令的延迟周期数
编译器的调度能力取决于程序中 ILP 和功能单元的延迟
循环并行性
循环迭代之间的并行性
- 增加指令级并行性的最简单且最常用的方式
- 静态或动态的循环展开
- 使用 SIMD 矢量处理器或 GPU
循环展开
增加有效指令的相对数量
- 简单地多次复制循环体
- 调整循环终止代码
strip mining：一种拆分循环以利用缓存技术的编译技术
调度+循环展开
何时、如何更改指令顺序
步骤
- 确定是否可以展开，不是所有的循环都可以展开
- 使用不同的寄存器来避免不必要的约束
- 消除额外的测试和分支指令
- 通过观察来自不同迭代的 load 和 store 是否独立，来确定展开循环中 load 和 store 是否可以互换
- 调度代码，保留产生与原始代码相同结果所需的所有相关项
关键需求
- 理解一条指令是如何依赖于另一条指令的
- 根据相关性，如何更改或重排指令
限制
- 展开所分摊的开销减少
- 代码大小的限制
- 寄存器的限制
高级分支预测技术降低分支代价
关联分支预测
基本 2 bit 预测方法
- 只使用单条分支指令的近期行为来预测它未来的行为
- 对每条分支指令预测转移或不转移，如果连续两次错误，改变预测结果
关联预测方法 两级预测方法
- 同时考虑其它分支指令最近的行为
- (m, n)预测器：使用最近m条分支指令的行为来从\(2^m\)个分支预测中进行选择， 其中每个分支预测器都是一条分支指令的n位预测器
- 最近m条分支指令的全局历史记录在一个m位移位寄存器中，每一位记录看该分支指令是转移还是未转移
锦标预测器
- 合金预测器：结合局部分支历史和全局分支历史
- 锦标预测器：自适应结合局部预测器和全局预测器
问题：错误预测时需要改变全局预测器、局部预测器和预测器
标记混合预测器
最好的分支预测方法时组合多个预测器
-
多个预测器：跟踪预测是否可能与当前分支相关
-
问题：意味着巨大的数据表
部分匹配预测法 PPM
标记混合预测器
- 一类基于 PPM 思路的分支预测器
- 使用一组使用不同长度历史所以的全局预测器
预测器初始化问题
- 随机初始化
- 设置有效位
- 根据分支方向设置初始预测
动态调度
静态调度（最小化停顿）
- 取指令——发指令
- 如果存在数据相关，且旁路或向前不能解决
- 危害检测硬件从使用结果指令开始停顿
动态调度（避免停顿）
在维持数据流和中断行为的同时，硬件重新排列指令执行顺序以减少停顿
特点
- 代码编译不考虑微体系结构
- 能够处理编译时处理不了的相关性的一些情况
- 允许处理器容忍延迟
- 硬件复杂性提高
动态调度意味着
- 乱序执行
- 乱序完成
拆分 ID 流水段为两部分
- 发出：译码、检测结构危害
- 读操作数：等待数据危害的小时，读取操作数
特点
- 保持按序发出
- 能够乱序执行，暗示乱序完成
乱序执行：一旦指令的操作数有效则马上开始执行
乱序执行
- 乱序完成可能导致不精确中断
- 不精确中断：当发生中断时处理器状态看起来不完全像指令以严格程序次序顺序执行的结果
- 流水线中已经完成的指令在程序次序上比引起中断的指令晚
- 还未完成的指令在程序次序上比引起中断的指令早