Romain Saussard
email: romain.saussard@renault.com

Boubker Bouzid
email: boubker.bouzid@renault.com

Marius Vasiliu
email: marius.vasiliu@u-psud.fr

Roger Reynaud
email: roger.reynaud@u-psud.fr

Optimal Performance Prediction of ADAS Algorithms on Embedded Parallel Architectures

Keywords: Heterogeneous Architectures, Embedded Systems, Performance Prediction, Image Processing

ADAS (Advanced Driver Assistance Systems) algorithms increasingly use heavy image processing operations. To embed this type of algorithms, semiconductor companies offer many heterogeneous architectures. These SoCs (System on Chip) are composed of different processing units, with different capabilities, and often with massively parallel computing unit. Due to the complexity of these SoCs, predicting if a given algorithm can be executed in real time on a given architecture is not trivial. In fact it is not a simple task for automotive industry actors to choose the most suited heterogeneous SoC for a given application. Moreover, embedding complex algorithms on these systems remains a difficult task due to heterogeneity, it is not easy to decide how to allocate parts of a given algorithm on the different computing units of a given SoC. In order to help automotive industry in embedding algorithms on heterogeneous architectures, we propose a novel approach to predict performances of image processing algorithms applicable on different types of computing units. Our methodology is able to predict a more or less wide interval of execution time with a degree of confidence using only high level description of algorithms, and a few characteristics of computing units.

I. INTRODUCTION

Vehicles increasingly provide ADAS (Advance Driver Assistance System) capabilities, as passive systems (e.g. lane departure warning system alerts the driver when the vehicle crosses a lane) or active systems (e.g. lane centering assist system controls car trajectory). Some of these systems use cameras and image processing algorithms to sense the environment and detect potential obstacles, we can cite lane detection [START_REF] Bertozzi | Gold: A parallel real-time stereo vision system for generic obstacle and lane detection[END_REF], obstacle detection [START_REF] Dagan | Forward collision warning with a single camera[END_REF], pedestrian detection [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], [START_REF] Geronimo | Survey of pedestrian detection for advanced driver assistance systems[END_REF], etc. As they process high amount of data, image processing algorithms need high computational capabilities. Most of state-of-the-art ADAS algorithms run on powerful computers but not in real time. However, image processing algorithms can often be parallelized, so they can benefit from using hardware accelerators like GPUs or multi-core CPUs. Automotive industry needs low-power high computational embedded systems to embed image processing applications on vehicles.

Semiconductor companies are moving into the market of embedded systems for ADAS with heterogeneous architectures. These architectures embed several processing units with different capabilities on the same SoC (System on Chip), often with massively parallel computing unit. We can cite the Tegra K1 SoC, or more recently the Tegra X1, of Nvidia (which embed ARM, GPU and ISP), the TDA2x SoC [START_REF] Sankaran | TDA2X, a SoC optimized for advanced driver assistance systems[END_REF] of Texas Instrument (ARM, DSP and EVE vectorial processor), or the EyeQ of Mobileye [START_REF] Stein | A computer vision system on a chip: a case study from the automotive domain[END_REF].

The problem of this type of architecture is the complexity to embed algorithms. First, finding the most suited heterogeneous SoC for a given application is not trivial. Then, as there are several processing units, it is not easy to find the best mapping between algorithms and processing units. Moreover, adjusting an algorithm to embed it on a single processing unit is quite time-consuming, that is why adjusting the algorithm for all processing units to determine the best association is unachievable. In light of that fact, there is a need for car manufacturers and suppliers to predict performances of algorithms on different processing units to help them to choose the best algorithm-processing unit association and the most suited SoC for a given application.

In this work, we introduce a novel methodology to meet automotive industry needs, to predict performances of computationally expensive ADAS algorithms on heterogeneous architectures. First, in section II, we describe the Nvidia K1 and TDA2x heterogeneous SoCs, their characteristics and capabilities. Then, in section III, we introduce our parallelism classification and the problem of kernel mapping optimization. In section IV, we present existing work on performance prediction, followed by our novel approach description in section V. We illustrate our methodology with an example extracted from an ADAS application in section VI. Finally, we discuss future work and conclude in section VII.

II. EMBEDDED HETEROGENEOUS ARCHITECTURE

Semiconductor companies such as Nvidia, Texas Instrument and Freescale propose heterogeneous architectures to meet automotive industry needs to embed image processing algorithms for ADAS. These architectures handle high performance computing with massively parallel computing unit (e.g. GPU or vectorial processor) and low-power consumption. In this paper, we propose a general approach which can fit with any of these SoCs, and we show some preliminary results obtained with Nvidia Tegra K1 heterogeneous SoC.

A. Nvidia Tegra K1 Architecture

The Nvidia Tegra K1 SoC is composed of quad-core ARM Cortex A15 CPU (1.8 GHz clock rate) providing ARMv7 instruction set and out-of-order speculative issue 3-way superscalar execution pipeline, each core has a NEON and FPU unit [START_REF] Lanier | Exploring the design of the cortex-A15 processor[END_REF].

The Kepler GPU of the K1 is composed of one streaming multiprocessor (SMX) of 192 cores [START_REF]Nvidia kepler GK110 architecture whitepaper[END_REF], accessible with CUDA [START_REF]Cuda C programming guide[END_REF] and the new standard OpenVX [START_REF] Rainey | Addressing system-level optimization with OpenVX graphs[END_REF]. This framework is a hardware abstraction layer for image processing applications supporting modern hardware architectures such as embedded heterogeneous SoCs. OpenVX is based on the implementation of image processing kernels designed by SoCs manufacturers, beneficing from hardware acceleration of architectures.

The parallelization with CUDA is qualified as SIMT (Single Instruction Multiple Threads). The GPU has three memories reachable by all threads:

• Global memory: read and write access.

• Constant memory: read access only.

• Texture memory: read access only, can interpolate adjacent data value, always handles boundary issues.

The global memory of the K1 is the same for GPU and ARM, and both can potentially access to the same data. Memory area of each processing unit is handled by the OS (L4T or Vibrante, which are both based on Linux kernel).

B. K1 Specific Features

The K1 also has several hardware processing units like Image Signal Processor (ISP) and Image Processing Accelerator providing fast and specific image processing algorithms such as debayering, noise reduction, lens correction etc. These units are very fast but the user can only control a limited set of parameters and the chaining order of kernels is restricted.

In addition of basic instructions, ARM and Kepler GPU have specific features which can be used to accelerate image processing algorithms. Thus, ARM processor provides SIMD instructions with NEON units [START_REF] Mitra | Use of SIMD vector operations to accelerate application code performance on low-powered ARM and Intel platforms[END_REF]. In order to handle the issues of concurrent reading and writing, CUDA provides atomic instructions based on hardware design.

The Nvidia GPU texture memory provides couple of advantages for reading images data. When accessing to non-integer pixel coordinates (e.g. Im[i-0.5][j-0.5]), texture units handle linear interpolation. This is cost-free because it is computed by hardware design. Moreover texture units handle access to pixels outside the image (e.g. Im[-1][-1]), also cost-free.

C. Texas Instrument TDA2x SoC

The TDA2x is composed of four different types of programmable units. First, it provides 750 MHz dual core ARM A15 and dual-Cortex-M4. These computing units do not bring that much computing capability (A15 core on TDA2x is 4 times less powerful than the one in K1), but they can be used for data management, video acquisition control / rendering, high level decision making, etc.

To handle heavy image processing tasks, TDA2x provides a mix of Texas Instrument fixed and floating point TMS320C66x DSP (Digital Signal Processor) and up to four EVEs (Embedded Vision Engine) cores. TMS320C66x is the most recent DSP from Texas Instrument, it can handle up to 32 multiply accumulate operations per cycle. Each EVE is a 650 MHz core, optimized for image processing, composed of one specific RISC processor and one 512-bit vector coprocessor.

III. HARDWARE ACCELERATION AND KERNEL MAPPING

In order to increase performance of a given algorithm, we have to identify parts of code which can benefit from hardware accelerations of a given architecture. This implies to separate the algorithm in more or less fine blocks called kernels.

A. Parallelization Level and Classification

Execution time of a given kernel can be accelerated by using different levels of parallelization of a given architecture. First, one can address parallelism at register level, which we usually call SIMD instructions or vectorization (e.g. NEON for ARM). Some compilers can handle automatic vectorization, e.g. GCC [START_REF] Naishlos | Autovectorization in GCC[END_REF], but optimization result can vary depending on compiler.

Secondly, computing units often provide multi-core (ARM provides 4 cores and GPU 192 CUDA cores on K1 SoC). This parallelism can be accessed by using different API, e.g. for multi-core CPU, with pthread (for linux), or at more generic level with OpenMP [START_REF] Dagum | OpenMP: an industry standard API for shared-memory programming[END_REF] and C++11/14 parallel features. Pthread is a low level API, which enables fine-grained control over thread management but may be difficult to implement, sometimes too much complicated (depending on code complexity). On the other hand, OpenMP is a high level API, easier to implement, but may have different performances than pthread.

At higher level, heterogeneous architectures offer multicomputing units with different capabilities. Each of these computing units may execute different kernels concurrently. Speed increasing brought by parallelism is not the same for all kernels, of course it depends on how kernel can be parallelized. To characterize kernels parallelism degree, we propose four simple classes, each one with a specific prediction model:

• Simple parallelism P 0 : kernels for which there is no dependency between data, each operation can be executed without the result of another one, so concurrently, e.g. convolution.

