Gilles Coppin
email: gilles.coppin@telecom-bretagne.eu

François Legras
email: francois.legras@telecom-bretagne.eu

Sylvie Saget
email: sylvie.saget@telecom-bretagne.eu

Supervision of autonomous vehicles: mutual modeling and interaction management

Keywords: unmanned vehicles systems, interaction, dialogue, trust in automation

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Unmanned Vehicle Systems (UVSs) will considerably evolve within the next two decades. In the current generation of UV Systems, several ground operators operate a single vehicle with limited autonomous capabilities, whereas, in the next generation of UV Systems, a ground operator will have to supervise a system of several cooperating vehicles performing a joint mission, i.e. a Multi-Agent System (MAS) [START_REF] Johnson | Inverting the control ratio: Human control of large, autonomous teams[END_REF][START_REF] Legras | Autonomy spectrum for a multiple UAVs system[END_REF]. In order to enable mission control, the autonomy of the vehicle and of the system will increase and will require new and richer forms of Human-system interaction.

The operator of an UVS performs two tasks at the same time: (1) mission command & control, and (2) interaction with the system. Both tasks induce varying workloads during the system's operation. In current systems, interaction is barely distinguishable from command & control. But as UVSs evolve, the interaction workload will rise as the operator will have to switch between several vehicles, streams of data, decision support systems, and so on. As Mouloua et al. have pointed out [START_REF] Mouloua | Workload, situation awareness, and teaming issues for UAV/UCAV operations[END_REF], the complexity of the interaction mechanisms between the operators and the system, and the complexity of the mission should vary in opposite ways. If mission complexity goes up (higher workload), interaction complexity should go down (simpler interaction with the system).

In this perspective, we propose to dynamically leverage different interaction strategies in the context of operator-UVS activities in order to modulate the workload of the operator. In the remainder of this section, we describe the roles of the Operator Support System in these future UVSs and the kind of interaction that they should support. In section 2, we discuss the interaction models that provide a basis for our work. Section 3 exposes our rationale for workload adaptation via dynamic interaction strategies, and section 4 discusses trust in automation and mutual modeling between the operator and the interactive system.

Roles of an Operator Support System in future UVSs

From the perspective of this paper, the main component of the Ground Control Station 1 (GCS) of an UVS is the Operator Support System (OSS) i.e. the information system that allows the command & control of the UVS by the operator. The OSS should support the following functions:

• Situation Awareness (SA) and information display, the OSS should make available to the operator all mission-related data i.e. information about vehicles (position, status, etc.), information about mission elements (objectives, threats, maps, etc.), data from vehicles' sensors (e.g. video feed);

• Vehicle command & control (C 2 )
, the OSS should allow the operator to issue commands to the Vehicles of the system and track their progress; • Decision support, as UVS operational capabilities increase, the OSS should provide the operator with decisional aids of some sort (e.g. semi-automatic route planning, information fusion). As a support to these new functions, the OSSs will integrate two additional roles in the UVS:

• Interaction management, considering the wealth of possible two-way interactions at different levels (SA, C 2 , decision support, see section 1.2) between the OSS and the operator, it becomes necessary to regulate these interactions. In similar ways to Human interaction, it becomes necessary to manage turn-taking, interruptions, task priorities and so forth; • Semantic bridge, as interactions within the UVS become more abstract (higher level) than the current remote operation, some kind of translation service becomes necessary. There is a need to convert operational commands from the operator side to machine-understandable instructions, for instance if 1 For the sake of simplicity we will consider only UVSs with a single GCS and a single operator in the scope of this paper the operator instructs a system of several vehicles to perform a search on a specific zone (see Figure 1). Similarly, one has to convert multiple sensor data or Decision Support System (DSS) output to Human-understandable form.

Types of interaction and non-understandings

As was stated earlier, several types of interaction can happen between the operator and the OSS. Furthermore, several parts of the UVS can initiate interactions, notably:

operator, vehicles and decision support systems. Table 1 illustrates some of these types interaction. Every type of high-level interaction2 can produce non-understandings. Humans usually deal with non-understanding by clarifying things. This is also applicable to operator-OSS interactions, with the OSS asking to re-phrase or for some clarification as in the following example:

-Operator: "Send UV2 to the building" -OSS: "Which building?" -Operator: "The building near the airport" -OSS: "North of the airport?" -Operator: "Yes" -OSS: "OK." Here, the feedback "OK" allows the participants to consider the non-understanding to be solved. Although this example is expressed in natural language interaction, a similar exchange could happen via more conventional means, with for example the OSS highlighting the building on the map.

Interaction

Interaction as a Collaborative Activity

The traditional view of interaction [START_REF] Grice | Logic and conversation, Syntax and Semantics[END_REF][START_REF] Searle | Speech acts: an essay in philosophy of language[END_REF] defines it as a unidirectional process resulting from two individual activities: the generation of a communicative act by the speaker and the understanding and interpretation of this communicative act by the addressee.

The success of an interaction is a consequence of the cooperative attitude of the speaker (his sincerity, his relevance, etc.). Consequently, the production of a suitable communicative act is concentrated on a single exchange and a single agent. The complexity (i.e. the cognitive load) of such a process is high. Moreover, the set of possible strategies to produce and understand a communicative act is very limited. The addressee having a passive role, positive feedbacks such as "Okay", "Mhm", "uhuh", nodding, etc., signaling successful understandings, are not necessary. Finally, non-understandings are regarded as communication errors, which have to be handled by additional complex mechanisms.

In contrast with this traditional view, collaborative models define interaction as a bidirectional process resulting from a single social activity [START_REF] Clark | Using language[END_REF]. Interaction is considered as a collaborative activity between dialog partners oriented toward the shared goal of reaching mutual understanding. Mutual understanding is reached through negotiation on interpretation, which is a form of interactive refinement of understanding until a sufficient point of intelligibility is reached. Consequently, the production of a suitable communicative act can be distributed between several exchanges from several dialog partners. The effort needed from each partner in such a process is lower than the effort produced by the speaker in the traditional view of interaction i.e. each partner has to contribute in some way to the interaction. The addressee has an active role, explicit and implicit feedbacks are required in order to publicly signal successful understandings. Finally, note that non-understandings are fully expected events in the process of negotiation and part of the model.

Interaction as a Subordinate Activity

As usual for goal-oriented interaction, the operator of an UVS is engaged in two activities: achievement of the mission and interaction with the OSS. As stated by Clark [START_REF] Clark | Using language[END_REF][START_REF] Bangerter | Navigating joint projects with dialogue[END_REF]: "Dialogues, therefore, divide into two planes of activity. On one plane, people create dialogue in service of the basic joint activities they are engaged inmaking dinner, dealing with the emergency, operating the ship. On a second plane, they manage the dialogue itself-deciding who speaks when, establishing that an utterance has been understood, etc. These two planes are not independent; for problems in the dialogue may have their source in the joint activity the dialogue is in service of, and vice versa. Still, in this view, basic joint activities are primary, and dialogue is created to manage them."

Interaction is defined by the dialog partner's goals to understand each other, in other words to reach a certain degree of intelligibility, sufficient for the current purpose. That means that:

• Perfect understanding is not required. The level of understanding required is directed by the basic activity (i.e. the mission) and the context (e.g. time pressure);

•

