Guillaume Aupy

Anne Benoit

Brice Goglin

Loïc Pottier

Yves Robert

Co-scheduling HPC workloads on cache-partitioned CMP platforms

Keywords: Co-scheduling, cache-partitioning, multiprocessor chips, cache allocation technology (CAT)

Co-scheduling techniques are used to improve the throughput of applications on chip multiprocessors (CMP), but sharing resources often generates critical interferences. We focus on the interferences in the last level of cache (LLC) and use the Cache Allocation Technology (CAT) recently provided by Intel to partition the LLC and give each co-scheduled application their own cache area. We consider m iterative HPC applications running concurrently and answer the following questions: (i) how to precisely model the behavior of these applications on the cache partitioned platform? and (ii) how many cores and cache fractions should be assigned to each application to maximize the platform efficiency? Here, platform efficiency is defined as maximizing the performance either globally, or as guaranteeing a fixed ratio of iterations per second for each application. Through extensive experiments using CAT, we demonstrate the impact of cache partitioning when multiple HPC application are coscheduled onto CMP platforms.

I. INTRODUCTION

Co-scheduling applications on a chip multiprocessor (CMP) has received a lot of attention recently [START_REF] Muralidhara | Reducing memory interference in multicore systems via application-aware memory channel partitioning[END_REF], [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF]. The main motivation is to improve the efficiency of the parallel execution of each application. Consider for instance the Gyoukou ZettaScaler supercomputer, currently ranked #4 in the TOP500 benchmark [START_REF] Strohmaier | The top500 benchmark[END_REF]: it uses PEZY-SC2, a 2048-core processor chip sharing a 40MB last level cache (LLC) [START_REF] Computing | Zettascaler-2.0 configurable liquid immersion cooling system[END_REF]: with so many cores at disposal, few applications can efficiently be deployed on the entire computing platform. This is because most application speedup profiles obey Amdahl's law, which tends to severely limit the number of cores to be used in practice.

The remedy is simple: schedule many applications to execute concurrently; each application receives only a fraction of the total number of cores, hence its parallel efficiency is improved. Which fraction of computing resources should actually be assigned to each application depends on many factors, including speedup profiles, but also external constraints prescribed by the user such as response times or application priorities.

Unfortunately, the remedy comes with complications: when multiple applications run concurrently on a CMP, they compete to access shared resources such as the LLC, and their performance actually degrades. This issue turned out so severe [START_REF] Leverich | Reconciling high server utilization and sub-millisecond quality-of-service[END_REF], [START_REF] Zhuravlev | Addressing shared resource contention in multicore processors via scheduling[END_REF] that the name co-run degradation has been coined.

Modeling and studying cache interferences to prevent co-run degradation has been the object of many studies [START_REF] Zhang | Smite: Precise QOS prediction on real-system SMT processors to improve utilization in warehouse scale computers[END_REF], [START_REF] Bui | Impact of cache partitioning on multi-tasking real time embedded systems[END_REF], [START_REF] Tian | A study on optimally co-scheduling jobs of different lengths on chip multiprocessors[END_REF] (see Section II on related work for more details).

Intel recently introduced a new hardware feature for cache partitioning called Cache Allocation Technology (CAT) [START_REF] Nguyen | Introduction to Cache Allocation Technology in the Intel R Xeon R Processor E5 v4 Family[END_REF]. CAT allows the programmer to reserve cache subsections, so that when several applications execute concurrently, each of them has its own cache area. Using CAT, Lo et al. [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF] showed experimentally that important gains could be reached by co-scheduling latency-sensitive applications with a strict cache partitioning. In this paper, we also use CAT to partition the LLC into several areas when co-scheduling applications, but with the objective of optimizing the throughput of insitu or in-transit analysis for large-scale simulations. Indeed, in such simulations, data is generated at each iteration and periodically analyzed by parallel processes on dedicated nodes, concurrently of the main simulation [START_REF] Sewell | Large-scale compute-intensive analysis via a combined in-situ and co-scheduling workflow approach[END_REF]. If these dedicated nodes belong to the main simulation platform (thereby reducing the number of available cores for simulation), we speak of in-situ processing, while if they belong to an auxiliary platform, we speak of of in-transit processing [START_REF] Bauer | In situ methods, infrastructures, and applications on high performance computing platforms[END_REF]. In both cases, several applications (various computational kernels for data analysis) have to run concurrently to analyze the data in parallel of the current simulation step. The constraint is to achieve a prescribed throughput for each application, because the outcome of the analysis drives the next steps of the simulation. In the simplest case, each application will have to complete within the time of a simulation step, hence we need to achieve the same throughput for each application, and maximize that value. In other situations, some applications may be needed only every k simulation steps, with a different value of k per application [START_REF] Malakar | Optimal scheduling of in-situ analysis for large-scale scientific simulations[END_REF]. This calls for achieving a weighted throughput per application, and for maximizing the minimum value of these weighted throughputs, which dictates the global rate at which the data analysis can progress.

