Compile and Run-Time Support for the Parallelization of Sparse Matrix Updating Algorithms

This work presents a survey of the capabilities that the sparse computation offers for improving performance when parallelized, either automatically or through a data-parallel compiler. The characterization of a sparse code gets more complicated as code length increases: Access patterns change from loop to loop, thus making necessary to redefine the parallelization strategy. While dense computation solely offers the possibility of redistributing data structures, several other factors influence the performance of a code excerpt in the sparse field, like source data representation on file, compressed data storage in memory, the creation of new nonzeroes at run-time (fill-in) or the number of processors available. We analize the alternatives that arise from each issue, providing a guideline for the underlying compilation work and illustrating our techniques with examples on the Cray T3E.