Cache Modeling and Optimization using Miniature Simulations

Website Maintenance Alert

Due to scheduled maintenance, the USENIX website will not be available on Tuesday, December 17, from 10:00 am to 2:00 pm Pacific Daylight Time (UTC -7). We apologize for the inconvenience.

If you are trying to register for Enigma 2020, please complete your registration before or after this time period.

Authors: 

Carl Waldspurger, Trausti Saemundsson, and Irfan Ahmad, CachePhysics, Inc.; Nohhyun Park, Datos IO, Inc.

Awarded Best Paper!

Abstract: 

Recent approximation algorithms (e.g., CounterStacks, SHARDS and AET) make lightweight, continuously-updated miss ratio curves (MRCs) practical for online modeling and control of LRU caches. For more complex cache-replacement policies, scaled-down simulation, introduced with SHARDS, offers a general method for emulating a given cache size by using a miniature cache processing a small spatially-hashed sample of requests.

We present the first detailed study evaluating the effectiveness of this approach for modeling non-LRU algorithms, including ARC, LIRS and OPT. Experiments with over a hundred real-world traces demonstrate that scaled-down MRCs are extremely accurate while requiring dramatically less space and time than full simulation.

We propose an efficient, generic framework for dynamic optimization using multiple scaled-down simulations to explore candidate cache configurations simultaneously. Experiments demonstrate significant improvements from automatic adaptation of parameters including the stack size limit in LIRS, and queue sizes in 2Q.

Finally, we introduce SLIDE, a new approach inspired by Talus that uses scaled-down MRCs to remove performance cliffs automatically. SLIDE performs shadow partitioning transparently within a single unified cache, avoiding the problem of migrating state between distinct caches when partition boundaries change. Experiments demonstrate that SLIDE improves miss ratios for many cache policies, with large gains in the presence of cliffs.

Open Access Media

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 {203257,
author = {Carl Waldspurger and Trausti Saemundsson and Irfan Ahmad and Nohhyun Park},
title = {Cache Modeling and Optimization using Miniature Simulations},
booktitle = {2017 {USENIX} Annual Technical Conference ({USENIX} {ATC} 17)},
year = {2017},
isbn = {978-1-931971-38-6},
address = {Santa Clara, CA},
pages = {487--498},
url = {https://www.usenix.org/conference/atc17/technical-sessions/presentation/waldspurger},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Audio

Award: