Software approaches to memory latency reduction for scalable shared-memory multiprocessors

Scalable shared-memory multiprocessors typically have distributed memory with various modules being relatively closer to some groups of processors than to others. From a particular processor, accesses to the farthest memory module can be a few orders of magnitude slower than accesses to the local one. The performance of these machines is thus constrained by average memory access latency. Software techniques are needed for reducing memory latency. Without software support for attaining locality, data might be placed in a memory module far away from the processor using the data, significantly reducing performance. This thesis focuses on the development and evaluation of new software techniques that improve data locality in main memory and cache. These techniques are (1) a data transformation framework that optimizes data layout in shared-memory, (2) dynamic load balancing schemes that reduce mismatching accesses and achieve load balancing, and (3) a cache affinity-based scheme for cache coherence that reduces the frequency of coherence misses. In uniprocessors, arrays are mapped onto memory in either row-major or column-major fashion. In scalable shared-memory multiprocessors, such mappings cause many unnecessary remote memory accesses. We propose data transformations that map the original arrays into desirable placements in the memory modules. Without changing the original array references in programs, the actual accesses to these arrays will be translated into less expressive accesses to mapped arrays. Complementary to loop transformations that mainly maximize parallelism, data transformations provide better data layout in the memory hierarchy, and improve data locality in both local memory and cache. We also develop a set of C macros, called NUMACROS, that implements data distributions (a subset of data transformations) and facilitates parallel programming with data distributions and loop partitioning. Load balancing in parallel applications becomes an important issue when the iteration execution times or the task sizes have high variance. We develop a new loop scheduling technique, Locality-based Dynamic Scheduling (LDS), that allows for the variance in iteration execution times, and a new partitioning technique, called Overpartitioning, that allows for the variance of task sizes. LDS retains data locality while balancing load in scalable shared-memory environments where locality is important. Overpartitioning has been applied to different sorting algorithms, and the resulting algorithms outperform other parallel sorting methods on shared-memory machines. The effective use of cache can significantly reduce average memory access time. Cache coherence is an important issue in multiprocessors. Most current compiler-directed schemes for cache coherence ignore cache reuse across parallel loops, resulting in many coherence misses. With increasing cache size, such cache reuse becomes more important to performance. We develop the Cache Affinity-based Scheme (CAS) which allows valid data to reside in caches across parallel loops, resulting in higher cache hit ratios than other soft ware schemes that have been proposed. We experimentally evaluate our new software techniques on two scalable multiprocessors Hector and the KSR1. Our benchmarks include a set of kernel parallel programs (such as matrix multiplication and LU decomposition), NAS Parallel benchmarks, and parallel sorting. With our software techniques, these kernels and applications achieve nearly linear speedups on both Hector and the KSR1.