The attention of the operator (and the associated workload) is split between the two activities. As we consider that interaction is subordinated to mission achievement and that the operator has finite cognitive resources, interaction complexity should vary depending on the complexity involved by the mission [START_REF] Mouloua | Workload, situation awareness, and teaming issues for UAV/UCAV operations[END_REF]. Indeed, the collaborative effort for a basic activity (i.e. not subordinated) has to be optimized, whereas the collaborative effort for a subordinated activity has to be minimized [START_REF] Cherubini | Grounding is not shared understanding: Distinguishing grounding at an utterance and knowledge level[END_REF]. Such a behavior is rational (i.e. coherent) at both the collaborative and individual levels [START_REF] Saget | Goal-oriented dialog as a subordinated activity involving collective acceptance[END_REF].

Load adaptation

Collaborative models of interaction have already been used for the design of OSSs, for example in the WITAS [START_REF] Lemon | Collaborative dialogue for controlling autonomous systems[END_REF] and GeoDialogue [START_REF] Cai | Communicating Vague Spatial Concepts in Human-GIS Interactions: A Collaborative Dialogue Approach[END_REF] projects. The model of collaboration that we propose to use and have outlined in section 2.1 has two main characteristics: (1) the interpretation process is simple and therefore allows for realistic implementation; (2) it supports a wide range of methods for generation and interpretation. As we will see in the following subsections, the OSS can adjust its cooperative attitude toward the operator by choosing among different strategies for handling understanding of communicative acts, as well as for generation and interpretation of communicative acts.

Understanding and Non-understanding

In all collaborative models of interaction, the reaction to the understanding of a communicative act is the same: a positive feedback. These feedbacks range from a simple "OK" to a comprehensive recast of the act (e.g. "OK. Sending UV2 to building B213.") 3 , but from a collaborative point of view, they have the same value.

Concerning non-understandings, several strategies are available, that we illustrate here in decreasing order of collaborative effort on the part of the OSS:

• Proposing a refinement or clarification to the operator (disambiguation) e.g. "Do you mean the building north of the airport?"; • Requesting a refinement or clarification to the operator (disambiguation) e.g. "Which building?"; • Asking for a recasting of the whole communicative act e.g. "Please rephrase.";

• Postponing or giving up, because something more urgent is coming e.g. "Hold on… Intruder detected at XY". The more collaborative effort is put in the non-understanding management by the OSS the less effort is needed from the operator i.e. the operator only needs to answer by "Yes" (or "No") to the question "Do you mean the building north of the airport?" whereas he or she has to recompose his or her request if the OSS replies "Please rephrase." Thus, the management of non-understandings constitutes the first degree of freedom in setting the cooperative attitude of the OSS.

Generation and Interpretation

Similarly, there exist many different strategies with varying levels of complexity for generating and interpreting communicative acts. Our model allows the use of many different strategies e.g. Higher levels of consideration of each other's mutual beliefs are possible, but are rarely deployed. These strategies are listed in order of ascending complexity [START_REF] Bard | Let's you do that: Enquiries into the cognitive burdens of dialogue[END_REF]. Complexity concerns Human beings, who tend to rely on the simplest sufficient strategy for the current purpose, but concerns also the OSS if these strategies are to be implemented. The choice of a strategy for generation and interpretation constitutes the second degree of freedom in setting the cooperative attitude of the OSS.

Rationale for Adjusting the Cooperative Attitude of the OSS

One can define the cooperative attitude of the OSS as its level of contribution to interaction at a given moment, expressed by the choices of strategies for (1) nonunderstanding management and (2) generation and interpretation. A high level of cooperative attitude on the part of the OSS will require less effort from the operator in order to interact with the OSS, thereby allowing him or her to concentrate on the mission. Therefore, it would seem logical to set the OSS at the maximum level of cooperative attitude throughout the whole mission. 4 On the contrary, we argue that it should be beneficial to set the OSS to a lower level of cooperation attitude in some circumstances.

A low level of cooperative attitude on the part of the OSS will force the operator to put more effort in the interaction process. Such an effort will notably lead to:

• Maintaining the operator's situational awareness (SA) i.e. it is easier to lose track of what is happening if all the operator has to do is answering by "Yes" or "No" to the requests of the OSS, particularly during low stress phases of the mission;

•

Improving the operator's feeling to be part of a team (working conjointly) with the OSS; • Constructing and maintaining a common language. Therefore enabling the use of "cooperative" or "mutual awareness" strategies (see section 3.2) later on e.g. by using the "selfish" strategy at one point, the OSS will force the operator to learn its terminology, which will allow for more effective interaction later; • Developing more accurate model of each other's capabilities by using different interaction possibilities. Of course, during high-stress, high workload phases of the mission, the OSS should bear the brunt of the interaction workload, therefore relieving the operator. This balancing effect will be all the more pregnant that the operator has had the opportunity to interact at different levels with the OSS.

Mutual Modeling

System predictability and mutual modeling

Being solely focused on the workload assessment may lead to some limitations in setting an adequate mode of man-machine cooperation. Therefore we expect an adequate interaction manager to include or rely on a model of cooperation between the operator and the system. We consider here the concept of cooperation in the sense of Klein et al.'s approach [START_REF] Klein | Common ground and coordination in joint activity[END_REF] involving the notions of basic compact, common ground, predictability and directibility. We will not address the basic compact (that represents the underlying agreement of working as a team and of following a cooperative behavior) and the common ground (that we have proposed to enrich in our approach as described here below). Predictability and directibility are on the contrary central in the approach. According to Klein et al., predictability means that the operator is able to anticipate the future behavior and strategies of the system -including interaction strategies -so that (s)he can better synchronize and coordinate with it. Still according to these authors, directibility means that the operator is able to "guide" the system towards a desired behavior.

According to this approach this means that both operator and system should have a model of each other. This mutual modeling can be used for a better cross-estimation of mutual performances and for feeding an optimized allocation mechanism functioning at meta level. But it also opens to the setting of a different kind of relationship between the operator and the system based on trust.

Trust

Classical models of trust are trying to associate the concepts of workload, trust and global performances. Lee's model [START_REF] Lee | trust, self-confidence, and operator's adaptation to automation[END_REF], for instance, proposes to compute a dynamical level of trust through a first order autoregressive equation as follows:

Trust(t) = a 1 Trust(t-1) -a 2 Fault(t) + a 3 Fault(t-1) + a 4 perf(t) -a 5 perf(t-1)
where perf is the system's (i.e. operator + machine) performance and fault represents a fractional variation of the control system in regard with the reference values. Still according to Lee et al.

[i], one can derive from this equation a percentage of work allocation to the automation, defined through: work_auto(t) = work_auto(t-1) + b 1 (Trust(t) -Sc(t)) + b Indiv + e where work_auto(t) is the percentage of work allocated to the machine at time t, Sc(t) is the level of self-confidence, Indiv is a constant individual bias depending on the operator and e a random noise.

Even if possibly adapted to our context of multi vehicle control, this kind of model obviously ignores the effect of adequate (or inadequate) interaction between the operator and the system on trust and -possibly mutual -reliance.

Based on our approach of adaptive interaction management, we can propose to enhance the classical approaches with new indicators, especially such as the level of understanding that may have been reached and, as a correlate, the relevance of the communication strategy of the automata according to the context and the operator workload.

Thus taking into account interaction strategies and modes allow us to go beyond classical performance (observation of behavior) analysis and to include complementary aspects of trust such as process (understanding of causal mechanisms) and purpose (intend of use) aspects.

Conclusion

