上海交通大学 计算机组成原理考研辅导讲稿

1、第八章流水技术第一节流水线工作原理流水工作方式：将一个计算任务细分成若干个子任务，每个子任务由专门的部件处理， 多个计算任务依次进行并行处理。处理锁处理锁处理锁部件存9部件存* 1部件存一1器2器器CLK一、流水线的分类操作部件级，指令级，处理器级单功能，多功能静态，动态线性，非线性标量，向量二、流水线的性能吞吐率：单位时间内流水线能处理的任务数量。对于线性流水线：t=maxt1，f,tm + tz时空图：图8 1流水线的时空图例子最大吞吐率：流水线达到不间断流水的稳定状态后可获得的吞吐率。Tp max1_ 1maxr,., t,., t +1, t1 i m l流水线瓶颈的解决:t&(b)瓶

2、颈段细分(c)瓶颈段重复设置部8 2消除流水线瓶颈段的两种方法(a)原流水线时空图对于线性流水线，完成n个任务所需时间为T=mAt+(n-1)At,实际吞吐率为: n1T p maxT =p mZ + (n -1) AtAt (1+ m-1)1+ m -1nn加速比：流水方式的工作速度与等效的顺序工作方式时间的比值。 对于线性流水线:S _ T _ nm _ mp Tk m + n 1 1 + m -1 n3.使用效率:工作时间的时空区与流水线中各段总的时空区之比。E nmAtn Sp 了 心m( m + n 1) At m + n 1 m p退耦流水线三、流水线的相关处理三种相关性：1.资源

