第6章并行处理机

高性能计算机发展历程

自1964年以后,高性能计算机经历了三个发展阶段:

萌芽阶段、向量机鼎盛阶段和大规模并行处理机（MPP）蓬勃发展阶段。

1.萌芽阶段（1964-1975）

1964年诞生的CDC6600被公认为世界上第一台巨型计算机，其运算速度为1Mflops。70年代初研制成功STAR-100向量机，这是世界上最早的向量机。随后于1974年，诞生了世界上最早的SIMD阵列计算机--ILLIAC-IV并行机。2.向量机鼎盛阶段（1976-1990）

1976年，CRAY公司推出CRAY-1向量机，开始了向量机的蓬勃发展，其峰值速度为0.1Gflops.

1985年，CRAY-2，1Gflops

1990年，SX-3，22Gflops

1991年，Cray-YMP-C90，16Gflops

向量机处理对提高计算机运算速度十分有利，有利于流水线的充分利用，有利于多功能部件的充分利用，但由于时钟周期已接近物理极限，向量计算机的进一步发展已经不太可能。3.MPP（massivelyparallelprocessing

蓬勃发展阶段（1990年至今）

就在传统向量机逐渐萎缩的同时，迎来了大规模并行处理MPP机蓬勃发展的时代。各种新技术层出不穷，大公司也纷纷介入。这一时期的代表机型有：

1989年，BBN公司的TC2000

1992年，Intel公司的Paragon，TMC公司的CM-5

1993年，Cray公司的T3D

1994年，IBM公司的SP2

1996年，Cray公司的T3E，Hitachi公司的SR2201，SGI公司的Origin2000，Intel公司的ASCERED。其中，1996年12月宣布的ASCIRED，运算速度超过了万亿次/秒。银河-I巨型计算机1983年12月银河-II巨型计算机1992年11月银河-II主机为我国高性能向量中央处理机共享主存紧耦合系统，基本字长64位，峰值速度为每秒10亿次以上运算操作，拥有两个独立的输入输出子系统。各项技术指标达到了八十年代中后期国际先进水平。银河-III巨型计算机

1997年6月银河III采用分布共享存储结构，峰值性能达到每秒130亿浮点运算。具有良好的可扩展性，银河III在MPP资源管理与处理机调度、并行I/O软件、高性能优化编译、网络软硬件设计等技术方面均达到国内领先水平，系统综合技术达到当时国际先进水平。我国超级计算机的发展和应用

曙光一号并行计算机是1993年我国自行研制的第一台用微处理器芯片（88100微处理器）构成的全对称紧耦合共享存储多处理机系统（SMP），最大支持16个CPU（4CPU共享存储为一结点主板，4个主板通过VME总线连接），系统外设采用SCSI设备，系统峰值定点速度每秒6.4亿，主存容量最大768MB。在对称式体系结构、操作系统核心代码并行化和支持细粒度并行的多线程技术等方面实现了一系列的技术突破。硬件的技术突破包括多处理机共享内部总线协议设计、多机中断控制器芯片设计等；软件包括SNIX(SymmetricuNIX)操作系统采用的细粒度加锁以及动态分配I/O中断向量以实现多机系统对称式处理的方法；在UNIX核心中增加共享资源进程以及成群调度(GangScheduling)策略，在用户空间以库函数的方式实现线程(Threads)概念，支持中微粒度的并行计算等。“神威”巨型计算机 1999年8月“神威”计算机有384个CPU，内存总容量为48GB，峰值运行速度达到了每秒3840亿次。国家最高科学技术奖2010年

师昌绪（著名材料科学家）王振义（血液学专家）

2009年

谷超豪（著名数学家）孙家栋（运载火箭与卫星技术专家）

2008年

王忠诚（神经外科专家）徐光宪（化学家）

2007年

闵恩泽（石油化工催化剂专家）吴征镒（著名植物学家）

2006年

李振声（遗传学家，小麦远缘杂交的奠基人）2005年

