Parallelizing Matrix Exponential based Algorithm using Cilk Plus

Abstract

Matrix exponential based algorithm (MEXP) is a recently developed method for solving a positive de nite system of linear equations. The MEXP was de- signed to have computations that are readily parallelizable on customizable hardware platforms such as eld-programmable gate arrays (FPGAs) and application speci c integrated circuits (ASIC). It has been shown that if the parallelism of MEXP is exploited on an FPGA it outperform other state of the art algorithms, such as the Preconditioned Conjugate Gradient method (PCG), for most of the cases. In this research we analyze the performance of MEXP on multicore hardware platforms using a shared-memory model called Cilk and compare it with PCG and CG (Conjugate Gradient with- out preconditioner). Our parallel implementation of MEXP outperforms the Cilk based parallel PCG and parallel CG in terms of parallelism and execu- tion time as the numbers of threads are increased. The comparison of the performance for the tested benchmark problems shows that parallel MEXP relatively gives almost 3 times more speedup than parallel PCG and 5 to 7 times more speedup than parallel CG. Thus, our performance evaluation shows that MEXP is more parallelizable and scalable than both PCG and CG. The parallelized version of MEXP is also applied to two real-world appli- cations which are Heat Equation and Riccati-Recursion. The parallel MEXP based heat equation and riccati-recursion solvers show higher parallelism val- ues than the parallel Cholesky Decomposition (CD) based heat equation and riccati-recursion solvers. In case of riccati-recursion, parallel MEXP based solution gives almost 2 times more relative speedup than of parallel CD based solution.