Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

An effective sparse storage scheme for GPU-enabled uniformization method

, ,

DOI: http://dx.doi.org/10.15439/2018F271

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 307–310 ()

Full text

Abstract. The authors developed a GPU approach to the uniformization method for the computing transient solution of Markov models. The authors use two techniques to reduce the memory size of storing matrices. One of them is a modification of a storage sparse matrix format HYB; second is to utilize two GPU cards and the multicore CPU. The modified HYB format is suitable for sparse Markovian transition rate matrices and oversized matrices on single GPU, also improving computation performance at the same time. The use of two GPUs enables processing matrices of even bigger sizes.

References

  1. Bylina, B., Bylina, J., Karwacki, M.: Computational Aspects of GPU-accelerated Sparse Matrix-Vector Multiplication for Solving Markov Models. Theoretical and Applied Informatics 23, 127–145 (2011)
  2. Bylina, B., Karwacki, M., Bylina, J.: A CPU-GPU Hybrid Approach to the Uniformization Method for Solving Markovian Models — A Case Study of a Wireless Network. In: Kwiecień, A., Gaj, P., Stera, P. (eds.) CN 2012. CCIS, vol. 291, pp. 401–410. Springer, Heidelberg (2012)
  3. Bylina, B., Karwacki, M., Bylina, J.: Multi-GPU Implementation of the Uniformization Method for Solving Markov Models. In: Proceedings of Federated Conference on Computer Science and Information Systems (FedCSIS) 2012, pp. 533–537 (2012)
  4. Bylina, J., Bylina, B., Karwacki, M.: An Efficient Representation on GPU for Transition Rate Matrices for Markov Chains; Lecture Notes in Computer Science 8384, 663–672. Springer, Heidelberg (2014)
  5. G. Ciardo and M. Tilgner.: On the use of Kronecker Operators for the Solution of Generalized Stochastic Petri Nets. ICASE Report 96-35, Institute for Computer Applications in Science and Engineering, 1996.
  6. N. J. Dingle, P. G. Harrison, W. J. Knottenbelt: Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models, Journal of parallel and distributed computing, 64 (2004), 908-920
  7. Fernandes, P., Plateau, B., Stewart, W.J.: Efficient Descriptor-Vector Multiplication in Stochastic Automata Networks. J. ACM 45, 381–414 (1998)
  8. M. Z. Kwiatkowska, G. Norman, D. Parker: PRISM: Probabilistic Symbolic Model Checker, Computer Performance Evaluation, Modelling Techniques and Tools 12th International Conference, TOOLS 2002, LNCS 2324, pp.200-204, Springer, 2005.
  9. Resing, J. A. C. (1993). Polling systems and multitype branching processes. Queueing Systems 13 (4): 409–426
  10. H. Hermanns, J. Meyer-Kayser and M. Siegle. Multi Terminal Binary Decision Diagrams to Represent and Analyse Continuous Time Markov Chains. In B. Plateau and W. Stewart and M. Silva (editors), Proc. 3rd International Workshop on Numerical Solution of Markov Chains (NSMC’99), pages 188-207, Prensas Universitarias de Zaragoza. 1999.
  11. R. B. Sidje: Expokit: A software package for computing matrix exponentials, ACM Trans. Math. Software, 24 (1998), pp. 130–156.
  12. R. B. Sidje, K. Burrage, S. MacNamara: Inexact Uniformization Method for Computing Transient Distributions of Markov Chains. SIAM J. Scientific Computing 29(6): 2562–2580 (2007).
  13. Intel Math Kernel Library, http://software.intel.com/en-us/articles/intel-mkl/