Integrating dense and sparse data partitioning

Abstract

Layout methods for dense and sparse data are often seen as two separate problems with its own particular techniques. However, they are based on the same basic concepts. This paper studies how to integrate automatic data-layout and partition techniques for both dense and sparse data structures. In particular, we show how to include support for sparse matrices or graphs in Hitmap, a library for hierarchical tiling and automatic mapping of arrays. The paper shows that is possible to offer a unique interface to work with both dense and sparse data structures, without losing significant performance. Thus, the programmer can use a single and homogeneous programing style, reducing the development effort and simplifying the use of sparse data structures in parallel computations.