The first major contribution of this paper is to introduce a model that characterizes application performance. Next, we provide strategies to decide how many cores and which cache fraction should be assigned to each application, in order to maximize the weighted throughput. A dynamic programming algorithm provides an optimal strategy, according to the model. The last major contribution is to provide an extensive set of experiments conducted on the Intel Xeon, which assesses the gains achieved by our optimal resource allocation strategy. We therefore demonstrate that cache-partitioning strategies can lead to gains in performance for in-situ analysis for large-scale simulations.

The rest of the paper is organized as follows. Section II provides an overview of related work. Section III details the main framework and all application/platform parameters, as well as the optimization problem. Section IV presents five co-scheduling strategies, including a dynamic programming approach that provides an optimal resource assignment (according to the model). Section V describes the real cache partitioned platform used to perform the experiments. Section VI assesses the accuracy of the model. Section VII reports extensive experiments. Finally, Section VIII summarizes our main contributions and discusses directions for future work.

II. RELATED WORK

Recent multi-core processors show dozens of cores and a shared cache always larger. In this context, co-scheduling has been extensively studied [START_REF] Muralidhara | Reducing memory interference in multicore systems via application-aware memory channel partitioning[END_REF], [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF]. The main idea behind coscheduling is to execute applications concurrently rather than in sequence in order to improve the global throughput of the platform. Indeed, many HPC applications are not perfectly parallel, and it is not beneficial to deploy them on the entire platform: the application speedup becomes too low beyond a given core count. A new trend in large-scale simulations is in-situ and in-transit approaches, to visualize and analyze the data during the simulation [START_REF] Dreher | A Flexible Framework for Asynchronous In Situ and In Transit Analytics for Scientific Simulations[END_REF]. Basically, the idea behind these approaches is that a new dataset is generated periodically, and we need to run different applications on different parts of this dataset before the next period. In the in-situ approach, simulation and analyzes are co-located in the same node, while in the in-transit approach, the data analyzes are outsourced onto dedicated nodes [START_REF] Bauer | In situ methods, infrastructures, and applications on high performance computing platforms[END_REF]. Several studies have shown that large-scale simulations with in-situ could benefit from coscheduling approaches [START_REF] Sewell | Large-scale compute-intensive analysis via a combined in-situ and co-scheduling workflow approach[END_REF], [START_REF] Bao | A data colocation grid framework for big data medical image processing-backend design[END_REF]. The difficulty consists in ensuring that the in-situ part processes the data fast enough to avoid slowing down the main simulation, which is directly related to co-scheduling issues: how to partition the resources across the concurrent analysis applications sharing the CMP? Shared resources include cache, memory, I/O channels and network links, but among potential degradation factors, cache accesses are prominent [START_REF] Zhuravlev | Survey of scheduling techniques for addressing shared resources in multicore processors[END_REF]. Modeling application interferences is challenging, and one way to address this problem is to partition the cache to avoid these potential interferences. Multiple cache partitioning schemes have been designed, through hardware techniques [START_REF] Kim | Fair cache sharing and partitioning in a chip multiprocessor architecture[END_REF], [START_REF] Qureshi | Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches[END_REF], [START_REF] Nesbit | Virtual private caches[END_REF] and software techniques [START_REF] Taylor | The tlb slice-a low-cost highspeed address translation mechanism[END_REF], [START_REF] Tam | Managing shared l2 caches on multicore systems in software[END_REF], [START_REF] Lin | Gaining insights into multicore cache partitioning: Bridging the gap between simulation and real systems[END_REF], [START_REF] Guan | Cache-aware scheduling and analysis for multicores[END_REF]. Most of the hardware approaches are efficient with a very low overhead at the execution time, but they suffer from an extra cost in terms of hardware components. In addition, hardware solutions are difficult to implement and often only tested through simulated architectures. On the side of software-based solutions, the most popular is page coloring, where physical pages are selected for application allocations so that they end up in specific sections of the cache. Tam et al. [START_REF] Tam | Managing shared l2 caches on multicore systems in software[END_REF], showed that important gains can be achieved through a static partitioning of the L2 cache using page coloring. Besides static strategies, dynamic cache partitioning strategies using page coloring have also been studied. In [START_REF] Lin | Gaining insights into multicore cache partitioning: Bridging the gap between simulation and real systems[END_REF], the cache partitioning is refined and adjusted periodically at runtime, with the objective to maximize platform efficiency.

Modeling application interference is a challenging task, and Hartstein et al. [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF] showed, with the Power Law of cache misses (or the √ 2 rule), how the cache size affects the cache miss ratio. The Power Law states that, if for a baseline cache of size C 0 , the cache miss ratio is equal to m 0 , then for a cache of size C, the cache miss ratio m = m 0 C0 C α , where α is usually set to 0.5.

