S A S Cortus

Michael Chapman
email: michael.chapman@cortus.com

Erven Rohou
email: erven.rohou@inria.fr

Rue De Freyr

D5.1 -Technical description of the holistic design flow in CONTINUUM Project Partner Contact Information

Introduction

The holistic design flow targeted by our project is motivated by the following considerations:

• the need for a co-design approach between both compiler and architecture designers, and technology experts. This should bring all the actors to tightly cooperate towards the seamless definition of the target compute node architecture, which able to answer the energy-efficiency challenge;

• beyond the choice of suitable CPU cores, the careful selection of suitable technologies could significantly contribute to reducing the expected system power consumption without compromising the performance. In particular, we explored emerging non-volatile memory technologies as the key solution;

• as a consequence, the need for revisiting existing compilation and runtime management techniques to adapt them to the specific features of the designed compute node, e.g., core and memory heterogeneity, which calls for some adaptive management of workloads and data.

According to the above considerations, we, therefore, study a system design "continuum" that seamlessly goes from software level to memory technology level via hardware architecture. Figure 1 depicts the different aspects involved in the considered design flow. NVM technology integration implications, we respectively discuss the effort achieved by the project to optimize the energy consumption through innovative compilation and workload management techniques (Section 2); then, we briefly describe the final compute node architecture prototype designed with the Cortus core technology (Section 3). Finally, some concluding remarks are given (Section 4). We first describe some studies that have been done in the project up to now in order to suitably leverage NVM-based memory hierarchy. Then, we discuss our efforts for contributing to efficient workload management.

Portable NVM-oriented analysis and optimizations

We explore some compile-time analyses and optimization and software analysis, as a possible alternative to leverage the low leakage current inherent to emerging NVM technologies [START_REF] Chen | A review of emerging non-volatile memory (nvm) technologies and applications[END_REF] for energyefficiency. A major advantage is a flexibility and portability across various hardware architectures enabled by such an approach, compared to the hardware-oriented techniques found in the literature. Our proposal is inspired by some existing techniques such as the silent store elimination technique introduced by Lepak et al. [START_REF] Lepak | Silent stores for free[END_REF] and worst-case execution time analysis techniques [START_REF] Wilhelm | The worst-case execution-time problem—overview of methods and survey of tools[END_REF]. Our main contributions are summarized below.

Silent store elimination: profiling-based versus static analysis approaches. In [START_REF] Bouziane | How could compile-time program analysis help leveraging emerging nvm features?[END_REF][START_REF] Bouziane | LLVM-based silent stores optimization to reduce energy consumption on STT-RAM cache memory[END_REF][START_REF] Bouziane | Compile-time silent-store elimination for energy efficiency: an analytic evaluation for non-volatile cache memory[END_REF], we proposed a silent store elimination technique through an implementation in the LLVM compiler [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transf[END_REF]. Thanks to this implementation, a program is optimized once and run on any execution platform while avoiding silent stores. This is not the case of the hardware-level implementation. We evaluated the profitability of this silent store elimination for NVM cache memories. Silent stores have been initially proposed and studied by Lepak et al. [START_REF] Lepak | Silent stores and store value locality[END_REF]. They suggested new techniques for aligning cache coherence protocols and micro-architectural store handling techniques to exploit the value locality of stores. Their studies showed that eliminating silent stores helps to improve monoprocessor speedup and reduce multiprocessor data bus traffic.

Methods devoted to removing silent stores are meant to improve the system performance by reducing the number of write-backs. Bell et al. [START_REF] Bell | Characterization of silent stores[END_REF] affirmed that frequently occurring stores are highly likely to be silent. They introduced the notion of critical silent stores and show that all of the avoidable cache write-back can be removed by removing a subset of silent stores that are critical.

In our proposal, the silent store elimination technique is leveraged at compiler-level. This favors portability and requires no change to the hardware. We remind that this technique is not dedicated only to STT-RAM but to all NVMs. Here, STT-RAM is considered due to its advanced maturity and performance compared to other NVM technologies. Our approach concretely consists in modifying the code by inserting silentness verification before stores that are identified as likely silent. As illustrated in Figure 2, the verification includes the following instructions:

1. a load instruction at the address of the store; 2. a comparison instruction, to compare the to-be-written value with the already stored value; 3. a conditional branch instruction to skip the store if needed. We showed that energy gains highly depend on the silentness percentage in programs, and on the energy consumption ratio of read/write operations costs for NVMs. We validated our proposal with the Rodinia benchmark suite while reporting up to 42% gain in energy for some applications. This validation relies on an analytic evaluation considering typical NVM parameters extracted from the literature.

The above silent store analysis was carried out based on program profiling, a complementary study leveraging static code analysis is proposed [START_REF] Pereira | Static prediction of silent stores[END_REF]. It aims at predicting the presence of silent stores prediction by analyzing the syntactic properties of programs, through a set of 127 features organized into eight categories. To validate the approach, we collected a number of benchmarks from well-known suites, such as SPEC CPU2006, MiBench, mediabench, BitBench, CoyoteBench, Trimaran, etc. In total, we reused 34 different collections, which gave us 222 programs to analyze.

Out of the 127 features, 100 have been observed in our benchmarks. Figure 3 shows them, together with the probability of silentness associated with their occurrence. Features in each category refer to different parts of the store instruction " : p[i] = v", and are described as follows:

• VALUETYPE. The type of variable v: Vfp: 32-bit floating point; Vdb: 64-bit floating point;

Vin: integers (with different bitwidths); Vpt: pointer.

• VALUESIZE. The size of the type, in bits: sz0: size is unknown v; sz1: one bit; sz8: two to eight bits; s16: nine to 16 bits; s32: 16 to 32 bits; szN: more than 32 bits.

• VALUEDEPS. The operands (instructions, addresses and constants) that contribute to forming the value of v.

• VALUEORIGIN The last instruction or operation that produced the value v. within more than three loop nests. Scm: post-dominates the entry point of the function. Thus, if this function is invoked, the store happens compulsorily. Scl: is compulsory within the loop where it is located. Spl: exists within a compulsory loop, i.e., the loop's entry point post-dominates the function's entry point. Slx: is within a single-exit loop, i.e., after the loop runs, the program always reaches the same point. Ssl: is within a single-latch loop. A latch is a block inside the loop that leaves it. Sdl: dominates the single latch in the loop. Smp: in a basic block with multiple predecessors. Sms: in a basic block with multiple successors. Svi: reached only by invariant definitions of v. Spi: reached only by invariant definitions of p.

• POINTERSTRIDE. The offset i that is added to p when building the store address, e.g., p + i. We use LLVM's scalar evolution to recover this information. Erc: i is created by some recursive expression, e.g.: i = i + 1; Eaf: i is created by some affine expression, e.g., i = 2 * b + c; Es1: i has a stride of size 1; Es4: i has a stride of size 4; Es8: stride of size 8; EsN: regular stride, but its value is unknown; Esp: stride has the same size as the region pointed by p; Etp: i exists in a loop of known trip-count.

Partial WCET analysis for efficient NVM mapping. On the other hand, we proposed another type of program analysis, which aims at exploiting the variable NVM data retention capacities. This opens the opportunity to explore different energy/performance trade-offs, depending on the energyefficiency requirements of a system. We introduced a variant of worst-case execution time analysis [START_REF] Wilhelm | The worst-case execution-time problem-overview of methods and survey of tools[END_REF], to determine the partial worst-case lifetimes of the variables of a program, referred to as δ-WCET [START_REF] Bouziane | Energy-efficient memory mappings based on partial WCET analysis and multi-retention time STT-RAM[END_REF]. Based on this knowledge, the variables can be safely allocated to NVM memory banks accommodating their requirements in terms of data retention duration.

Our methodology is a two-step process, illustrated in Figure 4. First, we identify the def-use chains in the program. In other words, for each store instruction, we determine all the loads that can read the value previously written. Second, we compute the worst-case execution time between the store and all subsequent loads (step referred to as "δ-WCET"). For this purpose, we have developed a method to compute partial WCET estimates (see details in our previous work [START_REF] Bouziane | Partial Worst-Case Execution Time Analysis[END_REF]). We computed the dynamic energy gain, as illustrated in Figure 5 for the Malardalen benchmark-suite, w.r.t. 4 MB and 32 KB STT-RAM memory setups respectively. Here, the reported gain is computed against a baseline setup consisting of an STT-RAM memory with a retention time of 4.27 years. The results show that we achieved with the small memory configuration up to 80 % of energy gain compared to the baseline (small memory with 4.27 years retention time) [START_REF] Bouziane | Energy-efficient memory mappings based on partial WCET analysis and multi-retention time STT-RAM[END_REF].

Figure 5: Energy savings evaluation

Exploring advanced cache replacement policies for last-level cache in NVM. We evaluated the impact of cache replacement policies in the reduction of cache memory write [START_REF] Péneau | Improving the performance of STT-MRAM LLC through enhanced cache replacement policy[END_REF] in presence of STT-RAM. We observed that state-of-the-art Hawkeye cache replacement policy can be beneficial for larger last level caches [START_REF] Jain | Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement[END_REF][START_REF] Péneau | Performance and energy assessment of last-level cache replacement policies[END_REF]. Our evaluations showed that the global system performance can be improved up to 14% for a multicore platform. This gain, combined with the drastic static energy reduction enabled by STT-RAM in place of usual SRAM, enhances the energy-efficiency by up to 27.7%.

For example, Figure 6 illustrates the effect of the Hawkeye policy over LRU, based on the study presented in [START_REF] Péneau | Improving the performance of STT-MRAM LLC through enhanced cache replacement policy[END_REF]. In the configuration names, the prefixes M ("Medium"), B ("Big") and H ("Huge") respectively correspond to 2MB, 4MB and 8MB last level cache sizes. The considered architecture consists of an Intel Core i7 system, with a 3-level on chip cache hierarchy plus a main memory. We used the SPEC CPU2006 benchmark set. The reported results are normalized for each memory technology configuration combined with the Hawkeye policy, compared to its LRU counterpart. Typically, H_stt_hawk is normalized to H_stt_lru. For this experiment, we run the SRAM configuration that do not fit into area constraint to illustrate the effect of Hawkeye on SRAM and STT-MRAM for the same cache size. Both SRAM and STT-MRAM configurations follow the same trend regarding the MPKI 1 (Miss Per Kilo Instructions) reduction over LRU since the Hawkeye policy is not impacted by 1 MPKI is a common metric used to assess LLC performance. It is defined as the total number of cache misses divided by the total number of executed instructions. One possibility to reduce the MPKI is to increase the cache size. The cache Page 8

Version 2.0 (2019) Confidentiality: Public Distribution cache latency. Moreover, we use a single core platform where parallel events cannot occur. Hence, eviction decision remains identical for a given cache size, regardless of the cache size. However, the average gain obtained with Hawkeye is slightly better with STT-MRAM. The performance gap between SRAM and STT-MRAM is 3.3% and 3.1%, respectively with LRU and Hawkeye. Hence, reducing the amount of write-fill has higher impact on STT-MRAM where writes are penalizing. Figure 6 shows that the 8MB configuration is not as efficient as the 4MB configuration in terms of performance improvement. The average gain for the Instruction Per Cycle (IPC) for H_sram_hawk and H_stt_hawk is lower than B_sram_hawk and B_stt_hawk. This suggests an issue that can be due to either a larger LLC, or the Hawkeye policy, or both. On the other hand, we observe that Hawkeye increases the MPKI compared to LRU for a 8MB LLC. This is explained by some wrong eviction decisions made by Hawkeye. Indeed, the Hawkeye predictor exploits all cache accesses to identify the instructions that generate cache misses. Since a large cache size reduces the number of cache misses, it becomes hard for the predictor to learn accurately from a small set of miss events. Note that the performance for H_stt_hawk is still better than other configurations despite these inaccurate decisions.

It is important to notice that the above evaluation was conducted with the ChampSim simulator [START_REF]The ChampSim simulator[END_REF] used for the Cache Replacement Championship at ISCA'17 conference. Despite the notable efforts made recently for accelerating and making systematic gem5-based simulation [START_REF] Butko | A trace-driven approach for fast and accurate simulation of manycore architectures[END_REF][START_REF] Nocua | Elasticsimmate: A fast and accurate gem5 trace-driven simulator for multicore systems[END_REF][START_REF] Nocua | A gem5 trace-driven simulator for fast architecture exploration of openmp workloads[END_REF][START_REF] Senni | Embedded systems to high performance computing using STT-MRAM[END_REF][START_REF] Delobelle | System-level Evaluation of Manycore Systems with Emerging Memory Technologies[END_REF][START_REF] Delobelle | Flot automatique d'évaluation pour l'exploration d'architectures à base de mémoires non volatiles[END_REF], we decided to use ChampSim which is more abstract and faster yet relevant-enough for our experiments.

Workload management

We addressed the workload management issue on multicore heterogeneous architectures, by investigating a few techniques. State-of-the-art approaches solve this problem dynamically, e.g., at runtime / operating system levels, or via a middleware [START_REF] Margiolas | Portable and transparent software managed scheduling on accelerators for fair resource sharing[END_REF][START_REF] Nishtala | Hipster: Hybrid task manager for latency-critical cloud workloads[END_REF], or statically, e.g., via compilers [START_REF] Mendonça | DawnCC: Automatic annotation for data parallelism and offloading[END_REF][START_REF] Nugteren | Bones: An automatic skeleton-based C-to-CUDA compiler for GPUs[END_REF].

Compiler-assisted Adaptive Program Scheduling. In a proposed approach [START_REF] Novaes | Poster: Compiler-assisted adaptive program scheduling in big.little systems[END_REF], we used the compiler to partition source code into program phases: regions whose syntactic characteristics lead to contains more data and reduces the probability for a cache miss to occur. This results in penalties in terms of cache latency, energy and area.

Version 2.0 (2019) Confidentiality: Public Distribution similar runtime behavior. Reinforcement learning is used to map hardware configurations that best fit program regions. To validate our proposal, we implemented the Astro framework to instrument and execute applications in heterogeneous architectures. The framework collects syntactic characteristics from programs and instruments them using LLVM [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transf[END_REF]. For a program region, the scheduler can take into account its corresponding characteristics collected statically, for immediate action. An action consists in choosing an execution configuration and collecting the "reward" related to that choice. Such feedback is then used to fine-tune and improve the subsequent scheduling decisions. We rely on reinforcement learning technique to explore a vast universe of configurations (or states), formed by different hardware setups and runtime data changing over time. However, the universe of runtime states is unbounded, and program behavior is hard to predict without looking into its source code. To speed up convergence, we resort to a compiler, which gives us two benefits: i) mining program features to train the learning algorithm, and ii) instrumenting programs to provide feedback to the scheduler on the code region currently under execution.

