Xiameng Hu, Xiaolin Wang, Lan Zhou, Yingwei Luo, Peking University; Chen Ding, University of Rochester; Zhenlin Wang, Michigan Technological University
The reuse distance (LRU stack distance) is an essential metric for performance prediction and optimization of storage and CPU cache. Over the last four decades, there have been steady improvements in the algorithmic efficiency of reuse distance measurement. This progress is accelerating in recent years both in theory and practical implementation.
In this paper, we present a kinetic model of LRU cache memory, based on the average eviction time (AET) of the cached data. The AET model enables fast measurement and low-cost sampling. It can produce the miss ratio curve (MRC) in linear time with extremely low space costs. On both CPU and storage benchmarks, AET reduces the time and space costs compare to former techniques. Furthermore, AET is a composable model that can characterize shared cache behavior through modeling individual programs.
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
BibTeX
@inproceedings {196237,
author = {Xiameng Hu and Xiaolin Wang and Lan Zhou and Yingwei Luo and Chen Ding and Zhenlin Wang},
title = {Kinetic Modeling of Data Eviction in Cache},
booktitle = {2016 USENIX Annual Technical Conference (USENIX ATC 16)},
year = {2016},
isbn = {978-1-931971-30-0},
address = {Denver, CO},
pages = {351--364},
url = {https://www.usenix.org/conference/atc16/technical-sessions/presentation/hu},
publisher = {USENIX Association},
month = jun
}
