《计算机系统结构》电子教案(课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;i0;i- -) xi=xi+s; 解： (1)初步编译结果如下 Loop： L.D F0, 0(R1) /F01个向量元素 ADD.D F4, F0, F2 /F4F0+F2（即标量s） S.D F4, 0(R1) /F4存回向量元素 DADDIU R1, R1, #-8 /R1R1-8（指向前1个元素，长浮点） BNE R1, R2, Loop /若R1R2，转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=展开倍数MK（K是整数），则新的循环次数K=N/M，否则要在循环结束之后增加补偿代码来完成剩余的操作； 原来多轮循环重复使用的寄存器，合并之后必须通过重命名来区分，否则发生名相关，限制并行性； 原来各轮循环中的循环控制指令，合并后可以减少。,6.1.2 循环展开方法,2014.2.17,计算机系统结构,9,(1)展开后没有调度的程序如下 Loop: L.D F0, 0(R1) ;F0 xi（取数） ADD.D F4, F0, F2 ;F4 F0 + F2 S.D F4, 0(R1) ;xi F4（存结果） L.D F6, -8(R1) ;F6 xi-1（取数） ADD.D F8, F6, F2 ;F8 F6 + F2 S.D F8, -8(R1) ;xi-1 F8（存结果） L.D F10,-16(R1) ;F10 xi-2（取数） ADD.D F12, F10, F2 ;F12 F10 + F2 S.D F12, -16(R1) ;xi-2 F12（存结果） L.D F14, -24(R1) ;F14 xi-3（取数） ADD.D F16, F14, F2 ;F16 F14 + F2 S.D F16, -24(R1) ;xi-3 F16（存结果） DADDIU R1, R1, #-32 ;R1 R1 - 48（指针前移4个数） BNE R1, R2, Loop ;若 R1R2，循环,例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.D F0, 0(R1) ;F0 xi（取数） L.D F6, -8(R1) ;F6 xi-1（取数） L.D F10,-16(R1) ;F10 xi-2（取数） L.D F14,-24(R1) ;F14 xi-3（取数） ADD.D F4, F0, F2 ;F4 F0 + F2 ADD.D F8, F6, F2 ;F8 F6 + F2） ADD.D F12, F10, F2 ;F12 F10 + F2） ADD.D F16, F14, F2 ;F16 F14 + F2 S.D F4, 0(R1) ;xi F4（存结果） S.D F8, -8(R1) ;xi-1 F8（存结果） DADDUI R1, R1, -32 ;R1 R1 - 48（指针前移4个数） S.D F12, 16(R1) ;xi-2+4 F12（存结果，指针+32） BNE R1, R2, loop ;若 R1R2，循环 S.D F16, 8(R1) ;xi-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.D F0, 0(R1) L.D F4, 0(R2) MUL.D F0, F0, F4 ADD.D F2, F0, F2 DADDUI R1, R1, #-8 DADDUI R2, R2, #-8（原题错写为R1） BNE R1, 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) Ai+1=Ai+Ci; /*S1*/ Bi+1=Bi+Ai+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) Ai+1=Ai+Ci; /*S1，来自第1个迭代*/ Bi+1=Bi+Ai+1; /*S2，来自第1个迭代*/ Ai+2=Ai+1+Ci+1; /*S3，来自第2个迭代*/ Bi+2=Bi+1+Ai+2; /*S4，来自第2个迭代*/ 这时如果因为S1、S2相关造成停顿，需要在它们之间插入一条语句的话，插入S3仍有同样的相关，S4则不能调至S3之前。实际上无语句可调。 由此例可以看出： 循环迭代内相关是局部性限制，不影响指令在大范围内移动； 循环携带相关是全局性限制，影响了指令在大范围内移动。 所以需要寻找消除循环携带相关的方法。,例6.7解（续）,2014.2.17,计算机系统结构,19,有一类循环携带相关可以修改为循环内相关，例如 for(i=1;i=100;i=i+1) Ai=Ai+Bi; /*S1*/ Bi+1=Ci+Di; /*S2*/ 解： 其特征是本轮循环的一条语句与下轮循环的另一条语句相关，这种情况不构成连续的相关链，可以把相关的两条语句重新组合到同一轮循环中 A1=A1+B1; for(i=1;i=99;i=i+1) Bi+1=Ci+Di; /*原来的S2*/ Ai+1=Ai+1+Bi+1; /*原来的S1*/ B101=C100+D100; 以后就可以顺利地进行循环展开。相关链分析见下页。,例6.8（P173）,2014.2.17,计算机系统结构,20,例6.8（续）,2014.2.17,计算机系统结构,21,显式相关与隐式相关 同一变量名出现在多条语句中是显式相关，可通过字符匹配来识别 同一数组元素以不同的存储别名出现在多条语句中是隐式相关，不能通过简单的字符匹配来识别 什么是存储别名 一个元素被不同的地址表达式访问，如 Ai+5、Aj2-6、Ak 由于编译时难以预测索引变量i、j、k将来的运行值，故疑似存储别名一律作相关看待，所在语句之间必须保持足够距离，避免并行执行 存储别名判则适用条件数组是仿射的（affine） 仿射数组：访问地址表达式均为一次函数，形如Aai+bj+c 非仿射数组：例如ABi,2. 存储别名导致的隐式相关（GCD判则）,2014.2.17,计算机系统结构,22,GCD判则（最大公因数，Greatest Common Divisor） 问题 给定一维数组Am:n和任意整数j、k（mj，kn），地址表达式 Aaj+b 与 Ack+d 有没有可能是同一个元素，即什么条件下满足aj+b = ck+d 判则 如果GCD(c,a)可以整除(d-b)，可能存在存储别名（疑似相关） 如果GCD测试的结果为假（不能整除），一定不存在存储别名 判则之所以说“可能存在”，是因为目标程序在运行中，j、k的实际取值范围也可能到不了满足aj+b = ck+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测试方法判断下面