近年来随着各种应用计算需求的不断增长，集群计算的规模也在不断扩大。然而集群规模的增大并不意味着绝对计算速度和并行效率的提升,其中影响并行应用程序计算性能发挥的主要瓶颈之一是消息传递通信设计不理想或使用不合理，导致全局通信使用频率过高，造成通信堵塞、各种操作的响应时间持续延长和计算性能的下降。有数据表明，在大多数集群通信中，聚合通信开销往往占据全部消息传递通信开销的80%以上。因此，合理调整消息传递中聚合通信机制、降低全局通信流量应是改善现有集群计算环境的有效手段之一[1]。
本文基于MPI集群框架结构，通过分析单层型集群和树型结构集群的聚合通信原理，提出了一种采用树型结构的MPI集群系统设计方案，用以降低聚合通信的开销，改善集群计算环境，同时也为集群的扩展提供更加灵活的手段。聚合通信包括很多全局操作(如广播、同步、归约、分发、收集)等，但很多聚合通信是由其他聚合通信的组合来实现的，本文选择了有代表性的广播和收集作为主要研究对象。
1 单层型结构与树型结构
1.1 单层型结构介绍
单层型结构是目前大多数MPI集群工具所采用的框架结构。如图1所示。该结构由一个主控节点和多个从属节点组成，主控节点和每个从属节点之间都建立了通信连接，实现聚合通信，从属节点相互之间可以实现点到点通信[2]。

　主控节点的功能主要包括与用户进行交互，向从属节点广播、分发消息，收集、归纳从属节点发来的消息，以及系统认证、网络管理和远程控制等。
从属节点的功能主要用于计算、接收主控节点发来的各种控制命令、数据，根据控制命令在其节点机上进行相应的执行，然后将执行后的结果传回给主控节点。
　单层型结构集群的实现相对简单，易于操作，且集群工具和应用软件较多，所以应用广泛。但是由于集群中只有一个主控节点，在聚合通信时，无论是一对多模式，多对多模式还是多对一模式，都要围绕着主控节点进行,使得集群中全局通信流量所占比重较大。当集群节点数增加或计算量很大时，网络负载极易到达额定上限，使得主控节点无法正常运行，计算性能下降。
　单层型结构的消息广播和消息收集的时间复杂度均为：O(n)
1.2 树型结构介绍
树型结构是针对单层型结构在消息广播和消息收集方面速度慢、可扩展性差的弱点而提出的新的消息传输结构。图2所示为典型的树型结构，和单层型结构一样，树型结构也有主控节点（根节点）和从属节点（叶子节点），且功能与单层型结构类似。不同的是，树型结构中还包含分支节点，这些分支节点是树的内部节点，没有计算功能，也没有系统认证、网络管理和远程控制等功能，只有对消息的转发、分发和收集功能，所以也叫路由节点。图2中，根节点与其下一层的分支节点有直接的通信连接，同样每个分支节点都与其下一层的节点有直接通信连接，上层节点与下层节点可以实现聚合通信，而拥有同一个父亲的同层节点之间可以进行点到点通信。除此以外，其他非同父节点相互之间没有建立直接的通信连接。

树型结构集群可以将全局通信域划分为多个子通信域，并且可以将主控节点的负载量分担到各个分支节点上，降低全局通信量进而改善集群计算环境。同时随着树的深度增加，使得集群更易于扩展。但该集群实现起来比较复杂，且没有专用的协议、应用软件或集群工具的支持[3]。
树型结构的消息广播和消息收集的时间复杂度均为：O(logn)
2 树型MPI的设计与实现

