Quentin Baert

Anne-Cécile Caron

Maxime Morge

Jean-Christophe Routier
email: christophe.routier@univ-lille.fr

Kostas Stathis
email: kostas.stathis@rhul.ac.uk

Anne-Cécile Caron

{quentin Baert

Maxime Anne-Cecile Caron

Jean Morge

An adaptive multi-agent system for task reallocation in a MapReduce job

Keywords: Artificial Intelligence, Multi-agent systems, Negotiation, MapReduce, BigData

Introduction

Data science involves the processing of large volumes of data which requires distributed file system and parallel programming. This emerging distributed computing topic brings new challenges related to task allocation and loadbalancing. The adaptivity of these systems to various settings without configuration requiring user expertise, and their responsiveness to rapid changes need to be improved. This paper is concerned with a class of practical applications where (a) the resources (e.g. data) required to successfully execute a task are distributed among nodes, (b) some of these nodes may encounter potential execution hazards, e.g. slowing down nodes or communication lags and (c) the number of tasks prevents from using a centralized approach to compute the allocation. As several resources are necessary to perform a task, any allocation inevitably requires fetching some of these resources from other nodes, thus incurring an extra time cost for task execution [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF]. In this class of applications the task allocation can be challenged during their executions and should capitalize upon the way resources are distributed in the system.

In this class of practical applications, we consider here MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] which is the most prominent distributed data processing model for tackling vast amount of data on commodity clusters. Tasks are divided into a set of map tasks and reduce tasks that are distributed on nodes. The task allocation among the reducers is a priori fixed by the partition function. For instance, the partition number is the hash value of the key modulus the number of partitions according to the default partition of the most popular implementation Hadoop [START_REF]The Apache Software Foundation, Apache Hadoop[END_REF]. Such a task allocation can be problematic. Firstly, several data skews in the MapReduce applications lead to an unbalanced workload during the reduce phase [START_REF] Kwon | Skewtune: mitigating skew in mapreduce applications[END_REF][START_REF] Kwon | Managing skew in Hadoop[END_REF].

Secondly, an unfair allocation can occur during the reduce phase due to the heterogeneous performance of nodes. Thirdly, the load-balancing can be challenged by some rapid performance variations due to exogenous reasons.

In order to tackle the problem of load-balancing and task allocation in applications such as those that motivate this work, multi-agent technologies have received a lot of attention [START_REF] Agnetis | Multiagent Scheduling -Models and Algorithms[END_REF]. A multi-agent system is a decentralized system where multiple agents take local decisions based on their perceptions of the environment such that a solution to a complex problem can emerge from the interactions between simple individual behaviours [START_REF] Ferber | Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence[END_REF]. Most of the existing works adopting the market-based approach [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF][START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF][START_REF] Turner | Distributed Strategy Adaptation with a Prediction Function in Multi-Agent Task Allocation[END_REF] model the load-balancing problem as a non-cooperative game in order to optimize user-centric metrics rather than system-centric ones such as the global runtime considered in this paper.

We assume that agents are cooperative, viz.: they share the same objective, minimizing the global runtime. We also assume there is no shared knowledge, including any knowledge about the whole task allocation. However, agents have a model of their peers, i.e. they are able to compute the cost of tasks for their peers. We further assume, as required by our practical application, that a task can be performed by any single agent without preemption and precedence order.

A task is indivisible, with no deadline and not shareable i.e. a task belongs to only one agent at a time.

In this paper, we formalize the multi-agent situated task allocation problem. We propose a dynamic and on-going task reallocation process which takes place concurrently with the task execution and so the distributed system is adaptive to disruptive phenomena (e.g. slowing down nodes). When agents locally identify opportunities within a current unbalanced allocation, they trigger concurrent and one-to-many negotiations to reallocate some tasks. Apart from decentralization, i.e. avoiding performance bottlenecks due to global control, we show here that a multi-agent approach for situated task allocation supports two additional crucial requirements (a) concurrency -where task reallocation and task executions are concurrent, and (b) adaptation -where task reallocation is triggered when a disruptive event is performed. This paper significantly extends our previous works. Contrary to [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF], we do not assume that each task has an intrinsic cost (e.g. the number of data to process) but the location of resources is taken into account. Beyond [START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF], we introduce here a multi-auction process which allows an agent to bid in several concurrent negotiations in order to improve the responsiveness of the system. Additionally, we present a vast panel of experiments in order to empirically evaluate (a) the adaptivity of our multi-agent system in an heterogeneous environment, (b) the responsiveness of the multi-agent system due to the multi-auction process, and (c) the adequacy of the agent strategy with respect to the computing infrastructure. Specifically, our contributions are as follows:

• We formalize the multi-agent situated task allocation problem where tasks have different costs for different agents due to the resource locality.

• We design a multi-agent version of the MapReduce pattern in a distributed system setting which solves the partitionning data skew problem. The task reallocation process based on concurrent negotiations between agents occurs all along the MapReduce job processing to cope with a continuously evolving environment.

• We conduct extensive experiments on real-world datasets. The experimental results show that our method improves the runtime with a negligible computational overhead and it mitigates the heterogeneity of the computational environment.

The paper is structured as follows. Section 2 overviews relevant related works. Section 3 defines the socially rational task delegation considered by the agents in order to locally improve the task allocation. Section 4 sketches the negotiation process which is concurrent with task consumptions. Section 5 specifies the strategies, i.e. how agents choose which task to perform/negotiate.

Our practical application and empirical evaluation are described in Section 6.

Finally, Section 7 summarizes our contribution and outlines our future work.

Related work

The context of this paper is a single MapReduce job. In this context the problem of task scheduling consists of assigning map and reduce tasks as suggested by Selvitopi et al. in [13]. This problem should not be confused with that of job scheduling, where one considers the allocation and the usage of the resources in case of multiple MapReduce jobs as discussed by Banerjee and Hecker in [START_REF] Banerjee | A multi-agent system approach to load-balancing and resource allocation for distributed computing[END_REF]. Several common data skews in the MapReduce applications are identified in [START_REF] Kwon | Skewtune: mitigating skew in mapreduce applications[END_REF][START_REF] Kwon | Managing skew in Hadoop[END_REF] which lead to an unbalanced workload during the data processing. In this paper, we focus on the partitioning skew leading to an unbalanced allocation among the nodes where the reduce phase is slowed down since it is penalized by the most loaded reducer. This data skew is tackled by [START_REF] Chen | SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment[END_REF][START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF] using parametrization based on prior knowledge about the data and the distributed computing environment. Every reduce task is scheduled in [START_REF] Hammoud | Center-of-Gravity Reduce Task Scheduling to Lower MapReduce Network Traffic[END_REF] according to the data skew and the data locality without modifing the partition. In this paper, we address the partitionning data skew with the dynamic and adaptative task reallocation which is concurrent with the task consumption. Thus, reallocation is adaptative to the data processing. This enables us to tackle the following real-world issues: (a) the lack of prerequisite knowledge over the data and the processing, (b) the inaccurate estimation of task execution time, and (c) the execution hazards (slowing down nodes, communication lag). To the best of our knowledge, no other proposal is scalable and responsive, like ours.

We provide here a comparison of our work with the most significant existing methods for task allocation and load-balancing which is summarized in Table 1.

This analysis grid classifies these works according to the crucial aspects which are requested by our practical application: the deployment of the MapReduce design pattern for processing large datasets. Classical scheduling problems have been the subject of extensive research producing offline schedulers for some simple models [START_REF] Chen | scheduling: Complexity, algorithms and approximability[END_REF]. The problem of minimizing the makespan (the completion time of the last task to perform) with n tasks on m unrelated machines (i.e. with different capabilities), denoted R||C max , is NP-hard [START_REF] Horowitz | Exact and approximate algorithms for scheduling nonidentical processors[END_REF]. Pseudo-polynomial algorithms developed for this problem include: the earliest completion time heuristic (ECT) proposed by Ibarra and Kim in [START_REF] Ibarra | Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors[END_REF], two-phase heuristics based on linear programming suggested by Lenstra et al. in [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF], the local search heuristics proposed by Hariri and Potts in [START_REF] Hariri | Heuristics for scheduling unrelated parallel machines[END_REF], and the branch and bound algorithm applied by Martello et al.

in [START_REF] Martello | Exact and approximation algorithms for makespan minimization on unrelated parallel machines[END_REF]. These centralized algorithms and the most recent ones [START_REF] Mokotoff | Parallel machine scheduling problems: A survey[END_REF], even the ECT heuristic which is an approximation algorithm giving acceptable results with very small computational requirements, cannot be applied to our scenario with a large number of tasks (e.g. 100, 000 keys in Sec. 6). The strategies presented in Sec. 5 are decentralized local search heuristics.

Multi-agent scheduling [START_REF] Agnetis | Multiagent Scheduling -Models and Algorithms[END_REF] has received significant attention for load-balancing problems in distributed systems, but it is different from the classical scheduling problems due to the following aspects:

• Decentralization: global control causes a performance bottleneck as it must collect status information of the entire system in real time. Instead, task allocation can be negotiated by agents representing the nodes. For instance, Jiang et al. propose in [START_REF] Jiang | Task allocation for undependable multiagent systems in social networks[END_REF] a negotiation reputation-based allo-cation mechanism for load-balancing in order to reduce the resource access time and so the responding time.

• Adaptation: classical scheduling problems are static. The inaccurate estimation of tasks execution time and the disruptive phenomena (task consumption, slowing down nodes, etc.), may require major modifications in the existing allocation to stay optimal. Di and Wang introduce in [START_REF] Di | Decentralized proactive resource allocation for maximizing throughput of P2P Grid[END_REF] a self-adaptive system to implement a high adaptable task allocation to a dynamic environment. Turner et al. combine in [START_REF] Turner | Distributed Strategy Adaptation with a Prediction Function in Multi-Agent Task Allocation[END_REF] supervised classification learning with an internal decision-making process for task assignments. Schaerf et al. investigate in [START_REF] Schaerf | Adaptive load balancing: A study in multi-agent learning[END_REF] the adaptive behaviour of agents for efficient load-balancing using multi-agent reinforcement learning. These methods cannot be used for the class of practical applications we are concerned since neither generalizable predictive patterns nor prior model of the data/environment are available.

