第十章 依赖于机器的优化 在指令级并行的机器上，程序的运行速度依 赖于下面几个因素 程序中潜在的并行 处理器上可用的并行 从串行程序提取并行的能力 在给定的调度约束下发现最佳并行调度的能力 并行的提取和并行执行的调度都可以静态地 在软件中或动态地在硬件中完成
第十章 依赖于机器的优化 • 在指令级并行的机器上，程序的运行速度依 赖于下面几个因素 – 程序中潜在的并行 – 处理器上可用的并行 – 从串行程序提取并行的能力 – 在给定的调度约束下发现最佳并行调度的能力 • 并行的提取和并行执行的调度都可以静态地 在软件中或动态地在硬件中完成
第十章 依赖于机器的优化 本章内容 使用指令级并行的基础问题 提取并行的数据相关性分析 代码调度的基本概念 基本块调度的技术、发现通用程序中的高度数据 相关控制流的方法、调度数值程序的软件流水线 技术 在多处理器系统上，使用数组的计算密集型程序 的并行化和数据局部性优化的概念和方法
第十章 依赖于机器的优化 • 本章内容 – 使用指令级并行的基础问题 – 提取并行的数据相关性分析 – 代码调度的基本概念 – 基本块调度的技术、发现通用程序中的高度数据 相关控制流的方法、调度数值程序的软件流水线 技术 – 在多处理器系统上，使用数组的计算密集型程序 的并行化和数据局部性优化的概念和方法
10.1处理器体系结构 在考虑指令级并行时，通常想象成一个处理 器在单个时钟周期内发射几个操作 事实上，在每周期内发射一个操作是可能的： 而指令级并行的获得是通过使用流水线技术 本节先解释流水线，然后讨论多指令发射
10.1 处理器体系结构 • 在考虑指令级并行时，通常想象成一个处理 器在单个时钟周期内发射几个操作 • 事实上，在每周期内发射一个操作是可能的, 而指令级并行的获得是通过使用流水线技术 • 本节先解释流水线，然后讨论多指令发射
10.1处理器体系结构 10.1.1指令流水线和分支延迟 i+1 i+2 i+3 i+4 1. F 5级指令流水线中 2. D F 的5条连续指令 3. EX D 4. MEM EX D 5. WB MEM EX 6. WB MEM EX D 7. WB MEM EX 8. 取指令F,译码D,执行操作EX, WB MEM 9. 访问内存MEM,回写结果WB WB
10.1 处理器体系结构 10.1.1 指令流水线和分支延迟 i i + 1 i + 2 i + 3 i + 4 1. IF 2. ID IF 3. EX ID IF 4. MEM EX ID IF 5. WB MEM EX ID IF 6. WB MEM EX ID 7. WB MEM EX 8. WB MEM 9. WB 取指令IF, 译码ID, 执行操作EX, 访问内存MEM, 回写结果WB 5级指令流水线中 的5条连续指令
10.1处理器体系结构 10.1.1指令流水线和分支延迟 分支延迟 发现应该执行一个分支而不是直接后继 转向一个分支时会引起取分支目的地址指令的延 迟并引起指令流水线“打嗝” 可以通过使用硬件，根据分支的执行历史来预测 分支结果并从预测的目的地址预取指令 分支延迟不可避免，因为分支预测会发生偏差
10.1 处理器体系结构 10.1.1 指令流水线和分支延迟 • 分支延迟 – 发现应该执行一个分支而不是直接后继 – 转向一个分支时会引起取分支目的地址指令的延 迟并引起指令流水线“打嗝” – 可以通过使用硬件，根据分支的执行历史来预测 分支结果并从预测的目的地址预取指令 – 分支延迟不可避免，因为分支预测会发生偏差
10.1处理器体系结构 10.1.2流水化的执行 如果不依赖一条指令结果的随后指令在该结 果产生前就被允许执行 有些指令的执行需要几个周期，几个操作同时出 现在它们的执行级上可能的 如果最长的执行流水线是n级，n个操作同时进行 的可能性是存在的 并非所有的指令都能被完全流水化，例如浮点除 通用处理器大都动态察觉相继指令之间的依赖性 嵌入式系统把数据相关性的检查交给软件
10.1 处理器体系结构 10.1.2 流水化的执行 如果不依赖一条指令结果的随后指令在该结 果产生前就被允许执行 – 有些指令的执行需要几个周期，几个操作同时出 现在它们的执行级上可能的 – 如果最长的执行流水线是n级，n个操作同时进行 的可能性是存在的 – 并非所有的指令都能被完全流水化，例如浮点除 – 通用处理器大都动态察觉相继指令之间的依赖性 – 嵌入式系统把数据相关性的检查交给软件
10.1处理器体系结构 10.1.3多指令发射 每周期发射几个操作，让更多操作同时进行 超长指令字机器 将若干个操作编码在单周期中发射 编译器需要确定哪些操作可以并行发射 超标量机器 超标量机器有按普通顺序执行语义的正规指令集 硬件自动察觉指令之间的相关性，并且在它们的 操作数可用时就发射它们 更复杂的调度器能够“乱序”执行指令
10.1 处理器体系结构 10.1.3 多指令发射 每周期发射几个操作，让更多操作同时进行 • 超长指令字机器 – 将若干个操作编码在单周期中发射 – 编译器需要确定哪些操作可以并行发射 • 超标量机器 – 超标量机器有按普通顺序执行语义的正规指令集 – 硬件自动察觉指令之间的相关性，并且在它们的 操作数可用时就发射它们 – 更复杂的调度器能够“乱序”执行指令
10.2代码调度的约束 代码调度 -用在代码生成器产生的机器代码上的优化技术 本节讨论代码调度的约束 控制相关约束 在原程序中执行的所有操作都 必须在优化代码中执行 数据相关约束 优化程序中的操作产生的结果 必须同原程序对应操作的结果一样 资源约束 调度不能过分占用机器的资源 优化程序很难调试 内存状态可能和顺序执行的任何内存状态不匹配
10.2 代码调度的约束 • 代码调度 – 用在代码生成器产生的机器代码上的优化技术 • 本节讨论代码调度的约束 – 控制相关约束 在原程序中执行的所有操作都 必须在优化代码中执行 – 数据相关约束 优化程序中的操作产生的结果 必须同原程序对应操作的结果一样 – 资源约束 调度不能过分占用机器的资源 • 优化程序很难调试 – 内存状态可能和顺序执行的任何内存状态不匹配
10.2代码调度的约束 10.2.1数据相关 真相关 如果对同一个单元先写后读，那么 读依赖于所写的值 反相关 如果对同一个单元先读后写。可以 通过把值存在不同的单元来删除反相关 输出相关 如果对同一个单元先后写两次。也 可删除 数据相关概念可同时用于内存访问和寄存器 访问
10.2 代码调度的约束 10.2.1 数据相关 – 真相关 如果对同一个单元先写后读，那么 读依赖于所写的值 – 反相关 如果对同一个单元先读后写。可以 通过把值存在不同的单元来删除反相关 – 输出相关 如果对同一个单元先后写两次。也 可删除 • 数据相关概念可同时用于内存访问和寄存器 访问
10.2代码调度的约束 10.2.2发现内存访问中的相关性 。例 (1)a=1 (2)*p=2 (3) x=a -语句1)和(2)可能构成输出相关 -语句1)和(3)可能构成真相关 -语句(2)和3)可能构成真相关 除非编译器知道p不可能指向a,否则3个操作必 须串行执行
10.2 代码调度的约束 10.2.2 发现内存访问中的相关性 • 例 (1) a = 1 (2) p = 2 (3) x = a – 语句(1)和(2)可能构成输出相关 – 语句(1)和(3)可能构成真相关 – 语句(2)和(3)可能构成真相关 – 除非编译器知道p不可能指向a，否则3个操作必 须串行执行