计算机系统结构第3章流水线技术.ppt

《计算机系统结构第3章流水线技术.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构第3章流水线技术.ppt（127页珍藏版）》请在三一办公上搜索。

1、1,第三章 流水线技术,3.1流水线的基本概念3.2流水线的时空图及性能分析3.3流水线的相关3.4MIPS R4000流水线计算机 3.5向量处理机,2,3.1 流水线的基本概念,一指令的重叠执行1.一条指令执行的几个过程段 1）取指令：根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）译码分析：译出指令的操作性质，准备好所需数据 3）执行：将准备好的数按译出性质进行处理，主要涉及ALU（算术逻辑运算部件）,有关基本概念,3,2.对指令执行的几种方式 1）顺序执行(传统机采用)只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令,取,译,执,取,译,执,i,条,

2、i,+1,条,4,2)仅两条指令重叠：第i条指令的执行与第i+1条的取指重叠。3)三条指令重叠：第i条指令的执行与第i+1条的译码及第i+2条的取指重叠。,5,若一条指令的过程段划分更多时，重叠组合方式更多。重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。3.重叠方式中所需时间表达式及所需时间计算 1）条件：设一条指令分为三个过程段，各过程段分别用t取、t译、t执表示。执行n条指令，分别采用顺序执行、两条重叠、三条重叠。,2）分别列出上述三种执行方式所需时间表达式顺序执行 n*（t取+t译+t执）两条重叠 t取+n*t译+(n-1)*max(t取,t执)+t执三条重叠 t取+max(

3、t译,t取)+(n-2)*max（t取,t译,t执）+max(t执,t译)+t执,6,3)例子 当n=200，t取=3t，t译=4t，t执=5t，时，分别计算上述三种执行方式的时间。顺序执行：200(3+4+5)=2400t 两条重叠：3+2004+(200-1)5+5=1803t 三条重叠：3+4+(200-2)5+5+5=1007t,7,重叠方式需要解决的问题1）对存储器的频繁访问 有哪些访问：取指令、取操作数、存放执行结果,I/O通道访问.希望存储器为多体结构，以适应多种访问源的需要。当存储器为单体结构时，需要将访问源排队，先后顺序为：取指令、取数据、I/O通道访问、存结果,2）应具有先

4、行控制部件 先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。,8,2）先行控制部件的主要内容）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址以及先行操作数地址；）先行操作数译码站，用来完成对多条指令的译码并保留译码输出状态。,9,3）也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称后行部件。包括：后行数地址站，提供后行数存放地址。后行数站，存放运行的结果，并且，这些结果需送存储器。,10,1

5、1,二、从重叠到流水,1、工业生产流水线 下面通过一个例子来说明流水线的好处:两种方案两种方案的工作过程对比流水线生产过程的抽象描述这种流水工作方式的主要特点,12,洗衣店的例子,A,B,C,D,均有一些衣物要清洗，甩干，折叠,清洗要花 30 分钟,甩干要用 30 分钟,叠衣物也需要 30 分钟,还要花费 30 分钟的时间,将衣物放在衣柜里,A,B,C,D,13,顺序操作,洗4 个人的衣物，顺序操作需要 8 个小时,如果使用流水线作业,将需要多少时间呢?,30,任,务,顺,序,时间,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,6 下午,7,8,9,

6、10,11,12,1,2 上午,14,流水线作业,流水线作业洗4个人的衣物只需要 3.5 个小时!,任,务,顺,序,12,2 上午,6 下午,7,8,9,10,11,1,时间,15,流水线,流水线无法帮助解决单个任务,的延迟,有利于减少整个工作,全部时间,多个任务同时操作需要不同的资源,流水线的速率受速度最慢,的流水段的限制,流水线各段长度不均会降低加速比,6 下午,7,8,9,时间,任,务,顺,序,16,2、流水线技术把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。3、流水线中的

7、每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。,17,4、指令流水线把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍4段指令流水线,18,5、浮点加法流水线把流水线技术应用于运算的执行过程，就形成了运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化4个子过程。理想情况：速度提高3倍,19,3.1.2 流水线的分类,流水线可按不同的观点进行分类，一般来说流水线可以分为以下几个类型。,1、按各过程段用时是否相等分类 流水线按各过程段用时

