第21届HotNets于2022年11月14日-11月15日在美国得克萨斯州奥斯汀召开。本次会议共收到104篇投稿，接收32篇论文，录取率为30.77%。

SNG的同学们按照会议日程对论文内容进行了分期评述，本期介绍session9的论文。

Session 9: Keeping up with ever-increasing performance demands

Efficient Flow Scheduling in Distributed Deep Learning Training with Echelon Formation

Rui Pan (Max Planck Institute for Informatics), Yiming Lei (Max Planck Institute for Informatics), Jialong Li (Max Planck Institute for Informatics), Zhiqiang Xie (Max Planck Institute for Software Systems), Binhang Yuan (ETH Zurich), Yiting Xia (Max Planck Institute for Informatics)

分布式深度学习训练的经典假设是语义相关的流应该同时完成。作者对大量分布式深度学习训练的工作流进行了分析，反驳了经典假设：分布式训练任务可能在不同时间消耗数据。基于此，作者首先对训练范式进行建模，据此建立EchelonFlow来调整流的完成时间。为了评估系统的性能，作者进行了案例研究，结果表明了EchelonFlow调度系统的灵活性。

背景

近年来，依托于数据集和模型复杂度增加，在分布式框架下训练的深度学习模型的质量取得重要进展。然而，训练这些模型需要节点间大量的通信。合理调度这些网络流量有可能降低任务完成时间。然而，现在还没有关于分布式深度学习流调度的研究。原因有2个：定义训练任务的优化目标困难；缺少网络抽象。

为了进一步探索分布式深度学习流调度问题，作者进行了大量分布式深度学习训练任务。分析结果表明，每一个分布式深度学习训练任务都有一个唯一的、预定义的计算模式，该模式调整流传输的完成时间。这些计算模式本质是有向无环图。利用神经网络的layer和iteration间的计算相似性，这些计算表现出可抽取的模式。

利用这些洞见，作者提出EchelonFlow。EchelonFlow是一个网络抽象，它刻画了计算模式下流的完成时间。这个网络抽象可以用来建立全局优化目标：最小化通信时间和保持计算模式。

EchelonFlow

EchelonFlow的设计灵感来自斜线阵列。具体来说，分布式深度学习训练的计算单元模仿了军事梯队中的飞机队列。斜线排列中计算单元的相对位置映射为分布式深度学习的模式。在这样的排列中，单元的形状由特定的工作流决定，单元间的距离是计算单元的持续时间。上面的形状和距离可以通过迭代运行训练过程得到。维持计算排列的关键是管理流的完成时间。

因此，作者定义了流的理想完成时间。假设数据传输时间是零，理想的流完成时间是它的开始时间。如果计算单元生成的数据流不满足计算排列，它们的理想流完成时间应该延后来偏移相应的延迟。此外，作者也定义了引用时间作为第一个流的开始时间。基于第一个流的开始时间和流的引用时间，后面的流完成时间可以被刻画出来。

一个EchelonFlow是一个理想完成时间相关的网络流集合。作者定义了流的理想完成时间，实际完成时间，和延迟的时间（实际完成时间减去理想完成时间）。由于要保证计算的排列，因此延迟时间应该保持一致。那么EchelonFlow整体的延迟时间应该取最大值，最小化EchelonFlow完成时间就是最小化最大延迟时间。多个EchelonFlow的目标函数可以通过（加权）求和来表示。

作者证明了EchelonFlow的4个性质：1. EchelonFlow调度最小化主流的分布式深度学习训练范式的完成时间。2. EchelonFlow是Coflow的超集。3. EchelonFlow的调度是NP-hard。4. Coflow调度算法可以在相同复杂度下适配到EchelonFlow任务中。

案例研究

第一个案例是符合coflow范式情况。Coflow是EchelonFlow中的流共享相同理想完成时间的特例。这方面的例子有数据并行，例如AllReduce、parameter server和Megatron的张量并行情况中，只有接收到所有梯度后才会进行下一阶段计算。

第二个案例是流水线并行。例如GPipe为每个节点上的连续批数据传递激活值/梯度，因此这些计算所依赖的数据流应该在流水线中保持交错的完成时间。它的排列函数刻画理想完成时间是引用时间或上一阶段时间加上T。

第三个案例是全分片的数据并行。ZeRO/FSDP在下一层前向/反向计算前收集所有的梯度，构成coflow，这些coflow沿着计算时间线进一步构成EchelonFlow。

实现框架

EchelonFlow位于分布式深度学习训练框架和消息传播后端之间。它首先通过EchelonFlow的API收集每一个流的信息和排列函数，然后实现流调度算法并将调度决策发给后端。

个人观点

EchelonFlow扩展了Coflow的语义，但是该抽象的前提条件较高，需要收集数据和额外的计算，另外没有量化的实验分析。

