Um Modelo de Desempenho Multinível para Algoritmos Paralelos Wavefront 2D Clássicos

• Alexandre Lauredo UERJ
• Alexandre Sena UERJ
• Maria de Castro UERJ
• Leandro Marzulo UERJ
• Tiago Alves UERJ

DOI: https://doi.org/10.5753/wscad.2016.14265

Resumo

O padrão wavefront 2D clássico é comumente usado para paralelizar algoritmos de programação dinâmica, onde elementos ou células de dados são distribuídos em uma matriz. Como os elementos da diagonal são completamente independentes, eles podem ser computados em paralelo. Em sistemas modernos, como os clusters multicore, usualmente é adotada uma abordagem de paralelismo multinível. A seleção do tamanho de cada tarefa tem uma importância crítica para maximizar o desempenho. As tarefas com granularidade grossa resultam em baixa concorrência, enquanto as de granularidade fina podem produzir alta sobrecarga. Neste trabalho analisa-se este balanço (tradeoff), considerando aspectos tais como o tamanho das tarefas (em dois níveis) e limitações de memória. Como resultado desta análise, é proposto um modelo que prediz quais configurações de tamanhos de tarefas produzem alto desempenho, com base nos parâmetros mencionados. Para avaliar a precisão do modelo é usado o algoritmo clássico para encontrar a maior subsequência comum (LCS), que é uma parte importante do alinhamento de sequências de DNA.

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 International Parallel and Distributed Processing Symposium., IPDPS 2002, pages 8 pp–.

Arora, N. S., Blumofe, R. D., and Plaxton, C. G. (1998). Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 119–129, New York, NY, USA. ACM.

Chen, Y., Yu, S., and Leng, M. (2006). Parallel sequence alignment algorithm for clusIn Shangai. Knowledge Enterprise: Intelligent Strategies in Product tering system. Design, Manufacturing, and Management, pages 311–321.

D. A. Benson, M. Cavanaugh, K. C. I. K.-M. D. J. L. J. O. and Sayers, E. W. (2013). Genbank. Nucleic Acids Research, 41:36–42.

Eggleston, H. G. (1967). The isoperimetric problem. In Press, P., editor, Exploring University Mathematics, volume 1, chapter 7. Pergamon Press.

Mohanty, S. and Cole, M. (2007). Autotuning wavefront applications for multicore multigpu hybrid architectures. In Proceedings of Programming Models and Applications on Multicores and Manycores, PMAM'14, pages 1:1–1:9, New York, NY, USA. ACM.

Sena, A. C., Nascimento, A. P., Boeres, C., Rebello, V., and Bulcao, A. (2011). An In E approach to optimise the execution of rtm algorithm in multicore machines. Science (e-Science), 2011 IEEE 7th International Conference on, pages 403–410.

Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. J. ACM, 21(1):168–173.