On the complexity of loop fusion

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 report 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.
Document type :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101854
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:10 AM
Last modification on : Sunday, May 19, 2019 - 1:20:46 AM

File

RR1998-50.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101854, version 1

Collections

Citation

Alain Darte. On the complexity of loop fusion. [Research Report] LIP RR-1998-50, Laboratoire de l'informatique du parallélisme. 1998, 2+17p. ⟨hal-02101854⟩

Share

Metrics

Record views

5

Files downloads

10