• Parallelism using atomic instructions P 1 : kernels for which different threads may write on the same shared data at the same time. Thus mutex, memory barriers or atomic instructions should be used, e.g. histogram construction.

• Parallel reduction P 2 : kernels for which parallel reduction can be used, e.g. computing the sum of vector elements.

• Iterative kernels P 3 : kernels for which each iteration depends the on result of the previous one, e.g. if

u i = f (u i-1
). Due to this dependency, kernels in their original form cannot be parallelized. However, operations executed at each iteration, e.g. f (u), may be parallelized.

Complex algorithms provide a mix of kernels which belong to different parallelism classes.

B. Kernel Mapping Optimization

Embedding a given algorithm on a heterogeneous architecture is a difficult task because one can not easily find how to allocate kernels on the different processing units (kernel mapping) [START_REF] Zhou | Task mapping in heterogeneous embedded systems for fast completion time[END_REF]. We propose a metric to evaluate a static kernel mapping efficiency.

Let P be the vector of the processing units of a given heterogeneous architecture, K be the vector of the kernels of a given algorithm, the matrix M constitutes the mapping of K on P , given by P = M.K. Let ϕ be the spatiotemporal dependency matrix: a kernel instance K i (t) may depends on the execution of another kernel K j (t), and its previous instance K i (t -1); ϕ is used to find possible execution pipelines. Let τ (M ) be the execution function (returning the execution time for each kernel), δ(M ) be the transfer function (returning the transfer delay needed for each kernel), η(M ) be the occupancy function (returning the occupancy for each computing unit) and f (P, K, ϕ, τ (M ), δ(M ), η(M )) be the cost function (returning the global execution time of the algorithm). The aim of kernel mapping optimization is to find M minimizing f :

arg min M [f (P, K, ϕ, τ (M ), δ(M ), η(M ))] . (1)
Parameters of function f can be measured or predicted for different M . Measure needs all kernels implementation on all processing units (very time consuming), but prediction needs kernels and architectures analysis (very efficient but needs deep SW / HW knowledge).

IV. RELATED WORK

The aim of performance prediction is to estimate the execution time of a given kernel on a given computing unit. It needs characterization of the computing unit (provided by manufacturer or by benchmark results), and characterization of the kernel (high level description, source code analysis, or analysis of binary file).

The difficulty for performance prediction techniques is to find the best compromise between complexity of model and precision of predictions. In fact if technique needs a full optimized source code in order to estimate execution time on one target, it does not bring that much gain compared to measure real performance on real embedded system. Whereas, if technique needs only a high level description of a kernel in order to predict performance for different computing unit, one can rapidly find what target will bring the best performance for that kernel.

A survey of performance modeling techniques is given in [START_REF] Lopez-Novoa | A survey of performance modeling and simulation techniques for accelerator-based computing[END_REF], according to it three main approaches for performance modeling can be found in literature: analytical modeling, machine learning, and simulation. A performance simulator is able to reproduce a computing unit behavior, it can give a lot of information, identify bottlenecks, predict performance, etc, and generally obtains a fine estimation. Some simulators address hybrid architectures (CPU+GPU), e.g. [START_REF] Ubal | Multi2sim: a simulation framework for CPU-GPU computing[END_REF].

Using an architecture simulator implies to port kernel to simulator, which represents about the same amount of work as embedding kernel on the architecture. Moreover, a fine simulation of the system implies a very long execution time.

An analytical model is a set of equations which represents characteristics of the system (kernel and computing unit). Machine learning techniques extract some characteristics by using a set of code and hardware features, then it performs by using feature selection, clustering and regressions techniques to estimate execution times of a kernel, e.g. [START_REF] Kerr | Modeling GPU-CPU workloads and systems[END_REF] which addresses CPU and GPU.

Most of analytical model handle performance prediction for only one type of architecture. In [START_REF] Hoste | Performance prediction based on inherent program similarity[END_REF], authors propose a model based on 47 architecture independent characteristics. Then performances are predicted by using programs in a benchmark suite and measuring similarity between benchmark programs and application, using the 47 architecture independent characteristics. Authors show results on different CPU architectures, but do not address neither GPU nor embedded architectures like DSP.

The famous model of Hong and Kim [START_REF] Hong | An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness[END_REF] addresses performance prediction for GPU with two metrics: Memory Warp Parallelism (MWP) and Computation Warp Parallelism (CWP). The aim of this two metrics is that if M W P ≤ CW P then performance is limited by memory bandwidth and latency, but if CW P > M W P then memory latency is hidden by computing operations. Authors report 13.3% mean error on execution time estimation.

The roofline model [START_REF] Williams | Roofline: an insightful visual performance model for multicore architectures[END_REF] uses approximatively the same approach by studying the arithmetic intensity of application and memory / computational bandwidths of architecture. However, it is not used for performance prediction, only for bottleneck highlighting and code optimization. The boat hull model [START_REF] Nugteren | The boat hull model: enabling performance prediction for parallel computing prior to code development[END_REF] adapts the roofline model to provide performance prediction. It is based on a set of primitives, kernel complexity, and memory / computational bandwidths of architecture. It shows good results, 3 and 8% of error for 2 applications. However, the model is limited to kernels which fit in classification given in [START_REF] Nugteren | A modular and parameterisable classification of algorithms[END_REF], and cannot handle arbitrary code.

V. PERFORMANCE PREDICTION USING THE COMPUTING PROFILE

We propose a novel model for performance prediction which can address multiple architectures, is not limited to a set of primitives, can be used without specific optimized source code and does not need a deep knowledge of architectures. Our methodology is based on a kernel descriptor, called the computing profile.

A. Basic Level of Classification

A kernel can be defined as a set of well-defined instructions, and each instruction can be classified in two classes: computing instructions, and memory instructions. Secondly, we can classify each computing instruction. The key is that one class of computing instructions is executed by one type of unit on the computing unit, e.g. additions will be executed by the ALU, and floating point operations by the FPU.

Classes of instruction are:

• S Int: simple operations on integer: add, sub, cmp...

• M Int: operations with multiplications on integers, this includes multiply accumulate operations.

• Float: floating points operations, instructions computed by the FPU.

• Specific: specific operations which often encapsulate several instructions, e.g. div, sqrt, etc.

• Branch: branching instructions, e.g. for loop, if, etc.

• Address: addressing operations, e.g. accessing to the ith element of an array.

• Memory: load and store instructions.

B. Computing Time Prediction with the Computing Profile

The computing profile of a kernel is an illustration of resources needed by this kernel. The aim is not to get the complexity (number of operations), but to know which classes of instructions are used.

The profile is the ratio of each class, this is the number of instructions of one class divided by the number of instructions of all computing classes. Let C be the set of computing instructions (no memory instructions):

C = {S int, M int, F loat, Specif ic, Branch, Address} (2)
Let N c be the number of instructions associated with class c, with c ∈ C. The ratio for the class c, r c is:

r c = N c i∈C N i . (3)
The computing profile shows us which class of instructions is the most used (the maximum of the r c for all c ∈ C). This information can be used to choose the best architecture for the algorithm. For example an algorithm with a of branching operations will have poor performance if embedded on GPU, but could have good performance on ARM, with speculative execution.

Moreover, if we know the throughputs of different classes of instructions for a given architecture, we are able to estimate the computation time for each class of instructions on this architecture. Let p c,a be the throughput (in operations per cycle) of architecture a for class of instructions c, computation time (in cycles) T c,a is:

T c,a = N c p c,a . (4)
If architecture a is scalar, different instructions of different classes cannot be executed simultaneously, so the total computation time is the sum of all T c,a :

t a = i∈C T i,a . (5)
If architecture a is superscalar, and in the optimal case (when instructions of different classes follow each other with good timing in order to get the maximum benefit from the superscalar capability of the architecture), the computation time is given by the maximum of all T c,a :

t a = max {i∈C} T i,a . (6)
State-of-the-art architectures are all superscalar, thus we can estimate an execution time interval for the kernel associated with architecture a. In the best case (when the superscalar capability is fully exploited), the computation time is given by the maximum of all T c,a . In the worst case (when the superscalar capability is not exploited), the total computation time is the sum of all T c,a :

t min,a = max {i∈C} T i,a t max,a = i∈C T i,a . (7)
Given a kernel and a computing unit, we are able to estimate a computation time interval. The model is based on throughputs of architectures, p c,a , this information may be given by manufacturers. Moreover, we establish throughputs for different computing units by using a benchmark, which measures the time to execute a known number of instructions. As our methodology is applicable to different types of computing units, it is possible to compare prediction for different architectures by knowing the clock frequency of each computing unit. If the arithmetic intensity of kernel is high enough then memory access latency are hidden by computation time, thus execution time is equal to computation time. However, if the execution time is limited by memory delay then execution time is greater than predicted computation time. In order to address prediction where performance depends on other parameters than computing profile and throughput, we are using a generic benchmark-vectors set which automatically extracts parameters of the system. The extracted parameters are specific for a given architecture and compiler, it can be acceleration provided with auto-vectorization, memory access delays, transfers delays between computing units, etc. Thus, both information from computing profile and benchmarkvectors set are used to obtain predicted performances and the best mapping for a given algorithm and heterogeneous SoC.

C. Prediction for Consecutive Kernels

With computing profile prediction, we can obtain an interval of predicted execution time for a given kernel and different computing units. However a complete algorithm is composed of consecutive kernels, so we have to associate predictions of multiple kernels in order to predict performance of a complete algorithm.

