算法设计与分析讲义chapter9参考模板

1、第九章 并行算法的设计与分析9.1 并行计算机系统的发展 自从四十年代第一台电子计算机问世以来，计算技术的发展异常迅速，对人类活动的各个方面都产生了深刻的影响。伴随着计算机的迅猛发展，计算机应用日新月异，从科学计算到人类智能的模拟，对计算机的处理能力提出了越来越高的要求。提高计算机的处理能力一直是计算机发展的源动力。计算机科学家一直在追求三(Trillion，万亿)目标，即:每秒一万亿次的运算速度，一万亿字节的存储容量，每秒一万亿字节的数据通信能力。这三个目标的每一个都是现有超级计算机性能的一千倍。 在计算机问世后的数十年间，计算机始终沿袭着Von Neumann计算机结构的顺序操作方式。提高

2、计算机的速度一直被认为是加快时钟频率。到70年代初，顺序运行速度的提高显著地减慢了，其主要原因是元器件的速度已接近物理极限。人们开始了新的探索。以Cray为代表的计算机科学家企图在这个瓶颈周围探索一条迂回道路。他们把器件更紧密地组合在一起以便最大限度地减少电讯号的传递距离，并采用了新的电路散热技术。同时，他们也采用了并行化技术。 他们把CPU分成若干相互协作的子单元，并把这些子单元装配成一条计算流水线。这种方法导致了并行向量处理计算机系统的出现。 CRAY RESEARCH公司的CRAY1和CRAY2计算机系统、日本NEC公司的SX-3计算机、日本富士通公司的VP-2600等都是并行向量处理系

3、统的典型实例。这些机器的运算速度最多只达到5.5Gflops，距离每秒一万亿次还相距甚远。 日本的计算机制造者和CRAY寄希望于延用老的设计，使用砷化镓芯片取代硅芯片，以取得更高的速度。砷化镓芯片是以故障率高而昭著于世的。这种选择是一场代价昂贵的赌博。即使这种砷化镓计算机能够成功，也只能达到20Gflops的速度，距离一万亿次计算速度还相差50倍。 追求三目标的另一种探索是增加计算机系统中处理器的数量。这种探索导致了大规模并行计算机(MPP)的出现。MPP计算机把大量的处理器集中在一起，以获得高速度。它把逻辑部件、存储器和通信网集成一体。通常，MPP计算机中的单个处理器的速度要比CRAY1的处

4、理器慢，但是当我们把一个问题分解成许多子问题时，这个处理器集群就能以极高的速度来解决这个问题。第一台多处理器并行计算机Illiac是在1975年投入运行的。Illiac是一台由64个处理器组成的阵列式并行计算机。1982年，CRAY X-MP诞生。它把两台CRAY1处理器组合在一起。两个处理器共享一个公共存储器。两个处理器可以执行不同的指令流。CRAY X-MP是第一台超过CRAY1计算机的计算速度的超级计算机。1987年，Daniel Hillis的Connection Machine(CM)问世。CM计算机是一台彻底摆脱了Von Neumann结构的MPP计算机。 CM计算机问世后不仅站住

5、了脚，而且取得了举世瞩目的迅猛发展，CM1、CM2和CM5先后投入市场。 CM计算机的出现使人们相信， 具有数万、数十万个处理器的MPP计算机有可能达到三目标。1990年以来，越来越多的多处理器并行计算机系统开始投入市场，如nCUBE、IPSC/2、Wavetracer、Multimax、Symmetry、FX/8、CRAY YMP、CM2、CM5等。目前多处理器并行计算机已经成为计算机领域的一场革命，推动了计算技术发展。1 / 599.2 并行计算机系统的分类模型 并行计算机系统的分类方法很多。我们使用二维分类方法对并行计算机系统进行分类。所有并行计算机系统可以视为图9.2.1所示的二维空间

6、的子集合。图9.2.1所示的并行计算机系统空间的第一维，即“存储器”维，把并行计算机系统分为两类。第一类是具有共享存储器的并行计算机。第二类是具有分布式存储器的并行计算机。“指令流数据流”维把并行计算机系统分类为SISD、SIMD、MISD和MIMD四种并行计算机系统。下边我们以“指令流数据流”为主，讨论各类并行计算机系统模型。9.2.1 SISD计算机系统 SISD表示“单指令流单数据流”。SISD计算机系统由一个处理器、一个控制器和一个存储器系统组成。存储器系统由多个存储模块组成。这类计算机系统包括了所有单处理器计算机系统。具有流水线并行性的向量计算机也包括在这一类计算机中。图9.2.2描

7、述了SISD计算机系统的结构。 SISD计算机系统的处理器仅接收和处理单个指令流，而且这个指令流仅在一个数据流上执行。在SISD计算机的每步计算中，控制器向处理器发出一条指令，处理器在一个来自存储器的数据上执行这条指令。SISD计算机只有共享存储器一种类型。处理器对多个存储部件的存取由连接网络实现。 实际上，SISD计算机是传统的Von Neumann计算机。9.2.2. MISD计算机系统 MISD表示“多指令流单数据流”。MISD计算机系统的结构如图9.2.3所示。 MISD计算机系统由多个处理器组成。每个处理器都有自己的控制器。所有处理器共享由多个存储部件组成的存储器。连接网络实现多个处

