Understanding Stragglers in Large Model Training Using What-if Analysis

Jinkun Lin1, Ziheng Jiang2, Zuquan Song2, Sida Zhao2, Menghan Yu2, Zhanghan Wang1, Chenyuan Wang2, Zuocheng Shi4, Xiang Shi3, Wei Jia2, Zherui Liu2, Shuguang Wang2, Haibin Lin2,†, Xin Liu2, Aurojit Panda1, Jinyang Li1,†

1New York University, 2ByteDance Seed, 3ByteDance, 4Zhejiang University

†Corresponding authors

主要贡献

本文针对大型语言模型（LLM）训练中的落后者（straggler）问题进行全面研究，使用从字节跳动LLM训练集群收集的五个月跟踪数据。核心问题是：落后者在实际大规模LLM训练部署中是否构成严重的性能问题？研究目标包括：（1）评估落后者对训练作业的影响频率及其对作业性能的影响；（2）分析落后者是否表现出时间或空间模式；（3）探讨落后者的潜在根本原因。创新点在于采用“假设分析”（what-if analysis）方法，通过模拟无落后者的场景与实际场景对比，量化落后者的影响。该方法基于作业操作的依赖模型，使用非落后执行时间进行模拟。分析揭示落后者普遍存在，导致42.5%的作业至少慢10%，尾部作业浪费45%的分配资源；大多数步骤在落后作业中表现出相似的减速，表明问题持久而非瞬时；计算操作而非通信操作更常导致落后者；作业大小与落后相关减速无正相关。进一步结合模拟和手动检查，识别出管道阶段分区不均衡、序列长度不均衡和垃圾回收暂停作为主要根本原因，而硬件或软件问题并非主要原因。基于此，开发了监控系统SMon，用于实时检测和调试落后者。

背景知识

混合并行训练和落后者。 几种策略已被开发用于并行化LLM训练，以克服内存限制并减少训练时间。每种并行策略都容易受到落后者的影响。下面介绍我们集群中使用的策略及其落后者来源。我们将术语“工作者”定义为单个GPU及其控制进程（运行在CPU上）。

数据并行（DP）、ZeRO【31，Samyam Rajbhandari et al. Zero: Memory optimizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, 2020】和全分片数据并行（FSDP【43，Yanli Zhao et al. Pytorch fsdp: Experiences on scaling fully sharded data parallel. Proc. VLDB Endow., 2023】）。DP将训练数据分区到多个工作者，每个工作者拥有整个模型的副本。在每个训练步骤中，一个工作者被分配一个训练批次。工作者为其分配的批次运行前向和后向计算，然后所有工作者在进入下一个训练步骤前执行梯度全归约步骤。梯度全归约步骤需要工作者之间同步，慢工作者会导致所有工作者停滞，导致落后者。ZeRO和FSDP通过将优化器状态、参数和/或梯度分区到工作者来扩展DP，以减少每个GPU的内存需求。两者不是使用梯度全归约步骤，而是需要计算梯度的reduce-scatter步骤、设备本地参数更新步骤，以及为每个训练步骤收集参数的全聚集步骤。reduce-scatter和全聚集步骤需要跨工作者同步，因此同样容易受到落后者影响。

管道并行（PP）。PP将模型分区到多个工作者，每个工作者持有连续模型层的不相交集合，称为管道阶段。PP减少模型权重和激活的每个GPU内存需求。在训练期间，一个数据批次被分割成几个微批次，训练通过PP阶段流水线化。已提出几种微批次调度方法，包括GPipe【18，Yanping Huang et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems, 2019】、1F1B【12，Shiqing Fan et al. Dapple: A pipelined data parallel approach for training large models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2021】和虚拟管道并行（VPP【28，Deepak Narayanan et al. Efficient large-scale language model training on gpu clusters using megatron-lm. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2021】）。所有这些调度方法假设计算均匀分区到管道阶段，并旨在最小化管道气泡，即管道阶段等待前一阶段数据而空闲的时间。如果PP阶段未均匀分区，最慢阶段会使其他阶段停滞，成为性能瓶颈。因此，PP容易因PP阶段之间计算分区不均匀而导致落后者。为便于说明，我们不明确讨论VPP，但我们的分析确实考虑了它。