Congestion Control in Machine Learning Clusters

Sudarsanan Rajasekaran (MIT), Manya Ghobadi (MIT), Gautam Kumar (Google), Aditya Akella (UT Austin)

公平共享不是机器学习训练集群的期望属性。对于特定的作业组合，引入不公平性可以提升训练时间。作者把这个特定的作业组合叫做兼容性，并定义了兼容性的度量。作者提出的抽象需要首先运行一轮，并旋转作者的通信阶段来识别出兼容的作业。使用该抽象可以提升1.3倍的平均训练时间。作者主张资源管理算法应该考虑作业在网络链接上的兼容性。然后提出三个缓解网络拥塞的方向：自适应不公平拥塞控制算法，交换机上的优先级队列，精确的流调度。

背景

分布式机器学习中的通信开销占据了训练迭代的大部分。现有缓解通信开销的方法忽略了网络拥塞，倾向于使用TCP或RDMA的默认拥塞控制机制来解决。作者发现对特定的作业组合，引入不公平性有可能优化训练时间。背后的思想是这些作业可以交替执行计算和通信，作者把这叫做兼容。为了识别出作业集的兼容性，作者提出使用深度学习训练的周期开闭模式来根据时间来判断。据此，作者提出使兼容的作业放置在相同的网络链路，为兼容的作业引入不公平性可以优化训练完成时间。

几何抽象

作者核心回答的问题是：一种方式来滑行作业的通信模式使得作业间没有overlap。

首先作者对训练进行建模：一轮迭代时间的环形表示。一次迭代训练需要的时间分两部分：计算和通信。将这两部分时间看成整体，首尾相连构成时间环。

然后作者提出旋转环来避免拥塞。将多个环放在一起，通过旋转环来避免计算时间冲突，找到这样一个没有冲突的环的旋转角度叫做找到了一组兼容的作业。

为了实现方法的普适性，使用各个作业迭代时间的最小公倍数。

在求解该优化问题时，如果存在环上每个事件只有不超过一个作业执行，即为最优解。

工作流程

具体的工作流程分为2步骤：

1. 在网络链路上考虑作业的兼容性，找到最优的旋转参数；

2. 实现不公平的调度。作者给出三种可行方法：

（1）不公平的拥塞控制算法，例如调整发送速率速率公式。

（2）用packet的优先权实现不公平性，例如在主机标注优先权，交换机据此划分带宽，从而实现不公平性。

（3）调度方式，例如使用中心调度器来实现周期性调度流。

个人观点

这篇文章本质是多作业调度，但提出了一种新的调度目标：最小化网络拥塞。最小化作业完成时间是广泛采用的,但是避免拥塞是用户期望的行为吗？这个问题还需要时间检验。

Getting back what was lost in the era of high-speed software packet processing

Marcelo Abranches (University of Colorado Boulder), Oliver Michel (Princeton University), Eric Keller (University of Colorado Boulder)

这篇⽂章由康奈尔大学和谷歌团队合作完成。

背景与问题

Linux实现其网络堆栈所需的数据包处理的过程是低效的，性能不能满足需求。人们广泛采用基于软件的数据包处理的方式，实现高性能的定制的数据包处理的新方法。例如内核旁路，它有效地将数据包复制到用户空间程序进行处理；内核网络堆栈旁路，它们运行在内核空间内，但只有当流量不接触Linux网络堆栈时才能获得高性能。但是在不降低性能的情况下，这些方法无法利用Linux丰富且广泛使用的网络功能、丰富的ecosystem扩展到围绕Linux API和接口以及命令行工具构建的管理软件和控制平面软件等等。因此，本文建议重新考虑Linux网络堆栈的设计，以解决其缺点，提高其数据包处理的性能，而不是直接用别的方法取而代之。

设计

本文重新设计Linux网络堆栈，核心思想是将Linux数据包处理分解为一组Linux网络子系统的一系列轻量级模块。其中涉及（1）将分组处理分解为快速路径和慢速路径，以及（2）透明地动态地创建仅实现当前配置的处理任务的自定义快速路径。利用Linux的eXpress Data Path来加载高效且小的快速路径模块，让kernel堆栈充当慢路径。为此，本文介绍了透明网络加速（TNA），其核心组成部分是TNA快速路径模块和TNA控制器。具体如下：

首先，设计快速路径模块（Fast Path Modules）。上述每个子系统的轻量级模块负责简单的任务，如解析和重写数据包。这些轻量级模块即为TNA快速路径模块。作者仍需要为这些模块构建库来执行每个网络子系统所需完成的任务。在模块中插入轻量级元素，使其只需要完成几个简单的任务，但是可以处理大部分的数据包，而不需要转发到Linux网络堆栈中，提高数据包处理效率。因此，还要在模块中添加确定数据包是在快速路径中处理，还是需要传递到Linux堆栈的功能。而这个功能只使用现有的Linux网络数据结构。