The heart of the Astro system is the Actuation Algorithm outlined in Figure 7. Actuation consists of phase monitoring, learning and adapting. These three steps happens at regular intervals, called check points, which, in Figure 7, we denote by i and i+1. The rest of this section describes these events. Monitoring step.

(H i-1 , S i-1 , D i-1 , H i , r i ) backprop. (H i , D i , S i ) (A 1 , R 1 ) ... (A n , R n ) H' = best(A x , R x ) 1 x n H i+1 = chg(H', H i ) Next Config H' feedforward i i+1 i > 0 M O N I T O R L E A R N A D A P T OS (H i , p i ) PowMon e i
To collect information that will be later used, a monitor in Astro reads four kinds of data. • From the Program (Log): the current program phase S.

• From the device's performance counters (PerfMon): the current hardware phase D.

• From the power monitor (PowMon [START_REF] Walker | Accurate and stable run-time power modeling for mobile and embedded cpus[END_REF]): the energy e consumed since the last checkpoint.

The monitor collects this data at periodic intervals, whose granularity is configurable. It was 500 milliseconds in our setup. The recording of the program phase is aperiodic, following from instrumentation inserted in the program by the compiler. Information is logged at the entry point of functions, and around library calls that might cause the program to enter a dormant state. The hardware configuration is updated whenever it changes. The metrics e and p let us define the notion of reward as follows:

Definition 1 (Reward). The reward is the set of observable events that determine how well the learning algorithm is adapting to the environment. The reward is computed from a pair (e, p), formed by the Energy Consumption Level e, measured in Joules per second (Watt), and the CPU Performance Level p, measured in the number of instructions executed per second.

The metric used in the reward is given by a weighted form of performance per watt, namely M IP S γ /W att, where γ is a design parameter that gives a boosting performance effect in the system. This is usually a trade-off between performance and energy consumption. To optimize for energy, we let γ = 1.0. A value of γ = 2.0 emphasizes performance gains: the reward function optimizes (in fact, maximizes the inverse of) the energy delay product per instruction, given by W att/IP S 2 ; letting IP S = I/S we have (W att × S × S)/I 2 = (Energy × Delay)/I 2 . This aims to minimize both the energy and the amount of time required to execute thread instructions [START_REF] Brooks | Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors[END_REF].

Learning step.

