Title: Runtime characterisation of irregular accesses applied to parallelisation of irregular reductions

Authors: David E. Singh, Maria J. Martin, Francisco F. Rivera

Addresses: Department of Computer Science, University Carlos III of Madrid, Spain. ' Department of Electronics and Systems, University of A Coruna, Spain. ' Department of Electronics and Computer Science, University of Santiago de Compostela, Spain

Abstract: Irregular reduction operations are the core of many large scientific and engineering applications. There are, in the literature, different methods to solve these operations in parallel. In this paper we discuss a new technique which improves performance significantly, both in terms of execution time and memory overhead. These improvements are achieved in the preprocessing as well as in the resulting parallel code. Our proposal is based on the use of the Irregular Access Region Descriptor (IARD). This data structure is a compact characterisation of indirectly accessed arrays that can be used for the efficient parallelisation of a wide spectrum of irregular codes. In this paper we present its application to parallelise irregular reduction operations on a shared memory machine. We compare our proposal with two other competitive solutions.

Keywords: compiler analysis; runtime parallelisation; irregular codes; irregular reductions; shared memory system; irregular access; execution time; memory overhead; parallel code; subscript arrays; sparse matrices; scientific computing; engineering computing.

DOI: 10.1504/IJCSE.2005.008906

International Journal of Computational Science and Engineering, 2005 Vol.1 No.1, pp.1 - 14

Published online: 02 Feb 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article