The enormous amount of varying related studies (see [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF] for a recent survey) mainly distinguish themselves through the following aspects:

• Objectives: the makespan minimization is the most widely applied optimization objective for task allocation. Selvitopi et al. [START_REF] Selvitopi | Locality-aware and loadbalanced static task scheduling for mapreduce[END_REF] propose a task scheduling to minimize the makespan however the allocation is made once for all before the reduce phase while our method challenges the allocation all along the process. Minimizing the total or mean response time of all tasks means minimizing the waiting time of tasks. The throughput measures the number of tasks completed per time unit. The reliability measures the probability that the tasks can be successfully executed. Attiya and Hamam distinguish in [START_REF] Attiya | Task allocation for maximizing reliability of distributed systems: A simulated annealing approach[END_REF] the node-related reliability, i.e. the reliability of resources/computation and the path-related reliability, i.e.

the reliability of communications.

• Distribution: some resources are placed at the nodes and can be accessed and shared to execute the tasks. For this purpose, the location of agents and the accessibility of required resources should be considered which is not the case of most of the task allocation algorithms. In [START_REF] Jiang | Contextual resource negotiation-based task allocation and load balancing in complex software systems[END_REF], Jiang and

Jiang consider that the number of allocated tasks on a node is proportional to its own resources and the resources of its interacting nodes. Jiang and Li propose in [START_REF] Jiang | Locality-sensitive task allocation and load balancing in networked multiagent systems: Talent versus centrality[END_REF] a locality-sensitive resource allocation model which takes into account the distance between the nodes and the locality of resources.

Jiang and Zhichuan present in [START_REF] Jiang | The rich get richer: Preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching[END_REF] a task allocation mechanism based on the contextual resources: if a node has richer experiences of executing tasks, the node may have higher access to the resources. In this paper, the nodes are equidistant from each other in a fully connected physical and social network. The efficiency of a task allocation depends both on the proportion of resources (data) which are local and their intrinsic talent (CPU).

• Cooperation: Garg et al. distinguish in [START_REF] Garg | Double auction-inspired meta-scheduling of parallel applications on global grids[END_REF] the meta-schedulers which optimize system-centric metrics and the most recent ones focusing on usercentric metrics. Most of the latter adopts the market-based approach: they model the load-balancing problem as a non-cooperative game. Walsh and Wellman present in [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF] a task allocation protocol among agents which acquire and provide goods on behalf of consumers or producers. Kraus et al.

consider in [START_REF] Kraus | Coalition formation with uncertain heterogeneous information[END_REF] that, even if each agent tries to maximize its benefits, they need to cooperate to perform tasks. An et al. propose in [START_REF] An | Automated negotiation with decommitment for dynamic resource allocation in cloud computing[END_REF] a distributed negotiation mechanism where selfish agents negotiate over resources both a contract price and a decommitment penalty. Penmatsa and Chronopoulos formulate in [START_REF] Penmatsa | Game-theoretic static load balancing for distributed systems[END_REF] the load balancing problem as a non-cooperative game among the users who try to minimize the expected response time of their own tasks. Fewer works are based on cooperative agents which negotiate to address system-centric metrics such as the global runtime we consider in this paper. For instance, Shehory and Kraus consider in [START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF] that task assignments to groups of agents as necessary since tasks cannot be performed by a single reliable agent. By contrast, we assume here that a task, which can be performed by any single agent without preemption and precedence order, is indivisible, not shareable (i.e. a task belongs to only one agent at a time) and with no deadline.

Situated task allocation

We formalize here the multi-agent situated task allocation (MASTA) problem where tasks have different costs (runtime) for different agents due to the resource locality.

Definition 1 (MASTA). A multi-agent situated task allocation problem of size (k, m, n) with k ≥ 1, m ≥ 2 and n ≥ 1 is a tuple M AST A = N ode, A, T , l, d, c such that: • N ode = {node 1 , . . . , node k } is a set of k nodes;
• A = {1, . . . , m} is a set of m agents;

• T = {τ 1 , . . . , τ n } is a set of n tasks to perform;

• l : A → N ode is a function which returns the location of an agent;

• d : T × N ode → N + is a function which specifies how many resources for a task are on a particular node;

• c : T × N ode → R * + specifies the cost of a task τ at a given location such that the tasks are cheaper when the required resources are more local ones:

∀i, j ∈ A, d(τ, l(i)) > d(τ, l(j)) ⇒ c i (τ, l(i)) ≤ c(τ, l(j)) (1)
In the rest of the paper, l i , c i (τ ) and

d i (τ ) denote l(i), c(τ, l i ) and d(τ, l i ),
respectively. Similarly, we denote

d τ = node∈N ode d(τ, node). We say that τ is local, partially local, or distant for agent i if d i (τ ) = d τ , d i (τ ) < d τ , or d i (τ ) = 0, respectively.
In the following of this section, we consider a particular MASTA problem and we evaluate the task allocation from a collective viewpoint by considering the maximum completion time, i.e. the makespan.

Definition 2 (Task allocation, workload and makespan). A task allocation P is a partition of tasks among agents, i.e a set of m task bundles {P (1), . . . , P (m)} such that:

∪ i∈A P (i) = T (2) ∀i ∈ A, ∀j ∈ A \ {i}, P (i) ∩ P (j) = ∅ (3)
The workload of the agent i ∈ A in the allocation P is defined as:

w i (P ) = τ ∈P (i) c i (τ ) (4)
The makespan of P is defined as:

C max (P ) = max{w i (P ) | i ∈ A} (5)
Let us consider the following walk-through example.

Example 1 (Task allocation, workload and makespan). Let The agents modify the task allocation by negotiating task delegations. The delegation δ of the task τ from agent i to agent j aims at improving the makespan, i.e the load-balancing between the two agents. The following definition formalizes the required conditions for an effective task delegation.

M AST A ex =< N ode, A, T , l, d, c > a problem of size (2, 2 , 7)
Definition 3 (Socially rational task delegation). Let P be a task allocation. The delegation δ of the task τ from agent i to agent j is defined s.t. the resulting allocation δ(P ) = {P (1), . . . , P (m)} is as follows:

∀k ∈ A \ {i, j}, P (k) = P (k) (6)
P (i) = P (i) \ {τ } ∧ P (j) = P (j) ∪ {τ } ( 7
)
The delegation is socially rational iff:

w j (P ) + c j (τ ) < w i (P ) (8)
Since a socially rational task delegation δ strictly decreases the local makespan between the two agents, it does not increase the global makespan (C max δ(P ) ≤ C max (P )).

We can now denote Γ i (P ) the set of socially rational task delegations that an agent i can trigger:

Γ i (P ) = {τ ∈ P (i) | ∃j ∈ A \ {j}, w j (P ) + c j (τ ) < w i (P )} (9)
A task allocation P is said stable if no agent can trigger a socially rational task delegation.

Example 2 (Socially rational task delegation). Let δ 1 be the delegation of the task τ 6 from agent 1 to agent 2 in the example 1 which leads to the task allocation P = δ 1 (P ). Since w 1 (P ) = 38 and w 2 (P ) = 40, δ 1 improves the makespan: C max (P ) = 40 < C max (P ) = 46. However P is not stable.

Let P = δ 2 (P ) be the task allocation where δ 2 is the delegation of τ 1 from agent 2 to agent 1. Even if P is not optimal (C max (P ) > C max (P mks)), P is stable. Figure 1 depicts the workloads of the two agents after the delegations

δ 1 and δ 2 .
It is worth noticing that the load-balancing process which consists of a sequence of socially rational delegations is finite. Property 1 (Load-balancing process). An unstable task allocation can always lead to a stable one using a finite number of socially rational task delega-250 tions.

Proof 1 (Load-balancing process). Let P a task allocation and W P =< w i1 , . . . , w im > the vector of the workloads in decreasing order where w ir denotes the r th largest workload. If P is not stable, there exists a socially rational task delegation δ which leads to P = δ(P ). Formally, 255 ∃i, j ∈ A, max w i (P ), w j (P ) < max w i (P ), w j (P ) (10)

∧∀k ∈ A \ {i, j}, w k (P ) = w k (P ) (11)
It implies that W P < W P in the lexicographic order. Formally,

∃r ∈ [1, m] ∀r < r, W P (r ) = W P (r ) ∧ W P (r) < W P (r)
Since there is a finite number of allocations and the order is strict, there is a finite number of socially rational task delegations.

Negotiation process

We sketch here the repeated negotiations process which is concurrent with task execution. When a task is consumed, it will be removed from the set of tasks, and so the multi-agent system aims at minimizing the makespan of the current allocation for this new MASTA problem.

The execution of a task is a disruptive event which modifies the MASTA problem and the task allocation.

T = T \ {τ } (12)
P (i) = P (i) \ {τ } (13) ∀j ∈ A \ {i}, P (j) = P (j) (14)
A sequence of task consumptions removes all the tasks from the initial allocation until a final empty one, denoted ⊥. Obviously, a task consumption may decrease the makespan.

Decentralized task delegation process. Agents operate in concurrent, oneto-many and single-round negotiations for task delegations. Each negotiation, which is based on the Contract Net Protocol [START_REF] Smith | The contract net protocol: High-level communication and control in a distributed problem solver[END_REF], includes three decision steps:

(a) the choice of the task to negotiate by the strategy of the initiator described in Section 5, (b) the refusals/bids from the peers which check the social rationality of the task delegation, and (c) the selection of the winning bid by the initiator.

We consider here that the initiator selects the bidder with the smallest workload in order to decrease the makespan. Since there is no shared knowledge, an agent has partial and not necessarily true beliefs about the current allocation P . Indeed, agent i knows its own workload w i (P ) and it has a belief base:

B i (P ) = w i 1 (P ), . . . , w i i-1 (P ), w i i+1 (P ), . . . , w i m (P ) [START_REF] Chen | SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment[END_REF] where w i j (P ) is the belief of the agent i about the workload of agent j in the allocation P .

The set of potential socially rational task delegations Γ B i (P ) that an agent i can initiate in the task allocation P is based on its belief base B i (P ). Formally,