8、理器对多个存储部件的存取。系统中每个处理器执行一个独立的指令流。多个处理器同时在一个数据流上工作。在MISD计算机系统的计算过程中，每个处理器都在同一个来自存储部件的数据流上执行自己的指令流。MISD计算机系统是并行计算机系统。它的并行性体现在多个处理器并行地完成不同的任务。我们来看一个MISD计算机系统的应用实例。 给定一个n维组数Z。我们要判别Z中的n个数是否素数。为了完成这个任务，我们需判别Z中每个数Zi是否仅能被和Zi本身整除。为了容易说明，我们假设每个Zi有P个可能因子，记作fi1、fi2、.、fiP。下边是用一个具有P个处理器的MISD计算机系统判别Z中的n个数是否素数的并行算法：

9、 FOR i=1 TO n DO 从存储器读Zi，送到所有P个处理器； FOR j=1 TO P DO （并行地） 从存储器读fij, 送处理器j； ENDFOR； FOR j=1 TO P DO （并行地） 处理器j判别fij是否可整除Zi； ENDFOR; IF P个处理器都回答“不能整除” THEN Zi是素数；ELSE Zi是合数；ENDIF; ENDFOR。 从上述算法可以看到, 使用MISD计算机系统，P个处理机一次并行判别就可知Z中的一个数是否素数。如果使用单处理器计算机，P次判别才能给出回答。如果Zi的可能因子多于P个，读者可以自行修改上述算法，完成Z1、Z2、.、Zn是否素数

10、的判别。 显然，MISD计算机系统只有共享存储器一种类型。9.2.3 SIMD计算机系统 SIMD计算机系统是一类非常重要的并行计算机系统。SIMD表示“单指令流多数据流”。SIMD计算机系统分为两种。一种是共享存储器的SIMD计算机系统。另一种是具有多布式存储器的SIMD计算机系统。前一种又称为紧耦合SIMD计算机系统。后一种也称为松散耦合SIMD计算机系统。 图9.2.4描述了松散耦合SIMD计算机系统的结构。松散耦合SIMD计算机系统包括一个控制器和多个处理单元（简称PE），每个PE具有自己的存储器。多个PE由一个连接网络连接在一起。控制部件向多个PE广播指令。所有处于活动状态的PE同时

11、执行由控制器广播的相同指令。于是，系统中只有一个指令流。每个PE在各自存储器的数据上执行控制器广播的指令。于是，系统具有多个数据流。连接网络用来实现PE间的通信。连接网络把每个PE连接到所有或部分其它处理器。一个数据传送指令可以使每个处于活动状态的PE向所有与它相连接的PE发送一个数据。在不直接连接的两个PE之间传送数据需通过中间PE间接进行。例如，假设PE0仅连接到PE1，PE1仅连接到PE2。要从PE0传递数据D到PE2，D必须先传递到PE1，然后再由PE1传递到PE2。 图9.2.5给出了紧耦合SIMD计算机系统的结构。紧耦合SIMD计算机系统的多个处理器共享一个全局存储器。全局存储器由

12、多个存储器模块组成。控制器仍然负责向多个处理器广播指令。所有处于活动状态的处理器在来自存储器的不同数据上同时执行由控制器广播的相同条指令。紧耦合SIMD计算机系统的连接网络把每个处理器连接到所有或部分存储器模块。它也把每个存储模块连接到所有或部分处理器。一个数据传送指令可以使每个处理器把数据传送到它所连接的一个或多个存储块，也可以把每个存储模块中的数据传送到它所连接的一个或多个处理器。处理器之间的数据通信可以通过共享存储器实现。如果两个处理P1和P2都与存储器模块M连接，P1和P2之间的数据通信可以通过M实现。如果P1和P2之间无直接相连的共享存储器，但P1和P3直接与存储器模块M13相连接，

13、P3和P2直接与存储器模块M32相连。如果P1要把数据传送到P2，P1需先把传送到M13，然后P3把M13中的传送到M32。P2可以从M32中得到P1送来的数据D。 第一个SIMD计算机系统是Illiac 计算机。目前最大的SIMD计算机系统是CM2计算机。它包括65536个处理器。CM5计算机也具有SIMD的特点。下边我们来看一个SIMD计算机系统应用的例子。设X、Y和Z是三个向量。试求向量X与Y的和，并将结果存入Z。完成这个任务的单处理器计算机程序可以写为： FOR i=0 TO N-1 DO Z(i):=X(i)+Y(i)； ENDFOR.然，这个程序在单处理器计算机上需要执行N步。 设

14、X、Y和Z存储在具有N个处理单元的SIMD计算机中，如图9.2.6所示。要完成上述任务，SIMD计算机系统只需执行一条指令：Z:=X+Y。 我们把上述例子略作修改，可得如下程序：FOR i=1 TO N-1 DO Z(i) := X(i)+Y(i-1); ENDFOR； Z(0) := X(0).设X、Y、Z仍然如图2.2.6所示的那样存储在SIMD计算机系统中。SIMD计算机系统可以按如下步骤完成这个计算： 1. FOR i=1 TO N-1 DO （并行地） 通过连接网络把Y(i-1)从PEi-1移到PEi； 2. ENDFOR; 3. 使PE0处于不活动状态; 4. FOR i=1 TO

