并行算法研究现状及其相关问题

并行程序的编程模型、运行环境、调试环境等都要比串行程序复杂得多。提供良好的高性能计算开发环境，一直是学术界和工业界所追求的目标。这里的开发环境既包括并行计算机体系结构，计算机网络拓扑结构等硬件环境；也包括并行程序的开发模式，网络通信协议和通信方式等软件环境。并行算法研究要以硬件，即并行计算机为依托，并行计算机性能的发挥要依靠优秀并行算法的设计的实现。

所以本文，并行算法研究现状及其相关问题的综述，将对与并行紧密相关的并行计算机体系结构，并行程序开发环境，通信技术三个问题依次进行讨论。

一、     并行计算机体系结构

“ 并行计算机是由一组处理单元组成的；这组处理单元通过相互之间的通 信与协作，以更快的速度共同完成一项大规模的计算任务。”这就是并行计算机的经典定义。这个定义并没有包含更多的细节，但是从中我们也不难看出并行计算机的两个最主要的组成部分：计算节点和节点间的通信与协作机制。

并行计算机体系结构的发展变化非常快，而这种变化主要体现在计算节点 性能的提高以及节点间通信技术的改进两方面。长期以来，超大规模集成电路技 术一直在按照摩尔定律高速发展，芯片的元件密度以及时钟频率在不断提高，从 而大大提高了作为并行计算机基本处理单元的微处理器的性能。而在通信技术 方面， 传统的交叉开关的切换速度不断提高，而新的高速网络技术也不断应用 到并行计算机中，从而大大提高了节点间通信的速率。

（一）体系结构的分类
1972年，Micheal Flynn根据指令和数据流的概念对计算机的体系结构进行了分类，这就是所谓的Flynn分类法。

Flynn将计算机划分为四种基本类型，即SISD、MIMD、SIMD、MISD。

传统的顺序执行的计算机在同一时刻只能执行一条指令（即只有一个控制流）、处理一个数据（即只有一个数据流），因此被称为单指令流单数据流计算 机（Single Instruction Single Data即SISD计算机）。而对于大多数并行计算机而言，多个处理单元都是根据不同的控制流程执行不同的操作，处理不同的数据，因此，它们被称作是多指令流多数据流计算机，即MIMD（Multiple Instruction Multiple Data）计算机。

曾经在很长一段时间内成为超级并行计算机主流的向量计算机除了标量处理单元之外，最重要的是具有能进行向量计算的硬件单元。在执行向量操作时， 一条指令可以同时对多个数据（组成一个向量）进行运算，这就是单指令流多数 据流（Single Instruction Multiple Data，SIMD）的概念。因此，我们将向量计算机称SIMD计算机。

第四种类型即所谓的多指令流单数据流（Multiple Instruction Single Data）计算机。在这种计算机中，各个处理单元组成一个线性阵列，分别执行不同的指令流，而同一个数据流则顺次通过这个阵列中的各个处理单元。这种系统 结构只适用于某些特定的算法。

相对而言，SIMD和MISD模型更适合于专用计算。 在并行计算机中，MIMD模型最为通用，SIMD次之，而MISD最少用。

(二)体系结构的发展过程
并行计算机40年的发展过程中出现过许多著名的机器。

60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，并迎 来了它的第一个黄金时代。

这一时期的并行计算机多是规模不大的共享存储多处理器系统，不过，当时它们可是被当作大型主机（Mainframe）来看待的。Burroughs B5000, D825以及IBM System 360是这一时期的典型代表。其中，IBM System 360在过渡到370系列时引入了多处理机的概念，而CDC 6600则在中央处理器与多个I/O处理器 之间采用了异步共享存储器的机制。与这些机器有所不同的是，RW400则是最早 采用消息传递机制的大型主机。

到了60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用 大大提高了并行计算机系统的性能。

