Alfredo Goldman

Yanik Ngoko

Denis Trystram
email: denis.trystram@imag.fr

A Framework for the Design of Parallel Adaptive Libraries on Hard Computational Problems

Keywords: adaptive algorithms, adaptive systems, automatic algorithm combination, resource sharing

In this work, we present the Adaptive Multi-Selection Framework (called AMF). AMF is an API built for helping designers to develop optimized combinations of multiple algorithms solving the same problem in function of the physical architecture and algorithm behavior. AMF offers a simple and generic model for developing automatic combination of algorithms. In this model, the user needs to specify the set of algorithms to be combined and a representative benchmark of instances of the problem solved by the algorithms. This generic solution has advantages over many existing solutions for making automatic combination that are specific to a fixed set of algorithms or computational problems. Automatic combinations of algorithms are made in AMF with the multi-selection technique. For each instance of a computational problem, its resolution under multi-selection includes a selection of a subset of candidate algorithms followed by a concurrent run of the selected algorithms with a smart resource sharing. The resource sharing is decided according to the physical architecture, the problem instance and the time allowed to compute it. The multi-selection strategy provides excellent results when there is a large variance of execution time per instance. The actual implementation of AMF is built for shared memory architectures. However, it can be extended to distributed ones. The AMF principles have been validated in particular on the well-known Constraint Satisfaction Problem.

Introduction

The continuous evolution of algorithmics is leading to a huge amount of algorithms available for each computational problem. For the same problem, the performance of these algorithms might vary depending on many aspects like the considered problem instance or the machine architecture [START_REF] An | STAPL: An adaptive, generic parallel C++ library[END_REF][START_REF] María | A dynamically tuned sorting library[END_REF]. In order to obtain good performances, there is the need for solutions that can combine efficiently various algorithms designed for solving the same problem. The huge variety of computational problems for which such solutions are required, the large amount of algorithms and machine architectures suggest that automatic generic combinations should be prioritized. In this paper, we focus on the automatic combination of multiple algorithms solving the same problem, specially those related to hard computational problems. Our main objective is to provide a framework that eases the implementation of automatic combination of algorithms.

Contributions

We propose the Adaptive Multi-Selection Framework designed to ease the task of combining multiple algorithms solving the same problem on parallel architectures. For this end, AMF typically requires for each computational problem a set of candidate algorithms (sequential or parallel) and a benchmark for tuning algorithm performances. These information determine AMF knowledge on building automatic combination of algorithms for the targeted computational problem.

AMF works like a problem solver and provides an interface where any instance of a computational problem can be solved under the multi-selection technique. The resolution of a problem instance under the multi-selection contains three phases: a selection of a set of candidate algorithms for the instance, a computation of an optimal resource sharing for the instance and the execution of the algorithm combination related to this selection. These combinations are defined in AMF as algorithms portfolio [START_REF] Huberman | An economics approach to hard computational problems[END_REF]. An algorithm portfolio execution is a set of algorithms run each with a predefined number of resources an stopped as soon as one algorithm completes its execution.

The actual version of AMF is designed for shared memory architectures and support parallelism based on threads. Moreover, we provide some validations of its utilization for defining automatic combination of algorithms for the Constraint Satisfaction Problem, either sequential or parallel.

Text organization

The rest of the paper is organized as follows: Section 2 presents the multiselection technique as designed in AMF. The architecture of AMF in a component point of view is presented in Section 3. Section 4 gives an example of utilization of AMF on the Constraint Satisfaction Problem. In Section 5, we discuss about advantages of the multi-selection. Related works are presented in Section 6 and we conclude in Section 7.

The Multi-selection technique

We suppose that we have a parallel machine architecture and a finite set of algorithms(parallel or sequential) solving a same problem P . Within multi-selection, each instance of P is solved in three phases. The first phase consists in a selection of candidate algorithms for the instance. The second phase consists in sharing resources between the selected algorithms. The third phase is a concurrent execution of the selected algorithms under the adopted resource sharing. Each phase is described in the following.

Selection of the candidate algorithms

At this stage, we have a finite set of algorithms (parallel or sequential) solving the computational problem P. Given an instance of P, we have to decide which algorithm to use. The multi-selection considers two modes for instance resolution: the online and offline mode. These two modes affect differently the selection phase.

Let suppose that we have a base A of candidate algorithms for solving an instance I of P. In the offline mode, all candidate algorithms known for P will be selected at this stage of the multi-selection. Thus the selection in the offline mode will output A(I) = A. In the online mode, just a subset of candidate algorithms is retained. This means that the selection in the online mode will output a set A(I) where A(I) ⊆ A.

Details about the selection phase in AMF will be given in Section 3.1. For now, we can retain that the two possible modes (online and offline) lead to different types of overhead on instance resolution. We illustrate this as follows: let us denote the total resolution time for solving I as t(I). In multi-selection, we have t(I) = t s (I)+t rs (I)+t ep (I) where, t s , t rs and t ep are, respectively, the time for selecting a subset of algorithms, the time for computing a resource sharing, and the time for executing the chosen algorithms with the computed resource sharing. Since in the offline mode the selection of algorithms is the same for each problem instance, one can pre-compute the optimal resource sharing that will be re-used for all instances. Thus, the cost t s (I) + t rs (I) will typically be negligible in the offline mode.

Algorithms selected at this phase of the multi-selection will then be executed concurrently. However, it is only the result of one execution that will be exploited at the end. This means that the more selected algorithms, the more the overhead in the resolution. The philosophy of the online mode is to try to reduce t ep (I) by efficient selection of algorithms even if it will lead to more significant values of t s (I) + t rs (I). Such a selection can be guide by a comparative analysis of instance feature and algorithm behavior [START_REF] Dongarra | Self-adapting numerical software (SANS) effort[END_REF].

Computation of the optimal resource sharing

For the determination of resource sharing (second phase in multi-selection), the multi-selection uses the dRSSP model [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF]. In dRSSP, we assume that we have a finite set of homogeneous computation units or resources P = {0, . . . , m}. On these units, parallel algorithms can be run.

Given a computational problem P, the inputs for dRSSP model are : a finite set of algorithms A = {A 1 , . . . A k }, a finite set I = {I 1 , . . . , I n } of representative instances of P, and cost values C(A i , I j , p) giving the execution time of each algorithm A i ∈ A on the instance I j ∈ I when executed on p ∈ P resources.

The resolution of instances in the dRSSP model is based on Algorithm portfolio [START_REF] Huberman | An economics approach to hard computational problems[END_REF]. Let us define a resource sharing as a vector S = (S 1 , . . . , S k ) such that S i ∈ P and S i ≤ m. Here, S i is the number of resources used by A i . With Algorithm portfolio, we can define the resolution time of any instance under this resource sharing as C(S, I j ) = min

Ai∈A {C(A i , I j , S i )|S i > 0)} 3 .
Given these inputs, we suppose in dRSSP that to solve the problem P, any of its instance will behave like one instance in I. Therefore, a global approach to minimize the resolution time of the problem instance can consist in finding the resource sharing S minimizing Ij ∈I C(S, I j ). We will denote this as the MinSum optimization function.

In the optimal solution under the MinSum objective, significant variations can be observed between instances resolution time. In a competition setting where we have a finite set of instances to solve in a maximal amount of time, this might not be a problem. However, in a context where instances are not solved in block, variations between execution times of instances are sensitive. In this case for example, a good optimization goal is to minimize the maximal time we can wait for having the solution of an instance. This will be taken as the MinMax objective given by the function: minimize max

Ij ∈I C(S, I j ).
Under the MinMax or MinSum objectives, one can easily show that the problem of computing the optimal resource sharing is NP complete [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF]. Thus, heuristics must be used in the online mode in order to have an acceptable overhead on instance resolution (in the offline mode the resource sharing is pre-computed).

Minimize I j ∈I C(S, Ij) 1. Si ∈ {0, . . . , m} 2.
Si ≤ m (a) MinSum optimization Minimize max

I j ∈I C(S, Ij) 1. Si ∈ {0, . . . , m} 2. Si ≤ m (b) MinMax optimization

Execution of algorithms with resource sharing

The last stage of the multi-selection is the concurrent execution of algorithms on the instance to solve, according to the computed resource sharing. All algorithms with a non null resource allocation are executed until one ends its execution. This requires to have interruptible algorithms. We will see however later that AMF provides a support to automate the interruption of algorithms in a concurrent execution on multi-core machines.

