A Theory of Reads and Writes for Multi-level Caches







Deposit Papers 


Sondag, Tyler and Rajan, Hridesh (2009) A Theory of Reads and Writes for Multi-level Caches. Technical Report 09-20a, Computer Science, Iowa State University.

Full text available as:Adobe PDF

There is a later version of this eprint available: Click here to view it.


A wide range of program analysis and optimization techniques rely on the knowledge of the programs cache behavior. Thus soundness and precision of the underlying cache behavior model is important for these client analyses. Soundness and precision of the cache behavior models are becoming even more important with the recent advent of multi-core and many-core architectures due to two reasons. First, cache sizes are generally small for these architectures, thus precision becomes important. Second large scale sharing of the communication bandwidth between processors and memory potentially creates contention resulting in even larger hit on program's execution-time due to a cache miss, thus the cost of imprecise analysis is higher. The main contribution of this work is a sound technique for cache behavior analysis that advances the state of the art in three dimensions. First, unlike previous work that only work with single-level caches, our technique is able to handle multi-level caches. Second, unlike previous work which handled either instruction or data caches, our technique handles both. Third, and as a consequence of the first advance, we are able to model a variety of multi-level cache policies. Each of these allow our analysis to more closely model cache behavior in currently available general-purpose multi-core and many-core processors such as the Intel Core 2 Duo, TILE64, etc. The technical device that underlies the theory is the definition of live caches. Live caches model relationships between cache levels and help improve the accuracy of analysis.

Keywords:abstract interpretation, cache behavior, program analysis, multi-level cache
Software: PROGRAMMING LANGUAGES: Formal Definitions and Theory (D.2.1, F.3.1-2, F.4.2-3)
ID code:00000614
Deposited by:Tyler Sondag on 11 August 2009

Available Versions of This Paper

Contact site administrator at: