ARTICLE

WANG W, KHAZRAEE M, ZHONG Z, et al. TopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed Training Jobs \[Z\]. NSDI. 2023 https://www.usenix.org/conference/nsdi23/presentation/wang-weiyang 论文简介 1. 摘要 本文提出一种新的适用于DNN的直连结构网络$T_{OPO}O_{PT}$，它可以在计算、通信和网络拓扑三个维度上优化分布式训练的过程。我们演示了 AllReduce 流量的可变性，并利用此属性为 DNN 训练作业构建高效的网络拓扑。然后，$T_{OPO}O_{PT}$使用交替优化技术和名为TotientPerms的群论启发算法来找到最佳网络拓扑和路由计划以及并行化策略。我们构建了一个功能齐全的 12 节点直连原型，具有 100 Gbps 的远程直接内存访问 (RDMA) 转发。对真实分布式训练模型的大规模模拟表明，与类似成本的 Fat-tree 互连相比，TOPOOPT 将 DNN 训练时间减少了高达 3.4 倍。 2. 主要贡献 综合考虑了计算、通信和网络拓扑三个维度的优化策略 分析了MP与AllReduce的流量特征 利用AllReduce的流量可变性优化AllReduce路径 利用交替优化技术和TotientPerms算法来找到最佳网络拓扑 在12个节点的情况下，比传统的胖树网络降低了DNN的3.4倍训练时间 实现方法 1. $T_{OPO}O_{PT}$架构 假定有n个Server，每个Server有d个接口，每个接口连接一个Optical Seicth，共计需要d个Optical Switch。Optical Switch可以通过配置可以在内部视作直接连接任意两个端口，从而实现任意两个Server之间的直接连接。 论文中提到Server与Optical Switch之间的连接是使用RDMA网卡，并对其进行了修改：原生RDMA网卡会抛弃非本机的数据，修改后支持数据转发和数据中继。 TOPOOPT的网络连接方式 论文中称Server的端口数量d为Server的Degree，它决定着每个Server与其他Server的连接数量，也是 $T_{OPO}O_{PT}$ 算法的一个计算参数。 2. 交替优化策略 问题： 从计算、通信、网络拓扑三个维度对并行计算进行优化会产生一个非常大的搜索空间，导致该优化问题可能无法求得最优解。 ...

I. 前置内容 在了解集合通信（Collective Communication）之前要先了解点P2P对点通信（Point-to-Point）。P2P通信通常为两个不同进程间的通信，是1对1的； 在MPI规范中，既有同步阻塞的P2P接口：MPI_send和MPI_Recv接口，也定义了非阻塞的P2P接口如：MPI_Isend、MPI_Irecve。 集合通信和P2P通信是相对应的，集合通信则是1对多或是多对多的。在分布式系统中，各个节点间往往存在大量的集合通信需求，而我们可以用消息传递接口（Message Passing Interface，MPI）来定义一些比较底层的消息通信行为譬如Reduce、Allreduce、Scatter、Gather、Allgather等。 1.1 系统架构 集合通信算法的优化往往与其对应的网络拓扑和系统架构有直接关系，通常情况下，一个节点内的GPU-GPU或GPU-CPU之间的结构成为系统架构，节点之间的网络连接称为网络拓扑，一种确定的系统架构会有确定的网络拓扑架构。 在HPC领域有很多经典的系统架构和网络拓扑，例如：Summit system或者Lassen system等。本文主要由于发表于2021年，很多系统架构和指标数据与当先最新数据差异较大，但是为了方便后续的理解，本文后续还是以Summit system和Lassen system为例进行分析。 简化的Summit System和Lassen System（论文中的结构） 每个节点包含6个GPU和2个CPU，每3个GPU和1个CPU组成一个Group，使用NVLink进行连接，CPU与CPU之间使用X-Bus进行连接，同时与IB网卡使用PCIe进行连接，节点间使用IB协议进行组网。NVLink、NVSwitch、IB等硬件设备的概念将会在下一节中介绍。 1.2 相关组件 NVLink and NVSwitch NVLink和NVSwitch是一种可支持服务器内和服务器间实现高级多 GPU 通信的基础模组。第四代NVLink技术可为多 GPU 系统配置提供高于以往 1.5 倍的带宽，以及增强的可扩展性。第三代NVSwitch基于 NVLink 的高级通信能力构建，可为计算密集型工作负载提供更高带宽和更低延迟。 Mellanox InfiniBand InfiniBand（直译为“无限带宽”技术，缩写为IB）是一个用于高性能计算的计算机网络通信标准，它具有极高的吞吐量和极低的延迟，用于计算机与计算机之间的数据互连。InfiniBand也用作服务器与存储系统之间的直接或交换互连，以及存储系统之间的互连。常用的IB交换机/网卡带宽普遍为为400GB/s。 Remote Direct Memory Access (RDMA) RDMA是一种概念，在两个或者多个计算机进行通讯的时候使用DMA， 从一个主机的内存直接访问另一个主机的内存。 1.3 (Non-)Personalized All-to-All 1.3.1 Non-Personalized All-to-All Non-Personalized All-to-All（通常称为 MPI_Allgather）是一种 MPI 集体通信模式，是 MPI_Gather 和 MPI_Bcast 的结合。所有进程按等级顺序从其他进程收集数据。操作结束时，每个进程都将与所有其他进程交换数据。 1.3.2 Personalized All-to-All Personalized All-to-All称为 MPI_Alltoall，与 MPI_Allgather 类似，所有进程都相互共享数据。然而，每个进程都会向其他进程发送不同的数据，从而形成一种个性化的集体通信模式（即，每个进程都会向每个其他进程发送不同的数据块） 1.4 相关算法 1.4.1 Ring 每个进程i发送数据给(i+1) \ N并从(i-1) \ N接收数据，但是这种方法会带来过高的延迟。 ...

