计算机组成与体系结构 课件 11指令流水线、12并行计算系统

指令流水线计算机组成与体系结构如何提高计算机的性能器件的进步摩尔定律体系结构面积换性能（TradeAreaforPerformance）空间换时间（TradeSpaceforTiming）实现方式时间重叠空间重叠时间重叠+空间重叠流水线（Pipeline）为什么工业化生产采用流水线？在CPU中，一种指令的执行方式时间重叠方式状态机→流水线指令的几种执行方式T=3ntT=(1+2n)tT=(2+n)t每个执行步骤时间为

t，则执行

n

条指令的用时

T

为:流水线时空图表示法流水线的特点把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现流水线每一个功能段部件后面都要设置缓冲寄存器，或称为锁存器，其作用是保存本流水段的结果流水线的特点流水线中各功能段的时间应尽量相等，否则将引起堵塞、断流，要求流水线的时钟周期不能快于最慢的流水段只有连续不断地提供同一种任务时才能发挥流水线的效率，所以在流水线中处理的必须是连续任务流水线需要有装入时间和排空时间装入时间是指第一个任务进入流水线到输出流水线的时间排空时间是指第n个（最后一个）任务进入流水线到输出流水线的时间流水线的分类（一）部件功能级流水线运算操作流水线（ArithmeticPipelines）。浮点加法器就是一种典型的功能部件级流水线。处理机级流水线指令流水线（InstructionPipelines），它是把执行指令的过程按照流水方式处理，使处理机能够重叠地秩序多条指令。处理机间级流水线宏流水线（MacroPipelines）。这种流水线由两个或者两个以上的处理机通过存储器串行连接起来，每个处理机完成整个任务的一部分。流水线的分类（二）单功能流水线只能完成一种固定的功能多功能流水线流水线各段可以进行不同的连接流水线的分类（三）静态流水线在同一段时间内，各功能段只能够按照一种固定方式连接，实现一种固定功能。动态流水线在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。流水线的分类（四）线性流水线LinearPipelines非线性流水线处理机级流水线NonlinearPipelines流水线的性能指标吞吐率（ThroughputRate）加速比（SpeedupRatio）效率（Efficiency）最佳段数流水线的吞吐率ThroughputRate衡量流水线速度的重要指标指在单位时间内流水线所完成的任务数量吞吐率的计算流水线的实际吞吐率为：当连续输入的任务n→∞时，得最大吞吐率为：最大吞吐率与实际吞吐率的关系是：流水线的吞吐率流水线的加速比SpeedupRatio完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比加速比的计算如果流水线各段执行时间都相等，则一条k段流水线完成n个连续任务实际加速比为：上述情况下的最大加速比为：流水线的加速比流水线的效率Efficiency流水线设备利用率称为流水线的效率效率的计算如果流水线的各段执行时间均相等，而且输入的n个任务是连续的，则一条k段流水线的效率为：在流水线的各段执行时间均相等，输入到流水线的任务是连续的情况下，流水线的最高效率为：流水线的效率流水线的最佳段数选择增加流水线段数时，流水线的吞吐率和加速比都能提高但是每一流水段输出端必须设置一个锁存器，当流水段数增多时，锁存器的总延迟时间也将增加，且流水线的价格也会增加要综合考虑各方面的因素，选择流水线最佳段数EXETIME

=#Insts×

CPI×cycletime硬件成本能耗一般处理机中的流水线段数在3到12之间，极少有超过15段的流水线一般把8段或超过8段的流水线称为超流水线，采用8段以上流水线的处理机有时也称为超流水线处理机流水线练习有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算，画出其时空图，并计算其吞吐率、加速比和效率。时空图结果如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t=29△t。所以加速比为：18个△t时间中，给出了7个结果，吞吐率为：效率可由阴影区的面积和5个段总时空区的面积的比值求得：时空图-动态流水线122334441123154321243abababccc17时空图-拆分段13234341241543-23-121abababccc11242343214时空图-资源重复1223344411231543213abababccc1424流水线中的相关问题结构相关，是指在指令重叠执行的过程中，遇到了因硬件资源不足而不能正常流水的冲突数据相关，是指在同时重叠执行的几条指令中，遇到了后续指令用到前面指令的执行结果，但前面指令尚不能提供的冲突控制相关，它是指流水线中的分支指令或者其他需要改写PC的指令时，遇到了不能及时确定应该取哪一条指令的矛盾经典的5段流水线结构相关解决方案一时空图解决方案二设置相互独立的存储器哈佛结构指令存储器数据存储器分立Cache指令Cache数据Cache数据相关采用定向（旁路）技术无法定向的情况流水线互锁编译器调度方法例如对于最常见的A＝B＋C这样的操作形式，采用比较典型的代码生成方法可以得到如下的指令序列：

