O Problema Direto da TIE Paralelizável em GPU Utilizando o Formato Matricial {p}JDS Colorido para matrizes esparsas

Renato Seiji Tavares¹; Thiago de Castro Martins¹; Edson Kenji Ueda¹; André Kubagawa Sato¹; Rogério Yugo Takimoto¹; Raul Gonzalez Lima¹; Marcos de Sales Guerra Tsuzuki¹

¹ Escola Politécnica da Universidade de São Paulo

Baixar PDF

Resumo

A Tomografia por Impedância Elétrica (TIE) é uma técnica de imageamento que reconstroi a distribuição da condutividade interna a um objeto a partir da injeção de corrente e medição de potencial elétrico na superficie do objeto. Este trabalho utiliza o gradiente conjugado precondicionado para solucionar o problema direto, e possui dois principais módulos: multiplicação matriz esparsa por vetor e solucionador triangular. O problema principal é a solução de sistema linear com matriz esparsa definida positiva simétrica. Várias abordagens utilizam a formato CSR que apresenta divergência de threads quando o solucionador triangular é executado. Neste trabalho, é proposta uma nova representação para matrizes esparsas que elimina a divergência de threads e realiza acesso à memoria exclusivamente sequencial e alinhados. A nova representação foi denominada como colored jagged diagonals storage. Os resultados demonstram o elevado desempenho da nova representação.

Palavras-chave: GPGPU; CUDA; Processamento Paralelo; Coloração de Grafos; Tomografia por Impedância Elétrica