The learning phase uses the Q-learning algorithm. As illustrated in Figure 7, a key component in this process is a multi-layer Neural Network (NN) that receives inputs collected by the Monitor. The NN outputs the actions and their respective rewards to the Actuator so that a new system adaptation can be carried out. Following the common methodology, learning happens in two phases: back-propagation and feed-forwarding. During back-propagation, we update the NN using the experience data given by the Actuator (Figure 7). Experience data is a triple: the current state, the action performed and the reward thus obtained. The state consists of a hardware configuration (H i-1 ), static features (S i-1 ) and dynamic features (D i-1 ) at check points i-1.

The action performed at check point i-1 makes the system move from hardware configuration H i-1 to H i . The reward is given by r i , received after the action is taken. The NN consists of a number of layers including computational nodes, i.e., neurons. The input layer uses one neuron to characterize each triple (state, action, reward). The output layer has one neuron per action/configuration available in the system. During the feed-forward phase, we perform predictions using the trained NN. Each node of the NN is responsible to accumulate the product of its associated weights and inputs. Given as input a state (H i , D i , S i ) at checkpoint i, the result of the feed-forward step is an array of pairs A × R, where A is an action, and R is its reward, Version 2.0 (2019) Confidentiality: Public Distribution estimated by NN. Actions determine configuration changes; rewards determine the expected performance gain, in terms of energy and time, that we expect to obtain with the change. We use the method of gradient descent to minimize a loss function given by the difference between the reward predicted by the NN, and the actual value found via hardware performance counters.

Adaptation step. At this phase, Astro takes an action. Together with states and rewards, actions are one of the three core notions in Q-learning, which we define below:

Definition 2 (Action). Action is the act of choosing the next hardware configuration H to be adopted at a given checkpoint.

An action may change the current hardware configuration; hence, adapting the program according to the knowledge inferred by the Neural Network. Following Figure 7, we start this step by choosing, among the pairs {(A 1 , R 1 ), . . . , (A n , R n )}, the action A x associated with the maximal reward R x . A x determines, uniquely, a hardware configuration H . Once H is chosen, we proceed to adopt it. However, the adoption of a configuration is contingent on said configuration being available. Cores might not be available because they are running higher privilege jobs, for instance. If the Next Configuration is accessible, Astro enables it; otherwise, the whole system remains in the configuration H i active at check point i. Such choice is represented, in Figure 7, by the function H i+1 = chg(H , H i ). Regardless of this outcome, we move on to the next check point, and to a new actuation round.

Machine learning-based performance model building. In [START_REF] Gamatié | Empirical model-based performance prediction for application mapping on multicore architectures[END_REF], we kept investigating the definition of performance and energy consumption prediction models. Following the promising insights obtained from ar earlier work [START_REF] Gamatié | Performance prediction of application mapping in manycore systems with artificial neural networks[END_REF], we generalized our study to more machine learning techniques. We mainly focused on supervised machine learning techniques: Support Vector Machines (SVM) [START_REF] Hearst | Support vector machines[END_REF], Adaptive Boosting (AdaBoost) [START_REF] Schapire | Explaining AdaBoost[END_REF] and Artificial Neural Networks (ANNs) [START_REF] Hopfield | Artificial neural networks[END_REF]. We considered a dataset consisting of mapping scenarios evaluated with the McSim simulator [START_REF] Latif | Design space exploration for complex automotive applications: an engine control system case study[END_REF][START_REF] Latif | An Integrated Framework for Model-Based Design and Analysis of Automotive Multi-Core Systems[END_REF]. Our evaluation showed that providing some limited training efforts, AdaBoost and ANNs can provide very good predictions, estimated around 84.8% and 89.05% correct prediction scores. This opens an interesting perspective for considering such models in the runtime mapping and scheduling decisions for heterogeneous architectures. We devised a novel original asymmetric multicore architecture comprising two execution islands: parallel and sequential [START_REF] Gamatié | Towards energy-efficient heterogeneous multicore architectures for edge computing[END_REF]. While the former is devoted to highly parallelizable workloads for high throughput, the latter addresses weakly parallelizable workloads. Accordingly, the parallel island is composed of many low power cores and the sequential island is composed of a small number of highperformance cores. Our proposal integrates the cost-effective and inherently low power core technology provided by Cortus [START_REF]Cortus SAS -Advanced Processing Solutions[END_REF], one of the world-leading semiconductor IP companies in the embedded domain. These cores are highly energy (MIPS/µW) and silicon efficient (MIPS/mm 2 ) compared to existing technologies. We believe the massive usage of such embedded cores deserves attention to achieve the energy-efficient architectures required for high-performance embedded computing.

Another trade-off considered in our solution is the support of floating point arithmetic, which benefits certain operations in embedded applications, e.g., matrix inversion required for Multiple Input / Multiple Output (MIMO), Fast Fourier Transforms (FFTs) which often suffer from scaling problems in fixed point. As floating point units (FPUs) can be expensive in terms of area and power in the very low power cores being considered, it will be supported only by a subset of these cores. A prototype comprising 7 CPU cores has been devised (see Figure 8). One high performance CPU Core is implemented with Cortus APSX2 core IP. It is combined with two clusters that mix smaller CPU cores integrating hardware floating point support or not. Each core has a local cache. The relevance of such a heterogeneous multicore architecture has been recently illustrated [START_REF] Novo | Evaluation of heterogeneous multicore cluster architectures designed for mobile computing[END_REF][START_REF] Butko | Exploration of performance and energy trade-offs for heterogeneous multicore architectures[END_REF]

Conclusions

This deliverable presented a brief description of the techniques defined in the framework of the holistic design flow proposed by the CONTINUUM project. This covers: energy consumption optimization through innovative compilation approaches and cache memory system design, taking into account the integration of non-volatile memory technologies; a workload management technique enabling performance and energy improvements in heterogeneous multicore systems; and finally, the compute node architecture prototype designed with the Cortus core technology.

Figure 1 :

 1 Figure 1: Holistic design flow of CONTINUUM project

2

  Software level: workload analysis and runtime optimization

Figure 2 :

 2 Figure 2: Silent store elimination: (a) original code stores val at address of x; (b) transformed code first loads the value at address of x and compares it with the value to be written, if equal, the branch instruction skips the store execution; (c) when the instruction set supports predication, the branch can be avoided and the store made conditional.

Figure 4 :

 4 Figure 4: Sketch of our framework (input: C code).

Figure 6 :

 6 Figure 6: Performance impact of Hawkeye normalized to LRU

  reward(e i , p i )

Figure 7 :

 7 Figure 7: The actuation algorithm [31].

Figure 7 •

 7 From the Operating System (OS): current hardware configuration H and instructions p executed since last check point.

3

  Hardware level: a multicore asymmetric architecture

Figure 8 :

 8 Figure 8: Sketch of the implemented heptacore system.

  block caches all the memory access to the external DDR memory, reducing the memory access latency. As a proof-of-concept, a multi-thread execution model is defined for program execution. The workload management exploits the nature of programs, which is analyzable statically during compilation, e.g., computation versus memory intensiveness, floating-point intensive or not.

4

 4