3、相关(结构相关)解决方法：增加资源数据相关（RAW、WAR、WAW）解决方法：停顿、编译检测、旁路相关专用通路控制相关。解决方法：提前判断、转移延迟槽等四、流水线的调度非线性流水线的调度方法预约表禁止表冲突向量C = 10110001调度状态转换图图8- 3非线性流水线状态图调度方案比较表8-2各种调度方案的平均间隔拍数调度策略平均间隔周期bc: (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.50a700习题：5，6

4、第二节标量流水技术一、基本概念指令流水线结构:PC指令存储数据寄存数据Do存储器指令级并行性：指令序列中的并行性。基本块循环级并行性：循环递归之间的并行性。例：for (i=1; i=1000; i=i+1) xi = xi + s;循环展开后loop: LDF0, 0(R1);F0=array elementADDDF4,F0,F2;add scalar in F2SD0(R1),F4;store resultSUBIR1,R1,8;decrement pointer 8 bytes (per DW)BNEZR1,loop;branch if R1!=zero执行时的情况：loop: LDF

5、0, 0(R1)1stall2ADDDF4,F0,F23stall4stall5SD0(R1),F46SUBIR1,R1,87BNEZR1,loop8stall9指令调度后：loop: LDF0, 0(R1)stallADDDF4,F0,F2SUBIR1,R1,8BNEZR1,loopSD8(R1),F4执行时间减少到6个时钟周期。将上述程序展开3次之后loop: LD F0, 0(R1)2ADDDF4,F0,F23SD0(R1),F41LDF6,-8,0(R1)2ADDDF8,F6,F23SD-8(R1),F81LDF10,-16(R1)2ADDDF12,F10,F23SD-16(R1),F

6、121LDF14,-24(R1)2ADDDF16,F14,F23SD-24(R1),F161SUBI R1,R1,#321BNEZ R1,loop2未调度时，执行时间为27个周期，平均每个迭代6.8个周期。loop: LD F0, 0(R1)LD F6,-8,0(R1)LD F10,-16(R1)LD F14,-24(R1)ADDD F4,F0,F2ADDD F8,F6,F2ADDD F12,F10,F2ADDD F16,F14,F2SD 0(R1),F4SD -8(R1),F8SD -16(R1),F12SUBI R1,R1,#32BNEZ R1,loopSD 8(R1),F16调度后，执行

7、时间为14个周期，平均每个迭代3.5个周期。指令流水处理中的相关性：数据相关。如果满足以下两个条件，则称指令j与指令，是数据相关的：指令i产生的结果被指令j使用；指令j与指令k数据相关，而指令k与指令i数据相关。上述程序简单展开的结果是：loop: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4SUBI R1,R1,#8LD F6,0(R1)ADDD F8,F6,F2SD 0(R1),F8SUBI R1,R1,#8LD F10,0(R1)ADDD F12,F10,F2SD 0(R1),F12SUBI R1,R1,#8LD F14,0(R1)ADDD F16,F14,F

8、2SD 0(R1),F16SUBI R1,R1,#8BNEZ R1,loop这里，相关性都来自减法指令。它使得指令只能顺序执行，而且指令数量多。名字相关。名字相关发生在当两条指令使用相同的寄存器或存储单元(称为名字) 时。但是在指令之间不存在涉及该名字的数据流。在指令i及其后的指令j之间存在两种名 字相关性。反相关。当指令j写一个寄存器，而指令i读这个寄存器时发生反相关。反相关对 应于WAR险象，这种险象的检测使得反相关指令对保持其原有的顺序。输出相关。输出相关发生于指令i和指令j写相同寄存器或存储器单元时。指令的 顺序必须保持。输出相关对应于WAW险象，可通过检测手段发现。解决名字相关的方法

9、：寄存器更名(Register rename)。例如对于上述循环的例子，如果不进行寄存器重新命名，其名字相关的情况如下所示：loop: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4LD F0,-8(R1)ADDD F4,F0,F2SD -8(R1),F4LD F0,-16(R1)ADDD F4,F0,F2SD -16(R1),F4LD F0,-24(R1)ADDD F4,F0,F2SD -24(R1),F4SUBI R1,R1,#32BNEZ R1,loop这些名字相关迫使指令序列只能按序执行。在经过了寄存器重新命名之后，名字相关就被消除，而只剩下数据相关。loop

10、: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4LD F6,-8(R1)ADDD F8,F6,F2SD -8(R1),F8LD F10,-16(R1)ADDD F12,F10,F2SD -16(R1),F12LD F14,-24(R1)ADDD F16,F14,F2SD -24(R1),F16SUBI R1,R1,#32BNEZ R1,loop控制相关。控制相关决定了转移指令与其它指令之间的执行顺序。程序中除了开 始的第一个基本块之外，其它每条指令都对某些分支指令有控制相关性，通常必须保持这 种控制相关性。控制相关导致两个基本约束：一条与一个分支相关的指令不能移动到

11、这个分支指令之前而使这条指令不受该分 支的控制。一条与一个分支不相关的指令不能移动到这个分支之后而使这条指令受到该分支 指令的控制。上例中循环展开时取消了一些控制指令，因而消除了一些控制相关。两种保持控制相关性的方法：(1)按序执行；(2)检测控制或分支险象，保证与分支指 令控制相关的指令在分支的方向明确之后才执行，而与分支指令不相关的指令则可以提前 或者延迟执行。控制相关本身不是必须保持不变的本质因素。必须保持不变的是程序的两个特性：异常行为和数据流。例如：BEQZ R2,L1LW R1,0(R2)L1:这里只存在控制相关，不存在数据相关。习题：7二、指令的动态调度静态调度：用编译调度动态调

12、度：用硬件调度基本思想：无序执彳丁打破指令执彳丁的顺序限制。有序指令启动：DIVD F0,F2,F4ADDD F10,F0,F8SUBD F12,F8,F14第三条指令不能提前启动。无序指令启动的方法：记分牌方法，Tomasulo法1.记分牌方法记分牌的构成：指令状态表。功能部件状态表。寄存器结果状态表。四个执行阶段：启动、读操作数、执行、写结果启动规则：无结构冲突，没有WAW相关读操作数规则：操作数具备一一消除RAW相关写结果规则：前面指令已读取操作数或者无数据相关一一消除WAR相关例如：一个具有五个功能部件的CPU,包括一个整数部件(Integer)、两个乘法部件(Multi,Mult2)

13、、一个加法部件(Add)和一个除法部件(Divide)。假定以下指令序列：LD F6,34(R2)LD F2,45(R3)MULTD F0,F2,F4SUBD F8,F6,F2DIVD F10,F0,F6ADDD F6,F8,F2这里LD指令由整数部件执行(无流水功能)，加法和减法都由加法部件执行，乘法和 除法运算操作由相应的部件执行。指令状态表WF2F4F6F8F10F12F30指令指令状态启动读操作数执行完成写结果LD F6,34(R2)1234LD F2,45(R3)567MULTD F0,F2,F46SUBD F8,F6,F27DIVD F10,F0,F68ADDD F6F8F2MMi

14、ltl IntegerSub Divide假定加法部件的执行需要2个时钟周期，乘法需要10个周期，除法需要40个周期。在MULTD和DIVD写结果时的记分牌情况如下所示。指令状态表指令指令状态启动读操作数执行完成写结果LD F6,34(R2)1匕人】/卜厂厂定入234LD F2,45(R3)5678MULTD F0,F2,F4691920SUBD F8,F6,F2791112DIVD F10,F0,F68216061ADDD F6F8F2UU1622功能部件状态表功能部件状态部件名BusyOpFiFjFkQjQkRjRkIntegerNoMult1YesMultF0F2F4NoNoMult2N

15、oAddYesAddF6F8F2NoNoDivide1YesDivF10F0F6Multi寄存器状态表No-FQF2F4F6F8F10F12:F30MultiAddDivide习题：122. Tomasul o调度法特点：寄存器更名一一消除名字相关分布式保存站一一并行调度消除调度瓶颈写回控制一一写写相关时最后一条指令写入命令队列一一使取指令与启动执行退耦例如：指令序列及其执行状态如下（假定执行周期数与上述相同）：指令状态表指令指令状态启动执行完成写结果LD F6,34(R2)134LD F2,45(R3)245MULTD F0,F2,F431516SUBD F8,F6,F2478DIVD F1

16、0,F0,F655657ADDD F6 F8 F261011各保存站情况如下:各浮点寄存器状态如下表:0F2F4E6E8E10E12-E30Mult1Load2Add2Add1 ,Mult2保存站部件名BusyOdViVkQiQkAdd1YesSUBMem34+RegsR21Load2Add2YesADDAdd1Load2Add3NoMult1YesMULTRegsF4Load2Mult2YesDIVMem34+RegsR2Mult1存储器总线一装入缓存一J0010LD F3,34(R2)0001LD F6,K4(R3)指令处理部件忙站号数据1100 )0T0 0001浮点寄存器OPrQi V

