FALCON: Pinpointing and Mitigating Stragglers for Large-Scale Hybrid-Parallel Training

特征分析

  • 计算延迟：来自CPU资源竞争和GPU热节流的性能下降，频率较低，影响较小
  • 通信延迟：网络拥堵为主，其中跨节点RDMA通信最差，影响大
  • 大规模训练出现上述两者叠加出现，规模大，延迟久

框架设计

包括FLC:Detect和FLC:Mitigate

FLC:Detect

分为三阶段

  • Tracking
  • Profiling
  • Validation

Tracking

通过 Linux LD_PRELOAD 环境变量，在训练框架与底层系统库（NCCL、CUDA）之间插入 “Shim 层”，由 Monitor 拦截所有 NCCL 通信调用（如 AllReduce、ReduceScatter），记录调用信息

自周期计算

FLC希望做到“框架无关”，适配Megatron-LM等主流分布式训练框架分布式训练架构图

定义通信调用序列 X={x1​,x2​,…,xL​}，计算自相关函数 ACF(X)k​（k 为 “延迟步长”）：
ACF
其中 μ 为序列均值，ACF(X)k​ 越高，说明 “间隔 k 步的通信序列越相似”，即 k 越可能是迭代周期。
取首个满足 ACF(X)k​≥0.95（阈值通过实验校准）的 k 作为迭代周期，进而计算 “迭代时间”（相邻周期内同名通信操作的时间差），解决 “框架 / 模型周期未知” 的问题（R1）。

慢周期计算

为监测过慢周期，文章采用了BOCD 算法（贝叶斯在线变点检测），定义运行长度rt，若rt=0则说明t时刻迭代时间突变，通过贝叶斯推理计算rt=0的概率，当概率大于90%，将t时刻标记为潜在延迟
rt计算
计算变点前后 “平均迭代时间” 的差异，仅当差异≥10% 时判定为 “真实延迟”，排除 “瞬时波动”（如 CPU 短暂抢占）导致的误判，将 False Positive Rate（FPR）降至 0%。

Profiling

该阶段通过日志分析，对可疑组进行分析，由 Monitor 向 NCCL 调用中注入 CUDA Events（轻量计时工具，overhead<0.1%），记录每个通信组（如数据并行组、张量并行组）的 “数据传输时间”“等待时间”。

  • 通信可疑组：若某通信组的 “数据传输时间” 超过所有同类型组 “中位数的 1.1 倍”，则标记为可疑 —— 说明该组可能存在链路拥堵（传输慢）；
  • 计算可疑组：若某通信组的 “等待时间” 显著过长（超过传输时间的 2 倍），则标记为可疑 —— 说明该组内存在慢 GPU（计算慢，导致其他 GPU 等待）。

Validation

计算延迟验证

Global Controller 向可疑组的 Benchmark Executor 发送指令，并行执行标准GEMM测试（矩阵乘法）
若某 GPU 的耗时超过组内 “中位数的 1.2 倍”，则判定为“慢 GPU”，进一步结合 GPU 温度 / 频率数据，区分热节流与硬件故障。

通信延迟验证

环形
分为环形拓扑和树形拓扑，其中环形拓扑分为偶数环和奇数环，偶数用两轮测试覆盖所有线路，奇数环增加1轮覆盖剩余链路。树形则通过四次测试覆盖所有父子链路，第 1-2 轮偶数层左右子节点→父节点，第 3-4 轮奇数层父节点→子节点
对每条 P2P 链路发送固定大小的测试数据（如 1GB），记录传输延迟，延迟超过中位数 1.2 倍的链路判定为 “拥堵链路”。

FLC:Mitigate

Val
提供了四种方式处理问题,其中S2,S3重要

S2（Adjust micro-batch distribution）

动态调整数据并行组（DP）的微批数量，减少慢 GPU 的负载
微批重分配的核心是求解 “各 DP 组的微批数量mi​”，目标是让所有 DP 组的 “总处理时间（mi​×ti​）尽可能一致”
微批处理
问题转化为了最小化所有 DP 组 “mi​×ti​” 的方差（mi​×ti​​为平均值，转化为了二次规划问题

S3 （Adjust Topology）

重分配拥堵链路到轻量通信组，然后合并慢 GPU 到最少流水线阶段（PP）。首先通过拓扑映射调整，交换拥堵链路关联的 DP 组与空闲 PP 阶段
拓扑调整
然后，根据 PP 阶段的 GPU 容量（每个 PP 阶段包含的 GPU 数量，由 TP 策略决定），计算 “容纳所有 straggler 节点所需的最少 PP 阶段数。选择负载最轻的 PP 阶段作为 straggler 合并的目标阶段
最少PP如何计算
验证
图中表明慢PP阶段决定了周期