Table of Contents

 of Portable NVM-oriented analysis and optimizations . . . . . . . . . . . . . . . . . . 4 2.2 Workload management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

	Introduction	2
	Software level: workload analysis and runtime optimization	4
	2.1 Hardware level: a multicore asymmetric architecture	13
	Conclusions	15
	References	17
	Version 2.0
	(2019)
	Confidentiality: Public Distribution

  Probabilities of silentness distributed per features[START_REF] Pereira | Static prediction of silent stores[END_REF]. Total shows number of instructions that present each feature. The other columns show thresholds of silentness. Darker cells indicate a higher proportion of silent stores. For instance, 48% of stores with the feature Ozr were silent 80% or more of the time.

	• POINTERTYPE. The type of p: Pfp: 32-bit floating point; Pdb: 64-bit floating point; Pin: integer; Pst: C-like struct; Pay: array; Ppt: another pointer; Pvc: SIMD vector. • POINTERLOC. The location of the region pointed by p: Msc: static memory; Msk: stack; Mhp: heap; Mar: unknown location loaded from function argument; Mfn: unknown location returned P1.0 P0.8 P0.6 P0.4 P0.2 Total Feat 1 0.8 0.6 0.4 0.2 1078 Vfp 0.13 0.24 0.28 0.32 0.38 2844 Dc? 0.07 0.1 0.11 0.13 0.15 3116 Vdb 0.08 0.14 0.15 0.19 0.22 11755 Dar 0.07 0.12 0.14 0.17 0.21 27266 Vin 0.12 0.17 0.2 0.24 0.29 20216 Dld 0.06 0.11 0.13 0.17 0.21 7914 Vpt 0.1 0.12 0.14 0.17 0.19 5385 Dcl 0.09 0.13 0.16 0.2 0.24 7915 sz0 0.1 0.12 0.14 0.17 0.19 590 Dcp 0.11 0.19 0.24 0.35 0.39 142 sz1 0.33 0.47 0.54 0.61 0.65 5185 Dph 0.07 0.15 0.19 0.23 0.28 1118 sz8 0.16 0.23 0.27 0.32 0.37 392 Dsl 0.05 0.09 0.13 0.19 0.24 858 s16 0.1 0.21 0.23 0.27 0.34 10883 Dad 0.04 0.09 0.11 0.14 0.17 24195 s32 0.12 0.17 0.2 0.24 0.29 3336 Dsb 0.05 0.11 0.13 0.17 0.22 5146 szN 0.09 0.15 0.17 0.2 0.23 3397 Dml 0.05 0.11 0.13 0.16 0.2 614 Pfp 0.1 0.23 0.26 0.3 0.37 1249 Ddv 0.02 0.09 0.13 0.17 0.22 2087 Pdb 0.07 0.14 0.16 0.19 0.22 341 Drm 0.02 0.05 0.08 0.12 0.21 18523 Pin 0.09 0.14 0.17 0.21 0.25 1660 Dsh 0.02 0.09 0.12 0.15 0.2 10797 Pst 0.15 0.2 0.23 0.28 0.32 1397 Dbt 0.05 0.12 0.16 0.19 0.23 3532 Pay 0.15 0.22 0.24 0.28 0.33 13275 Dgp 0.06 0.12 0.15 0.18 0.23 3820 Ppt 0.08 0.1 0.1 0.12 0.14 2233 Dcs 0.04 0.08 0.12 0.14 0.16 1 Pvc 0 1 1 1 1 181 Dex 0.06 0.09 0.14 0.18 0.22 6281 Ozr 0.4 0.48 0.52 0.58 0.62 207 Dfi 0.03 0.08 0.11 0.14 0.14 3857 Oin 0.05 0.1 0.12 0.15 0.18 648 Dif 0.03 0.07 0.11 0.15 0.19 466 Ofp 0.02 0.03 0.03 0.07 0.08 15 Dip 0.13 0.13 0.33 0.33 0.33 454 Ogb 0.09 0.15 0.18 0.22 0.27 86 Dpi 0.07 0.12 0.15 0.16 0.2 427 Oay 0.16 0.2 0.21 0.22 0.24 1955 Dtr 0.04 0.09 0.12 0.18 0.22 5043 Oag 0.05 0.09 0.11 0.15 0.19 6876 Dsx 0.05 0.12 0.15 0.2 0.25 5322 Old 0.09 0.14 0.18 0.23 0.29 1753 Dzx 0.09 0.16 0.19 0.24 0.29 2578 Ocl 0.11 0.15 0.18 0.24 0.28 12290 Dal 0.05 0.09 0.12 0.16 0.21 937 Omx 0.07 0.15 0.21 0.26 0.32 289 Di? 0.03 0.1 0.13 0.15 0.17 4075 Oad 0.05 0.08 0.11 0.13 0.16 1166 Smn 0.21 0.22 0.23 0.23 0.24 3082 Oic 0 0.01 0.01 0.01 0.02 25142 Sl0 0.13 0.17 0.19 0.23 0.26 140 Ong 0.04 0.16 0.2 0.22 0.23 8957 Sl1 0.08 0.14 0.18 0.22 0.27 9 Ont 0 0 0.11 0.11 0.22 3543 Sl2 0.08 0.17 0.21 0.24 0.29 768 Omd 0.07 0.17 0.18 0.22 0.25 1274 Sl3 0.07 0.17 0.22 0.26 0.29 938 Omu 0.04 0.11 0.14 0.17 0.22 458 Sln 0.06 0.11 0.15 0.21 0.27 989 Obn 0.04 0.12 0.16 0.2 0.23 16197 Scm 0.13 0.17 0.19 0.23 0.26 2728 Ocs 0.05 0.09 0.12 0.17 0.22 5830 Scl 0.1 0.15 0.19 0.24 0.29 12 Oal 0 0 0 0.08 0.08 643 Spl 0.1 0.16 0.19 0.3 0.33 238 Oun 0.04 0.1 0.13 0.15 0.17 11032 Slx 0.08 0.15 0.19 0.24 0.29 1030 Oiy 0.01 0.03 0.03 0.05 0.06 6881 Smp 0.14 0.2 0.23 0.28 0.32 5306 Msc 0.19 0.23 0.25 0.26 0.28 10631 Sms 0.1 0.15 0.18 0.23 0.27 18978 Msk 0.08 0.12 0.15 0.19 0.22 13771 Ssl 0.08 0.15 0.19 0.23 0.28 761 Mhp 0.16 0.22 0.24 0.28 0.3 8741 Sdl 0.07 0.13 0.16 0.21 0.25 6127 Mar 0.11 0.16 0.19 0.24 0.28 3151 Svi 0.19 0.29 0.34 0.4 0.46 6075 Mld 0.14 0.22 0.26 0.31 0.36 6174 Spi 0.05 0.1 0.14 0.18 0.22 1190 Mfn 0.15 0.2 0.23 0.25 0.28 2364 Erc 0.09 0.14 0.19 0.24 0.29 930 Mph 0.06 0.12 0.15 0.19 0.25 2364 Eaf 0.09 0.14 0.19 0.24 0.29 7 Mbt 0 0 0.43 0.43 0.43 100 Es1 0.09 0.12 0.16 0.26 0.41 18800 Dzr 0.18 0.24 0.28 0.32 0.37 565 Es4 0.05 0.14 0.21 0.29 0.35 24733 Din 0.05 0.1 0.13 0.16 0.2 631 Es8 0.21 0.24 0.28 0.32 0.35 1353 Dfp 0.03 0.08 0.1 0.15 0.17 952 EsN 0.04 0.1 0.13 0.17 0.2 5181 Dgb 0.08 0.14 0.16 0.19 0.23 1122 Esp 0.05 0.12 0.18 0.25 0.31 5008 Dfn 0.09 0.14 0.17 0.21 0.25 3181 Etp 0.08 0.19 0.24 0.29 0.33 by function; Total Feat Figure 3: Page 6 Version 2.0
	(2019)
	Confidentiality: Public Distribution

Mph: unknown location loaded from an SSA φ-function; Mbt: unknown location produced by a bitwise operation; Mld: other unknown locations; Version 2.0 (2019) Confidentiality: Public Distribution • LABELLOC. the location of the instruction within the program. Smn: within the main function; Sl0: not inside a loop. Sl1-Sl3: within a singly, doubly or triply nested loop; Slx:


E Anton

U Ayesta

M Jonckheere

I M Verloop

A Survey of Stability Results for Redundancy Systems

Keywords: redundancy, load balancing, stability

Redundancy mechanisms consist in sending several copies of a same job to a subset of servers. It constitutes one of the most promising ways to exploit diversity in multiservers applications. However, its pros and cons are still not sufficiently understood in the context of realistic models with generic statistical properties of service-times distributions and correlation structures of copies. We aim at giving a survey of recent results concerning the stability -arguably the first benchmark of performance -of systems with cancel-oncompletion redundancy. We also point out open questions and conjectures.

Introduction

While there are several variants of redundancy-based systems, the general notion of redundancy is to dispatch multiple copies of each job to a subset of servers and to consider the result of whichever copy completes service first. By allowing for redundant copies, the aim is to minimize the system latency by exploiting the variability in the queue lengths of the different queues. The potential of redundancy mechanisms lies in finding the right trade-off between exploiting variability and the waste of resources induced by having redundant copies.

Several empirical ( [START_REF] Ananthanarayanan | Why let resources idle? Aggressive cloning of jobs with dolly[END_REF][START_REF] Ananthanarayanan | Effective straggler mitigation: attack of the clones[END_REF][START_REF] Dean | Achieving rapid response times in large online services[END_REF][START_REF] Dean | The tail at scale[END_REF][START_REF] Sieber | The cost of aggressive http adaptive streaming: quantifying youtube's redundant traffic[END_REF][START_REF] Vulimiri | Low latency via redundancy[END_REF]) and numerical studies ( [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF][START_REF] Gardner | A better model for job redundancy: decoupling server slowdown and job size[END_REF][START_REF] Joshi | Efficient redundancy techniques for latency reduction in cloud systems[END_REF][START_REF] Lee | When do redundant requests reduce latency?[END_REF][START_REF] Lee | The mds queue: analysing the latency performance of erasure codes[END_REF]) suggest that redundancy might potentially improve the performance of real-world computer system applications. In particular, Vulimiri et al. [START_REF] Vulimiri | Low latency via redundancy[END_REF] consider a 10 DNS servers system and compare the system where each arriving query dispatches 10 copies to all the 10 DNS servers, to an alternative system where queries are assigned to a single server chosen uniformly at random. The authors observe that the fraction of queries with a service time exceeding 500 ms is reduced by a factor 6.5, and the fraction exceeding 1.5 sec is reduced by a factor 50. Another interesting study is provided by Dean and Barroso [START_REF] Dean | The tail at scale[END_REF] who underline that several redundancy techniques are applied in Google's BigTable in order to improve the latency of incoming queries. They show that a redundancy system with two copies reduces the median response time by 16% and the 99.9th-percentile of the tail of the response time distribution by nearly 40% compared to the non-redundant system.

Broadly speaking, depending on when replicas are deleted, we can consider two classes of redundancy systems: cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.). In redundancy systems with c.o.c., once one of the copies has completed service, the other copies are deleted and the job is said to have received service. In redundancy systems with c.o.s., copies are deleted as soon as one copy starts being served, and as a consequence, c.o.s. does not waste any computation resources.

