Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/2650
Tipo: Tese
Título: Soluções para os problemas da soma máxima e do k-ésimo menor elemento de uma sequência usando o modelo BSP/CGM
Autor(es): Lima, Anderson Corrêa de
Primeiro orientador: Cáceres, Edson Norberto
Abstract: Neste trabalho são propostos algoritmos paralelos para os seguintes problemas: a subsequência de soma máxima, a submatriz de soma máxima, o hiper-retangulo de soma máxima e a seleção do k-esimo menor elemento de um sequencia não ordenada. Todos os problemas tratados possuem aplicações em diversas áreas da ciência, com destaque para biologia computacional, visão computacional, analise de volumes rochosos e de ordem. No projeto de nossos algoritmos adotamos uma extensão do modelo BSP/CGM de computação paralela e mostramos que, além do ambiente de memoria distribuida, o modelo BSP/CGM também pode ser utilizado em arquiteturas com memoria compartilhada e com múltiplos núcleos, tais como as GPUs. Diferentemente de soluções anteriores, nossos algoritmos e implementações utilizam novas estratégias na solução de cada problema. Apresentamos algoritmos paralelos para subproblemas relacionados ao problema da soma máxima, para os quais, de acordo com o nosso melhor conhecimento, a literatura não apresenta soluções no modelo BSP/CGM. As implementações foram construídas utilizando CUDA, MPI e OpenMP. Por fim, destacamos que nossos algoritmos são competitivos, quando comparados com as respectivas soluções sequenciais e paralelas já existentes.
ABSTRACT- In this work we propose parallel algorithms for the following problems: the maximum subsequence sum, the maximum subarray sum, the maximum hyperrectangle sum and the selection of the k-th smallest element of an unsorted sequence. The problems treated have applications in many areas of science, such as bioinformatics, computer vision, rock analysis and order. In the design of our algorithms we adopted an extension of the BSP/CGM parallel computing model, showing that it can be used not only for distributed memory environments but also in architectures with shared memory and multiple cores, such as GPUs. Differently from previous solutions, our algorithms and implementations use new strategies for solving each problem. Besides, we also present parallel algorithms for maximum sum related problems, and to the best of our knowledge, there are no BSP/CGM solutions for this subproblems in the literature. All implementations were built using MPI, OpenMP and CUDA. Finally, we emphasize that our algorithms have achieved competitive performance speedups, compared to sequential and parallel solutions described in the literature.
Palavras-chave: Algorítmos Paralelos
Parallel Algorithms
Linguagem de Programação (Computadores)
Programming Languages (Electronic Computers)
Computação
Computer Science
Tipo de acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/2650
Data do documento: 2015
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
ANDERSON CORRÊA DE LIMA.pdf1,3 MBAdobe PDFThumbnail
Visualizar/Abrir


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