（1）并行计算机。并行计算机至少浩瀚两台或两台以上处理机，这些处理机通过互联网络相互连接，互相通信。
（2）应用问题必须具有并行度。应用可以分解为多个子任务，并且这些子任务可以并行地执行。
（3）并行编程。在并行计算机提供的并行编程环境上，具体实现并行算法。
2.2.1 并行编程模式编程模式是程序员和计算机之间的界面，它是建立在计算机体系结构之上的程序的抽象，它定义了程序的设计与其实现之间的接口。在并行计算机发展的历史过程中，人们提出过许多适合不同并行体系结构的编程模式[ST98]，经过时间的淘汰，目前比较流行的并行编程模式基本上趋向于以下三种[Chen99, Du01, ZCML06]：
● 消息传递模式：程序的执行分为多个进程，用户需要显式地为每个进程分配数据和指令。进程都在自己的私有空间中运行，显式地通过发送和接收消息进行交互。有同步通信和异步通信两种方式。消息传递模式为程序员提供了更灵活的控制手段和表达并行的方法，因此消息传递并行程序往往能达到高的执行效率。但由于程序员需要显式地指定进程间的信息交换、协调和控制，编写基于消息传递模式的并行计算程序对于程序员的能力要求比较高。尽管如此，消息传递仍然是目前最常用的并行编程模式。MPI[MPI03a, MPI03b]和并行虚拟机[PVM07]是其中两种广泛使用的消息传递编程标准库。
● 共享存储模式：程序是由运行在一个公共地址空间的一组进程所组成。用户无需进行数据分配，每个进程相对独立地运行，进程间的通信通过存放在公共存储器中的共享变量进行。所以保持变量操作的一致性和同步性是使用这种编程模式时必须考虑的关键问题。基于该模式通过手工或编译器将串行程序并行化，相对比基于消息传递模式更容易，对程序员要求也相对较低。目前使用较多的共享存储模式的实现有IEEE标准委员会的多线程接口[PTP06]和OpenMP标准委员会的OpenMP[OMP07]。
● 数据并行模式：程序所处理的数据被划分为多个小块，分配到系统中的各个处理单元上，每个处理单元执行相同的程序，不需要显示同步。数据并行模式的实现层次较高，一般由编译器实现，程序员只需指明怎样的并行操作和操作的对象即可。高性能Fortran[HPF06]是一种使用较多的数据并行语言。
2.2.2 并行计算机体系结构并行计算机的分类是随着并行计算机的发展而发展的。在并行计算技术发展的不同阶段，各个计算机生产厂商发明了各种各样把多个处理器（处理单元）整合在一起的方法，从而使得系统的整体计算能力有所提高。这些技术经过不断地发展，逐渐成熟并衍生出技术分支，同时也产生出许多不同的并行计算机体系结构。
描述这些体系结构特征的最常用的方法是Flynn分类法[Fly72]。它根据指令流数目和数据流数目来分类，将计算机分成了4类：SISD、SIMD、MISD和MIMD。其中，属于并行计算机的有：
(1) 单指令多数据流（SIMD）：同一指令被复制成多份，并发地发送给多个处理器，形成多个独立的进程，每个进程都具有自己的数据流（如图2.2所示），具有同步性和确定性。
SHAPE \* MERGEFORMAT
图2.2 SIMD体系结构
(2) 多指令多数据流（MIMD）：在MIMD系统中，每个处理器都具有自己的指令来操作自己的数据，与其他处理器无关。指令流可以同步或异步地执行，指令流的执行具有确定性和不确定性。如图2.3所示。
SHAPE \* MERGEFORMAT
图2.3 MIMD体系结构
随着技术的发展，曾经风行的SIMD并行计算机已经退出了历史舞台，MIMD体系的并行机已经占据了统治性的地位。目前世界上流行的并行计算机系统基本上都是属于MIMD计算机。
在MIMD的分类中，按照内存访问模型、微处理器和互联网络的不同，并行计算机可分为以下5类[ZCML06]：
(1) 对称多处理共享存储并行计算机（Symmetric Multi-Processing, SMP）:SMP系统中任何处理器都可以直接访问任何存储模块中的存储单元和I/O模块，且各自间的访问延迟、带宽都一样。整个系统只有一个操作系统驻留在共享存储器中，可以动态地分配进程到各个处理器，而且每个进程都是使用共享的数据存储区来完成通信，通信的延迟较低。但是由于各个处理单元之间的耦合程度较高，所以只要总线、存储器或操作系统其中一个出错，便会导致整个系统的崩溃，而且系统的可扩张性较差。支持消息传递、共享存储并行程序设计。
(2) 分布式共享存储并行计算机（Distributed Shared Memory, DSM）：系统以节点为单位，每个节点包含一个或多个CPU，每个CPU有局部的cache。存储在物理上分布，但在逻辑上是统一的内存地址空间。各个节点既可以直接访问本地的局部存储单元，也进行访问其他节点的局部存储单元，但远端访问必须通过高性能互联网络，性能远不如本地访问。DSM系统的可扩展性强，可扩展至数百个节点。支持消息传递、共享存储并行程序设计。
(3) 集群系统（Cluster）