伊利诺依大学和Burroughs公司此时开始了一项庞大的工程，即Illiac IV 计划。他们认为，当时已有的技术已经走到尽头了，因此决定另辟蹊径。根据这一规划，Illiac IV 应该是一台64个CPU的SIMD主机系统，它涉及到从最底层 的硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内 的众多研究课题。不过，当一台规模大大缩小了的16 CPU系统终于在1975年露 出了它的庐山真面目的时候，整个计算机界已经发生了巨大的变化。

首先是存储系统概念的彻底革新。虚拟存储和缓存这两个概念现在已经应用在了几乎所有的计算机系统里，但在70年代初期，它们却带来一场真正的革 命。 IBM 360/85系统与360/91是属于同一系列的两个机型，360/91的主频高于360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线；但是，360/85的整体性能却高于360/91，唯一的原因就是前者采用了缓存技术，而后者则没有。

其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器中被用作缓存，而CDC 7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到了计算机中。元器件技术的这两大革命性突破，使 得Illiac IV的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。

Illiac IV原本是想解决数值计算中向量运算密集的问题的，不过，这个任 务却是由这一时期诞生的最早的向量流水线计算机CDC STAR 100完成的。而到 了1976年CRAY 1问世以后，一个长达15年的新时代开始了，向量计算机从此牢牢地控制着整个高性能计算机市场。CRAY 1对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使CRAY 1的主频达到了令时人不可思议的80 MHz。

微处理器的出现则使并行计算机的体系结构迈出了另一大步。最早的微处理器性能并不是很理想，但是随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基梅隆大学开始在当时流行的DEC PDP 11小型计算机的基础上进行共享存储多处 理器系统的研究。C.mmp就是这一研究项目的具体成果。它是一台由16个PDP 11/40处理机通过交叉开关与16个共享存储器模块相连接而成的。

从80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache 一致性问题的处理方案。从此，C.mmp开创出的共享存储多处理器之路越走越 宽；到了10年之后的今天，这种体系结构已经基本上统治了服务器和桌面工作站市场。

同一时期，基于消息传递机制的并行计算机也开始不断涌现。80年代中期， 加州理工成功地将64个i8086/i087处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。

向量计算机渐渐衰落下去。数据并行方式的计算机在相对沉寂了一段时间之后，到了80年代中期又开始逐渐复兴。这一时期数据并行方式的计算机主要 有Goodyear MPP，Thinking Machines的CM 1、CM 2以及MasPar等。在互连机 制方面，这一代机器不仅仅限制在相邻的节点之间，而是可以根据需要在任意节点之间进行通信。CM 2则更是具备了大量的浮点单位并行（Bit parallel）运算单元。

80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的 发展。IBM公司在RP 3计划中希望能将大量早期RISC微处理器通过蝶形互连网 络连结起来。而BBN公司则先后推出了两个型号的这类机器，即采用Motorola 68000芯片的BBN Butterfly以及采用88100芯片的TC2000。通过这些尝试，人 们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可 扩展性（Scalability）。90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。MIT的Alewife 计划则试图简化为保持缓存一致性而带来的硬件开销。

90年代以来，主要的几种体系结构开始走向融合，这种趋势有其内在的必然性。为了获得更好的性能，在Alewife以及FLASH等共享存储类型的项目中也引入了消息传递机制；而属于数据并行类型的CM 5除大量采用商品化的微处理 器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA结构 的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术；Meiko CS 2采用的是消息传递机制，但是， 一个节点上用户程序虚地址空间内的数据却可以直接复制到另一个节点上另一个程序的虚地址空间里去，实际上这正是共享地址空间机制的特点。

不过IBM近年来大获成功的SP 1、 SP 2系列机群系统走的则是另外一条路 线。在这些系统中，各个节点采用的都是标准的商品化Unix工作站（RS 6000）， 它们之间通过高速网络连接起来。各节点内存系统之间没有多少联系，网络连接的可靠性也不高，面向的是通用的应用领域。因此，从总体上说，SP 1、SP 2基本上属于消息传递型系统。