This paper aims at emphasizing the role and interest of interaction management in man-machine cooperation and adaptive authority sharing. Dynamical management of interaction may not only have direct impact on the global workload of the operator while impacting the interaction-related workload, but also have a direct impact on the operator's trust in the system. Increasing the level of trust in the system should haveat least indirectly -a positive impact on the way the operator uses the automation and should consequently lead to performance enhancement.

Figure 1 .

 1 Figure 1. Illustration of the concept of semantic bridge on multi-UV system.

Table 1 .

 1 Types of interaction.

	Initiator  addressee	Interaction type	Examples in natural language
	Operator  Vehicles	Command & Control	"Send the two nearest Vehicles to patrol
			zone 1"
	DSS  Operator	Decision support	"The intruder detected on the north
			fence seems headed toward hangar 2"
	Operator  OSS	Interaction management	"Do not disturb me for the next two
			minutes"
	Operator  OSS	Interface manipulation	"Display the power lines and zoom on
			the alarm"

High-level considered as opposed to low-level interaction like clicking on a button.

Again, this example uses natural language for simplicity, but the OSS could very well recast such a communicative act graphically by highlighting UV2 on the display and showing its route toward building B123.

We will not consider computational power in the scope of this paper, even though it could indeed happen that some interaction strategies are too cost intensive in some circumstances.


Bilel Derbel

Arnaud Liefooghe

Gauvain Marquet

El-Ghazali Talbi

A Fine-Grained Message Passing MOEA/D

We propose the first large-scale message passing distributed scheme for parallelizing the computational flow of MOEA/D, a popular decomposition-based evolutionary multiobjective optimization algorithm. We show how synchronicity and workload granularity can impact both quality and computing time, in an extremely fine-grained configuration where each individual in the MOEA/D population is mapped to a single distributed processing unit. More specifically, we deploy our distributed protocol using a large-scale environment of 128 computing cores and conduct a throughout analysis using a broad range of bi-objective combinatorial ρMNK-landscapes. Besides being able to show significant speed-ups while maintaining competitive search quality, our experimental results provide insights into the behavior of the proposed scheme in terms of quality/speedup trade-offs; thus pushing a step towards the achievement of effective and efficient parallel decomposition-based approaches for large-scale multi-objective optimization.

I. INTRODUCTION

Multi-objective optimization problems (MOPs) refer to the situation where multiple objectives are to be optimized in a simultaneous manner. Many-often, the objectives to be optimized are conflicting, and solving a given MOP turns out to seek a whole set of solutions instead of just a single one. The set of optimal solutions is called the Pareto set, which is the set of all non-dominated solutions, i.e., solutions for which there exist no other solution providing a better tradeoff in all objectives. It is well understood that computing the Pareto set is a difficult task which is in addition intractable for several MOPs. In this context, evolutionary multi-objective optimization (EMO) algorithms have been proved extremely helpful in computing a high-quality approximation of the Pareto set which portrays good and representative balance among conflicting objectives. One can find different classes and paradigms in EMO algorithms, ranging from Paretobased methods, indicator-based methods, and aggregationbased methods. In this paper, we are interested in the last group of methods and particularly on the design of new advantageous approaches dedicated to large-scale and distributed computing environments. In this respect, the motivation of this paper is to be understood from two perspectives.

On the one hand, aggregation-based EMO methods have attracted a lot of attention during the last few years. In particular, the so-called MOEA/D (multi-objective evolutionary algorithm based on decomposition) framework [START_REF] Zhang | MOEA/D: A multiobjective evolutionary algorithm based on decomposition[END_REF] is being actively developed by the community due to its simplicity, but also due to its high search ability, computational efficiency, and adaptability to many problems. In MOEA/D, a MOP is reformulated as a set of single-objective sub-problems by means of scalarizing functions configured with different weight vectors in the objective space. As such, MOEA/D solves the soobtained single objective sub-problems in a cooperative man-ner using evolutionary mating selection, replacement and variation operators. On the other hand, when abstracting away from the optimization-specific operations, one can view MOEA/D as a divide-and-conquer algorithm which might expose intrinsic parallelism since the original MOP is explicitly decomposed in order to be solved. Such a claim would allow one to tackle large-scale problems and to take much benefits from the increased availability and computing power of nowadays large-scale distributed platforms such as clusters and grids. Generally speaking, designing parallel and distributed EMO algorithms has a well established foundation and a long-term practical usefulness in solving difficult MOPs. Nevertheless, investigating to what extent the MOEA/D framework can be redesigned to run efficiently in large-scale compute environments is surprisingly not yet fully addressed although one can find some recent attempts in this direction [START_REF] Nebro | A study of the parallelization of the multi-objective metaheuristic MOEA/D[END_REF], [START_REF] Durillo | Distribution of computational effort in parallel MOEA/D[END_REF], [START_REF] Mambrini | PaDe: A parallel algorithm based on the MOEA/D framework and the island model[END_REF]. We attribute this to the following two challenging questions:

• How to maintain the search ability of the MOEA/D framework when attempting to break the dependencies in the computational flow of its original implementation? In fact, MOEA/D is inherently sequential and it needs to be accurately adapted in order not only to fit the distributed setting, but also to guarantee as much approximation quality as possible.

• How to deal with the fine-grained parallelism that is likely to be encountered when effectively deploying the so-obtained variants at a large distributed scale? In fact, fine-grained workload can drastically prevent high performance when scaling up computing resources, especially in the scenario where communication cost is non-negligible compared to objectives' evaluation cost of the target MOP.

The ultimate challenge standing behind the previous questions is to derive novel parallel MOEA/D algorithms presenting a good balance between approximation quality and speed-up in the largest scales where fine-grained computations are unavoidable. The aim of this paper is to address this challenge and to shed more light into decomposition-based EMO best practices in the context of large-scale distributed environments. More precisely, our contributions can be summarized as follows:

• We propose a new fine-grained message-passing scheme to distribute the MOEA/D computations. Our scheme can be configured so as to run in synchronous, as well as in asynchronous manner, and has an additional parameter allowing to control workload granularity; thus eliciting different trade-offs between parallel efficiency and approximation quality.

• We implement our distributed scheme using the MPI message-passing library and deploy the so-obtained distributed protocols in a real experimental set-up on top of a cluster of 128 computing cores. To our best knowledge, this is the first time that such a computing environment is considered. As a case study, we consider an extensive set of combinatorial biobjective ρMNK-landscapes, ranging from small-to large-size instances, as well as instances with different characteristics in terms tractability and difficulty.

• We provide a throughout evaluation of our distributed scheme and its implemented variants. Overall, we are able to experimentally validate the accuracy of our approach. In particular, we obtain significant speedups while maintaining very competitive approximation quality even in the most fine-grained scenarios; thus pushing parallelism in MOEA/D to its limits. More importantly, our experimental study provides the first comprehensive results on the benefits and the limits of parallelizing the MOEA/D computational flow.

The rest of this paper is organized as follows. In Section II, we recall some basic definitions and provide a related work overview. In Section III, we describe our distributed scheme and discuss its message passing implementation. In Section IV, we provide a throughout experimental study on bi-objective ρMNK-landscapes. In Section V, we conclude the paper.

II. BACKGROUND AND RELATED WORK

A. Multi-objective Optimization

