Transformando Laços Seqüenciais em Laços Paralelos com Atribuição Única Durante a Execução
Resumo
Laços mais internos são fontes promissoras para a exploração de paralelismo em programas. A exploração do paralelismo nestes laços requer uma análise das dependências de dados existentes entre as iterações e a inserção de sincronização apropriada para a execução paralela correta. Motivados pela dificuldade encontrada pelos compiladores reestruturadores atuais, na detecção e inserção da sincronização, propõe-se neste artigo um esquema inédito de paralelização e sincronização de laços mais internos que, atuando durante a execução, elimina anti-dependências e dependências de saída, resultando em laços com atribuições únicas. As dependências de fluxo restantes são garantidas por uma primitiva de sincronização apropriada (flowbit), que, quando aplicada a laços com atribuições únicas, dispensa a detecção das dependências e o cálculo das distâncias para a sincronização correta.
Referências
Alfred V. Aho, Ravi Sethi e Jeffrey D. Ullmann, Compilers Principles, Techniques and Tools, Addison Wesley, 1986
Eduardo Voigt, Paralelismo e Sincronização em Laços, Dissertação de Mestrado, UNICAMP, 1991
Burton Smith, The Architecture of the HEP, Parallel MIMD Computation: The HEP Supercomputer and its Applications, MIT Press, 1985.
Peiyi Tang, Pen-Chung Yew e Chuan-Qi Zhu, Compilers Techniques for Data Synchronization in Nested Parallel Loops, ACM International Conference on Supercomputing, 1990
V.P Krothapalli e P.Sadayappan, An Approach to Synchronization for Parallel Computing, Proceedings of ACM International Conference on Supercomputing, 1988
Z. Shen, Z. Li e Pen-Chung Yew, An Empirical Study of FORTRAN Programs for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Computers, 1, 3, 1990
Allan Gottlieb et al., The NYU Ultracomputer, Designing an MIMD Shared Memory Parallel Computer, IEEE Transactions on Computers, C-32, 2, 1983
Eduardo Voigt, CP, Um Simulador de Paralelismo. Manual do Usuário, Documento Interno, Instituto de Estudos Avançados (IEAv), CTA, novembro 1990
