并行处理技术-计算机系统结构.ppt

1、1,第九章并行处理技术9.1并行处理技术的发展9.2SIMD并行计算机(阵列机)9.3计算机互连网9.4MM的多处理机及多计算机系统9.5机群9.6网络计算9.7并行机的发展趋势,2,第九章并行处理技术9.1并行处理技术的发展9.1.1并行性基本概念所谓并行性是指在数值计算、数据处理、信息处理或是人工智能求解过程中可能存在某些可同时进行运算或操作的部分。,在进行并行处理时，其每次处理的规模大小可能是不同的，这可用并行性颗粒度来表示。,并行性主要是指同时性或并发性。同时性在时间概念上要求较严，它是指同一时刻发生的两个或多个事件。并发性是指在同一段时间间隔内发生的两个或多个事件。,并行性指一种相对

2、于串行处理的信息处理方式。它着重开发计算过程中存在的并发事件。,3,并行粒度大小G可用以下公式表示(假定系统中共有P个处理器)。,其中TC表示所有处理器通信的时间总和。,其中TW表示所有处理器进行计算的时间总和。,由(9.1)式可见，TC，G较小，表明处理粒度较细。当处理较细时，处量器间的通信量将加大，反之粒度较粗时，通信量较小。,(9.2),(9.3),4,并行性有不同的等级，从不同角度有不同的划分法：程序执行过程可划分五个等级：作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级。见图9.1,并行处理是指在这些层次上的任何一级或多级上的并行性开发。层次越高的并行处理粒度就越粗。

3、而低层次上的并行处理粒度就较细。,5,粗粒度并行开发主要采用MIMD方式。细粒度并行开发主要采用SIMD方式。并行处理技术的发展首先是从单处理机中所采用的并行处理技术方法逐步发展起来的。这些方法包括：多功能部件、流水线部件、使CPU和I/O部件操作重叠以及采用如多道程序和分时那样的软件方法。9.1.2并行性的开发策略开发并行性，一般采用资源重复、时间重叠和资源共享三种。资源重复：通过使用多功能部件，引入空间重复因素，例：几个完全相同的处理器受同一控制器控制的SIMD方式的工作系统，就是利用资源重复的例子。时间重叠：是在并行概念中引入时间因素，让多个处理过程在时间上相互错开，重叠使用同一套部件的

4、各部分，象流水操作。,6,资源共享：采用软件手段让多用户按时间片来轮流使用同一套硬件资源，以提高利用率，象多道程序和分时系统。并行性的开发按不同的等级可分为粗粒度和细粒度两种开发方式。,对作业或程序级并行性开发，主要对并行算法的分析。对任务级并行性开发，主要涉及如何分解任务，将任务中的各个子任务乃至各子任务中的各循环或例行程序分配到不同的处理器上,开发粗粒度并行性，主要采用软件手段。如,开发细粒度并行性：涉及到指令内的操作级与处理器的外特性和内特性密切相关，因此主要采用硬件手段，但通常还必须辅以必要的软件，随着RISC技术的发展，超标量、VLIW、超级流水线等技术的出现，更明显地发映了这一技术

5、的发展趋向。,7,9.1.3并行计算机系统的分类并行计算机系统通常以计算方式是SIMD或MIMD的以及存储器是共享的还是分布的这两个准则加以分类，一般可分为以下4类：共享存储一SIMD(SMSIMD)；分布存储一SIMD(DMSIMD)；共享存储一MIMD(SMMIMD)；分布存储一MIMD(DMMIMD)。阵列处理机单向量机系统,多向量机(MultiVectorProcessor，MVP)系统中有多套向量部件，但存储器是共享的，因此属于SM-MIMD类型。对称多处理器系统(SymmetricMultiprocessor，SMP)也属这一类型。MVP和SMP又被称为是UMA(UniformMe

6、moryAccess-均匀访问存储器)系统，因为系统中所有处理器对任何存储单元都有相同的访问时间。,当今的并行计算机系统大多以MIMD方式工作。,8,与UMA系统相对的系统称为NUMA系统，在NUMA系统中存储器是分布的，各个处理器对同一存储单元的访问时间可能是不同的，依赖于处理器在系统中所处的具体物理位置。显然，NUMA系统属于DM-MIMD类型。应注意的是，NUMA系统中的处理器可对远程存储器、(即非本地存储器)以load-store指令形式进行直接访问，因此该系统有一个统一的存储器逻辑地址空间。NUMA并行机系统按是否对Cache一致性提供硬件支持可进一步分为CC-NUMA(Cache-

7、CoherentNUMA)和NCC-NUMA(Non-Cache-CoherentNUMA)。当存储器全由Cache组成时就变为COMA(CacheOnlyMemoryArchitecture)系统。当并行计算机系统中的处理器必须以消息传递方式访问远程存储器时，则成为NORMA(NoRemoteMemoryAccess)系统，它也是DM-MIMD类型。NORMA系统按计算机间的互连紧密程度，又分为紧耦合和松耦合两种。,9,机群(Cluster)系统是松耦合的典型代表，而大规模并行处理MPP(MassivelyParallelProcessing)系统则是紧耦合的典型代表。图9.2所示为并行计算

8、机系统的分类情况。,10,Gustafson等人在1988年发现并用大量实验验证了这一规律，并据此提出了固定时间加速比模型。由于求解问题规模变大，而求解时间保持不变，必将使系统中各处理器处于忙碌状态，从而提高了系统中处理器的利用率。假设原来求解问题的工作负载为W，其中f百分比为可并行执行部分，而1-f百分比为顺序负载，不可并行执行。若在单处理器上执行，其执行时间为W，n个处理器上执行时，将工作负载扩大为W=(1-f)W+nfW，但n个结点并行执行的时间仍为W。由于工作负载扩大为W，则该扩大的工作负载在单处理器上执行时，所需的时间就将增大为W=(1-f)W+nfW,(9.4),11,扩大工作负载