8、是否相等可分为均匀流水线和非均匀流水线两种。,1）均匀流水线指的是各过程段用时全相等的流水线,2）非均匀流水线指的是各过程段用时不全相等的流水线,20,2、按处理的数据类型,1）标量流水线：用于对标量数据进行流水处理。2）向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）,按处理的数据类型可分为标量流水处理机和向量流水处理机两种。,21,3.按流水线的规模 按流水线的规模可分为操作流水线、指令流水线和宏流水线。,1）操作流水线是把处理机的算术逻辑部件分段，使得各种数据类型的操作能够进行流水，规模最小。,2）指令流水线则是把解释指令的过程按照流水方式处理。,3）宏流水线它是指由两个以

9、上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。,22,4.按功能分类 按流水线完成的功能是否单一，流水线可分为单功能流水线与多功能流水线两种。,1）单功能流水线：只能完成一种固定功能的流水线。2）多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。例：ASC的多功能流水线,23,24,5.按工作方式分类 流水线按工作方式可分为静态流水线和动态流水线两种。,1）静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。例如：ASC的8段流水线,25,2）动态流水

10、线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。优点灵活，能够提高流水线各段的使用率，从而提高处理速度。缺点控制复杂。,26,静、动态流水线时空图对比,27,6.按连接方式分类 按照流水线的各个功能段之间是否有反馈信号，可将流水线分为线性流水线和非线性流水线。,1）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。2）非线性流水线：流水线中除了有串行的连接外，还有反馈回路,28,29,例：在一个5段流水线上9拍完成一个任务，其预约表为：分别写出延迟禁止表F和冲突向量C。并请给出一种可行的调度方案。,30,7.其他分

11、类 除上述几种外，流水线分类还有下述几种。,1）根据控制方式分成顺序流水线和乱序流水线。,2）在线性流水线中，根据控制方式还可以分成同步流水线和异步流水线。,31,3.1.3 流水线的特点,1.流水线处理的必须是连续任务，只有连续不断的任务才能充分发挥流水线的效率。2.流水线依靠多个功能部件并行工作来缩短程序的执行时间，实际上是把一个大的功能部件分解为多个子过程，如前述将浮点数加法器分解为4个子过程。3.流水线中的每一功能部件后面都要有一个缓冲寄存器，即所谓的锁存器，以便平滑各个功能段延时时间的不一致。4.流水线中各段时间应尽量相等，避免段延时过长引起的相互等待。5.流水线需要有“装入时间”和

12、“排空时间”。,32,3.2 流水线的时空图及性能分析,一、时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。4段指令流水线的时空图,3.2.1 流水线的时空图,33,3.2.2 流水线的性能分析,吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。,一、吞吐率,n：任务数Tk：处理完成n个任务所用的时间,34,1、各段时间均相等的流水线各段时间均相等的流水线时空图,35,流水线完成n个连续任务所需要的总时间为（假设一条k段线性流水线）Tkkt(n-1)t(kn-1)t 流水线的实际吞吐率,最大吞吐率,36,最大吞吐率与实际吞吐

13、率的关系,流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n等有关。只有当nk时，才有TPTPmax。,37,2、各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 举例（时空图）一条4段的流水线S1，S3，S4各段的时间：tS2的时间：3t（瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。,38,39,各段时间不等的流水线的实际吞吐率：（ti为第i段的时间，共有k个段）,流水线的最大吞吐率为,40,3、解决流水线瓶颈问题的常用方法 1）细分瓶颈段 例如：对前面的4段流水线把瓶颈段S3细分为3个子流水线段：S3a，S3b，S

14、3c,改进后的流水线的吞吐率：,41,2)重复设置瓶颈段缺点：控制逻辑比较复杂，所需的硬件增加了。例如：对前面的4段流水线重复设置瓶颈段S3：S3a，S3b，S3c,42,重复设置瓶颈段后的时空图,43,二、加速比,流水线的加速比（Speedup,S）完成某个任务顺序执行所用时间与流水线执行所用时间之比。,假设：不使用流水线（即顺序执行）所用的间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为,44,1、流水线各段时间相等（都是t）一条k段流水线完成n个连续任务 所需要的时间为 Tk=(kn-1)t顺序执行n个任务 所需要的时间：Ts=nkt流水线的实际加速比为,45,最大加速比,当