Γ B i (P ) = {τ ∈ P (i) | w i j (P ) + c j (τ ) < w i (P )}. ( 16
)
If Γ B i (P ) = ∅, then agent does not initiate negotiations. The computation of the local makespan by the initiator of a negotiation is also based on its belief base, possibly inaccurate. This is the price to pay for decentralization. However, an agent informs its peers about its workload when it is triggered for the first time, within the negotiation messages, and after each task execution. Therefore, the belief base of the peers is updated. It follows that a successful negotiation can only reach a socially rational task delegation, and so tends to improve the makespan. When an agent, according to its belief base, identifies opportunities within a current unbalanced allocation, it initiates negotiations. These local decisions promote the adaptivity of the multi-agent system.

Concurrent consumptions and delegations. Task delegations and task consumptions are concurrent and complementary operations since a task removal may be an opportunity for new socially rational task delegations. Figure 2 represents the influence of these operations over the path from the initial allocation P 0 until the final one ⊥. Agents perform socially rational task delegations to improve the makespan (e.g. the path from P 0 to P k ) until a task consumption (e.g. the edge from P k to P 0 ), which eventually interrupts the path toward a stable allocation (e.g. the path from P k to P 0 represented in grey). A task consumption may occur when the agents have reached a stable allocation (e.g. P stable ) or not (e.g. P k ). we introduce here a multi-auction process which allows agent to bid in several concurrent negotiations as in [START_REF] Alrayes | Concurrent bilateral negotiation for open e-markets: the CONAN strategy[END_REF] in order to improve the responsiveness of the system. In this way, as stated by our empirical results in Section 6, the gap between the most loaded reducer and the least loaded one is filled faster and so the load-balancing process is faster.

Multi-auction.

In order to tackle the eager bidder problem [START_REF] Schillo | The eager bidder problem: a fundamental problem of dai and selected solutions[END_REF], we adopt a conservative approach which warrants that the task delegations are socially rational. For this purpose, a bidder computes an overhead.

Definition 5 (Overhead). Let P be an allocation, D ⊂ T the tasks which are currently negotiated and D j the set of pending tasks for which the agent j has made proposal. The overhead of the agent j is:

v j (D) = Σ τ ∈Dj c j (τ ) (17)
The potential workload of the agent j, which represents its workload if it wins all the auctions in which it is involved (w j (P )+v j (D)), allows a bidder not to be too optimistic and to make proposals which only lead to socially rational task delegations. In order to evaluate the delegation of the task τ from the agent i, the bidder j adopts the following strategy:

• either w j (P ) + c j (τ ) ≥ w i (P ) so the bidder declines the delegation which is not socially rational;

• or w j (P )+c j (τ ) < w i (P ) ≤ w j (P )+v j (D)+c j (τ ) so the bidder postpones the evaluation of the delegation which depends on the outcomes of the pending negotiations;

• or w j (P )+v j (D)+c j (τ ) < w i (P ) so the bidder makes a proposal since the task delegation is socially rational whatever the outcomes of the pending negotiations are. Then,

v j (D ∪ {τ }) = v j (D) + c j (τ ) (18)
Moreover, the bidder informs the initiator about its potential workload.

In the latter case, when the negotiation closes:

• either the bidder is selected (P j = P j ∪ {τ }) and its workload is updated w j (P ) = w j (P ) + c j (τ );

• or it is not the case (P j = P j ), its workload remains the same w j (P ) = w j (P ).

In both cases, the overhead is updated:

v j (D) = v j (D ∪ {τ }) -c j (τ ) (19)
Finally, the pending delegations are re-evaluated.

Example 3 (Multi-auction). Let P be an allocation among the set of agents A = {1, 2, 3, 4, 5, 6} such that the workloads are: We focus here on the overhead of the agent 1 and it influence over the negotiations. We assume the agents 2, 3, 4, 5 and 6 ask for the delegation of the tasks τ 2 , τ 3 , τ 4 , τ 5 and τ 6 respectively. The cost of these tasks for the agent 1 are:

c 1 (τ 2 ) = 6 c 1 (τ 3 ) = 2 c 1 (τ 4 ) = 4 c 1 (τ 5 ) = 3 c 1 (τ 6 ) = 3
Figure 3 illustrates the evolution of the overhead for the agent 1 during its interactions with its peers. The agent 1 can make a proposal to the agents 2 and 3

(messages 2 and 4). However, the delegation requested by the agent 4 (message 5), which is not socially rational, is declined (message 6). The agent 1 must postpone the evaluation of the delegations from the agents 5 and 6 (messages 7

and 8) which depends on the previous pending negotiations. When the delegation of the task τ 2 is confirmed (message 10), the agent 1 can decline the delegation of τ 5 (message 11) but the social rationality of the delegation of the task τ 6 is neither excluded nor confirmed. Finally, when the delegation of the task τ 3 is rejected (message 12), the agent 1 can make a proposal about τ 6 (message 12).

Strategies

Since task delegations and task consumptions are concurrent, the strategy of an agent must select the next task to perform/delegate.

Definition 6 (Strategy).

Let P be an allocation, the strategy of the agent i is the couple (perf orm i , negotiate i ) where:

• perf orm i : P (i) → T ∪ {⊥}, selects the next task to perform or none

(denoted ⊥) if P (i) = ∅; • negotiate i : Γ B i (P ) → T ∪ {⊥}, selects the next task to negotiate or none if Γ B i (P ) = ∅.
It is worth noticing that the delegation which is selected by the strategy must be a potential socially rational one. In the following, we propose two strategies.

While the local agnostic strategy is only based on the cost function, the locationaware one takes into account the location of the required resources.

Local agnostic strategy. By adopting the principle "consume small, delegate big", an agent performs the smallest task in its bundle and negotiate the largest one which may lead to a potential socially rational delegation. For this purpose, this strategy only requires that the agent sorts the tasks according to their costs. We can notice that the consideration of the resource fetching time by this strategy is implicit since an agent should perform first the local tasks which may cost more for its peers and delegate first the distant tasks which may cost less for its peers. The following strategy makes this principle explicit.

Location-aware strategy. According to this strategy, an agent performs first the large local tasks and it negotiates first the large distant ones based on its local beliefs and knowledge. This strategy is built on a data structure, called local-aware bundle.

Firstly, the local availability ratio measures the locality of tasks:

Definition 7 (Local availability ratio). The local availability ratio of the agent

i for the task τ is defined as:

o i (τ ) = d i (τ ) d τ (20)
The maximum local availability ratio for the task τ is:

ô(τ ) = max i∈A {o i (τ )} (21)
The local availability ratio of an agent i for a task is the ratio between the number of local resources and the total number of resources for this task.

Secondly, the local-aware bundle of agent i, which is depicted in Figure 4, is divided in three subbundles in accordance with the local availability ratios of the agent for the tasks:

1. The maximum local bundle contains the tasks such that agent i owns at least one resource and there is no other agent which owns more resources for this task. The tasks are sorted by decreasing order of cost (cf. left of

Results and discussion

After introducing our practical application, we describe our prototype and we discuss our empirical results.

Practical application

We consider as a practical application the distributed deployment of the MapReduce design pattern in order to process large datasets on a cluster [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF], as with Hadoop [START_REF]The Apache Software Foundation, Apache Hadoop[END_REF]. A MapReduce job consists of two successive phases: map and reduce. During the map phase, nodes filter in parallel input data and generate key-value pairs written into data chunks. Each data chunk is located on the same node as the mapper which has generated it. During the reduce phase, nodes process in parallel the keys and their individual lists of values.

The reduce phase of a MapReduce job can be formalized by a MASTA problem N ode, A, T , l, d, c (cf. Definition 1) where: N ode is the set of nodes in the cluster, A is the set of reducer agents, T is a set of reduce tasks, l captures the fact that we put one reducer per node in our experiments and d considers the data location. In conformance with Equation 1, we specify the cost of a task τ for an agent i as follows:

c i (τ ) = ρ is a chunk for the task τ c i (ρ), with c i (ρ) =      |ρ| if ρ is local for i κ × |ρ| otherwise ( 22
)
where |ρ| denotes the number of values for the chunk ρ and κ captures the resource fetching time. We empirically set up κ = 2 for a cluster and κ = 10 when we use a network of computers. Our experiments show that the cost function does not need to be carefully tuned since the adaptivity of our dynamic task reallocation process allows to mitigate an inaccurate cost function.

Implementation

We have developed a multi-agent version of the MapReduce pattern in a distributed system setting using the MAS4Data testbed [START_REF] Baert | MAS4Data: Multiagent systems for processing very large datasets[END_REF]. MAS4Data is implemented in Akka [START_REF] Lightbend | Akka toolkit[END_REF] for highly concurrent, distributed, and resilient messagedriven applications. Even if fault-tolerance of nodes is out of the scope of this paper, we assume that the message transmission delay is arbitrary but not negligible and that messages may be lost. These are the reasons why we have included acknowledgments and deadline mechanisms in the interaction protocol. In order to decrease the complexity related to the design of a reducer agent, we have adopted a modular agent architecture that allows the concurrency of the negotiations and the tasks performance, as well as the separation between communicative and decision-making behaviours.

Empirical results

This section starts by explaining the experimental setting in details, which includes the choice of the metrics, the datasets and the jobs. Then, we report on the experimental results.

Metrics. In order to evaluate the runtime and the fairness of our experiments we have introduced in our previous works [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF][START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF] the following metrics:

• The contribution of a reducer is the sum of the costs of the tasks it has performed;

• The contribution fairness is the ratio between the minimum and the maximum contributions of the agents;

• The runtime of the reduce phase is the runtime of the reducer which finished last;

• The time fairness is the ratio between the runtime of the slowest reducer and the runtime of the fastest one.

While the contribution of a reducer corresponds to its ex-post workload (see Definition 2), the runtime effectively measures the makespan. The closer to 1 the contribution fairness and time fairness are, the fairer is the allocation. In other words, we want to keep every agent as busy as all the other ones, thus sharing as much as possible the workload of the application.

Setup. We consider here two different hardware configurations: (a) a cluster with 10 blades, each having 10 CPUs with 512Go RAM; (b) a network of 16 PCs with 4 cores Intel(R) i7 and 16GB RAM each. Since we obtain similar results

with the second configuration, we present here the experiments on the cluster with an exception for the last experiment which compares the two configurations.

We use two distinct real-world datasets. The first dataset (2.4 Gb) contains 100, 480, 507 ratings that 480, 189 users gave to 17, 770 movies [START_REF] Bennett | The netflix prize[END_REF] [dataset].

The job, called RecByMov, counts the number of rankings per movie. The second dataset (977 Mb) contains 3, 963, 480 weather records (station id, timestamp, temperature, rainfall, etc.) from 62 stations taken during the last 20 years [START_REF]Données synop essentielles omm[END_REF] [dataset]. The job, called RecByTempSta, counts the number of records per half degree of temperature and per station. In order to increase the volume of data without slowing down the mapping phase (which is out of the scope of this paper) and without changing the data distribution, we replicate k times the number of values for each key: k = 200 for the job RecByTempSta and k = 20

for the job RecByMov. Whatever the job and the datasets are, we use as many mappers as reducers and each experiment is run 30 times. Due to the observable nondeterminism of distributed execution, we comment distinctive runtimes.

Figure 5 shows the initial workloads for these two jobs with the default Hadoop partition function, i.e. the hashcode of the key modulo the number of reducers. While the first partition is well balanced, the second one is intentionally caricatural2 since half of the reducers have no task to perform. The latter highlights the partitioning skew [START_REF] Kwon | Skewtune: mitigating skew in mapreduce applications[END_REF][START_REF] Kwon | Managing skew in Hadoop[END_REF] since half of the reducers execute no task. Empirical results . Firstly, our experiments aims at validating our approach.

We show that: (a) the negotiation improves the makespan and so the runtime with a small overhead cost for the negotiation, and (b) our multi-agent system is adaptive to performance variations and heterogeneous environments. We adopt by default the local agnostic strategy and the multi-auction process. Secondly, we evaluate these choices.

Negotiation improves the runtime. Negotiation is beneficial whether or not the initial allocation is fair. In order to validate this hypothesis, we compare the contribution fairness, the time fairness and the runtime of jobs with/without negotiations. Note that, throughout the paper, whenever we use the term "without negotiation" we refer to results obtained "with the classical Hadoop".

Empirical result 1. The negotiation improves the runtime due to the loadbalancing of the reducers contributions.

Figure 6 shows that a job can strongly benefit from the negotiations. Starting from an initial unfair allocation (cf. Figure 5b), we execute 30 times the job RecByMov with 10 reducers on 10 homogeneous nodes. During the data processing, task delegations occur since the workloads are unbalanced. The most loaded reducers propose tasks which are accepted by the less loaded ones. Finally, the contributions are fairly distributed among the nodes and all the reducers terminate at the same time since the fairnesses are close to 1 (cf. Figures 6a and6b).

Therefore, the makespan (cf. Figure 6d) and so the runtime (cf. Figure 6c) are more than halved.

Empirical result 2. When the initial allocation is fair, the overhead of the negotiation is negligible and it does not affect the runtime.

Figure 7 shows that a job cannot be penalized by the negotiations. Starting from an initial fair allocation (cf. Figure 5a), we execute 30 times the job RecByTempSta with 8 reducers on 8 homogeneous nodes. Since the initial allocation is fair, it is not surprising that the contribution fairness (cf. Figure 7a)

and the time fairness (cf. Figure 7b) are quite good even without negotiation, i.e. close to 0.85. However, they are still improved by negotiation since the makespan can be slightly decreased (cf. Figure 7d). Therefore, the runtime is about 7% faster with negotiation (cf. Figure 7c). It is worth noticing that no negotiation is triggered when the agents believe that the allocation is stable. These two experiments validate that our adaptive dynamic process based on concurrent negotiations for tasks reallocation improves the runtime even if the initial allocation is fair. The first experiments demonstrates how MAS4Data

tackles the partitioning skew. The second one highlights that the overhead of negotiation is negligible with respect to the benefit of the load-balancing.

Negotiation mitigates heterogeneity. The heterogeneity of a computational environment comes from a permanent non-uniformity of the processing capabilities of the nodes or a temporary one due to exogenous reasons (e.g. the slowdown of a node).

Empirical result 3. The negotiation allows in an heterogeneous environment to reallocate the tasks to the fastest nodes in order to improve the runtime.

Figure 8 shows that the multi-agent system adapts the allocation to runtime hazards. Starting from an initial fair allocation (cf. Figure 5a), we execute 30 times the job RecByTempSta with 8 reducers. Indeed, only one CPU is activated on each node and the first reducer cannot use more than 50% of the CPU time. Therefore, the seven other reducers run faster. The initial fair allocation is challenged by the slower reducer. Without negotiation (cf. Figure 8c), seven reducers terminate after 130 seconds while the slower reducer ends after 300 seconds and so the time fairness is low (around 0.43). By contrast, the negotiation allows the slower reducer to terminate after 150 seconds like the other ones (cf. Figure 8d). The time fairness is very close to 1 since some negotiations are triggered during the job processing for load-balancing. Thanks to this dynamic and continuous task reallocation process, the job is not penalized by the slower node and the job runs two times faster due to the negotiations. Finally, the contribution of the slower reducer is lower than the contributions of the other ones (cf. Figure 8b), and so the contribution fairness is low, approximately 0.35 (cf. Figure 8a).

This experiment shows that the negotiation process mitigates the impact of a runtime hazard which slows down one reducer. A reducer which is slowed down can delegate some tasks in order to execute the job as soon as possible. Figure 9 shows that the multi-agent system adapts the allocation to heterogeneous environment. Starting from an initial fair allocation (cf. Figure 5a), we execute 30 times the job RecByTempSta with 8 reducers. Indeed, only one CPU is activated on each node, four reducers run on the same node and four reducers contributions of the others (cf. Figure 9d), and so the contribution fairness is low. a g e n t 1 a g e n t 2 a g e n t 3 a g e n t 4 a g e n t 5 a g e n t 6 a g e n t 7 a g e n t 8

Contribution

(d) The contributions These two experiments validate that a job running in an heterogeneous en- Adequacy of the strategy with respect to the infrastructure. We assume that the efficiency of the location-aware strategy depends on the resource fetching time.

Empirical result 5. The location-aware strategy improves the runtime when the extra cost for fetching resources is significant.

Figure 11 shows that the efficiency of the negotiation strategy depends on the hardware configurations. We have generated a dataset (8 Gb) with 82, 283 keys such that the initial task allocation for the job RecByKey can be challenged. In order to evaluate the impact of the proximity between data resources and processing nodes on the runtime, most of the data required for a task are not located on the same node as the assigned reducer (See [START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF] of more details). With a network of computer, the location-aware strategy significantly improves the runtime with respect to the local agnostic strategy, around -7.6%

(cf. Figure 11a). By contrast, the local agnostic strategy is more efficient within a cluster (cf. Figure 11b). Indeed, the cost of fetching distant resources from other nodes in a network of computers has a real impact and so the local execution of tasks speeds up the runtime. By contrast, this extra cost for task execution is low within a cluster. We experimentally measure it to be around 10%. Moreover, it is worth noticing that the locality is implicitly taken into account in the local agnostic strategy since the underlying cost function is defined such that the tasks are cheaper when the required resources are more local ones (cf. Equation 1).

Whatever the dataset and the job are, we observe that the location-aware strategy is the best strategy over a network of computers while the local agnostic strategy is more suitable on a cluster.

Conclusion

In this paper, we have proposed a multi-agent system for task reallocation among distributed nodes based on the location of the required resources to perform these tasks in order to minimize the makespan. In particular, we have applied our negotiation framework for load-balancing the reduce phase in the distributed MapReduce model in order to process large datasets.

Our prototype has been empirically evaluated. Our experiments show that MAS4Data is adaptive to the partitioning skew, an heterogeneous computing environment, and any potential execution hazards. This is due to the fact that the negotiation process improves the runtime due to the load-balancing of the reducers contributions. Some of our experiments suggest that future work should consider: (a) task swaps to improve the makespan of stable allocations and (b) task bundles in order to speedup the negotiation process. MAS4Data is scalable since it tackles a large number of tasks due to the local decisions of agents about the next task to delegate/perform. Moreover, the overhead of the negotiation is negligible with respect to the benefit of the load-balancing since the task reallocation is concurrent with the task consumption and no negotiation is triggered when the agents believe that the allocation is stable. Indeed, our method is not a scheduling algorithm which allocate the tasks once and for all but an ongoing distributed strategy attempting to repair a potential unbalanced partition.

From the user perspective, even if our adaptive and dynamic approach tackles the problem of performance drop, the fault tolerance can still be achieved through data replication. It is worth noticing that MAS4Data does not require expertise for the parametrization due to its adaptivity. Even if the choice of the strategy depends on the hardware configuration, no other parameter needs to be carefully tuned such as the replication factor (by default the value 3 in HDFS [START_REF]The Apache Software Foundation, Apache Hadoop[END_REF]). A sensitivity analysis to study the influence of this parameter has been beyond the scope of this work, but it is certainly worth of further investigation.

Generally, future work must consider here the continuous arrival of complex jobs concurrently submitted by several users. Our study focuses on the reassignment of independent fine-grained tasks in a single job during their execution.

In order to fill this granularity gap, the formal framework must be extended and the optimization objective to be considered should be the mean flowtime of several concurrent jobs i.e. the mean of the maximum completion times of dependent tasks in these jobs.

Grant

This work is supported by the CNRS Challenge Mastodons and the call ULille "Internationalisation Actions bilatérales". We thank the anonymous reviewers for their stimulating comments which help us to improve the paper.

  , where N ode = {node 1 , node 2 }, A = {1, 2} and T = {τ 1 , . . . , τ 7 } with l(1) = node 1 and l(2) = node 2 . The locations of the tasks and their costs are represented in

  Pmks and P be two task allocations such that Pmks = {{τ 1 , τ 3 , τ 5 , τ 6 }, {τ 2 , τ 4 , τ 7 }} and P = {{τ 2 , τ 4 , τ 6 }, {τ 1 , τ 3 , τ 5 , τ 7 }}. Pmks is optimal since w 1 (Pmks) = 33 and w 2 (Pmks) = 35 and so C max (Pmks) = 35. As shown at top of Figure1, it is not the case of P since w 1 (P ) = 46, w 2 (P ) = 27 and so C max (P ) = 46.

Figure 1 :

 1 Figure 1: The workloads of the agents 1 and 2 for the allocations P (at top), P (at bottom left) and P (at bottom right) in our walk-through example.

  Formally, Definition 4 (Task consumption). Let P be the current task allocation for the problem M AST A = N ode, A, T , l, d, c . The consumption γ of the task τ by the agent i leads to the task allocation P = γ(P ) for the problem M AST A = N ode, A, T , l, d, c such that:

Figure 2 :

 2 Figure 2: Concurrent task consumptions (vertical edges) and task delegations (horizontal edges).

w 1 (

 1 P ) = 30 w 2 (P ) = 45 w 3 (P ) = 39 w 4 (P ) = 28 w 5 (P ) = 34 w 6 (P ) = 40

Figure 4 ); 2 . 3 .

 423 Figure 4); 2. The intermediate local bundle contains the tasks which are partially local.The tasks are sorted by decreasing order of local availability ratio and the tasks with the same local availability ratio are sorted in decreasing order of cost (cf. center of Figure4);

