Increase Parallel Granularity and Data Locality by Unimodular Metrics
Ma Guo · Chinese Journal of Computers · 2004
In this paper we discussed a loop transformation method which would increase the granularity of the loop body and improve the data locality of the transformed loop: By analyzing the dependence vector set of the given nested double-loop, we could merge several nodes in the iteration space, which have same outer loop variable value and different inner loop variable value into one node in the folded iteration space, while preserving the parallelism of inner loop at the same time. Thus, we increased the granularity of the parallel loop body. Furthermore, we discussed how to find a unimodular metrics to transform the given iteration space with the given dependence into an iteration space in which iteration nodes could be merged using our methods given above. We also present a method to preserve the locality of the original loop while doing our loop transformation and iteration space folding. Our method discussed in this article is the generalization of the wavefront method. Compared with the wavefront method, our method can achieve higher performance due to larger granularity and better data locality. We apply our method to ygx, a program of the IAPCM Benchmark, to evaluate the effect the technique. The experiment data show that our method can spare the execution time by 22% compared with the wavefront method when the program is parallel processed by 4 CPU’s on SGI origin 200 system which is a typical 4 CPU’s SMP architecture.