流水技术与向量处理课件

《流水技术与向量处理课件》由会员分享，可在线阅读，更多相关《流水技术与向量处理课件（189页珍藏版）》请在金锄头文库上搜索。

1、第第1 1章章 计算机系统设计基础计算机系统设计基础第第2 2章章 数据表示与指令系统性能分析数据表示与指令系统性能分析第第3 3章章 通道处理机通道处理机第第4 4章章 流水技术和向量处理流水技术和向量处理 第第5 5章章 阵列计算机阵列计算机 第第6 6章章 多处理机系统多处理机系统第第7 7章章 其它计算机结构其它计算机结构7/29/20241第第4 4章章 流水技术与向量处理流水技术与向量处理 4.1 标量流水工作原理标量流水工作原理4.2 标量流水中的障碍及控制标量流水中的障碍及控制 4.3 流水线的调度技术流水线的调度技术4.4 先进的流水技术先进的流水技术4.5 Pentium微

2、微处处理理器器中中的的流流水水技技术术4.6 向量流水技术向量流水技术7/29/20242本章学习要求掌握标量流水的性能分析及障碍的处理方法掌握非线性流水调度技术掌握向量流水机的结构特征、向量指令并行性分析了解标量流水、超标量流水、超流水及超长指令字计算机的基本工作原理7/29/20243提高指令执行速度的主要途径：提高指令执行速度的主要途径：(1) (1) 提高处理机的工作主频提高处理机的工作主频(2) (2) 采用更好的算法和设计更好的功能采用更好的算法和设计更好的功能部件部件(3) (3) 采用指令级并行技术采用指令级并行技术三种指令级并行处理机：三种指令级并行处理机：(1) (1) 流

3、水线处理机和超流水线流水线处理机和超流水线(Super-(Super-pipelining)pipelining)处理机处理机(2) (2) 超标量超标量(Superscalar)(Superscalar)处理机处理机(3) (3) 超长指令字超长指令字(VLIW: Very Long (VLIW: Very Long Instruction Word)Instruction Word)处理机处理机7/29/202444.1 标量流水工作原理标量流水工作原理什么是流水线？什么是流水线？考虑设计一个洗衣机的工作流程，假定它有三道考虑设计一个洗衣机的工作流程，假定它有三道工序：洗涤、清洗、甩干。每

4、个环节为工序：洗涤、清洗、甩干。每个环节为5 5分钟分钟。需要完成的任务为需要完成的任务为3 3批，则考虑下述工作方式的工批，则考虑下述工作方式的工作效率作效率：第一种：串行工作方式，即按照如下方式工作：第一种：串行工作方式，即按照如下方式工作：第第1批批洗涤洗涤第第1批批清洗清洗第第1批批甩干甩干第第2批批洗涤洗涤第第2批批清洗清洗第第2批批甩干甩干第第3批批洗涤洗涤第第3批批清洗清洗第第3批批甩干甩干3批批衣服的整个工作时间为衣服的整个工作时间为3*3*5=45分钟分钟7/29/20245第二种：重叠工作方式，设计三个部件，可以同时第二种：重叠工作方式，设计三个部件，可以同时工作，每个部件

5、只做一样工作，操作方式如下图：工作，每个部件只做一样工作，操作方式如下图：第第1批批洗涤洗涤第第1批批清洗清洗第第1批甩干批甩干第第2批洗涤批洗涤 第第2批清洗批清洗第第2批甩干批甩干第第3批洗涤批洗涤第第3批清洗批清洗第第3批甩干批甩干Tttttt3 3批批衣服的工作时间为衣服的工作时间为5*5=255*5=25分钟，节省分钟，节省2020分钟。分钟。7/29/20246引出下述关于洗衣机工作的有关性能特点：引出下述关于洗衣机工作的有关性能特点： 吞吐率：单位时间内完成的任务数吞吐率：单位时间内完成的任务数TP=n/TTP=n/T 加速比：串行方式与流水线方式的时间比：上述为加速比：串行方式

6、与流水线方式的时间比：上述为 45/25=1.845/25=1.8 效率：即洗衣机的利用率，上述洗衣机的效率是效率：即洗衣机的利用率，上述洗衣机的效率是9/15=3/5=60%9/15=3/5=60%将一条指令的执行分为几个阶段，让几条指令按重将一条指令的执行分为几个阶段，让几条指令按重叠或流水方式工作，以提高程序的执行速度。这就叠或流水方式工作，以提高程序的执行速度。这就引出了计算机中的流水线技术。引出了计算机中的流水线技术。7/29/20247指令的重叠解释与先行控制计算机系统中广泛存在着重叠工作方式指令的解释方式一般只有三种：顺序、重叠和流水重叠和流水给指令的执行带来了高的吞吐率和加速比

7、，同时也给系统增加了障碍7/29/20248指令的解释过程指令的解释过程ALULOAD/STOREIF取指取指取指取指ID译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆EX执行执行计算访存有效地址计算访存有效地址MEM-访存（读或写）访存（读或写）WB结果写回寄存器堆结果写回寄存器堆将将读出的数据写入寄存器堆读出的数据写入寄存器堆7/29/20249一、指令的重叠解释方式一、指令的重叠解释方式1 1、顺序执行方式、顺序执行方式 一条指令的执行过程：一条指令的执行过程：取指令取指令-分析分析-执行执行执行执行n n条指令所用的时间为：条指令所用的时间为： 如每段时间都为如每段时

8、间都为t t，则执行则执行n n条指令所用的时间为：条指令所用的时间为：T=3ntT=3nt主要优点：主要优点：控制简单，节省设备。控制简单，节省设备。主要缺点：主要缺点：执行指令的速度慢，功能部件的利用率很低。执行指令的速度慢，功能部件的利用率很低。取指令k 分析k 执行k 取指令k+1 分析k+1 执行k+17/29/202410 2 2、重叠执行方式、重叠执行方式( (最简单的流水线方式最简单的流水线方式) ) 如果每个过程的时间相等，则执行如果每个过程的时间相等，则执行n n条指令的条指令的时间为：时间为：T=(1+2n)tT=(1+2n)t 主要优点：主要优点： 指令的执行时间缩短指

9、令的执行时间缩短 功能部件的利用率明显提高功能部件的利用率明显提高 主要缺点：主要缺点： 需要增加一个需要增加一个IBRIBR取指 分析 执行取指 分析 执行取指 分析 执行7/29/2024113、更高重叠度的重叠解释方式、更高重叠度的重叠解释方式把取第把取第k+1条指令提前到分析第条指令提前到分析第k条指令同时执行条指令同时执行如果三个过程的时间相等，执行如果三个过程的时间相等，执行n n条指令的时间条指令的时间为：为：T=(2+n)tT=(2+n)t理想情况下同时有三条指令在执行理想情况下同时有三条指令在执行处理机的结构要作比较大的改变，必须采用先行处理机的结构要作比较大的改变，必须采用

10、先行控制方式控制方式取指k+2 分析k+2 执行k+2取指k+1 分析k+1 执行k+1取指k分析k执行k7/29/2024121访存冲突访存冲突 分析与取指均要访问主存分析与取指均要访问主存 解决：解决： 1）采用两个独立编制的存贮器）采用两个独立编制的存贮器 数据数据/指令指令 但增加了复杂性但增加了复杂性 2）采用多体交叉存贮器）采用多体交叉存贮器 3）指令缓冲寄存器指令缓冲寄存器2功能部件的冲突功能部件的冲突 解决：解决：设置独立的分析部件和执行部件设置独立的分析部件和执行部件 重叠方式对计算机组成的要求重叠方式对计算机组成的要求7/29/2024133同步同步 分析与执行所需的时间不

11、同，要求的是一次分析与执行所需的时间不同，要求的是一次重叠重叠 一一次次重重叠叠：任任何何时时间间都都是是“分分析析K+1”与与“执执行行K”的重叠的重叠 =相邻两条指令的重叠相邻两条指令的重叠分析分析K执行执行K分析分析K+1 执行执行K+1T=(n+1)t7/29/2024144转移转移 无无条条件件转转移移/条条件件转转移移当当转转移移成成功功时时，重重叠叠预预取无效，变为顺序执行取无效，变为顺序执行 应尽可能不使用或少使用条件转移指令应尽可能不使用或少使用条件转移指令5相关相关 邻邻近近指指令令之之间间出出现现某某种种关关联联，为为避避免免出出错错而而不不能能同时执行的现象。同时执行的

12、现象。 局部性相关、全局性相关局部性相关、全局性相关7/29/2024157/29/202416先行控制技术先行控制技术基本思想：使分析和执行部件分别连续不断地运行，使部基本思想：使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。件空闲状态减至最低。(a)重叠方式分析分析k+1分析分析k执行执行k执行执行k+1分析分析k+2执行执行k+2分析部件空闲执行部件空闲分析分析k+1分析分析k执行执行k分析分析k+2(b)先行控制执行执行k+1执行执行k+27/29/202417关键：缓冲技术预处理技术缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作预处理技术：把进

13、入运算器的指令都预处理成R-R型指令，与缓冲技术相结合，为进入运算器的指令准备好所需的全部操作数先行控制方式使运算器可专注于运算，从而可大幅度提高程序的执行速度 硬件要求：增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。7/29/202418工作原理主主 存存存存 控控指令分析器指令分析器先行先行指令栈指令栈先行读先行读数栈数栈后行写后行写数栈数栈执行执行部件部件先行操作栈先行操作栈数据缓冲栈数据缓冲栈 栈的深度要求：栈的深度要求：D D指缓指缓D D操作操作 D D读栈读栈 D D写栈写栈7/29/202419二、标量流水工

