第4章并行处理机

1第四章并行处理机•两种并行性概念：同时性并行Simultaneity：两个或两个以上事件在同一时刻发生并发性并行Concurrency：两个或两个以上事件在同一时间间隔内发生•实现并行的三条技术途径：资源重复：通过重复设置多个处理部件来提高速度时间重叠：流水线资源共享：分时系统，分布式系统并行处理机采用同时性并行，资源重复技术。4.1并行处理机模型4.2并行处理机的基本结构4.3并行处理机实例4.4并行处理机算法举例24.1并行处理机模型•并行处理机的定义：多个PU按照一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作。从CU看，指令是串行执行的，从PU看，数据是并行处理的。并行处理机也称为阵列处理机、SIMD处理机等•并行处理机的应用领域：主要用于高速向量或矩阵运算•并行处理机的操作模型可用五元组来表示：M＝(N，C，I，M，R),其中：N为PE（处理单元）个数。C为控制部件CU执行的指令集，包括标量指令和程序控制指令。I为所有PE并行执行的指令集，包括ALU、数据传送等操作M为屏蔽操作集，将PE划分为允许操作和禁止操作两个子集R是数据寻径集，互连网络中PE间通信所需要的各种模式3PE0PE1PE2PE2……H.J.Siegel提出的并行处理机模型控制器P0M0P1P1P2P2PN-1PN-1互连网络M1M2MN-1M04典型并行处理机系统型号SIMD计算机系统结构和性能语言、编译器和软件支持MasPar计算机公司MP-1系列1024～16384个PE，26GIPS或1.3Gflops。每个PE带16KB本地存储器，X-Net网格加一个多级交叉开关互连网。Fortran77、MasParFortran(MPF)和MasPar并行应用语言；X-窗口UNIX/OS，符号调试程序，可视化和动画片制作器。ThinkingMachines公司CM-265536个PE排成10维超立方体，每个PE可有1M位存储器，32个PE共享FPU选件，峰值速度28Gflops和持续速度5.6Gflops。由VAX，Sun或Symbolics360主机驱动，PARIS支持的Lisp编译器、Fortran90、C*和*Lisp。ActiveMemoryTechnologyDAP600系列1K位/PE方形网格互连成4096PE的细粒、位片SIMD阵列，正交4-邻位链接，20GIPS和560Mflops峰值性能。由主机VAX/VMS或UNIXFortran-plus或DAP上APAL提供，主机的Fortran77或C。与Fortran90标准有关的Fortran-plus。54.2并行处理机的基本结构•并行处理机有两种典型结构：分布存储器并行处理机、共享存储器并行处理机•一台并行处理机由五个部分组成：多个处理单元PE，多个存储器模块M，一个控制器CU，一个互连网络ICN，一台输入输出处理机IOP。4.2.1分布存储器并行处理机4.2.2共享存储器并行处理机4.2.3并行处理机的特点64.2.1分布存储器并行处理机•目前的大部分并行处理机是基于分布式存储器模型的•比较容易构成MPP(MassivelyParallelProcessor)（大量信息并行处理机）,几十万个PE。•必须依靠并行算法来提高PE的利用率。因此，应用领域有限。•CU是控制部件，执行标量指令，并把向量指令广播到各个PE中。在CU中通常有一个较大容量的存储器。•IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。•数据在局部存储器中的分布是一个很关键的问题。•标量指令与向量指令可以并发执行。7CUIOPLM0LM1LMn-1PE0PE1PEn-1互连网络广播总线8根据以上结构，可以看出，它包含重复设置的多个同样的处理单元PE，通过数据寻径网络（互连网络）以一定方式相连。每个PE有各自的本地存储器LM。在统一的CU作用下，实现并行操作。程序和数据通过IOP装入，由于通过CU的是单指令流，所以指令的执行顺序还是和单处理机一样，基本上是串行处理。指令进行译码后，如果是标量操作，则直接由与CU直接连接的标量处理机执行。如果是向量操作，则将它广播到所有的PE并行的执行。互连网络负责PE间的通信，CU通过执行程序来控制互连网络。PE间的同步由CU的硬件实现。换句话说，所有的PE在同一周期执行同一条指令，然而可以通过用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令。94.2.2共享存储器并行处理机•共享多体并行存储器SM通过互连网络与各处理单元PE相连。•存储模块的数目等于或略大于处理单元的数目。•同时在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响。这种结构在PE数目不多的情况下是很理想的。•共享存储器模型的处理单元数目一般不多，几个至几十个。•BurroughsScientificProcessor(BSP)采用了这种结构。16个PE通过一个16×17的对准互连网络访问17个共享存储器模块。•存储器模块数与PE数互质可以实现无冲突并行访问存储器。10CUIOPPE0PE1PEnSM0SM1SMk互连网络11无论采用哪种存储方案，互连网络的存在都是必要的。在共享内存方案中，它是内存与处理单元之间的必由之路。在分布内存方案中，即使处理单元所需数据在大多数情况下能由本地存储器提供，处理单元之间的数据交往仍是必不可少的。而各处理单元之间可以通过两条途径相互联系：一条是通过广播总线广播到各PE中，另一条是通过互连网络。在处理单元很多的并行处理机中，PE之间的直接数据通路是有限的。因此，互连网络的研究是解决性能的一个很重要的方面。124.2.3并行处理机的特点•速度高，依靠增加PE个数来提高速度，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。•模块性好，生产和维护方便。•可靠性高，容易实现容错和重构。•效率低，通常作为专用计算机，在很大程度上依赖于并行算法。它依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些。•依赖于互连网络。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。•它基本是一台向量处理专用计算机。134.3并行处理机实例•IlliacIV是最先采用SIMD结构的并行处理机。•随后一个方向是用位片PE制造的并行处理机，如GoodyearMPP、AMT/DAP610和TMC/CM-2。CM-5是以SIMD模式运行的同步MIMD计算机。另一个方向是用字宽运算PE的中粒度SIMD计算机。•并行处理机的两个发展方向：保留阵列结构，但每个处理单元的规模减小，如一个bit。去掉阵列结构和分布存储器。Burroughs公司的BSP是代表。GF-11是由IBMWatson实验室研制、作科学模拟研究用的。MasParMP1是中粒度并行处理机的典型代表。•并行处理机的两种典型代表：采用阵列结构分布存储器的IlliacIV并行处理机去掉阵列结构和分布存储器BSP并行处理机。144.3.1IlliavIV并行处理机•1963年，美国西屋电器公司提出“Slotnick，TheSOLOMONComputer，SimultaneousOperationlinkedOrdinalModularNetwork”。•1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位浮点数，每个局部存储器PEM为2K64位，总的原算速度为1GFLOPS。•美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1/20的速度。只实现了88＝64个PE，只达到50MFLOPS。•IlliacIV系统的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。•IlliacIV系统由三大部分组成。IlliacIV处理机阵列，阵列控制器，一台标准的BurroughsB6700计算机。15PEM63PEM0PEM1CUCDCBIOMB6700CPUB6700内存B6700多路开关B6700外围设备IOS激光存储器6464X8CU总线控制线模式位线APPA网接口1282561024I/O总线CDBPE63PE01024实时装置48484848256PE0PE1PE63...DFSIlliacIV系统由三大部分组成•IlliacIV处理机阵列：8X8，包括PE、PEM和互连网络。•阵列控制器CU，•输入输出处理机：一台标准的BurroughsB6700计算机。161、阵列控制器•阵列控制器CU实际上是一台小型控制计算机。对阵列处理单元实行控制和完成标量操作。标量操作与各PE的数组操作可以重叠执行。•控制器的功能有以下五个方面：(1)对指令进行译码，并执行标量指令；(2)向各处理单元发出执行数组操作指令所需的控制信号；(3)产生和向所有处理单元广播公共的地址；(4)产生和向所有处理单元广播公共的数据；(5)接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2、输入输出系统•IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。•I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。173、IlliacIV处理阵列•IlliacIV处理阵列由８８＝64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。•每一个PUi只和它的东、西、南、北四个近邻PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64直接连接。•南北方向同一列PU连成一个环，东西方向构成一个闭合螺线。•闭合螺线最短距离不超过7步。普通网格最短距离不超过8步。例如：从PU0到PU36的距离：采用普通网格必须8步：PU0PU1PU2PU3PU4PU12PU20PU28PU36或PU0PU8PU16PU24PU32PU33PU34PU35PU36或…如果采用闭合螺旋线，只需要7步：PU0PU63PU62PU61PU60PU52PU44PU36或PU0PU63PU55PU47PU39PU38PU37PU36或……•对于n×n个单元的阵列，任意两个单元之间的最短距离不超过n-1步。普通网格必须8步：PU0PU1PU2PU3PU4PU12PU20PU28PU36或PU0PU8PU16PU24PU32PU33PU34PU35PU36或…闭合螺旋线只要7步：PU0PU63PU62PU61PU60PU52PU44PU36或PU0PU63PU55PU47PU39PU38PU37PU36或……PU56PU57PU63PU6323456PU8PU81011121314PU1616171819202122232425262728293031323334353637383940414243444546474849505152535455PU555859606162PU0PU0PU1PU7PU0PU1PU8PU9PU56PU57PU7PU15PU63194.3.2BSP处理机•BSP（BuroughsScientificProcessor）计算机是由美国宝来公司和伊利诺依大学于1979年制造的。•BSP是共享存储器结构的并行处理机的典型代表。•BSP由控制处理机、并行处理机、文件存储器、并行存储器模块以及对准网络等5个部分组成。1、并行处理机•时钟周期160ns，向量运算速度最高可达50MFLOPS。•17个并行存储器模块，每个模块512K字，存储周期160ns。•5级流水线：(1)从17个存储模块中读出数据(2)通过输出对准网络把数据送入1