Figure 4 :

 4 Figure 4: The local-aware bundle contains the maximum local bundle (at left), the intermediate local bundle (at center) and the distant bundle (at right). The rectangle size represents the cost of the task. The arrows depict the order in which an agent looks for a task to perform/negotiate.

Figure 5 :

 5 Figure 5: The allocation for our two jobs with the classical Hadoop

Figure 6 :Figure 7 :

 67 Figure 6: The median metrics and their standard deviations depicted in boxplots (a,b,c), and the contributions after negotiation for a distinctive execution of the job RecByMov (d).

Figure 8 :

 8 Figure 8: The median contribution fairness and its standard deviations depicted in boxplots (a), the contributions (b) for a distinctive execution of the job RecByTempSta when a node is slowed down, the evolution of the workloads without negotiation (c) and with negotiation (d).

Figure 9 :

 9 Figure 9: The median metrics and their standard deviations depicted in boxplots (a, b, c) and the contributions after negotiation for a distinctive execution of the job RecByTempSta in an heterogeneous environment (d).

Figure 10 :

 10 Figure 10: The initial workloads, the contributions and the workloads for a distinctive execution of the job RecByKey with single-auction (b and d) or multi-auction (c and e).

Figure 11 :

 11 Figure 11: The runtimes for a distinctive job on a network of computers (a) and on a cluster (b).

Table 1 :

 1 Analysis grid of related works according to the main aspects.

		Decentralization Adaptation	Cooperation Distribution	Objectives
	Ibarra and Kim [18]	-	-	-	-	Makespan minimization
	Lenstra et al. [19]	-	-	-	-	Makespan minimization
	Hariri and Potts [20]	-	-	-	-	Makespan minimization
	Martello et al. [21]	-	-	-	-	Makespan minimization
	Jiang [22]			-		Response time
	Selvitopi et al. [13]		-	-		Makespan minimization
	Di and Wang [23]					Throughput
	Turner et al. [10]				-	Throughput
	Schaerf et al. [24]					Throughput
	Jiang and Jiang [25]					Throughput
	Jiang and Li [26]					Response time minimization
	Jiang and Zhichuan [27]					Response time minimization
	Walsh and Wellman [8]			-		An allocation
	Kraus et al. [28]			-	-	An allocation
	An et al. [29]			-		Response time minimization
	Penmatsa and Chronopoulos [30]		-	-	-	Response time minimization
	Shehory and Kraus [9]				-	Makespan minimization
	MAS4Data					Makespan minimization

Table 2 .

 2 Let τ 1 τ 2 τ 3 τ 4 τ 5 τ 6 τ 7

	d 1 (τ k ) 1	0	3	6	1	6	0
	d 2 (τ k ) 0	4	6 12 4	1	7
	c 1 (τ k ) 1	8 15 30 9	8 14
	c 2 (τ k ) 2	4 12 24 6 13 7

Table 2 :

 2 Locations and costs of tasks

For this purpose, we consider Double for the type of the keys, i.e. the movie ids.

run on separate nodes. As previously, the contribution fairness with negotiation is worst since the four slower reducers perform less task than the others. Once again, the dynamic and continuous task reallocation process allows the time fairness to reach approximately 1 and the job runs five times faster due to the negotiations. Finally, the contribution of the slower reducers is lower than the vironment benefits from the adaptivity of our multi-agent system. When a performance variation brings to an unbalanced allocation, our continuous and dynamic process detects it and triggers the reallocation of tasks toward the fastest nodes leading to the speedup of the runtime.

Single-auction versus multi-auction. We assume that our multi-auction process, which allows agents to bid in several concurrent negotiations, improves the responsiveness of the multi-agent system.

Empirical result 4. The multi-auction process reaches faster stable allocation.

Figure 10 shows that the multi-agent system adapts the allocation faster with a multi-auction process. We have generated a dataset (775 Mb) with 100, 000, 000 lines such that the initial task allocation is unfair. The job, called

RecByKey, counts the number of values per key. We use 8 reducers in an homogeneous environment where none task is assigned to the first reducer while 100, 000 tasks with 1, 000 values per task are assigned to the others reducers which have similar workloads (cf. Figure 10a). As in the previous experiments, the negotiation improves the load-balancing (cf. Figure 10b and10c). However, the multi-auction process is more efficient. While the multi-auction process needs 50 seconds to reach a fair allocation (cf. Figure 10e), the workload of the first agent remains close to 0 during the whole reduce phase with the single-auction process (cf. Figure 10d). Actually, the tasks are delegated in the single-auction process to the first reducer one after the other and they are instantly performed.

By contrast, this agent continuously bids in seven simultaneous auctions during the multi-auction process. Therefore, the data processing with a single-auction process (∼ 275s) is around 10% slower than with a multi-auction one (∼ 245s).

Finally, the contribution fairness is around 0.3 with a single-auction while it is close to 0.85 with a multi-auctions process.

This experiment shows that the multi-auction process speeds up the loadbalancing process and so improves the responsiveness of the multi-agent system.


Ific Goudé

Jérémy Lacoche

Rémi Cozot

Tone mapping High Dynamic 3D scenes with global lightness coherency

Tone mapping high dynamic 3D scenes with global lightness coherency

Ific Goudé, Jérémy Lacoche, Rémi Cozot

Introduction

In computer graphics, High Dynamic Range (HDR) images of 3D scenes are rendered with all perceptible dark and bright details that befall in the real world. However, displaying such HDR images on standard screens or Head-Mounted Displays (HMDs) is impossible because of their limited dynamic range. To overcome this limitation and to be able to watch HDR contents on Standard Dynamic Range (SDR) displays, the high dynamic range of these contents is compressed to fit the limited dynamic range of the display. This operation is ensured by a Tone Mapping Operator (TMO) that seeks to preserve as best as possible global and local contrasts.

In this paper, we tackle real-time tone mapping of HDR rendering of 3D scenes taking into account both spatial and temporal coherency. Such applications like video games involve a camera moved by a user through a 3D scene. At each frame, the part of the scene that stands in front of the camera is rendered in HDR. The HDR image is then tone mapped and displayed onto a SDR display (or a HMD). As described later in the paper, processing each image independently without accounting for spatial or temporal coherency may produce visual artifacts Boitard et al. (2014a) which degrades the image quality. We propose a tone mapping method which accounts for the whole scene to ensure a spatial and temporal co-herency. That way, our TMO allows content consumers to better feel the lighting atmosphere of the scene and avoids visual artifacts such as flickering effect.

Furthermore, in order to demonstrate the efficiency of our TMO, we conducted a user study to evaluate the fidelity of tone mapped content with respect to the HDR reference using different TMOs. Compared to other methods, we found that our TMO better preserves fidelity and is more appreciated. While our TMO works for interactive rendering of 3D scenes displayed on 2D screens, we focused on Virtual Reality (VR) contents because of the growth of this technology and the challenge of the existing tone mapping operators to target the limited dynamic range of today's HMDs. Moreover, in the VR use case, the user, and consequently the camera, is constantly moving, which increases artifacts occurrence and degrades the immersion feeling. Finally, we propose a new subjective study protocol to compare HDR content visualized on a 2D display with its tone-mapped version visualized on a HMD.

The paper is organized as follows. Section 2 presents related work regarding real-time tone mapping. In section 3, we detail an existing TMO dedicated to the visualization of 360 • HDR images on HMDs [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF] and we propose different changes to adapt this TMO to the problem of walking through 3D scenes rendered in HDR. The implementation of our TMO is detailed in section 4 while some results are presented in section 5. Finally, we describe the subjective study we conducted to evaluate our solution over previous TMOs in section 6. Limits and future work are discussed in section 7 to conclude the paper.

Related work

The research in the field of TMOs started many years ago and has given rise to many different methods. The main purpose is to visualize HDR images, while preserving all details and contrasts on a display with a lower dynamic range. It amounts to a compression problem with loss, that seeks to preserve global and local contrasts as better as possible. We can distinguish two main groups of TMOs: global ones process all pixels of an image with the same operator, while local ones process each pixel according to its neighborhood [START_REF] Reinhard | High dynamic range imaging: acquisition, display, and imagebased lighting[END_REF]; [START_REF] Banterle | Advanced high dynamic range imaging[END_REF]. Many TMOs are based on the Human Visual System (HVS) sensitivity and on how the HVS accommodates to bright and dark luminances to produce a pleasant and coherent tone mapped image. HVS lightness perception has long been studied and can be simulated using mathematical models. The logarithm of the luminance seems to fit well with the perceived lightness [START_REF] Fechner | Elements of psychophysics[END_REF][START_REF] Fairchild | Color appearance models[END_REF]. Tone mapping an HDR image using the logarithm of the luminance compresses its dynamic range by coherently preserving the perceived contrast. A common way to tone map HDR images is to find a luminance of adaptation to transform the input image luminance to an output luminance on the display [START_REF] Ferwerda | A model of visual adaptation for realistic image synthesis[END_REF]; [START_REF] Pattanaik | A multiscale model of adaptation and spatial vision for realistic image display[END_REF]. More specifically, few TMOs simulate the visual adaptation over time to improve the feeling of contrast when visualizing a sequence of tone mapped images [START_REF] Pattanaik | Time-dependent visual adaptation for fast realistic image display[END_REF]; [START_REF] Ledda | A local model of eye adaptation for high dynamic range images[END_REF]. Another way to improve the contrast for scenes with very high luminances is to simulate the maladaptation phenomenon [START_REF] Pajak | Visual maladaptation in contrast domain[END_REF]; [START_REF] Ritschel | A computational model of afterimages[END_REF]; E. [START_REF] Jacobs | Simulating the visual experience of very bright and very dark scenes[END_REF]. This effect occurs when a visible area is bleached after having looked at something very bright (the sun for example). During few seconds, colors and local contrasts are lost in this view area.

