Guillaume Aupy

Anne Benoit

Sicheng Dai

Loïc Pottier

Padma Raghavan

Yves Robert

Manu Shantharam

Co-scheduling Amdahl applications on cache-partitioned systems

Keywords: Co-scheduling, cache partitioning, complexity results

Cache-partitioned architectures allow subsections of the shared last-level cache (LLC) to be exclusively reserved for some applications. This technique dramatically limits interactions between applications that are concurrently executing on a multi-core machine. Consider n applications that execute concurrently, with the objective to minimize the makespan, defined as the maximum completion time of the n applications. Key scheduling questions are: (i) which proportion of cache and (ii) how many processors should be given to each application? In this paper, we provide answers to (i) and (ii) for Amdahl applications. Even though the problem is shown to be NP-complete, we give key elements to determine the subset of applications that should share the LLC (while remaining ones only use their smaller private cache). Building upon these results, we design efficient heuristics for Amdahl applications. Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed.

Ordonnancement concurrent d'applications Amdahl pour systèmes à partitionnement de cache

Résumé : Les architectures à partitionnement de cache permettent d'allouer des portions du dernier niveau de cache (LLC) exclusivement réservées à certaines applications. Cette technique permet de réduire drastiquement les interactions entre applications qui sont exécutées simultanément sur un machine multi-coeurs. Considérons n applications exécutées simultanément avec l'objectif de minimiser le makespan, défini comme le maximum des temps de complétions parmi les n applications. Les problèmes d'ordonnancement sont les suivants: (i) quelle proportion de cache et (ii) combien de processors doivent être alloués à chaque application. Ici, nous assignons des nombres de processeurs rationnels pour chaque application, pour qu'ils puissent être partagés parmi les applications grâce au multi-threading. Dans ce travail, nous fournissons des réponses aux questions (i) et (ii) pour des applications parfaitement parallèles. Malgré cela, le problème est prouvé être NP-complet, et nous donnons des éléments clés pour déterminer le sous-ensemble des applications qui doivent partager le dernier niveau de cache (tandis que les autres utilisent seulement leur petit cache privé). Basé sur ces résultats, nous développons des heuristiques efficaces pour des profils d'applications généraux. Un ensemble complet de simulations démontre l'utilité de l'ordonnancement concurrent quand les techniques de partitionnement de cache sont mises en place.

Mots-clés : Ordonnancement concurrent; partitionnement de cache; résultats de complexité.

Introduction

At scale, the I/O movements of HPC applications are expected to be one of the most critical problems [START_REF]Ten technical approaches to address the challenges of Exascale computing[END_REF]. Observations on the Intrepid machine at Argonne National Laboratory (ANL) show that I/O transfers can be slowed down up to 70% due to congestion [START_REF] Gainaru | Scheduling the I/O of HPC applications under congestion[END_REF]. When ANL upgraded its house supercomputer from Intrepid (Peak perf: 0.56 PFlops; peak I/O throughput: 88 GB/s) to Mira (Peak perf: 10 PFlops; peak I/O throughput: 240 GB/s), the net result for an application whose I/O throughput scales linearly (or worse) with performance was a downgrade from 160 GB/PFlop to 24 GB/PFlop! To cope with such an imbalance (which is not expected to reduce on future platforms), a possible approach is to develop in situ co-scheduling analysis and data preprocessing on dedicated nodes [START_REF]Ten technical approaches to address the challenges of Exascale computing[END_REF]. This scheme applies to data-intensive periodic workflows where data is generated by the main simulation, and parallel processes are run to process this data with the constraints that output results should be sent to disk storage before newly generated data arrives for processing. These solutions are starting to be implemented for HPC applications. Sewell et al. [START_REF] Sewell | Large-scale compute-intensive analysis via a combined in-situ and co-scheduling workflow approach[END_REF] explain that in the case of the HACC application (a cosmological code), petabytes of data are created to be analyzed later. The analysis is done by multiple independent processes. The idea of their work is to minimize the amount of data copied to I/O filesystem, by performing the analysis at the same time as HACC is running (what they call in situ). The main constraint is that these processes are data-intensive and are handled by a dedicated machine. Also, the execution of these processes should be done efficiently enough so that they finish before the next batch of data arrives, hence resulting in a pipelined approach. All these frameworks motivate the design of efficient co-scheduling strategies.

One main issue of co-scheduling is to evaluate co-run degradations due to cache sharing [START_REF] Zhuravlev | Addressing shared resource contention in multicore processors via scheduling[END_REF]. Many studies have shown that interferences on the shared last-level cache (LLC) can be detrimental to co-scheduled applications [START_REF] Leverich | Reconciling high server utilization and sub-millisecond quality-of-service[END_REF]. Previous solutions consisted in preventing co-schedule of possibly interfering workloads, or terminating low importance applications [START_REF] Zhang | Smite: Precise QOS prediction on realsystem SMT processors to improve utilization in warehouse scale computers[END_REF]. Lo et al. [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF] recently showed experimentally that important gains could be reached by co-scheduling applications with strict cache partitioning enabled. Cache partitioning, the technique at the core of this work, consists in reserving exclusivity of subsections of the LLC of a chip multi-processor (CMP), to some of the applications running on this CMP. This functionality was recently introduced by Intel under the name Cache Allocation Technology [START_REF]Intel 64 and IA-32 architectures software developer's manual[END_REF]. With the advent of large shared memory multi-core machines (e.g., Sunway TaihuLight, the current #1 supercomputer uses 256-cores processor chips with a shared memory of 32GB [START_REF] Dongarra | Report on the sunway taihulight system[END_REF]), the design of algorithms that co-schedule applications efficiently and decide how to partition the shared memory (seen as the cache here), is becoming critical.

In this work, we study the following problem: given a set of parallel applications, a multi-core processor with a shared last-level cache LLC, how can we best partition the LLC to minimize the total execution time (or makespan), i.e., the moment when the last application finishes its computation. For each application, we assume that we know the number of compute operations to perform, and the miss rate on a fixed size cache. For the multi-core processor, we know its LLC size, the cost for a cache miss, the cost for a cache hit, the size of the cache and total number of processors. For the theoretical study, we assume that these processors can be shared by two applications through multi-threading [START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF], hence we can assign a rational number of processors to each application, and this allows us to study the intrinsic complexity of co-scheduling with cache partitioning. Equipped with all these applications and platform parameters, recent work [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] shows how to model the impact of cache misses and to accurately predict the execution time of an application. In this context, we make the following main contributions:

• With rational numbers of processors, we show that the co-scheduling problem is NPcomplete, even when applications are perfectly parallel, i.e., their speed-up scales up linearly with the number of processors. • With rational numbers of processors, we show several results that characterize optimal solutions, and in particular that the co-scheduling cache-partitioning problem reduces to deciding which subset of applications will share the LLC; when this subset is known, we show how to determine the optimal cache fractions and rational number of processors for perfectly-parallel applications. Furthermore, we show that all applications should finish at the same time, even if they are not perfectly parallel. • These theoretical results guide the design of heuristics for Amdahl applications. We show through extensive simulations (using both rational and integer numbers of processors) that our heuristics greatly improve the performance of cache-partitioning algorithms, even for parallel applications obeying Amdahl's law with a large sequential fraction, hence with a limited speedup profile. The rest of the paper is organized as follows. Section 2 provides an overview of related work. Section 3 is devoted to formally defining the framework and all model parameters. Section 4 gives our main theoretical contributions. The heuristics are defined in Section 5, and evaluated through simulations in Section 6. Finally, Section 7 outlines our main findings and discusses directions for future work.

Related work

Since the advent of systems with tens of cores, co-scheduling has received considerable attention. Due to lack of space, we refer to [START_REF] Muralidhara | Reducing memory interference in multicore systems via application-aware memory channel partitioning[END_REF][START_REF] Dauwe | A methodology for co-location aware application performance modeling in multicore computing[END_REF][START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF] for a survey of many approaches to co-scheduling. The main idea is to execute several applications concurrently rather than in sequence, with the objective to increase platform throughput. Indeed, some individual applications may well not need all available cores, or some others could use all resources, but at the price of a dramatic performance loss. In particular, the latter case is encountered whenever application speedup becomes too low beyond a given processor count.

The main difficulty of co-scheduling is to decide which applications to execute concurrently, and how many cores to assign to each of them. Indeed, when executing simultaneously, any two applications will compete for shared resources, which will create interferences and decrease their throughput. Modeling application interference is a challenging task. Dynamic schedulers are used when application behavior is unknown [START_REF] Qureshi | Utility-based cache partitioning: A low-overhead, highperformance, runtime mechanism to partition shared caches[END_REF][START_REF] Tian | A study on optimally co-scheduling jobs of different lengths on chip multiprocessors[END_REF]. Static schedulers aim at optimizing the sharing of the resources by relying on application knowledge such as estimated workload, speed-up profile, cache behavior, etc. One widely-used approach is to build an interference graph whose vertices are applications and whose edges represent degradation factors [START_REF] Jiang | Analysis and approximation of optimal coscheduling on chip multiprocessors[END_REF][START_REF] Zhu | Modelling and developing co-scheduling strategies on multicore processors[END_REF][START_REF] He | Developing graph-based co-scheduling algorithms on multicore computers[END_REF]. This approach is interesting but hard to implement. Indeed, the interaction of two applications depends on many factors, such as their size, their core count, the memory bandwidth, etc. Obtaining the speedup profile of a single application already is difficult and requires intensive benchmarking campaigns. Obtaining the degradation profile of two applications is even more difficult and can be achieved only for regular applications. To further darken the picture, the interference graph subsumes only pairwise interactions, while a global picture of the processor and cache requirements for all applications is needed by the scheduler.