14、作原理二、标量流水工作原理基本思想：基本思想：流水是重叠的进一步延伸，流水是重叠的进一步延伸，使指令解释过程进一步细化，提高各部使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度。件的利用率，以提高指令执行速度。流水线的表示方法：流水线的表示方法：连接图、时空图、连接图、时空图、预约表预约表7/29/2024201 1、简单流水线的连接图表示、简单流水线的连接图表示 流水线的每一个阶段称为流水段、流水线流水线的每一个阶段称为流水段、流水线阶段、阶段、流水功能段流水功能段、功能段、流水级、流水、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相节拍等。一个流水阶段与另一个流

15、水阶段相连形成流水线。连形成流水线。 有些复杂指令，在执行阶段也采用流水线有些复杂指令，在执行阶段也采用流水线方式工作，称为操作流水线。方式工作，称为操作流水线。取指取指访存访存执行执行译码译码写回写回IFIDEXMEMWBS1S2S3S4S5输入输入输出输出7/29/202421 一种指令流水线一种指令流水线一般一般4 4至至1212个流水段，等于及大于个流水段，等于及大于8 8个流水段的称为超流水个流水段的称为超流水线处理机线处理机2 2、流水线的时空图、流水线的时空图采用采用“时空图时空图”表示流水线的工作过程。表示流水线的工作过程。一条简单流水线一条简单流水线的时空图的时空图：取指形成

16、操作数地址译码取操作数执行保存结果7/29/202422一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图( (由求阶差、对阶、由求阶差、对阶、尾数加和规格化尾数加和规格化4 4个流水段组成个流水段组成) )：ED1时间空间0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4 MA5NL1 NL2 NL3 NL4 NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差EDEAMANLmt7/29/2024233、流水线的预约表时间流水段1234567S1XXXS2XXS3XXS4X7/29/202424三、流水

17、线工作方式三、流水线工作方式取指取指访存访存执行执行译码译码写回写回IFIDEXMEMWBS1S2S3S4S5输入输入输出输出指令的流水处理指令的流水处理 流流水水线线的的基基本本结结构构中中主主要要包包括括三三大大部部分分：锁锁存存器器、时时钟钟、功能段。功能段。 流流水水线线中中每每个个段段都都是是由由一一些些执执行行算算术术和和逻逻辑辑功功能能的的组组合合逻逻辑辑线线路路组组成成的的，它它们们可可以以互互相相独独立立地地对对流流过过的的信信息息进进行行某某种种操操作作，相相邻邻两两站站由由高高速速锁锁存存器器（latch）隔隔开开，信信息息在在各各段段间间的的流流动靠同时送到各站的时钟信

18、号来控制。动靠同时送到各站的时钟信号来控制。1 1、流水线的结构、流水线的结构7/29/202425S1S2Sm输入输入 输出输出流水线的基本结构流水线的基本结构.时钟时钟7/29/202426121321nn-1.43215432.543.54.5nn-1.n-1.nn-1 n1234tt0 0 t t0 0 t t0 0 t t0 0T T0=0=m m t t0 0n n t t0 0T T(m-1) t(m-1) t0 0(n-1) t(n-1) t0 0填入填入 正常正常 排空排空 流水时空图流水时空图空间空间时间时间建立时间、正常流动时间、排空时间。建立时间、正常流动时间、排空时间

19、。2 2、流水线工作的三个时间、流水线工作的三个时间7/29/2024273 3、流水线的分级、分类、流水线的分级、分类分级分级：（处理的级别分类）：（处理的级别分类）v 部件级部件级(操作流水线操作流水线)：将复杂的算逻运算组成流水工作方式；：将复杂的算逻运算组成流水工作方式；v指令级：指令级：把一条指令解释过程分成多个子过程把一条指令解释过程分成多个子过程 ；v处理机级：每个处理机完成某一专门任务，各个处理机所得到的处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中结果需存放在与下一个处理机所共享的存储器中 7/29/202428其他分类：其

20、他分类： 功能：单功能流水线（如功能：单功能流水线（如CRAY-1CRAY-1）、）、多功能流水线（如多功能流水线（如TI-TI-ASCASC） 工作方式：静态流水线、动态流水线工作方式：静态流水线、动态流水线 连接方式：线性、非线性连接方式：线性、非线性 处理数据：标量流水、向量流水处理数据：标量流水、向量流水1234出出入入非线性流水线非线性流水线7/29/2024291)ASC算术运算流水线（多功能）算术运算流水线（多功能）输入输入减阶减阶对阶移位对阶移位相加相加规格化规格化相乘相乘累加累加输出输出123456784 4、流水线举例、流水线举例输入输入减阶减阶对阶移位对阶移位相加相加规格

21、化规格化输出输出123458加加输入输入相乘相乘累加累加输出输出1678乘乘7/29/202430.1234.n-1 n.1234.n-1 n.1234.n-1n.1234.n-1 n12345867.1234.n-1 n.1234.n-1 n时间时间空间空间(段号段号)加法加法一一 二二 三三 四四二二 三三一一二二一一一一乘法乘法.静态多功能流水线时静态多功能流水线时-空图空图静态流水线：静态流水线：只有当进入的是一串相同运算的指令时，流水的只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据效能才得以发挥，才能使各个功能段并行地对多条指令的数据

22、进行流水处理。进行流水处理。 7/29/202431区区别别：如如果果从从软软硬硬功功能能分分配配的的观观点点上上来来看看，静静态态流流水水线线其其实实是是把把功功能能负负担担较较多多地地加加到到软软件件上上，以以简简化化硬硬件件；动动态态流流水水线线则则是是把功能负担较多地加在硬件上，以提高流水的效能。把功能负担较多地加在硬件上，以提高流水的效能。.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n12345867.12345.n-1 n.12345.n-1 n时间时间加法加法乘法乘法一一二二三三 四四 五五 六六一一二二三三 四四 五五 六六七七

23、一一二二三三 四四 五五一一二二三三 四四动态多功能流水线时动态多功能流水线时-空图空图m7/29/202432四、标量流水线性能分析四、标量流水线性能分析衡量流水线处理机的性能主要是衡量流水线处理机的性能主要是吞吐率、加速比和效率吞吐率、加速比和效率。 1吞吞吐吐率率：单单位位时时间间内内能能处处理理的的指指令令条条数数或或能能输输出出的的数数据据量量。吞吞吐吐率率越越高高，计计算算机机系系统统的的处处理理能能力力就就越越强强。就就流流水水线线而而言言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。吞吐率就是单位时间内能流出的任务数或能流出的结果数。最大吞吐率：流水线达到稳定状态后可获

24、得的吞吐率。最大吞吐率：流水线达到稳定状态后可获得的吞吐率。（1）Tpmax=1/ t （2）TPmax=1/ max t1， t2， t3， t4 “瓶颈瓶颈”子过程：子过程： 1234 t t 3 t t 7/29/202433子过程子过程3为瓶颈段的时空图为瓶颈段的时空图最大吞吐率最大吞吐率TPmax=1/3 t mTS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234输出输出7/29/202434131232334 2 1 4 3a 3b 3c 333瓶颈段细分瓶颈段细分重复设置瓶颈流水段重复设置瓶颈流水段解决瓶颈有两

25、种方法解决瓶颈有两种方法A：B：7/29/202435T重复设置瓶颈流水段后的工作时空图重复设置瓶颈流水段后的工作时空图mS1S2S3aS3cS3bS41 2 3546 7 8 9 10 11121 2 3546 7 8 9 10 11121471025811369121 2 3546 7 8 9 10 11 12t1t12t177/29/202436实际吞吐率实际吞吐率（1）完成）完成n条指令的解释共需时间条指令的解释共需时间 可可以以看看出出不不仅仅实实际际的的吞吞吐吐率率总总是是小小于于最最大大的的吞吞吐吐率率，而而且且只只有有当当nm时时，实实际际的的吞吞吐吐率率才才能能接接近近于于理

26、理想想的最大吞吐率。的最大吞吐率。(2)各功能段时间不相等各功能段时间不相等7/29/2024372.效率：设备的利用率，直接反映了处理机结构有效程度。流水线有建立时间、排空时间，不总是满负载工作。各段时间相等：各段时间相等：各段时间不等：各段时间不等：7/29/202438各段时间相等各段时间相等:各段时间不等各段时间不等:3.加速比加速比：M段流水线的速度与等效的非流水线的速段流水线的速度与等效的非流水线的速度之比。度之比。7/29/202439K=6K=10任务个数加速比10246811 248 16 32 64 128因为因为因此：因此：E=TPE=TP t t ，S=kS=kE E流

27、水线的吞吐率、加速比与效率的关系流水线的吞吐率、加速比与效率的关系7/29/202440例例1.有一四段线性流水线,每功能段延时时间分别是：t1=t3=t4=t, t2=3t。现在这个流水线上分别执行4个任务和40个任务。求实际吞吐率、效率和加速比。解法一：解法一：时空图分析法时空图分析法时间时间12343111223234123123123444443t3t3t3t空间空间157/29/202441Tp=4/(15t)E=24t/(4*15t)=40%Sp=4*6t/15t=1.6完成4个任务时：完成40个任务时，如何画时空图呢？方法二，公式分析法。当流水线中各功能段的执行时间不相等时，有7

28、/29/2024427/29/202443例2、以浮点加法运算为例（四段）各段时间相等，求Z=A+B+C+D+E+F+G+H的TP、E、Sp。时间时间空间空间Z=A+B+C+D+E+F+G+H1234567TP=7/15ttE E=7*4/(15*4)=7/15Sp=4*7/15=28/15=1.871111222233334444555566667777157/29/202444例例3. ASC计算机功能算术运算流水线各段时间相等，6次浮点加、5次定点乘的吞吐率、效率和加速比。1,2,3,4,5,8组成加法流水1,6,7,8组成乘法流水12345678对阶减阶输出相加规格化相乘累加输入ASC

29、计算机的流水线7/29/202445分析：分析：T T加加=6+(6-1)*1=11 T=6+(6-1)*1=11 T乘乘=4+(5-1)*1=8 =4+(5-1)*1=8 TP= 11/(11+8)t =11/19 tTP= 11/(11+8)t =11/19 tE= (6*6+5*4) t /(19*8t)=11.54%E= (6*6+5*4) t /(19*8t)=11.54%Sp= 56 t /19 t =2.94Sp= 56 t /19 t =2.941 234561 234561 234561 23456123458671 234561 23456时间时间浮加浮加定点乘定点乘一一二

30、二三三 四四 五五一一二二三三 四四 五五一一二二三三 四四五五一一二二三三 四四五五7/29/2024464.24.2 标量流水中的障碍及控制标量流水中的障碍及控制保持流水线性能条件：保持流水线性能条件：不能停顿或断流。不能停顿或断流。影响流水线性能因素：影响流水线性能因素：相关和功能切换。相关和功能切换。相关类型：相关类型：全局相关：转移指令引起的相关全局相关：转移指令引起的相关结果：结果：流水线断流，流水线中后续指令全部作流水线断流，流水线中后续指令全部作废。废。局部相关：资源或结构相关；指令相关；数据相局部相关：资源或结构相关；指令相关；数据相关。关。结果：结果：流水线停顿，流水线中后

31、续指令有效。流水线停顿，流水线中后续指令有效。7/29/202447一、资源相关资源相关：功能部件、主存资源当有多条指令进入流水线后在同一机器周期内争用同一功能部件所引起的相关（冲突）当有多条指令进入流水线后在同一机器周期内同时访问主存资源7/29/202448例例1：两条指令同时要用一个加法器两条指令同时要用一个加法器ALULOAD/STOREIF取指取指取指取指ID译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆EX执行执行计算访存有效地址计算访存有效地址MEM-访存（读或写）访存（读或写）WB结果写回寄存器堆结果写回寄存器堆将将读出的数据写入寄读出的数据写入寄存器堆存器堆

32、指指 令令流水段流水段不同类型指令中各流水段进行的操作不同类型指令中各流水段进行的操作7/29/202449两条指令同时访存造成资源相关两条指令同时访存造成资源相关MEMEXIDIF指令指令i+4WBMEMEXIDIF指令指令i+3WBMEMEXIDIF指令指令i+2WBMEMEXIDIF指令指令i+1WBMEMEXIDIFLoad指令指令87654321 时钟时钟指令指令冲突冲突取指取指 译码译码 执行执行 访存访存 写回写回例例2：7/29/202450EXIDIF指令指令i+4MEM EXIDIF停顿停顿指令指令i+3WBMEMEXIDIF指令指令i+2WBMEMEXIDIF指令指令i+

33、1WBMEMEXIDIFLoad指令指令87654321 时时钟钟指令指令9WBMEM使使i+3指令停顿一拍进入流水线，以解决访存相关；指令停顿一拍进入流水线，以解决访存相关；或重复设置一个存储器；采用或重复设置一个存储器；采用先行控制技术先行控制技术解决方法：解决方法：7/29/202451二、指令相关后续指令的内容取决于当前指令执行的结果，即指令允许修改引起的相关解决相关：不准修改指令、变指令相关为数据相关EXR1D2B2X2IBM370中的“执行”指令7/29/202452三、数据相关由于流水线中的各条指令间的重叠解释，使得原来对操作数的访问顺序发生了变化，从而导致了数据之间的相关。这种

34、相关有三类：先写后读（改用相关） 、先读后写（用改相关） 、写写相关（改改相关）。设有i和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为：7/29/202453 RAW读写读写(先写后读)-指令j试图在指令i写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。 i: R1+R2-R3 j: R3*R4-R5 WAR写读写读(先读后写)-指令j试图在指令i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。 i: R3*R4-R5 j: R1+R2-R3 WAW写写写写(先写后写)-指令j试图在指令i写寄存器之前就写入该寄存器，这

35、样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。 i: R1*R2-R3 j: R4+R5-R37/29/202454解决数据相关的办法用软件和硬件技术：解决数据相关的办法用软件和硬件技术：v时间推后法时间推后法v旁路技术或相关专用通路技术旁路技术或相关专用通路技术例：例： n : load A IF ID EX WR n+1: load B IF ID EX WR n+2: add A,B IF ID 气泡气泡 EX WR n+3: store C IF ID 气泡气泡 EX WR n+4 : jump K IF ID EX WR n+5: load E 停顿停顿

36、停顿停顿 停顿。停顿。 n+6 停停顿。顿。 K: IF ID EX 例中有资源相关、有控制转移相关，这将影响流水线的性能。例中有资源相关、有控制转移相关，这将影响流水线的性能。7/29/202455IF ID EX MEM WB IF ID EX WB IF ID EX WB IF ID EX WB IF ID EX WB ADD R1,R2,R3SUB R4,R1,R5AND R6,R1,R7OR R8,R1,R9XOR R10,R1,R11定向传递定向传递R1值值数据相关和定向传递指令数据相关和定向传递指令写写R1完完成成MEM MEM MEM MEM 7/29/202456ALU运算结

37、果运算结果写写RF RF读读RFALU操作数寄存器操作数寄存器专用通路（旁路）专用通路（旁路）旁路旁路RFALUBufferMultMult7/29/202457四、全局性相关由转移指令（条件/无条件）引起的相关转移指令在程序中所占比例约为20-25%，不可忽视解决这种相关的方法：猜测法、加快和提前形成条件码、加快短循环程序的处理、采用延迟转移技术7/29/2024581 1、猜测法：、猜测法：选取发生概率较高的分支为猜测选取发生概率较高的分支为猜测方向，若猜对，继续执行；否则方向，若猜对，继续执行；否则, ,作废猜测作废猜测方向的执行，返回实际转移处。方向的执行，返回实际转移处。（1 1）如

38、何提高猜测命中率）如何提高猜测命中率 静态猜测法：静态猜测法：猜测不成功方向。由程序猜测不成功方向。由程序员和编译程序把发生概率高的分支安排在猜员和编译程序把发生概率高的分支安排在猜测方向。测方向。 动态猜测法：动态猜测法：根据转移历史猜测。根据转移历史猜测。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功7/29/202459转移目标缓冲器(BTB)利用BTB(BranchTargetBuffer)硬件，动态地预测转移方向转移指令地址转移指令地址转移目标地址转移目标地址状态状态欲取欲取指令的指令的PC查找查找预测预测PC值值=按按正常顺正常顺序执行序执行NY7

39、/29/202460转移预测原理：转移预测原理：用用2位二进制数记录实际转位二进制数记录实际转移状态移状态(历史位历史位)，高位，高位为为1时预测转移发生，时预测转移发生，高位为高位为0时预测转移不发生。时预测转移不发生。注意：注意：初始状态、状态修改、猜测方向表示初始状态、状态修改、猜测方向表示预测发生11预测发生10预测不发生01预测不发生00转移1不转移0不转移0不转移0转移1转移1转移1不转移07/29/202461（2 2）猜测的后续处理）猜测的后续处理 分支现场的保护及恢复：分支现场的保护及恢复： 猜测执行只完成译码、取操作数或执行但不写结果； 采用后援寄存器保存可能被破坏的状态。

40、 预防猜不中时的加速处理：预防猜不中时的加速处理： 预取猜测方向的另一方向的前几条指令，放到缓冲器中，加速猜不中时回头速度。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功7/29/2024622 2、加快和提前形成条件码、加快和提前形成条件码单条指令的条件码并不一定要等执行完成单条指令的条件码并不一定要等执行完成得到运算结果后才能形成得到运算结果后才能形成循环程序判断的提前形成循环程序判断的提前形成 3 3、优化延迟转移技术、优化延迟转移技术 a.a.将转移指令前的那条指令调度到延迟槽中；将转移指令前的那条指令调度到延迟槽中； b.b.将转移目标处的那条指令调

41、度到延迟槽中；将转移目标处的那条指令调度到延迟槽中； c.c.将转移不发生时该执行的那条指令调度到将转移不发生时该执行的那条指令调度到延迟槽中。延迟槽中。4 4、加快短循环处理、加快短循环处理7/29/202463五、流水线中的中断处理流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题不精确断点法不精确断点法：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。断点就是最后进入流水线的那条指令7/29/202464S1S8S7S6S5S4S3S2输入输入输出输出i+5ii-1i+1i+2i+3i+4i-2PC：不精确断点

42、申请中断申请中断精确断点精确断点特点：特点：硬件开销小，控制简单，适用于常规的I/O操作。7/29/202465 精确断点法：精确断点法：不论第i条指令是在流水线中哪一段发出的中断申请，给中断处理程序的现场全都是对应第i条的。适用于程序性错误和机器故障等产生的中断精确断点法中对原有现场的恢复，要增加后援寄存器，以保留各功能段状态i:FADDR1,R2;(R1)+(R2)R1i+1:FMULR3,R1;(R3)*(R1)R3S6：加法加法结果溢出结果溢出精确断点法有利于程序调试7/29/202466例4在一条单流水线处理机上执行下面的程序。每条指令都要经过“取指”,“译码”,“执行”和“写结果”

43、4个流水段。每个流水段的延迟时间都是5ns。在“执行”流水段,LS部件完成LOAD或STORE操作,其它操作都在ALU部件中完成,两个操作部件的输出端有直接数据通路与任一操作部件的输入端相连,ALU部件产生的条件码也能够直接送入控制器。7/29/2024671:SUBR0,R0;R002:LOADR1,#8;向量长度83:LOOP:LOADR2,A;R2A向量的一个元素4:MULR2,R1;R2(R2)*(R1)5:ADDR0,R2;R0(R0)+(R2)6:DJNER1,LOOP;R1(R1)-1若(R1)0则转7:STORER0,S;保存结果(1)采用静态分支预测技术,每次都预测转移不成功