At this stage, we presented the multi-selection technique. The basic requirements of this technique ( benchmark of instances, parallel or sequential algorithms, interruptibility, multi-core machines) makes it applicable on a large class of computational problem and machine architecture. We will discuss about the multi-selection technique in Section 5. In the next section, we illustrate how it is applied with AMF.

The multi-selection in AMF

The AMF framework is implemented in C/C++. The description of a computational problem in AMF is made through applications. An application has mainly a set of algorithms solving a same problem. It can be associated to a benchmark of instances for the related computational problem. AMF works like a problem solver that generates automatic combination of algorithms when it receives specifications of a benchmark and application. It also offers an interface for solving instances of known computational problems under the multi-selection.

In Figure 1a), we describe an example of application insertion in AMF. Applications and benchmarks are defined through through block of data of type AMF Application and AMF Benchmark. The application in the example is related to the CSP (Constraint Satisfaction Problem) and has three algorithms (max deg, min dom, max dom deg) that are CSP heuristics. These algorithms are sequential since the application is of type AMF SEQ). Parallel algorithms can be also defined in AMF. In this case, the application is of type AMF PAR. Certain requirements must be fullfilled for a successful application insertion. As indicated by Figure 1b), the algorithms solving the computational problem of the specified applications must be defined in the file AMF AMF ALG.cpp.

Figures 1c) and1d) describe the insertion of a new benchmark for CSP. Similarly to the creation of an application, the insertion is made by invoking a function of the class AMF Learner. Finally, in Figure 1f), we show how to update information for an inserted application.

Figure 1e) presents the resolution of an instance with AMF. All problem instances in AMF are specified using a block of data of type AMF Instances.

In the example, we defined an instance of the application CSP and used the function generateOneCSP for initializing data of the CSP problem. Then, we invoked an AMF solver (object of the class AMF Solver) for its resolution under the multi-selection. After the resolution of the instance, the result is given as a void pointer that from a transtypage operation one can re-structure. All results are provided in AMF as an array of floats. The implementation of algorithms in AMF AMF ALG.cpp must take into account this information.

Figure 1 gives a tour of possible operations in AMF and manipulated objects. The internal structure of the framework is described in the next section.

3 The AMF component structure The benchmark and algorithms containers can be modified by the user. The submission of a request for the resolution of an instance is done in AMF through AMF Solver. This component calls AMF Optimizer for computing an adequate resource sharing and then run the a portfolio engine with the appropriate resource sharing. In the next sections we give details about these components.

The Solver

The solver component is constituted mainly by the class AMF Solver. In this part we will present the following methods of this class: void solve(AMF_Instance I, float *argout) void set_MultiSelector(char *app_name, char *method_name)

The solve method takes in inputs an instance (I) and outputs an array of floats(argout) containing the solution of the instance. AMF Instance is a structure whose fields comprise:

the application name to which the instance refers, -a void pointer toward the input data describing the instance, -the mode of resolution chosen (online or offline), -the time limit for instance resolution (this time is significant only if the chosen mode is online),

the type of optimization (MinSum or MinMax).

a proportion field p ∈ [0, 1],

When the solve method is called, it communicates with the learner to have information about the referred application (in particular, the benchmark file tuned for its). Using this information, it will ask a resource sharing to the optimizer and will finally call a portfolio engine for its execution. Thus, the solver coordinates the entire execution of the multi-selection in AMF. It is important to notice that the solution of an instance in AMF is always returned as an array of floats. Despite this restriction, we believe that this format can handle many other internal representations (strings, integers etc.).

For the first phase of the multi-selection, AMF gives the possibility to define an appropriate method (a selector) for selecting a subset of candidate algorithms in the online mode of resolution. Each selector code must be defined in the file MultiSelector.cpp. The signature of a selector has the structure void <selector name>(AMF Instance I, int tab[], int k). Its implementation must ensure that <selector name> modifies the array tab for indicating among the k algorithms available for the application, the ones selected ( when tab[i] = 1, 1 ≤ i ≤ k, the solver will consider that the algorithm i is selected).

After, the implementation of the selector, the AMF internal database can be informed of the new defined selector through a call to the method set MultiSelector of the class Solver.

We believe that the definition of an efficient selector is a challenging task, requiring a good knowledge on the addressed computational problem. Some patterns for building selectors have been studied in [START_REF] Ngoko | Combining numerical iterative solvers[END_REF][START_REF] Bhowmick | Application of machine learning to the selection of sparse linear solvers[END_REF][START_REF] Burke | Exploring hyper-heuristic methodologies with genetic programming[END_REF]. Morever, AMF has a default one for all applications. Thus, one might have at a moment for a given application two selectors that can be used in the online mode. The choice between these selectors depends on the proportion field p of the AMF instance to solve. When an instance is submitted for the online resolution mode, if p = 0, then, the solver supposes that a personalized selector has been defined for the application and call it. If p ∈]0, 1], the AMF default selector will be called. This latter one will select randomly a proportion of p algorithms among available ones for the referred application.

In AMF, a constant array of functions containing addresses of selector is defined in the file MultiSelector.h. This pointer is used by the solver to determine for each application the associated selector. When the method set MultiSelector is called, the content of MultiSelector.h is re-generated in order to update the pointer of selectors.

The Optimizer

The optimizer component is implemented by AMF Optimizer. It is used in two main scenarios:

-When a new benchmark data is provided for an application, the optimizer is called by the learner to pre-compute an offline resource sharing;

-For the resolution of an instance in the online mode, the optimizer is called by the solver component to compute a good resource sharing within time limit.

The main functions used in the Optimizer are :

void getOnlineRS(AMF_Algp_desc) void getOfflineRS(AMF_Algp_desc)
getOnlineRS serves to compute a resource sharing in the online mode and getOfflineRS serves for the offline mode. Optimizer implementation a) Main heuristics : For computing resource sharing, AMF has for each optimization objective, 5 heuristics specialized in resource sharing building on parallel application and 5 ones for sequential applications. These heuristics solved the dRSSP model presented in Section 2.2 and are listed in Table 1. Detailed explanations on the heuristics implementations for parallel applications can be found in [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF] and especially in [START_REF] Goldman | Optimizing resource sharing on cooperative execution of algorithms[END_REF] for HIF. Heuristics 1.: Heuristics used for optimization, guaranteed approximations ratio and complexity. k is the number of algorithms to combine, n is the size of the benchmark for tuning algorithms and m is the number of computational units in the dRSSP model.

for sequential algorithms are just adaptations of those of the parallel case where we limited the number of possible resources for each algorithm to 1.

We added small changes in the MAG implementation. The original one consists of selecting a number g of algorithms (guessed algorithms) on which all possible assignments of resources are explored. If for the g chosen heuristics, we explore an assignment of resources that use a total of m g resources, one fairly shares the mm g resources to the remaining algorithms (each algorithm then has approximately ⌊ (m-mg) k-g ⌋ resources). One can easily notice that when the number of guessed algorithms g = k, the MAG heuristic gives the optimal solution.

We modified MAG in observing that given a selection of g algorithms, between the kg remaining ones, some might not have any resources in the exact solution. So, instead of assigning to all these algorithms ⌊ (m-mg) k-g ⌋ resources, we considered any possible subsets of algorithms k ′ < kg algorithms among the remaining ones and shared between them the mm g resources. The best resource sharing that we obtain is retained.

In the offline optimization mode (execution of getOfflineRS), the resource sharing is computed using the optimal heuristics (OPT s and MAG with g = k). In the online mode (execution of getOnlineRS), the computation of the resource sharing must be done under the time limit defined in the AMF instance (see Section 3.1). Therefore, a tradeoff must be found between the quality of the solutions proposed and the time limit for the optimization.

b) Optimization in the online mode :

The online optimization mode comprises two steps: the construction of a plan that is, an ordered subset of optimization heuristics to be executed and the execution of the optimization heuristics following the plan. The total time for deriving a resource sharing with a time limit t can be formulated as: t rs (I|t) = t cp (I|t) + t ep (I|t). In this expression, t cp (I|t) is the time required for computing the plan and t ep (I|t) is the time required for executing the plan. The construction of the plan must guarantee that t ep (I|t) ≤ t and t cp (I|t) are small.