张量并行（TP）和上下文并行（CP）。除了PP，还可以使用张量（TP【22，Vijay Anand Korthikanti et al. Reducing activation recomputation in large transformer models. Proceedings of Machine Learning and Systems, 2023】【28，Deepak Narayanan et al. Efficient large-scale language model training on gpu clusters using megatron-lm. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2021】）和上下文（CP【11，Abhimanyu Dubey et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024】【25，Hao Liu et al. Ring attention with blockwise transformers for near-infinite context, 2023】【34，NVIDIA Team. Context paralellism. https://docs.nvidia.com/megatron-core/developer-guide/latest/api-guide/context_parallel.html】）并行来进一步减少每个GPU的内存需求。TP将每个层的权重分区到工作者，CP将每个序列的标记分区到工作者。两者都需要在每个Transformer层后进行同步步骤，以便聚合TP或CP组中所有工作者的部分结果。由于慢设备会在同步期间使进度停滞，因此TP和CP都容易受到落后者影响。正如我们在§7中讨论的，我们不分析TP和CP组中的系统性落后者。

混合并行。在实践中，LLM训练使用混合策略，结合上述所有并行策略，提供比任何单个策略更好的性能。当使用混合并行时，工作者可以组织成超立方体，其中每个维度对应一个并行策略。一个工作者的坐标提供其在每个并行维度中的排名（例如，管道阶段）。工作者也被分配唯一全局排名用于识别。图1显示了一个DP-PP-TP并行训练的工作者拓扑示例。

混合并行训练以分层方式操作。例如，当使用DP-PP-TP并行时，具有相同DP排名的工作者被分组到一个PP组中，负责计算训练批次的梯度。在每个PP组内，具有相同PP排名的工作者被分组到一个TP组中，每个TP组负责单个PP阶段。最后，相同TP组内的工作者使用TP并行计算PP阶段中的每个层。

混合并行的落后者情况。混合并行受到其结合的任何并行策略中出现的落后者的影响。例如，在DP-PP-TP并行策略中，慢TP工作者会减慢其所属的PP排名，导致PP气泡。这个PP气泡反过来会减慢工作者所属的整个DP排名，延迟梯度同步并使其他DP排名停滞。

目标和挑战。 落后者定义。使用混合并行的LLM训练作业是无落后者的，如果所有工作者完成其分配工作的时间相同。这最小化同步所需时间，导致理想的无落后者场景，实现最佳性能。我们还注意到，根据这个相当宽泛的落后定义，任何原因导致工作者落后于其他工作者的情况都被视为落后者。这些原因不仅包括确定性影响单个工作者的硬件问题，还包括均匀影响所有工作者的不可预测停滞（例如，阻止任务进展的垃圾回收【21，Ziheng Jiang et al. MegaScale: Scaling large language model training to more than 10,000 GPUs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024】【37，The Imbue Team. From bare metal to a 70b model: infrastructure set-up and scripts. https://imbue.com/research/70b-infrastructure/, 2024】），以及由于数据偏差【30，Kay Ousterhout et al. Making sense of performance in data analytics frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), 2015】【42，Zili Zhang et al. DistTrain: Addressing model and data heterogeneity with disaggregated training for multimodal large language models, 2024】或权重分区不良（例如，PP阶段）【11，Abhimanyu Dubey et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024】导致的工作负载不均衡。

我们的目标。在本文中，我们希望调查落后者如何影响实际LLM训练作业，并揭示一些潜在根本原因。为此，我们试图量化实际LLM训练作业的速度与其理想无落后者情况的差异。根据我们先前的定义，落后工作者是完成工作比其他工作者慢的那个。因此，在存在落后者的情况下，作业由于需要跨工作者组同步而延迟，导致比理想无落后者场景更慢的速度。

我们的研究基于分析从LLM训练作业收集的五个月跟踪数据。尽管这些跟踪捕捉了每个作业的实际执行时间，但估计相应的无落后者完成时间仍然具有挑战性。这是因为在存在重叠执行的情况下，评估落后操作对整体作业持续时间的影响很棘手。传统的关键路径分析【5，Anupam Bhatnagar et al. Holistic trace analysis. https://hta.readthedocs.io/en/latest/index.html, 2023】在这种上下文中不足，因为高度并行且同质的工作负载如LLM训练可能表现出许多类似的关键路径。专注于单一路径可能导致误导性结论，如Coz【8，Charlie Curtsinger and Emery D Berger. Coz: Finding code that counts with causal profiling. In Proceedings of the 25th Symposium on Operating Systems Principles, 2015】所示。为解决此问题，我们使用基于跟踪的模拟来“执行”每个作业在备用时间线上，其中落后操作与同行一致。

方法细节

本节中，我们描述用于我们研究的数据跟踪以及分析它们的方法。

集群设置。 收集跟踪的集群专用于训练，并由多个团队内部共享。集群中使用的机器具有类似于NVIDIA的DGX服务器的硬件配置：每个服务器配备八个GPU，通过NVLink或PCIe链接互连，四或八个NIC，具有数百Gbps带宽，一个用于存储和管理的单独NIC，几百个CPU核心和几TB内存。服务器通过高性能交换机互连，配置为三层CLOS拓扑。网络被过度配置并仔细调优【21，Ziheng Jiang et al. MegaScale: Scaling large language model training to more than 10,000 GPUs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024】，以确保没有由于网络拥塞导致的减速。