Shared resources include cache, memory, I/O channels and network links, but among potential degradation factors, cache accesses are prominent. When several applications share the cache, they are granted a fraction of cache lines as opposed to the whole cache, and their cache miss ratio increases accordingly. Multiple cache partitioning strategies have been proposed [START_REF] Bui | Impact of cache partitioning on multitasking real time embedded systems[END_REF][START_REF] Guan | Cache-aware scheduling and analysis for multicores[END_REF][START_REF] Blagodurov | Contention-aware scheduling on multicore systems[END_REF][START_REF] Dwyer | A Practical Method for Estimating Performance Degradation on Multicore Processors, and Its Application to HPC Workloads[END_REF]. In this paper, we focus on a static allocation of LLC cache fractions, and processor numbers, to Inria concurrent applications as a function of several parameters (cache-miss ratio, access frequency, operation count). To the best of our knowledge, this work is the first analytical model and complexity study for this challenging problem.

Model

This section details platform and application parameters, and formally states the optimization problem.

Architecture. We consider a parallel platform of p homogeneous computing elements, or processors, that share two storage locations:

• A small storage S s with low latency, governed by a LRU replacement policy, also called cache; • A large storage S l with high latency, also called memory. More specifically, C s (resp. C l ) denotes the size of S s (resp. S l ), and l s (resp. l l ) the latency of S s (resp. S l ). In this work, we assume that C l = +∞. We have the relation l s l l . In this work, we consider the cache partitioning technique [START_REF]Intel 64 and IA-32 architectures software developer's manual[END_REF], where one can allocate a portion of the cache to applications so that they can execute without interference from other applications.

Applications. There are n independent parallel applications to be scheduled on the parallel platform, whose speedup profiles obey Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]. For an application T i , we define several parameters:

• w i , the number of computing operations needed for T i ;

• s i , the sequential fraction of T i ;

• f i , the frequency of data accesses of T i : f i is the number of data accesses per computing operation; • a i , the memory footprint of T i . We use these parameters to model the execution of each application as follows.

The power law of cache misses. In chip multi-processors, many authors have observed that the Power Law accurately models how the cache size affects the miss rate [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF]. Mathematically, the power law states that if m 0 is the miss rate of a workload for a baseline cache size C 0 , the miss rate m for a new cache size C can be expressed as m = m 0 C0 C α where α is the sensitivity factor from the Power Law of Cache Misses [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] and typically ranges between 0.3 and 0.7 with an average at 0.5. Note that, by definition, a rate cannot be higher than 1, hence we extend this definition as:

m = min 1, m 0 C 0 C α . (1)
This formula can be read as follows: if the cache size allocated is too small, then the execution goes as if no cache was allocated, and all accesses will be misses.

Computations and data movement. We use the cost model introduced by Krishna et al. [START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] to evaluate the execution cost of an application as a function of the cache fraction that it has been allocated. Specifically, for each application, we define m 0 , the miss rate of application T i with a cache of size C 0 (we can also use the miss rate of applications with a cache of another fixed size). We express the execution time of T i as a function of p i , the number of processors allocated to T i , and x i , the fraction of S s allocated to T i (recall both are rational numbers). Let F l i (p i ) be the number of operations performed by each processor for application T i , given that the application is executed on p i processors. We have F l i (p i ) = s i w i + (1 -s i ) wi pi according to Amdahl's speedup profile. Finally,

Exei(pi, xi) =              F li(pi) (1 + fi (ls + l l )) if xi = 0; F li(pi) 1 + fi ls + l l • min 1, m 0 x i Cs C 0 α if xiCs ≤ ai; F li(pi) 1 + fi ls + l l • min 1, m 0 a i C 0 α otherwise. (2)
Indeed, for each operation, we pay the cost of the computing operation, plus the cost of data accesses, and by definition we have f i accesses per operation. At each access, we pay a latency l s , and an additional latency l l in case of cache miss (see Equation ( 1)). The last case states that we cannot use a portion of cache greater than the memory footprint a i of application T i . This model is somewhat pessimistic: cache accesses to the same variable by two different processors are counted twice. We show in Section 6 that despite this conservative assumption (no sharing), co-scheduling can outperform classical approaches that sequentially deploy each application on the whole set of available resources.

Equation ( 2) calls for a few observations. For notational convenience, let i , or x i = 0: indeed, if we give application T i a fraction of cache smaller than d

d i = m 0 C0 Cs α : • It is
1 α
i , the minimum is equal to 1, and this fraction is wasted. Hence, we have for all i:

x i = 0 or d

1 α i < x i ≤ a i C s . (3)
Of course, if d

1 α
i ≥ ai Cs for some application T i , then x i = 0. We denote by Exe seq i (x i ) = Exe i (1, x i ) the sequential execution time of application T i with a fraction of cache x i .

Scheduling problem.

Given n applications T 1 , . . . , T n , we aim at partitioning the shared cache and assign processors so that the concurrent execution of these applications takes minimal time. In other words, we aim at minimizing the execution time of the longest application, when all applications start their execution at the same time. Formally: Definition 1 (CoSchedCache). Given n applications T 1 , . . . , T n and a platform with p identical processors sharing a cache of size C s , find a schedule {(p 1 , x 1 ), . . . , (p n , x n )} with n i=1 p i ≤ p, and

n i=1 x i ≤ 1, that minimizes max 1≤i≤n Exe i (p i , x i ).
We pay particular attention in the following to perfectly parallel applications, i.e., applications T i with s i = 0. In this case,

Exe i (p i , x i ) = Exei(1,xi) pi = Exe seq i (xi) pi
. The co-scheduling problem for such applications is denoted CoSchedCachePP.

Complexity results

In this section, we focus on the CoSchedCache problem with rational numbers of processors in order to study the intrinsic complexity of co-scheduling with cache partitioning. We first Inria prove that in an optimal execution, all applications must complete at the same time when using rational numbers of processors (Section 4.1). We remind that CoSchedCache is NP-complete, even for perfectly parallel applications (Section 4.2), and we show several dominance results on the optimal solution (Section 4.3). While some of these dominance results only hold for perfectly parallel applications, they will guide the design of heuristics for general applications in Section 5.

All applications complete at the same time

Lemma 1. To minimize the makespan when using rational numbers of processors, all applications must finish at the same time.

Proof. Consider n applications T 1 , . . . , T n that obey Amdahl's law, and a solution S = {(p i , x i )} 1≤i≤n to CoSchedCache. Let D S = max i Exe i (p i , x i ) be the makespan of this solution. For simplicity, we let

A i = 1 + f i l s + l l • min 1, m i 1MBSs xiCs 10 6 α , b i = A i w i s i , c i = A i w i (1 -s i ) Hence, Exe i (p i , x i ) = b i + ci pi .
The set of applications whose execution time is exactly D S is denoted by I S .

We show the result by contradiction. We consider an optimal solution S whose subset I S has minimal size (i.e., for any other optimal solution S o , |I S | ≤ |I So |). Then we show that if |I S | = n, we can construct a solution S with either (i) a smaller makespan if |I S | = 1 (contradicting the optimality hypothesis), or (ii) one less application whose execution time is exactly D S (contradicting the minimality hypothesis).

Assume |I S | = n, let T i0 ∈ I S and T i1 / ∈ I S . We have Exe i1 (p i1 , x i1 ) < Exe i0 (p i0 , x i0 ) = D S , that is

b i1 + c i1 p i1 < b i0 + c i0 p i0 , and hence (b i1 -b i0 )p i0 p i1 -c i0 p i1 + c i1 p i0 < 0. ( 4
)
We now prove that we can always find 0

< ε < p i1 s.t. Exe i0 (p i0 , x i0 ) > Exe i0 (p i0 + ε, x i0 ) > Exe i1 (p i1 -ε, x i1 ), i.e., D S = b i0 + ci 0 pi 0 > b i0 + ci 0 pi 0 +ε > b i1 + ci 1 pi 1 -ε . The left part of inequality b i0 + ci 0 pi 0 > b i0 + ci 0
pi 0 +ε is always true when ε > 0. For the right part of inequality above, we have:

-(b i1 -b i0 )ε 2 + [(p i1 -p i0 )(b i1 -b i0 ) + c i0 + c i1 ]ε + (b i1 -b i0 )p i0 p i1 -c i0 p i1 + c i1 p i0 < 0. (5)
From Equation (4), we know that (b i1 -b i0 )p i0 p i1 -c i0 p i1 + c i1 p i0 < 0, so we can always find a 0 < ε < p i1 that could make Equation (5) satisfied.

Then clearly, S = {(p i , x i )} i where p i is (i

) p i if i / ∈ {i 0 , i 1 }, (ii) p i0 + ε if i = i 0 , (iii) p i1 -ε if i = i 1 ,
is a valid solution: we have the property i p i = i p i ≤ p, and i x i =

