Algoritmos Paralelos para Detecção de Palíndromos

Autores

1614
Maodo Rudá Dia
678,163
1615
Valmir Carneiro Barbosa
(Orientador)
678,163

Informações:

Publicações do PESC

Título
Algoritmos Paralelos para Detecção de Palíndromos
Linha de pesquisa
Arquitetura e Sistemas Operacionais
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
26/3/1998
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Algoritmos Paralelos para Detecção de Palíndromos

Maodo Rudá Dia

Março/1998
Orientador: Valmir Carneiro Barbosa  

 
Programa: Engenharia de Sistemas e Computação

      Este trabalho apresenta algoritmos paralelos projetados para detecção de palíndromos em qualquer tipo de cadeia de caracteres. Os algoritmos servem como base para a solução de um problema da Biologia Molecular, que é a detecção de transpons. Transpons são repetições invertidas, não necessariamente perfeitas, encontradas no genoma. Foram desenvolvidos três algoritmos de alocação de dados e um algoritmo de sincronização das trocas de mensagens. A implementação dos algoritmos resultaram num programa chamado PPALIN. Este programa foi executado numa máquina IBM SP2 para a obtenção de dados comparativos. Os speedups ficaram em torno de 50%, o que numa execução com 16 processadores resultou num desempenho 8 vezes superior que a versão sequencial. A necessidade de memória na versão paralela é de 66% a mais que a versão sequencial, logo se a maior entrada no sequencial fosse de 1 milhão de elementos, com 16 processadores poderíamos ter uma entrada quase 10 vezes maior.

Abstract
PESC: Master Degree Abstracts Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

Parallel Algorithms for Detection of Palindromes

Maodo Ruda Dia

March/1998
Advisor:Valmir Carneiro Barbosa  
Department: Systems Engineering and Computer Science

      This work presents parallel algorithms projected for detection of palindromes on any type of strings. The algorithms serve as a basis for the solution of a Molecular Biology problem called the transpons detection. Transpons are inverted repetitions sequences founded on the genome, and are not necessarily perfect. Three algorithms were developed for data alocation and one for message-passing sincronization. A program called PPALIN was the result of the implementation of these algorithms. It was, executed on an IBM SP2 machine to obtain comparative data. These executions achive about 50% of speedup, which means that running with 16 processors the performance was 8 times better than the sequencial version. The parallel version needs 66% more of amount of memory. If the biggest source sequence have I million elements, with 16 processors we can have a source sequence near 10 times greater.

Arquivo
Topo