并行处理技术.ppt

1、第5章 并行处理技术,5.1 计算机系统结构中并行性的发展 5.2 SIMD并行处理机 5.3 SIMD计算机的互连网络 5.4 网络特性 5.5 静态连接网络 5.6 动态连接网络 习题5,5.1 计算机系统结构中并行性的发展,5.1.1 并行性的基本概念 1. 并行性的定义 所谓并行性(parallelism)是指在数值计算、数据处理、信息处理或是人工智能求解过程中可能存在某些可同时进行运算或操作的部分。开发并行性的目的是为了能进行并行处理，以提高计算机系统求解问题的效率。,例如单体多字存储器，每次访存时能同时读出多个字，以加快CPU的访存操作。再如超标量流水线，它通过在CPU中重复设置多

2、条流水线，由多个相同的流水线子部件来同时完成对多条指令的解释。这些都是靠器件简单的重复来实现的。 并行性有更广义的定义，如单处理机中指令的重叠解释方式和流水方式，操作系统中的多道程序分时并行，都是广义上的并行。,由此可以看出，并行性有二重含义，即同时性(simultaneity)和并发性(concurrency)。同时性是指多个事件在同一时刻发生，如SIMD阵列处理机中各PE的并行操作、超标量流水处理机中多条指令的并行解释。并发性是指多个事件在同一时间段内发生。如操作系统中的多道程序分时并行、指令的流水解释过程和运算操作的流水处理过程等。,2 . 并行处理的概念 所谓并行处理是指一种相对于串行

3、处理的信息处理方式，它着重开发计算过程中存在的并发事件。在进行并行处理时，其每次处理的规模大小可能是不同的，这可用并行性颗粒度(granularity)来表示。,颗粒度是衡量软件进程所含计算量的大小，最简单的方法是用程序段中指令的条数来表示。粒度的大小决定了并行处理的基本程序段是指令、循环，还是子任务、任务或作业。颗粒度的大小一般分为细粒度、中粒度和粗粒度三种，若程序段中指令条数小于500条，则称为细粒度，500条到2000条指令之间则称为中粒度，大于2000条则称为粗粒度。 假定系统中共有n个处理器，颗粒度大小G还可用以下公式来表示： G=,TW,TC,式中，TW表示所有处理器工作负载(wo

4、rkload)的总和，即TW=twi，这里的工作负载实际上就是进行计算的时间；TC表示所有处理器的通信开销(communication overhead)的总和，即TC=tci，这里的通信开销实际上就是进行通信的时间。 由G的表达式可见，当工作负载一定时，粒度愈细，表明通信开销愈大；反之，粒度愈粗，表明通信开销愈小。,n,n,i=1,i=1,3. 并行性的等级 并行性有不同的等级，而且从不同角度来观察时，会有不同的划分方法。在程序执行过程中，根据并行进程中颗粒度的大小不同，通常可划分成以下五个等级：作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级，如图5.1所示。,图5.1 程

5、序执行过程中的不同层次的并行性,通常，并行处理是指在这些层次上的任何一级或多级上的并行性开发。层次越高的并行处理粒度就越粗，而低层上的并行处理粒度就较细。粗粒度并行性的开发主要采用MIMD方式，它开发的主要是功能并行性。而细粒度并行性的开发则主要采用SIMD方式，它开发的主要是数据并行性。,5.1.2 实现并行性技术的途径 计算机系统中实现并行性技术的途径多种多样，但就其基本思想而言，可归纳为以下三种途径： 1. 时间重叠（time-interleaving） 时间重叠是指在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速

6、度。,例如指令的流水解释过程，它通过把指令的解释过程划分成若干个相互联系的子过程，每一个子过程由专门的子部件来完成，利用时间重叠的方式解释不同的指令。采用时间重叠的方式基本上不需要增加硬件设备就可提高系统的速度和性能价格比。,2. 资源重复（resource-replication） 资源重复是指在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。随着硬件价格的降低，这种方式在单处理机中被广泛使用，而多处理机本身就是资源重复的结果。 例如热备用系统、容错系统等，它们根据不同性能和成本的要求，利用资源重复的方式组织冗余部件，以提高系统的可靠性。,再例如阵列处理机，它通过设置多个处

7、理单元，在同一控制器的控制下，各执行部件同时对分配给自己的数据完成同一种运算，利用资源重复的方式来提高整个系统的性能。,3. 资源共享（resource-sharing） 资源共享是指利用软件的方法让多个任务按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地也可以提高整个系统的性能。 例如利用共享CPU、主存资源、大容量的磁盘存储器等，以降低系统价格，提高设备利用率，如多道程序、分时系统、计算机网络等。,5.1.3 计算机系统结构中并行性的发展 计算机系统结构中的并行性已从顺序标量计算机中的完全顺序处理，逐步向重叠、流水、多功能部件并行、多数据并行、多任务并行的并行处理方向发展，如

8、图5.2所示。,图5.2 从顺序处理到多数据、多任务并行处理的发展,标量处理机只能进行指令的顺序解释，先行技术的出现，使I/E（指令读取/译码和执行）操作重叠起来，从而能实现功能并行性。支持功能并行性的方法有两种：一种是同时使用多个功能部件，另一种是在不同处理级别实施流水线技术。流水线技术对处理向量数据元素的重复相同的操作表现出强大的威力，从而产生了向量流水处理机，主要用于向量数据的并行处理。并行性的开发主要有两种途径，即隐式并行性与显式并行性。,隐式并行性的开发是指采用传统的C、Fortran、Lisp或Pascal等语言来编写源程序。顺序编码的源程序可用并行化编译器编译成并行目标代码，此编

9、译器必须能检测并行性，并能分配机器资源。显式并行性的开发是指程序员直接利用并行程序设计语言C、Fortran、Lisp或Pascal等开发出并行语言源程序。并行性在用户程序中显式说明，这将大大减轻编译器的负担，而编译器只需根据程序并行性说明，将资源分配给目标机器。,向量处理机包括存储器-存储器工作方式的向量处理机和寄存器-寄存器工作方式的向量处理机，两者的不同之处在于源向量和结果向量是来自于存储器还是寄存器。1976年以后开发的向量处理机基本上都属于寄存器-寄存器工作方式的向量处理机，它通过在处理机中设置有较大容量的向量寄存器，让大多数操作都在向量寄存器间进行，从而提高了向量处理的速度。,并行

10、处理机从整体上可分为两类，一类是用于数据并行处理的SIMD并行处理机，典型的SIMD并行处理机有相联处理机和阵列处理机，以及早期的大规模并行处理机；另一类是用于作业和任务级并行处理的MIMD并行处理机。MIMD并行处理机可分为两大类，即共享存储器多处理机和消息传递型多计算机。多处理机和多计算机之间的主要差别在于存储器共享和处理机间通信机制的不同。,5.2 SIMD并行处理机,本节将讨论以SIMD方式工作、采用资源重复的并行性措施的SIMD并行处理机，主要介绍SIMD并行处理机的结构与特点、阵列处理机ILLIAC-IV的处理单元阵列结构，以及适合于在阵列机上进行加工的并行算法。,5.2.1 SI

11、MD并行处理机的基本结构与特点 SIMD并行处理机由于存储器采用的组成方式不同，有两种基本结构，即具有分布式存储器结构的SIMD并行处理机和具有集中式共享存储器结构的SIMD并行处理机。 1. 分布式存储器结构 分布式存储器结构的SIMD并行处理机如图5.3所示。它包含重复设置的多个相同的处理单元PE(Processing Element)，每个PE都拥有自己独用的本地存储器LM(Local Memory)。,图5.3 分布式存储器结构的阵列处理机,计算机全部工作所用的程序和数据由一个与用户相连的主机提供，主机的工作与一般计算机完全相同，即控制I/O操作，从外设获得程序和待处理的数据，存入一个

12、大容量存储器，将处理结果进行图示或其它形式输出。 当启动处理机阵列工作时，主机就将程序和数据取入控制部件存储器中。先将要处理的数据通过数据总线存入各个PE所带的本地存储器LM，PE所处理的数据就从本地存储器中取得，并将结果写回本地存储器。,本地存储器中的内容根据需要通过数据总线与主机进行交换。控制部件存储器中的指令逐条地送入阵列控制部件译码，将其中的标量指令送入一个专设的标量处理机处理。而将向量指令用广播总线送到各PE中，使各PE同时执行同一条指令。从执行指令的过程看出，SIMD计算机每次只能执行一条指令，即仍然是串行的，但是从执行数据的过程来看，由于多个处理单元在同时执行一条指令时，产生了多

13、个数据流，因此具有数据并行性。,各个PE通过互连网络ICN(Interconnection Network)实现相互连接。控制部件对控制程序进行译码，其结果用以控制网络的寻径，以便完成如点对点通信、广播、聚集等功能。PE之间的同步是由控制部件的硬件实现的，即保证各PE在同一周期中执行同一条指令。并且可以通过对屏蔽位的设置，控制一个PE是否执行当前指令。 现在出现的SIMD计算机，几乎都是基于分布式存储器结构的系统。各种系统之间的主要差别在于采用了不同的互连网络。,2. 集中式共享存储器结构 集中式共享存储器结构的SIMD并行处理机如图5.4所示。与图5.3相比，两者只是在存储器的结构上有明显的

14、区别，其它部分基本上是相同的。共享存储器结构中将系统的存储器作集中管理，为了提高各PE访问存储器的速度，在组成上将存储器设计成多模块交叉存储器，如图中的SM0SMK-1。这些存储器模块为各PE所共享，即任一个PE都可以访问任一个存储体。图5.4中的互连网络用来实现各PE与共享存储器SM(Shared Memory)的各个模块之间的通信，互连网络由阵列控制部件根据对控制指令的译码进行控制。,图5.4 集中式共享存储器结构的阵列处理机,这种结构形式比较适合于用在处理单元数目不太大的情况下。当处理单元增加时，为了获得互不冲突的存储器分配就将耗费大量的系统资源，大大降低系统的性能价格比。BSP(Bur

15、roughs Scientific Processor)计算机采用了这种共享存储器结构，系统中的16个处理单元通过一个1617的对准网络访问17个共享存储器模块。对准网络包含完全交叉开关以及用来实现数据从一个源PE广播至几个目的PE以及当几个源PE寻找一个目的PE时能分解冲突的硬件。根据存储器设计的理论可知，在PE与存储器数目互质的情况下，就有可能实现无冲突访问。,无论是哪一种结构的SIMD并行处理机，其基本结构都由用于数组和向量运算的处理单元阵列、用于标量处理的标量处理机、用于PE和互连网络控制的阵列控制部件、用于系统输入输出及操作系统管理的主机，以及用于PE之间、PE和存储器模块之间进行数

