Revisiting loop fusion in the polyhedral framework

Sanyam Mehta, Pei Hung Lin, Pen Chung Yew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

Loop fusion is an important compiler optimization for improving memory hierarchy performance through enabling data reuse. Traditional compilers have approached loop fusion in a manner decoupled from other high-level loop optimizations, missing several interesting solutions. Recently, the polyhedral compiler framework with its ability to compose complex transformations, has proved to be promising in performing loop optimizations for small programs. However, our experiments with large programs using state-of-the-art polyhedral compiler frameworks reveal suboptimal fusion partitions in the transformed code. We trace the reason for this to be lack of an effective cost model to choose a good fusion partitioning among the possible choices, which increase exponentially with the number of program statements. In this paper, we propose a fusion algorithm to choose good fusion partitions with two objective functions-achieving good data reuse and preserving parallelism inherent in the source code. These objectives, although targeted by previous work in traditional compilers, pose new challenges within the polyhedral compiler framework and have thus not been addressed. In our algorithm, we propose several heuristics that work effectively within the polyhedral compiler framework and allow us to achieve the proposed objectives. Experimental results show that our fusion algorithm achieves performance comparable to the existing polyhedral compilers for small kernel programs, and significantly out-performs them for large benchmark programs such as those in the SPEC benchmark suite.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
Pages233-245
Number of pages13
Volume49
DOIs
StatePublished - Aug 2014
Event2014 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014 - Orlando, FL, United States
Duration: Feb 15 2014Feb 19 2014

Other

Other2014 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014
Country/TerritoryUnited States
CityOrlando, FL
Period2/15/142/19/14

Keywords

  • Coarse-grained parallelism
  • Data reuse
  • Loop fusion
  • Polyhedral framework

Fingerprint

Dive into the research topics of 'Revisiting loop fusion in the polyhedral framework'. Together they form a unique fingerprint.

Cite this