Matrix-Vector Multiplication and Triangular Linear Solver Using GPGPU for Symmetric Positive Definite Matrices Derived from Elliptic Equations

Autor(es)

Martins, Thiago de Castro ; Kian, Jacqueline de Miranda ; Sato, Andre Kubagawa ; Guerra Tsuzuki, Marcos de Sales ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 6TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS, AND THE 13TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS; v. N/A, p. 6-pg., 2012-01-01.

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. (AU)

• Processo FAPESP: 11/01194-8 - Paralelização Massiva do Método dos Gradientes Conjugados Pré-Condicionado para reconstrução de Imagens de Tomografia Por Impedância Elétrica
• Beneficiário: Jacqueline de Miranda Kian
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Processo FAPESP: 10/19646-0 - Translações Aplicadas a Polígonos de Obstrução para que Regiões Livres de Colisão Degeneradas Sejam Criadas por Operações Booleanas Não Regularizadas
• Beneficiário: André Kubagawa Sato
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 09/07173-2 - Aplicação do recozimento simulado à tomografia por impedância elétrica para a obtenção de imagens absolutas
• Beneficiário: Marcos de Sales Guerra Tsuzuki
• Modalidade de apoio: Auxílio à Pesquisa - Regular