In this survey, we will provide an overview on stability results in redundancy systems. From the point of view of stability, c.o.s. does not have any negative impact, and for this reason we focus on stability results when c.o.c. is implemented.

Let us illustrate through a simple example how redundancy affects the stability region. Consider a system with K homogeneous servers in which copies of each arriving job are dispatched to d ≤ K servers chosen uniformly at random. We assume that jobs arrive according to a Poisson process of rate λ and jobs have general service times with unit mean. Without redundancy, i.e. d = 1, the stability condition under any work-conserving policy is given by λ < µK, where µ is the capacity of the servers. Now, let us assume that the service times of copies are i.i.d. and that d = K. In this case, the system behaves as a single server system with arrival rate λ and server capacity µK, and the stability condition is again λ < µK. However, if all the copies had the same service time as the original job (identical copies), servers are synchronized and the instantaneous departure rate is just µ. Therefore, the system behaves as a single server system with arrival rate λ and server capacity µ, for which the stability condition is λ < µ. This simple example illustrates how the modeling assumptions and the degree of redundancy can dramatically impact the stability condition of the system.

One of the main lessons we draw from the results available in the literature, is that the stability region depends strongly on the scheduling policy employed at the servers and the correlation structure of copies. Somewhat surprisingly, we also identify situations for which it was shown that adding redundant copies does not reduce the stability region. Overall, we believe more research is needed in order to design efficient redundancy algorithms.

The rest of the survey is organized as follows. Section 2 describes the main model assumptions and notation, Section 3 deals with the case in which the service times of the copies are i.i.d., and Section 4 with identical and correlated copies. In Section 5, we present a brief account of results on redundancy that, even though not directly related to stability, are relevant from the performance point of view. We conclude with Section 6 where we discuss several open problems and state various conjectures.

Model Description and Preliminaries

We consider a K parallel heterogeneous server system. That is, we have a set of servers S = {1, . . . , K} and server s has capacity µ s , for s ∈ S. Jobs arrive to the system according to a Poisson process of rate λ. Arriving jobs have service times that are independent across jobs and are identically distributed with mean 1.

Jobs are labeled by types c = {s 1 , . . . , s i } ⊂ S, where i is the number of copies and c is the set of servers to which this job will dispatch copies. We let C be the set of all possible types. A job is of type c with probability p c , where c∈C p c = 1.

We consider redundancy models that are c.o.c., that is, as soon as a copy is fully served, the additional copies of that job are removed from the system. This cancellation process induces a correlation in the departure process at the servers. Thus, within a server s there is a departure of a copy due to the following two events: i) a local copy departs due to completion in server s, or ii) a copy in another server completes that induces a departure in server s.

Model Topology. A well-known symmetric topology is the one in which each job sends a copy to d out of K servers. In case the server are chosen uniformly at random, that is, p c = 1/ K d , and servers have the same capacity µ, we refer to this model as the redundancy-d model, see Figure 1 When no specific structure is assumed, we refer to it in the sequel as a general topology.

Scheduling Policy. A scheduling policy determines how copies are served within each server. As we will see, the choice of the scheduling policy can have a dramatic impact on the stability region. First-Come-First-Served (FCFS) and Processor Sharing (PS) are widely implemented in real-world computer systems ( [START_REF] Harchol-Balter | Performance Modeling and Design of Computer Systems: Queueing Theory in Action[END_REF]), and are thus common policies considered in the literature on redundancy. Random-Order-of-Service (ROS) is not a common discipline in systems, but as we will see in the ensuing, it yields very good performance in terms of stability for a redundancy system. These three policies represent the main focus of our survey. To the best of our knowledge, other policies such as Last-Come-First-Served (LCFS), Shortest-Remaining-Processing-Time (SRPT), and Least-Attained-Service (LAS) have not been considered so far.

Correlation Structure Among Copies. This describes how the service times of the copies of a given job are related. Formally, the service times X 1 , . . . , X k of the copies of one job can be sampled from a joint distribution F (x 1 , . . . , x k ). Two extreme cases are i.i.d. copies and identical copies. Under i.i.d. copies, all copies have independent service times sampled from the same distribution, whereas with identical copies, all the copies of a job have the same service time. Another interesting framework is the so-called S&X model introduced in [START_REF] Gardner | A better model for job redundancy: decoupling server slowdown and job size[END_REF]. Here, the service time of each copy is decomposed into two components; the inherent job size, which is identical for all the copies of a job, and the experienced slowdown on the server it is being served.

Existing Stability Results. Table 1 summarizes the main stability results for c.o.c. redundancy models available in the literature and discussed in this survey. The table is organized by scheduling policy, service time distribution, redundancy topology and correlation structure. In brackets we specify the additional assumptions that the authors consider in their respective paper. The term "red-d" refers to the redundancy-d system and the term "gen." refers to a general redundancy topology.

The stability condition when jobs have i.i.d. copies is the main topic of Section 3, first for exponential service times (Section 3.1) and then for scaled Bernoulli distributions (Section 3.2). These are the results in the first two columns of Table 1. Correlated copies are discussed in Section 4, first for identical copies (Section 4.1, middle two columns in Table 1) and then for general correlation structures (Section 4.2, last two columns of Table 1). In Section 6, we discuss open problems and state various conjectures regarding stability conditions. In Table 1, these conjectures are indicated with a X.

Independent and Identically Distributed Copies

In this section we assume that jobs have i.i.d. copies.

Exponential Service tTmes

We first discuss results on FCFS and exponentially distributed service times, a setting studied by Gardner et al. [START_REF] Gardner | Redundancy-d: the power of d choices for redundancy[END_REF][START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF] and Bonald and Comte [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF]. It was shown in [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF] that this model fits the framework of Order Independent queues (see [START_REF] Krzesinski | Order independent queues[END_REF]Chapter 2]), which is a large class of systems that have a product-form steady-state distribution. This can be seen as follows. Since copies are i.i.d., we can describe the system through the Markovian state descriptor (c n , c n-1 , . . . , c 2 , c 1 ). Here, n is the number of jobs in the system, c 1 is the type of the eldest job in the system and c i is the type of the ith eldest job. Because of FCFS, the eldest job is served in all of its compatible servers c 1 . The i-th eldest job is in service at servers s ∈ c i \ ∪ i-1 j=1 c j , for i = 1, . . . , n. Due to the exponentially distributed service times and i.i.d. copies, the instantaneous departure rate of the ith job is given by the sum of the rates in the servers where the job is in service, that is, s∈c i \c 1 ,...,c i-1 µ s . Hence, the total instantaneous departure rate out of state (c n , c n-1 , . . . , c 2 , c 1 ) is s∈∪ n j=1 c j µ s , which depends on the set of classes present in the system, but not on their ordering in the state descriptor, i.e., the so-called order independent property.

The characterization of the steady-state distribution facilitates the derivation of performance measures such as the stability condition and mean response times. The proposition below states the stability result for this model.

Proposition 1 ( [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF][START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF]). For a redundancy system with general topology under FCFS with exponentially distributed service times and i.i.d. copies, the system is stable if for all C ⊆ C,

λ c∈C p c < s∈S(C) µ s , (1)
where S(C) = c∈C {s ∈ c}. The system is unstable if there exists C ⊆ C such that

λ c∈ C p c > s∈S( C) µ s .
Informally, Equation [START_REF] Akgun | Partial flexibility in routing and scheduling[END_REF] states that the arrival rate to any subset of job types must be less than the total capacity of the associated compatible servers. For exponential service times, this is the maximum stability condition, i.e., the system cannot be stable if one of these inequalities were not satisfied. Thus, we conclude that the stability region is not reduced due to adding redundant copies. The latter might seem counter-intuitive at first, since even if servers waste resources serving copies that are not fully served, the stability condition is as large as if there was no redundancy (see also the simple example in the introduction).

