Uma avaliação de implementações via OpenMP e Pthreads de duas heurísticas para reduções de largura de banda de matrizes

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOliveira, Sanderson L. Gonzaga de-
Autor(es): dc.contributorBarros, Carla Osthoff Ferreira de-
Autor(es): dc.contributorKischinhevsky, Mauricio-
Autor(es): dc.creatorRibeiro, Jean Antonio-
Data de aceite: dc.date.accessioned2026-02-09T12:14:27Z-
Data de disponibilização: dc.date.available2026-02-09T12:14:27Z-
Data de envio: dc.date.issued2018-07-06-
Data de envio: dc.date.issued2018-07-06-
Data de envio: dc.date.issued2018-07-05-
Data de envio: dc.date.issued2018-05-04-
Fonte completa do material: dc.identifierhttps://repositorio.ufla.br/handle/1/29544-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1157315-
Descrição: dc.descriptionIn 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.-
Descrição: dc.descriptionFundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG)-
Descrição: dc.descriptionNeste 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Federal de Lavras-
Publicador: dc.publisherPrograma de Pós-Graduação em Ciência da Computação-
Publicador: dc.publisherUFLA-
Publicador: dc.publisherbrasil-
Publicador: dc.publisherDepartamento de Ciência da Computação-
Direitos: dc.rightsrestrictAccess-
Palavras-chave: dc.subjectRedução de largura de banda-
Palavras-chave: dc.subjectRedução de profile-
Palavras-chave: dc.subjectBusca em largura-
Palavras-chave: dc.subjectReverse Cuthill-McKee-
Palavras-chave: dc.subjectKP-band-
Palavras-chave: dc.subjectAlgoritmos paralelos-
Palavras-chave: dc.subjectPthreads-
Palavras-chave: dc.subjectOpenMP-
Palavras-chave: dc.subjectMétodo dos gradientes conjugados precondicionado-
Palavras-chave: dc.subjectFatoração incompleta de Cholesky-
Palavras-chave: dc.subjectBandwidth reduction-
Palavras-chave: dc.subjectProfile reduction-
Palavras-chave: dc.subjectParallel computing-
Palavras-chave: dc.subjectParallel algorithms-
Palavras-chave: dc.subjectPreconditioned conjugate gradient method-
Palavras-chave: dc.subjectIncomplete Cholesky factorization-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleUma avaliação de implementações via OpenMP e Pthreads de duas heurísticas para reduções de largura de banda de matrizes-
Tipo de arquivo: dc.typedissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal de Lavras (RIUFLA)

Não existem arquivos associados a este item.