For having small values of t cp (I|t), we classified the optimization heuristics in three classes: the polynomially fast heuristics ( MA, RAND, WTA), the polynomially slow heuristics (HIF), and the exponential heuristics (MAG, OPT). Given a time limit t, the construction of the plan starts with an estimation of the time required for executing and selecting the best resource sharing from the first class of heuristics. If the estimation suggests that this part of the plan will not exceed t, one evaluates the possibility of including polynomially slow heuristics with the remaining time limit estimated. Finally, exponential heuristics are considered. For this latter case, we search for the best value of g that will lead to an optimization under the remaining time limit. The clustering of optimization heuristics is motivated by their theoretical complexities (see Table 1) and experimental behaviors. In particular, Figure 4 depicts an experimentation made on a benchmark of sequential SAT solvers with the sequential heuristics for optimization. The results concern the MinSum objective. The experiments are done on a total of 23 sequential SAT solvers. We built on this set a resource sharing with optimization heuristics, assuming that we have 1, 2, 3.. homogeneous resources. Details about the experiments can be found in [START_REF] Goldman | Optimizing resource sharing on cooperative execution of algorithms[END_REF]. The times of the polynomially fast heuristic are not reported but are always under 0.1 seconds. This figure exhibits the tradeoffs between the quality of the heuristic and the execution time required. For example HIF computes a better solution than WTA as shown by Figure 4a). However, it is more time consuming as shown by Figure 4b).

The Learner

The learner is the central component of the AMF architecture. Its is mainly involved in the following scenarios:

-It learns platform settings (mainly at the installation of AMF) and tunes the analytical performance model of the optimizer; -It is the main component for application and benchmark registration; -The learner is also invoked by other components when they need information about applications (e.g. the optimizer needs to know if an application is parallel or sequential).

The basic functions used for these operations are:

void tune_bench(int app_id) void add_app(AMF_Application) void add_bench(AMF_Benchmark) AMF_Application getData_app(int app_id) AMF_Benchmark getData_bench(int app_id)

We will discuss them in what follows.

Tuning of the optimizer The tuning of the optimizer starts when the function add bench is called. It consists of measuring the performances of heuristics listed in Table 1 on the parallel machine (we suppose multi-core) where AMF runs.

The learner supposes that the execution time of each of each heuristics can be described as a real function f (m, n, k, g) (m is the number of cores of the architecture). This choice is motivated by the complexity result obtained in Table 1. For the tuning, the learner explores the database of applications and benchmarks for finding possible value (n, k). For all valid points (n, k) 4 , the learner considers all values of g ∈ {1, . . . , k} and makes multiple executions (actually 20 but it is customizable) of available optimization heuristics (HIF, MA etc). It retains the mean execution time obtained from the executions and save it.

Applications and benchmarks registration Benchmarks and applications registration are made in AMF through the learner functions: add app and add bench.

An application to add is described through a block of data of type AMF Application. This block is mainly characterized by:

-An application ID that is an integer unique to each application; -A name which is supposed to be the computational problem to which we refer (e.g. SAT for Satisfiability );

-A list of algorithms that are given through pointer toward algorithms implemented and available for the resolution of computational problem; -A type that can be Sequential if all algorithms available for the application are sequential or Parallel otherwise. This information is important for the computation of resource sharing.

An AMF Benchmark comprises mainly:

-An application ID that is the application referred by the benchmark; -A benchmark source file that are brute instances representative of the computational problem; -A benchmark reader that is a pointer towards a function that can extract an instance from the benchmark source file.

The registration of a new application will automatically create a unique identifier for it. It also inform the portfolio engine by code generation of this new registration (we will se how later).

To any application, there is associated a unique AMF Benchmark block of information. For completing a benchmark registration, the learner first calls the function tune bench for automatically generating a benchmark performance profile 5 . It then calls optimization heuristics that given this benchmark profile can compute an optimal resource sharing for algorithms known on the registered applications. Finally, it informs the benchmark container (by code generation) of the presence of a new identified reader function, and eventually tunes the optimization heuristic if a new couple (number of benchmark instances, number of algorithms) is introduced.

Communications with other components

The learner is involved in multiple operations by other components when they need information about applications and benchmarks. To do so, they invoke its functions getData app and get-Data bench. To ease the access to this information, the learner maintains a table of applications and a table of benchmarks. These tables can be loaded explicitly as in Figure 1, in using the methods load app conf() and load bench conf().

The Learner manipulates a great deal of information related to the AMF internal setting. In Figure 5, we describe relations between information related to applications and benchmarks that are manipulated by the learner.

The portfolio engine

The portfolio engine is mainly invoked in two scenarios:

-It is invoked in the last stage of the multi-selection for the portfolio execution of algorithms; -It is invoked by the learner when this latter has to generate a benchmark performance profile.

Alg 2 Alg 3 Alg 1 Alg. Cont. BS 2 BS 1 BS 3 Bench. Cont.
Bench. profile

BP 1 BP 2

Applications Table Benchmarks Table

Id

Id name There are as entries as registered applications Fig. 5.: Data dependencies in the learner. Each entry of the application table is related to at most one entry in the benchmark table (when a benchmark is specified for the application). These entries also point to benchmark source files (in the benchmark container), benchmark performance profile files, and algorithms (in the algorithm container).

The portfolio engine keeps a pointer towards candidate algorithms (defined in the algorithm container) for application registered in AMF. The description of this pointer is in the file AlgPointers.h of the Portfolio container. This file is updated by the learner when an application is inserted or updated.

Given a defined resource sharing for an application, the portfolio engine can start the concurrent execution of algorithms accessible from its pointers following the resource sharing. In the concurrent execution, if the application is sequential, the resource sharing indicates the algorithms that will be run. In the parallel cases, it gives the number of resources for the execution of each algorithm. For coordinating the execution of multiple algorithms, the portfolio engine uses a Monitor object. This object has two important attributes:

-A boolean value that indicates that a solution is found; -An array of float where can be written as result at the end of the execution.

These attributes can only be manipulated through synchronized functions implemented in the monitor. The monitor object is accessible in the file AMF ALG.cpp (where application algorithms are defined) and must be used in the implementation of algorithms to indicate that a result is found. We will see an example of utilization in Section 4.

Algorithms and Benchmark container

The algorithms and benchmark containers comprise implementation of algorithms and benchmark readers. Algorithms source codes in C/C++ must be implemented in the file AMF ALG.cpp. The signature of each algorithm must have the generic form void* <algorithmName>(void *). Despite the fact that the input argument is of type void *, its internal organization is of type AMF Argument. This structure comprises:

-A pointer towards the input arguments that are data of the computational problem instance ; -A pointer towards a monitor object used for the synchronization and collection of results; -The number of resources for the execution.

For an effective coordination of the execution, each algorithm defined in AMF ALG.cpp must set in the monitor (given in input) a solution when it is found (An example of such an implementation is provided later). Moreover, AMF typically supports for now parallel algorithms based on threads.

The benchmark container comprises programs for reading benchmark source files provided in AMF. The definition of benchmark readers in AMF is done in the file reader.cpp of the Benchmark container. The signature of a reader must have the form void* <readerName>(FILE *F). The implementation must ensure that in the file pointed by F, a call of the reader function returns an instance as a void pointer. In the registration of a new benchmark, the name of the reader must be given.

Example of Constraint Satisfaction

We validated the AMF architecture for the resolution of the Constraint Satisfaction Problem. For this purpose, we inserted in AMF parallel and sequential versions of algorithms solving this problem. In Table 2, we detail the different actions that we did related to the parallel version of CSP (PCSP).

These actions define the general operations that are required for programming with AMF. As one can see the effort done by the developer consists mainly in providing algorithms, benchmarks, and benchmark readers in the algorithms and benchmarks containers. At the end of the execution of actions described in Table2, a new application is ready for utilization in AMF.

Parallel algorithms defined in AMF must be based on threads. This is important for the synchronization of the execution. Others rules in code writing must be respected in the actions done above, we will discuss about them in the Section 4.1.

Writing algorithms and readers

There are three aspects that are important while defining a new algorithm: the algorithm signature, the management of result and the coordination with 6:

For receiving the inputs arguments, one must notice that AMF will execute the defined algorithms with an argument that is of type AMF Argument (even if it is passed as a void pointer). This is what explains the cast operations that the developer must do at the beginning of Figure 6a). From the cast operation, the algorithm has access to a monitor (here std1→sync). It must use this latter one to set the result of its execution. The monitor provides the barrier functions (lock barrier() and unlock barrier()) to allow modifications of the result in mutual exclusion. Finally, throughout the function setEnd, ones indicates for all algorithms that a solution has been found. It is important when defining each algorithm for PCSP to think about setting the result in the monitor object when a solution is found. This is what will inform the other algorithm that are run concurrently to stop their execution.

When writing a reader, it is important to return a void pointer that can be translated from a cast operation in the adequate data structure. We give in Figure 6b) an example of reader structure for a CSP instance. Using AMF, we defined one sequential and parallel CSP applications, each having with 9 algorithms. The description of these algorithms can be found in [START_REF] Goldman | Optimizing resource sharing on cooperative execution of algorithms[END_REF]. For each application, we associated a benchmark of 225 CSP instances described in [START_REF] Goldman | Optimizing resource sharing on cooperative execution of algorithms[END_REF]. Then, we consider a scenario in which one has to solve again these 225 instances using AMF. In this scenario, we used a selector that ignores the benchmark instances. Thus, even if AMF has been tuned on the instances that we have to solve, it does not use this information.

In this scenario, we evaluated both the offline and online mode of resolution and the resolution under different optimization objective. We run the experiments on a parallel multi-core machine with 4 cores. The cores have a frequency of 2661MHz and hyper-threading is used in each core.

Experiments in the offline mode Table 3 presents the execution time obtained with AMF for solving the CSP instances with sequential algorithms. In this table, p is the number of threads that are created in the resolution. One can see here that if 4 threads are used in the MinSum optimization, the execution time obtained is better than those of the best single algorithm. Execution times presented are the means that we obtained from 30 executions. The standard deviation in the time was small (lower than 0.002).

We present in this table both theoretical estimations made by the AMF optimizer when computing a resource sharing and experimental results observed for the resolution of instances under the MinSum and MinMax objectives. Theoretical predictions do not coincide with measured execution times. This is due to cache sharing and hyper-threading overhead in the concurrent execution. The hyper-threading overhead is clearly visible since the more the number of threads exceeding the number of cores, the more the difference with theoretical estimations. Finally, the time for the MinMax optimization here does not change because the CSP algorithms are run with a maximal time unit of (30 seconds) and, there are some instances that can not be solved under this time limit.

We also did an evaluation of the offline optimization with parallel CSP algorithms. The results are reported in Table 4. This evaluation again shows that AMF can outperform the best algorithm.

(
However, when we have more threads than core, hyper-threading overhead is more present. Finally, in Table 5 we depict the cumulative execution time that was needed for generating a benchmark profile for CSP instances and for computing an optimal resource sharing (given a benchmark profile) in the offline mode. The optimization time is not important mainly because we do not have many cores (see Table 1 on complexity analysis). The tuning time however is greater and, could have been more important if we did not decide to execute parallel and sequential CSP algorithms only one time instead of 20 times, when from the first execution, it is clear that the algorithm can not solve the instance under the 31 seconds. Experiments in the online mode In these experiments, we solved CSP instances with different time limits in order to have a solution under a polynomially slow and polynomially fast optimization (see Section 3.2). In the first phase of the multi-selection, the chosen selector selects all algorithms available for the application. There is no interest in having such a selector for online optimization. But, we used it solely to have a setting of comparison with the offline optimization. In Table 7 we depict for solving the 225 instances, the ratio between the cumulative execution time with AMF under online optimization and the optimal measured times when performing offline optimizations. The evaluation is done with the parallel CSP application. While p ≤ 3, there is no overhead incurred by online optimization. This is due to the fact that the optimal solution consists in executing the best algorithm. This solution is found by the WTA heuristic for optimization. When p is between 4 and 6, the best algorithm is not the optimal possible solution. However, the polynomially fast and slow optimization choose a plan that cede all resources to the best algorithm. When p = 7, a difference appears between the polynomially fast and slow optimization modes. While the former sets all resources to the best algorithm, the latter suggests a better resource sharing. However, the polynomially slow resource sharing leads, in the execution, to more overhead than the polynomially fast ones. Finally, on p = 8, the polynomially slow optimization computes a resource sharing that in the execution outperforms the polynomially slow optimization. These experiments show that the multi-selection technique as implemented in AMF can effectively combine multiple algorithms solving the same problem in order to reduce the execution time needed in problem resolution. They also show that there is a difference between the expected time in AMF when making combination of algorithms and the effective times observed in practice. Therefore, there is a need to integrate more knowledge about machine architectures (for example hyper-threading overhead) in AMF. We have shown experimentally that the multi-selection technique is efficient in combining multiple algorithms solving the same computational problem. In the next section, we provide a short analysis of the technique. The objective is to provide general intuitions that justify its utilization.

Analysis of multi-selection

We discuss here the advantage of multi-selection as done in AMF with respect to the importance of selecting more than one algorithm for solving a problem instance. We also present an alternative model: algorithm ranking [START_REF] Xu | Satzilla: Portfolio-based algorithm selection for sat[END_REF][START_REF] Bhowmick | The role of multi-method linear solvers in pde-based simulations[END_REF]. In all the discussion, we consider that we have a shared memory parallel context with a finite number of m homogeneous units of computations. a)Multiple selection vs unique selection: Let us suppose that for solving an instance with some candidate algorithms A = {A 1 , . . . , A k } we select a single algorithm. Let us also suppose that we have n instances to solve. On each instance i, let us denote by t * i its minimal resolution time with one algorithm of the set A Given a technique T x , the mean expected time for solving the n instances is denoted E[T x (n)] . The risk of this technique is denoted E[T x (n)]t opt where t opt = n i=1 t * i . When selecting a unique algorithm, we might have a probability of p for selecting the right algorithm. For each instance i, let us denote by t 1 i , . . . , t k i the time required to solve it respectively by A 1 , A 2 , . . . , A k . Let us also assume that we have an equiprobability of having any algorithm as the wrong selected ones. The mean time for solving n instances by selection of a single algorithm is then

E[S(n)] = n i=1 p.t * i + (1 -p)(t * i + 1 k k u=1 (t u i -t * i ))
. For solving all instances with a multi-selection of k algorithms, we can expect a time of

E[M (n)] ≤ n i=1 α i t *
i (since we execute all algorithms concurrently) where α i depends on the resource sharing 6 . When isolating the optimal resolution time

t opt = n i=1 t * i , we have E[S(n)] = t opt + (1-p) k n i=1 [ k u=1 (t u i -t * i )] and E[M (n)] ≤ t opt + n i=1 (α i -1)t * i .
It is reasonable to bound the value of α i with, for example, the number of resources if there is a linear parallelism, and we have less algorithms than resources k ≤ m. We will then have α i ≤ m. Thus the risk in offline multiselection can be bounded at a fixed distance factor to the optimal solution while the quantity (1-p)

k n i=1 [ k u=1 (t u i -t * i )
] can be arbitrarily large. This means that the selection of a unique algorithm is more risky than the multiple selection in the offline mode.

Smart values of α i could be proposed to minimize M (n). In particular, we can share resources to algorithms in order to tolerate, an important overhead on instances whose execution time is small for all algorithms. This is the key point of heuristics for optimizing resource sharing in AMF.

The bigger the value of p, the smaller the risk in unique selection. This is the main interest for an online multi-selection. Indeed, if it is possible to detect with high probability what is the optimal algorithm, then, it might be possible to have a process that can choose for each instance i a subset of k i algorithms (k i ≤ k and n i=1 k i < nk) such that the best algorithms on the instance is included on the subset with a probability of 1. Thus, the expected time for the portfolio will be E[M (n)] ≤ n i=1 β i t * i and since k i ≤ k, we have less algorithms executed concurrently and we could expect that

n i=1 (β i -1)t * i ≤ n i=1 (α i -1)t * i .
b)Algorithm portfolio vs algorithm ranking: In algorithm ranking, the selected algorithms are not executed concurrently. A fixed amount of time or cutoff and a ranking between algorithms is decided. Then each algorithm is executed on the instance to solve during the cutoff time decided and following the decided ranking. The executions is stopped when a solution is found. This model of execution is certainly a good alternative to algorithm portfolio. One advantage is that there is no need to compute a resource sharing since each algorithms is executed with all resources. Algorithm ranking has been used with interesting results in [START_REF] Xu | Satzilla: Portfolio-based algorithm selection for sat[END_REF].

In algorithm ranking it is important to fix a cutoff time. This is not easy since if the cutoff is two small, then on some instances, it might be impossible to have a solution under it. Let us suppose that the cutoff has a value of t and that there is at most one algorithm that can solve each instance under this cutoff. Given a ranking of algorithms, an instance will be solved by the first algorithms or if not, the second and if not the third etc. We suppose that any instance has an equiprobability p to be solved at each rank. Thus, the time for solving n instances will be E

[R(n)] ≥ n i=1 (pt * i + p(t + t * i ) + p(2t + t * i ) + • • • + p((k -1)t + t * i ))
. In isolating the optimal resolution time, we have

E[R(n)] ≥ t opt +p n i=1 k(k-1) 2 (t * i + (t -t * i ))
. The risk again depends on the cutoff factor. In order to guarantee that each instance will be solved under the cutoff, this value must be in general big, we find the algorithm portfolio approach less risky.

