Flattening and parallelizing irregular, recurrent loop nests
- 1 August 1995
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 30 (8) , 58-67
- https://doi.org/10.1145/209936.209944
Abstract
Irregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. In this paper, we describe a suite of transformations to automatically parallelize such irregular loop nests, even in the presence of recurrences. We describe a simple, general loop flattening transformation, along with new optimizations which make it a viable compiler transformation. A robust recurrence parallelization technique is coupled to the loop flattening transformation, allowing parallelization of segmented reductions, scans, and combining-sends over arbitrary associative operators. We discuss the implementation and performance results of the transformations in a parallelizing Fortran 77 compiler for the Cray C90 supercomputer. In particular, we focus on important sparse matrix-vector multiplication kernels, for one of which we are able to automatically derive an algorithm used by one of the fastest library routines available.Keywords
This publication has 5 references indexed in Scilit:
- Solving linear recurrences with loop rakingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Parallelizing complex scans and reductionsPublished by Association for Computing Machinery (ACM) ,1994
- Implementation of a portable nested data-parallel languagePublished by Association for Computing Machinery (ACM) ,1993
- Relaxing SIMD control flow constraints using loop transformationsPublished by Association for Computing Machinery (ACM) ,1992
- Scans as primitive parallel operationsIEEE Transactions on Computers, 1989