First, we can simply use interval arithmetic, to sum intervals of the different kernels in order to obtain another interval. This imply a loss of precision because of a larger interval. Let an algorithm be composed of two consecutive kernels k 1 and k 2 , let x 1 , x 2 be the real execution time of k 1 and k 2 on a given computing unit. Let [a 1 , b 1 ], [a 2 , b 2 ] be the predicted interval obtained with computing profile for k 1 and k 2 , such as

x 1 ∈ [a 1 , b 1 ] and x 2 ∈ [a 2 , b 2 ]
. This approach returns another interval for the predicted total execution time:

(x 1 + x 2 ) ∈ [a 1 + a 2 , b 1 + b 2 ].
The exact value of execution time is unknown (until we measure it in real condition), so this value belongs to the predicted interval [t min , t max ]. Without any other specific information, we can modelize the possible values for the execution time as a uniform distribution over the predicted interval [t min , t max ]. As predictions of two different kernels are independent (as long as they are not executed concurrently), summing two predicted execution times imply summing two independent random variables. Let us now consider two independent random variables X 1 and X 2 representing the estimated execution times, and two uniform distributions f X1 (p) and f X2 (p), describing the relative likelihood that X 1 = x 1 and X 2 = x 2 , defined such as:

f Xi (p) = 1 bi-a1 for a i ≤ p ≤ b i , 0 for p < a i or p > b i , i ∈ {1, 2}. (8)
Thus:

P r[p 1 ≤ X i ≤ p 2 ] = p2 p1 f Xi (p)dp. (9)
As X 1 and X 2 are independent, the probability density function of their sum, f X1+X2 , is given by the convolution of the two density functions:

f X1+X2 (p) = ∞ -∞ f X1 (p -u)f X2 (u)du. (10)
The density function

f X1+X2 (p) is non-zero for p ∈ (a 1 + a 2 , b 1 + b 2 ) and is maximum for p ∈ [min(a 1 + b 2 , a 2 + b 1 ), max(a 1 + b 2 , a 2 + b 1 )].
For both approach predicted interval become larger each time we add a kernel. However the probabilistic approach enables to reduce the estimated interval with a degree of confidence, as shown in [START_REF]Cuda C programming guide[END_REF], thus we obtain a better precision for performance prediction.

VI. CASE OF STUDY: HISTOGRAM OF ORIENTED GRADIENTS EMBEDDED ON THE K1 SOC

To illustrate our method for performance prediction, we take an automotive use-case: pedestrian detection application. We choose to implement the famous algorithm of Dalal and Triggs, which uses histogram of oriented gradients (HOG) descriptor for pedestrian detection [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. We choose to focus on HOG construction, the algorithm processes in 3 steps: The different steps are illustrated in Fig. 1. Both step 1 and 2 belong to P 0 , so are easy to parallelize. However step 3 computes a histogram for each cell (8 × 8 pixels), this imply to accumulate shared values for pixels of a same cell, thus this kernel is P 1 at pixel granularity.

In order to achieve high arithmetic intensity, temporary values are stored in small buffer, benefiting from low latency of local memory (L1 cache or register).

A. Prediction on ARM

First, we apply prediction model for ARM using one core and no vectorization. Horizontal, vertical and norm of the gradient computation needs 24 S Int and 4 Branch operations, so predicted execution time is t ∈ [START_REF] Naishlos | Autovectorization in GCC[END_REF][START_REF] Ubal | Multi2sim: a simulation framework for CPU-GPU computing[END_REF] clock ticks per pixel.

To achieve good performance for the orientation computation, we choose to replace atan() operations by successive branches and to use integer instead of floating point numbers. Thus predicted execution time for orientation computation is t ∈ [27, 38] clock ticks per pixel.

In the last step, each pixel of a cell vote for an orientation. As one thread handle all pixel of one cell, there is no need of atomic instructions, so predicted time is t ∈ [START_REF] Sankaran | TDA2X, a SoC optimized for advanced driver assistance systems[END_REF][START_REF] Lanier | Exploring the design of the cortex-A15 processor[END_REF].

Finally, the probability density function is:

f (p) =                           
For example, we can affirm execution time t ∈ [48, 57] with 79% of confidence.

As all kernels are P 0 , execution time ARM using 4 cores is 4 times faster than ARM using 1 core. For our test, we work with 640 × 480 image, on 1.8 GHz ARM using 4 cores. Thus prediction gives us t = 2240µs ± 8.6% with 79% of confidence. Real execution time is t real = 2194µs.

B. Prediction on GPU

For GPU, we choose to focus only on the two first steps because histogram construction is P 1 and needs atomic instructions whereas prediction for P 1 kernels are not discussed in this paper. In order to maximize occupancy, each thread computes 4 pixels. For the same operations, prediction on GPU gives us t ∈ [0.75, 1.65625] clock ticks per pixel, or t = 134µs ± 30% to compute gradient norm and orientation for a 640 × 480 image (clock rate of GPU is 696 Mhz).

The kernel needs to load 4 Words (16 pixels) per thread from global memory, according to our benchmarks these memory operations cost 230µs, which is greater than predicted computation time. Thus execution of our algorithm will be limited by memory bandwidth and latency. Real execution time is t real = 244µs. We also measure execution time without load operations: t computation = 132µs. Full execution time, included all steps and memory transfer, is 1030µs.

C. Example of Kernel Mapping

Our application is composed of 3 kernels, and the K1 is composed of 5 computing units (1 GPU and 4 ARM cores), thus 125 different mapping can be tested, and different execution pipelines can be explored. For TDA2x, there are 512 different mapping. Instead of testing all these configurations, it is possible to use our performance prediction model to find the best mapping.

Thus, for K1 our methodology gives us as best mapping to execute the first two steps on GPU and histogram construction on ARM. By using a shared memory area and by optimizing execution pipeline (both ARM and GPU can run at the same time), we achieve execution time t = 670µs.

VII. CONCLUSION AND FUTURE WORK

In this work, we have introduced a novel approach for performance prediction addressing multi-architectures, and operating without specific and optimized source code of application for each architecture. Our methodology is based on a high level description of kernels, the computing profile, and computing throughputs of architectures. We have shown, with an example extracted from an ADAS application, our approach is able to predict a more or less wide interval of execution time with a degree of confidence.

We are working to improve our methodology by taking into account memory delay to predict performances of kernels with small arithmetic intensity. Thus, we are adapting the approach of boat hull model to our methodology, classifying type of memory access found in image processing algorithms and studying there behaviors. Moreover, we are applying our methodology to TDA2x SoC to confirm the general approach for computing units like vectorial processor.

In a future work, we will propose results on kernels which belong to other parallelism classes than P 0 . Finally we will show performance prediction using both computing profile and parameters extracted with our set of benchmarks, in order to predict all terms of (1). Thus, we aim to deal with performance prediction of a complex application for different heterogeneous architectures, to help with kernel mapping optimization, and to choose the best suited SoC for a given application.

Fig. 1 :

 1 Fig. 1: Successive steps of the HOG descriptor.

1 )

 1 Horizontal and vertical gradient computation obtained by convolution and L1-norm: {S Int = 0.86, Branch = 0.14}. 2) Gradient orientation computation: {S Int = 0.52, Branch = 0.33, M Int = 0.15}. 3) Construction of the histogram of orientation for each cell (8 × 8 pixels in our case): {S Int = 0.82, Branch = 0.18}.


Alain Aubert
email: alain.aubert@univ-st-etienne.fr

Nathalie Bochard
email: nathalie.bochard@univ-st-etienne.fr

Virginie Fresse
email: virginie.fresse@univ-st-etienne.fr

AN ADAPTIVE EMBEDDED ARCHITECTURE FOR REAL-TIME PARTICLE IMAGE VELOCIMETRY ALGORITHMS

Particle Image Velocimetry (PIV) is a method of imaging and analysing fields of flows. The PIV techniques compute and display all the motion vectors of the field in a resulting image. Speeds more than thousand vectors per second can be required, each speed being environment-dependent. Essence of this work is to propose an adaptive FPGA-based system for real-time PIV algorithms. The proposed structure is generic so that this unique structure can be re-used for any PIV applications that uses the cross-correlation technique. The major structure remains unchanged, adaptations only concern the number of processing operations. The required speed (corresponding to the number of vector per second) is obtained thanks to a parallel processing strategy. The image processing designer duplicates the processing modules to distribute the operations. The result is a FPGA-based architecture, which is easily adapted to algorithm specifications without any hardware requirement. The design flow is fast and reliable.

INTRODUCTION

Particle Image Velocimetry PIV is a method of imaging and analysing fields of flow in critical environment. The initial groundwork for a PIV theory was laid down by Adrian [START_REF] Adrian | Statistical properties of particle image velocimetry measurements in turbulent flow[END_REF] who described the expectation value of the auto-correlation function for a double exposure continuous PIV image. Nowadays many techniques exist and they all remain computing intensive [2]. Traditional systems are therefore not suitable for real-time PIV applications as they cannot achieve the required high performance and be integrated in the critical environment. From an algorithmic point of view, several parameters depend on the experimental environment. The size of images, camera frequency and other information are tailored for a given environment as they depend on the characteristics (size and speed) of the fluid.

