CASHT: Contention Analysis in Shared Hierarchies with Thefts

We define THEFTS as workload interactions in the last-level cache that result in an eviction. Counting thefts requires capturing these interactions, which we show in Figure 1(a). Given unique data request streams from two cores, we see how both share a four-way cache employing the least recently used (LRU) as the eviction policy to choose which block is removed first. The first THEFT happens at sequence #6 where core 2 requests data block E, cannot find it in the cache, and needs to evict the LRU block (B) from the set so E can be written. Core 1 inserted Block B at #2, so core 2 evicting block B means core 2 executes a THEFT of resources from core 1. We see similar occurrences at #10 (Core 1 executes theft on Core 2) and #15 (Core 2 executes theft on Core 1). In this way, we can capture a new event with a simple equivalence comparator that is out of the critical path. Further, the context of interaction means there is also perspective, i.e., if we look at the first theft event, then we see that core 2 executes a THEFT and core 1 experiences INTERFERENCE. Moving forward, we refer to the execution and experience of thefts as THEFTS and INTERFERENCE, respectively.

Thefts can result in misses but not all misses are thefts. Given that thefts are a type of eviction, we must consider the relationship between misses caused by evictions, or conflict misses. Figure 1(b) compares conflict misses captured in isolation to cache thefts and interference. The order of magnitude difference between conflict misses when compared to thefts and interference show that contention is not a consequence of a workload not fitting in cache but of forcing applications to contend in a limited space. Certainly, we can consider the working set of the mix as one working set and take thefts as conflict misses, but we lose the unique and nuanced behavior of each workload.

Detecting thefts is a simple process that requires simple modifications of miss detection logic: adding a core or thread ID comparator, and access type comparator. We assume the system represented in this and the remaining algorithms do not employ simultaneous multi-threading (SMT), so the CPU ID indicates physical core ID. In the case of SMT, a thread ID could be used. Algorithm 1 describes how we employ native contention tracking (NCT) to detect when evictions of valid cache blocks are thefts. On a miss, we check whether the cache block chosen by the eviction policy is valid and whether the CPU ID of the block and the CPU ID of the accessing CPU are different. If this holds, then we have detected contention and can update counters. Assuming the access type is not a writeback, we can update the theft counter for the accessing CPU and the interference counter of the CPU that initially inserted the eviction candidate block. If the access type IS a writeback, then we DO NOT update the theft counter. The reason for not updating the thefts counter is because we want to make thefts a distinct action taken by the related CPU, not a consequence of the upper-level caches not having the capacity to hold modified data.

Cache statistics are often used in characterization studies and feature heavily in results coming from simulation environments [7, 19, 22, 34]. Commonly used statistics include cache hits, misses, evictions, and these can be broken down further by access type. Such metrics still contribute great information for analysis, but growing cache hierarchies hide and obscure relationships that statistics like hits and misses are frequently used to determine. For example, we have reached a point with deep cache hierarchies and scaling cores that misses can mean something dire or simply be a consequence of the application. We believe misses and other familiar information lack context of the new shared cache paradigm and should be offset with contention information like thefts. To demonstrate this, we show results from conducting Pearson and Spearman statistical significance tests on miss-based heuristics like Miss Rate (\(\frac{misses}{accesses}\)), Misses per 1,000 Instruction (MPKI), and similarly formulated theft- and interference-based heuristics in Table 1. Each cache statistic data set is tested against a data-set composed of the instructions per cycle (IPC) from a common set of 860, different two-workload trace experiments. All features are normalized between 0 and 1 per respective features (for example, all thefts are normalized between 0 and 1 according to the maximum and minimum theft across all experiments). Pearson tests determine the linear correlation, or whether two data sets are linearly independent by computing a correlation coefficient (R) bound between \(-1\) and 1 (0 means little to no correlation) and the P-value, which indicates if the result is statistically significant (P < 0.05 or 0.1 often acceptable) [6]. Spearman rank correlation determines if two sets of data can be described by a monotonic function, and has similar implications regarding R- and P-values. While not as strong in all cases, theft- and interference-based metrics have a clear statistical significance (P well below 0.05). In fact, the correlation of thefts per miss demonstrates that thefts complement and are complemented by misses, and they help characterize potential relationships between misses due to contention and performance.