More recently, many works have tackled TMOs for HDR videos Boitard et al. (2014b); [START_REF] Aydin | Temporally coherent local tone mapping of hdr video[END_REF]; [START_REF] Eilertsen | Real-time noise-aware tone mapping[END_REF]. Video tone mapping operators have to cope with spatio-temporal coherency issues Boitard et al. (2014a). A complete survey on video tone mapping has been proposed by [START_REF] Eilertsen | A comparative review of tone-mapping algorithms for high dynamic range video[END_REF], it especially details methods that take temporal coherency into account. For example, Zonal Brightness Coherency TMO proposed by Boitard et al. Boitard et al. (2014b) processes the tone mapping of a video by considering spatio-temporal segments to preserve the temporal coherency and avoid incoherent luminance changes. However, this solution cannot be used for real-time tone mapping of HDR images rendered from a 3D scene as the whole video sequence has to be known. [START_REF] Eilertsen | Real-time noise-aware tone mapping[END_REF] proposed a real-time noise-aware tone mapping that answers the main issues of temporal consistency described by Boitard et al. Boitard et al. (2014a). Nevertheless, this TMO requires too much processing power to be processed in real-time and does not care about object brightness consistency.

Another TMO proposed by [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF] addresses the issue of spatial coherency in the case of still HDR panoramas visualized on HMDs. In that case, the sequence of successive viewport images is unknown and the tone mapping has to be applied in real-time. The authors propose to apply two different TMOs, a first one to the whole panorama that preserves the global coherency and a second one to the viewport image only to enhance the local contrast. The viewport TMO is smoothed over time to mimic the eye accommodation to the luminance level and consequently avoid the flickering effect produced by sudden changes in the image. The final tone mapped image is a combination of both TMOs in the logarithmic domain.

Durand and Dorsey [START_REF] Durand | Interactive tone mapping[END_REF] proposed an Interactive tone mapping that simulates the visual adaptation. This TMO is dedicated to interactive walk in a 3D scene rendered in HDR and tone mapped on the fly. They added a post processing pass that accounts for chromatic adaptation and adds flares around light sources to increase the brightness effect. Due to visual adaptation, this TMO ensures temporal coherency but does not take into account the whole scene to tackle the spatial coherency.

Recall that our objective is to walk through a 3D scene, render it in real-time from the current camera, tone map the resulting HDR viewport image (which corresponds to the current position of the camera) and display it on an SDR screen, while preserving spatial and temporal coherency. Spatial coherency is obtained by accounting for the luminance of the whole scene. Temporal coherency is ensured by efficiently smoothing transitions between successive views. In this work, the image sequence is unknown because the camera is controlled by the user and the lighting conditions of the scene may change over time (turning on and off light sources, moving objects, etc.) Our solution relies on a combination of two TMOs as described by [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF].

The first one is a global TMO that takes into account the luminance distribution of the whole scene to preserve the spatial and temporal coherency, while a second TMO, that only considers the image rendered on the viewport, enhances the local contrast and the temporal coherency. A more detailed description of our method is given in the following section.

3 Dynamic Range of a 3D scene

Problem statement

A previous work about tone mapping 360 • HDR images raises the issues of spatial and temporal coherency when these images are visualized on a HMD [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF]. At each time step, only a part viewport of the 360 • image is displayed on the HMD, corresponding to where the user is looking at. To visualize these limited parts of the 360 • image one after the other, a naive approach is to tone map each viewport image individually. This way, each current image in the viewport is well tone mapped but the sequence visualized as a whole can suffer from temporal incoherence. Indeed, the used TMO is based on a global operator proposed by [START_REF] Reinhard | Photographic tone reproduction for digital images[END_REF] that computes luminance values of the HDR image: the log-luminance average and the maximum luminance value. If sudden changes in luminance happen from a view to another, the operation of tone mapping can produce flickering artifacts that breaks the temporal coherency. The solution initially proposed by [START_REF] Yu | Dynamic tone mapping with head-mounted displays[END_REF] is to smooth the tone mapping values over time in order to mimic the way the human eyes accommodate to bright and dark luminances. In this way, flickering artifacts are avoided by the smooth transitions and the temporal coherency is then preserved. Nevertheless, processing each image in the viewport irrespective of the entire 360 • image tends to produce tone mapped images with the same overall luminance average. Dark areas of the 360 • image will be brightened while bright areas will be darkened. Thus, the spatial coherency of the 360 • image is lost because all areas will be rendered with the same average luminance.

Goudé et al. proposed to solve the problem of spatial coherency by applying a TMO to the entire 360 • image. Tone mapping the entire 360 • image in one go with the same global operator [START_REF] Reinhard | Photographic tone reproduction for digital images[END_REF] preserved the spatial coherency. Dark areas are still dark on the tone mapped image. Moreover, there is no more problem of temporal coherency (like flickering effect) as the tone mapping is applied once. Tone mapping the entire 360 • image only once could solve the incoherence issues but it is to the detriment of reducing the used dynamic range of the tone mapped image in the viewport. Effectively, the dynamic range of a 360 • image can be potentially much higher than a limited area of the same image in the viewport. Reducing the used dynamic range leads to a reduced contrast in the tone mapped image that degrades the visual quality. The authors suggest to keep advantages of those two TMOs by combining them together.

Finally, a smoothed TMO applied to the viewport enhances the contrast and is temporally coherent while a TMO applied to the 360 • image preserves the spatial coherency. Combining these two TMOs provides a balanced result. The global TMO can be processed once at the start and the viewport TMO is processed at each time step. To obtain a coherent tone mapped image, the combination is performed in the logarithmic domain (as explained in section 4). This approach (called HMD-TMO from now on) can be reused in the case of interactive HDR rendering of 3D scenes. Indeed, the viewport TMO can be used as is for each frame, while the global one has to be modified because the luminances of a 3D scene differs from the luminance of a 360 • image. For this reason, HMD-TMO cannot be adapted to 3D scenes, it is then not evaluated in our study. The adaptation of HMD-TMO to 3D scenes is the objective and the main contribution of the paper; it is detailed in the following section.

Approximating the luminance distribution

While the dynamic range of a still image has a clear definition (minimum and maximum luminance values), the dynamic range of an entire scene is a more complex notion. Looking at the luminance of all pixels of an image gives the dynamic range of this image.

On the other hand, a straightforward approach to compute the dynamic range of a 3D scene is to look at the luminance of every space point of the scene. Indeed, for each 3D position (x, y, z) in the scene, if we compute the luminance coming from every direction (θ, φ), we can obtain the light field of the scene defined by the five-dimensional plenoptic function L(x, y, z, θ, φ) [START_REF] Adelson | The plenoptic function and the elements of early vision[END_REF]. Proceeding this way would give the most precise estimation of the luminance of the scene. In comparison, while the luminance of a pixel for an image is given by L(x, y), the luminance at a position of a 3D scene that comes from a direction is given by L(x, y, z, θ, φ). Nevertheless, computing such a luminance in a 3D scene lead to place a large number of 360 • cameras at many points of the scene [START_REF] Mcmillan | Plenoptic modeling: An image-based rendering system[END_REF] and render the scene for all of these cameras, which is a complex, memory and time consuming process. We assume that the luminance of the scene can be approximated by placing only few 360 • cameras at key positions as illustrated in Figure 1. The rendered images are 360 • images of the surrounding environment [START_REF] Debevec | Rendering synthetic objects into real scenes: Bridging traditional and image-based graphics with global illumination and high dynamic range photography[END_REF] called environment maps (EMs) from now on. Of course, the placement of the 360 • cameras depends on the scene topology, and it is not excluded to put several cameras in the same room if this one is huge or with a particular topology. At the end, we get a set of HDR EMs rendered by all 360 • cameras placed in the scene. Looking at the luminance of all pixels of those EMs gives an approximation of the dynamic range of the scene. But the positioning of the 360 • cameras may affect the luminance of the pixels, and then the result of the tone mapping.

Importance of the 360 • cameras positioning

The positioning of the 360 • cameras could affect the actual dynamic range of the scene. If the EMs are not placed correctly in the scene (for example not close to sources of high luminance such as light sources, specular and glossy surfaces, etc.) then the dynamic range of the scene is not well captured, which affects the TMO. We will precisely detail later how the TMO processes the rendered HDR image. In the example of the Figure 2, when the 360 • camera is placed close to a window (first row), the rendered EM is mainly bright (left image), the tone mapped image is dark (right image). On the other hand, when the 360 • camera is far from the window (second row), the EM is darker (left image) and the tone mapped image is bright (right image). In both tone mapped images (right side), the position of the 360 • camera is represented by a sphere circled in red. The placement of the 360 • cameras in the scene has a real impact on the tone mapped image and it is left to the content creator to place the 360 • cameras depending on the expected result. Besides the influence of 360 • cameras positioning, the rendering method used by these cameras to generate the HDR EMs can also impact the resulting tone mapping.

Comparison of rendering methods

In order to obtain the most representative luminance distribution of the scene, a realistic simulation of the light interaction with objects surfaces should be done. Ray tracing based methods produce more realistic images but are still too slow to render multiple EMs of complex 3D scenes in real-time. Nevertheless, approaching a realistic rendering in real-time can be achieved using some simplifications. We decided to render direct lighting and add an ambient light and an ambiant occlusion terms that coarsely approach indirect lighting.

