Interprocedural Compiler Analysis for Reducing Memory Latency

Abstract

The growing discrepancy between the processor and the memory speed forces us to find a way to improve the performance of memory systems. In a current typical memory system, a cache miss incurs heavy penalty in terms of latency. With shared-memory multiprocessors, the problem of high memory latency is more pronounced than uniprocessor systems because most or all of the main memory system is remote to the processor, whose accesses are significantly slower than accesses to the cache and the local memory. This thesis makes three contributions towards the reduction of remote memory accesses. First, we present an interprocedural compiler analysis to statically align the scheduling of the parallel tasks and to allocate data so as to reduce the number of remote memory references. Second, most compiler tedmiques for data locality enhancement benefit more from static task scheduling methods, but static scheduling potentially results in unbalanced workload among the processors. This thesis proposes a compiler algorithm to identify parallel loops with relatively balanced operation counts in their iterations. Furthermore, we describe an experiment to compare the workload balance under different task scheduling methods. Third, this thesis examines the interaction between different. levels of memory mapping on Cache Coherent, Non Uniform Memory Access (CC-NUMA) multiprocessors and compares several mapping alternatives. Event-driven simulations a.re performed to examine the effectiveness of our compiler techniques and to compare different mapping alternatives. The simulation results show that data allocation schemes often make a great impact on the execution time even with sizable private caches and that our compiler schemes perform consistently well.