多个作业可以同时调度在集群上运行，每个作业在其持续时间内独占其分配的GPU。调度器确保每个作业使用同质硬件，通过分配相同类型的GPU。此外，调度器以尽力方式执行GPU分配，以确保作业的GPU在网络拓扑中靠近。由于大作业请求的GPU是8的倍数，不同大作业不共享同一服务器机器。结合缺乏网络拥塞，这意味着尽管作业在同一集群上运行，我们没有看到由于资源争用导致的落后者。

跟踪收集。 我们研究中使用的跟踪是从2024/01/01到2024/05/31期间提交的LLM预训练作业收集的。由于我们的研究专注于大作业，我们仅使用至少使用128个GPU的作业的跟踪。我们还丢弃无效或不适合分析的跟踪，如§7所述。这产生了3079个作业用于我们的分析。这些作业包含密集和专家混合（MoE）模型，配置为使用短或长上下文序列训练。在3079个作业中，31.7%使用≥256个GPU，18.3%使用≥512个GPU，3.6%使用≥5000个GPU。总计，分析的作业覆盖所有LLM训练作业中约一半的GPU小时。

我们跟踪中的所有作业使用开源分布式LLM训练系统Megatron-LM【27，mega. Megatron-lm. https://github.com/NVIDIA/Megatron-LM, 2020】的自定义版本【21，Ziheng Jiang et al. MegaScale: Scaling large language model training to more than 10,000 GPUs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024】完成。作业配置为使用Megatron-LM支持的不同并行策略组合，包括DP、PP、TP和CP。

基于Megatron-LM的训练系统已使用我们的内部剖析工具NDTimeline【19，ByteDance Inc. Ndtimeline vescale. https://github.com/volcengine/veScale/ters.blob/main/vescale/ndtimeline/README.md】进行仪器化。默认情况下，它采样作业10%的训练步骤（又称迭代）进行剖析。对于每个剖析步骤，该工具记录被视为重要的操作集的开始和结束时间，包括执行前向和后向计算的操作以及执行通信的操作。表1给出了所有剖析的操作类型及其描述。一个剖析的前向或后向计算操作由许多GPU内核组成，以减少跟踪许多小计算内核的成本。NDTimeline定期同步作业所有机器的时钟，从而允许我们为假设分析（§3.2）的目的对齐不同机器的相关操作。

对于跟踪中的每个操作，其日志条目包含操作类型、其开始和结束时间戳以及一组元数据，包括训练步骤ID、微批次ID、PP排名（在每个PP组内）和DP排名（在整体DP组内）。这些元数据使我们能够重建操作依赖关系，这对于模拟如果没有落后者存在的备用时间线是必要的（§3.2）。

假设分析的模拟器。 假设分析的目标是通过回答以下问题来评估落后者的影响：1. 如果所有落后者不存在，作业将需要多长时间？2. 如果除特定落后者组外的所有落后者不存在，作业将需要多长时间？

为回答这些问题，我们模拟无落后者的备用时间线。主要洞察是，在没有落后者的情况下，可比操作将具有相同的持续时间。基于此洞察，我们首先尝试估计每个操作在备用无落后者场景中的持续时间。然后，我们模拟备用时间线，其中操作根据其依赖关系启动，并在估计的理想化持续时间内完成。通过比较模拟的作业完成时间（JCT）与实际跟踪的JCT，我们可以评估落后者的影响。

估计无落后者场景的理想化操作持续时间。 概念上，我们可以将跟踪的操作组织成四维张量：训练步骤、微批次、PP排名和DP排名。我们将此张量称为OpDuration张量。我们为表1中的每个操作类型有一个这样的张量。对于计算操作，张量中的元素只是跟踪中相应操作的持续时间。对于通信，我们计算跟踪持续时间的子部分，称为传输持续时间。由于通信作为集体（或P2P对）的一部分完成，单个操作的跟踪持续时间受两个因素影响：1）将数据传输到另一个排名的持续时间，即“传输持续时间”。2）等待集体（或P2P对）中其他操作启动的持续时间，即“阻塞持续时间”。在两个因素中，“传输持续时间”对集体操作是内在的，而“阻塞持续时间”由操作调度决定。因此，我们仅将“传输持续时间”存储在通信操作类型的OpDuration中，例如params-sync、forward-send等。要估计操作的“传输持续时间”，我们取其同一集体（或同一P2P对）中所有同行操作的最大开始时间，并从中减去其结束时间。