A multi-objective optimization problem (MOP) can be defined by a set of M objective functions f = (f 1 , f 2 , . . . , f M ), and a set X of feasible solutions in the decision space. In the combinatorial case, X is a discrete set. Let Z = f (X) ⊆ IR M be the set of feasible outcome vectors in the objective space. To each solution x ∈ X is assigned an objective vector z ∈ Z, on the basis of the vector function f : X → Z. In a maximization context, an objective vector z ∈ Z is dominated by an objective

vector z ∈ Z (z ≺ z ) iff ∀m ∈ {1, 2, . . . , M }, z m ≤ z m and ∃m ∈ {1, 2, . . . , M } such that z m < z m . A solution x ∈ X is dominated by a solution x ∈ X (x ≺ x ) iff f (x) ≺ f (x ). A solution x ∈ X is
termed Pareto optimal (or non-dominated), if there does not exist any other solution x ∈ X such that x ≺ x. The set of all Pareto optimal solutions is the Pareto set. Its mapping in the objective space is the Pareto front. In the combinatorial case, the size of the Pareto set is typically exponential in the size of the problem instance, and deciding if a solution belongs to the Pareto set may be NPcomplete. Therefore, our goal is to identify a good Pareto set approximation. For this purpose, evolutionary multi-objective optimization (EMO) constitute a popular, effective and efficient alternative. In this paper, we are interested in decompositionbased methods, and especially on the MOEA/D framework.

B. The MOEA/D framework

Decomposition-based EMO algorithms [START_REF] Zhang | MOEA/D: A multiobjective evolutionary algorithm based on decomposition[END_REF], [START_REF] Giagkiozis | Generalized Decomposition[END_REF], [START_REF] Hughes | Multiple Single Objective Pareto Sampling[END_REF] seek a good-performing solution in multiple regions of the Pareto front by decomposing the original MOP into a number of scalarized single-objective sub-problems. Different scalarizing functions have been proposed so-far [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]. In this paper, we use the weighted Chebyshev (g te ) function, to be minimized:

g te (x, λ) = max i∈{1,...,m} λ i • z i -f i (x) ,
where x ∈ X, λ = (λ 1 , . . . , λ m ) is a positive weighting coefficient vector such that λ i 0 for all i, and z = (z 1 , . . . , z m ) is a reference point.

In the MOEA/D framework, sub-problems are optimized in a dependent manner by defining a neighborhood relation between sub-problems. In fact, solving a single sub-problem is likely to benefit from the current solutions found for the corresponding neighboring sub-problems. In more details, let (λ 1 , . . . , λ µ ) be a set of µ uniformly distributed weighting coefficient vectors defining µ sub-problems. MOEA/D maintains a population P = (x 1 , . . . , x µ ), each individual corresponding to a good-quality solution for one sub-problem. For each sub-problem i ∈ {1, . . . , µ}, a set of neighbors B(i) is defined by considering the T closest weight vectors. To evolve the population, sub-problems are optimized iteratively. At a given iteration corresponding to one subproblem i, two solutions are selected at random from B(i), and an offspring solution x is created by means of variation operators (mutation and crossover). A problem-specific repair or improvement heuristic is potentially applied on solution x to produce x . Then, for every sub-problem j ∈ B(i), if x improves over j's current solution x j then x replaces it, i.e., if g te (x , λ j ) ≤ g te (x j , λ j ) then set x j = x . The algorithm loops over sub-problems until a stopping condition is satisfied.

One can find other more specific variations of MOEA/D which may differ in the way scalarizing functions are defined, or in the way the neighbors are computed. We do not address these variations and we rather focus on the parallelization of the main MOEA/D components. In fact, the design of MOEA/D is inherently sequential since sub-problems are considered iteratively in a dependent manner. These dependencies are one of the main issues one has to deal with in a parallel setting. In the following, we review existing related solutions.

C. Parallelism in MOEA/D

Although one can find an extensive literature on the benefits of parallel and distributed computing with respect to EMO algorithms in general [START_REF] Van Veldhuizen | Considerations in engineering parallel multiobjective evolutionary algorithms[END_REF], we can report relatively few recent work related to the MOEA/D framework. The first study is conducted in [START_REF] Nebro | A study of the parallelization of the multi-objective metaheuristic MOEA/D[END_REF] where the authors investigated the intuitive idea that non-overlapping sub-problems, i.e. sub-problems having disjoint T -neighbors, could be processed in parallel. A threadbased implementation, specific to a shared memory system with multi-core processors, was derived. The population is partitioned so that each thread handles a separate partition. Since the neighbors of sub-problems at the borders of partitions overlap, some elements of a thread could be concurrently modified. To avoid race conditions, critical sessions are identified and implemented accordingly. Using eight-core machine and continuous MOP benchmarks, it is shown that speed-ups can be obtained at the price of significantly deteriorating the approximation quality compared to the sequential MOEA/D. Actually, above 4 partitions for a population size of 600, the approximation quality starts to drop substantially, which indicates that the proposed approach cannot scale properly.

The idea of partitioning the MOEA/D population was extended in [START_REF] Durillo | Distribution of computational effort in parallel MOEA/D[END_REF], and the partitions were made disjoint to avoid the overlapping issues. The observation that disjoint partitions may require different computational efforts was investigated. Advanced mechanisms controlling the size of partitions dynamically or evenly distributing the number of function evaluations were studied. Experimental results with 8 partitions for a population size of 300 were shown. Besides the limitations inherent to such a configuration, no parallel implementation was actually provided. In fact, the focus therein was on studying the impact of the proposed models on quality, and not on parallel issues.

More recently, a parallel variant of MOEA/D based on the island model, and called PaDe, was investigated in [START_REF] Mambrini | PaDe: A parallel algorithm based on the MOEA/D framework and the island model[END_REF]. In such a model, every island evolves a sub-population of individuals with respect to given sub-problems. Selected individuals are then sent to other islands during a migration phase. The parallel efficiency of the so-designed model is demonstrated with a 8core shared-memory machine on a thread-basis implementation where a thread can handle a subset of islands. However, two major issues are left open. While PaDe is experimented with a self-adaptive differential evolution (DE) operator, different from the standard DE operator used to run MOEA/D, it is still not able to output similar approximation results. More importantly, a thread-based implementation is suitable for a shared memory system, and it is known that scaling up and adapting it for a distributed setting while maintaining its accuracy can suffer several shortcomings; because concurrent shared-memory read/write operations are no more possible, and distributed communication is typically many orders of magnitude more costly, which can be prohibitive.

Tightly related to the island model, novel generational sequential MOEA/D variants were described in [START_REF] Marquet | Shake them all! rethinking selection and replacement in MOEA/D[END_REF]. The idea developed there-in is to rethink MOEA/D selection and replacement mechanisms by evolving the whole individuals simultaneously at once instead of iteratively one after the other. In their conclusion, the authors pointed out that a generational approach opens the door to incorporating parallelism in MOEA/D. However, moving to a distributed setting is not obvious and requires further careful investigations.

D. Discussion and Contribution Positioning

