# Com-CAS: Effective Cache Apportioning Under Compiler Guidance

Bodhisatwa Chatterjee<EMAIL_ADDRESS>Georgia Institute of
TechnologyAtlantaGAUSA ,  Sharjeel Khan<EMAIL_ADDRESS>Georgia Institute
of TechnologyAtlantaGAUSA and  Santosh Pande<EMAIL_ADDRESS>Georgia Institute of TechnologyAtlantaGAUSA

###### Abstract.

With a growing number of cores in modern high-performance servers, effective
sharing of the last level cache (LLC) is more critical than ever. The primary
agenda of such systems is to maximize performance by efficiently supporting
multi-tenancy of diverse workloads. However, this could be particularly
challenging to achieve in practice, because modern workloads exhibit dynamic
phase behaviour, which causes their cache requirements & sensitivities to vary
at finer granularities during execution. Unfortunately, existing systems are
oblivious to the application phase behavior, and are unable to detect and
react quickly enough to these rapidly changing cache requirements, often
incurring significant performance degradation.

In this paper, we propose Com-CAS, a new apportioning system that provides
dynamic cache allocations for co-executing applications. Com-CAS differs from
the existing cache partitioning systems by adapting to the dynamic cache
requirements of applications just-in-time, as opposed to reacting, without any
hardware modifications. The front-end of Com-CAS consists of compiler-analysis
equipped with machine learning mechanisms to predict cache requirements, while
the back-end consists of proactive scheduler that dynamically apportions LLC
amongst co-executing applications leveraging Intel Cache Allocation Technology
(CAT). Com-CAS’s partitioning scheme utilizes the compiler-generated
information across finer granularities to predict the rapidly changing dynamic
application behaviors, while simultaneously maintaining data locality. Our
experiments show that Com-CAS improves average weighted throughput by 15% over
unpartitioned cache system, and outperforms state-of-the-art partitioning
system KPart (El-Sayed et al., 2018) by 20%, while maintaining the worst
individual application completion time degradation to meet various Service-
Level Agreement (SLA) requirements.

##  1\. Introduction

Modern high performance systems facilitate concurrent execution of multiple
applications by sharing resources among them. The Last-Level Cache (LLC) is
one such resource, which is usually shared by all running applications in the
system. However, sharing LLC often results in inter-application interference
(Temam et al., 1994; Wu and Martonosi, 2011), where accesses from multiple
applications can map on to the same cache line and incur conflict misses,
resulting in performance degradation. This problem is futher exacerbated by
the fact that the number of cores, and the processes, that share the LLC, are
rapidly increasing in the recent architectural designs. To address this issue,
modern processors use Cache Partitioning to divide the LLC among the co-
executing applications in the system. The main goal of cache partitioning
schemes is to obtain performance isolation to secure dedicated regions of
cache memory to high-priority cache-intensive applications to ensure their
performance. Apart from achieving superior application performance and
improving system throughput (Molnos et al., 2006; Muralidhara et al., 2010;
El-Sayed et al., 2018; Pons et al., 2020; Wang et al., 2017; Sanchez and
Kozyrakis, 2011; Xu et al., 2018; Yuan et al., 2021; Noll et al., 2018; Su et
al., 2018), cache partitioning can also improve system utilization, power and
energy consumption (Ravindran et al., 2007; Cook et al., 2013; Kasture et al.,
2015; Nikas et al., 2019; Shen et al., 2019; Nejat et al., 2020; Huang et al.,
2018; Xiang et al., 2018), ensure fair resource allocation (Sari et al., 2019;
Selfa et al., 2017; Zhang and Zhu, 2020; Park et al., 2019; Xiao et al., 2020;
Saez et al., 2022; Roy et al., 2021) and even enable worst case execution-time
analysis (Mueller, 1995). Due to such significant benefits of cache
partitioning, modern processor families (Intel® Xeon Series) implement
hardware way-partitioning through Cache Allocation Technology (CAT) (Herdrich
et al., 2016), which provides the users with extended control and flexibility
to customize cache partitions as per their requirements.

On the other hand, modern workloads exhibit dynamic phase behaviour (Fried et
al., 2020; Iorgulescu et al., 2018) due to which their resource requirements
rapidly change throughout their execution cycle. These changes in phase
behaviours arise from the complex control flows, diverse and irregular memory
referencing behaviors in the applications, and different sizes of the problems
tackled by the loops, which lead to variant footprints and different reuse
patterns. As a result, it is often the case that a single program region (such
as a given loop in a program) can exhibit variant data reuse behaviour during
multiple invocations. Prior works (Cook et al., 2013; Selfa et al., 2017; Wang
et al., 2017; Xu et al., 2018; Nikas et al., 2019; Suo and Yang, 2009; Moreto
Planas et al., 2007; Liang et al., 2017; Pons et al., 2020) on cache
partitioning tend to classify workloads into categories based on different
levels of cache sensitivity. Based on this offline workload characterization,
cache allocations are then decided though a mix of static and runtime
policies. The fact that a single application can exhibit dual behaviour, i.e
both cache-sensitive & cache-insensitive behaviour during its execution is not
taken into account by such schemes. This often leads to cache being
injudiciously partitioned, and causes performance degradation (§2). Such
static schemes do not account for dynamic loop characteristics dependent on
variant loop bounds, memory footprints and reuse behaviors.

Some cache partitioning approaches (Cook et al., 2013; Qureshi and Patt, 2006;
Wang et al., 2016; Suh et al., 2004; Ye et al., 2014; Gupta and Zhou, 2015)
adapt a ‘damage-control’ strategy, where the partitions are dynamically
adjusted after detecting changes in application behaviour using runtime
monitoring. Unfortunately, these approaches are reactive, and suffer from the
problem of detection and reaction lag, i.e. they detect the phase change only
after a certain interval after its occurrence, and the application behaviour
of workloads are likely to change before the adjustments are made, leading to
lost performance (§6).

In this work, we study the problem of providing smart cache partitioning by
accounting for applications’ dynamic phase behaviors, just-in-time before
entering such cache-sensitive program regions. Our end goal is to obtain
superior performance & maximal isolation by reducing inter-application
interference in multi-execution environments. We propose Compiler-Guided Cache
Apportioning System (Com-CAS), which estimates the dynamic cache requirements
for all co-executing applications just-in-time, and then uses this information
to perform runtime cache partitions.

Probes Compiler Framework (§3): The first contribution of this paper is a
compiler framework that estimates applications’ cache requirements just-in-
time, through a combination of static & dynamic program attributes (Algorithm
1). Program attributes (memory footprint, data reuse behaviour, phase timing,
cache sensitivity) that dictate the cache requirements are obtained via
traditional compiler analysis coupled with machine learning algorithms. The
attributes are then encapsulated in specialized library markers called
‘probes’, which are statically instrumented outside every loop-nest in the
application. The probes communicate these attributes during program execution
for cache management. This represents the front-end of Com-CAS.

BCache Allocation Framework (§4): The second contribution of this paper is a
new runtime apportioning mechanism, consisting of phase-aware allocation
algorithms for determining LLC partitions, based on aggregation of probes-
generated information. The dynamic apportioning mechanism of BCache Framework
first detects phase overlaps of co-executing applications and then minimizes
application interference. It does so by avoiding co-location of processes with
high data-reuse, and by grouping processes with minimal phase overlap, while
maintaining data locality. A net result of such apportioning decisions making
is that LLC misses are shifted from applications with higher cache sensitivity
(high sensitivity reuse) needs to the lower ones (lower sensitivity reuse or
streaming) (§5.5).

Proactive Scheduling: The third contribution of this paper is an user-level
scheduler that interacts with Intel CAT to perform the actual cache
partitioning according to application phase changes. The phase change occurs
whenever an executing application changes its reuse-behaviour or exhibits a
significant variation in its memory footprint, which necessitates cache re-
allocation. The phase information is relayed by probes to the scheduler, which
in-turn invokes apportioning algorithms to obtain phase-based cache partitions
for co-executing applications. Anecdotally, compiler-driven analyses usually
focus on one application at a time (including locality-promoting loop
transformations) to improve single application performance in isolation, and
are oblivious to other co-executing applications in a system. Designing an
user-level scheduler allows us to aggregate compiler-generated attributed
across all applications, thus making the way for system-wide decision making.
To the best of our knowledge, this is the first compiler approach that is able
to take a ”global” view of the cache sensitivity problem in a shared setting
with good performance gains over the current state-of-the-art (El-Sayed et
al., 2018).

We evaluated Com-CAS on an Intel Xeon Gold system with 35 application mixes
from a diverse sets of workloads (Beamer et al., 2015; Che et al., 2009;
Pouchet et al., 2012) that are typically encountered in a multi-tenant
environments (§5). Our target applications 111The current evaluation is
throughput-oriented, and adheres to a fixed latency degradation limit.
Currently, we do not focus on latency-critical applications. are loop-heavy,
data driven, memory-bound and cache-sensitive workloads from domains such as
machine learning, scientific computations, graph analytics, which typically
exhibit phased execution behavior. The average weighted throughput gain
obtained over all the mixes is 15% (upto 35%). In all the instances, no
degradation was observed over a vanilla co-execution environment (with no
cache apportioning scheme). In addition, we show that our proactive cache
partitioning scheme outperforms state-of-art apportioning system KPart (El-
Sayed et al., 2018) by 20%, and other hardware counter-based apportioning
policies by 30% on average. We also show the Com-CAS maximises the isolation
of reuse heavy loops reducing inter-application interference simultaneously
while ensuring fairness and maintaining individual process latencies.

##  2\. Background and Motivation

