Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/29544
Título: Uma avaliação de implementações via OpenMP e Pthreads de duas heurísticas para reduções de largura de banda de matrizes
Autor : Ribeiro, Jean Antonio
Lattes: http://lattes.cnpq.br/3365110652150024
Primeiro orientador: Oliveira, Sanderson L. Gonzaga de
Primeiro membro da banca: Barros, Carla Osthoff Ferreira de
Segundo membro da banca: Kischinhevsky, Mauricio
Palavras-chave: Redução de largura de banda
Redução de profile
Busca em largura
Reverse Cuthill-McKee
KP-band
Algoritmos paralelos
Pthreads
OpenMP
Método dos gradientes conjugados precondicionado
Fatoração incompleta de Cholesky
Bandwidth reduction
Profile reduction
Parallel computing
Parallel algorithms
Preconditioned conjugate gradient method
Incomplete Cholesky factorization
Data da publicação: 5-Jul-2018
Agência(s) de fomento: Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG)
Referência: RIBEIRO, J. A. Uma avaliação de implementações via OpenMP e Pthreads de duas heurísticas para reduções de largura de banda de matrizes. 2018. 81 p. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal de Lavras, Lavras, 2018.
Resumo: Neste trabalho, são descritos dois algoritmos paralelos, em arquiteturas multicore, para solucionar os problemas de reduções de largura de banda e de profile de matrizes simétricas e esparsas. Para isso, as linhas e colunas da matriz de coeficientes são permutadas, deixando-as com uma estrutura compacta, de modo que os coeficientes não nulos estejam próximos à diagonal principal. Os novos algoritmos paralelos foram comparados a algoritmos disponíveis na biblioteca HSL e nos softwares Octave e Matlab. Nas simulações, esses algoritmos são aplicados como um pré-processamento na resolução de sistemas de equações lineares. Mais especificamente, os sistemas de equações lineares serão resolvidos pelo método dos gradientes conjugados precondicionado pela fatoração incompleta de Cholesky, em que a matriz de coeficientes é simétrica e positiva definida. Uma localidade de memória adequada contribui para a eficiência do método dos gradientes conjugados precondicionado, e essa característica pode ser obtida por reordenações de linhas e colunas da matriz de coeficientes. As bibliotecas utilizadas foram OpenMP e Pthreads. A qualidade da solução entre os algoritmos sequenciais e paralelos se manteve para a maioria das instâncias testadas; contudo o tempo computacional foi melhor com a biblioteca OpenMP do que com a biblioteca Pthreads, especialmente quando foram utilizadas duas threads nas execuções dos algoritmos. Todavia os experimentos computacionais, realizados neste trabalho, mostram que heurísticas paralelas, para reduções de largura de banda, têm potencial de acelerar o método paralelo dos gradientes conjugados precondicionado.
Abstract: In this work, two parallel algorithms are described in multicore architectures to solve the bandwidth and profile reduction problems of symmetric and sparse matrices. For this, the rows and columns of the coefficient matrix are permuted, leaving it with a compact structure so that the nonzero coefficients are close to the main diagonal. The new parallel algorithms were compared to algorithms available in the HSL library and in the Octave and Matlab softwares. In the simulations, these algorithms are applied as a preprocessing in the resolution of systems of linear equations. More specifically, systems of linear equations will be solved by the conjugate gradients method with incomplete Cholesky factorization preconditioning, where the coefficient matrix is symmetric and positive definite. A suitable memory location contributes to the efficiency of the preconditioned conjugate gradient method, and this characteristic can be obtained by rearrangements of rows and columns of the coefficient matrix. The libraries used were OpenMP and Pthreads. The quality of the solution for sequential and parallel algorithms was maintained for most of the tested instances. However, computational time was better with the OpenMP library than with the Pthreads library, especially when two threads were used in the execution of the algorithms. Nevertheless, in this work, it is shown that parallel heuristics for bandwidth reductions have the potential to accelerate the parallel method of the preconditioned conjugate gradients. However, the computational experiments carried out in this work showed that parallel heuristics for bandwidth reductions have the potential to accelerate the parallel method of preconditioned conjugate gradients.
metadata.teses.dc.description: Arquivo retido, a pedido do autor, até julho 2019.
URI: http://repositorio.ufla.br/jspui/handle/1/29544
Publicador: Universidade Federal de Lavras
Idioma: por
Aparece nas coleções:DCC - Ciência da Computação - Mestrado (Dissertações)

Arquivos associados a este item:
Não existem arquivos associados a este item.


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.