i x i ≤ 1. Hence, • If |I S | = 1,
then for all i, Exe i (p i , x i ) < D S , hence showing that S is not optimal; • Else, I S = I S \ {i 0 }, and D S = D S , hence showing that S is not minimal. This shows that necessarily, |I S | = n.

Intractability

We prove that the problem is NP-complete, even for perfectly parallel applications. Therefore, we formally state the decision problem associated to CoSchedCachePP: Definition 2 (CoSchedCachePP-Dec). Given n perfectly parallel applications T 1 , . . . , T n and a platform with p identical processors sharing a cache of size C s , and given a bound K on the makespan, does there exist a schedule {(p 1 , x 1 ), . . . , (p n , x n )}, where p i and x i are nonnegative rational numbers with

n i=1 p i ≤ p and n i=1 x i ≤ 1, such that max 1≤i≤n Exe i (p i , x i ) ≤ K?
The proof of intractability is done thanks to a reformulation of the problem using the following Lemma:

Lemma 2. CoSchedCachePP can be rewritten as finding the optimal cache partitioning strategy X = {x 1 , . . . , x n } that minimizes the completion time of an optimal solution:

1 p n i=1 Exe i (1, x i ). ( 6
)
Theorem 1. CoSchedCachePP-Dec is NP-complete.

Proof. For perfectly parallel applications, we can transform CoSchedCachePP into an equivalent problem that does not depend on the number of processors but that relies simply on the cache partitioning strategy (Lemma 2 below). This result will guide processor assignment for general applications in Section 5. We start with a few lemmas.

The following lemma shows the optimal rational processor assignment:

Lemma 3. Given n perfectly parallel applications T 1 , . . . , T n and a partitioning of the cache {x 1 , . . . , x n }, then the optimal number of processors for application T i (i ∈ {1, . . . , n}) is:

p i = p Exe seq i (x i ) n j=1 Exe seq j (x j )
.

Proof. According to Lemma 1, all applications finish at the same time. Given i 0 ∈ {1, . . . , n}, we have

Exe seq i 0 (xi 0 ) pi 0 = Exe seq i (xi) pi
for all 1 ≤ i ≤ n. In addition, we have n i=1 p i = p: the fact that this bound is tight in an optimal solution is due to the fact that we have perfectly parallel applications. We express p in terms of the others variables, and we do the summation:

p = n i=1 p i = pi 0 Exe seq i 0 (xi 0 ) n i=1 Exe seq i (x i
) . This directly leads to the result.

Lemmas 1 and 3 lead to the following reformulation of CoSchedCachePP:

Proof. Lemma 3 gives us that in an optimal solution the processor distribution is uniquely determined by the cache partitioning strategy. Furthermore, given a cache partitioning strategy, we know that all applications finish at the same time (Lemma 1) and that the completion time is equal to

Exe seq 1 (x 1 ) p 1 = n i=1 Exe seq i (x i ) p .
We are now ready for the proof of Theorem 1. CoSchedCachePP-Dec is obviously in NP: given the x i 's, it is easy to verify all constraints in linear time. We prove the completeness by a reduction from Knapsack, which is NP-complete [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Consider an arbitrary instance I 1 of Knapsack: given n objects, each with positive integer size u i and positive integer value v i for Inria 1 ≤ i ≤ n, and two positive integer bounds U and V , does there exist a subset I ⊂ {1, . . . , n} such that i∈I u i ≤ U and i∈I v i ≥ V ? Given I 1 , we construct the following instance I 2 of CoSchedCachePP-Dec:

• We define two constants ε = 1 N (N +1) and η = 1 -1 N , where N = max(n, 2U + 1). • We let d i = uiη U α , e i = d 1 α i + ε α , a i = e 1 α i C s , and w i f i l l = vi 1- d i e i
for 1 ≤ i ≤ n. Note that we only need the value of the product w i f i , and we can set one of them arbitrarily.

• The bound K is defined as:

pK = n i=1 w i (1 + f i l s ) + n i=1 w i f i l l -V.
To simplify notations, let

z i = w i f i l l . Letting A = n i=1 w i (1 + f i l s ) and Z = n i=1 z i , we get pK = A + Z -V . Also, we have n i=1 w i 1 + f i l s + l l • min 1, di x α i = A + B, where B = n i=1 z i min(1, di x α i
). Recall from Lemma 2 that I 2 has a solution if and only if 1 p (A+B) ≤ K. Let I C ⊆ {1, . . . , n} denote the subset of applications that are given some cache (x i = 0 if and only if i ∈ I C ). We also call I C the nonzero subset of I 2 . We have

d 1 α i ≤ x i ≤ a i C s = e 1 α i , so that we can rewrite B = Z -i∈I C z i 1 -di x α i
. Given the value of the bound K, we have

A + B ≤ pK if and only if i∈I C z i (1 - d i x α i ) ≥ V.
We show that I 1 has a solution if and only if I 2 does. Suppose first that I 1 has a solution subset I ⊂ {1, . . . , n}. Then we let x i = e 1 α i if i ∈ I and x i = 0 otherwise. This is a valid solution to I 2 with nonzero subset I C = I. Indeed:

• If i ∈ I, then d 1 α i ≤ x i = e 1 α i = ai Cs . • We have i∈I x i = i∈I (d 1 α i + ε) = i∈I u i η U + |I|ε.
But i∈I uiη U ≤ η (since we have a solution for I 1 ), and

|I|ε ≤ nε ≤ 1 N +1 , hence i∈I x i ≤ η + 1 N +1 ≤ 1. • Finally, i∈I z i (1 -di x α i ) = i∈I z i (1 -di ei ) = i∈I v i ≥ V (since we have a solution for I 1 ), hence A + B ≤ pK.
Suppose now that I 2 has a solution, and let I C be its nonzero subset. We claim that I = I C is a solution to I 1 . Indeed, for i ∈ I C we have

d i ≤ x α i ≤ e i and i∈I C z i (1 -di x α i ) ≥ V . First, we have i∈I C z i (1 -di x α i ) ≥ i∈I C z i (1 -di ei ) = i∈I C v i , hence i∈I C v i ≥ V . Then i∈I C d 1 α i ≤ i∈I C x i ≤ 1, and i∈I C d 1 α i = i∈I C uiη U , hence i∈I C u i ≤ U η . But U η ≤ U + 1 2 by the choice of η, thus i∈I C u i ≤ U + 1 2 .
Because the sizes are integers, i∈I C u i ≤ U . Altogether, I C is indeed a solution to I 1 . This concludes the proof.

Dominance results for perfectly parallel applications

In this section, we provide dominance results that will guide the design of heuristics. The dominance results are for perfectly parallel applications (s i = 0) but we give intuition on how to extend this work for Amdahl applications in Section 4.4. Finally, we further assume that application memory footprints are larger than the cache size (a i = +∞), and we assume rational numbers of processors.

The core of the previous intractability result relies on the hardness to determine the set of applications that receive a cache fraction (denoted by I C ) and those that do not (denoted by I C ). In this section, we show (i) how to determine the optimal solution when these sets I C and I C are known, and (ii) whether one can disqualify some partitions as being sub-optimal.

In particular, we define a set of partitions of applications that we call dominant (Definition 4). We show that (i) if a partition of applications I C , I C is dominant, then we can compute the minimum execution time for this partition, and (ii) if a partition is not dominant, then we can find a better dominant partition. We start by rewriting the problem when the partitioning I C , I C of applications is known:

Definition 3 (CSCPP-Part I C , I C ).
Given a set of applications T 1 , . . . , T n and a partition I C , I C , the problem CSCPP-Part I C , I C (for CoSchedCachePP-Part) is to find a set X = {x 1 , . . . , x n } that minimizes the execution time: Furthermore, given a solution of CSCPP-Ext I C , I C , one can easily see that its execution time in CoSchedCache will be lower (the objective function is lower since it involves a minimum for all applications in I C ). Lemma 4. Given a set of applications T 1 , . . . , T n and a partition I C , I C , the optimal solution to CSCPP-Ext I C , I C is

1 p   i∈I C w i (1 + f i (l s + l l )) + i∈I C w i (1 + f i l s + f i l l d i x α i )   under the constraints x i = 0 if i ∈ I C , x i > d 1/α i if i ∈ I C ,
x i = (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) if i ∈ I C , x i = 0 otherwise.
Proof. We want to compute X = {x 1 , . . . , x n } that minimizes the execution time. Discarding constant factors, this reduces to minimizing

K(X ) = i∈I C w i f i d i x α i under the constraints: x i = 0 if i ∈ I C , x i ≥ 0 otherwise, and i x i ≤ 1.
Clearly, one can see that this last inequality is an equality when I C = ∅ (otherwise K is not minimum).

Inria

To minimize the function, we compute the partial derivatives of K:

∀i ∈ I C , ∂K(X ) ∂x i = -α w i f i d i x α+1 i .
By setting them all to 0, we obtain the following equality for 1 ≤ i ≤ n:

-α w i f i d i x α+1 i = -α w n f n d n x α+1 n .
Hence,

∀i ∈ I C , x i = x n (w i f i d i ) 1 α+1 (w n f n d n ) 1 α+1 ; n i=1 x i = x n (w n f n d n ) 1 α+1 i∈I C (w i f i d i ) 1 α+1 = 1.
Hence, the desired result.