9、后的固定时间加速比定义为：,(9.4),为了衡量加速比是在增加多少处理器的情况下才能获得的这一指标，通常使用效率E来加以表示：E=Sp/n,12,CU控制将指令广播给系统中各个PE，而所有活跃的PE将以同步方式执行该相同的指令(单指令流)，它们从相应的MM模块中取得自己所需要的数据对象(多数据流)。IN用来使各个PE之间或是PE和M之间实现方便的通信连接。IN有时也称为对准(Alignment)或排列(Permutation)网络。根椐MM模块是以分布方式存取还是集中方式存取，阵列机可分为两个基本结构：分布式存储器阵列机和集中共享存储器的阵列机。,9.2SIMD并行计算机(阵列机)9.2.1阵

10、列机的基本结构,阵列机通常由一个控制器(CU)、N个处理机单元(PE)、M个MM模块(M)以及一个互连网络部件(IN)所组成。,13,分布式存储器阵列机见图9.3(a)，其主要结构特征如下：,具有几个相同的处理单元PE，它由处理器P和局部存储器M组成。只要数据分配得当，各个Pi主要将从自己的局存Mi中获取数据进行操作。各个PE将通过IN实现相互间必要的数据交换，因此IN是单向的。CU中有自己的MM，以存放系统程序和用户程序，也可存放各个PE所需的共享数据。CU的主要功能是对指令译码和判别它应在何处执行。对于标量或控制类指令，CU本身中含有运算器，,图9.3阵列机两种结构类型,14,可以直接执行

11、。若是向量指令，它就将该指令广播给各个PE去执行。各个PE同步执行来自CU的操作命令，但并不是每个操作非得所有PE参加，CU将对PE实行屏蔽控制，只有哪些未被屏蔽的活跃的PE才可参加操作。CU还控制互连网络IN，使各个PE之间通过IN实现相互间的必要数据交换，当相互需要交换数据的两个PE不直接相连时，就需要经过它们之间的中间的PE来完成连接。共享MM的阵列机见P237图9.2(b)与分布式MM阵列主要区别在于：每个PE没有局存，MM以集中方式为所有PE经过IN共享。互连网受CU控制，用来构成PE和MM之间的数据交换通路，要求互连网具有同时连接PE-M和M-PE的双向性。系统中的一个PE可以与任

12、何另一个PE实现数据交换(只要有任何一个MM同时与这两个PE相接)。当两个需要交换数据的PE之间,15,没有共享的MM时，可能需要经过多次传送之后，方可实现交换。为形式化地表示阵列机特征，可用以下参数描述C=(N，F，I，M)N：为PE数F：为确定互连网结构及连接拓朴的互连参数I：指令集。M：屏蔽方式集合，每一种方式将PE集合分为活跃和非活跃两个子集。9.2.2阵列机的主要特点,采用资源重复方法引入空间因素，即系统中设置多个相同的处理单元开发并行性，这与利用时间重叠的流水线处理机是不一样的。此外它是利用并行性中的同时性，而不是并发性，所有处理单元必须同时进行相同的操作。,阵列机以单指令流多数据

13、流方式工作的，特点如下：,16,它是以某一类算法为背景的专用计算机。阵列机的研究必须与并行算法研究密切结结合，以使它的求解算法的适应性更强一些，应用面更广一些。从处理单元看，由于都是相同的，因而可将阵列机看成是一个同构型并行机，但它的控制器(CU)实质上是一个标量处理机，为了完成I/O操作及OS的管理，尚需一个前端机，因此实际的阵列机系统由上述三部分构成的一个异构型多处理机系统。9.2.3阵列机的并行算法阵列机是从求解诸如有限差分，矩阵计算，信号处理、图象处理、线性规划等一系列计算问题为背景发展起来的。以图象平滑化算法为例，该算法是用来平滑输入图象的灰度级。I和S分别以表示输入和输出图象。,1

14、7,设I和S均含有512*512个象素，I中每个点是一个8位不带符号的整数，用来表示256个灰度级。0：白色255：黑色平滑后图象中的每个点S(i，j)是I(i，j)和它的8个最邻近的象素的灰度级的平均值。,S中的上、下、左、右边线上的象素，由于在I中的相应象素无8个邻近象素，因而置为0。若用1024个PE的阵列机来实现上述算法，见P239图9.4(a)。排列成3232，每一个PE中存储一个1616的子图象块。,18,整个图象为(3216)(3216)=512512个象素，PE0存放0-15行和0-15列的子图象，PE1存放(0-15行)和(16-31)列的子图象。每个PE平滑自己的子图象，而

15、所有的PE同时进行平滑操作。在每个1616子图象的边界处，为了计算已平滑的值，数据必须在PE间传送，见图9.4(b)。阵列机中的每个PE都有相类似于单处理单元的数据传送模式。为了对512512图象完成平滑，则对于每个为1616大小的共1024子图象用并行方法完成平滑，则要1616=256次并行平滑操作，,129,19,操作过程中，总共需并行传送数据为416+4=68次(上、下、左、右每边需要16次，而4个对角为4次)。如用串行完成同样大小的图象平滑，虽不需要进行PE间数据传输，却需要512512=262114次平滑操作，因此并行算法可比串行算法快1024倍(262114/256)。如计入数据传

