A Hybrid Parallelization Scheme for Standard Simplex Method based on CPU/GPU Collaboration
Basilis Mamalis, Marios Perlitis · 2016
The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches have also extensively been studied due to the intensive computations required, especially for the solution of large problems. The rapid proliferation of multicore CPU architectures as well as the computational power provided by the massive parallelism of modern GPUs have turned OpenMP and CUDA programming models increasingly into focus over the last years. However, the efficient CPU/GPU collaboration through the combined use of the above programming models still remains a major research challenge. In this paper we present a highly efficient parallel implementation of the standard simplex method, which can exploit concurrently the full power of the provided resources, on a multicore platform with a CUDA-enabled GPU. Specifically, we present three suitable parallel schemes, (a) a multi-threading one based on OpenMP, (b) a GPU-offloading scheme based on CUDA, and (c) a hybrid multi-threading/GPU offloading scheme. The experimental results show that the performance of our GPU-based implementation is comparable to other relevant works in the literature, and superior to our OpenMP-based implementation. The most important, the performance of our hybrid multi-threading/GPU offloading scheme is clearly superior to the GPU-based only implementation in almost all cases, which validates the worth of using both resources concurrently.