PARALLELIZATION TECHNIQUES FOR SPARSE-MATRIX APPLICATIONS

Sparse matrix problems are difficult to parallelize efficiently on dis tributed memory machines since data is often accessed indirectly. Insp ector-executor strategies, which are typically used to parallelize loo ps with indirect references, incur substantial runtime preprocessing o verheads when references with multiple levels of indirection are encou ntered-a frequent occurrence in sparse matrix algorithms. The sparse-a rray rolling (SAR) technique, introduced in [M. Ujaldon and E. L. Zapa ta, Proc. 9th ACM Int'l. Conf. on Supercomputing, Barcelona, July 1995 , pp. 117-126], significantly reduces these preprocessing overheads. T his paper outlines the SAR approach and describes its runtime support accompanied by a detailed performance evaluation. The results demonstr ate that SAR yields significant reduction in preprocessing overheads c ompared to standard inspector-executor techniques. (C) 1996 Academic P ress, Inc.