16、送时间改进倍数仍可达262114/(256+68)=809。对于求累加求和那样递归操作，为加快并行计算，常采用递归折叠方法。例子见图9.4。,图9.48个PE的递归折叠求和,20,9.2.4典型SIMD举例,46,21,图9.8BSP计算机的流水线结构,由前面举例可见：SIMD并行计算机的性能与所采用的算法密切相关，采用通常的串行算法是不能发挥其并行计算能力的。在求解过程中，并不是每个PE始终参与运算，这就需要控制器借助屏蔽方法使那些不必参加运算的处理器处于不活跃状态。由于在求解过程中各个处理器间需要交换信息，因此互连网络特性的好坏对求解速度会有较大影响。求解问题前，通常必须将有关数据预分配到

17、各个PE的局部存储器中。,22,9.3计算机互连网9.3.1互连网络的分类及设计准则静态网络中的连接是固定的链路，在运行中不能更改，不能进行控制，动态网络中的连接是当需要时才建立的，在运行中可以通过开关状态加以控制。,基于总线的网络又可进一步分为单总线和多总线的网络。基于交换的动态网络按照互连网络的结构又可进一步分为单级、多级和交叉开关网络。图9.9所示为基于连接的静动态性和网络拓扑的互连网络分类。,静态网络按连接的互连模式可进一步分为一维、二维、立方体(三维)或超立方体的(三维以上)。动态网络按互连方式可分为基于总线和基于交换的网络。,23,图9.9互连网络分类,若把处理单元或存储模块看成结

18、点，则互连网实际是为输入输出两组结点之间提供数据通路或映象。对于N个输入和M个输出映象共有NM种，一对一映象则为M！种。,连接度是指一个结点与其他结点的连接程度，一个结点连接的其他结点数越多，连接度就越高，表明连接性越好。,衡量互连网性能好坏的主要因素是它的连接度、延时性、带宽、可靠性和成本。,24,在设计互连网时应考虑以下的5个特征：通信工作方式可分为同步和异步两种。同步：不论各个PE对数据进行并行操作还是由CU向PE广播命令，都由统一的时钟加以同步。异步：不用统一时钟加以同步，各个PE根据需要相互建立动态连接。控制策略分为集中和分散两种集中式控制：由一个统一的控制器对各个互连的开关状态加以

19、控制。分散式控制：由各个互连开关自身实行管理。一般SIMD并行机采用集中控制。,延时性：指从一个结点传送信息到任何另一个结点所需的时间。通常可用结点间最大距离表示。,25,交换方式：分为线路交换和分组交换线路交换：是在整个交换过程中，在源和目标结点之间建立固定的物理通路，适用于成批数据传送。分组交换：把要传送的信息分成多个分组，分别送入互连网，这些分组可通过不同的路由到达目标结点。因此适用于短报文传送。,路由方式路由方式是指消息从源结点发出后按何种寻径机制到达目的结点，寻径机制的好坏对互连网络的时延性(从一个源结点传送一个消息到目的结点所需的总时间)有很大影响。互连网络中常用的路由方式有存储-

20、转发、虚拟直通和虫孔等。网络拓朴分为静态和动态两种拓朴是指互连网中的各个结点间连接关系，通常用图来描述。静态拓扑：指各结点间有专用的连接通路，且在运行中不能改变。,SIMD并行机一般采用线路交换方式。MIMD多机系统往往采用分组交换方式。,26,动态拓扑：则因设置有源开关，所以可根据需要借助控制信号对连接通路加以重新组合。9.3.2静态互连网络静态互连网络的主要特征是在处理器间有单向或双向的固定通路。有两种类型的静态网络，分别是全互连网络和有限互连网络。全互连网络当全互连网络中的结点数为N时，则全互连网络中的链路数为N(N-1)/2，因此网络的复杂性为O(N2)。全互连网络的时延复杂性为O(1

21、)。图9.10所示为一个N=6的例子，为了满足网络全互连性的要求，总共需要15条链路。,有限互连网络有限互连网络不提供从每个结点到每个其他结点的一条直接链路，而是采用某些结点间的通信必须路由经过网络中其他结点的方法。图9.11所示为这些网络的结构示意图。,27,图9.11静态有限互连网络的结构示意图,线形阵列网络直径为N-1，速度太慢，当结点数N增大时就更为如此。线形阵列的网络复杂性和时间复杂性都为O(N)。如果将线形阵列网络两端的结点连接起来，则为环状网络，其网络直径为N/2。在树状网络中(其中二叉树是一个特例，见图9.11(c)，如果在i级(假定根结点处于0级)上的一个结点要与j级的一个结

22、点进行通信，其中ij(j即结点在i结点之上)，且目的结点属于相同根结点的子树，则,28,不得不发送它的消息沿树上行遍历级i-1，i-2，j-1上的结点直至到达目的结点。如果在i级(假定根结点处于0级)上的一个结点要与同级i上的另一个结点(或与在级ji上的结点)进行通信，而目的结点属于一个不同的根结点的子树)，则必须发送它的消息沿树上行直至到达0级的根结点。此后，该消息再从根结点下行直至到达目的结点。在一个k级的二叉树系统中，结点数为：N(k)=20+21+22+2k=(2k-1)/(2-1)=2k-1(9.7)注意：二叉树网络的高度为log2N，其中N是网络中的结点数。因此。复杂性为O(2k)