Despite the skillful design and the valuable efforts involved in the mentioned approaches, understating how the quality of MOEA/D is affected by parallelism, and what speed-ups can be attained when facing fine-grained parallelism at large distributed scales, is not yet fully accomplished. In this respect, our work departs from the previous studies in several aspects; but it also retains insightful lessons learnt from them. As in [START_REF] Nebro | A study of the parallelization of the multi-objective metaheuristic MOEA/D[END_REF], [START_REF] Durillo | Distribution of computational effort in parallel MOEA/D[END_REF], the idea of handling overlapping neighbors is a key point for scalability and high-quality approximation. As in [START_REF] Marquet | Shake them all! rethinking selection and replacement in MOEA/D[END_REF], we adopt a generational approach to maintain good approximation quality. As in [START_REF] Mambrini | PaDe: A parallel algorithm based on the MOEA/D framework and the island model[END_REF], we get inspired by the island model for the purpose of parallel efficiency. However, our approach is not explicitly based on the concept of islands and it is finely optimized to face fine-grained parallelism and to handle concurrency in the MOEA/D computational flow. As a by-product, the so-obtained scheme is proved very competitive when effectively implemented using message-passing under harsh configurations. This is a distinctive aspect of our work which gives room for further research in this line.

III. A FINE GRAINED DISTRIBUTED SCHEME

Our MOEA/D distributed scheme, called MP-MOEA/D, and its high-level implementation using the message passing paradigm are summarized in Algorithm 1 and the procedures of Algorithms 2 and 3. Before going into the details, it is important to remark that the template of Algorithm 1 is to be executed independently in parallel by every processing unit (all variables are local and not shared in any way). In fact, we assume that each processing unit (PU) p i , i ∈ {0, . . . , µ}, is handling one single sub-problem with respect to weight vector λ i , obtained by decomposition as in the standard MOEA/D framework. In other words, the population is partitioned into disjoint single-individual sub-populations evolved separately by every single PU 1 . In addition, the T neighbors of PU p i are defined consequently as those holding the T neighboring sub-problems corresponding to weight vectors λ j , j ∈ B(i).

Having this in mind, the main responsibility of a PU is to identify the best solution with respect to its sub-problem while cooperating with its neighbors. For this purpose, the computations performed by PU p i within the MP-MOEA/D scheme can be divided in two stages: The first stage (lines 3 to 14) is performed locally without any communication, whereas the second stage requires distributed communication with neighbors (line 16) as expanded in Algorithms 2 and 3.

A. Stage #1: Local Computations

The goal of PU p i is two-fold: (i) to identify an improving solution for its own sub-problem, and (ii) to check whether an improving solution is found w.r.t. neighboring sub-problems. For this purpose, p i maintains a representative copy of the solution of each neighbor. For clarity, we delay the mechanism to distributively maintain these copies to later.

Using its own solution and the copies with respect to its neighbors, a PU p i performs the same selection and variation mechanisms as in the conventional MOEA/D, with essentially three main modification: (i) p i 's actual solution x i is always selected for reproduction (line 7), (ii) the number of iterations during which new offspring solutions are generated is controlled by a parameter t max (line 5), and (iii) since the actual remote solutions of neighbors are not known nor directly accessible, PU p i simply checks whether any newly generated offspring does improve any of the local copy maintained for every neighbor (lines 13 to 14). The idea here is that, if the local copies are sufficiently up-to-date, then the protocol has the ability to distributively generate a 'good' offspring and to correctly detect any improvement on behalf of neighboring PUs. The improving offspring solutions are momentarily saved for the next stage.

B. Stage #2: Distributed Update

After the local computation stage, the second stage involving distributed communications and encapsulated within procedure DISTRIBUTED UPDATE (line 16) is activated. Its goal is to distributively update the local states of PUs. In fact, two main situations can occur at every PU p i after executing the first stage: (i) an improving offspring solution for its own sub-problem has been identified, (ii) an improving offspring solutions for one (or more) neighboring sub-problem(s) has Algorithm 1: MP-MOEA/D: High level code to be executed by every processing unit (PU) p i , i ∈ {0, . . . , µ} Input: B(i): neighboring sub-problems; λ j for every j ∈ B(i): neighbors' weight vectors; been identified. In the first case, p i has to notify its neighbors so that they can update their local copies with p i 's new current solution. In the second case, p i has to notify the corresponding neighbors so that they can update their own solutions with a new improving offspring. Symmetrically, p i has to check whether these situations occur at one (or more) neighbor(s) before resuming a new stage of local computations.

The implementation of the above described mechanism is to be handled with special care since this is where fine-grained parallelism can prevent scalability. In fact, the fastest the states of PUs are updated with fresh information from neighbors, the better should be the approximation quality. On the other side, synchronizing the PU states distributively more often implies more communication cost, that might dominate the cost of local computations. Notice that this is precisely the reason why we introduced the parameter t max in the previous stage, which offers the possibility of controlling the relative cost of local computations by fixing the communication frequency. Moreover, we experiment both synchronous (Algo. 2) and asynchronous (Algo. 3) message passing implementations where all distributed update operations are aggregated into a single message in order to reduce the number of messages transmitted over the network.

In the synchronous case, every PU sends a message with accurate information to its neighbors, and then blocks waiting for their respective messages to be received. This synchronous implementation provides the guarantee that all PUs will be updated with fresh information before resuming a new round of local computations. However, in order to avoid deadlocks, we need that every PU sends an acknowledgement (empty message) to its neighbors even if no change in the PU local state was observed. This has the drawback of introducing idle

11 v ← Msg[1]; 12 if v = ∅ then x j ← v; 13 ; 14 x ← Msg[2]; 15 if x = ∅ and g te (x, λ i ) < g te (x i , λ i ) then 16 x i ← x; flag ← 1; 17 for m ∈ {1, . . . , M } do 18 if z m < vm then z m ← vm; 19 ; 20 if z m < xm then z m ← xm; 21 ;
times where PUs are actually waiting for non-useful messages. The difficulty here is that a PU has no way to know whether a remote neighbor actually received a useful information.

The asynchronous implementation is technically very similar, but it removes the need to systematically send a message for neighbors and to wait for their messages. In fact, a PU updates a neighbor by sending non-empty messages containing useful fresh information only when needed. Symmetrically, a PU needs to simply check, without blocking, whether some messages are pending. Although this asynchronous mechanism removes waiting times and synchronization costs, it has a major limitation compared to the synchronous version. In fact, depending on the relative cost of communications compared to local computations, a PU may miss to update itself with fresh information. Hence, the first stage can eventually be resumed for several rounds with outdated information, which can constitute a sever penalty in terms of approximation quality.

C. Discussion

We notice that once a PU p i receives an offspring from a neighbor, this does not mean that the offspring is necessarily improving the actual solution of p i since the sender PU has only a copy of p i 's solution which may be outdated at the time the new offspring was computed. In addition, if a PU p i updates its solution because it received an improving offspring, then PU p i needs to inform its neighbors. This is handled using the f lag variable. Another important point is the update of the reference point (z ) required by the Chebyshev function. In our implementation, each PU relies only on the information received from neighbors. To terminate the description of our scheme, we also notice that every process needs to initialize the local copies of its neighbors. This is performed before starting the main optimization loop by making every PU generating an initial solution for its sub-problem, and then sending it to its neighbors.

All along the previous description, each PU was assumed to optimize a single sub-problem. It should be clear that the scenario where population size is much larger than the number of available PUs can also be captured by simply partitioning the population accordingly and modifying our protocols to handle the local copies of neighboring sub-problems being at the frontier of each partition. It should also be clear that such a scenario would be much more favorable and less challenging. In fact, our preliminary experiments showed that the resulting workload is less fine-grained and maintaining the local state at each PU's partition is less critical. We however choose to focus on the most harsh scenario where every PU is handling one single solution in order to push our scheme to its limits and to fairly appreciate its strengths and weaknesses.

