Parallelization techniques for sparse matrix applications

Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since data is often accessed indirectly. Inspector-executor strategies, which are typically used to parallelize loops with indirect references, incur substantial runtime preprocessing overheads when references with multiple levels of indirection are encountered - a frequent occurrence in sparse matrix algorithms. The sparse-array rolling (SAR) technique, introduced in [M. Ujaldón and E. L. Zapata, Proc. 9th ACM Int'l. Conf, on Supercomputing, Barcelona, July 1995, pp. 117-126], significantly reduces these preprocessing overheads. This paper outlines the SAR approach and describes its runtime support accompanied by a detailed performance evaluation. The results demonstrate that SAR yields significant reduction in preprocessing overheads compared to standard inspector-executor techniques.