High Performance Caching Based On Reuse Distance Prediction And Streaming Characterization

Along with the development of microprocessor technology, the gap between theperformance of processor and the performance of memory subsystem is increasing.On-chip caches are effective in bridging the performance gap between the processorand the memory subsystem, which exploit data locality in the programs. Many re-searches have been dedicated to cache replacement policy due to its key importanceto the cache performance. Traditional cache replacement policy fails to accommodatethe special streaming access patterns exhibited by many modern applications, leadingto decreased cache performance. In this dissertation, we explore the cache replace-ment policy on last-level caches, with regards to the diverse streaming access patternsexposed by applications. We make the following contributions:(1) A period detection based reuse distance prediction technology, PDRDP inshort, is proposed for last-level caches. PDRDP is memory instruction pointer (IP)independent, being able to capture the periodic regularity in reuse distance sequences.We show that PDRDP improves the prediction accuracy over the traditional confidencecounter based predictor by 18.3% on average. Especially, we characterize the pre-dictability in reuse distances of SPEC CPU2000 benchmark suite. A class of programsare found to have high predictability degree in reuse distance, which are good candi-dates for cache replacement policy based on reuse distance prediction.(2) A stream detection algorithm based on access reordering mapping table,ARMT in short, is presented. ARMT reorganizes the memory access sequences in ad-dress incremental order, then exloits the existing stream detection engines to recognizestreaming behavior in programs, and thus improves the coverage of stream detection.It is simple and low overheaded. The experimental results show that ARMT improvesthe coverage of stream detection and is able to recognize more long streams. It is alsofound to improve the quality of detected streams across a class of programs.(3) A new cache replacement policy called RDP is proposed, which is based on reuse distance prediction and stream sampling. RDP monitors the reuse distance withextended tag array in caches and predicts the reuse distance with our proposed PDRDP.RDP adjusts the replacement priority of cache blocks dynamically according to theprediction results, and thus reduces the cache misses. It adapts to diverse streamingaccess patterns in programs. The experimental results show that RDP outperforms thetraditional LRU policy and recently proposed DIP policy on average. On large last-level caches, RDP improves the cache performance across one class of programs withstrong streaming access patterns significantly, by 27.5% on average on a 32MB cache.