GPU Revised Simplex Solver
Description #
Project for Design of Parallel and High Performance Computing. In a team of five we implemented multiple variants of the revised simplex method on an NVIDIA GPU and compared them against established LP solvers.
Simplex is an awkward fit for a GPU: it is inherently sequential at the level of pivots, and each iteration’s work depends on the one before. The parallelism has to come from inside an iteration — the pricing step that picks the entering variable, the ratio test, and the dense linear algebra on the basis — which is what the different variants trade off against each other.
Implementation used a mix of cuBLAS/cuSPARSE routines and our own CUDA kernels where the library primitives did not fit the access pattern. Final benchmarks ran on a shared local machine, with each configuration in its own Docker container so runs stayed isolated and reproducible across the team.
As the final paper was part of the performance assessment of the course, a copy can be provided on request.