LWR1,BLWR2,CADDR3,R1,R2SWA,R3编译器调度方法处理数据相关编译器是如何通过指令调度来消除流水线暂停的呢？例如有下面连续的两个操作：a＝b＋c；d＝e－f；指令调度前后代码对比（左：调度前，右：调度后）LWRb，bLWRc，cADDRa，Rb，RcSWa，RaLWRe，eLWRf，fSUBRd，Re，RfSWd，RdLWRb，bLWRc，cLWRe，e；交换指令,消除ADD指令暂停ADDRa，Rb，RcLWRf，fSWa，Ra；交换指令,消除SUB指令暂停SUBRd，Re，RfSWd，Rd控制相关控制相关是因程序执行转移类指令而引起的相关控制相关会使流水线的连续流动受到破坏会引起程序执行段落的改变，使流水线损失更多的性能，所以称为全局相关控制相关的解决方法冻结或者排空流水线的方法(Flush)最简单的处理方式分支延迟（延迟转移）的方法分支预测的方法猜测条件表达式两路分支中哪一路最可能发生，然后推测执行这一路的指令，来避免流水线停顿造成的时间浪费并行计算系统计算机组成与体系结构内容提要Flynn分类法并行计算技术指令级并行指令多发射并发与并行超线程技术多核技术Flynn'sTaxonomy

1972年费林（MichaelJ.Flynn）单指令流单数据流SingleInstruction,SingleData,SISD单指令流多数据流SingleInstruction,MultipleData,SIMD多指令流单数据流MultipleInstruction,SingleData,MISD多指令流多数据流MultipleInstruction,MultipleData,MIMDSISDSIMDMIMD不同层面的并行计算技术指令级并行线程级并行进程级并行并行对象指令序列多个线程多个进程主要技术乱序发射超线程/多核处理器多处理机系统实施者硬件程序员程序员指令级并行指令级并行技术指令级并行度ILPInstructionLevelParallelism是指在一个时钟周期内流水线上流出的指令条数CPI（ClockCyclesPerInstruction）目标：使CPI＜1主要方法：乱序执行，指令调度指令调度静态调度依靠编译器对代码进行静态调度，以减少相关和冲突它不是在程序执行的过程中、而是在编译期间进行代码调度和优化通过把相关的指令拉开距离来减少可能产生的停顿动态调度在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿动态指令调度优点能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行以硬件复杂性的显著增加为代价典型算法CDC记分牌法Tomasulo令牌法指令调度中的数据依赖RAWReadAfterWrite，假设指令j是在指令i后面执行的指令，RAW表示指令i将数据写入寄存器后，指令j才能从这个寄存器读取数据。如果指令j在指令i写入寄存器前尝试读出该寄存器的内容，将得到不正确的数据WARWriteAfterRead，假设指令j是在指令i后面执行的指令，WAR表示指令i读出数据后，指令j才能写这个寄存器。如果指令j在指令i读出数据前就写该寄存器，将使得指令i读出的数据不正确WAWWriteAfterWrite，假设指令j是在指令i后面执行的指令，WAW表示指令i将数据写入寄存器后，指令j才能将数据写入这个寄存器。如果指令j在指令i之前写该寄存器，将使得该寄存器的值不是最新值动态指令调度示例DIV.D F4，F0，F2SUB.D F10，F4，F6ADD.D F12，F6，F14SUB.D指令与DIV.D指令关于F4相关，导致流水线停顿。ADD.D指令与流水线中的任何指令都没有关系，但也因此受阻。在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。