As a result, an embedded dedicated architecture must be designed for real-time PIV algorithms. This system must be adapted to the given algorithm specifications to meet the constraints without requiring a complete system redesign when the critical environment changes. To date, FPGAs are increasingly used in embedded systems as they can achieve high-performance in a small footprint. As modern FPGA integrate many different heterogeneous resources on one single chip, the complete image processing algorithm can be imple-mented without any other external resources. More importantly, the reconfigurable aspects of FPGA give the circuit the versatility to change its functionality according to the algorithm requirements.

Essence of this work is to propose an adaptive embedded architecture dedicated to real-time PIV algorithms. According to the given constraints and the required results, the designer changes the FPGA-based architecture with only few modifications and without any hardware requirement.

This paper is organised into 4 further sections. Section 2 presents the Particle Image Velocimetry algorithm. Section 3 introduces the proposed FPGA-based system with the global structure. Experimental results are presented in section 4 and section 5 concludes the paper. Indeed, small particles are used as markers for motion visualisation in the studied flow as shown in figure 1. This is a non invasive measure as the sizes of particles do not alter the flow or fluid properties [START_REF] Willert | Digital particle image velocimetry[END_REF].

PIV ALGORITHM

Particle

Two images are taken from one or two cameras within a short time interval t and t+∆t. In our application two single exposure image frames are recorded by one camera only. Images recorded by the camera are divided into small sub-regions called interrogation areas or interrogation windows.

From the interrogation window of the second image is extracted a pattern. This pattern is shifted in the corresponding interrogation window in image1 and both are direct cross-correlated as shown in equation 1.

( , ) 1( , ) 2( , )

x y F i j s x y s x i y j = × --∑∑

where s1 and s2 respectively represent the grey levels of the interrogation windows from images 1 and 2. The resulting output on the correlation plane is a single peaked function where the peak represents the displacement of the particles (figure 2). Direction of the displacement is determined unambiguously because the images from exposure 1 and 2 are recorded separately.

FIGURE 3. Resulting image of PIV

The resulting image is a set of vectors indicating the flow displacement as shown in figure 3. Traditional technique using grey-level images is adapted to binary direct cross-correlation to ensure an easier implementation on programmable logical circuits. A binary direct crosscorrelation gives efficient results if preceded by a suitable binary operation as shown in [START_REF] Dubois | Design of a binary correlator component and its integration in Round-About architecture for real-time motion measurement[END_REF]. Multiplications used in equation ( 1) are replaced by XNOR logical operations:

( , ) 1( , ).

.

2( , )

x y

F i j s x y XNOR s x i y j

= -- ∑∑ (2)
PIV algorithm is suitable for parallel processing as the direct cross-correlation computation is highly parallelisable. Two cross-correlated interrogation windows are independent of each other. A unique operation is computed simultaneously on different interrogation windows. These complex computations are therefore good candidates for a hardware real time implementation. First characteristic of PIV applications is unbalanced data flows between input and output as showed in figure 4. The input data flow captures several images meaning that input data correspond to thousand of pixels. The output data flow represents a little number of vectors. Another characteristic is the data parallelism inherent to this application. The correlation is duplicated several times (according the sizes of image and interrogation window) and processing operates on local pixels.

FIGURE 4. Main characteristics of PIV applications

Using these characteristics, a generic structure for PIV al gorithms is defined.

DEDICATED ARCHITECTURE

The FPGA-based system presents a Globally Asynchronous Locally Synchronous (GALS) architecture (figure 5). For all GALS structures, each module runs at its own fre quency and communicate asynchronously with a handshake protocol. All synchronous blocs units are therefore independ ent. As a result, a modification required for a specific module does not alter the rest of the architecture. For example, a CMOS image sensor must be replaced by a camera with a higher frequency. The modifications only concern the acquis ition module as other modules are independent.

A main characteristic is the communication ring for control data and output data. All modules are inserted around this ring by means of an asynchronous wrapper structure. This wrapper is a 4-phase handshake protocol and is identical for all types of module. The control remains identical and trusty operations are insured. The advantage of this ring includes minimizing latency as several commands can run simultaneously inside the ring. Empty commands can also be sent by the control module. This empty command can be used by any module to send some results back to the control module. As all modules are inserted around the communication ring, there are no limits in the number of inserted modules. And a module insertion does not modify the global structure. The advantage is a unique communication protocol whatever the number and type of modules. This structure handles different type of operations which are required in PIV applications. All these operations are designed in specific modules [START_REF] Lelong | Image processing implementation on embedded system ; physical parametres measurements by real-time correlation[END_REF].

Different type of modules

•

The Control Module sends commands to each module through the communication ring. These commands activate predefined macro functions in the target module. The integrity and the acceptation of the com mands are checked with a flag inserted in the same command that returns in the con trol module. As all commands are sent from this module, the scheduling is specified in the control module. In the same way, this module receives resulting data transferred coming from processing modules.

•

The Acquisition Module produces all CMOS image sensor commands and re ceives CMOS image sensor data. One part takes the 10 bit-pixel data from the sensor and generates one bit data thanks to a binar isation operation. As the binarisation de pends on the critical environment (i.e. the position of the camera and the acquired scene), this pre-processing operation can use either a unique threshold for the entire image or a local and adaptive threshold for each sub-region.

32 binary data are packed and sent to the storage module.

All commands dedicated to acquisition operations (win dowing, configuration, pre-processing…) are received from the Control Module through the ring.

•

The Storage Module stores incoming im ages from the Acquisition Module. Memory banks are FPGA-embedded memories, and writing and reading cycles are supervised by the control module.

•

The Processing Module contains the logic, which is required for the direct cross-correl ation operations. The result from the image processing is then sent to the control mod by means of the communication ring. More than one processing module can be used for the parallel direct cross-correlation operations.

In the GALS structure, each type of modules runs at their own frequency. For the following implementations, the used are given in table I.

Asynchronous wrapper

An asynchronous wrapper, figure 6 is designed to accept multi-clock domains. Each module is a synchronous module running at its own frequency. Communications between modules are asynchronous and they use a single-rail data path 4-phase handshake. The wrapper includes two independent asynchronous units. One receives frames from the previous module and the other one sends frames to the following module at the same time.

IMPLEMENTATIONS AND RESULTS

For the following implementations, the size of images is 320*256 with 80 interrogation windows (with a size of 32*32 pixels). The FPGA-based system is a NIOS II board with a Stratix II 2S60 FPGA. Image data are acquired in a 100ns CCD sensor.

The initial architecture contains 4 modules, one module for each type of operation. From this structure is added one or more processing modules in the communication ring that makes the execution time faster. The binary cross-correlations operations are then proceed in a parallel design strategy. As a consequence all processing module execute a binary cross-correlation operation several times. With an architecture that contains one processing module, this module performs all cross-correlation operations, and generates 80 vectors. With an architecture that contains two processing modules, both modules execute half of the cross-correlation oper-ations, each processing module giving 40 vectors. And so on…

The proposed architecture is implemented with one processing modules up to 6 processing modules. The implementation results are given in table II. Observation is as follow: the binary cross-correlation operations are distributed onto all processing modules. The parallel design strategy equally distributes the operations for each module. As a result, the number of vectors per second increases when the number of processing modules increases. This FPGA-based system can handle high-speed constraints such as more than 80000 vectors/second and be adapted to high-speed applications. With 6 processing modules, this system can work with a speed of 1 000 images/second (for a 320*256 image) and more than 330 images per second for a 512*512 image.

As the processing modules are inserted around the communication ring, there are no restrictions in the number of processing modules. The communication remains unchanged and resources required for the communication between modules are few.

FIGURE 7. Number of vector per second per number of processing modules.

Therefore, this FPGA-based system can integrate a high number of processing modules. As shown in figure 7, the number of processing depends on the specified speed (number of vectors per second). The image processing designer numbers how many processing modules are required and inserts them in the architecture. Theoretically, the number of processing modules is unlimited. The number of required resources depends on the number on processing modules. Therefore this number of processing modules will depend on the available FPGA resources. On the other hand, the communication ring will slow down the system for a very high number of processing modules. Indeed, the execution time decreases for an increasing number of modules but the communication time between neighboured modules remains unchanged. Present work consist in evaluating the limit (i.e. the number of processing modules) for which the communication ring will slow down the system.

CONCLUSION AND PERSPECTIVES

As a result, this FPGA-based system presents a generic architecture that can be easily adapted to any real-time PIV algorithms, which uses the cross-correlation technique. All functional blocks remain unchanged only the number of processing modules changes.

According to the speed, the image processing designer evaluates the number of processing modules. Then, he duplicates an identical processing modules several times around the communication ring without any functional modifications. All other type of blocks remain unchanged that makes the design flow fast and reliable.

Future work consists in demonstrating that changing any external devices does not alter the rest of the structure. The CMOS sensor will be therefore replaced by another external devices such as a camera or a CCD sensor with another frequency. The GALS structure ensures to integrate any modules running at a different frequency. In this paper, only the speed changes. Perspectives are to prove that this generic architecture can be also easily modified when the size of the image changes or the interrogation window.

FIGURE 1 .

 1 FIGURE 1. A real-time PIV system.

FIGURE 2 .

 2 FIGURE 2. 2 single exposure input sub-regions and the corresponding output cross-correlation plane. The location of the single bright correlation peak from the origin is the average displacement.

FIGURE 5 .

 5 FIGURE 5. Adaptive FPGA-based architecture for realtime PIV applications.

FIGURE 6 .

 6 FIGURE 6. The asynchronous wrapper structure.

TABLE I :

 I Frequencies per type of module.

	Modules	Pro	Acquisi	Sto	Control
		cessing	tion	rage
	Frequency	100	10	100	150
	(MHz)

