摘要：组播作为一种聚合操作其他聚合操作的基础操作，对并行系统的性能有着重要的影响。本文提出了一种适应与二路胖树的多目标编址方法：多区域位串编址。该方法可以缩短目标地址长度，并且可以实现路由器节点的快速解码。
　　关键词：二路胖树；聚合通信；树型组播；多目标编址
　　中图分类号：TP338 文献标识码：A 文章编号：1674-7712 (2012) 16-0034-02
　　一、引言
　　组播作为一种聚合操作和其它聚合操作实现的基础[0]，对并行系统的性能有着重要的影响。组播传统的实现方法是使用软件通过多个点到点的单消息通信完成，其硬件实现简单，但是产生的网络流量大，会造成频繁的网络拥塞，导致通信延迟的增加。文献[0]中通过研究发现，通过Switch支持的树型组播可以取得最高的性能，硬件实现的性能高于使用二项式树结构的软件实现。
　　树型网络拓扑对于树型组播的实现提供了比将树嵌入到直接网络中更加自然的支持。二路胖树结构不是一种可扩展的互连拓扑，但是在支持基于虫孔交换的组播中表现出了良好的特性。本文根据二路胖树的拓扑特性，提出了一种高效的多目标编址方法：多区域位串编址。
　　二、背景知识
　　2.路由算法
　　文献[3]中提出了虫孔交换双向多级互连网络（BMIN）中的Turnaround路由算法，Turnaround路由算法可以用于基于虫孔交换的二路胖树中，并且不会产生死锁。
　　二路胖树的任意子树的两个根结点在逻辑上是等价的。信息从源结点发出后，上行的过程中可以任意的选择一个当前结点的父结点，下行过程中也可以任意选择目标结点所在子树的两个根结点中的任意一个。对于任意给定的子树，只要一个根结点工作正常，则网络仍然是连接的。
　　要将一个消息发送到目标结点，消息头中需要包含最近公共父结点与源结点的距离、目标结点的编号信息和消息头当前所处的层号（初始值为）。消息上行过程中，每经过一个Switch距离信息和当前层号都减1，当距离信息减到0时表示已经到达了最近公共父结点，执行turnaround操作。消息下行过程中每经过一个Switch，当前层号加1，若是层号为（，则Switch根据编号的判断所要输出的下行端口号，否则Switch根据编好信息的（为当前层号）判断目标结点在当前结点的左子树还是右子树。
　　由消息路由的上行过程和下行过程可以看出，Switch根据报文头携带的信息对输出路径作出选择，不需要记录自身在网络中的位置。
　　三、多区域位串编址
　　（一）性能指标
　　多目标编址是实现硬件组播的一种有效方法。多目标地址带来网络开销和路由器解码开销，因此编址方式应希望达到以下目标：
　　1.长度尽量短；
　　2.利于路由信息的计算；
　　3.编码方式不假定交换节点知道自己在整个网络拓扑中的位置；
　　4.系统扩展后编址方式能够继续使用。
　　（二）编址方式
　　多区域位串编址适合于几个相邻区域的节点组。二路胖树中可以通过最近公共父节点表示区域，区域中位串的长度根据表示区域的最近公共父节点和处理节点之间的距离来判定。
　　对于树型结构存储方式，本文设计了一种带度数的深度优先的先根次序表示法。树的先根次序表示如1(a)所示。带度数表示的节点结构如1(b)所示。其中Info是该节点相对于父节点的位置，Degree是当前节点的子节点数目。