其他

SM利用率是什么
SM = Streaming Multiprocessor（流多处理器），是 NVIDIA GPU 的核心计算单元（负责执行 AI / 深度学习任务，如矩阵运算、激活函数计算）。​
SM 利用率 = （SM 实际工作时间 / 总观测时间）× 100%，反映 GPU 计算核心的忙碌程度。

为什么是一次周期包含RS,AG,AR,AR?
一、先明确操作缩写（论文上下文）​

RS = ReduceScatter（归约散射）：常用于张量并行（TP），拆分归约结果并分发到各 GPU；​

AG = AllGather（全聚集）：常用于张量并行（TP），收集各 GPU 的局部结果拼成全局数据；​

AR = AllReduce（全归约）：常用于数据并行（DP），同步所有 GPU 的梯度 / 参数，确保全局一致性。​

二、一次迭代包含这些操作的核心原因：适配混合并行（TP+DP）的通信需求​
在 FALCON 针对的混合并行训练（TP+DP 为主，PP 为辅） 中，一次迭代需完成 “算子拆分计算→梯度同步更新”，不同并行策略依赖特定通信操作，最终形成 “RS→AG→AR→AR” 的典型组合（顺序因模型层而异，核心是覆盖 TP 与 DP 的通信需求）：​

  1. 第 1 组操作（RS+AG）：服务张量并行（TP）的算子计算​
    TP 需拆分模型算子（如 Transformer 的 Attention/MatMul），依赖 RS+AG 完成 “局部计算→全局结果拼接”：​

    RS（ReduceScatter）：TP 组内各 GPU 计算算子局部结果后，通过 RS 将 “归约运算（如求和）” 的结果拆分分发（例：8-GPU TP 组，将 1024 维矩阵归约后拆分为 8 个 128 维子矩阵，每个 GPU 获 1 份）；​

    AG（AllGather）：各 GPU 拿到 RS 分发的子矩阵后，通过 AG 收集所有 GPU 的子矩阵，拼成完整的全局结果（例：8 个 128 维子矩阵拼成 1024 维矩阵），供后续层计算使用。​

  2. 第 2 组操作（AR+AR）：服务数据并行（DP）的梯度同步​
    DP 需复制模型副本、同步梯度，依赖 AR 完成 “局部梯度→全局统一梯度”，两次 AR 分别对应不同参数 / 梯度的同步（因混合并行中 TP 与 DP 参数需分开同步）：​

    第 1 次 AR：同步 TP 拆分后的 “局部参数梯度”（例：TP 组内各 GPU 的算子梯度），确保 TP 组内梯度一致；​

    第 2 次 AR：同步 DP 组内所有 GPU 的 “全局参数梯度”（例：所有 TP 组的梯度汇总后，通过 DP 组 AR 同步到全集群），最终所有 GPU 用统一梯度更新模型，避免参数不一致。

为什么有训练周期
Iteration time 源于分布式训练的 “同步执行逻辑”：​

单卡训练中，模型按 “批次（Batch）” 处理数据；分布式训练中，多 GPU 需协同完成 1 个 “全局批次（Global Batch）”，该协同周期即 1 个 Iteration，其耗时即为 Iteration time。​

核心目的：保证所有 GPU 参数同步更新（如 DP 组梯度 AllReduce 后统一更新），避免参数不一致导致训练发散。​

三、What Happens in 1 Iteration (Distributed Training)​
以混合并行（TP+DP+PP）为例，1 个 Iteration 的核心流程（循环执行）：​

  • 数据加载与拆分：CPU 加载数据，按 DP 组拆分微批（Micro-batch），分发至各 GPU；​

  • 并行计算（前向 + 反向）：​

    TP 组拆分算子并行计算（如 Attention 层）；​

    PP 组按流水线处理模型层（前一阶段激活值传递给后一阶段）；​

    各 GPU 独立完成前向传播（算预测值）与反向传播（算梯度）；​

  • 跨 GPU 通信同步：​

    DP 组：AllReduce 同步梯度；​

    TP 组：交换算子中间结果；​

    PP 组：传递激活值与梯度；

文章的时间序列是如何得出的？也就是Xt是怎么计算得来的
FALCON 通过修改训练框架（如 Megatron-LM）的代码逻辑，在每次迭代的 “起始” 和 “结束” 两个关键节点，植入基于 CUDA Events 或 系统时钟（如 Linux clock_gettime） 的计时工具（论文明确提到 CUDA Events 的 overhead<0.1%，不会干扰训练）：