16、据寻径的互连网络等五个部分组成。,3. SIMD并行处理机的主要特点 SIMD并行处理机的主要特点如下： (1)SIMD并行处理机利用的是资源重复，而不是时间重叠，利用并行性中的同时性，而不是并发性； (2)SIMD并行处理机是以某一类算法为背景的专用计算机；这是由于SIMD并行处理机中通常都采用简单、规整的互连网络来实现处理单元间的连接操作，从而限定了它所适用的求解算法类别。,(3)SIMD并行处理机的研究必须与并行算法研究密切结合，以使它的求解算法的适应性更强一些，应用面更广一些； (4)从处理单元上看，由于各处理单元都是相同的，因而可将SIMD并行处理机看成是一个同构型并行处理机。但从整

17、体上看，实际上的SIMD并行处理机是由标量处理机、处理机单元阵列、主机构成的一个异构型多处理机系统。,5.2.2 ILLIAC-IV的处理单元阵列结构 ILLIAC 阵列处理机是世界上最早采用SIMD结构的计算机，它由美国宝来公司和伊利诺依大学1965年就开始进行研制，从1972年开始正式生产。在阵列处理机上并行算法的研究是与结构紧密联系在一起的，而阵列处理机处理单元阵列的结构又是适合于一定类型计算问题而设计的专门结构。所以我们这里先介绍阵列处理机ILLIAC 的处理单元阵列结构，再介绍阵列处理机的并行算法。,ILLIAC 处理机阵列采用分布式存储器结构，如图5.5所示。每个处理单元PE都配有

18、自己专用的本地存储器LM，以及相应的存储器逻辑部件，组成一个处理部件PU(Processing Unit)。阵列共由64个处理部件组成，它们排列成平面矩形的88阵列结构，每一个PU都与其四个邻近的PU相连，即按上、下、左、右方向可以与其它PU通信。为了使处于边界或角上的PU并不因其连接而影响通信，PU在连接上采用了纵向连环，横向连接成一种闭合的螺线形状，所以其阵列又称闭合螺线阵列。,这种连接方式最大的好处在于使各PU之间的通信延时大为减少，任意两个PU之间的通讯可以用软件方法寻找最短径进行。例如，在图5.5中从PU10到PU46的通信路径为：PU10-PU9-PU8-PU0-PU63-PU62

19、-PU54-PU46，中间不超过7步。一般而言，在nn个PU组成的阵列中，这种连接可以使任意两个PU间的最短距离不超过（n-1）步。,图5.5 ILLIAC 处理单元的互连结构,5.2.3 阵列处理机的并行算法 1. 矩阵加并行算法 在阵列处理机上，解决矩阵加算法是最简单的一维情形。设A和B是nn阶矩阵，A、B的和矩阵为C，它也是nn阶矩阵。矩阵加的算法为： A+B=C=(cij)nn cij=aij + bij,由公式可以看出，计算cij时只与aij和bij有关。因此把aij和bij分布在同一个处理单元的局部存储器中，且结果cij也存放在此局部存储器中。图5.6给出了处理单元个数为64，A、

20、B、C为88矩阵的存储器分配示意图，其中为存储器地址。,图5.6 矩阵加算法的存储器分配示意图,假设求和所需的时间为t加，下面我们分两种情况来讨论矩阵加所需的总的计算时间。 (1)若处理单元的个数Pn2，则每个处理单元的本地存储器中对应的存放aij、bij和cij，所有处理单元并行对自己局部存储器的元素执行求和运算，所需的总的计算时间为： TP=t加,(2)若处理单元的个数Pn2，则需将n2个元素均匀地分布到各处理单元的局部存储器中，每个局部存储器中分配的元素个数为n2/P(若不为整数,则有的处理单元多分配1个元素,有的少分配1个元素)，所有处理单元分n2/P次串行对P个元素进行并行求和运算，

21、所需的总的计算时间为： TP=n2/Pt加,2. 矩阵乘并行算法 由于矩阵乘是二维数组运算，故它比矩阵加要复杂一些。设A和B是nn阶矩阵，A、B的乘积矩阵为C，它也是nn阶矩阵。矩阵乘的传统串行算法为： AB=C=(cij)nn cij=aikbkj,k=0,n-1,AB的最好串行算法的基本运算量为n3次乘法和加法，即问题规模(工作负载workload)为W=n3。设执行一次乘法所需的时间为t乘，加法的总时间为t加，则串行运行时间为T1=n3(t乘+t加)。 设处理单元个数P为某一整数m的平方(P=m2)，P个处理单元互连成mm的二维双向链路环网结构，下面我们分两种情况来讨论矩阵乘所需的总的计