23、，而时间复杂性是O(log2N)。二叉树网的一个主要缺点是根结点是通信的瓶颈，且容错性能也不好。一种改进的方案是采用胖树(FatTree)结构，在这种树中，趋向根结点的结点间的链路数将指数式地增长，从而可增加趋近根结点处的通信带宽，与此同时也改善了容错性能。图9.12所示为一个四叉胖树网络。,29,图9.12四叉胖树网络,下面将对2维和3维的网格进行更为详细的讨论。网格互连网络一个n维网格被定义为具有K0K1Kn个结点，其中n为网络的维数，K为i维的基(Radix)。图9.13所示为一个332网格网络的例子。位于(i，j，k)的一个结点将与在维i1、j1、k1的邻居结点相连接。带有环绕连接的网

24、格体系结构将形成一个环绕(Torus)网络。在网格中一个比较通用的路由消息机制，称为维序路由(Dimension-OrderingRouting)。,30,使用该路由机制时，消息每次只在一个给定维中路由，在进入到下一维之前必须先在每一维中到达合适的坐标。例如，对于一个3D网格，因为每个结点由它的位置(i，j，k)表示，所以消息首先沿i维传送，然后沿j维，最后沿k维。最多允许有两次转变方向，这即从i到j，然后从j到k。图9.13所示为从位于(0，0，0)的结点S发出的消息路由到位于(2，2，1)结点D处的情况。,(0,0,0),(0,2,0),(2,2,0),(2,2,1),31,立方体互连网一

25、个n-立方体(n阶超立方体)定义为一个有向无环图，它具有标号从0到2n-1的2n个顶点，且在一对给定的顶点间有一条边，而它们的二进制地址表示仅有一位不同。图9.14为4立方体网络.,图9.14一个4立方体网络,利用一对给定的顶点间有一条边，且它们的二进位地址表示仅有一位不相同这一性质，可以采用一种简单的路由机制，称为e-立方体路由算法：从源结点i到目的结点j的消息路由，可以通过异或i和j的二进位地址表示得到。如果给定位的异或操作结果为1，则消息必须沿与该地址位对应维的跨接链路传送。,32,则意味着为到达目的地该消息必须沿维2、3和4(从右往左数)传送。在一个n立方体中，每个结点的度为n。超立方

26、体是一种对数的体系结构，这是因为在含有N=2n个结点的n立方体中，一个消息为到达它的目的地而必须遍历的最大链路数为log2N=n。超立方体网络的构造具有递归性。一个n立方体可由两个(n-1)子立方体构成。k元n立方体互连网络,注意，在一个k元n立方体中结点数是N=kn，而当k=2就变为一个二元n立方体。一个k元n立方体中的消息路由可采用在网格网络中的类似方法。一个k元n立方体中路由选择的另一个因素是路由的最小性，它是用一个消息在到达其目的地之前所遍历的跳(Hop)(链路)数衡量的。,k元n立方体网络是一个基数为k的n维立方体。,33,图9.15k元n立方体网络示例：8元2立方体(8个8结点环)

27、网络,静态互连网络的性能指标影响互连网络性能好坏的主要因素是它的时延、带宽、网络直径、连接度、平均距离、成本和对称性。,一个k元n立方体网络中任何两个结点间的最长遍历距离为O(n+k).,34,网络时延是指经过网络传输单个消息所需的时间，包括通道延迟和交换(开关)延迟，依赖于网络硬件。它与通信时延不同。通信时延是指传送消息所需的总时间，包括软件开销和接口延迟，通常与结点间的最大距离密切相关。消息时延是指发送0长度消息所需的时间，包括所需的软、硬件开销(路由查找、打包、解包等)。网络带宽是指互连网络在单位时间内可传输的字节数，它是网络拓扑结构、通道宽度、通道数量、网络规模(端口数量)、交换度、网

28、络时钟频率的函数。网络带宽通常用对分带宽(BisectionBandwidth)来衡量，它是指当将网络分成两个相等部分时，被分割网的一部分向另一部分在单位时间内可传送的最大字节数。显然，它与网络的对分宽度(BisectionWidth)有关，对分宽度是指将网络分成两个相等部分时所必须切割的链路数。网络直径是指任何两个结点间最短距离中的最长者。连接度是指一个结点与其他结点的连接程度，也称为结点度，是指进入和离开一个结点的通道数的总和。,35,平均距离是指一个消息在静态网络中传播的平均距离，其计算公式如下：,其中，D是网络直径，Nd是对于一个给定的结点，与其距离为d的结点个数。成本通常用互连网络中

29、所用的链路数来衡量。对称性是指如果将任何结点标识为原点它都同形于本身，即从任何结点观察网络都是一样的。环状和环绕网络是对称的，而线形阵列和网格网络则不对称。一些常用的静态互连网的性能特性如表9.1所示。9.3.3基于总线的动态互连网络单总线系统单总线网络复杂性(空间复杂性)由所使用的总线数衡量，为O(1)，而时间复杂性由输入到输出的总延迟衡量，为O(N)。,36,表9.1静态网络的性能特征,图9.16单总线系统,37,多总线系统可能的连接方案有：全总线存储器连接的多总线，将所有存储器模块连接到所有总线。单总线存储器连接的多总线，使每个存储器模块连接到一个特定的总线。部分总线存储器连接的多总线。

30、使每个存储器模块连接到一个总线子集组。图9.17所示为在N=4处理器，M=3存储器模块以及B=3总线情况下，对上述这些连接方案的说明。一般可以用所需连接数和每条总线上的负载对这些连接的特征进行刻画，如表9.3所示。,38,39,一般来说，多总线多处理机系统具有高可靠性和易扩展性。单条总线发生故障时，在处理器和存储器模块间仍有B-1个不同的无故障的通路；另一方面，当总线数少于存储器模块数(处理器数)时，总线的竞争将会增加。总线仲裁器和仲裁算法仲裁器一般由某种仲裁算法和相应的实现硬件构成。仲裁算法的好坏对系统性能有较大影响。常用的仲裁算法有：静态优先级算法、固定时间片算法、动态优先级算法以及先来先

