单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,第三章 流水和向量处理,,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,的出现可以设置多个功能部件支持向量、超标量、超长指令字和超流水结构空间并行性可以有效提高计算机速度，速度提高的最大倍数,<=,部件设备量增加的倍数上述不等式的原因主要是有存储和外设限制造成的，为了提高速度往往需要高带宽存储系统的支持和高效的,I/O,能力，我们将在后面的章节讨论存储系统和,I/O,系统当然在,MPP,中各个结点相联还需要不同的互联网络的支持先行控制技术,—,补充,1.,顺序执行方式,,执行,n,条指令所用的时间为：,,,,如果每段时间都为,t,，则执行,n,条指令所用的时间为：,T,＝,3 n t,,,主要优点：,控制简单，节省设备,,主要缺点：,速度慢，功能部件的利用率低,2.,一次重叠执行方式,,如果两个过程的时间相等，则执行,n,条指令的时间为：,T,＝,(,1+2n)t,,,,,主要优点：,,,指令的执行时间缩短，,,功能部件的利用率明显提高。
主要缺点：,,,需要增加一些硬件，,,控制过程稍复杂3.,二次重叠执行方式,,如果三个过程的时间相等，执行,n,条指令的时间为：,T,＝,(,2,＋,n,）,t,,在理想情况下，处理机中同时有三条指令在执行处理机的结构要作比较大的改变，需要采用先行控制技术先行控制方式的原理,1.,采用二次重叠执行方式必须解决两个问题：,,(1),有独立的取指令部件、指令分析部件和指令执行部件,,把一个集中的指令控制器，分解成三个独立的控制器：,,存储控制器、指令控制器、运算控制器,,(2),要解决访问主存储器的冲突问题,,取指令、分析指令、执行指令都可能要访问存储器,,2.,解决访存冲突的方法：,,(1),采用低位交叉存取方式：,,这种方法不能根本解决冲突问题读指令、读操作数、写结果2),两个独立的存储器：,独立的指令存储器和数据存储器如果再规定，执行指令的执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行在许多高性能处理机中，有独立的指令,Cache,和数据,Cache,这种结构被称为哈佛结构3),采用先行控制技术,,采用先行控制技术的关键是缓冲技术和预处理技术缓冲技术通常用在工作速度不固定的两个功能部件之间。
设置缓冲栈的目的是用以平滑功能部件之间的工作速度在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度先行处理机结构,1.,三个独立的控制器：,,存储控制器、指令控制器、运算控制器2.,四个缓冲栈：,,先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈3.,处理机组成,4.,先行指令缓冲栈的组成,,作用：,只要指令缓冲栈没有充满，就自动发出取指令的请求设置两个程序计数器：,,先行程序计数器,PC,1,，用来指示取指令，,,现行程序计数器,PC,，记录指令分析器正在分析的指令地址5.,存在的主要问题：,,各类指令,“,分析,”,和,“,执行,”,的时间相差很大,,数据相关,,转移或转子程序指令,,先行指令缓冲栈的组成,指令执行时序,设置了指令缓冲栈，取指令的时间就可以忽略不计一条指令的执行可分为,2,个过程,,1.,分析指令和执行指令时间不相等时的情况,采用先行缓冲栈的指令执行过程,,先行读数栈,,,先行操作栈,,,后行写数栈理想情况下，指令执行部件应该一直忙碌连续执行,n,条指令的时间为：,先行缓冲栈,设置先行缓冲栈的目的：,使指令分析器和指令执行部件能够独立工作。
1.,先行指令缓冲栈：,,处于主存储器与指令分析器之间,,用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异,,RR,型指令,，不必处理，直接送先行缓冲栈,,RS,型指令,，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成,RR*,指令送先行缓冲栈,RI,型指令,，指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成,RR*,指令送先行缓冲栈,,转移指令,，一般在指令分析器中直接执行先行操作栈,,处于指令分析器和运算控制器之间,,使指令分析器和运算器能够各自独立工作采用先进先出方式工作，由指令寄存器堆和控制逻辑组成先行读数栈,,处于主存储器与运算器之间,,平滑运算器与主存储器的工作,,每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成也可以把地址寄存器和操作数寄存器合为一个当收到从指令分析器中送来的有效地址时，就向主存申请读操作数读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址后行写数栈,,每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址部分，形成,RR*,指令送入先行操作栈。
当运算器执行这条,RR*,型写数指令时，,,只要把写到主存的数据送到后行写数栈的数据寄存器中即可采用先行控制方式时一个程序的执行情况：,缓冲深度的设计方法,以静态分析为主，通过模拟来确定缓冲深度1.,先行指令缓冲栈的设计,,考虑两种极端情况：假设缓冲深度为,D,I,,(1),先行指令缓冲栈已经充满,,指令流出的速度最快，例如连续分析,RR,型指令，设这种指令序列的最大长度为,L,1,，平均分析一条这种指令的时间为,t,1,；,,指令流入的速度最慢，设平均取一条指令的时间为,t,2,从主存储器中取到先行指令缓冲栈中的指令条数是,L,1,－,D,I,条应该满足如下关系：,L,1,,t,1,＝,(,L,I,－,D,I,),t,2,,,计算出缓冲深度为：,,如果这种指令流的连续长度超过,L,1,，则先行指令缓冲栈失去作用2),先行指令缓冲栈原来为空,,输入端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为,L,2,，平均取一条这种指令的时间为,t,2,’,；,输出端指令流出的速度最慢,，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为,t,1,’,分析的指令条数是,L,2,－,D,I,条。
应该满足如下关系：,(,L,2,－,D,I,),t,1,’,＝,L,2,t,2,’,,,计算出缓冲深度为：,,如果这种指令流的连续长度超过,L,2,，先行指令缓冲栈失去缓冲作用设计举例,,在一般处理机中连续执行短指令的概率大例：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均用,4,个周期，如果这种指令的平均长度,为,9,，即,90,％的指令是执行时间短的指令解：计算先行指令缓冲栈的缓冲深度为：,先行指令缓冲栈的工作时间关系,,,,,,,,第,1,个周期，取走指令,k+1,，请求取指令,,第,4,个周期末尾，指令,k+8,取到先行指令缓冲栈,,第,8,个周期末尾，指令,k+9,取到先行指令缓冲栈,,第,9,个周期，分析指令,k+9,，先行指令缓冲栈空,,第,10,个周期，指令分析器等待,其余缓冲栈的设计原则,,一般有关系：,D,I,≥,D,C,≥,D,R,≥,D,W,,,其中：,D,I,是先行指令缓冲栈的缓冲深度，,,,D,C,是先行操作栈的缓冲深度，,,,D,R,是先行读数栈的缓冲深度，,,,D,W,是后行写数栈的缓冲深度例如：,IBM370/165,机：,,,D,I,＝,4,，,D,C,＝,3,，,D,R,＝,2,，,D,W,＝,1,。
我国研制的两台大型计算机：,,,D,I,＝,8,，,D,C,＝,D,R,＝,4,，,D,W,＝,2,D,I,＝,12,，,D,C,＝,D,R,＝,6,，,D,W,＝,2,流水线工作原理,1.,流水寄存器,,流水线的每一个阶段称为,流水步,、流水步骤、,流水段,、流水线阶段、流水功能段、,功能段,、,流水级,、流水节拍等在每一个流水段的末尾或开头必须设置一个寄存器，称为,流水寄存器、流水锁存器、流水闸门寄存器等,在一般流水线时空图中不画出流水寄存器2.,一种指令流水线,,一般,4,至,12,个流水段，≥,8,个流水段的称为超流水线处理机,,,,,,3.,流水线时空图,,一个浮点加法器流水线的时空图,4.,流水线的主要特点,,只有连续提供同类任务才能发挥流水线效率,,尽量减少因条件分支造成的“断流”,,通过编译技术提供连续的相同类型操作,,每个流水线段都要设置一个流水寄存器,,时间开销：流水线的执行时间加长,,是流水线中需要增加的主要硬件,,各流水段的时间应尽量相等,,流水线处理机的基本时钟周期等于时间最长的流水段的时间长度流水线需要有,“,装入时间,”,和,“,排空时间,”,,流水线的分类,1.,线性流水线与非线性流水线,,流水线的各个流水段之间是否有反馈信号,,线性流水线,（,Linear Pipelining,）：,,每一个流水段都流过一次，而且仅流过一次,,非线性流水线,（,Nonlinear Pipelining,）：,,某些流水段之间有反馈回路或前馈回路。
线性流水线能够用流水线连接图唯一表示,,非线性流水线必须用流水线连接图和流水线预约表共同表示,2.,按照流水线的级别来分,,处理机级流水线，又称为,指令流水线,例如：在采用先行控制器的处理机中，各功能部件之间的流水线,,部件级流水线,(,操作流水线,),,,如浮点加法器流水线,,,,,,,宏流水线,(Macro Pipelining),,,处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理3.,单功能流水线与多功能流水线,,单功能流水线：,,只能完成一种固定功能的流水线Cray-1,计算机种有,12,条，,YH-1,计算机有,18,条,,,Pentium,有一条,5,段定点和一条,8,段浮点流水线PentiumⅢ,有两条定点和一条浮点指令流水线多功能流水线：,,,流水线的各段通过不同连接实现不同功能,,,Texas,公司的,ASC,机，,8,段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等4.,静态流水线与动态流水线,,静态流水线,：同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能动态流水线,：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。
5.,流水线的其他分类方法,,按照数据表示方式：,标量流水线和向量流水线,,按照,控制方式：,同步流水线和异步流水线,,,,,,顺序流水线与乱序流水线,，乱序流水线又称为无序流水线、错序流水线或异步流水线等线性流水线的性能分析,,主要指标：,吞吐率、加速比和效率,,1.,吞吐率（,Though Put,）,,流水线吞吐率的最基本公式：,,其中：,n,为任务数，,,Ｔ,k,为完成,n,个任务所用的时间各段执行时间相等，输入连续任务情况下，完成,n,个任务需要的总时间为：,,,T,k,＝,(k,＋,n,－,1),,t,,,其中：,k,,为流水线的段数，,,t,为时钟周期T,k,= k,· Δt + (n-1) Δt =,(k+n-1),,t,,吞吐率为：,,最大吞吐率为：,,各段时间不等，完成,n,个连续任务：,,,吞吐率：,,,最大吞吐率：,,,,,流水线各段执行时间不相等的解决办法,(1),将,“,瓶颈,”,部分再细分,（如果可分的话）,2.,加速比（,Speedup,）,,计算加速比的基本公式：,,各段执行时间相等，输入连续任务情况下,,,（不考虑栈寄存器时间）,,,加速比：,,最大加速比：,,,,各段时间不等，输入连续任务情况下,,,实际加,,,速比为：,,当流水线段数增加时，需要连续输入的任务数也必须增加,3.,效率（,Efficiency,）,,计算流水线效率的一般公式：,,,,各流水段时间相等，输入,n,个连续任务，流水线的效率为：,,,,最高效率为：,,各流水段时间不等，输入,n,个连续任务，,流水,,线效率为：,,,,,,,,,,流水线的吞吐率、,加速比与效率的关系：,,,因为：,,,因此：,E,＝,TP,·,,t,，,S,＝,k,·,E,,,流水线性能分析举例,,对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。
对于输入不连续任务，或多功能流水线，通常采用基本公式计算例：,,用一条,4,段浮点加法器流水线求,8,个浮点数的和：,Z,＝,A,＋,B,＋,C,＋,D,＋,E,＋,F,＋,G,＋,H,解：,,,Z,＝,[(A,＋,B),＋,(C,＋,D)],＋,[(E,＋,F),＋,(G,＋,H)],解：,流水线的设计原理,为提高系统效率我们当然希望流水线分站越多越好，但是站寄存器的存在增加了流水线的延迟和代价，降低了功能部件的时间利用率和流水线的性价比站数的确定，可以用流水线功能时间利用率不小于,e,和最高性能价格比以及器件和工艺条件综合决定效率：,T/(T+kt,d,)>=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,位之后：,010101∨101010,＝,111111,，,,,S,右移,3,位之后：,000101∨101010,＝,101111,，,,,S,右移,5,位之后：,000001∨101010,＝,101011,，,,,S,右移,7,位或大于,7,位后：还原到它本身101111,右移,5,位之后：,000001∨101010,＝,101011,，,,101011,右移,3,位之后：,000101∨101010,＝,101111,，,,101011,右移,5,位之后：,000001∨101010,＝,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,个周期，,,如果操作部件不采用流水线结构，则使用同一个操作部件的两条指令序号应该,至少相差,m×k,,如果操作部件采用,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++) c[i] = a[i] + b[i] ;,,在向量处理机上,,,可以只用一条指令：,C(10:1010)=A(10:1010) + B(10:1010),一条向量指令可处理Ｎ个或Ｎ对操作数,,在标量处理机上用,10,多条指令，其中有,8,条指令要循环,1000,次。
采用多寄存器结构的两地址指令编写程序,,存储器采用字节编址方式，字长为,32,位,从标量到向量,在一般标量处理机中需要如下指令序列来实现（,A,、,B,、,C,分别是向量,a,、,b,、,c,在内存中的起始地址）：,START: LOAD R0, ST ;,读循环初值,10,,,LOAD R1, ED ;,读循环终值,1010,,,LOAD R2, L ;,读内存地址增量,4,,,MOVE R3, R2,,MUL R3, R0 ;,计算向量偏移量,,,,;,初始值为,40,,LOOP: LOAD R4,A(R3) ;,读,A,向量的一个元素,LOAD R5, B(R3) ;,读,B,向量的一个元素,,,ADD R4, R5 ;,加一个元素,,,STORE R4, C(R3) ;,写,C,向量的一个元素,,,ADD R3, R2。
