Improving the structure of loop nests in scientific programs
We conduct a benchmark characterization study to report on the extent to which perfect nests are prresent in 23 applications from 4 standard benchmark suites. Further, we evaluate the effectiveness of 3 transformations for converting imperfect nests into perfect ones: code sinking, loop distribution (with and without scalar expansion) and loop fusion. Using the number of loop nests made perfect by these transformations as a metric is misleading because loop nests impact differently on execution time. Instead, we measure actual execution time of loop nests and use it to asses the effectiveness of each of the transformations. We find that on average, perfect nests contribute to only 39% of the execution time of the benchmarks. Code sinking causes the largest increase in the relative contribution of perfect nests (to 56%,), followed by loop distribution with scalar (to 51%), and loop distribution (to 45%). Loop fusion is found to result in no significant improvement on the relative contribution of perfect nests. In addition, we evaluate the overhead resulting from the use of the transformations and based on the results, suggest a strategy for Using the transformations in a compiler.
loop nests code sinking loop distribution scalar expansion loop fusion high-performance compilers loop transformations