Effortless and Efficient Distributed Data-Partitioning in Linear Algebra

This paper introduces a new technique to exploit compositions of different data-layout techniques with Hit map, a library for hierarchical-tiling and automatic mapping of arrays. We show how Hit map is used to implement block-cyclic layouts for a parallel LU decomposition algorithm. The paper compares the well-known ScaLAPACK implementation of LU, as well as other carefully optimized MPI versions, with a Hit map implementation. The comparison is made in terms of both performance and code length. Our results show that the Hit map version outperforms the ScaLAPACK implementation and is almost as efficient as our best manual MPI implementation. The insertion of this composition technique in the automatic data-layouts of Hit map allows the programmer to develop parallel programs with both a significant reduction of the development effort and a negligible loss of efficiency.