一．并行计算机的基本概念

    随着计算机应用范围的迅速扩大，使用计算机解决的问题规模也越来越大，因此对计算机运算速度的要求也越来越高。不断改进元器件的制造工艺，提高硬件速度是提高计算机运算速度的重要途径之一。近十年来流行的典型微处理器芯片已从最初的8085沿8086，80186，80286，80386一直发展到今天的80586，每一新产品的推出都伴随着一次速度的升级。除了提高元器件的速度外，改进系统结构也是提高计算机速度的重要途径之一。特别是在元器件速度达到极限(比如光速)时，后者将更为重要。

    传统的计算机是串行结构的，每一时刻只能按一条命令指令对一个数据进行操作。为了克服这种传统结构对提高运算速度的限制，从60年代起开始将并行处理技术引入计算机的结构设计中，利用其对计算机系统结构进行改进。所谓并行处理就是把一个传统串行处理的任务分解开来，并将其分配给多个处理器同时处理，即在同一时间间隔内增加计算机的操作数量。为并行处理所设计的计算机称为并行计算机。  

    对于计算机，存在着几种不同的分类方法，目前大家普遍遵循的是flynn分类法，它首先按指令流的重数将机器分为二类：

 si(single instruction stream)     单指令流;

 mi(multiple instruction stream)   多指令流。

其次，按数据流的重数加以区分：

 sd(single data stream)      单数据流； 

 md(multiple data stream)    多数据流。

这样，就有4种可能的组合，即sisd，simd，misd，mimd。 

    sisd计算机代表如今使用的大多数串行计算机，是单指令流对单数据流进行操作。

    simd计算机是所谓的阵列机，它有许多个处理单元(Pe)，由同一个控制部件管理，所有Pe都接收控制部件发送的相同指令，对来自不同数据流的数据集合序列进行操作。

    misd计算机从概念上讲，则有多个Pe，接收不同的指令，对相同数据进行操作，一般认为misd机目前尚无实际代表，此类结构很少受到人们的注意。

    mimd计算机包括多处理机和多计算机两类，它们都由可各自执行自己程序的多处理器组成。其中，多处理机以各处理器共享公共存储器为特征，而多计算机以各处理器经通信链路传递信息为特征．它们与simd计算机的根本区别在于，simd机中每．台处理器只能执行中央处理器的指令，而mimd机中每台处理器仅接受中央处理器分给它的任务，它执行自己的

指令，所以可达到指令、任务并行。

    根据flynn分类法，通用的并行计算机分为simd机和mimd机两大类，它们是并行算法的物质基础。对于并行算法的设计者而言，不能仅局限于某种具体的并行机而设计并行算法，而必须从算法的角度，将各种并行机的基本特征加以理想化，抽象出所谓的并行计算机模型，然后在此基础上研究和设计各种有效的并行算法。由flynn分类法，可将并行计算机分为两大类，这两大类也确定了两大类并行计算模型，即simd和mimd两类并行计算模型。这两大类还可进一步细分，simd模型可细分为基于共享存储的simd模型和基于互连网络的

simd模型;mimd模型主要可细分为基于共享存储的mimd模型和基于异步通信的互连网络模型。

    simd共享存储模型是假定有有限或无限个功能相同的处理器，每个处理器拥有简单的

算术运算和逻辑判断能力，在理想的情况下假定存在一个容量无限大的共享存储器，在任何时刻，任意一个处理器均可通过共享存储器的共享单元同其它任何处理器互相交换数据。由于实际情况是共享存储器的容量是有限的，因此在同一时刻，当多个处理器访问同一单元时就会发生冲突。根据模型解决冲突的能力，simd共享存储模型又可进一步分为    (1)不容许同时读和同时写。即每次只允许一个处理器读和写一个共享单元，这种模型筒记为simd-erew Pram。

    (2)容许同时读，但不容许同时写。即每次允许多个处理器同时读一个共享单元的内容，但每次只允许一个处理器向某个共享单元写内容，这种计算模型简记为simd-crew

Pram。

    (3)允许同时读和写。即每次容许任意多个处理同时读和同时写同一个共享存储单元，这种计算模型简记为simd-crcw Pram。

    对于同一求解问题，在以上三种计算模型上设计的并行算法通常是不同的。算法的运算时间也不相同，记三种算法的计算时间为t１，t2，t3，它们满足下面关系：

    ti≥t2≥t3

    在simd互连网络模型中，每个处理器在控制器控制下或处于活动状态，或处于不活动状态。活动状态的处理器都执行相同的指令，处理器之间的数据交换是通过互联网络进行的。

根据互连网络的连接方式，simd互连网络模型又分为两类。一类是处理器—处理器之间直接互连(称为闺房式)，如图9．1所示；另一类是处理器—存储器之间直接互连(称为舞厅式)，如下图所示。从算法设计者来讲，这二类无本质差别。因此，以后仅讨论闺房式这一类。 

  

 在共享存储的mimd计算模型中，所有的处理器共享一个公共的存储器；每个处理器各自完成自己的任务，各处理器之间的通信是通过共享存储器中的全局变量来实现的。在这种模型上开发的算法称之为异步并行算法。   

    在基于互连网络的mimd计算模型中，处理器之间不存在共享存储器，每个处理器从各自存储器中存取指令和数据。各处理器之间用通信网络以信息方式交换数据。在此模型上设计的算法称为分布式算法。   

 二．并行机的结构  

在基于互连网络的模型中，由于数据分布存储，信息通过互连网络进行传递，因此算法与处理器互联的拓扑结构紧密相关，下面列举一些常用的互连网络的拓扑结构。

   1．一维线性连接

 此连接方式是所有并行机中处理器之间一种最简单的互连方式。其中每个处理器只与其左右近邻相连(头尾处理器除外)，如图所示。

    

  2．二维网孔连接

    在此连接方式中处理器之间按二维阵列形式排列，每个处理器仅与四个相邻处理器(若有的话)互连，如图所示。二维网孔连接有二个重要的变种，在这二个变种中，边界处理器也有线相连接。

 

 3．超立方连接

 对于n＝2 个处理器，可将其组织成一个k—维超立方连接。首先，处理器按0，1，2 -1依次编号，然后，处理器之间按下述方式连接：处理器i与处理器j有线连接当且仅当i与j的二进制表示中仅一位不同。上图给出了k＝4的四维超立方连接方式。

 4．树形连接方式   

 树形连接方式是利用二叉树这种常用的数据结构组织而成的。对于一棵有d级<编号由根至叶为0到d一1)的满二叉树，每个结点表示一个处理器，因此，对于一个具有d级的树形连接方式，共有n=2 一1个处理器组成。在此结构中，处理器的工作方式通常是：叶子结点对数据进行计算，而内部结点仅负责叶子结点间的通信及简单的逻辑运算。下图给出了d＝4的树形连接结构。  

 

 

5．洗牌—交换连接方式   

    洗牌—交换是一类非常有用的互连结构。对于n=2 -1个处理器i将它们按0，1，2， 2 一1编号，设处理器i的二进制表示为i ,i , i ,i .

下面定义洗牌与交换二个连接函数：

sh(i i …i )=i i …i i

ex(i i …i )=i i i …i

其中 ＝１－i 。在此连接方式中，处理器i与二进制表示为i i …i i i 或i i i …i 的处理器相连。上图示出了n＝2 的洗牌—交换连接结构，其中实线表示ex函数，虚线表示sh函数。