Extending Proposition 1 to other scheduling policies is an important open problem (see Section 6 for more details). To the best of our knowledge, this has only been achieved for the redundancy-d model. In this case, it is easy to see that Equation (1) reduces to λ < µK, and it has been shown that this stability condition remains valid when either PS or ROS is implemented.

Proposition 2 ( [4]

). For the redundancy-d model under either PS or ROS with exponentially distributed service times and i.i.d. copies, the system is stable when λ < Kµ and unstable when λ > Kµ.

Hence, under PS, ROS and FCFS, the redundancy-d model is maximum stable. This however does not hold true in general. In the example below (originally in [START_REF] Anton | On the stability of redundancy models[END_REF]), we describe priority policy that is not maximum stable, i.e., the system can become unstable even though λ < Kµ.

Example: Priority Policy. Consider the redundancy-d system with K = 3, d = 2 and µ = 1. There are three different types of jobs: C = {{1, 2}, {1, 3}, {2, 3}}. In server 1, FCFS is implemented. In server 2 and server 3, jobs of types {1, 2} and {1, 3} have preemptive priority over jobs of type {2, 3}, respectively. Additionally, within a type, jobs are served in order of arrival.

Figure 2: The trajectory of the number of jobs per type when λ = 2.9.

In Figure 2 we plot the sample-path of the number of jobs when λ = 2.9 < 3 = µK. We observe that the number of type-{2, 3} jobs in the system grows large, while the number of type-{1, 2} and type-{1, 3} jobs stay close to 0. Hence, the system is clearly unstable, even though λ < µK. This can intuitively be explained by the inefficiency induced by the priority mechanism as the type-{2, 3} jobs are preempted by type-{1, 2} and type-{1, 3} jobs in servers 2 and 3, respectively. We refer to [START_REF] Anton | On the stability of redundancy models[END_REF] for more details.

General Service Times

To the best of our knowledge, no stability results exist for general service times with i.i.d. copies. In this section, we present the stability result obtained for scaled Bernoulli service times, defined as

X • M, with probability 1/M 0, with probability 1 -1/M,
where M > 0 and X is a strictly positive random variable with E[X] = 1. In this setting, Raaijmakers et al. [START_REF] Raaijmakers | Redundancy scheduling with scaled Bernoulli service requirements[END_REF] characterize the stability condition for the redundancy-d model where FCFS is implemented and the number of servers grows large.

Proposition 3 ( [35]

). Consider the redundancy-d model under FCFS with scaled Bernoulli service times and i.i.d. copies. Then, λ <

M d-1 E[min(X 1 ,...,X d )]
is a sufficient stability condition for any M . In addition, for any , it holds that (1

-)λ < M d-1 E[min(X 1 ,...,X d )
] is a necessary condition, for M sufficiently large.

We observe that the stability condition is independent of the number of servers, but strongly depends on the number of copies d. The latter is in contrast to the exponentially distributed service times, where the stability condition does dependent on the number of servers but is independent of d (see Proposition 2). Thus, we observe that when copies are i.i.d., the stability condition strongly depends on the service time distribution. In addition, we observe that as M grows large (and hence the variance of the service times grows large), the stability region increases by a factor M d-1 , by taking advantage of a greater diversity in service times.

Correlated Copies

Several studies (e.g., [START_REF] Vulimiri | More is less: reducing latency via redundancy[END_REF]) have shown that the i.i.d. copies assumption can be unrealistic, since large jobs remain large when replicated. Hence, having additional copies could lead to high response times and even instability. Motivated by the latter, stability results with correlated copies have been the focus of recent literature.

Identical Copies

In this section, we assume that jobs have identical copies, i.e., all copies belonging to one job have the same size. This correlation makes that a job can only depart due to its copy that has received most service so far. Thus, the instantaneous departure rate of a job depends on its copy that has currently attained most service.

FCFS Policy. With FCFS, the eldest job in the system will be served at all of its compatible servers. A job later in the queue will be served at its compatible servers that are not engaged by earlier jobs in the queue.

The stability condition for the redundancy-d system with FCFS and exponentially distributed service times is characterized in Anton et al. [START_REF] Anton | On the stability of redundancy models[END_REF], through the average departure rate per type in the so-called saturated system. The latter assumes an infinite backlog of jobs waiting for service. The long-run timeaverage number of jobs in service in the saturated system is denoted by ¯ . A detailed description of the saturated system and the characterization of ¯ can be found in [START_REF] Anton | On the stability of redundancy models[END_REF].

Proposition 4 ( [4]

). For the redundancy-d system under FCFS with exponentially distributed service times and identical copies, the system is stable if λ < ¯ µ and unstable if λ > ¯ µ.

The value of ¯ , and hence the stability region, can be numerically obtained by solving the balance equations of the saturated system, see [START_REF] Anton | On the stability of redundancy models[END_REF] for more details. We note that the instantaneous departure rate in the saturated system strongly depends on the types in service. As a consequence, no expression has been derived so far for ¯ for general K and d values.

Note that the stability condition can equivalently be written as λ Kµ < ¯ K , where λ Kµ is the traffic load. In Figure 3 (originally in [START_REF] Anton | On the stability of redundancy models[END_REF]), we provide numerical values for ¯ K , that is, the traffic supported by the system. The table (left) shows ¯ /K for small values of K and the figure (right) plots the value of ¯ /K as K grows large. To obtain the value of ¯ for d = 1, K -2, K -1, K, the authors simulate the saturated system, rather than solving the balance equations 1 . It was proven in [START_REF] Anton | On the stability of redundancy models[END_REF] that ¯ /K, hence the amount of supported traffic, increases when the number of servers (K) grows large, a property that can be observed in Figure 3.

¯ /K K = 2 K = 3 K = 4 K = 5 K = 6 K = 7 K = 8 d = 1 1 1 1 1 1 1 1 d = 2 0.
Processor Sharing Policy. Under PS and identical copies, the stability condition is characterized in [START_REF] Anton | Improving the performance of heterogeneous data centers through redundancy[END_REF]. There it is shown that the stability condition coincides with that of a K parallel server system where each type-c job is only dispatched to its so-called least-loaded servers. In order to state this result, we first need to define several sets of servers and customer types. The first subsystem includes all servers, that is S 1 = S. We denote by L 1 the set of least-loaded servers in the system S 1 = S. Thus,

L 1 =    s ∈ S 1 : s = arg min s∈S 1    1 µ s c∈C(s) p c       .
For i = 2, . . . , K, we define recursively

S i := S\ ∪ i-1 l=1 L l , C i := {c ∈ C : c ⊂ S i }, C i (s) := C i ∩ C(s), L i := s ∈ S i : s = arg min s∈S i 1 µ s c∈C i (s) p c .
The S i -subsystem refers to the system consisting of the servers in S i , with only jobs of types in the set C i . The C i (s) is the subset of types that are served in server s in the S i -subsystem. We let C 1 = C. The set L i represents the set of least-loaded servers in the S i -subsystem. Finally, we denote by i * := arg max i=1,...,K {C i : C i = ∅} the last index i for which the subsystem S i is not empty of job types. The stability condition is now characterized in [START_REF] Anton | Improving the performance of heterogeneous data centers through redundancy[END_REF] by the least-loaded servers that can serve each job type.

Proposition 5 ( [5]

). Assume that the service time distribution is such that it has no atoms and is lighttailed in the following sense,

lim r→∞ sup a≥0 E[(X -a)1 {X-a>r} |X > a] = 0. ( 2
)
For a redundancy system with a general topology under PS with identical copies, the system is stable if λ c∈C i (s) p c < µ s , for all s ∈ L i , i = 1, . . . , i * . The redundancy system is unstable if there exists ι ≤ i * and s ∈ L ι such that λ c∈Cι(s) p c > µ s .

It can be seen (as observed in [START_REF] Paganini | Network stability under alpha fair bandwidth allocation with general file size distribution[END_REF]) that the light-tailed condition in (2) also implies

sup a≥0 E[(X -a)|X > a] ≤ Φ < ∞, (3)
which is a usual light-tailed condition (see [START_REF] Foss | An Introduction to Heavy-Tailed and Subexponential Distributions[END_REF]). Hence, (2) and (3) exclude heavy tailed distributions like Pareto, but include large sets of distributions such as phase type (which are dense in the set of all distributions on R + ), exponential and hyper-exponential distributions, as well as distributions with bounded support.

For the redundancy-d model, the above stability condition simplifies into λ < Kµ/d. The latter coincides with the stability condition of a system where all the copies need to be served, that is, the worst possible stability condition.

ROS Policy. When ROS is implemented in the servers, it was shown in [START_REF] Anton | On the stability of redundancy models[END_REF] that the stability condition is not reduced when adding redundant copies. This was proved for exponentially distributed service times and identical copies for the redundancy-d model. However, as stated in Section 6, we believe that this holds true for any redundancy structure and any correlation structure.

