Abstract
An approach of generation of tiled code with an arbitrary order of loops within tiles is presented. It is based on the transitive closure of the program dependence graph and derived via a combination of the Polyhedral and Iteration Space Slicing frameworks. The approach is explained by means of a working example. Details of an implementation of the approach in the TRACO compiler are outlined. Increasing tiled program performance due to loop permutation within tiles is illustrated on real-life programs from the NAS Parallel Benchmark suite. An analysis of speed-up and scalability of parallel tiled code with loop permutation is presented.
Keywords
- Optimizing compilers
- tiling
- loop permutation
- transitive closure
- dependence graph
- code locality
- automatic parallelization
MSC
68N20, 65Y05, 52Bxx, 97E60, 05-XX
Cite this article
@article{cai-3363,
author = {Marek Palkowski and Wlodzimierz Bielecki},
title = {Parallel Tiled Code Generation with Loop Permutation within Tiles},
journal = {Computing and Informatics},
volume = {36},
number = {6},
pages = {1261--1282},
year = {2017},
issn = {1335-9150},
doi = {10.4149/cai_2017_6_1261}
}
TY - JOUR AU - Marek Palkowski AU - Wlodzimierz Bielecki TI - Parallel Tiled Code Generation with Loop Permutation within Tiles JO - Computing and Informatics VL - 36 IS - 6 SP - 1261 EP - 1282 PY - 2017 SN - 1335-9150 DO - 10.4149/cai_2017_6_1261 UR - https://doi.org/10.4149/cai_2017_6_1261 KW - Optimizing compilers KW - tiling KW - loop permutation KW - transitive closure KW - dependence graph KW - code locality KW - automatic parallelization ER -
Palkowski, M., & Bielecki, W. (2017). Parallel Tiled Code Generation with Loop Permutation within Tiles. Computing and Informatics, 36(6), 1261–1282. https://doi.org/10.4149/cai_2017_6_1261