In a previous work [START_REF] Aupy | Co-scheduling Amdahl applications on cachepartitioned systems[END_REF] using this Power law, we focused on a static allocation of LLC cache fractions, and core numbers, to concurrent applications, as a function of several parameters (cache-miss ratio, access frequency, operation count) in order to minimize the total execution time. The problem was shown to be NP-complete and heuristics were provided. We used simulations to assess the performance of these heuristics, because at that time no cache partitioning technologies were available. Intel recently released a new software technique to internally partition the last level cache (LLC), called the Cache Allocation Technology (CAT) [START_REF] Nguyen | Introduction to Cache Allocation Technology in the Intel R Xeon R Processor E5 v4 Family[END_REF], [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF]. In this paper, we use CAT to experiment with a real cache partitioned platform. The main differences with our previous work are as follows. In this work: (i) we use an application model that renders the problem tractable and is still sufficiently precise; (ii) we target a real-life optimization objective that corresponds to weighted throughput in steady-state processing; (iii) we provide an optimal polynomial algorithm for this objective function; (iv) finally, we perform actual implementations and experiments to verify our model and algorithms. To the best of our knowledge, this work is the first co-scheduling study for a cache partitioned system (using CAT) with HPC workloads.

III. MODEL AND OPTIMIZATION PROBLEM

The objective is to execute m iterative applications A 1 , . . . , A m on P identical cores. The applications are sharing a cache of size C, which can be divided into X different fractions. For instance, if X = 20, we can give several fractions of 5% of the cache to each application.

Let p i be the number of cores on which application A i is executed, and let x i be the number of fractions of cache assigned to A i , for 1 ≤ i ≤ m. Hence, A i uses a cache of size xi X C. We must have m i=1 p i = P and m i=1 x i = X, i.e., all the cores and the cache fractions are partitioned across the applications.

Given p i and x i , an application A i executes one iteration in time T real i (p i , x i ). On a given platform, all these values can be measured, and we aim at providing a model that characterizes these values. In the model, we use the following formula:

T i (p i , x i ) = t i (p i ) (1 + h i (x i )) , (1)
where t i (p i ) represents the computation cost and h i (x i ) the slowdown induced by cache misses in the LLC. Intuitively, the computation cost decreases when p i increases, and similarly, the slowdown decreases when x i increases, i.e., t i (p i ) and h i (x i ) are non-increasing functions. In this formula, we assume that the slowdown incurred by cache misses does not depend on the number of cores assigned to the application. While this assumption may not be true in practice, we will discuss the model accuracy in Section VI, where we measure cache misses and refine the model. We now detail the model for t i (p i ) and h i (x i ).

A. Computations t i (p i )

We assume that all applications obey Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]:

t i (p i ) = s i T seq i + (1 -s i ) T seq i pi , where T seq i
is the sequential time of the application executed with 100% of the cache, and s i is the sequential fraction of the application.

B. Cache misses effect h i (x i )

The most challenging part is to model the slowdown factor h i (x i ). In chip multiprocessors (CMP), many studies have observed that cache miss ratio follows the Power Law, also called the √ 2 rule [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF], [START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF], [START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF]. The Power Law of cache misses states that for a cache of size C act , the cache miss ratio r can be expressed as

r = r 0 C 0 C act α , (2)
where r 0 represents the cache miss ratio for a baseline cache of size C 0 , and α is a parameter ranging from 0.3 to 0.7, with an average at 0.5. We consider α = 0.5 in the following. We slightly generalize the Power Law formula (with α = 0.5) to avoid side effects, and define the slowdown as follows:

h i (x i ) = a i + b i √ x i , (3)
where a i and b i are constants depending on the application A i .

From Equation ( 2) with α = 0.5, we have

b i = r 0 C0X C (since C act = xi X C
), and a i is a constant added to avoid side effects. In Section VI, we determine a i and b i by interpolation, from experimentally measured cache misses, see Table II.

Overall, when assigning p i cores and a fraction x i of the cache, and letting c i = 1 + a i , an application A i executes one iteration in time:

T i (p i , x i ) = t i (p i ) c i + b i √ x i . (4)

C. Optimization problem

As stated in Section I, the goal is to maximize a weighted throughput, since analysis applications may be required at different rates, from every simulation step to every tenth (or more) step [START_REF] Malakar | Optimal scheduling of in-situ analysis for large-scale scientific simulations[END_REF]. We let β i denote the weight of application A i for 1 ≤ i ≤ m. Intuitively, β i represents the number of times that we should execute application A i at each iteration step. These priority values are not absolute but relative: for m = 2 applications, having β 1 = 1 4 and β 2 = 1 means we execute four times A 2 (at each step) while executing A 1 only once (every fourth step). This is equivalent to having β 1 = 1 and β 2 = 4 if we change the granularity of the simulation steps. In fact, what matters is the relative number of executions of each A i that is required, hence we aim at maximizing the weighted throughput. The throughput achieved when executing β i instances of application A i is 1 βiTi(pi,xi) , and the objective is to partition the shared cache and assign cores such that the total time taken by the slowest application is minimal, i.e., the lowest weighted throughput is maximal. The weighted throughput allows us to ensure some fairness between applications, and to enforce a better analysis rate of the simulation results whenever the bottleneck is the slowest application. Note that letting β i = 1 leads to maximizing the rate of the analysis when all applications are needed at the same frequency. The optimization problem is formally expressed below: Definition 1 (COSCHED-CACHEPART). Given m iterative applications with priorities (A 1 , β 1 ), . . . , (A m , β m ) and a platform with P identical cores sharing a memory of size C with X fractions of cache, the COSCHED-CACHEPART problem consists in finding a schedule