TABLE II :

 II Implementation results.

	Nb of pro-		Pixel clock	Nb of vectors
	cessing mod-	Image/sec.	frequency	per second
	ules		(MHz)
	1	204	16.8	16 393
	2	403	33.0	32 258
	3	571	46.8	45 714
	4	757	62.1	60 606
	5	925	75.9	74 074
	6	1 063	87.1	85 106


Ines Ben Jemaa
email: ines.ben_jemaa@inria.fr

Oyunchimeg Shagdar
email: oyunchimeg.shagdar@inria.fr

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Arnaud De

La Fortelle

Extended Mobility Management and Geocast Routing for Internet-to-VANET Multicasting

Keywords: MULTICAST, INTERNET, VANET, MOBILITY MANAGEMENT, GEOCAST

Emerging ITS applications, such as point of interest distribution, require information delivery from the Internet to a group of vehicles. Such an Internet-to-VANET multicast service raises several challenges including efficient multicast mobility management and multicast message delivery in a geographic area (geocast). In this paper we propose to extend the PMIP (Proxy Mobile IP) mobility management scheme such that it allows vehicles in a geographic area to subscribe to the multicast group with low control overhead by exploiting vehicular ad hoc networking. We then propose Melody, a geocast routing protocol, which extends the multicast service coverage in the VANET based on overlay routing. Our simulation results show that Melody provides an improved communication performance in urban areas in comparison to geographic flooding.

Introduction

Intelligent Transport Systems (ITS) are expected to largely improve road safety, efficiency, and driving comfort and therefore it has received a great attention in both the academics and industry. An important goal of ITS is to provide mobile users (e.g., drivers) with the existing Internet-based services (e.g., WEB surfing) as well as new types of services dedicated to the vehicular environments.

A significant number of these ITS applications require multicast communications. Particularly, in addition to the traditional applications such as video conferencing or gaming, vehicular communications enable new emerging multicast applications such as Point Of Interest (POI) distribution. POI distribution refers to informing drivers and passengers about specific location points (e.g., parking lots, restaurants, and so on), which can be interesting or useful for the nearby road users. This application requires multicast message delivery from a centre in the Internet to a set of users who are located in a specific geographic area. Enabling such an application is fraught with challenges, due to the hybrid communications path (from the Internet to the wireless media and finally to a geographic destination area) and also the highly mobile nature of the destination nodes.

To support multicast services in the Internet, a set of functions are required including multicast addressing [START_REF] Holbrook | Using Internet Group Management Protocol Version 3 (IGMPv3) and Multicast Listener Discovery Protocol Version 2 (MLDv2) for Source-Specific Multicast[END_REF], membership management [START_REF] Cain | Internet Group Management Protocol, Version 3[END_REF], and multicast routing [START_REF] Pusateri | Distance vector multicast routing protocol[END_REF], [START_REF] Fenner | Protocol Independent Multicast -Sparse Mode (PIM-SM): Protocol Specification (Revised)[END_REF]. However, the dynamics of vehicular environment and the requirements of geographic dissemination make it difficult to directly extrapolate these protocols to VANETs. In particular, geographic multicasting to VANET mobile users (i.e., drivers and occupants) requires additional challenges including: (i) geographic multicast addressing, (ii) multicast mobility management, and (ii) geographic message dissemination in the wireless network. Regarding geographic multicast addressing, we proposed a solution in [START_REF] Ben | A Framework for IP and Non-IP Multicast Services for Vehicular Networks[END_REF] that is adapted to the context of vehicular networks. The second and the third challenges are the scope of this current work. The objective of mobility management is to locate mobile users and provide them data in a seamless manner. Two mobility management protocols have been standardized by IETF: (i) the Mobile IPv6 (MIPv6 for IPv6) [START_REF] Johnson | Mobility support in IPv6[END_REF], which is a host-based mobility management, and (ii) the proxy mobile IP version 6 (PMIPv6) [START_REF] Gundavelli | Proxy mobile IPv6[END_REF], which is a network-based mobility management solution. The key idea of MIPv6 relies on a fixed entity in the home network of Mobile Node's (MN), the so-called Home Agent (HA), which locates the MN and builds a bidirectional tunnel to transfer data packets destined to the MN. The weaknesses of MIPv6 include long latency, high signaling overhead and location privacy problems [START_REF] Kempf | Problem Statement for Network-Based Localized Mobility Management[END_REF]. To overcome these issues, PMIP is designed. In PMIP, the visiting network localizes the MN, communicates with the home entity, and builds a tunnel for data transfer.

Although the existing multicast mobility management solutions can provide multicast data to mobile nodes (MNs), an issue of these solutions is that they are somehow based on the assumption that users usually stay in their home network (fixed network) and hence they are designed to provide mobility management to only one or few users. Therefore, a direct application of these solutions to vehicular services would create large control overhead due to a per-user membership management and inefficient bandwidth utilization due to the unicast transmissions over the tunnels. Such control overhead and inefficient bandwidth usage should be avoided and we believe that it is possible especially for the cases where the mobile members are in the same geographical area. Indeed this is the case for the above-mentioned POI service.

In this paper, we propose to extend PMIPv6 in such a way that mobility management to multiple vehicles can be provided with low cost and low complexity. Specifically, we propose to use PMIPv6 for mobility management to a single user, which further provides mobility management to a multiple users by exploiting vehicular ad hoc networking. Extending PMIPv6 for VANETs has another benefit in contrast to the conventional PMIPv6. Indeed, the mobile users, which do not have Internet connection (because they are not in the coverage of access networks, and/or they are not equipped with 3G/4G devices), can now receive multicast service over the Internet-to-VANET communication.

A number of efforts towards enabling geocasting in ad-hoc networks have been previously made.

Examples are LBM [START_REF] Ko | Geocasting in mobile ad hoc networks: Location based multicast algorithms[END_REF] and GeoGrid [11] protocols, which rely on flooding techniques to disseminate a message to a given area. However, if vehicles are in the close proximity of each other, the protocols may lead to a massive packet redundancy on the network, which increases the overhead and bandwidth consumption. Opportunistic routing has been proposed to improve packet delivery and reduce the overhead in the network. Opportunistic routing such as [START_REF] Le | Opportunistic Overlay Multicast in Wireless Networks[END_REF] exploits the broadcast nature of wireless transmissions. It allows candidate nodes that overhear the packet and are close to the destination to participate in forwarding the packet and thus reduce the number of retransmissions.

However, in multicast services, where the message has to be delivered to the members, opportunistic routing using broadcasting techniques may not guarantee the packet delivery due to the lack of an acknowledgement system.

In this paper, we introduce Melody, a geocast routing protocol that uses a variant of opportunistic routing technique to transmit multicast packets over an overlay path to a geographic area.

The rest of this paper is organized as follows: Section 2 details our proposal for Internet-to-VANET multicasting. More specifically, we explain the scenario and present the VANET multicast group management scheme. In Section 3, we present the dissemination process to deliver information from the Internet to the group of multicast members located in an urban destination area. In Section 4 we assess our proposal by computer simulations for different urban scenarios. Finally, Section 5 concludes the paper.

Internet-to-VANET Multicasting

In this section, we first present the scenarios of Internet-to-VANET multicast communication required by the POI application. We then introduce the enhanced mobility management scheme for PMIPv6 architecture.

Preliminaries and scenario description

The scope of this work is multicast message delivery from a server residing in the Internet to an urban area. The message may include information about road status (congested or not), an advertisement of a new restaurant or parking facilities in a specific area. The messages are first sent to Road Side Units (RSU), which are deployed on a city scale to serve small urban zones. The source (server) sends the message to a multicast address that identifies the multicast service. It also specifies the destination area in the packet. It should be noted here that the destination area is transparent to the entities, which forward the multicast message in the Internet. The role of those entities is to forward the message to the multicast address following the Internet path, e.g., a tree path built by the PIM protocol [START_REF] Fenner | Protocol Independent Multicast -Sparse Mode (PIM-SM): Protocol Specification (Revised)[END_REF].

Figure 1 -Internet to VANET Geocast scenario

The scenario is depicted in Figure 1. When an RSU receives the information sent from the server, it has to forward it to the interested vehicles, which reside in a geographic area specified in the data packet. The multicast vehicles use the mechanism as detailed in [START_REF] Ben | A Framework for IP and Non-IP Multicast Services for Vehicular Networks[END_REF] to auto-configure a valid address using the service identifier and the geographic attributes of the area. If the destination area is not directly reachable from the RSU, the data has to be relayed in the vehicular network from the RSU until the geographic area, where it is disseminated to the multicast members.

Extended multicast mobility management for the PMIPv6 architecture

The membership management and data transmission in PMIPv6 multicast mobility management schemes are illustrated in Targeting the above-mentioned issues, we propose to extend the multicast mobility management by exploiting the VANET concept. In the proposed scheme, the RSU plays the role of the MAG. RSU will be aware about the existence of multicast group in the destination area as follows. The RSU acts as MAG and broadcasts MLQs in the VANETs. Unlike usual one-hop transmission of MLQ, in our scheme it is unicasted until it reaches the destination area. When the MLQ reaches the destination area, it is flooded in the area until it reaches at least one multicast member subscribed to the group. The multicast member that first receives the MLQ sends a MLR. Note that as specified by the protocol, if multiple members receive the MLQ, only one member respond with MLR. To do so, each vehicle sets up a random timer and the one with the shortest timer responds with a MLR. Upon reception of the MLR, the other members restrain their MLR transmission. If a node that received an MLQ is not a multicast member of the group, it simply forwards the message. The informal description of the algorithm can be found below.

