Otimizando Laços em Computação por Fluxo de Dados

O modelo de dataflow dinâmico permite que as iterações distintas de um loop executem simultaneamente, impulsionando a exploração de paralelismo no modelo. Para evitar que operandos produzidos em iterações futuras sejam utilizados em iterações passadas, cada operando possui um rótulo com um número de instância, que é incrementado a cada iteração do loop. A execução de uma instrução é disparada somente quando todos seus operandos de entrada com os mesmos rótulos se tornam disponíveis. Entretanto, este mecanismo de rótulo tradicional impõe a geração de instruções de controle desnecessárias para manipular os rótulos e garantir o casamento correto de operandos que não são processados dentro de um loop. Para tratar desse problema, este trabalho apresenta um conjunto de técnicas de otimização de loop no dataflow. O Stack-Tagged Dataflow é um mecanismo que utiliza pilha de inteiro no rótulo de cada operando para reduzir o controle de overhead em dataflow. Contudo, este mecanismo de pilha pode obter overheads significativos em loops aninhados. O Tag Resetting pode ser usado para zerar o rótulo de um operando quando ele alcançar um ponto seguro de execução, permitindo a redução de um nível da profundidade de pilha. Finalmente, o Loop Skipping contribui ainda mais com a redução do overhead da comparação de pilha em loops, quando o número de iterações de um loop pode ser previsto pelo compilador. Os resultados dos experimentos mostram que todas as técnicas contribuem com a redução do overhead em loops no dataflow. Os experimentos mostram que a execução de tarefas com granularidade mais fina se torna viável com a aplicação dessas técnicas. Além do mais, uma abordagem de compilação híbrida pode ser usada para melhorar o desempenho de cada técnica.