Integrando Execução Especulativa à Paralelização de Laços e Tarefas

Resumo

Esta proposta traz cinco contribuições para abordar o problema de paralelização de código. Primeiro, propõe uma ferramenta para medir a probabilidade de dependências loop-carried de cada componente e detectar padrões loop-carried de laços estendendo a cláusula check de OpenMP. Experimentos iniciais mostram que a loop-carried probability é uma métrica eficaz para decidir quando usar TLS ou BDX para paralelizar laços, assim, para certos laços, slowdowns podem ser transformados em 2× de speed-ups selecionando rapidamente o algoritmo apropriado. Em segundo lugar, propõe uma abordagem de anotação de código para separar os componentes sequenciais ou may sequenciais de um dado loop baseado na loop-carried probability de cada componente, expondo assim outros componentes à paralelização. Em terceiro lugar, integra dois algoritmos (TLS e BDX) em uma cláusula OpenMP simples que permite ao programador selecionar a melhor algoritmo para cada componente de um determinado laço (abordagem judicious). Quarto, propõe novas cláusulas do OpenMP para implementar privatizações especulativas (spec private e spec reduction) que são essenciais para alcançar bom desempenho no algoritmo TLS. Finalmente, esta proposta também descreve uma nova técnica de especulação para a execução paralela de tarefas. Essa técnica, chamada de Speculative Task Execution (STE), executa especulativamente tarefas que têm dependências de controle com tarefas anteriores. No entanto, STE também pode ser usado para especular dependências de dados entre tarefas de diferentes iterações em um loop possivelmente gerado por uma construção taskloop. STE requer suporte de hardware que pode ser fornecido de maneira semelhante ao dispon1vel nos sistemas HTM (Hardware Transactional Memory). Propomos a implementação de um protótipo para o STE e o projeto de novas construções e cláusulas especulativas para integrar STE em uma paralelização baseada em tarefas de OpenMP: (a) a construção spec on; (b) a cláusula tls para taskloop; e (c) o tipo de dependência spec in para a cláusula depend.