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.
Referências
Anvik, J., MacDonald, S., Szafron, D., Schaeffer, J., Bromling, S., and Tan, K. (2002). Generating parallel programs from the wavefront design pattern. In Proceedings of the 16th International Parallel and Distributed Processing Symposium, páginas 165–172.
Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., and McDonald, J. (2000). Parallel Programming in OpenMP. Morgan Kaufmann, 1st edition.
Diaz, J., Mu˜noz-Caro, C., and Ni˜no, A. (2012). A survey of parallel programming models and tools in the multi and many-core era. IEEE Transactions on Parallel and Distributed Systems, 23(8):1369–1386.
Driga, A., Lu, P., Schaeffer, J., Szafron, D., Charter, K., and Parsons, I. (2003). FastLSA: a fast, linear-space, parallel and sequential algorithm for sequence alignment. In 2003 International Conference on Parallel Processing, 2003. Proceedings., páginas 48–57.
Guseld, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18(6):341–343.
Lento, G. (2014). Optimizing performance with intel*R advanced vector extensions. Technical report, Intel.
Martins, W. S., del Cuvillo, J., Useche, F. J., Theobald, K. B., and Gao, G. R. (2001). A multithreaded parallel implementation of a dynamic programming algorithm for se- quence comparison. In Pacic Symposium on Biocomputing.
Mohanty, S. and Cole, M. (2014). Autotuning wavefront applications for multicore multi- gpu hybrid architectures. In Proceedings of Programming Models and Applications on Multicores and Manycores, PMAM'14, páginas 1:1–1:9, New York, NY, USA. ACM.
Needleman, S. B. and Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443 – 453.
Rashid, N. A., Abdullah, R., and Talib, A. Z. H. (2007). Parallel homologous search with In Proceedings of the 11th
hirschberg algorithm: A hybrid MPI-pthreads solution. WSEAS International Conference on Computers, páginas 228–233.
Sandes, E. F. D. O., Boukerche, A., and Melo, A. C. M. A. D. (2016). Parallel optimal pairwise biological sequence comparison: Algorithms, platforms, and classication. ACM Comput. Surv., 48(4):63:1–63:36.
Smith, T. and Waterman, M. (1981). Identication of common molecular subsequences. Journal of Molecular Biology, 147(1):195 – 197.
Yang, J., Xu, Y., and Shang, Y. (2010). An efcient parallel algorithm for longest common subsequence problem on GPUs. In Proceedings of the World Congress on Engineering, páginas 499–504.