所有相同类型的操作处理相同的工作负载，这意味着在没有落后者的情况下，理想化OpDuration张量中的所有元素将是相等的。为了评估特定落后者组的影响——例如特定于具有PP排名p和DP排名d的机器的那些——我们选择性地“修复”所有其他机器上的落后，通过用理想值覆盖那些机器上操作的持续时间。对于属于落后机器的元素（即OpDuration[:,:,p,d]），我们保持其原始持续时间。我们采用类似方法（在§5中）来估计仅修复某些落后元素的效应：我们仅对需要修复的元素使用理想化操作时间，并保持其他不变。

一旦我们确定OpDuration张量中哪些部分在假设的无落后者设置中应具有相同的理想值，问题仍然是该值应是什么。我们对计算和通信操作使用不同的方法。对于计算操作，我们使用要均衡的元素组的平均值。对于通信操作，我们使用中位数而不是平均值。最初，我们对两种操作类型都使用平均值，但在一些手动根本原因调查后改变了解决方案。特别是，我们观察到计算落后主要由于工作负载分区不均衡引起。因此，取平均值有意义，因为这样做相当于工作负载重新平衡。另一方面，通信操作在不同训练步骤、微批次、PP排名和DP排名中具有相同的传输量，但由于外部问题如交换机/NIC抖动而落后。而且，受影响的操作往往很长，这显著扭曲平均值，使中位数成为更好的选择。

提取操作依赖关系。 我们的模拟器需要两个输入：理想化操作持续时间和操作依赖模型。我们先前讨论了如何估计理想化操作持续时间。接下来，我们将解释模拟器的依赖模型，该模型源自使用的基于Megatron-LM的训练系统。

在该依赖模型中，每个工作者运行几个“流”来执行其操作。调度到单个流的所有操作按顺序执行，而跨流的操作系统只要其依赖满足就可以并发。更具体地说，每个工作者有一个流执行所有前向和后向计算操作，一个流执行所有DP特定通信操作，以及四个流每个执行不同类型的PP特定通信操作：forward-recv (RF)、backward-recv (RB)、forward-send (SF)和backward-send (SB)，如图2所示。操作之间的依赖如下：

• 同一流依赖：流内的操作根据其在跟踪中的启动时间排序。我们假设相邻操作之间有隐式依赖，因为同一流上的操作按顺序执行。

• DP通信和计算依赖：每个PP阶段的第一个微批次的前向计算操作应在相应params-sync集体通信获取该阶段参数后发生，如图2所示 (Syncparams → CF,mid=1)。参数本地缓存并用于后续微批次。不同微批次的梯度本地累积，然后跨DP排名聚合。因此，最后一个微批次的后向计算应在grads-sync集体通信聚合该PP阶段跨DP排名的梯度前发生，如图2所示 (CB,mid=8 → Syncgrads)。

• PP通信和计算依赖：除第一个PP排名外，PP排名p上微批次的前向和后向计算操作必须在同一GPU上该微批次的前向和后向接收通信操作完成后开始，如图2所示（例如 RF,mid=1 → CF,mid=1, RB,mid=7 → CB,mid=7）。类似地，除最后一个PP排名外，PP排名p上微批次的前向和后向发送操作必须在同一GPU上该微批次的前向和后向计算操作完成后开始，如图2所示（例如 CF,mid=1 → SF,mid=1, CB,mid=7 → SB,mid=7）。

跨排名通信依赖。 对于给定微批次的DP通信操作（即params-sync、grads-sync）在具有相同PP排名的所有DP排名间形成集体组。类似地，对于给定微批次的PP发送和接收操作在具有相同DP排名的相邻PP排名间形成一对。集体（或P2P）操作组的依赖模型是，没有单个操作可以启动其数据传输，直到所有操作已启动。

模拟备用时间线。 使用依赖模型和理想化持续时间，我们可以使用以下规则模拟备用执行时间线：

• 模拟器在其所有依赖操作完成后立即启动一个操作。换言之，操作的开始时间计算为其依赖操作的最大结束时间。

• 启动后的计算操作立即标记为完成，其结束时间计算为开始时间加上OpDuration中相应操作持续时间。

• 对于每个通信操作，模拟器等待同一集体组（或P2P对）中的所有同行操作启动。操作的结束时间计算为组中最大启动时间加上OpDuration中存储的相应传输持续时间。

落后相关减速和GPU浪费的指标。 现在我们设计了一个模拟器来估计作业在备用无落后者时间线中的完成时间，我们应该计算什么指标来量化落后者的影响？让我们用T_ideal表示无落后者的JCT。类似于【30，Kay Ousterhout et al. Making sense of performance in data analytics frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), 2015】，为了考虑模拟引入的错误，我们还使用未修改的操作持续时间模拟原始时间线，并将结果JCT表示为T。模拟错误相对小，并在§6中报告。而且，我们的一些跟踪有大模拟错误，为了确保分析保真度，我们丢弃模拟错误≥5%的跟踪（§6）。为了量化落后相关性能减速，我们计算减速指标S作为比率：

