供应链问题正在比以往任何时候都更多的SKU、运输路线和约束条件中蔓延，而能源电网则实时平衡着更多分布式电源。为应对这些挑战，团队需要在实际规划窗口内评估更大的模型和更多的不确定性。
NVIDIA cuOpt GPU加速决策优化已经可以在单GPU上为大规模线性规划（LP）问题提供比CPU求解器超过10倍的加速。然而，当今最大的规划问题可能需要数小时才能收敛，或超出单个GPU的内存容量。这些限制成为驱动业务决策的工作流的瓶颈。
历史上，大型且极具挑战性的LP问题一直是研究人员和从业者持续关注的主题。其中一个问题，zib03，由Thorsten Koch于2008年提出，具有超过1.04亿个非零元素，已成为新算法和求解器广泛研究的基准。图1展示了该领域通过新算法和新硬件在解决此问题上取得的进展。cuOpt现在通过使用mPDLP在多个GPU上解决该问题，进一步推动了极限，实现了比一年前快近10倍的求解速度。
图1. 线性规划求解器在问题zib03上求解时间的进展本文介绍了新的cuOpt多GPU线性规划原始-对偶混合梯度（mPDLP）求解器。它将LP问题分布到通过NVLink连接的GPU上，实现了两个主要成果：
- 减少大型问题的求解时间，这些问题在规划者可用的时间窗口内无法实际解决
- 与单GPU PDLP相比，每个GPU的峰值内存使用量最多降低6倍（LP问题上限为21亿个非零元素）
本文还通过两个合作伙伴应用突出了这种方法的好处：Kinaxis在全球受限的供应和生产计划中，以及PSR在大规模能源系统容量扩展模型中。
PDLP算法如何求解LP？
求解LP在于为以下方程找到(x)：
\begin{aligned}
\min_{x} \quad & c^\top x \
\text{s.t.} \quad & Ax = b \
& l \leq x \leq u
\end{aligned}
LP的原始-对偶混合梯度（PDLP）是求解LP的一阶方法。它基于类似梯度下降的方法，使其高度可并行化且对GPU友好，从而实现显著加速。
该算法的热循环是稀疏矩阵-向量乘法（SpMV），随后是几个映射操作。
此方法在两个向量上迭代：
- 原始解（(x)）
- 对偶解（(y)）
LP 的约束被抽象为一个矩阵（(A)）。这是 SpMV 循环中使用的矩阵。还有这个矩阵的转置（(A)T）。
迭代算法由以下操作组成：
\begin{aligned}
x^{k+1} &= \text{proj}_{[l,, u]}!\left(x^k – \tau(c – A^\top y^k)\right) \
y^{k+1} &= y^k + \sigma\left(b – A(2x^{k+1} – x^k)\right)
\end{aligned}
这里，τ 和 σ 是原始步长和对偶步长，proj[l,u] 表示投影到变量边界 (l ≤ x ≤ u)，(b) 是线性等式约束的右侧，(c) 是我们试图最小化的目标函数的成本向量。
该算法主要由逐元素操作组成：投影和基本算术。这些操作在多 GPU 上分配是微不足道的，因此在开发分布式算法时可以忽略它们。剥离到其非平凡的通信步骤，算法是：
\begin{aligned}
x^{k+1} &= A^\top y^k \
y^{k+1} &= Ax^{k+1}
\end{aligned}
(y) 的最后一个值用于通过 SpMV 计算下一个 (x)，而 (x) 的最后一个值用于通过另一个 SpMV 计算下一个 (y)。
分布式 PDLP
在 PDLP 中唯一需要分配的非平凡任务是 SpMV，这是一个内存受限的操作。这意味着增加可用带宽会增加操作速度。要增加带宽，您可以选择等待下一代 NVIDIA GPU 发布，或者使用更多 GPU，有效地将总可用带宽乘以 GPU 数量。然而，这伴随着分布式算法的成本。
在分配算法时，必须最小化两个主要开销：
通信开销：等待来自其他 GPU 的信息所花费的时间负载不平衡：工作在不同 GPU 之间的不均匀分配，导致一些 GPU 等待其他 GPU
NVIDIA 为硬件和软件栈提供了高效分布式计算所需的通信工具。
对于硬件栈，NVLink 和 NVSwitch 提供了计算骨干。NVLink 支持两个 GPU 之间快速、优化的数据交换，而 NVSwitch 高效地协调多个 GPU 之间的通信。
对于软件栈，NCCL 是一个 C/C++ 库，提供对 GPU 直接点对点通信和 GPU 之间的集体操作（AllReduce、AllGather、Broadcast）的访问。这些操作原生使用 NVLink 和 NVSwitch 以充分发挥其能力。
通过 NVLink、NVSwitch 和 NCCL 的结合，多个不同的 GPU 成为一个快速共享机器。数据以高带宽和低开销在设备之间移动，因此分布式算法可以在不离开 GPU 的情况下扩展。
2D 分区 D-PDLP
之前将 PDLP 分布到多个 GPU 的努力包括 D-PDLP。首先，可以重新排序矩阵以改善负载平衡。然后，它沿其行和列划分为几个子块，这些子块分布在 GPU 上。最后，通过在每个子块上执行 SpMV 并求和对应于同一行的结果部分输出来计算原始矩阵的 SpMV，以重建最终结果。
这意味着输出向量的每个结果都需要通过多个 GPU 之间的通信来构建。这项技术效果良好，D-PDLP 利用它展示了多 GPU 加速的潜力。然而，D-PDLP 中的二维分区独立计算每个 SpMV，而 cuOpt mPDLP 则利用了连续 SpMV 通过 (x) 和 (y) 向量共享依赖关系这一事实。
最小割分区的 PDLP
最小割分区利用了每次 PDLP 迭代中执行的两个 SpMV 之间共享的依赖关系。与将 SpMV 独立处理的二维分区方法不同，最小割分区在决定如何将约束矩阵分布到多个 GPU 上时，会联合考虑这两个操作。
其核心思想是对矩阵进行分区，使得输入和输出向量之间紧密连接的依赖关系尽可能保留在同一个 GPU 上。通过利用 (A) 的稀疏模式，最小化连续 SpMV 之间的通信。
图 2. 约束矩阵 (A) 与原始解 (x) 之间的稀疏矩阵向量乘法示例，产生 (y)
在执行 (y^{k+1} = Ax^{k+1}) 时，底层操作如下：
\begin{aligned}
y_1 &= 1x_1 + 2x_2 + 4x_3 + \textcolor{gray}{0x_4} \
y_2 &= 3x_1 + 6x_2 + \textcolor{gray}{0x_3} + \textcolor{gray}{0x_4} \
y_3 &= \textcolor{gray}{0x_1} + 7x_2 + 1x_3 + 2x_4 \
y_4 &= \textcolor{gray}{0x_1} + \textcolor{gray}{0x_2} + 3x_3 + 4x_4
\end{aligned}
在计算 (y) 时，对于 (y) 中的不同分量 (y)1、(y)2、(y)3、(y)4，无需使用完整的向量 (x)。这是由于 (A) 的稀疏性。在执行计算 (y)1 的操作时：(x)4 是不必要的。对于 (y)2：(x)3 和 (x)4 是不必要的。这在图 3 的二部图中进行了说明。
(x)
图 3. 基于矩阵稀疏性连接原始变量(y) 与对偶变量的二部依赖图
*图 3 展示了计算每一行所需数据的一般概览（如果从右向左阅读，该图也代表 AT 上 SpMV 的依赖关系）。这也意味着，如果图被划分为 k 个部分，k 为 GPU 的数量，那么位于一个分区内部的边可以在本地计算，而分割在两个分区之间的边将需要与边相关联的两个 GPU 之间进行通信。
图 4. 跨两个 GPU 的最小割图划分，突出显示跨 GPU 通信边
回到示例，在图 4 中，图被划分，GPU 1 拥有（即负责计算）上组中的 (y)1、(y)2、(x)1、(x)2，而 GPU 2 拥有下组中的其他行和列。这种划分在执行 SpMV 时提高了局部性。在 GPU 1 上，计算 (y)1 时，需要来自 (x)1、(x)2 和 (x)3 的数据。然而，(x)1 和 (x)2 是局部的，并且已经在上一步中计算过。只需要从 GPU 2 拉取 (x)3，这是远程的。
通信与边割紧密相关。(y)1-(x)3 边在分区之间被割开，这导致计算 (y)1 时需要额外的一次通信。这意味着，在划分图的同时减少边割的数量——取决于 (A) 的稀疏模式——可能会大大减少通信需求。这正是最小割划分所做的：一种减少边割的图划分。
总结：
- (A) 是表示线性规划约束的稀疏矩阵
- 首先，具体化由矩阵 (A) 定义的双部图
- 然后，将图进行 k 路划分（对于 k 个 GPU）以减少边割
- 根据分区中的节点，为每个 GPU 分配行和列的子集
- 执行 PDLP 迭代；工作主要是 GPU 本地的，通信发生在划分中被割开的边上
这种方法高度依赖于图中的边割数量，导致性能因矩阵 (A) 的稀疏模式而变化。
基准测试结果
这里展示的基准测试结果将 mPDLP 与另外两种 PDLP 实现进行比较：单 GPU cuOpt PDLP 和基于多 GPU 的 D-PDLP。
我们在超过 100 个 LP 实例上运行了基准测试，涵盖多个数据集，包括：
- Hans Mittleman LPFeas基准集 - Hans Mittleman
LPFeas大型问题附录 PDLP基准数据集D-PDLP基准数据集Open Energy Benchmark- 来自 NVIDIA 行业合作伙伴的问题
对于每个实例，我们使用目标容差 10−6，时间限制为一小时。分布式求解器 mPDLP 和 D-PDLP 在配备 NVIDIA DGX B200 GPU 的节点上进行评估，这些 GPU 通过全互联 NVLink 拓扑连接。单 GPU cuOpt PDLP 实现使用单个 B200 GPU 进行评估。
图 5. mPDLP cuOpt 与单 GPU cuOpt 在不同非零元数量下的墙钟时间加速比比较
图 5 比较了 mPDLP cuOpt 和单 GPU cuOpt。它表明加速比与问题规模强烈相关。当非零元（nnz）数量超过 107 时，加速比显著。超过此阈值后，加速比随问题规模增加，意味着更大的问题从多 GPU 实现中获益比单 GPU 版本更多。
请注意，这些运行时间包含若干与迭代无关的开销：预求解、A 的主机端转置、图划分和后求解。只有 PDLP 步骤分布在各个工作节点上，因此只有它们能从额外的 GPU 中获益。仅测量 PDLP 步骤的加速比，mPDLP 在 tsp-gaia-10m 上最高可达 11.4 倍
，远高于端到端测得的 4.2 倍。
图 6. cuOpt mPDLP 与 D-PDLP 在各基准数据集上的性能比较图 6 比较了 mPDLP 与 D-PDLP。同样，在小规模问题上观察到性能较低，而一旦非零元素数量超过 10^7，mPDLP 就变得更具竞争力。在大多数这些大规模实例（nnz>10^7）上，mPDLP 相对于 D-PDLP 实现了 1.2 倍到 2.5 倍的加速。
然而，在三个超大规模实例上，mPDLP 比 D-PDLP 更慢。值得注意的是，这些实例来自既有的优化基准，可能无法代表 cuOpt mPDLP 所针对调优的真实世界问题中的稀疏模式。这可能导致了所观察到的性能下降，尽管超大规模实例数量较少，也使得难以得出普遍结论。
多 GPU PDLP 只有在问题足够大、通信开销相对于计算时间变得可忽略时才能带来加速。在较小的问题上，每次迭代中 GPU 同步和数据传输的固定成本超过了并行带来的收益。
稀疏结构也很重要：在最小割划分后具有高边割比率的问题会产生大量的跨 GPU 通信，这可能抵消甚至逆转加速效果。
在整个优化生态系统中集成多 GPU PDLP
NVIDIA 正在与优化生态系统中的合作伙伴合作，将多 GPU PDLP 求解器能力引入开发者已经使用的工具和平台中。
Kinaxis 在其 Maestro 平台上使用 NVIDIA cuOpt mPDLP，在八块通过 NVLink 连接的 NVIDIA H100 GPU 上，对一个拥有超过 1.35 亿个变量的 CPG 供应链 LP 模型实现了 3.3 倍的加速。PSR 在八块通过 NVLink 连接的 NVIDIA B200 GPU 上使用 NVIDIA cuOpt mPDLP，对一个拥有 1.85 亿个变量的随机能源扩展 LP 模型展示了超过 5 倍的加速。
持续改进 cuOpt mPDLP
NVIDIA 还在致力于以下 cuOpt mPDLP 的改进和功能：
最小割划分：当前划分未考虑每个 GPU 的计算负载。权重感知的最小割与超图划分将使分布具备负载感知能力，从而减少 GPU 之间的不均衡与通信开销。隐藏通信：当前 SpMV 热循环按顺序进行通信与计算；将矩阵拆分为本地与远程两部分，可使本地计算与远程数据传输并行运行，减少 GPU 空闲时间。可行性打磨：大规模 LP 通常需要数百万次 PDLP 迭代才能收敛。可行性打磨以最优性换取速度，在更少的迭代次数内给出可行解，并扩展了 mPDLP 在实际时间限制内可求解的问题范围。
在 NVIDIA cuOpt 中开始使用 mPDLP
使用 cuOpt mPDLP 教程在多个 GPU 上运行你的 LP 模型。按照该 notebook 安装 cuOpt、配置求解器，并比较不同 GPU 数量下的求解时间。先从提供的示例入手，然后加载你自己的 MPS 文件，以衡量你的工作负载上的性能。
在 NVIDIA/cuopt GitHub 仓库中探索 cuOpt 源代码，并参阅产品文档以了解 API、求解器设置和部署指南。
在 cuOpt GitHub 讨论论坛 上与开发者社区交流。通过订阅 NVIDIA 新闻 并在 LinkedIn 、 X 、 Discord 和 YouTube 上关注 NVIDIA AI，随时了解 NVIDIA cuOpt 的最新动态。