虽然使用树型结构的集群系统可以改善聚合通信的效率，但其实现起来则相对复杂。主要原因是常用的MPI计算通信工具基于单层型集群设计，是在主控节点与若干计算节点之间的通信基础之上实现的。为此，本文提出了一种利用IP转发技术和MPI并行编程技术实现树型结构的MPI集群系统设计方案。这里需要注意以下问题：
　(1)根节点的设计
　在构建集群网络时，网络安全和通信效率既相互依赖又相互制衡。若省去频繁的核实用户身份等安全方面的检查，则可以省去一部分系统开销，进而提高网络通信效率，但集群网络的安全性就无法保障；同样，若牺牲通信效率而实现网络安全，则集群计算的优势将无法体现。通常的做法是采用内外网模式，即从属节点和主控节点之间由内部网络互联，只有主控节点另有网络通道通向外部网络。这样，由于内外网络物理隔离，为网络安全提供了保证，在内部网络中可以省去频繁的用户身份认证等安全方面的开销，从而为通信效率的提升留出空间。
　根节点（主控节点）的设计也将采用内外网模式，在其机器上安装两块网卡（网络适配器），一块接集群内部网，使用内部网络设置，提供内部网络服务（域名服务，NIS，NFS和RSH）；另一块接外部网，留出对外联系的通道，两网卡之间不提供路由、转发等功能。
　(2)分支节点的设计
　树形结构中的分支节点用于连接根节点（主控节点）和叶子节点（计算节点），在整个集群中发挥两个作用：一个是承上启下的连接作用，另一个则是对根节点（主控节点）的分担作用，所以分支节点应具有路由和对消息的传递、分发和收集等功能。
分支节点的设计与根节点有类似之处。也是在其机器上安装两块网卡，一块连接上层节点（根节点或上层的分支节点），IP地址设置在上层节点的同一个网段内，默认网关指向上层节点（父节点），使其成为上层网络的成员；另一块连接下层节点（下层的分支节点或叶子节点），设置IP地址（最好与前一块网卡的IP地址不同网段），为下层网络提供网关服务。但若要在上下层两个网络实现路由，需要在分支节点上修改 /etc/sysctl.conf配置文件中的net.ipv4.ip_forward = 1（以Linux操作系统为平台参考），使得本节点机IP转发功能生效。这样做的目的是既能实现上下两层网络之间的通信，同时又能阻止基于网络第二层的广播帧的传播。
　(3)域名的设计
　在TCP/IP中,计算机之间的通信通过IP访问来实现，但IP地址不容易编程和管理，所以整个集群系统需要为每个节点提供一套统一的命名机制。如图3所示，Boot为根节点内部网卡的网络标识，bran01-up和bran01-down为同一个分支节点机上的两块网卡上的网络标识，前一块为连接上层网络的接口，后一块为连接下层网络的接口，leaf01为叶子节点的网络标识。MPI编程环境可以通过此域名来区分、访问运行在各个节点机上的进程（如MPI_Get_processor_name()函数）。

　对于集群系统来说，集群中所有节点域名和IP地址的对应关系的建立是在/etc/hosts文件中描述的，不仅是因为它们经常用到，而且还因为该文件结构简单，更易于快速查找。图3所示的/etc/hosts.equiv文件可以为RSH(远程shell命令)提供无口令远程登录，这也为各节点载入同一个计算程序二进制代码和用户身份的快速验证提供了可能。
(4)进程组和通信域的设计
　 MPI中的通信域（Communicator）提供了一种组织和管理进程间通信的方法。每个通信域包括一组MPI进程，称为进程组。这一组进程之间可以相互通信，而且这个通信域内的通信不会跨越通信域的边界。这样就提供了一种安全的消息传递机制，因为它隔离了内部和外部的通信，避免了不必要的同步。每个进程都至少在某个特定的通信域中，但有可能进程在多个通信域中，这就像某个人可以是多个组织的成员一样。进程组由一个进程的有序序列进行描述，每个进程根据在序列中的位置被赋予一个进程号（0， 1， ...，N-1）[4]。
　 本文将根节点与其相邻的下一层节点（孩子节点）划定为一个进程组0，将分支节点1与其相邻的下一层节点（孩子节点）划定为进程组1，…，依此类推，直到所有分支节点或根节点都拥有自己的进程组为止，如图4所示。由于每个分支节点或根节点都有两块网卡，所以将两块网卡分属不同的进程组中，彼此互不包含。将全局通信域划分成若干个子通信域，使得大量的消息传递开销被限制在局部范围内,大大降低了全局通信的频率，从而提高了集群通信的性能。