The rendering performed by these two methods (ray tracing and ambient based rendering) produces slightly different results that are illustrated in Figure 3. Moreover, as detailed later, only the log-luminance average value ( Lw in equation 2) of the EMs is needed to compute our global TMO. We compare the logluminance average of the environment map rendered using ray tracing (Figure 3a) and when approximating it with ambient and occlusion terms (Figure 3b). The difference between these two computed values ( Lw ) does not impact the resulting TMO. Thus, all EMs are rendered in real-time by computing direct lighting added to an ambient term and an ambient occlusion. Our global TMO is then performed using all the rendered EMs as described in section 4. To finish, as the process has to be real-time, we propose three optimizations that can increase significantly the rendering time.

Optimizations

First, we propose to render the EMs with a low resolution as only the log-luminance average value is needed by the global TMO. This value is pretty equivalent for a high or a reasonably low resolution.

Secondly, the number of EMs to render impacts the processing time. As the scene can be huge, dozen of 360 • cameras can be useful to obtain the global TMO. We propose to limit the number of EMs to render by considering only the nearest cameras from the user. The number of cameras to take into account is a user-defined parameter. The impact of number of EMs to render and their resolutions is shown in Figure 4.

Moreover, the scene is dynamic: lights can be turned on and off, doors can be opened and closed, Figure 4: Impact of the number of EMs to render and their resolution for a complex 3D scene (CPU Intel core i5 6600 3.30GHz, 16GO RAM, NVidia GTX 980Ti). etc. To obtain a correct global TMO, EMs should be rendered at each frame, which is time-consuming. We finally propose to render the EMs only at the first frame, and when the scene changes. A change is detected only for objects that can significantly affect the luminance of the scene (lights and doors for example, moving little objects does not impact the luminance too much). If any change is detected on a object close to a 360 • camera, the EM is rendered again to take into account this change in real-time.

4 TMO for HDR rendering of 3D scenes

Global TMO of a 3D scene

Before describing our TMO that considers the luminance of the whole scene, we will explain the basics of HMD-TMO [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF]. The global TMO performed by HMD-TMO is applied to the 360 • HDR image that is visualised on the HMD. During all the process, the luminance is calculated following the Rec. 709 standard:

L w = 0.2126 × R + 0.7152 × G + 0.0722 × B. (1)
First, the log-luminance average Lw of the 360 • image is computed as:

Lw = 1 N exp x,y log δ + L w (x, y) , (2)
where L w is the world luminance of a pixel (x, y).

A small value δ is used to avoid singularities and N is the number of pixels of the 360 • image. Then, the global TMO processes each pixel (x d , y d ) of the viewport using the Photographic Tone Reproduction operator proposed by Reinhard et al. [START_REF] Reinhard | Photographic tone reproduction for digital images[END_REF]:

L(x d , y d ) = a Lw L w (x d , y d ), (3)
G(x d , y d ) = L(x d , y d ) 1 + L(x d , y d ) , ( 4
)
where a is a user defined value (default value is equal to 0.18) and G is the global tone mapped luminance.

In our case, we also want to tone map the HDR image rendered by the user camera using equations 3 and 4. However, the log-luminance average Lw (defined in equation 2) can not be computed in the same way as the scene is not represented by a unique 360 • HDR image. We have to take into account the set of HDR EMs obtained before to compute the logluminance average of the whole scene. First, we compute the log-luminance average Lw of each HDR EM i rendered by the 360 • cameras:

Lw EM i ) = 1 N i exp x,y log δ + L w (EM i , x t , y t ) , (5)
where L w is the world luminance of a pixel (x t , y t ) of the EM i at a time t. A small value δ is still used to avoid singularities and N i is the number of pixels for the EM i . The global log-luminance average of the whole scene is then approximated by the probability for the user camera to be in a particular room at a moment. As we do not have any a priori on the position of the user in the scene, the probability of being in a room is the same everywhere. That conducts in an arithmetic mean of the log-luminance averages of all EMs:

Lw = 1 M i Lw (EM i ) , (6)
where M denotes the number of 360 • cameras in the scene. Our newly defined Lw (equation 6) replaces the one given in equation 3. At this point, the spatial coherency is preserved as the TMO is computed considering the log-luminance average of the entire scene. However, temporal changes are not considered because luminance variations in the scene can happen (lights turn on and off, doors can be opened and closed, etc). To take into account these variations, the computation of the logluminance average of the whole scene (equation 4) is performed at each time step. Indeed, if an area of the scene suddenly becomes very bright, the scene luminance globally increases and the tone mapped image is darkened. In order to avoid a sudden change in the tone mapped image, we decided to temporally smooth the value of the log-luminance average of the whole scene in the same way Goudé et al. smoothed the viewport TMO in HMD-TMO:

L w (t) = α g Lw (t) + (1 -α g ) L w (t -1), (7)
where L w (t) is the smoothed log-luminance average value of the entire scene between two successive time steps and α g is a time dependent interpolation variable which defines how fast is the smoothing. We fixed α g = 0.1 in our implementation, which means the transition takes about 10 seconds. The smoothed log-luminance average value L w (t) replaces Lw in equation 3. This allows us to adapt the tone mapping to temporal changes of lighting in the scene with smooth transitions.

Viewport TMO of the user camera

As detailed in HMD-TMO, a TMO only applied to the global scene results in a very limited use of the dynamic range of the display. To use a higher dynamic range and then enhance the contrast in the tone mapped image, a second TMO has to be applied to the viewport. Goudé et al. proposed to compute a second tone mapping of the image rendered in the viewport and combine it with the global TMO. The used operation is the same, but the log-luminance average is that of the HDR image of the viewport. 9)