15、nk时，S k思考：流水线的段数愈多愈好？,46,2、流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为,47,三、效率,流水线效率（Efficiency，E）是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与k个功能段总的时空区之比，因此流水线的效率包含时间和空间两个方面的因素。,实际上，n个任务占用的时空区就是顺序执行n个任务的总的时间T0；而用一条k段流水线完成n个任务的总的时空区为K*Tk，其中Tk 是流水线完成n个任务所使用的总时间，则一条k段流水线的效率为：,48,举例计算：S=a0+a1+a2+a3+a4+a5+a6+a7对相关算式

16、要合理分解算式尽量分解为少相关算式：S0=a0+a1 S4=S0+S1 S1=a2+a3 S5=S2+S3 S2=a4+a5 S6=S4+S5 S3=a6+a7,49,吞吐率：TP=7/18（1/t）效率：E=（作用区域面积）/（完成运算所需时间矩形面积）=（7*5t）/（18t*5）=7/18,50,3.3 流水线中的相关,3.3.1 什么是流水线相关,如果要执行算式S=a/b+c，要通过下列四条指令来执行。LD R,A DIV R,B ADD R,C；要等DIV结果 ST R,S；存结果,第3条指令ADD R,C执行的前提是第2条指令执行完毕、有了结果以后才能执行。换句话说，只有第2条指令

17、没有执行完毕，结果没有出来，第3条指令就无法执行下去，这就出现了指令因等待前面结果，使后面没指令无法继续下去的现象，即相关。,51,流水线中的相关主要分为以下3种类型,1.结构相关,2.数据相关,3.控制相关,52,3.3.2 流水线中的结构相关（资源相关）,如果某些指令组合在流水线中重叠执行时产生了资源冲突，那么我们称该流水线有结构相关。,由于访问同一个存储器而引起的结构冲突,53,对于这种冲突，通常有以下两种解决方法,解决办法(1)：插入暂停周期，即让流水线在完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作,为消除结构冲突而插入的流水线气泡,54,引入暂停后的时空图,55,解决方

18、法(2)：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache,56,3.3.3 流水线中的数据相关,如果下面的条件之一成立，则指令j与指令i数据相关：（1）指令j使用指令i产生的结果（2）指令j与指令k数据相关，指令k与指令i数据相关，则指令j与指令i数据相关。,第2个条件指出，如果两条指令之间存在类似上述的相关链，则它们之间也是相关的。这条相关链甚至可以贯穿整个程序。,57,例如：下面这一段代码存在数据相关。,Loop：L.D F0，0（R1）/F0为数组元素 ADD.D F4，F0，F2/加上F2中的值 S.D F4，0（R1）/保存结果 DADDIU R1

19、，R1，8/数组指针递减8个字节 BNE R1，R2，Loop/如果R1R2，则分支,58,3.3.4 流水线的控制相关,控制相关是指因为程序的执行方向可能被改变而引起的相关。,典型的程序结构是“if-then”结构。请看一个示例：,if p1 S1；S；if p2 S2；,59,控制相关带来了以下两个限制：（1）控制相关于一个分支的指令不能被移到分支之前执行。ifthen程序中，then后面的语句不能移至if之前执行。（2）没有控制相关于一个分支的指令不能移至该分支指令之后从而受这个分支控制，如ifthen程序中，if前的指令不能移至then部分中执行。,60,3.4 MIPS R4000

20、流水线计算机,MIPS(Microprocessor without Interlocked Piped Stages)系列处理机属于超流水线处理机。,3.4.1 MIPS R4000流水线计算机基本结构和工作原理,R4000处理器是一种流水线处理器，它所实现的MIPS-3指令集是一种和DLX类似的64位指令集。但是和DLX流水线不同，R4000的流水线特别考虑了流水访问存储器的操作。,61,一、基本结构,62,MIPS R4000处理机的流水线操作,二、工作原理,由于流水线段数较多，这有利于提高时钟频率（其时钟速率可达100-200MHz），所以这种类型的流水又称为是“超级流水”(super

21、pipelining)。,63,MIPS R4000正常指令流水工作时序,一条指令的执行过程经历8个流水线周期。由于一个主时钟周期包含有两个流水线周期，因此，也可以认为每4个主时钟周期执行完一条指令。,64,3.4.2 MIPS R4000流水线,指令序列在MIPS R4000流水线中重叠执行情况如图所示：,65,从上图可以看出，由于从存储器中读入的数据在DS段的末尾才会有效，所以其载人延迟是2个时钟周期，如下图所示：,66,指令序列在R4000流水线中的执行时空图,67,对R4000的流水线来说，定向是十分重要的。,在R4000的流水线中，ALU输入端的定向源有4个：EX/DF、DF/DS、