$S = \frac{T}{T_{ideal}}$

除了整体落后相关减速，我们还希望量化由于不同类型操作（表1）中的落后导致的减速。为此，我们首先为每个操作类型t计算操作类型减速S_t作为

$S_t = \frac{T_{-t}^{ideal}}{T_{ideal}}$

其中T_ideal如上所述计算的理想JCT，T_{-t}^{ideal}是当OpDuration中操作类型t的元素未修复时的JCT。

在我们的集群中，作业在其整个持续时间内独占访问GPU。因此，作业完成时间的增加（或减速）可以直接转化为作业浪费的GPU小时量。具体地，我们使用方程估计作业的资源浪费作为浪费的GPU小时百分比：

$W = 1 - \frac{1}{S}$

类似地，我们可以通过计算1 - 1/S_t来计算由于不同操作类型浪费的资源。

实验环境

数据集：使用字节跳动LLM训练集群中从2024年1月至5月收集的五个月跟踪数据，覆盖3079个至少使用128个GPU的LLM预训练作业。这些作业包括密集模型和专家混合（MoE）模型，训练短或长上下文序列。数据集总计覆盖约一半的总GPU小时。长上下文作业使用最大序列长度如32K的数据集，具有长尾序列长度分布（图10）。

模型架构：模型为大型语言模型，使用混合并行策略，包括数据并行（DP）、管道并行（PP）、张量并行（TP）和上下文并行（CP）。作业配置不同并行度，例如DP-PP-TP组合。模型大小从数百亿参数到更大，部分使用虚拟管道并行（VPP）。关键参数包括管道阶段数（如4阶段，每个阶段9个Transformer层，最后阶段额外损失层）、微批次数、序列长度（最大32K）。

硬件配置：集群服务器类似于NVIDIA DGX，每个配备8个GPU（通过NVLink或PCIe互连）、4或8个数百Gbps NIC、1个用于存储/管理的单独NIC、数百CPU核心和几TB内存。服务器通过三层CLOS拓扑高性能交换机互连，网络过度配置以避免拥塞。作业独占分配的GPU，调度确保同质硬件和网络拓扑亲和性。作业规模从128 GPU到>5000 GPU。

软件配置：基于自定义Megatron-LM【27，mega. Megatron-lm. https://github.com/NVIDIA/Megatron-LM, 2020】的训练系统，使用PyTorch。剖析使用NDTimeline【19，ByteDance Inc. Ndtimeline vescale. https://github.com/volcengine/veScale/ters.blob/main/vescale/ndtimeline/README.md】，采样10%训练步骤。操作系统未指定，但包括Python运行时（带有垃圾回收）。依赖库包括Megatron-LM支持的并行策略。

实验结果

落后者的影响分析。 实验内容：对3079个作业跟踪进行假设分析，模拟无落后者场景，计算减速S和资源浪费W。结果：落后者普遍存在，42.5%作业至少慢10%，>10%作业浪费至少21.3% GPU小时，~1%作业浪费至少45%（图3）。总体，10.4%分配GPU小时因落后浪费。分析结论：落后者导致显著资源浪费，尾部影响严重。

步骤减速模式。 实验内容：针对减速S>1.1的落后作业，计算每个步骤的减速比率，并归一化为作业整体减速。结果：中位步骤归一化减速为1.0，90th百分位为1.06（图4）。分析结论：大多数步骤在落后作业中减速相似，表明落后由持久问题引起，而非瞬时因素，采样少数步骤即可剖析。

操作类型对落后者的贡献。 实验内容：计算每个操作类型（表1）的减速S_t和资源浪费。结果：计算操作导致最多浪费，通信影响最小；PP级通信略高于DP级（图5）。分析结论：与FALCON【40，Tianyuan Wu et al. FALCON: Pinpointing and mitigating stragglers for large-scale hybrid-parallel training. arXiv preprint arXiv:2410.12588, 2024】相反，计算而非通信主导落后，归因于充足网络带宽和优化【21，Ziheng Jiang et al. MegaScale: Scaling large language model training to more than 10,000 GPUs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024】。

作业大小与落后相关性。 实验内容：分析减速与作业GPU数相关性。结果：无明显正相关。分析结论：作业大小非决定因素，其他因素如模型类型或人为因素更重要；大作业常被优化，长上下文小作业更易落后。