22、算时间。,(1)若处理单元的个数Pn2 设P为某一整数m的平方(P=m2)，且n为m的整数倍。将A、B与C以适当方式分为P块Aij、Bij和Cij(0i,jm-1)，每块为(n/mn/m)子矩阵，将这些块映象到mm个逻辑处理阵列机上，每个处理机记为Pij，Pij存储Aij，Bij，并计算Cij。图5.7给出了处理单元个数为64，6464矩阵A的矩阵分块和存储器分配示意图，矩阵B、C的矩阵分块图和存储器分配与A相似。,在计算Cij时，需要所有子矩阵块Aik、Bkj(0km-1)，因此A的块在处理机阵列每行作多对多广播，而B的块在处理机阵列每列作多对多广播。当Pij接收完Ai0，Ai1，Ai(m-

23、1)；B0j，B1j，B(m-1)j后，执行子矩阵乘法和加法运算。下面分析这种并行算法的计算时间和通信时间。,计算时间 用Pij计算Cij时，需要对(n/mn/m)阶子矩阵中的每个元素cij进行n次乘法和n次加法(cij=aikbkj)，故Pij的运行时间为： nn/mn/m(t乘+t加)=n3/m2(t乘+t加)=n3/P(t乘+t加),n-1 k=0,通信时间 设ts为发送消息的启动时间，tw为传送每个浮点数时的通信时间，由于算法需要在由m台处理机组成的组中作二次多对多广播，每次包含处理机阵列上所有行或列的m次并发广播，发送消息的个数由n2/P个元素的子矩阵组成，所以整个通信时间为： 2(

24、mts + mn2/Ptw)=2(mts + n2/mtw) 整个并行运行时间为： TP=n3/m2(t乘+t加)+ 2(mts + n2/mtw),图5.7 6464矩阵A的矩阵分块和存储器分配示意图,(2)若处理单元的个数Pn2 在这里，每个处理单元可单独处理一个矩阵元素cij，它实际上是前一种情况在m=n下的一个特例。 当Pn2时，只使用n2个处理单元，这些处理单元记为Pij(0i,jn-1)。A、B与C矩阵的Aij、Bij和Cij(0i,jn-1)元素，映象到P(P=n2)个逻辑处理阵列机上，即Pij存储Aij，Bij，并计算Cij。,在计算Cij时，需要所有Aik、Bkj(0kn-1

25、)，因此A的元素在处理机阵列每行作多对多广播，而B的元素在处理机阵列每列作多对多广播。当Pij接收完Ai0，Ai1，Ai(n-1)；B0j，B1j，B(n-1)j后，执行子矩阵乘法和加法运算。下面分析这种并行算法的计算时间和通信时间。,计算时间 用Pij计算Cij时，需要进行n次乘法和n次加法(cij=aikbkj)，故Pij的运行时间为： n(t乘+t加),n-1 k=0,通信时间 设ts为发送消息的启动时间，tw为传送每个浮点数时的通信时间，由于算法需要在由n台处理机组成的组中作二次多对多广播，每次包含处理机阵列上所有行或列的n次并发广播，每次发送1个消息(浮点数)，所以整个通信时间为：

26、2(nts + ntw)=2n(ts + tw),整个并行运行时间为： TP=n(t乘+t加)+ 2n(ts + tw) 值得注意的是：对于具有分布式存储器的并行处理机系统能否发挥其并行性，与数据在存储器的分布状况是密切相关的。而并行处理的速度除了与数据的存储器分布有关外，还与并行度和程序的粒度有关，这些内容将在第7章详细介绍。,3. 累加和并行算法 对于累加和这样的递归操作，为了加快并行计算，常采用递归折叠方法。例如，某一个向量含有N个向量元素，要求这些元素的累加和。如果在单机中采用串行方法来完成，则需要进行N-1次加法。现用N个处理单元来求和，且假定每个处理单元已事先分配有一个向量元素，如

27、果仍用串行方法，则只能由一个处理单元来完成累加操作，所有其它处理单元将把它们的向量元素送往此处理单元，显然，这仍需要进行N-1次加法。对于分布式存储器的并行处理机，还会增加数据传送的时间延迟。因此，尽管用并行机来求累加和，但由于使用串行方法，速度上没有任何提高。,下面我们来分析递归折叠方法是如何提高并行求和速度的，为讲述的方便，假设处理单元的个数为8个，即PE0PE7，采用分布式存储器并行处理机系统，PEi的本存储器LMi中存放向量的一个元素Ai。对向量的8个元素A0A7求累加和的递归折叠过程如图5.8所示。,假定在第1步时，所有下标为奇数值（即1，3，5，7）的PE，将它们的向量元素送往一个

28、下标为偶数值的PE（即1到0，3到2等），然后所有下标为偶数值的PE把它们所收到的向量元素与它自己拥有的向量元素并行相加，从而形成4个部分和，所有下标为奇数的PE不参加求和运算。第2步时，将重复这一过程，PE2将把它得到的部分和送往PE0，而PE6的部分和送往PE4，然后PE0和PE4分别将所收到的部分和与它们所保留的部分和并行相加。,在这一过程中，除PE0和PE4外的其它所有PE都不参加求和运算。第3步时，PE4将它求得的部分和送往PE0，然后PE0将所收到的部分和与它自己保留的部分和相加，得到最后的累加和。整个累加求和过程仅需3次并行传送和3次并行相加。,图5.8 8个PE的递归折叠求和过

29、程,一般而言，对于在P个处理单元上实现P个元素累加求和，需要折叠log2P次，并行相加log2P次，并行传送数据的次数根据各PE间互连网络的拓扑结构不同而有很大差异。设加法1次所需的时间为t加，并行相加的总次数为n，数据在两个相邻处理单元之间传送一次所需的时间为t传，并行传送数据的总次数为x，则并行处理所需的总的时间为：nt加+ xt传 。,在求累加和的过程中，并非每个处理单元始终参加运算。在第1步，处理单元1、3、5、7不参加运算；在第2步，处理单元1、2、3、5、6、7不参加运算；在第3步，处理单元17不参加运算。这些处理单元在这些阶段处于不活跃状态是由控制器CU借助屏蔽方式来实现的。,例