44、。画出指令流水线的时空图。计算流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。(2)采用静态分支预测技术,每次都预测转移成功。计算指令流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。7/29/2024685211211 23223334 54445556666取指写回ALULS译码33334444 5555666633334444 5555666633334444 555566667777.重复8次m(1)解:每次预测转移不成功,流水线时空图如下:7/29/20246911211 23223334 54445556666取指写回ALULS译码333344

45、44 5555666633334444 555566667777.重复8次m(2)解:每次预测转移成功,流水线时空图如下:7/29/2024704.3流水线的调度技术静态调度静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。动态调度动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式两种。7/29/202471一、静态调度技术静态调度静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。非线性流水线中存在着前（反）馈回路，必然会引起功能段的冲突而发生流水线停顿。调度方法会减少停顿时间。

46、调度方案是基于二维预约表和状态图来进行分析7/29/202472非线性流水线的连接图非线性流水线的连接图时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线的预约表非线性流水线的预约表S1S2S3S4输出输入反馈线7/29/202473某流水线结构如下：某流水线结构如下：非线性流水线调度举例非线性流水线调度举例 S1S2S3S4S5入入出出 流水线调度方案如下：流水线调度方案如下：7/29/202474（1）形成预约表）形成预约表指令总拍数指令总拍数为为n，流水线有流水线有k个段，则形成个段，则形成nk的预约表，段的使用情况用的预约表，段的使用情况用“”表示。表示。 预约表如下

47、：预约表如下：543 2198765438271tS7/29/202475（2）由预约表形成禁止表）由预约表形成禁止表FF=各段中冲突间隔拍各段中冲突间隔拍数数 -功能段1的禁止间隔拍数为8；-功能段2的禁止间隔拍数为5和6；-功能段3的无禁止间隔拍数；-功能段4的禁止间隔拍数为1；-功能段5的禁止间隔拍数为1。 F=1 F=1，5 5，6 6，88（3 3）由禁止表）由禁止表F F形成初始冲突向量形成初始冲突向量C C0 0C C0 0 = =（1011000110110001），）， c ci i=1=1冲突，冲突，0 0不冲突。不冲突。 7/29/202476（4 4）由初始冲突向量由初

48、始冲突向量C C0 0形成状态转换图形成状态转换图a.a. 取取C C0 0分别间隔分别间隔2 2、3 3、4 4、7 7拍，且将拍，且将C C0 0分别逻分别逻辑右移辑右移2 2、3 3、4 4、7 7位，高位补位，高位补0 0后再后再与与C C0 0按位按位“或或”，形成新的冲突向量，形成新的冲突向量C C1 1 、C C2 2 和和C C3 3 ；10110001101101111011110110111011初始状态初始状态3427C0C1C2C37/29/202477b. 再再分别取分别取C1间隔间隔2、7拍；取拍；取C2间隔间隔4、7拍；拍；取取C3间隔间隔3、7拍。方法同上，直至

49、全部完拍。方法同上，直至全部完成。成。 注意：注意：向量向量C Ci i右移后，总是与原始向量右移后，总是与原始向量C C0 0作逻辑作逻辑加。加。1011000110110111101111011011101110111111初始状态初始状态34422777C0C1C2C3C4777/29/202478（5 5）根据状态图写出调度方案）根据状态图写出调度方案 每一个每一个闭合回路闭合回路就是一个调度方案（策略）就是一个调度方案（策略）1011000110110111101111011011101110111111初始状态初始状态34422777C0C1C2C3C47737/29/202479

50、本例中调度方案如下：本例中调度方案如下：调度策略平均间隔拍数调度策略平均间隔拍数(2, 7)4.50(4, 3)3.50(2, 2, 7)3.67(4, 3, 7)4.67(3, 4)3.50(4, 7)5.00(3, 7)5.00(7)7.00(3, 4, 7)4.67 平均延时最小的调度方案为最佳平均延时最小的调度方案为最佳调度方案，本例调度方案，本例为（为（3，4）和（）和（4，3）。）。 对非对非C0开始的调度方案由开始的调度方案由流水线控制器流水线控制器完成控制完成控制的过渡。的过渡。7/29/202480调度方案的验证原理：二维预约表方法：给定任务数，使用每一种可能的调度方案进行调

51、度验证：调度过程中有无功能段的冲突？7/29/20248112345678910 11 12 13 1415S1 S2S3S4S5例如，按(3,4)调度方案，连续输入3个任务的调度过程如下：7/29/202482按（4，3）调度方案连续输入6个任务的时空图S1S2S3S4S5mt7/29/202483性能分析性能分析设共输入设共输入8个任务，按最佳调度方案（平均个任务，按最佳调度方案（平均时延最小时延最小3.5拍）（拍）（3，4）进行调度，计算）进行调度，计算流水调度的最大和实际吞吐率流水调度的最大和实际吞吐率7/29/202484例5设有一4段流水线处理机如下图所示。此流水线的总值时间为6个

52、时钟周期,所有相继段必须在每个时钟周期之后才能使用。(1)列出这一流水线的4行6列的预约表;(2)列出禁止表和画出状态图;(3)求出平均延迟最小的调度方案和最大吞吐率。S1S2S3S4输出输入7/29/202485功能段123456S1S2S3S4解法一：4行6列的预约表(一)禁止表的原始冲突向量为：F=4，C=(1000)7/29/20248610001100111011111010100110111101111212333223解法一的状态转移图平均延迟最小的调度方案是：(1,2,3,2)。最小平均延迟是：2t。最大吞吐率是：TPmax=1/2t。7/29/202487功能段123456S

53、1S2S3S4解法二：4行6列的预约表(二)禁止表的原始冲突向量为：F=2,4，C=(1010)7/29/20248810101111101113355解法二的状态转移图平均延迟最小的调度方案是：(3)。最小平均延迟是：3t。最大吞吐率是：TPmax=1/3t。7/29/202489二、动态调度技术动态调度：动态调度：通过硬件重新安排指令的执行顺通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式序以减少流水的停顿。有集中式和分布式优点：（1）能处理某些在编译时无法知道的相关情况（2）能简化编译程序设计（3）使代码有可移植性缺点：相应的硬件较为复杂。7/29/2024901、集中式

54、动态调度静态调度中的指令是按序(In-order)执行，如果一条指令在流水线中发生停顿，后续指令就不再前进了动态调度可使指令按无序(Out-order)方式工作集中式动态调度：依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作7/29/202491EX MEM WB 集中式动态调度集中式动态调度IF ID整数部分整数部分浮点加浮点加浮点乘浮点乘浮点除浮点除RF记录控制器记录控制器指令指令控制控制/状态状态控制控制/状态状态状态记录控制器（记分牌）状态记录控制器（记分牌）记录与控制在流水线的记录与控制在流水线的EXEX段开始。段开始。7/29

55、/202492检测功能：功能部件（资源）冲突；源、目的REG引起的RAW、WAR、WAW相关。控制功能：有冲突或相关的指令推后进入流水线的执行部件，否则正常指令进入流水线的执行部件；记录功能部件、REG、指令的状态；根据记录的状态，控制后续指令的进入。7/29/2024932、分布式动态调度此方法是由Tomasulo于1967年提出来的，已在IBM360/91机中采用。IBM360/91的浮点运算器主要部件：（1）运算部件：一个加法部件和一个乘除部件。（2）保存站：加法部件中有A1A3三个保存站，乘除部件有M1和M2两个保存站，用来保存当前参加运算的数据。7/29/202494（3）指令操作缓

56、冲栈：存放经分析后由指令部件送来的指令，译码后，产生相应的控制信号送到各个部件。（4）浮点操作数寄存器（FLB）：存放由主存预取来的操作数。（5）浮点寄存器（FLR）：存放操作数的寄存器。（6）存储数据缓冲站（SDB）：存放将写入存储器的结果数据，也有站号。（7）公共数据总线（CDB）：以上各部件间的连接总线。7/29/202495浮点操作数缓冲器(FLB)控浮点操作栈(FLOS)忙制位站号源1控制站号 源2站号源1站号源2 控制控制号站存数缓冲器(SDB)加法器乘/除法器译码器站号浮点寄存器(FLR)M1M2A1A2A3101010111100FLB总线FLR总线10001001CDB公共数

57、据总线指令处理部件存储器总线654321站号：01100001F76543F21F0保存站 IBM360/91IBM360/91的浮点运算部件的浮点运算部件结构框图结构框图7/29/202496S1：(FLB1)F0S2： (F0)*(FLB2)F0S3： (F0) AS4： (FLB3)F0S5： (F0)+(FLB4)F0;F0站号置为站号置为0001;F0置忙位为置忙位为1，M1源源1为为0001，源，源2为为0010，F0站号为站号为1000;C1站号置站号置1000;F0站号置为站号置为0011;F0置忙位为置忙位为1，A1源源1为为0011， 源源2为为0100，F0站号为站号为1

58、010调度方法特点调度方法特点：通过FLR的“忙”位，检测RAW相关；通过修改站号（重命名），消除WAR、WAW相关；通过设置保存站，减少资源相关冲突；借助CDB作相关专用通路。7/29/2024974.44.4 先进的流水技术先进的流水技术流水中指令级并行性的进一步开发流水中指令级并行性的进一步开发粗粒度并行性：粗粒度并行性：在多处理机上分别运行多个在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；进程，由多台处理机合作完成一个程序；细粒度并行性：细粒度并行性：指在一个进程中进行操作一指在一个进程中进行操作一级或指令一级的并行处理。级或指令一级的并行处理。RISCRISC机进一步开

59、发细粒度并行性机进一步开发细粒度并行性7/29/202498一、超标量流水处理技术每个时钟周期平均执行指令的条数大于或等于2超标量处理机典型结构：多条指令流水线、多个功能部件先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU,图形加速部件GPU，大量的通用寄存器，两个一级高速Cache超标量处理机的指令级并行度ILP大于17/29/202499超标量流水线处理机的一般结构超标量流水线处理机的一般结构IFIDFA1FA2FA3MD1 MD2 MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWR7/29/2024100整数部件整数部件位操作浮点加乘法部件除法部件

60、图形部件图形部件内部总线读数存数部件通用寄存器堆扩展寄存器堆目标指令指令分配转移部件数据Cache(8KB)指令Cache(8KB)系统总线32位地址总线32位数据总线超标量处理机超标量处理机MC88110MC88110的结构的结构7/29/2024101IFIDFA1 FA2 FA3MD1 MD2 MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWRIFID先行指令窗口注注：先先行行指指令令窗窗口口除除了了能能够够做做数数据据相相关关性性分分析析和和功功能能部部件件冲冲突突的检测之外，还至少有一套取指令部件和一套指令译码部件的检测之外，还至少有一套取指令部件和一套指

61、令译码部件7/29/2024102IF时钟周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR超标量流水处理机的时空图超标量流水处理机的时空图7/29/2024103超标量流水线的调度按序发射：当指令按策划功能序的次序发射时，称之为按序发射（in-orderissue）无序发射：为改善流水线性能，可以将有相关的指令推后发射，而将后面的无相关性的指令提前发射，即不按程序原有次序发射指令，称之为无序发射（out-of-order）按序完成：完成顺序与发射顺

62、序一致无序完成：完成顺序与发射顺序不一致7/29/2024104按序发射按序完成静态调度策略；（Pentium)按序发射无序完成动态调度策略；（PentiumII/III）无序发射无序完成动态调度策略。无论那种调度策略，都要保证程序运行的最终结果是正确的，发射策略由译码控制器完成，完成策略由执行控制器完成。常用的调度方法7/29/2024105IF1ID1L/S WR1IF2ID2部件FA1WR2FA3FA2顺序(RAW)顺序(WAW)顺序顺序(RAW)MD1 MD2 MD3WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2MD1 MD2 MD3I1WR2IF2

63、I2I3I4I5I6指令时钟周期12345678910流水线2流水线1I1：LOADR1，A；主存单元AR1I2：FADDR2，R1；(R1)+(R2)R2I3：FMULR3，R4；(R3)(R4)R3I4：FADDR4，R5；(R4)+(R5)R4I5：DECR6；(R6)-1R6I6：FMULR6，R7；(R6)(R7)R6按序按序发射按序完发射按序完成之调度过程成之调度过程7/29/2024106IF1ID1L/S WR1IF2ID2部件FA1WR2FA3FA2(RAW)(RAW)MD1 MD2 MD3 WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2M

64、D1 MD2 MD3I1WR2IF2I2I3I4I5I6指令时钟周期123456789流水线2流水线1I1：LOADR1，A；主存单元AR1I2：FADDR2，R1；(R1)+(R2)R2I3：FMULR3，R4；(R3)(R4)R3I4：FADDR4，R5；(R4)+(R5)R4I5：DECR6；(R6)-1R6I6：FMULR6，R7；(R6)(R7)R6按序按序发射无序完发射无序完成之调度过程成之调度过程7/29/2024107IF1ID1L/S WR1IF2ID2FA1WR2FA3FA2MD1 MD2 MD3WR1IF1ID1FA2FA3FA1ID3IF3WR2ID2ALIF2WR1I

65、D2MD2 MD3MD1I1WR2IF2I3I4I2I5I6指令时钟周期12345678流水线2流水线1I1：LOADR1，A；主存单元AR1I2：FADDR2，R1；(R1)+(R2)R2I3：FMULR3，R4；(R3)(R4)R3I4：FADDR4，R5；(R4)+(R5)R4I5：DECR6；(R6)-1R6I6：FMULR6，R7；(R6)(R7)R6无序发射无序完无序发射无序完成之调度过程成之调度过程先行控制7/29/2024108超标量流水线的资源冲突在先进的超标量流水机中，有多个操作（执行）部件，如：ALU、FADD、FMUL、GPU、LSU等操作部件必须采用流水结构，可减少资

66、源冲突7/29/2024109I1：FADDR0，R1；(R0)+(R1)R0I2：FMULR2，R3；(R2)(R3)R2I3：FADDR4，R5；(R4)+(R5)R4I4：FMULR6，R7；(R6)(R7)R6IF1IF2ID1ID2FADDIF1ID1IF2ID2WR1FMULWR2FADDFMULWR1WR2I1I2I3I41234567891011双流水线超标量处理机（操作部件非流水结构）7/29/2024110I1：FADDR0，R1；(R0)+(R1)R0I2：FMULR2，R3；(R2)(R3)R2I3：FADDR4，R5；(R4)+(R5)R4I4：FMULR6，R7；(

67、R6)(R7)R6IF1IF2ID1ID2FA1IF1ID1IF2ID2WR1FM1WR2WR1I1I2I3I412345678t双流水线超标量处理机（操作部件流水结构）FA2FA3FM2 FM3 FM4FA1FA2FA3FM1WR2FM2 FM3 FM47/29/2024111二、超流水线处理机两种定义：两种定义： 一个周期内能够分时发射多条指令的处理机称为超流水线处理机。 指令流水线有8个或更多功能段的流水线处理机称为超流水线处理机。提高处理机性能的不同方法：提高处理机性能的不同方法： 超标量处理机是通过增加硬件资源为代价来换取处理机性能的。 超流水线处理机则通过各硬件部件充分重叠工作来提

68、高处理机性能。两种不同并行性：两种不同并行性： 超标量处理机采用的是空间并行性 超流水线处理机采用的是时间并行性7/29/2024112指令执行时序指令执行时序每隔每隔1/n1/n个时钟周期发射一条指令，流水线周期个时钟周期发射一条指令，流水线周期为为1/n1/n个时钟周期个时钟周期在超标量处理机中，流水线的有些功能段还可在超标量处理机中，流水线的有些功能段还可以进一步细分，例如：以进一步细分，例如：IDID功能段可以再细分为功能段可以再细分为译码、读第一操作数和读第二操作数三个流水译码、读第一操作数和读第二操作数三个流水段。也有些功能段不能再细分，段。也有些功能段不能再细分，如如WRWR功能

69、段一功能段一般不再细分。因此有超流水线的另外一种定义：般不再细分。因此有超流水线的另外一种定义：有有8 8个或个或8 8个以上流水段的处理机称为超流水线个以上流水段的处理机称为超流水线处理机处理机7/29/2024113IF时钟周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每个时钟周期分时发送每个时钟周期分时发送3 3条指令的超流水线条指令的超流水线7/29/2024114MIPS R4000MIPS R4000处理机的流水线操作处理机的流水线操

70、作指令CacheIFIF：取第一条指令取第一条指令ISIS：取第二条指令取第二条指令RFRF：读寄存器堆，指令译码读寄存器堆，指令译码EXEX：执行指令执行指令DFDF：取第一个数据取第一个数据DSDS：取第二个数据取第二个数据TCTC：数据标志校验；数据标志校验；WBWB：写回结果写回结果指令译码读寄存器堆ALU数据Cache标志检验寄存器堆IFISRFEXDFDSWBTC7/29/2024115IF流水线周期当前CPU周期IS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC W

71、BIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WBIFIS RF EX DF DS TC WB主时钟周期MIPS R4000MIPS R4000正常指令流水线工作时序正常指令流水线工作时序7/29/2024116三、超标量超流水线处理机把超标量与超流水线技术结合在一起，就成为超标量超流水线处理机指令执行时序指令执行时序 超标量超流水线处理机在一个时钟周期内分时发射指令n次，每次同时发射指令m条，每个时钟周期总共发射指令m n条。7/29/2024117IF时钟周期指令I1I2I3IDEXWR12345I4I5I

72、6I7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRI10I11I12每时钟周期发射每时钟周期发射3 3次次, ,每次每次3 3条指令条指令7/29/2024118不同结构计算机的性能分析标量处理机的并行度(1,1)超标量处理机的并行度(m,1)超流水处理机的并行度(1,n)超标量超流水处理机的并行度(m,n)7/29/2024119标量流水处理机上执行N条指令的时间：超标量流水处理机上执行N条指令的时间：7/29/2024120超流水处理机上执行N条指令的

73、时间：超标量超流水处理机上执行N条指令的时间：7/29/2024121四、超长指令字(VLIW)计算机VLIW是以一条长指令实现多个操作的并行执行，减少存储器访问。主要特点：主要特点：（1）单一的控制流。只有一个控制器，每个周期启动一条指令。（2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。（3）在编译阶段完成超长指令中多个可并行执行操作的调度。7/29/2024122 超长指令字计算机举例如完成以下运算：C=A+B、K=I+J、L=M-K、Q=CK需以下13条指令完成：（需花14个T）LOADA、LOADB、C=A+B、STOREC、LOADI、LOADJ、K=I+J、

74、STOREK、LOADM、L=M-K、STOREL、Q=CK、STOREQ7/29/2024123主存RF(寄存器堆)LD/ST2FADDFMULLD/ST1LD/ST1LD/ST2FADDFMUL存/取1存/取2浮点加浮点乘操作并行度操作并行度4 4LOADALOADBLOADILOADJC=A+BLOADMSTORECK=I+JSTOREKL=M-KQ=CKSTORELSTOREQ用VLIW则只需6个T7/29/2024124例6 在下列不同结构的处理机上运行88的矩阵乘法C=AB，计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间

