第6章 并行处理机

1、 高性能计算机发展历程自自19641964年以后年以后, ,高性能计算机经历了三个发展阶段高性能计算机经历了三个发展阶段: :萌芽阶段、向量机鼎盛阶段和大规模并行处理机萌芽阶段、向量机鼎盛阶段和大规模并行处理机（MPPMPP）蓬勃发展阶段。）蓬勃发展阶段。1. 1. 萌芽阶段（萌芽阶段（1964-19751964-1975） 19641964年诞生的年诞生的CDC6600CDC6600被公认为世界上第一台被公认为世界上第一台巨型计算机，其运算速度为巨型计算机，其运算速度为1Mflops1Mflops。7070年代初研年代初研制成功制成功STAR-100STAR-100向量机，这是世界上最早的向

2、量向量机，这是世界上最早的向量机。随后于机。随后于19741974年，诞生了世界上最早的年，诞生了世界上最早的SIMDSIMD阵阵列计算机列计算机-ILLIAC-IV-ILLIAC-IV并行机。并行机。 2.2.向量机鼎盛阶段（向量机鼎盛阶段（1976-19901976-1990） 19761976年，年，CRAYCRAY公司推出公司推出CRAY-1CRAY-1向量机，开始向量机，开始了向量机的蓬勃发展，其峰值速度为了向量机的蓬勃发展，其峰值速度为0.1Gflops.0.1Gflops. 1985 1985年，年，CRAY-2CRAY-2，1G flops1G flops 1990 1990年

3、，年，SX-3SX-3，22G flops22G flops 1991 1991年，年，Cray-YMP-C90Cray-YMP-C90，16Gflops16Gflops 向量机处理对提高计算机运算速度十分有利，向量机处理对提高计算机运算速度十分有利，有利于流水线的充分利用，有利于多功能部件的有利于流水线的充分利用，有利于多功能部件的充分利用，但由于时钟周期已接近物理极限，向充分利用，但由于时钟周期已接近物理极限，向量计算机的进一步发展已经不太可能。量计算机的进一步发展已经不太可能。3. MPP3. MPP（massively parallel processingmassively para

4、llel processing蓬勃发展阶段（蓬勃发展阶段（19901990年至今年至今） 就在传统向量机逐渐萎缩的同时，迎来了大就在传统向量机逐渐萎缩的同时，迎来了大规模并行处理规模并行处理MPPMPP机蓬勃发展的时代。各种新技术层机蓬勃发展的时代。各种新技术层出不穷，大公司也纷纷介入。这一时期的代表机型出不穷，大公司也纷纷介入。这一时期的代表机型有：有： 1989 1989年，年，BBNBBN公司的公司的TC2000TC2000 1992 1992年，年，IntelIntel公司的公司的ParagonParagon，TMCTMC公司的公司的CM-5CM-5 1993 1993年，年，Cray

5、Cray公司的公司的T3DT3D 1994 1994年，年，IBMIBM公司的公司的SP2SP2 1996 1996年，年，CrayCray公司的公司的T3ET3E，HitachiHitachi公司的公司的SR2201SR2201，SGISGI公司的公司的Origin2000Origin2000，IntelIntel公司的公司的 ASCE REDASCE RED。其中，。其中，19961996年年1212月宣布的月宣布的ASCI REDASCI RED，运，运算速度超过了万亿次算速度超过了万亿次/ /秒。秒。银河银河-I巨型计算机巨型计算机 1983年年12月月银河银河-II-II巨型计算机巨

6、型计算机 19921992年年1111月月银河银河-II-II主机为我国高性能主机为我国高性能向量向量中央处理机中央处理机共享主存紧耦合系统共享主存紧耦合系统，基本字长，基本字长6464位，峰值位，峰值速度为每秒速度为每秒1010亿次以上运算操作，拥有两个亿次以上运算操作，拥有两个独立的输入输出子系统。各项技术指标达到独立的输入输出子系统。各项技术指标达到了八十年代中后期国际先进水平。了八十年代中后期国际先进水平。银河银河-III-III巨型计算机巨型计算机 1997 1997年年6 6月月银河银河IIIIII采用采用分布共享存储结构分布共享存储结构，峰值性能达，峰值性能达到每秒到每秒1301