Definition 4 (Dominant partition). Given a set of applications T 1 , . . . , T n , we say that a partition of these applications

I C , I C is dominant, if for all i ∈ I C , (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) > d 1/α i .
We can now state the following result:

Theorem 2. If a partition I C , I C is not dominant, then we can compute in polynomial time a better solution.

Proof. Let I C , I C be a non-dominant partition.

Let i 0 ∈ I C such that (wi 0 fi 0 di 0 )

1/(α+1) j∈I C (wj fj dj ) 1/(α+1) ≤ d 1/α i0 .
First we can show that there is i 1 ∈ I C \{i 0 }. Indeed, otherwise we would have (wi 0 fi 0 di 0 )

1/(α+1) j∈I C (wj fj dj ) 1/(α+1) = 1 ≤ d 1/α
i0 , and I C , I C is not a valid partition: then CSCPP-Part I C , I C does not admit any solution.

Let T e (resp. T p ) be the optimal execution time of CSCPP-Ext I C , I C (resp. CSCPP-Part I C , I C ). We know that T e ≤ T p . Let us further denote by X = {x 1 , . . . , x n } the optimal solution to CSCPP-Ext I C , I C . Let X = {x 1 , . . . , xn } be such that (i) xi0 = 0, (ii) xi1 = x i0 + x i1 , and (iii) xi = x i for all other i's.

Then clearly X is a solution, and we have:

Exe seq i0 (x i0 ) ≤ w i0 1 + f i0 l s + f i0 l l d i0 x α i0 ; Exe seq i1 (x i1 ) < w i1 1 + f i1 l s + f i1 l l d i0 x α i1 ; ( 7
)
Exe seq i (x i ) ≤ w i 1 + f i l s + f i l l d i x α i if i ∈ I C ; Exe seq i (x i ) = w i (1 + f i (l s + l l )) if i ∈ I C .
Indeed, these results are direct consequences of the definition of Exe seq , except Equation ( 7), which we establish as follows:

• If x i1 ≥ d 1/α i1 , then xi1 > d 1/α i1 Exe seq i1 (x i1 ) = w i1 1 + f i1 l s + f i1 l l d i0 xα i1 < w i1 1 + f i1 l s + f i1 l l d i0 x α i1 . • If x i1 < d 1/α i1 , then for all x ∈ [0, 1], Exe seq i1 (x) < w i1 1 + f i1 l s + f i1 l l di 0 x α i 1
.

Hence:

1 p n i=1 Exe seq i (x i ) < 1 p i∈I C w i (1 + f i (l s + l l )) + i∈I C w i (1 + f i l s + f i l l d i x α i ) = T e ≤ T p ,
which shows that X is a better solution computed in polynomial time from X . Furthermore, by construction of X , we have strictly decreased the size of the new set I C .

We can show a second dominance result characterizing the optimal solution:

Theorem 3. If a partition I C , I C is dominant, then the optimal solution to CSCPP-Part I C , I C is:

x i = (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) if i ∈ I C ; x i = 0 otherwise.
Proof. This is a corollary of Lemma 4. Indeed, this solution is the optimal solution to CSCPP-Ext I C , I C and it is a valid solution to CSCPP-Part I C , I C , hence it is the optimal solution to CSCPP-Part I C , I C .

Extension of the dominance criterion for Amdahl applications

Finally, we provide extended definitions for non-perfectly parallel applications, by defining the dominant partition of both the parallel part and the sequential part of such applications.

Definition 5 (Dominant partition of parallel part). Given a set of applications T 1 , . . . , T n , we say that a partition of these applications I C , I C is dominant for the parallel part if for all i ∈ I C ,

(w i f i d i (1 -s i )) 1/(α+1) j∈I C (w j f j d j (1 -s j )) 1/(α+1) > d 1/α i .
Definition 6 (Dominant partition of sequential part). Given a set of applications T 1 , . . . , T n , we say that a partition of these applications I C , I C is dominant for the sequential part if for all i ∈ I C ,

(w i f i d i s i ) 1/(α+1) j∈I C (w j f j d j s j ) 1/(α+1) > d 1/α i .

Inria

The intuition behind these two definitions is the following: recall from Lemma 1 that the execution time is defined as Exe i (p i , x i ) = b i + ci pi , with

A i = 1 + f i l s + l l • min 1, m i 1MBSs xiCs 10 6 α , b i = A i w i s i , c i = A i w i (1 -s i ).
We can observe that s i , the sequential fraction, is key to decide which parts b i or ci pi we should favor to minimize Exe i (p i , x i ). If s i << 1 pi , then ci pi dominates the execution time, i.e., Exe i (p i , x i ) ≈ c i . Hence the application could be seen as a perfectly parallel application where the new number of computing operations to do is wi = w i (1 -s i ). Then Definition 5 is just a consequence of applying the definition of Dominant Partition to this new application. Symmetrically, if s i is large in front of one over the number of processors assigned to an application, then b i dominates the execution time. Intuitively in this case, the number of processors by application is less important (and we will have a fair balance of processors). Hence, we want to favor applications with large values of s i w i f i d i .

We verify these intuitions experimentally in Section 6.

Heuristics

In this section, we aim at designing efficient heuristics for general applications that obey Amdahl's law, and whose memory footprints are larger than the cache size (a i = +∞). However, the CoSchedCache problem seems to be very difficult for such applications, as seen in Section 4.

We first explain how heuristics work, in particular to assign (rational numbers of) processors, in Section 5.1. The core of the heuristic consists in building a dominant partition, and we detail different possibilities to do so in Section 5.2. Finally, we propose a way to round the number of processors in case we need an integer number of processors, for instance if no multi-threading is allowed (see Section 5.3).

Structure of heuristics

We simplify the design of the heuristics by temporarily allocating processors as if the applications were perfectly parallel, and then concentrating on strategies that partition the cache efficiently among some applications (and give no cache fraction to remaining ones). In accordance with Theorem 2, our goal is to compute dominant partitions. Recall that I C represents the subset of applications that receive a fraction of the cache. Once a dominant partition is given, we obtain the schedule S = {(x i , p i )} i as follows: first we determine the x i 's with Theorem 3, and then we recompute the p i 's so that all applications complete simultaneously at time K. Indeed, while Lemma 3 does not hold for Amdahl applications, we still know thanks to Lemma 1 that all applications should complete simultaneously.

However, there is no longer a nice analytical characterization of the makespan K, hence we use a binary search to compute K as follows: for each application T i , the execution time writes (s i + 1-si pi )c i = K, where s i is the sequential fraction, and and we compute K through a binary search. A lower (resp. upper) bound for K is to assign p (resp. 1) processor(s) to each application.

c i = w i (1 + f i (l s + l l di x α i )) if T i ∈ I C , or c i = w i (1 + f i (l s + l l )) otherwise. From n i=1 p i = p, we derive the equation n i=1 1 -s i K ci -s i = p RR n°9021

Computing a dominant partition

To compute dominant partitions, we use two greedy strategies:

• Dom: we start with I C = I and greedily remove some applications from I C until we have a dominant partition (see Algorithm 1); NotDom(i, I C ) returns true if i does not satisfy the definition of dominant partition for I C ;

• DRev: initially I C is empty, and we greedily add applications while I C remains dominant (see Algorithm 2); IsDom(I C ) returns true if I C is a dominant partition. Both strategies come in three flavors, depending on the dominance definition that we use. From Definition 4, we get that NotDom(i, I C ) is true if and only if (wifidi) 1/(α+1)

d 1/α i ≤ j∈I C (w j f j d j ) 1/(α+1) ,
and IsDom(I C ) is true if and only if ∀i ∈ I C , (wifidi) 1/(α+1) For each of these strategies, the greedy criterion to select the next application is the choice function taken from the following three alternatives:

d 1/α i > j∈I C (w j f j d j ) 1
• Random: choice(I) picks up randomly one application among all applications;

• MinRatio considers the ratio that appears in Definition 4, 6 or 5 (dominant partitions), and chooses an application with a small ratio; for Dom and DRev, we have:

choice(I) = arg min i∈I (w i f i d i ) 1/(α+1) d 1/α i ;
and we replace w i by w i s i in DomS and DRevS, or by w i (1 -s i ) in DomP and DRevP;

Inria

• MaxRatio proceeds the other way round, by choosing an application with a large ratio, simply replacing the arg min by an arg max. The intuition behind these heuristics is the following: applications that make the solution non dominant for Dom and DRev are such that (see Definition 4):

(

w i f i d i ) 1/(α+1) d 1/α i ≤ j∈I C (w j f j d j ) 1/(α+1) .
Hence, we expect to reach dominance faster by removing from a non-dominant solution applications with low (wifidi) 1/(α+1) Altogether, by combining six strategies, and with three different choice functions for each strategy, we obtain 18 heuristics to build dominant partitions. We denote by Dom-MinRatio the Dom strategy using MinRatio as a choice function, and we use a similar notation for all heuristics.

Integer processor assignment