31、服务算法。这些算法已在8.4.2节做了论述，这里不赘述.上述的各种仲裁算法，通常用集中方式加以实现，即统一由一个仲裁器来实现仲裁算法。此时，对于总线的请求和允许使用信号可采用如下3种实现方式：一是请求线共享，而允许使用线则用串行菊花链方式连接；二是使请求和允许使用线都采用分离独立的线；三是采用前两种混合方式。,40,分布仲裁工作方式如下：每个潜在总线主控器分配一个唯一的优先号，提出申请的主控器将自己的优先号送往共享请求/有效线进行逻辑或操作，得到一个合成优先号，然后提出申请的主控器将自己的优先号与合成号相比较。比合成优先号小的申请者将自动撤销申请，这样剩下获得总线使用权的必将是具有最高优先号的

32、处理机。分布仲裁算法的优点是有较高的可靠性。分布仲裁器的工作过程如下：首先，通过请求线接收来自各处理机发来的使用总线请求；然后，由仲裁器加以仲裁并以串行链接或并行分离方式向选中的处理机在总线准用线上发出总线有效信号；最后，由选中处理机通过总线忙控制线向其他处理机表明总线已被占用的总线忙信号。当主控处理机使用总线传送信息后便撤销总线忙信号，此后仲裁器便可再去响应选择其他处理机对总线的请求。多处理机总线的发展趋向是实行标准化，目前已有一些总线标准支持多处理机系统，常用的有VME总线和Multibus总线等。前者以异步方式传送信息，后者则以同步方式传送信息。如前所述，总线互连方式虽有简单、价廉等优点

33、，但其吞吐率是固定有限的。当有更多的处理机连到总线上时，就会使总线的工作速度大幅降低。而当处理机数多到某一程度时，总线将会出现饱和状态，因此总线互连方式不适宜连接过多的处理机。,41,图918一个44交叉开关网络,或,交叉开关网络如图9.18所示的44交叉开关网络，其中1i4。,所需的开关点数为16，且消息从输入传输到输出的延迟不论是哪对输入/输出进行通信总为常数。一般对一个NN交叉开关，以开关点数衡量的网络复杂性为O(N2)，而以输入到输出的延迟衡量的时间复杂性为O(1)。,9.3.4基于交换的动态互连网络一般存在3种基本的互连拓扑：交叉开关、单级和多级。互连函数通常把N个入端x和N个出端f

34、(x)都用二进制编码表示，从中可看到它们之间的对应关系。例如x的n位(n=log2N)的二进制表示为：x=bn-1，bn-2，b1，b0相当于x=bn-12n-1+bn-22n-2+b12+b0例如：f(x)=(bn-2bn-3b0bn-1),42,图91922开关元件的不同设置,单级互连网络在单级互连网络中，网络的输入和输出间最简单的开关元件是22开关元件。图9.19说明了这种开关元件的4种可能设置：直通、交换、上播和下播，因此这种开关元件被称为四功能开关元件。,(1)立方体网络用于立方体网中的互连函数为：,0klog2N-1。图9.20所示为N=8时网络的立方体互连模式。互连函数为：,50

35、,43,图9.20N=8的立方体网络,44,加减2i(PM2I)互连网“加减2i”单级网的简称PM2I网，又称“循环移数网”，互连函数为PM2+i(j)=(j+2i)(modN)PM2i(j)=(j2i)(modN)N为结点数，0in10jN1n=log2N显然互连网共有2n个互连函数。N=8时，PM2+0，PM21，PM22。PM2+0表示从当前PE与其相距20个的PE相连。PM21表示从当前PE与其相距-21个的PE相连。PM22表示从当前PE与其相距22个的PE相连。PM20和PM2+0，PM21和PM2+1方向相反。互连网中情况见图9-21。,45,图9.21N=8的PM2I网络,对于

36、相同的N，与立方体网络相比，PM2I网络具有更好的连接性。例：0#PE可与1#，2#，4#，6#，7#PE相连，见图。而立方体只能使0#PE与1#，2#，4#PE相连。,46,从通用情况(忽略方向)总有PM2+(n1)=PM2(n1)。因此，实际上PM2I互连网只有2n1种不同的互连函数。在ILLIAC中的PE之间的互连就只用了PM2I互连网中的PM20和PM22的4个互连函数，是PM2I互连网中的特例。PM2I互连网的最大距离为：,对于同样规模的网络，PM2I比ILLIAC-网格网络(螺旋闭合)具有更快的传递速度，其加速比为,例N=1024，则SN=6.2,47,此外，闭合网络中全部通路数为

37、2N条，而PM2I网有(2n-1)N/2条，从而比闭合网格增加了(2n-5)2n1条通路，因而具有较高的传输效率。混合交换互连网由全混洗和交换两种互连函数组成。全混洗互连网络和互联函数为Shuffle(bn-1bn-2b0)=(bn-2b1b0bn-1),相当于将PE的二进制位中最左位移到最右边一位的循环。此时，每个PE只有一条直接连接通路，由于它所实现的PE之间的连接犹如一叠扑克牌对分后均匀洗牌所实现的连接，故称全混洗互连网，如图9.22为8个PE全混互连。,图9.228个PE的全混互连,这种全混互连网有一个缺点，当PE地址为全“0”或全“1”时，将无法与网中其它PE相连，(因为循环移结果还

38、是原样)。为此引入前面交换网中Cube0互连函数。它的表达式为,48,图2.23混洗交换互连网的连接图,其中每一个PE也只有一条通路，这样就由全混洗和交换网所组成的混洗交换互连网具有如下复合形式。见图9.23。,混洗交换网中，最远的两个PE(全0和1)间的连接需n次交换和n-1次混洗，因此它的最大距离为2n-1。蝶形互连网它的互连函数为Butterfly(bn-1bn-2b0)=(b0bn-2b1bn-1)将二进制的最高位与最低位相互交换位置。图9.24为n=3的蝶形互连网。将二进制的最高位与最低位相互交换位置。图9.24为n=3的蝶形互连网。,图9.24蝶形互连网络的互连情况,49,多级互连

