Compiler techniques for the distribution of data and computation

Angeles Navarro, Emilio Zapata, David Padua

Research output: Contribution to journalArticlepeer-review


This paper presents a new method that can be applied by a parallelizing compiler to find, without user intervention, the iteration and data decompositions that minimize communication and load imbalance overheads in parallel programs targeted at NUMA architectures. One of the key ingredients in our approach is the representation of locality as a Locality-Communication Graph (LCG) and the formulation of the compiler technique as a Mixed Integer Nonlinear Programming (MINLP) optimization problem on this graph. The objective function and constraints of the optimization problem model communication costs and load imbalance. The solution to this optimization problem is a decomposition that minimizes the parallel execution overhead. This paper summarizes the process of how the compiler extracts the locality information from a nonannotated code and focuses on how this compiler can derive the optimization problem, solve it, and generate the parallel code with the automatically selected iteration and data distributions. In addition, we include a discussion about our model and the solutions - the decompositions - that it provides. The approach presented in the paper is evaluated using several benchmarks. The experimental results demonstrate that the MINLP formulation does not increase compilation time significantly and that our framework generates very efficient iteration/data distributions for a variety of NUMA machines.

Original languageEnglish (US)
Pages (from-to)545-562
Number of pages18
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number6
StatePublished - Jun 2003


  • Communication pattern
  • Load balancing
  • Locality analysis
  • Mixed integer nonlinear programming
  • Parallelizing compiler

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Compiler techniques for the distribution of data and computation'. Together they form a unique fingerprint.

Cite this