high performance computing on graphics processing units: hgpu.org

Linear Programs (LPs) appear in a large number of applications and offloading them to the GPU is viable to gain performance. Existing work on offloading and solving an LP on GPU suggests that performance is gained from large sized LPs (typically 500 constraints, 500 variables and above). In order to gain performance from GPU for applications involving small to medium sized LPs, we propose batched solving of a large number of LPs in parallel. In this paper, we present the design and CUDA implementation of our batched LP solver library, keeping memory coalescent access, reduced CPU-GPU memory transfer latency and load balancing as the goals. The performance of the batched LP solver is compared against sequential solving in the CPU using an open source solver GLPK (GNU Linear Programming Kit). The performance is evaluated for three types of LPs. The first type is the initial basic solution as feasible, the second type is the initial basic solution as infeasible and the third type is the feasible region as a Hyperbox. For the first type, we show a maximum speedup of 18.3x when running a batch of 50k LPs of size 100 (100 variables, 100 constraints). For the second type, a maximum speedup of 12x is obtained with a batch of 10k LPs of size 200. For the third type, we show a significant speedup of 63x in solving a batch of nearly 4 million LPs of size 5 and 34x in solving 6 million LPs of size 28. In addition, we show that the open source library for solving linear programs-GLPK, can be easily extended to solve many LPs in parallel with multi-threading. The thread parallel GLPK implementation runs 9.6x faster in solving a batch of 1e5 LPs of size 100, on a 12-core Intel Xeon processor. We demonstrate the application of our batched LP solver in the domain of state-space exploration of mathematical models of control systems design.