Algoritmos paralelos realísticos para a maior subsequência comum

Abstract

Neste trabalho estudou-se o problema da Maior Subsequência Comum (Longest Common Subsequence - LCS) que deseja encontrar uma subsequência comum de comprimento máximo de duas sequências. O problema LCS pode ser resolvido em tempo sequencial quadrático usando a técnica de programação dinâmica. Este trabalho consiste em estudar os algoritmos paralelos baseados nos modelos realísticos para resolver o problema LCS. Inicialmente estudou-se um algoritmo sequencial, um algoritmo paralelo no modelo PRAM e um no modelo realístico que encontra a LCS de todas as subcadeias. Fez-se uma implementação paralela realística com O(p) rodadas de comunicação usando p processadores. O resultado desta implementação não obteve speedup satisfatório, o que motivou o estudo mais teórico da paralelização do problema. Neste sentido, a partir do algoritmo PRAM descreveu-se uma solução paralela realística, usando estrutura de dados bem conhecidas como soma prefixa paralela e a técnica de pointer jumping.

In this work, it was studied the problem of the Longest Common Subsequence - LCS that aims to finds a common subsequence of maximum lenght of two sequences. The LCS problem can be solved in quadratic sequential time using the dynamic programmimg technique. This work consists in studying the parallel algorithms based on the realistic models to solve the LCS problem. Initially they studied a sequential algorithm, a parallel algorithm PRAM model and one at the realistic model that nds the LCS of all substrings. It was done a realistic parallel implementation with O(p) communication rounds using processors (p). The result of this implementation didn't get a satisfactory speedup that led to a more theoretical study of the problem parallelization. Thus, from the PRAM algorithm it was described a realistic parallel solution, using well-known data structure as parallel prefix sum and the pointer jumping technique.