【博士论文】集群系统中的网络流调度

2021 年 12 月 7 日 专知

来自清华大学张彤的博士论文，入选2021年度“CCF优秀博士学位论文奖”初评名单！

https://www.ccf.org.cn/Focus/2021-11-22/750448.shtml

集群系统中的网络流调度

当前，集群系统的部署和使用非常广泛。在集群系统中，一个任务通常分为多个处理阶段顺序执行，而在各处理阶段之间需要通过内部网络来传输数据和中间结果。已有测量工作表明，数据传输时间占整个任务运行时间的比重很大，因此优化集群系统中的数据传输时间对于加速任务、提升应用性能非常重要。网络流调度是优化数据传输时间的有效方法，主要指为数据流设定传输顺序以及分配带宽。在小规模集群系统中，网络内部容易做到无阻塞，流调度主要在边缘链路上；而在大规模集群系统中，网络内部也可能成为瓶颈，流调度也应作用于网络内部。由于集群系统应用种类繁多，通信模式各不相同，因此内部网络中既存在独立的单流也存在并发的流束。相应地，网络流调度既包括单流调度也包括流束调度。根据以上分类，本文分别在小规模与大规模集群系统中针对单流调度和流束调度的问题进行了研究：

(1) 提出了稳定的单流调度策略。针对小规模与大规模集群系统都存在的调度策略不稳定问题，本文设计了稳定的单流调度策略 BASRPT，并且针对小规模和大规模集群系统分别设计了两个版本。BASRPT 同时考虑流的剩余大小和所在队列的队长，优先传输长队列中的短流，既能够控制队长又能够缩短流完成时间。仿真结果表明，BASRPT 能够维持队列长度稳定并取得较低的流完成时间。

(2) 提出了已知部分信息的流束调度策略。针对小规模集群系统中部分流束信息可知的场景，本文设计了已知部分信息的流束调度策略 IICS。IICS 借助流束中已到达子流信息对剩余传输时间进行预测，并基于预测值近似实现最小剩余时间优先。仿真结果表明，IICS 能够取得与信息完全可知的策略接近的流束完成时间。

(3) 提出了网络内部瓶颈感知的流束调度策略。 针对大规模集群系统中的网络内部瓶颈约束，本文设计了分布式网络内瓶颈感知的流束调度策略 DBA。DBA 在所有链路的带宽约束下，通过各节点演化的方式近似实现了全网范围的最小剩余时间优先策略。仿真结果表明，DBA 具有优越的流束完成时间性能和高吞吐量。

(4) 提出了光电路交换网络中的流束调度策略。针对大规模集群系统中光电路交换技术的快速发展，本文设计了光电路交换网络中优化流束完成时间的调度策略 GMRTF。GMRTF 同时结合了电路调度与流束调度，将同一电路上的子流适当分组，组内不切换电路，组间采用最小剩余时间优先策略。大量仿真实验验证了在光电路交换网络中 GMRTF 能够显著降低流束完成时间并提高吞吐量。