上海交通大学-计算机组成原理考研辅导讲稿(8).docx

《上海交通大学-计算机组成原理考研辅导讲稿(8).docx》由会员分享，可在线阅读，更多相关《上海交通大学-计算机组成原理考研辅导讲稿(8).docx（15页珍藏版）》请在三一办公上搜索。

1、第八章流水技术第一节流水线工作原理流水工作方式：将一个计算任务细分成若干个子任务，每个子任务由专门的部件处理,多个计算任务依次进行并行处理。处理部件I锁存 牌CLKf处理锁部件存2器处理部件n锁存器一、流水线的分类操作部件级，指令级，处理器级单功能，多功能静态，动态线性，非线性标量，向量二、流水线的性能1.吞吐率：单位时间内流水线能处理的任务数量。对于线性流水线：=maxZ,m)r/时空图：段S5S4S2矫图8-1流水线的时空图例子最大吞吐率：流水线达到不间断流水的稳定状态后可获得的吞吐率。max力力J+tf流水线瓶颈的解决：zz34l-T-1T13|*(a)原流水线，第3段为瓶颈tttttt

2、(b)瓶颈段细分34ttd3ltAtTHTF3-J3(C)瓶颈段重复设置部(C)流水段重复的时空图对于线性流水线，完成个任务所需时间为六心f+5-l),实际吞吐率为:rj,n1TpmaxP机加+(-I)Afr(lm1)IZWTnn2 .加速比：流水方式的工作速度与等效的顺序工作方式时间的比值。对于线性流水线：TinmtnSp=-=-Tkm+n-1+加一1n3 .使用效率：工作时间的时空区与流水线中各段总的时空区之比。nmtnSPE=-=Tftm(m+n-1)m+n-1m退耦流水线TIl卜第级Tm第2级Tm第3级三、流水线的相关处理三种相关性：1 .资源相关(结构相关)解决方法：增加资源2 .数

3、据相关（RAW、WAR、WAW）解决方法：停顿、编译检测、旁路相关专用通路3 .控制相关。解决方法：提前判断、转移延迟槽等四、流水线的调度非线性流水线的调度方法预约表禁止表F=l,5,6,8冲突向量C=10110001调度方案比较表8-2各种调度方案的平均间隔拍数调度策略平均间隔周期be:(3,4)3.50ad:(2,7)4.50ade:(2,2,7)3.67abcb:(3,4,2,7)4.25abc:(3,4,7)4.67acb:(4,3,7)4.67ab:(3,7)5.00ac:(4,7)5.50a:(7)7.00习题：56第二节标量流水技术一、基本概念指令流水线结构:指令级并行性：指令序

4、列中的并行性。基本块循环级并行性：循环递归之间的并行性。例：for(i=l;i=1000;i=i+l)Xi=Xi+s;循环展开后loop:LDF0zO(Rl);F0=arrayelementADDDF4,F0,F2;addscalarinF2SDO(R1),F4;storeresultSUBIRlzRl,8;decrementpointer8bytes(perDW)BNEZRl,loop;branchifRl!=zero执行时的情况：loop:LDF0,0(Rl)1stall2ADDDF4,F0,F23stall4stall5SD0(Rl)zF46SUBIRl,Rl,87BNEZRl,loop

5、8stall9指令调度后：loop:LDF0z0(Rl)stallADDDF4zF0,F2SUBIRl,Rl,8BNEZRl,loopSD8(R1),F4执行时间减少到6个时钟周期。将上述程序展开3次之后loop:LDFOz0(Rl)2ADDDF4,F0,F23SDO(Rl),F41LDF6,-8,O(R1)2ADDDF8,F,F23SD-8(Rl),F81LDF1O,-16(R1)2ADDDF12,F10,F23SD-16(Rl),F121LDF14,-24(Rl)2ADDDF16,F14,F23SD-24(Rl)zF161SUBIRl,Rl,#321平均每个迭代6.8个周期。BNEZRl,

6、loop2未调度时，执行时间为27个周期,loop:LDFOz0(Rl)LDF6f-8,O(Rl)LDF1O,-16(R1)LDF14,-24(Rl)ADDDF4,F0,F2ADDDF8,F6,F2ADDDF12,F10,F2ADDDF16,F14,F2SD0(Rl),F4SD-8(Rl),F8SD-16(R1),F12SUBIRl,Rl,#32BNEZRl,loopSD8(Rl),F16调度后，执行时间为14个周期，平均每个迭代3.5个周期。指令流水处理中的相关性：(I)数据相关。如果满足以下两个条件，则称指令j与指令i是数据相关的：A.指令i产生的结果被指令_/使用；B.指令)与指令女数据