Proposition 6 ( [4]

). For the redundancy-d model under ROS with exponentially distributed service times and identical copies, the system is stable if λ < Kµ.

The intuition behind the above result is as follows. Whenever there are many jobs in a server, the probability that this server serves a copy of a job that has also a copy elsewhere in service will be close to zero. Hence, with a probability close to 1, all highly-loaded servers are serving copies of different jobs and their instantaneous departure rate equals the sum of their capacities.

Generally Correlated Copies

In this section, we consider redundancy models where the service times of the copies of each job are correlated according to some general structure.

For FCFS, Raaijmakers et al. [START_REF] Raaijmakers | Achievable stability in redundancy systems[END_REF] consider a general workload model, which subsumes the S&X model, introduced in [START_REF] Gardner | Redundancy-d: the power of d choices for redundancy[END_REF]. The main difference is that in [START_REF] Raaijmakers | Achievable stability in redundancy systems[END_REF] the server capacities are not fixed, but each job samples server capacities from a discrete and finite distribution. The authors assume that the server speed variations (slowdowns) are either distributed according to New-Better-than-Used (NBU) or New-Worse-than-Used (NWU). See [START_REF] Ross | Stochastic Processes[END_REF] for more details on NBU and NWU distributions 2 .

Depending on the random variation in the server speed, the authors prove that either no replication (d = 1) or full replication (d = K) provides a larger stability region. Note that here the stability region refers to a wider concept than what we considered before. That is, it refers to the set of arrival rates such that there exists a static assignment rule that makes the system stable.

Proposition 7 ( [34]

). Consider the following model. Each job is routed to d servers according to some static probabilistic assignment. Servers implement FCFS. Every time a server starts serving a new copy, it samples a speed variation, which is independent across servers. The type of a job is determined by the capacities it would obtain in each server. A job has a generally distributed service time.

• If the probabilistic assignment can depend on the job type, and the speed variation follows an NBU distribution, then the stability region for d = 1 is larger or equal than that for d > 1.

• If the probabilistic assignment does not depend on the job type, and the speed variation follows an NWU distribution, then the stability region for d = K is larger or equal than that for d = 1.

From the above we observe that the optimal redundancy degree does not depend on the job size distributions, but rather on the random variation in the server speeds for a given job among the servers.

A sufficient stability condition for the redundancy-d model with FCFS has been obtained in Mendelson [START_REF] Mendelson | A lower bound on the stability region of redundancy-d with FIFO service discipline[END_REF]. He considers that the service times of the copies X 1 , . . . , X d are identically distributed with mean 1 and sampled from a joint distribution F (x 1 , . . . , x d ).

Proposition 8 ( [32]). Consider the redundancy-d model where FCFS is implemented and the service times of the copies are sampled from a general joint distribution F (x 1 , . . . , x d ). Then, λ < λ lb is a sufficient stability condition, where

λ lb := µK d m=0 d-m j=1 E[min(X 1 , . . . , X j )] + mE[min(X 1 , . . . , X d )] P m ,
and

P m = K-d d-m d m / K d .
For the special cases d = 1 and d = K, the sufficient condition simplifies to λ < λ lb = Kµ and λ < λ lb = µ/E[min(X 1 , . . . , X d )], respectively, which are in fact also the necessary stability conditions.

We now consider the redundancy-d model where PS is implemented. Raaijmakers et al. [START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF] characterize the stability condition under any service time distribution through the minimum of the service times of the copies of a job. The latter can be heuristically explained as follows: assume that all servers are equally loaded. Then, due to PS, the copy that completes first is the one with the smallest service time among all copies of the job.

Proposition 9 ( [36]

). For the redundancy-d model under PS where the service times of the copies are sampled from a general joint distribution F (x 1 , . . . , x d ), a necessary stability condition is λdE[min(X 1 , . . . , X d )] < Kµ.

In the particular case where copies are identical, the authors in [START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF] prove that Proposition 9 gives a sufficient and necessary stability condition, which is given by λd < Kµ. We note that the latter coincides with the stability condition for light-tailed service times distributions provided in Proposition 5. Moreover, [START_REF] Raaijmakers | Stability of redundancy systems with processor sharing[END_REF] shows that the stability condition under NWU service time distributions, respectively NBU service time distributions, is larger, respectively smaller, than that for exponential service times.

Related Work

In this section, we briefly overview relevant papers on redundancy. Even though the results do not deal directly with stability, they are important pointers for the reader who wishes to work on redundancy.

Response Time

The response time (a.k.a. delay) measures the time elapsed between arrival and departure. It is together with stability the main performance measure, and it has received considerable attention. The first performance analysis of a redundancy model was for cancel-on-complete (c.o.c.) with exponentially distributed service times, independent and identically distributed (i.i.d.) copies and FCFS. As discussed in Section 3.1, Gardner et al. [START_REF] Gardner | Redundancy-d: the power of d choices for redundancy[END_REF][START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF] and Bonald and Comte [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF] exploit the link between this redundancy system and the Order Independent queue [START_REF] Krzesinski | Order independent queues[END_REF], in order to show that the steady-state distribution has a product form. The paper [START_REF] Gardner | Redundancy-d: the power of d choices for redundancy[END_REF] showed that the mean response time in the system reduces as the redundancy degree d increases. Redundancy c.o.s. with FCFS and exponentially distributed job sizes has been analyzed in Ayesta et al. [START_REF] Ayesta | On a unifying product form framework for redundancy models[END_REF], where it was shown that the steady-state distribution also has a product form. This was achieved by showing that this model fits within the framework of multi-type jobs and multi-type servers studied in Visschers et al. [START_REF] Visschers | A product form solution to a system with multi-type jobs and multi-type servers[END_REF]. The above results have motivated researchers to develop unifying frameworks to explain the emergence of product form distributions in redundancy models. This is done in Ayesta et al. [START_REF] Ayesta | A token-based central queue with orderindependent service rates[END_REF] and Gardner and Righter [START_REF] Gardner | Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview[END_REF] by extending the frameworks of Visschers et al. [START_REF] Visschers | A product form solution to a system with multi-type jobs and multi-type servers[END_REF] and Order Independent queues [START_REF] Krzesinski | Order independent queues[END_REF], respectively.

Comte and Dorsman [START_REF] Comte | Pass-and-swap queues[END_REF] introduce the Pass-and-Swap queue, not included in the above unifying frameworks, but for which the product-form of the steady-state distribution is preserved. The authors provide several examples that fall into this framework, including a loss variant of the c.o.s. redundancy model.

The response time has also been studied in limiting regimes such as heavy traffic and mean field. Cardinaels et al. [START_REF] Cardinaels | Redundancy scheduling with locally stable compatibility graphs[END_REF] consider both c.o.c. and c.o.s. and establish that in heavy traffic the joint distribution of the number of jobs of the various types converges to the product of an exponentially distributed random variable times a deterministic vector, a phenomenon known as state-space collapse. Hellemans et al. [START_REF] Hellemans | Analysis of redundancy(d) with identical replicas[END_REF][START_REF] Hellemans | Performance of redundancy(d) with identical/independent replicas[END_REF] consider the mean-field regime and characterize the stationary workload distribution of c.o.c. with FCFS, general service times and both identical and i.i.d. copies. In Hellemans et al. [START_REF] Hellemans | Performance analysis of workload dependent load balancing policies[END_REF] the authors generalize the previous result to other redundancy scheduling implementations such as replication if above certain threshold, delayed replication policy or replicate small jobs. Another mean-field result can be found in Hellemans et al. [START_REF] Hellemans | On the Power-of-d-choices with least loaded server selection[END_REF] where the authors analyze the stationary response time and workload distributions of JSW(d), JSQ(d) and redundancy-d under FCFS and general service times.

Optimizing Redundancy

The stability results presented in this survey show that both the scheduling policy and the degree of redundancy can have a big impact on the stability region and hence on the performance of the system. Motivated by this, researchers have aimed at i) characterizing what is the optimal scheduling policy in the servers and ii) determining what is the optimum number of copies that should be created.

One of the first papers studying redundancy was by Koole and Righter [START_REF] Koole | Resource allocation in grid computing[END_REF], which considered a system where jobs can dispatch i.i.d. copies to any subset of servers in the system. The authors showed that with FCFS and NWU service time distributions, the best policy is to replicate to all the servers.

Several optimality results have been derived for the Least-Redundant-First (LRF) scheduling policy, which serves jobs in lower priority as their number of copies increases (jobs with the same number of copies are served according to FCFS). In particular, Gardner et al. [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF][START_REF] Gardner | A little redundancy goes a long way: convexity in redundancy systems[END_REF] consider nested redundancy models with exponential service times and i.i.d. copies, and show that the mean response time is minimized under LRF. We note that a redundancy model is nested if for all c, c ∈ C, either i) c ⊂ c or ii) c ⊂ c or iii) c ∩ c = ∅.