DIV.D F10,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14存在反相关存在输出相关CDC记分牌法在资源充足时，尽可能早地执行没有数据阻塞的指令，达到每个时钟周期执行一条指令如果某条指令被暂停，而后面的指令与流水线中正在执行的或被暂停的指令不相关，那么这条指令可以继续流出并执行下去记分牌电路负责记录资源的使用，并负责相关检测，控制指令的流出和执行记分牌指令状态表：它登记已取指到指令流水线的各条指令的状态：是否已完成发射、是否已取完操作数、是否已完成执行、是否已完成写回功能部件状态表：每一个功能部件占有一个表项，登记是否“忙”、目的寄存器名、源寄存器名等是否就绪目标寄存器表：每一个寄存器与预约使用它作为目标寄存器的功能部件相联系，1个寄存器只能作为1个功能部件而不能同时作为两个功能部件的目标寄存器定向逻辑指令发射条件一条译码后的指令若它所需的功能部件可用，并且目标寄存器也不是其他功能部件已预约的目标寄存器，那么这条指令就可发射，否则等待直到条件满足再发射，这样首先杜绝了WAW相关在取寄存器操作数时要判测是否有WAR相关若先前发射出的指令以某寄存器为目标寄存器，则只有该指令向目标寄存器写入后（目标寄存器表中此项清除），此寄存器才作为其他指令的源寄存器就绪，从而消除WAR相关在写回(W)段要判测是否有RAW相关先前发射出的指令若以本指令预定的目标寄存器为源寄存器，而还没有读取的话，则本指令的写回操作要推迟，直到RW相关清除再写回CDC记分牌法(A×B)＋(C+D)I1LOADR1,M(A)I2LOADR2,M(B)I3MULR5,R1,R2I4LOADR3,M(C)I5LOADR4,M(D)I6ADDR2,R3,R4I7ADDR2,R2,R5按序发射但不按序完成Tomasulo算法核心思想记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小通过寄存器换名来消除WAR冲突和WAW冲突只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中指令的执行结果也是直接送到等待数据的其它保留站中去基于Tomasulo算法的MIPS处理器浮点部件的基本结构保留站reservationstation每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。包括：操作码、操作数以及用于检测和解决冲突的信息浮点加法器有3个保留站：ADD1，ADD2，ADD3浮点乘法器有两个保留站：MULT1，MULT2每个保留站都有一个标识字段，唯一地标识了该保留站保留站Op：要对源操作数进行的操作。Qj，Qk：将产生源操作数的保留站号。等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。Vj，Vk：源操作数的值。对于每一个操作数来说，V或Q字段只有一个有效。对于load来说，Vk字段用于保存偏移量。Busy：为“yes”表示本保留站或缓冲单元“忙”。A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。Qi：寄存器状态表每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪公共数据总线CDB所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDBload缓冲器和store缓冲器load缓冲器存放用于计算有效地址的分量记录正在进行的load访存，等待存储器的响应保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输store缓冲器存放用于计算有效地址的分量保存正在进行的store访存的目标地址，该store正在等待存储数据的到达保存该store的地址和数据，直到存储部件接收示例指

令

指令状态表

流出

执行

写结果

L.D F6,34(R2)√√√L.D F2,45(R3)√√MUL.D F0,F2,F4√SUB.D F8,F6,F2√DIV.D F10,F0,F6√ADD.D F6,F8,F2√

名称

保留站

Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOp

LDSUBADD

MULDIVVj

Vk

Mem[34+Regs[R2]]

Reg[F4]Mem[34+Regs[R2]]Qj

Load2Add1

Load2Mult1Qk

Load2A

45+Regs[R3]

寄存器状态表

F0F2F4F6F8F10…F30QiMult1

Load2Add2Add1Mult2…多指令发射技术超标量(Superscalar)处理机超流水线(Superpipelining)处理机超标量超流水线(SuperscalarSuperpipeling)处理机超长指令字(VeryLongInstructionWord)处理机超标量处理机乱序发射-指令的调度顺序发射顺序完成顺序发射乱序完成乱序发射乱序完成乱序发射顺序完成超流水线处理机分时发射多条指令超标量超流水线处理机执行时间加速比单流水线处理机超标量处理机超流水线处理机超标量超流水线处理机性能计算

性能计算现有12个任务需要进入流水线，流水线的功能段都为4个，流经每个功能段的时间相同，设为Δt。现在计算再下列情况下完成12个任务分别需要多少时间？（1） 单发射基准流水线。（2） 超标量流水线，每个时钟周期可以发射三条指令。（3） 超流水线，每个时钟周期可以分时发射三次，每次可以发射3条指令。T(1,1)=(4+12-1)Δt=15Δt

