资源描述：
《第十部分依赖于机器的优化教学课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十章依赖于机器的优化在指令级并行的机器上，程序的运行速度依赖于下面几个因素程序中潜在的并行处理器上可用的并行从串行程序提取并行的能力在给定的调度约束下发现最佳并行调度的能力并行的提取和并行执行的调度都可以静态地在软件中或动态地在硬件中完成第十章依赖于机器的优化本章内容使用指令级并行的基础问题提取并行的数据相关性分析代码调度的基本概念基本块调度的技术、发现通用程序中的高度数据相关控制流的方法、调度数值程序的软件流水线技术在多处理器系统上，使用数组的计算密集型程序的并行化和数据局部性优化的概念和方法10.1处理器体系结构在考虑指令级并行时，通常想象成一个处理
2、器在单个时钟周期内发射几个操作事实上，在每周期内发射一个操作是可能的,而指令级并行的获得是通过使用流水线技术本节先解释流水线，然后讨论多指令发射10.1处理器体系结构10.1.1指令流水线和分支延迟ii+1i+2i+3i+41.IF2.IDIF3.EXIDIF4.MEMEXIDIF5.WBMEMEXIDIF6.WBMEMEXID7.WBMEMEX8.WBMEM9.WB取指令IF,译码ID,执行操作EX,访问内存MEM,回写结果WB5级指令流水线中的5条连续指令10.1处理器体系结构10.1.1指令流水线和分支延迟分支延迟发现应该执行一个分支而不是直接后继转
3、向一个分支时会引起取分支目的地址指令的延迟并引起指令流水线“打嗝”可以通过使用硬件，根据分支的执行历史来预测分支结果并从预测的目的地址预取指令分支延迟不可避免，因为分支预测会发生偏差10.1处理器体系结构10.1.2流水化的执行如果不依赖一条指令结果的随后指令在该结果产生前就被允许执行有些指令的执行需要几个周期，几个操作同时出现在它们的执行级上可能的如果最长的执行流水线是n级，n个操作同时进行的可能性是存在的并非所有的指令都能被完全流水化，例如浮点除通用处理器大都动态察觉相继指令之间的依赖性嵌入式系统把数据相关性的检查交给软件10.1处理器体系结构10.1
4、.3多指令发射每周期发射几个操作，让更多操作同时进行超长指令字机器将若干个操作编码在单周期中发射编译器需要确定哪些操作可以并行发射超标量机器超标量机器有按普通顺序执行语义的正规指令集硬件自动察觉指令之间的相关性，并且在它们的操作数可用时就发射它们更复杂的调度器能够“乱序”执行指令10.2代码调度的约束代码调度用在代码生成器产生的机器代码上的优化技术本节讨论代码调度的约束控制相关约束在原程序中执行的所有操作都必须在优化代码中执行数据相关约束优化程序中的操作产生的结果必须同原程序对应操作的结果一样资源约束调度不能过分占用机器的资源优化程序很难调试内存状态可能和
5、顺序执行的任何内存状态不匹配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发
6、现内存访问中的相关性发现数据相关需要不同形式的分析数组元素间的别名分析A[i]和A[j]是否互为别名指针别名分析若p和q相等，则p和q、p->next和q->next、p->data和q->data等都分别互为别名过程间分析引用调用场合：形参和形参之间、形参和全局变量之间因实参而引起互为别名10.2代码调度的约束10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e)LDR1,aLDR2,bADDR1,R1,R2LDR2,cADDR1,R1,R2LDR2,dLDR3,eADDR2,R2,R3ADDR1,R1,R2+e+c+ab+d若瞄准
7、极小化寄存器的使用个数，则只需使用3个寄存器10.2代码调度的约束10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e)LDR1,aLDR2,bADDR1,R1,R2LDR2,cADDR1,R1,R2LDR2,dLDR3,eADDR2,R2,R3ADDR1,R1,R2+e+c+ab+d完成整个计算需要7步10.2代码调度的约束10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e)+e+c+ab+d如果对每个中间结果使用不同寄存器，则完成计算只需要4步R1=aR6=R1+R2R8=R6+R3R9=R8+R7R2=bR7=R
8、4+R5R3=cR4=dR5=e10.2代码调度的约束10.2.4
