A Hybrid Multi-GPU Implementation of Simplex Algorithm with CPU Collaboration
Preprint
Abstract
The simplex algorithm has been successfully used for many years in solving linear programming (LP) problems. Due to the intensive computations required (especially for the solution of large LP problems), parallel approaches have also extensively been studied. The computational power provided by the modern GPUs as well as the rapid development of multicore CPU systems have led OpenMP and CUDA programming models to the top preferences during the last years. However, the desired efficient collaboration between CPU and GPU through the combined use of the above programming models is still considered a hard research problem. In the above context, we demonstrate here an excessively efficient implementation of standard simplex, targeting to the best possible exploitation of the concurrent use of all the computing resources, on a multicore platform with multiple CUDA-enabled GPUs. More concretely, we present a novel hybrid collaboration scheme which is based on the concurrent execution of suitably spread CPU-assigned (via multithreading) and GPU-offloaded computations. The experimental results extracted through the cooperative use of OpenMP and CUDA over a notably powerful modern hybrid platform (consisting of 32 cores and two high-spec GPUs, Titan Rtx and Rtx 2080Ti) highlight that the performance of the presented here hybrid GPU/CPU collaboration scheme is clearly superior to the GPU-only implementation under almost all conditions. The corresponding measurements validate the value of using all resources concurrently, even in the case of a multi-GPU configuration platform. Furthermore, the given implementations are completely comparable (and slightly superior in most cases) to other related attempts in the bibliography, and clearly superior to the native CPU-implementation with 32 cores.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Revised simplex algorithm for linear programming on GPUs with CUDAMultimedia Tools and Applications, 2018
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- Efficient GPU-based implementations of simplex type algorithmsApplied Mathematics and Computation, 2015
- MPI + MPI: a new hybrid approach to parallel programming with MPI plus shared memoryComputing, 2013
- Parallel distributed-memory simplex for large-scale stochastic LP problemsComputational Optimization and Applications, 2013
- Parallel Processing and Applied Mathematics2012
- Hybrid CUDA, OpenMP, and MPI parallel programming on multicore GPU clustersComputer Physics Communications, 2011
- Towards a practical parallelisation of the simplex methodComputational Management Science, 2008
- A parallel interior point decomposition algorithm for block angular semidefinite programsComputational Optimization and Applications, 2008
- A parallel-vector simplex algorithm on distributed-memory computersStructural and Multidisciplinary Optimization, 1996