迭代起始锚点（Tstart,t​）：在 “第 t 次迭代的数据加载开始前” 触发计时 —— 此时训练框架刚完成第 t−1 次迭代的参数更新，准备启动第 t 次的数据处理；
迭代结束锚点（Tend,t​）：在 “第 t 次迭代的参数更新完成后” 触发计时 —— 此时第 t 次迭代的 “数据加载→前向计算→反向传播→通信同步→参数更新” 全流程已结束，框架准备进入第 t+1 次迭代。

迭代时间序列的自相关系数在 “真实周期对应的滞后阶数” 处会出现显著峰值，且当该峰值超过 0.95 时，可确认此滞后阶数即为迭代的稳定周期。ACF 的核心特性：自相关系数衡量 “时间序列在滞后阶数τ处的自我相似性”—— 若迭代存在周期τ0​，则在τ=τ0​,2τ0​,3τ0​…处，ACF 值会出现峰值（相似性最高）；而在非周期滞后阶数处，ACF 值会接近 0（相似性低）。

BOCD
BOCD 的核心思路是 “在线追踪迭代时间的概率分布变化”：

假设前提：无故障时，迭代时间服从稳定的概率分布（如正态分布，参数由 ACF 分析得到的 “正常周期” 确定）；当延迟故障发生时，迭代时间的分布会突然改变（如均值增大、方差变大）。
在线推断：每新增一次迭代的耗时数据（即新的Xt​），BOCD 会基于 “历史数据概率” 和 “新数据似然度”，动态更新 “当前时刻是否为变化点” 的概率。
变化点判定：当 “当前为变化点的概率” 超过预设阈值（论文未明确数值，但基于场景推断为高置信度阈值，如 0.95）时，判定检测到变化点 —— 即迭代耗时从正常转为异常，可能存在延迟故障。

  1. 第一步：BOCD 变点检测（识别潜在性能突变）
    BOCD（Bayesian Online Change-point Detection）是一种高效的时间序列分析算法，能够在线（实时）检测动态序列中的 “变点”（即性能突然变化的时间戳），这些变点通常对应 fail-slow 的开始或结束（）。其核心逻辑基于贝叶斯推断，具体实现如下：

输入数据：由 FALCON-DETECT 的 Monitor 模块采集的 “迭代时间序列”—— 通过自相关函数（ACF）分析通信操作的周期性，计算出每个训练迭代的精确耗时（、）。
核心定义：运行长度（run-length, rt​）

算法为每个时间戳t定义 “运行长度”rt​，用于描述 “当前时刻与上一个变点之间的迭代数”：rt​={0,rt−1​+1},​若 t 是变点（性能突变）若 t 不是变点（性能连续）​
例如，若t=50时rt​=0，说明第 50 次迭代是性能突变点；若rt​=10，说明从第 40 次迭代到第 50 次迭代性能未变（）。
贝叶斯推断计算变点概率

算法通过贝叶斯公式实时计算 “当前时间戳t为变点” 的概率：
假设 “变点先验”（反映 fail-slow 发生的预期频率，文档中未明确具体值，但实验中通过阈值控制灵敏度）；
对每个时间戳t，计算rt​=0（即t是变点）的后验概率；
若该概率超过预定义阈值（实验中设为 0.9），则将t标记为 “潜在变点”，初步判定为 fail-slow 的发生或结束（）。
算法优势：BOCD 的时间复杂度为O(T)（T为迭代次数），可实时处理动态迭代序列，且无需预先知道变点数量，适合训练过程中 “突发且不可预测” 的 fail-slow 检测（）。

  1. 第二步：变化点验证（过滤误报，提升准确性）
    直接使用 BOCD 会产生大量误报—— 训练过程中常见的 “短暂性能波动”（如 GPU 瞬时负载变化、网络抖动）可能被误判为 fail-slow（）。为此，FALCON-DETECT 增加 “变化点验证” 步骤，通过对比变点前后的性能差异，过滤非实质性的波动，具体逻辑如下：
    验证逻辑：对 BOCD 识别出的每个 “潜在变点”，计算 “变点前N次迭代的平均耗时” 与 “变点后N次迭代的平均耗时”（N为滑动窗口大小，文档未明确具体值，但需保证统计显著性）；
    判断标准：若两者的性能差异（slowdown）小于 10%，则判定为 “正常性能波动”，排除该变点；若差异≥10%，则确认该变点为 “真实 fail-slow 事件”（）。
    验证目的：通过 “10% 性能差异阈值” 过滤误报，例如：若某迭代的耗时从 1.0s 短暂升至 1.05s（差异 5%），则判定为波动；若升至 1.2s（差异 20%），则确认是 fail-slow（）。