22、DS/T和TC/WB，如图所示，所以其对定向的控制也要比DLX流水线复杂得多。,68,R4000流水线的基本分支延迟为3个时钟周期,69,基于单周期延迟分支方法，R4000流水线处理分支指令的时空图,70,3.5 向量处理机,向量处理的基本概念,在流水线处理机中，设置向量数据表示和相应的向量指令，称为向量处理机。不具有向量数据表示和相应的向量指令的流水线处理机，称为标量处理机。,71,一、向量处理方式,计算：fi=ai*bi+ci 设各向量分别放在大写字母单元中:,72,1、横向处理 按照算式一个一个地进行计算，即按行计算 第一步计算：f0=a0*b0+c0 LD R,A0 MUL R,B0

23、ADD R,C0 ST R,F0 第二步计算：f1=a1*b1+c1 即将第一步中的脚标0改为1，同样用上述四条指令。直到第一百步，f99 优点：作为工作单元的通用寄存器少（本例 仅用一个R）缺点：条条指令发生相关，因而无人采用。,73,2、纵向处理 将所有算式列出后，按列进行计算。如对f0 f99可分为四大步完成。第一大步：取向量 LD R0,A0：LD R99,A99 第二大步：向量乘 MUL R0,B0：MUL R99,B99 第三大步：向量加 ADD R0,C0：ADD R99,C99,74,第四大步：送结果 ST R0,F0：ST R99,F99优点：解决了相关问题，将原来条条发生相

24、关改为条条不相关。缺点：在向量数据较多时，所用的寄存器数目多。如本例共用了一百个寄存器（R0R99），因而在向量数据不多时，可用纵向处理，而向量数据较多时，可用纵横处理。,75,3、纵横处理 基本思想：将所有算式分为若干组进行如f0 f99 可分为10组：第一组：，第二组，第十组。组内采用纵向处理，组间采用横向处理。如第一组：取向量 LD R0,A0：LD R9,A9 向量乘 MUL R0,B0：MUL R9,B9,76,向量加 ADD R0,C0：ADD R9,C9 送结果 ST R0,F0：ST R9,F9 其余各组与第一组类似，因而总共用了10个寄存器（R0 R9）,77,3.5.2 向

25、量处理机的结构,向量处理机最简单的框图,一种能实现两个向量加得流水结构的加法器,78,向量指令的执行过程及简单性能计算,一、CRAY-1机有关问题 1）向量指令类型 取向量：Vi存储器 存向量：存储器Vi 向量与向量运算：Vi Vj OP Vk 向量与数据运算：Vi Vj OP B,79,2）多向量寄存器组结构 共有8个向量寄存器组（V0V7），每个组可存放64个长度为64位的二进制数的向量数据。,80,3）多功能部件 每个部件都以1=10ns 为单位的流水线结构。,逻辑运算：定点加：移位：浮点加：访存储器：浮点乘：除法：此外，在功能部件和向量寄存器组之间相互传送也用1。,81,4）、独立总线

26、结构 每个向量寄存器组到每个功能部件之间都有单独总线连接，在不冲突条件下，可实现功能部件之间并行运行。,82,二、向量指令的执行过程及简单性能计算,衡量向量处理机性能的简单参数有向量指令的完成时间和向量数据处理速度两个,通过两个例子分别讨论这两个参数的含义和计算方法。,83,例3-4 单条向量指令的执行过程 已知向量指令：V2 V1+V0（浮点加）向量长度为64，实际上是64组向量数据求和。请计算该向量指令的完成时间和向量数据处理速度。,1）写出64组算式 V2.0V1.0+V0.0 V2.1V1.1+V0.1 64 V2.63 V1.63+V0.63,84,2）画出向量指令结构图（如图所示）

