archives

An Abstract Domain for Multi-level Caches


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Sondag, Tyler and Rajan, Hridesh (2010) An Abstract Domain for Multi-level Caches. Technical Report 09-20b, Computer Science, Iowa State University.

Full text available as:Adobe PDF

This is the latest version of this eprint.

Abstract

Many program analyses and optimizations rely on knowledge of cache behavior. The precision of the underlying cache model is increasingly important with the recent uptake of multi-core and many-core architectures for two reasons. First, per-core cache sizes generally decrease as the number of cores becomes large resulting in more cache misses. Second, large scale sharing of the communication bandwidth to memory increases contention resulting in greater cost of cache misses. We present a sound technique for cache behavior analysis that handles instruction and data caches as well as a variety of multi-level cache policies. The resulting analysis is applicable to current general-purpose processors. Our technique relies on a new abstraction, live caches which model relationships between cache levels to improve accuracy of multi-level cache analysis. In an existing many-core cache configuration, live caches improve L2 hit accuracy by an average of 5.7%. Among others, this reduces the upper bound on memory accesses for worst case execution time (WCET) by an average 6.4%.

Keywords:abstract interpretation, cache behavior, program analysis, multi-level cache
Subjects:Software: PROGRAMMING LANGUAGES
Software: PROGRAMMING LANGUAGES: General
Software: PROGRAMMING LANGUAGES: Formal Definitions and Theory (D.2.1, F.3.1-2, F.4.2-3)
ID code:00000632
Deposited by:Tyler Sondag on 01 April 2010

Available Versions of This Paper



Contact site administrator at: ssg@cs.iastate.edu