Use este identificador para citar ou linkar para este item: http://repositorio.bc.ufg.br/handle/ri/15167
Tipo do documento: Artigo
Título: Efficient BSP/CGM algorithms for the maximum subsequence sum and related problems
Autor: Lima, Anderson Corrêa de
Branco, Rodrigo Gonçalves de
C´aceres, Edson Norberto
Gaioso, Roussian Di Ramos Alves
Aquino, Samuel Benjoino Ferraz
Song, Siang Wun
Martins, Wellington Santos
Abstract: Given a sequence of n numbers, with at least one positive value, the maximum subsequence sum problem consists in finding the contiguous subsequence with the largest sum or score, among all derived subsequences of the original sequence. Several scientific applications have used algorithms that solve the maximum subsequence sum. Particularly in Computational Biology, these algorithms can help in the tasks of identification of transmembrane domains and in the search for GC-content regions, a required activity in the operation of pathogenicity islands location. The sequential algorithm that solves this problem has O n time complexity. In this work we present BSP/CGM parallel algorithms to solve the maximum subsequence sum problem and three related problems: the maximum longest subsequence sum, the maximum shortest subsequence sum and the number of disjoints subsequences of maximum sum. To the best of our knowledge there are no parallel BSP/CGM algorithms for these related problems. Our algorithms use p processors and require O n/p parallel time with a constant number of communication rounds for the algorithm of the maximum subsequence sum and O log p communication rounds, with O n/p local computation per round, for the algorithm of the related problems. We implemented the algorithms on a cluster of computers using MPI and on a machine with GPU using CUDA, both with good speed-ups.
Palavras-chave: Parallel algorithms
Multicore
GPU
Maximum subsequence sum problem
País: Estados unidos
Unidade acadêmica: Instituto de Informática - INF (RG)
Citação: LIMA, Anderson C.; BRANCO, Rodrigo G.; CÁCERES, Edson N.; GAIOSO, Roussian R. A.; FERRAZ, Samuel ; SONG, Siang W. ; MARTINS, Wellington S. Efficient BSP/CGM algorithms for the maximum subsequence sum and related problems. Procedia Computer Science, New York, v. 51, p. 2754-2758, 2015.
Tipo de acesso: Acesso Aberto
Identificador do documento: 10.1016/j.procs.2015.05.421
Identificador do documento: 10.1016/j.procs.2015.05.421
URI: http://repositorio.bc.ufg.br/tede/handle/ri/15167
Data de publicação: 2015
Aparece nas coleções:INF - Artigos publicados em periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Artigo - Anderson Corrêa de Lima - 2015.pdf358,15 kBAdobe PDFThumbnail
Baixar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons