Implementac¸a˜ o e Avaliac¸ a˜o de Te´cnicas de Paralelizac¸ a˜o no Algoritmo de Hirschberg para Sistemas Multicore

Resumo

2Instituto de Matema´tica e Estat´ıstica, UERJ - Rio de Janeiro - RJ - Brasil 3Instituto de Computac¸a˜o, UFF - Nitero´i - RJ - Brasil Resumo. Descobrir a maior subsequeˆncia comum entre duas sequeˆncias em um tempo razoa´vel e´ fundamental para solucionar diversos problemas. Para garantir que a soluc¸ a˜o o´tima seja encontrada, algoritmos baseados em programac¸ a˜o dinaˆmica sa˜o necessa´rios. O algoritmo de Hirschberg possui complexidade linear de espac¸o, podendo ser usado para comparar sequeˆncias longas. Pore´m, devido a` sua complexidade quadra´tica de tempo, o uso do paralelismo e´ fundamental. Assim, o objetivo deste trabalho e´ implementar e avaliar te´cnicas de paralelismo para o algoritmo de Hirschberg que permitam a comparac¸ a˜o de sequeˆncias de caracteres longas. Para alcanc¸ar este objetivo, treˆs estrate´gias de paralelismos sa˜o implementadas e investigadas em cima de melhorias na versa˜o sequencial do algoritmo. Os resultados mostram que e´ poss´ıvel executar mais eficientemente o algoritmo de Hirschberg em ma´quinas multicore, especialmente para grandes cadeias de caracteres, sendo poss´ıvel alcanc¸ar um desempenho ate´ 33 vezes melhor do que a versa˜o sequencial original.