重叠流水和向量流水处理机.pptx

5.1重叠方式重叠原理和一次重叠图5.1对一条机器指令的解释取指令分析执行。t t一、顺序解释（sequence）：一条指令执行完再取下一条指令。若各阶段执行时间相等，则共需3nt t优点：控制简单，节省设备；缺点：速度慢，机器各部件的利用率很低。取k k分析k k执行k k取k+1k+1分析k+1k+1执行k+1k+1指令的解释方式一般分为顺序、重叠、流水三种。设指令工作方式分成取指令、分析、执行指令阶段第1页/共118页执行n条指令需：T=（1+2n）t；优点：指令执行时间缩短了近1/2；功能部件的利用率也有所提高；缺点：需要增加一些部件，控制也要复杂些；取k分析k执行k分析k+1取k+1执行k+1取k+2分析k+2执行k+2二、重叠（Overlap）：在两条相近指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。1.上一条指令的执行阶段与下一条指令的取指阶段完全重叠；取k分析k执行k分析k+1取k+1执行k+1取k+2分析k+2执行k+22.将相邻两条指令的重叠时间再往前提前一个阶段；第2页/共118页执行执行n n条指令需要：条指令需要：T=T=（2+n2+n）t t指令的执行时间缩短了近指令的执行时间缩短了近2/32/3，是一种比较理想的指令执行方式；，是一种比较理想的指令执行方式；这这种种执执行行方方式式存存在在着着访访存存冲冲突突，要要解解决决访访主主存存的的冲冲突突问问题题,通通常常采采用用以以下下几种方式：几种方式：（1 1）主主存存分分成成两两个个独独立立编编址址的的存存储储器器，一一个个专专门门存存放放指指令令，一一个个专专门门存存放放操操作数；作数；（2 2）指指令令和和数数据据仍仍然然混混存存在在一一个个存存储储器器中中，采采用用多多体体交交叉叉主主存存结结构构，不不能能根根本解决本解决;(3 (3）采用先行控制技术，增设采用先进先出方式工作的指令缓冲寄存器）采用先行控制技术，增设采用先进先出方式工作的指令缓冲寄存器。第3页/共118页3 3 一次重叠：一次重叠：把取指令操作隐含在分析、执行指令过程中，则把取指令操作隐含在分析、执行指令过程中，则在任何时候只允许上条指令在任何时候只允许上条指令“执行执行”与下条指令与下条指令“分析分析”相重叠。相重叠。分析k执行k执行k+1分析k+1连续执行连续执行n n条指令所需时间为：条指令所需时间为：T=T=（1+n1+n）t t；实际达到这个速度是很难得，存在几个问题：实际达到这个速度是很难得，存在几个问题：（1 1）各种类型的指令）各种类型的指令“分析分析”与与“执行执行”所需时间差别很大；从所需时间差别很大；从而导致相互等待。而导致相互等待。（2 2）当出现转移指令或转移子程序指令时，程序的执行过）当出现转移指令或转移子程序指令时，程序的执行过程就不是顺序的了，那么指缓中的内容以及已经分析完的程就不是顺序的了，那么指缓中的内容以及已经分析完的下一条指令都将作废；下一条指令都将作废；（3 3）数据相关以及控制相关；）数据相关以及控制相关；第4页/共118页三、先行控制 使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。(a)重叠方式分析k+1分析k执行k执行k+1分析k+2执行k+2分析部件空闲执行部件空闲分析k+1分析k执行k分析k+2(b)先行控制执行k+1执行k+21.1.工作原理第5页/共118页 结果：解决了分析与执行时间不等长问题。与重叠区别：分析和执行部件可同时处理两条不相邻指令。2.2.硬件要求 增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。第6页/共118页 硬件结构：主存存控指令分析器指令缓冲栈读数据缓冲区执行部件先行操作栈数据缓冲栈写数据缓冲区第7页/共118页相关处理1.转移指令的处理采用延迟转移技术，将转移指令与条件转移无关的第k-1条指令交换一下位置，即使转移成功也不会使重叠效率下降。2.指令相关的处理“执行”指令是IBM370机器为此设置的一条指令，其形式为执行R1X2B2D2当执行到“执行”指令时，按第二操作数(X2)+(B2)+D2地址取出操作数区中单元的内容作为指令来执行，参见图5.5。第8页/共118页图5.5IBM370“执行”指令的执行第9页/共118页3.主存空间数相关的处理图5.6主存空间数相关的处理第10页/共118页4.通用寄存器组相关的处理设机器的基本指令格式为操作码L3L1B2d2或 操作码L3L1L2第11页/共118页图5.7指令解释过程中与通用寄存器内容有关的微操作时间关系第12页/共118页图5.8“执行k”、“分析k+1”重叠时，访问通用寄存器组的时间关系（1）通用寄存器组数相关处理第13页/共118页图5.9用相关专用通路解决通用寄存器组的数相关处理方法：a.推后下一条指令的分析。b.设置相关专用通路第14页/共118页（2）通用寄存器组基址值和变址值相关的处理图5.10B一次相关与二次相关第15页/共118页图5.11B一次、二次相关的推后处理处理方法：处理方法：a.推后分析推后分析第16页/共118页图5.12B相关专用通路法b.设置相关专用通路设置相关专用通路第17页/共118页5.2流水方式基本概念1.1.工作原理(重叠的进一步延伸)一种典型的指令流水线 流水线中每一个子过程还可以再进一步分解成更小的子过程将浮点加法器分解为求阶差、对阶、尾数加和规格化4个子过程。图5.13一种典型的指令流水线图5.14浮点数加法器流水线第18页/共118页流水线工作方式：指令一条接着一条从输入端流入，经过各个子过程后从输出端流出。时空图：描述流水线工作过程的二维坐标。对应图5.13所示的流水线的时空图如图5.15所示。图5.15对应图5.13流水线的时空图m t(n-1)t1 1）时空图第19页/共118页图5.16是对应5.14浮点数加法器流水线的时空图图5.16浮点数加法器流水线的时空图从横坐标方向看，流水线中的各个功能部件在逐个连续地完成自己的任务。从纵坐标方向看，在同一个时间段内有多个流水段在同时工作，执行不同的任务。第20页/共118页（2）流水线特点：1）流水一定重叠，比重叠更苛刻。2）一条流水线通常有多个流水段组成。3）每段有专用功能部件，各部件顺序连接，不断流。4）流水线有建立时间、满载时间、排空时间。5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。6）给出指标如最大吞吐率，为满负载最佳指标。第21页/共118页2 流水线分类分级：（处理的级别分类）分级：（处理的级别分类）部件级：指部件内各子部件间的流水，将复杂的部件级：指部件内各子部件间的流水，将复杂的算逻运算组成流水工作方式；算逻运算组成流水工作方式；处理机级：指构成处理机的各部件之间的流水，处理机级：指构成处理机的各部件之间的流水，如取指、分析、执行部件间的流水如取指、分析、执行部件间的流水 ；处理机间级：构成计算机系统的每个处理机完成处理机间级：构成计算机系统的每个处理机完成某一专门任务，各个处理机所得到的结果需存放在某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中与下一个处理机所共享的存储器中 。按流水具有的功能多少：按流水具有的功能多少：A.A.单单功功能能流流水水线线：指指流流水水线线内内各各段段固固定定连连接接，同同一一时间内只能完成单一的一种功能。时间内只能完成单一的一种功能。第22页/共118页TI-ASC运算器流水线（多功能）输入减阶对阶移位相加规格化相乘累加输出12345678输入减阶对阶移位相加规格化输出123458浮加、减输入相乘累加输出1678定乘 B.B.多功能流水线：流水线中各段可以有多种不同的连接方式，以实现多种不同的运算和功能；第23页/共118页按工作方式分为：A.A.静态流水线：在某一时间内各段只能按一种功能连接流水，只有等流水线全部流空后，才能切换为另一种功能；B.B.动态流水线：各个段可以同时为不同的功能服务，也就是说各功能段在同一时间内可以按不同运算或功能连接；第24页/共118页浮加排空完，再进行定乘浮加未排空完，已输入定乘。为什么？产生冲突产生冲突第25页/共118页按流水线中各功能段是否有反馈回路，分为：A.A.线性流水线：各段串行联接，没有反馈回路，各个段只经过一次；B.B.非线性流水线：除有串行联接通路外，还有某种反馈回路，需多次经过某个段或越过某个段；按机器所具有的数据表示分为：标量流水机和向量流水机1234+出入非线性流水线+特点：动态流水线必是多功能流水线；单功能流水线必是静态流水线第26页/共118页 一、吞吐率、加速比和效率。一、吞吐率、加速比和效率。流水线处理机的主要性能流水线处理机的主要性能 1.1.吞吐率（吞吐率（Thoughput rateThoughput rate，TPTP）指在单位时间内流水线完成的任务数或输出的结果数。其中：n表示任务数，Tk表示完成n个任务所用的时间第27页/共118页（1）各段时间均相等的流水线各段时间均相等的流水线时空图 S1 S2 S3 S4tttt时间4t(n-1)t完成n个任务n个任务所需要的时间第28页/共118页流水线完成n个连续任务所需要的总时间为（假设一条k k段线性流水线）TkTkk kt t(n n-1)-1)t t(k kn n-1)-1)t t 流水线的实际吞吐率最大吞吐率TP=n(k+n-1)tTPmax=n(k+n-1)tlimn=1t第29页/共118页最大吞吐率与实际吞吐率的关系流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k k以及输入到流水线中的任务数n n等有关。只有当n nk k时，才有TPTPTPTPmaxmax。第30页/共118页流水线中各个段的执行时间不完全相等，流水线出现“瓶颈”部件。时空图（a）各段执行时间不相等的流水线（b）各段执行时间不相等的时空图图5.17各段流水线不相等的流水线和时空图第31页/共118页流水线各段执行时间不相等的情况下的实际吞吐率为：流水线各段执行时间不相等的情况下的最大吞吐率为：对于图5.17所示的例子，流水线的最大吞吐率为：第32页/共118页解决流水线“瓶颈”问题有两种方法：一种方法：将流水线的“瓶颈”部分再细分（a）瓶颈功能段细分的流水线连接图（b）瓶颈功能段细分的时空图图5.18瓶颈功能部件细分的流水线和时空图流水线的最大吞吐率为：第33页/共118页另一种方法：将流水线的“瓶颈”子部件设置多套并联（a）重置瓶颈功能部件的流水线（b）重置瓶颈功能部件的时空图 图5.19重置瓶颈段的流水线和时空图流水线的最大吞吐率为：第34页/共118页2.2.加速比加速比 指流水线加速比是指完成一批任务时，不采用流水线所用的时间与采用流水线所用的时间之比 其中：用T0表示采用顺序方式下的执行时间；用T表示采用流水线的执行时间；用S表示流水线的加速比第35页/共118页（1）各个功能段执行时间均相等的k段流水线上完成n个连续任务的实际加速比为：在k个功能段相等的流水线中，最大加速比为：第36页/共118页（2）如果流水线上各个功能段的执行时间不相等，则流水线的加速比为：计算图5.17、图5.18所示的流水线的加速比？第37页/共118页3.3.效率效率 指流水线的设备利用率。其中：kT：表示k段流水线完成n个任务的总的时空区；T：表示流水线完成n个任务所使用的总时间；E：表示k段流水线的效率；即：在时空图上，流水线的效率为n个任务占用的时空区与k个功能段总的时空区之比。第38页/共118页（1）在流水线的各功能段执行时间相等连续输入n个任务的情况下，一条k段流水线的效率为：流水线的最高效率为：流水线效率与吞吐率的关系式：E=TPt 流水线效率与加速比的关系式：第39页/共118页（2）流水线的各段执行时间不相等连续执行n个任务时的流水线效率为：计算图5.17(b)的时空图所示，整个流水线的效率E？在图5.18和图5.19中分别采用的细分瓶颈功能部件和重置瓶颈功能部件的效率？第40页/共118页二二.标量流水线的性能举例标量流水线的性能举例【例5.1】采用前面图5.14所示的4段浮点数加法器流水线计算下面式子的8个浮点数的和，画出流水线的时空图，并求出流水线吞吐率、加速比和效率。Z=A+B+C+D+F+G+H解：Z=（A+B）+（C+D）+（E+F）+（G+H）按照数学计算顺序的方法从左到右一个一个计算上式，先计算（A+B），其结果出来后再开始计算（A+B）与C的加法，依次类推。第41页/共118页第42页/共118页流水线的实际吞吐率TP为：流水线的加速比S为：流水线的效率E为：第43页/共118页【例5.2】设向量A和B各有4个元素，图5.20为静态双功能的流水线连接图，其中，1235组成加法流水线，145组成乘法流水线，设每个流水线所经过的时间均为t，则计算向量点积画出完成上面运算流水线的时空图，并求出静态双功能流水线的实际吞吐率、加速比和效率。按照数学运算优先级顺序进行(a1b1)+(a2b2)+(a3b3)+(a4b4)的运算，分别用任务1到7表示。解：加14325乘图5.20第44页/共118页第45页/共118页流水线的实际吞吐率TP为：流水线的加速比S为：流水线的效率E为：第46页/共118页【例5.3】假设图5.20表示的双功能流水线为动态双功能流水线，则重新计算向量点积要求画出完成上面运算流水线的时空图，并求出动态双功能流水线的实际吞吐率、加速比和效率。解：动态多功能流水线在不发生功能部件冲突前提下，同一时间可以按不同运算进行不同功能的连接。因此，只要任务1、任务2、任务3和任务4的结果输出，任务5和任务6就可以输入流水线。下图为在动态流水线下执行向量点积的时空图。第47页/共118页图6-17动态双功能流水线的时空图第48页/共118页流水线的实际吞吐率TP为：流水线的加速比S为：流水线的效率E为：第49页/共118页课堂练习有一个乘、加双功能的静态流水线，“乘”由1236完成，“加”由1456完成，各段如下图所示。若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（1）完成全部运算所需时间是多少？画时空图计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比是多少？1234562t2t2t2ttt第50页/共118页一、局部性相关处理（1 1）资源冲突（相关）原因：许多指令争抢同一功能部件。如访存流水机器的相关处理和控制机构1 1、各种局部性相关的处理包括资源或结构相关、指令相关、数据相关。两条指令同时访存造成资源相关MEMEXIDIF指令i+4WBMEMEXIDIF指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321时钟指令冲突取指译码执行访存写回例：第51页/共118页 解决方法：a.时间方法-后续指令冲突部件推后一拍执行；b.b.空间方法-重复设置资源。EXIDIF指令i+4MEMEXIDIF停顿指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321时钟指令9WBMEM使i+3指令停顿一拍进入流水线，以解决访存相关或重复设置一个存储器第52页/共118页（2 2）指令相关 原因：由指令可修改引起。解决方案：a.a.禁止方法-指令不允许修改；b.b.转换方法-把新指令作为“执行”指令的操作数，使指令相关变成数据相关。第53页/共118页（3 3）数据相关原因：对主存数据或通用寄存器数据的操作引起的相关。相关类型一：RAW（先写后读）有针对存储器RAWRAW和针对通用寄存器RAWRAW两种。IFIDEXMEMWBSUBIFIDEXMEMWBADD123456指令时钟写R1读R1例：ADDR1，R2，R3；R2+R3R1SUBR4，R1，R5；R1-R5R4第54页/共118页 相关类型一解决方案：a.a.延迟执行法（后推法）不同拍之间相关时，停顿后继指令的运行，直到前面指令结果生成；（R R或M M相关）同一拍中相关时，采用推后读、提前写方法（后半拍读、前半拍写）；（R R或M M相关）RISCRISC指令的装载延迟，采用联锁硬件检测，并使流水线停顿，直到相关消除。第55页/共118页 b.b.相关专用通路法 执行结果除写寄存器外，可直接送到ALUALU的操作数保存栈中。（R R相关）多路开关多路开关ALUR4R1寄存器堆RF旁路旁路缓冲寄存器2缓冲寄存器1第56页/共118页 c.c.异步流动法 让流水线中相关指令的后续不相关指令先执行，自动消除相关。读段写段入出段号：12345678相关专用通路njmlkih（异步流动的）kj空空空ih（顺序流动的）指令地址：kjih（判出j,h相关）绝大多数系统均采用异步流动的方法。异步流动会产生新的数据相关类型，使其控制很复杂。第57页/共118页 相关类型二：相关类型二：WAR(WAR(先读后写先读后写)、WAW(WAW(写写写写)这两种相关只有在异步流动流水线中才会产生。这两种相关只有在异步流动流水线中才会产生。RAWRAW（先写后读）相关在任何流水线中都会出现。（先写后读）相关在任何流水线中都会出现。WARWAR（读（读写）：写）：在先的指令先读，在后的指令才能写的关在先的指令先读，在后的指令才能写的关联，称联，称“先读后写先读后写”相关。相关。如：如：1 MOV AL1 MOV AL，2000H2000H 2 MOV 2000H 2 MOV 2000H，BLBLWAWWAW（写（写写）：写）：在先的指令先写入，在后的指令才能写的关在先的指令先写入，在后的指令才能写的关联，称联，称“写写写写”相关。相关。如：如：1 MOV 2000H1 MOV 2000H，ALAL 2 MOV 2000H 2 MOV 2000H，BLBL 相关类型二解决方案：使用动态调度方法检测和处理相关。第58页/共118页2.2.局部相关的分布式控制和管理目的：解决异步流动的WAR和WAW相关。关键技术：动态调度、寄存器重命名和动态存储器地址判别技术 IBM360/91 IBM360/91的浮点运算器部分包括了以下主要部件：的浮点运算器部分包括了以下主要部件：（1 1）运算部件运算部件（2 2）保存站保存站（3 3）浮点操作栈（浮点操作栈（FLOSFLOS）（4 4）浮点操作数缓冲器（浮点操作数缓冲器（FLBFLB）（5 5）存储数据缓冲器（存储数据缓冲器（SDBSDB）（6 6）浮点寄存器（浮点寄存器（FLRFLR）：）：寄存器号寄存器号F0F7F0F7，每个寄存器设置，每个寄存器设置一个一个“忙位忙位”，只要寄存器，只要寄存器FiFi正在使用，正在使用，“忙位忙位”就置为就置为“1 1”，使用完就清，使用完就清0 0。若。若某个操作命令使用某个操作命令使用FiFi，先检查，先检查“忙位忙位”是否为是否为“1 1”，若为，若为1 1则发生相关。则发生相关。（7 7）公共数据总线（公共数据总线（CDBCDB）第59页/共118页结构框图：浮点操作数缓冲器(FLB)控浮点操作栈(FLOS)忙制位站号源1控制站号源2站号源1站号源2 控制控制号站存数缓冲器(SDB)加法器乘/除法器译码器站号浮点寄存器(FLR)M1M2A1A2A3101010111100FLB总线FLR总线10001001CDB公共数据总线指令处理部件存储器总线654321站号：01100001F76543F21F0保存站第60页/共118页a.利用公共数据总线作为相关专用通路；b.利用FLR“忙”位，检测REG的RAW相关；c.利用修改站号（寄存器重命名），检测和消除REG的WAR和WAW相关；d.利用存数缓冲器的动态存储器地址判别技术，检测和消除MEM的RAW、WAR和WAW相关。应用举例：S1：(FLB1)F0 S2：(F0)*(FLB2)F0S3：(F0)+(FLB4)F0工作原理：第61页/共118页二、全局性相关处理 原因：由转移指令(占总指令的1/4)1/4)引起的相关。解决方法：程序执行时：停顿加速生成结果猜测结果程序生成时：优化延迟转移1.1.加快和提前形成条件码 对转移指令的条件码，部分可提前生成；加快单条指令或循环内条件码形成。第62页/共118页2.2.猜测法 选取发生概率较高的分支为猜测方向，运行但不写回结果。若猜对，继续执行；选取发生概率较高的分支为猜测方向，运行但不写回结果。若猜对，继续执行；否则否则,作废猜测方向的执行，返回实际转移处。作废猜测方向的执行，返回实际转移处。（2 2）实现方法：）实现方法：a.a.根据转移指令根据转移指令PCPC值检索值检索BTBBTB；BTB BTB包含转移指令包含转移指令PCPC值、有效位、历史位、转移目标值、有效位、历史位、转移目标PCPC值项。值项。b.b.命中时，根据历史位取得转移的猜测方向，猜测为转移时，取得转移目标命中时，根据历史位取得转移的猜测方向，猜测为转移时，取得转移目标PCPC值，值，预取指令送入指令队列头，否则，顺序执行；预取指令送入指令队列头，否则，顺序执行；（1 1）硬件要求：）硬件要求：增设转移目标缓冲器增设转移目标缓冲器BTB,BTB,加快另一分支的流动加快另一分支的流动第63页/共118页指令预取器转移指令地址有效位历史位转移目标地址指令译码1（D1）(PC+2)顺序取取指令转移取指令队列查找执行（EX）控制逻辑加入新项猜测发生错误命中与否实情执行情况更新旧项 c.c.根据转移指令实际结果，增加或修改根据转移指令实际结果，增加或修改BTBBTB相关相关指令项，更新其有效位、转移目标指令项，更新其有效位、转移目标PCPC、历史位。、历史位。第64页/共118页3.3.延迟转移技术延迟转移技术 是一种静态调度方法，由编译程序实现。是一种静态调度方法，由编译程序实现。实现方法实现方法（转移前指令与转移指令关系）：（转移前指令与转移指令关系）：无相关：无相关：转移前指令入槽；转移前指令入槽；相相 关：关：空指令入槽。空指令入槽。结果：结果：50%50%以上指令可进入延迟槽，其余为空指令。以上指令可进入延迟槽，其余为空指令。4.4.设置特殊循环指令，加快短循环处理设置特殊循环指令，加快短循环处理第65页/共118页三、流水机器的中断处理 1.解决问题如何处理好中断现场的保护与恢复。2.解决方法（1）不精确断点法不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。特点：硬件开销小，控制简单，程序排错不方便。第66页/共118页（2 2）精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的所有指令的原有现场都能保存和恢复。中断处理方法：平时采用一定数量的后援寄存器，把流水线中所有指令的执行现场保存下来，中断产生时可实现精确断点现场保护与恢复。特点：效果理想，硬件代价高，控制复杂。现在的流水都采用了精确断点法。第67页/共118页四.流水线调度1、单功能非线性流水线调度非线性流水线：由于段间有前馈和反馈通路任务,执行过程中可能会多次通过同一流水段,发生几个任务同时争用同一流水段的现象,这就是功能段的使用冲突。S1S2S3S4S5入出 某流水线结构如下：第68页/共118页解决方法：非线性流水线上输入任务时，在不发生功能段冲突，又能使流水线有较高的吞吐率和效率的情况下，应该如何选择输入任务的间隔时间？非线性流水线调度的任务就是找出一个最佳调度方案，按照这个调度方案向流水线输入任务，流水线的各个功能段都不会发生冲突。同时，非线性流水线的吞吐率和效率最高。流水线调度方案步骤如下：形成预约表；由预约表形成禁止表；由禁止表形成初始冲突向量；由初始冲突向量形成状态转换图；由状态转换图中找出最佳调度方案。第69页/共118页图5-21是一条由4个功能段组成非线性流水线的连接图，它有两条反馈线和一条前馈线，输出端在第一个功能段S1。图5-21非线性流水线连接图（1 1）形成预约表第70页/共118页预约表的横坐标表示流水线工作的时间周期，纵坐标表示流水线功能段，功能段在某个时钟周期处于工作状态用“”表示，空白的地方表示该功能段在对应的时间周期内不工作。图5-22与图5-21对应的一张预约表第71页/共118页一张非线性流水线的预约表可能与多个非线性流水线的连接图相对应；一个非线性流水线的连接图也可能与多个非线性流水线的预约表相对应。图5-23与图5-21对应的另一张预约表第72页/共118页图5-24是非流水线预约表5-22对应的另一种连接图。图5-24与图5-22对应的另一张预约表非线性流水线连接图5-21和对应的预约表图5-22可以唯一确定非线性流水线的工作过程。第73页/共118页图5-25启动距离为2的流水线冲突情况在图5-21和图5-22所确定的非线性流水线，当启动距离为2时，有关功能段的冲突情况如图5-25所示。第74页/共118页（2 2）由预约表形成禁止表F F 所对应的禁止向量为F=（3,4,6），若不想发生冲突，两个任务送入流水线的间隔拍数不属于F，F的拍数禁止使用。（3 3）由禁止表F F形成初始冲突向量C C0 0把预约表的每一行中任意两个“”之间的距离都计算出来，去掉重复的，将这些数组成一个数列。第75页/共118页初始冲突向量用一个m位的二进制数表示，其中m表示禁止向量中的最大值。对于一张k列的预约表，有m k-1。通常禁止向量用C0=(CmCm-1C1)来表示，如果i在禁止向量中，则Ci为1，否则Ci为0。上例中预约表的初始冲突向量C0=（101100）（4 4）由初始冲突向量C C0 0形成状态转换图a.a.C C0 0每过一拍逻辑右移一位，若移出0 0，则允许后续指令进入流水线，再与C C0 0按位“或”，形成新的冲突向量C Ci i=修改后的冲突向量初始冲突向量；1拍后，C C0 0右移1位，左边补0形成修改的冲突向量结果 010110010110101100右移1位0修改的冲突向量与原始冲突向量“或”第76页/共118页 010110+101100=111110=C1，即为新的冲突向量。同理，我们可计算出C2=101111，C5=101101，用冲突向量可画出流水线状态转换图：（1）冲突向量中，位=0表示不发生冲突，其位置号是不发生冲突的间隔拍数。（2）从初始状态开始，检查冲突向量中为0的位，有几个0，就会有几个新的冲突向量。（3）逐次计算新的冲突向量，并用有向图连接。（4）有向弧上的数字表示产生新的冲突向量所用的间隔拍数101100101111111110101101初始状态2517第77页/共118页 b.b.各C Ci i再每过一拍逻辑右移一位，若移出0 0，允许后续指令进入，再与C C0 0按位“或”，形成新的冲突向量C Cijij=C=Ci i C C0 0 ；说明：C Cijij为第i+j拍后流水线的冲突向量，若此时流水线中已有三条指令，C Cijij用于判断第四条指令的进入。对C C5 5，再2 2拍后，C C2 2右移2位，左边补0形成修改的冲突向量101101 右移2位0结果 001011001011修改的冲突向量与原始冲突向量“或”001011+001011+101100=101111=C C5252，即为新的冲突向量。第78页/共118页 c.c.重复上一步骤，直到不再生成新的冲突向量为止。图5-26与图5-22预约表对应的状态转换图第79页/共118页（5 5）找出最佳调度方案 从各个闭合回路中找出平均间隔最小的一个。a.从初始状态出发，沿箭头方向，每走一个闭环，即为一个方案。b.若中间遇到小闭环，每个小闭环也可作为一个方案。c.遍历初始状态中的Ci每一个回路。第80页/共118页本例中调度方案如下：调度策略调度策略平均间隔拍数平均间隔拍数调度策略调度策略平均间隔拍数平均间隔拍数（1，7）4（5，7）6（1，1，7）3（5）5（2，7）4.5（7）7（2，5）3.5（5，2）3.5（2，5，7）4.7（5，2，7）7.7对于非等间隔调度方案，找出每种调度法的平均间隔拍数，然后找出最小者，就是最佳调度方案。本例子平均间隔拍数最小的调度方案有(1,1,7).(1,1,7).平均间隔拍数=循环周期/任务数第81页/共118页非线性流水线的各个功能段在任何周期中都不会发生冲突的流水线预约表如图5-27所示。图5-27最佳调度方案（1，1，7）的流水线预约表第82页/共118页最大吞吐率Tpmax=1/(3 t)照最佳调度方案（1，1，7）连续输入9个任务，求流水线的实际执行时间、吞吐率和效率。完成任务的总时间=建立时间+（n-1）个任务流出时间 =（7+1+1+7+1+1+7+1+1）t=27t其中，（n-1）个任务的流出时间示意如下：任务1 2 3 4 5 6 7 8 9 9个任务可以在27个周期内完成。吞吐率=9/(27 t)=1/(3 t)=33%/t 效率=8*9/(4*27)=2/3=66.7%10个任务可以在34个周期内完成。吞吐率10=10/34=5/17=29%/t 效率10=8*10/(4*34)=80/136=58.8%11711711第83页/共118页例：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，需经7拍完成一个任务，它的预约表如下图：时间时间流水段流水段1234567S1XXS2XXS3XXS4X（1）写出流水线的禁止表和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最优调度方案及最小平均间隔时间和流水线的最大吞吐率。（4）按最优调度方案连续输入8个任务时，流水线的实际吞吐率是多少？第84页/共118页解：（1）禁止表F=2，4，6冲突向量为C=（101010）。（2）7+表示大于等于71010101111111011111010117+157+3537+57+第85页/共118页（3）平均最小间隔拍数，即平均最小延迟的调度方案是：（1，7）、（5，3）、（3，5）平均最小延迟是4拍简单循环简单循环平均间隔时间平均间隔时间（1，7）4（5，3）4（5，7）6（3，5，7）5（5，3，7）5（3，7）5（5）5（7）（3，5）74调度方案如右表：Tpmax=1/4（4）（1，7）调度方案，Tp=n/（7+25）=8/32（5，3）调度方案Tp=n/（7+29）=8/36（3，5）调度方案Tp=n/（7+27）=8/34Tp=n/（7+25）=8/32最佳第86页/共118页练习：一条有5个流水段的非线性流水线，每个流水段的延迟时间都相等，需经7拍完成一个任务，它的预约表如下图：时间时间流水段流水段1234567S1XXS2XXS3XXS4S5XXXX（1）写出流水线的延迟禁止表和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最优调度方案及最小平均延迟时间和流水线的最大吞吐率。（4）按最优调度方案连续输入10个任务时，流水线的实际吞吐率是多少？第87页/共118页2.2.多功能非线性流水线调度 如：加（A）、乘（B）双功能流水线预约表如下：1 12 23 34 4 5 5S1S1A AB BA A B BS2S2A AB BS3S3B BA AB BA AV VAAAA =(0110)=(0110)，V VABAB =(1011)=(1011)；V VBBBB =(0110)=(0110)，V VBABA =(1010)=(1010)。V VABAB表示先执行B B后执行A A；V VBABA表示先执行A A后执行B B。M MA A为A A的初始冲突矩阵(从A A开始)，包含V VAAAA和V VBABA；M MB B为B B的初始冲突矩阵(从B B开始)，包含V VBBBB和V VABAB。第88页/共118页 a.a.同单功能调度方法，首先生成n个初始冲突矩阵（按在先功能分类）。调度方案：0110101010110110MAMB b.b.再由初始冲突矩阵按后续功能分类按位右移，形成新的冲突矩阵，最终形成状态转换图。新冲突矩阵形成规则：V VB B=（V Vxx）|M|MB B，V V后续操作为B B；V VA A=（V Vxx）|M|MA A，V V后续操作为A A。第89页/共118页011010101011011010110111011111111111011101111010B1,B3A4MAB4B4B1B4MBB5A5A3B1,B3A3A4A1A4 c.c.从闭合回路中找出调度方案（按功能顺序分成几种）。第90页/共118页向量机对向量的各种运算可以采用不同的加式方式，一种是横向加工，一种是纵向(垂直)加工，还有就是纵横向加工(分组加工)，这是分段技术在向量加工方式上的实现。以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。for(i=1；i=n；i+)yi=ai(bi+ci);一、横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。逐个分量进行处理：假设中间结果为T(i)计算第1个分量：T(1)B(1)C(1)Y(1)A(1)T(1)计算第2个分量：T(2)B(2)C(2)Y(2)A(2)T(2)最后一个分量：T(N)B(N)C(N)Y(N)A(N)T(N)5.3向量的流水处理与向量流水处理机向量的处理和向量的流水处理第91页/共118页qq存在两个问题：1.在计算向量的每个分量时，都发生先写后读数据相关，流水线效率低。2.如果采用静态多功能流水线，必须频繁进行流水线切换。qq横向处理方式是向量处理方式，但不是向量流水处理方式。二、纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。T(1)=B(1)+C(1)T(2)=B(2)+C(2)T(n)=B(n)+C(n)Y(1)=A(1)T(1)Y(2)=A(2)T(2)Y(N)=A(N)T(N)第92页/共118页qq采用向量指令只需要2条：VADDT，B，CVMULY，A，Tqq这种处理方式适用于向量处理机，数据相关不影响流水线连续工作。1次相关，不同的运算操作只需要切换1次。特点：向量长度不受限制，但访存次数增加，宜于M-MM-M型向量处理方式及其向量流水处理方式。三、纵横处理方式，又称为分组纵横处理方式。横向处理和纵向处理相结合的方式。分成k组,每组长度为m，组内垂直处理，组间水平处理。n=k*m+r(r为第k+1组剩余分量)Bi+CiEi(1到m)Bi+CiEi(m+1到2m)Ei*AiDi(1到m)Ei*AiDi(m+1到2m)第93页/共118页向量流水处理机的结构1.1.向量处理机的指令系统 指令类型：V+VVV+VVV+SVV+SV主存V VVV主存123456VkVjVi123456ViVkSj123456Vi主存123456Vi主存第94页/共118页2、向量处理机基本系统结构按向量元素和结果存放分M-MM-M和R-RR-R两类。主存标量寄存器标量功能部件向量功能部件向量寄存器/向量缓冲器向量指令控制部件向量存取部件指令处理部件向量功能部件向量功能部件 控制部分：控制部件和缓冲部件 标量流水：功能部件和标量寄存器(S)向量流水：功能、存取部件和寄存器(V、VM、VL)向量处理机的典型结构图第95页/共118页以CRAY-1机为例（寄存器寄存器）CPU结构向量寄存器8*64*64指令缓存器4*64*16标量寄存器8*64向量屏蔽Vm64位向量长度寄存器Vl地址寄存器等。CPU功能部件12个可并行工作的单功能流水部件3个向量部件加（3）逻辑运算（2）移位（4）3个浮点部件加（6）乘（7）求倒数（14）4个标量部件2个地址功能部件存储器存取（6）第96页/共118页主存V0V7向量寄存器组(864个)加向量功能部件标量寄存器S0S7加浮点功能部件VM向量控制 移位逻辑运算相乘迭代求倒数向量控制向