依赖于机器的优化课件

第十章依赖于机器的优化在指令级并行的机器上，程序的运行速度依赖于下面几个因素

程序中潜在的并行处理器上可用的并行从串行程序提取并行的能力

在给定的调度约束下发现最佳并行调度的能力并行的提取和并行执行的调度都可以静态地在软件中或动态地在硬件中完成第十章依赖于机器的优化在指令级并行的机器上，程序的运行速第十章依赖于机器的优化本章内容使用指令级并行的基础问题提取并行的数据相关性分析代码调度的基本概念基本块调度的技术、发现通用程序中的高度数据相关控制流的方法、调度数值程序的软件流水线技术在多处理器系统上，使用数组的计算密集型程序的并行化和数据局部性优化的概念和方法第十章依赖于机器的优化本章内容10.1处理器体系结构在考虑指令级并行时，通常想象成一个处理器在单个时钟周期内发射几个操作事实上，在每周期内发射一个操作是可能的,而指令级并行的获得是通过使用流水线技术本节先解释流水线，然后讨论多指令发射10.1处理器体系结构在考虑指令级并行时，通常想象成一个10.1处理器体系结构10.1.1指令流水线和分支延迟

i i+1 i+2 i+3 i+41. IF2. ID IF3. EX ID IF4. MEM EX ID IF5. WB MEM EX ID IF6. WB MEM EX ID7. WB MEM EX8. WB MEM9. WB取指令IF,译码ID,执行操作EX,访问内存MEM,回写结果WB5级指令流水线中的5条连续指令10.1处理器体系结构10.1.1指令流水线和分支延迟10.1处理器体系结构10.1.1指令流水线和分支延迟分支延迟发现应该执行一个分支而不是直接后继转向一个分支时会引起取分支目的地址指令的延迟并引起指令流水线“打嗝”可以通过使用硬件，根据分支的执行历史来预测分支结果并从预测的目的地址预取指令分支延迟不可避免，因为分支预测会发生偏差10.1处理器体系结构10.1.1指令流水线和分支延迟10.1处理器体系结构10.1.2流水化的执行 如果不依赖一条指令结果的随后指令在该结果产生前就被允许执行有些指令的执行需要几个周期，几个操作同时出现在它们的执行级上可能的如果最长的执行流水线是n级，n个操作同时进行的可能性是存在的并非所有的指令都能被完全流水化，例如浮点除通用处理器大都动态察觉相继指令之间的依赖性嵌入式系统把数据相关性的检查交给软件10.1处理器体系结构10.1.2流水化的执行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发现内存访问中的相10.2代码调度的约束

10.2.2发现内存访问中的相关性发现数据相关需要不同形式的分析数组元素间的别名分析 A[i]和A[j]是否互为别名指针别名分析 若p和q相等，则p和q、p->next和q->next、 p->data和q->data等都分别互为别名过程间分析 引用调用场合：形参和形参之间、形参和全局变量之间因实参而引起互为别名10.2代码调度的约束10.2.2发现内存访问中的相10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 若瞄准极小化寄存器的使用个数，则只需使用3个寄存器10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 完成整个计算需要7步10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e)

+e+c+ab+d

如果对每个中间结果使用不同寄存器，则完成计算只需要4步R1=aR6=R1+R2R8=R6+R3R9=R8+R7R2=bR7=R4+R5R3=cR4=dR5=e10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.4寄存器分配和代码调度的次序安排先寄存器分配结果代码中会有很多存储相关非数值应用本质上没有多少并行，采用这种方式先代码调度导致寄存器溢出，抵消指令级并行的优点适用于有许多大表达式的数值应用在假定伪寄存器就是物理寄存器情况下，先调度指令，然后寄存器分配，把处理寄存器溢出的代码附加在必要的地方，并再次进行代码调度10.2代码调度的约束10.2.4寄存器分配和代码调10.2代码调度的约束

10.2.5控制相关

在非数值计算中，基本块非常小，其中的操作通常高度相关，几乎不能并行调查跨基本块的并行是至关重要的若一条指令很可能被执行且有空闲的资源可“免费”用于完成该指令的操作，则可以投机地执行该指令；若投机成功，则程序运行得快一些例 if(a>t) b=aa依赖于比较a>t的结果

b=aa; 若aa不会产生副作用，则 d=a+c; aa可以投机地执行10.2代码调度的约束10.2.5控制相关10.2代码调度的约束

10.2.6投机执行的支持内存读取是一类使用频繁，且能从投机执行大大获益的指令但在if(p!=null) q=p 中，投机地对p脱引用将引起该程序因p等于null而错误地停止许多高性能处理器提供专门的特性来支持投机地内存访问10.2代码调度的约束10.2.6投机执行的支持10.2代码调度的约束

10.2.6投机执行的支持预取指令 在数据使用前将其从内存取到缓存,若该单元无效或访问它会引起缺页，则忽略

