Skip to Main content Skip to Navigation
Conference papers

Cache Replacement Policy Using Map-based Adaptive Insertion

Abstract : In this paper, we propose a map-based adaptive insertion policy (MAIP) for a novel cache replacement. The MAIP estimates the data reuse possibility on the basis of data reuse history. To track data reuse history, the MAIP employs a bitmap data structure, which we call memory access map. The memory access map holds all memory accessed locations in a fixed sized memory area to detect the data reuse. It can cover a large memory area that is compared to the size of a large L3 cache memory. The MAIP can use a large amount of data reuse history from the memory access map. On the basis of reuse history from both the original cache tag and the memory access map, the MAIP estimates reuse possibility of the incoming line in terms of two metrics: (1) spatial locality and (2) temporal locality. The combination of these metrics improves the accuracy of the reuse possibility estimation because each locality supports different memory access patterns. When the reuse possibility is insufficient, the incoming cache line is not inserted into the MRU position so as to evict it before other cache lines. We evaluate the MAIP by performing a simulation study. The simulation result shows that the MAIP reduces the cache miss count by 8.3% compared to the LRU policy while the Dynamic Insertion Policy (DIP) reduces the cache miss count by 0.1%. The MAIP improves performance by 2.1% in a single-core configuration and by 9.1% in a multi-core configuration compared with the traditional LRU policy.
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Thursday, June 17, 2010 - 3:18:33 PM
Last modification on : Monday, May 17, 2021 - 12:00:04 PM
Long-term archiving on: : Monday, September 20, 2010 - 5:32:26 PM


Files produced by the author(s)


  • HAL Id : inria-00492985, version 1



yasuo Ishii, Mary Inaba, Kei Hiraki. Cache Replacement Policy Using Map-based Adaptive Insertion. JWAC 2010 - 1st JILP Worshop on Computer Architecture Competitions: cache replacement Championship, Jun 2010, Saint Malo, France. ⟨inria-00492985⟩



Record views


Files downloads