Based on the rational cache allocation, we want to give an integer processor allocation in order to tackle architectures that do not allow to share processors between applications through multithreading. The choice functions above are first used to build a dominant partition, then we assign cache based on that partition to obtain the x i 's. In Algorithm 3, the set I contains all applications and x is the set that contains all x i 's. Finally, p is the total number of processors and n the total number of applications (i.e., n = |I|). After the cache is assigned, we initialize processor assignment by giving one processor to each application, and the remaining processors are assigned in a greedy way: assign one processor to the application currently with longest execution time, until all processors are assigned. It should be noted that integer processor assignment will only work when p ≥ n, since each application needs at least one processor. App Description CG Uses conjugate gradients method to solve a large sparse symmetric positive definite system of linear equations BT Solves multiple, independent systems of block tridiagonal equations with a predefined block size LU Solves regular sparse upper and lower triangular systems SP Solves multiple, independent systems of scalar pentadiagonal equations MG Performs a multi-grid solve on a sequence of meshes FT Performs discrete 3D fast Fourier Transform

Simulations

To assess the efficiency of the heuristics defined in Section 5, we have performed extensive simulations. The simulation settings are discussed in Section 6.1, and results are presented in Section 6.2 (comparison of the 18 heuristics of Section 5), Section 6.3 (assessing the gain due to co-scheduling), and Section 6.4 (with integer numbers of processors). The code is publicly available at http://perso.ens-lyon.fr/loic.pottier/archives/cache-int.zip.

Simulation settings

We use data from applicative benchmarks to run the experiments. Table 1 provides a brief description of the NAS Parallel Benchmark (NPB) suite [START_REF] Bailey | The NAS Parallel Benchmarks -Summary and Preliminary Results[END_REF], and Table 2 shows the parameters for these six HPC applications. We obtain the values shown in Table 2 by instrumenting and simulating the benchmarks (CLASS=A) on 16 cores using PEBIL [START_REF] Laurenzano | PEBIL: Efficient static binary instrumentation for Linux[END_REF]. For the simulations, we use a cache configuration representing an Intel Xeon CPU E5-2690, with a 40MB last level cache per processor of 8 cores. Since the cache miss ratio is defined for a 40MB cache, we have

d i = m i 40MBSs 40×10 6 Cs α .
To build a set of n applications, we pick randomly n times one application among the six applications defined by Table 2, the number of application wanted. In additions, for each of these n applications, the work w i is randomly taken between 1E+8 and 1E+12. Other data Inria sets building upon these applications have been used (see Appendix A), and the results are very similar. The sequential fraction of work s i is taken randomly between 1% and 15%.

For the execution platform, we consider one manycore Sunway TaihuLight [START_REF] Dongarra | Report on the sunway taihulight system[END_REF] with 256 processors and a shared memory of 32GB. We chose this platform because of its high core count. Strictly speaking, this platform does not have a last level cache (LLC), but the shared memory can be seen as the LLC, using the disk as the large memory. We have C s = 32 × 10 9 . The large storage latency l l is set to 1. The small storage latency l s is set to 0.17. According to the literature [START_REF] Kultursay | Evaluating STT-RAM as an energy-efficient main memory alternative[END_REF][START_REF] Molka | Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP Architecture[END_REF][START_REF] Pena | Toward the efficient use of multiple explicitly managed memory subsystems[END_REF], the last level cache (LLC) latency is on average four to ten times better than the DDR latency, and we enforce a ratio of 5.88 in the simulations. We have used different ratios in Appendix A, and they lead to similar results. Finally, the Power Law parameter is set to α = 0.5. We execute each heuristic 50 times and we compute the average makespan, i.e., the longest execution time among all co-scheduled applications. Figure 2 shows the normalized makespan obtained by all of the heuristics building dominant partitions. We set the number of processors to 256. Results are normalized with the makespan of AllProcCache, which is the execution without any co-scheduling: in the AllProcCache heuristic, applications are executed sequentially, each using all processors and all the cache. We vary the number of applications between 1 and 256. The eighteen heuristics obtain similarly good results, with a gain of 85% over AllProcCache as soon as there are at least 50 applications.

Comparison of the heuristics

Since all eighteen variants show the same performance on the previous data sets, we investigate the impact of the cache miss rate by varying it between 0 and 1 with a LLC of C s = 1GB in Figure 3. Results are now normalized with DomS-MinRatio in both figures, which enables to zoom out the differences.

The first noticeable result from Figure 3 is that for all versions of the strategies that build dominant strategies, MinRatio performs better with strategies that remove applications from the I C (Dom, DomS, DomP), whereas MaxRatio works better with strategies that add applications to the I C (DRev, DRevS, DRevP). This confirms the mathematical intuition presented in Section 5. Furthermore, we confirm the mathematical intuition on the influence of the Amdahl factor (s i ) presented in Section 4.4:

• We observe that in Figure 3a, when the sequential fraction is not negligible (s i chosen uniformly at random between 0.01 and 0.15), DomS-MinRatio and DRevS-MaxRatio are always the best (their plots overlap), with a gain from 10 to 15% with respect to the random-based heuristics when the cache miss rate is greater than 0.5. • On the contrary, when it is negligible (s i chosen uniformly at random between 0.001 and 0.01), then the DomP-MinRatio and DRevP-MaxRatio versions perform better.

Note that overall, the observable differences between heuristics is mainly when the cache miss ratio is large. According to current data, m 40MBSs ranges from 1E-02 to 1E-04 (see Table 2). In addition, these differences are visible only with a small shared memory (1GB in the example), while our execution platform has a 32GB shared memory. Overall, for the system used in these simulations, all heuristics perform similarly, even though DomS-MinRatio and DRevS-MaxRatio seem to perform best in all other settings that we tried (see Appendix A).

In the following simulations, the sequential fraction will always, unless otherwise mentioned, be taken between 1% and 15%. Therefore, for clarity, we plot only one heuristic based on dominant partitions in the remaining simulations, namely DomS-MinRatio.

Gain with co-scheduling

In this section, we assess the gain due to co-scheduling by comparing DomS-MinRatio with AllProcCache and with three other heuristics:

• Fair gives p i = p n processors, and a fraction of cache x i = fi n j=1 fj to each application; • 0cache gives no cache to any application, i.e., x i = 0 for 1 ≤ i ≤ n, and then it computes the p i 's so that all applications finish at the same time; • RandomPart randomly partitions applications with and without cache. For those in cache, the x i 's are computed with the method used for dominant partitions. Then, the p i 's are computed so that all applications finish at the same time.

Impact of the number of applications. Figure 4 (normalized with AllProcCache on the left) shows the impact of the number of applications when the number of processors is set to 256. We see that DomS-MinRatio outperforms the other heuristics, hence showing the efficiency of our approach based on dominant partitions. Results are also normalized with DomS-MinRatio (on the right), so that we can better observe the differences between co-scheduling heuristics.

Fair exhibits good results only for a small number of applications, when all applications can fit into cache. Otherwise, the use of dominant partitions is much more efficient, as seen with RandomPart, or even 0cache that does not use cache but ensures that all applications finish at the same time. These results show the accuracy of the model and the benefits of using dominant partitions. Also, we note the importance of cache partitioning, since the difference between 0cache and DomS-MinRatio relies on cache allocation.

Impact of the number of processors.

Figure 5 (normalized with AllProcCache on the left) shows the impact of the number of processors when the number of applications is set to 16. When the number of processors increases, the gain of co-scheduling increases. In both figures, DomS-MinRatio and outperforms other methods. RandomPart, which builds a random partition instead of a dominant one, is outperformed by DomS-MinRatio, and the latter is the only heuristic that surpasses AllProcCache when the number of processors is low. So, building a dominant partition seems a good strategy to optimize the makespan.

The normalization with DomS-MinRatio (on the right) shows that when the number of processors increases, Fair becomes better, while RandomPart and 0cache are quite stable since they are based on the same model as DomS-MinRatio. The only difference between 0cache and DomS-MinRatio is the cache allocation strategy, and the gain from cleverly distributing cache fractions across applications exceeds 20%. With more applications, we obtain the same ranking of heuristics, except that Fair is always the worst heuristic: since there are less processors on average per application, a good co-scheduling policy is necessary (seeAppendix A for detailed results).

Impact of the sequential fraction of work. Figure 6 (normalized with AllProcCache) shows the impact of the sequential part s i when the number of processors is set to 256. The number of applications is set to 16. As expected, when the sequential fraction of work increases, all co-scheduling heuristics perform better than AllProcCache, and DomS-MinRatio is always the best heuristic. It leads to a gain of more than 50% when s i = 0.01. The normalization with DomS-MinRatio better shows the impact of the sequential part: we observe that when the sequential fraction of work increases, Fair obtains results closer to DomS-MinRatio.

Processor and cache repartition.

Figure 7 shows the processor repartition and cache repartition when we vary the number of applications from 1 to 256 with 256 processors. We use an error bar plot where the error interval represents here the maximum and minimum number of processors (or cache fraction) allocated to an application. As expected, we observe that the range between minimum and maximum decreases when the number of applications increases. The processor allocation of Fair is not interesting, the maximum is always equal to the minimum because we allocate the same number of processors to each application.

Since all dominant partition heuristics give the same results, we only use DomS-MinRatio. The repartition of processors for 0cache is interesting: it turns out to be very close to the repartition obtained with DomS-MinRatio, even though it is not using cache.