{(p 1 , x 1 ), . . . , (p m , x m )} such that MAXIMIZE min 1≤i≤m 1 βiTi(pi,xi) SUBJECT TO m i=1 p i = P, m i=1 x i = X.

IV. SCHEDULING STRATEGIES

In this section, we introduce several co-scheduling strategies that we will compare via experiments on the Intel Xeon. We start with a (theoretically) optimal schedule, and then present simple heuristics that we use for comparison.

A. Optimal solution to COSCHED-CACHEPART

Given the time to execute one iteration of application A i with p i cores and a fraction x i of the cache T i (p i , x i ), we can solve the COSCHED-CACHEPART problem optimally, with a dynamic programming algorithm.

Theorem 1. COSCHED-CACHEPART can be solved in time O(mP X), where m is the number of applications, P is the number of processors, and X is the number of different possible cache fractions. Proof: Let T (i, q, c) be the maximum weighted throughput that can be obtained with applications A 1 , . . . , A i , using q cores and c fractions of cache. The goal is to find T (m, P, X). We compute T (i, q, c) as follows:

T (i, q, c) =                    max 1≤q1≤q 1≤c1≤c 1 β1T1(q1,c1) if i = 1, max 1≤qi<q 1≤ci<c min T (i -1, q -q i , c -c i ), 1 βiTi(qi,ci) otherwise.
The base case i = 1, for one application, takes the best out of all possible allocations (in terms of number of processors and number of cache fractions). Note that for most execution time profile, the execution time in this case is obtained by T (1, q, c) = 1 β1T1(q,c) , since using less processors or less fractions of cache would only increase the execution time, but we write the general expression to encompass any execution time profile, and not only the one given by Equation ( 4).

In the recurrence, we try all possible number of processors and number of cache fractions for application i, and re-use the optimal solution for the i -1 other applications. If we did not use the optimal solution, we would be able to create a better solution, hence it is easy to see that the problem has an optimal substructure property and can be solved with a dynamic programming algorithm.

There are mP X values to compute, and they can each be obtained in constant time, except for the generalized base case, where we need to perform a maximum over P X values. Overall, with the execution profile of our model, we can compute all values in time O(mP X), and the complexity becomes O(mP 2 X 2 ) in the general case. In practice on the Intel Xeon, we have m ≤ P = 14, and X = 20, hence the dynamic programming algorithm executes almost instantaneously in all the experiments.

This optimal algorithm provides us with our first strategy to schedule applications, and it is called DP-CP (Dynamic Programming with Cache Partitioning). Checking the behavior of this strategy in practice will assess the accuracy of the performance model, when using the values of T i (p i , x i ) obtained with the model of Section III.

B. Equal-resource assignment

To evaluate the global efficiency of the optimal solution for DP-CP, we compare it to EQ-CP, a simple strategy that allocates the same number of cores and the same number of cache fractions to each application. The algorithm is the following: we start to give x i = X m and p i = P m for all i, then, we give the P mod m extra cores one by one to the first P mod m applications, and we give the X mod m extra cache fractions one by one to the last X mod m applications. Doing this, we forbid the case where an application receives an extra core plus an extra fraction of cache, thereby avoiding a totally unbalanced equal assignment.

C. Impact of cache allocation

In order to isolate the impact of cache partitioning on performance, we introduce some variants where only the cache allocation is modified. DP-EQUAL uses the number of cores returned by the dynamic programming algorithm, hence the same as for DP-CP, but shares the cache equally across applications, as done by EQ-CP. We also consider strategies that do not enforce any cache partitioning, but only decide on the number of cores for each application. DP-NOCP uses the same number of cores as DP-CP, and EQ-NOCP uses an equal-resource assignment as in EQ-CP. However, for these two strategies, all applications share the whole cache, i.e., CAT is disabled.

V. EXPERIMENTAL SETUP

In this section, we first describe the platform and the benchmark applications in Section V-A. Then in Section V-B, we explain in details the Cache Allocation Technology CAT.

A. Platform and applications

The experimental platform is composed of a Dell Pow-erEdge R730 server with two Intel Xeon E5-2650L v4 processors (Broadwell microarchitecture). Each processor contains P = 14 cores (with Hyper-Threading disabled) sharing a 35MB last-level cache (Cluster-on-Die disabled), divided into X = 20 slices (or fractions). Nodes run a vanilla 4.11.0 Linux kernel with cache partitioning enabled.