其次，如图，使用一系列组件来设计TNA控制器。TNA控制器能够反思Linux内核，构建表示网桥所需内核对象的依赖关系图，包括网桥名称、连接的网络接口及其配置（例如，VLAN、STP等）。基于此图，TNA快速路径汇编器构成最小数据路径。关键步骤：（1）反思Linux内核。既在控制器启动时向内核发送查询以获得当前配置服务的初始视图，也通过加入多播组以获得关于配置更改和更新的内核通知。接收到的消息被转换为包含对象类型和一组配置属性的网络对象描述（TNA对象）；（2）构建依赖关系图。TNA通过将TNA对象提供给拓扑管理器组件来构建依赖关系图，该组件负责处理每个对象并建立它们之间的关系，即创建TNA图。它表示当前配置的服务和组成它们的对象的依赖关系图。

评估

为了说明TNA的好处和性能提升，本文加速了Linux桥接子系统。将TNA与Linux（kernel 5.15）和Polycube(v0.9.0)进行部署和比较。

根据CPU数量，TNA加速网桥的吞吐量比Linux网络堆栈实现提高了3.5–4.5倍。使用TNA加速的Linux网桥比不使用TNA的网桥快4.5倍,比Polycube网桥快2.5倍。TNA还可以利用Linux网桥实现和相应的配置工具。在这种情况下，TNA的速度更快，因为它避免不必要的数据包处理开销和对内核数据结构的优化访问。

总结

TNA具备许多良好特性。例如，Polycube绕过Linux网络堆栈，直接利用XDP加速桥接，无法使用标准Linux工具配置Linux网桥，对用户不透明。而本文可使用标准的未修改工具（例如ip）配置Linux网桥，并让TNA控制器自动为此部署一个加速的XDP数据路径，对用户透明。基于对当前网络配置的反省，TNA自动生成最小数据路径，避免了Linux中的许多网络堆栈开销，同时确保了高性能并能够继续利用Linux丰富的功能。但TNA仍有诸多需要改善的地方。未来工作如下：

(1) 对Linux内核网络堆栈进行更全面的分析，以支持本文提出的Linux内核网络堆栈重新设计,对其进行更多的分解。

(2) 研究构建和优化TNA依赖关系图的技术，并基于此生成和部署代码。

(3) 提出一个模型，在插入自定义处理时，确保数据平面的正确性和一致性。

(4) 探索考虑新网络堆栈设计的调试机制。

Understanding Host Interconnect Congestion

Saksham Agarwal, Rachit Agarwal (Cornell University); Behnam Montazeri, Masoud Moshref, Khaled Elmeleegy, Luigi Rizzo, Marc de Kruijf, Gautam Kumar (Google); Sylvia Ratnasamy (Google and University of California Berkeley); David Culler, Amin Vahdat (Google)

这篇⽂章由康奈尔大学和谷歌团队合作完成。本文呈现了在生产集群上发现的主机端拥塞的问题：采用高带宽的链路会导致主机端互连（网卡到CPU的数据路径）内出现瓶颈问题。文章说明了，现有的I/O内存管理单元和/或内存子系统上的竞争会严重减少网卡到CPU大可用带宽，导致数百毫秒的排队时延，最终导致主机上的数据包丢失，这个问题使用目前最先进的拥塞控制机制也不能有效解决。

背景

主机上网卡和CPU间的数据路径如下图所示。

网卡将所有到达的数据包放入它的输入缓冲区的队列中；

网卡从一个队列中取出一个Rx描述符。若I/O设备的内存保护机制开启，这些描述符提供的是一个的DMA到主机端内存的虚拟地址；

网卡使用数据包描述符中的地址，实例化一个PCIe写传输，PCIe使用credit-based的流量控制； 写传输请求会被PCIe root complex（PCIe的另一端）处理。PCIe root complex首先使用input/output memory management unit (IOMMU)，进行内存虚拟地址到物理地址的转换，I/O translation lookaside buffer (IOTLB)的cache可以加速虚实地址转换的过程； 获取到物理地址后，PCIe root complex通过内存总线（和CPU共享），将数据移动到主机内存； root complex完成内存写操作后，就会补充PCIe credit；网卡中断CPU开始数据包处理，补充RX描述符。

值得注意的是，如果内存保护没有开启，就不需要虚实地址的转换，因为描述符能够提供网卡DMA数据包的目的内存物理地址。

主机端拥塞

文章阐述了在大规模谷歌的生产集群中观察到了主机端拥塞现象。下图显示了主机的链路利用率(按访问链路带宽标准化)和丢包率的散点图。该集群同时运行Linux内核和SNAP网络堆栈，分别使用TCP和Swift拥塞控制协议。

