The Analysis and Implementation of Parallel Hybrid Model with MPI and OpenMP on Conjugate Gradient Method

Abstract

Conjugate Gradient method is one of the iterative methods to solve linear equation system. The method consumes much time to get the solution. Therefore to reduce its execution time, parallel processing is implemented on this method. There was a research related to this topic by Hoefler et al (2007). On their research, they were optimizing a pure MPI implementation by modifying collective functions into a non-blocking collective communication. This research used parallel hybrid model by combining MPI and OpenMP. The aim of this research is to analyze and implement the complexity and the performance of sequential, MPI and hybrid conjugate gradient algorithm. The analysis performed in this research includes the analysis of performance metrics and the experimental results of every implementation. This research uses 8 computers for running MPI processes and for hybrid experiment added 4 threads for running OpenMP on every computer. There are five matrices uses in this research obtained from matrices collection of University of Florida. The results of this research show that the execution time of all implementation for matrices with greater sizes give longer time. For example, on sequential implementation a matrice size of 2548 x 2548 takes 28.94 seconds and a matrice size of 4884 x 4884 takes 48.24 seconds. The execution time of MPI conjugate gradient is less than its sequential implementation, and the execution time of hybrid conjugate gradient is less than its MPI conjugate gradient. The speedup of MPI and hybrid conjugate gradient grows but not proportionally with the increasing size of matrices used. The overall result of hybrid implementation is quite good when the number of thread used is the same as the number of processor available on the computer.