Only one processor (with 14 cores) is used for the experiments, since the LLC is not shared across processors. It matches standard practice because users who co-schedule real-applications often place each application inside a single processor to benefit from the shared cache. Batch schedulers also allocate cores of the same processor whenever possible. Hence our work focuses on co-scheduling the subset of applications that are assigned to a single processor by the user or by the batch scheduler.

Cache experiments are very sensitive to perturbations, so we take great care to ensure that all experiments are fully reproducible. To avoid perturbations: (i) we average values obtained (like cache misses) over 20 (in Section VI) or 5 (in Section VII) identical runs; (ii) we flush the last-level cache entirely between runs; and (iii) experiments run on a dedicated processor while the program launching and monitoring them runs on the other processor. All the data presented in this paper (cache misses, number of floating operations, etc), is obtained with PAPI 5.5.1 [START_REF] Browne | A portable programming interface for performance evaluation on modern processors[END_REF]. Each benchmark is compiled using the Intel Fortran Compiler 17.0.1 with the optimization level -O2 and the flag -mcmodel=medium.

For validation and performance evaluation, we use HPC workloads from class A NAS benchmarks [START_REF] Bailey | The NAS Parallel Benchmarks -Summary and Preliminary Results[END_REF]. Due to lack of space, we focus on three applications CG, MG and FT, which exhibit the most interesting behaviors (see Table I). Three additional NAS benchmarks are considered in the extended version [START_REF] Aupy | Co-scheduling HPC workloads on cache-partitioned CMP platforms[END_REF], and lead to similar conclusions.

B. Cache Allocation Technology

The Cache Allocation Technology (CAT) [START_REF] Nguyen | Introduction to Cache Allocation Technology in the Intel R Xeon R Processor E5 v4 Family[END_REF]

VI. ACCURACY OF THE MODEL

In this section, we assess the precision of the model introduced in Section III. First, we detail the experimental protocol and explain how to obtain the model parameters for each application in Section VI-A. Then in Section VI-B, we study the behavior of cache misses on the platform described in Section V-A. Finally, we study in Section VI-C the accuracy of the model by comparing the expected execution time from Equation ( 4) to the measured one T real .

A. Experimental protocol

To instantiate the model and check its accuracy, we need to find for each application the value of three parameters used in Equation ( 4): s i (sequential fraction), a i (or equivalently c i = a i + 1), and b i (cache slowdown). To this purpose, we monitor each application with PAPI [START_REF] Browne | A portable programming interface for performance evaluation on modern processors[END_REF] and use multiple interpolations on the produced data to find the desired constants. More precisely, we proceed as follows. Each application A i executes alone on a dedicated processor. First, we give 100% of the cache to the application A i and vary the number of cores from 1 to 14 to derive the sequential fraction s i . Then, for each cache fraction x i ranging from 15% to 85%, we record the number of cache misses when p i ranges from 1 to 14 and derive values for c i and b i . Finally, we put the pieces together, keeping the value of s i while scaling c i and b i by a constant factor, thereby deriving the final values for T i (p i , x i ) in Equation ( 4).

As a side note, we point out that this complicated (and definitely not scalable) approach was necessary because the least-square interpolation program would not converge when fed directly with 80% of the 280 experimental values for each application (14 processors, and 16 values of x out of 20). We expect it will be even more challenging to instantiate the model for future platforms where the number of cores will be higher.

Note that the Power Law with α = 0.5 suits well the behavior of compute-intensive benchmarks such as CG, but struggles to model memory/communication-intensive applications such as MG and FT. The results for each application are displayed in Table II (more detailed results are available in [START_REF] Aupy | Co-scheduling HPC workloads on cache-partitioned CMP platforms[END_REF]).

B. Cache miss behavior

Figure 2 shows the evolution of cache miss ratios for the three applications depending on the number of cores and cache fraction. We observe that for most applications, the cache miss ratio increases with the number of cores for small cache fractions, while it does not vary significantly with the number of cores for higher cache fractions. Hence, most of the time, the assumption taken in the model that the slowdown incurred by cache misses does not depend on the number of cores is acceptable, even though there might be some differences, in particular for the MG application.

C. Accuracy of the execution time

Finally, we aim at verifying the accuracy of the execution time predicted by the model. Figure 3 shows, for each application, the comparison between the measured execution time and the model, when the application runs alone on the platform (no co-scheduling here). In Figure 3, the number of cores varies from 1 to 14 while the cache fraction is fixed at x = 3 (or 15%).

Figure 4 shows the relative error between predictions and the real data. The relative error is defined as