Agnostic Contention Estimation, or ACE affords us the ability to track contention agnostic of the contention-mitigation methods enforced in the cache. Specific to cache partitioning, ACE leverages the LRU stack to determine when a partition prevents eviction of the true LRU when that block is in another partition. ACE tests if the current eviction candidate provided by the replacement policy is LRU on a cache miss. If the candidate is not LRU, then we traverse the set until we find either the LRU block or the block with the highest LRU value exclusive of the eviction candidate. To avoid double-counting of prevented contention, we skip blocks that have the theft bit set, which indicates we prevented an eviction on this block on previous access. If we find a block that meets our criteria, then theft estimates for the CPU inserting a new block and interference estimates for the CPU that inserted the protected block are incremented only if the CPU identifiers do not match. ACE does have time and area overhead when employed as we describe (Section 3.3), but we simplify this by comparing the LRU stack position of a replacement candidate to LRU to avoid CPU ID overhead. The time to traverse the set for the next nearest replacement candidate can also be avoided by finding the set-wide LRU and using the associated CPU ID to update interference counters.

Figure 2 compares our theft estimates from ACE to thefts captured in an un-partitioned cache. We do this by normalizing theft estimates collected in all possible partitioning configurations to real thefts captured in the un-partitioned cache, which we illustrate on the y-axis (higher than 1 means over-estimation, and lower than 1 means under-estimation). The x-axis shows the name of the benchmark our traces are derived from, and data is represented as box plots, because for each trace we have 15 times 41 different data points from our partitioning studies. The figure shows the mean of most box plots is near 1, so our estimates do capture expected behavior, but the upper and lower bounds are orders of magnitude away from this mean. Such wide ranges of normalized theft estimates speak to the capacity sensitivity and utility of partitioning solutions. Further, estimating contention with ACE has the consequence of enabling per access sampling. Cache set sampling is the common method of collecting cache statistics on certain cache sets that the architect designates at design time, either as an Associative Tag Directory (ATD), which needs additional hardware, or In-cache Estimation (ICE), which needs a subset of cache not managed like the rest of cache [32, 48]. Prior work employs these techniques to great effect [21, 31, 32, 46], but only sample accesses to selected sets, which runs the risk of misrepresenting workload behavior and can lead to different conclusions about a given workload.

Modern cache sampling logic is built such that the number of cache sets chosen to be sampled implies a ceiling on cache accesses to be sampled. We can define this ceiling as follows:where s is the number of cache sets designated for sampling and S is the total number of cache sets. The concern with the sampled access ceiling is that the amount of sampled accesses may never approach it, because not every designated set (fixed or randomly selected) may be accessed by any workload. PSA employs the sampled ceiling as a probability threshold over which no statistical accounting can occur.

A comparison of sampler hit rates in Figure 3 shows PSA replicates full workload hit rate more reliably than both ATD and ICE. The summary in Table 2 shows PSA captures 99% of the full hit rate for SPEC 2017 traces on average while ATD and ICE over-estimate (are optimistic) hit rate by 2.98% and 2%, respectively. The data in Figure 3 shows sampled hit rates captured by each of the sampling techniques normalized to full hit rate. ATD and ICE are configured such that candidate sets are equidistant from each other across the cache. Because PSA collects lines with some probability, 25 simulation iterations are taken per workload and represented as a box plot. Please note that we use the C/C++ random library, and seed it with the time at the start of each simulation.

Workloads that ATD and ICE over-estimate are captured fairly accurately by PSA with (619.lbm, 511.povray, 641.leela, 541.leela). 538.imagick indicates a lower bound on the range of hit rates seen across PSA iterations that are far lower than what ATD and ICE represent, and an additional set of workloads (511.povray, 648.imagick, and 603.bwaves) indicate PSA simultaneously over- and under-estimates hit rate. The behavior can be attributed to workloads having multiple working sets with different hit rate behaviors being captured by PSA run with a different time seed. Such behavior indicates PSA sensitivity to different behaviors across a workload that lends well to prefetcher training or other dynamic policies hoping to capture distinct behavior, though further investigation will have to wait for future work.