Melody: A Reliable Geocast routing in Urban VANET

In the previous section, we proposed an extended multicast mobility management scheme that enables a MN to join a multicast group in the Internet, and thereby making it possible to create VANET multicast groups in order to disseminate multicast data to nodes using vehicular networking solutions.

Delivery of a multicast packet from the Internet to the RSU can be achieved following an Internet multicast routing protocol (e.g., Protocol Independent Multicast, PIM).

The interest of this section is to describe the multicast packets delivery approach in VANET, from the RSU to the geographic destination area, where multicast members are located. As mentioned in the previous section, geocast techniques based on flooding may create overhead on the link and result in packet collision. Moreover, opportunistic routing does not avoid packet loss and require coordination between candidate nodes to forward the packet. In this paper, we propose Melody, a variant of the opportunistic routing disseminates the multicast messages sent from the RSU to the destination area using unicast or multicast overlay paths.

Neighbor Discovery

In Melody, each vehicle in the network has to maintain a list of its neighbors. To do so, vehicles periodically broadcast Hello messages in every second. A Hello message announces the position, the velocity, the connectivity degree and the multicast membership status (i.e., whether the node belongs to a multicast group or not) of the node. The connectivity degree is the number of neighbors of the node at the time of sending the Hello message. By including the membership status in the Hello message, it is now not necessary for the multicast members to periodically broadcast multicast joining requests, which is forwarded in the entire network to announce the membership status. The consequence of using the single-hop Hello messages for announcement of membership, is obviously low overhead, but also the membership status of a node is known only by its is one hop neighbors. It is indeed enough for Melody, which is an opportunistic routing algorithm.

Relay Phase

It is possible that the majority of the multicast members are far from the roadside infrastructure that receives the data from the multicast server (in the Internet). The objective of the relay phase is then to quickly and reliably deliver data packets from the RSU to the geographical areas, where the multicast members reside. Unlike traditional opportunistic routing, Melody builds a hop-by-hop overlay path until the data packet reaches the geographical area(s). Each relay that receives the multicast message retransmits it by specifying the next relay node in the packet. The neighboring node, which is closest to the center of the destination area and which has the maximum number of neighbors (highest connection degree), is selected as the next relay for the packet (See Figure 3). Choosing the forwarder, which has a high connection degree, provides a high chance to guarantee that the packets reach the maximum number of multicast members.

It should be noted that since Melody targets urban road, the destination area might be segments of different roads. In this case, Melody selects relay nodes for each destination road to transmit the packet towards the destination.

Dissemination Phase

Figure 3 illustrates the dissemination phase in Melody. Dissemination phase has dual goals: 1) distributing data packet to the multicast members, which reside in the destination geographical area and 2) similar to relay phase, multi-hop message delivery from a one end to the other end of the dissemination area. To achieve the goals, we propose the following two types of Melody:

• Melody using multicast overlay: The relay nodes send the data packets using the multicast mode. The address of the next-hop node is indicated in the packet. Nodes that received the packet check if its address is indicated as the next hop node. If yes, it selects the next realy node and transmits a copy of packet in the multicast mode. Furthermore, if the receiving node is a multicast member it provides the packet to the multicast client application.

• Melody using unicast overlay: The relays generate two copies of the data message: one copy is sent to the members using the multicast mode and the second copy is sent to the next hop node using the unicast mode. While the overhead is higher than the above-described multicast overlay method, using two copies of the message improves transmission reliability as it exploits the acknowledgement procedure of the medium access control (MAC) protocol for unicast frames.

Performance Evaluation

Melody is implemented in the NS3 simulator [16] and its performances in terms of packet delivery ratio (PDR), end-to-end delay, and the number of packet retransmissions are compared against those of the geographical flooding approach. Table 1 summarizes the settings of our simulations.

In the IEEE 802.11p standard [15], the communication range is around 300 meters. The Cooperative Awareness Message (CAM) specified by ETSI is used as background traffic. CAM are transmitted by each vehicle in every 100ms. Since CAM already includes position and velocity of the node, Melody uses CAM as a Hello message, by adding the necessary information such as the connectivity degree and membership status The SUMO traffic simulator [START_REF]Simulator for Urban MObility SUMO[END_REF] is used to generate realistic vehicular mobility traces. We simulated a Manhattan grid scenario as illustrated in Figure 4. The area length of the road is 2000x1500. The road has two lanes. The multicast members reside in the destination area.

The maximum velocity of the vehicles is limited to 50km/h. The acceleration and deceleration values of the vehicles are set to 0.8 m/s 2 and 4.5 m/s 2 , respectively, and the minimum inter-vehicle distance is 2.5 meters. Vehicles are generated in the grid following the Poisson process at the average rate λ (in terms of vehicles/second), which takes value on 1/15, 1/10, 1/5, or 1 that correspond to the number of nodes 160, 248, 538, or 817 respectively, as shown in Table 1. Ten SUMO runs of 100 seconds are carried out for each λ to obtain mobility traces for NS3. Flooding. As can be seen in the figure, both variants of Melody perform better than flooding when the number of nodes is moderately high (i.e., less than 248). Melody using unicast overlay path achieves 100% of packet delivery when the network is not highly dense, whereas Melody using a multicast relay path ensures between 95% to 80% packet deliveries. This is because using unicast path guarantees higher reliability than using multicast transmission, where no MAC-layer acknowledgement is performed. For the same densities, flooding shows low PDR: about 40%.

For high traffic density (817 nodes), however, the performances of the two variants of Melody fall considerably compared to the flooding. In the congested road scenario (817 nodes), the channel experiences high access contention by the background traffic (See Table 1), and hence the moderate number of retransmissions of data packets of Melody does not ensure the communication reliability, resulting in the reduced PDR. In contrast, flooding is not sensitive to the increase of the traffic density.

The increase of the packet retransmissions even favors the PDR in certain density (value corresponding to 538 nodes in the graph). This is because in flooding each node in the network retransmits the packet that it receives in the link. Even if it creates congestion, redundant packet paths ensure at some extent packet delivery to multicast members.

Conclusion

In this paper, we propose a scheme that targets POI type of services for ITS, which require transmissions of data flows from Internet to vehicles in given geographic areas.

Our scheme extends the mobility management of multicast members of PMIPv6 by exploiting the geocast transmission in VANET. Thus, it allows reducing control overhead and expanding the POI service coverage. The proposed geocast protocol, Melody, has two dissemination approaches. The first approach exploits the reliability of the unicast transmission to relay and disseminate multicast packets in the destination area; the second approach uses only multicast transmissions and largely reduces the number of retransmissions. The performances of Melody were evaluated using the SUMO traffic simulator and NS3 network simulator. Specifically, we compared the performances of Melody and the geographic flooding in relatively dense vehicular urban scenarios. Simulation results show that Melody reduces the overhead incurred by the geographic flooding and achieves thus greater reliability in moderate dense scenario.

As a future work, we propose to improve the dissemination approach of Melody for highly urban dense scenarios.

Figure 2 .

 2 schemes are illustrated inFigure 2. The Mobile Access Gateways (MAGs) broadcast a Multicast Listener Query MLQ (MLQ) to Mobile Nodes (MN) under their coverage, collect Multicast Listener Report (MLR) from them, and send aggregated MLRs to their respective Local Mobility Anchor (LMA). As illustrated in Figure 2, the control overhead and bandwidth utilization in PMIPv6 degrades with the increase of the number of multicast mobile nodes. Moreover, PMIP cannot obviously deliver data to the MNs that do not have Internet connection.

Figure 2 -

 2 Figure 2 -PMIPv6 operations

Algorithm 1 -

 1 Extended PMIPv6 for Geocast transmissionMelody operates in three phases: a neighbor discovery, relay phase, and dissemination phase. In what follows, we explain the procedures of each phase.

if

  Node is MulticastMemberInDestArea or HasMulticastNeighborsInDestArea then Set Timer to respond with MLR; while TimerNotExpired do if MLR heard on the link then return; World Congress, Bordeaux, France, 5-9 October 2015

Figure 3 -

 3 Figure 3 -Melody relay and dissemination phases

Figure 4 -Figure 5

 45 Figure 4 -Simulation scenario

Figure 6

 6 Figure6compares the number of retransmissions of Melody and Flooding approaches. As shown in the figure, the number of retransmissions increases in Flooding when the number of nodes increases up to 538; it is small and relatively stable for the two variants of Melody. It has to be said here that Melody with unicast overlay generates more packet transmissions in compared to Melody with multicast overlay. In the dense scenario (the number of nodes is 817), the number of retransmissions of flooding as well as Melody is reduced in comparison to the case of 517 nodes. The reason behind this is as follows: the larger the number of nodes, the higher the bandwidth consumption for the

Figure 5 -Figure 6 -Figure 7

 567 Figure 5 -Performance evaluation of the Packet Delivery Ratio

Figure 7 -

 7 Figure 7 -Evaluation of the delay

Table 1 . Simulation parameters Simulation Parameter Value

 1

	Simulation scenario	Urban (Manhattan Grid)
	Simulation time	100 seconds
	Area size		2000m*1500m
	Packet size		512 bytes
	Number of lanes	2 lanes
	Vehicle's	generation	rate
			1/15, 1/10, 1/5, 1
	(car/seconds)
	Number of vehicles in the
			160, 248, 538, 817
	whole area
	Communication range	About 300 meters
	Channel bandwidth	6 Mbps
	Propagation model	Log distance