7、相关，而指令A与指令，数据相关。上述程序简单展开的结果是：loop:LDR),O(Ri)ADDDF4,FO,F2SDO(R1),F4SUB!R1.R1.#8LDF6,0(RI)ADDDF8,F6,F2SDO(R1),F8SUBlR1.R1.#8LDF10.0(Ri)ADDDF12,FIO,F2SDO(R1),F12SUBIRLRL#8LDF14.O(R1)ADDDFI6.F14,F2SDO(R1),FI6SUBiRl,Rl,#8BNEZR!.loop这里，相关性都来自减法指令。它使得指令只能顺序执行，而且指令数量多。(2)名字相关。名字相关发生在当两条指令使用相同的寄存器或存储单元(称为名字)

8、时。但是在指令之间不存在涉及该名字的数据流。在指令i及其后的指令)之间存在两种名字相关性。A.反相关。当指令j写一个寄存器，而指令i读这个寄存器时发生反相关。反相关对应于WAR险象，这种险象的检测使得反相关指令对保持其原有的顺序。B.输出相关。输出相关发生于指令i和指令/写相同寄存器或存储器单元时。指令的顺序必须保持。输出相关对应于WAW险象，可通过检测手段发现。解决名字相关的方法：寄存器更名(RegiSterrename)o例如对于上述循环的例子，如果不进行寄存器重新命名，其名字相关的情况如下所示：loop:LDF0,0(RI)ADDDF4,FO,F2SDO(R1),F4LDFO.-8(R1

9、)ADDDF4.F0,F2SD-8(R1),F4LDFO,-16(R1)ADDDF4,F0,F2SD-16(R1).F4LDFO,-24(R1)ADDDF4,F0,F2SD-24(R1),F4SUBIRl.Rl.#32BNEZRLIoop这些名字相关迫使指令序列只能按序执行。在经过了寄存器重新命名之后，名字相关就被消除，而只剩下数据相关。loop:LDFO.O(Rl)ADDDF4.F0.F2SDO(R1),F4LDF6,-8(R1)DDDF8,F6,F2SD-8(R1),F8LDF1O.-I6(R1)ADDDFI2,FI0,F2SD-16(R),F12LDFI4.-24(RI)ADDDF16.

10、F14,F2SD-24(Ri),F16SUBIRl,Rl,#32BNEZRl,loop(3)控制相关。控制相关决定了转移指令与其它指令之间的执行顺序。程序中除了开始的第一个基本块之外，其它每条指令都对某些分支指令有控制相关性，通常必须保持这种控制相关性。控制相关导致两个基本约束：A. 一条与一个分支相关的指令不能移动到这个分支指令之前而使这条指令不受该分支的控制。B. 一条与一个分支不相关的指令不能移动到这个分支之后而使这条指令受到该分支指令的控制。上例中循环展开时取消了一些控制指令，因而消除了一些控制相关。两种保持控制相关性的方法：(1)按序执行；(2)检测控制或分支险象，保证与分支指令控制

11、相关的指令在分支的方向明确之后才执行，而与分支指令不相关的指令则可以提前或者延迟执行。控制相关本身不是必须保持不变的本质因素。必须保持不变的是程序的两个特性：异常行为和数据流。例如：BEQZR2,L1LWRlz0(R2)Ll:这里只存在控制相关，不存在数据相关。习题：7二、指令的动态调度静态调度：用编译调度动态调度：用硬件调度基本思想：无序执行一一打破指令执行的顺序限制。有序指令启动：DIVDF0,F2zF4ADDDFlO,F0,F8SUBDF12,F8zF14第三条指令不能提前启动。无序指令启动的方法：记分牌方法，TOmaSUk)法1.记分牌方法记分牌的构成：(1)指令状态表。(2)功能部件

12、状态表。(3)寄存器结果状态表。四个执行阶段：启动、读操作数、执行、写结果(1)启动规则：无结构冲突，没有WAW相关(2)读操作数规则：操作数具备一一消除RAW相关(3)写结果规则：前面指令已读取操作数或者无数据相关一一消除WAR相关例如：一个具有五个功能部件的CPU,包括一个整数部件(Integer)、两个乘法部件(MUIt1,MUlt2)、一个加法部件(Add)和一个除法部件(DiVide)。假定以下指令序列：LDF6,34(R2)LDF2,45(R3)MULTDF0,F2,F4SUBDF8,F6,F2DIVDFI0,F0,F6ADDDF6,F8,F2这里LD指令由整数部件执行(无流水功能

13、)，加法和减法都由加法部件执行，乘法和除法运算操作由相应的部件执行。指令状态表指令状态指令启动该操作数执行完成写结果LDF6,34(R2)1234LDF2.45(R3)567MULTDF0,F2,F46SUBDF8,F6,F27DlVDF10,F0,F68ADDDF6.F8.F2功能部件状态表部件功能部件状态名称BusyOpFiFjFkQjQkRjRkIntegerYesLoadF2R3NoMultiYcsMultFOF2F4IntegerNoYcsMult2NoAddYcsSubFSF6F2IntegerYcsNoDivideYesDivFiOFOF6MultiNoYcs寄存器结果状态表FO