根本原因分析：单个工作者问题。 实验内容：针对S≥1.1的作业，计算每个工作者减速S_w，选择前3%慢工作者，计算其对整体减速的贡献M_w（使用DP/PP排名近似）。结果：仅1.7%作业中，工作者问题贡献>50%减速（图6）；这些作业平均减速3.04 vs 整体1.28。分析结论：工作者硬件/软件问题非多数落后主导原因。

根本原因分析：阶段分区不均衡。 实验内容：针对使用PP的作业，模拟仅修复最后管道阶段的操作，计算其贡献M_s。结果：39.3%作业中，最后阶段贡献≥50%减速（图7）。手动调优实验显示9.9%加速，但最后阶段前向计算仍1.55X其他阶段。分析结论：损失层计算密集导致不均衡；手动调优ϵ层数缓解，但受层分配限制和词汇大小影响。

根本原因分析：序列长度不均衡。 实验内容：针对长上下文作业，计算前向-后向计算相关系数（阈值0.9）；分析序列长度分布和计算时间（O(∑ s_i^2)）。结果：21.4%作业受影响，平均减速1.34（图11）；最大序列长度增加时影响更大（图12）；原型再分配算法改善23.9%吞吐。分析结论：长尾分布导致微批次计算不均，产生气泡；再分配缓解DP级不均衡，但PP级需进一步方法（图8、9、10）。

根本原因分析：垃圾回收。 实验内容：检查Python GC暂停对计算的影响。结果：不同工作者异步GC导致停滞（图13）；计划GC优化（手动间隔）改善12.6%；但调优间隔困难，未默认启用。分析结论：GC暂停随作业进展增加，可能因内存泄漏；计划GC掩盖泄漏，维持吞吐。

根本原因分析：其他。 实验内容：手动检查不常见原因。结果：CUDA内存碎片导致分配器慢；虚假内核依赖（MoE模型）通过增加CUDA_DEVICE_MAX_CONNECTIONS缓解。分析结论：这些问题不常见，但有趣，需进一步研究。

模拟保真度验证。 实验内容：比较模拟与实际步骤时间；人工注入落后并比较减速。结果：中位模拟偏差1.3%，90th 5.5%；注入减速实际1.16/1.40/2.03 vs 模拟1.21/1.42/1.98。分析结论：模拟准确，丢弃>5%偏差跟踪。

在线检测系统SMon。 实验内容：部署SMon监控，生成热图显示工作者减速。结果：部署一个月内识别并修复多个落后案例（图14）。分析结论：热图模式帮助诊断根本原因，提高效率。

结论

本文通过假设分析对LLM训练中的落后者问题进行深入研究，揭示落后者普遍导致显著性能损失和资源浪费，主要由持久问题引起，如计算操作主导而非通信。根本原因包括管道阶段分区不均衡、序列长度不均衡和垃圾回收暂停，而机器问题罕见但严重。观察到无作业大小与落后正相关。开发SMon监控系统，提高检测和诊断效率。未来工作包括扩展分析以覆盖TP/CP落后、评估序列再分配在规模上的效果，并调查不常见原因如内存碎片。

附录

模拟保真度验证。 我们的分析使用模拟器估计无落后者的作业执行时间，以及修复某些落后者后的时间。我们通过两种方式验证模拟器的准确性：1）比较作业在模拟原始时间线中的平均步骤时间与其实际时间线中的平均步骤时间；2）人工注入落后者并比较模拟和实际减速。

模拟不准确及其来源。正如§3所述，并非所有操作类型都记录在跟踪中：具体地，运行在CPU上的操作，包括数据加载，被省略。在大多数情况下，此限制不成问题，因为这些CPU操作与GPU操作重叠，允许隐藏其延迟。然而，重叠并不总是完美，会延迟下一个操作的启动。此启动延迟未被模拟，构成模拟中主要差异来源。为了测量差异，我们计算具有n步骤的作业的模拟原始时间线平均步骤运行时间τ = T / n，并将其与实际步骤运行时间τ_act比较。在我们的实验中，模拟差异的中位数为1.3%，90百分位为5.5%。

在检查具有大模拟差异的跟踪后，我们发现了三个主要原因：（a）由于数据存储在远程存储集群中使用单独的较慢网络，数据加载容易受到网络减速和超时，导致一些训练步骤的第一个前向计算操作有长启动延迟；（b）长上下文作业在每个步骤的第一个前向计算操作启动前可能有长延迟，因为作为批次准备的一部分，样本被填充到最大序列长度，这很耗时；（c）计划GC优化的早期部署，其中GC在梯度同步前每几个训练步骤运行，导致那些操作的启动变慢。我们已解决后两个问题，但所有三个问题影响我们捕获的一些跟踪。为了确保分析保真度，我们丢弃模拟差异大于5%的任何跟踪。

