You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact webmaster@ide.mdh.se

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

Fulltext:


Authors:


Publication Type:

Doctoral Thesis

Publisher:

Mälardalen University


Abstract

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.

Bibtex

@phdthesis{Vera500,
author = {Xavier Vera},
title = {Cache and Compiler Interaction (how to analyze, optimize and time cache behavior)},
number = {7},
month = {January},
year = {2004},
school = {M{\"a}lardalen University},
url = {http://www.es.mdh.se/publications/500-}
}