27、3）画出各算式执行过程示意图送数1，加法6，输出结果1，共8。,85,86,4）完成运算时间第一个结果时间+（长度-1）=(1+6+1)+(64-1)=715）向量数据处理速度计算（向量指令条数*长度）/（完成运算用时）=（1*64）/（71*10-8S）=90MFOLPS,87,例3-6：多条向量指令的执行过程 已知有多条向量指令：V0存储器；V3 V2V1；V6 V5V4；三条指令可并行执行，向量长度为64，请计算该向量指令的完成时间和向量数据处理速度。,88,解：若有多条向量指令，且可并行执行时，完成运算用时，可选用时最多的那条向量指令。如:V0存储器 可并行执行，V3 V2V1 向量长

28、度为64V6 V5V4 由于除法用时最长，以它为准。1+14+1+(64-1)=79()3*64/(79*10-8S)244MFLOPS,89,一、向量的链接特性 1 链接：将多条相关的向量指令链接起来组成更大规模的流水线，从而进一步提高向量数据处理速度，这种链接称为向量链接。,3.5.4 向量的链接技术,2 向量指令之间的几种情况1）既不相关，又无冲突 不能链接，但可并行执行（执行时间以最长向量指令时间为准）2）条条指令相关，且无冲突 可顺利链接3）条条指令相关，但有冲突不能顺利链接，执行时间往往需要推迟。,90,3 例子 例3-6：条条指令相关，可顺利链接的情况有如下向量指令：V0存储器;

29、V2V0+V1;V3V2位移;V5 V3V4;V7 V5V6向量长度64，请计算该向量指令的完成时间和向量数据处理速度。,解：分析相关性：每条指令之间，上一条向量指令的结果作下一条指令的一个源操作数。,91,1）画出向量链接特性图,92,2）完成运算有时 6+2+6+2+4+2+7+2+14+2+（64-1）=110()3）计算向量数据处理速度：5*64/(110*10-8S)291MFLOPS此处结论：相关在向量链接中有利于向量数据处理速度的提高。,93,例3-7：条条指令相关，不能顺利链接的情况 有如下向量指令：V0存储器；V2V0V1；V4V2+V3；V5V4位移；V7V5V6；V0V7

30、V1向量长度为64，请计算该向量指令的完成时间和向量数据处理速度。,解：分析相关性：上述向量指令条条相关，且有冲突，故不能顺利链接。,94,1）不能顺利链接时，对画向量链接特性图的影响。源冲突：第一次送出画实线，第二次送出画虚线目冲突：第一次接收画实线，第二次接收画虚线功能部件冲突：第一次出现画实线，第二次出现画虚线,95,96,2）为了计算是否需要推迟时间，以及推迟多少时间，先计算冲突部件的有关时间。源冲突：从第一次送出到第二次送出之前1目冲突：从第一次接收到第二次接收之前1功能块：从第一次送出到第二次送入之前1,源冲突（V1）：1+7+1+1+6+1+1+4+1+1+14+1=39()目冲

31、突（V0）：1+1+7+1+1+6+1+1+4+1+1+14+1+1+7=48()功能块（）：1+1+6+1+1+4+1+1+14+1=31()说明：乘法功能部件冲突最严重，上述三个时间以最短时间为准。,97,3）推迟时间计算：当长度大于最短有关时间时，实际需要推迟时间为：向量时间 有关时间 当长度小于等于有关时间时，实际不用推迟，可视为表面冲突。本例推迟时间为：64-31=33（）4）完成运算用时计算：顺利连接时间+推迟时间1+6+1+1+7+1+1+6+1+1+4+1+1+14+1+1+7+1+（64-1）+33=152()5）性能：6*64/（152*10-8）253M FLOPS,98

32、,补充：关于向量指令冲突1）源寄存器冲突：邻近向量指令使用了同一源向量寄存器，如上例中的V1。2）目寄存器冲突：邻近向量指令使用了同一目向量寄存器，如上例中的V0。3）功能部件冲突：邻近向量指令使用了同一功能部件，如上例中的乘法功能部件。解决冲突的办法是推迟法。冲突又分为表面冲突与实际冲突如上例中，向量长度为30时，仅表面冲突。,99,课后习题第7题:在CRAY-1机上，在下列指令组中，组内哪些指令可以链接？哪些不可以链接？不能链接的原因是什么？完成各指令所需的拍数（设向量长度均为64,打入寄存器及启动功能部件各需1）。（1）V0存储器(6);V1V2+V3(6);V4V5V6(7)（2）V2

