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

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.Ł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