Summary.

To summarize, all heuristics based on dominant partitions are very efficient, especially when compared to the classical heuristics Fair (which shares the cache fairly between applications) and AllProcCache (which does no co-scheduling). The unexpected result that can be observed is that the gain brought by our heuristics comes even with very low sequential time (below 0.01)! This is unexpected since the natural intuition would be a behavior such as the one observed on Fair: a makespan up to 1.9 times longer than AllProcCache with low sequential time.

We show that the ratio processors/applications has a significant impact on performance: when many processors are available for a few applications, it is less crucial to use efficient cache-partitioning and all applications can share the cache, hence Fair obtains good results, close to DomS-MinRatio. Otherwise, RandomPart is the second best heuristic. A surprising information that also confirms the strength of our partition based heuristics is that natural heuristics such as Fair and AllProcCache perform worse than 0cache our implementation with no usage of cache.

All heuristics run within a very small time (less than ten seconds in the worst of the settings used, to be compared with a typical application execution time in hours or days), hence they can be used in practice with a very light overhead.

With an integer number of processors

In this section, we study the impact of rounding the number of processors to an integer number on heuristics. We focus again mainly on DomS-MinRatio, and we add the suffix Int to heuristic names to denote the fact that we use Algorithm 3 to compute an integer processor allocation.

Impact of the number of applications. In this simulation, we vary the number of applications from 1 to 256 on 256 processors. Figure 8 is normalized with AllProcCache (on the left), and heuristics obtain a similar relative performance as in Section 6.3, with a gain of 90% over AllProcCache as soon as there are at least 50 applications. The right side of Figure 8 shows the performance of the same heuristics but normalized with DomS-MinRatioInt. As expected, 0cacheInt is the worst, and RandomPartInt performs always in the middle between 0cacheInt and FairInt. As we use the same algorithm to round the rational processor allocation, the differences in performance mostly rely on cache allocation.

The fact that FairInt and DomS-MinRatioInt give similar results show that the cache allocation of DomS-MinRatioInt must not be far from the fair distribution of FairInt. However, contrarily to Fair, processors are not equally shared between applications but distributed according to their needs, hence the much better performance of FairInt compared to Fair.

Simulations showing the impact of the number of processors and of the sequential fraction of work give similar results, with FairInt and DomS-MinRatioInt overlapping and beating other heuristics. We refer to Appendix A for details.

Impact of the sequential fraction and the cache miss rate. As DomS-MinRatioInt and FairInt show the same performance, we study the impact of the sequential fraction and the cache miss rate, as we did in Section 6.2, in Figure 9. The number of applications is set to 16 and the number of processors to 256 with a LLC of C s = 1GB. The results are normalized with DomS-MinRatioInt. In the left figure, we compare all dominant partition heuristics by varying the sequential fraction when the cache miss rate is set to 0.8 in order to see differences between heuristics. We note that the dominant partition heuristics favoring the sequential part outperform the others, especially the ones favoring the parallel part. Dom-MinRatioInt and DRev-MaxRatioInt overlap with DomS-MinRatioInt. All variants using Random criterion perform on average around 1.10. As expected, giving more cache to applications with bigger sequential fractions is better. In the right figure, we vary the cache miss rate between 0 and 1 This figure is interesting due to the difference of performance between DomS-MinRatioInt and FairInt. Clearly, the difference of performance between heuristics when we use integer processors rely on cache allocation. When the cache miss ratio increases, the performance of DomS-MinRatioInt becomes better. When the cache miss rate is larger than 0.01, DomS-MinRatioInt outperforms all other heuristics, and we obtain an average gain of 10% on FairInt. The performance of 0cacheInt becomes better when the cache miss rate increases.

Summary.

To summarize, when we use integer processors, all heuristics based on dominant partitions are still very efficient, but those that favor either the sequential part or none of them perform better. The main difference between results with rational and integer processor assignments is that DomS-MinRatioInt and FairInt overlap if the cache miss rate is low (less than 1%), because of the better processor assignment for FairInt. We show that the cache miss rate has a significant impact on performance: when many cache misses occur, it is more crucial to use efficient cache-partitioning and all applications can share the cache, hence DomS-MinRatioInt outperforms FairInt when the cache miss rate is larger than 10%. As expected, DomS-MinRatioInt performs better when the cache miss rate increases. Otherwise, RandomPartInt is the third best heuristic, followed by 0cacheInt that does not use the cache.

Conclusion

In this paper, we have provided a preliminary study on co-scheduling algorithms for cachepartitioned systems, building upon a theoretical study. The two key scheduling questions are (i) which proportion of cache and (ii) how many processors should be given to each application. For rational numbers of processors, we proved that the problem is NP-complete, but we have been able to characterize optimal solutions for perfectly parallel applications by introducing the concept of dominant partitions: for such applications, we have computed the optimal proportion of cache to give to each application in the partition. Furthermore, we have provided explicit formulas to express the number of processors to assign to each application. Several polynomial-time heuristics focusing on Amdahl's applications have been built upon these results, both for rational and integer numbers of processors. Extensive simulation results demonstrate that the use of dominant partitions always leads to better results than more naive approaches, as soon as there is a small sequential fraction of work in application speedup profiles.

Inria

The concept of sharing the cache only between a subset of applications seems highly relevant, since even an approach with a random selection of applications that share the cache leads to good results. Also, a clever partitioning of the cache pays off quite well, since our heuristics lead to a significant gain compared to an approach where no cache is given to applications. Overall, the heuristics appear to be very useful for general applications, even though their cache allocation strategy rely mainly on simulating a perfectly parallel profile.

Future work will be devoted to gain access to, and conduct real experiments on, a cachepartitioned system with a high core count: this would allow us to further validate the accuracy of the model and to confirm the impact of our promising results. On the theoretical side, we plan to focus on the problem with integer numbers of processors and we hope to derive interesting results that could help design even more efficient heuristics.

A Additional simulation results

We consider three sets of data for simulations:

• NPB-6: Limited to the six applications defined in Table 2;

• NPB-SYNTH: We build synthetic applications from Table 2 with only varying randomly the work w i between 1E+8 and 1E+12 (used in the core of the paper); • RANDOM: We build synthetic applications from Table 2 with varying all values randomly.

The work w i is taken between 1E+8 and 1E+12, f i between 1E-01 and 9E-01, and m i 40MBSs between 1E-02 and 9E-04.

A.1 Impact of the number of applications

Figure 10 (normalized with AllProcCache and DomS-MinRatio) shows the impact of the number of applications when the number of processors is set to 256. We observe similar results with RANDOM and NPB-SYNTH. Dominant partition heuristics still outperform other heuristics. As in Section 6, results are also normalized with DomS-MinRatio, so that we can better observe the differences between co-scheduling heuristics. Results are quite similar to the results obtained with NPB-SYNTH. A.2 Impact of the number of processors Figure 11 (normalized with DomS-MinRatio) shows the impact of the number of processors with 64 applications. Compared to Figure 5, the main difference is that Fair now obtains the worst performance, even 0cache is better. This difference in performance for Fair is due to a higher number of applications. As each application receive a fraction of cache and a fraction of processors, each of them obtains less resources when the number of applications increases. Figure 12 (normalized with AllProcCache and DomS-MinRatio) shows the impact of the number of processors with NPB-6. The number of applications is set to 6. We observe with less applications that Fair obtains better results than 0cache when the number of processors is bigger than 50.

Figure 13 (normalized with AllProcCache and DomS-MinRatio) shows the impact of the number of processors with RANDOM. The number of applications is set to 16. We obtain similar results with RANDOM and NPB-SYNTH.

Figure 14 (normalized with AllProcCache and DomS-MinRatio) shows the impact of the number of processors with RANDOM and 64 applications. As expected, we obtain similar results, 0cache and RandomPart show better performance when the number of applications A.3 Impact of the sequential fraction of work A.4 Impact of the cache latency

A.5 Processor and cache repartition

Figure 18 shows the processor repartition and cache repartition when we vary the number of applications from 1 to 256 with 256 processors. The results with RANDOM are very similar to the results obtained with NPB-SYNTH. However, note that cache allocation with Fair is more heterogeneous when we have random application profiles.

A.6 Impact of the cache miss rate

Figure 19 (normalized with DomS-MinRatio) shows the impact of the cache miss rate with NPB-SYNTH and 16 applications. We vary the cache miss rate m i 40MBSs between 0 and 1. When the cache miss rate increases, the performance of RandomPart and 0cache increases. Indeed, when the rate of miss increases, using the cache is less important, so 0cache becomes competitive. But, we have to keep in mind that, with real applications, the cache miss rate rarely exceeds 20%.

A.7 With an integer number of processors

Impact of the number of applications. In this simulation, we vary the number of applications from 1 to 256 on 256 processors using the set of applications RANDOM. with AllProcCache (on the left), and heuristics obtain a similar relative performance as in Inria Section 6.3, with a gain of 90% over AllProcCache as soon as there are at least 50 applications. The right side of Figure 8 shows the performance of the same heuristics but normalized with DomS-MinRatioInt.