Algorithm 2 shows how PSA and ACE come together. The algorithm has a similar structure to Algorithm 1 except now statistics collection happens depending on the result of the random number generator from PSA at line 9. Also, now we use ACE at line 10 to detect if the replacement candidate is the set-wide LRU (comparison to the max LRU value, associativity-1), and again at line 14 to find the set-wide LRU block to update interference. ACE requires a bit to be added per block to enable correct theft and interference accounting, which translates to 8 kB for a 4 MB LLC and scales with cache size. PSA requires logic for a random number generator and comparator logic for the current probability and the sampling threshold we impose. Hardware random number generators can come with a cost, but recent efforts see low power, low area, accurate RNGs that can be included in our design [24, 30, 50]. Finally, since we are sampling contention on any given miss with some probability due to PSA, we can modify line 10 to test if an eviction candidate is LRU, remove line 14, and avoid the cost of an additional bit per block. For comparison, UCP requires 3.7 kB per core for each Associative Tag Structure, which scales with core count, while PSA sees no additional memory overhead aside from the hardware counters for thefts and interference per core.

Similar to Ren et al. [33], we explore different learning to determine a good fit to the prediction problem, and start with Multi-level Perceptrons (MLPs). However, these fully connected models are pretty expensive due to their high number of weight parameters. We next test pure Decision Trees but achieve very low accuracy, and then Random Forests, which improves the accuracy to some extent. We have also explored employing logistic regression and SVM models for our training purposes. Comparing the accuracy of all these models, we decided to use Gradient-boosting Trees, or GBTs [12]. Decision trees, at the core of GBTs, have the following satisfactory properties that make them beneficial for our study: These models do not require pre-processing such as feature normalization on data; we can easily visualize and analyze them; and implementing them in hardware is easy due to the simplicity of tree logic. In addition, as we will describe shortly, they can solve multi-label problems. One major disadvantage of decision trees is that they could easily over-fit and have lower prediction accuracy compared to other more complicated models. We discuss how to improve decision tree results and to prevent over-fitting with ensemble techniques in this section.

We use the gradient-boosting method for this study. In gradient boosting, several shallow trees are trained and connected in a serial manner, where the residuals of each tree are fed as input to the next tree. This way each subsequent tree would gradually improve predictions of the previous tree. The simple structure of decision trees combined with gradient boosting is the sweet spot we were looking for to decide on a partitioning configuration. Figure 4(a) shows a high-level flow for how we train a GBT model. To reach an acceptable accuracy, we train our model on more than 600 different mixes of application pairs. After creating the workload combinations and extracting their features through simulation, we trained a model offline on the feature sets. The trained model is then used on unseen mixes to predict a partition, approximating the oracle configuration.

We devised the partition prediction problem as a multi-class multi-label problem, as shown by Figure 4(b). The rationale is as follows: the overall goal of our model is to choose a partitioning configuration to achieve the best IPC. This IPC is the result of the Oracle partitioning configuration that is shown in the first row in Figure 4(b). The label for this example is (000000000000010). The index of 1 shows where we have to partition the cache to achieve the optimal IPC. However, by observing our dataset, we learned that some of the Oracle configuration’s neighbours have an IPC that is pretty close to the Oracle. This inspired us to put a threshold in place where if the IPC of another partition choice is within 1% of optimal IPC, then it will also be counted as an acceptable configuration. These pseudo-Oracle partition configurations are shown in the second row. The label for this example is (000000000001111). Therefore, for each application pair, we can have one to several partition choices and this will make it a multi-label problem.