抑制位 允许投机地从内存将数据读取到寄存器堆，若出现非法内存访问或缺页，则设置目标寄存器的抑制位判定指令 在判定条件为真时才执行的指令 例if(a==0) 翻译成ADDR3,R4,R5 b=c+d; CMOVZR2,R3,R1 假定a、b、c和d分别被分配了R1、R2、R4和R5

可用来将相邻基本块组合成一个更大基本块10.2代码调度的约束10.2.6投机执行的支持10.2代码调度的约束

10.2.7一个基本的机器模型机器模型M=(R,T)T：操作类型集，如读取、存储和算术运算等R=[r1,r2,…]：硬件资源向量集，如内存访问部件、算术运算部件和浮点功能部件 ri代表第i类资源中可用的部件数每个操作有一组输入操作数、一组输出操作数和一个资源需求和每个输入操作数相关的是一个输入延迟和每个输出操作数相关的是一个输出延迟10.2代码调度的约束10.2.7一个基本的机器模型10.2代码调度的约束

10.2.7一个基本的机器模型机器模型M=(R,T)对每种操作类型t，资源使用由一张二维资源预留表RTt来建模条目RTt[i,j]是t类型的一个操作在它被发射i时钟周期后，使用第j种资源的部件数对任何t、i和j，RTt[i,j]必须小于或等于R[j]10.2代码调度的约束10.2.7一个基本的机器模型10.3基本块调度10.3.1数据依赖图基本块由数据依赖图G=(N,E)来表示结点集合N表示该块的机器指令中的操作集合有向边集合E表示这些操作之间的数据相关约束G的结点集N和边集E按如下两步构造N中的每个操作n有一张资源预留表RTn，其值直接就是n的操作类型的资源预留表每条边e都标示有延迟de，表示e的目的结点必须在它源结点发射de个时钟周期之后才可以发射10.3基本块调度10.3.1数据依赖10.3基本块调度数据依赖图资源预留表alumenLDR2,0(R1)ST4(R1),R2LDR3,8(R1)ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3222111111i1i2i3i4i5i6i7灰色表示1

白色表示0操作是全流水的，只需显示在第1行使用的资源

10.3基本块调度数据依赖图资源预留表a10.3基本块调度10.3.2基本块的表调度关键路径包括最后5个结点，故第3条指令先调度再调度第1条指令，因为第4条指令还需等1周期第4周期调度2条资源预留表alumen调度表LDR3,8(R1)

ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3ST4(R1),R2

LDR2,0(R1)

10.3基本块调度10.3.2基本块的10.3基本块调度10.3.2基本块的表调度根据每个结点同先前已经被调度的各结点之间的数据相关约束，来计算一个结点可以执行的最早时间槽这个结点所需资源根据一张资源预留表来进行检查，该资源预留表收集了所有到目前为止被占用资源。这个结点的调度按有足够资源的最早时间槽来安排10.3基本块调度10.3.2基本块的10.4全局代码调度对于有适度指令级并行的机器，仅对每个基本块进行紧凑调度会引起许多资源空闲全局调度：为了更好地利用机器资源，需要考虑把指令从一个基本块移到另一个基本块的代码生成策略 必须保证原来程序中所有指令在优化程序中都被执行当优化程序可以投机地执行额外指令时，这些指令肯定不能有任何多余的副作用10.4全局代码调度对于有适度指令级并行的机器，仅对每个10.4全局代码调度10.4.1简单的代码移动先用例子展示操作在基本块之间移动涉及的问题