Impact of the number of processors. Figure 21 shows the impact of the number of processors when the number of application is set to 16 and the number of processor very between 16 and 256. The left figure is normalized with AllProcCache and the right figure is normalized with DomS-MinRatioInt. As for previous results, all heuristics outperform AllProcCache, the performance of heuristic methods does not get better with the growth of processor number when the processor number get bigger than 24. However, all heuristics obtain a gain of 60% on average. The right figure helps us to zoom on details, DomS-MinRatioInt and FairInt are overlapping.

All heuristics get better with the increasing of the processor number, and perform almost as good as DomS-MinRatioInt and FairInt when the number of processors reach 100. From Figure 8, we can find out that average number of processors per application is one of the most critical parameter to obtain good performance. Figure 22 shows the impact of the number of processors when the number of application is set to 16 and the number of processor very between 16 and 256. But for this figure, we use the set of applications RANDOM. We observe similar results to the previous figure using NPB-SYNTH. Finally, Figure 23 shows the impact of the number of processors when the number of applications is set to 6 and the number of processors vary between 6 and 256. For this figure, we use the set of applications NPB-6. The results are not as good as with other sets of applications due the lower number of applications involved.

Impact of the sequential fraction of work. Figure 24 shows the performance obtained when the sequential fraction of work vary. The number of applications is set to 16 and the number of processors is set to 256. The left figure is normalized with AllProcCache and the right one is normalized with DomS-MinRatioInt. We can see from both figures that DomS-MinRatioInt and FairInt overlap, and both of them outperform other heuristic methods. Figure 25 shows the performance obtained with the same parameters but with the RANDOM set of applications. We note the same results and behavior with this set of applications. Finally, Figure 26 shows the performance obtained with the same parameters but with the NPB-6 set of applications, so with 6 applications and not 16 as before.

  and 1≤i≤n x i ≤ 1. We now relax some bounds in CSCPP-Part I C , I C and define CSCPP-Ext I C , I C , which is the same problem except that the constraints on the x i 's when i ∈ I C is relaxed: we have instead x i ≥ 0 if i ∈ I C . A solution of CSCPP-Part I C , I C is a solution of CSCPP-Ext I C , I C , because we simply removed the constraints x i > d 1/α i in the latter problem. Hence the execution time of the optimal solution of CSCPP-Ext I C , I C is lower than that of CSCPP-Part I C , I C .

Algorithm 1 : 2 IC ← I; 3 while 4 k 5 IC ← IC \ {k}; 6 if 7 end 8 ICAlgorithm 2 : 3 k 4 I C ← {k}; 5 while 6 IC ← I C ; 7 IC ← IC \ {k}; 8 if 9 k 10 IFigure 1 :

 1234567823456789101 Figure 1: Two strategies to build dominant partitions.

  /(α+1) (strategies Dom and DRev). If we use Definition 6, we simply replace all w k 's by w k s k (strategies DomS and DRevS focusing on the sequential part), while with Definition 5, we replace all w k 's by w k (1 -s k ) (strategies DomP and DRevP focusing on the parallel part).

  of the equation). Intuitively, Dom, DomS and DomP should work well with the MinRatio criterion. For symmetric reasons, we expect DRev, DRevS and DRevP to work well with the MaxRatio criterion. These intuitions will be experimentally confirmed in Section 6.

Algorithm 3 : 5 while premain > 0 do 6 i 7 p i = p i + 1 ; 8 premain = premain - 1

 3567181 Integer processor assignment 1 procedure IntegerProcessor (x, p, I) 2 begin 3 for i ∈ I do p i = 1; 4 premain = p -n; = arg max k∈I (Exe k (p k , x k ));

Figure 2 :

 2 Figure 2: Comparison of all dominant partition heuristics on 256 processors.

  s i randomly set between 0.01 and 0.15. s i randomly set between 0.001 and 0.01.

Figure 3 :

 3 Figure 3: Impact of the cache miss ratio m i 40MBSs with a 1GB cache and 16 applications.

Inria

Figure 4 :Figure 5 :

 45 Figure 4: Impact of the number of applications.

Figure 6 :

 6 Figure 6: Impact of sequential fraction of work.

Figure 7 :

 7 Figure 7: Processor and repartition with 256 processors.

Inria

Figure 8 :

 8 Figure 8: Impact of the number of applications.

Figure 9 :

 9 Figure 9: Impact of the sequential fraction and the cache miss rate.

Figure 10 :

 10 Figure 10: Impact of the number of applications with RANDOM.

Inria

Figure 11 :Figure 12 :Figure 13 :Figure 14 :

 11121314 Figure 11: Impact of the number of processors with NPB-SYNTH and 64 applications.