39、网单级互连网(除了交叉开关网)都只能实现有限几种基本连接，不能实现任意PE之间连接，可采用下两种方法：同一套单级互连网引入时间重复性，循环地加以使用，这种方法虽然节省器材，但I/O控制较为复杂，因此工作速度较慢，一般不采用。采用空间重复原理将多套单级互连串接使用，虽然成本有所增,9.25多级互连网,50,加，但缩短了通过时间，而提高速度，且可以用不同的互连函数控制，将多种单级互连网进行灵活组合，从而组成具有多种连接模式的多级互连网，以适应多种算法，因此这种方法得到了广泛应用。决定互连网特性的主要因素有以下三个方面：交换开关，拓朴结构和控制方式。交换开关是组成互连网的基本单元，通常它是二功能的：

40、直通和交换。或是四功能：在上述功能再加上播和下播，见P253图9.19。拓朴结构用来表明级间I/O端相互连接的规则和连接模式，可将各种单级互连网进行不同的组合，从而构成各种不同连接性的多级互连网。控制方式是对各交换开关进行控制的方式，通常有以下三种方式：级控同一级的所有交换开关都受同一控制信号控制，对一个n级网络就需要n个控制信号。单元控制每一个交换开关都有一个单独的控制信号。对于n级网络，由于输入端和输出端数N=2n，故每一级将有N/2个开关单,51,元，这种控制就需用Nn/2个控制信号，因此控制电路较为复杂，但灵活性较高。部分级控对不同的级采用不同数量的控制信号，如一种常用的方法是第0级采

41、用1个控制信号，第1级用2个控制信号，第i级采用i+1个控制信号，其中0in-1，n为级数，显然它是前两种方式的折衷。,几种常用多级互连网多级立方体网络通常将具有Cube0、Cube1、Cube2三种互连函数的三个单级立方体网串接起来构成。当0-2级控为101时(1表示交换，0表示直通)见图9.26。,多级混洗交换网络又称OMEGA网络，见图9.27，交换开关是四功能的，一般为单元控制方式。,52,1级Shuffle2级Shuffle3级Shuffle,Exchange1Exchange2Exchange3,多级PM2I互连网络又称数据交换网，P259图9.28示出了一个三级PM2I互连网连接

42、状况，其中N=8，n=log2N，各级处理单元按PM2I互连函数连接起来。,如果采用级控，则它就成为STARN交换网的逆网，即它们的I/O端的数据流向相反。,53,PM2I2PM2I1PM2I0,(0+20)mod8=1,(0+21)mod8=2,(0+22)mod8=4,已知单级PM2I互连网直径为n/2，但组成多级PM2I网时用了n级，因此网中有冗余度，通路显然有利于提高可靠性。,54,榕树(Banyan)网络榕树网络级间互连采用逆混洗互连函数。R(bn-1bn-2b0)=(b0bn-1bn-2b1),55,多级互连网络中的阻塞在多级互连网络中有许多分类准则，其中之一是阻塞性。按照这一准则

43、多级互连网络可分类如下：阻塞网络阻塞网络的特性是：当一对输入/输出已建立互连的情况要求任意两个未被使用的输入和输出间建立一个新互连的到达请求时，可能被满足或不被满足。,例如，在输入000和输出101、输入101和输出011以及输入110和输出010间已同时建立了3对连接，现在若要在输入100和输出001间再建一对连接就不可能。,图9.3088混洗-交换网络中的阻塞,56,由前面所介绍的单级和多级互连网络来看，若只考虑输入到输出端的一对一的映射，则互连网络功能实际就是用新排列来代替N个输入端的原有排列。对于N个输入端的全部排列共有N!种，但使用单元控制的n=log2N级互连网所有交换开关的总数为

44、(Nlog2N)/2。假定开关功能是二功能的，则所有开关处于不同状态的总数最多为2(Nlog2N)/2=NN/2种。当N2时，总有NN/2N!，显然无法实现相应的所有N!种排列。例：设N=8，则n=3，则功能开关共有(8log28)/2=12。因此总状态数为212=4096，显然不可能实现8!=40320种排列，仅能提供4096/40320=10.16%的排列。可重安排网络可重安排网络的特征是它总可以重安排已建立的连接以同时许可建立其他的连接。Benes是一个著名的可重安排网络的例子。图9.31所示为一个88Benes网络的例子。它共有5级，每级有4个2功能开关，共计有45=20个开关，可提供

45、245=220种排列。,57,为了布通Benes网络所有源/目的对间的互连，且不发生冲突，可以采用以下的策略：首先挑选一个输入，并将与其相连的开关设置成使该输入经网络上半部分开关，直至到达它的目的输出。然后，反向操作，将与该目的输出处于同一交换开关的另一目的输出作为起点，逆向通向它的对应源输入，但此时必须途经网络下半部分开关。直至到达它的源输入。,图9.3188Benes网络,此后，对于具有同一输入交换开关的另一源输入，存在两种可能：一是它已经连接，此时就可选任何另一对未被连接的源/目的，按上述方法重新开始进行连接；二是使用上半部网络继续进行正向连接。如此进行，直至布通所有的源/目的对的连接。

