第2讲-并行计算机系统及其结构模型

1计算机学院计算机科学与技术系主讲：陈蕾博士/副教授E-mail:chenlei@第二讲并行计算机系统及其结构模型2并行计算的研究内容IssuesinParallelComputing

并行计算的研究内容广泛，包括并行计算机系统结构、并行算法设计、并行编程环境等，具体表现在下面几个方面：（1）并行计算机的设计

DesignofParallelComputers包括并行计算机的结构设计、互联拓扑、网络通信等。设计并行计算机重要的一点要考虑处理机数目的按比例增长（即可扩展性）及支持快速通信及处理机间的数据共享等。3(2)有效算法的设计

DesignofEfficientAlgorithms如果没有有效的并行算法，并行计算机无法使用，而并行算法的设计完全不同于串行算法的设计，不同的并行计算机的算法设计不同，只有将不同的并行计算机与不同的实际问题相结合，才能设计出有效的并行算法。主要研究内容包括并行计算模型、并行算法的一般设计方法、基本设计技术和一般设计过程，并讨论一些数值并行算法与非数值并行算法的设计。4(3)评价并行算法的方法

MethodsforEvaluatingParallelAlgorithms

对于给定的并行计算机及运行在上面的并行算法，需要评价运行性能。性能分析需解决的问题：如何利用基于并行计算机及其相适应的并行算法去快速地解决问题，及如何有效地利用各个处理器。研究内容包括结合机器与算法，提出相应的性能评测指标，为设计高效的并行算法提供依据。5(4)并行计算机语言

ParallelComputingLanguage

与传统的机器语言不同，并行计算机语言依赖于并行计算机，并行计算机语言必须简洁，编程容易，可以有效地实现，目前的语言有：PVM（ParallelVirtualMachine）、MPI(MessagePassingInterface)、HPF(HighPerformanceFortran)等，而且新的编程语言与编程模式正在不断地出现。6(5)并行编程环境与工具

ParallelProgrammingEnvironmentsandTools为了使编程容易，必须开发综合的编程环境与工具，且能达到两个目的：并行计算机的底层结构对用户透明；为用户提供设计与开发程序所需要的调试器与模拟器等工具7(6)并行程序的可移植性

PortableParallelPrograms可移植性为并行程序设计的主要问题，要求在一台并行机上开发的程序不加修改或进行少量修改即可在另一台计算机上运行。这一点为目前受到了广泛关注的重要课题。8(7)并行计算机的自动编程

AutomaticProgrammingofParallelComputers

可否设计一个并行化编译器，使用户的串行程序通过并行化编译器编译，直接可在并行机上运行。到目前为此，这种编译器还不存在，而仅有一些半自动并行化编译器。9并行计算机分类

对并行计算机的分类有多种方法，其中最著名的是1966年由M.J.Flynn提出的分类法，称为Flynn分类法。Flynn分类法是从计算机的运行机制进行分类的。首先作如下定义：

指令流（instructionstream）：机器执行的指令序列；

数据流（datastream）：由指令流调用的数据序列，包括输入数据和中间结果。

10Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类：

（1）单指令流单数据流（SingleInstructionstreamSingleDatastream,SISD）；

（2）单指令流多数据流（SingleInstructionstreamMultipleDatastream,SIMD）；

（3）多指令流单数据流（MultipleInstructionstreamSingleDatastream,MISD）；

（4）多指令流多数据流（MultipleInstructionstreamMultipleDatastream,MIMD）。SISD就是普通的顺序处理的串行机。SIMD和MIMD是典型的并行计算机。MISD在实际中代表何种计算机，也存在不同的看法，甚至有学者认为根本不存在MISD。

11单指令流多数据流机SIMD

在一台SIMD计算机中，有一个控制部件（又称为控制单元，controlunit）和许多处理单元（processingunit）。大量的处理单元通常构成阵列，因此SIMD计算机有时也称为阵列处理机。所有的处理单元在控制部件的统一控制下工作。控制部件向所有的处理单元广播同一条指令，所有的处理单元同时执行这条指令，但是每个处理单元操作的数据不同。控制部件可以有选择地屏蔽掉一些处理单元，被屏蔽掉的处理单元不执行控制部件广播的指令。12SIMD计算机其结构如下图所示，其中PE表示处理单元，P表示处理器，M表示存储器。

