Effortless and Efficient Distributed Data-Partitioning in Linear Algebra

Abstract

This paper introduces a new technique to exploit compositions of different data-layout techniques with Hitmap, a library for hierarchical-tiling and automatic mapping of arrays. We show how Hitmap 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 Hitmap implementation. The comparison is made in terms of both performance and code length. Our results show that the Hitmap 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 Hitmap allows the programmer to develop parallel programs with both a significant reduction of the development effort and a negligible loss of efficiency.