计算机系统结构第五章

第五章标量流水技术计算机处理器的主要功能是控制指令的解释执行，为了能引入并行处理，目前普遍使用一种经济有效的方法，即流水控制方式。本章讨论的是有关流水控制的概念、原理、涉及的问题与解决的办法，以及流水控制技术的应用和进一步的发展。5.1控制流及其改变按算法要求控制指令序列的先后顺序执行称控制流，通常指令的执行顺序是相继的，但控制流经常会发生间断，破坏顺序性，主要有以下几种情况：1.转移指令不转移：PC=K0+K1T转移：控制流发生间断，以目标地址为起始点，再顺序流动。Pcpc转移指令Pc=k0+k1K0Tt(a)(b)2.过程调用和返回可嵌套和递归，返回时从原来断点继续执行。3.协同程序与调用不同，被调用过程不总是从头开始，如下图。协同程序A协同程序B4.中断和自陷为使流水控制方式能高效地解释指令，程序执行的控制流必须是连续的，因此对控制流的改变要采取有效的措施，以保证流水控制的实现。5.2标量流水工作原理5.2.1重叠操作方式和先行控制指令的解释执行有以下几种工作方式：1.顺序方式这种方式指令串行执行，设一条指令的解释分为：取指、分析、执行三个阶段，指令解释执行如下图所示：设各阶段执行时间为t，解释n条指令的时间是：tnT3若各阶段执行时间不同，分别为t取、t分、t执，则解释n条指令时间为：niT1(t取i+t分i+t执i)顺序方式控制简单，但指令串行解释速度慢，设备利用率低。2.重叠方式这是使相邻指令的解释在一些阶段上的操作在时间上重叠执行，如：T=(n+2)t或T=(2n+1)t重叠方式需增设指令缓冲寄存器，在执行k条指令时存放k+1条指令。同时还要解决取操作数与取指令都要访问存储器的冲突。解决冲突的方法：•使用分开的指令存储器和数据存储器，称为哈佛结构，如Pentium处理器设置有指令Cache和数据Cache。•采用多体交叉存储器•设置指令缓冲寄存器组这可预取指令，取指阶段时间短，可以合并到分析阶段，一条指令解释是分析和执行两个阶段。重叠方式如下：T=(n+1)t这称为一次重叠。取指k分析k执行k取指k+1分析k+1执行k+1取指k分析k执行k取指k+1分析k+1执行k+1取指k分析k执行k取指k+1分析k+1执行k+1分析k执行k分析k+1执行k+1分析k+2执行k+23.先行控制一次重叠方式中，若分析和执行两个阶段操作时间不一样，有可能使分析与执行操作有时处于空闲，如下图：分析k执行k空闲分析k+1执行k+1分析k+2执行k+2空闲解释n条指令的时间为：T=t分1+ni2(max(t分i，t执i–1))+t执n要消除空闲等待的时间，可进行如下操作：分析k执行k分析k+1执行k+1分析k+2执行k+2T=t分1+ni1t执I为此，必须采用先行控制技术，即指令预取、指令先行分析、预取数据等。并增设有关部件，如：指令缓冲站、先行操作栈、数据缓冲站等。先行控制结构图如下：数据缓冲栈5.2.2标量流水工作原理流水是重叠方式的进步发展，如把一条指令的解释细分为：取指、译码、执行、访存、写回寄存器五个子过程，相邻指令之间多个子过程时间上重叠操作，如下图所示。主存存控指令缓冲栈读数据缓冲区写数据缓冲区指令分析器先行操作栈执行部件S空间(功能段)建立(填入)正常(满载)排空S512345nS412345nS312345nS212345nS112345nt1t2t3t4t5tnT时间m∆t(n-1)∆t这种工作方式与工厂中的装配流水线相类似，所以称其为流水方式。上图给出了指令各功能段重叠操作的时间关系，称此为流水方式的时空图。流水的物理实现称流水线，其一般结构如下：LLLLL输入输出时钟L：锁存器，锁定时间为∆tl，Si：功能段，延迟时间为∆ts。1流水线最高最高工作频率为：∆ts+∆tl流水线有以下特点：(1)一条流水线通常由多个流水段组成，(2)每个流水段有专门的功能部件，相邻两个功能部件由锁存器隔开，(3)各流水段所需时间是一样的，(4)流水线工作分建立、满载和排空三个阶段，(5)流水线满载工作时，每隔∆t时间有一个结果流出流水线。上面流水线用于指令的解释，其实也可以用于运算操作，例如浮点运算。下面是浮点加法运算的流水操作。paA2qbB2两个浮点数相加分四个阶段：S1：对阶r=max(p，q)，t=|p-q|，小阶尾数右移t位。S2：两个尾数相加求和。S3：规格化尾数，数前导0，左移尾数S4：修改阶码设4个段的延时为S1=60nsS2=50nsS3=90nsS4=80nsL=10nsS1S2Sk四个阶段最大延迟时间为90+10=100ns，流水线满载运行时，每100ns可完成一次浮点加法操作。顺序执行时，完成一次浮点加法操作需要的时间为：2l+S1+S2+S3+S4=20+60+50+90+80=300ns采用流水线运算速度提高三倍。下图为浮点加法流水线。Paqb阶码S1减法器t=|p-q|r=max(p,q)LLL尾数r加法器S2LLS3rLLL阶码S4加法器LL5.2.3流水线分类流水线按不同的应用，有不同的结构、形式和功能：1.按处理级别分操作部件级：如浮点加减运算，指令级：如指令的解释执行，处理机级：多处理机的流水操作。尾数选择器右移位器前导0计数左移位器2.按功能分单功能：只是一种连接，完成一种功能。多功能：有多种连接组成流水控制，完成多种功能。如不同连接实现：定点加、浮点加、定点乘浮点向量点积等。3.按工作方式分静态：同一时间内只能以一种方式工作，可以是单功能和多功能，多功能时从一种功能切换到另一种功能，流水线必须排空，然后重新建立。动态：同一时间内将不同的功能段连接成不同的功能子集，完成不同的运算功能。单功能是静态的，动态是多功能的。4.按连接方式分线性：每个功能段从输入到输出只通过一次，无反遗非线性：有反遗回路，如下图：输入输出5.按维数分有一维和多维之分，如脉动流水控制是平面型的。5.2.4流水线的主要性能及其分析衡量流水线性能主要有三个指标：1.吞吐率(Tp)吞吐率是指单位时间内能处理的任务数或输出的结果数。(1)最大吞吐率流水线达到稳定状态后可获得的吞吐率。表示为：),2,1max(1maxtnttTp如下面流水线，∆t∆t3∆t∆ttTp31max流水线工作时钟周期按max{∆ti,i=1,2…n}确定，这是直接影响吞吐率的，所以称其为瓶颈。提高流水线吞吐率需寻找并消除瓶颈。一般有两种方法。S1S2S3S41243SS41234S31234S21234S11234t•瓶颈段细分∆t∆t∆t∆t∆t∆t•重复设置瓶颈段∆t∆t∆t3∆t时空图如下：SS412345678910S3c369S3b258S3a147S212345678910S112345678910t(2)实际吞吐率设流水线由m段组成，时钟周期为∆t，连续处理的任务数为n，通过各段的时间都是∆t，则：完成n个任务的时间T=M∆t+(n-1)∆t实际吞吐率)/)1(1(1)1(nmttntmnTpnmT/)1(1max流水线在开始时有一段建立时间，结束时有一段排空时间，123a3b3c43a3b3c124还有各种相关因素使流水线无法继续流动，所以实际吞吐率总是小于最大吞吐率。当n››m时，Tp≈Tpmax。2.加速比(Sp)这是流水方式的工作速度与等效的顺序串行方式的工作速度之比，具体计算如下：nmmnmnmtntmtnmSP/)1(11)1(当n››m时，Sp≈m。这说明要获得高的加速比，流水线的段数m应尽可能大，即加大流水线深度。3.效率(E)效率是指流水线中的各功能段的利用率。具体可用流水线各段处于工作时间的时空区与流水各段总的时空区的比来衡量流水线的效率。n个任务占用的时空区m段总的时空区tTmSnmntnmmtnmEPP1)1(这说明效率与实际吞吐率Tp成正比。5.2.5流水线性能分析举例设有A，B两个向量：A=(a1，a2，a3，a4)B=(b1，b2，b3，b4)要求在静态加、乘双功能流水线上计算)(41iiiba。流水线如下图所示：乘加加法：156，乘法：123461.流水线先设置加法功能，连续计算ai+bi，(i=1…4)其中a1+b1，a3+b3返回x输入端，a2+b2，a4+b4返回y输入端。2.流水线切换为乘法功能，计算：(a1+b1)(a2+b2)返回x输入端，(a3+b3)(a4+b4)返回y输入端。3.继续乘法功能计算：(a1+b1)(a2+b2)(a3+b3)(a4+b4)=∏(ai+bi)i=1…4。123465时空图如下：SS61234123s51234s4123s3123s2123s11234123t总计算时间T=17∆t，流出结果7个。tTP1774.26349102271763543tttttE%顺序串行执行，即非流水操作，所需时间为：T1=4×3∆t+3×5∆t=27∆t，所以88.11727ttSP这个例子表明流水线的吞吐率、效率及加速比均不是很理想，这是由于功能切换时，要有额外的建立和排空的开销。此外还有相关问题。流水线适合的操作是求解操作相同，且输入、输出间相互独立的一大串运算，此时，流水线的吞吐率可接近最大吞吐率，效率接近于1，而加速比也可接近流水线的段数值。5.3流水操作中的主要障碍流水操作中可能出现的相关会造成流水线断流，下面以一RISC机的一个五段流水线为例，分析流水线中可能出现的相关和解决的办法。不同类型指令在各流水功能段进行的操作指令流水段ALULOAD/STOREBRANCHIF取指取指取指ID译码读寄存器堆译码读寄存器堆译码读寄存器堆EX执行计算访存有效地址计算访存有效地址，设置条件码MEM–访存(读或写)若条件成立，将转移目标地址送PCWB结果写回寄存器堆将读出的数据写入寄存器堆5.3.1资源冲突(结构冲突)这是多条指令进入流水线后，在同一机器周期内争用同一功能部件所发生的冲突。例如：时钟12345678指令LOADIFIDEXMEMWB指令I+1IFIDEXMEMWB指令I+2IFIDEXMEMWB指令I+3IFIDEXMEMWB访存冲突解决冲突的办法：停顿一拍流水线。指令LOADIFIDEXMEMWB指令I+1IFIDEXMEMWB指令I+2IFIDEXMEMWB指令I+3停顿IFIDEXMEMWB5.3.2数据相关冲突这是多条指令在流水线中重叠操作，使对操作数访问的顺序发生变化所产生的冲突。常见的是后继指令所需的操作数是前一指令运算的结果，而此时结果却未产生。称此为先写后读相关，简称为RAW相关(Readafterwrite)。例如：ADDR1，R2，R3(R2)+(R3)→R1SUBR4，R1，R5(R1)–(R5)→R4指令流水操作：时钟12345写R1ADDIFIDEXMEMWBSUBIFIDEXMEMWB读R1ADD指令在笫5时钟周期将运算结果写入R1，而SUB指令在第3时钟周期就要读R1，显然读出的是R1旧的内容。解决冲突的办法：(1)推后执行，即停顿后继指令的运行。(2)相关专用通路，上例中写入R1的ADD运算结果在EX功能段就已产生，所以可通过硬件设置专用通路将此时产生的结果直接送往SUB的EX段进行运算，代替读R1。时钟12345写R1ADDIFIDEXMEMWBSUBIFIDEXMEMWB(3)周期分割，即将写R寄存器堆放在时钟周期的前半周期，读R寄存器堆放在后半周期，这样在一个周期写读同一个寄存器时就没有相关问题。如下例：写R1ADDR1，R2，R3IFIDEXMEMWBSUBAND读R1ORR8，R1，R9IDIDEX类似于RAW相关，前面指令从存储器读取操作数以供后继指令使用出现的相关称装载延迟。如下例：写R1LOADR1，AIFIDEXMEMWBADDR3，R1，R2IFIDEXMEMWB读R1此时专用通路不起作用，因为从存储器读取数据是MEM功能段，不可能提供ADD指令在