30、5.1 A=(aij)，B=(bij)为6464的矩阵。有1台由64个带本地存储器的PE组成的SIMD并行处理机，64个PE互连成88的两维双向链路的环网结构。 (1)画出矩阵元素aij和bij在各PE本地存储器上的初始化分配情况。 (2)试设计一种矩阵乘算法，使之在这种机器上执行的时间最短。 (3)假设每个PE在每个周期可以执行一次乘法、一次加法或一次移数（把数据移给它4个相邻的PE之一）操作。,在把数据传给相邻PE之前，应该首先对本地数据进行乘法和加法操作。SIMD移数操作可以在循环连接的环网上向上、下、左、右进行。估算矩阵乘算法总共需要多少个SIMD指令周期，这包括所有的运算和数据寻径操

31、作时间在内，最后乘积C=AB=(cij)在各个PE的存储器中没有拷贝。 解：(1)矩阵元素aij在各PE本地存储器上的初始化分配情况如图5.7所示，矩阵元素bij在各PE本地存储器上的初始化分配情况与aij相似。,(2)矩阵乘算法为：因为P=82，P642，且64为8的整数倍。将A、B与C以图5.7的方式分为64块Aij、Bij和Cij(0i,j7)，每块为(88)子矩阵，将这些块映象到88个逻辑处理阵列机上，每个处理机记为Pij，Pij存储Aij，Bij，并计算Cij。在计算Cij时，需要所有子矩阵块Aik、Bkj(0k7)，因此A的块在处理机阵列每行作多对多广播，而B的块在处理机阵列每列作

32、多对多广播。当Pij接收完Ai0，Ai1，Ai7；B0j，B1j，B7j后，执行子矩阵乘法和加法运算。,(3) t乘、t加和tw 均为一个指令周期，ts忽略不计，n=64，m=8 整个矩阵乘算法所需的总的运行时间为： TP =n3/m2(t乘+t加)+ 2(mts + n2/mtw) =643/82(1+1)+2(0+642/81) =9216(指令周期),5.3 SIMD计算机的互连网络,5.3.1 互连网络的设计准则 在SIMD计算机中，无论是处理单元之间（具有分布式存储器的并行处理机结构形式），还是处理单元与存储体之间（具有集中式共享存储器的并行处理机结构形式），都要通过互连网络实现信息

33、交换。因此，互连网络性能好坏对SIMD计算机系统的运算速度、处理单元的利用率、求解算法适应性、拓扑结构灵活性以及成本等有很大影响，所以，它是SIMD计算机中重要的研究课题之一。,衡量互连网络性能好坏的因素主要有结点的度、网络直径、网络带宽、可靠性和成本。在设计互连网络时应考虑以下的四个特征： 1. 通信工作方式 通信工作方式可分为同步和异步两种。在同步方式中，不论是各个PE对数据进行并行操作还是由控制器向处理单元广播命令，都由统一的时钟来加以同步。SIMD并行机都采用同步方式。异步方式则不用统一时钟加以同步，各个处理单元根据需要相互建立动态连接。,2. 控制策略 控制策略分为集中和分散两种。集

34、中式控制由一个统一控制器对各个互连开关状态加以控制，而分散式控制则由各个互连开关自身实行管理。一般的SIMD并行机都采用集中控制。,3. 交换方式 交换方式分为线路交换和分组交换两种。线路交换是在整个交换过程中，在源和目标结点之间建立固定的物理通路，适用于成批数据传送。分组交换则把要传送的一个信息分成多个分组，分别送入互连网络。这些分组可通过不同的路由到达目标结点。因此，较适合于短数据报文的传送。SIMD并行机一般采用线路交换，因为处理单元间的联接比较紧密。MIMD多机系统则往往采用分组交换方式。,4. 网络拓扑 网络拓扑分为静态和动态两种。这里的拓扑是指互连网络中各个结点间的连接关系，通常用

35、图来描述。有关网络拓扑的内容我们将在本章的最后二节作详细的介绍。,5.3.2 互连函数的表示 使用互连函数是为了描述各处理单元之间或处理单元与共享主存各模块之间传递数据时，互连网络的出端号和入端号的一一对应关系。如果定义互连网络的所有入端号分别为0、1、.、j、.N-1，那么互连函数f(j)则表示的是入端号j连至出端号f(j)的函数对应关系。由于在实现处理器之间的互连时，互连网络的入端和出端实际上都是属于同一组处理单元的输出端和输入端，所以互连网络实际上反映了一种“排列（组合）”关系。,互连函数的分析工具一般有二种： (1)互连网络中入、出端的连接图；由于当处理单元的个数较多时，连接图在描述各

36、结点之间的连接时显得非常复杂，并且难以体现出各结点连接的内在规律，因此此分析方法一般只在结点数比较少的情况下使用。 (2)采用某种互连函数的函数关系式。也就是说，把所有入端j和出端f(j)都使用二进制编码，从二者的二进制编码上找出其对应的函数规律，并用函数关系式来表示。,5.3.3 单级互连网络 1. 立方体单级网络（Cube）,图5.9 8个处理单元的二元三维立方体结构图,这里的立方体单级网络实际上是二元三维立方体单级网络，Cube的名称来源于图5.9所示的二元三维立方体结构。立方体的每一个顶点代表一个处理单元，处理单元的编号用其所在的位置，即坐标（zyx）表示。 三维的立方体单级网络有3种