14、F2F4F6F8FIOF12F30MUIllIntegerSUbDiVide假定加法部件的执行需要2个时钟周期，乘法需要10个周期，除法需要40个周期。在MULTD和DIVD写结果时的记分牌情况如下所示。指令状态表指令指令状态启动读操作数执行完成写结果LDF6,MR2)1234LDF2.45(R3)5678MULTDF0.F2.M691920SUBDF8.F6,F2791112D1VDF1O,R),F68216061DDDF6.F8,F213141622功能部件状态表功能部件状态部件名BusyOpHHFkQiQkRjRkIntegerNoMulllYcsMultFOF2F4NoNoMult2N

15、oAddYcsAddF6F8F2NoNoDivideYesDiv FlO FO F6 Multi寄存器状态表FOF2F4F6FBFlOFl2F30MuKlAddDivide习题：122.Tomasulo调度法特点：寄存器更名一一消除名字相关分布式保存站一一并行调度消除调度瓶颈写回控制一一写写相关时最后一条指令写入命令队列一一使取指令与启动执行退耦例如：指令序列及其执行状态如下（假定执行周期数与上述相同）：指令状态表指令状态指令启动执行完成写结果LDF6,34(R2)134LDE2.45(R3)245MULTDF0,F2.F431516SUBDF8,F6,F2478DIVDF10,F0,F655

16、657ADDDF6.F8.F261011各保存站情况如下：保存站部件名BusyOpVjVkQjQkAddlYesSUBMcm34+Rcgs(R2iLoad2Add2YesADDAddILoad2Add3NoMultiYesMULTRcgslF4)Load2Mult2YesDIVMcmI34+RcgsR2Multi各浮点寄存器状态如下表：R)F2F4F6FSFIOF12F30MultiLoad2Add2AddlMult2存储器总线In Ir二装入缓存指令处理部件忙站号数据浮点寄存器图8-5Tomasulo指令调度法结构框图三、分支预测静态：永远不转移，永远转移，后向转移(准确率40%65%)(i

17、486)动态：1位，2位，多位(1级，2级)建立一个记录转移状态的cache1位动态：根据上次转移情况预测下次，准确率77%79% (Alpha)2位动态：根据上两次转移情况预测下次，准确率78%89%(奔腾)12级预测：根据多次转移情况选择预测状态，准确率93%(P6)移位方向转移历史寄存器图8-7两级转移预测方法分支目标缓存：快速形成分支目标地址或者目标指令。为新PC值图8-8分支目标缓存图中：目标缓存一一分支目标地址预测PC一一分支指令地址标记预测状态位一一预测状态的编码四、多重指令启动目标：在一个时钟周期内能够启动多条指令。方法：动态多重指令启动（超标量，超流水），静态多重指令启动（V

18、UW）。退耦结构：将数据装载操作和数据运算并行进行，并采用IOad/store缓存，使得访存操作与运算操作之间存在一个弹性关系。表84（假设可同时启动一条浮点指令和一条整型指令）迭代编号指令启动周期执行周期写回周期1LDF0,0(Rl)1241ADDDF4,F0,F21581SD0(Rl),F429-1SUBIRl,Rl,83451BNEZRl,LOOP45-2LDF0,0(Rl)5682ADDDF4,F0,F259122SD0(Rl),F4613-2SUBIRl,Rl,#87892BNEZRlfLOOP69-时空图表示:超长指令字：指令中包含多个部件的操作访存部件I访存部件2浮点部件1浮点部

19、件2整型/转移LDFOz0(Rl)LDF6,-8(Rl)LDF10z-16(Rl)LDF14,-24(Rl)LDF18,-32(Rl)LDF22,-4O(R1)ADDDF4,F0,F2ADDDF8,F6,F2LDF26,-48(Rl)ADDDF12,F10,F2ADDDF16,F14,F2ADDDF20,F18,F2ADDDF24,F22,F2SDO(R1),F4SD-8(Rl),F8ADDDF28,F26,F2SD-16(Rl)zF12SD-24(Rl)zF16SD-32(Rl),F20SD-4O(R1),F24SUBIRl,Rl,#56SD+8(Rl)zF28BNEZRl,LOOP执行时间

20、为9个周期，平均每个迭代1.28个周期。习题：15五、指令级并行性的进一步开发1 .相关性的检测与消除采用编译技术消除相关性(见书上例子)2 .软件流水重新组织循环程序例：对于前面的循环例子LDF0,0(Rl)ADDDF4,F0,F2LDF0,0(R)SD0(RI),F4ADDDF4,F0,F2LDF0,0(RI)SDO(R1),F4ADDDF4,F0,F2SDO(Rl),F43 .路径调度技术将指令调度的范围扩展到跨越转移指令的更大的区域，开发非循环分支程序中的并行性，用于VLlW。两种步骤：路径选择，路径压缩4 .条件指令给指令增加一个条件，以消除转移指令，或使得指令能够跨越转移指令进行调