André Fabbri

Frédéric Armetta

Éric Duchêne

Salima Hassas

A new self-acquired knowledge process for Monte Carlo Tree Search

Computer Go is one of the most challenging field in Artificial Intelligence Game. In this area the use of Monte Carlo Tree Search has emerged as a very attractive research direction, where recent advances have been achieved and permitted to significantly increase programs efficiency. These enhancements result from combining tree search used to identify best next moves, and a Monte Carlo process to estimate and gradually refine a position accuracy (estimation function). The more the estimation process is accurate, the better the Go program performs. In this paper, we propose a new approach to extract knowledge from the Go tree search which allows to increase the evaluation function accuracy (BHRF: Background History Reply Forest). The experiments results provided by this new approach are very promising.

Introduction

The game of Go is a deterministic fully observable two player game. Despite its simple rules, it stands for one of the great challenge in the field of AI Game.

Go tactical and strategic decisions are extremely difficult to tackle, since each move could have a high impact a long time after having been played. A single stone move could completely change the board configuration and therefore, there is no static evaluation function available during the game [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF]. Professional human players succeed where programs fail, thanks to their expertise and knowledge acquired from their long experience.

Recent developments in Monte Carlo Tree Search allowed to considerably increase program's efficiency. These enhancements result from combining Tree Search used to identify best next moves to a Monte Carlo process based on random playing attempts to estimate and gradually refine a position accuracy (estimation function).

Monte Carlo Tree Search programs are able to reach up a professional level by simulating thousands of pseudo random games [START_REF] Lee | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF]. However these program's performances does not scale with computational power increasing [START_REF] Bourki | Scalability and Parallelization of Monte-Carlo Tree Search[END_REF].

A promising way to increase program's efficiency arises from learning on-line local knowledge to enhance the relevance of random simulations used to evaluate positions [START_REF] Baier | The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte-Carlo go[END_REF][START_REF] Rimmel | Multiple Overlapping Tiles for Contextual Monte Carlo Tree Search[END_REF][START_REF] Rimmel | Biasing Monte-Carlo Simulations through RAVE Values[END_REF].

In this context, one can note that the issue is not only focused on the computing power available, but in our ability to manage additional more sophisticated self-acquired knowledge. Then, in the rest of the paper, we will focus on this ability. Further work will propose additional enhancements to optimize the process associated to knowledge management in order to decrease the computingresources consumption.

In this paper we propose a new approach to collect the knowledge acquired through the tree search of estimated positions. Our proposal appears as a complementary data structure. As described in section 3, a tree search is used to define what are the best next moves to play from a completly described current position. The structure we propose to build addresses a more abstract question: if a set of relatives moves are played, what to play next ? We show with our approach presented in section 4 that a natural manner to tackle this question is to constitute a Background History Reply Forest (BHRF). We then describe how to build and maintain this generic forest and how to exploit it. These two points raise new questions, but we show that a first straightforward setup produces good results. Some promising experimental results are presented in 5 and show that using BHRF allows to play better.

The next section presents the general structure of knowledge involved in a learning process. The section 3 focus on the kind of knowledge used in the existing Go programs. Section 4 introduces a Background History Reply Forest (BHRF) for the Monte Carlo Tree Search. The last section sums up experiments carried on the model. A conclusion is presented in 6.

Knowledge in computer Go

While a game is running, for each step, a Go player aims at selecting the best move according to the game overall state. The overall game state involves any information related to the current game such as the board setup, the history of played moves, local fights and also the opponent's level. During the decision process, players need to select the relevant parts of the game to focus on. Human players accumulate knowledge by studying standard techniques, watching professional games or interacting with other players. Computer programs encode directly Go expert knowledge (apriori knowledge) or create their own knowledge using machine learning technic. This information is evaluated and stored in a data structure (knowledge acquisition or learning) for a further exploitation (knowledge exploitation or planning). Reinforcement learning methods iteratively apply these two steps to progressively build an effective policy [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Silver | Temporal-difference search in computer Go[END_REF].

Go knowledge acquiring

Knowledge is useful to evaluate a position (current state or targeted state resulting from a set of planned moves). Either generic (fitting many cases) or specific knowledge could be used to do this evaluation.

For instance, understanding the shapes formed by the stones on a Goban is a relevant way to solve local fights. In this case, local patterns are a powerful way to encode Go expert knowledge [START_REF] Silver | Temporal-difference search in computer Go[END_REF][START_REF] Helmut | Board Representations for Neural Go Players Learning by Temporal Difference[END_REF].

An other way is to consider a knowledge based on high-level characteristics of the game: groups, groups stability, influences between groups, etc [START_REF] Graepel | Learning on Graphs in the Game of Go[END_REF]. The representation can then focus on the intersection around the last move played to find local replies [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF].

The value of this knowledge generally represents the probability to win if we reach this game state representation. The quality of the estimator determines the accuracy of the considered knowledge. The value given by poor estimators are not reliable and have to be considered with caution. Several estimators for the same knowledge can be combined to produce a more effective estimation. The knowledge values are computed based on professional game records [START_REF] Coulom | Computing Elo Ratings of Move Patterns in the Game of Go[END_REF][START_REF] Stern | Bayesian Pattern Ranking for Move Prediction in the Game of Go[END_REF], professional players comments [START_REF] Hoock | Intelligent Agents for the Game of Go[END_REF] or self-playing [START_REF] Silver | Temporal-difference search in computer Go[END_REF]. These knowledge values will be exploited to choose an action according to the current game state.

Go knowledge exploitation

