并行计算机体系结构第三章

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 流水和向量处理,3.1,提高计算机速度的措施,MIPS=IPC*f,c,其中,IPC,为每拍流出的指令条数。提高,IPC,和,f,c,是提高计算机速度最直接最有效的方法。,提高,IPC,：增加每拍并行流出的指令条数和配置更多的功能部件。空间并行。,提高,f,c,：功能部件应该能在更高的频率下工作。时间平行。,可以用,P=O,（,s*f,）衡量系统的潜在性能，,s,是与设备量成正比的功能部件并行度，,f,是主频。,3.1.1,提高频率,提高系统的频率是提高系统性能的最直接的方法，但是频率的提高具有很大的难度：,1.,器件的速度和集成度,2.,流水线分站的代价和效率,3.,高速信号传输,4.,时钟沿的离散,5.,高密度组装工艺和冷却技术,*往往当通过提高频率来提高计算机的速度不能满足要求时，我们才考虑空间并行性,3.1.1,空间并行,为了达到更高的主频，需要特殊技术并且代价巨大。这导致了大规模并行处理系统,MPP,的出现。,可以设置多个功能部件支持向量、超标量、超长指令字和超流水结构。空间并行性可以有效提高计算机速度，速度提高的最大倍数,=e,性价比：,PCR=1/(T/k+t,d,)(C+kd),其中,k,为流水线站数，,T,为每段执行时间，,t,d,为站流水线的延迟时间，,C,为功能部件的价格。,流水线的设计原理,令（,PCR,）,=0,，得到,因为,（,PCR,）,0,，所以此时,k,站流水线的性价比最高,同时为了减少站寄存器的位数，分段时往往选在连线最少的部位。如果每段时间无法保持一致，则,M,（最大段执行时间）和,t,d,同时决定了流水线的工作周期。其频率为,1/(,M,+ t,d,).,由于工程实现时元件的布局和器件时间参数离散等原因，到达各站寄存器的时钟信号时离散的。,流水线的设计原理,设相邻两站的最大离散值为,，则工作频率降低为,1/(,M,+ t,d,+,),。,书本,35-36,页，图,3.2,信号穿透问题。,非线性流水线的调度,非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。,1.,非线性流水线的表示,线性流水线能够用流水线连接图唯一表示,对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表,例如：,非线形流水线的连接图和预约表,一张预约表可能与多个流水线连接图相对应,一个流水线连接图对应于多张预约表,2.,非线性流水线的冲突,启动距离：连续输入两个任务之间的时间间隔,流水线冲突：几个任务争用同一个流水段,3.,无冲突调度方法,由及其学生于,1971,年提出,禁止向量,：预约表中每一行任意两个,“,”,之间距离的集合。上例中为,（,3,，,4,，,6,）,冲突向量,：,C,（,C,m,C,m-1,C,2,C,1,）,其中：,m,是,禁止向量中的最大值。,如果,i,在禁止向量中，则,C,i,1,，否则,C,i,0,。,上,例中,C,(101100),例：一条,4,功能段的非线性流水线，每个功能段的延迟时间都相等为,t,，它的预约表如下：,(1),写出流水线的禁止向量和初始冲突向量。,(2),画出调度流水线的状态图。,(3),求最小启动循环和最小平均启动距离。,(4),求平均启动距离最小的恒定循环。,(5),按照最小启动循环连续输入,4,个任务，求流水线实际吞吐率。,解：,(1),禁止向量为：,(2,，,4,，,6),初始冲突向量：,S = 101010,(2),构造状态图,S,逻辑右移,2,、,4,、,6,位时，不作任何处理，,逻辑右移,1,、,3,、,5,和大于等于,7,时：,S,右移,1,位之后：,010101101010,111111,，,S,右移,3,位之后：,000101101010,101111,，,S,右移,5,位之后：,000001101010,101011,，,S,右移,7,位或大于,7,位后：还原到它本身。,101111,右移,5,位之后：,000001101010,101011,，,101011,右移,3,位之后：,000101101010,101111,，,101011,右移,5,位之后：,000001101010,101011,。,简单循环：,状态图中各种冲突向量只经过一次的启动循环。,(3),最小的启动循环,为（,1,，,7,）和（,3,，,5,）,平均启动距离为,4,。,(4),启动距离最小的恒定循环为（,5,）,(4),按照最小启动循环（,1,，,7,）连续输入,4,个任务，流水线实际吞吐率为：,1/,（,4,t,）,数据相关,(,局部相关,),数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。,控制相关：由条件分支指令、转子程序指令、中断等引起的相关。,解决数据相关的方法有两种：,推后处理,设置专用路径,1.,指令相关,发生指令相关的情况：,n,：,STORE R1,n,+1,n,+1,：,满足关系： 结果地址,(,n),指令地址,(,n,+1),当第,n,条指令还没有把执行结果写到主存之前，取出的第,n,+1,条指令显然是错误的。,在,k,个流水段的流水线处理机中，第,n,条指令要修改从第,n+,1,到第,n+ k,指令中的任意一条指令，都可能造成程序执行结果发生错误。,在采用先行控制方式的处理机中，如果执行部件正在执行第,n,条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误,:,存放在先行操作栈中的指令,正在指令分析器中分析的指令,已经预取到先行指令缓冲栈中的指令,更严重的是：有些分支指令，可能已经在指令分析器中执行完成。,解决指令相关的根本办法是：,在程序执行过程中不允许修改指令。,现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。,在,IBM370,系列机中，用,“,执行,”,指令来解决：在程序执行过程中既能够修改指令，程序又具有再入性。,“,执行”指令执行由第二地址,(X,2,)+(B,2,)+D,2,),决定的主存数据区中的指令。,2.,主存操作数相关,(,相邻两条指令之间出现对主存同一单元要求先写后读的关联,),发生主存操作数相关的指令序列：,n,：,OP A,1,，,A,2,，,A,3,；,A,1,(A,2,) OP (A,3,),n+1,：,OP A,1,，,A,2,，,A,3,；,A,1,(A,2,) OP (A,3,),出现下列情况之一，就发生主存操作数相关：,A,1,（,n,）,A,2,（,n,1,）,A,1,（,n,）,A,3,（,n,1,）,解决办法,(,出现概率低,不宜采用设置专用通路,),：,对于访问主存储器的请求，写结果的优先级高于读操作数，实现自动推后处理。,3.,通用寄存器数据相关,发生寄存器数据相关的可能性很大，影响面也很大,n,：,OP R,1,，,A,2,；,R,1,(R,1,) OP (A,2,),n+1,：,OP R,1,，,R,2,；,R,1,(R,1,) OP (R,2,),发生,R,1,(n),R,1,(n,1),称为,R,1,数据相关。,发生,R,1,(n),R,2,(n,1),称为,R,2,数据,相关。,解决通用寄存器数据相关的方法：,方法一：把读操作数、写运算结果与指令执行合在一个节拍。,采用一种典型的运算器结构，通用寄存器到运算器之间建立有直接数据通路，即不设置缓冲寄存器或锁存器。,当发生下述情况时，不能采用这种方法：,当寄存器个数多时，读写寄存器的时间长,当功能部件的执行时间比较长，或要求指令的执行时间短时,方法二：建立相关专用通路,(ByPass),由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路，以增加硬件为代价减少速度损失。,在运算器的输出端到锁存器输入端之间建立一条专用的数据通路。,变址相关：,在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关，发生概率较高，通常多采用设置专用通路的方法解决相关问题。,4. LOAD,相关,LOAD,操作的执行时间可能比较长,n,：,LOAD R,1,，,A,；,R,1,(A),n+1,：,ADD R,1,，,R,2,；,R,1,(R,1,) OP (R,2,),如果,R,1,(n),R,2,(n,1),，或,R,1,(n),R,1,(n,1),，,则发生,LOAD,数据相关。,解决方法：,方法一：,由编译器在,LOAD,之后插入不发生数据相关的指令，,由于,LOAD,的执行时间不确定，不能根本解决问题,方法二：,由硬件自动插入空操作，直到,LOAD,操作完成,在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。,控制相关,(,全局相关,),因程序的执行方向可能被改变而引起的相关，也称为,全局相关,。,主要包括：,无条件转移、一般条件转移、复合条件转移、中断,等。,1.,无条件转移,在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。,如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。,如果转移目标指令,L,不在先行指令缓冲栈中,，则要将先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令,L,。,如果转移目标指令,L,在先行指令缓冲栈中,，只要作废先行指令缓冲栈中的部分指令。,无条件转移指令一般对指令执行部件的工作不会造成影响。,为进一步减少无条件转移指令造成的影响，,在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器,2.,一般条件转移,k,：,;,置条件码,CC,k+1,：,JMP(CC) L ;,如果,CC,为真转向,L,L,：,当条件码是上一条指令产生时，相关最严重,无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。,无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。,如果转移成功：指令,L,已经在先行指令缓冲栈，指令分析器接着,“,分析,L,”,，如果指令,L,不在先行指令缓冲栈，指令分析器要等待一个周期。,转移不成功，对程序执行影响不大，,当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。,在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。,3.,复合条件转移,k,：,OP L ;,产生条件码，并决定是否转向,L,L,：,如果转移不成功：不造成任何影响，就象普通的运算型指令一样,如果转移成功：造成的影响比一般条件转移指令还要大得多。,全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。,必须采取策略，减小转移成功造成的影响。,条件分支对流水线的影响,处理好条件转移和中断的关键问题有两个：,要确保流水线能够正常工作,减少因,“,断流,”,引起的吞吐率和效率的下降,1.,条件分支的处理方法,条件转移指令对流水线的影响很大，必须采取措施来减少这种影响。可能的措施有：,(1),延迟转移技术和指令取消技术,只能用于单流水线处理机中，且流水线的级数不能太多；,据统计，,编译器调度一条指令成功的概率在,90,以上，而调度两条指令成功的概率只有,40,左右。,当没有合适的指令可调度时，编译器只能插入空操作。,(2),动态分支预测技术,根据近期转移是否成功的记录来预测下一次转移的方向。,所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。,(3),静态分支预测技术,转移预测的方向是确定的，或者预测转移不成功，或者预测转移成功，,在程序实际执行过程中，转移预测的方向不能改变。,静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。,TI,公司的,SuperSPARC,处理机采用了静态转移预测技术，而且设置有转移目标缓冲栈，在两个方向上都预取指令。,2.,条件分支在流水线中的执行过程,因为第,i,条指令所需要的条件码由第,i-1,条指令给出；在一条由,k,个功能段的流水线中，第,i-1,条指令要等到第,i+k-2,条指令进入流水线时才能形成条件码。,转移不成功，猜测正确，流水线的吞吐率和效率没有降低，,转移成功，猜测错误，要先作废流水线中已经执行的,i+1,、,i+2,、,、,i+k-2,指令；然后再从分支点开始执行第,P,、,p+1,、,指令。,条件分支指令在流水线中的执行过程,当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。,例如，若第,i+1,条指令是：,(R1,(R2)R1,，,寄存器,R1,中内容就被破坏，整个程序执行的结果是错误的。,目前的处理机有两种做法：,一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；,另一种方法是一直执行到运算完成，但不送回运算结果。,静态分支预测技术,静态分支预测：,在程序执行过程中转移预测方向不能改变,动态分支预测：,在程序执行过程中能够改变转移预测方向,本节讲静态预测技术,1.,软件,“,猜测法,”,目标：,通过编译器尽量降低转移成功的概率。,例如：对于循环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水线极为不利。,软件,“,猜测法,”,：,通过编译器降低转移成功的概率,2.,硬件,“,猜测法,”,方法：,通过改变硬件结构来降低转移指令对流水线的影响,在先行指令缓冲栈的人口处设置一个简单的指令分析器，当检测到转移指令时，就把转移目标地址,L,送入先行程序计数器,PC,1,中，同时保留当前,PC,1,中的内容到另一寄存器中。,转移成功，猜测正确。对转移指令对流水线不造成影响。,转移不成功，用保存下来的地址恢复,PC,1,和,PC,。,软硬件共同配合，都往同一个方向去猜测。,3.,两个先行指令缓冲栈,向前条件转移，转移成功与不成功各,50%,在先行指令缓冲栈中,增加一个先行目标缓冲栈,按照转移成功的方向预取指令到先行目标缓冲栈中。,先行指令缓冲栈仍然按照转移不成功的方向继续预取指令。,如果转移不成功，则继续分析原来先行指令缓冲栈中指令。,如果转移成功，则分析新增设的先行目标缓冲栈中的指令。,提前形成条件码,必要性：对提高流水线的性能非常有效,可能性：,可在运算开始或中间产生条件码,对于乘除法，两个源操作数的符号相同结果为正，符号相反结果为负,对于乘法，有一个操作数为,0,，则乘积为,0,被除数为,0,，商为,0,； 除数为,0,，除法结果溢出,同号加或异号减，结果符号与第一操作数相同,异号加或同号减，结果的符号与绝对值大的操作数相同,溢出及是否为,0,可以通过一个比较器提前产生,精确断点与不精确断点,对于输入输出设备的中断服务，实际上不需要有精确断点。,比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。,对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：,不在于缩短时间，关键是要正确保存现场和正确恢复断点。,不精确断点,(Imprecise),，,流水线可以不断流,需要的硬件比较少，控制逻辑比较简单,中断响应时间加长,采用不精确断点法可能会发生如下两个问题：,(1),程序的调试困难,早期的流水线处理机，多采用不精确断点法,近期的流水线处理机一般都采用精确断点法,(2),程序执行的结果可能出错，例如：,i,：,FADD R1, R2,；,(R1),(R2)R1,i+1,：,FMUL R3, R1,；,(R3)(R1)R3,当第,i,条指令执行到,S,6,段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，已经进入流水线的第,i+1,条指令将执行完成；因为第,i+1,条指令使用了不正确的,R1,，所以浮点乘法的执行结果是不正确的。,采用精确断,(Precise),点法，要设置一定数量的后援寄存器,，把整个流水线中所有指令的执行结果和现场都保存下来。,动态调度技术,实现方法：,由硬件动态调整指令执行顺序，以减少数据相关造成的影响。,主要优点：,能够处理在编译时无法确定的相关，并简化编译器设计,在其他流水线机器上编译的目标代码也能够高效运行,用静态调度法生成的代码也能在动态调度法的机器中运行,主要缺点：,指令级并行度低，因为只能在比较小的范围内寻找并行性,顺序流动与乱序流动,1.,顺序流动方式：,任务按顺序流入流水线,也按顺序流出流水线,把如下一段程序输入到这条流水线中：,k,：,R0,（,R1,）,k+1,：,k+2,：,R2,（,R0,）（,R3,）,k+3,：,k+4,：,k+5,：,指令,k+2,无法继续执行，要在功能段,S,2,中等待。,后续的指令,k+4,、,k+5,、,等也不能进入流水线。,功能段,S,3,、,S,4,、,S,5,将逐渐空闲。,缺点：,吞吐率和效率降低,优点：,流水线的控制逻辑比较简单,流水线,“,断流,”,，有些功能段,“,空闲,”,2.,乱序,(Out of order),流动方式：,指令流出流水线的顺序与流入流水线的顺序不同。,又称为,错序流动方式、无序流动方式、异步流动方式等。,乱序流动中的数据相关,在乱序流动方式中，可能发生三种数据相关,写写相关,k,：,LOAD F1, A ;F1,（,A,）,写读相关,k+1,：,FADD F2, F1 ;F2,（,F2,）,+,（,F1,）,k+2,：,FMUL F1, F3 ;F1,（,F1,）,（,F3,）,k+3,：,STORE F1, B ;B,（,F1,）,读写相关,(1),写读相关：,指令,k,与指令,k+1,之间关于,F1,的相关，又称为数据相关、先写后读相关、流相关、,WR,相关、,RAW,相关等。,(2),读写相关：,指令,k+1,与指令,k+2,之间关于,F1,的相关，变量名相关、先读后写相关、反相关、,RW,相关、,WAR,相关等。,(3),写写相关：,指令,k,与指令,k+2,左边的,F1,之间的相关关系称为：输出相关、写写相关、,WW,相关、,WAW,相关或写后再写相关等。,有时把,相关,称为,“,冒险,”,(hazard),、,“,竟争,”,(competition),等。,在程序执行过程中，只有避免相关，执行结果才是正确的。,三种数据相关可以用下列关系式来表示：,对于写读相关,D(i) S(j) ,对于读写相关,S(i) D(j) ,对于写写相关,D(i) D(j) ,数据重定向方法,1.,三种数据相关的重定向,重定向之前，,j,只能在,i,之后执行。,重定向之后，可以做到：,(1),写读相关，,j,与,i,可以同时执行,即专用数据通路,(2),写写相关，,先后顺序无关,(3),读写相关，,先后顺序无关,后两种情况又称为,“,变量换名技术,”,2.,变量换名技术,用来自动消除,读写数据相关,和,写写数据相关,规则：,一个变量只允许定值一次,在三种数据相关中，实际上只有写读数据相关必须依靠硬件、或采用软硬件结合的方法来解决,解决方法：,推后处理,或,专用数据通路,在上面的数据重定向图中，把,B,换成了,B,，并在以后的都引用,B,读写数据相关和写写数据相关就不存在了。,三种主流处理机,(,指令级高度并行的超级处理机,),：,超标量处理机,超流水线处理机,超标量超流水线处理机,基本结构,普通标量流水线处理机：,一条指令流水线,，一个多功能操作部件，,每个时钟周期平均执行指令的条数小于,1,。,多操作部件标量处理机：,一条指令流水线,，多个独立的操作部件，,指令级并行度小于,1,。,超标量处理机典型结构：,多条并行工作的指令流水线,，,多个独立的操作部件，,指令级并行度（,ILP,）大于,1,。,Motorola,公司的,MC88110,有,10,个操作部件,两个寄存器堆：,整数部件通用寄存器堆，,32,个,32,位寄存器,浮点部件扩展寄存器堆，,32,个,80,位寄存器,缓冲深度为,4,的先行读数栈,缓冲深度为,3,的后行写数栈,两个独立的高速,Cache,中，各为,8KB,，采用两路组相联方式,转移目标指令,Cache,，用于存放另一条分支上的指令,单发射与多发射,1.,单发射处理机,(,普通流水线标量处理机,),：,每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果。,取指令部件和指令译码部件各设置一套；,只设置一个多功能操作部件或设置多个独立的操作部件；,操作部件中可以采用流水线结构，也可以不采用流水线结构。,目标是每个时钟周期平均执行一条指令，,ILP,的期望值为,1,。,2.,多发射处理机：,每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。,多个取指令部件，多个指令译码部件和多个写结果部件。,设置多个指令执行部件，有些指令执行部件采用流水线结构。,目标是每个时钟周期平均执行多条指令，,ILP,的期望值大于,1,。,3.,超标量处理机,(,一个时钟周期内同时发射多条指令的处理机,),：,有两条或两条以上能同时工作的指令流水线。,先行指令窗口,：能够从指令,Cache,中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测，提高功能部件利用率，一般取,2-8,条指令。,由于程序中指令并行性的开发有限，所以度,m,比较低，理论上最佳,m=3,。,超标量处理机的指令级并行度：,1,ILP,m,。,超标量处理机非常适合于求解像稀疏向量或矩阵这类标量计算问题。,多流水线调度,顺序发射,(in-order issue),与乱序发射,(out-order issue),：,指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射,顺序完成,(in-order completion),与乱序完成,(out-order completion),：,指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成,多流水线的调度主要有三种方法：,顺序发射顺序完成,顺序发射乱序完成,乱序发射乱序完成,以如下,6,条指令组成的程序为例，说明这三种调度方法（,m=2,）,I,1,：,LOAD R1, A,；,R1(A),I,2,：,FADD R2, R1,；,R2(R2),(R1),I,3,：,FMUL R3, R4,；,R3(R3)(R4),I,4,：,FADD R4, R5,；,R4(R4),(R5),I,5,：,DEC R6,；,R6(R6),1,I,6,：,FMUL R6, R7,；,R6(R6)(R7),6,条指令中有,4,个数据相关，包括,2,个写读相关，,1,个读写相关和,1,个写写相关。,1.,顺序发射顺序完成,共用,10,个时钟周期完成,还有,8,个空闲的时钟周期,2.,顺序发射乱序完成,总的执行时间为,9,个时钟周期，,节省了一个时钟周期。少了,5,个空闲时钟周期。,3.,乱序发射乱序完成（采用先行指令窗口，度,m=3,）,没有空闲周期，功能部件得到充分利用。,总的执行时间为,8,个周期，节省,2,个周期。,资源冲突,如果操作部件采用流水线结构，发生资源冲突的可能性很小；,如果不采用流水线结构，发生资源冲突的可能性就比较大。,下面是一个由,4,条指令的程序例子：,I1,：,FADD R0, R1,；,R0(R0),(R1),I2,：,FMUL R2, R3,；,R2(R2)(R3),I3,：,FADD R4, R5,；,R4(R4),(R5),I4,：,FMUL R6, R7,；,R6(R6)(R7),操作部件不采用流水线：,做完,4,条指令总共用了,11,个周期，,有,5,个空闲周期,。,操作部件采用流水线：,做完,4,条指令共用,8,个周期，,少用,3,个周期。,操作部件采用流水线结构的原因分析,假设每个周期发射,m,条指令，操作部件的延迟时间为,k,个周期，,如果操作部件不采用流水线结构，则使用同一个操作部件的两条指令序号应该,至少相差,mk,如果操作部件采用,k,段流水线结构，则使用同一个操作部件的两条指令,只需相差,m,或,m,以上,操作部件的延迟时间,k,一般在,4,至,10,之间，每个时钟周期发射的指令条数,m,在,2,至,4,之间。取中间值，,k,7,，,m,3,为了不发生资源冲突，如果操作部件不采用流水线结构，,两条使用同一个功能部件的指令序号必须相差,21,或,21,以上。,如果操作部件采用流水线结构，,两条使用同一个功能部件的指令序号只需要相差,3,或,3,以上。,因此，在超标量处理机中，操作部件一般要采用流水线结构。,如果由于某种原因，操作部件不能采用流水线结构，则必须设置多个相同种类的操作部件,普通标量处理机，希望相同操作连续出现。,只有连续出现相同操作的指令序列时，流水线的效率才能得到充分发挥。,超标量处理机,则正好相反，,希望相同操作不要连续出现,。,相同操作的指令序列连续出现时，会发生资源冲突；,要求相同操作的指令能够相对均匀地分布在程序中。,超标量处理机的这种要求正好符合一般标量程序的特点,。,超标量处理机性能,单流水线普通标量处理机的指令级并行度记作,(1, 1),，,超标量处理机的指令级并行度记作,(m, 1),，,超流水线处理机的指令级并行度记作,(1, n),，,而超标量超流水线处理机的指令级并行度记作,(m, n),。,在理想情况下，,N,条指令在单流水线标量处理机上的执行时间为：,T(1, 1),(k,N,1),t,在每个周期发射,m,条指令的超标量处理机上执行的时间为：,超标量处理机相对于单流水线标量处理机的加速比为：,超标量处理机的加速比的最大值为：,S,(,m,1),MAX,m,超流水线处理机的两种定义：,在一个基本时钟周期内分时发射多条指令的处理机,指令流水线的段数大于等于,8,的流水线处理机（深度流,水）,提高处理机性能的两种方法：,通过增加硬件资源来提高处理机性能（空间并行性）,通过各部分硬件的重叠工作来提高处理机性能（时间并,行性）,两种不同并行性：,超标量处理机采用的是空间并行性。,超流水线处理机采用的是时间并行性。,指令执行时序,每隔,1/n,个时钟周期发射一条指令,，,即处理机的流水线周期为,1/n,个时钟周期。,典型处理机结构,MIPS R4000,处理机：,每个时钟周期包含两个流水段,是一种很标准的超流水线处理机结构。,指令流水线有,8,个流水段。,指令,Cache,和数据,Cache,的容量各,8KB,，,每个时钟周期可以访问,Cache,两次，,在一个时钟周期内可以从指令,Cache,中读出两条指令，从数据,Cache,中读出或写入两个数据。,主要运算部件有整数部件和浮点部件。,如果在,LOAD,指令之后的两条指令中，任何一条指令要在它的,EX,流水级使用这个数据，则指令流水线要暂停一个时钟周期。,超流水线处理机性能,指令级并行度为,(1,n),的超流水线处理机，执行,N,条指令所的时间为：,超流水线处理机相对于单流水线普通标量处理机的加速比为：,加速比的最大值为：,S(1, n),MAX,n,超标量超流水线处理机,一个时钟周期发射,n,次，每次发射,m,条指令，每个时钟周期共发射指令,mn,条。同时开发空间并行性和时间并行性,指令执行时序,典型处理机结构,DEC,公司的,Alpha,处理机为典型的,超标量超流水线结构,。,主要由四个功能部件和两个,Cache,组成：整数部件,EBOX,浮点部件,FBOX,地址部件,ABOX,中央控制部件,IBOX,指令,Cache,和数据,Cache,在,EBOX,内还有多条专用数据通路，可以把运算结果直接送到执行部件。,中央控制部件,IBOX,能够同时完成：,同时读出两条指令；,同时对两条指令进行译码，并作相关性检测；,如果资源和相关性允许，,IBOX,就把两条指令同时发射给,EBOX,、,ABOX,和,FBOX,三个执行部件中的两个。,指令流水线的控制方式：,采用,顺序发射乱序完成,。,在指令,Cache,中有一个转移历史表，实现条件转移的动态预测。,Alpha 21064,处理机共有,三条指令流水线：,(1),整数操作流水线为,7,个流水段,，其中，取指令,2,个流水段、分析指令,2,个流水段、运算,2,个流水段、写结果,1,个流水段。,(2),访问存储器流水线为,7,个流水段,。,(3),浮点操作流水线分为,10,个流水段,，其中，浮点执行部件,FBOX,的延迟时间为,6,个流水段。,三条指令流水线的平均段数为,(7+7+10)/3=8,，且每个时钟周期发射两条指令。因此，,Alpha 21064,处理机为超标量超流水线处理机。,超标量超流水线处理机的性能,指令级并行度为,(m,n),的超标量超流水线处理机，连续执行,N,条指令所需要的时间为：,超标量超流水线处理机相对于单流水线标量处理机的加速比为：,在理想情况下，超标量超流水线处理机加速比的最大值为：,S,(m,n),MAX,m n,三种标量处理机的性能比较,从三种标量处理机的性能曲线中，可以得出如下结论：,1.,三种处理机的性能关系,超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，,主要原因如下：,(1),超标量处理机功能部件的冲突比超流水线处理机小。在指令执行过程中的许多功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。,(2),条件转移等操作造成的损失，超流水线处理机要比超标量处理机大。,由于超流水线处理机采用深度流水线结构，对条件转移等操作比超标量处理机敏感。,(3),超流水线处理机的启动延迟通常要比超标量处理机大。,超标量处理机在每个时钟周期的一开始就同时发射多条指令，,超流水线处理机把一个时钟周期平均分成多个流水线周期，每个流水线周期只发射一条指令。,2.,实际指令级并行度与理论指令级并行度的关系,当横坐标给出的理论指令级并行度比较低时，处理机的实际指令级并行度的提高比较快。,当理论指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。,在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当，否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。,目前，一般认为，,m,和,n,都不要超过,4,。,3.,最大指令级并行度,一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是有限的，是有个确定的值。,最大指令级并行度由程序自身的语义决定，与这个程序运行在那一种处理机上及采用何种方法开发并行性无关。,对于某一个特定的程序，图中的三条曲线最终都要收拢到同一个点上。,对于各个不同程序，这个收拢点的位置也是不同的。,具有向量数据表示和向量指令系统的处理机,向量处理机是解决数值计算问题的一种高性能计算机,向量处理机属,大型或巨型机,，也可以用微机加一台,向量协处理器,组成,向量处理机一般都采用流水线结构，,通常有有多条并行工作的流水线,必须把要解决的问题转化为向量运算，才能发挥向量处理机的效率,向量处理,例：一个简单的,C,语言程序如下：,for (i = 10; i = 1010; i+) ci = ai + bi ;,在向量处理机上,可以只用一条指令：,C(10:1010)=A(10:1010) + B(10:1010),一条向量指令可处理个或对操作数,在标量处理机上用,10,多条指令，其中有,8,条指令要循环,1000,次。,采用多寄存器结构的两地址指令编写程序,存储器采用字节编址方式，字长为,32,位,从标量到向量,在一般标量处理机中需要如下指令序列来实现（,A,、,B,、,C,分别是向量,a,、,b,、,c,在内存中的起始地址）：,START:LOADR0,ST ;,读循环初值,10,LOADR1,ED ;,读循环终值,1010,LOADR2,L ;,读内存地址增量,4,MOVER3,R2,MULR3,R0 ;,计算向量偏移量,;,初始值为,40,LOOP:LOADR4,A(R3) ;,读,A,向量的一个元素,LOADR5, B(R3) ;,读,B,向量的一个元素,ADDR4, R5 ;,加一个元素,STORER4, C(R3) ;,写,C,向量的一个元素,ADDR3, R2