论文部分内容阅读
聚合通信是由一组进程参与的通信模式,在科学和工程计算中有着非常广泛的应用。数据分析表明,在许多大规模并行程序中,聚合通信的开销甚至占到全部通信开销的80%、总执行时间的60%以上,成为高性能计算机系统的性能瓶颈。传统的基于软件的实现方法已经不能满足高性能计算技术发展的需求,如何通过网络硬件对聚合通信进行支持成为一个重要的研究课题。基于互连网络的聚合通信技术自从被提出以来,已经取得了广泛而深入的研究。多数研究主要集中在聚合通信基本功能的实现上,包括路由器功能需要做怎样的扩展、聚合通信报文如何寻址、如何路由以及死锁问题如何解决等。基于互连网络的聚合通信在路由器上执行的是一对多或者多对一操作,更加容易形成报文冲突,其性能也更加容易受到报文冲突的影响。因此,要从实用性的角度进一步提高其性能,还需要解决两个方面的问题:第一,如何减少报文之间的冲突;第二,使用什么样的策略解决已经产生的冲突。本文围绕这两个问题对基于k-ary n-tree的硬件聚合通信技术展开了深入的研究,主要取得了以下一些研究成果。1.深入研究了k-ary n-tree的拓扑特性。提出了k-ary n-tree上的一种路由器等价关系,形式化地描述了一条报文传输路径或者一棵聚合通信树所经过的路由器范围,为k-ary n-tree上负载平衡的研究奠定了理论基础。2.提出了聚合通信的全局负载平衡策略。该策略在聚合通信树构建算法的上升过程中,使用路由器等价类的聚合通信负载作为选择最轻负载父节点的标准,保证了聚合通信负载在整个k-ary n-tree上的平衡分布,从而减小了由报文冲突引起的聚合通信性能降低。3.分析了组播拥塞的产生和传播机制,提出了单播报文的前瞻自适应路由算法。该算法在单播报文传输的上升过程中,根据当前路由器的组播负载状况对网络中可能存在的组播拥塞进行预测,并由此控制报文输出端口的选择,以避免单播报文经过可能存在组播拥塞的路由器,从而减小了由组播拥塞引起的网络性能降低。4.针对高性能计算机对互连网络延迟敏感这一特点,提出了最大服务优先的组播调度算法——MSFS。MSFS从减小组播报文在单个路由器上传输延迟的角度出发,根据接收到报文副本的输出端口数和报文在缓存队列头位置的等待时间来确定组播报文的优先级,同时兼顾了网络吞吐率和报文传输延迟。如果将单播报文看成是扇出数为1的组播报文,MSFS等价于FCFS单播调度算法,因此在单播和组播并存的互连网络中,MSFS能够与FCFS进行“无缝”集成。5.建立了无冲突和有冲突条件下的归约延迟模型,并具体分析了不同类型的冲突对归约延迟的影响。证明了剩余集中的调度算法能够取得多个归约操作在路由器上平均延迟的最小值;提出了使用FCFS策略解决归约报文之间冲突,以减小后调用操作对先调用操作的性能影响;提出使用归约报文优先的策略解决单播报文和归约报文之间的冲突,以减小单播对归约性能的影响。本文基于离散事件模拟平台OMNeT++开发了多级互连网模拟器MINSimCC。模拟结果表明,本文提出的负载平衡策略和报文调度算法都能够有效的提高聚合通信的性能。