A 2 A 3 a) Algorithm portfolio b) Algorithm ranking A 1 t 2t A 2 A 3
Fig. 8.: Example of execution pattern in algorithm portfolio and algorithm ranking. In the case of portfolio, all algorithms are executed concurrently to solve the instance while they are executed given a rank and under a time limit (here t). In both cases, we have useless executions (dashed in the figure).

The multi-selection technique is a less risky approach when there is an important difference between execution of algorithm. This is in particular of heuristics solving hard computational problem.

Related Work

The main philosophy that has been considered in the automation of algorithms combination is the problem specific approach. In such approaches, an adaptive algorithm that can adapt its execution depending on the machine architecture is designed for a specific computational problem. Given a computational problem P, the adaptive algorithms manage a pool of candidate algorithms designed for P. Depending on the machine architectures and instance of P to solve, it selects the most appropriate algorithm(s) to obtain good performances. To be able to make these choices, the adaptive algorithm will learn how to proceed during its installation on each platform from a finite benchmark of P instances. This problem specific approach has been applied successfully on many computational problem such as matrix multiplication [START_REF] Petitet | Automated empirical optimization of software and the ATLAS project[END_REF][START_REF] Dongarra | Self-adapting numerical software (SANS) effort[END_REF], Sorting [START_REF] An | STAPL: An adaptive, generic parallel C++ library[END_REF][START_REF] María | A dynamically tuned sorting library[END_REF][START_REF] Bida | An automatically-tuned sorting library[END_REF], Fast Fourrier Transform [START_REF] María | A dynamically tuned sorting library[END_REF][START_REF] Steven | FFTW: An adaptive software architecture for the FFT[END_REF], etc.. Let now consider the problem specific approach philosophy in the perspective of evolution of algorithms and machine architectures. We can say that if only the machine architectures change, the philosophy of adaptive algorithms suggests that we might not necessarily need to re-design the problem specific approach (since the algorithm adapts itself to the platform). However, if the set of known algorithms for the problem changes, a design of adaptive algorithms is required in order to include this new algorithm in the suite (otherwise, it is possible that there exists a more efficient external algorithm than the adaptive algorithm). However, one cannot anticipate the algorithmics evolution on a computational problem. Moreover, depending on the utilization context, the set of algorithms required for solving a problem can change. For example, there is no advantage of using the quicksort algorithm in a context where there are only a small number of item to sort [START_REF] Knuth | The Art of Computer Programming[END_REF]. To deal with this, one can observe how parallelization is done in parallel computation. Parallel programming proposes both problem specific library (on sorting, searching etc.) and general API like MPI and pthreads for simplifying the implementation of parallel program. Considering this example, we can say that the design of automatic combination of algorithms also requires general API that eases the implementation task without being specific to a particular computational problem. This point of view has received an increasing interest over the last decade.

Among the most relevant studies, let us recall the AEOS method [START_REF] Demmel | Self-adapting linear algebra algorithms and software[END_REF] used on Self Adaptive Numerical System [START_REF] Eijkhout | The component structure of a self-adapting numerical software system[END_REF]. AEOS deals with automatic selection between multiple implementations of the same algorithm (in changing for example the order of the loops in the implementation). AEOS has been used in particular as a methodology for tuning and selecting kernels on dense and sparse linear algebra problems.

In [START_REF] Roch | On-line adaptive parallel prefix computation[END_REF], a framework is proposed for composing a general parallel algorithm with sequential algorithms in order to automatically balance the load during the parallel execution. Such a solution is typically well suited when there are parallel algorithms based on divide and conquer with few communications. In [START_REF] Buisson | A framework for dynamic adaptation of parallel components[END_REF], a framework (mainly conceptual) for dynamic adaptation of parallel codes (in a context of computational grid) is proposed.

The works that are certainly the closest to the contribution proposed of this paper are those done on hyper-heuristics [START_REF] Burke | Exploring hyper-heuristic methodologies with genetic programming[END_REF]. The idea is to develop generic search procedures that work on a space of algorithms solving the same problem. Typically, this search must select the most efficient algorithm solving a computational problem. This idea has been validated on many case studies like the resolution of time tabling problem [START_REF] Qu | Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems[END_REF].

In this work, we have proposed a framework for developing adaptive and parallel programs based on automatic combination of algorithms. The proposed solution is based on the multi-selecttion and can be considered as a first step towards the development of parallel hyper-heuristics.

We presented in this paper a new Framework for the design of adaptive libraries of algorithms. AMF is based on a collaborative approach allowing the users to constantly improve their knowledge on the resolution of a target problem. The adaptation is done through the multi-selection technique. The key point of this technique is the computation of efficient resource sharing for running concurrently a set of algorithms on an instance to solve. We described the implementation of this technique in AMF and provided a qualitative assessment on the Constraint Satisfaction Problem.

For continuing this work, our first envisioned issue is to extend AMF for distributed contexts. A first step for reaching this objective consists of introducing in AMF a support for executing algorithms designed based on multiple operating system processes execution. We believe that the main challenge for this purpose is in the distributed coordination of concurrent execution of algorithms. For the moment, we operated the coordination at the algorithmic level throughout a monitoring. For supporting parallelism at a process level, this variable can be mapped in a shared memory space accessed by all processes. Another option is to operate the coordination of execution at the operating system level. In this case, we will check the state of execution of launched processes and then stop all processes when one solution is found. A system coordination might also have the advantage of avoiding the necessity of manipulating synchronization informations while writing algorithms in the file AMF ALG.cpp.

Another interesting issue is to propose efficient generic selectors for the first phase of the multi-selection. We showed that for solving an instance under multiselection, there is a compromise to make between the number of algorithms selected and the overhead in the concurrent execution. In employing the recent techniques of multi-objective optimization, good algorithms selectors can be proposed for the first phase. Finally, we believe that the computation of the plan in the optimizer may also be improved. Indeed, for instance this problem is closed to the knapsack problem for which efficient heuristics already exists.

Figure 2 describes

 2 Figure 2 describes AMF internal components and dependencies among them.The key component of this architecture is AMF Learner that centralizes infor-

Fig. 4 .

 4 Fig. 4.: MinSum cost and execution time of heuristics for sequential optimization on a benchmark of SAT solvers

  Fig. 6.: Example of algorithms and benchmark reader

Fig. 7 .

 7 Fig. 7.: Ratio between the cumulative execution time obtained with online optimization and the one obtained with offline optimization.

  The Optimizer structure The Optimizer components contains 4 classes: AMF Optimizer, AMF AO, AMF MS, AMF MMO. Dependencies between these classes are presented in Figure3. The two classes AMF MSO, AMF MMO are

	AMF_Optimizer		AMF_Algp_desc{ int app_id;
			int app_type; // (seq. or parallel)
			int *Resource_Sharing;// Resource repartition
			int objective_function; //minsum or minmax
	AMF_MMO	AMF_MSO	float timeLimit; // <> 0 if mode = online ...
			...
	AMF_AO		virtual void getOnlineRS(AMF_Algp_desc );
			virtual void getOfflineRS(AMF_Algp_desc );
			...

} Fig. 3.: Classes of the optimizer component. The function getOnlineRS and getOf-flineRS are designed to compute a resource sharing in the online and offline modes.

specialized on the computation of resource sharing under respectively the Min-Sum and MinMax objectives (see Section 2.2). These two classes are derived from an abstract optimizer class (AMF AO). Finally, the class AMF Optimizer works as interface of communication for other components.

  Optimization heuristics in the parallel case (|A| = k, |I| = n and m resources)

	Heuristics Approx. ratio	Time complexity
	HIF	arbitrary	O(min(k, m).(n 2 k 2 + km 2 ))
	MAG	k -g + 1	O(n2 k-g .(m + 1) g .(nk))
	MA	2k -1	O(k)
	RAND	arbitrary	O(k)
	WTA	arbitrary	O(nk)
		Optimization heuristics in the sequential case
	HIF s	arbitrary	O(m.n 2 k 2 )
	WTA s	arbitrary	O(nk)
	RAND s	arbitrary	O(k)
	OPT s	1	O k

m Table

