上海交通大学-计算机组成原理考研辅导讲稿.docx
第八章流水技术第一节流水线工作原理流水工作方式：将一个计算任务细分成若干个子任务，每个子任务由专门的部件处理,多个计算任务依次进行并行处理。处理部件1锁存器处理 锁部件 存2器处理 锁部件 存n器一、流水线的分类操作部件级，指令级，处理器级单功能，多功能静态，动态线性，非线性 标量，向量二、流水线的性能1.吞吐率：单位时间内流水线能处理的任务数量。对于线性流水线：/=max九，力，册+时空图：最大吞吐率：流水线达到不间断流水的稳定状态后可获得的吞吐率。1 pmax-maxA,.，A,.，%+tiAz流水线瓶颈的解决：At At34At12345678123456781 23456781 2 34567812 3 45678时间段S554S3525ICLK(a)原流水线，第 3段为瓶颈(a)原流水线，第 3段为瓶颈At At At At At At(b)瓶颈段细分At34(c)瓶颈段重复设置部为新 PC值图 8-8分支目标缓存图中：目标缓存一一分支目标地址预测PC分支指令地址标记预测状态位一一预测状态的编码U!目标：在一个时钟周期内能够启动多条指令。方法：动态多重指令启动（超标量，超流水），静态多重指令启动（VLIW）。退耦结构：将数据装载操作和数据运算并行进行，并采用load/store缓存，使得访存操 作与运算操作之间存在一个弹性关系。表8-4（假设可同时启动一条浮点指令和一条整型指令）迭代编号指令启动周期执行周期写回周期1LDF0,0(R1)1241ADDD F4zF0zF21581SD0(RI),F4291SUB工R1,R1,#83451BNEZ RI,LOOP452LDF0,0(RI)5682ADDD F4,F0,F259122SD0(RI),F4613一2SUB工RI,RI,#87892BNEZ RI,LOOP89时空图表示:超长指令字：指令中包含多个部件的操作执行时间为9个周期，平均每个迭代L28个周期。访存部件1访存部件2浮点部件1浮点部件2整型/转移LD F0,0(RI)LDF6,-8(RI)LD F10,-16(RI)LDF14,-24(RI)LD F18z-32(RI)LDF22,-40(RI)ADDD F4,F0,F2ADDD F8,F6,F2LD F26,-48(RI)ADDD F12,F10,F2ADDD F16,F14,F2ADDD F20,F18,F2ADDD F24,F22,F2SD 0(RI),F4SD-8(RI),F8ADDD F28,F26,F2SD-16(RI),F12 SD-24(RI),F16SD-32(RI),F20 SD-40(RI),F24SUB工RI,RI,#56SD+8(RI),F28BNEZ RI,LOOP习题：15五、指令级并行性的进一步开发1.相关性的检测与消除采用编译技术消除相关性(见书上例子)2.软件流水重新组织循环程序例：对于前面的循环例子3.路径调度技术将指令调度的范围扩展到跨越转移指令的更大的区域，开发非循环分支程序中的并行 性，用于VLIW。两种步骤：路径选择，路径压缩4.条件指令给指令增加一个条件，以消除转移指令，或使得指令能够跨越转移指令进行调度。例：语句 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(RIO)LW R9,0(R8)L:程序浪费一个存储器操作节拍，转移不发生时将发生一个数据相关停顿，因为转移指 令后的第二条LW指令与上一条指令是相关的。LD FO,O(R1)ADDD F4,F0,F2SDO(R1),F4LD FO,O(R1)ADDD F4,F0,F2SDO(R1),F4LD FO,O(R1)ADDD F4,F0,F2SD O(R1),F4LDFO,O(R1)ADDD F4,F0,F2SDO(R1),F4-用条件访存指令LWC,程序改为：LW R1,40（R2）ADD R3,R4,R5LWC R8,20（RIO）,RIO ADD R6,R3,R7BEQZ RIO,L LW R9,0（R8）.推测执行一一将指令的执行与指令结果的写回退耦，允许指令预执行。指令的提交：结果写回提交方式：有序提交（可实现精确中断），无序提交（需进行相关性检测）重排序缓存：保存指令执行完成后但尚未提交的结果。第三节向量流水技术一、向量指令和数据的编码表示向量指令：以向量数据为操作数的指令。向量操作数：包含个数据元素的有序集合，称为向量的长度。在FORTRAN扩展语言中，向量元素子集的表示：初始下标:终止下标:下标增量el:e2:e3 el:e2|0川0|0|1回可丁1（b）有序向量|A0|A3I|（c）压缩向量图8-12稀疏向量、有序向量和压缩向量 自定义类型的数据标志符数据图 8-13带标志符数据表示格式优点：（1）简化指令系统，（2）数据类型检查和转换能够用硬件实现。（3）硬件能自动 转换数据转换。（4）方便了程序调试。主要问题：（1）使数据区域占用的存储空间增加。（2）指令执行速度将减慢。（3）数据 的初始化复杂。数据描述符：用于描述复合数据类型。格式：描述符标志位特征标记数据块长度数据块起始地址习题：9,el:e3例子:图8-15向量处理机的典型结构图 六种向量指令(1)向量-向量指令。例：ADDV VI,V2,V3(2)向量-标量指令。例：ADDV V1,F2,V3(3)向量-存储器指令。例：LVV1,R1(4)向量归约指令。例：MAXFO,VI(5)收集-扩展指令。Gather-Scatter(6)屏蔽指令。例：SENSVFO,VI标量a装入FO装入向量X到VI,Rx为向量X的首址 向量X与标量a相乘，结果写入V2装入向量Y,Ry为向量Y的首址向量加，结果写入V4存结果向量，SV为向量存指令地址生成：向量跨步三、提高向量处理性能的方法.多功能部件的并行操作(Cray-1的结构)相关的检测数据相关：读读相关ADDV二、向量流水原理典型的向量机基本系统结构二、向量流水原理典型的向量机基本系统结构例如,计算Y=a*X+YLD FO,a;LV VI,Rx;MULTV V2ZFO,VI;LV V3,Ry;ADDV V4,V2,V3;SV Ry,V4;V4V1+V2;V5-V2 AV3;V4-V1+V2;V4V1+V2;V5-V2 AV3;V4-V1+V2V4,VI,V2 ANDV V5,V2,V3又如：读写相关ADDV V4,VlfV2ANDV V5,V4,V3;V5-V4 AV3 资源冲突ADDV V3,VI,V2;V3-V1+V2ADDV V6,V4ZV5;V6T4+V51.链接技术。利用向量指令间存在的写后读(RAW)的数据相关性采用专用通道来加快 向量指令序列执行速度。例如：ADDV VI,V2,V3;VI-V2+V3MULTV V4,VI,V5;V4-V1+V5又如：LV V3,A;V3-AADDV V2,VO,VI;V2-V0+V1MULTV V4ZV2,V3;V4-V2XV32.条件语句的处理。采用屏蔽向量例如：do 100 i=l,64if(A(i).ne.0)thenA(i)=A(i)-B(i)endif100 continue的向量指令为：LV VI,Ra；将向量A装入VILV V2,Rb；将向量B装入V2LDFOZ#0SENSVF0,VISUBVVI,VI,V2CVMSVRa,VI 屏蔽向量不能减少执行时间；将浮点数0装入FO；V1(i)ZF0,则将 VMi 置为 1；在屏蔽向量控制下进行减法操作；将屏蔽向量寄存器置为全“1”；将结果存入A4.向量归约操作 递归折叠法：思考题：画出本例的流水线的时空图 习题:217117p max/p=mAZ+(7?-1)AZAr(l+m1)1 Im-1nn2.加速比：流水方式的工作速度与等效的顺序工作方式时间的比值。Ti _ nm _ mTk m+n-1+1n工作时间的时空区与流水线中各段总的时空区之比。nmNtn SPE=TpAtm(m+m+n-1 m三、流水线的相关处理三种相关性：1.资源相关(结构相关)段 号(c)流水段重复的时空图对于线性流水线：3.使用效率:退耦流水线Sp 解决方法：增加资源.数据相关（RAW、WAR、WAW）解决方法：停顿、编译检测、旁路相关专用通路.控制相关。解决方法：提前判断、转移延迟槽等非线性流水线的调度方法预约表表8-1非线性流水线预约表tht4ts（6tl18t9XXs2XXX3X兴XXS5XX禁止表冲突向量 C 二 10110001调度状态转换图图8-3非线性流水线状态图调度方案比较表8.2各种调度方案的平均间隔拍数调度策略平均间隔周期be:(3,4)3.50ad:(2,7)4.50ade:(2,2,7)3.67abeb:(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第二节标量流水技术一、基本概念指令流水线结构:U!流水线的调度F=1,5,6,8)loop:LDstallADDDSUBIBNEZSDFO,0(RI)F4,FO,F2RI,RI,8RI,loop8(RI),F4指令级并行性：指令序列中的并行性。基本块循环级并行性：循环递归之间的并行性。例：for(i=l;i=1000;x i =x i +s;i=i+l)循环展开后loop:LDADDDSD SUBIBNEZFO,0(RI);F4,FO,F2;0(RI),F4;RI,RIA8;RI,loop;F0=arrayelement addscalar in F2store resultdecrementpointer 8bytes(perDW)branchif RI!=zero执行时的情况：loop:LD FO,0(RI)stallADDD F4,FO,F2stall stallSD 0(RI),F4 SUBIRI,RI,8 BNEZRIfloop stall指令调度后：123456789执行时间减少到6个时钟周期。loop:LD FO,0(RI)ADDD SD LDADDD SD LD ADDD SD LD ADDDF4,FO,F20(RI),F4 F6,-8,0(RI)F8,F6,F2-8(RI),F8F10,-16(RI)F12rF10,F2-16(RI),F12F14r-24(RI)F16,F14,F2 将上述程序展开3次之后23123123123SD-24(RI),F16SUBI RI,RI,#32 BNEZ RI,loop未调度时，执行时间为27个周期，平均每个迭代6.8个周期。loop:LD F0,0(R1)LD F6,-8,0(R1)LD F10,-16(R1)LD F14,-24(RI)ADDD F4,F0,F2ADDD F8,F6,F2ADDD F12zF10,F2ADDD F16,F14,F2SD 0(RI),F4SD-8(RI),F8SD-16(RI),F12SUBI RI,RI,#32BNEZ RI,loopSD 8(RI),F16调度后，执行时间为14个周期，平均每个迭代3.5个周期。指令流水处理中的相关性：(1)数据相关。如果满足以下两个条件，则称指令j与指令，是数据相关的:A.指令i产生的结果被指令,使用；B.指令J与指令攵数据相关，而指令Z与指令i数据相关。上述程序简单展开的结果是：loop:LD FO,O(R1)ADDD F4,F0,F2SD O(R1),F4SUBI RI,RI,#8LD F6,O(R1)ADDD F8,F6,F2SD O(R1),F8SUBI RI,RI,#8LD F10,0(Rl)ADDD F12,F10,F2SD O(R1),F12SUBI RI,Ri,#8LD F14,O(R1)ADDD F16,F14,F2SD O(R1),F16SUBI RI,RI,#8BNEZ RI,loop这里，相关性都来自减法指令。它使得指令只能顺序执行，而且指令数量多。(2)名字相关。名字相关发生在当两条指令使用相同的寄存器或存储单元(称为名字)时。但是在指令之间不存在涉及该名字的数据流。在指令i及其后的指令)之间存在两种名 字相关性。A.反相关。当指令j写一个寄存器，而指令i读这个寄存器时发生反相关。反相关对 应于WAR险象，这种险象的检测使得反相关指令对保持其原有的顺序。B.输出相关。输出相关发生于指令i和指令/写相同寄存器或存储器单元时。指令的 顺序必须保持。输出相关对应于WAW险象，可通过检测手段发现。解决名字相关的方法：寄存器更名(Register rename)。例如对于上述循环的例子，如果不进行寄存器重新命名，其名字相关的情况如下所示：loop:LD FO,O(R1)ADDD F4,F0,F2SD 0(Rl),F1LD F0,-8(Rl)ADDD F4,F0,F2SD-8(Rl),F4LD F0,-l6(Rl)ADDD F4,F0,F2SD-16(Rl),F4LD F0,-24(Rl)ADDD F4,F0,F2SD-24(Rl),F4SUBI RI,RI,#32BNEZ R1 Joop这些名字相关迫使指令序列只能按序执行。在经过了寄存器重新命名之后，名字相关就被消除，而只剩下数据相关。loop:LD FO,()(R1)ADDD F4,F0,F2SD O(R1),F4LD F6r8(Rl)ADDD F8,F6,F2SD-8(R1),F8LD F1O,-16(R1)ADDD F12,F1(),F2SD-16(R1),F12LD F14,-24(R1)ADDD Fl 6,Fl 4,F2SD-24(R1),F16SUBI RI,RI,#32BNEZ RI,loop(3)控制相关。控制相关决定了转移指令与其它指令之间的执行顺序。程序中除了开 始的第一个基本块之外，其它每条指令都对某些分支指令有控制相关性，通常必须保持这 种控制相关性。控制相关导致两个基本约束：A.一条与一个分支相关的指令不能移动到这个分支指令之前而使这条指令不受该分 支的控制。B.一条与一个分支不相关的指令不能移动到这个分支之后而使这条指令受到该分支 指令的控制。上例中循环展开时取消了一些控制指令，因而消除了一些控制相关。两种保持控制相关性的方法：(1)按序执行；(2)检测控制或分支险象，保证与分支指 令控制相关的指令在分支的方向明确之后才执行，而与分支指令不相关的指令则可以提前 或者延迟执行。控制相关本身不是必须保持不变的本质因素。必须保持不变的是程序的两个特性：异常行为和数据流。例如：BEQZ R2,L1 LW R1,0(R2)L1:这里只存在控制相关，不存在数据相关。习题：7二、指令的动态调度静态调度：用编译调度 动态调度：用硬件调度 基本思想：无序执行一一打破指令执行的顺序限制。有序指令启动：DIVD FO,F2,F4ADDD F10,FO,F8SUBD F12,F8,F14第三条指令不能提前启动。无序指令启动的方法：记分牌方法，Tomasulo法1.记分牌方法记分牌的构成：(1)指令状态表。(2)功能部件状态表。(3)寄存器结果状态表。四个执行阶段：启动、读操作数、执行、写结果(1)启动规则：无结构冲突，没有WAW相关(2)读操作数规则：操作数具备一一消除RAW相关(3)写结果规则：前面指令已读取操作数或者无数据相关一一消除WAR相关 例如：一个具有五个功能部件的CPU,包括一个整数部件(Integer)、两个乘法部件(Multi,Mult2).一个加法部件(Add)和一个除法部件(Divide)。假定以下指令序列：LD F6,34(R2)LD F2,45(R3)MULTD F0,F2,F4SUBD F8,F6,F2DIVD F10,F0,F6ADDD F6,F8,F2这里LD指令由整数部件执行(无流水功能)，加法和减法都由加法部件执行，乘法和 除法运算操作由相应的部件执行。指令状态表指令状态指令启动 读操作数执行完成写结果LD F6,34(R2)1234LD F2,45(R3)567MULTD F(),F2,F46SUBD F8,F6,F27DIVDF10,F0,F68ADDD F6,F8,F2功能部件状态表部件功能部件状态名称Busy OpFiFjFkQjQkRjRkIntegerYesLoad F2R3NoMultiYes Mult FOF2F4IntegerNo YesMult2NoAddYesSubF8F6F2Integer Yes NoDivideYesDiv F10FOF6MultiNo Yes寄存器结果状态表FOF2F4F6F8 F10F12F30MultiIntegerSub Divide假定加法部件的执行需要2个时钟周期，乘法需要10个周期，除法需要40个周期。在MULTD和DIVD与结果时的记分牌情况如下所示。指令状态表指令状态指令启动读操作数执行完成写结果LD F6,34(R2)1234LD F2,45(R3)5678MULTD F0,F2,F4691920SUBD F8,F6,F2791112DIVDF10,F0,F68216061ADDD F6,F8,F213141622功能部件状态表功能 部件状态部件名BusyOpFiFjFkQjQkRjRkIntegerNoMultiYesMultFOF2F4NoNoMult2NoAddYesAddF6F8F2NoNoYes Div F10 FO F6 Multi 寄存器状态表FOF2F4F6F8F10F12 F30MultiAddDivide习题：122.Tomasulo调度法特点：寄存器更名一一消除名字相关分布式保存站一一并行调度消除调度瓶颈写回控制一一写写相关时最后一条指令写入命令队列一一使取指令与启动执行退耦例如：指令序列及其执行状态如下（假定执行周期数与上述相同）：指令状态表指令状态指令启动执行完成写结果LD F6,34(R2)134LD F2,45(R3)245MULTD F0,F2,F431516SUBD F8,F6,F2478DIVDF10,F0,F655657ADDD F6,F8,F261011各保存站情况如下:部件名保存站BusyOpVjVkQjQkAddlYesSUBMem34+RegsR21Load2Add2YesADDAddlLoad 2Add3NoMultiYesMULTRegsF4Load2Mult2YesDIVMem34+RegsR2Multi各浮点寄存器状态如下表:FO F2F4F6 F8 F10F12F30Multi Load2Add2 Addl Mult2DivideNo Yes三、分支预测静态：永远不转移，永远转移，后向转移(准确率40%65%)(i486)动态：1位,2位，多位(1级，2级)建立一个记录转移状态的cache1位动态：根据上次转移情况预测下次，准确率77%79%(Alpha)2位动态：根据上两次转移情况预测下次，准确率78%89%(奔腾)指令处理部件存储器总线装入缓存二s001(LD F3.34(R2)LDF6 j 4(R3)译码器二浮点操作 二命令队列浮点寄存器2级预测：根据多次转移情况选择预测状态，准确率93%(P6)图8-7两级转移预测方法分支目标缓存：快速形成分支目标地址或者目标指令。2级预测：根据多次转移情况选择预测状态，准确率93%(P6)移位方向转移历史寄存器
