Casos de estudo com ferramentas de programação multithread felipe haertel

Arquiteturas paralelas tem se tornado onipresentes como suporte computacional em funcao da popularidade da tecnologia multicore. Nestas arquiteturas, as ferramentas de programacao mais adequadas sao aquelas que implementam modelos de programacao multithread, permitindo que programas sejam descritos por multiplos fluxos de execucao concorrente capazes de ocupar as varias unidades de processamento de forma paralela. Existem dois modelos basicos para decomposicao do paralelismo de uma aplicacao: a decomposicao em termos de paralelismo de dados ou de tarefas. A opcao por um ou outro destes modelos se da em funcao da natureza do problema que esta sendo implementado, sendo que diferentes ferramentas de programacao multithread oferecem diferentes facilidades de desenvolvimento para cada caso. Este trabalho avalia a interface de programacao oferecida por quatro ferramentas multithread como suporte a implementacao de diferentes padroes de paralelismo expresso por problemas recorrentes em aplicacoes matematicas. Neste texto sao considerados quatro padroes de problemas: (i) trivialmente paralelizaveis, (ii) recursivos, (iii) programacao dinâmica, e (iv) com grande numero de dependencias entre as atividades paralelas. Estes padroes sao representados, respectivamente, pelas seguintes aplicacoes: (i) problema de Satisfatibilidade Booleana (denominado 3Sat no restante deste texto), (ii) calculo da serie de Fibonacci (Fibo), (iii) o algoritmo Smith-Waterman para o alinhamento de sequencias (S-W), e (iv) decomposicao LU de uma matriz (LU). O estudo e completado com uma analise do desempenho dos programas construidos para estas aplicacoes nas diferentes ferramentas considerando suas estrategias de escalonamento. Com este tipo de trabalho, interdisciplinar, entende-se obter avancos tanto na area de desenvolvimento de software matematico como aprimoramento nas tecnicas de execucao paralela, conforme discutido em [1] Este texto limita-se a caracterizar as ferramentas de programacao selecionadas nesta fase do trabalho, que sao a academica Athreads [2], e as comerciais Cilk, OpenMP e TBB, sumarizadas em [4], e exemplificar os resultados pela analise de um conjunto de resultados de desempenho. Um dos objetivos a ser atingido e identificar a usabilidade de ferramentas de programacao multithread [3] no desenvolvimento de diferentes padroes de problemas matematicos. Athreads, Cilk e TBB embutem um nucleo de escalonamento que explora informacoes sobre a ordem lexicografica definida entre os threads pelo programa em execucao. Destas dependencias sao inferidos os custos computacionais de cada thread, assumindo que quanto mais antigo um thread for, maior sera seu custo computacional. Esta informacao de custo e considerada nas tomadas de decisao sobre os recursos de processamento disponiveis. A diferenca entre estas ferramentas se da na interface de programacao. Enquanto Cilk restringe o modelo de programacao em uma estrutura de criacao e sincronizacao aninhada de threads (nested fork/join), Athreads permite a construcao de qualquer estrutura de dependencias. Como consequencia, a estrutura regular em Cilk pode ser explorada com uma eficiencia maior por uma heuristica simples de escalonamento que considere esta regularidade nas dependencias entre threads. Por outro lado, em Athreads cabe ao programador conhecer a estrategia de escalonamento e organizar a criacao de threads de forma a refletir a heuristica de escalonamento empregada. TBB tambem tem como padrao a criacao aninhada de threads, mas, para nao limitar tanto como Cilk o poder de expressao de paralelismo, esta ferramenta permite ao programador criar threads externas a esta estrutura aninhada. Com uma interface de programacao totalmente diversa das anteriores, OpenMP e voltado para problemas onde ocorre paralelismo de dados, sendo seus programas caracterizados pela criacao, tambem aninhada, de lotes de trabalho. Seu nucleo de escalonamento considera a distribuicao da carga de trabalho contida neste lote. Operando, portanto, em rodadas de lotes de trabalhos recebidos. Dependencias entre os trabalhos nao sao consideradas, apenas o programador pode indicar que diferentes trabalhos, em um mesmo lote, possuem cargas computacionais diferentes para auxiliar nas heuristicas de escalonamento. Na Figura 1 sao apresentados os desempenhos, em termos de speedup (relacao entre o tempo de execucao do problema com uma thread e seu tempo de execucao paralelo) em uma arquitetura com oito cores. Por questoes de espaco, o grafico reflete o speedup apenas para o caso de execucao paralela com tambem oito threads. Figura 1. Grafico de speedup para o caso de oito threads. Observamos que, para uma aplicacao trivialmente paralelizavel, como o 3Sat, nao houve grande impacto do mecanismo de escalonamento e tambem as interfaces de programacao oferecidas pelas ferramentas nao impuseram nenhuma restricao a sua implementacao. No outro extremo, em aplicacoes como LU, em que o numero de dependencias entre threads e alto, tambem observamos que o nucleo de escalonamento nao possui margem de trabalho que permita diferenciar as ferramentas. Neste tipo de problema tambem notou-se uma maior dificuldade de desenvolvimento do programa em ferramentas vocacionadas ao paralelismo de dados, como OpenMP. Ja em aplicacoes onde existe uma estrutura regular na criacao de tarefas, como no calculo recursivo de Fibonacci, a heuristica de escalonamento adotada por Athreads, Cilk e TBB reflete em ganho de desempenho. Note-se que, quanto maior for a restricao imposta pela ferramenta para expressao do paralelismo (como em Cilk e TBB), maiores as chances de sucesso do escalonamento. Por outro lado, em Athreads, pequenas variacoes na ordem de criacao de threads, o que e permitido pela ferramenta, ocasionam impacto no desempenho obtido. Finalmente, no caso de um algoritmo de programacao dinâmica, como o S-W, encontramos dificuldades em modelar o problema considerando as diferentes interfaces de programacao utilizadas. No grafico e traduzido o desempenho obtido na melhor implementacao realizada ate o momento pelo grupo.