Distributing and Parallelizing Non-canonical Loops
summary
An algorithm that builds a data flow graph, collapses it into a condensation graph, computes a proper saturated covering and emits loop-fissioned code, proven to preserve semantics and to work when the iteration space is unknown. Implementation maps the IR to C and injects OpenMP directives automatically; benchmarks show comparable execution-time speedups to a state-of-the-art source-to-source tool on canonical loops and succeed on many non-canonical loops the other tool cannot transform. The artifact is open source.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:06Loop Optimization
- 3:55Our Technique
- 5:26Technique Overview
- 6:11Program Under Analysis
- 7:18Variables in Command C
- 8:34Data Flow Graph (DFG)
- 10:36Correction
- 11:29Algorithm
- 11:58Dependence Graph
- 13:21Condensation Graph & Covering
- 14:30Example
- 17:21Experimental Evaluation
- 19:00Experimental Results
- 22:59Conclusion
related talks
25mAn Empirical Study of the Effect of Source-level Loop Transformations on Compiler Stability
14mOn-Stack Replacement for Program Generators and Source-to-Source Compilers
17mFuzzing Loop Optimizations in Compilers for C++ and Data-Parallel Languages
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
19mCompiling Recurrences over Dense and Sparse Arrays
01h 02mHydroflow: A Compiler Target for Fast, Correct Distributed Programs
14mAchieving High-Performance the Functional Way - A Functional Pearl on Expressing High...
16mBeyond Relooper: Recursive Translation of Unstructured Control Flow to Structu…