Applicability of Automatic Program Comprehension to Sparse Matrix Computations

Automatic program comprehension techniques have been shown to improve automatic parallelization of dense matrix computations. The recognition of concepts in the code enables aggressive automatic program transformations up to local algorithm replacement, and supports automatic data layout and performance prediction. We show how this approach can be generalized to sparse matrix codes. Program comprehension will be particularly useful in this case, since it should allow to abstract e.g. from specific storage formats used in the code. Unfortunately, space-efficient data structures for sparse matrices typically yield programs in which not all data dependencies can be determined at compile time. We propose a speculative program comprehension and parallelization method suitable for sparse matrix codes. Only where static analysis does not supply sufficient information, a parallelized run time test must check whether a code fragment speculatively recognized at compile time as a sparse matrix computation really implements this type of computation. The placement of run-time tests is supported by a static data flow analysis framework