SIMD中通常包含大量处理单元PE，而控制部件只有一个。控制部件广播一条指令，所有的处理单元同时执行这条指令，但不同的处理单元操作的数据可能不同。

13典型的SIMD计算机-MasParMP-1可有1024，4096，…，16384个处理器。在16k个处理器，32位整数运算，16kB局部存储器模块的配置下，1.5GFlops.单指令流多数据流机SIMD

14多指令流多数据流机MIMD在MIMD计算机中没有统一的控制部件。在MIMD中，各处理器可以独立地执行不同的指令。实际上，在SIMD机中，各处理单元执行的是同一个程序，而在MIMD机上，各处理器可以独立执行不同的程序。在MIMD中，每个处理器都有控制部件，各处理器通过互连网络进行通信。MIMD结构比SIMD结构更加灵活。SIMD计算机通常要求实际问题包含大量的对不同数据的相同运算（例如向量运算和矩阵运算）才能发挥其优势。而MIMD计算机则无此要求，它可以适应更多的并行算法，因此可以更加充分地开掘实际问题的并行性。SIMD所使用的CPU通常是专门设计的，而MIMD可以使用通用CPU。15

多指令流多数据流机MIMD多指令流多数据流机MIMD一般可以分为5类：

1、并行向量处理机PVP（ParallelVectorProcessor）

2、对称多处理机SMP（SymmetricMultiprocessor）

3、大规模并行处理机MPP（MassivelyParallelProcessor）

4、工作站机群COW（ClusterOfWorkstations，也称为NetworkOfWorkstations，NOW）

5、分布式共享存储多处理机DSM（DistributedSharedMemory）。

16并行向量处理机PVP在并行向量处理机中有少量专门定制的向量处理器。每个向量处理器有很高的处理能力。并行向量处理机通过向量处理和多个向量处理器并行处理两条途径来提高处理能力。CrayC-90、CrayT-90、NECSX-4和我国的银河1号都是PVP。PVP通常使用定制的高带宽网络将向量处理器连向共享存储器模块。存储器可以以很高的速度向处理器提供数据。例如，在CrayT-90中，共享存储器能以14GB/s的速率将数据提供给一个处理器。这种机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。17并行向量处理机其系统结构如下图所示。图中VP表示向量处理器，SM表示共享存储器。

18对称多处理机SMP对称多处理机的最大特点是其中的各处理器完全平等，无主从之分。所有的处理器都可以访问任何存储单元和I/O设备。存储器一般使用共享存储器，只有一个地址空间。因为使用共享存储器，通信可用共享变量（读写同一内存单元）来实现。这使得编程很容易。对称多处理机（SymmetricMultiprocessor,SMP）结构在现今的并行服务器中普遍采用。它是应用得最广泛的并行计算机，例如曙光1号、HP9000/T600、IBMRS6000/R40、SGIPowerChallengeXL、SUNUltraEnterprise6000等。采用商用微处理器，通常有片上和外置Cache，基于总线或交叉开关连接，集中式共享存储

19SMP的结构如下图所示。P/C表示处理器和高速缓存，SM表示共享存储器。20对称多处理机SMP优点对称性单地址空间，易编程，动态负载平衡，无需显式数据分配高速缓存及其一致性，硬件维持一致性低通信延迟问题所有的处理器都可以访问存储器和I/O设备，使得存储器和I/O设备的负载很大，容易成为系统的瓶颈，这限制了系统中处理器的数量。可用性：总线、存储器、操作系统中有一个失效就会导致整个系统的崩溃，系统不够可靠和稳定。不可扩放性：总线和交叉开关一旦做成就难以扩展。21

