Matrix-vector multiplication and triangular linear solver using GPGPU for symmetric positive definite matrices derived from elliptic equations


Autoria(s): Martins, Thiago de Castro; Kian, Jacqueline de Miranda; Sato, André Kubagawa; Tsuzuki, Marcos de Sales Guerra
Data(s)

14/03/2014

14/03/2014

14/03/2014

Resumo

The modern GPUs are well suited for intensive computational tasks and massive parallel computation. Sparse matrix multiplication and linear triangular solver are the most important and heavily used kernels in scientific computation, and several challenges in developing a high performance kernel with the two modules is investigated. The main interest it to solve linear systems derived from the elliptic equations with triangular elements. The resulting linear system has a symmetric positive definite matrix. The sparse matrix is stored in the compressed sparse row (CSR) format. It is proposed a CUDA algorithm to execute the matrix vector multiplication using directly the CSR format. A dependence tree algorithm is used to determine which variables the linear triangular solver can determine in parallel. To increase the number of the parallel threads, a coloring graph algorithm is implemented to reorder the mesh numbering in a pre-processing phase. The proposed method is compared with parallel and serial available libraries. The results show that the proposed method improves the computation cost of the matrix vector multiplication. The pre-processing associated with the triangular solver needs to be executed just once in the proposed method. The conjugate gradient method was implemented and showed similar convergence rate for all the compared methods. The proposed method showed significant smaller execution time.

AK Sato was supported by FAPESP (grant 2010/19646-0). JM Kian was supported by FAPESP (grant 2011/01194-8). MSG Tsuzuki was partially supported by the CNPq (grant 309.570/2010–7). This work was supported by FAPESP under grants 2009/07173-2 and 2010/14699-0

Identificador

9781467327428

http://www.producao.usp.br/handle/BDPI/44134

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6505077

Idioma(s)

eng

Publicador

Kobe

Relação

International Conference on Soft Computing and Intelligent Systems, 6. and International Symposium on Advanced Intelligent Systems, 13.

Direitos

restrictedAccess

Attribution-NonCommercial-NoDerivs 3.0 Brazil

http://creativecommons.org/licenses/by-nc-nd/3.0/br/

IEEE

Palavras-Chave #Massive Parallelization #GPGPU #Sparse Matrix #Matrix-Vector Multiplication #SISTEMAS LINEARES #ARQUITETURAS PARALELAS #ALGORITMOS
Tipo

conferenceObject

Palestra