L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度10.4.1简单的代码移动L:if10.4全局代码调度假定a,b,c,d和e的地址不同，分别保存在R1到R5由于数据相关，块内的指令必须串行执行，且插入NOPL:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度假定a,b,c,d和e的地址不10.4全局代码调度假定机器在一个时钟周期执行任意的两个操作读取操作有2周期的延迟，其他指令1周期的延迟L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度假定机器在一个时钟周期执行任意的两个10.4全局代码调度B3肯定要执行，因而可以和B1并行执行B2的读取操作在执行B1时投机地完成B2的存储操作放到B3的 一份拷贝中L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度B3肯定要执行，因而可以和B1并行执10.4全局代码调度L:全局调度前后的流图if(a==0)gotoLc=be=d+d(a)源代码ST0(R5),R8(b)局部调度的机器代码LDR6,0(R1), LDR8,0(R4)LDR7,0(R2)ADDR8,R8,R8,BEQZR6,LST0(R5),R8, ST0(R3),R7L:(c)全局调度的机器代码B1B3B3LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度L:全局调度前后的流图if(a=10.4全局代码调度基本块之间的支配关系指令在基本块之间的移动因支配关系不同而不同B1和B3控制等价：B1支配B3， B3后支配B1B1支配B2， 但是B2并非后支配B1B2不支配B3， 但是B3后支配B2LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度基本块之间的支配关系LDR6,010.4全局代码调度10.4.2向上的代码移动 从块src向上移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次dstsrc10.4全局代码调度10.4.2向上的代码移动dsts10.4全局代码调度10.4.2向上的代码移动 从块src向上移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次若src未后支配dst，被移动操作可利用空闲资源免费执行，在控制流到达src时获益dstsrc10.4全局代码调度10.4.2向上的代码移动dsts10.4全局代码调度10.4.2向上的代码移动 从块src向上移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次若src未后支配dst，被移动操作可利用空闲资源免费执行，在控制流到达src时获益若dst不支配src， 需要插入被移动操作的拷贝

dstsrc10.4全局代码调度10.4.2向上的代码移动dsts10.4全局代码调度10.4.3向下的代码移动 从块src向下移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次srcdst10.4全局代码调度10.4.3向下的代码移动srcd10.4全局代码调度10.4.3向下的代码移动 从块src向下移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次src未后支配dst,向下移动的代码经常是存储操作,复制从src到dst路径上的各块，并把 被移动操作仅放置在dst的新拷贝中srcdst10.4全局代码调度10.4.3向下的代码移动srcd10.4全局代码调度9.5节的例子可作为参考B1B2B3B4a=b+cB5B6B7d=b+cB1B2B3B4t=b+ca=tB4B5d=td=b+cB6B6B710.4全局代码调度9.5节的例子可作为参考B1B2B310.4全局代码调度10.4.3向下的代码移动 从块src向下移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次src未后支配dst,向下移动的代码经常是存储操作,复制从src到dst路径上的各块，并把 被移动操作仅放置在dst的新拷贝中dst没有后支配src，插入补偿代码以保证被移动操作在不经dst路径上也执行srcdst10.4全局代码调度10.4.3向下的代码移动srcd10.4全局代码调度10.4.4更新数据相关 代码移动会改变操作之间的数据相关关系两个对x的赋值之一可以移动到最上面的基本块，该变换能维持原来程序中的所有相关性一旦一个对x的赋值被上移，另一个就不能移动了移动使得x在最上面块的出口 由不活跃变成活跃一个变量在某个程序点 活跃，则就不能把对它的投机 定值移到该点的上面x=1x=210.4全局代码调度10.4.4更新数据相关x=110.4全局代码调度10.4.5全局调度的其他问题

程序调度应该使经常执行的路径运行得快一些， 不经常执行的路径可能会因调度变得慢一些编译器可用来估计执行频率的技术有若干种

(1)内循环比外循环执行得更频繁

(2)分支指令往回跳转比不跳转要更经常 (3)看守程序出口或异常处理例程的分支语句很少被执行最好的频率估计来自动态剖析，程序被静态插桩以用来运行时记录条件分支每次的走向10.4全局代码调度10.4.5全局调度的其他问题10.4全局代码调度10.4.5全局调度的其他问题最简单的全局调度算法也相当复杂，不介绍在一些全局调度算法中，循环迭代的边界是代码移动的一种屏障，需循环展开for(i=0;i<N;i++){ for(i=0;i+4<N;i+=4){ S(i); S(i);S(i+1);} S(i+2);S(i+3); } for(;i<N;i++){ S(i); }10.4全局代码调度10.4.5全局调度的其他问题10.4全局代码调度10.4.6静态调度器和动态调度器的相互影响动态调度器的优点是可以根据运行时的情况建立新的调度表，无需事先编码所有可能的调度表10.4全局代码调度10.4.6静态调度器和动态调度器10.4全局代码调度10.4.6静态调度器和动态调度器的相互影响存在动态调度情况下，静态调度器的作用保证尽早地取高延迟的指令，使得动态调度器能够尽早发射它们尽早安排预取指令，使数据到要用时已经在缓存,或尽早安排可能不命中缓存的操作只需要给数据相关的操作安排正确的次序，无需通过极小化延迟来分离每一对数据相关的操作给分支预测指令较高优先级，以减少预测错误的代价10.4全局代码调度10.4.6静态调度器和动态调度器10.5软件流水

10.5.1引言 软件流水是一种调度算法，它每次调度一个完整的循环，以充分利用穿越迭代的并行性单次迭代的操作中几乎没有什么并行性软件流水技术不断地重叠一些相继迭代，直到所有迭代都填入流水线为止能产生高效和紧凑的代码 以一周期内可以同时发射一个读取、一个存储、一个算术运算（全流水）和一个分支操作的机器来举例10.5软件流水10.5.1引言10.5软件流水

每次调度一个迭代的结果见右边for(i=0;i<n;i++) //R1,R2,R3=&A,&B,&D

D[i]=A[i]B[i]+c;

//R4 =c //R10 =n1 L:LDR5,0(R1++) LDR6,0(R2++) MULR7,R5,R6 NOP ADDR8,R7,R4 NOP ST0(R3++),R8,BLR10,L该计算大部分是串行的，它需要7周期，只有循环回跳指令和迭代中最后一条指令重叠10.5软件流水每次调度一个迭代的结果见右10.5软件流水

循环展开4次迭代的调度结果见右边for(i=0;i<n;i++) L: LD

D[i]=A[i]B[i]+c;

LD

LD MUL LD MUL LD ADD LD ADD LD ST MUL LD ST MUL ADD ADD ST ST BL(L)

展开后每次迭代的执行用13周期，或者说原来的每次迭代仅需要3.25周期忽略了寄存器分配的细节10.5软件流水循环展开4次迭代的调度结果10.5软件流水

周期

j=1 j=2 j=3 j=4 j=5

(1) LD (2) LD (3) MUL LD (4) LD (5) MUL LD (6) ADD LD (7) MUL LD (8) ST ADD LD (9) MUL LD (10) ST ADD LD (11) MUL (12) ST ADD (13) (14) ST ADD (15) (16) ST 不考虑寄存器分配10.5.2循环的软件流水右边是展开5次的迭代调度满足所有的资源和数据相关约束第7和8周期执行的操作同第9和10周期执行的是一样的10.5软件流水 周期 j=1 10.5软件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考虑寄存器分配10.5.2循环的软件流水右边是经软件流水化的代码每行对应到一条机器指令第7和第8两行构成一个2时钟的循环，重复执行n3次10.5软件流水 (1) LD不考虑10.5软件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考虑寄存器分配10.5.2循环的软件流水右边是经软件流水化的代码当一个老的迭代在该流水线上撤出，一个新的迭代填入当所有迭代都填完，该流水线排空10.5软件流水 (1) LD不考虑10.5软件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考虑寄存器分配10.5.2循环的软件流水右边是经软件流水化的代码第1到6行的指令序列叫序曲第7和8行叫做稳定状态第9到14行指令序列叫做尾声

10.5软件流水 (1) LD不考虑10.5软件流水

周期

j=1 j=2 j=3 j=4 j=5

(1) LD (2) LD (3) MUL LD (4) LD (5) MUL LD (6) ADD LD (7) MUL LD (8) ST ADD LD (9) MUL LD (10) ST ADD LD (11) MUL (12) ST ADD (13) (14) ST ADD (15) (16) ST 10.5.3寄存器分配和代码生成第1次迭代乘运算的结果在第3周期产生，在第6周期使用第2次迭代结果在第5周期产生，第8周期用结果必须保存在不同寄存器10.5软件流水 周期 j=1 10.5软件流水

10.5.3寄存器分配和代码生成 奇数次迭代和偶数次迭代的代码不完全一样，所以进入稳定状态后的循环由2周期加倍成4周期用源代码解释，相当于下面的循环if(N>=5) N2=1+2((N1)/2);else N2=0;for(i=0;i<N2;i++) //该循环被流水化 D[i]=A[i]B[i]+c;for(i=N2;i<N;i++) //不需要优化 D[i]=A[i]B[i]+c;10.5软件流水10.5.3寄存器分配和10.5软件流水

10.5.4Do-Across循环 软件流水也可以用到迭代之间存在数据相关的循环，这样的循环叫做do-across循环

for(i=0;i<n;i++){ sum=sum+A[i]; B[i]=A[i]b; }该循环的执行不可能快于每2周期1次迭代即使有更多的加法器或乘法器，也不可能更快吞吐能力受到穿越迭代的数据相关链的限制10.5软件流水10.5.4Do-Acr10.5软件流水

10.5.5软件流水的目标和约束目标基本目标是极大化耗时较长的循环的吞吐能力次要目标是保持所产生代码的规模较小达到目标的体现软件流水化的循环应该有较小的流水线稳定状态实现策略让每次迭代的相对调度都相同，并且这些迭代以同样的时间间隔逐步启动10.5软件流水10.5.5软件流水的目10.5软件流水

10.5.5软件流水的目标和约束资源约束令机器资源由R=[r1,r2,...]表示，其中ri是第i类资源可用部件数若循环的一次迭代需要第i类资源ni个部件流水化循环的平均启动间隔至少是maxi(ni/ri)周期如果maxi(ni/ri)小于1，则将源代码展开几次是有用的10.5软件流水10.5.5软件流水的目10.5软件流水

10.5.5软件流水的目标和约束数据相关一个操作可能依赖于前一次迭代中同样操作的结果，不同于到目前为止碰到的数据相关仅用延迟来标记边不够用，需要区别不同迭代中同一操作的实例，例如：

for(i=2;i<n;i++) A[i]=B[i]+A[i2] 写A[i]和读A[i2]的依赖边上标记的迭代次数差是210.5软件流水10.5.5软件流水的目10.6并行性和数据局部性优化概述并行编程模型任务并行数据并行流水线并行（前面几节涉及较多）本节内容围绕任务并行和数据并行介绍并行计算机系统结构的概况给出并行化的基本概念，程序循环的变换，还有对并行化有用的概念类似的考虑怎样用于优化数据局部性以矩阵乘算法的优化为例

10.6并行性和数据局部性优化概述并行编程模型10.6并行性和数据局部性优化概述10.6.1多处理器对称多处理器的体系结构二级缓存内存总线二级缓存二级缓存二级缓存一级缓存一级缓存一级缓存一级缓存处理器处理器处理器处理器多个高性能处理器集成在一块芯片上10.6并行性和数据局部性优化概述10.6.1多处理器10.6并行性和数据局部性优化概述10.6.1多处理器对称多处理器的体系结构二级缓存内存总线二级缓存二级缓存二级缓存一级缓存一级缓存一级缓存一级缓存处理器处理器处理器处理器多个高性能处理器集成在一块芯片上通过共享内存来进行通信必须在处理器的缓存中找到它操作的大部分数据，以保证性能10.6并行性和数据局部性优化概述10.6.1多处理器10.6并行性和数据局部性优化概述10.6.1多处理器分布式内存机器总线或其它互连二级缓存二级缓存二级缓存二级缓存一级缓存一级缓存一级缓存一级缓存处理器处理器处理器处理器局部内存局部内存局部内存局部内存在内存分层中又引入一层处理器能迅速访问自己的局部内存

10.6并行性和数据局部性优化概述10.6.1多处理器10.6并行性和数据局部性优化概述10.6.1多处理器分布式内存机器总线或其它互连二级缓存二级缓存二级缓存二级缓存一级缓存一级缓存一级缓存一级缓存处理器处理器处理器处理器局部内存局部内存局部内存局部内存在内存分层中又引入一层处理器能迅速访问自己的局部内存

非均匀内存访问的机器和消息传递的机器；为获得良好的性能软件都必须有很好局部性10.6并行性和数据局部性优化概述10.6.1多处理器10.6并行性和数据局部性优化概述10.6.2应用中的并行性并行应用性能衡量的两种标准并行覆盖：整个计算中并行运行部分的百分比并行粒度：处理器上无需和其它处理器同步或通信的计算量 循环对并行化来说特别有吸引力，循环可以有许多次迭代计算，如果这些计算相互独立，则它们是并行计算的主要来源 许多控制结构简单、数据量大并且耗时长的科学和工程应用，很容易以较细粒度被并行化

10.6并行性和数据局部性优化概述10.6.2应用中的10.6并行性和数据局部性优化概述10.6.3循环级并行 耗时的应用一般都使用大数组，导致程序中出现有许多次迭代的循环，这些迭代经常相互独立，可以把这类循环的大量迭代分到各处理器上10.6并行性和数据局部性优化概述10.6.3循环级并10.6并行性和数据局部性优化概述10.6.3循环级并行

for(i=0;i<n;i++){ Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; } //

变换成如下代码

b=ceil(n/M);//M个处理器,p=0,1,…,M

1

for(i=bp;i<min(n,b(p+1));i++){ Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; }//数据并行的例子10.6并行性和数据局部性优化概述10.6.3循环级并10.6并行性和数据局部性优化概述10.6.3循环级并行对并行化来说，任务级不像循环级那样有吸引力对一个程序而言，独立的任务数是一个常数，它不像典型的循环那样，独立的计算单元随迭代次数增加而增加任务通常不是等规模的，因此很难保证所有的处理器在所有时间都处于忙碌10.6并行性和数据局部性优化概述10.6.3循环级并10.6并行性和数据局部性优化概述10.6.4数据局部性程序局部性大多数程序的大部分时间在执行一小部分代码，并且仅涉及一小部分数据时间局部性程序访问的内存单元在很短的时间内可能再次被程序访问空间局部性毗邻被访问单元的内存单元在很短的时间内可能被访问10.6并行性和数据局部性优化概述10.6.4数据局部10.6并行性和数据局部性优化概述10.6.4数据局部性同一个缓存行上的元素一起被使用的情况是空间局部性的一种重要形式这种空间局部性将缓存未命中降到最低，因此使得程度获得明显的加速10.6并行性和数据局部性优化概述10.6.4数据局部10.6并行性和数据局部性优化概述10.6.4数据局部性

for(i=0;i<n;i++){ //该程序段对向量机来 Z[i]=X[i]Y[i]; //说是一种优化形式

} for(i=0;i<n;i++){ Z[i]=Z[i]Z[i]; } for(i=0;i<n;i++){ //有较好的数据局部性

Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; }10.6并行性和数据局部性优化概述10.6.4数据局部10.6并行性和数据局部性优化概述10.6.4数据局部性对行为主的数组Z，根据空间局部性，显然更愿意逐行地给该数组元素置零

for(j=0;j<n;j++) for(i=0;i<n;i++) for(i=0;i<n;i++) for(j=0;j<n;j++)

Z[i,j]=0; Z[i,j]=0;为了获得最好的性能，应该并行化外循环

b=ceil(n/M); for(i=bp;i<min(n,b(p+1));i++)

for(j=0;j<n;j++)

Z[i,j]=0;10.6并行性和数据局部性优化概述10.6.4数据局部10.6并行性和数据局部性优化概述10.6.4数据局部性操作在数组上的数值应用的几个重要特征数组代码经常有许多可以并行化的循环当循环有并行性时，它们的迭代可按任意次序执行，因而可重新安排计算次序以彻底改进数据局部性在创建相互独立的并行计算大单元时，串行执行这些单元往往会产生较好的数据局部性10.6并行性和数据局部性优化概述10.6.4数据局部10.6并行性和数据局部性优化概述10.6.5矩阵乘法算法该算法是计算密集型的，原则上内存访问不应该构成瓶颈假定矩阵的布局是行为主假定正好c个数组 元素能够放满一个 缓存行，X的一行仅 散布在n/c个缓存行上假定缓存足以放下X所 有的缓存行，读入X出 现n2/c次缓存未命中for(i=0;i<n;i++) for(j=0;j<n;j++){ Z[i,j]=0.0; for(k=0;k<n;k++) Z[i,j]=Z[i,j]+X[i,k]Y[k,j];

}10.6并行性和数据局部性优化概述10.6.5矩阵乘法10.6并行性和数据局部性优化概述10.6.5矩阵乘法算法先考虑在单处理器上顺序执行j=01…n

1i=0XY完成Z一行元素的计算，取Y出现的缓存未命中次数在n2/c和n2之间完成整个Z，Y未命中次数在n2/c和n3之间10.6并行性和数据局部性优化概述10.6.5矩阵乘法10.6并行性和数据局部性优化概述10.6.5矩阵乘法算法再考虑在p个处理器上并行计算把Z不同行的计算指派到不同处理器，每个处理器计算Z的连续n/p行每个处理器访问矩阵X和Z的n/p行以及整个Y，用n3/p次乘加运算来完成对Z的n2/p个元素的计算虽然计算时间与p成比例减少，但通信代价却与p成比例增加，因为交付给p个处理器之缓存的总缓存行是n2/c+pn2/cp逼近n时，计算时间为O(n2)，通信代价为O(n3)

10.6并行性和数据局部性优化概述10.6.5矩阵乘法10.6并行性和数据局部性优化概述10.6.6矩阵乘法算法的优化

复用在缓存的数据才代表数据局部性好复用应该很快发生，数据才可能还在缓存在上述算法中，n2个乘加操作隔开了矩阵Y中同一个数据的复用，n个乘加操作隔开了Y中同一个缓存行的复用分块是重排循环中迭代次序的一种方法，它能够极大地改进程序的局部性10.6并行性和数据局部性优化概述10.6.6矩阵乘法10.6并行性和数据局部性优化概述10.6.6矩阵乘法算法的优化

从第4到7行的程序计算左上角为X[ii,kk]和Y[kk,jj]的两块对左上角为Z[ii,jj]的块的贡献for(ii=0;ii<n;ii=ii+b)for(jj=0;jj<n;jj=jj+b)

for(kk=0;kk<n;kk=kk+b) for(i=ii;i<ii+b;i++) for(j=jj;j<jj+b;j++) for(k=kk;k<kk+b;k++) Z[i,j]=Z[i,j]+ X[i,k]Y[k,j];bn10.6并行性和数据局部性优化概述10.6.6矩阵乘法10.6并行性和数据局部性优化概述10.6.6矩阵乘法算法的优化

适当选择b，使3个矩阵都有一个块可以装到缓存把X或Y一块取到缓存，会出现b2/c次缓存未命中对于X和Y的一对块，第4到7行的程序完成b3次乘加计算由于整个矩阵乘法需要n3次乘加计算，则取一对块到缓存的总次数是n3/b3对于X和Y的一对块会有2b2/c次缓存未命中，因此缓存未命中的总次数是2n3/bc和10.6.5节的O(n3/c)，甚至O(n3)次缓存未命中相比，在b较大时，2n3/bc能体现出分开方法的好处10.6并行性和数据局部性优化概述10.6.6矩阵乘法习题第一次：10.1,10.3第二次：10.5,10.6习题第一次：10.1,10.3第十章依赖于机器的优化在指令级并行的机器上，程序的运行速度依赖于下面几个因素

程序中潜在的并行处理器上可用的并行从串行程序提取并行的能力

在给定的调度约束下发现最佳并行调度的能力并行的提取和并行执行的调度都可以静态地在软件中或动态地在硬件中完成第十章依赖于机器的优化在指令级并行的机器上，程序的运行速第十章依赖于机器的优化本章内容使用指令级并行的基础问题提取并行的数据相关性分析代码调度的基本概念基本块调度的技术、发现通用程序中的高度数据相关控制流的方法、调度数值程序的软件流水线技术在多处理器系统上，使用数组的计算密集型程序的并行化和数据局部性优化的概念和方法第十章依赖于机器的优化本章内容10.1处理器体系结构在考虑指令级并行时，通常想象成一个处理器在单个时钟周期内发射几个操作事实上，在每周期内发射一个操作是可能的,而指令级并行的获得是通过使用流水线技术本节先解释流水线，然后讨论多指令发射10.1处理器体系结构在考虑指令级并行时，通常想象成一个10.1处理器体系结构10.1.1指令流水线和分支延迟

i i+1 i+2 i+3 i+41. IF2. ID IF3. EX ID IF4. MEM EX ID IF5. WB MEM EX ID IF6. WB MEM EX ID7. WB MEM EX8. WB MEM9. WB取指令IF,译码ID,执行操作EX,访问内存MEM,回写结果WB5级指令流水线中的5条连续指令10.1处理器体系结构10.1.1指令流水线和分支延迟10.1处理器体系结构10.1.1指令流水线和分支延迟分支延迟发现应该执行一个分支而不是直接后继转向一个分支时会引起取分支目的地址指令的延迟并引起指令流水线“打嗝”可以通过使用硬件，根据分支的执行历史来预测分支结果并从预测的目的地址预取指令分支延迟不可避免，因为分支预测会发生偏差10.1处理器体系结构10.1.1指令流水线和分支延迟10.1处理器体系结构10.1.2流水化的执行 如果不依赖一条指令结果的随后指令在该结果产生前就被允许执行有些指令的执行需要几个周期，几个操作同时出现在它们的执行级上可能的如果最长的执行流水线是n级，n个操作同时进行的可能性是存在的并非所有的指令都能被完全流水化，例如浮点除通用处理器大都动态察觉相继指令之间的依赖性嵌入式系统把数据相关性的检查交给软件10.1处理器体系结构10.1.2流水化的执行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发现内存访问中的相10.2代码调度的约束

10.2.2发现内存访问中的相关性发现数据相关需要不同形式的分析数组元素间的别名分析 A[i]和A[j]是否互为别名指针别名分析 若p和q相等，则p和q、p->next和q->next、 p->data和q->data等都分别互为别名过程间分析 引用调用场合：形参和形参之间、形参和全局变量之间因实参而引起互为别名10.2代码调度的约束10.2.2发现内存访问中的相10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 若瞄准极小化寄存器的使用个数，则只需使用3个寄存器10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 完成整个计算需要7步10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.3寄存器使用和并行执行之间的折衷例：(a+b)+c+(d+e)

+e+c+ab+d

如果对每个中间结果使用不同寄存器，则完成计算只需要4步R1=aR6=R1+R2R8=R6+R3R9=R8+R7R2=bR7=R4+R5R3=cR4=dR5=e10.2代码调度的约束10.2.3寄存器使用和并行执10.2代码调度的约束

10.2.4寄存器分配和代码调度的次序安排先寄存器分配结果代码中会有很多存储相关非数值应用本质上没有多少并行，采用这种方式先代码调度导致寄存器溢出，抵消指令级并行的优点适用于有许多大表达式的数值应用在假定伪寄存器就是物理寄存器情况下，先调度指令，然后寄存器分配，把处理寄存器溢出的代码附加在必要的地方，并再次进行代码调度10.2代码调度的约束10.2.4寄存器分配和代码调10.2代码调度的约束

10.2.5控制相关

在非数值计算中，基本块非常小，其中的操作通常高度相关，几乎不能并行调查跨基本块的并行是至关重要的若一条指令很可能被执行且有空闲的资源可“免费”用于完成该指令的操作，则可以投机地执行该指令；若投机成功，则程序运行得快一些例 if(a>t) b=aa依赖于比较a>t的结果

b=aa; 若aa不会产生副作用，则 d=a+c; aa可以投机地执行10.2代码调度的约束10.2.5控制相关10.2代码调度的约束

10.2.6投机执行的支持内存读取是一类使用频繁，且能从投机执行大大获益的指令但在if(p!=null) q=p 中，投机地对p脱引用将引起该程序因p等于null而错误地停止许多高性能处理器提供专门的特性来支持投机地内存访问10.2代码调度的约束10.2.6投机执行的支持10.2代码调度的约束

10.2.6投机执行的支持预取指令 在数据使用前将其从内存取到缓存,若该单元无效或访问它会引起缺页，则忽略

抑制位 允许投机地从内存将数据读取到寄存器堆，若出现非法内存访问或缺页，则设置目标寄存器的抑制位判定指令 在判定条件为真时才执行的指令 例if(a==0) 翻译成ADDR3,R4,R5 b=c+d; CMOVZR2,R3,R1 假定a、b、c和d分别被分配了R1、R2、R4和R5

可用来将相邻基本块组合成一个更大基本块10.2代码调度的约束10.2.6投机执行的支持10.2代码调度的约束

10.2.7一个基本的机器模型机器模型M=(R,T)T：操作类型集，如读取、存储和算术运算等R=[r1,r2,…]：硬件资源向量集，如内存访问部件、算术运算部件和浮点功能部件 ri代表第i类资源中可用的部件数每个操作有一组输入操作数、一组输出操作数和一个资源需求和每个输入操作数相关的是一个输入延迟和每个输出操作数相关的是一个输出延迟10.2代码调度的约束10.2.7一个基本的机器模型10.2代码调度的约束

10.2.7一个基本的机器模型机器模型M=(R,T)对每种操作类型t，资源使用由一张二维资源预留表RTt来建模条目RTt[i,j]是t类型的一个操作在它被发射i时钟周期后，使用第j种资源的部件数对任何t、i和j，RTt[i,j]必须小于或等于R[j]10.2代码调度的约束10.2.7一个基本的机器模型10.3基本块调度10.3.1数据依赖图基本块由数据依赖图G=(N,E)来表示结点集合N表示该块的机器指令中的操作集合有向边集合E表示这些操作之间的数据相关约束G的结点集N和边集E按如下两步构造N中的每个操作n有一张资源预留表RTn，其值直接就是n的操作类型的资源预留表每条边e都标示有延迟de，表示e的目的结点必须在它源结点发射de个时钟周期之后才可以发射10.3基本块调度10.3.1数据依赖10.3基本块调度数据依赖图资源预留表alumenLDR2,0(R1)ST4(R1),R2LDR3,8(R1)ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3222111111i1i2i3i4i5i6i7灰色表示1

白色表示0操作是全流水的，只需显示在第1行使用的资源

10.3基本块调度数据依赖图资源预留表a10.3基本块调度10.3.2基本块的表调度关键路径包括最后5个结点，故第3条指令先调度再调度第1条指令，因为第4条指令还需等1周期第4周期调度2条资源预留表alumen调度表LDR3,8(R1)

ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3ST4(R1),R2

LDR2,0(R1)

10.3基本块调度10.3.2基本块的10.3基本块调度10.3.2基本块的表调度根据每个结点同先前已经被调度的各结点之间的数据相关约束，来计算一个结点可以执行的最早时间槽这个结点所需资源根据一张资源预留表来进行检查，该资源预留表收集了所有到目前为止被占用资源。这个结点的调度按有足够资源的最早时间槽来安排10.3基本块调度10.3.2基本块的10.4全局代码调度对于有适度指令级并行的机器，仅对每个基本块进行紧凑调度会引起许多资源空闲全局调度：为了更好地利用机器资源，需要考虑把指令从一个基本块移到另一个基本块的代码生成策略 必须保证原来程序中所有指令在优化程序中都被执行当优化程序可以投机地执行额外指令时，这些指令肯定不能有任何多余的副作用10.4全局代码调度对于有适度指令级并行的机器，仅对每个10.4全局代码调度10.4.1简单的代码移动先用例子展示操作在基本块之间移动涉及的问题

L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度10.4.1简单的代码移动L:if10.4全局代码调度假定a,b,c,d和e的地址不同，分别保存在R1到R5由于数据相关，块内的指令必须串行执行，且插入NOPL:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度假定a,b,c,d和e的地址不10.4全局代码调度假定机器在一个时钟周期执行任意的两个操作读取操作有2周期的延迟，其他指令1周期的延迟L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度假定机器在一个时钟周期执行任意的两个10.4全局代码调度B3肯定要执行，因而可以和B1并行执行B2的读取操作在执行B1时投机地完成B2的存储操作放到B3的 一份拷贝中L:if(a==0)gotoLc=be=d+d(a)源代码(b)局部调度的机器代码LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度B3肯定要执行，因而可以和B1并行执10.4全局代码调度L:全局调度前后的流图if(a==0)gotoLc=be=d+d(a)源代码ST0(R5),R8(b)局部调度的机器代码LDR6,0(R1), LDR8,0(R4)LDR7,0(R2)ADDR8,R8,R8,BEQZR6,LST0(R5),R8, ST0(R3),R7L:(c)全局调度的机器代码B1B3B3LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度L:全局调度前后的流图if(a=10.4全局代码调度基本块之间的支配关系指令在基本块之间的移动因支配关系不同而不同B1和B3控制等价：B1支配B3， B3后支配B1B1支配B2， 但是B2并非后支配B1B2不支配B3， 但是B3后支配B2LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代码调度基本块之间的支配关系LDR6,010.4全局代码调度10.4.2向上的代码移动 从块src向上移动到块dst，假定移动未违反数据相关，并使得通过dst到src的路径运行得较快若dst和src等价，则被移动操作应该被执行时，它正好仅被执行一次dstsrc10.4全局代码调度10.4.2向上的代码移动dsts10.4全局代