Akgun et al. [START_REF] Akgun | Partial flexibility in routing and scheduling[END_REF] consider a two-server system in which each server has dedicated traffic, that is, each server is a unique compatible server for one job type. The authors consider the DCF (Dedicated-Customers-First) scheduling policy and analyze the efficiency and fairness for both dedicated and redundant jobs.

Sun et al. [START_REF] Sun | On delay-optimal scheduling in queueing systems with replications[END_REF] consider various low-complexity redundancy scheduling techniques for systems where jobs have i.i.d. copies, and investigate when these are delay-optimal (or nearly-delay optimal) with respect to the stochastic ordering. These new scheduling techniques are based on job replication and job cancellation decision features. For instance, the authors show that the fewest unassigned task first with low-priority replication and earliest due date first with replication policies are nearly delay-optimal with NBU and NWU distributions, respectively.

Related Models

Redundancy as considered in this chapter is closely related to the (n, k) fork-join system. In the latter, there exist n servers each one receiving one of the blocks, and the job is completed once k < n blocks are served. If k = 1, this model becomes equivalent to the redundancy-n model with c.o.c..

For the (n, k) fork-join model, Lee et al. [START_REF] Lee | The mds queue: analysing the latency performance of erasure codes[END_REF] provide sequences of systems that upper and lower bound the original one, and that converge to the original system. Through these bounds, the authors characterize the mean response time of the system. Li et al. [START_REF] Li | Mean-field-analysis of coding versus replication in cloud storage systems[END_REF] derive that in the mean-field regime, coding always improves the mean response time compared to the redundancy model, i.e., (n, 1).

In [START_REF] Joshi | Efficient redundancy techniques for latency reduction in cloud systems[END_REF], the authors consider the (n, r, k) partial fork-join system, where the job is sent to r out of n servers uniformly chosen at random and waits for the first k ≤ r to complete. They study effective replication strategies for various scenarios. The authors show that both latency and cost are minimized when r increases for log-convex (high variable) service time distributions. Duffy et al. [START_REF] Duffy | MDS coding is better than replication for job completion times[END_REF] compare the tail response time of the (n, r, k) model to that of the redundancy-d model (with batch arrivals of size r). The authors show that the tail distribution of the response time under (n, r, k) partial fork-join is smaller than under the redundancy-d model as long as r -k ≥ d, as the number of servers tend to infinity.

In a recent paper, Zubeldia [START_REF] Zubeldia | Delay-optimal policies in partial fork-join systems with redundancy and random slowdowns[END_REF] considers the S&X model where the slowdown experienced by each copy in service is independent across servers, but not necessarily independent from the job's service time. The author provides a lower-bound on the mean delay for the (n, r, k) partial fork-join system, and shows that when slowdowns are exponentially distributed and independent of the service time of the job, the expected delay is minimized in the mean-field limit for a constant r that only depends on the arrival rate and mean slowdown.

Conclusions, Open Problems and Conjectures

The literature on the stability analysis of redundancy systems is recent and growing. However, there are many important cases that have not been analyzed yet. In this section, we address some of the open problems related to stability, and state several conjectures that are based on our intuitive understanding of the system. It is our hope that this survey might encourage more research on this relevant and timely topic.

I.i.d. Copies.

As shown in Proposition 1, FCFS is maximum stable with exponential service times and i.i.d. copies. We believe that this result should remain valid for any work-conserving scheduling policy with nonpreferential treatment across types, for instance PS, ROS, LCFS, LAS and SRPT. The reason for this is that the i.i.d assumption combined with the non-preferential treatment across types permits to take advantage of diversity when the system is close to saturation. Conjecture 1. Consider a redundancy system with a general topology with exponentially distributed service times and i.i.d. copies. For any work-conserving non-preferential scheduling policy, the system is stable if for all C ⊆ C,

λ c∈C p c < s∈S(C) µ s ,
where S(C) = c∈C {s ∈ c}.

Open Problem 1. If we relax the exponential service times to general service time distribution, the stability condition is unknown.

FCFS Scheduling Policy with Identical Copies

In Section 4.1, we saw that λ/µK < ¯ /K is the stability condition of the redundancy-d system where jobs have identical copies and exponential service times.

Open Problem 2. If we relax the redundancy-d structure to general topologies, or the exponential service times to general service times, the stability condition is unknown.

For exponential service times with the redundancy-d structure, we observed in Figure 3 that for a given number of copies d, lim K→∞ ¯ /K < 1. Note that λ/µK < 1 is the stability condition for a system with no redundancy. Hence, if it can be proved that lim K→∞ ¯ /K < 1, this would imply that as the number of servers grows large, the traffic load that a redundancy system can support is smaller than if no redundancy was implemented. The limit should coincide with the stability condition given in [START_REF] Hellemans | Analysis of redundancy(d) with identical replicas[END_REF], where the authors develop a numerical method to derive the stability condition in the mean-field limit.

We also observed the following monotonicity property in the number of redundant copies. More precisely, we conjecture that as the degree of redundancy increases, the stability region becomes smaller. Conjecture 3. Consider the redundancy-d model where FCFS is implemented and jobs have exponentially distributed service times and identical copies. Then, for fixed K, ¯ is decreasing in d, and hence, the stability region is decreasing in d.

ROS Scheduling Policy with Generic Correlation Structure.

In the particular case of ROS, we believe that Conjecture 1 will remain valid even if copies follow a general correlation structure, including identical copies. So far, this was only proved for the redundancy-d model with exponential distributed service times with identical copies, see Proposition 6. The intuition would be the following. In principle, multiple copies of the same job could be served simultaneously at various of its compatible servers. Due to the heterogeneous capacities and the correlation among the copies, the departure rate of that job depends on the residual service time of each copy. However, when the number of jobs in the system grows large, the probability that more than one copy of the same job is simultaneously in service goes to zero. Using fluid-limit techniques, as done in [START_REF] Anton | On the stability of redundancy models[END_REF], one then obtains that the fluid limit of the system equals that of the system where jobs have i.i.d. copies. Hence, if Conjecture 1 is valid, this would imply that Conjecture 4 is true as well.

Redundancy-Aware Scheduling

Another interesting, and so far unexplored area, is the impact of redundancy-aware scheduling policies on the stability region and the performance of the system. By redundancy-aware we refer to policies like LRF or Most-Redundant-First that can use information on the number of copies when choosing which copy to serve in a server. As discussed in Section 5.2, the authors of [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF][START_REF] Gardner | A little redundancy goes a long way: convexity in redundancy systems[END_REF] consider the nested model with exponentially distributed service times and i.i.d. copies and show that LRF minimizes the mean response time. It would be interesting to explore this further for more general redundancy settings.

Figure 1 :

 1 Figure 1: (a) The redundancy-d model for K = 4 and d = 2. (b) The N -model. (c) The W -model.

Figure 3 :

 3 Figure 3: The table and figure show the values of ¯ /K for different values of d and K.

Conjecture 2 .

 2 Consider the redundancy-d model where FCFS is implemented and jobs have exponentially distributed service times and identical copies. Then, for fixed d, lim K→∞ ¯ /K < 1.

Conjecture 4 .

 4 Consider a redundancy system with a general topology with exponentially distributed service times and an arbitrary correlation structure among copies. ROS is stable if for all C ⊆ C,λ c∈C p c < s∈S(C) µ s ,where S(C) = c∈C {s ∈ c}.

When d = K -1, there are d servers that process copies of one job, and the remaining K -d = 1 server serves one additional job, hence, ¯ =

When instead d = 1, there is no redundancy and each server serves one job in the saturated system, i.e., ¯ = K. When d = K, the system behaves as a single server with capacity µ, that is, ¯ = 1.

X is said to be New-Better-than-Used (NBU) if for all t1, t2 ∈ R, FX (t1 + t2) ≤ FX (t1) FX (t2). X is said to be New-Worse-than-Used (NWU) if for all t1, t2 ∈ R, FX (t1 + t2) ≥ FX (t1) FX (t2). A sufficient condition for X to be NBU (NWU) is to have an increasing (a decreasing) hazard rate, i.e., r(x) is increasing (decreasing) in x.

Acknowledgement

Research of E. Anton supported and research of M. Jonckheere partially supported by the French "Agence Nationale de la Recherche (ANR)" through the project ANR-15-CE25-0004 (ANR JCJC RACON). U. Ayesta has received funding from the Department of Education of the Basque Government through the Consolidated Research Group MATHMODE (IT1294-19).