北大河图发布分布式训练神器Galvatron，一键实现大模型高效自动并行化Model是最典型的大模型之一，成为当前FoundationModel的核心架构。比如NLP领域的BERT和GPT系列，CV领域的ViT和SwinTransformer系列，以及最近非常流行的多专家混合模型MoE和多模态模型CLIP等，都是以Transformer为核心基础设施.相应地，这类密集的大模型拥有数十亿、数百亿甚至数万亿个参数，面临着高昂的计算、存储和通信开销，这也给AI基础设施带来了巨大的挑战。为了支持大模型的训练，人们开发了很多工具（如NVIDIA提出的“Megatron”、微软提出的DeepSpeed、Meta提出的FairSeq等）来实现各种并行方法、数据并行、张力体模型并行、流水线并行、分片数据并行等，这些系统对上述并行方式进行了很好的封装，对外屏蔽了相应的实现细节，用户可以通过添加配置实现混合并行策略。基于以上思路，关于如何在张量或算子层面表达各种并行方法，已经有很多工作。这类工作的“自动化”主要体现在从并行API到执行层的转换过程。但如果仅限于设计并行API或中间表达式，这种工程封装并不能从根本上解决分布式训练的问题。最直观的结果就是用户仍然无法摆脱分布式部署的问题。事实上，大模型的分布式部署是一个非常复杂的问题。目前的分布式训练系统大多依赖于用户手动反复尝试和系统专家的经验部署，资源利用效率严重低下，与真正的“自动并行”有相当大的差距。基于此，北大河图团队提出了分布式训练神器Galvatron，实现大型模型的高效自动并行化。研究论文入选顶级国际会议VLDB2023。论文地址：https://arxiv.org/abs/2211.13878项目代码链接：https://github.com/PKU-DAIR/Hetu/tree/main/tools/Galvatron大模型自动并行，难点在哪里？研究人员认为，大模型自动并行化的难点主要体现在以下三个方面：（1）多样性：首先，在并行方法方面，目前大模型的并行方法呈现出百花齐放的趋势，即使对于相同的operator,different考虑混合并行，不同的基本并行也会有显着差异，导致内存开销、通信成本、计算效率不同。下图展示了四种最重要的基本并行方式，分别是DataParallelism、TensorParallelism、PipelineParallelism和SharedDataParallelism。在GPU上分布式执行简单矩阵乘法运算符的过程。并行方法对比示意图其次，在模型方面，最近出现了各种模型架构，往往伴随着不同的模型配置（如不同的输入序列长度、模型层数、模型隐藏层宽度等）。),从而导致计算量的差异。此外，在硬件方面，用户往往面临差异化很大的集群环境，可能面临不同的内存容量、通信带宽、计算能力等。总的来说，由于上述多样性，没有一种并行技术总能达到最好的训练效率，“自动并行”成为分布式训练的核心挑战。(2)复杂性：以上分析比较简单。事实上，即使是同一个算子，也可以同时应用多种不同的基本并行方法。如果考虑由这些基本并行方法组成的混合并行方法，会使问题变得非常复杂。更重要的是，大型模型的计算图往往具有非常庞大的结构，相应地需要更大规模的集群。如果对每个算子都进行探索（包括在集群中选择合适的计算资源，设计相应的混合并行方法），会导致组合空间爆炸的问题，很难找到整个模型的最优分布式执行方案。(3)实用性：另外，实用性也是一个很重要的问题。一方面，在自动并行搜索过程中，对于各种分布式执行方案，需要提供更准确的内存、通信、计算开销，否则结果会与实际执行偏差过大，导致次优解或者根本无法解决它们。使用。为此，需要一个非常准确的成本模型来模拟不同的模型结构和硬件条件。另一方面，系统自动并行能力带来的额外时间开销必须在可以接受的范围内，过高的搜索成本也是不能接受的。分布式训练神器Galvatron，一键实现大规模模型高效自动并行系统特点：为了解决上述问题，研究人员提出了一些探索混合并行自动搜索的系列工作：一类工作主要讨论同时考虑数据并行和模型并行搜索空间，代表作有FlexFlow、Tofu，另一类工作是在流水线并行场景生成，结合数据并行，代表作有PipeDream、DAPPLE。在此基础上还有一些衍生作品，如Unity、Alpa等，进一步拓展了自动并行探索的范围。北大河图团队提出的系统“惊破天”也属于自动并行搜索的研究领域，但与现有工作相比，该系统具有以下三个优势：（1）在多样性方面，现有工作的并行维度能够支持的还是比较有限的，惊破天不仅可以支持更多的并行维度，还可以对差异化程度更高的Transformer模型结构进行精准建模，验证了其在不同集群硬件条件下的自适应调优。优秀的能力。大规模分布式训练系统对比示意图(2)在复杂度上，惊破天由于其多样性优势，面临着空前庞大的搜索空间。为此，研究人员探索了目前的几种大规模分布式训练方法。过程中一些经过实验或理论验证的重要观察结果被用作搜索空间的剪枝标准，以实现高效的分布式执行计划优化。(3)在实用性方面，本研究结合了理论建模和实验测量的优势，实现了对内存、通信和计算开销的准确估计，甚至考虑了重叠计算和通信导致的GPU执行效率降低的问题，从而保证能够得到足够准确的自动并行优化结果。另外，惊破天在底层选择了PyTorch作为执行引擎，兼容Huggingface等常见的主流Transformer模型实现，不会给PyTorch用户带来额外的使用负担；同时，不需要用户支付额外的系统安装或调试费用。只需添加几行代码，即可轻松完成自动并行化的整个过程。Galvatron工作流程及用户界面展示关键技术1.基于决策树的搜索空间分解Galvatron的设计目标是在复杂庞大的并行策略空间中高效自动搜索，并提供给定的Transformer模型和分布式环境生成一个最佳并行执行计划。在搜索空间方面，Galvatron是业界首个考虑四种主流并行方式的自动并行训练系统，包括数据并行（dataparallelism，DP）、分片数据并行（shardeddataparallelism，SDP）、张量并行（tensorparallelism，TP）)和管道并行性(PP)。由于混合并行策略包括以上四种并行算法的任意组合，这种组合带来的搜索空间在多GPU场景下非常大。比如双机四卡场景，一个可行的策略是机器内使用2路TP，机器间使用2路PP。另一种可行的策略是在机器中使用2-wayPP，在机器之间使用2-wayPP。使用2路DP。当一个节点的GPU数量扩展到8张卡时，模型的每一层都有数百个候选策略。随着模型层数的增加，其搜索空间规模呈指数级增长，难以有效探索。为了有效地搜索如此大的搜索空间，该研究首先提出以下观察结果作为指导：要点#1：PP倾向于跨设备孤岛放置。这里的“设备孤岛”指的是一组内部带宽很高的设备，在大多数Transformer模型中，PP的流量明显小于其他并行方式。因此，人们通常更喜欢在PP中拆分模型并将其放置在设备岛之间。Takeway#2：在设备同构的前提下，并行策略倾向于平分设备。例如，4卡GPU的2路DP倾向于将设备分成两组2卡设备，而不是一组1卡和一组3卡设备。在这种情况下，一个设备组内的最优混合并行策略与其他设备组内的最优策略是一致的。Takeway#3：一般来说，当您可以混合使用DP和SDP时，理论上仅使用SDP性能更好。根据分析结果，N-waySDP的通信开销和内存开销要优于和的组合，其中。基于以上重要观察，本研究提出了一种基于决策树的搜索空间构建方法：（1）给定一个Transformer模型，基于Takeway#1和Takeway#2，Galvatron首先使用PP将模型划分为多个阶段，同时，将设备均匀连续地分成多个设备组。比如8卡场景，模型分为1/2/4/8路PP，对应设备组大小为8/4/2/1。(2)每个PP分裂对应一棵决策树和一个子搜索空间。决策树叶子节点的总数是设备组的大小，决策树的高度是可用并行方法的数量。也就是说，决策树的每一层都可以应用并行策略。(3)并行策略不能在决策树的不同层之间复用。(4)非叶节点的度数默认取自2的指数幂{2,4,8,…}。基于上述决策树构建规则，惊破天构建的决策树可以表示上述平行线的任意组合。Takeway#1和Takeway#2帮助惊破天避免低效的并行组合并缩小搜索空间。对于在8卡GPU上训练一层模型的场景，上述规则会产生34种候选混合并行策略。更进一步，使用Takeway#3对决策树中DP和SDP同时出现的情况进行剪枝后，8张候选策略的数量减少为22个。下图为决策树下的示意图8卡GPU场景下不同的PP并行度（8/4/2/1）。8卡GPU场景下不同PP并行度（8/4/2/1）下的决策树示意图二、基于动态规划的并行优化算法现有系统如Megatron或DeepSpeed通常指定全局并行方案及其相应的用户并行度这严重限制了表达分布式执行计划的能力。Galvatron的优化目标是在给定模型定义和分布式环境的情况下，在不指定任何并行配置的情况下，自动生成最优的分布式执行计划。具体地，给定一个L层模型M和N个GPU设备，内存容量为E，Galvatron的优化目标是搜索最高的系统吞吐量T_pt并返回对应的并行解，其中并行解是指层（或算子）)作为细粒度混合并行策略的基本单元。算法1：惊破天优化过程优化过程：惊破天的优化过程如算法1所示。Galvatron的最外层循环逐渐增加搜索的批量大小，直到超过设备内存；给定每个候选batchsizeB，Galvatron首先根据Takeaway#1对模型进行PP分割，搜索不同的并行度P（第4行），选择P-wayPP后，将模型分为P个stages（第6行）),对应的所有设备分为P组，每组包含N/P个设备；然后Galvatron构建相应的决策树，可以表示DP、SDP、TP的任意组合，不重复，从而得到策略集S；然后对于每个模型阶段M_i，在设备内存限制E下，Galvatron使用动态规划搜索获得每一层的最优混合并行策略并返回最小时间开销（第9行）；最后，Galvatron在所有可能的PP并行度和批量大小中选择吞吐率最高的策略并返回（第15行）。动态规划搜索：Galvatron并行优化工作流程中的动态规划搜索算法如下所述。对于给定的包含L层的模型阶段，用代价函数C(L,E)表示设备内存限制E下L层模型的总执行时间，用策略S_j，其中策略S_j为并行策略候选集S中的一个策略。设置初始值，惊破天的动态规划搜索遵循如下状态转移方程（式1）：其中，为策略的内存开销L层使用的S_j，是L层使用的策略S_j，和上一层转换开销使用的策略S_i。在状态转换期间，当内存开销超过设备内存限制E时，开销函数C返回无穷大。复杂度分析：Galvatron使用的动态规划搜索（公式1）的计算复杂度为O(LE|S|)。可以看出，每层搜索空间S的大小对整体搜索复杂度非常重要。Galvatron提出的基于决策树的搜索空间分解可以显着缩小搜索空间，将搜索开销控制在合理范围内。3.基于混合建模的执行成本估算方法惊破天使用策略成本估算模块来估算混合并行策略的计算、通信和内存成本。现有的开销估计方法主要包括剖析和模拟。Galvatron吸收了两者的长处，设计了一种具有成本效益、高效且准确的开销估算方法。具体来说，对于内存开销，惊破天使用张量的形状和数据类型来完成估计；对于计算时间，Galvatron通过在单个设备上进行profiling来衡量每个样本的计算时间，结合batchsize和fittingfunction来估算整体的计算时间；对于通信时间，惊破天通过通信量除以设备通信带宽得到预估通信时间，其中通信量通过理论计算得到，通信带宽通过剖析测量得到。基于以上估算结果，Galvatron通过模拟执行过程，使用给定策略计算给定层的成本c(l,s)。不同于现有分布式训练系统的成本模型，惊破天在建模中首次考虑了计算和通信重叠对GPU性能下降的影响。研究通过实验发现，重叠导致的GPU性能下降会显着影响系统的执行效率，这在以往的工作中被忽视了。因此，Galvatron具有更准确的开销估计和更好的并行优化。实验结果实验设置：在实验中，研究人员将Galvatron与四个基线系统（DP、SDP、TP、PP）使用单一并行策略和专家设置的DeepSpeed3DParallelism进行了比较，同时额外设置了两个弱化版本Galvatron作为辅助基线在有限的并行策略组合空间（即TP+DP、PP+DP）中进行自动并行搜索。本研究选取NLPTransformer模型BERT和T5、CVTransformer模型ViT和SwinTransformer作为实验对象。惊破天与基准系统在8个GPU20G显存吞吐量对比实验对比效果：本研究首先在八卡NvidiaRTXTITAN24GB环境下进行实验。实验表明，在不同的模型大小和不同的内存约束下，Galvatron总是能达到最优的吞吐率，并且与现有的最先进的单并行方法和混合并行方法相比，训练吞吐量有显着提高。.具体来说，在ViT模型上，Galvatron相比单一策略吞吐量提速高达338%，相比其他混合并行策略吞吐量提速高达55%；在其他三个模型的性能方面，Galvatron相比单一策略和现有的混合策略可以实现高达200%-334%和28%-52%的加速。SchematicdiagramofSchematicofsomeoptimalparallelstrategiesgetsofGalvatronsearch可解释性实验：本研究选择惊破天搜索得到的一些最优并行策略进行展示。对于8GB情况下的BERT模型（CaseA），Galvatron选择了PP-TP-DP和PP-TP-SDP两种混合并行策略，当可用显存增加到12GB时，Galvatron放弃PP，选择使用a更多的DP，同时引入SDP来节省显存空间。SwinTransformer上的情况略有不同。模型的不同层次表现出明显的异质性。当内存比较稀缺时（CaseC），浅层SDP的并行度更高。随着层数加深，每层的激活，参数变多，所以TP逐渐取代SDP。当显存增加时（CaseD），不仅重新启用PP来替代一些低效的SDP，而且浅层使用DP的倾向也更加明显。可扩展性实验：该研究在更大的集群上进一步测试了惊破天，包括具有16个NvidiaRTXTITANGPU和64个NvidiaA100GPU的环境。在16张卡的环境中，Galvatron与其他策略相比仍然具有最高的吞吐量。与相同内存限制的8卡实验结果相比，惊破天由于混合并行策略更加多样化，在16卡上可以实现2倍以上的吞吐量。加速比。在64张卡的实验中，惊破天的吞吐率也是其他策略中最高的。这表明Galvatron具有良好的可扩展性，详细的结果可以在原论文中找到。河图团队简介河图开发团队来自北京大学数据与智能研究实验室（以下简称“实验室”），由北京大学计算机学院崔斌教授领衔。多年来主要在人工智能和大数据领域开展前沿研究，在理论技术创新和系统研发方面取得多项成果。在国际顶级学术会议和期刊发表学术论文100余篇。河图系统是一个面向超大模型的分布式深度学习系统。与现有的老式分布式深度学习框架相比，它在系统功能、系统复杂度和系统易用性等方面有很多创新贡献，如自动分布式并行策略、共识协议和通信架构、GPU算子优化等。河图团队在多种分布式机器学习或深度学习场景进行了学术创新，相关成果被SIGMOD、VLDB、ICML、KDD等国际顶级会议收录。其中，稀疏大模型分布式训练systemHET荣获VLDB2022Best最佳可扩展数据科学论文奖。此次被VLDB2023录用的论文Galvatron是河图团队在密集大模型分布式训练场景的又一突破性成果。已经集成到河图系统并开源。目前，河图团队已与腾讯、阿里巴巴、快手、字节跳动等多家知名企业展开科研合作与应用落地。