IV. EXPERIMENTAL STUDY

A. Experimental Setup 1) ρMNK-Landscapes:

To analyze the behavior of our approach, we consider combinatorial bi-objective ρMNKlandscapes with a broad range of instances with different structures and sizes. The family of ρMNK-landscapes constitutes a problem-independent model used for constructing multi-objective multi-modal landscapes with objective correlation [START_REF] Verel | On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives[END_REF]. A multi-objective ρMNK-landscape aims at maximizing an objective function vector f : {0, 1}

N → [0, 1] M . Solutions are binary strings of size N . The parameter K defines the number of variables that influence a particular position from the bit-string (the epistatic interactions). By increasing the number of variable interactions k from 0 to (N -1), landscapes can be gradually tuned from smooth to rugged. The objective correlation parameter ρ defines the degree of conflict between the objectives. The positive (resp. negative) data correlation allows to decrease (resp. increases) the degree of conflict between the objective function values. This has an impact on the cardinality of the Pareto front [START_REF] Verel | On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives[END_REF]. We investigate 50 random ρMNK-landscapes with ρ ∈ {-0.8, -0.4, 0.0, 0.4, 0.8}, M = 2, N ∈ {128, 256, 512, 1024, 2048} and K ∈ {4, 8}.

2) Parameter setting: We deploy our scheme on top of the Grid5000 French grid [START_REF]Grid'5000 French national gird[END_REF]. We use a number of µ = 128 cores (using a cluster of 46 times 2 CPUs Intel@2.83GHz, 4 cores/CPU), which also corresponds to the population size used in all our experiments. Our synchronous and asynchronous implementations are based on the C++ MPI library. The conventional sequential MOEA/D [START_REF] Zhang | MOEA/D: A multiobjective evolutionary algorithm based on decomposition[END_REF] is also considered as a baseline algorithm. All approaches use an independent bitflip mutation with a rate 1/N and one-point crossover with probability 0.9. The initial population is generated randomly. The stopping condition is set to µ • 10 4 evaluation function calls. Based on preliminary experiments, we investigate a neighborhood size T ∈ {3, 5, 7} and t max ∈ {1, 2, 3, 4, 5, 6}. Overall, we tested 1 950 different configurations, each one executed 30 times. Due to space limitations, we only highlight a subset of settings allowing us to state our findings.

B. Impact of Synchronicity

1) Approximation Quality: We follow the performance assessment design proposed in [START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF] using the hypervolume difference and the multiplicative epsilon indicators [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF] which are both to be minimized. The hypervolume difference indicator (I - H ) gives the difference between the portion of the objective space that is dominated by a Pareto set approximation and some reference set. The reference point is set to the worst value obtained over all approximations, and the reference set is the best-found approximation over all tested configurations. The epsilon indicator (I × ε ) gives the minimum multiplicative factor by which the approximation set has to be translated in the objective space in order to weakly dominate the reference set.

In Table I, we show a representative subset of results assessing the approximation quality of MP-MOEA/D when compared against the conventional MOEA/D. The sign " " (resp. "∇", "≈") indicates that the algorithm in the column outperforms (resp. is outperformed by, equivalent to) MOEA/D significantly using a Wilcoxon signed ranked test with a pvalue of 0.05. We can see that synchronous MP-MOEA/D is the best performing algorithm. It is able to significantly improve upon the standard MOEA/D w.r.t. both the epsilon and hypervolume indicators in 25 out of 50 instances, while never being worst. The asynchronous implementation provides less impressive results since it improves upon MOEA/D on 7 instances, while being worst in also 7 instances (w.r.t. both indicators). It is also clear that the difference between MP-MOEA/D and MOEA/D is more substantial when considering higher dimensions, no matter whether the synchronous or the asynchronous implementation is considered.

Remember that the only difference between the synchronous and the asynchronous implementation is that in the former PUs have the guarantee to receive fresh information about neighbors states after every local computation stage, whereas in the latter, PUs do not spend time waiting for this information. Hence, these first observations show that synchronicity in the distributed update stage is a critical point in terms of approximation quality. However, as analyzed below, synchronicity comes with a running time penalty.

2) Running Time and Parallel Efficiency: In Fig. 1, we report some observations rendering the interrelation between parallel running time and approximation quality. On the left column of Fig. 1, we can appreciate the acceleration obtained by our implementations where we also vary the neighborhood size. The acceleration is measured as the ratio between the sequential running time of MOEA/D and the parallel running time of MP-MOEA/D. First, we can see that the asynchronous MP-MOEA/D is substantially faster. Second, we observe that the acceleration depends on the neighborhood size and also on the instance dimension. This is better illustrated in Fig. 2 where acceleration is analyzed as a function of the problem size. In fact, the evaluation cost increases with the problem dimension, thus making the relative cost of communication lower, and then leading to more significant accelerations. Moreover, larger neighborhoods imply a lager amount of communication, and thus less parallel efficiency. Notice however that even for the smallest instances of size N = 128 and the largest neighborhood, asynchronous MP-MOEA/D is still able to obtain significant accelerations while being very competitive in terms of approximation quality. This can be seen in the two last columns of Fig. 1 where the approximation quality of the synchronous and asynchronous implementations compared to sequential MOEA/D is well maintained.

3) Discussion: From the previous subset of results, we can conclude that there is a non-trivial trade-off to attain w.r.t. approximation quality and speed-up when parallelizing MOEA/D; which is well captured by our synchronous and asynchronous MP-MOEA/D. Actually, the previous analysis holds for t max = 1, which means that PUs distributively update their respective states immediately after performing one single evolutionary step. Like for synchronicity, controlling the number of steps a PU is authorized to perform in parallel before attempting to distributively update its neighbors has a deep impact on the type of trade-offs our MP-MOEA/D scheme is able to provide. This is analyzed in the rest of the paper.

C. Impact of Workload Granularity