46、,58,下面举例说明上述的布通策略。,59,非阻塞网络非阻塞网络的特征是：在任何一对输入/输出已建立连接时总可以在任何未被使用的输入/输出对之间建立一个连接。Clos是一个著名的非阻塞网络的例子，它由r1n1m个输入交叉开关(r1为输入交叉开关数，n1m为每个输入交叉开关的大小)，mr1r2个中间交叉开关(m为中间交叉开关数，r1r2为每个中间交叉开关的大小)以及r2mn2个输出交叉开关(r2为输出交叉开关数，mn2为每个输出交叉开关的大小)组成。只要满足不等式mn1+n2-1，Clos网络就不会阻塞。图9.33所示为一个三级的Clos网络。,60,图933一个三级的Clos网络,61,动态互

47、连网络的性能指标动态互连网络中的性能指标包括时延、带宽、成本、阻塞性、容错度等。表9.4所示为若干动态互连网络的性能比较。,9.3.5计算机动态互连网络的带宽分析互连网络的带宽是指互连网络的数据传输率，即单位时间内所传输的字节数。下面分析交叉开关和多级互连网络的带宽。,62,交叉开关带宽交叉开关的带宽定义为:在一个给定的周期内一个交叉开关能接受的平均请求数。在交叉开关中，当处理器请求存储器模块时，如果有两个或多个处理器请求访问同一存储器模块，就可能发生争用。对于M个存储器模块和n个处理器而言，如果一个处理器在一个周期中生成一个请求的概率为p，并以相同的概率导向每个存储器，那么该带宽的表达式可计