15、 N-1 DO （并行地） PEi完成 Z(i) := X(i) + Y(i-1)； 5. ENDFOR; 6. 使除PE0以外的其它PE处于不活动状态； 7. PE0完成 Z(0):=X(0). 这个例子说明了处理单元间连接网络的必要性，也说明了SIMD计算机系统应能使某些处理单元处于活动状态或不活动状态。2.2.4 MIMD计算机系统 MIMD表示“多指令流多数据流”。MIMD计算机系统由多个处理器、多个控制器、多个存储模块和连接网络组成。每个处理器执行自己的程序。于是，MIMD计算机系统具有多个指令流。每个处理器在它自己的数据流上执行自己的指令流。所以，MIMD计算机系统具有多个数据流。

16、连接网络用来实现处理器之间或处理器与存储模块之间的数据通信。在SIMD计算机系统中，处理器同步地使用连接网络。而在MIMD计算机系统中，各处理器独立异步地使用连接网络。MIMD计算机系统分为紧耦合和松散耦合两类。图9.2.7给出了紧耦合MIMD计算机系统的结构。在紧耦合MIMD计算机系统中，所有处理器共享多个存储模块。连接网络实现处理器与存储模块之间以及处理器与处理器之间的通信。 图9.2.8给出了松散耦合MIMD计算机系统的结构。这类计算机系统由多个处理单元和一个连接网络构成。每个处理单元PE由控制器、处理器和自己的存储器组成。连接网络实现处理单元之间的通信。 MIMD计算机系统与SIMD计

17、算机系统的主要区别在于前者的处理器异步独立运行，后者的处理器同步运行。MIMD计算机系统具有很大的灵活性，程序设计比较困难，要求比较复杂的同步机制。很多应用都要求使用MIMD计算机系统。目前已经出现了很多MIMD计算机，如nCUBE、IPSC/2、Wavetracer、CM5等。由高速通信网连接的多计算机系统也可以视为一台MIMD计算机。我们在讨论支持并行数据库的并行计算结构时提到的SM并行计算结构是紧耦合MIMD计算机系统特例，SD和SN并行计算机结构是松散耦合MIMD计算机系统的特例。9.3 连接网络 在9.2节我们已经看到，连接网络是并行计算机系统的关键组成部分，关系到多处理器(或多计算

18、机)的通信方式和多存储模块的存取模式，对并行算法和并行程序设计具有十分重要的影响。连接网络的目标是以最小的造价提供快速灵活的通信方式。为了达到这个目标人们提出了大量的连接网络。每种连接网络都有其优点和缺点，但是没有一种连接网络在任何情况下都是最优的。连接网络分为动态连接网络和静态连接网络两类。9.3.1 动态连接网络 动态连接网络主要用于共享存储器并行计算机系统结构，实现多处理器对多存储器模块的共享存取。本小节介绍几种比较重要的动态连接网络。 1. 共享总线连接网络 共享总线连接网络是最简单的动态连接网络。共享总线网络既可以用来实现多处理器对共享存储器的存取，也可以实现多处理器之间的通信。图9

19、.3.1的(a)图给出了共享总线连接网络的实例。共享总线连接网络具有最简单的结构，也具有最严重的资源竞争，通信效率很低。 为了减轻共享总线的瓶颈问题，很多基于共享总线连接网络的并行计算机系统都使用了高速缓冲器技术。每个处理器设置一个局部高速缓冲器(Cache)。每个处理器可以预先把其即将使用的数据预先从共享存储器中读入局部高速缓冲器。这样，局部高速缓冲器就减少了处理器对共享存储器的存取次数，从而减轻了共享总线的瓶颈问题。图9.3.1的(b)图给出了具有局部高速缓冲器的共享总线连接网络结构。 2. 交叉开关网络 交叉开关网络主要用于实现多处理器对多个存储模块的共享，使所有处理器能够并行地存取所有

20、存储模块。与共享总线相反，交叉开关网络具有最少的资源竞争，但具有最高的硬件复杂性。图9.3.2给出了交叉开关网络的例子。图中的每个小圆圈表示一个开关。 3. 蝶形连接网络 蝶形连接网络是与快速傅立叶变换(FFT)密切相关的连接网络。一个K-维蝶形连接网络具有(K+1)2K个开关结点和K2K+1条边。一般地说，每个开关具有n个输入端和n个输出端。每个输入端可以与任何一个输出端连通。在任意时刻，一个输入端能而且只能与一个输出端连通，反之亦然。我们称这样的交叉开关为n×n开关。下边是一个2×2开关的两种连通状态： 蝶形连接网络的开关结点分为2K行(或维)和K+1级。每个开关结点对