E i (p i , x i ) = T i (p i , x i ) -T real i (p i , x i ) T real i (p i , x i ) ,
where T real i (p i , x i ) is the measured execution time on the cache partitioned platform for application A i with p i cores and x i fractions of cache. We observe that our model predicts execution times rather well for CG and MG, with less than 25% of error for worst cases. For FT, the model is accurate for x i ≥ 6 (30%) and p i ≤ 10, with a relative error below 15%, but the model loses accuracy for small cache fractions and high number of cores. This is due to a specific behavior of FT: its execution time tends to become constant after a certain core threshold (see Figure 3), while the model expects a strictly decreasing execution time. This constant plateau is not due to Amdahl's law (FT is parallel enough to scale up to 14 cores), hence a contention effect (either from the cache or the memory bandwidth) is probably behind this constant level in performance. Another reason to explain these mispredictions when the number of cores increases, is that the model assumes that the number of cores does not impact LLC cache misses, which is not always true in practice, as seen in Figure 2.

D. Summary

We have checked that the model is relatively accurate, even though it takes some simplifying assumptions that are not completely true in practice (cache misses independent of the number of cores, execution time decreasing with higher core counts). The next section assesses the performance of the scheduling strategies, in particular when using the model.

VII. RESULTS

To assess the performance of the scheduling strategies of Section IV and to evaluate the impact of cache partitioning on co-scheduling performance, we conduct an extensive campaign of experiments using a real cache partitioned system.

A. Experimental protocol

The platform and the applications used for all the experiments are described in Section V. Recall that we consider iterative applications, hence we have modified their main loop such that each of them computes for a duration T . We choose a value for T = 3 minutes, which is large enough to ensure that each application reaches the steady state with enough iterations. In addition, for all the following experiments, we use 12 cores out of the 14 available, to avoid rounding effects when we co-schedule a number of applications that is not divisible by the number of cores. Similar results were obtained when co-scheduling applications on all 14 cores, in particular with two applications that could use seven cores each. To study the performance of the different algorithms in terms of weighted throughput, we measure the time for one iteration of A i : T i = T #iteri , where #iter i is the number of iterations of application A i during T . Then, we compute min i 1 βiTi . We are then interested by the relative speed of each application with respect to the others. Indeed, recall that for all i, j, the goal is to have β i T i = β j T j , by definition of the β's. Hence, we further study the following fairness criterion, representing the distance to the optimal fairness, ∆ f airness :

∆ f airness = i =j β i T i β j T j -1 . (5)
In addition to studying the maximum weighted throughput that can be obtained with the applications, we also report the value of ∆ f airness in the experiments, so as to assess whether the heuristics are ensuring that the correct number of iterations of each application is performed during a given amount of time. The goal is to have ∆ f airness as close to 0 as possible.

B. Impact of cache partitioning

The first step is to assess the impact of cache partitioning (CP) on performance. To this purpose, we co-schedule two applications, so we have three combinations (CG+MG, CG+FT, FT+MG). For all i, j, we set the number of cores for A i and A j to six, and we vary the fraction of cache allocated to A i from 5% to 95% while, conversely, the cache fraction of A j is varying from 95% to 5%. The y-axis represents the aggregated number of iterations executed by all applications. We run the applications both with cache partitioning enabled or not.

Figure 5 shows the impact of CP for CG+MG: we see that when CG has more than 35% of the cache, CP outperforms the version without CP. The impact of CP lies in the behavior of each application, more specifically their data access pattern. CG is a compute intensive application with an irregular memory access pattern, while MG is a memory intensive application. More specifically, MG does not take a great benefit for more cache beyond 35%, while the performance of CG greatly depends on the cache size (for more details on application behaviors, see Figure 2). Without a cache partitioning scheme, by reading/writing a lot of different cache lines, MG will often evict CG cache lines, hence significantly decreasing its performance.

For the other combinations CG+FT or FT+MG (see Figures 6 and7), we see little improvement, since FT is more communication intensive (all-to-all communication) than strictly memory intensive, hence the gain obtained by cache partitioning is less important than for CG+MG. The worst case for cache partitioning is when combining FT with MG, since both applications are memory and communication intensive, and hence none of them needs a strict cache partitioning, since their use of the cache varies during iterations.

Overall, the cache partitioning is very interesting when compute-intensive and memory-intensive application are coscheduled (important gain, up to 25%, for CG+MG, small gain for CG+FT). On the contrary, FT and MG together perform badly with the cache partitioning enabled, these applications do not benefit from the cache to improve their execution time by iteration. Hence, the behavior of applications has a strong impact on the global performance of cache partitioning, and in general, co-scheduling applications with the same behavior results in degraded global performance when using cache partitioning. is really interesting to isolate applications that pollute the cache, such as MG. Figure 9 clearly shows the impact of cache on performance when the number of is set for each application. In the worst cases, for instance with FT and MG, the cache partitioning does not improve performance, but does not degrade it either.

D. Co-scheduling results with three applications

Similarly to the case with two applications, with three applications (A 1 , A 2 , A 3 ), β 3 is ranging from 0.25 to 4, while β 1 = β 2 = 1. We present only two examples of co-schedules; more combinations are available in [START_REF] Aupy | Co-scheduling HPC workloads on cache-partitioned CMP platforms[END_REF], with no significantly different conclusions. Experiments with different values of β 1 and β 2 also provide similar results.