48、算如下：一个处理器请求一个特定存储器模块的概率为p/M；在给定周期内一个处理器不请求该特定存储器模块的概率为(1-/M)。而在给定周期内n个处理器中没有一个请求该特定存储器模块的概率为(1-/M)n。因此，M个不同存储器模块至少有一个被请求(带宽)的期望数为BW=M(1-(1-(/M)n)。注意：如果处理器对任何存储器模块的请求概率相同，则上面方程式中/M这一项将变为1/M。对于M=4和n=4的情况，则有BW=175/64=2.73。,63,多级互连网络(MIN)带宽下面将计算一个多级互连网络的带宽。为了计算方便，可做如下的简化假设，即多级互连网络由多级ab交叉开关组成。这样，就可以利用在推导

49、交叉开关网络带宽时所得到的结果。假设在第一级输入处的请求率由r0给定。为第一级接受并传递给下一级的请求数是r1=(1-(1-(r0/b)a)。在第一级任何b输出线上的请求数是r1=(1-(1-(r0/b)a)。因为这些请求变为下一级的输入，用类推的方法在第二级输出的请求数是r2=(1-(1-(r1/b)a)。扩展这一递推关系就可根据来自j-1级的输入请求率对j级输出处的请求数进行如下计算：rj=(1-(1-(rj-1/b)a)，1jn，其中n是级数。据此，多级互连网络的带宽由下式给定：BW=bnrn。,64,9.4MIMD多处理机及多计算机系统9.4.1多处理机的主要特征及其分类相对SIMD并

50、行机而言，主要特征表现在以下几方面：具有更大的灵活性和更强的通用性，适宜于求解通用算法，它能灵活地开发数据并行性和功能并行性，而SIMD系统只能开发数据并行性。因此通用性较差。主要开发高层次作业及任务级(粗粒度)并行性。SIMD机开发低层次操作一级的并行性。并行任务的派生需要显式的专用语句或指令加以表示。SIMD中并行操作由单独指令表示的控制，故不需要设置专门的指令。并发执行的进程间的同步需采取特殊措施，以保证原来的正确语义。SIMD机中，由于受同一控制器控制，因此工作自然是同步的。对资源分配和任务分派要进行良好的调度，因此要采用软件的手段，否则系统性能将受很大的影响。SIMD机中往往只需用屏

51、蔽来控制实际参加并行操作的PE数目。,65,MIMD系统在执行条件语句(如ifthenelse)时，比SIMD有更高的效率。由于是多指令流的特性，MIMD中每个处理单元，犹如单机一样，能独立地按任一方向执行。在SIMD机中，当“条件”与处理单元中的局部数据相关时，就必须串行执行“then”模块和“else”模块。MIMD的异步特性使得它在执行一串完成时间可变的指令时，比SIMD有更快的速率。在SIMD中每次要执行下一条指令时，必须等待最慢的PE完成上一次指令的执行，因此所需总的执行时间为“最大值的和”，,而MIMD总的执行时间为“和的最大值”。,一般有TSIMDTMIMD,(9.17),(9.

52、18),66,MIMD多机系统分类如前所述，当今的并行计算机系统大多以MIMD方式工作。按照同步、交互机制、地址空间、访存方式等语义属性，可将它们的物理机模型进一步分类成以下5种：多向量机(MultiVectorProcessors。MVP)；对称多处理机(SymmetricMultiprocessor，SMP)；非均匀存储器访问多处理机(NonUniformMemoryAccess，NUMA)；大规模并行处理机(MassivelyParallelProcessor，MPP)；机群(Cluster)。MVP系统由少量功能强大的定制向量处理器采用共享存储器方式互连而成，它能高效地处理向量数据，通

53、常不使用Cache，而是使用大量的向量寄存器和一个指令缓存器。SMP系统具有对称性，即每个处理器能平等地访问共享存储器、I/O部件以及操作系统。也称为UMA系统(UniformMemoryAccess)。,67,NUMA系统采用分布式存储器，但处理器可用读/写指令直接访问系统中的任何存储单元，因此存储器的逻辑地址是共享的，为此它也被称为是分布共享存储器系统(DSM)。依据处理器所在的物理位置，访问存储器所需的时间不尽相同，因此是非均匀存储器访问。,68,MPP系统使用大量的商品化处理结点，用定制的高带宽、低时延互连网络将它们连接起来，存储器在物理上是分布的，必须通过消息传递实现进程间的相互通信

54、，是紧耦合的并行机系统，具有良好的可扩展性。图9.34(d)所示为MPP的结构。CrayT3E和IBMBlue/Gene(蓝色基因)系统是MPP系统的典型代表。,69,Cluster系统中每个结点是一个完整的计算机，可能没有某些外设，结点也可以是一台SMP或PC等。图934(e)所示为Cluster的结构。,70,UMA、NUMA和COMA多处理机系统UMA、NUMA和COMA3种多处理机属于SM系统，但在数据共享的方式上有所不同：UMA实现的是物理上的共享，是对任意存储单元的真正共享；NUMA和COMA实现的是逻辑存储器的共享(即具有单一的共享存储器地址空间)，且通常实现的是对Cache的共

55、享。UMA多处理机系统UMA多处理机系统通过共享主存实现PE间的相互通信，因此各个PE间相互紧密连接，称为紧耦合(TightlyCoupled)多处理机系统。有两个方面约束：因为是采用共享主存通信，所以当PE数目增大时，将导致访问主存冲突概率加大，使系统性能下降；PE与MM间的互连网络的带宽有限，当PE增多时，互连网将成为系统性能的瓶颈。常采用改善的方法如下：采用多模块交叉访问。交叉度越大，访存冲突概率就越小，但必须注意如何恰当地将数据分配到各个模块中。,71,使每个处理机拥有一个小容量的局部存储器，用来存放频繁使用的核心代码等，以减少对主存的访问。使每个处理机都有一个Cache，以减少对主存

56、的访问。但必须注意Cache与主存两者之间以及各个Cache之间的数据一致性。UMA紧耦合系统按所用处理机类型是否相同及对称，又可分为同构或异构以及对称或非对称形式。常见的组合是同构对称式多机系统及异构非对称式多机系统。同构对称式多机系统。,72,Sun公司的Enterprise10000(又称Starfire10k)是当前SMP的高端服务器，它比起Enterprise6000在可扩展性、可靠性和可用性方面有了很大的改进。,图9.36SunEnterprise10000的体系结构,73,异构非对称式多机系统。图9.37所示为异构非对称式多机系统。,(2)NUMA多处理机系统图9.38所示为NU

57、MA共享存储器系统的组成。,74,图9.38NUMA共享存储器系统,由于在NUMA系统中，存储器在物理上是分布的，因此如何保持各处理器中Cache的一致性(采用软件还是硬件)，如何在系统中有效地复制和迁移共享的数据以及如何选择共享数据颗粒度大小等，就成为设计中的关键问题。基于这些原则，NUMA系统通常可分为CC-NUMA(CacheCoherentNUMA)、NCC-NUMA(NonCacheCoherentNUMA)SC-NUMA(SoftwareCoherentNUMA)三类。,75,(3)COMA(Cache-OnlyMemoryAccess)多处理机系统类似于NUMA系统，在全高速缓存

58、(COMA)系统中每个处理器有局部的共享存储器。但此时的共享存储器全由Cache组成。COMA采用硬件方法实现Cache一致性，并以Cache行的颗粒度实现数据共享，由硬件在Cache行级实现数据的复制和迁移。,图9.39COMA系统的组成,76,MPP多处理机系统MPP大规模并行计算机一般是指具有规模可伸缩的、拥有成百上千甚至更多个处理机的系统。MPP并行机系统的主要特点是：采用分布式存储器且具有良好的规模可伸缩性。(1)MPP系统体系结构的主要特征所有的MPP计算系统都使用物理上分布的主存且使用分布式的I/O。每个结点机拥有一个或多个处理器和高速缓存、一个本地主存，无磁盘或多个磁盘。结点内

59、部的互连网络将处理器、主存以及I/O设备连接在一起。图9.40所示为现代MPP计算系统的通用体系结构。,77,就MPP系统的体系结构而言，它具有以下主要特征：大规模，且具有良好的可扩展性。由于规模大，因此MPP系统通常能提供很高的性能。紧耦合的互连。由于MPP系统中采用的是分布式存储器结构，因此为了提高各结点机间的通信速度，MPP系统通常都采用将互连网络通过网络接口电路(NIC)与结点内的存储器总线相连的紧耦合方式(机群系统则采用与结点内的I/O总线相连的松耦合方式)。高带宽、低时延的定制互连网络。,78,此外，MPP系统往往还提供专门的通信软件以减小通信软件的开销，这是因为通信的总开销除了通信硬件导致的开销外，通信软件也占去了相当的比例。(2)MPP系统构成的主要方法MPP系统虽然是MIMD类型中的一个重要子类型，但其构成方法却在原来传统的小结点方法上不断演变，往往借助其他的子类型结构来组成，因此现在的MPP系统主要是指其规模。归纳起来构成当今MPP系统体系结构的方法主要有以下5种：第一种是采用小结点；第二种是采用机群；第三种是采用NUMA结构；第四种是采用超结点；第五种是采用向量机与超标量机相结合的方法。小结点方法。所谓小结点是指结点