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

• Raul Junji Nakashima USP
• Gonzalo Travieso USP

DOI: https://doi.org/10.5753/wscad.2001.19118

Resumo

Este trabalho descreve técnicas de análise estática de compilação baseadas na álgebra e programação linear que buscam otimizar a distribuição de loops forall e array em programas escritos na linguagem SISAL visando à execução em máquinas paralelas de memória distribuídas. Na fase de alinhamento, buscamos o alinhamento de hiperplanos com o objetivo de tentar encontrar as porções dos diferentes arrays que devem ser distribuídas juntas. A fase de particionamento, que tenta quebrar em partes independentes dados e computações, duas funções afins, a função de decomposição de dados e a função de decomposição de computação são usadas para isso. A última fase, o mapeamento, distribui os elementos de computação nos elementos de processamento usando um conjunto de inequações sobre os limites. Essas técnicas estão sendo implementadas num compilador SISAL, mas podem ser usadas sem mudanças em outras linguagens de associação simples e com a adição de análise de dependências podem ser usadas em linguagens imperativas.

Palavras-chave: Otimização, análises estáticas de compilação, alinhamento, particionamento, mapeamento, forall

Referências

ANDERSON, J. M, Automatic Computation and Data Decomposition For Multiprocessors, Thesis CSL-TR-97-719, Stanford University, Mar 1997.

BOOKMAN, J. B., Kogge, P. M., The Case for Processing-in-Memory, Technical Report TR-97-03, University of Notre Dame, Jan. 1997

CULLER, D., et. al, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers, ISBN 1558603433, 1999.

FEO, J. T. et. al, A Report on the Sisal Language Project, Journal of Parallel and Distributed Computing, 10, 349-366, Dec. 1990.

MEYER, C. D., Matrix Analysis and Applied Linear Algebra, Society for Industrial & Applied Mathematics-SIAM, ISBN: 0898714540, Jun. 2000.

MCGRA W, J. et al. SISAL: Stream and lteration in a Single Assignment Language, Language Reference Manual, Technical Report M-146, Rev. I, University of California, Lawrence Livermore National Laboratory, Mar. 1985.

O'BOYLE, M. F. P., Program and Data Transformations for Efficient Execution on Distributed Memory Architectures, Technical Report UMCS-93-1-6, Department of Computer Science, University of Manchester, Jun. 1993.

SKEDZIELEWSKI, S. K. and Glauert, J., IFI An lntermediate Form for Applicative Languages, Manual M170, Lawrence Livermore National Laboratory, Livermore, California, Jan. 1985.

SKEDZIELEWSKI, S. K., Parallel and Functional Languages and Compilers, ACM Press, 1991

WOLF, E. M., lmproving Locality and Parallelism in Nested Loops, Department of Computer Science, Stanford University, Aug. 1992.