Optimizing data alignment for data parallel programs

Data decomposition across processors is critical to the performance of data parallel programs on distributed-memory machines. The data decomposition problem involves data alignment and data distribution. This paper addresses the data alignment phase which can be classified into slope alignment and offset alignment. We propose a data reference graph (DRG) model. Based on the DRG model, a slope alignment heuristic algorithm and an offset alignment heuristic algorithm are proposed for the purpose of minimizing interprocessor communication. Such a DRG-based data alignment framework makes our work unique from other related work. The time complexity of both proposed algorithms are in the linear order of distinct references given in a program structure.