Sparse code generation for imperfectly nested loops with dependences
Vladimir Kotlyar, Keshav K. Pingali · 1997
Standard restructuring compiler tools are based on polyhedral algebra and cannot be used to analyze or restructure sparse matrix codes. We have recently shown that tools based on relational algebra can be used to generate an efficient sparse matrix program from the corresponding dense matrix program and a specification of the sparse matrix format. This work was restricted to DO-ALL loops and loops with reductions. In this paper, we extend this approach to loops with dependences. Although our results are restricted to Compressed Hyperplane Storage formats, they apply to both perfectly nested loops and imperfectly nested loops. 1 INTRODUCTION Although sparse matrix computations are ubiquitous in computational science, research in restructuring compilers has focused almost exclusively on dense matrix programs. This is because the tools used in restructuring compilers are based on the algebra of polyhedra, and can be used only when array subscripts are affine functions of loop index vari...