75、。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns，C的初始值为“0”。各操作部件的输出端有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。7/29/2024125（1）处理机内只有一个通用操作部件，采用顺序方式执行指令。解：需要完成的乘法次数为888=512次需要完成的加法次数为887=448次执行完成总时间为：7/29/2024126（2）单流水线标量处理机，有一条两个功能的静态流水线，流水线每个功能段的延迟时间均为一个时钟周期，加法操作和乘法操作各经过3个功能

76、段。解：IFIDAD1AD2AD3MU1MU3MU27/29/2024127（3）单流水线标量处理机，处理机内有两条独立的操作流水线，流水线每个功能段的延迟时间均为一个时钟周期。解：IFIDAD1AD2AD3MU1MU3MU27/29/2024128（4）超标量处理机，每个时钟周期同时发送一条乘法指令和一条加法指令，处理要内有两条独立的操作流水线，流水线的每个功能段的延迟时间均为一个时钟周期。（不考虑数据之间的相关性，下同。）解：7/29/2024129（5）超流水处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件的延迟时间都为6个流水级，每个时钟周期能够分时发射两条指令，即每个流水级能

77、够发射一条指令。IFIDAD1AD2AD3MU1MU3MU2解：123456789107/29/2024130（6）超标量超流水线处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件延迟时间都为6个流水级，每个流水级能够同时发射一条乘法指令和一条加法指令。解：7/29/20241314.6向量流水技术向量流水的基本原理CRAY-1型向量处理机增强向量处理性能的方法7/29/20241324.6.14.6.1 向量流水的基本原理向量流水的基本原理提高流水性能方法：提高流水性能方法：增加流水线段数，以减少增加流水线段数，以减少t；每个时钟同时启动多条指令；每个时钟同时启动多条指令；减少相关，减

78、少功能变换次数，增加处理指令条数。减少相关，减少功能变换次数，增加处理指令条数。向量操作特点向量操作特点1.向量元素间操作相互向量元素间操作相互独立独立，且为相同操作。，且为相同操作。2.相当于标量循环，对指令带宽的访问要求不高。相当于标量循环，对指令带宽的访问要求不高。3.可采用多体交叉存储器，减少访存延迟。可采用多体交叉存储器，减少访存延迟。向量操作很适合于流水处理或并行处理。向量操作很适合于流水处理或并行处理。7/29/2024133例如：Y=a*X+YX、Y为向量，长度为64；a为标量LDF0，aADDIR4,RX,#512；由X向量的末址地装入R4LOOP:LDF2,0(RX)；取向

79、量元素X(i)MULDF2,F0,F2；X向量与标量乘LDF4,0(RY)；取向量元素Y(i)ADDDF4,F2,F4SD0(RY),F4；存结果向量ADDIRX,RX,#8ADDIRY,RY,#8；地址增量SUBR20,R4,RX；R4-RXR20JNZR20,LOOP；判是否为07/29/2024134如果用向量处理机来完成同样的操作LDF0，aLDVV1,RX；装入向量XMULVV2,F0,V1；X向量与标量乘LDVV3,RY；取向量元素YADDVV4,V2,V3SDVRY,V4；存结果向量特点：1、执行指令6条（标量执行8*64+2=514条）。降低了存储器对取指带宽的要求。2、标量运

80、算过程中存在的数据相关性，在向量运算过程中已基本消除（共2次）。7/29/2024135一、向理处理的方式有三种处理方式：1横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。2纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。3纵横处理方式，又称为分组处理方式，纵横向加工方式等。横向处理和纵向处理相结合的方式。7/29/2024136向量处理方式向量处理方式以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。for (i = 1for (i = 1；i = ni = n；i+)i+)yi = ai

81、yi = ai ( bi + ci );( bi + ci );7/29/20241371、横向处理方式 逐个分量进行处理：设k中间变量第1个分量：kB1C1,Y1 A1k;第2个分量：kB2C2,Y2 A2k; 第n个分量：kBNCN,YNANk.存在两个问题：在计算向量的每个分量时，都发生先写后读的数据相关。流水线性能降低如果采用多功能流水线，必须频繁进行流水线切换横向处理方式对向量处理机不适合即使在标量处理机中，也经常通过编译器进行指令流调度。7/29/20241382、纵向处理 也称为垂直处理方式，纵向加工方式等T1 = B1 + C1T2 = B2 + C2Tn = Bn + CnY

82、1 = A1T1Y2 = A2T2YN = AN TN采用向量指令只需要2条：ADDV T, B, CMULV Y, A, T这种处理方式适用于向量处理机，数据相关不影响流水线连续工作。不同的运算操作只需要切换1次。7/29/20241393、纵横向处理方式 将长度为n的向量分成若干组，每组长度为N，组内按纵向方式处理，依次处理各组，组间是横向处理方式。用于寄存器-寄存器结构的向量处理机中向量寄存器的长度是有限的，例如，每个向量寄存器有64个寄存器。向量长度N=64时，需要分组处理。分组方法：nN，其中：为余数，共分组。组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式。7/

83、29/2024140二、向量处理机的分类向量处理机的基本思想是把两个向量的对应分量进行运算，产生一个结果向量。最关键问题是存储器系统能够满足运算部件带宽的要求。主要采用两种方法：1. 存储器存储器结构多个独立的存储器模块并行工作处理机结构简单，对存储系统的访问速度要求很高2. 寄存器寄存器结构运算通过向量寄存器进行需要大量高速寄存器，对存储系统访问速度的要求降低7/29/20241411、存储器存储器结构下图说明一个具有8个存储体的向量处理机： MMMMMMMM流水结构加法器ABC=A+B三条互相独立的数据通路，三条互相独立的数据通路，可并行工作，同一个存储模可并行工作，同一个存储模块同时只能

84、为一个通路服务块同时只能为一个通路服务7/29/2024142 参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子C=A+B存储器存储器ABC流水线运算部件流水线运算部件(4)一种能实现两个向量相加的流水结构的加法器7/29/2024143功能部件功能部件4功能部件功能部件3功能部件功能部件2功能部件功能部件1存储体存储体M8存储体存储体M7存储体存储体M6存储体存储体M5存储体存储体M4存储体存储体M3存储体存储体M2存储体存储体M1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t 1 2 3 4 5

85、 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8RB6 RB6 RA8 RA8 WD4 WD4RB5 RB5 RA7 RA7 WD3 WD3RB4 RB4 RA6 RA6 WD2 WD2RB3 RB3 RA5 RA5 WD1 WD1RB2 RB2 RA4 RA4 RB1 RB1 RA3 RA3 RA2 RA2 RA1 RA1 WD8 WD8WD7 WD7WD6 WD6WD5 WD5RB8 RB8RB7 RB7C=A+B向量处理时序图向量处理时序图7/29/20241442、寄存器-寄存器结构向量寄存器与标量寄存器的主要差别是：一个向量寄存器

86、能够保存一个向量，例如：64个64位寄存器。连续访问一个向量的各个分量。需要有标量寄存器和地址寄存器等。采用寄存器-寄存器结构的主要优点：降低主存储器的流量。例如：采用寄存器-寄存器结构的CRAY-1与采用存储器-存储器结构的STAR-100比较，运算速度高3倍多，而主存流量低2.5倍。STAR-100的主存储器流量：328W/1.28us=200MW/SCRAY-1的主存储器流量： 4W/50ns=80MW/S7/29/20241454.6.2 CRAY-1型向量流水处理机CRAY-1型向量流水处理机的结构CRAY-1型向量流水处理机的四类指令7/29/2024146一、CRAY-1型机的结

87、构1976年由美国CRAY公司生产V0-V7共8个向量寄存器，每个寄存器由64个64bit构成；8个64bit的标量寄存器S0-S7；8个24bit的地址寄存器A0-A7；64个24bit的中间寄存器B、 64个64bit的中间寄存器T；VM和VL4组功能运算部件7/29/2024147A0-A7S0-S7V0-V7VLVMBT主主存存储储器器向量运算加加(3)浮点向量运算浮浮加加(6)标量运算标加标加(3)地址运算加加(3)CRAY-1型向理处理机7/29/2024148二、向量处理机的四类指令 标量类指令和向量类指令共128条，其中4种向量指令如下图所示：n4321VjVkVin4321S

88、jVkVi第一类向量指令第一类向量指令第二类向量指令第二类向量指令7/29/2024149MLDV第三类向量指令MSTV第四类向量指令7/29/20241504.6.3增强向量处理性能方法多功能部件的并行执行链接技术条件语句和稀疏矩阵的加速处理向量归约操作的加速处理7/29/2024151一、多功能部件的并行执行由于向量处理机处理每个功能部件，与每个向量寄存器Vi之间有总线互连。每个运算部件是流水操作，故其操作可重叠（并行）并行操作条件：并行操作条件：(1)(1)不存在向量寄存器使用冲突不存在向量寄存器使用冲突 不允许出现不允许出现RAWRAW、WARWAR、WAWWAW、RARRAR相关。相

89、关。 如：如：V4V1+V4V1+V2V2 V5 V5V2V2V3V3(2)(2)不存在功能部件使用冲突不存在功能部件使用冲突 每种功能部件一般只设置一个。每种功能部件一般只设置一个。 如：如：V3V1V3V1V2V2 V6V4 V6V4V5V57/29/2024152二、链接技术利用向量寄存器之间先写后读的数据相关性，加快向量运算的技术链接技术采用了“相关专用通道”思想，实现向量流水之间的“链接”例如：有如下3条浮点向量指令： V3 A V2 V0V1 V4 V2V37/29/20241533条向量指令的执行示意图如下：MALDVV3I1：V3A116V2V1V0ADDVI2：V2V0V11