7、30亿浮点运算。具有良好的可扩展性，亿浮点运算。具有良好的可扩展性，银河银河IIIIII在在MPPMPP资源管理与处理机调度、并行资源管理与处理机调度、并行I/OI/O软件、高性能优化编译、网络软硬件设计软件、高性能优化编译、网络软硬件设计等技术方面均达到国内领先水平，系统综合等技术方面均达到国内领先水平，系统综合技术达到当时国际先进水平。技术达到当时国际先进水平。 我国超级计算机的发展和应用 曙光一号曙光一号并行计算机是并行计算机是 1993 年我国自行研制的第一台用微处年我国自行研制的第一台用微处理器芯片（理器芯片（88100 微处理器）构成的全对称紧耦合共享存储微处理器）构成的全对称紧耦

8、合共享存储多处理机系统（多处理机系统（SMP），最大支持），最大支持 16 个个 CPU（4 CPU 共享共享存储为一结点主板，存储为一结点主板，4 个主板通过个主板通过 VME总线连接），系统外总线连接），系统外设采用设采用 SCSI 设备，系统峰值定点速度每秒设备，系统峰值定点速度每秒 6.4亿，主存容量亿，主存容量最大最大 768 MB。在对称式体系结构、操作系统核心代码并行。在对称式体系结构、操作系统核心代码并行化和支持细粒度并行的多线程技术等方面实现了一系列的技化和支持细粒度并行的多线程技术等方面实现了一系列的技术突破。硬件的技术突破包括多处理机共享内部总线协议设术突破。硬件的技术突

9、破包括多处理机共享内部总线协议设计、多机中断控制器芯片设计等；软件包括计、多机中断控制器芯片设计等；软件包括 SNIX (Symmetric uNIX) 操作系统采用的细粒度加锁以及动态分配操作系统采用的细粒度加锁以及动态分配 I/O 中断向量以实现多机系统对称式处理的方法；在中断向量以实现多机系统对称式处理的方法；在 UNIX 核心中增加共享资源进程以及成群调度核心中增加共享资源进程以及成群调度 ( Gang Scheduling) 策略，策略， 在用户空间以库函数的方式实现线程在用户空间以库函数的方式实现线程 ( Threads) 概念，概念， 支持中微粒度的并行计算等。支持中微粒度的并行

10、计算等。 “神威神威”巨型计算机巨型计算机1999年年8月月“神威神威”计算机有计算机有384个个CPU，内存总容量为，内存总容量为48GB，峰值运行速度达，峰值运行速度达到了每秒到了每秒3840亿次。亿次。国家最高科学技术奖国家最高科学技术奖2010年年 师昌绪师昌绪 （著名材料科学家（著名材料科学家 ）王振义王振义 （血液学专家（血液学专家 ）2009年年 谷超豪谷超豪 （著名数学家）（著名数学家）孙家栋（运载火箭与卫星技术专家）孙家栋（运载火箭与卫星技术专家）2008年年 王忠诚王忠诚 （神经外科专家）（神经外科专家）徐光宪（化学家）徐光宪（化学家）2007年年 闵恩泽（石油化工催化剂专

11、家）闵恩泽（石油化工催化剂专家）吴征镒（著名植物学家）吴征镒（著名植物学家）2006年年 李振声（遗传学家，小麦远缘杂交的奠基人）李振声（遗传学家，小麦远缘杂交的奠基人）2005年年 叶笃正（世界著名气象学家），叶笃正（世界著名气象学家），吴孟超（世界著名肝脏外科学家）吴孟超（世界著名肝脏外科学家）2004年年 空缺空缺2003年年 刘东生（著名地球环境科学家）刘东生（著名地球环境科学家）王永志（著名航天技术专家）王永志（著名航天技术专家）2002年年 金怡濂（高性能计算机领域的著名专家）金怡濂（高性能计算机领域的著名专家）2001年年 王选（汉字激光照排系统创始人）王选（汉字激光照排系统创始

12、人）黄昆（著名物理学家）黄昆（著名物理学家）2000年年 吴文俊（世界著名数学家）吴文俊（世界著名数学家）袁隆平（杂交水稻之父）袁隆平（杂交水稻之父） 2009年年6月月15日，国内首台百万亿次超级计算机日，国内首台百万亿次超级计算机“魔方魔方”，在，在上海正式启用。上海正式启用。“魔方魔方”不但是亚洲第一的超级计算机，也是目不但是亚洲第一的超级计算机，也是目前美国本土之外唯一计算速度排名进入全球前十的超级计算机，前美国本土之外唯一计算速度排名进入全球前十的超级计算机，表明中国成为全球第二个能够研发百万亿次超级计算机的国家。表明中国成为全球第二个能够研发百万亿次超级计算机的国家。 2009年年