37、互连函数：Cube0、Cube1和Cube2，连接方式如图5.10所示。从图5.10中可以看出，Cube函数下标数字0（或1、2）表示相连的入端和出端的二进制标号只在右起第0位（或第1位、第2位）上有差别，即仅在该位上的代码“0”、“1”互反，其余各位代码都相同。,图5.10 8个处理单元的立方体单级网络连接图,推广到n维的情形，立方体单级网络共有n=log2N种互连函数，即： Cubei（Pn-1PiP1P0）= Pn-1PiP1P0 其中，Pi为入端标号的二进制代码第i位，且0in-1。对于n维立方体单级网络，要实现任意两个处理单元之间的连接，最多需使用n次不同的互连函数，因此n维立方体单

38、级网络的最大距离为n。,2. PM2I单级网络（是加减2i的简称，Plus-Minus 2i）,图5.11 8个处理单元的PM2I互连网络的部分连接图,PM2I单级网络能实现j号处理器与j2i mod N号处理器的直接相连，互连函数为： PM2+i（j）=j+2i mod N PM2-i（j）=j-2i mod N 式中，0jN-1，0in-1，n=log2N，N为处理器的个数。因此，它共有2n个互连函数。,例如，对于N=8，各互连循环为： PM2+0：（0 1 2 3 4 5 6 7） PM2-0：（7 6 5 4 3 2 1 0） PM2+1：（0 2 4 6）（1 3 5 7） PM2-

39、1：（6 4 2 0）（7 5 3 1） PM22：（0 4）（1 5）（2 6）（3 7）,由于PM2I网络总存在有PM2+（n-1）=PM2-（n-1），所以实际上，PM2I网络只有2n-1种不同的互连函数。SIMD并行处理机ILLIAC-中的64个处理单元间的互连，实际上就是只采用了PM2I互连网络中的PM20和PM23这四个互连函数。PM2I单级网络的最大距离为n/2。在图5.11中给出了PM2I互连网络的部分连接图。,3. 混洗交换互连网络（Shuffle-Exchange） 混洗交换互连网络由全混洗和交换两种互连函数组成。 (1)全混洗 全混洗所用的互连函数为： Shuffle（P

40、n-1Pn-2P1P0）= Pn-2P1P0Pn-1 从图5.12中可以看出，其连接规律是把全部按标号次序排列的处理器从中间分为数目相等的两半，前一半和后一半在连至出端时正好一一隔开。,由于它所实现的处理单元之间的连接，就好象将一叠扑克牌对分后均匀洗牌所实现的理想的“全混洗”状态一样，因此称这种互连网络为全混洗单级互连网络。在此互连网络中，如果经过n=log2N次全混洗连接后，除了编号为全“0”和全“1”的处理器外，各个处理器都遇到了与其它处理器连接的机会。,图5.12 8个处理单元的全混连接,(2)交换 由于单一的全混洗互连网络不能实现二进制编号为全“0”和全“1”的处理器与其它任何处理器的

41、连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络，其连接图如图5.13所示。 图5.13中虚线表示全混，实线表示交换。在混洗交换网络中，最远的两个入、出端号是全“0”和全“1”，它们的连接，需要经过n次交换和n-1次混洗，所以混洗交换网络的最大距离为2n-1。,图5.13 8个处理单元的全混交换互连网络连接图,4. 蝶形互连网络（Butterfly） 蝶形互连网络的互连函数为： Butterfly(bn-1bn-2b1b0)=(b0bn-2b1bn-1) 即将二进制地址的最高和最低位相互交换位置。图5.14为8个处理单元的蝶形互连网络的连接

42、图。,图5.14 8个处理单元的蝶形互连网络连接图,5.4 网络特性,在后面的章节中，我们要介绍将计算机子系统互连在一起构造成多处理机或多计算机的静态和动态网络，这些网络可将集中式系统或分布式系统中内部的处理机、存储模块以及磁盘阵列连接起来。这里我们先介绍网络特性和寻径功能，然后再介绍组成网络的拓扑结构。,5.4.1 结点度和网络直径 与结点相连接的边(链路或通道)数称为结点度(node degree)。在单向通道的情况下，进入结点的通道数叫做入度(in degree)，而从结点出来的通道数则称为出度(out degree)。结点度就是入度与出度之和。结点度反映了结点所需要的I/O端口数，也即

43、反映了结点的价格。因此，结点度应保持恒定，为了降低价格，应尽可能使它小。,网络直径(network diameter)是网络中任意两个结点间最短路径的最大值。路径长度用遍历的链路数来度量。所以网络直径也是指任意两个结点间不同行程数的最大值，这是说明网络通信性能的一个指标。因此，从通信的观点来看，网络直径应当尽可能地小。 网络对称性(network symmetry)可以这样描述，如果从网络任意结点看上去拓扑结构都是相同的，便称该网络是对称的，否则网络是非对称的。网络的对称性可提高可扩展性和寻径的效率。,5.4.2 聚集带宽和等分带宽 对于一个给定网络，聚集带宽(aggregate bandwi

44、dth)定义为从一半节点到另一半结点，每秒钟传输消息的最大位数或字节数。例如：HPS是一个对称式网络，包含512个节点，每个端口带宽为40MB/s，可计算出HPS的聚集带宽为：512/240MB/s=10GB/s。,一个有n个结点的网络的等分平面是一组连线，它的移动将把网络分为两个(n/2)个结点的网络。一个网络可以有许多个等分平面。最小的等分平面是指具有最小连线数的等分平面。一个网络的等分带宽(bisection bandwidth)定义为：每秒钟内在最小等分平面上通过所有连线的最大信息位数或字节数。 设b为穿越最小等分平面的链路数，w为每条链路的连线数，r为每条连线的数据传输率（单位为：位