33、V0V1;V3存储器;V4V2+V3（3）V0存储器;V2V0V1;V3V2+V0;V6V3+V4（4）V0存储器;V11/V0(14);V3V1V2;V5V3+V4,100,解：（1）既不相关又不冲突并行执行（不可链接）1+7+1+（64-1）=72()3*64/（72*10-8）267MFLOPS（2）有相关，不冲突可链接 1+7+1+1+6+1+（64-1）=80()3*64/（80*10-8）=240 MFLOPS,101,（3）条条指令相关，但有冲突不能顺利链接,源冲突（V0）:1+7+1=9()推迟 64-9=55 功能块冲突（加）:1推迟 64-1=63 用时：1+6+2+7+2

34、+6+2+6+1+（64-1）+118=214()性能：4*64/（214*10-8）120M FLOPS,102,（4）条条相关，且无冲突可顺利链接,用时：1+6+2+14+2+7+2+6+1+（64-1）=104()性能：4*64/（104*10-8）246M FLOPS,103,提高向量处理机的方法,1.链接技术 前面已经详细介绍了，这里不再叙述。,2.向量循环或分段开采技术,如果向量的长度大于向量寄存器的长度，该如何处理呢？当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。这种技术称为分段开采技术。由系统硬件和软件控制完成，

35、对程序员是透明的。,104,例3-9 设A和B是长度为N的向量，考虑在Cray-1向量处理器上实现以下的循环操作：DO 10 I=1，N 10 A（I）=5.0*B（I）+1,105,S1 5.0；将常数5.0送入标量寄存器S1S2 1.0；将常数1.0送入标量寄存器S2VL N；在向量长度寄存器VL中设置向量长度NV0 B；从存储器中将向量B读入向量寄存器V0V1 S1 V0；向量B中的每个元素分别和常数S1相乘V2 S2+V1；向量V1中的每个元素分别和常数S2 相加A V2；将计算结果从向量寄存器V2存入存储 器的向量A,当N 64时，可以用以下指令序列：,106,当N 64时，就需要进

36、行分段开采。循环次数K：余数L：,107,S1 5.0；将常数5.0送入标量寄存器S1S2 1.0；将常数1.0送入标量寄存器S2VL L；在向量长度寄存器VL中设置向量长度LV0 B；从存储器中将向量B0.L-1读入向量；寄存器V0V1 S1*V0；向量B中的每个元素分别和常数S1相乘V2 S2+V1；向量V1中的每个元素分别和常数S2相加A V2；将计算结果从向量寄存器V2存入存储 器的向量A0.L-1,处理余数部分,计算L个元素,108,For(I=0 to K-1)V0 B；从存储器中将向量BL+I*64.L+I*64+63；读入向量寄存器V0V1 S1*V0；向量B中的每个元素分别和

37、常数S1；相乘；V2 S2+V1；向量V1中的每个元素分别和常数S2；相加A V2；将计算结果V2存入存储器的向量；AL+I*64 L+I*64+63,循环K次,分段处理,109,3、向量递归技术,在向量操作中，结果通常是不送回到作为源操作数使用的同一个向量寄存器中的。有一类特殊的向量循环，其流水线功能部件的输出可能要回送到它的一个源向量寄存器。换句话说，一个向量寄存器用来同时存放源操作数和结果操作数。在功能流水线上的这种递归操作要求特别小心以避免产生数据阻塞问题。,110,4.稀疏矩阵的处理技术,一个稀疏向量由两个向量组成。其中一个是短向量，它仅包含向量的非零元素。另一个是位向量，其中“1”

38、表示对应位置为非零元素，“0”表示对应位置为零元素。位向量的长度与稀疏向量的长度相等。如果向量元素是64位的操作的话，那么现在所需的位数知识原来的1/64。,大型的稀疏矩阵往往非常稀疏，64：1的节省远远不够。稀疏向量这种方法如何进一步改进仍是一个有待研究的问题。,111,3.5.6 向量处理机的性能评价,1.向量指令的处理时间Tvp,执行一条向量长度为n的向量指令所需的时间为,Ts：向量流水线的建立时间Tvf：向量流水线的流过时间它是从向量指令开始译码算起，到第一对向量元素流过流水线直到产生第一个结果元素所需的时间。Tc：流水线瓶颈段的执行时间,112,如果流水线不存在“瓶颈”，每段的执行时

