Program transformations for cache locality enhancement on shared-memory multiprocessors
Tarek S. Abdelrahman, Naraig Manjikian · 1997
This dissertation proposes and evaluates compiler techniques that enhance cache locality and consequently improve the performance of parallel applications on shared-memory multiprocessors. These techniques target applications with loop-level parallelism that can be detected and exploited automatically by a compiler. Novel program transformations are combined with appropriate loop scheduling in order to exploit data reuse while maintaining parallelism and avoiding cache conflicts. First, this dissertation proposes the shift-and-peel transformation for enabling loop fusion and exploiting reuse across parallel loops. The shift-and-peel transformation overcomes dependence limitations that have previously prevented loops from being fused legally, or prevented legally-fused loops from being parallelized. Therefore, this transformation exploits all reuse across loops without loss of parallelism. Second, this dissertation describes and evaluates adaptations of static loop scheduling strategies to exploit wavefront parallelism while ensuring locality in tiled loops. Wavefront parallelism results when tiling is enabled by combining the shift-and-peel transformation with loop skewing. Proper scheduling exploits both intratile and intertile data reuse when independent tiles are executed in parallel on a large number of processors. Third, this dissertation proposes cache partitioning for preventing cache conflicts between data from different arrays, especially when exploiting reuse across loops. Specifically, cache partitioning prevents frequently-recurring conflicts in loops with compatible data access patterns. Cache partitioning transforms the data layout such that there are no conflicts for reused data from different arrays during loop execution. An analytical model is also presented to assess the potential benefit of locality enhancement. This model estimates the expected reduction in execution time by parameterizing the reduction in the number of memory accesses with locality enhancement and the contribution of memory accesses towards execution time. Experimental results show that the proposed techniques improve parallel performance by 20%-60% for representative applications on contemporary multiprocessors. The results also show that significant improvements are obtained in conjunction with other performance-enhancing techniques such as prefetching. The importance of the techniques described in this dissertation will continue to increase as processor performance continues to increase more rapidly than memory performance.