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

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 na 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 conguraçõ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.