Skip to Main content Skip to Navigation
Journal articles

Performance analysis methods for list-based caches with non-uniform access

Giuliano Casale 1 Nicolas Gast 2
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state space explosion. In this setting, we propose novel methods to analyze performance for a general class of list-based caches with tree structure, non-uniform access to items and lists, and random or first-in first-out replacement policies. Even though the underlying Markov process is shown to admit a product-form solution, this is difficult to exploit for large caches. Thus, we develop novel approximations for cache performance metrics, in particular by means of a singular perturbation method and a refined mean field approximation. We compare the accuracy of these approaches to simulations, finding that our new methods rapidly converge to the equilibrium distribution as the number of items and the cache capacity grow in a fixed ratio. We find that they are much more accurate than fixed point methods similar to prior work, with mean average errors typically below 1.5% even for very small caches. Our models are also generalized to account for synchronous requests, fetch latency, and item sizes, extending the applicability of approximations for list-based caches.
Complete list of metadata

https://hal.inria.fr/hal-03102188
Contributor : Nicolas Gast <>
Submitted on : Thursday, January 7, 2021 - 2:25:04 PM
Last modification on : Friday, January 8, 2021 - 1:21:12 PM
Long-term archiving on: : Thursday, April 8, 2021 - 7:12:45 PM

File

main-rev2.pdf
Files produced by the author(s)

Identifiers

Citation

Giuliano Casale, Nicolas Gast. Performance analysis methods for list-based caches with non-uniform access. IEEE/ACM Transactions on Networking, IEEE/ACM, 2020, pp.18. ⟨10.1109/TNET.2020.3042869⟩. ⟨hal-03102188⟩

Share

Metrics

Record views

26

Files downloads

52