叶笃正（世界著名气象学家），吴孟超（世界著名肝脏外科学家）2004年空缺2003年

刘东生（著名地球环境科学家）王永志（著名航天技术专家）

2002年金怡濂（高性能计算机领域的著名专家）

2001年王选（汉字激光照排系统创始人）黄昆（著名物理学家）2000年吴文俊（世界著名数学家）袁隆平（杂交水稻之父）

2009年6月15日，国内首台百万亿次超级计算机“魔方”，在上海正式启用。“魔方”不但是亚洲第一的超级计算机，也是目前美国本土之外唯一计算速度排名进入全球前十的超级计算机，表明中国成为全球第二个能够研发百万亿次超级计算机的国家。2009年10月29日，我国首台千万亿次超级计算机系统——“天河一号”由国防科学技术大学研制成功。该系统突破了多阵列可配置协同并行体系结构、高速率可扩展互连通信、高效异构协同计算、基于隔离的安全控制、虚拟化的网络计算支撑、多层次的大规模系统容错、系统能耗综合控制等一系列关键技术，系统峰值性能达每秒1206万亿次双精度浮点运算，内存总容量98TB，点点通信带宽每秒40Gb，共享磁盘容量为1PB，具有高性能、高能效、高安全和易使用等显著特点，综合技术水平进入世界前列。

“魔方”的诞生将中国的超级计算一下子带入了百万亿次计算时代，但是应用却仍停留在几万亿次到几十万亿次的水平，中间至少相差了一代。因为现在能够写此类软件的人才太过稀少，硬件跟软件的关系就像“修了一条好路，却没有好车”。一、并行处理机1、概念：并行处理机是将重复设置的N个处理单元，按一定方式互连组成阵列，在单一控制部件CU控制下，同时对处理单元各自分配到的数据并行完成同一条指令所规定的操作。又叫阵列处理机，是典型的指令操作级并行的SIMD计算机2、特点：特别适于求解向量、阵列类的计算问题阵列处理机：依靠处理单元的资源重复设置，利用的是并行性中的同时性；实现的是操作级的并行解题专用性强，灵活性差，处理单元的时间利用率低，但提高速度的潜力大向量流水处理机：依靠的是在系统同一套资源中各个处理机、部件、子部件在时间上的重叠使用，利用的是并行性中的并发性解题通用性强，灵活性好，流水线各部件的时间利用率高，提高速度受到限制。3、实质：异构型的多处理机系统专门进行向量/数组运算的处理单元阵列专门进行标量运算和处理的控制处理机CU专门进行输入输出和运行操作系统的管理处理机SC互连网络特别重要，它规定了处理单元的连接模式，决定了SIMD能适应的算法类别4、并行处理机的构形PEM0PEM1PEMN-1PE0PE1PEN-1ICNI/O接口DCUCUMSC分布式存储器的并行处理机构形:各处理单元的局部存储器只能被本处理单元直接访问；在CU中有存放程序和数据的主存储器；ILLIACⅥ、MPP、DAP、CM-2、MP-14、并行处理机的构形MM0MM1PEMN-1PE0PE1PEN-1ICNCUSC集中式共享存储器的并行处理机构形:系统存储器由N个存储体集中组成，经互连网络ICN为全部N个处理单元所共享BSPI/O-CHI/OSM5、处理单元阵列结构（以ILLIAC

Ⅵ为例）PU1PU57PU0PU56PU7PU63PU8PU8PU9PU15PU56PU57PU63PU16PU0PU63PU7PU55PU0PU1PU7任意两个处理单元之间的最短距离不会超过√N-1步闭合螺旋阵列闭合螺旋阵列PU1PU0PU3PU2PU4PU5PU7PU6PU12PU13PU15PU14PU8PU9PU10PU116、SIMD计算机的互连网络SIMD互连网络的设计目标：结构要简单，以降低成本；连接要灵活，以满足算法和应用的需要；中转传送的步数要少，以提高阵列运算速度；规整性、模块性要好，以便可以采用基本构件来组合，增强系统的可扩充性，也便于大规模集成。互连网络的连接规律可以用互连函数来表示，它反映了所有N个入端同时存在的入端j连至出端f（j）的函数关系。XYZ000001101100111011010110N个节点的立方体单级网络共有n=log2N种互连函数，Cubei(Pn-1…Pi…P1P0)=Pn-1…Pi…P1P0