21、应一个序对(w,i)，其中i是这个结点的级或维，w是这个结点所在行号的二进制表示。设i<i'。两个结点(w,i)和(w',i')由一条边相连当且仅当： (1). w和w'相同，或 (2). w和w'的第i'位不同（从最左位算起）。 如果w和w'相同，则对应的边称为直边，否则称为交叉边。连接i级和i+1级结点的边称为i+1级边。在实际并行计算机系统中，蝶形网络的输入端连接处理器，输出端连接存储器模块。图9.3.3给出了一个三维蝶形连接网络的例子。图中每个圆圈表示一个2×2开关。 4. Omega连接网络 一个log2N维Om

22、ega连接网络有N(1+log2N)个交叉结点，分为N行(或维)1+log2N级。Omega网络中的一个交叉开关结点对应一个序对(W, L)，其中，W是结点所在行，L是结点所在的级，W，0Llog2N。结点(W, L)和(W', L+1)之间有一条边当且仅当： (1). W'是W的一个循环左移，或 (2). W'是W的一个循环左移并改变最后一位。 图9.3.4给出了一个维Omega连接网络的实例。 5. Flip连接网络 一个log2N维Flip连接网络包括N(1+log2N)个开关结点，分为N行1+log2N级。网络中开关结点表示为(W, L)，W是结点所在的行，是结

23、点所在的级，W，0Llog2N。结点(W, L)和(W'，L+1)之间有一条边当且仅当： (1). W'是W的一个循环右移，或 (2). W'是通过首先改变W最末一位然后循环右移一位得到。 图9.3.5给出了一个三维Flip连接网络的结构。在实际应用中，Flip连接网络的输入端连接处理器，输出端连接存储器模块。 6. Baseline和逆Baseline互连网络 一个log2N维Baseline互连网络有N(1+log2N)个开关结点, 分为N行1+log2N级。开关结点表示为(W, L)，W和L的意义与Flilp网络中的W和L相同。结点(W, L)和(W',

24、L+1)相连当且仅当： (1). W'是W的最后log2NL位循环右移，或 (2). W'是通过首先改变W的最后一位，然后对最后log2NL位进行一次循环右移得到。 图9.3.6给出了一个三维Baseline互连网络的结构。 逆Baseline互连网络与Baseline互连网络的差别仅在于各级的排列顺序相反。9.3.2 静态连接网络 静态连接网络主要用于分布式存储器并行计算机系统，实现多处理器之间的通信。下边我们介绍几种重要的静态连接网络。 1. 完全连接网络 多处理器的完全连接网络是一个结点为处理器的完全图，使得每个处理器都可以直接与其它处理器通信。图9.3.7给出了一个具有

25、个处理器的完全连接网络。 2. 一维线性连接网络 一维线性连接网络(Linear Array)是一种比较简单的连接网络。图9.3.8给出了一个连接N个处理器的一维线性连接网络。在具有N个处理器的一维线性连接网络中，Pi与Pi-1和Pi+1通过双向通信线连接（2iN-1）。P1只与P2连接，PN只与PN-1连接。一维线性连接网络的连接函数定义为： R(Pi)=Pi+1 (1iN-1), L(Pi)=Pi-1 (2iN)，其中，R(P)表示在处理器P右边与P直接连接的处理器，L(P)表示在处理器P左边与P直接连接的处理器。 把一维线性连接网络的第一个处理器和最末一个处理器连接起来，我们就得到一个环

26、形连接网络。设N个处理器编号为0，1，2，., N-1。环形连接网络的连接函数定义如下：R(P)=P+1 mod NL(P)=P-1 mod N其中，P是任一处理器的编号。R(P)表示在P号处理器(按逆时针方向)之后与号处理器直接相连的处理器，L(P)表示按逆时针方向在号处理器之前直接与P号处理器相连的处理器号。图9.3.9给出了一个具有16个处理器的环形连接网络实例。 3. 二维阵列连接网络 二维阵列连接网络把N个处理器连接成一个二维矩阵。设N个处理器编号为0、.、N1，是一个整数，P是任意一个处理器的编号。在P的上、下、左、右四个方向上与P直接连接的处理器由如下四个函数确定： R(P)=P

27、+1 (P不是任一行的最末一个处理器)；L(P)=P-1 (P不是任一行的第一个处理器)；A(P)=P-n (P不是任一列的第一个处理器)； B(P)=P+n (P不是任一列的最末一个处理器)。其中，R(P)表示在P号处理器右侧直接与P号处理器相连的处理器号，L(P)表示在P号处理器左侧直接与P号处理器相连的处理器号，A(P)表示在P号处理器上部直接与P号处理器相连的处理器号，B(P)表示在P号处理器下部直接与P号处理器相连的处理器号。图9.3.10给出了一个N=16时的二维阵列连接网络的实例。 如果把二维阵列连接网络每行的首尾两个处理器相连接、把每列的首尾两个处理器相连接，我们就得到一个首尾

28、连接的二维阵列连接网络。图9.3.11给出了一个具有16个处理器的首尾连接的二维阵列连接网络。图9.3.11. 一个具有16个处理器的首尾连接的二维阵列连接网络。 4. 星形连接网络 星形连接网络是一种集中形网络，具有一个中心处理器，其它处理器都连接且仅连接到这个中心处理器。图9.3.12给出了一个具有16个处理器的星形连接网络。设N个处理器编号为0、1、.、N-1。星形连接网络的连接函数定义为：N(P)=0, P0。N(P)表示直接与P相连接的处理器。 5. 树形连接网络 我们在这里介绍两种树形连接网络。第一种树形连接网络是以处理器为结点的完全二叉树。设系统具有N=2d-1个处理器，编号为、

29、.、N。这N个处理器的完全二叉树连网络由级组成，从根结点开始编号为0到-1，N=2d-1。图9.3.13给出了一个具有15个处理器的完全二叉树连接网络。完全二叉树连接网络的连接函数为: L(P)=2P (0P20+21+22+.+2d-2) R(P)=2P+1 (0P20+21+22+.+2d-2) P(P)= (1PN-1)，其中，L(P)表示P号结点的左子结点的处理器号，R(P)表示P号结点的右子结点的处理器号，P(P)表示号结点的父结点的处理器号。 树形连接网络可加以改进，使同一级处理器连接成为一维阵列连接网络，如图9.3.14所示。 在完全二叉树连接网络中，具有较低级别的结点形成了通信

30、瓶颈。级别越低，瓶颈问题越严重。例如，当根结点的左子树中有很多结点要与根结点的右子树中的结点通信时，根结点必须把左子树送来的所有数据都传递给右子树。显然，根结点是最严重的通信瓶颈。为了解决完全二叉树连接网络的瓶颈问题，人们提出了第二种树形连接网络，即胖树(Fat Tree)。在胖树中，第i-1级结点与第i级结点之间具有(d-1)-(i-1)= d-i条连接线。图9.3.15给出了一个具有15个处理器的胖树。图9.3.15. 给出了一个具有15个处理器的胖树。 6. 洗牌交换连接网络 我们先来介绍洗牌连接网络。洗牌的名字来源于“洗牌”游戏，即将一叠牌对分为两半，然后依次从两半中各取其一相互交叠在

31、一起。设N个处理器编号为0、1、.、N-1，N=2n，n是正整数。第个处理器所连接的处理器号由下列连接函数确定：设i的二进制表示为im-1im-2.i1i0，则S(i)可以等价地表示为:S(im-1im-2.i1i0)=im-2im-3.i0im-1.图9.3.16给出了一个由个处理器构成的洗牌连接网络 洗牌交换连接网络是在洗牌的基础再进行交换，即使奇偶编号的处理器可以交换数据。洗牌交换连接网络的连接函数定义为： S(im-1im-2.i1i0)=im-2im-3.i0im-1， E(im-1im-2i1i0)=im-1im-2.i1。其中，im-1im-2.i1i0是数i的二进制表示。表示i

32、0的反码。洗牌交换连接网的建立分两步。首先按照函数把N个处理器相连，然后再按照函数增加新的连接边。图9.3.17给出了一个具有个处理器的洗牌交换连接网络。 7. 超立方连接网络 设有N个处理器P0、P1、.、PN-1，N=2k。一个k维超立方连接网络把每个处理器与k个其它处理器相连接。设i的二进制表示为ik-1ik-2.i1i0，则与Pi相连接的k个处理器为Pjj=ik-1.im-1im+1.i0，0mk-1.当k和时，k维超立方连接网络为通常的正方形和立方体。图9.3.18给出了一个由个处理器组成的维超方体。 8. 组合连接网络 上面讨论的各种连接网络可以组合成各种复杂的连接网络，下边我们以

33、两种组合连接网络为例来说明构造组合连接网络的原理。 我们可以把一维线性阵列连接网络与完全二叉树连接网络相结合形成一维线性树阵列连接网络。一维线性树阵列网络通过把一维线性阵列网络的每个结点用一个具有K个叶结点的完全二叉树连接网络替代而形成。图9.3.19给出了一个一维线性树阵列网络的实例。 我们也可以把超立方连接网络与环形连接网络相结合得到一个复杂的组合网络，称为立方环。立方环结合了超立方连接网络和环形连接网络的优点和性质。立方环网络通过把超立方连接网络的每个结点代之以一个环形连接网而得到。图9.3.20给出了一个立方环网络的例子。这个立方环网络是用个结点的环代替三维超方体的每个顶点所得到的。9

34、.3.3 静态连接网络的性能分析 本小节介绍几个评价静态连接网络性能的测度，并使用这些测度分析2.3.2节介绍过的部分静态连接网络的性能。 1. 网络直径 连接网络中两个处理器P1和P2之间的距离d(P1,P2)定义为这两个处理器之间的最短路径包含的边数。连接网络的直径定义为max d(P1,P2) | P1和P2是网络中任意两个处理器。由于距离直接影响连接网络的通信时间，所以连接网络的直径越小网络的通信效率越高。完全连接网络的直径为1。星型连接网络的直径是2。具有P个处理器的环型连接网络的直径是。二维阵列连接网络的直径是2(-1)。首尾连接的二维阵列连接网络的直径是2。超立方体连接网络的直径

35、是log2P。完全二叉树连接网络的直径是2log2(P+1)/2)。 2. 网络连通性 连接网络的连通性是度量网络中任意两处理器之间的路径多少的测度。连接网络的连通性越高越理想。这是因为网络的连通性越高，处理器之间的路径越多，通信资源的竞争就越小。连接网络的连通性的定义方法很多。设L(P1 ,P2)是处理器P1和P2之间的路径数。我们可以定义连接网络的连通性为 min L(P1 ,P2)| P1和P2是网络中任意两个处理器 。我们称这种连通性为路径连通性。我们也可以定义一个连接网络的连通性为：把该网络分为两个不连通的子网络时必须删除的最小边数。我们称这种连通性为边连通性。一维线性连接网络的边连

