Next: Experimental Framework Up: Tolerating Latency Through Software-Controlled Previous: Implementation Experience

Prefetching for Uniprocessors

In this chapter, we evaluate the performance benefits of prefetching for array-based uniprocessor applications. Section describes the experimental framework used throughout this chapter, including our architectural assumptions, benchmarks, compile-time parameters, and simulation environment. The results of these experiments are presented in four major subsections. First, Section contains a detailed evaluation of the algorithm described in the previous chapter for prefetching affine array references. We observe that each component of this core compiler algorithm is effective at achieving its goal, thereby improving overall execution time by as much as twofold. Second, Section evaluates the robustness of this algorithm by varying the compile-time parameters that are determined heuristically rather than precisely for a specific architecture (i.e. the effective cache size, the target memory latency, and the policy on unknown loop bounds). The results show that these parameter variations affect only a small subset of the applications, and the performance impact in those cases is generally small; therefore the algorithm appears to be robust. Third, having already examined prefetching in isolation, Section evaluates the interaction between prefetching and another powerful latency-hiding technique for dense-matrix codes: locality optimizations. The results illustrate that prefetching and locality optimizations are complementary, and therefore should be combined. Finally, having focused thus far only on affine array references, we extend our core algorithm in Section to handle indirect references, which allows us to prefetch sparse-matrix codes. The results demonstrate that this relatively straightforward extension improves performance by as much as an additional 20%. Finally, we conclude the chapter in Section with a summary of the important results.

Sat Jun 25 15:13:04 PDT 1994