CASHT: Contention Analysis in Shared Hierarchies with Thefts
Open Access
- 23 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 19 (1), 1-27
- https://doi.org/10.1145/3494538
Abstract
Cache management policies should consider workloads’ contention behavior when managing a shared cache. Prior art makes estimates about shared cache behavior by adding extra logic or time to isolate per workload cache statistics. These approaches provide per-workload analysis but do not provide a holistic understanding of the utilization and effectiveness of caches under the ever-growing contention that comes standard with scaling cores. We present Contention Analysis in Shared Hierarchies using Thefts, or CASHT,1 a framework for capturing cache contention information both offline and online. CASHT takes advantage of cache statistics made richer by observing a consequence of cache contention: inter-core evictions, or what we call THEFTS. We use thefts to complement more familiar cache statistics to train a learning model based on Gradient-boosting Trees (GBT) to predict the best ways to partition the last-level cache. GBT achieves 90+% accuracy with trained models as small as 100 B and at least 95% accuracy at 1 kB model size when predicting the best way to partition two workloads. CASHT employs a novel run-time framework for collecting thefts-based metrics despite partition intervention, and enables per-access sampling rather than set sampling that could add overhead but may not capture true workload behavior. Coupling CASHT and GBT for use as a dynamic policy results in a very lightweight and dynamic partitioning scheme that performs within a margin of error of Utility-based Cache Partitioning at a 1/8 the overhead.Keywords
This publication has 40 references indexed in Scilit:
- HOTLACM SIGPLAN Notices, 2013
- The gradient-based cache partitioning algorithmACM Transactions on Architecture and Code Optimization, 2012
- SniperPublished by Association for Computing Machinery (ACM) ,2011
- VantageACM SIGARCH Computer Architecture News, 2011
- High performance cache replacement using re-reference interval prediction (RRIP)ACM SIGARCH Computer Architecture News, 2010
- PIPPACM SIGARCH Computer Architecture News, 2009
- The open science gridJournal of Physics: Conference Series, 2007
- Adaptive insertion policies for high performance cachingACM SIGARCH Computer Architecture News, 2007
- Automatically characterizing large scale program behaviorACM SIGOPS Operating Systems Review, 2002
- Hypothesis testing and information theoryIEEE Transactions on Information Theory, 1974