Suppose that we have N ways and we want to divide it between two cores. A possible configuration is to give 1 way to application one and \(\text{N}-1\) ways to application two. Or 2 ways to application one and \(\text{N}-2\) ways to application two. Increasing the number of ways given to the first application would decrease the number of ways given to the second application and vice versa. The goal is to train a model that, based on features extracted from each core, would tell us where to partition the cache to achieve the highest IPC for the system. These models are shown in the third row of Figure 4. We can see from the figure that for a cache that has N ways, there are \(\text{N}-1\) locations that we can partition the cache between two cores (shown by bars in Figure 4(b)) considering that each core gets at least one way. We will then train a GBT for each of the \(\text{N}-1\) partition choices.

The training is done offline on all the instances of the training set. To train the models using our supervised learning algorithm, we need input feature vectors and true labels for each instance. We have collected the input features through extensive simulations. Additionally, the label for each GBT would be either 0, meaning that we should not partition in that specific location, or 1 meaning that we should. Using the features and labels we train our models and the result of this stage is a group of trained GBT models. Next, we use instances in our test set to receive a prediction on where to divide the cache between cores. The third row of Figure 4(b) shows the outcome of doing a prediction using GBTs on one of our test set instances. This result comes in the form of the model’s confidence on where the optimal position for the partitioning should be. We will choose the partition configuration with the highest confidence and assign cache ways to cores based on that prediction (fourth row).

Taking into account our choice of problem definition, it is apparent that false positives have much more importance compared to false negatives. False positives show configurations predicted by the model to have optimal IPC while they do not, and false negatives are ones that models predicted not to have optimal IPC while they do. We are not concerned about false negatives as long as our model produces at least one true positive result. This positive result should be either the optimal partition choice or one of the other partitions (if any) that has an IPC difference of less than 1% from optimal IPC. However, false positives should be avoided, since they could penalize system performance.

One question that remains is how important are the specific features introduced in this work, namely, Thefts and Interference, in describing our models. To answer this question, we first conducted a study on highest accuracy achieved by training models using either features from all levels of cache or LLC only. The accuracy of these models were pretty close. However, it was more reasonable to use LLC-only features due to higher cost of passing and maintaining the core cache data when the accuracy is the same. Using LLC statistics, we explored the feature importance for one of the low-cost high-accuracy models. The result is shown in Figure 5(a). The x-axis shows the top 20 important features in the model, and the y-axis shows the location of the partitioning configuration. The darker the cell in this figure, the more important the feature to select an optimal partitioning located in that location. As we can see in this figure, the importance of Thefts and Interference is more pronounced in the middle locations compared to the extremities. This was expected, since there is considerably more contention between workload pairs that mutually require larger partitions, compared to the pairs where at least one application needs a small partition.

We discuss selection and training of a supervised learning model, gradient-boosting trees, on a two-core mix data-set and employ it to predict the last-level cache-partitioning configuration with the highest system IPC. We use features extracted from last-level cache, which include thefts, MPKI, and so on. We define the partitioning problem as a multi-label problem and produce several, correct labels per two-trace pair. To achieve an acceptable accuracy using our models, we need to tune their many hyper-parameters. Utilizing XGBoost library [8], these hyper-parameters include the number of trees, the maximum depth of trees, the learning rate, the sampling ratio of training instances, and so on. We grid-searched these hyper-parameters and did fivefold cross-validation on the training set to attain a good degree of confidence in the accuracy of our models. Figure 5(b) shows the cost versus accuracy plot of these models. The x-axis in this plot shows the size of the model in Bytes and the y-axis shows the accuracy of the model, predicting one of the correct partitioning configurations. As we can see, the smaller models have lower accuracy, but it is not necessary to have the largest models to achieve the highest accuracy. On the contrary, some of the largest models show lower accuracy compared to smaller models. This is due to the models over-fitting when the trees get too deep or too many.

The high accuracy of the GBT model at two cores motivates interest in a model that can predict for higher core counts, but the effort to generate the data to do so is prohibitive. For example, to find the best configuration for a four-core mix, we would need to simulate 455 different simulations! We present Tree Scaling, an algorithmic approach to enable a GBT model, which trains on features from two-core simulation results to be of use at higher core counts (4+ cores). Tree scaling takes advantage of the multi-label confidence output or configuration confidence (CC) list that GBT generates to reason about how to distribute cache allocations on >2 core systems. Tree scaling has three hyper-parameters (T, D, and s_max) and two components: Scaling and Balancing.