21、度。例：语句if(A=O)S=T;在一般的计算机中转换成BNEZRlrLMOVR2,R3L:可以用一条条件传输指令，在第三个操作数为零时进行数据传输操作：CMOVZR2,R3,R1又如，对于下列双启动的超标量机指令序列：LWRlz40(R2)ADDR3,R4zR5ADDR6,R3,R7BEQZRlOzLLWR8,20(RlO)LWR9,0(R8)L:程序浪费一个存储器操作节拍，转移不发生时将发生一个数据相关停顿，因为转移指令后的第二条LW指令与上一条指令是相关的。用条件访存指令LWC程序改为：LWRlz40（R2）ADDR3,R4,R5LWCR8,20（RlO）,RlOADDR6,R3,R7B

22、EQZRlOzLLWR9z0（R8）5 .推测执行一一将指令的执行与指令结果的写回退耦，允许指令预执行。指令的提交：结果写回提交方式：有序提交（可实现精确中断），无序提交（需进行相关性检测）重排序缓存：保存指令执行完成后但尚未提交的结果。EXl写缓Im提交I习题：9,10第三节向量流水技术一、向指令和数据的编码表示向量指令：以向量数据为操作数的指令。向量操作数：包含个数据元素的有序集合，称为向量的长度。在FORTRAN扩展语言中，向量元素子集的表示：初始下标:终止下标:下标增量el:e2:e3el:e2el:*:e3IoIIlok)IIIol 而(b)有序向量（c）压缩向量图8-12稀疏向量、

23、有序向量和压缩向量自定义类型的数据标志符数据图8/3带标志符数据表示格式优点：（1）简化指令系统，（2）数据类型检查和转换能够用硬件实现。（3）硬件能自动转换数据转换。（4）方便了程序调试。主要问题：（1）使数据区域占用的存储空间增加。（2）指令执行速度将减慢。（3）数据的初始化复杂。数据描述符：用于描述复合数据类型。格式：描述符标志位I特征标记I数据块长度I数据块起始地址例子:1013101:描述符000:单精度书101ToTS2一 S3 S4000al2all000a21000a22OOO000a31000a32二、向流水原理典型的向量机基本系统结构图8-15向量处理机的典型结构图六种向量

24、指令(1)向量向量指令。例：ADDVVI,V2,V3(2)向量.标量指令。例：ADDVVI,F2,V3(3)向量存储器指令。例：LVVI,Rl(4)向量归约指令。例：MAXH),V1(5)收集扩展指令。Gather-Scatter(6)屏蔽指令。例：SENSVF0,Vl标量a装入Fo装入向量X到VI,RX为向量X的首址 向量X与标量a相乘，结果写入V2 装入向量Y, RV为向量Y的首址 向量加，结果写入V4存结果向量，SV为向量存指令例如，计算Y=a*X+YLDF0za;LVVI,Rx;MULTVV2,FOzVl;LVV3,Ry;ADDVV4,V2,V3;SVRy,V4;地址生成：向量跨步三、

25、提高向处理性能的方法1 .多功能部件的并行操作(Cray-I的结构)相关的检测数据相关：读读相关;V4V1+V2;V5*-V2AV3ADDVV4,VlzV2ANDVV5,V2,V3又如：读写相关ADDVV4,V1,V2ANDVV5,V4,V3V5V4V3资源冲突ADDVV3zVlzV2;V3-V1+V2ADDVV6,V4,V56-V4+V52 .链接技术。利用向量指令间存在的写后读(RAW)的数据相关性采用专用通道来加快向量指令序列执行速度。例如：ADDVV1,V2,V3;V1V2+V3MULTVV4,V1,V5；V4-V1+V5V3-AV2*-V0+Vl执行时间：(16+1)N-1又如：LVV3zA;ADDVV2,VO,V1;MULTVV4,V2,V3;3.条件语句的处理。采用屏蔽向量例如：do100i=l,64if(A(i).ne.0)thenA(i)A(i)-B(i)endif100continue的向量指令为：LVVI,Ra；将向量A装入VlLVV2,Rb;将向量B装入V2LDFOz#0SENSVFOzVl；将浮点数0装入FO;若VI(i)F0z则将VMi置为1SUBVVI,V1,V2；在屏蔽向量控制下进行减法操作CVMSVRa,Vl；将屏蔽向量寄存器置为全“1”；将结果存入A屏蔽向量不能减少执行时间4.向量归约操作递归折叠法：思考题：画出本例的流水线的时空图习题：21