Table 2

 2

	Action	Modified Components	Description
	Definition of parallel	The files	AMF ALG.cpp and	The data structures for the PCSP in-
	PCSP algorithms	AMF ALG.h of AMF AContainer	stances are defined in AMF ALG.h and
				the algorithms in AMF ALG.cpp
	Copy of a PCSP bench-	AMF BContainer	A benchmark data file for PCSP is put in
	mark file in AMF			the Bcontainer
	Definition of a bench-	AMF BContainer	the code of a reader for PCSP instance is
	mark reader			written in the file reader.cpp
	Insertion of the PCSP	AMF Learner, AMF PContainer In using the method add app of the
	application			AMF Learner, one inserts the PCSP ap-
				plication. It modifies the portfolio engine
				and the configuration of the application
				table
	Insertion of a PCSP	AMF Learner, AMF BContainer In using the method add bench of the
	benchmark			AMF Learner, one inserts a PCSP bench-
				mark. It generates pointers towards read-
				ers for the BContainer and configure the
				benchmark table
	Global compilation	All components	The framework must be re-compiled to
				handle new codes generated in the previ-
				ous steps

.: Defining a new application and benchmark in AMF other algorithms. Let us suppose that data of PCSP instances as defined in the file AMF ALG.h are type CSPInstance. An example of algorithm for PCSP is described in Figure

Table 3 .

 3 : Execution time (in seconds) in the offline resolution mode for sequential CSP algorithms. p is the number of threads.

Table 4 .

 4 : Execution time (in seconds) in the offline resolution mode for parallel CSP algorithms

		|A| = 9, |I| = 225 and m = 8)
		Best alg.		Theoretical	Experimental
	p Best MinSum Best MinMax Th. MinSum Th. MaxSum MinSum MinMax
	1	526	31	526	31	526	31
	2	190	31	190	31	190	31
	3	70	30	70	30	70	31
	4	60	6	38	6	41	7
	5	53	6	27	6	30	7
	6	60	6	21	4	27	5
	7	65	6	19	4	32	5
	8	53	6	19	4	32	5

Table 5 .

 5 : Times for Benchmark profile generation and computation of optimal resource sharing

	Sequential		Parallel
	Optimization Profiling Optimization Profiling
	1 s	23 hours	4 s	160 hours

This is deduced from the fact that we stop the execution on each instance as soon as one algorithm completes its execution

A point (n, k) is valid if there is a benchmark of size n for an application of size k

This profile is given by the values C(Ai, Ij, p) described in Section 2.2


Beloufa Sabrina
email: sabrina.beloufa@renault.com

Cauchard Fabrice
email: fabrice.cauchard@u-bourgogne.fr

Vailleau Benjamin
email: benjamin.vailleau@renault.com

Vedrenne Joël
email: joel.vedrenne@ensam.eu

Boucheix Jean-Michel
email: jean-michel.boucheix@u-bourgogne.fr

Kemeny Andras
email: andras.kemeny@renault.com

Mérienne Frédéric
email: frederic.merienne@ensam.eu

Enhanced game mode for Eco-driving simulator

Keywords: Eco-driving, Driving simulation, Serious game, Learning, Human machine interface

The use of driving simulators is part of RENAULT's approach for eco-driving development. The geDRIVER project objectives were to: develop ECO mode for all, taking into account eco-driving criteria; develop a training business offer and develop specific assistance HMI (Human Machine Interface).

In terms of driving simulation, this induced a need to develop a wide range deployment training tools integrating multisensorial feedback, enhanced gameplay for scenario design, and driving analysis tool into ECO² simulator.

Several experiments were carried out, in order to evaluate validity of simulation for an eco-driving training purpose.

Results show that visual indicators is the most appropriate and that the eco-driving rule "gear up at 2500

rpm" is the most efficient. At last, the simulator appears to be an efficient tool, to understand and integrate eco-driving rules, and to improve economies in terms of CO2 emissions.

I. Introduction

Analysis of driver behavior has been the purpose of many studies for several years. This is linked with expansion of driving assistance systems in modern vehicles, as well as development of new systems and solutions. On the other hand, improvement in numerical technologies has enabled more detailed experimental studies conditions for behavior analysis with well controlled immersive driving situations (full-scale simulators, haptic feedback, designed scenarios, virtual reality, etc). However, only a few scientific studies focused on ecological behavior and fuel consumption (some applications of learning methods for truck drivers for example [KEM1]). Another new aspect, which was not often discussed in driver behavior studies, is learning processes.

This study was part of a double context: Today, technologies in support of learning are evolving to accompany the implementation of this directive (e-Learning, simulators).

The objective was to design and provide tools and methods for eco-driving behavior learning, in order to enable driver to improve their eco-performance, in the respect of environmental and safety rules. With a strong practical experience, this project aimed to reinforce position and utility of driving simulation between theoretical and practical learning. The consortium of the project geDRIVER (green efficient driver), labeled by the French national pole System@tic, included industrial partners: Oktal (leader), Renault SAS and KDC (eco-driving school), and research partners: Arts et Métiers ParisTech, and LEAD University of Bourgogne.

II. Eco-driving Method

Eco-Driving Program

More and more companies are concerned with eco-driving, in order to reduce fuel consumption and CO2 emissions, and reduce accidents risks. Whether it is large companies equipped with fleets of vehicles, or smaller ones, whishing to make their employees aware of eco-driving benefits: optimize and reduce operating costs, harmonize mobility and environment, and protect them as part of the road risk prevention in enterprises ( [START_REF] Anable | Supporting document to Climate Change Working Group of the Commission for Integrated Transport[END_REF]).

Renault has deployed an eco-driving program, illustrated with the label eco2 1 , which takes different forms:



Advice 5: Use engine wisely

Stop engine from 30 seconds stops; do not preheat engine; start engine quickly after ignition.

These are part of the advice provided during eco-driving lessons. During practical session, it is applied and adapted to various situations with specific traffic and road configurations.

Main findings from Renault and KDC internal studies and learning results analysis showed that eco-driving enables generally consumption (and CO2 emissions) gains of 10 to 20%. Improvement is noticed immediately after learning. Unfortunately, eco-performance curve goes down over time, for a residual gain of about 5%.

Another drawback was that drivers often may not go to the end of the experiment, organized during several weeks if not coached by a trainer.

This led to necessity to improve some points: necessity to do periodic reminders, and to improve interest of drivers for exercises. This means a necessity to have appropriate learning tool and appropriate application integrated. Driving simulator could provide an interesting solution.

Eco-driving simulation

Driving simulators are mainly used for driving learning, experimental research on human behavior, and automotive engineering ([Par1], [START_REF] Azzi | Eco-Driving Performance Assessment With in-Car Visual and Haptic Feedback Assistance[END_REF], [START_REF] Kemeny | Un simulateur de conduite pour la formation des conducteurs de véhicules poids-lourds[END_REF]). With evolutions and improvements of simulation techniques, as well as the increasing popularity of some gaming technologies, simulators have gradually become testing tools that could be provided turnkey. These more accessible solutions enabled to focus on contents (teaching, scripting, realism, interactivity). Fidelity of simulation provided by these tools is useful for application such as eco-driving learning.

DSC'12

Experimental studies of the project geDRIVER required specific content in order to enable validation of simulator as a pertinent learning tool for eco-driving. Techniques derived from videogames enabled to reinforce interest of the experiment and of the learning sessions [START_REF] Boucheix | Multimedia Simulation and Comprehension Aid Tool for Complex technical documents[END_REF]. Serious gaming is indeed now quite widespread for learning and awareness, and has been acknowledged as efficient and effective tool, with great attractivity, especially for the general public. In order to feed this content, analysis models for eco-driving, and performance monitoring were adapted to a learning context. New interactive guidance techniques based on ecologic and safety criteria were developed, and gameplay was enhanced with more interactive scripting techniques.

Eco-driving software architecture

As can be seen in Figure 1, the simulator was a one-person fixed-base simulator including an adjustable seat, a wheel, a gear stick, the clutch, gas and brake pedals. The player was immersed in the simulated environment by means of three LCD screens, audio speakers located in front and behind the seat, and vibrators embedded in the seat. The eye-tracking is a faceLAB apparatus and the eye-tracking data and the driving performance data are recorded at a frequency of 60 Hz.

Simulation was based on

Eco-driving analysis

A driving style measurement and analysis method was implemented and improved in order to adapt former measurement system and to validate this tool for simulated and real driving. A technical demonstrator was built in order to test interactions between SCANeR™ and KDC former tool. Each one runs on a dedicated PC and exchanging data through a network communication layer (cf. fig 2).

This tool analyses driving style with data based on driver actions on vehicle. These data acquisition system is implemented via a CAN bus interface and takes into account all vehicle and engine data (pedals position, acceleration, speed, rpm, distance, etc…). While comparing several identical driving courses data (for the same driver or for an eco-driving expert) it enables to determine global driving behavior (cumulated braking time, accelerations duration) and fuel consumption.