We tune CASHT by sweeping the contention collection method, the sampling rate or probability of sampling on a given access, and the rate that we re-partition cache. The performance metrics we analyze are average system IPC improvement (percentage difference from an un-partitioned LLC), average normalized throughput of the slower application in each mix (the so-called slow-core is the workload that completes warm-up and simulation only once), and slow-core fairness (IPC normalized to IPC observed when the same workload is simulated alone, also referred to as weighted IPC). We also analyze best to worst case normalized throughput and fairness with percentile 1–99% of each metric. Percentiles indicate values found in a data set that exceed a designated percentage of all values in that set (i.e., P=1% yields a value that is greater than 1% of all values), and are color coded in the figure (for example, P=1% or p01 is yellow). We discuss the results in Figure 7, analyzing each column respective of each of the following sections.

We use ChampSim [22], from the second cache replacement competition [1], as our simulation environment, and we modify it to allow dynamic re-partitioning and embedded python calls for the GBT model. ChampSim is trace-based, cycle-approximate, and simulates more than one workload trace such that each workload completes a set number of instructions. We configure Last-level Cache to be 16 way set associative, with cache capacity per core set at 2 MB with 64 B blocks. As noted by FIESTA [17], trace-based simulation can take two forms: fixed work where each trace only completes the same amount of work; and variable work where the total number of instructions to simulate is set and each trace runs until this goal is reached. ChampSim follows the fixed work method by warming cache for the first N instructions and simulating for the next M instructions; however, for cores \(\gt \!\!1\), warm-up and simulation completes when both workloads complete N and M instructions, respectively. If one workload completes before the other, then that workload restarts from the beginning of the traces. Due to simulator behavior, we focus performance analysis on the trace per each pair that completes once and identify it as Slow-core or Latency Critical workload throughout our analysis. Additionally, please note that this version of ChampSim has an eight-core upper bound on the number of cores it supports.

Our workloads are traces we generate by skipping the first 1B instructions of each benchmark in SPEC 17 [40] and tracing the following 750M instructions. The trace characteristics are shown in Table 3 (LLC intense traces in bold). We warm caches with the first 500M instructions and simulate the remaining 250M instructions of each trace, a method similar to what is done in prior work [32, 45, 48]. Traces are often generated by choosing representative regions [38], but the reasons for using representative regions are expedient characterizations of benchmarks and confidence that key parts of a trusted workload are being used to exercise the architecture. Our work is not a characterization of SPEC 2017, nor do we indicate our traces as being representative of SPEC 17 benchmarks. Our traces are important to exercise the caches and DRAM enough to produce diverse behavior across our mixes, and the amount of experiments we derive from all unique pairings of traces provides us with such variety. Finally, mix generation is exhaustive for the two-core simulations (totaling 860 mixes), while the four- and eight-core mixes are randomly generated with guarantee of at least 1 LLC intense workload per mix. In the end, we have 106 four-core mixes and 45 eight-core mixes.

Metrics to evaluate performance for partitioning techniques are normalized throughput and fairness. We calculate normalized throughput as IPC_{configuration}/IPC_LRU, where results greater than 1 indicates an improvement in throughput while those less than 1 indicates performance loss. Fairness can be represented as weighted IPC, or IPC_{c,configuration}/IPC_iso, where c indicates a workload in a C-workload mix (\(C\gt 1\)) and iso indicates IPC for workload c when run alone. Fairness is often referred to as weighted IPC.

We compare s-curves for Static Oracle, UCP, Even Partitioning, and CASHT in Figure 8. We plot s-curves (performance metric sorted from smallest to largest normalized throughput) and the average of those results for all trace in each of the 860-trace pairs. Because it is difficult to see all 860 results in an S-curve, we have broken curves to zoom into the interesting ends: the throughput results where the static oracle loses at least 0.5% from the unpartitioned case (or normalized IPC <0.995; totals 87 data points); and the throughput results where the static oracle gains at least 0.5% over the unpartitioned case (or normalized throughput >1.005; totals 240 data points). The top row shows normalized throughput for the traces and the bottom row shows fairness for the traces. In summary, CASHT averages 0.57% improvement in throughput and does no more than 1.8% harm to average single trace performance (i.e., averages 0.982% for fairness). While CASHT does not achieve the 1% average improvement in Latency Critical Trace throughput that the Static Oracle achieves, CASHT is within the margin of error of UCP performance at 1/8 the overhead in the two-core configuration.