最大距离：n，即反复使用单级网络，最多经过n次传送就可以实现任意一对入、出端间的连接。(1)、立方体单级网络基本的单级互连网络(2)、PM2I单级网络PM2I单级网络是“加减2i”（Plus–Minus2i）单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单元。即：PM2+i(j)=j+2imodNPM2-i(j)=j-2imodN式中，0≤j≤N-1，0≤I≤n-1，n=log2N实际上PM2I互连网络只有2n-1种不同的互连函数。最大距离：「n/2」102435670213456702134567PM2±2PM2+1PM2+0(3)、混洗交换单级网络0213456702134567000001010011100101110111000001010011100101110111混洗交换单级网络(Shuffle-Exchange)的连接规律是把全部按编码顺序排列的处理单元从当中分为数目相等的两半，前一半和后一半在连至出端时正好一一隔开。Shuffle(Pn-1…Pi…P1P0)=Pn-2…P1P0Pn-1特性：不可逆；每全混一次，新的最高位就被移至最低位；当经过n次全排列后，全部N各处理单元便又恢复到最初的排列顺序。在多次全混的过程中，除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会。02134567全混交换单级网络——在全混的基础上再增加Cube0交换函数。在全混交换单级网络中，最远的两个入、出端号是全“0”和“1”，它们的连接需要n次交换和n-1次混洗，所以最大距离为2n-1。单级网络只有有限的几种连接，因而在阵列机中必须经过多次循环，才能实现任意两个处理单元之间的信息传送。多级网络则是由多个单级网络组合而成，以实现任意两个处理单元之间的连接。不同的多级网络表现在交换开关的功能、拓扑结构和所用的开关控制方式上的不同。交换开关：具有两个入端和两个出端的交换单元，用作各种多级互连网络的基本构件。拓扑结构：指的是各级交换开关之间的连接模式，可以有立方体、混洗、PM2I或它们的组合控制方式：指的是对各个交换开关进行转切控制的方式。常分为三种：级控制、单元控制、部分级控制；多级互连网络交换开关只有直连和交换两种功能的称为二功能交换单元;交换开关可以有直连、交换、上播和下播等四种功能的称为四功能交换单元;i入j入i出j出直连——i入连i出,j入连j出交换——i入连j出,j入连i出上播——i入连i出和j出,j入空下播——j入连i出和j出,i入空多级立方体网络ABCDEFGHIJKL01234567012345670213465702134657041526370123456704152637STARAN网络：第i级交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元，和级控制方式。0级1级2级0级1级2级3级0123456789ABCDEF98AB54671023DCEF64530127ECDB89AF08192A3B4C5D6E7F0123674589EFABCDN=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)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级相同的网络组成，每一级都包含一个全混拓扑和随后一列2n-1个四功能交换单元，采用单元控制方式。0级1级2级多级混洗交换网络omega网络0415263701230A00A01A02A031A10A11A12A132A20A21A22A233A30A31A32A33012340A00A01A02A031A13A10A11A122A21A22A23A203A30A31A32A337、并行存储器的无冲突访问（以二维数组为例）要求：对于二维数组的行、列、主对角线、次对角线都能够实现无冲突访问。实现：同一行两个相邻元素在并行存储器中错开的距离为1；同一列两个相邻元素在并行存储器中错开的距离为2p；并行存储体的分体数m为：22p+1存储器PE存储器PEPEPEPEPEPE

脉动阵列机脉动结构是由一组处理单元PE构成的阵列。每个PE的内部结构相同，功能比较简单。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时，数据在阵列结构的各个处理单元间沿各自的方向，同步地向前推进。阵列内部的各个单元只接收前一