36、通性为1。环连接网络和二维阵列连接网络的边连通性为2。首尾连接的二维阵列连接网络的边连通性为4。d-维超立方连接网络的边连通性为d。 3. 二分宽度和二分带宽 一个连接网络的二分宽度定义为把该网络划分为两个相等的子网络需要删除的最小通信链路数。环连接网络的二分宽度为2。由P个处理器构成的二维阵列连接网络的二分宽度为。由P个处理器构成的首尾连接的二维阵列连接网络的二分宽度为2。树型连接网络的二分宽度为1。P个处理器的完全连接网络的二分宽度为P2/4。d-维超立方连接网络的二分宽度为2d-1。 连接网络中两个处理器的通信链路可并行传输的数据位数称为通道宽度。通道宽度等于通信链路的物理通信线数。每条

37、物理通信线传输数据位的速度峰值称为通道速度。通信链路传输数据位的速度峰值称为通道带宽。通道带宽等于通道速度和通道宽度的乘积。 一个连接网络的二分带宽是该网络的任意两个具有相等处理器个数的子网络之间的最小通信量。二分带宽等于二分宽度和通道带宽的乘积。 4. 连接网络的代价 连接网络代价的定义很多。连接网络的代价可以定义为该网络的通信链路的数量。按照这种定义，具有P个处理器的一维线性连接网络和树型连接网络的代价为P-1，具有P个处理器的首尾连接d-维阵列连接网络的代价为dP，具有P个处理器的超立方连接网络的代价为(Plog2P)/2。连接网络的二分带宽也可以定义为连接网络的代价。9.4 计算机机群