Figure 15 (Figure 15 :

 1515 Figure[START_REF] Jiang | Analysis and approximation of optimal coscheduling on chip multiprocessors[END_REF] (normalized with AllProcCache and DomS-MinRatio) shows the impact of the sequential fraction of work with NPB-6 and 6 applications. As in Section 6, results are also normalized with DomS-MinRatio, in order to show the differences between heuristics. We observe that the performance of Fair increases when the sequential fraction of work increases. Indeed, more the sequential fraction of work is important, more the cache allocation becomes crucial.

Figure 16 (Figure 16 :

 1616 Figure[START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] (normalized with AllProcCache and DomS-MinRatio) shows the impact of the sequential fraction of work with RANDOM and 16 applications. We observe similar results to the previous one obtained with NPB-SYNTH.

Figure 18 :Figure 19 :

 1819 Figure 18: Processor and cache repartition with 256 processors with RANDOM.

Figure 20 Figure 20 :

 2020 Figure 20: Impact of the number of applications with RANDOM.

Figure 21 :

 21 Figure 21: Impact of the number of processors with NPB-SYNTH.

Figure 22 :

 22 Figure 22: Impact of the number of processors with RANDOM.

Figure 23 :

 23 Figure 23: Impact of the number of processors with NPB-6.

Figure 24 :Figure 25 :Figure 26 :

 242526 Figure 24: Impact of sequential fraction.

  useless to give a fraction of cache larger than ai Cs to application T i ; • Because of the minimum min 1, di (xi) α , either x i > d

	1
	α

Table 1 :

 1 Description of the NPB benchmarks.

	App	w i	f i	m i 40MBSs
	CG 5.70E+10 5.35E-01 6.59E-04
	BT 2.10E+11 8.29E-01 7.31E-03
	LU 1.52E+11 7.50E-01 1.51E-03
	SP 1.38E+11 7.62E-01 1.51E-02
	MG 1.23E+10 5.40E-01 2.62E-02
	FT 1.65E+10 5.82E-01 1.78E-02

Table 2 :

 2 Experimental values from NPB benchmarks.

  Figure17(normalized with AllProcCache) shows the impact of the cache latency l s with NPB-SYNTH and 16 applications (on the left) on 256 processors. The sequential fraction of work is set to s i = 0.0001 for all i. We observe that the l s cost does not have an impact on relative performance. The right side of Figure17(normalized with AllProcCache) shows the impact of the cache latency l s with NPB-SYNTH and 64 applications on 256 processors. The sequential fraction of work is set to s i = 0.0001 for all i. As on the previous figure, we see that the l s cost does not have an impact on relative performance, even with 64 applications. Impact of latency l s with NPB-SYNTH with 16 and 64 applications.

				ALLPROCCACHE	RANDOMPART	OCACHE					ALLPROCCACHE	RANDOMPART	OCACHE
				DOMS-MINRATIO	FAIR							DOMS-MINRATIO	FAIR
		2.0										2.0
		1.8										1.8
	Normalized Makespan	1.2 1.4 1.6									Normalized Makespan	1.2 1.4 1.6
		1.0										1.0
		0.1 0.8	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0	0.1 0.8	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0
						ls value										ls value
			Figure 17:

RR n°9021

Acknowledgments

This research was possible thanks to an Inria grant and funding from Vanderbilt university.


Mohamed Essghair Chaibi
email: chaibi@enssat.fr

Laurent Bramerie

Sébastien Lobo

Christophe Peucheret

Mitigation of Mode Partition Noise in Quantum-Dash Fabry-Perot Mode-Locked Lasers using Manchester Encoding

The use of Manchester encoding with balanced detection is proposed in order to overcome the mode partition noise (MPN) limit of quantum-dash mode-locked lasers used as multi wavelength sources. Successful MPN mitigation is demonstrated for a 10-mode laser at 10 Gbit/s.

Introduction

Multi-wavelength sources are highly attractive in the context of short-reach access and datacentre networks since they enable the generation of an entire comb of wavelength division multiplexed (WDM) channels with equal frequency spacing in a single device. Such sources could advantageously replace full arrays of single-mode lasers in a cost effective way and would moreover reduce operational cost by removing the need for line-by-line frequency control.

Quantum-dot or quantum-dash (QD) modelocked lasers (MLLs) [START_REF] Lelarge | Recent advances on InAs/InP quantum dash based semiconductor lasers and optical amplifiers operating at 1.55 m[END_REF][START_REF] Vujicic | Quantum dash mode-locked lasers for data centre applications[END_REF] are highly compact and have been successfully used as multiwavelength sources in a number of transmission experiments [START_REF] Ben M'sallem | Quantum-dash mode-locked laser as a source for 56 Gb/s DQPSK modulation in WDM multicast applications[END_REF][START_REF] Pfeifle | Coherent terabit communications using a quantum-dash mode-locked laser and self-homodyne detection[END_REF] . They furthermore have the potential to be heterogeneously integrated on the silicon platform through wafer bonding techniques in order to implement fully integrated WDM transmitters. One well-known limitation of such sources, however, is the increase of the relative intensity noise (RIN) of the filtered comb lines due to the effect of mode partition noise (MPN). A powerful MPN mitigation technique consists in amplifying the filtered lines with a saturated semiconductor optical amplifier (SOA) in order to filter the low frequency part of the RIN spectrum that is enhanced due to the effect of MPN [START_REF] Sato | Reduction of mode partition noise by using semiconductor optical amplifiers[END_REF][START_REF] Gay | Single quantum dash mode-locked laser as a comb-generator in four-channel 112 Gbit/s WDM transmission[END_REF] . However, this technique can only be applied on the individual filtered comb lines after they have been demultiplexed and before modulation is applied. It is therefore not compatible with serial modulator architectures that have been recently proposed [START_REF] Chen | A comb laser-driven DWDM silicon photonic transmitter based on microring modulators[END_REF][START_REF] Xu | Cascaded silicon micro-ring modulators for WDM optical interconnection[END_REF] , and whose main benefit is not to require demultiplexing of the comb lines at the transmitter in order to perform modulation.

In this paper, we demonstrate how this issue can be circumvented by employing Manchester encoding in conjunction with balanced detection. The sensitivity to MPN of a 10-channel QD-MLL source is shown to be significantly reduced in a 10-Gbit/s experiment, resulting in improved receiver sensitivity or the suppression of MPNinduced bit-error-ratio floors down to 10 -9 .

Principle of the technique

A transmitter architecture relying on a QD-MLL laser followed by a serial array of micro-ring resonator (MRR) modulators [START_REF] Chen | A comb laser-driven DWDM silicon photonic transmitter based on microring modulators[END_REF][START_REF] Xu | Cascaded silicon micro-ring modulators for WDM optical interconnection[END_REF] is schematically represented in Fig. 1. Such a structure has the potential of being heterogeneously integrated on the silicon platform. The resonance of each MRR is tuned so that it only modifies the intensity of a single line of the frequency comb generated in the QD-MLL upon detuning due to the application of a modulating signal. The main benefit of this architecture is that the modulation operation does not require wavelength demultiplexing and re-multiplexing. However, since the individual lines are not accessible prior to modulation, the use of a saturated SOA for RIN mitigation cannot be applied with this scheme. New MPN mitigation techniques therefore need to be found. The use of balanced detection is known to be able to reduce the impact of RIN in analogue links [START_REF] Joshi | Balanced photoreceivers for analog and digital fiber optic communications[END_REF] . However, such a detection scheme is not compatible with the simple non-return-to-zero (NRZ) intensity modulation format to be applied in cost-effective short reach digital systems. On the other hand, Manchester line coding, in which the binary data is encoded in low-to-high or high-to-low transitions within the bit slot is fully compatible with intensity modulation and balanced direct detection [START_REF] Yamada | Tolerance for optical coherent crosstalk of a novel Manchester-code receiver[END_REF] . It also reduces the overlap between the modulation spectral content and the low-frequency region in which the RIN is enhanced due to MPN, albeit at the expense of a doubled modulation bandwidth. In the

Experimental set-up

The experimental set-up is represented in Fig. 2. A QD-MLL [START_REF] Gay | Single quantum dash mode-locked laser as a comb-generator in four-channel 112 Gbit/s WDM transmission[END_REF] biased with a current of 150 mA, generates the frequency comb with 100 GHz channel spacing shown in Fig. 3(a). In the following, the ten consecutive comb lines presenting the highest signal-to-noise ratios will be exploited as a WDM source. The impact of MPN is illustrated in Fig. 3(b), where the RIN spectra measured following direct detection of all the laser modes, as well after individual detection of a single mode after bandpass filtering (worst case mode 8 & good case mode 9) are represented. The RIN is also compared to that of a reference single-mode external cavity laser (ECL) used later in the experiment. It is clear that filtering the modes results in a significant increase of the RIN, especially in the low-frequency part of the spectrum. The frequency comb is first amplified by an erbium-doped fibre amplifier (EDFA). The comb lines are then individually filtered one at a time by an optical bandpass filter (OBPF) before being intensity-modulated at 10 Gbit/s in a Mach-Zehnder modulator (MZM) using either the NRZ or Manchester line code. The signal is finally detected in a preamplified receiver before bit-error-ratio (BER) measurement. For NRZ coding, a standard 10-Gbit/s receiver is used, while a balanced detection scheme 10 making use of a pair of 30-GHz photodiodes followed by a clock and data recovery (CDR) module and a D-flip-flop is employed in the Manchester case.

A pseudo-random binary sequence (PRBS) length of 2 31 -1 is employed throughout this work.

Results and discussion

The eye diagrams of the NRZ signal obtained when an ECL is substituted to the QD-MLL source as well as of a filtered comb line (mode 8) are shown in Fig. 4(a) and (b) respectively. The impact of MPN is clearly visible in the latter case. The corresponding eye diagrams obtained with Manchester coding are also represented in Fig. 4(c) and (d). Note that both NRZ and Manchester eye diagrams are monitored with the same single photodiode. The BER curves obtained for the filtered modes as well as for the reference ECL are represented in Fig. 5(a) and (b) for NRZ and Manchester coding, respectively. A large dispersion of the BER performance can be observed in the NRZ case, with the occurrence of floors for BER values as high as 10 -4 for the worst-case mode (#8). In contrast, the BER performance is significantly improved for all modes when Manchester coding is employed and the worst case BER floor now appears below 10 -9 . The improved overall sensitivity in the case of Manchester coding, as can be seen from the ECL reference case, stems from the use of balanced detection.

In order to clarify the origin of the performance improvement, the measured BERs of Manchester line coding are compared in Fig. 6 for both balanced (BD) and single-ended detection (SD; in a 30-GHz photodiode) to that of NRZ line coding in the ECL reference case as well as for the filtered mode #8. The benefit of balanced detection is clearly visible in the reference case since it provides a 3.2 dB better sensitivity (at a BER of 10 -9 ) for Manchester compared to NRZ, while Manchester encoding suffers from a 3.3 dB power penalty in the single-ended detection case. In the presence of MPN (filtered mode 8), the introduction of Manchester encoding with single-ended detection is not sufficient to provide enhanced performance compared to NRZ. It therefore appears that the use of balanced detection is responsible for the performance improvement of Manchester with respect to NRZ.

An expected benefit of Manchester coding would be the fact that its spectral content is shifted away from the low frequency region, where the RIN is particularly enhanced by MPN, as shown in the measured radio-frequency (RF) spectra in Fig. 7. This spectral shift has already been exploited, for instance in the context of orthogonal modulation labelling [START_REF] Zhang | Performance of Manchester-coded payload in an optical FSK labeling scheme[END_REF] , as well as for mitigation of Rayleigh noise in bidirectional links [START_REF] Liu | Rayleigh noise mitigated 70-km-reach bidirectional WDM-PON with 10-Gb/s directly modulated Manchester-duobinary as downstream signal[END_REF] . It is speculated that this frequency shift could also contribute to the performance enhancement provided by the use of Manchester encoding, even though this is not visible in our demonstration due to the relatively high level of RIN of the filtered comb lines in the high-frequency region. A higher RIN power would thus be integrated in the receiver bandwidth in the high-frequency region in the case of Manchester than for NRZ, due to the higher bandwidth requirement of the former coding scheme.

Conclusions

The use of Manchester encoding in conjunction with balanced detection has been shown to be an effective method to overcome the MPNinduced limitation in serially modulated WDM sources making use of QD-MLLs. A clear performance improvement was experimentally demonstrated at 10 Gbit/s in a 10-channel source, leading to BER enhancement and the reduction of BER floors to sub-10 -9 levels.

Fig. 1 :

 1 Fig. 1: Serial multi-wavelength transmitter based on a QD-MLL and micro-ring modulators.

Fig. 2 :

 2 Fig. 2: Experimental set-up.

Fig. 3 :

 3 Fig. 3: (a) QD-MLL optical spectrum for a bias current of 150 mA. (b) Measured RIN for the joint detection of all QD-MLL modes, after filtering of modes 8 or 9, and for the reference case of an external cavity laser.

Fig. 4 :

 4 Fig. 4: Eye diagrams of the NRZ signal obtained from (a) a reference ECL or (b) the filtered QD-MLL. (c) and (d): corresponding eye diagrams with Manchester coding.

Fig. 5 :

 5 Fig. 5: BER curves for (a) NRZ and (b) Manchester coding.

Fig. 6 :

 6 Fig. 6: Comparison of the BER performance for singleended and balanced detection Manchester coding, as well as NRZ coding in the reference ECL case and for a filtered QD-MLL mode.

Fig. 7 :

 7 Fig. 7: Comparison of the measured RF spectra of NRZ and Manchester line codes at 10 Gbit/s.

Acknowledgements

This work was supported by the European Commission's 7 th Framework Programme through the SEQUOIA project (grant agreement no. 619626). LPN and III-V Lab. are acknowledged for providing the QD-MLL developed in the framework of the TELDOT project supported by the French National Research Agency (ANR 2009-VERS-12).