45、/秒），那么该网络的等分带宽为B=bwr位/秒。,5.4.3 数据寻径功能 数据寻径网络用来进行PE间数据交换。这种寻径网络可以是静态的，如TMC/CM-2所用的超立方体寻径网络；也可以是动态的，如IBM GF 11所用的多级网络。在多级网络的情况下，数据寻径是通过消息传递来实现的。硬件寻径器可用来在多个计算机结点之间寻径传送消息。,图5.15 常见的数据寻径方式,寻径网络的功能较强，将有利于减少数据交换所需的时间，因而能显著地改善系统的性能。通常见到的PE之间的数据寻径功能包括个人通信(一对一或一对多)；广播、散射(一对多)；汇合/聚集、归约(多对一)；置换、循环移位、扫描、洗牌、全交换(多

46、对多)等。 一对一通信也称点对点(point-to-point)通信，仅有一个发送者和一个接收者。,一对多通信包括广播(broadcast)和散射(scatter)两种，广播操作是指其中一个进程(或称根进程)向所有进程(包括自己)发送相同消息。散射操作是通用化的广播操作，因为根进程对不同进程将发送一个不同的消息。 多对一通信包括汇合/聚集(gather)和归约(reduction)两种，汇合操作是指根进程从每个进程处接收一个不同消息，因此根进程总计接收了n个消息，这里的n是组的大小。归约是指某个根进程接收来自每个进程（包括自己）的局部值，并将它们在根进程中归约求和形成一个最后值。,多对多通信中

47、最简单的形式是置换(permutation)，其中每个进程只向一个进程发送并只接收一个进程发来的消息。如循环移位(circular shift)、扫描(scan)、全交换(total exchange)等。图5.15中给出了几种常见的数据寻径方式。,5.5 静态连接网络,互连网络的网络拓扑(networking topology)可以采用静态或动态的结构。静态网络(static network)由点-点直接相连而成，这种连接方式在程序执行过程中不会改变。动态网络(dynamic network)是用开关通道实现的，它可动态地改变结构，使之与用户程序中的通信要求匹配。,静态网络常用来实现集中式系

48、统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络包括总线、交叉开关和多级网络等，它们常用于共享存储器型多处理机中。这两类网络已在SIMD计算机中实现了PE间的数据寻径要求。,静态连接网络使用直接链路，它一旦构成后就固定不变。这种网络比较适合于构造通信模式可预测或可用静态连接实现的计算机。下面我们根据网络参数以及它们对网络通信的影响来介绍静态网络的拓扑结构。若无具体说明，假设网络中结点数N=2n。,5.5.1 线性阵列 这是一种一维网络，其中N个结点用N-1条链路连成一行，16个结点的线性阵列(linear array)如图5.16(a)所示。内部结点度为2，端结点度为1。网络直

49、径为N-1，N较大时，网络直径就比较大，等分带宽为1。线性阵列是连接最简单的拓扑结构，这种结构不具有对称性，当N很大时，通信效率很低。,5.5.2 环和带弦环 用一条附加链路将线性阵列的两个端结点连接在一起，就构成了环形网络，或简称环(ring)，16个结点的环形结构如图5.16(b)所示。环可以分为单向环和双向环两种。单向环只有一个方向，顺时针方向或逆时针方向。双向环有两个方向，当其中的一个单向环出现故障时，另一个环还可以继续工作。当两个环在同一处出现故障，则这种双向环结构就变成了线性阵列。单向环和双向环结构的结点度均为2，并且它们都是对称的。单向环的网络直径为N-1，双向环的网络直径为N/

50、2。,图5.16 线性阵列、环、度为3和4的两种带弦环、循环移数网络、全连接等6种网络拓扑结构,分别增加一条和两条附加链路就可以得到结点度分别为3和4的带弦环(chordal ring)，含16个结点的度为3和4的带弦环结构分别如图5.16(c)和5.16(d)所示。从图中可以看出，增加的链路愈多，则结点度愈高，网络直径愈小。,5.5.3 循环移数网络和全连接 图5.16(e)所示的是一个结点数为16的循环移数(barrel shifter)网络，它是将环上每个结点到与其距离为2整数幂的结点之间增加一条附加链而构成的。即如果|j-i|=2r，r=0，1，2，n-1，网络规模N=2n，则结点i与

51、结点j连接。这种循环移数网络的结点度为2n-1，网络直径为n/2。,16个结点的全连接网络(completely connected network)如图5.16(f)所示，任意两个结点间都有固定的线路进行连接。这种全连接网络是一个对称的网络，当网络规模为N时，结点度为N-1，网络直径为1，链路数为N(N-1)/2。,5.5.4 树形和星形 一棵5层31个结点的二叉树(binary tree)如图5.17(a)所示。顶部的一个结点称为根，底部的16个结点称为叶子。其它的称为中间结点。除了叶子结点之外，每个结点都有两个孩子结点。一般来说，一棵h层完全平衡二叉树应有N=2h-1个结点。最大结点度为

