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 106
- Downloads 0
Towards Analytical Modeling for Persuasive Design Choices in Mobile Apps
Persuasive technology has emerged as a new field of research in the past decade with its applications in various domains including web-designing, human-computer interaction, healthcare systems, and social networks. Altho...
Evaluation of Fault Tolerance in Cloud Computing using Colored Petri Nets
Nowadays, the necessity of rendering reliable services to the customers in business markets is assumed as a crucial matter for the service providers, and the importance of this subject in many fields is undeniable. Desig...
An Agent-based Simulation for Studying Air Pollution from Traffic in Urban Areas: The Case of Hanoi City
In urban areas, traffic is one of the main causes of air pollution. Establishing an effective solution to raise public awareness of this phenomenon could help to significantly reduce the level of pollution in urban areas...
Organizing Multipath Routing in Cloud Computing Environments
One of the objectives of organizing cloud systems is to ensure effective access to remote resources by optimizing traffic engineering (TE) procedures. This paper considers the traffic engineering problem in a cloud envir...
Modelling for Forest Fire Evolution Based on the Energy Accumulation and Release
Forest fire evolution plays an important role in the decision-making of controlling the forest fire. This paper aims to simulate the dynamics of the forest fire spread using a cellular automaton approach. Having analyzed...