Parallel Implementations of RCM Algorithm for Bandwidth Reduction of Sparse Matrices

AUTOR(ES)

RODRIGUES, T.N., BOERES, M.C.S., CATABRIGA, L.

FONTE

TEMA (São Carlos)

DATA DE PUBLICAÇÃO

2017-12

RESUMO

RESUMO O algoritmo Reverse Cuthil-McKee (RCM) constitui uma heurística bem conhecida para o reordenamento de matrizes esparsas. Ele é tipicamente aplicado para a melhoria do desempenho da computação de sistemas lineares de equações. Este artigo descreve duas abordagens paralelas propostas para o algoritmo Reverse Cuthill-McKee, assim como versões otimizadas baseadas em alguns aprimoramentos propostos. Na primeira abordagem há a exploração de uma estratégia para a redução de threads ociosas, enquanto a segunda abordagem faz uso de um bucket array estático como estrutura de dados principal, além de suprimir algumas etapas do algoritmo original. As modificações apresentadas conduzem a resultados relevantes tanto em termos do tempo de reordenamento quanto na redução da largura de banda. O desempenhode cada algoritmo é comparado com a sua respectiva implementação disponibilizada pela biblioteca Boost. O paralelismo é suportado pelo framework OpenMP e ambas as versões do algoritmo são testadas com matrizes esparsas de grande porte e estruturalmente simétricas.

ASSUNTO(S)

rcm paralelo redução de largura de banda matrizes esparsas

Documentos Relacionados

• Parallel Subtraction of Matrices
• Synthesis of Sparse Arrays Based On CIGA (Convex Improved Genetic Algorithm)
• Study of the audio coding algorithm of the MPEG-4 AAC standard and comparison among implementations of modules of the algorithm
• A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays
• Automatic Identification of Cigarette Brand Using Near-Infrared Spectroscopy and Sparse Representation Classification Algorithm