Automatic Implementation of Multi-partitioning Using Global Tiling

Strategies for partitioning an application¿s data and computation play fundamental role in determining the efficiency of parallelization. This paper describes a sophisticated strategy for partitioning data and computation known as multi-partitioning, which can support the best parallelization for some applications such as the line sweep computations. However, the implementation of multi-partitioning is very difficult and, as we know, there is none automatic parallelizing compiler supports such partitioning strategy. Though the dHPF compiler implemented multi-partitioning as a special extension for block style HPF partitioning, it still needs the programmer¿s participation to analyze the application and decide the data distribution scheme. In this paper, we present a global tiling transformation algorithm and a tile-to-processors mapping strategy called hyper-diagonal modular mapping, to implement the multi-partitioning strategy. The experimentation with NPB2.3-serial SP shows that the code generated by the compiler achieves scalable performance.