并行运算器

传统计算机是串行结构，每一时刻只能按一条指令对一个数据进行操作，在传统计算机上设计的算法称为串行算法。并行算法是用多台处理器联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。1

概述传统计算机是串行结构，每一时刻只能按一条指令对一个数据进行操作，在传统计算机上设计的算法称为串行算法。并行算法是用多台处理器联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。

为利用并行运算，通常计算问题表现为以下特征：

(1)将工作分离成离散部分，有助于同时解决。例如，对于分治法设计的串行算法，可以将各个独立的子问题并行求解，最后合并成整个问题的解，从而转化为并行算法；

(2)随时并及时地执行多个程序指令；

(3)多计算资源下解决问题的耗时要少于单个计算资源下的耗时。1

模型并行运算模型通常是指从并行算法的设计和分析出发，将各种并行运算机(至少某一类并行运算机)的基本特征抽象出来，形成一个抽象的计算模型。从更广的意义上说，并行运算模型为并行运算提供了硬件和软件界面，在该界面的约定下，并行系统硬件设计者和软件设计者可以开发对并行性的支持机制，从而提高系统的性能。

并行算法设计是基于并行运算模型的，下面简要介绍目前常见的两种并行运算模型。

1．PRAM模型

PRAM(Parallel Random Access Machine，随机存取并行机器)模型，也称为共享存储的SIMD(单指令流多数据流)模型，是一种抽象的并行运算模型，它是从串行的RAM模型直接发展起来的。在这种模型中，假定有一个无限大容量的共享存储器，并且有多个功能相同的处理器，且它们都具有简单的算术运算和逻辑判断功能，在任意时刻各个处理器可以访问共享存储单元。

2．BSP模型

BSP(Bulk Synchronous Parallel，整体同步并行)模型是个分布存储的MIMD(多指令流多数据流)计算模型，由哈佛大学的Viliant和牛津大学的Bill McColl提出。

一台BSP计算机由”个处理器/存储器(节点)组成，通过通信网络进行互联。

一个BSP程序有理个进程，每个驻留在一个节点上，程序按严格的超步(可以理解为并行运算中子问题的求解)顺序执行．如图4．11所示，超步问采用路障同步，每个超步分成如下有序的3个部分。

(1)计算：一个或多个处理器执行若干局部计算操作，操作的所有数据只能是局部存储器中的数据。一个进程的计算与其他进程无关。

(2)通信：处理器之间的相互交换数据，通信总是以点对点的方式进行。

(3)同步：确保通信过程中交换的数据被传送到目的处理器上，并使一个超步中的计算和通信操作必须全部完成之后，才能开始下一个超步中的任何动作。

BSP模型总的执行时间等于各超步执行时间之和。1

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学