验证减速估计的准确性。我们通过运行DP、PP和TP度为4、CP度为1的作业来验证减速估计的准确性。我们人工减慢第一个排名，即全局排名0的工作者，通过运行后台进程定期执行多个10K×10K矩阵乘法（MatMuls）。通过改变MatMul启动之间的时间间隔，我们创建三个减速水平并测量结果减速。我们还使用模拟器计算模拟减速。我们测量的减速分别为1.16、1.40和2.03，与估计减速1.21、1.42和1.98接近。

限制。 接下来，我们讨论我们分析的限制。我们的限制由于NDTimeline捕获的跟踪内容，我们计划在未来工作中解决这些限制。

NDTimeline捕获数据导致的限制。NDTimeline执行粗粒度剖析，并记录微批次前向和后向计算所用时间。使用此信息分析TP或CP组内的落后者具有挑战性，因为TP和CP组同步，TP或CP粒度的落后者在我们的跟踪中表现为慢微批次。因此，如果落后者减慢所有微批次，我们估计理想微批次持续时间的方法将不允许我们计算理想的无落后者执行时间，因此我们无法分析此类落后者的影响。

第二个限制是由于NDTimeline中的一个bug影响我们的一些跟踪。此bug导致NDTimeline未记录某些操作，导致错误地模拟某些前向和后向计算操作的启动更早。该bug在我们开始收集跟踪后被发现，我们对受此bug影响的跟踪进行后处理以修复此问题。

我们分析覆盖的作业。为了确保分析保真度，我们不得不丢弃我们从集群收集的部分跟踪。因此，我们的分析未覆盖集群内运行的所有LLM训练作业，并可能低估落后者的普遍性和严重性。丢弃的原因大多由于跟踪问题，我们在下面概述它们。

首先，我们消除任何反复失败的作业。我们的集群使用自动重新提交失败作业的系统。然而，软件bug导致单个作业可能失败数十次或更多，我们消除这些作业以避免引入分析偏差。特别是，我们丢弃任何重新启动超过15次的作业，这导致我们丢弃13.9%的记录作业或7.3%的记录GPU小时。

其次，我们丢弃我们无法成功运行假设分析的作业。这导致我们丢弃剩余作业的50.0%，相当于剩余GPU小时的34.1%。大多数由于跟踪问题：28%的跟踪被丢弃，因为我们无法解析作业的命令行以确定并行度；28%由于作业步骤太少无法分析；25%由于损坏的跟踪。

最后，如先前所述（§3.3），我们丢弃具有大模拟差异（>5%）的作业，这相当于剩余作业的11.2%和剩余GPU小时的7.7%。这导致总覆盖38.2%作业和56.4% GPU小时。

使用假设分析的在线落后者检测和诊断。 为了让用户更容易从我们讨论的分析中受益，我们构建了一个名为SMon的在线监控服务，它在每个NDTimeline剖析会话（记录数十个训练步骤）后自动运行。SMon估计减速、每个步骤减速和工作者的减速，并将结果呈现在网页上。类似于Pingmesh【17，Chuanxiong Guo et al. Pingmesh: A large-scale system for data center network latency measurement and analysis. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, 2015】，我们使用热图呈现工作者减速，其中每个单元格代表一个工作者，其x和y坐标分别为其DP和PP排名，颜色深度代表工作者的减速。我们使用此类热图有两个目的：首先，它使找到落后工作者更容易，其次，减速模式通常帮助定位减速的初始根本原因，使解决问题更容易。例如，具有工作者问题、阶段分区不均衡和序列长度方差的作业具有不同的模式，如图14所示。SMon还使用每个步骤持续时间而不是方程(4)中的平均值来计算工作者减速，呈现每个步骤热图，以仅反映每个步骤内的落后。

我们已配置SMon在重要作业经历显著减速时警报我们的值班团队。当警报时，值班团队检查工作者热图，通过查看是否匹配已知模式来识别可疑根本原因。然后我们使用每个步骤减速和每个步骤热图来定位问题步骤和排名，进一步深入了解问题。

在其部署一个月内，SMon帮助我们识别并解决几个落后者：它允许我们在三个机器问题导致落后者的案例中定位故障机器，它帮助识别一个序列长度方差导致大作业减速的案例，以及一个不均衡计算分区跨管道阶段导致的单独案例。