17、i，Qj Vjb忙图8 5 Tomasulo指令调度法结构框图三、分支预测静态：永远不转移，永远转移，后向转移（准确率40%65%） （i486） 动态：1位，2位，多位（1级，2级）建立一个记录转移状态的cache1位动态：根据上次转移情况预测下次，准确率77%79%（Alpha）0*=L2位动态：根据上两次转移情况预测下次，准确率78%89% （奔腾）012级预测：根据多次转移情况选择预测状态，准确率93%（P6）移位方向转移历史寄存器1 011 最近转移位图8 7两级转移预测方法 分支目标缓存：快速形成分支目标地址或者目标指令。取预测的PC作为新PC值图8-8分支目标缓存图中：目标缓存一

18、一分支目标地址预测PC分支指令地址标记预测状态位一一预测状态的编码四、多重指令启动目标：在一个时钟周期内能够启动多条指令。方法：动态多重指令启动（超标量，超流水），静态多重指令启动（VLIW）。退耦结构：将数据装载操作和数据运算并行进行，并采用load/store缓存，使得访存操 作与运算操作之间存在一个弹性关系。表8-4 （假设可同时启动一条浮点指令和一条整型指令）迭代编号指令启动周期执行周期写回周期1LDF00/R1)1241ADDDF4F0F21581SDL ,LU, L t0(P1)F429Q HP T3A1BNEZR1,R1,#8R1TOOP452t nFC) n f p 1 82A