The policy maps an action to each game state. The action is selected based on the knowledge matching that game state. A high knowledge value means a good move but the knowledge nature and its estimator might be misleading. Therefore uncertainty is generally inserted in the policy to mitigate the influence of wrong estimations. The -greedy policy selects with a probability the action associated to the highest knowledge value otherwise it generally plays a random move. The softmax policy selects each action with a probability depending on the associated knowledge value [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

A policy would be selected according to its context of application. During a tutorial process, a policy might tolerate exploratory moves but during a challenge the policy has to select the best possible action.

Reinforcement learning

Reinforcement learning is a way to manage learning in an autocatalytic way. The program is not taught what to do and learns therefore by its own experience [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Temporal difference learning is one of the most applied method for such problems and has been successfully applied to computer games. This method dynamically bootstraps its knowledge from simulated games.

The policy evolves as the simulations runs and will influence the incoming simulations. Since the knowledge is built on-line, the policy has to deal with exploiting the accumulated knowledge (exploitation) or gathering more knowledge (exploration). A good policy should produce accurate simulations to enable the learning process. A too strong policy can actually lead to a weaker program [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

TD(λ) methods reinforce their knowledge values according to the estimation difference of the game state between two time-step. A Monte Carlo method is a temporal difference method which reinforcement depends on the final game state of the simulation [START_REF] Silver | Temporal-difference search in computer Go[END_REF].

The main idea of Monte Carlo Tree Search is to build a tree of possible sequence of actions. The tree root corresponds to the current board situation and each child node is a possible future game state. The tree will be progressively expanded towards the most promising situation by repeating the 4 phases: descent, roll-out, update and growth (Fig. 1).

During the descent phase, the simulation starts from the root node and progresses trough the tree until it reaches a game state outside of the tree.

For each node the program will iteratively select the best action with respect to the descent policy. Once it leaves the Monte Carlo Tree, the roll-out phase generates the remaining moves according to the roll-out policy until the game reaches a final state. The update phase propagates the final game results in the node reached during the descent and the growth phase appends the first game situtation ouside of the tree to the overall structure [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF].

Monte Carlo Go programs involve two kinds of knowledge to guide the simulations from the current game state. The Monte Carlo Tree stores knowledge on-line. This knowledge is exploited during the descent phase. The current best programs exploit Go domain specific knowledge in the roll-out phase because the tree knowledge is no more available. In the last section we will present methods that attempt to dynamically build up knowledge for the roll-out phase.

Monte Carlo tree

In the Monte Carlo tree, each node is a knowledge piece that associates a possible future board setups with an accuracy value estimated from previous Monte Carlo simulations. Board setups are very precise game state representations which will be progressively selected as the simulations run. However the built tree depends on the current board situation. Local structures are not shared between branches leading to a new kind of horizon effect [START_REF] Drake | The Last-Good-Reply Policy for Monte-Carlo Go[END_REF] and at each new turn only a subtree is kept. All previously acquired knowledge in other branches is forgotten.

At each step of the descent phase, the policy selects in a greedy way the best action based on the child's node value or a default value for the resulting states outside of the tree [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF]. The node's estimator will have a huge influence on the policy's behaviour. Since the policy is not perfect and the estimation sample is too small, the mean of Monte Carlo rewards (MCTS value) is not a reliable indicator on the long-term run [START_REF] Gelly | The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions[END_REF]. The Upper Confidence bound applied to Tree estimator (UCT value) reveals to be a good trade-off between exploration and exploitation [START_REF] Kocsis | Bandit based Monte-Carlo Planning[END_REF]. Recent results show that, in practice, a combination between the MCTS value and a biased mean estimator called RAVE ensures a good exploratory behaviour [START_REF] Gelly | Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go[END_REF][START_REF] Gelly | The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions[END_REF] and also minimizes the knowledge lost at each new turn, but without control.

Go a priori knowledge

Contrary to the Monte Carlo tree, the Go expert knowledge is independent from the overall stones disposition and therefore can be exploited for a broader set of a board setup. The purpose of this knowledge is to guide the simulation after having left the tree structure. However the roll-out policy should not be too strong to do not disturb the learning process [START_REF] Gelly | Combining Online and Offline Knowledge in UCT[END_REF]. The knowledge encoded corresponds generally to static Go tactical rules based on the current board configuration. Sequence-like policies brought a substantial improvement by searching around the last opponent move [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF]. If no rules fit the current situation, the policy plays randomly. Other roll-out policies use a linear combination of local pattern. The weights are generally computed with off-line intensive machine learning [START_REF] Gelly | Combining Online and Offline Knowledge in UCT[END_REF] but recent works obtained promising results by tuning them on-line [START_REF] Huang | Monte-Carlo Simulation Balancing in Practice[END_REF][START_REF] Silver | Temporal-difference search in computer Go[END_REF].

Knowledge collected from Game

Several works aim at dynamically learn knowledge relative to the current game in order to exploit it during the roll-out phase (see Fig. 2). The game chosen state representations are generally small move sequences or patterns. As for the Monte Carlo tree, this knowledge will be built in a autocatalytic manner but this knowledge will persist over the turns.

Pool RAVE [START_REF] Rimmel | Biasing Monte-Carlo Simulations through RAVE Values[END_REF] exploits the RAVE values in the Monte-Carlo tree to influence the roll-out. The best RAVE values from the covered nodes (descent phase) are selected to influence the next roll-out. The roll-out policy proposed for the game of Go uses first a "fill-board heuristic" [START_REF] Chaslot | Adding expert knowledge and exploration in Monte-Carlo Tree Search[END_REF] to ensure a good exploratory behaviour and then applies the moves associated with one of the pooled RAVE values. Hence the selected RAVE value contributes directly to its own reinforcement.

Contextual Monte Carlo [START_REF] Rimmel | Multiple Overlapping Tiles for Contextual Monte Carlo Tree Search[END_REF] stores tiles of two moves played by the same player. Each tiles has Monte Carlo mean value updated when the two moves appears in the same simulation. The main idea is to link the expected success with a couple of moves played by the same player. During the roll-out phase a -greedy policy will select the best move according to the last player's move.

Last Good Reply Forgetting heuristic [START_REF] Baier | The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte-Carlo go[END_REF] associates a reply to each sequence of one or two consecutive moves. For each encountered sequence the program stores a single reply. In the update phase all the reply sequences are updated or forgotten according to the simulation result. Over the simulations the replies are frequently updated but the most persisting moves are spatially local replies [START_REF] Drake | The Last-Good-Reply Policy for Monte-Carlo Go[END_REF][START_REF] Baier | The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte-Carlo go[END_REF]. In the roll-out phase the policy successively tries to apply the reply to the two previous ones, the reply to the previous move or a move generated from a Go expert knowledge policy if no appropriate reply is stored.

Proposal

In this paper, we propose a new method to learn knowledge collected from game (game-based knowledge) persistent over the turns. We actually assume that we can extract knowledge from the Monte Carlo tree and reuse it during the roll-out phase. Therefore we build an independent data structure similar to the Monte Carlo tree to store game based knowledge. The roll-out policy will be modified to consider this new form of knowledge.

Background History Reply Forest

A Monte Carlo node represents a future possible board setup. If we consider the background history of the board rather than the position of the stones, a board setup is also the sequence of moves played since the beginning of the match. Hence each child node of the tree is a possible reply to that sequence. Our idea is to extend the LGRF heuristic catch the knowledge stored in the tree over the simulations. The size of the previous sequence will be lengthened and the reply estimation will be based on the tree values. This knowledge will be more biased than the one provided by Monte Carlo nodes but it will be exploited in the roll-out phase and will persist over the turns.

BHRF knowledge exploitation

Hence we build a forest of search trees such that each tree root is a potential reply and each child node a previous sequence to this reply (Fig. 3). The value associated to each node comes from the Monte Carlo tree. In the update phase all nodes corresponding to sequences chosen in the descent phase are reinforced. The search trees are progressively expanded in the growth phase as done in the Monte Carlo tree [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF]. This knowledge is then exploited during the roll-out phase, according to the previous moves played. The selected nodes with the longest corresponding sequences will be the most dependent on the game state.

BHRF exploitaiton

For each roll-out game state, we choose a reply among all legal positions on the board. The program progresses through the associated tree search to select the nodes with the longest previous sequences (up to a maximum size parameter called depth). The policy computes on-line the UCT value for the nodes with the same previous sequence according to their last Monte Carlo rewards.

Due to the biased nature of this knowledge and in order not to restrain the simulation diversity, we implemented a non determinist policy to generate the moves at each roll-out step. The policy plays the root reply associated with a selected node among those with the longest matching sequences. If no reply move was played by the policy, a default roll-out policy is applied.

The softmax policy selects a node according to a softmax distribution based on their UCT value and plays the associated move with a probability depending on its UCT value multiplied by a parameter α.

Experimental results

We implemented this proposed knowledge-based model on top of the state of art program Fuego [START_REF] Enzenberger | FUEGO -an Open-Source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search[END_REF]. To prove the effectiveness of our approach we tested the BHRF player against a Monte-Carlo player using a random roll-out policy. We disabled the expert heuristics involved in the Fuego roll-out policy except for the random move generation 1 . The experimental results were carried out on a 9x9 goban against a baseline program without the BHRF heuristic. The current implementation is not thread-safe and is time-consuming. Therefore to provide a fair comparison we removed the clock limitation and each turn both programs run 10000 Monte-Carlo games on a single thread. We first study the influence of the parameter α for the softmax policy. This parameter tunes the involvement of the BHRF knowledge during the roll-out phase (see Algo. 1). As we see in Fig. 4, the performance increases with α. The program actually performs better for α = 100 where the BHRF replies are applied quite systematically if a BHRF node matches (only 2% doesn't). These results show that the softmax policy provides a good simulation diversity by itself.

Hence we next set α at 100 and focus on the depth parameter. The depth parameter determines the "history relevance" of the selected knowledge. As the maximum depth increases, the suggested moves should be more accurate. The experiments were carried out up to a depth of 10 because of time consuming constraints. Further experiments will require an optimised BHRF implementation. The figure 5 reveals that the performance of our algorithm slightly decreases as the depth parameter grows.

To validate our approach, we compare the performance of the BHRF heuristic according to the number of Monte-Carlo games simulated at each turn. Table 1 shows that BHRF performs better for 10000 simulations search 2 . The resulting Background History Reply Forestfor deep Monte Carlo search produces better estimators and actually matches to a wider set of game states. About 90% of the roll-out game states benefit from a BHRF reply when the MCTS algorithm runs 10000 games against 80% for 1000 games simulated. These results show an overall improvement when reusing game-based knowledge, that is extracted from the Monte Carlo tree. As we mentionned before, our main concern was to build self-acquired knowledge to improve Monte Carlo simulations. The computing time of this algorithm is still higher than the baseline algorithm (up to 10 times) but improvements could be made. Indeed the heuristic searches at each roll-out step among all the potential moves through the whole board contrary to the Go expert policy which one focuses around the last played move [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF][START_REF] Enzenberger | FUEGO -an Open-Source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search[END_REF]. Furthermore we would like to point out that our main concern was to show the good impact of Game-based knowledge model. An optimised version will requires a deep modification of the Fuego libraries.

Conclusion

In this paper we present a new approach to complement the Monte Carlo Tree Search programs. The proposed framework is inspired from the reinforcement learning paradigm, and aims at distinguishing incorporated knowledge from its exploitation.

The proposed model extracts game-based knowledge from the Go Tree Search to introduce more accurate moves through simulations. The incorporated knowledge is based on history data and tends to find a trade-off between the specific knowledge stored in the tree and more biased game-relative heuristics.

We show with our approach that a natural manner to complement Go tree search knowledge is to constitute a Background History Reply Forest (BHRF). We then describe how to build and maintain this generic forest and how to exploit it. These two points raise new questions, but we show that a first straightforward setup provides good results.

The first proposed results underline the efficiency of our model, and allows to outperform the baseline MCTS algorithm with similar setting for up to 2/3 of the considered games. This encourages us to carry on the experiments on a larger board or with other settings (longer sequences, use of BHRF to compute initial values of leaf for the Go tree search, etc).

Fig. 1 .

 1 Fig. 1. General MCTS process

Fig. 2 .

 2 Fig. 2. Game knowledge for MCTS process

Fig. 4 .

 4 Fig. 4. BHRF success rate over α against the baseline program

1Fig. 5 .

 5 Fig. 5. BHRF success rate over depth against the baseline program

  Algorithm 1 softmax policy for BHRF knowledge

	curLength = 0
	for m in legalMoves do
	i = replyTree[m].selectNode(depth,lastmoves)
	nodeSelection.add(i)
	if n.length > curLength then
	curLength = n.length
	end if
	end for
	n = nodeSelection.softMaxUct(curLength)
	if randomValue() < α × n.uctValue then
	return n.rootReply
	else
	return defaultRandomMove()
	end if

Table 1 .

 1 Comparative between 1000 and 10000 games simulated for the softmax policy

	α	1		100
	games simulated 1000	10000	1000	10000
	success rate % 58.7 ± 2.49	63.4 ± 2.99	58.5 ± 2.49	68.8 ± 2.87