All this architecture was integrated into the cockpit of eco2 simulator shown on fig 1.

Interactive guidance techniques

Innovative interactive guidance techniques for eco-driving were built and implemented. A preliminary study was carried out, focusing on the guidance tools optimization, and the courses the subjects would have to drive on. The goal was to determine which sensory modality, or combination of modalities, was the most effective for each guidance dispositive. Then, the aim was also to see if the subjects could keep on using what they learned from this guidance dispositive when we removed it. Finally, we wanted to be sure that the guidance tools did not distub the driving behavior and activity.

The module was adapted to the simulation software and guidance dispositives integrated to the ECO² simulator. Global architecture is represented on fig. 3. Metaphors had to be interactive, easy understandable and not too heavy in terms of cognitive load. They included visual messages, sounds and tactile feedbacks. These guidance metaphors were connected to vehicle data and acquisition module.

Visual information concerned CO2 emmissions, gearbox engaged, action expected on gearbox, RPM ideal level, limit speed, messages concerning clutch and brake pedals. Illustration of visual feedback is visible on fig. 4. Sounds accompanied visual messages in the same situations of alerts, information, and were bips, spacialized 3D sounds, or vocal messages.

Haptic feedbacks were released through vibrations in the seat.

Enhanced gameplay

In order to implement these functionalities, improve simulation conditions, simplify use of the simulator, and result in a serious game configuration, several gameplays were built. The gameplays defined game modes, evaluation processes, and scenario events. They were designed to ensure sensitization of the player to eco-driving, and security. The developments also consisted in making SCANeR™ environment more accessible to trainers for creation of their own driving scenarios, with a high level scenarization tool. This included building of a new dedicated graphic interface, adapted to preparation of players' profiles, datafiles, and measurements. This interface had to be user friendly and enable introduction of learning sessions.

The game mode used was made of successive levels, illustrating different eco-driving rules, with dedicated scenarios. In each scenario, several events required specific interventions from the driver, corresponding to one eco-driving rule, the performance of which was evaluated.

A debriefing was presented to the player after a session. A score was calculated according to his eco-performance, and a detailed analysis of his drive provided. Some explanations could also be given, with advice to improve his score. Fig. 5

III. Eco-Driving Simulator Experiment

Several studies focused on attention and guidance during activity

([Bou1], [Bou2], [Low1], [Low2], [Sch1], [Bou3]).
The purpose of this study was to validate efficiency of geDRIVER learning, to quantify economies in CO2 emmissions, determine the respective contribution of each eco-driving rule to the achieved economy.The experiment was carried out in LEAD during July and August 2011. Subjects sample was composed of 72 persons, 45 males, and 27 females, aged 19 to 55 (mean age was 24). All of them had driving license for at least 1 year. They had driven 9000km in average during 12 last months (min 150, max 40000).

Progress of the geDRIVER learning was as following:

The player drove several dedicated courses, for learning or evaluation. Two of them were dedicated to learning, each one concerning a group of three eco-driving rules. For all courses, dashboard provided following information: tachometer, speedometer, gearbox indicator, GPS. Subjects were assigned to three groups: normal (with lessons and guidance system during training), control 1 (with lessons, without guidance), and control 2 (without lessons, without guidance).

In order to prevent from bias induced by difference in courses, or even habituation, a counterbalance system was used for initial and final courses between two half of subjects group. Courses were also equivalent in terms of curves, straight lines, specific events, etc…

The analysis performed on the CO2 emission with an ANOVA revealed a reliable Scenario x Group interaction, F (3, 69) = 8.54, p < .001. Results show a significant decrease of 10% in CO2 emissions in normal group, and of 7% in control 1 group. This indicates that interactive guidance systems help player to integrate focused eco-driving rules. In the control 2 group, no decrease is noticed, which indicates that differences noticed are indeed due to integration of eco-driving rules. Results are shown in fig. 6. Linear regression applied on results enables to estimate contribution of each rule to eco-performance. Two main conclusions can be enounciated: rules 1' and 2' seem to be the most efficient for CO2 emission decrease. Contribution of all other rules appears to be less evident. This can be partly explained by the fact that rule 1 is not very clear to players. "Gear up under 2500rpm" may encourage player to gear up too early, which is unefficient. A more precise message, such as "Gear up near 2400rpm" should be better interpreted. It's important to precise that mesures were also made to be sure that the learning of these rules has no effect on the travel times (by comparing the durations of initial and final courses), and security behavior of the subjects (by comparing several safety mesures between the initial and final couse).

CO² Emmissions

Conclusion

Results confirm the hypothesis that driving simulators provide efficient solution for eco-driving learning, with greater interest than classic learning tools. Rules concerning anticipation and deceleration strategy seem to be the most efficient for gamers. But better definition of the rules might provide better results. For example, to help rule 1, visual indicators could target ideal rpm area for gearing up.

In driving simulation experiment, it may be difficult to anticipate stops, because traffic lights and stop panels are not necessarily visible until 200-300m distance. Higher screen resolution, traffic, or visual signs may provide an efficient solution.

Further studies are planned in collaboration between Arts et Métiers ParisTech, LEAD and Renault to learn more on eco-driving electric cars, especially for an efficient use in the best safety and comfort conditions with optimal road traffic autonomy.

-

  Environemental context: reduction of energetic consumptions and CO2 emissions transports has become essential, and the object of socio-economic global issues. Drivers' behavior should change to take into account environmental criteria -Safety context: at the same time, European directive 2003/59 CE aimed to regulate qualification and learning for driver assigned to freight and passenger transportation, in terms of eco-driving and road safety.

  Communication campaigns were conducted in several companies and organisms, with distribution of communication kits, and demonstration of small static driving simulators (fig 1).

Figure

  Figure 1 : Static eco2 driving simulator

-

  SCANeR™ Studio v1.0, developed by Renault and Oktal and SCANeR™ DT v1.5 (training oriented version). Global architecture schema is represented in fig 2. Software evolutions were made so that utilization of SCANeR™ tool could remain generic. Main developments concerned: Integration of new simulator cockpit specific acquisition module to Studio v1.0 and DT v1.5; integration of new I/O information from cockpit commands -Industrialization on ECO-DS of the VEN interface (Virtual Extended Network), enabling communication and data exchange between distinct soft environments (vehicle data, driver evaluation variables, etc…) -Improvement of the Training Manager module of SCANeR™ DT v1.5 to manage training session database and interface.

Figure 2 :

 2 Figure 2: ECO-DS simulation architecture

Figure 3 :

 3 Figure 3: Metaphors restitution architecture

Figure 4 :

 4 Figure 4: Visual feedback on the dashboard

  illustrates a debriefing screen example.

Figure

  Figure 5: debriefing screen

  Rules were simplified versions of advices presented in the paragraph entitled Eco-Driving: 1: Gear up under 2500rpm 2: Drive with upper gearbox ratio possible 3: Maintain constant speed with clear road 1': Look far forward to anticipate decelerations 2': To decelerate: 1 release throttle, 2 gear down, 3 brake if necessary 3': Stop engine for more than 30sec stops Experiment progress was: Initial Evaluation (8 min) Eco-drive lesson 1 (1min43) -rules 1,2,3 Training 1 (8min) Eco-drive lesson 2 (2min10) -rules 1',2',3' Training2 (10min) Final evaluation (8min)