13、10月月29日，我国首台千万亿次超级计算机系统日，我国首台千万亿次超级计算机系统“天天河一号河一号”由国防科学技术大学研制成功。该系统突破了多阵列可由国防科学技术大学研制成功。该系统突破了多阵列可配置协同并行体系结构、高速率可扩展互连通信、高效异构协同配置协同并行体系结构、高速率可扩展互连通信、高效异构协同计算、基于隔离的安全控制、虚拟化的网络计算支撑、多层次的计算、基于隔离的安全控制、虚拟化的网络计算支撑、多层次的大规模系统容错、系统能耗综合控制等一系列关键技术，系统峰大规模系统容错、系统能耗综合控制等一系列关键技术，系统峰值性能达每秒值性能达每秒1206万亿次双精度浮点运算，内存总容量万亿

14、次双精度浮点运算，内存总容量98TB，点，点点通信带宽每秒点通信带宽每秒40Gb，共享磁盘容量为，共享磁盘容量为1PB，具有高性能、高能，具有高性能、高能效、高安全和易使用等显著特点，综合技术水平进入世界前列。效、高安全和易使用等显著特点，综合技术水平进入世界前列。 “魔方”的诞生将中国的超级计算一下子带入了百万亿次计算时代，但是应用却仍停留在几万亿次到几十万亿次的水平，中间至少相差了一代。因为现在能够写此类软件的人才太过稀少，硬件跟软件的关系就像“修了一条好路，却没有好车”。一、并行处理机一、并行处理机1、概念：、概念： 并行处理机是将重复设置的并行处理机是将重复设置的N个处理单元，按一定个

15、处理单元，按一定方式互连组成阵列，在单一控制部件方式互连组成阵列，在单一控制部件CU控制下，同时对控制下，同时对处理单元各自分配到的数据并行完成同一条指令所规定处理单元各自分配到的数据并行完成同一条指令所规定的操作。又叫阵列处理机，的操作。又叫阵列处理机， 是典型的指令操作级并行的是典型的指令操作级并行的SIMD计算机计算机2、特点：特别适于求解向量、阵列类的计算问题、特点：特别适于求解向量、阵列类的计算问题阵列处理机阵列处理机：依靠处理单元的资源重复设置，利用的是：依靠处理单元的资源重复设置，利用的是并行性中的同时性；实现的是操作级的并行并行性中的同时性；实现的是操作级的并行解题专用性强，灵

16、活性差，处理单元的时间利用率低，解题专用性强，灵活性差，处理单元的时间利用率低，但提高速度的潜力大但提高速度的潜力大向量流水处理机向量流水处理机：依靠的是在系统同一套资源中各个处：依靠的是在系统同一套资源中各个处理机、部件、子部件在时间上的重叠使用，利用的是并理机、部件、子部件在时间上的重叠使用，利用的是并行性中的并发性行性中的并发性解题通用性强，灵活性好，流水线各部件的时间利用率解题通用性强，灵活性好，流水线各部件的时间利用率高，提高速度受到限制。高，提高速度受到限制。3、实质：异构型的多处理机系统、实质：异构型的多处理机系统专门进行向量专门进行向量/数组运算的处理单元阵列数组运算的处理单元

17、阵列专门进行标量运算和处理的控制处理机专门进行标量运算和处理的控制处理机CU专门进行输入输出和运行操作系统的管理处理机专门进行输入输出和运行操作系统的管理处理机SC互连网络特别重要，它规定了处理单元的连接模式，决定互连网络特别重要，它规定了处理单元的连接模式，决定了了SIMD能适应的算法类别能适应的算法类别4、并行处理机的构形、并行处理机的构形PEM0PEM1PEMN-1PE0PE1PEN-1ICNI/O接口接口DCUCUMSC分布式存储器的并行处理机构形分布式存储器的并行处理机构形:各处理单元的局部存储器只能被本处各处理单元的局部存储器只能被本处理单元直接访问；理单元直接访问；在在CU中有存