19、DDDF4,F0,F259122SD0(R1)F46132SUBIu (、*，,R1R1#87892BNEZR1,LOOP89时空图表示:超长指令字：指令中包含多个部件的操作访存部件1访存部件2浮点部件1浮点部件2整型/转移LDF0,0(R1)LDF6,-8(R1)LDF10,-16(R1) LDF14,-24(R1)LDF18,-32(R1) LDF22,-40(R1)ADDD F4,F0,F2ADDD F8,F6,F2LDF26,-48(R1)ADDD F12,F10,F2ADDD F16,F14,F2ADDD F20,F18,F2ADDD F24,F22,F2SD0(R1),F4SD-8

20、(R1),F8ADDD F2 8,F2 6,F2SD-16(R1),F12 SD-24(R1),F16SD-32(R1),F20 SD-40(R1),F24SUBI R1,R1,#56SD_+ 8(R1) .F28BNEZ R1 .LOOP执行时间为9个周期，平均每个迭代1.28个周期。习题：15五、指令级并行性的进一步开发相关性的检测与消除采用编译技术消除相关性(见书上例子)软件流水重新组织循环程序例：对于前面的循环例子LD F0,0(R1)ADDD F4,F0,F2LD F0,0(R1)SD 0(R1),F4ADDD F4,F0,F2LD F0,0(R1)SD 0(R1),F4ADDD F

21、4,F0,F2SD 0(R1),F4路径调度技术将指令调度的范围扩展到跨越转移指令的更大的区域，开发非循环分支程序中的并行 性，用于VLIW。两种步骤：路径选择，路径压缩条件指令给指令增加一个条件，以消除转移指令，或使得指令能够跨越转移指令进行调度。例：语句if(A=0) S=T;在一般的计算机中转换成BNEZ R1,LMOV R2,R3L:可以用一条条件传输指令，在第三个操作数为零时进行数据传输操作：CMOVZ R2,R3,R1又如，对于下列双启动的超标量机指令序列：LW R1,40(R2) ADD R3,R4,R5ADD R6,R3,R7BEQZ R10,LLW R8,20(R10)LW

22、R9,0(R8)L:程序浪费一个存储器操作节拍，转移不发生时将发生一个数据相关停顿，因为转移指 令后的第二条LW指令与上一条指令是相关的。用条件访存指令LWC,程序改为：LW R1,40（R2） ADD R3,R4,R5LWC R8,20（R10）,R10ADDR6,R3,R7BEQZ R10,LLW R9,0（R8）5.推测执行将指令的执行与指令结果的写回退耦，允许指令预执行。指令的提交：结果写回提交方式：有序提交（可实现精确中断），无序提交（需进行相关性检测） 重排序缓存：保存指令执行完成后但尚未提交的结果。| IF | 川* IS | Ex | 写缓* 提交习题：9，10第三节向量流水技

23、术一、向量指令和数据的编码表示向量指令：以向量数据为操作数的指令。向量操作数：包含n个数据元素的有序集合，n称为向量的长度。在FORTRAN扩展语言中，向量元素子集的表示：初始下标:终止下标:下标增量 e1:e2:e3 e1:e2*e1:*:e3向量数据的压缩和展开LJE（b）有序向量（c）压缩向量图8-12稀疏向量、有序向量和压缩向量自定义类型的数据 标志符数据图8-13带标志符数据表示格式优点：（1）简化指令系统，（2）数据类型检查和转换能够用硬件实现。（3）硬件能自动 转换数据转换。（4）方便了程序调试。主要问题：（1）使数据区域占用的存储空间增加。（2）指令执行速度将减慢。（3）数据 的初始化复杂。数据描述符：用于描述复合数据类型。格式：描述符标志位特征标记数据块长度数据块起始地址图8-14数据描述符格式例子:二、向量流水原理典型的向量机基本系统结构主存;标量寄存器，向量地址H向量流部件寄存器指令处理部件，向量指令1控制部件图8-15向量处理机的典型结构图六种向量指令向量-向量指令。例：ADDV V1, V2, V3向量-标量指令。例：ADDV V1, F2, V3 向量-存储器指令。例：LV V1, R1向量归约指令。例：MAX F0, V1收集-扩展指令。Gather-Scatter屏蔽指令。例：SENSV F0, V1标量4装入0装入