90、116V4V3V2MULVI3：V4V2V311177/29/2024154若若三三条条指指令令串串行行执执行行，即即每每次次只只有有前前条条指指令令结结束束，才才执执行行后后继指令，那么三条指令执行的总时间为：继指令，那么三条指令执行的总时间为： T1=(1+6+1)+N-1+(1+6+1)+N-1+(1+7+1)+N-1=3N+22(拍拍)若第一、二条指令并行与第三条串行：若第一、二条指令并行与第三条串行： T2=(1+6+1)+N-1+(1+7+1)+N-1=2N+15(拍拍)若第一，二条指令并行与第三条链接：若第一，二条指令并行与第三条链接： T3=(1+6+1)+(1+7+1)+(N

91、-1)=N+16(拍拍)可以看出采用并行与链接后，可以很有效的改善性能。可以看出采用并行与链接后，可以很有效的改善性能。 如果每一个时钟周期的延迟称为1拍，在Cray-1机中LD指令需6拍，浮点加6拍，浮点乘7拍，向量寄存器的存与取的传送各为1拍，内存的传送为1拍。7/29/20241551234561234561234567DBC存储器V4V3V2A访访存存V1V0浮浮点点加加浮浮点点乘乘访存与浮点加并行，访存与浮点加并行，再与浮点乘链接再与浮点乘链接LD V3，AADDV V2，V0，V1MULTV V4，V2，V3并行和链接操作图并行和链接操作图7/29/2024156实现链接的条件：实

92、现链接的条件：(1) 没有向量寄存器冲突(RAM,WAR,WAW,RAR)和运算部件(同一功能)冲突。(2) 只有第一个结果送入向量寄存器的那一个周期可以链接。(3) 先行的两条指令产生运算结果的时间必须相等。(4)共用向量寄存器中向量长度、起始地址、偏移量、步长均相等。7/29/2024157三、条件语句和稀疏矩阵的加速Do100I=1,64If(A(i)NE0)ThenA(i)=A(i)-B(i)Endif100continue通过对A向量的测试后，形成一屏蔽向量。A(i)元素为0时，屏蔽向量中对应位置“0”7/29/2024158LDVV1,RA；装入向量A到V1LDVV2,RBLDF0

93、,#0；装入浮点0SENSVF0,V1；若V1(i)NEF0中相应位,将VMi置1SUBVV1,V1,V2；在屏蔽向量控制下进行减法操作CVM；屏蔽向量置为全1STVRA,V1注：SENSV为屏蔽向量生成指令稀疏矩阵也可采取类似的方法来实现向量化7/29/2024159四、向量归约操作的加速归约(Reduction)操作难于向量化，因为它是递推(Recurrence)操作的一个特例，归约的结果将得到一个标量值。Dot = 0.0Do 10 I=1,6410 dot=dot+A(i)*B(i) 此循环存在着迭代层间此循环存在着迭代层间的数据相关，无法直接的数据相关，无法直接向量化向量化可将此循环

94、分成可向量化部分和递推部分7/29/2024160Do 10 I=1,6410 dot(i)=A(i)*B(i)Dot1=0.0Do 20 I=1,6420 dot1=dot1+dot(i)第一部分循环可向量化，第二部分仍需递推。第二部分可采用递推折叠法(Recursivedoubling)，使叠加向量长度缩短的方法完成求和。7/29/2024161典型例题和部分习题解答典型例题和部分习题解答 5.15.1 设设一一条条指指令令的的执执行行过过程程分分为为“取取指指令令”、“分分析析”和和“执执行行”三三段段，每每一一段段的的执执行行时时间间分分别别为为tt、2t2t和和3t3t。在在下下列列

95、各各种种情情况况下下，分分别别写写出出连连续续执执行行n n条条指指令令所所需需要要的的时间表达式。时间表达式。（1 1）顺序执行方式。）顺序执行方式。（2 2）仅）仅“取指令取指令”和和“执行执行”重叠。重叠。（3 3）“取指令取指令”、“分析分析”和和“执行执行”重叠重叠（4)4)先行控制方式先行控制方式7/29/2024162解答：解答：（1 1）顺序执行需要的时间如下：）顺序执行需要的时间如下：（2 2）取指令和执行重叠，即一次重叠执行方式，我们假设第）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1n+1条指条指令的取指令和第令的取指令和第n n条指令的执行同时结束，那么所需要

96、的时间为：条指令的执行同时结束，那么所需要的时间为：（3 3）取指令、分析和执行重叠）取指令、分析和执行重叠(4)(4)先行控制方式先行控制方式7/29/20241635.2 5.2 一一条条线线性性流流水水线线有有4 4个个功功能能段段组组成成，每每个个功功能能段段的的延延迟迟时时间间都都相相等等，都都为为tt。开开始始5 5个个tt，每每间间隔隔一一个个tt向向流流水水线线输输入入一一个个任任务务，然然后后停停顿顿2 2个个tt，如如此此重重复复。求求流流水水线线的的实实际吞吐率、加速比和效率。际吞吐率、加速比和效率。解答流水线的时空图如下：7/29/2024164我我们们可可以以看看出出

97、，在在（11n+111n+1）tt的的时时间间内内，可可以以输输出出5n5n个个结结果果，如如果果指指令令的的序序列列足足够够长长（nn），并并且且指指令令间间不不存存在相关，那么，吞吐率可以认为满足：在相关，那么，吞吐率可以认为满足：加速比为：加速比为：从上面的时空图很容易看出，效率为：从上面的时空图很容易看出，效率为：7/29/20241655.3 5.3 用一条用一条5 5个功能段的浮点加法器流水线计算个功能段的浮点加法器流水线计算 每每个个功功能能段段的的延延迟迟时时间间均均相相等等，流流水水线线的的输输出出端端和和输输入入端端之之间间有有直直接接数数据据通通路路，而而且且设设置置有有

98、足足够够的的缓缓冲冲寄寄存存器器。要要求求用用尽尽可可能能短短的的时时间间完完成成计计算算，画画出出流流水水线线时时空空图图，并并计计算算流流水水线线的的实实际吞吐率、加速比和效率。际吞吐率、加速比和效率。 解解答答 首首先先需需要要考考虑虑的的是是，1010个个数数的的的的和和最最少少需需要要做做几几次次加加法法。我我们们可可以以发发现现，加加法法的的次次数数是是不不能能减减少少的的：9 9次次；于于是是我我们们要要尽尽可可能能快快的的完完成成任任务务，就就只只有有考考虑虑如如何何让让流流水水线线尽尽可可能能充满，这这需需要要消消除除前前后后指指令令之之间间的的相相关关。由由于于加加法法满满

99、足足交交换换率率和和结结合合率率，我我们们可可以以调调整整运运算算次次序序如如以以下下的的指指令令序序列列，我我们们把把中中间间结结果果寄寄存存器器称称为为R R，源源操操作作数数寄寄存存器器称称为为A A，最最后后结结果果寄寄存存器器称称为为F F，并并假设源操作数已经在寄存器中，则指令如下：假设源操作数已经在寄存器中，则指令如下：7/29/2024166I1：R1A1+A2I2：R2A3+A4I3：R3A5+A6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6I9：FR7+R8这并不是唯一可能的计算方法。假设功能段的延迟这并不是唯一可能

100、的计算方法。假设功能段的延迟为为tt。时空图如下，图中的数字是指令号。时空图如下，图中的数字是指令号。7/29/202416732141111222233334444555556666677777888889999921t部件m15432R1=A1+A2R2=A3+A4R3=A5+A6R4=A7+A8R5=A9+A10R6=R1+R2R7=R3+R4R8=R5+R6F=R7+R8R1R3R5R6R7R8FR2R47/29/2024168整个计算过程需要整个计算过程需要21t21t，所以吞吐率为：所以吞吐率为：加速比为：加速比为：效率为：效率为：7/29/2024169 5.45.4 流水线由流

101、水线由4 4个功能部件组成，每个功能部件个功能部件组成，每个功能部件的延迟时间为的延迟时间为t t。当输入当输入1010个数据后，间歇个数据后，间歇5t 5t ，又输入又输入1010个数据，如此周期性地工作，个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。求此时流水线的吞吐率，并画出其时空图。 分析分析 所谓输入所谓输入1010个数据后，间歇个数据后，间歇5t5t，又又输入输入1010个数据的含义应当是以输入时间为基准，个数据的含义应当是以输入时间为基准，即从第即从第1010个数据输入时算起，隔个数据输入时算起，隔5t5t后又开始后又开始输入新的一轮数据。输入新的一轮数据。7/

102、29/20241701 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 21时间(t)部件5t 解答解答 按题意可得按题意可得4 4个功能部件流水时的时空关系如下图所示个功能部件流水时的时空关系如下图所示所以，按周期性工作时的流水线平均吞吐率为所以，按周期性工作时的流水线平均吞吐率为T Tp p=10/(14t)=5/(7t)=10/(14t)=5/(7t)01234567891011121314151643217/29/2024171 5.55.5 有一个浮点乘流水线如下有一个浮点

103、乘流水线如下图图(a)(a)所示，其乘积可所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实直接返回输入端或暂存于相应缓冲寄存器中，画出实现现A*B*C*DA*B*C*D的时空图以及输入端的变化，并求出该流水的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图线的吞吐率和效率；当流水线改为下图(b)(b)形式实现同形式实现同一计算时，求该流水线的效率及吞吐率。一计算时，求该流水线的效率及吞吐率。阶加尾乘规格化t3tt积操作数图(a)阶加尾乘1尾乘2尾乘3规格化积t3tt3t3t图(b)7/29/2024172 分析分析 为了减少运算过程中的操作数相关，为了减少运算

104、过程中的操作数相关，A*B*C*DA*B*C*D应改为采用应改为采用(A*B)*(C*D) (A*B)*(C*D) 的算法步骤进行运算。的算法步骤进行运算。 解答解答 按图按图(a)(a)组织，实现组织，实现A*B*C*DA*B*C*D的时空关系如下图的时空关系如下图(A)(A)所示。所示。时间部件输入输出ABCDA*BC*DA*BC*DA*B*C*D13规格化尾乘阶加图(A)吞吐率吞吐率TP=3/(13t)TP=3/(13t)效率效率E=(3E=(35t)/(35t)/(313t)=5/13=38.5%13t)=5/13=38.5%7/29/2024173时间部件输入输出ABCDA*BC*D

