Cache and Compiler Interaction (how to analyze, optimize and time cache behavior)

Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. In addition, caches are a source of unpredictability, resulting in programs sometimes behaving in a different way than expected.Detailed information about the number of cache misses and their causes allows us to predict cache behavior and to detect bottlenecks. Small modifications in the source code may change memory patterns, thereby altering the cache behavior. Code transformations which take the cache behavior into account might result in a high cache performance improvement. However, cache memory behavior is very hard to predict, thus making the task of optimizing and timing cache behavior very difficult.This dissertation proposes and evaluates a new compiler framework that analyzes and tunes cache behavior. The proposed framework is based on a new characterization of data reuse across multiple loop nests, which allows analyzing the cache behavior of whole programs with regular computations. The framework uses an accurate cost model that describes misses across different cache levels and considers the effects of other hardware components such as branch predictors, which drives the application of tiling and padding transformations. In order to select the best parameter values, we combine the cost model with a genetic algorithm to compute tile and pad factors that enhance the program performance.Finally, our method explores the use of cache partitioning and dynamic cache locking to provide worst-case performance estimates in a safe and tight way for multitasking systems. We use cache partitioning, which divides the cache among tasks to eliminate inter-task cache interferences. We combine static cache analysis and cache locking mechanisms to ensure that all intra-task conflicts, and consequently, memory access times, are exactly predictable.The results of our experiments demonstrate the capability of our framework to describe cache behavior at compile time. Extensive validation shows that our accurate cost model is appropriate to achieve significant speedups compared to state-of-the-art techniques. This dissertation also compares our timing approach with a system with a non-partitioned but statically locked data cache. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, demonstrating that our fully predictable scheme does not compromise the performance of the transformed programs.