(5)组间通信
　进程组划分之后，形成相应的通信域，规避了大量节点间同步所消耗的开销。但进程组之间也要进行通信，根节点需要将消息逐层传递到叶子节点，同样叶子节点所计算出来的结果也是要逐层收集、规约到根节点，所以组间通信也是本系统实现的关键之一。这里,通过使用MPI组间通信函数(如MPI_Intercomm_create()函数)来实现组间消息的传递。
　(6)叶子节点的设计
　 叶子节点作为主要计算节点，除了NIS、NFS、RSH客户端软件和MPI相关软件外，尽量不再安装其他软件，以减少叶子节点额外的开销。设置与其父节点同属一个网段的IP地址，并将网关指向其父节点。如有必要可以精简操作系统内核，使其尽量占用CPU时间少、占用内存少。
3 实验结果与分析
3.1 实验环境和方法
本实验将先后搭建三组环境对这两种结构的MPI集群进行测试,测试环境如下：
(1)第一组是具有2个计算节点的集群，单层型和树型集群均由1个主控节点和两个计算节点构成。
(2)第二组是拥有4个计算节点的集群，单层型是指1主控节点和4个计算节点构成，而树型结构则是由1个根节点（主控节点），2个分支节点和4个计算节点构成，其中每个分支节点各连接两个计算节点,对称分布。
(3)第三组是具有6个计算节点的集群,如图5所示。左图为单层型MPI集群，拥有6个计算节点和1个主控节点；右图为树型集群，拥有1个根节点，2个分支节点和6个计算节点。

这其中每个节点包含一颗PIV处理器和2 GB内存，操作系统采用Redhat Linux Enterprise 5，并行集群软件为OPEN MPI 1.3。由于条件所限，加之实验规模较小，所以本实验采用MPI自带的函数MPI_Wtime()来采集MPI计算的开始和结束时间，取两者的时间差作为程序的运行时间，并对其进行比较和分析，用MPI_Wtick()函数来监测MPI_Wtime()返回结果的精度。
在实验用例设计上，考虑到两种MPI集群的通信机制中的传输路径不同，所以采用计算求解三对角方程组作为测试方案，主要测试通信和计算的平衡。
3.2 测度结果和分析
测试结果如表1、表2所示。

测试结果表明,在第一组的测试中，双方的运行时间没有明显差别，这是由于它们都拥有1个主控节点和2个计算节点。虽然树型结构在MPI聚合通信机制上有所改动，但影响有限，测试的结果基本相同。对于第二组的测试，测试结果差异较明显，在传输短消息时，可以发现单层型集群的运算速度并不比树型慢多少, 在16 B的情况单层型还优于树型。这是因为树型结构的集群中除了拥有和单层型相同数目的计算节点外，还有两个分支节点（也叫路由节点），分支节点需要在两个通信域之间传递处理消息，需要处理时间，所以树型结构的消息传输时间除了消息广播和收集时间外，还有域间转发处理的时间。尽管在时间复杂度上树型结构优于单层型结构，但在通信域中节点数较少、消息较小的情况下，两者之间差距不是十分明显，若再加上域间处理的时间，自然会出现这样的情况。但当消息增大时，由于树型结构中每个通信域的广播和收集时间远远小于单层结构的广播和收集时间，从而抵消了分支节点处理消息的时间，所以树型的整体运算时间明显小于单层型的运算时间。对于第三组的测试，树型的整体运算时间明显优于单层型集群，几乎相当于同级别单层型集群的1/2。这是由于随着计算节点的增加，树型MPI集群的优势明显发挥出来，尤其是聚合通信方面。
　由上分析表明，基于树型MPI并行计算集群的设计方案是可行的。在该方案上构建的MPI集群系统可以使消息广播和消息收集的速度明显提高，使得全局通信使用频率明显下降，从而提升了集群整体计算速度。同时，由于树型结构的特点，使得集群的扩展更加轻松。尽管从理论上可知随着节点数的增加树型MPI的集群的优势将更加凸显，但是由于实验条件的限制，只能对集群通信系统做初步验证。所以希望在未来的研发工作中能够引入更科学的评测体系，不断地论证和完善该系统，为提升中小型MPI集群性能提供帮助。
参考文献
[1] 刘洋，曹建文，李玉成. 聚合通信模型的测试与分析[J].计算机工程与应用，2006(9):30-33.
[2] CHEN C P. The parallel technologies (PaCT-2003)[C]. Nizhni Novgorod, Russia.2003.
[3] ROCH P C, ARNOLD D C, MILLER B P. MRNet: A software-based multicast/reduction network for scalable Tools[A]. Phoenix, Arizona, 2003.
[4] 莫则尧，袁国兴.消息传递并行编程环境[M].北京：科学出版社，2001.