Multi-GPU Implementation of the Uniformization Method for Solving Markov Models
Institute of Mathematics, Marie Curie-Sklodowska University, Pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland
Preprints of the Federated Conference on Computer Science and Information Systems pp. 561-565, 2012
@article{karwacki2012multi,
title={Multi-GPU Implementation of the Uniformization Method for Solving Markov Models},
author={Karwacki, Marek and Bylina, Beata and Bylina, Jaroslaw},
year={2012}
}
Markovian models can generate very large sparse matrices, which are difficult to store and solve. A useful method for finding transient probabilities in Markovian models is the uniformization. The aim of this paper is to show that the performance of the uniformization can be improved using multiGPU architecture. We propose partitioning scheme for HYB sparse matrix storage format and some optimization techniques adjusted so as to minimize communication between GPUs during iterative sparse matrix-vector multiplication, which is the most time consuming step. The results of experiments show that on multi-GPU we can solve larger matrices than on single device and accelerate computations in comparison to a multithreaded CPU. Computational test have been carried out in double precision for a wireless network models. Using multi-GPU we were able to solve model which is described by a matrix of the size 3.6×10^7.
August 31, 2012 by hgpu
