基于k-ary n-tree的硬件聚合通信技术研究

论文摘要

聚合通信是由一组进程参与的通信模式,在科学和工程计算中有着非常广泛的应用。数据分析表明,在许多大规模并行程序中,聚合通信的开销甚至占到全部通信开销的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。模拟结果表明,本文提出的负载平衡策略和报文调度算法都能够有效的提高聚合通信的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.1.1 互连网络成为HPC 的性能瓶颈
• 1.1.2 技术发展限制
• 1.1.3 亟待提高的聚合通信性能
• 1.2 聚合通信的实现方法
• 1.2.1 基于软件
• 1.2.2 基于网络接口
• 1.2.3 基于专用网络
• 1.2.4 基于互连网络
• 1.3 本文工作
• 1.4 论文结构
• 第二章 基于互连网络的聚合通信概述
• 2.1 引言
• 2.2 基本功能实现
• 2.2.1 报文寻址
• 2.2.2 路由算法
• 2.2.3 死锁问题解决
• 2.3 实用性能提高
• 2.3.1 负载平衡
• 2.3.2 报文调度
• 2.4 性能评价指标
• 2.4.1 聚合通信性能评价指标
• 2.4.2 互连网络性能评价指标
• 2.4.3 性能表示方法
• 2.5 本文采用的互连网络模型
• 2.6 本章小结
• 第三章 基于OMNeT++的模拟器开发
• 3.1 引言
• 3.2 OMNeT++简介
• 3.2.1 OMNeT++的组成
• 3.2.2 OMNeT++模型的结构
• 3.2.3 OMNeT++的建模流程
• 3.3 MINSimCC 的结构设计
• 3.3.1 结构模型
• 3.3.2 执行模型
• 3.3.3 模拟周期
• 3.4 模拟负载
• 3.4.1 负载模型
• 3.4.2 聚合通信负载模型
• 3.5 模拟结果收集
• 3.5.1 统计信息收集
• 3.5.2 结果可信度保证
• 3.6 本章小结
• 第四章 路由器等价关系和负载分布
• 4.1 引言
• 4.2 k-ary n-tree 简介
• 4.2.1 k-ary n-tree 的定义
• 4.2.2 拓扑特性
• 4.3 k-ary n-tree 上的报文路由
• 4.3.1 单播报文路由
• 4.3.2 基于树的聚合通信报文路由
• 4.4 路由器等价关系
• 4.4.1 等价关系的定义
• 4.4.2 定理和推论
• 4.5 负载分布
• 4.5.1 单播负载分布
• 4.5.2 聚合通信负载分布
• 4.6 本章小结
• 第五章 聚合通信的全局负载平衡
• 5.1 引言
• 5.2 基于树的报文路由
• 5.2.1 结构支持
• 5.2.2 聚合通信树构建算法
• 5.3 全局负载平衡策略
• 5.3.1 策略描述
• 5.3.2 算法复杂度分析
• 5.3.3 性能分析
• 5.3.4 算法实例
• 5.4 模拟评测
• 5.4.1 组播性能
• 5.4.2 归约性能
• 5.5 本章小结
• 第六章 单播前瞻自适应路由算法
• 6.1 引言
• 6.2 完全自适应路由算法
• 6.2.1 目标地址编址
• 6.2.2 路由决策
• 6.3 前瞻自适应路由算法
• 6.3.1 组播拥塞
• 6.3.2 前瞻自适应路由算法
• 6.3.3 算法实现
• 6.3.4 性能分析
• 6.3.5 与相关工作的比较
• 6.4 模拟评测
• 6.4.1 阈值确定
• m = 0.5 时的性能'>6.4.2 M_m = 0.5 时的性能
• m = 0.2 时的性能'>6.4.3 M_m = 0.2 时的性能
• 6.5 本章小结
• 第七章 MSFS 集成调度算法
• 7.1 引言
• 7.2 调度算法研究
• 7.2.1 单播调度算法
• 7.2.2 组播调度算法
• 7.2.3 集成调度算法
• 7.3 分布式仲裁机制下的报文调度
• 7.3.1 分布式仲裁机制
• 7.3.2 分布式仲裁机制下的集成调度
• 7.4 启发式组播调度算法——MSFS
• 7.4.1 报文调度的另一个目标——低延迟
• 7.4.2 MSFS 的基本思想
• 7.4.3 与单播调度算法的集成
• 7.4.4 算法实现
• 7.4.5 性能分析
• 7.5 模拟评测
• m = 1 时的性能'>7.5.1 M_m = 1 时的性能
• m = 0.5 时的性能'>7.5.2 M_m = 0.5 时的性能
• m = 0.2 时的性能'>7.5.3 M_m = 0.2 时的性能
• 7.6 本章小结
• 第八章 归约调度算法
• 8.1 引言
• 8.2 归约计算单元简介
• 8.2.1 归约计算单元结构
• 8.2.2 报文处理流程
• 8.3 归约的延迟模型
• 8.3.1 无冲突条件下的归约延迟
• 8.3.2 有冲突条件下的归约延迟
• 8.3.3 报文冲突对归约延迟的影响
• 8.4 报文调度算法
• 8.4.1 归约调度
• 8.4.2 与单播调度算法的集成
• 8.4.3 性能分析
• 8.5 模拟评测
• 8.5.1 归约调度算法的性能
• 8.5.2 集成调度算法的性能
• 8.6 本章小结
• 第九章 路由器结构设计与优化
• 9.1 引言
• 9.2 整体结构设计
• 9.2.1 顶层结构
• 9.2.2 微片格式
• 9.2.3 基于信用的流控
• 9.2.4 缓存队列管理
• 9.2.5 优先级仲裁器
• 9.3 性能优化
• 9.3.1 路由器延迟
• 9.3.2 延迟优化策略
• 9.4 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间所发表的论文