SHF: Small: Locality-Aware Concurrency Platforms

Washington University, Saint Louis MO

Investigators

Abstract

Title: SHF: Small: Locality-Aware Concurrency Platforms Modern machines have complex memory hierarchies consisting of many levels of "cache" that must be utilized effectively to gain performance. A program is said to have good locality or cache efficiency if its execution can utilize the underlying cache memory hierarchy effectively. Since the speed of processors is growing faster than the memory access latency, it is often more important to optimize one's program for locality than to minimize the number of instructions executed on the processor. With the prevalence of "multicore" systems, optimizing for locality becomes even more critical, since increase in the number of cores on a processor puts pressure on both the memory bandwidth and capacity available for each core. Writing parallel programs that utilize the cache hierarchy effectively for existing multicore machines is challenging, however. This project aims to develop a parallel programming platform that enables the programmer to program a parallel machine without worrying about locality, and the platform transforms and executes the program in a cache-efficient way. In terms of intellectual merits, this research will advance the understanding of scheduling algorithms, compiler transformations, and runtime automation. The project's broader importance is that programmers will be able to write portable, high-performant and cache-efficient programs for multicore systems while significantly reducing the programming effort compared to the traditional approach in writing cache-efficient code. The platform produced by this project will be made freely available on the World Wide Web, which can enable highly-efficient software. Writing cache-efficient parallel programs is challenging, because locality in a parallel program is a function of algorithm design, scheduling, and underlying machine configuration, and these factors are often tightly coupled. In addition, on parallel platforms, the performance depends on both load-balancing and cache efficiency, and these are often competing objectives. To design a locality-aware parallel programming platform, the project will take an integrated approach that combines efforts in scheduling theory, algorithmic design, runtime system support, and compiler transformations. In the realm of scheduling theory, the PIs will systematically study the trade-offs between load-balancing and cache efficiency, and design schedulers that provide sensible guarantees for both. Since cache-efficiency also depends on the program itself, the PIs will study the design patterns of cache-efficient algorithms and draw on this experience to investigate a set of program transformations to convert an ordinary program into one that can be executed in a cache efficient manner. These insights will be implemented in a prototype concurrency platform consisting of a compiler and a runtime system in order to study efficient mechanisms to support provably good policies developed for scheduling parallel programs in a cache-efficient manner.