在过去一个世纪中,从 单纯形 到 内部点法(IPM),线性编程(LP)求解器的演进取得了许多重大里程碑式的发展。 原始对偶线性编程(PDLP) 的引入又带来了另一项重大进展。
NVIDIA cuOpt 现已实施具有 GPU 加速功能的 PDLP。利用先进算法、NVIDIA 硬件、专用 CUDA 功能和 NVIDIA GPU 库,cuOpt LP 求解器的性能比基于 CPU 的求解器快了 5000 倍以上。
本文将探讨 LP 求解器算法的关键组件、LP 中的 GPU 加速,以及 Mittelmann 基准测试 和 最小成本流问题 实例上的 cuOpt 性能。
利用尖端创新实现大规模 LPHarnessing cutting-edge innovations for large-scale LP
LP 是一种涉及优化线性目标函数的方法,受一组线性约束。
假设情况:在土地、种子和化肥方面的限制条件下,农民必须决定种植哪些菜以及以何种数量实现利润最大化。目标是尽快确定最佳收入,同时遵守所有限制条件。
NVIDIA 开发了一个 LLM 智能体示例 ,可帮助对问题进行建模并使用 LP 求解器解决问题。LP 是一种必要的优化工具,在资源分配、生产规划、供应链以及 混合整数编程 (MIP) 求解器的中坚力量中都有应用。在某些情况下,使用数百万个变量和约束条件在数秒内解决数学问题具有挑战性,甚至不可能。
在 GPU 上高效解决 LP 问题有三个要求:
- 高效且大规模的并行算法
- NVIDIA GPU 库和 CUDA 功能
- 先进的 NVIDIA GPU
高效且大规模的并行算法
Dantzig 于 1947 年推出的 Simplex 仍然是大多数 LP 和 MIP 求解器的核心组件。它的工作原理是遵循可行区域的边缘来找到最优值。
下一个重大进步是 I. I. Dikin 在 1967 年发现的 内部点法 (IPM)。IPM 通过多面体内部向最佳方向移动,现在被认为是在 CPU 上求解大规模 LP 的先进技术。然而,这两种技术在大规模并行化方面都面临局限性。
2021 年,Google 研究团队推出了解决大型线性规划(LP)的新突破性技术: PDLP 。这是一种一阶方法(FOM),使用问题的导数迭代优化目标并最小化约束违反。
PDLP 通过引入预求解器、对角预处理、自适应重启和动态原始对偶步长选择等工具来改进收敛性,从而增强了 原始对偶混合梯度 (PDHG) 算法。预解和预处理使输入问题更加简单并提高了数值稳定性,而重启和动态步长计算则使求解器能够在优化期间进行自我调整。
与之前的方法相比,FOM 的一个主要优势是易于大规模并行化,因此非常适合 GPU 实现。
PDLP 采用两种高度并行的计算模式:Map 操作和稀疏矩阵向量乘法(SpMV)。这种方法使 PDLP 能够高效地并行处理数百万个变量和约束,使其在 GPU 上非常有效。
Map 在 PDLP 中广泛用于对所有变量和约束(可能涉及数百万个元素)执行加减法等操作。它在 GPU 上非常并行且高效。
SpMV 对应于将稀疏矩阵(包含许多零)与向量相乘。虽然此矩阵的大小可以达到数十亿,但其中包含的有用值却要少得多。例如,在种植蔬菜的问题中,“我不能种植超过 3.5 公斤的马铃薯”等约束在数百万个变量中只包含一个有用值。
SpMV 算法已针对 GPU 进行了广泛优化,使其比 CPU 实现快几个数量级。
NVIDIA GPU 库和 CUDA 功能
为了获得最佳性能,我们的 GPU PDLP 实现使用了先进的 CUDA 功能和以下 NVIDIA 库:
- cuSparse
- Thrust
- RMM
cuSparse 是 NVIDIA GPU 加速的稀疏线性代数库。它可以高效执行 SpMV,这是 GPU 上一项具有挑战性的任务。cuSparse 采用独特的算法,旨在充分利用 NVIDIA 的大规模并行架构。
Thrust 是 NVIDIA CUDA 核心计算库 (CCCL) 的一部分,提供高级 C++ 并行算法。它使用用于 GPU 执行的模式和迭代器来简化复杂算法的表达。我使用 Thrust 进行地图操作和重启过程,这需要按键对值进行排序。这是一项对 GPU 要求较高的任务,但已由 Thrust 进行了高效优化。
RMM 是快速灵活的 NVIDIA 内存管理系统,可通过使用内存池安全高效地处理 GPU 内存。
最后,我利用了先进的 CUDA 功能。在 GPU 上并行化 PDLP 的最大挑战之一是重启过程,该过程本质上是迭代的,不适合并行执行。为了解决这个问题,我使用了 CUDA 协作组 ,使您能够在各个级别定义 GPU 算法,其中最大的是包含所有工作程序的网格。通过实施协作内核启动和使用网格同步,能够在 GPU 上高效、优雅地表达迭代重启过程。
先进的 NVIDIA GPU
GPUs 通过使用数千个线程并行解决许多问题来实现快速计算。然而,在处理之前,GPU 必须先将数据从主内存传输到其工作线程中。
内存带宽 是指每秒可以传输的数据量。CPU 通常可以处理数百 GB/秒,而最新的 GPU NVIDIA HGX B100 的带宽为 8 GB/秒,高出两个数量级。
由于严重依赖 Map 和 SpMV 等内存密集型计算模式,此 PDLP 实施的性能会直接随着内存带宽的增加而扩展。随着未来 NVIDIA GPU 带宽的增加,PDLP 将自动变得更快,与其他基于 CPU 的 LP 求解器不同。
cuOpt 在 Mittelmann 基准测试中优于最先进的 CPU LP 求解器
对 LP 求解器的速度进行基准测试的行业标准是 Mittelmann 基准测试 。其目标是在尽可能短的时间内遵循限制条件,确定 LP 函数的最佳值。基准测试问题代表各种场景,包含数十万到数千万个值。
为了进行比较,我运行了一台先进的 CPU LP 求解器,并将其与此 GPU LP 求解器进行了比较。我使用相同的阈值 10^-4,并禁用了交叉。有关更多信息,请参阅本文后面的“ PDLP 精炼潜力 ”部分。
这两个求解器均在 float64
精度下运行。
- 对于 CPU LP 求解器,我使用了推荐的 CPU 设置:具有 16 个核心和 256 GB DDR4 内存的 AMD EPYC 7313P 服务器。
- 对于 cuOpt LP 求解器,我使用了 NVIDIA H100 SXM Tensor Core GPU,以利用高带宽,并且在没有预解析的情况下运行。
我考虑了不使用 I/O 的完整求解时间,包括两个求解器的扩展和 CPU LP 求解器的预求解。图 4 仅显示了为两个求解器收敛且具有正确目标值的实例。在 60% 的实例中,cuOpt 的速度更快,在 20% 的实例中,速度快 10 倍以上。在一个大型多商品流优化问题的实例中,最大的加速是 5000 倍。
我还在相同的设置和条件下,将 cuOpt 与先进的 CPU PDLP 实现方案进行了比较。cuOpt 的速度持续提高,速度提高了 10 倍到 3000 倍。
多商品流问题(MCF)涉及找到一种最有效的方法,将多种不同类型的商品从不同的起点路由到各自的目的地,确保不超过网络的容量限制。一种解决 MCF 问题的方法是将其转换为线性规划(LP)。在一组大型 MCF 实例中,PDLP 的速度始终保持在 10 倍到 300 倍之间。
PDLP 细化潜力
NVIDIA cuOpt LP 求解器提供令人惊叹的性能,但未来仍有可能进行增强:
- 处理更高的准确性
- 需要高带宽
- 一些收问题
- 小型 LP 权益有限
处理更高的准确性
要确定您是否已解决 LP 问题,您需要衡量两件事:
- 最优差距: 测量您距离找到目标函数最优值的程度。
- 可行性: 测量遵守限制条件的程度。
当两个数量均为 0 时,LP 被视为已解决。达到精确的 0 值可能很具有挑战性,而且通常没有必要,因此 LP 求解器使用的阈值可以在保持准确性的同时实现更快的收敛。现在,两个数量只需低于此阈值,即相对于问题值的大小而言。
大多数 LP 求解器都使用阈值,尤其是对于非常具有挑战性的大问题。到目前为止,行业标准是使用 10^-8。虽然 PDLP 可以使用 10^-8 来解决问题,但通常速度要慢得多。如果您需要高精度,这可能会成为问题。在实践中,许多人发现 10^-4 的准确度足够高,有时甚至更低。这对 PDLP 大有益,同时对于其他 LP 求解算法来说并不是一个很大的区别。
需要高带宽
PDLP 的性能随内存带宽呈线性扩展,因此在新 GPU 架构上更高效。它需要最近的服务器级 GPU 来重现性能分析部分中显示的结果。
关于某些问题的收敛问题
虽然 PDLP 可以快速求解大多数 LP,但有时需要大量步骤才能收敛,从而导致更高的运行时间。在 Mittelmann 的基准测试中,由于收敛速度慢,cuOpt LP 求解器在 49 个公共实例中的 8 个实例上超时 1 小时。
小型 LP 权益有限
与 CPU 求解器相比,GPU 的高带宽使 Small LPs 无法进行扩展,因此 Small LPs 受益更少。cuOpt LP 求解器为此场景提供了一种批量模式,您可以在其中并行提供并求解数百个 Small LPs。
结束语
cuOpt LP 求解器使用 CUDA 编程、NVIDIA GPU 库和最先进的 NVIDIA GPU 来求解 LP,其速度可能比 CPU 快几个数量级,并可扩展到超过 10 亿个系数。因此,它对于解决大规模问题特别有用,因为在这些问题中,其优势变得更加突出。
在传统的 Simplex 或 IPM 中,某些用例的效果仍然更好,我希望未来的求解器能够结合 GPU 和 CPU 技术。
注册以在 您试用 NVIDIA cuOpt LP 时收到通知。立即通过 NVIDIA 托管的 NIM 微服务试用 NVIDIA cuOpt Vehicle Routing Problem (VRP),在 NVIDIA API Catalog 上免费获取最新的 AI 模型。