计算机组成与体系结构 课件 12并行计算系统

并行计算系统计算机组成与体系结构内容提要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资源，在相同时间内完成更多工作虽然采用超线程技术能够同时执行两个线程，当两个线程同时需要某个资源时，其中一个线程必须让出资源暂时挂起，直到这些资源空闲以后才能继续IntelHyper-ThreadingIntelHyper-Threading单核技术的瓶颈多年来，在单线程性能方面已取得重大的进展为提高单线程性能，采用了各种微体系结构技术超标量发射乱序发射超流水技术推测执行但近年来，通过这些技术并未获得更好的性能能量和存储延时问题，已经成为提高单线程性能的障碍一些高频率芯片方案已被取消48能耗问题能量消耗大约与主频成立方关系P~c*f3处理器能量的消耗已经到了现有技术的极限对于有足够多线程的应用加倍并发线程的数目，能量消耗*2减半线程的工作频率，能量消耗