38、并行计算系统 最近几年，随着计算机网络技术的发展，一种新的并行计算系统应运而生，即基于网络的计算机机群并行计算系统。本节简单介绍一下这种并行计算系统。9.4.1 机群并行计算系统的特点 把多个独立的计算机系统通过高速通信网络相连接用来支持并行计算的系统称为机群并行计算系统。机群并行计算系统中的每个计算机称为结点机。机群并行计算系统的结点机可以是高档微机、工作站、小型机、大型机或巨型机。如果一个机群并行计算系统的所有结点机皆为工作站，则称其为工作站机群。工作站机群是目前主要的机群并行计算系统，与向量计算机和多处理器并行计算机相比，机群并行计算系统具有如下几个特点： . 易于实现。机群并行计算系统

39、只要求把现成的计算机用高速通信网络连接起来，容易实现。 . 可扩展性强。机群并行计算系统的处理能力容易扩展。例如，只要在网络上增加一台新的计算机，就可提高系统的处理能力，而对系统中的其他部件具有很少的影响，甚至没有影响。 . 灵活性高。用户可以根据需要把各种不同体系结构的计算机连接在一起，有机地形成一个用户需要的异构并行计算环境。 . 复用性强。通过网络，所有结点机的软硬资源都可以得到重复使用。由于机群并行计算系统的结点机是通用计算机，因此设计并行程序时可以充分利用这些机器的成熟代码，从而降低软件开发费用。借助分布共享存储DSM等技术，应用程序可以透明地访问到所有结点机的内存。 . 高度I/O

40、并行性。由于各结点计算机都有自己的I/O设备，如磁盘等，我们可以使用数据分布等技术充分发挥系统的I/O并行性。这种结构特别适用于并行数据库系统。 . 性能价格比高。机群并行计算系统的性能价格比非常高。例如，美国Oak Ridge国家实验室的一组实用并行程序测试表明，基于网络的11台IBM RS/6000工作站组成的并行系统的浮点运算速度可以达到0.7GFLOPS。这个运算速度已经接近某些巨型计算机的速度，但是价格却远远低于巨型计算机系统。 机群并行计算系统的上述特点，特别是易于实现这一特点，会给人一个印象，有了机群并行系统就不必要发展MPP技术了。事实上，机群并行计算系统并不能代替MPP技术。

41、首先，机群并行系统中的结点机的特点决定了它的应用范围。不同档次的机群并行计算系统的性能不尽相同，只有高档计算机组成的机群并行计算机系统的速度才能接近于MPP。低档计算机组成的机群并行计算系统的性能与MPP相差很远。其次，机群并行计算系统与MPP的目标也不同。MPP的目的是实现具有成千上万个处理器的并行系统，真正达到“大规模”并行。这个目标对机群并行计算系统是不现实的。从某种意义上讲，机群并行计算系统的优势在于无可比拟的灵活性。机群并行技术能方便地将不同体系结构的各种计算机连接在一起，有机地形成一个用户所需要的异构并行计算环境。 综上所述，机群并行系统是并行处理技术的一个重要分支，是进行高性能计