Determination of memory requirements and its allocation for applications
running in a multi-execution environment is quite a complex task. Typically,
in data centers, for maximizing resource utilization, multiple processes
execute concurrently in a batch, while sharing the same LLC (Amvrosiadis et
al., 2018). The cache demand for each process is dependent on the specific
program point, as well as the underlying execution phase, and can change from
loop nest to loop nest (Fig. 8). Not accounting for these dynamic variations
in cache requirements while partitioning the cache can cause significant
performance degradation (Sanchez and Kozyrakis, 2011; Yuan et al., 2021).
Thus, a good cache apportioning scheme must take into consideration dynamic
concurrency of the appropriate phases of co-executing applications. For
example, if loop nest 1 of application 1 is co-executing with loop nest 2 of
application 2, the apportioning will be quite different than loop nest 2 of
application 1 co-executing loop nest 2 of application 2. None of the current
works analyzes and apportions at this level of granularity leading to sub-
optimal performance. Moreover, since none of the approaches are compiler-
based, they lack the apriori ability needed to predict the cache behaviors.
Table 1 shows the comparison of four different apportioning policies (§5)
operating on a 6-process application mix from PolyBench. As we can observe,
apportioning policies that are agnostic to application phases, lead to
injudicious cache partitioning, causing slowdowns ranging from 10% to 20%,
whereas Com-CAS leads to a speed-up of 27.7% over the baseline of
unpartitioned, unmanaged cache allocation.

Table 1. Comparison of various cache allocation policies for a 6-process mix
($Cholesky,Floyd\\-Warshall,LudCmp,Lu,Corr,Cov$)

Partition Scheme | Policy Type | Interval | Exec Time | Performance
---|---|---|---|---
Max Cache Ways | Static | NA | 1230.41 sec | 19.82% (Slowdown)
Perf Counter-based | Dynamic (Reactive) | 250 ms | 1234.4 sec | 20.21% (Slowdown)
KPart | Dynamic (Reactive) |  $20^{6}$cycles | 1119.43 sec | 10.3% (Slowdown)
Com-CAS | Dynamic (Proactive) | Adaptive | 742.3 sec | 27.7% (Speedup)
Baseline | Unpartitioned Cache | NA | 1014.39 sec | Baseline

Modern workloads executing concurrently in multi-tenant environments exhibit
variant resource requirements in their nested-loop regions. Leveraging
compiler analysis enables us to anticipate these rapid phase changes right at
its onset (i.e at the loop entrances), and allows us to adapt the apportioning
decisions at a few millisecond granularity. Also, if the differences in cache
requirements between successive loop-nests are insignificant, no allocation
change is carried out by Com-CAS in order to prevent hysteresis. Thus Intel
CAT is invoked only when the phase-change entails substantial change in cache
requirements.

Finally, our work leverages Intel CAT (Herdrich et al., 2016), which is a
reconfigurable implementation of way-partitioning that allows the user to
specify cache capacity designated to each running application.

###  2.1. Intel Cache Allocation Technology (CAT)

Intel® Cache Allocation Technology (CAT) (Herdrich et al., 2016) allows the
user to specify cache capacity designated to each running application. The
primary objective of Intel CAT is to improve performance by prioritizing and
isolating critical applications. Through isolation, Intel CAT also provides
powerful means to stops certain kinds of side channel and DoS attacks. It
provides a customized implementation of way-partitioning with a “software
programmable” user-interface, that is used to invoke in-built libraries to
perform cache partitioning.

To reason about different cache partitions, Intel CAT introduces the notion of
Class-of-Service (CLOS), which are distinctive groups for cache allocation.
The implication of the CLOS abstraction is that one or more applications
belonging to the same CLOS will experience the same cache partition. Intel CAT
framework allows users to specify the amount of cache allocated to each CLOS
in terms of Boolean vector-like representations called Capacity Bitmasks
(CBMs). These are used to specify the entire cache configuration for each
CLOS, including isolation and overlapping of ways between one or more CLOS. On
the hardware side, Intel CAT uses arrays of MSRs to keep track of CLOS-to-ways
mappings. Minor changes are then done in the resource allocation mechanism of
Linux Kernel to interact with these dedicated registers. In our work, we use
apportioning algorithms to generate CBMs for a process residing in a
particular CLOS. We then use specialized library calls to interact with the
Intel CAT interface to perform the required allocation.

Adaption of Com-CAS for other (Non-Intel) architectures: In this version, Com-
CAS relies on an re-configurable cache partitioning mechanism that allows
users to customize the cache partitions. The phase requirement algorithms and
the apportioning algorithms are not dependent on any specific architecture as
they maximize isolation of cache-sensitive applications. However, the library
that interfaces Com-CAS with Intel CAT might need to be re-implemented to work
with a new re-configurable cache apportioning system - in case Com-CAS is to
be adapted to an entirely new architecture.

##  3\. Probes Compiler Framework

Figure 1. Overview of Com-CAS consisting of Probes Compiler Framework (§3) &
BCache Allocation Framework (§4)

This section describes the front-end (compiler phase) of Com-CAS (Fig. 1).
Probes Compiler Framework is a LLVM-based, instrumentation framework equipped
with machine learning mechanisms to determine an application’s resource
requirements across various execution points. It inserts ‘probes’ (specialized
library markers) at outermost nested-loops within each function of an
application. These probes estimate the attributes that dictates an
application’s cache requirements for each execution phase: memory footprint,
cache sensitivity, reuse behaviour & phase timing. In our work, we consider
each nested loop to potentially constitute a new execution phase.

###  3.1. Estimating Application Cache Behaviour

The first three attributes (footprint, sensitivity & reuse behaviour) quantify
the cache requirement during a phase, while loop-timing determines how long a
particular phase will last. The memory footprint and reuse behaviour can be
statically analyzed as closed-form expressions, while the phase timing must be
predicted using learning regression models which can be evaluated at runtime
using dynamic values. Such models are statically inserted before the loop
nest. In order to incorporate both the trained model & compute attributes
dynamically, the Probes Framework has two components: compilation component
and runtime component.

Figure 2. Cache profile for each loop nests are generated & encapsulated in
Probes

The compilation component primarily consists of multiple LLVM (Lattner and
Adve, 2004) compiler passes which instrument probes into application source
code and embeds loop memory footprint usage, data-reuse behaviour analysis and
trained phase-timing models. Apart from encapsulating loop attributes, the
compilation component also inserts a special probe-start function in the
preheader of the loop nest and a probe-completion function at the exit node of
the loop nest. For loops present in the inner-nesting levels, the probe
functions are hoisted outside the outermost loop inter-procedurally 222Please
refer to appendix §C for discussion on recursive calls. During hoisting, the
pass combines all attributes of inner-loops with the outermost loop. For
example, if any of the inner-most loop exhibits significant data reuse, then
the entire loop-nest is considered to be a reuse-heavy phase. The runtime
component on the other hand, complements the compilation component by
dynamically computing the values of memory footprint usage & phase-timing and
conveying them to the BCache Framework. This communication is facilitated by
passing the attributes as arguments to the probe library function calls, which
are further transferred to the scheduler via shared memory.

Input: Application $A$

Result: Estimate the loop timing, cache footprint, data-reuse behaviour, cache
sensitivity

for  _each loop-nest $L\in A$_ do

****** Learning Loop Timing ******

L.normalize()

$U\leftarrow getAllUpperBounds(L)$

$W\leftarrow intializeWeights()$

Generate Training & Testing Dataset (T, W) with representative inputs

Learn the linear regression equation $T_{W}(u)=W^{T}U$

****** Estimating Loop Memory Footprint ******

$N\leftarrow obtainLoopTripCount()$

Analyze affine memory-accesses $m(X),~{}\forall X\in\\{0,N\\}$

Obtain polyhedral mapping $[X]\rightarrow\\{m(X):0<X<N\\}$

****** Characterizing Loop Data Reuse Behaviour ******

$srd_{L}\leftarrow calcSRD(L)$

if  _$srd_{L} >\Delta$_ then

$L.type=reuse$

else

$L.type=stream$

end if

end for

****** Analyzing Application Cache Sensitivity ******

$W_{T}\leftarrow getTotalCacheWays()$

$c\leftarrow calcMaxWays(A)$

for  _$i\in\\{3,W_{max}\\}$_ do

Generate application timings $t_{i},t_{i-1}$ with representative inputs

$\Delta t_{i}=\left|t_{i}-t_{i-1}\right|$

$\Delta w_{i}=\left|w_{i}-w_{i-1}\right|$

$\alpha_{A}=\sum_{i=3}^{\max{ways}}\frac{\left|\Delta t_{i}\right|}{\Delta
w_{i}}$

end for

Algorithm 1 Phase Cache Requirement Estimation

The entire cache requirement estimation process is summarized in Algorithm 1.
We will now describe in detail how each steps of this algorithm computes the
program attributes.

####  3.1.1. Phase Timing Model

The phase-timing is defined as the time taken for executing an entire loop-
nest. Probes Compiler Framework uses a linear regression model to predict the
execution time for each loop-nest. The underlying idea is to establish a
numerical linear relation between loop-timing and loop-iterations.

###### Theorem 3.1 (Phase Timing).

For a normalized loop nest L with $n$ inner-nested loops with individual
upper-bounds $\\{U_{1},U_{2},...,U_{n}\\}$, the timing $T_{c}$ is given by the
linear equation:

(1)
$T_{c}=\mathbf{U}^{T}\mathbf{C}=c_{0}+c_{1}u_{1}+c_{2}u_{2}+...+c_{n}u_{n}$

where $C=\\{c_{0},c_{1},..c_{n}\\}$ are learnable parameters, feature vector
$\mathbf{U}=\\{u_{0},u_{1},..,u_{n}\\}$ and feature $u_{i}$ is mapped from
loop upper-bounds $U_{i}$ as $u_{i}=\prod_{k=1}^{i}U_{k}$

###### Proof.

In general, for a loop with arbitrary statements in its body, the loop-timing
is proportional to the loop bounds. Thus, for a loop $L$, with time $T$ and
Bounds $B$, we have:

(2) $\displaystyle T\propto B$ (3) $\displaystyle\Rightarrow T=\beta*B$

For nested-loops, bounds of each inner-loops must be included as well. Thus,
we have:

(4) $\displaystyle T=f(B_{1},B_{2},...,B_{n})$

where $B_{i}$ is the loop bound for the $i^{th}$ inner-nested loop. To make
this analysis easier, Probes Framework uses the LLVM’s (Lattner and Adve,
2004) loop-simplify & loop-normalization passes, which transforms each loop to
lower-bound of 0 and unit-step size, and upper-bound ($u_{i}$). Thus, eq. 4
becomes:

(5) $T=f(u_{1},u_{2},...,u_{n})$

Furthermore, to enable analysis of imperfectly nested-loops, loop distribution
can be performed to transform them into a series of perfectly-nested loops.
Thus, the phase-timing equation can be decomposed sum of individual $n$
distributed loops timings ($U_{i}$ represents loop upper bounds):

(6) $T=f_{1}(U_{1})+f_{2}(U_{1},U_{2})...+f_{n}(U_{1},U_{2},...,U_{n})$

In this work, we assume a linear relationship between loop bounds and loop
timing (any higher degree polynomial lead to overfitting). Thus, Eq. 6 can be
further mapped into features for a linear regression model, i.e $U_{1}=u_{1}$,
$U_{1}*U_{2}=u_{2}$ and so on. Rewritting, we obtain:

(7) $T_{c}=c_{0}+c_{1}u_{1}+c_{2}u_{2}+...+c_{n}u_{n}$

where $u_{i}=(U_{1}*U_{2}*..*U_{i})=\prod_{k=1}^{i}U_{k}$. This creates a
mapping from the individual loop bound $U_{i}$ to the individual feature
$u_{i}$ ∎

Eq. 1 can be interpreted as a linear-regression model $T_{c}(u)$ with weights
$c_{1},c_{2},...c_{n}$ & intercept $c_{0}$, where the weights can be learned.
Probes framework uses a compiler pass to generate loop-bounds & the timing for
a subset of application inputs to generate training data for the regression
model. The training data comprises of multiple program inputs, which the
learned co-efficients $c_{0},c_{1},c_{2},...c_{n}$ generalizable across
different inputs. Once the model is trained, the timing equation for each
loop-nest is embedded in its corresponding probe. During runtime, the actual
loop-bounds are plugged into this phase-timing equation to generate the phase-
time. For non-affine loops that have unknown bounds, we generate an
approximate loop-bound based on the test input sets to predict the timing.

####  3.1.2. Loop Memory Footprint

Memory footprint determines the amount of cache that will be utilized by an
application during an execution phase. Probes framework calculates the memory
footprint through static polyhedral analysis (Grosser et al., 2011), which is
a standard compiler technique for analyzing the memory accesses in a loop
nest.

Polyhedral analysis generates memory footprint equations of the form:

(8) $[X]\rightarrow\\{m(X):0<X<N\\}$

which represents a mapping from the loop iterations to the dynamic memory
accesses by a statement and $N$ is the expected iterations of the loop nest.
Therefore, at runtime with the value of loop upper-bound $N$, probes
calculates the exact footprint & passes it to the runtime component.

####  3.1.3. Classifying Reuse Behaviour

Most applications exhibit temporal and spacial locality across various loop
iterations. To fully utilize the locality benefits, the blocks of memory with
reuse potential must remain in the cache, along with all the intermediate
memory accesses. To determine the amount of cache required by a loop-nest for
maximizing locality, we need to obtain a sense of reuse behaviour exhibited by
the loop-nest. To classify reuse behaviour, Probes Framework defines Static
Reuse Distance (SRD) as follows:

######  Definition 3.0 (Static Reuse Distance (SRD)).

The Static Reuse Distance between program statements $S_{1}$ and $S_{2}$ is a
measure of the number of memory instructions between two accesses to the same
memory location from $S_{1}$ and $S_{2}$.

Based on this metric, the loop-nests could either be classified as Streaming
\- if its SRD is negligible, or else Reuse \- if the SRD is significant and
the reuse occurs over a large set of intermediate memory instructions.
Consequently, reuse loops require significantly larger cache than streaming
loop and this has to be accounted while deciding cache apportioning. Typically
in such cases, the reuse is carried by the outer loop and a large number of
inner loop iterations must be completed before the reuse occurs thus needing a
larger cache size to hold the outer loop references. Appendix §C shows an
example of how SRD can be leveraged to classify data-reuse behaviour of loop
nests.

At runtime, the exact SRD value is computed dynamically and passed on to the
probe functions. Similar to footprint estimation, approximate bounds are
generated to compute SRD for loops whose bounds are unknown. Also, loops
containing indirect subscripts or unanalyzable access patterns are classified
as reuse since at runtime they could potentially exhibit a data reuse.

####  3.1.4. Quantifying Cache Sensitivity

Intuitively, the performance of a cache-sensitive application should improve
with increase in allocated cache size. However, most applications often
experience performance saturation - after a certain number of allocated cache-
ways, there is no further performance benefit with more cache allocation.
Furthermore, before the performance saturation, the more cache-sensitive an
application is, the greater performance benefits it experiences with each
increment of cache allocation. In this work, we quantify performance
saturation and cache sensitivities by the following metrics:

######  Definition 3.0 (Max-Ways ($W_{max}$)).

The number of cache ways that correspond to performance saturation point of an
application, is defined as max ways. For applications that are cache-
insensitive, the max-ways is assumed to be two, as allocating less than two
ways degrades performance by behaving as a directly-mapped cache.

######  Definition 3.0 (Performance Sensitivity Factor ($\alpha$)).

For an application $A$, with loop nest execution times $t$, and allocated
cache ways $w$, the performance sensitivity factor is defined as:

(9) $\alpha_{A}=\sum_{i=3}^{\max{ways}}\frac{\left|\Delta t_{i}\right|}{\Delta
w_{i}}$

where $\Delta t_{i}=\left|t_{i}-t_{i-1}\right|$ and $\Delta
w_{i}=\left|w_{i}-w_{i-1}\right|$, while $i$ denotes an observed data-point. A
high value of $\alpha$ indicates that the application’s performance benefits
could be increased by increasing the cache allocation when a particular loop
nest is being executed.

In other words, $\alpha$ captures the change in an application’s loop nest
execution times as a function of cache ways allocated to that application.
Probes profiles and sends the tuple $(\alpha$, max-ways) for an application to
the scheduler at runtime to guide the apportioning algorithms. In case we have
data-points for all consecutive cache-ways (2,3,4,$\dots$n), $\Delta w_{i}=1$.

##  4\. BCache Allocation Framework

BCache Allocation Framework obtains efficient cache partitions for diverse
application mixes, based on their execution phases. Typically, during a
particular instance of system execution, an application executing a reuse loop
with a higher value of memory footprint is allocated a greater portion of the
LLC, compared to another application executing a streaming loop. The phase
change occurs whenever an executing application changes its reuse-behaviour or
exhibits a significant variation in its memory footprint, necessitating cache
re-allocation. The phase information is relayed by respective probes to the
scheduler, which in turn, invokes apportioning algorithms.

For grouping different applications into cache partitions, Intel CAT (Herdrich
et al., 2016) introduces the notion of Class-of-Service (CLOS). Applications
grouped in the same CLOS share the same cache partitions, and therefore must
have similar cache attributes, and must be compatible (should not lead to
conflict misses).

Each CLOS can be mapped to a specific cache configuration. These cache
configurations are expressed in terms of Capacity Bitmasks (CBM), which is
Boolean array of length $n$, where $n$ represents the total number of cache
ways present in the system. The CBMs serve as input to Intel CAT for the
actual partitioning. $CLOS\rightarrow CBM$ mapping is obtained by setting the
appropriate bits in the array.

When the processes start executing, they are assigned to a suitable CLOS based
on the triggered probe attributes ascertaining their compatibility. As the
execution proceeds, the underlying cache configurations for each CLOS are
adjusted as per the needs of their constituent processes, while maintaining
data-locality. We will now describe our apportioning scheme and the allocation
algorithms in detail.

###  4.1. Cache Apportioning Scheme

BCache allocation framework determines cache apportions for an application
based on its loop memory footprint & data-reuse behaviour by adopting an unit-
based fractional partitioning scheme. The underlying idea of this scheme is
that each application will be allocated a fraction of the LLC, which is
measured by estimating how much they contribute to the entire memory
footprint.

The memory footprint of each loop is first scaled as per whether it is a
streaming loop or a reuse loop. Scaling ensures that the reuse loops get a
bigger portion of cache than streaming loops. For an application $K$ with
current executing loop $n$ having memory footprints $m$, the adjusted loop
memory footprint is defined as: ${}^{K}m_{phase}={}^{K}m*S_{n}$, where $S_{n}$
denotes the scaling factor of the current loop $n$. It can be adjusted
dynamically and depending on the reuse behaviour exhibited by a loop, scaling
factor ranges from:

(10) $S_{n}=\left\\{\begin{matrix}=1,&\text{if n}\rightarrow\text{reuse}\\\
<1,&\text{if n}\rightarrow\text{stream}\end{matrix}\right.$

Based on the adjusted footprints values of all executing loops in the system,
a fraction of the cache size that will be allocated to each application is
determined. This fraction is calculated by determining how much does the
current application’s loop footprints contribute to the overall loop
footprints in the system. In a system with $N$ applications, the fraction of
cache allocated to application $K$ at time $t$ is given by:

(11)
$f^{cache}_{t}(K)=\frac{{}^{K}m_{phase}}{\sum_{I=1}^{N}{}^{I}m_{phase^{*}}}$

where ${}^{K}m_{phase}$ denotes the adjusted loop memory footprint of
application $K$ and ${}^{I}m_{phase^{*}}$ denotes the adjusted loop memory
footprint of application $I$ in their current execution phases. At $t=0$, all
the applications will be allocated an initial fraction of cache according to
the memory footprints of their first executing loop and the sum of these
fractions for all the applications at $t=0$ will be equal to 1. This means
that unless applications are grouped in same CLOS, each running application
will start their execution with an isolated portion of cache. However, an
important observation in the above equation is that each fraction is being
calculated based on an individual application’s current phase and will be
recomputed during their phase changes. Obviously, different co-executing
applications in the system might not undergo phase change at the same time as
others. This might result in an overlap between cache portions allocated to
different applications and the sum of cache fractions will deviate from 1.
Based on the sum of cache fractions for all applications in the system, Table
2 shows the three possible system scenarios at time $t$.

Table 2. Possible scenarios in fractional cache partitioning scheme

| Sum of Cache fractions
---
$\sum_{I=1}^{N}f^{cache}_{t}(I)$
System Scenario
$=1$ |  | Cache is fully occupied and each application
---
group has separate portion of cache
$>1$ |  | Cache is fully occupied and some applications
---
have overlapping cache portions
$<1$ |  | Cache is not fully occupied and each
---
application group have separate portion
of cache

###  4.2. Phase-Aware Dynamic Cache Allocation

Calculating cache partitions and generating their respective CBMs from cache
fractions is achieved by Initial Phased Cache Allocation (IPCA) and Phase
Change Cache Allocation (PCCA) algorithms. The IPCA algorithm (Algo 2) is
invoked whenever an application begins its execution. A separate socket is
dedicated for applications with a higher value of $\alpha$, while low-$\alpha$
applications resides in the other sockets. If there are no cache-ways left in
the high-$\alpha$ socket, then applications are grouped in different sockets
according to the available cores in the sockets.

Input: Process P

Result: Find effective cache partition for an application based on its initial
phase

****** Initializing Socket ******

if  _$(P\rightarrow\alpha) >1$_ then

if  _high- $\alpha Socket.ways()>(P\rightarrow\max ways)$_ then

Assign P to high-$\alpha$ Socket

end if

else

Assign P to a different socket with max available cores

end if

****** Selecting CLOS ******

if  _$socket.availCLOS >(0.75*socket.totalCLOS)$_ then

find new clos for REUSE process

find compatible clos for STREAM process

else

compatible clos $=$ all clos where $total\\_process\leq GFactor$

group STREAM process in compatible clos having $\max(\Delta_{t})$ value

group REUSE process in compatible clos having
$\min(\frac{\alpha}{\Delta_{t}})$

end if

****** Allocating cache ways ******

$req\\_ways=P\rightarrow getCacheApportion()$;

if  _$avail\\_ways >req\\_ways$_ then

Allocate $req\\_ways$ to $P\rightarrow CLOS$

else

Allocate $avail\\_ways$ to $P\rightarrow CLOS$

end if

Generate appropriate bitmasks for allocated ways

Algorithm 2 Initial Phased Cache Allocation (IPCA)

After socket allocation, a compatible CLOS is obtained for the process. If
more than 75% of total CLOS on a socket are vacant, each reuse processes gets
its own CLOS. For processes executing streaming loops, separate CLOS is
assigned only if there is no compatible CLOS available. Consequently, when the
number of occupied CLOS in a socket crosses the 75% mark, both streaming and
reuse loops are grouped in compatible CLOS groups. Next, the IPCA algorithm
estimates the initial cache demand by using the fractional scheme, which is
passed into a bitmask generator to obtain the required CBMs after checking the
available cache-ways in the system. In case the demand exceeds the available
cache capacity, the framework allocates all possible ways to the CLOS and
marks it as ‘unsatisfied’. Finally, Intel CAT is invoked by these generated
bitmasks to create partitions.

Input: Process* P

Result: Find efficient cache partition for an application based on its phase
change

$req\\_ways=P\rightarrow getCacheApportion()$;

$curr\\_ways=P\rightarrow ways$;

if  _$req\\_ways >curr\\_ways$_ then

$extra\\_ways=req\\_ways-curr\\_ways$;

$avail\\_ways=socket\rightarrow getavailWays()$;

if  _$avail\\_ways\geq extra\\_ways$_ then

Allocate $extra\\_ways$ to $P\rightarrow CLOS$

else

Allocate $avail\\_ways$ to $P\rightarrow CLOS$

end if

else

$free\\_ways=curr\\_ways-req\\_ways$;

Allocate $free\\_ways$ to most unsatisfied $P^{{}^{\prime}}\rightarrow CLOS$;

end if

Algorithm 3 Phase-Change Cache Allocation (PCC)

The BCache scheduler is implemented as an user-level process that ‘tasksets’
processes onto particular cores and manages them according to the probe
information. The probes conveys the scheduler of possible phase-changes in
application and PCCA algorithm (Algo. 3) is invoked to update the existing
cache partitions based on the new requirements. The PCCA algorithm obtains the
new demand by using the same fractional apportioning scheme and checks for
changes in cache demand. If demand increases, then extra ways are allocated to
the CLOS if possible. However, if the current demand of the application can be
satisfied with lesser ways, then extra ways are freed and allocated to the
‘most unsatisfied CLOS’ ($\alpha_{\max}$) in the system. The required CBMs are
obtained from the bitmask generator accordingly. A similar approach is
followed when a loop finishes its execution, along with updating all system
parameters like occupied CLOS, available ways, etc. Overall, the cache
allocation algorithms manages the following aspects of the system:

  * •

Preserving Data Locality: All processes are confined to their initial socket
throughout execution time. Applications that possess reuse loops with large
footprints are kept within the same CLOS, to maintain a fixed subset of cache-
ways for their execution period. On account of phase changes, the number of
ways in that CLOS are expanded or shrunk in a way that ensures that an
application doesn’t start over with cold cache.

  * •

Finding Compatible CLOS: When total allocated ways reaches above 75% of the
maximum available ways, processes are grouped if their way-demands are similar
(same cache configuration) and their difference in execution time ($\Delta t$)
is maximum. This ensures that grouped processes won’t co-execute for long.
This allows aggressive grouping of streaming process. However, for reuse
process, the compatibility relation also includes grouping with least
sensitive processes ($\min\alpha$) in the system to ensure overall performance
will not be impacted.

  * •

Limiting Total Process in a CLOS:The allocation algorithms constraints that at
any time instant, total processes in a given CLOS $\leq GFactor$ (adjustable
parameter) to avoid excessive thrashing. This prevents CLOS over-crowding and
limits application interference.

##  5\. Results & Evaluation

We evaluate Com-CAS to answer the following set of questions:

  * •

How accurately does Com-CAS predict the phased-cache requirements (§5.1) and
how effective are the resulting partitions in terms of maximizing throughput?
(§5.2, §5.6)

  * •

How does the dynamic proactive apportioning scheme compares with other
static/dynamic apportioning mechanisms and state-of-art KPart? (§5.2, §5.5)

  * •

What were the internal apportioning decisions taken by Com-CAS that allows it
to maximize performance (§5.4)?

  * •

How are the individual process latencies? Is Com-CAS fair to all co-executing
processes in the system? ( §5.6)

Experimental Setup: Com-CAS is evaluated on a Dell PowerEdge R440 server with
Intel Xeon Gold 5117 processors and way partitioning support through Intel
CAT. The system is equipped with 2 sockets (14 cores & 16 CLOS per socket) and
11-way set-associative, 19 MB shared LLC, running Ubuntu 18.04. Scaling Factor
($S_{n}$) was set to 0.1 for streaming process and $GFactor$ was set to 4.

Benchmarks333Our benchmark selection was influenced by the cache-sensitivity
study done in (Cook et al., 2013). This shows that popular SPEC CPU (Henning,
2006) benchmarks are mostly cache-insensitive, while Graph500 (GAPS) is highly
cache-sensitive: Four∗ diverse benchmark suites were chosen for our
experiments: GAP Benchmark Suite (Beamer et al., 2015), PolyBench Suite
(Pouchet et al., 2012), & Rodinia (Che et al., 2009). These benchmarks
represent memory-reuse heavy workloads from machine learning, data and graph
analytics, etc, i.e domains that typically require multi-tenant execution
environment (Amvrosiadis et al., 2018). Refer to Appendix §A.1 for
justification about benchmark selections and Table 3 for details about
benchmarks used for evaluation. For the sake of completeness, we also included
popular SPEC 2017 (Henning, 2006) in our evaluations (Appendix §A.2), inspite
of it being mostly cache-insensitive. All the benchmarks were compiled with
their default optimization flags (-O3/O2, -fopenmp, etc).

Table 3. List of Benchmarks used for evaluation

Suite | Benchmarks | Input
---|---|---
Polybench |  | Lu Correlation Covariance Gemm Symm Syr2k
---
Cholesky Trmm 2mm 3mm Doitgen Floyd-Warshall
Fdtd-2d Heat-3d Jacobi-2d, Seidel-2d
Nussinov Gramschimdt Syrk Adi Ludcmp
| MINI, STANDARD,
---
LARGE (Training)
EXTRALARGE
(Testing)
GAP | BC CC CC_SV TC PR SSSP BFS |  | Uniform Random
---
Graph (Train - $2^{22}$ nodes,
Test - $2^{24}$ nodes)
Rodinia |  | Backprop LU Heartwall CFD Hotspot Srad
---
Particlefilter Streamcluster
| Default Inputs (Train)
---
Customized Inputs (Test)

Parallel Execution: Com-CAS supports OpenMP Parallelism with cores assigned as
specified by OpenMP pragmas and default environment variables. Probes are
inserted before parallel-loop pragmas and cache requirements are calculated
normally; threads are forked into assigned cores and allocated cache is shared
among them. PCCA is triggered only when all threads join. Thus, Com-CAS
operates on aggregate cache requirements of all threads at process-level. GAPS
& Rodinia (partially) uses OpenMP compilation.

Creating Realistic Workload Mixes: Our goal is to evaluate Com-CAS on ‘groups
of applications that execute concurrently’ (mix), on a real-world, multi-
tenant shared cluster. Therefore, our mix creation process aims to encompass
all possible resource demand scenarios (either core count/cache occupancy)
that can occur in such a multi-execution setting - (a) mixes which exhibit
minimal/no contention for the shared resources (light-mixes), (b) mixes whose
resource demand just touches the system thresholds (medium-mixes) and (c)
mixes composed of processes that can potentially saturate the system in terms
of either cache demand or core demand (heavy-mixes). Thus, we created 35
workload mixes, with special emphasis on heavy-mixes (21 mixes) that can
stress-test the potential of our allocation algorithms. Apart from that, there
are 8 light-mixes and 6 medium-mixes. The applications with $\alpha>1$ are
added in every mix since we are interested in determining the effectiveness of
our framework in sensitive benchmarks.

System setting and metric: We target batch execution for the mixes, a common
setting to run modern workloads pertinent to data analytics, machine learning
and graph processing in a multi-tenant setting. We use throughput maximization
as the key metric for performance improvement. In addition, we use service
level agreement (SLA) as a constraint; SLA degradation should be limited to
15% in our setting.

Probe Overheads: The probe-instrumented applications have two sources of
overheads: (a) short probe-library calls during information broadcast that are
in range of $\sim 10\mu s$ (less than 1% overhead) and (b) training the
regression models that adds $\sim 120$ secs, and embedding adds $\sim 250$
secs to compilation time. Overall, the size of final instrumented binary is
about $15\%$ greater than the original binary.

Figure 3. Com-CAS’s weighted speedup (15% Avg) over Unpartitioned Cache System
for all 35 mixes. The largest performance gains are in heavy-mixes, where the
workload resource requirement saturates the system and judiciously
partitioning the cache is highly contingent upon utilizing dynamic phase
attributes like phase-timing, reuse-behaviour, etc as done by Com-CAS.

Figure 4. Com-CAS’s weighted speedup (21% Avg) over Max-Ways Cache
Partitioning Policy for all 35 mixes. Allocating fixed cache portion that
amounts to each application’s ‘max-ways’ throughout its execution, results in
maximum inter-application interference, where benefits of cache partitioning
are squandered.

Figure 5. Com-CAS’s weighted speedup (32% Avg) over HW Perf Counter-based
Cache Partitioning Policy for all 35 mixes. The strategy of changing the
cache-allocations at a fixed-interval (500ms) results in detection lag for
applications’ phase-changes and execution time worsens for all mixes. This
effect can be seen even in light & medium mixes, where performance degradation
is more pronounced than other policies.

Figure 6. Com-CAS’s weighted speedup (20% Avg) over state-of-art KPart for all
35 mixes. Com-CAS adjusts the cache allocations during each phase-change,
while KPart changes them per $20^{6}$ cycles. As a result, the performance
degradation occurs from non-adaptability to change in application’s resource
requirements and using fixed samples of cache apportions during each
allocation.

Comparison with other systems: We evaluate Com-CAS’s performance against four
different baselines as follows:

  * •

Unpartitioned Cache System: mixes are simply compiled with normal LLVM and
executed on Linux’s CFS Scheduler (Kobus and Szklarski, 2009), which is the
most commonly used scheduler in real-world systems with no cache apportioning.

  * •

Max Ways Static Policy: Each process in the mix is statically allocated its
max-ways number of cache ways. The purpose of this policy is to test whether
the knowledge of ‘optimal-cache ways’ obtained by offline profiling, is
sufficient to perform effective cache partitioning or not.

  * •

Perf-Counter Based Dynamic Policy: The objective of this policy is to test
whether an application’s dynamic phase-behaviour can be predicted by employing
hardware counters and then adjusting the cache partitions according to changes
in applications’ cache-misses and the IPC. This dynamic reactive policy starts
off with apportioning the cache equally among all the processes and then at
every fixed-time interval (500ms), allocates more cache-ways to processes that
exhibits higher $\frac{Cache\\-Miss}{IPC}$ ratio.

  * •

KPart (El-Sayed et al., 2018): State-of-art cache partitioning system that
groups applications in distinctive clusters by checking the compatibility
(reduction in combined cache miss) among applications sharing a cluster by
profiling. It then tries to find effective partitions for each cluster and
updates them periodically per $20^{6}$ cycles of instructions. In our
evaluation, we minimally modified the KPart code to account for sockets and
high core-counts. .

###  5.1. Loop Attribute Prediction Accuracies

We first empirically show that Com-CAS is able to accurately predict the loop
execution times and thus, cache footprints. The workloads are profiled by the
Probes Framework on training inputs (Appendix §A.1) to obtain loop-timing
models. The accuracy of these models are obtained by comparing the predicted
values with the actual attribute values on the testing inputs (Table 3). The
loop timing predicted by the Probes has an 86% average accuracy across all the
benchmarks, with lowest accuracy of 64% ($nussinov$) and highest accuracy of
100% ($symm$). Loop timing is affected by the hoisting of probes because it
replaces exact values with expected values leading to less precise timing and
footprint values. This result can be seen especially in GAP benchmarks because
these benchmarks tend to have more interprocedural loops compared to Polybench
and Rodinia. Few benchmarks in Polybench ($symm,syr2k$) exhibits typically
uniform behaviour across inputs sets, leading to almost perfect timing
accuracy ($>95\%$). Overall, high timing accuracies (Appendix §A.5) show that
Com-CAS was able to accurately predict the phase timings at fine levels of
granularities.

###  5.2. Improvement in Weighted Execution Time

Figs. 3-6 summarizes Com-CAS’s weighted geometric mean speedup in terms of
achieved throughput on the 35 mixes in each of the four baselines
respectively. Compared to the Unpartitioned Cache System (Fig. 3), Com-CAS
showed an average throughput improvement of 21% over all 15 Polybench mixes,
5% over all 10 GAPS mixes and 19% over all 10 Rodinia mixes.

In particular, we found that heavy-mixes from all three benchmarks (mixes #8 -
#17, #24 - #25, #31 - #35) showed the largest performance gains. This shows
that Com-CAS manages to perform effective cache allocation and superior
scheduling particularly when the workload resource demands are saturated and
it prevents overwhelming of the system. In addition to that, the Unpartitioned
Cache System can lead to complete sharing of ways and causing high inter-
application interference, while Com-CAS side-steps this issue by controlling
the number of reuse processes grouped in the same CLOS ($GFactor=4$). A
discussion on Com-CAS’s scalability is given in Appendix §A.4.

We found that static max-ways policy (Fig. 4) performs significantly worse
(40%-50% slowdown) in PolyBench and Rodinia over the baseline of Unpartitioned
Cache System. This is because mix heterogeneity & mix size (specially medium-
mixes & heavy-mixes), as well as individual process $\alpha$, is higher than
GAPS workload. All these factors results in excessive inter-application
interference when all processes are allocated ‘max-ways’ number of ways and
hence benefits of cache partitioning is squandered. Conversely, Perf counter-
based reactive scheme (Fig. 5) that adopts a damage-control methodology at 500
ms granularity, fails to detect the phase changes that vary from few ms to
$10^{2}$ ms and therefore performs significantly worse across all mixes.
Interestingly, this policy incurs a greater amount of performance degradation
in long-running, light & medium-mixes compared to other policies, suggesting
that even in workloads containing minimal number of processes (with their
collective resource requirement below the system limit), the ‘detection lag’
between an application’s actual resource demand and resource allocation by the
system results in injudiciously cache partitioning, leading to significant
performance degradation. Although this policy can potentially perform better
by fine-tuning the fixed-time interval for performing allocations, but this
requires a trial-and-error approach and will vary according to the mix
composition, which makes it impractical.

On the other hand, Com-CAS obtains an average improvement of 44% across all
the mixes over state-of-the-art KPart (Fig. 6). Although KPart uses a dynamic
partitioning policy and the compatible applications clusters are figured out
apirori, the performance gap primarily arises from the non-adaptability of
KPart to the varied phase timings (Fig. 8) and inability to judge the
appropriate amount of cache allocation for each application. While Com-CAS
changes the allocations at every loop-nest level with memory footprint
variation, KPart indiscriminately changes allocations every $20^{6}$ cycles
with different partition samples, which hinders performance. This highlights
an important distinction between KPart & Com-CAS: KPart essentially treats
each application like a black-box and attempts to find ‘best cluster fit’ for
a certain application mix, while Com-CAS is assisted by a compiler framework
that analyzes each application separately and guides the cache apportioning at
loop nest level. Thus, the attributes that Com-CAS uses to guide cache
allocations (loop timing, footprints, reuse behaviour) are better indicators
of an application’s resource requirement than aggregate measures such as
cache-misses and IPC. Similar to the unpartitioned cache baseline, Com-CAS’s
performance enhancement is more pronounced in heavy-mixes.

###  5.3. Com-CAS’s Process Scalability

Fig. 7 (right) gives a glimpse into the apportioning decisions taken by Com-
CAS across all the 35 mixes. The ‘total apportions’ for each mix denote the
number of partitioning decisions undertaken by Com-CAS. Although the number of
apportions rises with the total processes in the mix, we can observe that the
rate of increase in apportions is not as steep compared to rate of increase in
total processes in a mix. This hints at the scalability of Com-CAS with
respect to mixes containing larger number of processes. Another interesting
observation is that maximum processes that are grouped in one CLOS at any
point of time, is closer to 4 ($GFactor$), only when the mix size is large or
number of applications exhibiting streaming behaviour is dominant. Fig. 7
(left) shows total mix execution time for all the four baselines. This
represents the execution time for the longest running process in the mix
(typically characterized by high $\alpha$) and determines the overall
throughput. Com-CAS achieves an improvement of 20% (avg) over unpartitioned
cache and 40% (avg) over KPart.

Figure 7. Total Mix Execution time and different Apportioning Metrics across
all 35 mixes. The system throughput is determined by the total mix time. The
different apportioning metrics give an overview of Com-CAS’s decision making.

###  5.4. Case Study: Closer look at Com-CAS

In order to understand the decision making process of Com-CAS, we present a
case study comprising of a mix (#16) from GAPS, consisting of BC, CC, CC_SV,
TC, PR, SSSP & BFS. The loop attributes (loop-timing, memory footprint,
performance-sensitivity factor ($\alpha$), max-ways) are estimated by Probes
Compiler Framework and are encapsulated in the probes outside each loop. For
each of the 7 processes in the mix, the loop-timing and memory footprint
prediction accuracies are illustrated in Fig. 8, along with the values of
$\alpha$ & Max-Ways.

Figure 8. Case Study for 7-process mix (BC, CC, SSSP, TC, CC_SV, BFS, PR) from
GAPS: Probe Prediction Accuracies (left) and mix runtime behaviour (right).
The rapid transitioning in log scale for phase-timing & memory footprint
illustrate the complex dynamic phase behaviour for this workload.

During the execution, BCache Allocation Framework grouped BC & CC in same
socket because of their high $\alpha$ & larger max-way values, while the rest
five processes were put in another socket. At the start of the execution, BC,
CC, CC_SV, TC, & PR, were in reuse phase and exhibited footprints in the range
of $10^{3}$ units, while SSSP exhibits an initial footprint $\sim 10^{9}$
units, with streaming phase. BFS’s initial phase footprint was only 4 units.
Based on the footprint values (which are scaled by reuse behavior), $\alpha$,
max-ways and phase-timing, processes BC, CC, CC_SV, TC, PR and SSSP were
initially allocated with 2 cache ways each, while BFS was allocated 1 cache
way. The interesting aspect of Com-CAS’s apportioning is shown in the fact
that although SSSP’s footprint were considerably greater than other 5 process’
footprints, its allocation was limited by its streaming behavior and max-ways
value. Fig. 8 shows that as the execution goes on further, processes BC & CC
undergoes through 10 dynamic phases, while there were 9 phase changes for BFS,
8 each for CC_SV & SSSP, and 7 each for TC & PR. These phases varied from an
interval of $10^{5}$ to $10^{12}$ ns, while footprints changed from values as
low as $~{}1-2$ units (negligible) to extremely high values such as $10^{9}$
units. The allocations for BC changed from 2 to 4 (during phase $1\rightarrow
2$) and then was shrunk back to 2 (during phase $7\rightarrow 8$). Similarly,
CC’s ways were increased from 2 to 4 (during phase $2\rightarrow 3$ ) and then
was decreased back to 2 during the next phase transition. TC’s ways were
shrunk from 2 to 1 during phases $2\rightarrow 3$ and then increased back to
2. All the other processes were either increased to their max-ways and then
decreased back in subsequent phases or were kept constant throughout their
execution ($SSSP$ & $PR$). As we can see from Fig. 8, the application dynamic
phase-behaviour are rapid and can transition from high footprint phase to low
footprint one with varying reuse behaviour. Thus, the information broadcast
from the probes helps us to make appropriate apportioning decisions.

###  5.5. Effect on Cache Misses

Com-CAS’s allocation algorithms focuses on enhancing the overall system
performance by apportioning higher amount of cache to reuse-based processes
that exhibit higher cache-sensitivity (high $\alpha$). As a result, the
general trend observed is that reduction in LLC cache misses are shifted
towards reuse-based applications that “need a greater amount of cache”. This
is important since the system throughput is determined by the execution time
of process that has the longest execution time in mix and typically, they
demand more cache and are cache-sensitive. Over the unpartitioned cache
system, the processes Floyd-Warshall (Polybench), BC (GAP) & SRad (Rodinia)
showed a reduction of 27.56%, 3.44% & 44.9% respectively. For other
applications present in the mix, the cache misses are either the same or have
somewhat increased. This is because Com-CAS prioritizes applications which
exhibits higher degrees of cache-sensitivity. Also, for non-cache sensitive
applications that have been instrumented with probes exhibit more misses
because of the additional probe functions calls. Overall, Com-CAS achieved a
reduction of 4.6% in LLC misses over all the mixes in the unparitioned cache
baseline.

###  5.6. SLA, Individual Process Latencies & Fairness

Com-CAS strives to enhance the overall throughput enhancement by catering to
the requirements of processes that exhibit higher cache-sensitivity (high
$\alpha$). However, following such a scheme can be detrimental to individual
processes in the mix that are “less-cache sensitive” (low $\alpha$) or have
minimal phase-timings (low $t$). Therefore, in addition to enhancing system
throughput, it is important to focus on the individual process latencies in
each of the workloads as well. For our experiments, we assume that 15%
degradation compared to the ‘original-unmixed’ time, serves as an acceptable
latency degradation limit (service-level-agreement/SLA). The original-unmixed
time is measured by running the process individually in an unpartitioned cache
system. In our experiments, we found that all 35 mixes adhere by this limit,
i.e the individual process latency degradation is no more than 15%. To take a
closer look, we choose one ‘representative mix’ from each benchmark - the mix
that obtained maximum throughput gains (best-performing mix) over
unpartitioned cache. Fig. 9 compares the individual process times running as a
mix with their original-unmixed time in all 3 representative mixes and it’s
clear that none of the process show a latency degradation of more than 15%.
Note that in certain workloads with fully regular loops, the individual
latencies are better than the original unmixed time; this achieved by the
additional optimizations enabled by hoisting the probes to the outermost loop
preheader. This effect is only noticeable in regular workloads with affine
loops. Overall, across all 271 individual processes distributed in 35 mixes,
Com-CAS achieves an average performance degradation of 1.13%, compared to
their original-unmixed time, and all individual process latencies were within
the SLA limit.

Figure 9. Comparison of individual process latencies with original-unmixed
time in representative mixes from each benchmark (#10, #25, #27). All
processes adhere to 15% acceptable latency degradation limit (SLA).

In addition to this, Fig. 10 shows a comparison between Com-CAS and the three
other baseline partitioning policies - Max-Ways, Perf-Counter, and KPart, on
average. The fairness metric used here is Jain’s Fairness Index (Jain et al.,
1999), which is measured by $\frac{1}{1+\text{covariance}^{2}}$, where
covariance is obtained by $\frac{\sigma_{\text{mix-
thoughput}}}{\mu_{\text{mix-thoughput}}}$. Fig. 10 (left) shows the fairness
index comparison in terms of mix size, which depicts that Com-CAS maintains
fairness in enhancing performance even for large mixes. This fact is further
ratified by Fig. 10 (right), where the fairness is compared with mixes having
varying degrees of cache sensitivity ($\alpha_{mix}$ is defined as average
$\alpha$ of all the processes in the mix) and Com-CAS maintains an uniform
fairness index of $\sim 0.99$ for different mix-categories.

Figure 10. Fairness Comparison of Com-CAS with three partitioning policies as
a function of total process and average mix cache-sensitivity

##  6\. Related Work

Throughput-driven Approaches: Recent works have focused on approaches to
obtain finer-grain cache partitions (Wang et al., 2017; El-Sayed et al., 2018;
Pons et al., 2020). KPart (El-Sayed et al., 2018) (§5) takes a clustering
approach that requires profiling every pair of applications in the mix in
addition to profiling them separately, i.e performing $O(n^{2})$ profiling
operations on top of $O(n)$ individual operations. Apart from being non-
scalable for mixes containing large number of applications, this approach is
not practical in real-world scenarios, where mix composition or even
participating processes therein are not even known apriori. Similarly, another
recent work (Xiang et al., 2018) proposes an approach of online monitoring
using miss-curves also suffers from the same drawbacks - the fact that
workloads might be input sensitive and the miss-curves might vary according to
the execution scenario is ignored. An alternative approach (Pons et al., 2020)
that accounts for application phase changes, where based on the execution
behavior, applications are grouped into multiple categories by extensive
profiling. However, such static categorization misses an important aspect -
application phases are input-dependent and are dynamic as well as contingent
upon entire mix composition. Thus, an application behaviour might change based
on an different execution scenario or with new input data. Since this approach
misses accounting for dynamic interactions and concurrency of different
application phases, we feel that application classification is not a feasible
approach. Also, the evaluations are primarily done on SPEC CPU benchmarks
(Henning, 2006), which has been shown to be non-cache sensitive in (Cook et
al., 2013).

Latency-driven approaches: Our work primarily focuses on throughput
improvement and the 15% SLA requirement serves as an upper bound for allowable
latency degradation. Several resource managing mechanisms (Chen et al., 2019;
Zhu and Erez, 2016; Lo et al., 2015; Roy et al., 2021; Xiang et al., 2019;
Kasture and Sanchez, 2014; Kasture et al., 2015; Gifford et al., 2021) use CAT
to perform dynamic resource allocations for latency-critical server-based
applications; these approaches also focus on many critical resources such as
network bandwidths, memory hierarchies etc, which are critical in determining
QoS guarantees, maximization of utilization and effective co-location. In
contrast, our focus is on developing smart apportioning techniques for cache-
sensitive applications for throughput enhancement while maintaining isolation.
Furthermore, majority of these approaches have several drawbacks. For
instance, PARTIES (Chen et al., 2019) monitors behaviours of latency-critical
applications every $~{}10^{2}ms$, and takes corrective actions only after QoS
violation has been detected. This makes it susceptible to detection lag and
also ill-equipped to handle rapid phase-changes that are in order of few ms
(Fig. 8). A multi-resource partitioning scheme (Roy et al., 2021), constructs
bayesian curves to find “near-optimal” resource configuration. It’s agnostic
to the fact that applications batches may not remain stable in an actual
multi-tenant execution setting, and could be continuously updated (bayesian
optimization solution can change). Additionally, all these approaches have
been evaluated with smaller mix-sizes. On the other hand, Com-CAS can be
utilized in system configurations that execute data-intensive and cache-
sensitive applications. Workloads in such scenarios are mostly optimized and
tuned for in-core memory execution, and thus are agnostic to network
connections, remote data etc.

##  7\. Conclusion

In this work, we proposed Compiler-Guided Cache Apportioning System (Com-CAS)
for effectively apportioning the shared LLC leveraging Intel CAT. Probes
Compiler Framework evaluates cache-atributes such as reuse behaviour, cache
footprints, loop timings and cache sensitivity and relays them. Using these
information, BCache Allocation Framework uses allocation algorithms to
dynamically partitions the cache and schedules processes. Com-CAS improved
average throughput by 15% on unparititioned cache system, and 20% on state-of-
art KPart (El-Sayed et al., 2018), while maintaining the worst individual
application execution time degradation within 15% in a multi-tenancy setting.
In addition, Com-CAS’s scheduling minimizes the co-location of reuse
applications and curtails their overlap. With improved throughput, fulfilled
SLA agreement and reduced process interference, we contend that the proposed
Com-CAS is a viable system for multi-tenant setting.

## References

  * (1)
  * Amvrosiadis et al. (2018) George Amvrosiadis, Jun Woo Park, Gregory R. Ganger, Garth A. Gibson, Elisabeth Baseman, and Nathan DeBardeleben. 2018.  On the diversity of cluster workloads and its impact on research results. In _2018 USENIX Annual Technical Conference (USENIX ATC 18)_. USENIX Association, Boston, MA, 533–546.  https://www.usenix.org/conference/atc18/presentation/amvrosiadis
  * Beamer et al. (2015) Scott Beamer, Krste Asanović, and David Patterson. 2015\.  The GAP Benchmark Suite.  _arxiv_ 1 (2015).  https://doi.org/10.48550/ARXIV.1508.03619
  * Che et al. (2009) Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W Sheaffer, Sang-Ha Lee, and Kevin Skadron. 2009.  Rodinia: A benchmark suite for heterogeneous computing. In _2009 IEEE international symposium on workload characterization (IISWC)_. IEEE, IEEE, NJ, USA, 44–54.
  * Chen et al. (2019) Shuang Chen, Christina Delimitrou, and José F Martínez. 2019\.  Parties: Qos-aware resource partitioning for multiple interactive services. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_. ACM, New York, NY, USA, 107–120.
  * Cook et al. (2013) Henry Cook, Miquel Moreto, Sarah Bird, Khanh Dao, David A Patterson, and Krste Asanovic. 2013\.  A hardware evaluation of cache partitioning to improve utilization and energy-efficiency while preserving responsiveness.  _ACM SIGARCH Computer Architecture News_ 41, 3 (2013), 308–319.
  * El-Sayed et al. (2018) Nosayba El-Sayed, Anurag Mukkara, Po-An Tsai, Harshad Kasture, Xiaosong Ma, and Daniel Sánchez. 2018\.  KPart: A Hybrid Cache Partitioning-Sharing Technique for Commodity Multicores. In _IEEE International Symposium on High Performance Computer Architecture, HPCA 2018, Vienna, Austria, February 24-28, 2018_. IEEE Computer Society, NJ, USA, 104–117.  https://doi.org/10.1109/HPCA.2018.00019
  * Fried et al. (2020) Joshua Fried, Zhenyuan Ruan, Amy Ousterhout, and Adam Belay. 2020\.  Caladan: Mitigating Interference at Microsecond Timescales. In _14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)_. USENIX Association, Virtual Event, 281–297.  https://www.usenix.org/conference/osdi20/presentation/fried
  * Gifford et al. (2021) Robert Gifford, Neeraj Gandhi, Linh Thi Xuan Phan, and Andreas Haeberlen. 2021.  DNA: Dynamic Resource Allocation for Soft Real-Time Multicore Systems. In _2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)_. IEEE, NJ, USA, 196–209.  https://doi.org/10.1109/RTAS52030.2021.00024
  * Grosser et al. (2011) Tobias Grosser, Hongbin Zheng, Raghesh Aloor, Andreas Simbürger, Armin Größlinger, and Louis-Noël Pouchet. 2011.  Polly-Polyhedral optimization in LLVM. In _Proceedings of the First International Workshop on Polyhedral Compilation Techniques (IMPACT)_ , Vol. 2011. 1\.
  * Gupta and Zhou (2015) Saurabh Gupta and Huiyang Zhou. 2015.  Spatial Locality-Aware Cache Partitioning for Effective Cache Sharing. In _44th International Conference on Parallel Processing, ICPP 2015, Beijing, China, September 1-4, 2015_. IEEE Computer Society, NJ, USA, 150–159.  https://doi.org/10.1109/ICPP.2015.24
  * Henning (2006) John L Henning. 2006\.  SPEC CPU2006 benchmark descriptions.  _ACM SIGARCH Computer Architecture News_ 34, 4 (2006), 1–17.
  * Herdrich et al. (2016) Andrew Herdrich, Edwin Verplanke, Priya Autee, Ramesh Illikkal, Chris Gianos, Ronak Singhal, and Ravi Iyer. 2016.  Cache QoS: From concept to reality in the Intel® Xeon® processor E5-2600 v3 product family. In _2016 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, NJ, USA, 657–668.
  * Huang et al. (2018) Kai Huang, Ke Wang, Xiaoxu Zhang, and Xiaolang Yan. 2018\.  Curve fitting based shared cache partitioning scheme for energy saving.  _IEICE Electronics Express_ 15 (10 2018), 15–20180886.  https://doi.org/10.1587/elex.15.20180886
  * Iorgulescu et al. (2018) Călin Iorgulescu, Reza Azimi, Youngjin Kwon, Sameh Elnikety, Manoj Syamala, Vivek Narasayya, Herodotos Herodotou, Paulo Tomita, Alex Chen, Jack Zhang, et al. 2018\.  Perfiso: Performance isolation for commercial latency-sensitive services. In _2018 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 18)_. USENIX Association, Boston, MA, 519–532.
  * Jain et al. (1999) Raj Jain, Arjan Durresi, and Gojko Babic. 1999.  Throughput fairness index: An explanation. In _ATM Forum contribution_ , Vol. 99. ATM Forum contribution.
  * Kasture et al. (2015) Harshad Kasture, Davide B Bartolini, Nathan Beckmann, and Daniel Sanchez. 2015.  Rubik: Fast analytical power management for latency-critical systems. In _2015 48th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, IEEE, NJ, USA, 598–610.
  * Kasture and Sanchez (2014) Harshad Kasture and Daniel Sanchez. 2014.  Ubik: Efficient cache sharing with strict QoS for latency-critical workloads.  _ACM SIGPLAN Notices_ 49, 4 (2014), 729–742.
  * Kobus and Szklarski (2009) Jacek Kobus and Rafal Szklarski. 2009.  Completely Fair Scheduler and its tuning.  _draft on Internet_ (2009).
  * Lattner and Adve (2004) Chris Lattner and Vikram S. Adve. 2004.  LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In _2nd IEEE / ACM International Symposium on Code Generation and Optimization (CGO 2004), 20-24 March 2004, San Jose, CA, USA_. IEEE Computer Society, San Jose, CA, USA, 75–88.  https://doi.org/10.1109/CGO.2004.1281665
  * Liang et al. (2017) Yun Liang, Xiuhong Li, and Xiaolong Xie. 2017.  Exploring cache bypassing and partitioning for multi-tasking on GPUs. In _2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. IEEE, NJ, USA, 9–16.
  * Lo et al. (2015) David Lo, Liqun Cheng, Rama Govindaraju, Parthasarathy Ranganathan, and Christos Kozyrakis. 2015\.  Heracles: Improving resource efficiency at scale. In _Proceedings of the 42nd Annual International Symposium on Computer Architecture_. IEEE, NJ, USA, 450–462.
  * Molnos et al. (2006) Anca M Molnos, Sorin D Cotofana, Marc JM Heijligers, and Jos Tj Van Eijndhoven. 2006.  Throughput optimization via cache partitioning for embedded multiprocessors. In _2006 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation_. IEEE, IEEE, NJ, USA, 185–191.
  * Moreto Planas et al. (2007) Miquel Moreto Planas, Francisco Cazorla, Alejandro Ramírez Bellido, and Mateo Valero Cortés. 2007\.  Explaining dynamic cache partitioning speed ups.  _IEEE Computer Architecture Letters_ 6, 1 (2007), 1–4.
  * Mueller (1995) Frank Mueller. 1995\.  Compiler support for software-based cache partitioning.  _ACM Sigplan Notices_ 30, 11 (1995), 125–133.
  * Muralidhara et al. (2010) Sai Prashanth Muralidhara, Mahmut Kandemir, and Padma Raghavan. 2010\.  Intra-application cache partitioning. In _2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)_. IEEE, NJ, USA, 1–12.
  * Nejat et al. (2020) Mehrzad Nejat, Madhavan Manivannan, Miquel Pericàs, and Per Stenström. 2020.  Coordinated management of DVFS and cache partitioning under QoS constraints to save energy in multi-core systems.  _J. Parallel and Distrib. Comput._ 144 (2020), 246–259.
  * Nikas et al. (2019) Konstantinos Nikas, Nikela Papadopoulou, Dimitra Giantsidi, Vasileios Karakostas, Georgios Goumas, and Nectarios Koziris. 2019.  DICER: Diligent cache partitioning for efficient workload consolidation. In _Proceedings of the 48th International Conference on Parallel Processing_. ACM, New York, NY, USA, 1–10.
  * Noll et al. (2018) Stefan Noll, Jens Teubner, Norman May, and Alexander Böhm. 2018.  Accelerating concurrent workloads with CPU cache partitioning. In _2018 IEEE 34th International Conference on Data Engineering (ICDE)_. IEEE, NJ, USA, 437–448.
  * Park et al. (2019) Jinsu Park, Seongbeom Park, and Woongki Baek. 2019\.  CoPart: Coordinated partitioning of last-level cache and memory bandwidth for fairness-aware workload consolidation on commodity servers. In _Proceedings of the Fourteenth EuroSys Conference 2019_. ACM, New York, NY, USA, 1–16.
  * Pons et al. (2020) Lucia Pons, Julio Sahuquillo, Vicent Selfa, Salvador Petit, and Julio Pons. 2020.  Phase-Aware Cache Partitioning to Target Both Turnaround Time and System Performance.  _IEEE Transactions on Parallel and Distributed Systems_ 31, 11 (2020), 2556–2568.
  * Pouchet et al. (2012) Louis-Noël Pouchet et al. 2012\.  Polybench: The polyhedral benchmark suite.  _URL: http://www. cs. ucla. edu/pouchet/software/polybench_ 1, 1 (2012).
  * Qureshi and Patt (2006) Moinuddin K Qureshi and Yale N Patt. 2006.  Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches. In _2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06)_. IEEE, NJ, USA, 423–432.
  * Ravindran et al. (2007) Rajiv Ravindran, Michael Chu, and Scott Mahlke. 2007.  Compiler-managed partitioned data caches for low power.  _ACM SIGPLAN Notices_ 42, 7 (2007), 237–247.
  * Roy et al. (2021) Rohan Basu Roy, Tirthak Patel, and Devesh Tiwari. 2021\.  SATORI: Efficient and Fair Resource Partitioning by Sacrificing Short-Term Benefits for Long-Term Gains. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, IEEE, NJ, USA, 292–305.
  * Saez et al. (2022) Juan Carlos Saez, Fernando Castro, Graziano Fanizzi, and Manuel Prieto-Matias. 2022.  LFOC+: A Fair OS-Level Cache-Clustering Policy for Commodity Multicore Systems.  _IEEE Trans. Comput._ 71, 8 (2022), 1952–1967.  https://doi.org/10.1109/TC.2021.3112970
  * Sanchez and Kozyrakis (2011) Daniel Sanchez and Christos Kozyrakis. 2011.  Vantage: scalable and efficient fine-grain cache partitioning. In _Proceedings of the 38th annual international symposium on Computer architecture_. IEEE, NJ, USA, 57–68.
  * Sari et al. (2019) Sercan Sari, Onur Demir, and Gurhan Kucuk. 2019.  Fairsdp: Fair and secure dynamic cache partitioning. In _2019 4th International Conference on Computer Science and Engineering (UBMK)_. IEEE, NJ, USA, 469–474.
  * Selfa et al. (2017) Vicent Selfa, Julio Sahuquillo, Lieven Eeckhout, Salvador Petit, and María E Gómez. 2017\.  Application clustering policies to address system fairness with intel’s cache allocation technology. In _2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)_. IEEE, NJ, USA, 194–205.
  * Shen et al. (2019) Fanfan Shen, Yanxiang He, Jun Zhang, Qingan Li, Jianhua Li, and Chao Xu. 2019\.  Reuse locality aware cache partitioning for last-level cache.  _Computers & Electrical Engineering_ 74 (2019), 319–330.
  * Su et al. (2018) Xing Su, Xiangke Liao, Hao Jiang, Canqun Yang, and Jingling Xue. 2018.  SCP: Shared cache partitioning for high-performance GEMM.  _ACM Transactions on Architecture and Code Optimization (TACO)_ 15, 4 (2018), 1–21.
  * Suh et al. (2004) G Edward Suh, Larry Rudolph, and Srinivas Devadas. 2004\.  Dynamic partitioning of shared cache memory.  _The Journal of Supercomputing_ 28, 1 (2004), 7–26.
  * Suo and Yang (2009) Guang Suo and Xue-jun Yang. 2009.  System level speedup oriented cache partitioning for multi-programmed systems. In _2009 Sixth IFIP International Conference on Network and Parallel Computing_. IEEE, NJ, USA, 204–210.
  * Temam et al. (1994) Olivier Temam, Christine Fricker, and William Jalby. 1994\.  Cache interference phenomena.  _ACM SIGMETRICS Performance Evaluation Review_ 22, 1 (1994), 261–271.
  * Wang et al. (2017) Xiaodong Wang, Shuang Chen, Jeff Setter, and José F Martínez. 2017.  SWAP: Effective fine-grain management of shared last-level caches with minimum hardware support. In _2017 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, NJ, USA, 121–132.
  * Wang et al. (2016) Yao Wang, Andrew Ferraiuolo, Danfeng Zhang, Andrew C Myers, and G Edward Suh. 2016\.  SecDCP: secure dynamic cache partitioning for efficient timing channel protection. In _Proceedings of the 53rd Annual Design Automation Conference_. ACM, New York, NY, USA, 1–6.
  * Wu and Martonosi (2011) Carole-Jean Wu and Margaret Martonosi. 2011.  Characterization and dynamic mitigation of intra-application cache interference. In _(IEEE ISPASS) IEEE International Symposium on Performance Analysis of Systems and Software_. IEEE, IEEE, NJ, USA, 2–11.
  * Xiang et al. (2018) Yaocheng Xiang, Xiaolin Wang, Zihui Huang, Zeyu Wang, Yingwei Luo, and Zhenlin Wang. 2018\.  DCAPS: dynamic cache allocation with partial sharing. In _Proceedings of the Thirteenth EuroSys Conference_. ACM, New York, NY, 1–15.
  * Xiang et al. (2019) Yaocheng Xiang, Chencheng Ye, Xiaolin Wang, Yingwei Luo, and Zhenlin Wang. 2019.  EMBA: Efficient Memory Bandwidth Allocation to Improve Performance on Intel Commodity Processor. In _Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019, Kyoto, Japan, August 05-08, 2019_. ACM, New York, NY, 16:1–16:12.  https://doi.org/10.1145/3337821.3337863
  * Xiao et al. (2020) Zheng Xiao, Liwen Chen, Bangyong Wang, Jiayi Du, and Keqin Li. 2020.  Novel fairness-aware co-scheduling for shared cache contention game on chip multiprocessors.  _Information Sciences_ 526 (2020), 68–85.
  * Xu et al. (2018) Cong Xu, Karthick Rajamani, Alexandre Ferreira, Wesley Felter, Juan Rubio, and Yang Li. 2018\.  dcat: Dynamic cache management for efficient, performance-sensitive infrastructure-as-a-service. In _Proceedings of the Thirteenth EuroSys Conference_. ACM, New York, NY, USA, 1–13.
  * Ye et al. (2014) Ying Ye, Richard West, Zhuoqun Cheng, and Ye Li. 2014\.  Coloris: a dynamic cache partitioning system using page coloring. In _2014 23rd International Conference on Parallel Architecture and Compilation Techniques (PACT)_. ACM, New York,NY, USA, 381–392.
  * Yuan et al. (2021) Yifan Yuan, Mohammad Alian, Yipeng Wang, Ren Wang, Ilia Kurakin, Charlie Tai, and Nam Sung Kim. 2021.  Don’t Forget the I/O When Allocating Your LLC. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, NJ, USA, 112–125.
  * Zhang and Zhu (2020) Xi Zhang and Qixuan Zhu. 2020.  HiCa: Hierarchical Cache Partitioning for Low-Tail-Latency QoS Over Emergent-Security Enabled Multicore Data Centers Networks. In _ICC 2020-2020 IEEE International Conference on Communications (ICC)_. IEEE, NJ, USA, 1–6.
  * Zhu and Erez (2016) Haishan Zhu and Mattan Erez. 2016.  Dirigent: Enforcing QoS for latency-critical tasks on shared multicore systems. In _Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems_. ACM, New York, NY, USA, 33–47.