Simplex Parallelization in a Fully Hybrid Hardware Platform
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 4
Abstract
The simplex method has been successfully used in solving linear programming (LP) problems for many years. Parallel approaches have also extensively been studied due to the intensive computations required, especially for the solution of large LP problems. Furthermore, the rapid proliferation of multicore CPU architectures as well as the computational power provided by the massive parallelism of modern GPUs have turned CPU / GPU collaboration models increasingly into focus over the last years for better performance. In this paper, a highly scalable implementation framework of the standard full tableau simplex method is first presented, over a hybrid parallel platform which consists of multiple multicore nodes interconnected via a high-speed communication network. The proposed approach is based on the combined use of MPI and OpenMP, adopting a suitable column-based distribution scheme for the simplex tableau. The parallelization framework is then extended in such a way that it can exploit concurrently the full power of the provided resources on a multicore single-node environment with a CUDA-enabled GPU (i.e. using the CPU cores and the GPU concurrently), based on a suitable hybrid multithreading/GPU offloading scheme with OpenMP and CUDA. The corresponding experimental results show that the hybrid MPI+OpenMP based parallelization scheme leads to particularly high speed-up and efficiency values, considerably better than in other competitive approaches, and scaling well even for very large / huge linear problems. Furthermore, the performance of the hybrid multithreading/GPU offloading scheme is clearly superior to both the OpenMP-only and the GPU-only based implementations in almost all cases, which validates the worth of using both resources concurrently. The most important, when it is used in combination with MPI in a multi-node (fully hybrid) environment, it leads to substantial improvements in the speedup achieved for large and very large LP problems.
Authors and Affiliations
Basilis Mamalis, Marios Perlitis
Keywords
Related Articles
- EP ID EP258366
- DOI 10.14569/IJACSA.2017.080449
- Views 122
- Downloads 0
A Study of Mobile Forensic Tools Evaluation on Android-Based LINE Messenger
The limitation of forensic tool and the mobile device’s operating system are two problems for researchers in mobile forensics field. Nevertheless, some kinds of forensic tools testing in several devices might be helpful...
Secure Deletion of Data from SSD
The deletion of data from storage is an important component on data security. The deletion of entire disc or special files is well-known on hard drives, but this is quite different on SSDs, because they have a different...
Long-Term Weather Elements Prediction in Jordan using Adaptive Neuro-Fuzzy Inference System (ANFIS) with GIS Techniques
Weather elements are the most important parameters in metrological and hydrological studies especially in semi-arid regions, like Jordan. The Adaptive Neuro-Fuzzy Inference System (ANFIS) is used here to predict the mini...
Service Design for Developing Multimodal Human-Computer Interaction for Smart Tvs
A Smart TV integrates Internet and Web features into a TV, as well convergence between computer and TV and can utilize as a computer. Smart TV devices facilitate the curation of content by combining Internet-based inform...
A Novel Ball on Beam Stabilizing Platform with Inertial Sensors
This research paper presents dynamic modeling of inertial sensor based one degree of freedom (1-DoF) stabilizing platform. Plant is a ball on a pivoted beam. Nonlinear modeling of the plant is done. Ball position on beam...