《计算机系统结构》电子教案(课7).ppt

2014 2 17 计算机系统结构 1 第6章指令级并行软件方法 指令级 多发射或乱序执行 静态调度 本章学习由软件 即编译程序 实现的指令级并行方法 主要内容是如何修改 优化已编译完的目标程序 以减少指令间冲突造成的停顿 缩短程序执行时间 6 1基本指令调度及循环展开6 5开发更多的指令级并行 2014 2 17 计算机系统结构 2 教材P154第一段说可以采用图3 17的5段整数流水线 下图a 来讨论本节 本章 的整数 浮点数混合运算程序 实际上解释不通 我们改用下图b的整数 浮点分离的流水线结构来讨论 第6章采用的流水线模型 整数ALU浮点ALU b 实际可用的流水线结构 整数 浮点共用ALU a 图3 17流水线结构 P71 WB MEM IF ID F0 F1 F2 F3 WB MEM EX IF ID WB MEM EX 2014 2 17 计算机系统结构 3 3 4 1 2 1 采用P90图3 33的优化流水线方案 相关指令之间采用定向技术 包括前 后半周期定向 以减少停顿 在ID段处理分支指令 分支停顿为1个时钟周期 采用延迟分支技术 设1个延迟槽 2 相关浮点指令之间的停顿 浮点数在 执行 段需4拍 其它段为1拍 两条相关的浮点指令之间的最少停顿周期数如下表 即教材P153表6 1 第6章采用的流水线模型 IF ID F0 Mem WB IF ID EX Mem WB F1 F2 F3 IF ID F0 Mem WB F1 F2 F3 IF ID F0 Mem WB F1 F2 F3 IF ID EX Mem WB IF ID F0 Mem WB F1 F2 F3 IF ID EX Mem WB IF ID EX Mem WB 2014 2 17 计算机系统结构 4 6 1 1指令调度方法基本原理是按两条相关指令之间所需的最小启动距离将它们隔开 在二者之间安排其它的无关指令 减少直至消除流水线停顿 例6 1 P154 将如下C语言源程序编译成MIPS目标代码 然后使用指令调度技术 延迟分支技术优化其代码性能 指缩短运行时间 for i 1000 i 0 i x i x i s 解 1 初步编译结果如下Loop L DF0 0 R1 F0 1个向量元素ADD DF4 F0 F2 F4 F0 F2 即标量s S DF4 0 R1 F4存回向量元素DADDIUR1 R1 8 R1 R1 8 指向前1个元素 长浮点 BNER1 R2 Loop 若R1 R2 转Loop 6 1基本指令调度及循环展开 2014 2 17 计算机系统结构 5 调度前的相关链分析 代码性能 每轮循环完成1个浮点元素运算 需10拍 其中5拍是空转 6 1基本指令调度及循环展开 2014 2 17 计算机系统结构 6 模拟软件Cycles图 模拟结果比分析结果多1拍的原因在于模拟器的流水线存在 结构冲突 6 1基本指令调度及循环展开 2014 2 17 计算机系统结构 7 2 调度 延迟分支后的相关链分析 注意S D指令需要修改offset值 代码性能 每轮循环完成1个浮点元素运算 需6拍 其中1拍是空转 模拟软件Cycles图 6 1基本指令调度及循环展开 2014 2 17 计算机系统结构 8 从有效操作比例看 刚才的例子中每个浮点元素运算中使用3条有效指令 附加2条循环控制指令 辅助操作占了太高的比例 循环展开的目的一是降低辅助操作的比例 二是通过合并来增加每个循环体中的指令条数 使指令调度有更大的调整范围 优化效果更好 例6 2 P155 将例6 1未优化程序展开3次得到4个循环体 然后使用指令调度技术 延迟分支技术优化其代码性能 假设原循环次数是4的整倍数 解 先讨论几个注意事项 如果各轮循环之间不存在相关 展开后可以简单并行 否则需处理 如果原循环次数N 展开倍数M K K是整数 则新的循环次数K N M 否则要在循环结束之后增加补偿代码来完成剩余的操作 原来多轮循环重复使用的寄存器 合并之后必须通过重命名来区分 否则发生名相关 限制并行性 原来各轮循环中的循环控制指令 合并后可以减少 6 1 2循环展开方法 2014 2 17 计算机系统结构 9 1 展开后没有调度的程序如下Loop L DF0 0 R1 F0 x i 取数 ADD DF4 F0 F2 F4 F0 F2S DF4 0 R1 x i F4 存结果 L DF6 8 R1 F6 x i 1 取数 ADD DF8 F6 F2 F8 F6 F2S DF8 8 R1 x i 1 F8 存结果 L DF10 16 R1 F10 x i 2 取数 ADD DF12 F10 F2 F12 F10 F2S DF12 16 R1 x i 2 F12 存结果 L DF14 24 R1 F14 x i 3 取数 ADD DF16 F14 F2 F16 F14 F2S DF16 24 R1 x i 3 F16 存结果 DADDIUR1 R1 32 R1 R1 4 8 指针前移4个数 BNER1 R2 Loop 若R1 R2 循环 例6 2 P155 2014 2 17 计算机系统结构 10 调度前的相关链分析 未完 接下页 例6 2 续1 2014 2 17 计算机系统结构 11 代码性能 每轮循环完成4个浮点元素运算 共28拍 其中14拍是空转 折算每个浮点元素运算使用28 4 7拍 展开前10拍 其中3 5拍是空转 例6 2 续2 2014 2 17 计算机系统结构 12 2 展开后经过调度优化的程序如下loop L DF0 0 R1 F0 x i 取数 L DF6 8 R1 F6 x i 1 取数 L DF10 16 R1 F10 x i 2 取数 L DF14 24 R1 F14 x i 3 取数 ADD DF4 F0 F2 F4 F0 F2ADD DF8 F6 F2 F8 F6 F2 ADD DF12 F10 F2 F12 F10 F2 ADD DF16 F14 F2 F16 F14 F2S DF4 0 R1 x i F4 存结果 S DF8 8 R1 x i 1 F8 存结果 DADDUIR1 R1 32 R1 R1 4 8 指针前移4个数 S DF12 16 R1 x i 2 4 F12 存结果 指针 32 BNER1 R2 loop 若R1 R2 循环S DF16 8 R1 x i 3 4 F16 存结果 指针 32 例6 2 续3 2014 2 17 计算机系统结构 13 调度后的相关链分析 例6 2 续4 代码性能 每个浮点元素运算使用14 4 3 5拍 无空转 2014 2 17 计算机系统结构 14 习题改写 原题意思不清 以下向量点积循环段在教材图3 33所示改进流水线上运行 浮点运算延迟符合教材表6 1规定 F2的初值为0 loop L DF0 0 R1 L DF4 0 R2 MUL DF0 F0 F4ADD DF2 F0 F2DADDUIR1 R1 8DADDUIR2 R2 8 原题错写为R1 BNER1 R3 loop 1 使用循环展开和指令调度改造程序 结果含3个循环体 使 空转 周期数不超过1个 写出新程序 2 手工计算原程序处理每对元素所需的时钟周期数 其中的空转数 3 手工计算新程序处理每对元素所需的时钟周期数 其中的空转数 习题6 8 2014 2 17 计算机系统结构 15 4 用WinMIPS64模拟器依次运行原程序 新程序 测试 2 3 步的对应结果 最好打印Cycles图 5 分析模拟过程 你能找出哪些造成测试结果与手工计算结果不一致的原因 习题6 8 续 2014 2 17 计算机系统结构 16 前几大节基本解决了分支程序的控制相关问题 本大节重点讨论循环程序中的数据相关问题 对编译之前的源代码进行识别 优化更容易 6 5 1挖掘更多的循环级并行本小节重点讨论不同次循环迭代之间的相关 1 循环携带相关定义 不同次循环迭代之间的相关 影响 如果原始程序内存在循环携带相关 则在循环展开后 指令不能在各轮循环之间任意调动 这就大大限制了优化操作的效果发挥 6 5开发更多的指令级并行 2014 2 17 计算机系统结构 17 for i 1 i 100 i i 1 A i 1 A i C i S1 B i 1 B i A i 1 S2 假设数组A B和C中所有元素的存储地址都互不相同 请问语句S1与S2之间存在哪些数据相关 解 1 循环迭代内相关 蓝色箭头 2 循环携带相关 红色箭头 例6 7 P173 2014 2 17 计算机系统结构 18 进一步讨论循环展开的结果 以展开1次为例 for i 1 i 100 i i 2 A i 1 A i C i S1 来自第1个迭代 B i 1 B i A i 1 S2 来自第1个迭代 A i 2 A i 1 C i 1 S3 来自第2个迭代 B i 2 B i 1 A i 2 S4 来自第2个迭代 这时如果因为S1 S2相关造成停顿 需要在它们之间插入一条语句的话 插入S3仍有同样的相关 S4则不能调至S3之前 实际上无语句可调 由此例可以看出 循环迭代内相关是局部性限制 不影响指令在大范围内移动 循环携带相关是全局性限制 影响了指令在大范围内移动 所以需要寻找消除循环携带相关的方法 例6 7解 续 2014 2 17 计算机系统结构 19 有一类循环携带相关可以修改为循环内相关 例如for i 1 i 100 i i 1 A i A i B i S1 B i 1 C i D i S2 解 其特征是本轮循环的一条语句与下轮循环的另一条语句相关 这种情况不构成连续的相关链 可以把相关的两条语句重新组合到同一轮循环中A 1 A 1 B 1 for i 1 i 99 i i 1 B i 1 C i D i 原来的S2 A i 1 A i 1 B i 1 原来的S1 B 101 C 100 D 100 以后就可以顺利地进行循环展开 相关链分析见下页 例6 8 P173 2014 2 17 计算机系统结构 20 例6 8 续 2014 2 17 计算机系统结构 21 显式相关与隐式相关同一变量名出现在多条语句中是显式相关 可通过字符匹配来识别同一数组元素以不同的存储别名出现在多条语句中是隐式相关 不能通过简单的字符匹配来识别什么是存储别名一个元素被不同的地址表达式访问 如A i 5 A j 2 6 A k 由于编译时难以预测索引变量i j k将来的运行值 故疑似存储别名一律作相关看待 所在语句之间必须保持足够距离 避免并行执行存储别名判则适用条件 数组是仿射的 affine 仿射数组 访问地址表达式均为一次函数 形如A a i b j c 非仿射数组 例如A B i 2 存储别名导致的隐式相关 GCD判则 2014 2 17 计算机系统结构 22 GCD判则 最大公因数 GreatestCommonDivisor 问题给定一维数组A m n 和任意整数j k m j k n 地址表达式A a j b 与A c k d 有没有可能是同一个元素 即什么条件下满足a j b c k d判则如果GCD c a 可以整除 d b 可能存在存储别名 疑似相关 如果GCD测试的结果为假 不能整除 一定不存在存储别名判则之所以说 可能存在 是因为目标程序在运行中 j k的实际取值范围也可能到不了满足a j b c k d的点 2 存储别名导致的隐式相关 GCD判则 2014 2 17 计算机系统结构 23 例 6j 13与9k 1是否满足GCD判则 解 GCD c a 3 d b 12 能够整除 可能存在存储别名验证 对取值j 0 1 2 和k 0 1 2 有6j 13 13 19 25 31 37 43 49 55 61 9k 1 1 10 19 28 37 46 55 64 73 显然存在存储别名 将b和d互换后也一样 这时 d b 12 6j 1 1 7 13 19 25 31 37 43 49 9k 13 13 22 31 40 49 58 67 76 85 GCD判则成功的例子 2014 2 17 计算机系统结构 24 例 4j 1与2k 4是否满足GCD判则 解 GCD c a 2 d b 3 不能整除 不存在存储别名验证 对取值j 0 1 2 和k 0 1 2 有4j 1 1 5 9 13 17 21 25 29 33 2k 4 4 6 8 10 12 14 16 18 20 未发现存储别名 将b和d互换后也一样 验证略 GCD判则失败的例子 2014 2 17 计算机系统结构 25 例6 9 P175 使用GCD测试方法判断下面的循环中是否存在存储别名 for i 1 i 100 i i 1 x 2 i 3 x 2 i 5 0 解 在这个循环中 a 2 b 3 c 2 d 0 那么GCD a c 2 而d b 3 由于2不能整除 3 因此没有存储别名 即无论i取何值 x 2 i 3 与x 2 i 都将表示数组x的不同元素 GCD判则失败的例子 2014 2 17 计算机系统结构 26 在使用GCD测试之前 必须先对这段代码进行 规范化 修改下标从1开始 不必要 而且每次循环后增加1 Hennessy教材3版第4章 例如 学习指导书 题6 15原循环代码为for i 2 i 100 i 2 a