We analyze the performance impact each technique has on individual traces by analyzing the percentiles for individual workload performance while sharing LLC. Percentiles (P) indicate a value (V) in a data set for which N% of all values are less than V. Figure 9 shows P=1%, P=10%, P=50%, P=90%, and P=99% of normalized throughput and fairness for each trace when in a shared cache. The x-axis shows benchmarks sorted by UCP p99 throughput values, the y-axis for the top reflects throughput (IPC_cfg/IPC_LRU), and y-axis for the bottom reflects fairness (IPC_cfg/IPC_Iso). Each technique is distinguished by color density (light is UCP, medium is Even, dark is CASHT), and percentiles are distinguished by color families (p99=red, p90=green, p50=blue, p10=yellow, p01=gray), which are layered for compact representation of all percentiles per configuration. In summary, CASHT does not reach the peak performance of UCP but has a higher lower percentile indicating less harm to the worst 1% of normalized throughput. UCP has a clear advantage for mcf- and xalancbmk-based traces (20–79% gains in normalized throughput over LRU). Additionally, UCP also has performance advantages for 621.wrf, 638.imagick, and 657.xz. CASHT has some advantage in 500.perlbench, 510.parest, 603.bwaves, 628.pop2, and 619.lbm, though we can attribute some of the advantages to evenly splitting the cache between traces given that Even Partitioning has similar or better solutions in most of these cases. On close inspection of the p10 and p01 values, we observe CASHT has the advantage in minimizing harm for many LLC intense workloads (in bold in Table 3), indicating CASHT does less harm when LLC is more intensely in use. Add to this the fact that a >50% of traces have fairly similar results, and the attraction of a lighter technique is evident in those cases. Indeed, CASHT approaches UCP peak performance and minimizes harm to worst-case throughput at 1/8 the cost.

We analyze average normalized throughput and fairness metrics for UCP and CASHT when scaled from two to eight cores in Figure 10, and it is clear that CASHT approaches UCP performance in all metrics at each core configuration. The y-axis represents normalized throughput while the x-axes show each partitioning configuration. Each plot reflects different presentations of average performance data from left to right: the first plot shows the average performance of the system; the second shows the performance metric percentile values from 99 to 1 at a two-core configuration; the third shows the performance metric percentile values at a four-core configuration; and the fourth shows similar percentile results but for the eight-core configuration. Percentiles indicate a value in a data set that exceeds the ascribed percentage of that data set (for example, p=10 throughput is greater than 10% of all throughput values in a common set of data). We see that UCP and CASHT have comparable average throughput from the first plot, with CASHT having the advantage due to being a fraction of the overhead of UCP. Further, the percentile plots (plots 2 through 4) support that the lightweight CASHT framework not only approaches the heavyweight UCP implementation in the performance yielded per percentile but also approaches similar performance at a larger core count without the steep cost of scaling (aside from the additional hardware counters for thefts and interference that each core requires).

Modeling cache events and cache behavior are the foundation for performance analysis tools and efficient architectures. We compare related events and models to our theft-based metrics in this section. The Higher Order Theory of Locality (HOTL) describes footprint (fp(x)) as the number of unique accesses in a window of accesses across a trace, and this footprint can be used to derive miss rate and reuse distance [47]. The fp(x) metric necessitates time-based sampling to capture correctly, which likely results in occupying cache with this task and harming performance. Further, there is abstract knowledge of inter-core impact on footprint and derived metrics rather than direct knowledge (like with thefts). Average Eviction Time (AET) models least recently used stacks on a byte granularity to approximate the miss rate curve [27]. AET suggests periodic computation similar to what is done in many partitioning algorithms (including CASHT), but approximates miss rate and not cache contention behavior. Flow, or the rate that cache blocks are moved toward eviction, acts as a proxy for miss rate in Whirlpool [25] and is leveraged to approximate combined miss curves, which enables clustering in Kpart [11]. By comparison, our theft-based metrics are not models but actual events that are consequences of workload interaction and require we identify cause and effect directly. Flow is often taken in isolation and is also used as a proxy for misses, but it is well known that misses are not representative of performance in a deeper cache hierarchy (except in the extreme cases). Thefts show significant correlation to performance, are shown to complement miss-based statistics in Section 2, and can be used in concert with the above models.

