高阶互连网络中路由算法与交换开关调度方法研究

With the increasing speed of computation, high radix interconnection network has been proposed as the solution to the ever-growing communication requirements in high performance communicating system, and has become the hot topic in the research area. This research project will focus on addressing problems in communication of high-radix interconnection network, including congestion level modeling, routing algorithm design in the whole network, and scheduling algorithm design in single switch. Taking into account of packet type, load rate, length of packet queue, delay in router and on physical link, congestion level (CL) is modeled by analyzing the factors that influence the load distribution and flow, based on CL, the deterministic, adaptive, and congestion-aware adaptive routing algorithms are designed step by step. Besides, with fairness and time constriction, the model of scheduling in switch is determined, with relevant revolutionary methods designed according to the characteristics of different problems. Then, the congestion-unaware and congestion-aware scheduling algorithms are established successively. This research project will lay emphasis on communication optimization in high radix interconnection networks, including key problems in routing algorithm in the whole network and scheduling algorithm in the single switch, and also, it will provide methodology and theory tools to performance improvement of high performance computing system, development of new product, and victory achievement of international prestige.

随着计算速度的不断提高，高性能计算系统对通信性能的需求持续增长，高阶互连网络被提出并成为研究热点。本项目旨在研究高阶互连网络通信中路由算法设计和交换开关设计问题。通过分析影响负载分布和流向的因素，并综合考虑消息类型、通信负载、消息队列长度、路由器内部及物理链路上的传输延迟等信息，建立拥塞度的数学模型，递进设计确定性路由算法、适应性路由算法和拥塞相关的适应性路由算法；针对高阶网络中交换开关端口数较多的特性，在保证公平性和严格的时间约束下，建立交换开关资源-消息之间的调度模型，并针对不同的问题特点，设计求解模型的优化算法，在交换开关上递进实现拥塞无关的调度算法和拥塞感知的调度算法。项目在理论研究上解决高阶互连网络中通信优化问题，包括路由算法设计的关键问题以及交换开关设计中关键优化理论和方法，将为我国高性能计算系统的性能提高、新产品的研发、以及国际地位的赢得提供理论方法和技术支持。

近年来大数据已成为社会各界关注的焦点，成为一种可能提供巨大价值的资产，而大数据处理需要高性能计算的支持，成为支撑大数据分析的必经之路。互连网络的通信速度已经成为整个高性能计算系统的性能瓶颈，低延迟、低功耗、高吞吐量的互连网络设计是高性能计算系统发展的重要保障。在本基金项目的资助下，项目组应用并行分布式技术和最优化理论对高阶互连网络中路由算法设计和交换开关设计的优化与决策问题进行了深入研究，主要包括：提出了新的网络拓扑结构，并为之设计了相关的确定性和完全适应性无死锁路由算法；设计了高阶互连网络中的确定性和完全适应性无死锁路由算法；针对当前虚拟通道分配策略中存在的问题，提出了新的虚拟通道分配策略，增加了虚拟通道使用的均衡性，提高了通信性能；分析了应用映射对网络通信的影响，建立了应用映射优化的数学模型，给出了精确求解算法和启发式求解算法。四个方面的研究内容均进行了实验验证，本项目提出的一系列路由算法，有效提高了网络的通信吞吐量，降低了网络通信延迟；提出的虚拟通道分配策略可以与已有的路由算法结合使用，能够有效提高网络的通信性能；应用映射优化算法提供的映射方案所需要的功耗开销较小。本项目研究取得了一系列的科研成果，在项目执行期内，在国内外期刊上发表了一批高水平的学术论文（标注本基金号），包括SCI 收录论文7篇，发表在IEEE Transactions on Intelligent Transportation Systems (JCR 1区)上 1篇、IEEE Transactions on Systems, Man and Cybernetics: Systems (JCR 2区)上1篇(在线发表，DOI: 10.1109/TSMC.2016.2606440)、Journal of Supercomputing (JCR 2区)上3篇、IEICE Electronics Express (JCR 4区)上2篇，EI收录论文4篇，主要发表在《计算机学报》、ICA3PP会议上。