Parallelization of uniformization algorithm with CUDA-aware MPI

Uniformization is one of the best methods for computing the transient probabilities of continuous-time Markov chains. In this paper, we propose a method for parallelizing uniformization by performing its computation on graphic processing units residing on several computers communicating with each other via message passing interface. Since Markov chain models are usually sparse, hypergraph partition is used to reduce communications among the computers when performing repeated sparse matrix-vector multiplication operations. This method of parallelization in principle allows for unlimited scalability while still maintains computation speed. Indeed, our results show that the proposed method can solve large models faster. However, our results also show that up to 90 of the computation time is actually still spent for communications between computers.