作者通过实验，分析主机端拥塞是由IOMMU和内存总线这两方面导致的。

1. 由IOMMU导致的主机端拥塞：

几乎所有现代主机都使用输入/输出内存管理单元(IOMMU)启用内存保护——对于网卡发起的每个DMA请求，IOMMU使用主要驻留在内存中的页表将网卡可见的虚拟地址转换为主机物理地址;这些地址转换使用特殊的翻译备用缓冲区(IOTLB)缓存来加速。若IOTLB miss，则需要额外的一次或多次内存访问进行页表遍历，从而导致大的DMA延迟。例如，若IOTLB命中，则通常只需要几纳秒的延迟;然而，若IOTLB miss则可能触发一次或多次内存访问(取决于IOTLB中已经缓存的页面输入级别)，从而导致额外的延迟，这个延迟从几百纳秒到一微秒不等。考虑到NIC只能有少量固定大小的DMA事务在运行，每个DMA延迟的增加会直接影响NIC将数据传输到内存的速率。

作者进行了实验来验证上述结论。由下图可知，与关闭IOMMU相比，开启IOMMU导致的拥塞会造成最多的吞吐量下降，和最多的丢包率。随着CPU核数的增加，注册到IOMMU的页表项增多，大量IOTLB丢失很快造成主机端互连的瓶颈。

实验还发现，禁用大页会产生更多的IOMMU竞争，导致吞吐量下降以上。在如此低的网络利用率下，丢包率仍然可能高达，如下图所示。

1. 内存总线导致的主机端拥塞：

主机端拥塞的另一个根本原因是访问链路带宽和内存总线带宽之间的差距正在迅速缩小:在大型服务器中，执行大量内存操作的应用程序可能会导致来自网卡的内存请求饥饿。具体来说，在主机互连中，向内存读写数据的CPU与执行DMA操作的网卡共享内存总线;当内存总线竞争时，来自网卡的内存请求的每个DMA的延迟增加。

为更大的BDPs配置网络会使主机端拥塞问题变得更糟——主机需要至少BDP大小的内存来存储到达的数据包。如下图所示，较大的内存会显著降低应用程序的吞吐量，因为每个核向IOMMU注册的页数量增多，导致IOTLB miss增多，IOMMU会迅速成为瓶颈。

如下图所示，增加内存带宽竞争会降低网络利用率(即使没有IOMMU争用也会降低)。同时增加IOMMU竞争会导致更大的性能下降(15个core时，性能下降约)。

主机端拥塞问题的解决方法

文章从主机端结构、拥塞信号和拥塞应对这三个方面提出了可能的改进措施。

1. 为下一代数据中心网络重构主机端架构：

(a)能够保护内存不受网卡影响的其他体系结构，例如，像ATS这样的可以有效地卸载I/O地址转换的技术。

(b) PCIe链路层协议的替代方案，例如CXL，可能通过潜在地减少PCIe延迟或通过扩展PCIe通道上的内存带宽在一定程度上缓解主机拥塞问题。

(c)探索在计算和网络流量之间更“公平”地共享内存带宽的方案，如英特尔MBA和ARM MPAM。我们可以利用现有的QoS调度思想来设计共享内存带宽机制。

1. 重新设计拥塞控制信号：

未来的拥塞控制协议应该同时包含来自“网络外部”的新拥塞信号(例如，CPU利用率、内存带宽竞争、内存碎片等)，以及对这些信号作出反应的新机制。

1. 重新设计拥塞应对机制：

首先，需要一种更协调的方法来平衡所有组件(计算、内存带宽、网络带宽)的资源分配;例如，与其在网卡拥塞时降低网络传输速率，还不如触发CPU重调度来减少内存总线瓶颈(例如，调度不同于连接网卡的NUMA结点上的应用程序)。其次，需要重新思考拥塞响应的时间尺度:虽然RTT级别的响应可能足以应对网络拥塞，但太比特以太网和停滞的N网卡缓存大小的出现可能需要针对主机拥塞的次RTT响应。

个人观点

本文的作者关注到了主机端拥塞的问题，发现其来源是IOMMU和内存带宽。但早在2019年，阿里巴巴已设计了一个以缓存为中心的架构来应对主机端拥塞问题(https://arxiv.org/abs/2211.05975)。其基本思想是绕过内存，仅使用一小部分的cache容量，来确保接收的到数据可以以快速地被处理。从2020年开始，该设计已成功部署在阿里巴巴的实际生产网络中。

版权声明和个人见解说明

本文中所有的图片截取自论文正文，版权属于作者与ACM。

对每篇论文的“个人观点”仅仅是一人之见，希望能抛砖引玉，请大家多多发表意见。