Advice 4: Manage climbs and descents

	 Embedded assistance systems are developed, with specific information feedbacks and dedicated HMI
	(Human Machine Interface), and active automatic systems having hand on vehicle performance and engine
	mapping.
	 Learning modules are still distributed by KDC, with theoretic and practical phases, respectively with
	presentation of several driving "rules" and advice, and with driving sequences on open roads. These are
	based on successive evaluations, with analysis criteria, enabling to quantify eco-performance of
	candidates, as well as on long-term (several months) eco-performance evolution study.
	According to Renault specifications (http://www.renault.com/fr/capeco2/eco-conduite/pages/eco-conduite.aspx),
	main rules and advice to remember for eco-driving are the following:
	Advice 1: Optimize gear shift
	Gear down near 1000rpm; gear up near 2000rpm for diesel vehicle, and 2400rpm for gasoline vehicle; select 4 th or
	5 th gear at 50km/h.
	Advice 2: Drive smoothly
	Keep a steady speed (if >40km/h); use engine brake, and as little as possible brake pedal (natural deceleration
	cuts off fuel injection); drive at 50km/h in 5 th gear, release throttle 100m before the traffic lights.
	Advice 3: Moderate accelerations
	Up to 50km/h, it is better accelerating strong enough to be quickly in 5 th gear; above 50km/h, accelerations have to
	be moderate; gear up quickly to 5 th gear.
	Keep speed in descent; slow down in climbs (without interfering with traffic), and stabilize if possible at a speed >
	40km/h; release throttle in descents.

Figure 6: Levels of CO2 emmissions for initial (white) and final (green) courses in g/km

  An important point is that no significant difference was noticed in driving time to achieve courses between normal and control 1 group. Irrespective of the groups the players were in, they took approximately the same time to drive the initial and final scenarios. This result showed that it is possible to modify one's own driving behavior in a way that reduces the CO2 emission level without losing any time in completing one's drive Several indicators were analysed to evaluate driver behavior in terms of road safety : collisions, time leaving the road, safety distance,with other vehicles, eyes position, violation of highway rules, reaction time to dangerous events and ability to maintain the car in the middle of the lane. None of these indicators, showed a deficit in safety between two courses.

		250,00
		200,00	223	199	221	205	218	219
	g/km	100,00 150,00	-10%	-7%		Initial Course Final Course
		50,00
		,00
			Normal	With Lessons,	Without Lessons &
					without guidance	Guidance System
	Paper Number					-9-

If we focus on respective contribution of different rules in CO2 emission decrease, results show first that all rules were generally integrated except rule 2. Players did not really use highest gearbox ratio.

DSC'12


Aurélia Decherf
email: aurelia.decherf@teledetection.fr

Aurélie Boccio

Benoît Terrier

Flavie Cernesson

Nathalie Lalande

Benoît Terrier

P Hal-Aurélia

Decherf

Benoit Terrier

Keywords: Indicateurs spatialisés, corridors rivulaires, occupation du sol, retour d'expérience, co-construction

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Expériences croisées sur la production d'indicateurs à partir d'une cartographie très haute résolution spatiale de l'occupation du sol dans les corridors rivulaires

Expériences croisées sur la production d'indicateurs à partir d'une cartographie très haute résolution spatiale de l'occupation du sol dans les corridors rivulaires.

Jointed experiences to produce land use indicators based on very high spatial resolution map: application to riparian corridors.

INTRODUCTION

Facteurs de contrôle de l'état écologique et physique des cours d'eau, les corridors rivulaires constituent un élément clé de gestion pour atteindre les objectifs de bon état requis par la DCE ainsi que pour préserver la biodiversité (trame verte et bleue

Le processus d'interaction

Pour prioriser les actions de restauration, l'Agence de l'Eau Rhône Méditerranée et Corse (RMC) et l'Irstea (ex-Cemagref unité TETIS) débutent un partenariat en 2010. Sur le bassin pilote de la Saône, il s'agit de transposer et mettre en oeuvre la méthode de cartographie développée afin de modéliser les relations pressions/état pour le milieu aquatique. Ce travail fait l'objet de nombreuses validations intermédiaires. Lors de la restitution de la cartographie (sept. 2011), la volonté affichée d'associer les gestionnaires de terrain a encouragé les Syndicats en charge de la gestion de la vallée de l'Ognon à proposer un partenariat de mise à disposition des données produites et de constructions croisées des informations dérivées. Ce partenariat triparti, « au fil de l'eau », a pour but d'identifier et de partager les différents usages des indicateurs construits à partir de données d'occupation du sol dans les corridors. L'objectif de cette communication est de formaliser et analyser les étapes de cette démarche selon les besoins de chaque partenaire et les apports réciproques.

RÉSULTATS

Les différentes dimensions de besoins

Les différents partenaires ont des besoins en indicateurs issus de l'occupation du sol liés à leurs missions propres et aussi liés aux externalités qu'ils doivent produire (figure 1) :

Les apports réciproques

La production d'indicateurs pertinents issus de la carte d'occupation du sol dépasse la convergence des besoins. Les apports réciproques sont de différents ordres :

• la pertinence descriptive des indicateurs (traduction adéquate des processus écologiques), la validité des différentes productions (précisions sémantiques et géométriques idoines) ;

CONCLUSION

La concomitance des besoins, a conduit à structurer une équipe de projet autour de la production d'indicateurs issus de la cartographie fine de l'occupation du sol dans les corridors rivulaires. Si la carte est la donnée d'entrée des indicateurs, elle est devenue le média de partage et d'échange des connaissances. On aboutit à une réelle co-construction des indicateurs qui en assure la légitimité.

Cette approche permet de construire une vision et une représentation partagées des corridors rivulaires et des problématiques associées. Une étape ultérieure sera d'évaluer l'impact de l'utilisation de tels indicateurs dans le processus de diagnostics voire dans les prises de décision.

LIST OF REFERENCES

  échelles (du tronçon au bassin) dans le diagnostic du Plan pluriannuel de restauration et d'entretien ; • TETIS : produire des méthodes de construction d'indicateurs environnementaux et spatialisés à différentes échelles. Si la carte d'occupation du sol dans les corridors rivulaires permet de répondre en grande partie aux besoins pour la production d'indicateurs descriptifs ou normatifs, utilisée seule elle montre ses limites pour certains besoins spécifiques (la caractérisation des zones humides).

  transferts de la recherche aux gestionnaires.

  Wasson JG, Villeneuve B, Mengin N, Pella H,Chandesris A. (2006). Quelle limite de « bon état écologique » pour les invertébrés benthiques en rivières ? Apport des modéles d'extrapolation spatiale reliant l'indice biologique global normalisé à l'occupation du sol. Ingénieries -E A T 47: 3-15. Allan JD, Erickson D, Fay J. (1997). The influence of catchment land use on stream integrity across multiple spatial scales. Freshwater Biology 37(1): 149-161. Tormos T. (2010). Analyse à l'échelle régionale de l'impact de l'occupation du sol dans les corridors rivulaires sur l'état écologique des cours d'eau. Doctorat. AgroParisTech. Montpellier. 426 p.

Figure 1 :

 1 Figure 1: Les différentes dimensions du besoin

  ). Leur restauration constitue un enjeu local délicat pour les structures chargées de la gestion des bassins versants. Il s'agit pourtant d'une action prioritaire aux niveaux du district et national, tant pour les Agences de l'eau, principaux financeurs de ces actions, pour l'Etat qui définit les politiques de restauration et met en oeuvre les rapportages.

	Pour aider à la décision multi-niveau et multi-acteur, il est nécessaire de disposer d'outils permettant
	d'évaluer les impacts des actions humaines sur le milieu aquatique et en particulier d'analyser à large
	échelle de la réponse biologique de ces milieux aux différentes pressions s'exerçant sur eux (Wasson
	et al. 2006). Dans de nombreux de cas, un effet significatif de l'occupation du sol des corridors
	rivulaires sur l'état écologique des milieux aquatiques a été mis en évidence. Un des outils de prise de
	décision consiste donc en une caractérisation fine de l'occupation du sol et sa dérivation sous la forme
	d'indicateurs. Cette communication présente le retour d'expériences croisées, entre scientifiques,
	gestionnaires institutionnels et locaux, autour de la construction d'indicateurs à partir de cette
	cartographie sur le bassin versant de l'Ognon.
	bases des données géographiques auxiliaires	2 ).	1 ,

2 LA MÉTHODE

2.1

La caractérisation fine de l'occupation du sol Les pressions générées par les différents types d'activités humaines sont nombreuses, variées et d'autant plus difficiles à appréhender finement sur les étendues visées (bassins versants, districts hydrographiques). Si certaines pressions industrielles ou urbaines pourraient être déterminées à partir des données de rejets ponctuels, les pollutions diffuses de toutes origines ne peuvent pas être directement mesurées et sont généralement estimées par la modélisation. Ces dernières sont rattachées à une « source surfacique » et à un mode de transfert spatialisé. L'approche qui en découle est donc de considérer l'occupation du sol comme le socle de définition de la pression anthropique (Allan et al. 1997). Aucun référentiel national n'est aujourd'hui disponible à l'échelle des corridors. L'utilisation des outils de la géomatique permet d'apporter des réponses opérationnelles (Tormos 2010) : la production d'une cartographie fine d'occupation du sol dans les corridors basée sur des méthodes de télédétection orientée objets appliquées à des données multi-source disponibles nationalement (images à très haute et haute résolutions spatiales dans le visible et l'infrarouge

Images de la BD Ortho© de l'IGN et images SPOT5©

GeoSud -CNES 2 BD TOPO© de l'IGN, Registre Parcellaire Graphique© de l'Agence de Services et de Paiement, Corine Land Cover© de l'Agence Européenne de l'Environnement