Análises Estáticas para a Distribuição de Dados e Computações em Memória Distribuída

Abstract

This work describes static compiler analysis techniques based on linear algebra and linear programming to optimize the distribution of forall loops and array elements in programs written in the SISAL programmig language for distributed memory parallel machines. In the alignment phase, that tries to find the portions of different arrays that need to be distributed together, we work with alignment hyperplanes. In the partitioning phase, that tries to break the computations and data in independent parts, we use two afine functions: the data decomposition function and the computation decomposition function. The last phase, the mapping, distributes the elements of computation into the processing elements through a set of inequations. The techniques are being implemented in a SISAL compiler, but can be used without changes to other single assignment languages, and with the addition of dependecy analysis to other languages as well.