The techniques in Table 4 show a range of applications and implementations of cache re-partitioning in recent literature. We compare each with each other and our technique, CASHT across the following technique features: partition allocation algorithm; whether partitions are split between cores (C) or threads (T); what cache dimension (set or way) are caches partitioned; how partitions are enforced; if they are hardware (hw) or software (sw)-based; how cache behavior is profiled; when re-partitioning occurs; and the overhead. UCP tracks per workload cache hit curves to compute and balance the cache needs every 5M cycles [32]. UCP introduced the lookahead algorithm to cache-partitioning problem, and many works can and do adopt the algorithm as a foundation in their work [35, 45, 48], but UCP has large overhead and does not scale well as core counts scale up. COLORIS leverages page coloring via custom page allocator to partition cache along sets [49], but requires modifications to the operating system. Kpart exploits way partitioning adoption in silicon to partition last-level cache into cluster groups, and uses IPC (plus miss rates and bandwidth) to cluster workloads before passing input to the lookahead algorithm [11]. Kpart clusters applications to avoid the diminished returns of partitioning a few ways between many cores, which is not the goal of CASHT. Further, Kpart without clustering is similar to UCP adapted in software given that the lookahead algorithm is in use to determine partition sizes at each repartition step, so we believe comparing against UCP is sufficient. Cooperative partitioning addresses orphaned lines and smooth the transitions after a re-partition step occurs, and modifies lookahead to allow for blocks to be disabled altogether [42]. Reuse locality aware cache algorithm (ROCA) partitions between reused and not-reused cache blocks, leveraging a reuse predictor to determine partition placement at insertion [37]. This differs from the approach taken by partitioning algorithms generally, but can be reduced to identifying blocks by prediction rather than CPU ID so most way-based can adapt to this problem. Gradient-based Cache-partitioning Algorithm (GPA) enables continuous partition adjustment at a cache block granularity by determining how the rate at which blocks are placed in cache in a protected (or vulnerable) state [13]. Consequently, the usage of gradient sets can cause harm to a portion of cache due to purposeful beneficial and detrimental behavior across gradient sets, which CASHT avoids with PSA (Section 3). Machine learned cache (MLC) partitions L2 AND L3 cache via a trained reinforcement learning model called Q-learning, enables smart and collaborative partitioning decisions between per thread Markov agents [18]. Though MLC and CASHT both take advantage of learning algorithms, MLC partitions both L2 and L3 to achieve performance gain on a system that assumes Simultaneous Multi-Threading, which CASHT does not.

Theft-based metrics offer significant and complementary performance correlation, enable run-time contention analysis with the addition of two hardware counters per core or thread, and the theft mechanism allows estimation in the face of partitioning. Miss-based metrics, which are often collected in isolation, do require added overheads like a set sampler or run-time phases where application performance is harmed to collect them. Further, given that LLC misses (especially taken in isolation) are frequently reported as misleading, models based on such behavior render partial information and theft-based metrics can fill those gaps.

CASHT leverages theft-based metrics toward to address the cache-partitioning problem by enabling run-time contention analysis and coupling the results with a supervised learning model to make partitioning predictions. Prior art partitions along different cache dimensions (set or way) or employ different algorithms, but none consider cache contention directly. Additionally, the CASHT framework does not require the cache to operate in any harmful state for the sake of statistical analysis. Last, the CASHT framework approaches comparable performance to a technique with 8X the overhead for a 4 MB, 16-way LLC.