Figure 10 shows the minimum throughput obtained when we co-schedule 2CG+MG, while the weight β M G associated to MG is ranging from 0.25 to 4. Note that it is interesting to co-schedule multiple copies of the same application (two CGs in this scenario) in order to improve the global efficiency, when this application exhibits a speedup profile with limited gain from adding extra cores and/or extra fractions of caches. We observe that the scheduling strategies building on the dynamic programming algorithm, namely DP-CP, DP-EQUAL and DP-NOCP, outperform EQ-CP and EQ-NOCP. In addition, cache partitioning shows a great interest here: DP-CP exhibits a gain around 15% on average over DP-NOCP and DP-EQUAL. The model prediction is also very accurate with three applications, even more accurate than with two applications. This difference of accuracy mainly lies in the fact that our model is more accurate when p i and x i are not extreme (close to the minimum or the maximum possible), which happens when the number of applications increases. The fairness criterion ∆ f airness is also depicted. Recall that ideally, we would like to have β i T i = β j T j for all i, j (see Equation ( 5)). We observe that the method that is the closest to zero is DP-CP, confirming the strong interest of cache partitioning.

Figure 11 shows the minimum throughput obtained when co-scheduling the three different applications, while varying only the weight β FT of FT. We observe that the performance of the three DP-based algorithms is close to the performance obtained with the equal-resource assignment for β FT smaller than 0.5, but for the other cases, DP-CP and all its variants outperform EQ-CP and EQ-NOCP. The fairness criterion ∆ f airness leads to the same conclusion: DP-CP, DP-NOCP and DP-EQUAL are much closer to zero than EQ-CP and EQ-NOCP, especially when β FT is larger than 0.5.

Summary: Overall, we showed that we can obtain important gains using cache partitioning (CP) when co-scheduling three applications, but it is not always the case. The difficulty of obtaining some gain with CP increases with the number of applications involved. The first reason lies in the cache size, often too small to be efficiently partitioned between the applications. The second reason is related to the behavior of the co-scheduled applications. The results show that coscheduling one or two compute-intensive applications, such as CG, plus one memory-intensive application, such as MG, is a good way to achieve significant improvements with cache partitioning. CG is a compute-intensive kernel that performs a lot of irregular memory accesses, while MG is a memoryintensive kernel, hence if we co-schedule one CG and one MG, MG will often evict cache lines belonging to CG, which will slow down its execution.

VIII. CONCLUSION

We have investigated the problem of co-scheduling iterative HPC applications, using the CAT technology provided by Intel to partition the cache. We have proposed a model for the execution time of each application, given a number of cores and a fraction of cache, and we have shown how to instantiate the model on applications coming from the NAS benchmarks. The model turns out to be accurate, as shown in the experiments where we compare the execution time predicted by the model to the real execution time. Several scheduling strategies have been designed, with the goal to maximize the minimum weighted throughput of each application. In particular, we have introduced an optimal strategy for the model, based upon a dynamic programming algorithm. The results demonstrate that in practice, the optimal strategy often leads to better results than a naive strategy sharing equally the resources between applications. Also, we have determined which combinations of applications benefit most from cache partitioning, and demonstrated the usefulness of cache partitioning.

Future work will be devoted to extending this experimental study. We hope to get access to platforms with larger shared caches, so that we could scale up the experiments and confirm the usefulness of cache partitioning techniques. The first research direction is to design a better interpolation strategy, capable of retro-fitting a subset of the experimental data (execution times for each application, with each processor number and cache fraction) into a simple formula like Equation (4), and with good precision. We will also generalize the experiments to multiprocessors and see if there is a benefit in moving applications from one processor to another, in order to avoid co-locating several cache-intensive applications on the same processor. Another interesting direction would be to consider the Universal Scalability Law [START_REF] Gunther | Guerrilla capacity planning -a tactical approach to planning for highly scalable applications and services[END_REF] instead of Amdahl's law, thereby generalizing the model in order to account for contentions.

Figure 1 :

 1 Figure 1: CAT example with 2 classes of service, 3 cores and a 4-bit capacity mask (CBM). First COS has 2 cores and 75% of the LLC, the second class of service has the remaining resources.

Figure 2 :

 2 Figure 2: Evolution of cache miss ratio with x i and p i .

Figure 3 :Figure 4 :

 34 Figure 3: Comparison between predicted execution time by the model and measured execution time, when varying the number of cores up to 14 and with a cache fraction set to 15%.

Figure 5 :

 5 Figure 5: CG and MG (six cores each).

Figure 7 :

 7 Figure 7: FT and MG (six cores each).

Figure 8 :

 8 Figure 8: Minimum throughput and ∆ f airness for CG and MG.

Figure 9 :

 9 Figure 9: Minimum throughput and ∆ f airness for CG and MG, where both applications have six cores.

Figure 10 :

 10 Figure 10: Minimum throughput and ∆ f airness for 2CG+MG.

