第4章-指令级并行PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,2,第,4,章 指令级并行,主讲：顾一禾,2,本章学习内容,指令级并行的基本概念,指令的动态调度,动态分支预测技术,多指令流出技术,2,4.1,指令级并行,指令之间存在的潜在并行性称为,指令级并行,。（,ILP,：,Instruction-Level Parallelism,）,只有将硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。,2,1.,流水线处理机的实际,CPI,流水线处理机的实际,CPI,就是理想流水线的,CPI,加上各类停顿的时钟周期数：,CPI,流水线,=CPI,理想,+,停顿,结构冲突,+,停顿,数据冲突,+,停顿,控制冲突,CPI,理想,即理想,CPI,，是衡量流水线最高性能的指标之一。,2,IPC,（,Instructions Per Cycle,）,IPC,：每个时钟周期内完成的指令条数。,IPC,是,CPI,的倒数。,提高,IPC,的途径之一是减少,CPI,流水线,。,2,2.,基本程序块,基本程序块,：一段除了入口和出口以外不包含其他分支的一个线性代码段。,因为程序往往平均每,5,7,条指令就会有一个分支，而且指令之间还可能存在相关，所以在基本程序块中能开发的并行性是很有限的，很可能比基本块的大小要小很多。,为了明显地提高性能，必须跨越多个基本块开发指令的并行性。,2,3.,开发指令级并行常用的方法,（,1,）开发循环级并行,循环级并行（,Loop,level,parallelism,）,：循环程序不同迭代之间存在的并行性。,例：,for,（,i=1,；,i500,；,i=i,1,）,ai=ai,s,；,在每一次循环的内部，没有任何的并行性。,每一次循环都可以与其他的循环重叠并行执行。,开发循环级并行性是增加指令之间并行性的最简单和最常用的方法。,2,开发循环级并行的基本技术,采用循环展开技术,采用向量指令和向量数据表示,2,（,2,）解决相关与流水线冲突问题,相关,是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。,相关的三种类型：数据相关、名相关、控制相关。,如果两条指令相关，它们就不能并行执行，或只能部分重叠执行。,由于相关的存在，使得指令流中的下一条指令不能在指定时钟周期执行，就是发生了,流水线冲突,。,相关的存在限制了指令级并行（,ILP,）的开发。,2,流水线冲突的三种类型：结构冲突、数据冲突、控制冲突。,结构冲突：由硬件资源冲突造成。,数据冲突：由数据相关和名相关造成。,控制冲突：由控制相关造成。,具体的一次相关是否会导致,实际冲突,的发生以及该冲突会带来多长的停顿，根据流水线的属性而定。,2,解决相关与冲突的方法,保持相关，但,避免发生冲突,。,方法：指令调度，包括静态调度和动态调度。,通过代码变换，消除相关。,2,解决相关与冲突时需注意的问题,由于相关的存在，在开发指令级并行时，如果可能影响到程序的正确性，就必须,注意保持程序顺序。,程序顺序,：由源程序确定的在完全串行方式下指令的执行顺序。,控制相关并不是一个必须严格保持的关键属性。,当存在控制相关时，在对程序的正确性没有影响的前提下，可以不遵守控制相关的依赖关系，执行本来不该执行的指令。,2,必须保持的最关键的两个属性,要正确地执行程序，必须保持的最关键的两个属性是：,数据流,和,异常行为。,保持异常行为：,无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。,原来程序中是怎么发生的，改变执行顺序后还是怎么发生。,可弱化为：指令执行顺序的改变不能导致程序中发生新的异常。,如果能做到,保持,程序的数据相关和控制相关，就能保持程序的数据流和异常行为。,2,例：,DADDU,R2,，,R3,，,R4,BEQZ,R2,，,L1,LW,R1,，,0,（,R2,）,L1,：,如果不保持关于,R2,的数据相关，程序的执行结果就会改变。,如果不保持控制相关，把,LW,指令移到,BEQZ,之前，就有可能产生一个新的“访存保护”异常（如果,R2,0,）。,2,数据流,：指数据值从其产生者指令到其消费者指令的实际流动。,分支指令使得数据流具有,动态性,，因为它使得给定指令的数据可以有多个来源。,仅仅保持数据相关性是不够的,，一条指令可能与多条先前的指令数据相关，程序顺序决定了哪条指令真正是所需数据的产生者。,只有再加上保持控制顺序，才能够保持程序顺序。,2,例：,DADDU,R1,，,R2,，,R3,BEQZ,R4,，,L1,DSUBU,R1,，,R5,，,R6,L1,：,OR R7,，,R1,，,R8,OR,指令中使用的,R1,值取决于,BEQZ,指令分支的是否成功。即,OR,与,DADDU,或,DSUBU,指令相关。,必须通过保持控制相关，避免对数据流的修改，以保证数据流的正确。,DSUBU,不能被移到,BEQZ,之前。,2,有时，不遵守控制相关既不影响异常行为，也不改变数据流。在这种情况下，可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。,2,例：,DADDU R1,，,R2,，,R3,BEQZ,R12,，,Skipnext,DSUBUR4,，,R5,，,R6,DADDUR5,，,R4,，,R9,Skipnext,：,OR R7,，,R8,，,R9,如果已知,R4,在,Skipnext,后不再被使用，而且,DSUBU,指令不会产生异常，那么就可以把,DSUBU,指令移到,BEQZ,之前。,因为这个移动不会改变数据流。,2,开发指令的并行性的方法,硬件方法：指令的动态调度、动态分支预测、多指令流出技术。,软件方法：指令的静态调度、循环展开技术。,软硬件结合方法：显式并行指令计算,EPIC,。,2,4.5,循环展开和指令调度,4.5.1,循环展开和指令调度的基本方法,为了充分发挥流水线的作用，必须设法让它满负荷工作。因此要充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水线上重叠并行执行。,增加指令间并行性最简单和最常用的方法,开发循环级并行性,循环的不同迭代之间存在的并行性。,在把循环展开后，通过重命名和指令调度来开发更多的并行性。,2,编译器指令调度能力的限制,编译器完成指令调度的能力受限于两个特性：,程序固有的指令级并行性；,流水线功能部件的执行延迟。,2,浮点流水线延迟,Load,指令的结果可以通过定向路径及时送给,store,指令，所以延迟为,0,，不用插入停顿。,产生结果的指令,使用结果的指令,延迟（时钟周期数）,浮点计算,另一个浮点计算,3,浮点计算,浮点,store,（,S.D,）,2,浮点,load,（,L.D,）,浮点计算,1,浮点,load,（,L.D,）,浮点,store,（,S.D,）,0,2,例,4.6,对于下面的源代码，转换成,MIPS,汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。,for(i=1,；,i=1000,；,i+),xi=xi+s,；,解：,该循环的不同迭代之间不存在相关，所以多次迭代可以并行执行。,2,MIPS,汇编语言代码：,假设,R1,的初值指向第一个元素，,8,（,R2,）指向最后一个元素。,Loop,：,L.D F0,0(R1)/,取一个向量元素放入,F0,ADD.D F4,F0,F2 /,加上在,F2,中的标量,S.D F4,0(R1)/,存结果,DADDIU R1,R1,#,8 /,将指针减,8,（每个数据占,8,个字节）,BNE R1,R2,Loop /,若,R1,不等于,R2,，表示尚未结束，,/,转移到,Loop,继续执行,其中：,整数寄存器,R1,：指向向量中的当前元素。,（初值为向量中最高端元素的地址）,浮点寄存器,F2,：用于保存常数,s,。,2,不进行指令调度的情况下，程序的实际执行情况,Loop:L.D F0,0,（,R1,）,1,（空转）,2,ADD.D F4,F0,F2 3,（空转）,4,（空转）,5,S.D F4,0,（,R1,）,6,DADDIU R1,R1,，,#,8 7,（空转）,8,BNE R1,R2,Loop 9,（空转）,10,每个元素的操作需要,10,个时钟周期，其中,5,个是空转周期。,2,指令调度以后，程序的执行情况,Loop:L.D,F0,0,（,R1,）,（空转）,ADD.D,F4,F0,F2,（空转）,（空转）,S.D,F4,0,（,R1,）,DADDIU,R1,R1,#,8,（空转）,BNE,R1,R2,Loop,（空转）,Loop:L.D,F0,0,（,R1,）,DADDIU,R1,R1,#,8,ADD.D,F4,F0,F2,（空转）,BNE,R1,R2,Loop,S.D,F4,8,（,R1,）,因为修改指针,R1,的减,8,操作提前了，所以,S.D,指令中变址指针的偏移量要从,0,改为,8,.,2,指令流出时钟,Loop:L.D F0,0(R1)1,DADDIU R1,R1,#-8 2,ADD.D F4,F0,F2 3,（空转）,4,BNE R1,Loop 5,S.D F4,，,8(R1)6,一个元素的操作时间从,10,个时钟周期,减少到,6,个,其中,5,个周期是有指令执行,的，,1,个为空转周期,。,2,例子中的问题及解决方案,只有,L.D,、,ADD.D,和,S.D,这,3,条指令是有效操作，占用,3,个时钟周期。而,DADDIU,、空转,和,BEN,这,3,个时钟周期都是附加的循环控制开销。有效操作比例不高。,循环展开技术,把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件。,2,例,4.7,将例,4.6,中的循环展开,3,次得到,4,个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。,设,R1,的初值为,32,的倍数，即循环次数为,4,的倍数。因此不需要在循环体后面增加补偿代码。,方法：消除冗余的指令，并且不重复使用寄存器。,2,分配寄存器（不重复使用寄存器）,F0,、,F4,：用于展开后的第,1,个循环体,F2,：用于保存常数,F6,、,F8,：用于展开后的第,2,个循环体,F10,、,F12,：用于展开后的第,3,个循环体,F14,、,F16,：用于展开后的第,4,个循环体,2,展开后没有调度的代码,指令流出时钟,Loop:L.DF0,0(R1)1,（空转）,2,ADD.DF4,F0,F23,（空转）,4,（空转）,5,S.DF4,0,（,R1,）,6,L.DF6,-8(R1)7,（空转）,8,ADD.DF8,F6,F29,（空转）,10,（空转）,11,S.DF8,-8,（,R1,）,12,L.DF10,-16(R1)13,（空转）,14,指令流出时钟,ADD.DF12,F10,F215,（空转）,16,（空转）,17,S.DF12,-16(R1)18,L.DF14,-24(R1)19,（空转）,20,ADD.DF16,F14,F221,（空转）,22,（空转）,23,S.DF16,-24(R1)24,DADDIUR1,R1,#-3225,（空转）,26,BNER1,R2,Loop27,（空转）,28,2,结果分析,这个循环每遍共使用了,28,个时钟周期。,有,4,个循环体，完成,4,个元素的操作。,平均每个元素使用,28/4=7,个时钟周期,原始循环的每个元素需要,10,个时钟周期。,节省的时间：从减少循环控制的开销中获得的。,在整个展开后的循环中，实际指令只有,14,条，其他,14,个周期都是空转。,结论：效率并不高,2,对指令序列进行优化调度,指令流出时钟,Loop:L.DF0,0(R1)1,L.DF6,-8(R1)2,L.DF10,-16(R1)3,L.DF14,-24(R1)4,ADD.DF4,F0,F2 5,ADD.DF8,F6,F2 6,ADD.DF12,F10,F2 7,ADD.DF16,F14,F2 8,S.DF4,0(R1)9,S.DF8,-8(R1)10,DADDIUR1,R1,#-32 12,S.DF12,16(R1)11,BNER1,R2,Loop 13,S.DF16,8(R1)14,2,结果分析,没有数据相关引起的空转等待。,整个循环仅仅使用了,14,个时钟周期。,平均每个元素的操作使用,14/4=3.5,个时钟周期。,通过循环展开、寄存器重命名和指令调度，可以有效地开发出指令级并行。,2,循环展开和指令调度时要注意的问题,保证正确性。,在循环展开和调度过程中尤其要注意,两个地方的正确性：,循环控制，操作数偏移量的修改。,注意有效性。,只有能够找到不同循环体之间的无关性，才能有效地使用循环展开。,使用不同的寄存器。（否则可能导致新的冲突）,删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。,2,注意对存储器数据的相关性分析,例如对于,load,指令和,store,指令，如果它们在不同的循环迭代中访问的存储器地址是不同的，它们就是相互独立的，可以相互对调。,注意新的相关性,由于原循环不同次的迭代在展开后都到了同一次循环体中，因此可能带来新的相关性。,2,静态调度,依靠编译器对代码进行静态调度，以减少相关和冲突。,不是在程序执行的过程中、而是在编译期间进行代码调度和优化。,通过把相关的指令拉开距离来减少可能产生的停顿。,动态调度,在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。,4.2,指令的动态调度,2,指令的动态调度的,特点,能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器。,能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。,以硬件复杂性的显著增加为代价,2,4.2.1,动态调度的基本思想,到目前为止我们所使用流水线的最大的,局限性：,指令必须按序流出和执行,考虑下面一段代码：,DIV.D,F4,，,F0,，,F2,SUB.D F10,，,F4,，,F6,ADD.D F12,，,F6,，,F14,SUB.D,指令与,DIV.D,指令关于,F4,相关，导致流水线停顿。,ADD.D,指令与流水线中的任何指令都没有关系，但也因此受阻。,2,在前面的基本流水线中译码功能段的工作,ID,检测,结构,冲突,检测,数据,冲突,一旦一条指令受阻，其后的指令都将停顿。,解决办法：,允许乱序执行,2,为了允许乱序执行，将,5,段流水线的译码阶段再分为两个阶段：,流出,（,Issue,，,IS,）：指令译码，检查是否存在结构冲突。,读操作数,（,Read Operands,，,RO,）：等待数据冲突消失，然后读操作数。,IS,RO,检测,结构,冲突,检测,数据,冲突,2,在前述,5,段流水线中，顺序执行时是不会发生,WAR,冲突和,WAW,冲突的。但乱序执行有可能发生。,例：,DIV.D,F10,F0,F2,SUB.D,F10,F4,F6,ADD.D,F6,F8,F14,存在反相关,存在输出相关,可以通过使用寄存器重命名技术来消除相关。,2,动态调度的流水线支持多条指令同时处于执行当中。,要求：,具有多个功能部件、或者流水功能部件、或者兼而有之。,假设具有,多个功能部件。,指令乱序完成带来的,最大问题：,异常处理比较复杂,动态调度要保持正确的异常行为：只有那些在程序严格按程序顺序执行时会发生的异常，才能真正发生。,2,保持正确的异常行为：,对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行后，才允许它产生异常。,即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。,2,精确异常与不精确异常,精确异常：,发生异常时，处理机的现场跟严格按程序顺序执行时指令,i,的现场相同。,不精确异常：,当执行指令,i,导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令,i,的现场不同。,发生不精确异常的,原因：,当发生异常（设为指令,i,）时，流水线可能已经执行完按程序顺序是位于指令,i,之后的指令；,流水线可能还没完成按程序顺序是指令,i,之前的指令。,不精确异常使得在异常处理后难以接着继续执行程序。,2,4.2.2 Tomasulo,算法,核心思想,记录和检测指令相关，操作数一旦就绪就立即执行，把发生,RAW,冲突,的可能性减少到最小；,通过寄存器换名来消除,WAR,冲突,和,WAW,冲突,。,。,原因：,2,IBM 360/91,首先采用了,Tomasulo,算法,（,1,）,IBM 360/91,的设计目标是基于整个,360,系列的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能，因此需要更多地依赖硬件。,IBM 360,体系结构只有,4,个双精度浮点寄存器，限制了编译器调度的有效性。,360/91,的访存时间和浮点计算时间都很长。,（也是,Tomasulo,算法要解决的问题）,寄存器换名,可以消除,WAR,冲突和,WAW,冲突。,2,考虑以下代码：,DIV.DF0,，,F2,，,F4,ADD.D,F6,，,F0,，,F8,S.D,F6,，,0,（,R1,）,SUB.D,F8,，,F10,，,F14,MUL.D,F6,，,F10,，,F8,输出相关（,F6,）,导致,WAW,冲突,反相关（,F8,）,导致,WAR,冲突,2,消除名相关,引入两个临时寄存器,S,和,T,把这段代码改写为：,DIV.DF0,，,F2,，,F4,ADD.D,S,，,F0,，,F8,S.D,S,，,0,（,R1,）,SUB.D,T,，,F10,，,F14,MUL.D,F6,，,F10,，,T,两个,F6,都换名为,S,两个,F8,都,换名为,T,2,基于,Tomasulo,算法的,MIPS,处理器浮点部件的基本结构,2,保留站（,reservation station,）,每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。,包括：操作码、操作数以及用于检测和解决冲突的信息。,在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。,如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。,浮点加法器有,三,个保留站：,ADD1,，,ADD2,，,ADD3,浮点乘法器有,两,个保留站：,MULT1,，,MULT2,每个保留站都有一个,标识字段,，唯一地标识了该保留站。,2,公共数据总线,CDB,CDB,是,一条重要的数据通路,所有功能部件的计算结果都是送到,CDB,上，由它把这些结果直接送到（播送到）各个需要该结果的地方。,在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条,CDB,。,2,load,缓冲器和,store,缓冲器,用于存放读,/,写存储器的数据或地址,load,缓冲器,的作用：,存放用于计算有效地址的分量；,记录正在进行的,load,访存，等待存储器的响应；,保存已经完成了的,load,的结果（即从存储器取来的数据），等待,CDB,传输。,store,缓冲器,的作用：,存放用于计算有效地址的分量；,保存正在进行的,store,访存的目标地址，该,store,正在等待存储数据的到达；,保存该,store,的地址和数据，直到存储部件接收。,2,浮点寄存器,FP,共有,16,个浮点寄存器：,F0,，,F2,，,F4,，,，,F30,。,它们通过一对总线连接到功能部件，并通过,CDB,连接到,store,缓冲器。,指令队列,指令部件送来的指令放入指令队列,指令队列中的指令按先进先出的顺序流出,运算部件,浮点加法器完成加法和减法操作,浮点乘法器完成乘法和除法操作,2,在,Tomasulo,算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。,当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。,指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。,2,Tomasulo,算法的特点,冲突检测和指令执行控制是分布的。,每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。,计算结果通过,CDB,直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。,2,指令执行的步骤,使用,Tomasulo,算法的流水线需,3,段,：,流出,：从指令队列的头部取一条指令。,如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为,r,）。,如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站,r,。,如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站,r,。,一旦被记录的保留站完成计算，它将直接把数据送给保留站,r,。（寄存器换名和对操作数进行缓冲，消除,WAR,冲突）,完成对目标寄存器的预约工作 （消除了,WAW,冲突）,如果没有空闲的保留站，指令就不能流出。,（发生了结构冲突）,2,执行,当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。,load,和,store,指令的执行需要两个步骤：,计算有效地址（要等到基地址寄存器就绪）,把有效地址放入,load,或,store,缓冲器,写结果,功能部件计算完毕后，就将计算结果放到,CDB,上，所有等待该计算结果的寄存器和保留站（包括,store,缓冲器）都同时从,CDB,上获得所需要的数据。,2,每个保留站有以下,6,个字段：,Op,：要对源操作数进行的操作。,Qj,，,Qk,：将产生源操作数的保留站号。,等于,0,表示操作数已经就绪且在,Vj,或,Vk,中，或者不需要操作数。,Vj,，,Vk,：源操作数的值。,对于每一个操作数来说，,V,或,Q,字段只有一个有效。,对于,load,来说，,Vk,字段用于保存偏移量。,Busy,：为“,yes”,表示本保留站或缓冲单元“忙”。,A,：仅,load,和,store,缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。,2,Qi,：,寄存器状态表。,每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。,为,0,表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。,2,设有指令：,MUL F0,F2,F4,ADD F2,F0,F6,2,2,2,2,例,4.1,对于下述指令序列，给出当第一条指令完成并写入结果时，,Tomasulo,算法所用的各信息表中的内容。,L.DF6,，,34,（,R2,）,L.DF2,，,45,（,R3,）,MUL.D F0,，,F2,，,F4,SUB.D,F8,，,F2,，,F6,DIV.D F10,，,F0,，,F6,ADD.D F6,，,F8,，,F2,2,当采用,Tomasulo,算法时，在上述给定的时刻，保留站、,load,缓冲器以及寄存器状态表中的内容,。,指,令,指令状态表,流出,执行,写结果,L.D F6,34(R2),L.D F2,45(R3),MUL.DF0,F2,F4 ,SUB.D F8,F6,F2,DIV.DF10,F0,F6,ADD.D F6,F8,F2,2,Vk,Mem34+RegsR2,RegF4,Mem34+RegsR2,名称,保留站,Load1,Load2,Add1,Add2,Add3,Mult1,Mult2,Busy,no,yes,yes,yes,no,yes,yes,Op,LD,SUB,ADD,MUL,DIV,Vj,Qj,Load2,Add1,Load2,Mult1,Qk,Load2,A,45+RegsR3,寄存器状态表,F0 F2 F4 F6 F8 F10 F30,Qi,Mult1 Load2 Add2 Add1 Mult2,2,Tomasulo,算法的主要优点：,冲突检测逻辑是分布的,（通过保留站和,CDB,实现）,如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过,CDB,同时播送给所有这些指令，使它们可以同时执行。,消除了,WAW,冲突和,WAR,冲突导致的停顿,使用保留站进行寄存器换名，并且操作数一旦就绪就将之放入保留站。,2,4.4,多指令流出技术,如果每次只能流出一条指令（单流出），则,CPI,不可能小于,1,。,要想进一步提高性能，使,CPI,1,，就必须采用多流出技术。,2,单流出和多流出处理机执行指令的时空图,2,提高流水并行处理的方法,增加流水部件套数,超标量,合并多条指令操作码,超长指令字,细化流水部件段数,超流水,2,4.4.1,超标量方法（,Superscalar,）,在处理机内设置多个可并行操作的功能部件和多条流水线，在一个时钟周期内启动（发射）多条指令进行并行处理，使得,CPI,1,。,超标量方法是,采用,资源重复,的策略开发并行性。,超级标量机主要是借助对硬件资源重复来实现空间的并行操作。,2,采用超标量技术时,在每个时钟周期流出的指令条数,不固定,，依代码的具体情况而定（有上限）。,设这个上限为,n,，就称该处理机为,n,流出。,可以通过编译器进行指令的静态调度，也可以基于,Tomasulo,算法进行动态调度，以实现超标量技术。,2,理想的,RISC,机中指令流水的执行情况,理想的,RISC,机,取指,译码,执行,写回,0,1,2,3,4,5,6,T,7,2,在超标量机中每个时钟周期可同时启动三条指令的情况,0,1,2,3,4,5,6,T,取指,译码,执行,写回,每拍启动,3,条指令,要求并行度,=3,（,b,）超级标量机,配置多个功能部件,多个译码器，寄存器,端口，总线，能同时,执行多个操作。,2,单发射与多发射,发射：,处理机从指令存储单元取得指令的过程,单发射：,处理机在单时钟周期内只能取出一条指令供执行。,处理机只有一个,IF,和,ID,部件，但可以有多个运算部件。,多发射：,处理机在单时钟周期内可取出多条指令供执行。,处理机必须设置多个,IF,、,ID,、,WR,等部件。,2,超标量机的典型结构,主,存,D-cache,存储器操作部件,ALU,1,2,条指令并行,取出并同时译码,I-cache,2,指,令,调,度,转移控制部件,状态,记录部件,RF,寄存器,堆,译码器,2,指令执行部件,的功能,存储器操作部件,：,执行,Load,、,Store,指令,ALU,：,执行整数运算,转移控制部件,：,执行转移指令,2,指令调度部件（状态记录部件）的功能,进行流水动态调度。依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度的重叠工作。,对流水线中的各个功能部件的工作状态、进入流水线中的各条指令的工作状态、它们所使用的源寄存器和目的寄存器情况等进行集中的统一记录和调度。,在译码阶段，状态记录部件根据所记录的状态决定是否将译码后的指令发送给有关功能部件进行处理。,2,指令调度部件的主要检查内容,指令要使用的功能部件是否已被流水线中的其它指令占用（,资源冲突,）；,指令的源操作数寄存器是否为其它指令的目的寄存器，或者它所要写入的目的寄存器又正好是前面其它指令所要读出的操作数，或是要写入的目的寄存器。即检查是否存在,RAW,、,WAR,、,WAW,的数据相关。,2,多流水线中指令的发射策略（调度方法）,采用不同发射策略的目的：减少相关性。,1.,从指令的发射顺序和完成顺序两个方面考虑,顺序发射,：指令的发射顺序是按照程序中指令的排列顺序进行的。,乱序发射,：指令的发射顺序不是按照程序中指令的排列顺序进行的。,顺序完成,：指令的完成顺序是按照程序中指令的排列顺序进行的。,乱序完成,：指令的发射顺序不是按照程序中指令的排列顺序进行的。,2,2.,三种策略,顺序发射顺序完成,优点：流水线的控制逻辑比较简单,缺点：使吞吐率和效率降低,（是调度策略的基础，但死板、不实用）,顺序发射乱序完成,优点：缩短了流水线中任务的总的执行时间，提高了功能部件的利用率。,缺点：,指令执行时间长短不一，,控制逻辑比较复杂。,2,乱序发射乱序完成,优点：功能部件的利用率最高，流水线中任务的总的执行时间最短。,缺点：需要硬件、软件的支持，控制复杂。,需设置先行指令窗口、数据相关分析部件、功能部件冲突检测部件等。通常采用记分牌机制分析数据的相关性和功能部件的冲突，通过优化编译对指令序列进行重组开发程序中指令的并行性。,2,乱序发射乱序完成中的先行指令窗口,指令译码后,先行指令,窗口 功能单元,未满，不断送至窗口,可用，取窗口不断执行,2,目前，许多高性能超标量处理机中均采用了乱序发射乱序完成 的指令调度方法。,2,超标量机的主要特点,(1),配置有多个性能不同的处理部件，采用多条流水线并行处理。,(2),能同时对若干条指令进行译码，将可并行执行的指令送往不同的执行部件，从而达到在每个周期启动多条指令的目的。,(3),在程序运行期间由硬件,(,通常是状态记录部件和调度部件,),检查操作的并行性，完成指令的调度。,2,4.4.2,超长指令字,VLIW,超长指令字,（,Very Long Instruction Word,）,以一条长指令来实现多个操作的并行执行，以减少对存储器的访问。,在每个时钟周期流出的指令条数是,固定的,，将这些指令构成一条长指令或者一个指令包。,在指令包中，指令之间的并行性通过指令显式地表示出来。,指令调度由编译器静态完成,。,2,超长指令字的实现,在处理机中设置多个可并行操作的功能部件。在一条超长指令字的多个操作控制字段的直接控制下并行操作。,超长指令字是采用,资源重复,的策略开发并行性。,超长,指令字的长度达上百位，甚至上千位。,超长指令字的,并发操作主要是在流水的执行阶段进行的。,2,例：在执行阶段并行执行三个操作,0,1,2,3,4,5,6,T,3,个操作,每拍启动一条长指令，执行,3,个操作，相当于,3,条指令，要求并行度,=3,超长指令字计算机（,VLIW,）的原理结构,取指,译码,执行,写回,2,超长指令机的主要特点,(1),单一的控制流。只有一个控制器，每个周期启动一条长指令。,(2),超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。,(3),含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件较简单。,(4),在编译阶段完成超长指令中多个可并行执行操作的调度。,2,例：一个含有两个存取部件、一个浮点加部件和一个浮点乘部件的,VLIW,机。,主,存,VLIW,中的操作字段：,RF,（寄存器堆）,LD/ST1,LD/ST2,FADD,FMUL,LD/ST1,LD/ST2,FADD,FMUL,存,/,取,1,存,/,取,2,浮点加,浮点乘,2,在,VLIW,机中，所有功能部件均由同一时钟驱动，在同一时刻控制每个功能部件的操作字段组成一个超长指令字。,超长指令字的指令字长度与功能部件的数量有关。,超长指令字的生成是由编译器来完成的。编译器将串行的操作序列合并为可并行执行的指令序列，以最大限度实现操作并行性。,超长指令字的压缩技术可分为局部压缩和全局压缩两种方法,2,在程序基本块范围内进行指令压缩。,表调度法,是局部压缩方法中的一种。,例：实现以下赋值语句：,C,A,B,K,I,J,L,M,K,Q,CK,若按串行操作进行，则其所用的指令序列为：,1.,局部压缩,2,共需,14,个周期,源代码,源代码,所需周期,C=A+B,LOAD A,LOAD B,C=A+B,STORE C,1,1,1,1,K=I+J,LOAD I,LOAD J,K=I+J,STORE K,1,1,1,1,L=M-K,LOAD M,L=M-K,STORE L,1,1,1,Q=CK,Q=CK,STORE Q,2,1,2,压缩技术,表调度法,只需要,6,个周期。,超标量结构、超流水线结构一般采用指令窗方法，把一段指令（长度为窗口的大小，例为,8,）取到窗口中，判断这段指令能否并行执行。,LOAD A,LOAD B,LOAD I,LOAD J,C=A+B,LOAD M,STORE C,K=I+J,STORE K,L=M-K,Q=CK,STORE L,STORE Q,2,2.,全局压缩法,全局压缩是指进行压缩的代码操作可在基本块之间移动。,全局压缩法可获得更好的压缩效果。,全局压缩的代码操作在基本块间移动需有一定的限制，而且为了保持程序原来的语义，某些代码操作移动后，通常还需要增加一些辅助操作。,全局压缩主要有三种方法：,路径调度,(Trace scheduling),渗透调度,(Percolation scheduling),软件流水,(Software pipelining),。,2,VLIW,机与超标量机的比较,类型,译码,并行检测完成时间,代码密度,目标可移植性,VLIW,简单,编译,较差,不可移植,超标量,复杂,运行,较好,可移植,2,4.4.3,超流水线处理机,超流水线处理机,将每个流水段进一步细分，使流水线在一个时钟周期内能够分时流出多条指令。,对于一台每个时钟周期能流出,n,条指令的超流水线计算机来说，这,n,条指令不是同时流出的，而是每隔,1/n,个时钟周期流出一条指令。,实际上该超流水线计算机的流水线周期为,1/n,个时钟周期。,超流水方法是采用,时间重叠,的策略开发并行性。,2,每个时钟周期分时流出两条指令的超流水线计算机的时空图,2,在分解流水段时要根据实际情况，有些流水段分解的流水级数可多些；如“译码（,ID,）”流水段，可以再细分为“译码”流水级、“取第一个操作数”流水级和“取第二个操作数”流水级等；有些流水段分解的流水级数可少些，也的流水段可以不再细分，如“写回结果”流水段一般不再细分。,2,超流水线技术不用增加硬件，而是采用时间重叠的方法将流水线中各功能段的延迟时间缩短。,利用超流水线技术可提高系统的时钟频率。,但是流水深度加深后，当指令间出现各种相关时所引起的流水线的停顿时间也将增长。,2,MIPS R4000,指令流水线结构,2,各级的功能,IF,：取指令的前半步，根据,PC,值去启动对指令,Cache,的访问。,IS,：取指令的后半步，在这一级完成对指令,Cache,的访问。,RF,：指令译码，访问寄存器组读取操作数，冲突检测，并判断指令,Cache,是否命中。,EX,：指令执行。包括有效地址计算，,ALU,操作，分支目标地址计算，条件码测试。,2,DF,：,取数据的前半步，启动对数据,Cache,的访问。,DS,：,取数据的后半步，在这一级完成对数据,Cache,的访问。,TC,：,标识比较，判断对数据,Cache,的访问是否命中。,WB,：,load,指令或运算型指令把结果写回寄存器组,。,2,MIPS R4000,指令流水线时空图,2,超标量超流水机,将超标量和超流水方法结合起来时，可获得最高的性能增益。,例：将每个时钟周期可启动,3,条指令、并行度为,3,的超标量技术和每,1/3,个时钟周期可启动一条指令、并行度为,3,的超流水技术结合，可得到每一个机器周期最多可启动,9,条指令的超标量、超流水处理机。,2,超标量超流水线处理机的指令执行时空图,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,I3,I2,I1,时钟周期,1,2,3,4,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,0,2,超标量超流水线处理机在一个时钟周期内要发射指令,n,次，每次发射指令,m,条，因此，超标量超流水线处理机每个时钟周期总共要发射指令,mn,条。,2,超标量超流水机的特点,在一个时钟周期中可以启动多条指令并行操作。,因为超标量技术需增加硬件，超流水技术需增加时钟频率。因此要求增高芯片集成度，对芯片的要求高。,2,4.4.4,超级流水线的性能比较,超标量处理机、超流水线处理机和超标量超流水