42、算的一个有效途径，必将与MPP技术并驾齐驱，主宰并行计算技术的发展。从机群并行系统的特点可以看出，它们特别适于我国的国情。9.4.2 机群并行计算系统的高速通信网络 实现机群并行计算系统的最简单方法就是采用现成的计算机网络（如 Ethernet）把多个计算机连接在一起。这种方法简单、易行。但是，这种机群并行计算系统具有一个致命的弱点：多计算机间通信速度慢，存在严重的通信瓶颈问题。这个问题决定了机群并行计算系统只适于运行粗粒度或较粗粒度的并行程序，而且计算机间的通信量不能过大，否则效率就会下降，加速比就会很低。显然，通信瓶颈问题是影响机群并行计算系统性能的关键问题。为了解决通信瓶颈问题，机群并行

43、计算系统需要具有满足如下要求的高速通信网络： 1. 高传输率, 2. 低通信延迟。 网络传输率和通信延迟是引起通信瓶颈问题的关键因素。要解决通信瓶颈问题，我们必须同时考虑这两项因素。网络传输率是指网络每秒可传输的数据量。为了提高传输率，人们正在研制各种新型的高传输率网络。这些网络多采用光纤作为通信介质。目前，已经发现了一些高传输率通信网络。它们的传输率可达到每秒100M位、每秒300M位，甚至更高。在不久的将来，传输率可以达到每秒千兆位。 简单地使用高传输率网络并不能从根本上解决机群并行计算系统的通信瓶颈问题。我们还需要降低通信延迟。通信延迟主要由结点机发送和接收数据的软件开销决定。为了降低通

44、信延迟，国外一些厂商开发了专用硬件作为机群并行计算机系统互连网络。IBM以SWITCH技术为基础，推出了两种专用通信交换器：BIT-3和IBM V-7。CONVEX以共享存储器技术为基础，推出了共享存储器接口SMI。在CONVEX的META系列中，每一个SMI支持8台HP工作站互连，可以实现32台HP工作站的机群并行计算机系统。以上三种连接机构与DELTA机相比已难分仲伯。美国卡内基梅隆大学在其实验系统Nectar上，精心优化其硬件通信机构，采用最新的通信技术ATM（异步传输模式），达到了非常高的性能。表9.4.1比较了这几个系统的互连网络。表9.4.1. 互连网络网络延迟（毫秒）传输率（M字

45、节/每秒）ETHERNET3.50.05-0.1FDDI<14RS/6000 BIT_30.2410IBM V-70.143-5SMI<0.514NECTAR0.35100（峰值）DELTA0.135-79.4.3 机群并行计算系统的硬件环境 我们介绍两种计算机机群并行计算系统的硬件环境。一种是CMU开发的Nectar系统。另一种是我国黑龙江大学研制的Hcluster系统。 1. Nectar机群并行计算系统 Nectar是CMU开发的机群并行计算机系统原型。Nectar采用一种高传输率、低通信延迟的局域光纤网实现26台结点机的连接，其中包括用一条长26公里的光缆把一台CRAY Y

46、-MP作为节点机联入网内。Nectar光纤网的传输率为每秒100M字节。目前正在研制的Gigabit Nectar是美国五个国家级Gigabit实验台之一。这个系统支持每秒800M字节的HIPPI/ANSI标准和广域网的SONET/ATM接口。 图9.4.1给出了Nectar系统的结构。如图所示，Nectar系统分为结点机、通信加速器和Nectar网三部分。Nectar网由光纤链路和交换器等组成。通信加速器插在节点机的VME总线槽上，经光纤端口与Nectar网连接。光纤端口由光电转换器和FIFO数据缓冲区等构成。每个通信加速器包括1M字节的数据存储区、512K的指令存储区以及16.5M的SPA

47、RC处理器和DMA控制器。DMA用于控制光纤端口与通信加速器存储区以及该存储区与节点机的VME接口之间的数据传输。通信加速器是结点机与Nectar网之间的接口。它的主要功能是操纵一个1616的交叉开关。 Nectar网络软件由通信加速器的运行系统和结点机上配置的相应库函数组成。通信加速器的运行系统主要用来管理加速器上的硬设备（定时器、DMA等）、数据缓冲区（数据缓冲区管理程序）、支持并行程序设计（多线程软件包）。通信加速器的运行系统既支持TCP/IP协议，也支持CMU自行设计的RMP（Reliable Message Protocal)等协议。 为了解决通信瓶颈问题，Nectar系统采用了高速

48、光纤网，数据传输率可以从每秒100兆位到每秒800兆位。此外，Nectar系统还采用了两种方法来降低通信延迟。一是减少数据发送与接收时数据复制的次数。由于结点机主存带宽的限制，频繁的数据复制将引起很大的通信延迟。二是与通信有关的中断处理均由通信加速器完成，减少结点机中断次数。为了进一步减少通信延迟，Nectar系统采用了图9.4.2所示的方法设计节点机与网络的接口。这种设计把用户数据缓冲区移到通信加速器中。因此，发送或接收数据时不需要由结点机来控制数据的复制操作。数据的打包和拆卸等工作在通信加速器上由用户进程Server完成。这样，由主存带宽限制所引起的通信延迟被降到最低。如果采用通常的方法，

