并行处理机精选PPT.ppt

并行处理机第1页，此课件共28页哦M1M2MN-1M08.1 并行处理机模型并行处理机模型http:/ 五道口生活网 http:/ 五道论坛第2页，此课件共28页哦并行处理机的定义：多多个个PU按按照照一一定定方方式式互互连连，在在同同一一个个CU控控制制下下，对对各各自自的的数数据据完完成成同一条指令规定的操作。同一条指令规定的操作。从从CU看，指令是串行执行的，从看，指令是串行执行的，从PU看，数据是并行处理的。看，数据是并行处理的。并行处理机也称为阵列处理机、SIMD处理机等并行处理机的应用领域：主要用于高速向量或矩阵运算并行处理机的操作模型可用五元组来表示：并行处理机的操作模型可用五元组来表示：M M(N(N，C C，I I，M M，R),R),其中：N N为为PEPE个数个数。如IlliacIV有64个PE。C C为控制部件为控制部件CUCU执行的指令集执行的指令集，包括标量指令和程序控制指令。I I为所有为所有PEPE并行执行的指令集并行执行的指令集，包括ALU、数据传送等操作M M为屏蔽操作集为屏蔽操作集，将PE划分为允许操作和禁止操作两个子集R R是数据寻径集是数据寻径集，互连网络中PE间通信所需要的各种模式http:/ 五道口生活网 http:/ 五道论坛第3页，此课件共28页哦http:/ 五道口生活网 http:/ 五道论坛第4页，此课件共28页哦8.2 并行处理机的基本结构并行处理机有两种典型结构：分布存储器并行处理机、共享存储器并行处理机分布存储器并行处理机、共享存储器并行处理机一台并行处理机由五个部分组成：多个处理单元多个处理单元PEPE，多个存储器模块，多个存储器模块M M，一个控制器，一个控制器CUCU，一个互连网络一个互连网络ICNICN，一台输入输出处理机，一台输入输出处理机IOPIOP。8.2.1 8.2.1 分布存储器并行处理机分布存储器并行处理机 8.2.2 8.2.2 共享存储器并行处理机共享存储器并行处理机 8.2.3 8.2.3 并行处理机的特点并行处理机的特点http:/ 五道口生活网 http:/ 五道论坛第5页，此课件共28页哦8.2.1 分布存储器并行处理机分布存储器并行处理机http:/ 五道口生活网 http:/ 五道论坛第6页，此课件共28页哦目前的大部分并行处理机是基于分布式存储器模型的目前的大部分并行处理机是基于分布式存储器模型的比比较较容容易易构构成成MPP(Massively Parallel Processor),几十万个PE。必须依靠并行算法来提高PE的利用率。因此，应用领域有限。CU是控制部件，执行标量指令，并把向量指令广播到各个PE中。在CU中通常有一个较大容量的存储器。IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。数据在局部存储器中的分布是一个很关键的问题。标量指令与向量指令可以并发执行。http:/ 五道口生活网 http:/ 五道论坛第7页，此课件共28页哦8.2.2 8.2.2 共享存储器并行处理机共享存储器并行处理机共享多体并行存储器SM通过互连网络与各处理单元PE相连。存储模块的数目等于或略大于处理单元的数目。同时在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响。共享存储器模型的处理单元数目一般不多，几个至几十个。共享存储器模型的处理单元数目一般不多，几个至几十个。Burroughs Scientific Processor(BSP)采用了这种结构。16个PE通过一个1617的对准互连网络访问17个共享存储器模块。存储器模块数与存储器模块数与PEPE数互质可以实现无冲突并行访问存储器。数互质可以实现无冲突并行访问存储器。http:/ 五道口生活网 http:/ 五道论坛第8页，此课件共28页哦第9页，此课件共28页哦8.2.3 8.2.3 并行处理机的特点并行处理机的特点速速度度高高，依靠增加PE个数来提高速度，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。模块性好模块性好，生产和维护方便。可靠性高可靠性高，容易实现容错和重构。效效率率低低，通通常常作作为为专专用用计计算算机机，在很大程度上依赖于并行算法。它依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些。依赖于互连网络依赖于互连网络。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。需需要要有有一一台台高高性性能能的的标标量量处处理理机机。如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，则对于标量运算占10的题目，总的有效速度就不超过每秒一千万次。http:/ 五道口生活网 http:/ 五道论坛第10页，此课件共28页哦8.3 并行处理机实例并行处理机的两种典型代表：采用阵列结构分布存储器的IlliacIV并行处理机共享存储器结构共享存储器结构BSP并行处理机。http:/ 五道口生活网 http:/ 五道论坛第11页，此课件共28页哦8.3.1 IlliavIV 8.3.1 IlliavIV 并行处理机并行处理机1963年，美国西屋电器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位浮点数，每个局部存储器PEM为2K64位，总的原算速度为1GFLOPS。美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用用了了4倍倍的的经经费费，只只达达到到1/20的的速速度度。只只实实现现了了8 864个个PE，只达到，只达到50MFLOPS。IlliacIV系系统统的的影影响响非非常常大大。它它是是并并行行处处理理机机的的典典型型代代表表，也也是是分分布布存存储器并行处理机的典型代表。储器并行处理机的典型代表。IlliacIV系统由三大部分组成。IlliacIV处理机阵列，阵列控制器，一台标准的Burroughs B6700计算机。http:/ 五道口生活网 http:/ 五道论坛第12页，此课件共28页哦IlliacIVIlliacIV系统由三大部分组成系统由三大部分组成IlliacIV处理机阵列：8 X 8，包括PE、PEM和互连网络。阵列控制器CU，输入输出处理机：一台标准的Burroughs B6700计算机。http:/ 五道口生活网 http:/ 五道论坛第13页，此课件共28页哦1 1、阵列控制器、阵列控制器阵列控制器CU实际上是一台小型控制计算机。对对阵阵列列处处理理单单元元实实行行控控制制和和完完成成标标量量操操作作。标标量量操操作作与与各各PEPE的的数数组组操操作作可以重叠执行。可以重叠执行。控制器的功能有以下五个方面：(1)对指令进行译码，并执行标量指令；(2)向各处理单元发出执行数组操作指令所需的控制信号；(3)产生和向所有处理单元广播公共的地址；(4)产生和向所有处理单元广播公共的数据；(5)接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2 2、输入输出系统、输入输出系统IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。http:/ 五道口生活网 http:/ 五道论坛第14页，此课件共28页哦3 3、IlliacIVIlliacIV处理阵列处理阵列IlliacIV处理阵列由64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。每一个PUi只和它的东、西、南、北四个近邻PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64直接连接。南北方向同一列PU连成一个环，东西方向构成一个闭合螺线。闭合螺线最短距离不超过闭合螺线最短距离不超过7 7步。普通网格最短距离不超过步。普通网格最短距离不超过8 8步。步。例如：从PU0到PU36的距离：采用普通网格必须8步：PU0PU1PU2PU3PU4PU12PU20PU28PU36 或 PU0PU8PU16PU24PU32PU33PU34PU35PU36 或 如果采用闭合螺旋线，只需要7步：PU0PU63PU62PU61PU60PU52PU44PU36或 PU0PU63PU55PU47PU39PU38PU37PU36 或 对于nn个单元的阵列，任任意意两两个个单单元元之之间间的的最最短短距距离离不不超超过过n-1n-1步步。http:/ 五道口生活网 http:/ 五道论坛第15页，此课件共28页哦普通网格必须8步：PUPU0 0PUPU1 1PUPU2 2PUPU3 3PUPU4 4PUPU1212PUPU2020PUPU2828PUPU3636或 PUPU0 0PUPU8 8PUPU1616PUPU2424PUPU3232PUPU3333PUPU3434PUPU3535PUPU3636 或 闭合螺旋线只要7步：PUPU0 0PUPU6363PUPU6262PUPU6161PUPU6060PUPU5252PUPU4444PUPU3636 或 PUPU0 0PUPU6363PUPU5555PUPU4747PUPU3939PUPU3838PUPU3737PUPU3636 或 http:/ 五道口生活网 http:/ 五道论坛第16页，此课件共28页哦8.3.2 BSP8.3.2 BSP处理机处理机BSP（Buroughs Scientific Processor）计算机是由美国宝来公司和伊利诺依大学于1979年制造的。BSPBSP是共享存储器结构的并行处理机的典型代表。是共享存储器结构的并行处理机的典型代表。BSP由控制处理机、并行处理机、文件存储器、并行存储器模块以及对准网络等5个部分组成。1 1、并行处理机、并行处理机时钟周期160ns，向量运算速度最高可达向量运算速度最高可达50MFLOPS50MFLOPS。17个并行存储器模块，每个模块512K字，存储周期160ns。5 5级流水线：级流水线：(1)(1)从从1717个存储模块中读出数据个存储模块中读出数据(2)(2)通过输出对准网络把数据送入通过输出对准网络把数据送入1616个并行处理部件个并行处理部件(3)16(3)16个并行处理部件并行处理数据个并行处理部件并行处理数据(4)(4)通过输入对准网络把数据从并行处理部件送到并行存储器通过输入对准网络把数据从并行处理部件送到并行存储器(5)(5)把接收到的数据写入并行存储器把接收到的数据写入并行存储器http:/ 五道口生活网 http:/ 五道论坛第17页，此课件共28页哦http:/ 五道口生活网 http:/ 五道论坛第18页，此课件共28页哦2 2、控制处理机、控制处理机控制处理机主要用来控制并行处理机。控制处理机主要用来控制并行处理机。提供与系统管理机相连的接口。执行存放在控制存储器中的操作系统和用户程序的标量部分。执行存放在控制存储器中的操作系统和用户程序的标量部分。全部向量指令及成组的标量指令被送给并行处理机。控制维护单元是系统管理机与控制处理机之间的接口，用来进行初始化、监控命令通信和维护。3 3、文件存储器、文件存储器计算任务文件从系统管理机加载到文件存储器，由控制处理机执行。文件存储器是BSP直接控制下唯一的外围设备。程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出给用户之前是存在文件存储器中的。文件存储器的数据传输率较高，大大地缓解了I/O受限问题。http:/ 五道口生活网 http:/ 五道论坛第19页，此课件共28页哦4 4、对准网络、对准网络对准网络采用全交叉开关实现对准网络采用全交叉开关实现。数数据据从从一一个个源源广广播播至至几几个个目目的的地地，几几个个源源寻寻找找一一个个目目的的地地时时能能分分解冲突。解冲突。存储器模块和对准网络的组合实现了无冲突访问并行存储器存储器模块和对准网络的组合实现了无冲突访问并行存储器。对准网络还可以实现快速傅里叶变换、数据压缩和扩展操作。5 5、无访问冲突存储系统、无访问冲突存储系统只有数组存取和I/O访问并行存储器。等效存储周期为等效存储周期为10ns10ns。两次算术运算中需要用到三个变量，产生一个结果，共访问存储器4次，并行存储器和浮点运算之间的频带保持完全平衡频带保持完全平衡。对于长向量来，中间结果存在寄存器中，每次运算只需要一个操作数。因此并行存储器有足够的频宽留给输入和输出信息用。实实现现一一维维向向量量和和二二维维矩矩阵阵的的行行、列列、对对角角线线和和反反对对角角线线的的无无冲冲突突访问。访问。http:/ 五道口生活网 http:/ 五道论坛第20页，此课件共28页哦8.4 8.4 并行处理机算法举例并行处理机算法举例要发挥并行处理机的效率，特别要发挥并行处理机的效率，特别依赖于并行算法依赖于并行算法。并行算法的一个关键问题是要并行算法的一个关键问题是要提高向量化的程度提高向量化的程度。在在设设计计并并行行算算法法时时，要要特特别别注注意意数数据据在在多多个个存存储储模模块块之之间间的的分分布布，要解决好访问存储器的冲突问题。，要解决好访问存储器的冲突问题。互互连连网网络络并并不不能能提提供供所所有有处处理理单单元元之之间间的的连连接接，因因此此，并并行行算算法法要要充分利用互连网络的结构充分利用互连网络的结构。8.4.1矩阵乘矩阵乘8.4.2求累加和求累加和 http:/ 五道口生活网 http:/ 五道论坛第21页，此课件共28页哦8.4.1 8.4.1 矩阵乘矩阵乘A、B、C均为88的二维矩阵，则CAB的计算公式为：在串行机上要用一个三重循环程序，乘和加分别为512次(除循环控制外)。在并行处理机上求解，FORTRAN程序如下：DO 10 IDO 10 I0 0，7 7 C(I,J)=0C(I,J)=0 DO 20 K=0,7DO 20 K=0,72020C(I,J)=C(I,J)+A(I,K)*B(K,J)C(I,J)=C(I,J)+A(I,K)*B(K,J)10 CONTINUE10 CONTINUEhttp:/ 五道口生活网 http:/ 五道论坛第22页，此课件共28页哦在并行处理机上，J循环只需一次。速度提高到8倍。PE0PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070 PE1 PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b7171 PE7 PE7：c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707b b7777 PE0PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070 PE1PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777PE7PE7：c c7777a a7070b b0707a a7171b b1717a a7272b b2727a a7777b b7777行向量跨PEM存放列向量在同一个PEM初始时Cij0CU广播同一个乘数aij给所有PE;与B的第i个行向量的所有n个元素同时相乘http:/ 五道口生活网 http:/ 五道论坛第23页，此课件共28页哦http:/ 五道口生活网 http:/ 五道论坛第24页，此课件共28页哦PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b7171 PE7：c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707b b7777PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777 PE7：c c7777a a7070b b0707a a7171b b1717a a7272b b2727a a7777b b7777如果64个处理单元全部利用起来并行运算，即把K循环的运算也改为并行，则可进一步提高速度。要做到这一点，需要重新在阵列存储器中恰当分配数据。http:/ 五道口生活网 http:/ 五道论坛第25页，此课件共28页哦8.4.2 8.4.2 求累加和求累加和把N个数的顺序相加变为并行相加。串行求和的 FORTRAN 程序如下：C(-1)0 DO 10 I0,N10 C(I)C(I-1)A(I)在并行处理机上，采用递归加法，FORTRAN 程序如下：DO 10 I=0，log2N110AASRL(A,2*I)；把A向量逻辑右移2i个PE在并行处理机上只需做在并行处理机上只需做 log log2 2N N 次加法。次加法。http:/ 五道口生活网 http:/ 五道论坛第26页，此课件共28页哦http:/ 五道口生活网 http:/ 五道论坛第27页，此课件共28页哦递归求和算法的性能分析：递归求和算法的性能分析：运算速度提高运算速度提高：加速比为加速比为N/logN/log2 2N N倍倍运算次数增加运算次数增加：从从N N次增加到次增加到N Nloglog2 2N N次次如：N N10241024，速度提高，速度提高100100倍，运算次数增加倍，运算次数增加1010倍倍如果N220，即100万个数求和，速度可以提高5万倍。这种方法也称为级联求和，或递归求和。与流水线中采用的方法相同，它利用结合律来提高并行度。http:/ 五道口生活网 http:/ 五道论坛第28页，此课件共28页哦