We start by examining the acceleration we are able to obtain as a function of parameter t max . This is illustrated in Fig. 3 where one can additionally appreciate the relative impact of synchronicity and neighborhood size. We can see that larger t max -values lead to better speed-ups, which can clearly be attributed to the fact that workload granularity increases as a function of t max , thus reducing the relative cost of distributed communications. However, one may wonder the impact on quality. In order to better analyze the so-obtained trade-offs, we consider approximation quality (indicator's value) and acceleration as the couple of goals one would like to achieve simultaneously. This is illustrated in Fig. 4 where each point represents the acceleration (x-axis) and the approximation quality (y-axis) corresponding to one value of t max (reported as a label in the figure), and where the horizontal line with thick contour represents the average approximation quality obtained by the sequential MOEA/D with a 95% confidence interval. Roughly speaking, and since the quality indicators are to be minimized, the points being below this line indicate that MP-MOEA/D is competitive compared to MOEA/D. Similarly, since acceleration is to be maximized (with an ideal value at 128), points being farther on the right-side of each subfigure indicate better parallel efficiency.

Several insightful observations can be extracted from the figure. Firstly, there is a general tendency that approximation quality drops with higher t max -values, whereas acceleration becomes better. The interesting observation is that there exists values for which quality is very competitive to sequential MOEA/D with substantial improvements in acceleration. In particular, when considering small-size instances, for which relatively high speed-ups are more difficult to achieve since the evaluation function cost becomes relatively low compared to communication cost, we observe that the impact of t max on quality is less pronounced. Hence, larger t max -values have the overall effect of significantly improving acceleration without a substantial drop in terms of speed-up. Notice for example that speed-ups of up to 70 can be obtained with a quality being similar to MOEA/D for N = 128 whereas a speed-up of only 10 to 20 is obtained with t max = 1. Secondly, the obtained tradeoffs are surprisingly dependent on the correlation between the objective functions, especially for large-size instances. In fact, the more correlated the objective functions, the harder it is to obtain higher acceleration without a significant drop in performance. We attribute this to the fact that for such an objective correlation, an improving offspring solution found at some PU with respect to a given sub-problem, is more likely to dominate neighboring solutions, and thus to subsequently produce new improving offspring that speed-up the convergence of the optimization of neighboring sub-problems. Hence, communicating improving offspring solutions immediately, as they are discovered at every PU, is more critical for approximation quality. This is less likely for anti-correlated instances for which the size of the Pareto front is larger, and where diversity can balance this side-effect. Notice also that the more conflicting the objectives, and the larger the instances, the more the asynchronous dominates the synchronous MP-MOEA/D in both approximation quality and acceleration. For example, for such configurations, asynchronous MP-MOEA/D is able to attain a near linear acceleration of about 100 while being as good as MOEA/D in terms of approximation quality.

V. CONCLUSIONS AND PERSPECTIVES

The study conducted in this paper provides new insights into the benefits of using parallel and distributed computations within the MOEA/D framework. Besides being able to provide high-quality approximation and acceleration, the proposed MP-MOEA/D distributed scheme and its message passing implementations allow us to better harness the key ingredients for a successful distributed deployment of decomposition-based approaches, and to elicit in a comprehensive manner the different trade-offs attainable at a large-scale distributed setting. The extensive experiments conducted on top of a real distributed testbed and the throughout analysis, show that MP-MOEA/D is able to counteract the fine-grained parallelism exposed by the original sequential MOEA/D framework. Our results are in fact obtained under the very harsh assumption that the number of available PUs are equal to the population size. It is our opinion that relaxing this assumption would hopefully lead to better trade-offs; however, it would be worthwhile conducting a new experimental study to complement our results when varying the number of sub-problems handled at each PU.

In addition, a natural, but challenging, open question is whether there exist other distributed strategies allowing to enhance acceleration while providing similar approximation quality. We believe in fact that there are still some opportunities to extend and to improve our MP-MOEA/D and its implementations in order to address this issue An interesting idea would be to continuously self-adjust the t max -value (instead of fixing it), as a function of the offspring improvement observed both locally at every processing units and remotely when performing distributed updates from neighboring processes.

Algorithm 2 : 3 ; 4 if 5 ; 6 Send 12 ; // Update local solution 13 x;Algorithm 3 : 3 if flag = 1 then 4 Msg[ 0 ] 6 ; 7 Send

 234561213334067 DISTRIBUTED UPDATE: Synchronous message-passing implementation // Notify neighbors 1 for j ∈ B(i) \ {i} do 2 if flag = 1 then Msg[0] ← x i ; x j = y j then Msg[1] ← y j ; (Non-blocking) Msg to pj; // Wait for neighbors' notifications 7 flag ← 0; 8 for j ∈ B(i) \ {i} do 9 Wait until reception (Blocking) of Msg from pj; // Update neighbor's copy 10 v ← Msg[0];11 if v = ∅ then x j ← v; ← Msg[1]; 14 if x = ∅ and g te (x, λ i ) < g te (x i , λ i ) then15 x i ← x; flag ← 1; // Update local reference point 16 for m ∈ {1, . . . , M } do 17 if z m < vm then z m ← vm; 18 ; 19 if z m < xm then z m ← xm; 20 DISTRIBUTED UPDATE: Asynchronous message-passing implementation // Differences with Algo.2 are highlighted 1 for j ∈ B(i) \ {i} do 2 if x j = z j or flag = 1 then ← i ; Msg[1] ← x i ; 5 if x j = y j then Msg[2] ← y j ; (Non-blocking) Msg to pj; // Check for neighbors' notifications 8 flag ← 0; 9 while There is a pending message Msg do 10 j ← Msg[0] ;

Fig. 1 .Fig. 2 .

 12 Fig. 1. Acceleration (Left side) vs. Approximation quality (Right side) for ρMNK-landscapes with ρ = 0.0 and K = 4; tmax = 1.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Acceleration as a function of tmax for ρMNK-landscapes with ρ = 0.0, K = 4 and N ∈ {128, 256, 512, 1024, 2048} resp., from left to right.

TABLE I .

 I APPROXIMATION QUALITY OF MOEA/D vs. MP-MOEA/D FOR T = 5 AND tmax = 1. A LOWER INDICATOR-VALUE INDICATES A BETTER PERFORMANCE. THE AVERAGE VALUE AND THE STANDARD DEVIATION (IN BRACES, WITH A MULTIPLICATIVE FACTOR OF 10 2 ) ARE REPORTED.

	N	K	ρ	MOEA/D	Hypervolume Difference (I -H ) MP-MOEA/D Synchronous Asynchronous	MOEA/D	Epsilon Indicator (I × ε ) MP-MOEA/D Synchronous Asynchronous
	128	4 -0.8	0.013 (0.25) 0.013 (0.19) ≈ 0.015 (0.23) ≈	1.054 (1.15) 1.046 (1.02)	1.055 (1.33) ≈
	128	4 -0.4	0.017 (0.36) 0.017 (0.29) ≈ 0.021 (0.37) ∇	1.054 (1.00) 1.049 (0.67) ≈ 1.060 (1.07) ∇
	128	4	0.0	0.020 (0.30) 0.017 (0.29)	0.018 (0.22) ≈	1.073 (1.43) 1.059 (0.85)	1.068 (1.13) ≈
	128	4	0.4	0.011 (0.24) 0.010 (0.27) ≈ 0.010 (0.22) ≈	1.051 (1.09) 1.046 (1.26) ≈ 1.047 (0.79) ≈
	128	4	0.8	0.005 (0.15) 0.004 (0.12)	0.005 (0.12) ≈	1.047 (1.38) 1.035 (0.95)	1.043 (1.07) ≈
	128	8 -0.8	0.016 (0.27) 0.016 (0.28) ≈ 0.019 (0.23) ∇	1.070 (1.24) 1.058 (1.41)	1.071 (1.43) ≈
	128	8 -0.4	0.020 (0.24) 0.018 (0.34) ≈ 0.023 (0.29) ∇	1.064 (0.86) 1.057 (1.06)	1.069 (0.88) ∇
	128	8	0.0	0.021 (0.41) 0.022 (0.32) ≈ 0.022 (0.36) ≈	1.073 (1.55) 1.077 (1.35) ≈ 1.078 (1.19) ≈
	128	8	0.4	0.016 (0.31) 0.015 (0.31) ≈ 0.015 (0.18) ≈	1.068 (1.25) 1.064 (1.30) ≈ 1.065 (0.94) ≈
	128	8	0.8	0.007 (0.21) 0.007 (0.14) ≈ 0.006 (0.12) ≈	1.052 (1.66) 1.057 (1.19) ≈ 1.047 (1.05) ≈
	256	4 -0.8	0.010 (0.18) 0.011 (0.22) ≈ 0.013 (0.16) ∇	1.055 (1.11) 1.041 (0.96)	1.055 (1.18) ≈
	256	4 -0.4	0.013 (0.17) 0.012 (0.20)	0.014 (0.24) ≈	1.059 (1.05) 1.043 (0.71)	1.050 (0.87)
	256	4	0.0	0.011 (0.19) 0.010 (0.22)	0.012 (0.17) ≈	1.050 (0.79) 1.041 (0.77)	1.049 (0.81) ≈
	256	4	0.4	0.008 (0.16) 0.007 (0.18) ≈ 0.008 (0.13) ≈	1.045 (1.07) 1.039 (0.72)	1.044 (0.68) ≈
	256	4	0.8	0.004 (0.10) 0.003 (0.10) ≈ 0.004 (0.08) ≈	1.037 (1.06) 1.033 (0.96) ≈ 1.038 (0.92) ≈
	256	8 -0.8	0.010 (0.22) 0.010 (0.18) ≈ 0.013 (0.16) ∇	1.053 (1.26) 1.042 (0.90)	1.056 (0.95) ≈
	256	8 -0.4	0.013 (0.20) 0.013 (0.23) ≈ 0.014 (0.24) ≈	1.054 (0.69) 1.044 (0.77)	1.049 (0.85)
	256	8	0.0	0.028 (0.65) 0.024 (0.53)	0.027 (0.57) ≈	1.285 (1.88) 1.274 (1.41)	1.277 (1.61) ≈
	256	8	0.4	0.008 (0.21) 0.009 (0.17) ≈ 0.009 (0.21) ∇	1.042 (1.11) 1.045 (0.75) ≈ 1.049 (0.87) ∇
	256	8	0.8	0.004 (0.12) 0.004 (0.10) ≈ 0.004 (0.12) ≈	1.039 (1.23) 1.038 (1.06) ≈ 1.041 (1.18) ≈
	512	4 -0.8	0.008 (0.14) 0.008 (0.12) ≈ 0.010 (0.14) ∇	1.053 (1.01) 1.029 (0.43)	1.043 (1.25)
	512	4 -0.4	0.011 (0.15) 0.009 (0.19)	0.012 (0.16) ≈	1.056 (0.73) 1.038 (0.64)	1.045 (0.53)
	512	4	0.0	0.009 (0.15) 0.007 (0.16)	0.009 (0.14) ≈	1.048 (0.78) 1.034 (0.65)	1.043 (0.46)
	512	4	0.4	0.007 (0.13) 0.006 (0.16)	0.007 (0.10) ≈	1.045 (0.59) 1.036 (0.81)	1.040 (0.46)
	512	4	0.8	0.003 (0.07) 0.003 (0.09) ≈ 0.003 (0.06) ≈	1.031 (0.62) 1.028 (0.84) ≈ 1.032 (0.67) ≈
	512	8 -0.8	0.008 (0.14) 0.008 (0.13) ≈ 0.010 (0.10) ∇	1.056 (0.98) 1.031 (0.46)	1.045 (0.72)
	512	8 -0.4	0.010 (0.15) 0.008 (0.16)	0.011 (0.13) ≈	1.056 (0.78) 1.035 (0.54)	1.041 (0.43)
	512	8	0.0	0.010 (0.14) 0.009 (0.16) ≈ 0.011 (0.13) ∇	1.050 (0.75) 1.042 (0.81)	1.047 (0.51) ≈
	512	8	0.4	0.006 (0.13) 0.005 (0.13)	0.007 (0.13) ∇	1.037 (0.75) 1.033 (0.68)	1.042 (0.73) ∇
	512	8	0.8	0.003 (0.09) 0.003 (0.09) ≈ 0.003 (0.07) ≈	1.033 (0.96) 1.030 (0.86) ≈ 1.036 (0.82) ≈
	1024	4 -0.8	0.007 (0.09) 0.006 (0.07)	0.008 (0.11) ∇	1.063 (0.70) 1.028 (0.34)	1.039 (0.57)
	1024	4 -0.4	0.009 (0.13) 0.007 (0.10)	0.008 (0.09)	1.061 (0.40) 1.039 (0.65)	1.038 (0.60)
	1024	4	0.0	0.008 (0.15) 0.007 (0.11)	0.008 (0.09) ≈	1.049 (0.65) 1.041 (0.63)	1.040 (0.44)
	1024	4	0.4	0.005 (0.11) 0.004 (0.11)	0.005 (0.08) ≈	1.036 (0.52) 1.029 (0.52)	1.033 (0.48)
	1024	4	0.8	0.003 (0.08) 0.002 (0.08)	0.003 (0.05) ≈	1.023 (0.69) 1.021 (0.70) ≈ 1.029 (0.66) ∇
	1024	8 -0.8	0.007 (0.09) 0.007 (0.06)	0.008 (0.08) ∇	1.058 (0.67) 1.029 (0.33)	1.040 (0.83)
	1024	8 -0.4	0.010 (0.10) 0.009 (0.09)	0.009 (0.11)	1.061 (0.60) 1.051 (0.92)	1.043 (0.49)
	1024	8	0.0	0.008 (0.11) 0.006 (0.12)	0.008 (0.09)	1.053 (0.65) 1.042 (0.90)	1.041 (0.33)
	1024	8	0.4	0.006 (0.10) 0.005 (0.10)	0.006 (0.08) ≈	1.036 (0.63) 1.035 (0.71) ≈ 1.039 (0.45) ∇
	1024	8	0.8	0.002 (0.07) 0.002 (0.06)	0.003 (0.06) ∇	1.020 (0.55) 1.017 (0.54)	1.029 (0.64) ∇
	2048	4 -0.8	0.007 (0.08) 0.005 (0.05)	0.007 (0.05) ∇	1.074 (0.79) 1.036 (0.43)	1.039 (0.45)
	2048	4 -0.4	0.009 (0.09) 0.007 (0.10)	0.008 (0.07)	1.075 (0.72) 1.057 (1.06)	1.043 (0.68)
	2048	4	0.0	0.009 (0.10) 0.006 (0.07)	0.007 (0.05)	1.057 (0.46) 1.049 (1.05)	1.047 (0.46)
	2048	4	0.4	0.006 (0.08) 0.003 (0.08)	0.005 (0.06)	1.035 (0.45) 1.031 (0.76)	1.035 (0.48) ≈
	2048	4	0.8	0.003 (0.09) 0.002 (0.06)	0.004 (0.07) ∇	1.020 (0.50) 1.018 (0.49) ≈ 1.026 (0.47) ∇
	2048	8 -0.8	0.007 (0.06) 0.005 (0.05)	0.007 (0.05) ≈	1.070 (0.54) 1.033 (0.37)	1.039 (0.44)
	2048	8 -0.4	0.008 (0.04) 0.007 (0.06)	0.007 (0.07)	1.072 (0.34) 1.053 (0.99)	1.037 (0.43)
	2048	8	0.0	0.008 (0.08) 0.006 (0.09)	0.006 (0.07)	1.060 (0.38) 1.047 (0.80)	1.039 (0.40)
	2048	8	0.4	0.005 (0.07) 0.004 (0.07)	0.005 (0.05)	1.036 (0.43) 1.036 (0.64) ≈ 1.036 (0.45) ≈
	2048	8	0.8	0.002 (0.06) 0.002 (0.06) ≈ 0.003 (0.05) ∇	1.016 (0.34) 1.018 (0.65) ≈ 1.028 (0.42) ∇

Notice that this is a harsh assumption which allows us to fairly study the scalability of our scheme with very fine-grained computations.