Computational aspects of GPU - accelerated sparse matrix - vector multiplication for solving Markov models

• Autorzy: Bylina B. , Bylina J. , Karwacki M.

Warianty tytułu

PL

Obliczeniowe aspekty mnożenia macierzy rzadkiej przez wektor dla rozwiązywania modeli Markowa przyspieszanego przez karty GPU

• Języki publikacji: EN

Abstrakty

EN

In this article we investigate some computational aspects of GPU-accelerated matrix-vector multiplication where matrix is sparse. Particularly, we deal with sparse matrices appearing in modelling with Markovian queuing models. The model we use for research is a Markovian queuing model of a wireless device. This model describes the device’s behavior during possible channel occupation by other devices. We study the efficiency of multiplication of a sparse matrix by a dense vector with the use of an appropriate, ready-to-use GPU-accelerated mathematical library, namely CUSP. For the CUSP library we discuss data structures and their impact on the CUDA platform for the fine-grained parallel architecture of the GPU. Our aim is to find the best format for storing a sparse matrix for GPU-computation (especially one associated with the Markovian model of a wireless device). We compare the time, the performance and the speed-up for the card NVIDIA Tesla C2050 (with ECC ON). For unstructured matrices (as our Markovian matrices), we observe speed-ups (in respect to CPU-only computations) of over 8 times.

PL

Łańcuchy Markowa są przydatnym narzędziem do modelowania systemów złożonych, takich jak systemy i sieci komputerowe. W ostatnich latach łańcuchy Markowa zostały z powodzeniem wykorzystane do oceny pracy sieci bezprzewodowych. Jednym z problemów jaki się pojawia przy wykorzystywaniu łańcuchów Markowa w modelowaniu sieci są problemy natury obliczeniowej. W artykule zajmiemy się badaniem mnożenia macierzy rzadkiej przez wektor, które jest jedną z głównych operacji podczas numerycznego rozwiązywania modeli Markowowskich. Aby, przyspieszyć czas obliczeń mnożenia macierz rzadkiej przez wektor wykorzystano funkcje z biblioteki CUSP. Biblioteka jest zbiorem funkcji wykonywanych na GPU (ang.Graphics Processing Unit) celem skrócenia czasu obliczeń. Do testowania operacji mnożenia macierzy rzadkiej przez wektor badano macierze z Markowowskiego modelu pracy sieci bezprzewodowej. Model ten opisuje zachowanie urządzenia, gdy kanał transmisyjnych może być zajęty przez inne urządzenia. Macierz przejść wspomnianego modelu jest macierzą rzadką i potrzeba specialnej struktury danych do jej przechowywania, dlatego w artykule dyskutowane są różne struktury danych dla macierzy rzadkich i ich przydatność do obliczen na kartach graficznych. W pracy porównano czas, wydajność i przyspieszenie jakie otrzymano podczas testowania biblioteki CUSP na karcie NVIDIA Tesla C2050 dla niestrukturalnych macierzy rzadkich opisujących model zajętości węzła w sieciach bezprzewodowych przy różnych formatach przechowywania macierzy rzadkich. Dla testowanych macierzy zauważono ośmiokrotne przyspieszenie obliczeń przy wykorzystaniu karty graficznej.

Słowa kluczowe

EN

Markovian models; wireless network models; GPU; matrix-vector multiplication; sparse matrices

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2011
• Tom: Vol. 23, No. 2
• Strony: 127--145
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Bylina B.

autor

Bylina J.

autor

Karwacki M.

• Institute of Mathematics Marie Curie-Skłodowska University Pl. M. Curie-Skłodowskiej 5, 20-031 Lublin, Poland,

Bibliografia

• 1. J. Barnat, L. Brim, M. Ceska: DiVinE-CUDA — a tool for GPU accelerated LTL model checking, Proceedings of the 8th International Workshop on Parallel and Distributed Methods in Verification (PDMC’09), Eindhoven, November 2009, pp. 107-111.
• 2. N. Bell, M. Garland: Efficient Sparse Matrix-Vector Multiplication on CUDA, NVIDIA Tech. Report No. NVR-2008-004, 2008.
• 3. G. Bianchi: Performance Analysis of the IEEE 802.11 Distributed Coordination Function, IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, March 2000, pp. 535-547.
• 4. J. Bylina, B. Bylina: A Markovian Queuing Model of a WLAN Node, CCIS 160, Computer Networks 2011, pp. 80-86.
• 5. IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Nov. 1997, P80211.
• 6. B. R. C. Magalhaes, N. J. Dingle,W. J. Knottenbelt: GPU-enabled steady-state solution of large Markov models., 6th International Workshop on the Numerical Solution of Markov Chains (NSMC’10), 16-17 Sep 2010, Williamsburg, Virginia.
• 7. NVIDIA Corporation. CUDA Programming Guide. NVIDIA Corporation, 2009.http://www.nvidia.com/
• 8. 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).
• 9. W. J. Stewart: Introduction to the numerical solution of Markov chains, Princeton University Press, Princeton, NJ, 1994.
• 10. L.-C. Wang, S.-Y. Huang, A. Chen: On the Throughput Performance of CSMA-based Wireless Local Area Network with Directional Antennas and Capture Effect: A Crosslayer Analytical Approach, WCNC 2004 / IEEE
• 11. M. Wozniak, T. Olas, R. Wyrzykowski: Parallel Implementation of Conjugate Gradient Method on Graphics Processors, LNCS, PPAM 2009.
• 12. http://alice.loria.fr/index.php/software/4-library//23-opennl.html
• 13. http://code.google.com/p/cudpp/
• 14. http://code.google.com/p/cusp-library/
• 15. http://developer.nvidia.com/cuda-toolkit-40
• 16. http://software.intel.com/en-us/articles/intel-mkl/
• 17. http://www.cs.purdue.edu/ellpack/
• 18. http://www.mathworks.com/
• 19. http://www.nvidia.com/content/NV_Research/matrices.zip