18、放程序和数据的主存储器；中有存放程序和数据的主存储器；ILLIAC 、MPP、DAP、CM-2、MP-14、并行处理机的构形、并行处理机的构形MM0MM1PEMN-1PE0PE1PEN-1ICNCUSC集中式共享存储器的并集中式共享存储器的并行处理机构形行处理机构形:系统存储器由系统存储器由N个存储个存储体集中组成，经互连网体集中组成，经互连网络络ICN为全部为全部N个处理单个处理单元所共享元所共享BSPI/O-CHI/OSM5、处理单元阵列结构（、处理单元阵列结构（以以ILLIAC 为例为例 ）PU1PU57PU0PU56PU7PU63PU8PU8PU9PU15PU56PU57PU63PU1

19、6PU0PU63PU7PU55PU0PU1PU7任意两个处理单元之间的最短距离不会超过任意两个处理单元之间的最短距离不会超过N-1步步闭合螺旋阵列闭合螺旋阵列闭合螺旋阵列闭合螺旋阵列PU1PU0PU3PU2PU4PU5PU7PU6PU12PU13PU15PU14PU8PU9PU10PU116、SIMD计算机的互连网络计算机的互连网络SIMD互连网络的互连网络的设计目标设计目标：结构要简单，以降低成本；结构要简单，以降低成本；连接要灵活，以满足算法和应用的需要；连接要灵活，以满足算法和应用的需要；中转传送的步数要少，以提高阵列运算速度；中转传送的步数要少，以提高阵列运算速度；规整性、模块性要好，

20、以便可以采用基本构件来组合，增规整性、模块性要好，以便可以采用基本构件来组合，增强系统的可扩充性，也便于大规模集成。强系统的可扩充性，也便于大规模集成。互连网络的连接规律可以用互连函数来表示，它反映了所互连网络的连接规律可以用互连函数来表示，它反映了所有有N个入端同时存在的入端个入端同时存在的入端j连至出端连至出端f（j）的函数关系。）的函数关系。XYZ000001101100111011010110N个节点的立方体单级网个节点的立方体单级网络共有络共有n = log 2 N 种互连种互连函数，函数，Cube i (P n-1P i P 1P 0 )= P n-1P i P 1P 0 最大距离

21、：最大距离：n，即反复使，即反复使用单级网络，最多经过用单级网络，最多经过n次传送就可以实现任意一次传送就可以实现任意一对入、出端间的连接。对入、出端间的连接。(1)、立方体单级网络、立方体单级网络基本的单级互连网络基本的单级互连网络(2)、PM2I单级网络单级网络PM2I单级网络是单级网络是“加减加减2 i”（Plus Minus 2 i ）单级）单级网络的简称。能实现与网络的简称。能实现与 j 号处理单元直接相连的是号号处理单元直接相连的是号为为 j 2 i 的处理单元。即：的处理单元。即：PM2 +i ( j ) = j + 2 i mod NPM2 -i ( j ) = j - 2 i

22、 mod N式中，式中，0 j N-1， 0 I n-1，n = log 2 N实际上实际上PM2I互连网络只有互连网络只有2n-1种不同的互连函数。种不同的互连函数。最大距离：最大距离：n / 2102435670213456702134567PM2 2PM2 +1PM2 +0(3)、混洗交换单级网络、混洗交换单级网络0213456702134567000001010011100101110111000001010011100101110111混洗交换单级网络混洗交换单级网络(Shuffle-Exchange)的连接规的连接规律是把全部按编码顺序排列的处理单元从当中律是把全部按编码顺序排列的

23、处理单元从当中分为数目相等的两半，前一半和后一半在连至分为数目相等的两半，前一半和后一半在连至出端时正好一一隔开。出端时正好一一隔开。Shuffle(P n-1P i P 1P 0 ) = P n-2P 1P 0 P n-1特性：不可逆；特性：不可逆； 每全混一次，新的最高位就被移至最低每全混一次，新的最高位就被移至最低位；当经过位；当经过 n 次全排列后，全部次全排列后，全部N各处理单元各处理单元便又恢复到最初的排列顺序。在多次全混的过便又恢复到最初的排列顺序。在多次全混的过程中，除了编号为全程中，除了编号为全“0”和全和全“1”的处理单元的处理单元外，各个处理单元都遇到了与其他多个处理单外

