Efficient BSP/CGM algorithms for the maximum subsequence sum and related problems
Carregando...
Data
2015
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
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.
Descrição
Palavras-chave
Parallel algorithms, Multicore, GPU, Maximum subsequence sum problem
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.