参考文献： Narayanan D, Shoeybi M, Casper J, et al. Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM: SC’ 21, November 14-19, 2021, St. Louis, MO, USA \[C\], 2021. ACM, 2021-01-01. 单一的MP或DP无法硬度继续增长的大模型算力需求，面对成千上万的GPU集群规模增长，结合TP、PP、DP等多种方式组成3D Parallelism的并行方式逐渐成为了主流的并行计算框架。 1. 基于Megatron-LM 1.1 研究背景 单一的DP、TP、PP方法无法满足日益增长的模型参数量，因此提出一种基于多种并行方法的PTD-P并行技术。 1.2 实现方法 图. 默认的Pipeline调度（上）和插值的Pipeline调度（下） 对每个设备上运行的网络层进行进一步拆分，每个子集称为一个Chunk，在图（下）中用深色和浅色两种颜色表示 假设一共4个Device，每个Device可以分为4层（例如：在Device 1上运行1~4层，Device 2上运行5-8），则可以将每个设备的计算过程分为两个Chunk（每个Chunk需要计算两层网络）例如：Device 1对应1，2，9，10四层，Device 2对应3，4，11，12四层。 以Device 3为例，为什么运行完Chunk 2的Batch2后需要Wait，而不是直接运行Batch 3？只是为了展示插值的概念？ 1.3 实验结论 提出一种插值Pipeline调度算法，实现在3072个GPU上训练1T参数的训练，总体算力达到502PFLOPS，单个GPU的算力达到了理论峰值的52%。 相比较ZeRO-3（不带MP），因为减少了通信量，在175B和530B规模的大模型上效果要好70% 插值Pipeline调度算法可以增加计算密集度，但是对通信的开销也会增加 PP在较大的模型上效率更高，效果更好，TP的并行方式会增加不同设备之间的通信量 重算技术只是一个为了平衡内存与算力之间可选的技术，会降低内存消耗，但同时也会增加1/3的算力消耗 高度的MP可能会导致较小的矩阵乘运算，降低GPU的利用率 1.4 实验数据 本文对PTD-P模型中，GPU数量、全局Batch Size、Microbatch Size、Bubble Time、Throughput等多个参量进行多角度多变量讨论 ...

参考文献： Huang Y, Cheng Y, Chen D, et al. GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism: 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), \[C\], Vancouver, Canada, 2018. Harlap A, Narayanan D, Phanishayee A, et al. PipeDream: Fast and Efficient Pipeline Parallel DNN Training \[J\]. ArXiv, 2018,abs/1806.03377. Kim T, Kim H, Yu G, et al. BPipe: Memory-Balanced Pipeline Parallelism for Training Large Language Models: Proceedings of the 40th International Conference on Machine Learning ...

参考文献： Team D, Majumder R, President V, et al. DeepSpeed: Extreme-scale model training for everyone \[J\]. Microsoft, 2020. Rajbhandari S, Rasley J, Ruwase O, et al. ZeRO: Memory optimizations Toward Training Trillion Parameter Models \[C\], 2020. IEEE, 2020-01-01. Ren J, Rajbhandari S, Aminabadi R Y, et al. ZeRO-Offload: Democratizing Billion-Scale Model Training \[J\]. arXiv.org, 2021. Rajbhandari S, Ruwase O, Rasley J, et al. ZeRO-Infinity: Breaking the GPU MemoryWall for Extreme Scale Deep Learning: SC’ 21, November 14–19, 2021, St. Louis, MO, USA ...