On the Applicability of Program Comprehension Techniques to the Automatic Parallelization of Sparse Matrix Computations

Space-efficient data structures for sparse matrices are an important concept in numerical programming because they allow for considerable savings in space and time compared with common two--dimensional arrays. Unfortunately, for such programs it is usually impossible to statically determine all data dependencies. Thus, automatic parallelization of such codes is usually done at run time by applying the inspector-executor technique, incurring tremendous overhead. Program comprehension techniques exploit knowledge on frequently occurring implementation variations of important computations. They have been shown to improve many important fields of automatic parallelization of dense matrix computations, such as automatic program transformation and local algorithm replacement, data flow analysis, array distribution, and performance prediction. In this study we investigate up to which degree this approach could be generalized to sequential codes implementing sparse matrix computations, and h..