供应链问题正在比以往任何时候都更多的SKU、运输路线和约束条件中蔓延，而电网正在实时平衡更多分布式能源。为应对这些挑战，团队需要在切实可行的规划窗口内评估更大的模型和更多的不确定性。
NVIDIA cuOpt GPU加速决策优化在单GPU上针对大规模线性规划（LP）问题，已经能够比CPU求解器实现超过10倍的加速。然而，当今最大的规划问题可能需要数小时才能收敛，或超出单个GPU的内存容量。这些限制成为驱动业务决策的工作流的瓶颈。
历史上，大型且众所周知的棘手LP问题一直是研究人员和从业者持续关注的主题。其中一个问题zib03，由Thorsten Koch于2008年提出，具有超过1.04亿个非零元素，已成为新算法和求解器广泛研究的基准。图1展示了该领域通过新算法和新硬件在解决此问题上取得的进展。cuOpt现在通过mPDLP在多个GPU上求解该问题，进一步突破了极限，求解速度比一年前快了近10倍。
本文介绍新的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}
线性规划原始-对偶混合梯度（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 的情况下进行扩展。
二维分区的 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 之间的通信。
在执行 \(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 的二分图中有所展示。
图 3 展示了计算每一行所需数据的一般概览（如果从右向左阅读，该图也表示了 \(A\) T 上 SpMV 的依赖关系）。这也意味着，如果图被划分为 k 个部分，k 为 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 并通过全互联 NVLink 拓扑连接的节点上进行评估。单 GPU cuOpt PDLP 实现使用单个 B200 GPU 进行评估。
图 5 比较了 mPDLP cuOpt 和单 GPU cuOpt。它表明加速与问题规模密切相关。当非零元素数量（nnz）超过 10 7 时，加速效果明显。超过这一阈值后，加速比随问题规模增大而提高，这意味着更大的问题从多 GPU 实现中获益比单 GPU 版本更多。
请注意，这些运行时间包含若干与迭代无关的开销：预求解、A 的主机端转置、图划分和后求解。只有 PDLP 步骤分布在各个 worker 上，因此只有这些步骤能从额外的 GPU 中获益。仅测量 PDLP 步骤的加速比时，mPDLP 在 tsp-gaia-10m 上最高可达 11.4 倍，远高于端到端测得的 4.2 倍。
图 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 使用 NVIDIA cuOpt mPDLP，基于八块通过 NVLink 连接的 NVIDIA B200 GPU，在一个拥有 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 的最新动态。
转载声明：本文为转载整理，原文版权归原作者及原站点所有。
原文作者：Tanya Lenz；如有侵权，请联系管理员删除。