相关工作。 大数据中的落后者。落后者问题在大规模框架如MapReduce【2，Ganesh Ananthanarayanan et al. Reining in the outliers in Map-Reduce clusters using mantri. In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10), 2010】【9，Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th Symposium on Operating Systems Design & Implementation (OSDI 04), 2004】【16，Sukhpal Singh Gill et al. Tails in the cloud: a survey and taxonomy of straggler management within large-scale cloud data centres. The Journal of Supercomputing, 2020】【30，Kay Ousterhout et al. Making sense of performance in data analytics frameworks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), 2015】中已被广泛研究。Mantri【2】提供了大规模MapReduce作业中落后者的实证表征，其中他们量化落后者普遍性，并将根本原因归因于负载不均衡、跨机架流量和坏机器。他们提出一个系统，积极重启或复制异常任务，同时优化任务放置和调度以缓解延迟。Ousterhout et al【30】使用类似于我们方法的假设模拟，对Spark的性能瓶颈进行了更深入分析。他们将落后者归因于多样原因，包括Java GC和文件系统延迟。

然而，【2】【30】的模拟方法和发现不适用于LLM训练。首先，模拟MapReduce作业的大部分复杂性由于动态任务调度，例如，reduce任务在其输入在运行时可用后调度到机器。相反，LLM训练使用简单的静态调度，即任务在作业开始时放置且永不改变。其次，模拟LLM训练作业的复杂性在于处理源于混合并行的复杂依赖结构。特别是，LLM作业必须考虑管道并行、张量并行和数据并行，每个发生在不同粒度，并可能仅涉及排名子集。相比之下，MapReduce作业的依赖简单得多，即所有map任务与所有reduce任务通信。这些差异限制了他们的方法和结论对LLM训练的直接适用性。

深度学习训练中的落后者。落后者问题也在深度学习时代的数据并行上下文中被研究。许多先前提案专注于开发落后者缓解策略：Ramamoorthy et al【32，Aditya Ramamoorthy et al. Straggler-resistant distributed matrix computation via coding theory: Removing a bottleneck in large-scale data processing. IEEE Signal Processing Magazine, 2020】建议使用冗余编码计算缓解落后者；Downpour SGD【10，Jeffrey Dean et al. Large scale distributed deep networks. Advances in neural information processing systems, 2012】和Project Adam【7，Trishul Chilimbi et al. Project adam: Building an efficient and scalable deep learning training system. In 11th USENIX symposium on operating systems design and implementation (OSDI 14), 2014】使用异步SGD和陈旧梯度更新缓解落后者；Hop【26，Qinyi Luo et al. Hop: Heterogeneity-aware decentralized training. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 2019】、Tensorflow【1，Martín Abadi et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), 2016】和Chen et al【6，Jianmin Chen et al. Revisiting distributed synchronous sgd. arXiv preprint arXiv:1604.00981, 2016】使用备份工作者解决落后者；DropCompute【15，Niv Giladi et al. Dropcompute: simple and more robust distributed synchronous training via compute variance reduction. arXiv preprint arXiv:2306.10598, 2023】建议丢弃落后者的更新。相比之下，我们的工作专注于表征落后者的影响及其根本原因。

LLM训练中的落后者。最近的研究开始探索LLM训练中的落后者。Malleus【24，Haoyang Li et al. Malleus: Stragglerresilient hybrid parallel training of large-scale models via malleable data and model parallelization. arXiv preprint arXiv:2410.13333, 2024】使用基于实时设备性能的动态并行调整缓解落后者的影响。MegaScale【21，Ziheng Jiang et al. MegaScale: Scaling large language model training to more than 10,000 GPUs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024】、Llama3【11，Abhimanyu Dubey et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024】和Imbue的报告【37，The Imbue Team. From bare metal to a 70b model: infrastructure set-up and scripts. https://imbue.com/research/70b-infrastructure/, 2024】讨论LLM训练的基础设施挑战，并简要提及如何调试落后者，但未提供深入分析。与这些工作不同，我们专注于对落后者问题本身的详细和全面分析。

FALCON【40，Tianyuan Wu et al. FALCON: Pinpointing and mitigating stragglers for large-scale hybrid-parallel training. arXiv preprint arXiv:2410.12588, 2024】呈现落后者的详细表征并引入几种缓解策略。我们的工作在几个方面不同。首先，我们分析专用集群上的作业，而FALCON的分析针对共享集群。设置差异导致不同结果：与FALCON不同，我们未看到由于资源争用导致的落后者。其次，FALCON对大作业（512到1024 GPU）的分析仅限于27个作业跟踪，而我们的分析规模更大：在我们分析的3079个跟踪中，562个作业使用≥512 GPU。只有几十个跟踪，FALCON依赖手动分析研究落后者和确定根本原因。相比之下，我们使用结合假设分析的半自动化方法和假设根本原因的手动验证。而且，FALCON的分析忽略影响大多数步骤而非仅小部分步骤的落后者。正如我们在§4.2所示，前者在我们的跟踪中更常见。