Simultaneous Solving of Batched Linear Programs on a GPU
Simultaneous Solving of Batched Linear Programs on a GPU
复制标题
在 GPU 上同时求解批量线性程序
DOI：
10.1145/3297663.3310308
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Rajarshi Ray
中科院分区：
文献类型：
--
作者：
Amit Gurung;Rajarshi Ray
线性规划（Linear Programs，LP）在很多应用中出现。将LP求解任务卸载到GPU对于加速应用程序的性能是可行的。在GPU上卸载和求解LP的现有工作表明，性能只能针对大型LP（通常为500个约束，500个变量及以上）进行加速。本文的动机是从应用程序必须解决小LP，但其中许多。现有技术无法使用GPU加速此类应用。我们提出了一个批处理的LP求解器在CUDA加速这样的应用程序，并证明其效用的用例-状态空间探索模型的控制系统设计。还显示了使用开源求解器GLPK（GNU线性编程工具包）和IBM的CPLEX求解器在CPU中进行批量LP求解器与顺序求解的性能比较。对Netlib库中选定的LP基准测试的评估显示，对于一批1 e5 LP，CPLEX和GLPK求解器的最大速度分别为95倍和5倍。
Linear Programs (LPs) appear in a large number of applications. Offloading the LP solving tasks to a GPU is viable to accelerate an application's performance. Existing work on offloading and solving an LP on a GPU shows that performance can be accelerated only for large LPs (typically 500 constraints, 500 variables and above). This paper is motivated from applications having to solve small LPs but many of them. Existing techniques fail to accelerate such applications using GPU. We propose a batched LP solver in CUDA to accelerate such applications and demonstrate its utility in a use case - state-space exploration of models of control systems design. A performance comparison of The batched LP solver against sequential solving in CPU using the open source solver GLPK (GNU Linear Programming Kit) and the CPLEX solver from IBM is also shown. The evaluation on selected LP benchmarks from the Netlib repository displays a maximum speed-up of 95x and 5x with respect to CPLEX and GLPK solver respectively, for a batch of 1e5 LPs.
影响因子：
3
作者：
G. Yan;Jie Tian;Shouping Zhu;Yakang Dai;C. Qin
通讯作者：
G. Yan;Jie Tian;Shouping Zhu;Yakang Dai;C. Qin
影响因子：
3.8
作者：
Birk, Matthias;Dapp, Robin;Becker, J.
通讯作者：
Becker, J.