39、间等于一个时钟周期，则上式可以写为：s：向量流水线的建立时间所对应的时钟周期数e：向量流水线的流过时间所对应的时钟周期数Tclk：时钟周期时间 也可以将上式改写为：Tstart：向量功能部件启动所需的时钟周期数,113,对于一组向量指令而言，其执行时间主要取决于三个因素：向量的长度向量操作之间是否链接向量功能部件的冲突和数据的冲突性把几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。可以看出，同一个编队中的向量指令之间一定不存在流水向量功能部件的冲突和数据的冲突。,114,推论 假设每种向量功能部件只有一个，那么下面的一组向量指令能分成几个编队？LV V1，Rx MULTSV V

40、2，R0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4 解：分为4个编队第一编队：LV第二编队：MULTSV；LV第三编队：ADDV第四编队：SV,115,一个编队内所有向量指令执行完毕所要的时间为：（假设第i个编队中所有向量指令处理的向量元素个数均为n）Tci：第i个编队的执行时间Tstartij：第i个编队中第j条指令所使用向量功能部件的启动时钟周期数,116,编队后的向量指令序列总的执行时间为：m：向量指令序列编队的个数Tstart：向量指令序列编队总的启动时钟周期数,117,编队并采用分段开采技术后，向量指令序列执行所需的总的时钟周期数为：Tloop：分段开采所

41、需的额外的时间开销MVL：向量处理机的向量寄存器长度 m指令编队数目,118,例3-10 在某向量处理机上执行DAXPY的向量指令序列，也即计算双精度浮点向量表达式。其中X和Y是双精度浮点向量，最初保存在外部存储器中，是一个双精度浮点常数，已存放在浮点寄存器F0中。计算该表达式的向量指令序列如下：,LV V1，RxMULTFV V2，F0，V1LV V3，RyADDV V4，V2，V3SV Ry，V4,119,解：可以把上述5条向量指令按如下方式进行编队：第一编队：LV V1，Rx；第二编队：MULTFV V2，F0，V1；LV V3，Ry；第三编队：ADDV V4，V2，V3；第四编队：SV

42、 Ry，V4。假设：Tloop15向量存储部件的启动：12个时钟周期向量乘法部件的启动：7个时钟周期向量加法部件的启动：6个时钟周期向量寄存器长度：MVL=64,120,对n个向量元素进行计算所需的时钟周期数为采用向量链接技术，那么指令序列可以编队为第一编队：LV V1,Rx；MULTFV V2,F0,V1；第二编队：LV V3,Ry；ADDV V4,V2,V3；第三编队：SV Ry,V4。,121,第一编队启动需要12+7=19个时钟周期第二个编队启动需要12+6=18个时钟周期第三个编队启动仍然需要12个时钟周期 对n个向量元素进行计算所需的时钟周期数为,122,2.向量处理机的峰值性能R

43、,R 表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。对于上述例题3-10中 向量指令序列中的操作而言，只有“MULTFV V2,F0,V1”和“ADDV V4,V2,V3”两条浮点操作向量指令。假设该向量处理机的时钟频率为200 MHz，那么：,123,124,3.半性能向量长度n 1/2半性能向量长度n1/2是指向量处理机的运行性能达到其峰值性能的一半时所必须满足的向量长度。对于上面的例子由于该向量处理机的峰值性能R100 MFLOPS，所以根据半性能向量长度的定义有：,125,假设 64，那么有：,n1/2,5n1/2 64，n1/2 12.8,n1/2 13,2n1/2 200,643n1/2,n1/2,64,50,126,4.向量长度临界值nv向量长度临界值nv是指：对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。对于上述DAXPY的例子假设，在标量串行工作方式下实现DAXPY循环的开销为10个时钟周期。那么在标量串行方式下，计算DAXPY循环所需要的时钟周期数为：Ts=(1012127612)nv=59nv,127,在向量方式下，计算DAXPY循环所需要的时钟周期数为：Tv=643nv 根据向量长度临界值的定义，有：Tv=Ts 643nv=59nv,=,64,56,=2,nv,