105、A*BC*DA*B*C*D规格化尾乘3尾乘2尾乘1阶加图(B)11流水线按图流水线按图(b)(b)组织时，实现组织时，实现A*B*C*DA*B*C*D的时空关系如图的时空关系如图(B)(B)吞吐率吞吐率TP=3/(11t)TP=3/(11t)效率效率E =(3E =(35t)/(55t)/(511t)=3/11=27.3%11t)=3/11=27.3%7/29/20241745.65.6 一一条条线线性性静静态态多多功功能能流流水水线线由由6 6个个功功能能段段组组成成，加加法法操操作作使使用用其其中中的的1 1、2 2、3 3、6 6功功能能段段，乘乘法法操操作作使使用用其其中中的的1 1、

106、4 4、5 5、6 6功功能能段段，每每个个功功能能段段的的延延迟迟时时间间均均相相等等。流流水水线线的的输输入入端端与与输输出出端端之之间间有有直直接接数数据据通通路路，而而且且设设置置有有足足够够的的缓缓冲冲寄存器。现在用这条流水线计算：寄存器。现在用这条流水线计算：画画出出流流水水线线时时空空图图，并并计计算算流流水水线线的的实实际际吞吞吐吐率率、加加速速比比和和效率。效率。7/29/2024175解解答答：为为了了取取得得较较高高的的速速度度，我我们们需需要要一一次次将将乘乘法法作作完完，设设源源操操作作数数存存放放在在寄寄存存器器A A、B B中中，中中间间结结果果存存放放在在寄寄存

107、存器器R R中中，最最后后结果存放在寄存器结果存放在寄存器F F中，则执行的指令序列如下所示：中，则执行的指令序列如下所示：I1I1：R1A1*B1R1A1*B1I2I2：R2A2*B2R2A2*B2I3I3：R3A3*B3R3A3*B3I4I4：R4A4*B4R4A4*B4I5I5：R5A5*B5R5A5*B5I6I6：R6A6*B6R6A6*B6I7I7：R7R1+R2R7R1+R2I8I8：R8R3+R4R8R3+R4I9I9：R9R5+R6R9R5+R6I10I10：R10R7+R8R10R7+R8I11I11：FR9+R10FR9+R10这并不是唯一可能的计算方这并不是唯一可能的计算

108、方法。假设功能段的延迟为法。假设功能段的延迟为tt。时空图（不完全）如时空图（不完全）如下，图中的数字是指令号。下，图中的数字是指令号。7/29/20241761 222t部件m15432R1R10R6R7R8F6111332223 434445 6555 6667 87778889R1=A1*B1R2=A2*B2R3=A3*B3R4=A4*B4R5=A5*B5R6=A6*B6R7=R1+R2R8=R3+R4F=R9+R10R9=R5+R6R10=R7+R89991010111010111111乘法加法7/29/2024177整个计算过程需要整个计算过程需要22t22t，所以吞吐率为：所以吞吐

109、率为：加速比为：加速比为：效率为：效率为：7/29/20241785.75.7 有一个双输入端的加有一个双输入端的加- -乘双功能静态流水线，乘双功能静态流水线，由经过时间由经过时间为为t t、2t2t、2t2t、t t的的1 1、2 2、3 3、4 4四个子过程构成。加法按四个子过程构成。加法按124124连接，乘法按连接，乘法按134134连接，流水线输出设有数据缓冲器，也可连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行将数据直接返回输入。现要执行A*(B+C*(D+E*F)+G*HA*(B+C*(D+E*F)+G*H 的运算，请调整计算顺序，画出能获得吞吐率尽量的运算，

110、请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间流水线的情况，求出完成全部运算的时间及此期间流水线的效率效率。7/29/2024179 解答解答 根据题意，对算法经调整后，能使流水吞根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如下图所示。图中已标吐率尽量高的流水时空图如下图所示。图中已标出了流水线入、出端的数据变化情况。出了流水线入、出端的数据变化情况。 分析分析 因为是加因为是加- -乘双功能静态流水线，为了能有高的吞吐率，乘双功能静态流水线，为了能有高的吞吐率，应减

111、少流水线的功能切换次数。因此，宜将算法调整成先一连应减少流水线的功能切换次数。因此，宜将算法调整成先一连串的乘，然后再切换成一连串的加。这样，将计算式展开成串的乘，然后再切换成一连串的加。这样，将计算式展开成 A*BA*BA*C*DA*C*DA*C*E*FA*C*E*FG*H.G*H.对于该表达式的计算，自然应先对于该表达式的计算，自然应先进行乘法流水。为了减少因先写后读相关而等待的时间，应尽进行乘法流水。为了减少因先写后读相关而等待的时间，应尽量安排对计算式子项数最多的乘法先进行操作。此外，由于流量安排对计算式子项数最多的乘法先进行操作。此外，由于流水线中瓶颈子过程为水线中瓶颈子过程为2t

112、2t ，所以，流水输入端最快也只能每所以，流水输入端最快也只能每隔隔2t2t输入一组数据。输入一组数据。7/29/2024180根据上图的流水时空图，可以看出，完成全部运算的时间根据上图的流水时空图，可以看出，完成全部运算的时间为为24t24t。在此期间的流水线效率为在此期间的流水线效率为E=(6E=(64t+34t+34t)/(24t4t)/(24t4)=3/8=37.5%4)=3/8=37.5%4321子过程输入输出ACEFACACDEFACEFACDABACEFGHAB GHABACDACEFGHAB+ACDACEF+GHACEF+GHAB+ACD最终结果24时间乘法加法7/29/202

113、4181 5.8 5.8 在一个在一个4 4段的流水线处理机上需段的流水线处理机上需经经7 7拍才能完成拍才能完成一个任务，其预约表如下表所示。分别写出延迟禁一个任务，其预约表如下表所示。分别写出延迟禁止表止表F F、冲突向量冲突向量C C；画出流水线状态转移图；求出画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此流水调度方案，输入最佳方案。按此流水调度方案，输入6 6个任务，求实个任务，求实际的吞吐率。际的吞吐率。1234567S1S2S3S47/29/2024182 分析分析 二维的预约表其实就是一个任务在流二

114、维的预约表其实就是一个任务在流水时的时空图。在求出最佳调度方案后，要水时的时空图。在求出最佳调度方案后，要按流水调度方案输入按流水调度方案输入6 6个任务时，只需按调度个任务时，只需按调度间隔时间点调度即可。要注意，间隔大于等间隔时间点调度即可。要注意，间隔大于等于任务流经流水线最大拍于任务流经流水线最大拍数数N N（本例本例N=7N=7）时，时，调入任务也不会发生冲突。在调度方案中计调入任务也不会发生冲突。在调度方案中计算出的最小平均延迟有多个时，应取其首项算出的最小平均延迟有多个时，应取其首项延迟小的。如首项延迟最小的相同，则取次延迟小的。如首项延迟最小的相同，则取次项延迟小的，依次类推。

115、这样，当按调度方项延迟小的，依次类推。这样，当按调度方案调入的任务数是调度意义周期性的任务数案调入的任务数是调度意义周期性的任务数的整数倍时，可使实际的吞吐率更高些。的整数倍时，可使实际的吞吐率更高些。7/29/2024183解答延迟禁止表F=2,4,6初始冲突向量C=(101010)7/29/2024184101010111111101011101111初始状态7717357535状态转移图状态转移图状态转移图如下图所示。状态转移图如下图所示。7/29/2024185调度方案平均延迟(拍)(1,7)4(3,5)4(5,3)4(5)5(3,7)5(5,3,7)5(5,7)6(7)7各种调度方案

116、及其相应的平均延迟如表所示。各种调度方案及其相应的平均延迟如表所示。7/29/2024186由上表可知，最小平均延迟为由上表可知，最小平均延迟为4 4拍。此时流水线的最大吞吐率拍。此时流水线的最大吞吐率TPTPmaxmax=1/4(=1/4(任务任务/ /拍拍) )最佳调度方案宜选其中按最佳调度方案宜选其中按(l,7)(l,7)周期性地调度的方案。周期性地调度的方案。按按(l,7)(l,7)调度方案输入调度方案输入6 6个任务，全部完成的时间为个任务，全部完成的时间为 1 17 71 17 71 17=247=24（拍）（拍）实际吞吐率实际吞吐率TP=6/24(TP=6/24(任务任务/ /拍

117、拍) )若按若按(3,5)(3,5)调度方案输入调度方案输入6 6个任务，全部完成的时间为个任务，全部完成的时间为 3 35 53 35 53 37=267=26（拍）（拍）实际吞吐率实际吞吐率TP=6/26(TP=6/26(任务任务/ /拍拍) )若按若按(5,3)(5,3)调度方案输入调度方案输入6 6个任务，全部完成的时间为个任务，全部完成的时间为 5 53 35 53 35 57=287=28（拍）（拍）实际吞吐率实际吞吐率TP=6/28(TP=6/28(任务任务/ /拍拍) )可见最佳的方案应当为（可见最佳的方案应当为（1 1，7 7）调度方案，输入）调度方案，输入6 6个任务的实个任务的实际吞吐率较之其它方案的要更高些。际吞吐率较之其它方案的要更高些。时间171717结果7/29/2024187本章重点回顾标量流水的性能分析（吞吐率，效率和加速比）、非线性流水的调度（根据二维预约表求出最佳调度方案）、向量流水中指令组执行时间的分析7/29/2024188作业：作业：4 4、8 8、1111、17177/29/2024189