Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/2650
Registro completo de metadados
Campo DCValorIdioma
dc.creatorLima, Anderson Corrêa de-
dc.date.accessioned2016-03-22T22:48:16Z-
dc.date.available2021-09-30T19:56:06Z-
dc.date.issued2015-
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/2650-
dc.description.abstractNeste 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.pt_BR
dc.description.abstractABSTRACT- 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.pt_BR
dc.language.isoporpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgorítmos Paralelospt_BR
dc.subjectParallel Algorithmspt_BR
dc.subjectLinguagem de Programação (Computadores)pt_BR
dc.subjectProgramming Languages (Electronic Computers)pt_BR
dc.subjectComputaçãopt_BR
dc.subjectComputer Sciencept_BR
dc.titleSoluções para os problemas da soma máxima e do k-ésimo menor elemento de uma sequência usando o modelo BSP/CGMpt_BR
dc.typeTesept_BR
dc.contributor.advisor1Cáceres, Edson Norberto-
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.