目前的并行计算机系统主要有四类:第一类是多向量处理系统, 如Cray YMP 90、NEC SX 3 和Fujitsu VP 2000 等；第二类是基于共享存储的多处理机（SMP） 系统,如SGI Power Challenge、曙光1号等；第三类是基于分布存储的大模并行处理(MPP)系统,如Intel Paragon、IBM SP2、曙光1000等；第四类是基于RISC 工作站或高档微机通过高速互连网络连接而构成的机群计算机系统，如清华同 方探索集群计算机等。

展望

实现上述第一和第三类系统由于受研制费用高、售价高等因素的影响,其市场受到一定的限制。第二类系统由于共享结构的限制,系统的规模不可能很大。 由于机群系统计算机具有投资风险小、可扩展性好、可继承现有软硬件资源和开发周期短、可编程性好等特点，目前已成为并行处理的热点和主流。据专家预测：“未来的高性能计算机和超级服务器都将基于机群系统结构”。

二、     并行程序开发环境

目前比较流行的高性能计算系统，大体可以分为两类:一类是共享内存系统(SMP)，如IBM的P690，HP的SuperDome等，其特点是多个处理器拥有物理上共享的内存；一类是分布存储系统(DMP)，如MPP和集群系统，其特点是系统由多个物理上分布的结点组成，每个结点拥有自己的内存，结点通过高速以太网或专用高速网络连接。下面将介绍这两类系统上的开发工具。

（一）并行程序的开发模式

1.   共享内存模型

在共享内存模型中，一个并行程序由多个共享内存的并行任务组成，数据的交换通过隐含地使用共享数据来完成。此编程模式一般仅需指定可以并行执行的循环，而不需考虑计算与数据如何划分，以及如何进行任务间通信，编译器会自动完成上述功能。

由于分布式存储系统与集中式存储系统各有优缺点, 所以目前的趋势是将两者结合：系统含有上千个的处理器，虽然内存物理上分布于各个处理器上，但在逻辑上给用户提供统一的共享地址空间。这就是分布式共享存储系统(Distributed Shared Memory: DSM)[14]。简单的说，分布式共享存储系统就是在逻辑上给用户提供统一的共享地址空间，提供共享存储的编程模式，无须考虑在物理上各个存储模块是分布的。分布式共享存储系统以其方便的编程接口及良好的可扩展性而越来越受到学术界和工业界的极大关注，从而成为高性能计算机体系结构发展的主流。

分布式共享存储系统包括两类: 一类是由底层硬件实现的，具有统一的物理地址空间的系统。目前的共享存储型MPP机器多采用这种结构。另一类是由上层软件实现的，具有统一的虚拟地址空间的系统，这一类称为称为虚拟共享存储系统（Shared Virtual Memory：SVM）, 又称为软件分布式共享存储系统（Software DSM：SDSM）。其中有代表性的系统有Yale 大学的Ivy，Rice大学的 TreadMarks， Munin，Maryland 大学的 CVM，Carnegie Mellon 大学的 Midway，中科院计算所高性能计算机研究中心的JIAJIA 系统。

处理机1

处理机2

处理机n

本地存储器

本地存储器

 

本地存储器

 

虚拟共享存储层

 

虚拟共享存储层

 

虚拟共享存储层

 

虚拟共享存储地址空间

 

 

一个简单的虚拟共享存储系统如图1所示。 所有的处理机可以共享由虚拟共享存储系统提供的统一地址空间, 从程序员的角度来看，任何处理机可以访问整个地址空间的任何变量而无需考虑该变量位于哪个处理机上。每个处理机都有一个虚拟共享存储层，这个虚拟共享存储层不仅要负责本地存储器与虚拟共享地址空间的映射， 而且还要在本机发生共享数据不命中时， 到远地将所需数据取回，             图1：一个简单的虚拟共享存储系统

并及时维护整个地址空间的一致性。

