Condições exatas para paralelização de laços sequênciais - Fábio Carneiro Mokarzel (1995)
Este trabalho desenvolve condicoes exatas para a aplicacao de estrategias de paralelizacao a lacos sequenciais. A teoria de dependencias com sua atual formulacao nao consegue isoladamente responder com precisao sobre a paralelizacao de certos trechos de programas sequenciais. Faltam criterios para decidir quais dependencias desses trechos tem realmente utilidade nesse processo. Algumas delas podem ser violadas sem comprometer a correcao dos programas, enquanto outras, como aquelas relativas as variaveis de controle dos lacos, sao usadas em pouquissimos casos e avolumam muito o grafo de dependencias. Alem disso, essa teoria nao consideraa estrategia de paralelizacao escolhida. Este trabalho estabelece dispositivos matematicos (condicoes exatas) que respondem com precisao se um laco pertencente ao universo de lacos sequenciais unicos com um ou dois comandos de atribuicao em seus escopos pode ser paralelizado, considerando algumas estrategias de paralelizacao bem conhecidas. A determinacao das condicoes exatas para lacos genericos e um problema estruturalmente complexo. Isso impos limitacoes a este trabalho, reduzindo sua abordagem para uma familiarestrita do referido universo. Alem do estabelecimento das condicoesexatas, este trabalho apresenta relacoes entre os conjuntos de lacosparalelizaveis, nas estrategias estudadas, comparando a aplicabilidade dessas estrategias aos lacos sequenciais. Por fim, este trabalho compara a atual forma de utilizacao da teoria de dependencias na paralelizacao de lacos sequenciais com as condicoes exatas estabelecidas, evidenciando a imprecisao da utilizacao dessa teoria.