Abstract: Aiming at improving the performance of the default loop scheduling and tile size of Pluto, a commonly used polyhedral compiler, this paper proposes a method to compute a variety of legal permutations for its default scheduling and auto-tune its performance according to the configuration space composed of permutations and tile sizes. Through the processing of scalar dimension that defines loop fusion, both intra and inter permutations for imperfect loop nest are realized. Four machine learning driven auto-tuning strategies are proposed to find the optimized combination of permutation order and tile size for a loop with a given problem size. Under the default tile size, the optimal permutation gene- rated by the extended Pluto compiler in a parallel environment achieves a maximum speedup of 4.02  and a geometric mean of 2.12 compared with the default scheduling of Pluto. By further searching for a better combination of permutation order and tile size, the best auto-tuning strategy achieves a maximum speedup of 5.48  and a geometric mean of 2.86 compared with Pluto's default optimization in a parallel environment. In addition, the best configuration and the learned model obtained by auto-tuning for a particular problem size, when being applied to similar problem sizes, also outperform the default optimization of Pluto in various degrees.

Key words: loop permutation, loop tiling, polyhedral model, auto-tuning, machine learning