Reuse distance has been shown to be a useful metric for performance analysis of caches and programs, locality analysis and compiler optimization. Concurrent reuse distance profile defined as the reuse distance profile of a thread sharing the cache with many other threads varies from its standalone reuse distance profile due to interference from other threads. Measurement of reuse distance profile through simulation, especially for multi-threaded applications, consumes lot of time. Analytical model based reuse distance prediction can reduce drastically the time taken for exploring the cache memory design space. The objective of this work is to propose an analytical model to find the concurrent reuse distance profile of a thread belonging to multi-threaded applications in a shared memory environment. Using the standalone reuse distance profile of each thread as input, we derive three other reuse distance profiles: 1) The concurrent reuse distance profile of a thread sharing the cache with other threads 2) The combined reuse distance profile of all threads sharing the cache and 3) The coherent reuse distance profile of each thread, considering the coherency effect when each thread runs with private cache. We use Markov chain besides combinatorics and basic probability theory as a main analytical tool for the model. We validate our analytical model against simulations, using the multi-core simulator Sniper for the benchmarks of the PARSEC and the SPLASH benchmark suites.

Reuse distance is an important metric for analytical estimation of cache miss rate. To find the miss rate of a particular cache, the reuse distance profile has to be measured for that particular level and configuration of the cache. Significant amount of simulation time and overhead can be reduced if we can find the miss rate of higher level cache like L2 cache from the RD profile with respect to a lower level cache (i.e., cache that is closer to the processor) such as L1. The objective of this paper is to give an analytical method to find the miss rate of L2 cache for various configurations from the RD profile with respect to L1 cache. We consider all three types of cache inclusion policies namely (i) Strictly Inclusive, (ii) Mutually Exclusive and (iii) Non-Inclusive Non-Exclusive policy. We first prove some general results relating the RD profile of L1 cache to that of L2 cache. We use probabilistic analysis for our derivations. We validate our model against simulations, using the multi-core simulator Sniper with the PARSEC and the SPLASH benchmark suites.