并行体系结构提供了一个明确的,高层次的发展框架做为并行编程的解决方案,通过提供多个处理器(无论简单或复杂),来共同地解决问题,实现并行执行。多计算机系统架构已成为构建大规模并行计算机一种流行架构,因为它们具有良好的可延展性,如在一些系统中增加节点,则系统中总的通信带宽,存储带宽,处理能力也有所增加。分布式存储并行计算机中处理器之间通信的主要困扰是性能退化。事实上,在大多数的系统中,“基本的通信时间”仍然大于“基本的计算时间”。因此,我们主要关心分布式存储多处理器的通信策略的效率。对于一个单一来源,我们将通信问题划分为三类:单目传播、多目传播和广播。1.单目传播。这相当于一对一的通信,一个源节点只给一个目的节点发送了同样的信息(点对点)2–多目传播。在新的多计算机系统中的基本格局是多目传播蛀洞,相当于一对多的通信,其中一个源节点发送同样的消息给多个目的节点。现有的多目传播路由算法可分为基于单目传播,基于路径和基于树的。在基于单目传播的多目传播算法中,源节点发送消息给目的节点,通过发送一个顺序的分离的消息给每个目的节点。这意味着,仅有一个源节点和一个目的节点(点对点)。基于单目传播的方法的缺点是发送一个消息给巨大的目的节点集合需要大量的启动开销。在基于路径的方法中,报头包含能够到达的特定顺序的目的地址清单。更确切地说,一个报头包含一个有规则的顺序地址@(v1)@(v2)…@(Vk),即消息必须首先到达V1然后再到V2等等。当一个消息的迁移片段到达邻近的目的节点Vi时,地址@(vi)从报头中被移出,并且能够被复制到本地储存器,这样保证能够按顺序的到达下一个目的地,即报头中的地址@(vi+1)。当消息抵达最后一个目的节点,此消息从网络中移出。通过这种方式,一个消息能够以发送到单一目的节点的相同启动时延被传送给多个目的节点。在基于树的路由方法中,一条多目消息利用消息报头中的迁移片段所构成的多目消息路径在网络中路由至每一邻接结点;消息被注入网络之前,目的节点不必有序。3、广播业务。这相当于一对所有通信,在网络中,一个源节点发送同样的消息给所有可能的目的地。在此论文中,我们研究了第二类的问题。多目传播问题研究有两个方面,存储和转发路由以及蛀洞路由。在此论文中,我们把重点关注蛀洞路由下的多目传播问题。蛀洞路由。蛀洞路由是一种高效的多计算机系统消息路由算法。蛀洞路由交换技术被广泛的应用于实践中的原因有二:其一,其需求缓存量较低,并且允许高效地路由实现。其二,也是更重要的原因,在不考虑阻塞的情况下,其时延几乎不受消息距离的影响。在蛀洞路由网络中,封包被分解成迁移片段集,每个迁移片段是一个通道能够接受或者拒绝的最小信息单位。蛀洞路由直接将封包头在输入通道和输出通道间传送。这种从源节点到目的节点的传输要经由一系列的路由器。同一封包的所有迁移片段以管道方式按序传输。仅有迁移片段头知道封包的去向,而其余的迁移片段必须跟随迁移片段头的流向。一旦迁移片段头成功获得一个通道的访问权,当前的信息便拥有了此通道,直到迁移片段尾传输完毕,并释放此通道的拥有权。如果迁移片段头遇到通道正在被使用,则被阻塞,直到此通道被释放。在蛀洞路由中,如果输出通道是繁忙的,则消息被原地阻塞。蛀洞交换技术已经在新一代多计算机系统网络中广泛流行。第一个采用蛀洞路由技术的商用多计算机系统是Ametek 2010,它使用2D网格拓扑结构。Ncube-2使用超立方体拓扑,也采用了蛀洞路由机制。Intel Touchstone Delta和Inter Paragon使用2D网格的蛀洞路由。此外,麻省理工学院所研究的J -机原型在三维网格中使用了蛀洞路由。在蛀洞路由中,一个封包中邻近的迁移片段始终包含在相同或者相邻的网络节点中,这将有可能造成死锁。死锁。一个多计算机系统网络被认定为死锁的条件是没有消息能够到达目的地。在这种情况下,信息将无限期地被推迟传递。当消息被允许部分占有资源并仍要申请其它资源时,死锁可能发生。死锁是一个网络的灾难。在某些少量的资源被死锁的封包占用之后,其他的封包受阻于这些资源,使得网络瘫痪。为了预防这种情况,有三个办法:死锁预防,死锁避免、死锁复苏。死锁预防,资源以一种不会导致死锁的方式被分配给封包。这种方式可以通过在传输之前将封包所需的资源全部进行保留来完成。死锁避免,当包将在网络中传送时才申请资源。但是资源的分配仅当封包的资源申请被满足后的全局状态仍是安全的条件才可实施。死锁复苏的策略是乐观的。死锁复苏不采取任何行动来禁止死锁,但检测死锁的发生和解决死锁。这种模式基于这样的观察:在现实世界中,死锁是非常罕见的现象。目前,几乎所有的现代网络都采用死锁避免方法。多目传播延迟包含三个组成部分:启动延迟,网络延迟、阻塞延迟。启动延迟发生在操作系统准备向网络中注入消息的时候。网络延迟包括通道传播和路由器的拖延,阻塞延迟则由消息间对网络资源(例如缓冲器和通道)的竞争而导致。在当代机器中,启动延迟是通信成本的主导因素,目前通常用微秒来度量而网络延迟则常用纳秒来度量。另一方面,阻塞延迟依赖于路由算法和产生的通信量。因此,阻塞延迟可以有很大差异,此差异取决于瞬间的通信情况。本论文旨在设计有效的基于路径多目传播路由算法来平衡不同网络负载的启动延迟,来达到高并行和低通信延迟。一个网络的拓扑通常作为一个图模型定义,即网络节点如何通过通道而相互连接。网状连接拓扑结构是多计算机系统中网络拓扑最彻底的研究。它具有很多优点。首先,它使网络的构造从简单的积木扩大到一个模块化。第二,网格连接网络易于使用简单路由算法。第三,通过一个对称的网络很容易发展高效的多处理机相互连接计算算法。最后,它使得网络更容易模拟。网格连接的拓扑结构也称为k-ary-n dimensional meshes,有一个n维网格结构,每维都具有k个节点,通过一个直接的通信将每维的每个节点和其他的节点进行连接。网格连接拓扑结构包括n维网格,圆环面和超立方体。最近的网格连接专注于两维或者三维网格。此论文仅限于具有双通道的三维网格拓扑。An m (rows) x n (columns) x r (layers) 3-D mesh comprises mnr nodes interconnected in a grid fashion.三维网格拓扑能够模式化为一个图M (V, E),V (M)中每个节点对应于一个处理器,E (M)中的每条边对应一个通信通道。网格图的正式定义如下。Definition 3.1: An mxnxr non wraparound 3-D mesh graph is a directed graph M (V, E), where the following conditions exist:网格拓扑结构的不对称导致每维连接线的缺失。因此,节点可能无法连接到相同数量的邻居;那些在拐角,边缘和网络中间分别具有4到6个邻居。在该系统中,节点包括一个处理单元(PE)和路由器。处理单元包括一个处理器和一些本地存储器。这样本地的通道分别地被处理单元用于向网络中注入/推出消息。所产生的消息被处理单元通过注入通道注入到网络中。研究认为,所有端口路由器模式中,路由器能中继多种消息,并且提供给每个引入的消息所需的独一无二的输出通道到相邻节点,一个节点可以沿着推出和注入通道同时发送和接收消息。在论文中,四种基于路径多目传播蛀洞算法在一般的三维网络中的提出和研究。这四个算法被证明是无死锁的。首先介绍算法GTDBTPM的设计,在两个启动阶段,使用二进制查找可以发送消息给任意数量的目的节点;因此被命名为General Three-Dimension Binary Two-Phase Multicast。这是基于将三维网格网络分裂为层的集合。三维网格网络可以展现为层的集合,每一层是一个二维网格网络。在网格中的每个节点使用整数坐标表示(x, y, z)。事实上,如果我们具有mxnxr三维网格,我们将有r层的mxn二维网格。在z坐标的第一层为0,第二层是1,最后一层为R-1。GTDBTPM算法将网络在z坐标分为两个子网N+z,和N-z。子网N+z包含所有对角线以上通道的源地址[(x, y, z), (x, y, z + 1)],子网N-z包含所有对角线以下的源地址[(x, y, z), (x, y, z-1)]。第二个介绍的算法是GTDMPM算法的设计,在多个启动阶段,可以将信息发送到任意数量的目的地,因此我们可以命名为General Tree-Dimension Multi-Phase Multicast。将网络分为六个子网,NxR, NxL, Nxs,yu, Nxs,yL, Nxs,ys,zu and Nxs,ys,zL。子网NxR包含所有源地址[(x, y, z), (x + 1, y, z]水平线右边的通道;子网NxL包含所有源地址[(x, y, z), (x - 1, y, z)]水平线左边的通道;子网Nxs,yu包含所有源地址[(x, y, z), (x, y + 1, z]垂直上面的通道;子网Nxs,yL包含所有源地址[(x, y, z), (x, y - 1, z]垂直下面的通道;子网Nxs,ys,zu包含所有源地址[(x, y, z), (x, y, z + 1]斜对角线上面的通道;子网Nxs,ys,zL包含所有源地址[(x, y, z), (x, y, z - 1]些对角线下面的通道。第三个介绍的GTDTPM算法的设计,在两个启动阶段,可以将信息发送给任意数量的目的地,因而命名为General Three-Dimension Two-Phase。使用了Hamiltonian路径来执行多目传播的两个消息传递的阶段,从而减少网络规模和启动延迟。从源节点上,GTDTPM算法将网络划分为两个子网,NU和NL, NU的每个节点具比源节点较高的标签,NL中的每个节点比起源节点具有较低的标签。第四个介绍了算法GTDSPM的设计,在六个启动阶段可以将信息发送给任意数量的目的地,因而命名为General Three-Dimension Six-Phase Multicast.。利用了Hamiltonian路径在六个消息传递阶段执行多目传播。在三维网格中,多数节点具有输出度为6,传递一条信息可以多达6条路径,这取决于目的节点到源节点的距离。GTDSPM算法和GTDTPM算法的唯一区别就是源节点的消息准备,GTDTPM算法的目的集合DU和DL将进一步分割。集合DU划分为三个子集,DU1包含x坐标中大于源节点的的节点,DU2包含x坐标中小于源节点的的节点,DU3包含DU剩余的节点。集合DL划分为类似的样式,消息从这六个集合中同时发送给源节点的6个输出端口。模拟试验在三维网格动态的网络通信量的条件下比较这些多目传播算法的性能。为了评价一个互联网络中多目传播方法的性能,一些参数时必须加以考虑的,如注射率,多目传播大小,消息长度和启动延迟。注射率的平均间隔时间,多目传播大小是指目的节点的数量,消息长度f是一个消息的字节流的数量。消息启动延迟?包括软件开销的缓冲器的分配,消息复制,路由初始化等。我们首先给出假设,模拟系统架构中的参数。所有的模拟是执行6x6x6三维网格。在我们设计的不同的注射速率,组播尺寸,启动延迟,和信息的长度下,测试路由性能。对于每个多目传播的源节点和目的节点是随机生成的。大的消息启动延迟?设置为100ms,小的消息启动延迟?设置为10ms。小的消息启动延迟一般被用于先进的网络界面来改善延迟时间。对于所有的多目传播的消息大小模拟为1, 100, 1000 and 10000 flits。要比较我们设定的多目传播路由算法的性能,模拟程序用于在三维网格网络中一个单一通道,采用VC++和使用基于事件驱动的模拟软件包CSIM.,CSIM.允许多个进程来执行类似的方式,并且提供一个非常方便的用于书写模块的虚拟程序的接口。该模拟程序的多目传播通信是一个更大的模拟器,称为MultiSim,被设计为研究大规模的多处理器。MultiSim包括若干个组成部分,这些部件描述了程序和得到的结果。所有的模拟被执行直到置信区间小于5 %,也就是说使用95 %置信区间。这些算法使用模拟来比较,在论文中,由结果提出启动时间的比率?超过传播时间,并且消息大小是非常小的,当注射率增加时,GTDSPM算法性能是优于其它的算法的。当消息大小是中等的,GTDTPM and GTDSPM算法性能是优于GTDMPM and GTDBTPM算法的。那么,GTDMPM and GTDBTPM算法对于少量的负荷是高效的(负荷小于100点)。当消息大小增加,GTDMPM算法是最优的。当启动时间增加(100倍的传播时间),这些结论并没有改变太多。事实上,在实验结果中平均的网络延迟对目的节点数量是起作用的,也是GTDTPM算法中性能衰退的真实原因。当消息大小是中等的,GTDTPM算法优于其它的算法。当消息大小是巨大的,GTDMPM算法是优于其它算法。当启动时间增加(100倍的传播时间),这些结论并没有改变太多。总之,没有一个唯一的候选者是网格中最优的多目传播算法,选择主要依赖于众多的参数。最终的选择取决于通信量情况和网络的特点。从我们的结中,当消息大小是中小型情况(1到100flits)我们建议使用GTDTPM算法,当消息是巨大的(大于100 flits ),使用GTDMPM算法。