Validation为什么只有两种拓扑结构
在基于 NCCL（NVIDIA Collective Communications Library）的分布式训练中，环形和树形是实现关键通信操作（如 AllReduce、ReduceScatter、AllGather）的默认且最常用的拓扑结构，几乎覆盖所有混合并行训练的通信需求：

环形拓扑（Ring）：是 NCCL 实现 AllReduce（数据并行梯度同步）、ReduceScatter（张量并行结果拆分）的核心拓扑。其优势是 “无中心节点瓶颈”，通信效率随 GPU 数量线性扩展（如 8-GPU 环形拓扑，每个 GPU 仅需与相邻 2 个 GPU 通信，总通信量低），是中小规模集群（16-128 GPU）的首选拓扑；
树形拓扑（Tree）：常用于大规模集群（≥256 GPU）或跨节点通信场景，尤其适合 AllGather（张量并行结果拼接）操作。其优势是 “层级化通信”，可将跨节点通信拆解为 “节点内子树→节点间父树” 的两步传递，减少跨交换机的通信延迟，是超大规模训练的主流拓扑。

Adjust micro-batch distribution这里所求解的二次方程最终求解出来什么，又会如何根据所得结果调整micro-batch分配
核心是在 “总微批数量固定” 的约束下，找到一组x1​,x2​,…,xk​，使所有节点的处理总耗时T相等（即同步完成）。需注意：ti​的 “已知” 并非 “固定不变”，而是 “每次微批调整前均会重新采集与计算”—— 因为节点速度可能随故障变化。ti​的获取依赖 FALCON 的底层监控模块，与迭代时间序列Xt​的采集逻辑一致，具体通过以下 3 步实现 “已知”：
植入计时锚点，记录节点级耗时，在每个节点的 “微批处理流程” 中植入 CUDA Events 或系统时钟：
微批处理开始时记录Tstart,i,m​（节点i处理第m个微批的起始时间）；
微批处理结束时记录Tend,i,m​（节点i处理第m个微批的结束时间）；
单个微批耗时为Δti,m​=Tend,i,m​−Tstart,i,m​，直接可测。

如何根据问题作mitigate等级划分
等级划分规则（论文隐含逻辑，结合实验场景）：
故障等级 延迟比例δ 拥堵链路数Lc​ 慢 GPU 数Gs​ 核心特征
1 级（轻微） <15% ≤1 0 仅单条链路轻微拥堵，无慢 GPU
2 级（轻度） 15%−30% 2−3 1 少量链路拥堵，1 个慢 GPU
3 级（中度） 30%−60% ≥4 2−3 多条链路拥堵，少量慢 GPU
4 级（严重） >60% 全网拥堵 ≥4 大规模链路拥堵 + 多慢 GPU

Evaluation的和BOCD对比的滑动窗口算法是什么

窗口划分：维护一个固定长度的 “滑动时间窗口”（例如包含最近 N 次迭代的时间数据，N 为预设窗口大小，如 5-10 次迭代）；
统计基准：实时计算当前窗口内所有迭代时间的 “中位数”（而非平均值，以减少极端值干扰），将其作为 “正常性能基准”；
异常判断：当新迭代的时间与当前窗口的中位数偏差超过预设阈值（论文中设为 10%）时，立即报告检测到 Fail-Slow 事件。

简言之，该算法的核心规则可概括为：若（当前迭代时间 - 窗口内中位数）/ 窗口内中位数 > 10% → 判定为 Fail-Slow

上述基于磁盘的检查点方案为什么能证明拓扑调整开销不大？拓扑调整为什么使用Ckpt进行对比
就是想使用传统的检查点方案，对比现在的拓扑调整后的方案，证明拓扑调整开销不大。

文章中这里的60.1%是如何计算的
故障损失量=17.1−14.8=2.3 Iters/min
恢复量=16.2−14.8=1.4 Iters/min
缓解效果=(1.4/2.3​)×100%≈60.87%

拓扑结构中PP DP的动态调整
PP的通信量小，压力小，DP的通信量大，压力大。因此在出现communication 阻塞的时候，交换节点的任务角色。例如样例中节点3-4出现问题，是因为他们的DP交互问题，那么把3与2的角色交换就可以缓解问题。

为什么拓扑调整没有考虑TP
TP 的通信操作（如算子同步）仅发生在单节点内部，依赖节点内高速互联组件（如 NVSwitch，通信延迟低、性能稳定），不涉及跨节点的 RDMA 链路或 RoCE 网络（、）。而communication 阻塞通常发生在跨节点的通信场景。

PP-Stage
把PP-Stage看成多维度的三维的。PP-Stage 可跨多个节点，但会控制节点数量以降低通信延迟。一行就是一个GPU

说些什么吧！

gitalk