Implementação e Avaliação de Técnicas de Paralelização no Algoritmo de Hirschberg para Sistemas Multicore

Resumo

Descobrir a maior subsequência comum entre duas sequências em um tempo razoável é fundamental para solucionar diversos problemas. Para garantir que a solução ótima seja encontrada, algoritmos baseados em programação dinâmica são necessários. O algoritmo de Hirschberg possui complexidade linear de espaço, podendo ser usado para comparar sequências longas. Porém, devido a` sua complexidade quadrática de tempo, o uso do paralelismo é fundamental. Assim, o objetivo deste trabalho é implementar e avaliar técnicas de paralelismo para o algoritmo de Hirschberg que permitam a comparação de sequências de caracteres longas. Para alcançar este objetivo, três estratégias de paralelismos são implementadas e investigadas em cima de melhorias na versão sequencial do algoritmo. Os resultados mostram que é possível executar mais eficientemente o algoritmo de Hirschberg em máquinas multicore, especialmente para grandes cadeias de caracteres, sendo possível alcançar um desempenho até 33 vezes melhor do que a versão sequencial original.