On the complexity of loop fusion
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089795X,p. 149-157
- https://doi.org/10.1109/pact.1999.807510
Abstract
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this paper is to study, from a theoretical point of view, several variants of the loop fusion problem-identifying polynomially solvable cases and NP-complete cases-and to make the link between these problems and some scheduling problems that arise from completely different areas. We study among others, the fusion of loops of different types, and the fusion of loops when combined with loop shifting.Keywords
This publication has 10 references indexed in Scilit:
- Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Loop fusion in high performance FortranPublished by Association for Computing Machinery (ACM) ,1998
- Loop parallelization algorithms: From parallelism extraction to code generationParallel Computing, 1998
- Compiler reduction of invalidation traffic in virtual shared memory systemsPublished by Springer Nature ,1996
- More on the complexity of common superstring and supersequence problemsTheoretical Computer Science, 1994
- Collective loop fusion for array contractionPublished by Springer Nature ,1993
- Routing Printed Circuit Cards Through an Assembly CellOperations Research, 1991
- Automatic translation of FORTRAN programs to vector formACM Transactions on Programming Languages and Systems, 1987
- The shortest common supersequence problem over binary alphabet is NP-completeTheoretical Computer Science, 1981
- The Complexity of Some Problems on Subsequences and SupersequencesJournal of the ACM, 1978