目前流行的共享内存模型开发标准是OpenMP。OpenMP定义了一套编译指导语句，用于指定程序的并行性、数据的共享/私有等信息。其目标是为SMP系统提供可移植、可扩展的开发接口。OpenMP由OpenMP Architecture Review Board于1997年推出，现在已发展到2.0版。OpenMP支持的编程语言包括Fortran、C和C++。

OpenMP得到了工业界的广泛支持，有大量的商业编译器和其他开发工具支持OpenMP的开发，如IBM、HP、Sun、SGI、Intel等硬件厂商均有支持OpenMP的编译器产品，另外还有一些第三方厂商的OpenMP编译器。

2. 消息传递模型

在消息传递模型中，一个并行程序由多个并行任务组成。每个并行任务拥有自己的数据并对其进行计算操作。任务之间数据的交换是通过显式的消息传递语句来完成的。

现在广泛使用的消息传递模型有两个：PVM和MPI。PVM即Parallel Virtual Machine(并行虚拟机)与MPI即Message Passing Interface(消息传递界面)。PVM与MPI所提供的功能大致相同，但两者的侧重点有所不同。PVM强调在异构环境下的可移植性和互操作性，程序之间可以互相通信，并支持动态的资源管理和一定程度的容错；而MPI更强调性能，不同的MPI实现之间缺乏互操作性，本身也不支持容错（可以通过专门的容错软件来支持容错）。一般而言，使用MPI比较适合于开发MPP或同构集群上的并行应用，可以有较高的通信性能;而PVM更适合于异构的集群系统。

几乎所有的高性能计算系统都支持PVM和MPI。

3. HPF

HPF(High Performance Fortran)的思想与OpenMP类似，都是通过定义编译指导语句来帮助编译器生成并行代码。HPF的目标系统与OpenMP不同，它支持DMP系统。因此，除了指定并行性的编译指导语句外，HPF还指定数据划分的编译指导语句。HPF与消息传递模型的不同之处则在于:HPF通过编译器来生成通信语句，不需要程序员手工编写。

HPF得到了工业界的广泛支持，如IBM、HP、Sun都有HPF编译器。第三方产品则有PGI的PGHPF、APR的Forge xHPF等。其不足是对于某些问题无法得到与手工编写的消息传递程序相同的性能。

4. 并行库

使用并行库开发高性能计算程序的基本思想是:用户不需要自己编写通用的并行算法代码，而由程序库提供并行算法，并对用户透明。用户只需要根据自己的需求，调用相应的库函数，就可以编写出并行程序。由于库函数的编写者一般经验丰富，而且库函数会采取较为优化的算法，并采用优化编译，使得库函数的执行效率很高。对于大量使用通用计算算法的用户来说，使用并行库是一种高效的开发模式。并行库的缺点是无法帮助那些需要自己书写非通用并行算法的用户。

目前的并行库很多，包括PBLAS(Parallel Basic Linear Algebra Subroutines)，以及建立在其基础上的LAPACK和ScaLAPACK，提供了一些线性代数问题的并行求解算法，如求特征值、最小二乘问题等。LAPACK是为SMP系统优化的，ScaLAPACK是为DMP系统优化的。大多数高性能计算系统都提供在本系统上优化的PBLAS、LAPACK、ScaLAPACK。

另一个著名的并行库是PETSc。PETSc是一套基于MPI的数据结构和库函数，用于解决基于偏微分方程的典型科学计算问题。另外，MATLAB是很常用的科学计算软件。很多公司和研究机构也在进行并行化MATLAB的工作，如RTExpress。

5. 串行程序并行化

另一种并行程序的开发模式是将串行程序并行化。此模式的优点在于，可以将现有的很多串行代码转换成并行代码。

并行化分为全自动并行化和交互式并行化两种模式。全自动并行化的并行过程不需要人的干预，可以自动发现程序中可并行的部分，生成并行代码。现在，高性能计算系统提供商的Fortran和C编译器大都能提供面向SMP系统的自动并行化的编译选项。对于少数程序，全自动并行化编译器可以达到较好的效果；但对大多数程序来说，并行化的效果还不理想。