DeepSeek 4th day解读：运筹学登场！你的算力也许还有40%提升空间？

今天是DeepSeek开源周的第四天，DeepSeek开放了三个新的项目[1]——profileData、EPLB和DualPipe。其中profileData公开分享了他们训练和推理框架的分析数据；EPLB用于处理专家并行（EP）当中常常遇到的负载不均衡的问题；而DualPipe则是在DeepSeek-V3Technical Report [2]中推出，并引发众多讨论的一种新的流水线并行（PP）调度算法。

我们这里简要解读DualPipe调度的原理，并探讨基于MILP模型和COPT专业求解器对其进行改进的可能性。

流水线并行

在大模型训练和推理过程中，一般会将模型参数分布到多个GPU、多个计算节点上。这样，一方面可以有效地扩大模型的规模，另一方面可以通过各GPU并行进行计算来提升计算效率。

根据模型拆分方式的不同，常见的并行策略包括数据并行（DP）、张量并行（TP）、专家并行（EP）、流水线并行（PP）等。实践中，常常结合使用多种并行策略。例如DeepSeek-V3模型就同时使用了DP、EP和PP。

概念上，大语言模型（和其它许多深度学习模型）的推理过程可以表示为一系列函数的嵌套求值，即

流水线并行将不同的计算放到不同的GPU上。这样，在推理时，就由GPU 1计算，并将结果传递给GPU 2；GPU 2收到结果后计算，将结果传递给GPU 3，以此类推。训练过程中，除了相同的前向传播之外，还需要得出推理结果对应的误差，并将梯度反向传播回去。如图。

因此训练过程中的数据流向是

GPU 1 > GPU 2 > … > GPU n > … > GPU 2 > GPU 1

并且，由于数据之间的依赖关系，每个GPU都只能在所有前序计算完成之后再开始计算，如下图

从中能够看出，在任意时刻，实际上只有一个GPU在计算。因此虽然我们使用了多个GPU，并将模型的权重分布在了这些GPU上面，但是并没有实现计算的并行。将数据进一步拆分为micro-batch并分别求值能够部分地解决这个问题，如下图。但是由于流水线并行天生的数据依赖关系，在计算过程中仍然存在大量的GPU空闲时间，研究者将其称为bubble。

另一个问题是，上述建模过程完全忽略了通信时间，并因此低估了bubble的规模。实际上，通信的时间成本往往不能够简单地忽略掉，尤其是在使用H800等通信带宽较低的硬件的情况下。如DeepSeek-V3声称其计算通信比达到了1:1。

DualPipe调度

为了减少bubble数量，同时提升计算与通信之间的并行性，DeepSeek延续了之前两项研究——ZeroBubble [3] 和 Chimera [4] 的思路。Chimera提出可以通过增加一条反方向流水线的方法来提升并行性。直观来看，上图中的bubble出现在计算起始的一侧，这样，一对相向的流水线恰好能彼此利用对方的bubble，达成提升并行度的目的。ZeroBubble则指出，在反向传播的过程中，可以通过进一步拆解计算过程来消除一部分数据依赖，即将反向传播拆分为B和W两部分。这种拆分能够给调度提供更高的灵活度，进而减少bubble数量，提升并行度。DualPipe结合了这两项工作，得出了如下调度方案。

在这一调度方案中出现了很多对齐的“F-B-W”的计算流程。DeepSeek指出，这样的方案同时有利于通信和计算的相互掩盖。

这样，DeepSeek就通过这一算法成功解决了bubble数量和通信掩盖两个问题。

基于MILP模型的自动调度算法

上述所有的调度方案的提出，以及其有效性，都依赖于一个共同的前提假设，即F、B、W的计算时间相等。在ZeroBubble中，作者提到，这样的前提假设和手工排布方案在实际应用中将面临一系列问题。例如，对于F、B、W的实际计算时间差异较大的模型，在实际训练中，上述方案将引入没有预料到的bubble。同时，对通信时间的忽略（虽然DualPipe在稳态阶段能够掩盖通信时间，但是在其开始、结束两端，通信时间被忽略掉了）也将导致求值过程产生延迟。

在建立调度方案时考虑上述数据，能够使模型更贴合实际，获得更好的实际效果。ZeroBubble成功地将上述问题建模成为了混合整数线性规划问题(MILP)，同时给出了一种生成该问题的解的启发式方法。提出可以利用启发式方法得出该问题的初始解，并调用开源求解器CBC对其进行进一步优化，得出最终调度方案，并将这一流程称为自动调度。

我们从ZeroBubble的Github开源代码[5]中能够看到，它利用PuLP建立了上述模型，并调用开源求解器CBC进行求解。

遗憾的是，在后续的一次代码修改[6]中，求解ILP的逻辑被跳过。从此之后，这一自动调度算法只依赖于启发式算法给出的解。

经过试验我们发现，作者做出这样的修改，可能有两方面原因——一方面是因为其启发式方法在该问题下的确足够优秀，在很多情况下能够给出最优解；但另一方面也是因为其使用的开源求解器CBC的求解效率不尽如人意，在给定时限下难以得到更好的解。如果能够使用我们的专业级别COPT求解器进行求解，显然有更大可能性快速地证明解的最优性或找到更好的解。

例如，参照上表第一行的数据，ZeroBubble中的启发式方法给出的初始解的时长是3761.489，通过求解MILP模型，COPT能够在120s内将其改进到2236.089，改进了40%，而CBC在相同时间内则难以获得任何改进。如图所示。

初始解的目标值

COPT 7.2.4求解结果

CBC求解结果

使用MILP模型求解DualPipe自动调度

在DeepSeek最新公开的DualPipe相关代码中，我们注意到，它仍然以固定规则对计算流程进行调度。

我们相信，依照ZeroBubble提出的Automatic Scheduling的思想，在引入实际计算时间之后，DualPipe调度方案的效率能够得到进一步提升。

作为初步试验，我们在ZeroBubble模型的基础上，依照DualPipe模型的假设，增加一条反向流水线，并将其依赖的“F-B-W对齐”的约束加入了模型中。我们使用杉数COPT求解器求解该MILP模型，从而自动获得如下调度方案。

总结：

LLM训练和推理是非常复杂的并行计算问题。其计算效率不仅仅依赖于硬件本身的执行效率，也依赖于有效的调度方案。手工调度方案和基于规则的调度方案难以应对复杂多变的实际情况，此时MILP模型是表达这类调度问题的有效工具。然而，这些调度问题求解难度往往规模较大，开源求解工具往往难以满足需求，所以启发式算法和COPT等专业求解器的结合，可能能够为解决问题提供更高效更优化的途径！

（作者：葛冬冬、尹旭东、皇甫琦、陈艺天）

参考资料来源：

[1]https://github.com/deepseek-ai

[2]https://github.com/deepseek-ai/DeepSeek-V3

[3]https://arxiv.org/abs/2401.10241

[4]https://arxiv.org/abs/2107.06925

[5]https://github.com/sail-sg/zero-bubble-pipeline-parallelism

[6]https://github.com/sail-sg/zero-bubble-pipeline-parallelism/commit/a99d554107bef6a7969b24744d088e2363980de4