超长指令字（VLIW）处理机由编译程序在编译时找出指令间潜在的并行性，进行适当调度安排，把多个能并行执行的操作组合在一起，成为一条具有多个操作段的超长指令。由这条超长指令去控制VLIW处理机中多个互相独立工作的功能部件，每个操作段控制一个功能部件，相当于同时执行多条指令。VLIW处理机的主要特点超长指令字的生成是由编译器来完成的，由它将串行的操作序列合并为可并行执行的指令序列，以最大限度实现操作并行性单一的控制流，只有一个控制器，每个时钟周期启动一条长指令超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件含有大量的数据通路和功能部件。由于编译器在编译时间已解决可能出现的数据相关和资源冲突，故控制硬件比较简单VLIW处理机的结构模型FMULFADDLD/ST2LD/ST1VLIW中的操作字段浮点乘浮点加存/取2存/取1FMULFADDLD/ST2LD/ST1寄存器堆RF主存储器线程级并行进程与线程Thread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataAprocesshasthemainthreadthatinitializestheprocessandbeginsexecutingtheinstructions.2xSingleThreadRunningWithinaProgramProcessMultithreadedProgram2xThread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataThread1(ProgramCounter,Registers,etc.)CodesegmentDatasegmentStackStackStackthreadmain()…threadthreadProcessesandThreadsModernoperatingsystemsloadprogramsasprocessesResourceholderExecutionAprocessstartsexecutingatitsentrypointasathreadThreadscancreateotherthreadswithintheprocessEachthreadgetsitsownstackAllthreadswithinaprocesssharecode&datasegments线程CPU执行内核(executioncore)programcounterprogramcounterCopyofCPUregistersregistersasequenceofinstructionsALU进程计算机Addressspace,data,memorymanagementinformationmemoryFileDescriptorsdiskProgramcounter,Code,processstate,valuesofCPUregistersCPU进程与线程进程：OS进行计算机资源分配的单位一个进程可以理解成：OS为用户创建的、一个逻辑的计算机资源包括：内存，显卡，磁盘……线程：OS进行CPU资源调度的单位一个线程可以理解成：进程内顺序执行的一个指令序列只涉及CPU资源线程之间共享进程的资源为什么要多线程(multithreading)？减少程序的响应时间与进程相比，线程的创建和切换开销更小资源共享和通信更方便简化程序的结构并发与并行并发(concurrency)几件事情都在解决过程中，不是等到一件事情解决之后再解决另一件事情事情A和B都使用同一个资源（例如CPUexecutioncore），也使用不同的资源（内存单元）A和B各使用cache中的一半页面在把A需要的数据交换到cache时，可以用CPUexecutioncore处理B的一部分数据（已在cache中）通过并发，提高了公用资源的利用率：如何合理安排对共用资源的使用成为关键并发与并行并行(parallelism)同时解决几件事情，每件事情分别由不同的实体（人、计算机等）解决事情A和B分别使用不同的资源：A和B是两个独立的子问题A使用计算机1解决B使用计算机2解决通过并行，缩短了整个问题的解决周期，寻找到无关的子问题成为关键线程并行现实世界本质上是并发的并行是并发的一种特例：并发的事件之间，没有公用的资源并发的问题可以转换成并行的问题系统资源引起的并发：增加系统资源，如Multi-core代替Hyper-Threading，SMP代替UP，Cluster代替server，……应用领域资源引起的并发：改变算法如何实现线程并行？执行内核寄存器Cache线程间共享的资源主存空间文件句柄其他I/O超线程与多核超线程(Hyper-Threading)：支持将一个执行内核模拟成多个逻辑处理器（并发）每个逻辑处理器上运行一个线程逻辑处理器之间分享执行内核多核(Multi-core)：为进程的运行提供多个执行内核（并行）无关的线程在不同的执行内核上并行执行执行内核之间共享FSB、cache超线程Hyper-Threading,HT英特尔研发的一种技术，于2002年发布。超线程技术原先只应用于Xeon处理器中，当时称为Super-Threading。之后陆续应用在Pentium4HT中通过此技术，英特尔实现在一个实体CPU中，提供两个逻辑线程超线程技术充分利用空闲CPU资源，在相同时间内完成更多工作虽然采用超线程技术能够同时执行两个线程，当