《计算机系统结构电子教案优秀课件》由会员分享，可在线阅读，更多相关《计算机系统结构电子教案优秀课件（28页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 指令级并行软件方法指令级并行软件方法（指令级，多发射或乱序执行，静态调度）指令级，多发射或乱序执行，静态调度）本章学习由软件（即编译程序）实现的指令级并行方法，主要内容本章学习由软件（即编译程序）实现的指令级并行方法，主要内容是如何修改、优化已编译完的目标程序，以减少指令间冲突造成的停顿，是如何修改、优化已编译完的目标程序，以减少指令间冲突造成的停顿，缩短程序执行时间。缩短程序执行时间。6.1 6.1 基本指令调度及循环展开基本指令调度及循环展开6.5 6.5 开发更多的指令级并行开发更多的指令级并行2014.2.171计算机系统结构电子教案优秀教材教材P154P154第一段说
2、可以采用图第一段说可以采用图3.173.17的的5 5段整数流水线段整数流水线（下图下图a a）来讨论来讨论本节（本章）的整数、浮点数混合运算程序，实际上解释不通，我们改用本节（本章）的整数、浮点数混合运算程序，实际上解释不通，我们改用下图下图b b的整数、浮点分离的流水线结构来讨论的整数、浮点分离的流水线结构来讨论。 第第6 6章采用的流水线模型章采用的流水线模型整数整数ALU浮点浮点ALU(b) 实际可用的流水线结构实际可用的流水线结构整数、浮点共用整数、浮点共用ALU(a) 图图3.17流水线结构（流水线结构（P71 ）WBMEMIFIDF0F1F2F3WBMEMEXIFIDWBMEME
3、X2014.2.172计算机系统结构电子教案优秀(3) (3) (4) (4)(1) (1) (2) (2)(1) (1) 采用采用P90P90图图3.333.33的优化流水线方案：的优化流水线方案： 相关指令之间采用定向技术（包括前、后半周期定向），以减少停顿；相关指令之间采用定向技术（包括前、后半周期定向），以减少停顿； 在在IDID段处理分支指令，分支停顿为段处理分支指令，分支停顿为1 1个时钟周期；个时钟周期； 采用延迟分支技术，设采用延迟分支技术，设1 1个延迟槽。个延迟槽。(2) (2) 相关浮点指令之间的停顿：浮点数在相关浮点指令之间的停顿：浮点数在“执行执行”段需段需4 4拍，
4、其它段为拍，其它段为1 1拍。拍。两条相关的浮点指令之间的最少停顿周期数如下表（即教材两条相关的浮点指令之间的最少停顿周期数如下表（即教材P153P153表表6.16.1） 第第6 6章采用的流水线模型章采用的流水线模型IFIFIDIDF0F0MemMemWBWBIFIFIDIDEXEXMemMemWBWBF1F1F2F2F3F3IFIFIDIDF0F0MemMemWBWBF1F1F2F2F3F3IFIFIDIDF0F0MemMemWBWBF1F1F2F2F3F3IFIFIDIDEXEXMemMemWBWBIFIFIDIDF0F0MemMemWBWBF1F1F2F2F3F3IFIFIDIDEX
5、EXMemMemWBWBIFIFIDIDEXEXMemMemWBWB2014.2.173计算机系统结构电子教案优秀6.1.1 6.1.1 指令调度方法指令调度方法基本原理是按两条相关指令之间所需的最小启动距离将它们隔开，在基本原理是按两条相关指令之间所需的最小启动距离将它们隔开，在二者之间安排其它的无关指令，减少直至消除流水线停顿。二者之间安排其它的无关指令，减少直至消除流水线停顿。例例6.16.1（P154P154）：）：将如下将如下C C语言源程序编译成语言源程序编译成MIPSMIPS目标代码，然后使用指令目标代码，然后使用指令调度技术、延迟分支技术优化其代码性能（指缩短运行时间）。调度技
6、术、延迟分支技术优化其代码性能（指缩短运行时间）。 for(i=1000;i0;i- for(i=1000;i0;i- -)-) xi=xi+s; xi=xi+s;解：解：(1)(1)初步编译结果如下初步编译结果如下LoopLoop： L.D F0, 0(R1) /F01 L.D F0, 0(R1) /F01个向量元素个向量元素 ADD.D F4, F0, F2 /F4F0+F2ADD.D F4, F0, F2 /F4F0+F2（即标量即标量s s） S.D F4, 0(R1) /F4 S.D F4, 0(R1) /F4存回向量元素存回向量元素 DADDIU R1, R1, #-8 /R1R1
7、-8DADDIU R1, R1, #-8 /R1R1-8（指向前指向前1 1个元素，长浮点）个元素，长浮点） BNE R1, R2, Loop /BNE R1, R2, Loop /若若R1R2R1R2，转转LoopLoop6.1 6.1 基本指令调度及循环展开基本指令调度及循环展开2014.2.174计算机系统结构电子教案优秀调度前的调度前的相关链分析相关链分析 ：代码性能：每轮循环完成代码性能：每轮循环完成1个浮点元素运算，需个浮点元素运算，需10拍，其中拍，其中5拍是空转。拍是空转。6.1 6.1 基本指令调度及循环展开基本指令调度及循环展开2014.2.175计算机系统结构电子教案优秀
8、模拟软件模拟软件CyclesCycles图：图：模拟结果比分析结果多模拟结果比分析结果多1 1拍的原因在于模拟器的流水线存在拍的原因在于模拟器的流水线存在“结构冲突结构冲突”。6.1 6.1 基本指令调度及循环展开基本指令调度及循环展开2014.2.176计算机系统结构电子教案优秀(2) (2) 调度、延迟分支后的相关链分析调度、延迟分支后的相关链分析 ( (注意注意S.DS.D指令需要修改指令需要修改offsetoffset值值) )：代码性能：每轮循环完成代码性能：每轮循环完成1 1个浮点元素运算，需个浮点元素运算，需6 6拍，其中拍，其中1 1拍是空转。拍是空转。模拟软件模拟软件Cycl
9、esCycles图：图：6.1 6.1 基本指令调度及循环展开基本指令调度及循环展开2014.2.177计算机系统结构电子教案优秀从有效操作比例看，刚才的例子中每个浮点元素运算中使用从有效操作比例看，刚才的例子中每个浮点元素运算中使用3 3条有效指条有效指令，附加令，附加2 2条循环控制指令，辅助操作占了太高的比例。条循环控制指令，辅助操作占了太高的比例。循环展开的目的一是降低辅助操作的比例，二是通过合并来增加每个循环展开的目的一是降低辅助操作的比例，二是通过合并来增加每个循环体中的指令条数，使指令调度有更大的调整范围，优化效果更好。循环体中的指令条数，使指令调度有更大的调整范围，优化效果更好
10、。例例6.26.2（P155P155）：）：将例将例6.16.1未优化程序展开未优化程序展开3 3次得到次得到4 4个循环体，然后使用指个循环体，然后使用指令调度技术、延迟分支技术优化其代码性能。假设原循环次数是令调度技术、延迟分支技术优化其代码性能。假设原循环次数是4 4的整倍数。的整倍数。解：先讨论几个注意事项。解：先讨论几个注意事项。 如果各轮循环之间不存在相关，展开后可以简单并行，否则需处理；如果各轮循环之间不存在相关，展开后可以简单并行，否则需处理； 如果原循环次数如果原循环次数N N= =展开倍数展开倍数M MK K（K K是整数）是整数），则新的循环次数则新的循环次数K=N/MK
11、=N/M，否则要在循环结束之后增加补偿代码来完成剩余的操作；否则要在循环结束之后增加补偿代码来完成剩余的操作； 原来多轮循环重复使用的寄存器，合并之后必须通过重命名来区分，否原来多轮循环重复使用的寄存器，合并之后必须通过重命名来区分，否则发生名相关，限制并行性；则发生名相关，限制并行性； 原来各轮循环中的循环控制指令，合并后可以减少。原来各轮循环中的循环控制指令，合并后可以减少。6.1.2 6.1.2 循环展开方法循环展开方法2014.2.178计算机系统结构电子教案优秀(1)(1)展开后没有调度的程序如下展开后没有调度的程序如下Loop: L.D F0, 0(R1) ;F0 xiLoop:
12、L.D F0, 0(R1) ;F0 xi（取数）取数） ADD.D F4, F0, F2 ;F4 F0 + F2ADD.D F4, F0, F2 ;F4 F0 + F2 S.D F4, 0(R1) ;xi F4 S.D F4, 0(R1) ;xi F4（存结果）存结果） L.D F6, -8(R1) ;F6 xi-1L.D F6, -8(R1) ;F6 xi-1（取数）取数） ADD.D F8, F6, F2 ;F8 F6 + F2ADD.D F8, F6, F2 ;F8 F6 + F2 S.D F8, -8(R1) ;xi-1 F8 S.D F8, -8(R1) ;xi-1 F8（存结果）存
13、结果） L.D F10,-16(R1) ;F10 xi-2L.D F10,-16(R1) ;F10 xi-2（取数）取数） ADD.D F12, F10, F2 ;F12 F10 + F2ADD.D F12, F10, F2 ;F12 F10 + F2 S.D F12, -16(R1) ;xi-2 F12 S.D F12, -16(R1) ;xi-2 F12（存结果）存结果） L.D F14, -24(R1) ;F14 xi-3L.D F14, -24(R1) ;F14 xi-3（取数）取数） ADD.D F16, F14, F2 ;F16 F14 + F2ADD.D F16, F14, F2
14、 ;F16 F14 + F2 S.D F16, -24(R1) ;xi-3 F16 S.D F16, -24(R1) ;xi-3 F16（存结果）存结果） DADDIU R1, R1, #-32 ;R1 R1 - 48DADDIU R1, R1, #-32 ;R1 R1 - 48（指针前移指针前移4 4个数）个数） BNE R1, R2, Loop ;BNE R1, R2, Loop ;若若 R1R2R1R2，循环循环例例6.26.2（P155P155）2014.2.179计算机系统结构电子教案优秀调度前的调度前的相关链分析相关链分析 （未完，接下页）：（未完，接下页）：例例6.26.2（续（
15、续1 1）2014.2.1710计算机系统结构电子教案优秀代码性能：每轮循环完成代码性能：每轮循环完成4个浮点元素运算，共个浮点元素运算，共28拍，其中拍，其中14拍是空转。折拍是空转。折算每个浮点元素运算使用算每个浮点元素运算使用28/4=7拍（展开前拍（展开前10拍），其中拍），其中3.5拍是空转。拍是空转。例例6.26.2（续（续2 2）2014.2.1711计算机系统结构电子教案优秀(2)(2)展开后经过调度优化的程序如下展开后经过调度优化的程序如下loop: L.D F0, 0(R1) ;F0 xiloop: L.D F0, 0(R1) ;F0 xi（取数）取数） L.D F6, -
16、8(R1) ;F6 xi-1L.D F6, -8(R1) ;F6 xi-1（取数）取数） L.D F10,-16(R1) ;F10 xi-2L.D F10,-16(R1) ;F10 xi-2（取数）取数） L.D F14,-24(R1) ;F14 xi-3L.D F14,-24(R1) ;F14 xi-3（取数）取数） ADD.D F4, F0, F2 ;F4 F0 + F2ADD.D F4, F0, F2 ;F4 F0 + F2 ADD.D F8, F6, F2 ;F8 F6 + F2 ADD.D F8, F6, F2 ;F8 F6 + F2） ADD.D F12, F10, F2 ;F12
17、 F10 + F2 ADD.D F12, F10, F2 ;F12 F10 + F2） ADD.D F16, F14, F2 ;F16 F14 + F2 ADD.D F16, F14, F2 ;F16 F14 + F2 S.D F4, 0(R1) ;xi F4 S.D F4, 0(R1) ;xi F4（存结果）存结果） S.D F8, -8(R1) ;xi-1 F8S.D F8, -8(R1) ;xi-1 F8（存结果）存结果） DADDUI R1, R1, -32 ;R1 R1 - 48DADDUI R1, R1, -32 ;R1 R1 - 48（指针前移指针前移4 4个数）个数） S.D
18、F12, 16(R1) ;xi-2+4 F12S.D F12, 16(R1) ;xi-2+4 F12（存结果，指针存结果，指针+32+32） BNE R1, R2, loop ;BNE R1, R2, loop ;若若 R1R2R1R2，循环循环 S.D F16, 8(R1) ;xi-3+4 F16S.D F16, 8(R1) ;xi-3+4 F16（存结果，指针存结果，指针+32+32）例例6.26.2（续（续3 3）2014.2.1712计算机系统结构电子教案优秀调度后的调度后的相关链分析相关链分析 ：例例6.26.2（续（续4 4）代码性能：每个浮点元素运算使用代码性能：每个浮点元素运算
19、使用14/4=3.5拍，无空转。拍，无空转。2014.2.1713计算机系统结构电子教案优秀习题改写（原题意思不清）习题改写（原题意思不清）以以下下向向量量点点积积循循环环段段在在教教材材图图3.333.33所所示示改改进进流流水水线线上上运运行行，浮浮点点运运算算延迟符合教材表延迟符合教材表6.16.1规定，规定，F2F2的初值为的初值为0 0。loop: L.D F0, 0(R1)loop: L.D F0, 0(R1) L.D F4, 0(R2) L.D F4, 0(R2) MUL.D F0, F0, F4 MUL.D F0, F0, F4 ADD.D F2, F0, F2 ADD.D F
20、2, F0, F2 DADDUI R1, R1, #-8 DADDUI R1, R1, #-8 DADDUI R2, R2, #-8 DADDUI R2, R2, #-8（原题错写为原题错写为R1R1） BNE R1, R3, loop BNE R1, R3, loop(1)(1)使使用用循循环环展展开开和和指指令令调调度度改改造造程程序序（结结果果含含3 3个个循循环环体体），使使“空空转转”周期数不超过周期数不超过1 1个，写出新程序；个，写出新程序；(2)(2)手工计算原程序处理每对元素所需的时钟周期数、其中的空转数；手工计算原程序处理每对元素所需的时钟周期数、其中的空转数；(3)(3)
21、手工手工计算新程序算新程序处理每理每对元素所需的元素所需的时钟周期数、其中的空周期数、其中的空转数；数；习题习题6.86.82014.2.1714计算机系统结构电子教案优秀(4)(4)用用WinMIPS64WinMIPS64模模拟拟器器依依次次运运行行原原程程序序、新新程程序序，测测试试(2)(2)、(3)(3)步步的的对对应应结果（最好打印结果（最好打印CyclesCycles图）；图）；(5)(5)分分析析模模拟过程程，你你能能找找出出哪哪些些造造成成测试结果果与与手手工工计算算结果果不不一一致致的的原原因？因？习题习题6.86.8（续）（续）2014.2.1715计算机系统结构电子教案优
22、秀前几大节基本解决了分支程序的控制相关问题，本大节重点讨论循环前几大节基本解决了分支程序的控制相关问题，本大节重点讨论循环程序中的程序中的数据相关数据相关问题。对编译之前的问题。对编译之前的源代码源代码进行识别、优化更容易。进行识别、优化更容易。6.5.1 6.5.1 挖掘更多的循环级并行挖掘更多的循环级并行本小节重点讨论不同次循环本小节重点讨论不同次循环迭代迭代之间的相关。之间的相关。1. 1. 循环携带相关循环携带相关定义：不同次定义：不同次循环循环迭代之间的相关。迭代之间的相关。影响：如果原始程序内存在影响：如果原始程序内存在循环携带相关，则在循环携带相关，则在循环展开后，指令不能在循环
23、展开后，指令不能在各轮循环之间任意调动，这就大大限制了优化操作的效果发挥。各轮循环之间任意调动，这就大大限制了优化操作的效果发挥。6.5 6.5 开发更多的指令级并行开发更多的指令级并行2014.2.1716计算机系统结构电子教案优秀for(i=1;i=100;i=i+1)for(i=1;i=100;i=i+1) Ai+1=Ai+Ci; /*S1*/Ai+1=Ai+Ci; /*S1*/ Bi+1=Bi+Ai+1; /*S2*/Bi+1=Bi+Ai+1; /*S2*/ 假设数组假设数组A A、B B和和C C中所有元素的存储地址都互不相同，请问语句中所有元素的存储地址都互不相同，请问语句S1S1
24、与与S2S2之间之间存在哪些数据相关？存在哪些数据相关？解：解：(1) (1) 循环迭代内相关：循环迭代内相关：蓝色箭头蓝色箭头；(2) (2) 循环携带相关：循环携带相关：红色箭头红色箭头。例例6.76.7（P173P173）2014.2.1717计算机系统结构电子教案优秀进一步讨论循环展开的结果（以展开进一步讨论循环展开的结果（以展开1 1次为例）：次为例）：for(i=1;i=100;i=i+2)for(i=1;i=100;i=i+2) Ai+1=Ai+Ci; /*S1 Ai+1=Ai+Ci; /*S1，来自第来自第1 1个迭代个迭代*/*/ Bi+1=Bi+Ai+1; /*S2Bi+1
25、=Bi+Ai+1; /*S2，来自第来自第1 1个迭代个迭代*/*/ Ai+2=Ai+1+Ci+1; /*S3Ai+2=Ai+1+Ci+1; /*S3，来自第来自第2 2个迭代个迭代*/*/ Bi+2=Bi+1+Ai+2; /*S4Bi+2=Bi+1+Ai+2; /*S4，来自第来自第2 2个迭代个迭代*/*/ 这时如果因为这时如果因为S1S1、S2S2相关造成停顿，需要在它们之间插入一条语句的话，相关造成停顿，需要在它们之间插入一条语句的话，插入插入S3S3仍有同样的相关，仍有同样的相关，S4S4则不能调至则不能调至S3S3之前。实际上无语句可调。之前。实际上无语句可调。由此例可以看出：由此
26、例可以看出： 循环迭代内相关是局部性限制，不影响指令在大范围内移动；循环迭代内相关是局部性限制，不影响指令在大范围内移动； 循环携带相关是全局性限制，影响了指令在大范围内移动。循环携带相关是全局性限制，影响了指令在大范围内移动。所以需要寻找消除所以需要寻找消除循环携带相关的方法。循环携带相关的方法。例例6.76.7解（续）解（续）2014.2.1718计算机系统结构电子教案优秀有一类循环携带相关可以修改为循环内相关，例如有一类循环携带相关可以修改为循环内相关，例如for(i=1;i=100;i=i+1)for(i=1;i=100;i=i+1) Ai=Ai+Bi; /*S1*/Ai=Ai+Bi;
27、 /*S1*/ Bi+1=Ci+Di; /*S2*/Bi+1=Ci+Di; /*S2*/ 解：解：其特征是本轮循环的一条语句与下轮循环的另一条语句相关，这种情其特征是本轮循环的一条语句与下轮循环的另一条语句相关，这种情况不构成况不构成连续的相关链连续的相关链，可以把相关的两条语句重新组合到同一轮循环中，可以把相关的两条语句重新组合到同一轮循环中A1=A1+B1;A1=A1+B1;for(i=1;i=99;i=i+1)for(i=1;i=99;i=i+1) Bi+1=Ci+Di; /*Bi+1=Ci+Di; /*原来的原来的S2*/S2*/ Ai+1=Ai+1+Bi+1; /*Ai+1=Ai+1
28、+Bi+1; /*原来的原来的S1*/S1*/ B101=C100+D100;B101=C100+D100;以后就可以顺利地进行循环展开。以后就可以顺利地进行循环展开。相关链分析相关链分析见下页。见下页。例例6.86.8（P173P173）2014.2.1719计算机系统结构电子教案优秀例例6.86.8（续）（续）2014.2.1720计算机系统结构电子教案优秀显式相关显式相关与与隐式相关隐式相关q 同一变量名出现在多条语句中是同一变量名出现在多条语句中是显式相关显式相关，可通过，可通过字符匹配字符匹配来识别来识别q 同一数组元素以不同的同一数组元素以不同的存储别名出现在多条语句中是存储别名出
29、现在多条语句中是隐式相关隐式相关，不，不能通过简单的字符匹配来识别能通过简单的字符匹配来识别什么是什么是存储别名存储别名q 一个元素被不同的地址表达式访问，如一个元素被不同的地址表达式访问，如 Ai+5Ai+5、AjAj2-62-6、AkAkq 由于编译时难以预测索引变量由于编译时难以预测索引变量i i、j j、k k将来的运行值，故疑似存储将来的运行值，故疑似存储别名一律作相关看待，所在语句之间必须保持足够距离，避免并行执别名一律作相关看待，所在语句之间必须保持足够距离，避免并行执行行存储别名判则适用条件存储别名判则适用条件数组是数组是仿射的仿射的（affineaffine）q 仿射数组仿射
30、数组：访问地址访问地址表达式均为一次函数，形如表达式均为一次函数，形如AaAai+bi+bj+cj+c q 非仿射数组：例如非仿射数组：例如ABiABi2. 2. 存储别名导致的隐式相关（存储别名导致的隐式相关（GCDGCD判则）判则）2014.2.1721计算机系统结构电子教案优秀GCDGCD判则（最大公因数，判则（最大公因数，Greatest Common DivisorGreatest Common Divisor）q问题问题n给定一维数组给定一维数组Am:nAm:n和任意整数和任意整数j j、k k（mjmj，knkn），地址表达），地址表达式式 AaAaj+b j+b 与与 AcAc
31、k+d k+d 有没有可能是同有没有可能是同一个元素一个元素，即什么，即什么条件下满足条件下满足a aj+b = cj+b = ck+dk+dq判则判则n如果如果GCD(c,a)GCD(c,a)可以整除可以整除(d-b)(d-b)，可能存在存储别名（疑似相关），可能存在存储别名（疑似相关）n如果如果GCDGCD测试的结果为假（不能整除），一定不存在存储别名测试的结果为假（不能整除），一定不存在存储别名判则判则之所以说之所以说“可能存在可能存在”，是因为目标程序在运行中，是因为目标程序在运行中，j j、k k的实际的实际取值范围也可能到不了满足取值范围也可能到不了满足a aj+b = cj+b
32、= ck+dk+d的点。的点。2. 2. 存储别名导致的隐式相关（存储别名导致的隐式相关（GCDGCD判则）判则）2014.2.1722计算机系统结构电子教案优秀例：例：6j+136j+13与与9k+19k+1是否满足是否满足GCDGCD判则？判则？解：解：GCD(c,a) = 3 GCD(c,a) = 3 ，(d-b) = -12(d-b) = -12，能够整除，可能存在存储别名，能够整除，可能存在存储别名验证：验证：对取值对取值j = 0j = 0，1 1，2 2，和和k = 0k = 0，1 1，2 2， ，有，有6j+136j+13 = 13 = 13，1919，2525，3131，3
33、737，4343，4949，5555，6161，9k+19k+1 = 1 = 1，1010，1919，2828，3737，4646，5555，6464，7373，显然存在存储别名。将显然存在存储别名。将b b和和d d互换后也一样（这时互换后也一样（这时(d-b) = +12(d-b) = +12）6j+16j+1 = 1 = 1，7 7，1313，1919，2525，3131，3737，4343，4949，9k+139k+13 = = 1313，2222，3131，4040，4949，5858，6767，7676，8585，GCDGCD判则成功的例子判则成功的例子2014.2.1723计算机
34、系统结构电子教案优秀例：例：4j+14j+1与与2k+42k+4是否满足是否满足GCDGCD判则？判则？解：解：GCD(c,a) = 2 GCD(c,a) = 2 ，(d-b) = 3(d-b) = 3，不能整除，不存在存储别名，不能整除，不存在存储别名验证：验证：对取值对取值j = 0j = 0，1 1，2 2，和和k = 0k = 0，1 1，2 2， ，有，有4j+1 4j+1 = 1= 1，5 5，9 9，1313，1717，2121，2525，2929，3333，2k+4 2k+4 = 4= 4，6 6，8 8，1010，1212，1414，1616，1818，2020，未发现未发现
35、存储别名。将存储别名。将b b和和d d互换后也一样（验证略）互换后也一样（验证略）GCDGCD判则失败的例子判则失败的例子2014.2.1724计算机系统结构电子教案优秀例例6.96.9（P175P175）使用使用GCDGCD测试方法判断下面的循环中是否存在存储别名。测试方法判断下面的循环中是否存在存储别名。forfor（i=1i=1；i=100i=100；i=i+1i=i+1） x2*i+3 = x2*i * 5.0 x2*i+3 = x2*i * 5.0；解：解：在这个循环中，在这个循环中，a = 2a = 2，b = 3b = 3，c = 2c = 2，d = 0d = 0， 那么那么
36、GCD(a,c) = 2GCD(a,c) = 2，而，而d-b = -3d-b = -3。 由于由于2 2不能整除不能整除-3-3，因此没有存储别名，即无论，因此没有存储别名，即无论i i取何值，取何值，x2*i+3x2*i+3与与x2*ix2*i都将表示数组都将表示数组x x的不同元素。的不同元素。GCDGCD判则失败的例子判则失败的例子2014.2.1725计算机系统结构电子教案优秀在使用在使用GCDGCD测试之前，必须先对这段代码进行测试之前，必须先对这段代码进行“规范化规范化”修改下标修改下标从从1 1开始开始（不必要？）（不必要？），而且每次循环后增加，而且每次循环后增加1 1（ H
37、ennessyHennessy教材教材3 3版第版第4 4章）。章）。例如学习指导书题例如学习指导书题6.156.15原循环代码为原循环代码为for (i=2; i=100; i+=2)for (i=2; i=100; i+=2)ai = a50*i + 1;ai = a50*i + 1;进行规范化后的修改循环代码为进行规范化后的修改循环代码为for (i=1; i=50; i+)for (i=1; i=50; i+)a2*i = a100*i + 1;a2*i = a100*i + 1;再用再用GCDGCD测试法，测试法，a=2a=2，b=0b=0，c=100c=100，d=1d=1，GCD
38、(c,a)=2GCD(c,a)=2，(d-b)=1(d-b)=1，(d-(d-b) mod GCD(c,a)b) mod GCD(c,a)0 0，不能整除，所以该循环不存在循环携带的真数据相不能整除，所以该循环不存在循环携带的真数据相关。此题如果不先作规范化，则结论是关。此题如果不先作规范化，则结论是“存在循环携带相关存在循环携带相关”。习题习题6.7（注意（注意学习指导书中对应学习指导书中对应的题的题6.6答案是错的）答案是错的）GCDGCD测试之前要求循环代码测试之前要求循环代码“规范化规范化”2014.2.1726计算机系统结构电子教案优秀?3. 3. 数据相关处理数据相关处理?2014.2.1727计算机系统结构电子教案优秀各次作业应交的内容各次作业应交的内容作业作业7 7（第（第8 8次课）次课）6.8(6.8(改改) )，6.76.72014.2.1728计算机系统结构电子教案优秀
