Performance Analysis of Benchmarks for GPU-based Linear Programming Problem Solvers

摘要

The single instruction multiple threads (SIMT) architecture of modern graphics processing units (GPUs) shows great potential for efficiently solving compute-intensive linear programming (LP) problems. For benchmarking these GPU-based solutions, speedup is used to measure their relative performance gains with respect to CPU-based implementations. However, a methodological flaw has been observed in benchmarking these GPU-based LP problem solvers, namely, the magnitude of their speedup varies with the choice of CPU-based benchmark. In this paper, we analyze the performance of CPU-based LP problem solvers used to benchmark their GPU-based counterparts. More specifically, we consider benchmarks of two established GPU-based solutions for revised simplex method. The first solution is based on general-purpose computing on GPUs (GPGPU) programming model, and uses a custom-built CPU-based solution as benchmark. The second solution is an OpenGL-based solver, and uses the LP utility in GNU linear programming kit (GLPK) as benchmark. Further, we performed experiments to compare the efficiency of these CPU-based benchmarks with an LP tool present in a commercially available CPU-based software package called CPLEX. Our study reveals that the use of nonstandard benchmarks makes it unfair to quantitatively compare the claims made about speedups achieved by various GPU-based solvers. In order to facilitate decision making process for potential users of GPU-based solutions, we recommend that standard sequential benchmarks be used during any future attempts at developing GPU-based linear optimization tools.