52、3，网络直径为2(h-1)。 星形(star)是一种2层树，若结点的个数为N，则结点度为N-1，网络直径为2。如图5.17(b)所示的是一个结点数为9的星形网络。,5.5.5 胖树形 为了解决二叉树中根结点可能会成为性能的瓶颈这一不足之处，设计了二叉胖树(binary fat tree)形结构，各结点之间的连接如图5.17(c)所示。胖树的链路数从叶结点往根结点上行方向逐渐增多，它就象一棵真实的树形结构，愈靠近根的方向，其枝叉就愈粗。,图5.17 二叉树、星形、二叉胖树等3种网络拓扑结构,5.5.6 网格形和环网形 一个44网格(mesh)形网络如图5.18(a)所示。这是一种比较流行的结构，

53、它已以各种变体形式在ILLIAC IV、MPP、DAP、CM-2等中得到了实现。一般来说，N=rk结点的k维网格的内部结点度为2k，网格直径为k(r-1)，由于边结点、角结点和中间结点的度不相同，很明显，图5.18(a)所示的纯网格形是一种不对称的网络结构。,图5.18(b)给出了一种44呈闭合螺线状的网格图。ILLIAC IV系统采用的就是这种拓扑网络结构，故称这种结构为ILLIAC网，它实际上与结点度为4的带弦环是等效的，它是一种不对称的拓扑结构。一个rr ILLIAC网格的网络直径为r-1，它仅为纯网格直径的一半。 图5.18(c)是一种44环网(torus)形结构，它的每行每列的结点都

54、呈环形连接。一般来说，一个rr二维环网的结点度为4，网络直径为2r/2，此网络是一种对称的拓扑结构。,图5.18 网格型、Illiac网、环形网、搏动式阵列等4种网络拓扑结构,图5.19 2元3维立方体、2元4维立方体和带环3-立方体等3种网络拓扑结构,图5.18(d)是为完成矩阵相乘而专门设计的博动式阵列(systolic array)，这是一类为某些数据流算法而设计的应用驱动阵列结构。静态博动式阵列可在多个方向上使数据流变成以流水线方式工作。由于结构固定，搏动式阵列要求匹配给定算法的通信结构。因此，搏动式阵列一旦为给定应用优化后，就难以有效实现其它算法。,5.5.7 超立方体 严格地说，超

55、立方体(hypercube)应称为2元n维立方体。一个有8个结点的3-立方体，即2元3维立方体如图5.19(a)所示。一般来说，一个n-立方体由N=2n个结点组成，它们分布在n维上，每维有2个结点。4-立方体可通过将两个3-立方体的相应结点互连组成，如图5.19(b)所示。,5.5.8 带环立方体 带环立方体(cube-connected cycles)结构是从超立方体改进而来的，如图5.19(c)所示。一个3-立方体（2元3维立方体）可改成带环3-立方体(3-Cube-Connected Cycles，简称3-CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替。若要组成带环

56、k-立方体，只需将k-立方体的每个角结点用k个结点组成的环来代替，如图5.19(d)所示，其它链路的连接方法与5.19(b)相似。,5.5.9 k元n-立方体网络 环形、网格形、环网形、2元n维立方体(超立方体)和Omega网络都是k元-n立方体网络(k-ary n-cube network)系列的拓扑同构体。如图5.20所示，就是一种4元-3立方体网络。,图5.20 4元-3立方体网络的拓扑结构（未画出隐藏部分的结点和连接）,在k元-n立方体网络中，参数k是基数或者说是沿每个方向的结点数，n是立方体的维数。这两个数与网络中结点数N的关系为： N=kn，(n=logkN),在表5.1中汇总了静

57、态连接网络的重要特性，在这些网络特性中，结点度的愈大，表示连接性愈好，但链路数总体上会随结点度的增加而增加，这样会使得网络的连接愈复杂，成本也愈高。若能实现所有结点的连接，结点度愈小愈好，当然要求相应的网络时延也是愈小愈好。等分带宽愈大，表示网络的带宽就愈大。网络直径愈大，表示通信的时间延迟就愈大，由表5.1可以看出，网络直径的变化范围很大。但随着硬件寻径技术不断革新，如采用虫蚀寻径技术，网络直径已不是一个严重问题，因为任意两结点间的通信延迟在高度流水线操作下几乎是固定不变的。,对称性会影响可扩展性和寻径效率。客观地说，网络的总价格随结点度和链路数增大而上升。网络直径小仍然是一种优点，但是，结

58、点间的平均距离可能是一种更好的度量指标。等分带宽可以用较宽的通道宽度来扩大。根据以上分析，环、网格、环网、超立方体、k元n-立方体和CCC都具备一定条件用以建造未来的MPP系统。,表5.1 静态网络特性一览表,例5.2 设计一种采用加、乘和数据寻径操作的算法，分别在下面两种计算机系统上用最短的时间来计算表达式S=A1B1+A2B2+ +A32B32。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE。试确定下列每种情况的最小计算时间。 (1)一台串行计算机，处理机中有一个加法器和乘法器，同一时刻只有其中一个可以使用。这种单处理机系统不需要数据寻径操作。,(2)一台有8个PE(PE0，PE1，PE7)的SIMD计算机，8个PE连成双向环结构。每个PE用1个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEj(mod 8)中，其中i=1，2，32。每个PE可在不同时刻执行加法或乘法。 (3)若将(2)中8个PE之间的连接由双向环结构改为单向环结构，结果又如何？,解：(1)采用单处理机系统串行处