Performance optimization of irregular codes based on the combination of reordering and blocking, techniques

JC Pichel and DB Heras and JC Cabaleiro and FF Rivera, PARALLEL COMPUTING, 31, 858-876 (2005).

DOI: 10.1016/j.parco.2005.04.012

The combination of techniques based on reordering data with classic code restructuring techniques for increasing the locality in the execution of sparse algebra codes is studied in this paper. The reordering techniques are based on, first modeling the locality in run-time, and then applying a heuristic for increasing it. After this, a code restructuring technique specially tuned for sparse algebra codes called register blocking is applied. The product of a sparse matrix by a dense vector (SpM x V) is the code studied on different monoprocessors and distributed memory multiprocessors. The combination of both techniques was tested for a broad set of matrices from real problems and known repositories. The results expressed in terms of execution time show that an adequate reordering of the data improves the efficiency of applying register blocking, therefore, reducing the execution time for the sparse algebra code considered. (c) 2005 Elsevier B.V. All rights reserved.

Return to Publications page