大规模并行处理机（MPP）大规模并行处理机（MassivelyParallelProcessor,MPP）是指由几百或几千台处理机组成的大规模并行计算机系统。Intel和美国Sandia国家实验室1997年6月研制成功的MPP系统ASCIOptionRed有9216个处理器。MPP系统中处理器数目巨大，整个系统规模庞大，许多硬件设备是专门设计制造的，开发起来比较困难，通常被视为国家综合实力的象征。同时，MPP能够提供其它并行计算机不能达到的计算能力。达到3T性能目标和解决重大挑战性课题都寄希望于MPP。大规模并行处理机一般指规模非常大的并行计算机系统，含有成千上万个处理器。它一般采用分布式存储器，存储器一般为处理器私有，各处理器之间用消息传递的方式通信。大规模并行处理机的互连网络一般是专门设计定制的。典型的MPP有IntelParagon、IBMSP2以及OptionRed、曙光1000等。

22处理节点采用商用微处理器专门设计制造的高速互连网络每个节点内有一个或多个处理器、高速缓存、一个本地存储器和本地互连网络，有的MPP系统节点内还有磁盘存储器在物理上是分布的，而且都是私有的程序由多个进程组成，每个都有其私有空间，进程间采用消息传递相互作用

大规模并行处理机（MPP）23典型MPP系统特性比较MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一个大型样机的配置9072个处理器，1.8Tflop/s(NSL)400个处理器，100Gflop/s(MHPCC)128个处理器，51Gflop/s(NCSA)问世日期1996年12月1994年9月1996年10月处理器类型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBMUNIX）微内核CellularIRIX自然编程机制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM24MPP所用的高性能CPU特性比较属性PentiumProPowerPC602Alpha21164AUltraSPARCIIMIPSR10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数5.5M/15.5M7M9.6M5.4M6.8M时钟频率150MHz133MHz417MHz200MHz200MHz电压2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字长32位64位64位64位64位I/O高速缓存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2级高速缓存256KB(多芯片模块)1~128MB(片外)96KB(片上)16MB(片外)16MB(片外)执行单元5个单元6个单元4个单元9个单元5个单元超标量3路(Way)4路4路4路4路流水线深度14级4~8级7~9级9级5~7级SPECint92366225>500350300SPECfp92283300>750550600SPECint958.09225>11N/A7.4SPECfp956.70300>17N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU25MPP的结构如下图所示。其中MB表示存储器总线，P/C表示处理器和高速缓存，NIC表示网络接口电路，LM表示本地存储器。NIC是用来将计算机与网络（例如局域网）连接起来的接口电路。它的功能有：将消息格式化、路由选择、流和错误控制等。26分布式共享存储器多处理机DSM分布式共享存储器多处理机的主要特点是它的存储器在物理上是分布在各个结点中的，但是通过硬件和软件为用户提供一个单一地址的编程空间，即形成一个虚拟的共享存储器。DSM相对于MPP的优越性是编程较容易。它通过高速缓存目录支持分布高速缓存的一致性。DSM与SMP的区别在于各结点内有存储器，与MPP的区别在于存储器在逻辑上是共享的。典型的DSM有StanfordDASH、SGI/CrayOrigin2000。27DSM的结构如下图所示，其中DIR表示高速缓存目录，其它符号同前。

28工作站机群（COW）1994年,NASA两位工程师构建了第一个机群系统:Beowulf16台100MHz486微机10Mb/s以太网络74Mflops1997年,UCBerkeleyNOW-2100台SUN工作站Myrinet10Gflops首次进入Top500最新的Top500中，机群占81%29典型的机群系统结构30工作站机群COW分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好问题通信性能并行编程环境例子：BerkeleyNOW，AlphaFarm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN31工作站机群

工作站机群是一种新兴的并行系统。COW是由高档商品微机（包括工作站）用高速商品互连网络（有的商用机群也使用定制的网络）连接而成。COW的每个结点都是一台完整的计算机（可能没有鼠标、显示器等外设）。COW的每个结点上都有完整的操作系统，而MPP的每个结点上通常只有操作系统的微核。COW的每个结点内有本地磁盘，而MPP的结点内没有。COW各结点的网络接口是连接到I/O总线上的（松耦合），而MPP各结点的网络接口是连接到存储总线上的（紧耦合）。32COW的结构如下图所示，其中LD表示本地磁盘，B