24、，各个处理单元都遇到了与其他多个处理单元连接的机会。元连接的机会。02134567全混交换单级网络全混交换单级网络在全混的基础上再增加在全混的基础上再增加Cube 0交换交换函数。函数。在全混交换单级网络中，最远的两个入、出端号是全在全混交换单级网络中，最远的两个入、出端号是全“0”和和“1”，它们的连接需要，它们的连接需要 n 次交换和次交换和 n-1 次混洗，所以最次混洗，所以最大距离为大距离为2n-1。单级网络单级网络只有有限的几种连接，因而在阵列机中必须经过只有有限的几种连接，因而在阵列机中必须经过多次循环，才能实现任意两个处理单元之间的信息传送。多次循环，才能实现任意两个处理单元之间

25、的信息传送。多级网络多级网络则是由多个单级网络组合而成，以实现任意两个则是由多个单级网络组合而成，以实现任意两个处理单元之间的连接。处理单元之间的连接。不同的多级网络表现在不同的多级网络表现在交换开关的功能交换开关的功能、拓扑结构拓扑结构和所用和所用的的开关控制方式开关控制方式上的不同。上的不同。交换开关交换开关：具有两个入端和两个出端的交换单元，用作各种多级互连：具有两个入端和两个出端的交换单元，用作各种多级互连网络的基本构件。网络的基本构件。拓扑结构：拓扑结构：指的是各级交换开关之间的连接模式，可以有立方体、混指的是各级交换开关之间的连接模式，可以有立方体、混洗、洗、PM2I或它们的组合或

26、它们的组合控制方式：控制方式：指的是对各个交换开关进行转切控制的方式。常分为三种：指的是对各个交换开关进行转切控制的方式。常分为三种：级控制、单元控制、部分级控制；级控制、单元控制、部分级控制；多级互连网络多级互连网络交换开关只有直连和交换两种功能的称为二功能交换交换开关只有直连和交换两种功能的称为二功能交换单元单元;交换开关可以有直连、交换、上播和下播等四种功能交换开关可以有直连、交换、上播和下播等四种功能的称为四功能交换单元的称为四功能交换单元;i入入j入入i出出j出出直连直连i 入连入连 i 出出, j 入连入连 j 出出交换交换i 入连入连 j 出出, j 入连入连 i 出出上播上播i

27、 入连入连i 出和出和 j 出出, j 入空入空下播下播j 入连入连i 出和出和 j 出出, i 入空入空多级立方体网络多级立方体网络ABCDEFGHIJKL01234567012345670213465702134657041526370123456704152637STARAN网络网络：第第 i 级交换单元级交换单元处于交换状态时，处于交换状态时，实现的是实现的是Cube i 互连函数，且都互连函数，且都采用二功能交换采用二功能交换单元，和级控制单元，和级控制方式。方式。0级级1级级2级级0级级1级级2级级3级级0123456789ABCDEF98AB54671023DCEF6453012

28、7ECDB89AF08192A3B4C5D6E7F0123674589EFABCDN=16n =log2N=4每一级每一级N/2个个二功能交换二功能交换开关开关级控制信号（级控制信号（K3K2K1K0）101011001011输输入入端端0 (0000)1 (0001)2 (0010)3 (0011)4 (0100)5 (0101)6 (0110)7 (0111)8 (1000)9 (1001)A (1010)B (1011)C (1100)D (1101)E (1110)F (1111)AB89EF (1111)C (1100)D (1101)2 (0010)3 (0011)0 (0000)

29、1 (0001)674 (0100)55 (0101)B (1011)A (1010)9 (1001)8 (1000)F (1111)E (1110)D (1101)C (1100)321076544组组4元元3210，7654，BA98，FEDC;2组组8元元45670123，CDEF89AB;1组组16元元BA98FEDC32107654ABCDEFGHIJKL01234567024613570123456701234567omega网络：网络：由由n级相同的网级相同的网络组成，每一级络组成，每一级都包含一个全混都包含一个全混拓扑和随后一列拓扑和随后一列2 n-1个四功能交个四功能交换单元，采用单换单元，采用单元控制方式。元控制方式。0级级1级级2级级多级混洗交换网络多级混洗交换网络 omega网络网络0415263701230A00A01A02A031A10A11A12A132A20A21A22A233A30A31A32A33012340A00A01A02A031A13A10A11A122A21A22A23A203A30A31A3