49、计算机向网络传送数据时，其接口过程如图9.4.3所示。用户命令被解释为某种系统调用，由该系统调用控制向网上发送数据。在执行系统调用时，首先由结点机操作系统从用户空间复印数据到系统缓冲区，经过数据打包后传送给网络控制器，然后从网络控制器转发到网上。使用这种方法，每发送或接收数据时，至少需要占用三次总线，引起很大的通信延迟。 在Nectar网中，每台结点机通过交换器实现与其它结点机的直接点对点通信，数据传输率不随计算机结点的增加而下降。Nectar的围绕一组核心为1616交叉开关的交换器而设计。交换器能够使结点机的通信加速器“打开”或“关闭”。通信加速器可以实现数据包和非数据包方式的信息传输。按数

50、据包方式传输信息时，数据以包的形式传送，数据包的最大长度受到交换器端口FIFO缓冲区的长度限制。 按非数据包方式传输信息时，传送数据的长度不受限制。根据测定，Nectar网络进行数据传送时，数据包第一个字节的传送延迟（包括建立链路和完成传送两部分）约为0.7毫秒，其余字节传送时的延迟时间为0.35毫秒。Nectar的交换器能够在每0.7毫秒的周期内建立一个新的链路。 由于单个交换器的传送和开关延迟较低，多个交换器组成的网络结构附加的延迟也较少。CMU的实验表明，通过增加交换器的个数，Nectar网可以支持近100台工作站构成的机群并行计算系统。 2. Hcluster系统 Hcluster是黑

51、龙江大学信息技术研究所研制的微型计算机机群并行计算系统。 Hcluster并行计算系统目前由16台586高档微型计算机组成。16台计算机由我们自行研制的16台通信处理器和互连网络连接成4维Hypercube并行计算结构。Hcluster的系统结构如图9.4.4所示。图9.4.4. Hcluster的系统结构。图9.4.4中的每个处理结点由一台586微型计算机和一台通信处理器构成，其结构如下: 每个通信处理器由一台微处理器、通讯接口和高速缓冲器组成。 为了解决网络瓶颈问题，Hcluster摆脱了局域网络的束缚， 使用了一个具有Hypercube拓扑结构的通信网络。这个网络具有如下的特点: 1.

52、具有通信性能很高的Hypercube网络拓扑结构。 2. 突破了总线式通信网络的局限性，实现了网上多计算机并行通信, 即多计算机可同时在网上物理地传输信息。 3. 实现了网络物理链路的多位并行信息传输, 克服了局域网物理链路顺序性问题。 4. 实现了计算与通信过程的重叠，提高了系统的并行性。 5. 提供了简便高效的通信协议和消息传递机制，减少了通信延迟。 目前，Hcluster的信息传输率峰值可达每秒300兆位。 如果使用高速元器件，信息传输率可达每秒千兆位。Hcluster已经用于实现并行数据库管理系统。实验表明，Hcluster具有很高的效率和性能。9.4.4 机群并行计算系统的软件环境

53、我们在9.4.3节介绍了机群并行计算机系统的硬件环境。显然，仅有硬件环境，机群并行计算系统还不能有效地支持并行程序的开发和运行。软件开发环境是机群并行计算机系统必不可少的重要组成部分。最近几年，出现了一些基于机群并行计算机系统的软件开发环境，其中影响较大的是PVM和Express系统。本节简单介绍一下这两个系统。 1. PVM并行软件环境 PVM(Parallel Virtual Machine)是一个以UNIX基础，以TCP/IP为通信协议的并行计算机机群软件环境。PVM把多个异构计算机通过网络互连在一起，构成并行虚拟计算机系统。PVM是由美国OAK RIDGE国家实验室于1989年开始研制

54、的系统。田纳西大学、EMORY大学和卡内基梅隆大学也参加了PVM的研制工作，并得到了美国能源部、国家自然科学基金、CONVEX公司和田纳西州的资助。1995年初推出了3.3.7版。1995年9月推出了3.3.9版。与PVM配套的异构计算机网络环境HeNCE和可视化工具XPVM已经被推广使用。很多标准软件系统正在移植到PVM平台。 PVM支持的结点机可以是并行机、向量机、工作站等，网络可以是ETHERNET、FDDI等。在这个机群并行计算软件环境中，用户可以指定其中的任意一台结点机为主机。PVM中并行执行的基本单位是任务。任务与UNIX的进程类似，通常就是一个UNIX进程。PVM的基本功能就是支持多任务在多个结点机上并行执行。PVM提供了控制多任务并行执行和实现多任务间通信同步的软件工具。PVM支持FORTRAN和C语言。 PVM软件环境由两部分组成。第一部分是PVMD。PVMD运行在所有结点机上。用户使用PVM时，首先需要在一个网络结点机上执行PVMD。这个结点机上的PVMD将启动其它节点机上的PVMD，共同组成一个由用户定义的虚拟并行计算机。应用程序可以在任一结点上执行。多个用户可以配置多个相互重叠的虚拟机。每个用户可以同时执行多个应用程序。 组成PVM的第二部分是PVM函数库。PVM以函数的形式与用户程序接口，向用户提供各种服务。用户程序需要