Lw = 1 N exp x d ,y d log δ + L w (x d , y d ) , (8)
L w (t) = α v Lw (t) + (1 -α v ) L w (t -1), (
L(x d , y d ) = a L w L w (x d , y d ), ( 10
) V (x d , y d ) = L(x d , y d ) 1 + L(x d , y d ) , ( 11
)
where L w is the world luminance of the pixel (x d , y d ) in the viewport image, Lw is the viewport logluminance average, and a is still the user defined value. L w (t) is the smoothed value between two successive views and α v is a time dependent interpolation variable (α v = 1.0 as defined in [START_REF] Goudé | Hmd-tmo: A tone mapping operator for 360 • hdr images visualization for head mounted displays[END_REF]). Finally, V is the viewport tone-mapped luminance. There, the temporal coherency is also preserved by smoothing the Lw value through time (equation 9). Besides, the eye temporal adaptation is implicitly involved in these smooth transitions.

Resulting TMO: Combination of global and viewport TMOs

Finally, the combination of both, global and viewport TMOs is done in the logarithmic domain as proposed by Goudé et al.:

L d = exp β × ln(G) + (1 -β) × ln(V ) , (12)
L d = G β × V 1-β , ( 13
)
where G and V are respectively the resulting luminance of the global and the viewport TMO. β is a variable in the range (0, 1) that gives more emphasize on the global or the viewport result and L d is the final displayed luminance. Obviously, L d , G and V are evaluated for each pixel (x d , y d ).

Colorization

During the entire process, only the luminance is managed. The color is added at the end using the Schlick's approach [START_REF] Schlick | Quantization techniques for visualization of high dynamic range pictures[END_REF]:

C = C L w s L d , (14)
where C and C are respectively the input and output trichromatic values (RGB), L w the world luminance and L d the tone mapped luminance. The saturation parameter s is set to 0.7 for all of our results. We used a basic method to manage the color, but several approaches of color correction exist for tone mapping [START_REF] Mantiuk | Color correction for tone mapping[END_REF]; [START_REF] Artusi | Automatic saturation correction for dynamic range management algorithms[END_REF] and can be easily applied to this TMO. The efficiency of our TMO is illustrated in the following section.

Results

In this section, we evaluate our TMO for scenes rendered in HDR. We compare tone mapped images either rendered from two different viewpoints of the scene or from different time with a camera that moves through the scene.

We start by giving a detailed example of the effect of combining both TMOs illustrated by Figure 5. In this example, we compare two rooms of a same scene. One is very bright (first row) and the second is very dark (second row). When considering the global TMO only (β = 1.0), the global contrast between the two rooms is well preserved. However, details in both images are lost. The light reflection on the wall in the bright room is clipped, the floor in the dark room is totally black. Regarding the result when considering the viewport TMO only (β = 0.0), the contrast in each image is enhanced, all details are visible. However, the global coherency is completely lost, both rooms seem equally lit, it is impossible to say if one room is brighter than the other. A geometric mean between the two TMOs (β = 0.5) gives a good compromise for both images. The images of both bright and dark rooms are well detailed and the global contrast is preserved.

We also compared our method with a TMO applied to the viewport only with smooth transitions between views that simulate the visual adaptation to the light 1 . We are interesting in the temporal coherency as illustrated in Figure 6. This example corresponds to a scene where a car is driving in a tunnel [START_REF] Pattanaik | Time-dependent visual adaptation for fast realistic image display[END_REF]; [START_REF] Irawan | Perceptually based tone mapping of high dynamic range image streams[END_REF]. With the naive TMO only applied to the viewport (first row), the temporal coherency is lost. At start (t = 0), the car is inside the tunnel, only the spotlights are illuminating the area. We see in the background that the end of the tunnel is completely clipped. At the end (t = 3), the car is outside the tunnel, the image is mainly bright. We can not see anymore the red and blue lights from the back of the car. Over time, the HDR image became brighter and brighter, which leads to a darker and darker tone mapped image. With our TMO (second row), the inside and the outside of the tunnel are visible at each time in the tone mapped image because we take into account the luminance of the whole scene. Even if the contrast is reduced in each image independently, the temporal coherency is globally preserved. See the accompanying video for more details.

Subjective evaluation

In this section we detail our evaluation protocol regarding the efficiency of our TMO compared with two others. We suppose that our method is more

1 Eye-adaptation TMO implemented in Unity3D (https://unity.com/) faithful with respect to the HDR content and that users appreciate more our TMO. To confirm that, we conducted a subjective evaluation where participants had to judge an HDR content tone mapped with three different TMOs compared with the same HDR content visualized on an HDR display (the ground truth). Our panel consists of 18 participants (9 females and 9 males), between 23 and 44 years old. 9 were expert in VR with a daily use while the others had only a few VR experience before the experiment.

Experiment protocol

The objective is to allow a user to compare scenes visualized on the HDR display (the ground truth) with the tone mapped result visualized on a HMD.

Evaluating TMOs

As explained before, HMD-TMO cannot be evaluated in our study. Even if HMD-TMO ensures visual coherency while displaying 360 • HDR images, this coherency is limited to head rotation movement while in our case we tackle walk through 3D scenes.

That is why we chose to evaluate our TMO by comparing it with two others that can be computed in real-time. The first one is a naive method denoted Logarithm that is based on the Adaptive logarithmic mapping for displaying high contrast scenes proposed by [START_REF] Drago | Adaptive logarithmic mapping for displaying high contrast scenes[END_REF] with smoothed In addition to ensuring temporal coherency, this implementation tries to preserve the global coherency by introducing a scale factor. This parameter applies an offset to the display luminance depending on the world log-luminance average of the current image. In other words, if the HDR image is globally dark, this method applies a negative offset to darken the displayed image. It works similarly for bright images. This method is effective for a user defined luminance range. For our purpose we fixed the low and high limits corresponding to the minimum and maximum luminances that can be encoded by the used HDR display (ie. the dynamic range of the SIM2 display goes from 10 -4 to 10 4 cd/m 2 ).

t = 0 t = 1 t = 2 t = 3
To sum up, the three TMOs used in the experiment are:

1. Our TMO described in section 4 2. Eye-adaptation: The default eye-adaptation TMO implemented in Unity3D 3. Logarithm: Adaptive logarithmic mapping [START_REF] Drago | Adaptive logarithmic mapping for displaying high contrast scenes[END_REF] with smoothed values to avoid flickering.

Evaluation criteria

We asked participants to evaluate the three TMOs regarding two aspects. First, they had to grade the visual fidelity of the tone mapped content visualized on the HMD compared with the HDR content visualized on the HDR screen. Then, we ask them to rank their global appreciation regarding the visual quality of the tone mapped content regardless of the HDR reference. Finally, they had to rank the three TMOs by order of preference.

Evaluating 3D scenes

In order to evaluate our TMO, we developed two interactive scenes in Unity3D. These scenes are interactive as the camera can move and a door can be opened or closed. Both scenes have very contrasted areas (very dark and very bright) to confront evaluated TMOs with difficult conditions. The first one takes place in a car and the scene consists in driving in a tunnel. Outside the tunnel, the sun illuminates the scene while inside the tunnel, the car's headlights are the only light sources as showed in Figure 6. The second scene takes place in a little apartment. One room has a huge window and is illuminated by the sun. The second room is totally closed and is illuminated by a weak light. The two rooms are separated by a door as illustrated in Figure 5.

Evaluation procedure

The procedure can be described as follows. We start by explaining to participants the test protocol and ask them to fill in the consent form. First, we ask them to interact with the HDR scene during few minutes in order to view the different areas of the scene. The interaction with the scene is very simple: participants use a mouse to manipulate the position and the orientation of the camera in the scene. The content visualized on the HDR display is the ground truth.

Once the HDR scene has been explored, we present to participants exactly the same scene on the HMD. In that case, participants move physically in rotation and/or translation depending on the tested scene. The scene of the apartment had the same dimensions that the physical experiment room, so participants are entirely free of movement. For the scene of the tunnel in the car, participants are sat at the driver position and we give them a mouse to move the car forward and backward (by pressing left and right buttons). A constant speed was applied to the car in order to reduce the effect of motion sickness experienced by users LaValle (2016); LaViola [START_REF] Jr | A discussion of cybersickness in virtual environments[END_REF]. We observed this effect thanks to a Simulator Sickness Questionnaire (SSQ) [START_REF] Kennedy | Simulator sickness questionnaire: An enhanced method for quantifying simulator sickness[END_REF]. The image on the HMD is tone mapped using one of the three evaluated TMOs.

Finally, when the HDR content and the tone mapped content have been seen, we ask participants to give their grades regarding the two criteria: (1) The fidelity of the tone mapped content compared with the HDR reference is graded using a linear scale between 0 (not faithful at all) and 10 (very faithful). (2) The global appreciation regarding the visual quality of the tone mapped content is graded using a linear scale between 0 (not appreciated at all) and 10 (very appreciated). To sum up, a protocol loop consists of three steps:

1. Interact with the HDR content on the SIM2 HDR screen 2. Interact with the tone mapped content on the HMD 3. Grade the visual fidelity and the global appreciation

Once the three TMOs for a scene have been tried, we also ask participants to rank the three TMOs from the best to the worst in order of preference. For the whole study, we evaluate three TMOs for two scenes, which means the participants follow the protocol six times in total. We also randomized the order the scenes and the TMOs are tested in order to avoid any bias.

Software and hardware material

Hardware used were a SIM2 HDR display for the ground truth and an HTC Vive pro as a HMD. In order to render HDR images, an image effect shader compliant with the SIM2 display has been implemented. We implemented our solution in Unity3D as it is a friendly tool for VR and HDR developments. Tone mapping values are computed in real-time with compute shaders. Then we apply our TMO as an image effect shader on the rendered HDR image. All the process has to be real-time and run at least at 90 frames per second to ensure a pleasant experience in case of VR. We will now present the results of the experiment.

Experiment results

As our experiment involved physical navigation as well as virtual navigation using a controller, users fulfilled the SSQ before and after the test. Indeed, cybersickness could have an impact on our results. We followed the approach proposed by [START_REF] Kennedy | Simulator sickness questionnaire: An enhanced method for quantifying simulator sickness[END_REF] in order to compute the SSQ score of each user before and after the experiment. The mean (M) and standard deviation (SD) scores of the SSQ were slightly greater at the end of the experiment (start: M = 11.01, SD = 15.04 ; end: M = 14.13, SD = 21.75) mainly due to the disorientation symptoms. However, these scores can be considered rel- atively low. As these scores do not follow a normal distribution, we used a Wilcoxon Matched Pair Signed Rank Test to determine if this difference was significant. The result suggests that our experiment did not have a significant impact on cyberskickness (p > 0.05).

Regarding the different scores given for fidelity and appreciation, we first analyzed both criteria for each scene (scores presented in Table 1 and2). Globally, our TMO obtained the best scores while Logarithm obtained the worst for both fidelity and appreciation criteria. However, we performed an analysis of variance (ANOVA) on these results but we did not find any significant difference.

Results were also analyzed independently from the scene, by adding the scores obtained for both scenes for each criteria: fidelity and appreciation. We also performed an ANOVA on these results and we found a significant difference for the fidelity criteria (p < 0.05) as represented in Figure 7. Then, for comparing each pair of conditions, we performed a post hoc Turkey test and we only found a significant difference between Logarithm and our TMO conditions (p < 0.05). No significant difference was found for global appreciation.

Regarding the ranking of the three TMOs given at the end of the experiment, results are shown in Figure 8. Whatever the scene, our TMO (green) is the one which is the most ranked first and second and the least ranked third. The Logarithm TMO (grey) is often ranked third while the Eye-adaptation TMO (blue) is equally ranked first, second and third. Indeed, our TMO tends to be the one which satisfies most users.

To sum up, the non-significant results do not allow us to give a clear conclusion. However, they suggest that our method is globally more faithful and more appreciated than the others, especially compared with the Logarithm method.

Conclusion

Rendering in computer graphics produces more and more HDR images. Preserving the artistic intent and lighting atmosphere of the original content is essential during the tone mapping process. Previous methods do not consider the whole scene to tone map rendered images, which causes a loss of global coherency. To overcome this limitation, we proposed to consider the whole scene to compute a global tone mapping combined with a viewport tone mapping to render our final image. The entire process is performed in realtime and can be applied to more complex scenes. We showed that our method is slightly preferred when compared with other ones.

Nevertheless, this TMO suffers from inconsistency when a sudden change appear in a distant room: the global luminance changes and causes an undesired evolution of the tone mapped image. This issue is managed thanks to smooth transitions, but could be tackled differently considering visual adaptation or maladaptation. Our future work heads toward fixing

Figure 1 :

 1 Figure 1: (a) The environment map of the living room rendered by a 360 • camera is represented by a sphere. (b) Scene example with three 360 • cameras (circled in red) placed in different rooms.

Figure 2 :

 2 Figure 2: First row: the 360 • camera is close to the window, the environment map (left) is mainly bright and the TMO darken the image (right). Second row: the 360 • camera is far from the window, the environment map (left) is mainly dark, the TMO brighten the image (right).

Figure 3 :

 3 Figure 3: (a) Ray tracing rendering: Lw = 0.012 (b) Ambient based rendering: Lw = 0.01. The logluminance average does not differ enough to significantly impact the result of the TMO.

Figure 5 :

 5 Figure 5: The β variable of the combination (equation 13) gives more emphasize on the global TMO or on the viewport TMO. First row and second row are respectively the tone map rendering of the bright room and the dark room in the same scene showed by the left image.

Figure 6 :

 6 Figure 6: Comparison between eye-adaptation (first row) and our TMO (second row) on a image sequence.The eye-adaptation TMO only applied to the viewport does not preserve the temporal coherency. The tunnel is less and less visible while the outside becomes visible when the car gets out. Our method preserves the temporal coherency, both inside and outside of the tunnel are always visible.

Figure 7 :

 7 Figure 7: Box plot for the fidelity scores overall.

Figure 8 :

 8 Figure 8: Occurrence of TMOs ranked first, second and third overall.

Acknowledgments

All 3D assets come from the Unity Assets Store and are free to use. This work has been supported by the ANR project ANR-17-CE23-0020. We would like to thank Kadi Bouatouch for his help and proofreading. Thanks to reviewers for their constructive commentaries. Thanks to all experiment participants for their contributions.

this incoherent result. Moreover, an analysis of the scene topology to determine an efficient placement of the 360 • cameras could lead to a semi or fully automated process. Finally, more subjective evaluation should be conducted for manifold 3D scenes with various topology, lighting design and more interactivity.

It could be very interesting to evaluate our TMO on SDR 2D screens to confirm its efficiency compared with authors TMOs.