Figure 11 :

 11 Figure 11: Minimum throughput and ∆ f airness for CG, MG and FT.

Table I :

 I is part of a larger set of Intel technologies that are called the Resource Director Technology (RDT) and supported since the Haswell architecture. RDT lets the operating system group applications Description of the NAS parallel benchmarks.

	App Description
	CG	Uses conjugate gradients method to solve a large sparse
		symmetric positive definite system of linear equations
	MG	Performs a multi-grid solve on a sequence of meshes
	FT	Performs discrete 3D fast Fourier Transform
	into classes of service (COS). Each class of service describes
	the amount of resources, in particular cache, that assigned
	applications can use. The CAT divides the LLC into X
	slices of cache (see Figure 1). Each COS has a set of slices
	that applications can use: When reading or writing memory
	requires to fetch a cache line in the LLC, that cache line
	must be allocated in the slices available to the class of the
	current application. The set of slices available to a class is
	a capacity bit-mask (CBM) of length X. Note that CAT has
	some technical restrictions:
	Also, we consider a strict cache partitioning, hence each COS
	contains only one application (and each cache slice is available
	to a single application).
		COS 1		COS 2
		p 1	p 2	p 3
	LLC
		CBM 1 = 1110	CBM 2 = 0001

• The number of slices (CBM length) and classes are architecture dependent (20 and 16 on our platform); • A CBM cannot be empty (each class of applications must have at least one fraction of cache); • Bits set in a CBM must be contiguous; • Slices are not distributed geographically in the LLC, and address hashing ensures spreading of slices over the entire LLC; In other words, 0x10000 and 0x00001 CBM should behave exactly the same with respect to locality; there are no NUCA effects (Non Uniform Cache Access).

Table II :

 II Parameters a i , b i , and s i , obtained by interpolation from the data produced by measurements.

	App i	a i	b i	s i
	CG	-0.0379	0.0474	0
	MG	0.0460	0.0073	0.065
	FT	0.0092	0.0129	0.016

C. Co-scheduling results with two applications

Now that we have demonstrated the interest of cache partitioning, we study the performance of the scheduling strategies of Section IV. Recall that the COSCHED-CACHEPART optimization problem aims at maximizing the minimum weighted throughput among co-scheduled applications. Considering two applications (A i , A j ), for every β i iterations of A i , we aim at performing β j iterations of A j . To avoid some side effects that appear when the cache area is too small, we set the minimum cache fraction allocated to each application to three (each application has at least 15% of the cache and we slightly modify the dynamic algorithm accordingly), while the minimum number of cores per application is set to one.

We focus again on CG+MG, since this combination turned out to be the most interesting in terms of cache partitioning. On Figure 8 (top), we see what is the minimum throughput achieved by each method for CG+MG. The weight β M G of MG varies from 0.25 to 4. The algorithms based on dynamic programming DP-CP, DP-EQUAL and DP-NOCP outperform both equal-resource assignment heuristics EQ-CP and EQ-NOCP. In this scenario, the cache partitioning provides a good performance improvement, since on average DP-CP outperforms DP-NOCP. On the same figure, we also depict the model prediction, which reports the (analytical) minimum throughput computed from T i (p i , x i ) values with p i and x i derived from the optimal algorithm DP-CP. We observe that the model is accurate enough to satisfactorily fit the performance of DP-CP obtained on the experimental platform. Figure 8 (bottom) presents ∆ f airness , as defined in Equation [START_REF] Leverich | Reconciling high server utilization and sub-millisecond quality-of-service[END_REF]. We observe that DP-CP, DP-NOCP and DP-EQUAL exhibit the same ∆ f airness , near to zero, while EQ-CP and EQ-NOCP are far from the optimal fairness.

For the other combinations (CG+FT and MG+FT, see [START_REF] Aupy | Co-scheduling HPC workloads on cache-partitioned CMP platforms[END_REF]), we observe similar results, where the DP-based algorithms almost systematically outperform EQ-CP and EQ-NOCP. Also, in most cases, the variants using cache partitioning perform better than those without cache partitioning, even though FT benefits less from cache partitioning than when we combine CG with MG. In terms of fairness, the DP-based algorithms are always very close to zero.

We also consider a special case where all applications have the same number of cores (six in our case), so only the cache is available to increase performance, see Figure 9. In this case, DP-CP is the only method that can choose how to partition the cache, and it succeeds to obtain up to 25% improvement when β MG is smaller than 1 (compute more CG than MG). Also, even though ∆ f airness is high for all methods in this setting (since they cannot modify the number of cores), the error of DP-CP is the smallest. We also observe that the model prediction is pretty close to the experimental results.

Summary: Overall, the model is accurate enough to enforce that the corresponding optimal DP algorithm performs well: in most cases, DP-CP, DP-EQUAL and DP-NOCP outperform EQ-CP and EQ-NOCP. On the cache partitioning side, when co-scheduling CG and MG, the cache partitioning