Franck Butelle
email: franck.butelle@lipn.univ-paris13.fr

Camille Coti
email: camille.coti@lipn.univ-paris13.fr

Data Coherency in Distributed Shared Memory

Keywords: Distributed shared memory, concurrent systems, race condition

We present a new model for distributed shared memory systems, based on remote data accesses. Such features are offered by network interface cards that allow one-sided operations, remote direct memory access and OS bypass. This model leads to new interpretations of distributed algorithms allowing us to propose an innovative detection technique of race conditions only based on logical clocks. Indeed, the presence of (data) races in a parallel program makes it hard to reason about and is usually considered as a bug.

Introduction

The shared-memory model is a convenient model for programming multiprocessor applications: all the processes of a parallel application running on different processors have access to a common area of memory. Another possible communication model for distributed systems is the message-passing model, in which each process can only access its own local memory and can send and receive message to other processes.

The message-passing model on distributed memory requires to move data between processes to make it available to other processes. Under the shared-memory model, all the processes can read or write at any address of the shared memory. The data is shared between all the processes.

One major drawback of the shared-memory model for practical situations is its lack of scalability. A direct implementation of shared memory consists in plugging several processors / cores on a single motherboard, and letting a single instance of the operating system orchestrate the memory accesses. Recent blades for supercomputers gather up to 32 cores per node, Network on Chip (NoC) systems embed 80 cores on a single chip: although the "many-core" trend increased drastically the number of cores sharing access to a common memory bank, it is several orders of magnitude behind current supercomputers: in the Top 5001 list issued in November 2010, 90% of the systems have 1K to 16K cores each.

The solution to benefit from the flexibility and convenience of shared memory on distributed hardware is distributed shared memory. All the processes have access to a global address space, which is distributed over the processes. The memory of each process is made of two parts: its private memory and its public memory. The private memory area can be accessed from this process only. The public memory area can be accessed remotely from any other process without notice to the process that maps this memory area physically.

The notion of global address space is a key concept of parallel programming languages, such as UPC [START_REF]UPC Language Specifications[END_REF], Titanium [START_REF] Yelick | Titanium: A high-performance java dialect[END_REF] or Co-Array Fortran [START_REF] Numrich | Co-array fortran for parallel programming[END_REF]. The programmer sees the global memory space as if it was actually shared memory. The compiler translates accesses to shared memory areas into remote memory accesses. The run-time environment performs the data movements. As a consequence, programming parallel applications is much easier using a parallel language than using explicit communications (such as MPI [START_REF]MPI: A message-passing interface standard[END_REF]): data movements are determined by the compiler and handled automatically by the run-time environment, not by the programmer himself.

The memory consistency model followed by these languages, such as the one defined for UPC [START_REF] Bonachea | A Proposal for a UPC Memory Consistency Model[END_REF], does not define a global order of execution of the operations on the public memory area. As a consequence, a parallel program defines a set of possible executions of the system. The events in the system may happen in different orders between two consecutive executions, and the result of the computation may be different. For example, if a process writes in an area of shared memory and another process reads from this location. If the writer and the reader are two different processes, the memory consistency model does not specify any kind of control on the order in which these two operations are performed. Regarding whether the reader reads before or after the data is written, the result of the reading may be different.

In this paper, we introduce a model for distributed shared memory that represents the data movements and accesses between processes at a low level of abstraction. In this model, we present a mechanism for detecting race conditions in distributed shared memory systems.

This model is motivated by Remote Direct Memory Access capabilities of high-speed, low-latency networks used for high-performance computing, such as the InfiniBand standard2 or Myrinet 3 .

The remainder of this paper is organized as follows. In section 2, we present an overview of previous models for distributed shared memory and how consistency and coherency has been handled in these models. In section 3 we present our model for distributed shared memory and how it can be related to actual systems. In section 4 we present how race conditions can be represented in this model, and we propose an algorithm for detecting them.

Previous work

Distributed shared memory is often modeled as a large cached memory [START_REF] Holt | The effects of latency, occupancy, and bandwidth in distributed shared memory multiprocessors[END_REF]. The local memory of each node is considered as a cache. If a process running on this node tries to access some data, it gets it directly if the data is located in its cache. Otherwise, a page fault is raised and the distributed memory controller is called to resolve the localisation of the data. Once the data has been located (i.e., once the local process knows on which process it is physically located and at which address in its memory), the communication library performs a point-to-point communication to actually transfer the data.

In [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF], L. Lamport defines the notion of sequential consistency: on each process, memory requests are issued in the order specified by the program. However, as stated by the author, sequential consistency is not sufficient to guarantee correct execution of multiprocessor shared memory programs. The requirement to ensure correct ordering of the memory operations in such a distributed system is that a single FIFO queue treats and schedules memory accesses from all the processes of the system.

Maintaining the coherence of cache-based distributed shared memory can then be considered as a cache-coherency problem. [START_REF] Li | Memory coherence in shared virtual memory systems[END_REF] describes several distributed and centralized memory managers, as well as how coherence can be maintained using these memory managers.

However, in a fully distributed system (i.e., with no central memory manager) with RDMA and OS bypass capabilities, a process can actually access another process's memory without help from any memory manager. In parallel languages such as UPC [START_REF]UPC Language Specifications[END_REF], Titanium [START_REF] Yelick | Titanium: A high-performance java dialect[END_REF] and Co-Array Fortran [START_REF] Numrich | Co-array fortran for parallel programming[END_REF], data locality (i.e., which process holds the data in its local memory) is resolved at compile-time.

These languages rely on a concept called Parallel Global Address Space (PGAS). In this global address space, a chunk of data can be localized by a tuple of two elements: the aforementioned data locality, which is also called the process the data has affinity to, and the local address in the memory of the process this given chunk has affinity to.

In UPC, data can be declared as either shared or private. When a process (called a thread in the UPC terminology, by analogy with shared memory systems) accesses a shared chunk of data that does not have affinity to itself, it is accessed remotely by the run-time system (GASNet [START_REF] Boachea | Gasnet specification[END_REF] in the case of UPC, Titanium and the LANL implementation of Co-Array Fortran). The semantics of these remote data accesses will be discussed further in section 3.2.

The coordination language LINDA [START_REF] Ahuja | Linda and friends[END_REF] implements a model where the distributed shared memory is called a tuple space. Chunks of data called tuples can be added into the tuple space and read (and removed or not) from it. It can also create new processes on-the-fly to evaluate tuples. Besides the particular semantics of the language (based on tuples matching), the model it defines for implementing distributed applications is quite different from other PGAS languages such as UPC and Co-Array Fortran. In the LINDA model, the programmer explicitly pushes and pulls data from the distributed address space (the tuple space), and the run-time system is in charge with data locality.

Queries to the tuple space involve a search for matching tuples in the whole tuple space. In [START_REF] Basney | A Distributed Implementation of the C-Linda Programming Language[END_REF], the distributed memory manager is called the tuple handler. This implementation uses a centralized tuple server, and the processes of the application are clients. As stated by the author of this work, this creates a data bottleneck and is a major drawback of this implementation.

Javaspace [24] implements this distributed memory model using RMI and some features of the Java language such as class types comparisons. The transaction model relies on a two-phase commit model.

The simplicity of the LINDA language and its siblings make them attractive for implementing distributed applications [START_REF] Hanáček | Parallel simulation using the linda language[END_REF]. However, this simplicity has one major drawback: it has little (or no) safety features. The programmer has no control on the data accesses, such has the locks provided by languages from the family of UPC.

Locks are the most basic data safety mechanism there is. Their basic task is to ensure mutual exclusion in a critical section: the process that holds the lock is the only one that can access the critical section, while the other processes must wait until the lock is released to try to get it. As described more formally in section 3.1, locks can also be defined on memory areas. They guarantee the fact that only one process is accessing a given area of memory. Hence, they provide a certain form of data safety, in a sense that a chunk of data cannot be altered by any other process which a given process is accessing it. However, they are not sufficient to guarantee that the operations on this chunk of data are causally ordered and that the distributed program is free from race conditions [START_REF] Helmbold | A taxonomy of race detection algorithms[END_REF].

The MPI-2 standard [START_REF] Geist | MPI-2: Extending the message-passing interface[END_REF] defines remote memory access operations. The MARMOT error checking tool [START_REF] Krammer | Correctness checking of mpi one-sided communication using marmot[END_REF] checks correct usage of the synchronization features provided by MPI, such as fences and windows. A window is an area of a process's memory that is made available to other processes for remote memory accesses. Windows are created and destructed collectively by all the processes of the communicator. MARMOT associates an access epoch to each window to determine whether conflicting accesses are made to the same memory location in a window. MPIRACE-CHECKER [START_REF] Park | Detecting Race Conditions in One-Sided Communication of MPI Programs[END_REF] uses a mirror window and marks it such in a way that unsafe, concurrent memory accesses can be detected as such. These techniques are using features that are specific to the MPI-2 standard and its remote memory access model.

In this section, we define a model for distributed shared memory. This model works at a lower level than most models described previously in the literature. It considers inter-process communications for remote data accesses.

Distributed shared memory model

In many shared-memory models that have been described in the literature [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Dolev | Self-Stabilization[END_REF][START_REF] Tel | Introduction to Distributed Algorithms[END_REF], pairs of processes communicate using registers where they read and write data. Distributed shared memory cannot use registers between processes because they are physically distant from each other; like message-passing systems, they can communicate only by using an interconnection network.

Figure 1 depicts our model of organization of the public and private memory in a multiprocess system. In this model, each process maps two distinct areas of memory: a private memory and a public memory. The private memory can be accessed from this process only.

The public address space is made of the set of all the public memories of the processes (the Global Address Space). Processes can copy data from/to their private memory and the public address space, regardless of data locality.

Public memory can be accessed by any process of the application, in concurrent read and write mode. In particular, no distinction is made between accesses to public memory from a remote process and from the process that actually maps this address space.

P0

P1 P2

Private Address Space

Public Address Space

Remote get Remote put

Remote put

Figure 1: Memory organization of a three-process distributed shared memory system.

The compiler is in charge with data locality, i.e., putting shared data in the public memory of processes. For instance, if a data x is defined as shared by the programmer, the compiler will decide to put it into the memory of a process P . Instead of accessing it using its address in the local memory, processes use the process's name and its address in the memory of this process. This couple (process name, local address) is the addressing system used in the global address space. The compiler also performs the address resolution when the programmer asks a process to access this shared data x.

In addition, since NICs (Network Interface Controllers) are in charge with memory management in the public memory space, they can provide locks on memory areas. These locks guarantee exclusive access on a memory area: when a lock is taken by a process, other processes must wait for the release of this lock before they can access the data.

Communications

Accessing data in another process's memory is called Remote Direct Memory Access (RDMA). It can be performed with no implication from the remote process's operating system by specific network interface cards, such as InfiniBand and Myrinet technologies. It must be noted that the operating system is not aware of the modifications in its local shared memory. The SHMEM [START_REF] Brightwell | A new MPI implementation for Cray SHMEM[END_REF] library, developed by Cray, also implements one-sided operations on top of shared memory. As a consequence, the model and algorithms presented in this paper can easily be extended to shared memory systems.

RDMA provides two communication primitives: put and get. These two operations are represented in figure 2. They are both atomic.

P0

P1 P2 get p u t Put consists in writing some data into the public memory of another process. It involves one message, from the source process to the destination process, containing the data to be written. In figure 2, P 2 writes some data into P 1's memory.

Get consists in reading some data from another process's public memory. It involves two messages: one to request the data, from the requesting process to the process that holds the data, and one to actually transfer the data, from the process that holds the data to the requesting process. In figure 2, P 0 reads some data from P 1's memory.

Communications can also be done within the public space, when data is copied from a place that has affinity to a process to a place that has affinity to another process.

The get operation is atomic (and therefore, blocking). If a thread gets some data and writes it in a given place of its public memory, no other thread can write at this place before the get is finished. The second operation is delayed until the end of the first one (figure 3).

P0

P1 P2 get put Figure 3: A put operation is delayed until the end of the get operation on the same data.

Race conditions

One major issue created by one-sided communications is that several processes can access a given area of memory without any synchronization nor mutual knowledge. For example, two processes A and B can write at the same address in the shared memory of a third process C. Neither B nor C knows that A has written or is about to write there. Concurrent memory accesses can lead to race conditions if they are performed in a totally anarchic way (although some authors precise data race conditions, we will use only "race conditions" throughout this paper). A race condition is observed when the result of a computation differs between executions of this computation. A race condition makes, at least, hard to reason about a program and therefore is usually considered as a bug or at least as a design flaw. In figure 4 we present a very simple case of race condition. The order of the execution (due for example to differences between the relative speeds of the processes) generate two different results.

In the kind of systems we are considering here, a race condition can occur when several operations are performed by different processes on a given area of shared memory, and at least one of these operations is a write.

For instance, if a piece of data located in the shared memory is initialized at a given value v 0 and is accessed concurrently by a process A that reads this data and a process B that writes the value v 1 . If A reads it before B writes, it will read the value v 0 . If B writes before A reads, A will read v 1 .

More formally, we can consider read and write operations as events in the distributed system formed by the set of processes and the communication channels that interconnects them.

Two events e 1 and e 2 are causally ordered iff there exists an happens before (as defined by [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] and denoted →) relationship between them such that e 1 →e 2 or e 2 →e 1 . Race conditions are defined in [START_REF] Helmbold | A taxonomy of race detection algorithms[END_REF] by the fact that there exists no causal order between e 1 and e 2 (further denoted by e 1 × e 2 ).

A parallel pseudo-language

In this section, we describe a parallel pseudo-language. This language is meant to describe parallel algorithms using a parallel global address space in the same way as pseudo-code describes sequential algorithms. Its purpose is not to replace UPC nor any parallel programming language (Titanium, Co-Array Fortran...) but to describe algorithms with a language-agnostic description language.

Computation units are called processes. Variables have a visibility. They can be either private or shared. Private means that the variable is visible by the current process only, and is physically located in its memory. Shared means that the variable is in the distributed public memory space. It can be physically located in any process's memory. Each process is assigned a unique number, called its rank. If the total number of processes in the system is N , ranks are consecutive and range from 0 to (N -1). The physical location of this variable (i.e., the rank of the process that maps the chunk of memory where it is physically located) is called its affinity.

The compiler and the underlying run-time system translate accesses to shared variables that do not have affinity to the current process into remote data accesses. Accesses to the local area of shared memory are performed using the local memory controller.

An example using this parallel pseudo-language is given in algorithm 1. This algorithm defines two variables of type Integer : a and b; a is shared (line 2) and b is private (line 3). We put the value of the process rank into this private variable b (line 4). Then the value of b is put into the shared variable a (line 5). A global synchronization (i.e., a barrier, line 6) waits until all the processes have reached this point of the program. Then one process prints the value of a (line 8).

The equivalent code in UPC (Unified Parallel C) is given by algorithm 2. UPC calls threads its parallel processes. It predefines some identifiers, such as M Y T HREAD, which provides the rank of the current thread (line 4 and line 7). Shared variables are declared using the qualifier shared (line 2). By default, variables are private: hence, if nothing is specified, a variable is private (line 3). The compiler chooses where the shared variables are physically located. In our example, we assume without loss of generality that process rank 0 has been chosen to store integer a in its local memory. Algorithm 3 describes the sequence of instructions executed by each process with explicit communications (remote data accesses). The shared variable is actually declared on process 0 only (line 2-3). Access to this shared variable is done between lines 6 and 9. If the local process is the process that holds the data (lines 6-7), it corresponds to a simple local variable. If the shared variable does not have affinity to the local process, it must be accessed using a remote data access. Since our algorithm is writing into this variable, it corresponds to a put(localaddr, rank, remoteaddr) operation. A reading will be denoted by get(localaddr, rank, remoteaddr) (rank will always be the rank of the process owning remoteaddr variable physically).

The corresponding inter-process communications and the state of the shared variable a through the execution of this algorithm are depicted on figure 5 and figure 6 on an execution involving three processes P0, P1 and P2. As we can see here, all the processes write into the variable a without coordination. These two figures show two possible executions of the algorithm. Figure 5 depicts a situation where P0 writes first into a (upon this point, a = 0), then P1 performs a put into a (a = 1) and last, P2 performs a put into a (the value of a at the end is a = 2). Another possible execution is depicted in figure 6. In this case, P2's put operation is executed before P1's one. As a consequence, the final value for a is a = 1. This example contains a race condition.

Detecting race conditions

In this section, we present an algorithm for detecting race conditions in parallel applications that follow the distributed shared memory model presented in section 3.

As stated in section 2, previous works on race condition detection have focused on specific communication models. Here we present a new algorithm designed specifically for the model presented in the previous section, and how our algorithm takes specific advantage of one-sided communications and remote memory access.

Causal ordering of events

In section 3.3, we stated that there exists a race condition between a set of inter-process events when there exists no causal order between these events. In practice, this definition must be refined: concurrent accesses that do not modify the data are not problematic. Hence, when an event occurs between two processes, we need to determine whether it is causally ordered with the latest write on this data.

Lamport clocks [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] keep track of the logical time on a process; vector clocks (introduced by [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF]) allow for the partial causal ordering of events. A vector clock on a given process contains the logical time of each other process at the moment when the other process had an influence on this process (i.e., last time it had a causal influence on this process).

When the causality relationship between a set of events that contains at least a write event cannot be established, we can conclude that there exists a race condition between them. More specifically, when we compare the vector clocks that are associated with these events and the latest write.

Lemma 1 (See [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF], theorem 10) ∀e, e ∈ E : e < e iff H(e) < H(e ) and e e iff C(e) C(e ) Corollary 1 Consider two events denoted e 1 and e 2 and their respective clocks H 1 and H 2 . If no ordering can be determined between H 1 and H 2 , there exists a race condition between e 1 and e 2 (e 1 × e 2 ).

In the following algorithms, we detail the put and get commands. Algorithm 4 describes a put(src, j, dst) performed from P 0 by the library to write the content of src address into process j's memory at address dst. Algorithm 5 describes a get(dst, j, src) performed by the library to retreive content of src address from process P j's memory to process P 0's memory at address dst. Each process associates two clocks to areas of shared memory: a general-purpose clock V and a write clock W that keeps track of the latest write operation. Figure 7 shows an example of two concurrent remote read operations (i.e., get operations) on a variable a. This variable is initialized at a given value A before the remote accesses. Since none of the concurrent operations modifies its value, this is not a race condition. As stated in section 3.3, there exists a race condition between concurrent data accesses iff at least one access modifies the value of the data. As a consequence, concurrent read-only accesses must not be considered as race conditions.

The lock (resp. lock local) primitive takes care of mutual exclusion if the addressed value is in public space or not. If the address is in private space, there is no need of a real lock (except in multithreading). The lock(j, addr) command locks an area of memory located at address addr on process j. The local lock(addr) command locks an area of memory located at address addr on the local process.

In figure 8, we present three use-cases of our algorithm: two situations of race conditions and one when the messages are causally ordered.

Clock update

The clock vector V P i (or simply V in the algorithms to denote the local one) is maintained by each process P i. This vector is a local view of the global time. It is initially set to zero. Before P i performs an event, it increments its local logical clock V P i [i, i] (update local clock). Clocks are updated by any event as shown in algorithm 7, see [START_REF] Raynal | Logical time: Capturing causality in distributed systems[END_REF]. The update clock W algorithm is similar to the update clock algorithm, except that it updates the value of the "write clock" W .

Since the shared memory area is locked, there cannot exist a race condition between the remote memory accesses induced by the race condition detection mechanism.

Discussion on the size of clocks

If n denotes the number of processes in the system, it has been shown that the size of the vector clocks must be at least n [START_REF] Charron-Bost | Concerning the size of logical clocks in distributed systems[END_REF]. As a consequence, the size of the clocks cannot be reduced.

Discussion on error signalisation

In the algorithm presented here, we refine the error detection by using two distinct clocks, a generalpurpose one and a "write clock". The drawback of this approach is that it doubles the necessary amount of memory. On the other hand, it offers more precision and eliminates numerous cases of false positives (e.g., concurrent read-only accesses).

A race condition may not be fatal: some algorithms contain race conditions on purpose. For example, parallel master-worker computation patterns induce a race condition between workers when the results are sent to the master. Therefore, race conditions must be signaled to the user (e.g., by a message on the standard output of the program), but they must not abort the execution of the program.

As an example where race conditions are not an issue, we can consider a distributed sum computation. For instance, approximation of the Pi number using the sub-curve area method (it calculates the area under the curve of a quarter of a circle) distributes computation between the available parallel processes and computes a global sum of their partial results. Since the sum operation is commutative, this global sum can be computed in any order.

Algorithm 9 gives a distributed algorithm that computes the value of π in the parallel pseudolanguage we described in section 3.4. There exists a race condition on line 8, since the processes can write into the shared variable sum in any order.

This race condition is depicted in figure 9, on which a possible execution of this algorithm is represented. In this execution, the relative computing and communication speeds of the four processes are such that line 8 is first executed by process P 0, then by process P 2, followed by process P 1 and finally by process P 3. However, any other order would have given the correct result. As a consequence, this race condition does not have any influence on the final result of the computation. Hence, it is not fatal, and the program can be executed normally. A race condition detection system ought to notify the programmer about it but not abort the execution.

Conclusion and perspective

In this paper, we presented a model for distributed shared memory. This model considers interactions between processes and causal dependencies, while taking into account specific features from hardware used to implement such systems.

In this model, we propose an algorithm for detecting race conditions caused by the absence of ordering between events in the distributed system. This algorithm can be implemented in the communication library of the run-time support system that executes the program on a distributed system.

Discussion about overheads

As stated in section 4.3, the size of the clocks cannot be smaller than n, if n denotes the number of processes in the system. Moreover, a clock must be used for each shared piece of data. As a consequence, our algorithm has an overhead on data storage space (clocks associated with shared data) and with communication performance. Our algorithm is presented using additional messages (O(1) messages carrying O(n) bytes) for clock update introducing an overhead on latency. Note that sometimes it can be implemented by extending existing messages (by piggybacking techniques or extension of headers/enveloppe of active messages) when the underlying communication network allow longer messages.

However, race condition detection is typically a debugging technique. It does not need to be enabled on a parallel application that is actually running at full performance and large-scale systems. Parallel programmes are typically debugged on small data sets and a few processes (typically, about 10 processes).

Future works

The model presented in this paper leads to new interpretations of distributed algorithms. New operations can also be imagined, such as non-collective, global operations: for example, a process can perform a reduction (i.e., a global operation on some data held by all the other processes) without any participation of the other processes, by fetching the data remotely.

Our race condition detection algorithm can be implemented at two levels: in the communication library of a parallel language, for automatic detection of conflictual accesses, or in the pre-compiler, as wrappers around remote data accesses. It does not require any modification to the UPC language, since our algorithms can be implemented in the implementation of the communication primitives called by UPC.

It is also possible to extend this technique to perform trace analysis. When doing trace analysis, it is necessary to keep all messages interactions (generally speaking it is done at the sender side) and label them with a kind of "date". It is often hard (or impossible) to have a real physical global clock (for basic physics reasons, as stated in [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]). Some authors use some special counters available on processors (for example Time Stamp Counter of Intel processors) to achieve this; however, there is no reason for the timestamp counters of multiple CPUs to stay synchronized. We can use vector clocks as timestamps for this purpose, which would be a better way to memorize a "date". It can also be used for the so-called "replay" debugging technique: it logs the causality information of the execution of deployed application processes and replays them deterministically, reproducing race conditions faithfully and non-deterministic failures, enabling careful offline analysis and failure confinement [START_REF] Bouteiller | Retrospect: Deterministic replay of MPI applications for interactive distributed debugging[END_REF].

Figure 2 :

 2 Figure 2: Remote R/W memory accesses.

Figure 4 :

 4 Figure 4: Example of race condition

Algorithm 1 : 1 shared

 11 Example using our parallel pseudo-language begin

Figure 5 :

 5 Figure 5: Communications performed by algorithm 1: first situation

Figure 6 :

 6 Figure 6: Communications performed by algorithm 1: second situation

Figure 7 :j begin 1 lock 3 V 4 W

 7134 Figure 7: Two concurrent get operations

Algorithm 5 :j begin 1 lock local(dst); 2 lock(j, src); 3 W 4 V 6 signal 13 Algorithm 6 :Figure 8 : 1 V 2 V 3 V 5 end 6 Algorithm 8 : 2 return V ; 3 end 4

 5123461368123568234 Figure 8: Detecting race conditions with vector clocks

Algorithm 9 : 1 sharedFigure 9 :

 919 Figure 9: Possible communications performed by algorithm 9 on 4 processes

http://www.top500.org

http://www.infinibandta.org/

http://www.myri.com

Processes access areas of public memory mapped by other processes using point-to-point communications. They use one-sided communications: the process that initiates the communication can access remote data without any notification on the other process's side. Hence, a process A is not aware of the fact that another process B has accessed (i.e., read or written) its memory.


Heithem Abbes

Parallelization of Littlewood-Richardson Coefficients Computation and its Integration into the BonjourGrid Meta-Desktop Grid Middleware

Keywords: Incorporation of a threaded application with Desktop Grid infrastructures, Desktop Grid models, Modeling, Simulation, Emulation of large-scale environments, Resource management and scheduling

The aim of this paper is to show how to parallelize a compute intensive application in mathematics (Group Theory) for an institutional Desktop Grid platform coordinated by a meta-grid middleware named BonjourGrid. The paper is twofold: first of all, it shows how to parallelize a sequential program for a multicore CPU which participates in the computation and second it demonstrates the effort for launching multiple instances of the solutions for the mathematical problem with the BonjourGrid middleware. BonjourGrid is a fully decentralized Desktop Grid middleware. The main results of the paper are: a) an efficient multi-threaded version of a sequential program to compute Littlewood-Richardson coefficients, namely the Multi-LR program and b) a proof of concept, centered around the user needs, for the BonjourGrid middleware dedicated to coordinate multiple instances of programsfor Desktop Grids and with the help of Multi-LR. In this paper, the scientific work consists in starting from a model for the solution of a compute intensive problem in mathematics, to incorporate the concrete model into a middleware and running it on commodity PCs platform managed by an innovative meta Desktop Grid middleware.

Introduction and motivations

Desktop Grid (DG) have been successfully used to address large applications with significant computational requirements, including search for extraterrestrial intelligence (SETI@Home [START_REF]Seti@home[END_REF]), global climate predication (Climatprediction.net [21]), and cosmic rays study (XtremWeb [START_REF] Fedak | Xtremweb: A generic global computing system[END_REF][START_REF] Cappello | Computing on Large Scale Distributed Systems: XtremWeb Architecture,Programming Models, Security, Tests and Convergence with Grid[END_REF]). While the success of these applications demonstrates the potential of Desktop Grid, existing systems are often centralized and suffer from relying always on an administrative staff who guarantees the continuous running of the master. Moreover, although, in practical, the crash of the master is not frequent and replication techniques can solve this problem when it occurs, we still believe in the need to decentralized approaches. We justify this by the fact that since all institutions have not the same financial means to guarantee high levels of equipments robustness, the community should offer solutions to institutions which have not sufficient facilities to avoid the central element crash for instance. Thus, we believe in the importance of collaborative and decentralized solutions for the setting of Desktop Grid middleware.

In this context, Abbes, Cérin and Jemni have proposed a novel approach, called BonjourGrid [START_REF] Heithem Abbes | BonjourGrid as a Decentralised Job Scheduler[END_REF][START_REF] Heithem Abbes | BonjourGrid: Orchestration of Multiinstances of Grid Middleware on Institutional Desktop Grid[END_REF][START_REF] Heithem Abbes | BonjourGrid: Orchestration of Multiinstances of Grid Middleware on Institutional Desktop Grid[END_REF], which enables to establish a specific execution environment for each user. Indeed, BonjourGrid constructs, dynamically and in a decentralized way, a Computing Element (CE -a CE is a set of workers managed by one master, or an instance of a local Desktop Grid middleware) when a user needs to run an application. BonjourGrid orchestrates multiple instances of CEs in a decentralized manner. Our approach does not rely on a unique static central element in the whole system, since we dedicate a temporary central element for each running application, in a dynamic way.

Furthermore, it is important to note that BonjourGrid is not only a decentralized approach to orchestrate and coordinate local DG (Desktop Grid) but it is also a system which is able, contrarily to classical DG, to construct specific execution environment on-demand (based on any combination of XtremWeb, Boinc, Condor middleware), in a decentralized, dynamic and autonomous way. This is the originality of the BonjourGrid system. We consider that it is a novel approach, a step forward regarding Desktop Grid systems.

The application that we investigate in this paper to explain our approach is a compute intensive applicationin the field of Group Theory. To our knowledge, there has been no attempt in the past to derive a multi-threaded solution of the computation of Littlewood-Richardson coefficients for desktop grid, especially for those based on multi-core processors. We give an original and efficient solution to this difficult problem because it is hard to predict on the fly the space where the solution is located in as we will see later in the paper.

Therefore, the paper is mainly organized according to two central discussions: first of all the threading of the computation of LR coefficients and second the integration of the solution into BonjourGrid. The typical use case underlying our work is the following: a mathematician needs to guess the property of some numbers. Usually it uses the PCs in its institution to 'compute' the properties of the objects with the sequential implementation of Schur1 while colleagues work on others problems. He requires also that it could be done with a minimal effort for him (minimum of deployment, minimum of line codes to launch the application) because he is not an expert in grid middleware. This user belongs to the community of Boinc users, so he wants to use this middleware whereas one of his colleague belongs to the Condor community and he wants to use Condor. Our solution allows any user to run the multi-threaded release of the Schur application that we introduce in this paper on its favorite middleware.

We do not fully describe the adaptation of the application on the BonjourGrid infrastructure because it is out of the scope and will require too much space. BonjourGrid is a large project consisting in coordinating, simultaneously major desktop grid middleware such as Condor, Boinc and XtremWeb instances. This idea, while closely related to the concept of "Infrastructure on demand" concept central to the Cloud Computing paradigm and thus not completely new, may help in widening the spread of the Desktop Grid approach. The article strives to demonstrate the feasibility of the solution using the application from mathematics namely the computation of LR coefficients because we still need to validate BonjourGrid through 'real applications' and not emulation as we have already done. We choose the LR coefficients application because it is used by people in our laboratory, and because it is a central piece in the Schur package that is a tool to 'guess' properties of polynomials for instance.

Again, the main result of this paper is not about a new Desktop Grid middleware because in this case we need also to address, for the sake of completeness, the problems of volatility (host churn) and heterogeneity but it is about a multithreaded code for the computation of LR coefficients. The ultimate goal is not to beat records in speed but to demonstrate that BonjourGrid is able to coordinate multiple instances of the same application on multiple instances of an innovative grid middleware deployed over an institution and also that a non experimented user may use this new environment.

A computation problem in Group Theory

Mathematical background

In order to be self content we need some standard definitions and vocabulary from group theory [START_REF] Macdonald | Symmetric functions a nd Hall Polynomials[END_REF]. A partition of a positive integer n is a way of writing n as a sum of non increasing strictly positive integers. For example λ = (4,2,2,1) and μ = (2,1) are partitions of n = 9 and n′ = 3 respectively. We write λ ⊢ n and μ ⊢ n′ or |λ| = n and |μ| = n′.

The Ferrers diagram F λ associated to a partition λ = (λ 1 ,λ 2 , ,λ p ) consists of |λ| = n boxes, arranged in l(λ) = p left-justified rows of lengths λ 1 , λ 2 , , λ p . Rows in F λ are oriented downwards. F λ is called the shape of λ.

A semi-standard Young tableau of shape F λ (SSY T λ ) is a numbering of the boxes of F λ with entries from {1,2, ,n}, weakly increasing across rows and strictly increasing down columns. A tableau is standard (SY T λ ) if all its entries are different. Skew tableaux are defined in an analogous way. For example, for λ = (4,2,2,1) and μ = (2,1), F λ and SSY T λ are as follows:

A Symmetric Function is a function which is symmetric or invariant under permutation of its variables.

where σ is any permutation of the symmetric group S n . The Schur function s λ is the symmetric function defined as:

where Tab(λ) is the set of all tableaux of shape λ and x T is the product of the x i for all i appearing in the tableau T. For example, for μ = (2,1) there are 8 semi-standard tableaux of shape μ using {1,2,3}:

The associated Schur function is therefore:

The

The hives model

Littlewood-Richardson coefficients c λμ ν have a polynomial growth with respect to the dilatation factor N : ∈ ℕ where P λμ ν is a polynomial in N with non negative rational coefficients depending on λ, μ and ν. This was first conjectured in [START_REF] King | Toumazet Stretched Littlewood-Richardson and Kostka coefficients[END_REF]. A partial proof (existence of P λμ ν and rationality of coefficients) was given in [START_REF] Rassart | A polynomiality property for Littlewood-Richardson coefficients[END_REF].

Those polynomials [START_REF] King | Toumazet Stretched Littlewood-Richardson and Kostka coefficients[END_REF] are obtained considering a model known as the hive model. An n-integer-hive is a triangular array of non negative integers a j i with 0 ≤ i,j ≤ n where neighboring entries define three distinct types of rhombus, each with its own constraint condition.

In each case, with the labeling as shown, the hive condition takes the form:

A LR-hives [START_REF] King | Toumazet Stretched Littlewood-Richardson and Kostka coefficients[END_REF] is an integer hive satisfying the hive condition (1) for all its constituent rhombic of type R 1 , R 2 and R 3 , with border labels determined by the partitions λ, μ and ν, such that:

with l(λ), l(μ), l(ν) ≤ n and |λ| + |μ| = |ν|.

For example, for n = 4, LR-hives will be sketched as:

The Littlewood-Richardson coefficient c λμ ν is the number of LR-hives with border labeled as above by λ, μ and ν. So c λμ ν is the number of triples (a 1

1 ,a 1 2 ,a 2 1
) satisfying ( 1) for all rhombic of type R 1 , R 2 and R 3 . That is the number of integer solutions to the system of inequalities obtained by writing ( 1) for all rhombic. The degree of the polynomial P λμ ν (N) is always bounded by (n -1)(n -2)∕2, the number of interior points of the hive, but if any of the partitions, λ, μ or ν has repeated parts then it is possible to use the hive inequalities to improve this bound with some maxDeg < (n-1)(n-2)∕2. We compute c Nλ,Nμ Nν for any N with ∈ ℕ N increasing, and compute the interpolating polynomial for the points (N,c Nλ,Nμ

Nν

). The computation is stopped when two successive interpolating polynomials are equal. As stated by theory, actually the number of computed coefficients is often less than (n -1)(n -2)∕2.

A parallel computation

The aim of this section is to explain the different ways we compute the LR coefficients in parallel. Two kinds of parallelization is under concern in this article which are the parallelization on a single machine (multicore CPU) and the parallelization at the grid level. The goal is to replace the current sequential code provided with Schur2 by a multi-threaded one able to be integrated into a DG middleware. Schur is recognized to be a powerful and efficient tool for calculating properties of Lie groups and symmetric functions. Developing a parallel version of Schur is challenging and we restrict our study to the computation of LR coefficients in parallel.

Parallelization on a single machine: the Multi-LR code

The ways we are computing the Littlewood-Richardson coefficients allows us to split the enumeration process of the feasible space in several parts. To do this, we use the Pthread API, and divide the enumeration process in two pieces:

1. We assume that only n threads are allowed for the process. The first step of the enumeration is to divide the feasible space in n parts. Since the enumeration space is made of a product of intervals, we divide the first interval in min(nb_thread,interval_size) of the same size, and for each part we attach a thread. 2. Each thread uses an optimized method to explore the feasible space and returns the number of solutions. Once the enumeration is done for all the threads, the main thread sends the result to the user.

Parallelization using a Desktop Grid

The computation of LR polynomials can be achieved using the multiple machine on a local network. The idea is to compute the Littlewood-Richardson coefficients on various machines for a set of dilatation coefficients and to collect the results to build the interpolating polynomial. The time needed to compute one LR coefficient depends on the partitions given to the program and on the dilatation coefficient. The computation is stopped when the sequence becomes stationary. That means that P iλμ ν = P ( i+1)λμ ν for some i and it holds for any j greater than i.

The complexity of the algorithm used to compute each Littlewood-Richardson coefficient is where m is the number of intervals in the hive, |I k | is the number of elements in the interval I k and N is the dilatation coefficient. Thus, the time needed to compute a Littlewood-Richardson coefficient has a polynomial growth of order m (see figure 1). This means that for high values of m, the time needed to compute the coefficient N + 1 will be greater than the time needed to compute all the coefficients up to N.

In other words, for large values of m, the time needed for the whole computation (all coefficients) is more or less the time needed to compute the last one.

Experimental Results

Performance gain on a single machine

The use of threads to compute the Littlewood-Richardson coefficients leads to improvement in the execution time. To compare the gain in performance, we use a multi-core processor. In the remainder of the section, computation are done on a Bi-AMD Opteron dual core at 2.8GHz, which means that 4 cores were available for the computation.

The computation of Littlewood-Richardson coefficients was done for various partitions and variable maximum number of threads. The first remark is that the gain in time depends on the first interval (which is divided to create the threads) and on the symmetry of the problem. For example if the first interval is a single value, only one thread is launched, and the time needed for the computation is the same than without threads.

The "symmetry" of the feasible space is also important for the enumeration. To understand this, the algorithm has to be explained again. As said before, the enumeration method used by each thread is optimized, so that the whole feasible space is not searched. Each step of the algorithm corresponds to one point of the hive. For each feasible value of a point, the feasible space is computed again so that useless values are not tried. Therefore, the number of feasible values tried by each thread depends on the interval it received from the first step, and some threads are faster than other. This phenomenon can be observed on Figure 2, which shows the results for the partitions , μ = (6,6,4,2,1) and and , μ = (7,7,7,4), . The computation time for the dilatation coefficient N = 7 does not decrease when the number of threads increases.

However, the majority of the practical cases shows that threading the program is useful. The computation time is divided by a factor of 3.5, and nearly four in thebest cases, depending on the "symmetry" of the problem. In fact, we could think that the results should be similar for any number of threads greater than 4. But as we can see on the first diagram of figure 2, the time needed for the computation is stationary for a number of threads greater than 10. This is explained by the fact that for less than 10 threads, one of the threads is slower than the others because the number of values it deals with is bigger than for the other threads.

For a very large number of threads, the performance mainly depends on the operating system's scheduler. We are using the Linux scheduler, and even with a great number of threads (over 200 threads), the results are impressive. 3 Porting the parallel code on a Desktop Grid platform

Introduction to BonjourGrid

BonjourGrid is a meta Desktop Grid middleware meaning that it is able to instantiate multiple Desktop Grid middleware in the same infrastructure. As referenced in many other works [START_REF] Domingues | Using Checkpointing to Enhance Turnaround Time on Institutional Desktop Grids[END_REF][START_REF] Kondo | Resource Management for Rapid Application Turnaround on Enterprise Desktop Grids[END_REF], this kind of environment is called Institutional Desktop Grid or Enterprise Desktop Grid (e.g located in the same institution). The principle of the proposed approach is to create, dynamically and in a decentralized way, a specific execution environment for each user to execute any type of applications without any system administrator intervention. An environment do not affect another one if it fails.

This section aims at demonstrating the potential of BonjourGrid and it serves as a proof of concept. The BonjourGrid protocol has been validated in [START_REF] Heithem Abbes | BonjourGrid as a Decentralised Job Scheduler[END_REF][START_REF] Heithem Abbes | BonjourGrid: Orchestration of Multiinstances of Grid Middleware on Institutional Desktop Grid[END_REF][START_REF] Abbes | Fault tolerance based on the Publish-subscribe Paradigm for the BonjourGrid Middleware[END_REF] but the goal was to show that BonjourGrid is able to behave "like" a job scheduler. Here we are deploying a real application on top of BonjourGrid. Moreover, in this section we do not evaluate the application performance on the Grid, but we explain, from a user point of view, what is the work to accomplish to run a code on top of the middleware. Details about BonjourGrid follow and the software is available on sourceForge3 . Each user, behind its desktop machine in his office, can submit an application. BonjourGrid deploys a master (coordinator), locally on the user machine, and requests for participants (workers). Negotiations to select them should now take place. Using a publish/subscribe infrastructure, each machine publishes its state (idle, worker or master) when changes occur as well as information about its local load or its "utilization cost", in order to provide useful metrics for the selection of participants by the BonjourGrid middleware. Under these assumptions, the master can select a subset of workers nodes according to a strategy that could balance the "power" of the node and the "price" of its use. The master and the set of selected workers build the Computing Element (CE) which will execute, manage and control the user application. When a CE finishes the application, its master becomes free, returns in idle state and releases all workers to return also to the idle state. When no application is submitted, all machines are in the idle state.

The main technologies used in BonjourGrid are publish/subscribe systems [17] and ZeroConf protocol [START_REF] Steinberg | Zero Configuration Networking: The Definitive Guide[END_REF]. In a previous work [START_REF] Abbes | Chistophe Dubacq Analysis of Peer-to-Peer Protocols Performance for Establishing a Decentralized Desktop Grid Middleware[END_REF], we tackled the following questions: Can a system based on publish/subscribe protocols be "powerful"? Can it be scalable? What is the response time to publish a service? What is the discovery time of a service? We carried out experiments on various protocols such as Bonjour protocol, on the GdX node of Grid5000 [20] platform using more than 300 machines (AMD Opterons connected with a 1Gb/s network). Measures show that Bonjour is reliable and very powerful in resources discovery. Indeed, Bonjour discovers more than 300 services published simultaneously in less than 2 seconds with 0% of loss. These evaluations support and justify our choice to use Bonjour as a basis for the discovery protocol in BonjourGrid system. Moreover, we believe that using an existing and tested protocol for the industry (Bonjour is available on Macintosh machines), to evaluate its usability in Desktop Grid environment is, in itself, of great value and very useful for the community.

The advantages in using a publication/subscription (Pub-Sub) [START_REF] Th | The many faces of publish/subscribe[END_REF] mechanisms come from the asynchronous nature of the paradigm. The Pub-Sub paradigm is an asynchronous mode for communicating between entities. Some users, namely the subscribers or clients or consumers, express and record their interests under the form or subscriptions, and are notified later by another event produced by other users, namely the producers). This communication mode is thus multipoint, anonymous and implicit. It is a multipoint mode (one-tomany or many-to-many) because events are sent to the set of clients that have declared an interest into the topic. It is an anonymous mode because the provider does not know the identity of clients. It is an implicit mode because the clients are determined by the subscriptions and not explicitly by the providers.

It is also known that this asynchronous communicating mode allows spatial deco upling (the interacting entities do not know each other), and time decoupling (the interacting entities do not need to participate at the same time). This total decoupling between the production and the consumption of services increases the scalability by eliminating many sorts of explicit dependencies between participating entities. Eliminating dependencies reduces the coordination needs and consequently the synchronizations between entities. These advantages make the communicating infrastructure well suited to the management of distributed systems and simplify the development of a middleware for the coordination of DGs.

The key idea of BonjourGrid is to rely on existing Institutional Desktop Grid middleware, and to orchestrate and coordinate multiple instances, i.e multiple CEs, through a publish/subscribe system (see figure 3). Each CE will be owned by the user who has started the master on his machine. Then this CE is responsible for the execution of one or many applications for the same user. As shown in figure 3, in the user level, a user A (resp. B) deploys his application on his machine and the execution seems to be local. Level 1 (middleware layer) shows that, actually, a CE with 4 (resp. 5) workers has been dynamically created, specifically for the user A (resp. B). Level 0 shows that all machines are interconnected and under the availability of any user.

Implementation

BonjourGrid is entirely implemented using Python. We have used Bonjour-py package that offers a python interface to interact with Bonjour protocol. When a machine joins our system, information about its characteristics (i.e. MHZ, CPU, RAM, Hostname, IP address, average load) are automatically collected and stored in a Python dictionary. These informations are useful for the selection of the suitable machines that match the application requirements. For instance, one would like to select workers according to the CPU metric only; another one would like to select workers that have been being idle for a long time. In our system, we can easily plug a new policy in order to select workers. We can also imagine, in the future, to make an economic model based choice of the suitable policy; the coding effort is not important, thanks to the Python abstractions.

Running the XtremWeb services

In this paper, we choose to use XW (XtremWeb) as a middleware for the CE. To run or deactivate an XW service (coordinator or worker), the environment should be already installed. The procedure to install a XW-Coordinator, in particular, is not currently simple enough, so we have improved it. We would not like to make user spends his time in configuring and installing the various files and modules necessary to the XW installation. An installation procedure consists in installing a MySQL server, Java Development Kit, creating a specific database for XW, making several directories and configuring system files. Consequently, we set up an automatic installation of all the necessary packages. Such facilities were not included in the current distribution of XW.

Experiments and validation of BonjourGrid

From a user point of view, deploying an application on BonjourGrid starts with preparing the executable code and data that are archived in a compressed file. BonjourGrid enables the execution of applications with precedences between tasks. Indeed, the user can describe the precedences of a data flow graph using a XML description; this is not trivial, especially, for complex applications. SDAD is the system of deployment that we have developed and it helps the user in describing the data flow graph of his application according to an XML syntax using a graphical interface (for simple applications, see figure 9) or an advanced wizard (for complex ones, see figure 10). It also helps user to put the different files of his applications (i.e. binary and data files) in the right path of his package. SDAD generates a compressed package ready to be deployed on BonjourGrid system. Now, the user can submit his application to BonjourGrid. He can specify the size of the computing element (CE) and the middleware (XtremWeb in this case study) to run the application. BonjourGrid, then, will construct the CE according to the criteria mentioned in the XML file.

To summarize, using the SDAD tool, the user can draw the task graph and put binary and data files in the suitable path in the application tree. Thereafter, SDAD will generate the XML description of the application which is used by XW and BonjourGrid.

As described in subsection 2.3, the first module of the application Hives can be divided in several parallel tasks. The outputs of these tasks are forwarded to the so called BuildInter module. Finally, the module Interp gives the interpolation. Figure 4 shows the data flow graph of the Hives application.

Figure 5 shows the first part of this file which illustrates the description of the three modules of the application (i.e, OS architecture, OS type, location of binary files…). Here, the user can provide several binary files for different architectures and OS types. The precedences between tasks are illustrated in the second part of the XML file shown in Figure 6. On Figure 6 we have simplified the XML file to make it easier to understand (we drawn only two parallel tasks for the Hives module). Now, Hives is ready to be submitted to the BonjourGrid system. In the following, we illustrate snapshots picked out from a Hives execution using the Orsay node of Grid5000 [20]. Specifically for this demo, we are going to dissociate the CE building phase from the effective submission to illustrate the different steps. First, we initiate machines in idle state. We launch the coordinator, on any machine, to start the building phase of a suitable CE. Figure 7 shows the outputs of a construction of a CE with 2 workers (just for the sake of clarity of reading). Indeed, the coordinator is started on the gdx-5 node, requiring two workers as shown in the figure 7. For that, the coordinator gdx-5 searches for idle machines which match the tasks requirements. Figure 7 shows that the coordinator gdx-5 discovers in this test two idle machines gdx-9 and gdx-17 and asks them to accept to work for it. Thereafter, the gdx-5 coordinator receives two confirmations from gdx-17 and gdx-9 as depicted in figure 8. When the execution completes, we can invoke BonjourGrid to download the results. To summarize, the objective of this experiment was to present a use case of BonjourGrid using a real application and from the user point of view. Abbes, Cérin and Jemni have already done experiments to analyze the performance of BonjourGrid in [START_REF] Heithem Abbes | BonjourGrid as a Decentralised Job Scheduler[END_REF][START_REF] Heithem Abbes | BonjourGrid: Orchestration of Multiinstances of Grid Middleware on Institutional Desktop Grid[END_REF] and [START_REF] Abbes | Chistophe Dubacq Analysis of Peer-to-Peer Protocols Performance for Establishing a Decentralized Desktop Grid Middleware[END_REF] but the scope of this work is to demonstrate how BonjourGrid can help users to construct, dynamically and without any intervention of a system administrator, their own environments to deploy and perform out a parallel application.

Related work on advanced Desktop Grid Architectures

Before concluding, we compare BonjourGrid with others systems. OurGrid [START_REF] Cirne | Labs of the World, Unite!!![END_REF] system avoids the centralized server by creating the notion of the home machine from which applications are submitted; the existence of several home machines reduces the impact of failures at the same time. Moreover, OurGrid provides an accounting model to assure a fair resources sharing in order to attract nodes to join the system. However, the originality of BonjourGrid comparing to OurGrid is that it supports distributed applications with precedence between tasks as well as Bag-of-Tasks (BOT), while OurGrid supports only BOT applications (BOT applications are independent divisible tasks). WaveGrid [START_REF] Zhou | WaveGrid: a scalable fast-turnaround heterogeneous peer-based Desktop Grid system[END_REF] is a P2P middleware which uses a timezone-aware overlay network to indicate when hosts have a large block of idle time. This system reinforces the idea of BonjourGrid concept since changing from a set of workers to another one depending on the time zone (Wave Grid) is analogous to the principle of creating a CE from an application to another one in BonjourGrid, and depending on users requirements.

Approaches based on publish/subscribe systems to coordinate or decentralise Desktop Grid infrastructures are not very numerous according to our knowledge. A similar project to our project is the Xgrid project [19]. In Xgrid system, each agent (or worker) makes itself available to a single controller. It receives computational tasks and returns the results of these computations to the controller. Hence, the whole architecture relies on asingle and static component which is the controller. Moreover, Xgrid runs only on MacOS systems. In contrast with Xgrid, in BonjourGrid, the coordinator is not static and is created in a dynamic way. Furthermore, BonjourGrid is more generic since it is possible to "plug" on it any computing system (XW, Boinc, Condor) while Xgrid has its own computing system. The key advantage of bonjourGrid is that the user is free to use his favorite desktop grid middleware.

Conclusion and future works

In this work, we have proposed a novel algorithm to compute Littlewood-Richardson coefficients (by the Hive method) in parallel and we have shown how to run the code on top of BonjourGrid. The aim of BonjourGrid is to orchestrate multi-instances of computing elements, in a decentralized manner. BonjourGrid creates, dynamically, a specific environment for the user to run his application. There is no need for a system administrator. Indeed, BonjourGrid is fully autonomous and decentralized. We have conducted several experimentations to show that BonjourGrid operates well with a real world application. Therefore BonjourGrid has shown its usefulness. Moreover, the deployment of the Hive code on BonjourGrid, demonstrates that BonjourGrid may help users to create several independent environments. Then, mathematicians, for instance, can create their Desktop Grid easily to run their parallel applications.

Several issues must be taken into account in our future work about meta-Desktop Grid middleware. The first issue is to build a fault-tolerant system for the coordinators. In fact, it is important to continue the execution of the application when the coordinator (user machine) fails (it is disconnected for instance). This issue has been solved and it is currently tested overand validated on Grid'5000 testbed. Condor, Boinc plugins have also been built and are currently tested with the Hive code, especially but not only. The second issue is the reservation of participation: in the current version, BonjourGrid allocates available resources for a user without any reservation rules. Thus, BonjourGrid may allocate to a single user all the available resources. The third issue is to pass to a wide area network.

In order to be widely adopted by the community, we are currently working also on the following issues. First, BonjourGrid is still working on top of Bonjour which is a local-area network. The wide area-Bonjour4 is available but require some work to configure it. The goal is to deploy our protocol over the Internet and not over a local network. After installing Wide Area Bonjour, the experimental work could not really be about performance because they cannot be reproducible over Internet. The setting of a large platform of volunteers is more challenging and the experimental work would be to show that the system can handle large configurations of PC.

Another choice is to implement our protocol over another Pub-Sub tool. The target language may take the form of a popular language on the Internet such as XMPP5 . In fact, many libraries support the publishsubscribe mechanism are being deployed (e.g. Jetty), including the forthcoming HTML5 standard. The danger is reimplementing the protocol is to forget some implementation details that make the protocol correct. We are currently working on the specification of our coordination protocol by using Petri Net tools in order to isolate the main properties of our protocol but also the main knowhow in using Pub-sub systems. Petri Net is a formal tool to reasoning about the specification in order to check fundamental properties of the design such as safety ("nothing bad happens") for which the absence of deadlock is an example and liveness ("something good eventualy happens").

Any grid middleware should also support a security level. Even if you are sure that communications will not be decrypted you must ensure the authentication of the participants. Conventionally authentication in grids is via X509 certificates. In the case of BonjourGrid, we also need an orchestration of certificates to ensure for example that two Boinc coordinators can exchange participants. Who says X509 certificates also said VO (Virtual Organizations) that allow the federation of resources. The problem will be to manage various VOs.

We are also working on the adaptation of BonjourGrid principles for data management. The main challenge is to resume the protocol to coordinate data servers by introducing a new state in the Protocol to mean that a node can become a data server. This new state impacts the protocol with respect to fault tolerance. It will be necessary to revise the protocol to manage data backup and servers backup. We hope that this work helps to understand what is a possible future for Desktop Grid middleware as well as the new efforts that users should make to use such systems.

  Littlewood-Richardson coefficients c λμ ν are defined as the structure constants for the multiplication in the basis of the Schur functions. So if λ ⊢ n and μ ⊢ m: Example: Thus c 4221 ,21 5322 = c 4221 ,21 43221 = 2 and c 4221 ,21 6321 = c 4221 ,21 422211 = 1.

  The four input parameters (λ,μ,ν,N) are given to the program, where N is the dilatation coefficient. ∈ ℕ For each computer on the network, a unique dilatation coefficient is given. The result of each computation is the Littlewood-Richardson coefficient c Nλ,Nμ Nν . Thus many interpolation points (N,c Nλ,Nμ Nν ) are computed. Each time a new interpolation point is produced, a new interpolating polynomial is computed using all the values available. Thus, a sequence of polynomials is built:

Figure 1 :

 1 Figure 1: Computation time with respect to the dilatation coefficient. The partitions are λ = (5,3,2,2,1), μ = (4,3,2,2,1) and ν = (7,5,4,4,3,2).

Figure 2 :

 2 Figure 2: Evolution of the computation time needed with the number of threads allowed for partitions.

Figure 3 :

 3 Figure 3: BonjourGrid abstract layers

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Description of the data flow graph of Hives composed with 3 modules; Hives, BuildInter and Interp

Figure 7 :

 7 Figure 7: Construction of a new CE with 2 workers

Figure 8 :

 8 Figure 8: Confirmation of two idle machines to work for the master gdx-5

  .... Faire aussi des perspectives sur le calcul des coeff... c.a.d des perspectives moins en rapport avec des problematiques architectural.

Figure 9 :Figure 10 :

 910 Figure 9: One snapshot of SDAD tool which depicts the graphical interface to draw the Hives data flow graph


Etienne Corvee
email: etienne.corvee@inria.fr

Slawomir Bak
email: slawomir.bak@inria.fr

Francois Bremond
email: francois.bremond@inria.fr

People detection and re-identification for multi surveillance cameras

Keywords: people detection, people tracking, people re-identification, local binary pattern, mean Riemannian covariance

Re-identifying people in a network of non overlapping cameras requires people to be accurately detected and tracked in order to build a strong visual signature of people appearances. Traditional surveillance cameras do not provide high enough image resolution to iris recognition algorithms. State of the art face recognition can not be easily applied to surveillance videos as people need to be facing the camera at a close range. The different lighting environment contained in each camera scene and the strong illumination variability occurring as people walk throughout a scene induce great variability in their appearance. In addition, people images occlud each other onto the image plane making people detection difficult to achieve. We propose a novel simplified Local Binary Pattern features to detect people, head and faces. A Mean Riemannian Covariance Grid (MRCG) is used to model appearance of tracked people to obtain highly discriminative human signature. The methods are evaluated and compared with the state of the art algorithms. We have created a new dataset from a network of 2 cameras showing the usefulness of our system to detect, track and re-identify people using appearance and face features.

Introduction

Recently, the person re-identification problem became one of the most important tasks in video surveillance. Only knowledge about identities of tracked persons can allow a system to fully extract semantic information about scene activities. The human reidentification problem can be defined as a determination whether a given person of interest has already been observed over a network of cameras.

Haar features have been studied intensely for the detection of objects, in particular for face detection [START_REF] Viola | Robust real-time face detection[END_REF]. One another major feature used for object detection is provided by HOG as evaluated in [START_REF] Dollar | Pedestrian detection: a benchmark[END_REF]. Pedestrians, faces and bicycles are successfully detected when represented by HOG (Dalal and Triggs, 2005a;[START_REF] Adam | Robust fragment-based tracking using integral histogram[END_REF]. A boosting technique is often used to model and rapidly detect objects [START_REF] Laptev | Improvements of object detection using boosted histograms[END_REF] such as humans [START_REF] Zhu | Fast human detection using a cascade of histograms of oriented gradients[END_REF]. SVM coupled with HOG is also often used (Dalal and Triggs, 2005a) for this task. Although Covariance features can be computationally expensive to estimate, they have strong discriminative powers. [START_REF] Tuzel | Pedestrian detection via classification on riemannian manifolds[END_REF] use a Logiboost algorithm on Riemannian manifolds where Covariance features in a Riemannian geometry are trained allowing the classification of pedestrians.

Many recent papers use body parts to enhance people detection performance. There are many ways to combine body parts; for instance [START_REF] Mohan | Example-based object detection in images by components[END_REF] studied different voting combination of body parts classifiers. In [START_REF] Mikolajczyk | Human detection based on a probabilistic assembly of robust part detectors[END_REF], Mikolajczyk et al. use 7 body part detectors independently trained to better detect humans using SIFTlike descriptors. Hussein and Porikli [START_REF] Hussein | Object detection via boosted deformable features[END_REF] introduce the notion of deformable features in a Logiboost algorithm to allow body parts to have non fixed locations in a people image template. More recently, high performances were obtained by [START_REF] Huang | High performance object detection by collaborative learning of joint ranking of granules features[END_REF]) using a highly trained set of granules.

There is a natural consequence of an invention of robust human detection algorithms to extend approaches for re-identification purposes. The appearance-based re-identification techniques were focused on associating pairs of images, each containing one instance of individual. These methods are named single-shot approaches [START_REF] Bak | Person re-identification using spatial covariance regions of human body parts[END_REF][START_REF] Park | Vise: Visual search engine using multiple networked cameras[END_REF][START_REF] Wang | Shape and appearance context modeling[END_REF] and until now they were the most popular techniques. Currently researches try to improve identification accuracy by integrating information over many images. The group of methods which employs multiple images of the same person as training data is called multiple-shot approaches.

As to single-shot approaches, in [START_REF] Park | Vise: Visual search engine using multiple networked cameras[END_REF] the clothing colour histograms taken over the head, shirt and pants regions together with the approximated height of the person were used as the discriminative feature. Similarly, clothing segmentation together with facial features [START_REF] Gallagher | Clothing cosegmentation for recognizing people[END_REF] were employed to re-identify individuals. Shape and appearance context model is proposed in [START_REF] Wang | Shape and appearance context modeling[END_REF]. A pedestrian image is segmented into regions and their colour spatial information is registered into a co-occurrence matrix. This method works well if the system considers only a frontal viewpoint. For more challenging cases, where viewpoint invariance is necessary, the ensemble of localized features (ELF) [START_REF] Gray | Viewpoint invariant pedestrian recognition with an ensemble of localized features[END_REF] has been proposed. Instead of designing a specific feature for characterizing people appearance, a machine learning algorithm constructs a model that provides maximum discriminability by filtering a set of simple features. Enhancement of discriminative power of each individual signature with respect to the others was also the main issue in [START_REF] Lin | Learning pairwise dissimilarity profiles for appearance recognition in visual surveillance[END_REF]. Pairwise dissimilarity profiles between individuals have been learned and adapted into nearest neighbour classification. Similarly, in [START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF], a rich set of feature descriptors based on colour, textures and edges has been used to reduce the amount of ambiguity among human class. The high-dimensional signature was transformed into a low-dimensional discriminant latent space using a statistical tool called Partial Least Squares (PLS) in one-against-all scheme. Nevertheless in both methods, an extensive learning phase based on the pedestrians to re-identify is necessary to extract discriminative profiles what makes the approaches non-scalable. The person re-identification problem has been reformulated as a ranking problem in [START_REF] Prosser | Person re-identification by support vector ranking[END_REF]. The authors presented extensive evaluation of learning approaches and show that a ranking relevance based model can improve the reliability and accuracy.

Concerning multiple-shot approaches, in [START_REF] Gheissari | Person reidentification using spatiotemporal appearance[END_REF] the spatiotemporal graph was generated for ten consecutive frames for grouping spatiotemporally similar regions. Then, clustering method is applied to capture the local descriptions over time and improve matching accuracy. In (Bak et al., 2010a), the AdaBoost was applied to extract the most discriminative and invariant Haar-like features.

Here, again one-against-all learning scheme was used to catch human dissimilarities. In [START_REF] Farenzena | Person re-identification by symmetry-driven accumulation of local features[END_REF], the authors proposed to combine three features: 1) chromatic content (HSV histogram); 2) maximally stable colour regions (MSCR) and 3) recurrent highly structured patches (RHSP). The extracted features were weighted by the distance with respect to the vertical axis to minimize effects of pose variations. Recurrent patches were also proposed in [START_REF] Bazzani | Multiple-shot person reidentification by hpe signature[END_REF]. Epitome analysis was used to extract highly informative patches form the set of images.

Overview

Based on our previously evaluated appearance-based people re-identification system in [START_REF] Bak | Multiple-shot human re-identification by mean riemannian covariance grid[END_REF], we here test our system in a 2 camera network associating people, head and face. The first task is to detect people using simplified LBP features in section 3. Tracked objects are extracted from a video using a temporal trajectory analysis algorithm (A. [START_REF] Avanzi | Tracking multiple individuals for video communication[END_REF] which are fed to the appearance based people re-identification system in section 4. We propose a simple face recognition algorithm in section 5. Re-identification results are given in section 6. A new database was created to simulate a 2 cameras network with non overlapping views. This database is referred to as the TSP database and contains 23 persons walking back and forth in both cameras as illustrated in figure 1. Two tracked persons with heads and faces are shown in camera 1 and 2 of the TSP camera setup in figure 2. The standard LBP operator extract feature vector of size 256 [START_REF] Trefny | Extended Set of Local Binary Patterns for Rapid Object Detection[END_REF]. We have implemented a new simplified version of the LBP operator

v c,w,h = E x ,y I(x , y ) (1) c =      1 : x = [x : x + h], y = [y : y + w] 2 : x = [x : x + h], y = [y + w : y + 2w] 3 : x = [x + h : x + 2h], y = [y : y + w] 4 : x = [x + h : x + 2h], y = [y + w : y + 2w]
The SLBP feature is then calculated from 4 mean pixel intensity differences ∆v q as follows:

SLBP w,h (x) = 3 ∑ q=0 s(∆v q )2 q , s(.) = 1 if . > V 0 else ∆v q = v i -v j (q, i, j) = {(0, 1, 0), (1, 3, 2), (2, 2, 0), (3, 3, 1)}
An Adaboost training scheme is adopted to train cell features across the a people image database. The training is performed on a multiple scale approach by varying the SLBP cell dimensions: 1,1)(1,2)..(1,8),(2,1) The traditional Adaboost technique is used to train SLBP features. We reach a frame rate of 1fps for a minimum size of 160 pixels for people height in PAL images and when the scan is performed with an increase rate of 10% of its actual scanning window width and height. Simple rules are applied to the detected candidates in order to fuse overlapping candidates and eliminate stand alone noisy candidates: objects are merged if they overlap each other with a minimum union-over-intersection ratio of 50% and a final object requires a minimum number of 2 overlapping ones.

(w, h) = {(

Human re-identification

Recently, the person re-identification problem became one of the most important tasks in video surveillance. There is a natural consequence of an invention of robust human detection algorithms to extend approaches for recognition purposes. Person reidentification can be considered on different levels depending on information cues which are currently available in the system. Biometrics such as face, iris or gait can be used to recognize identities. Nevertheless, in most video surveillance scenarios such detailed information is not available due to video lowresolution or difficult segmentation (crowded environments, e.g. airports, metro stations). Therefore a robust modelling of a global appearance of an individual is necessary to re-identify a given person of interest. In these identification techniques (named appearance-based approaches) clothing is the most reliable information about an identity of an individual (there is an assumption that individuals wear the same clothes between different sightings). The model of an appearance has to handle differences in illumination, pose and camera parameters to allow matching appearances of the same individual observed in different cameras.

In [START_REF] Bak | Multiple-shot human re-identification by mean riemannian covariance grid[END_REF], a highly discriminative human signature, called Mean Riemannian Covariance Grid (MRCG), is proposed. This human signature has been designed to deal with low resolutions images and crowded environments where more specialized techniques (e.g. based on body parts detectors) might fail. Here, dense descriptors philosophy [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) is combined with extremely effectiveness of the covariance descriptor. First, an image is divided into a dense grid structure with overlapping spatial square regions (cells). Such dense representation makes the signature robust to partial occlusions and it contains a relevant information about spatial correlations between cells. The authors [START_REF] Bak | Multiple-shot human re-identification by mean riemannian covariance grid[END_REF] take advantage of the tracking and detection results combining information from multiple images.

Let C p 1 , . . . ,C p N be a set of covariance matrices extracted during tracking of N frames corresponding to image square regions at position of the cell p. The MRC is defined as the mean covariance of these covariance matrices computed using Riemannian space (see Fig. 4). The mean covariance matrix as an intrinsic average blends appearance information from multiple images. This mean covariance matrix keeps not only information about features distribution but also carries out essential cues about temporal changes of the appearance related to the position of the cell p. All MRC cells compose a full grid, named as Mean Riemannian Covariance Grid (MRCG).

In our surveillance system, this appearance-based descriptor is used to match the same appearances between different camera views.

5 Face recognition

Face visual signature extraction

Similarly to [START_REF] Huang | High performance object detection by collaborative learning of joint ranking of granules features[END_REF] where people body parts are manually located before being independently trained, we manually choose 4 facial parts (p = [1 : 4]) to model a face i visual signature S (i) which are the left eye, right eye, nose and mouth:

S (i) = H (i) p ; p = [1 : 4] (2)
Each signature

H (i)
p is represented by a set of SLBP histograms h

(i) p,w,h ( f ): H (i) p = h (i) p,w,h ( f ) ; (w, h) = {(1, 1)..(1, 8)..(8, 8)} h (i) p,w,h ( f ) = ∑ x∈P p s (SLBP (i) w,h (x), f ) (3) s (a, b) = 1 if a = b 0 else (4)
where P p represent the set of pixels within the predefined facial part area. Each histogram h is normalised over the SLBP feature value f = [1 : 16].

Matching faces

Two faces i and j are matched if their signatures S (i) and S ( j) are similar enough or in other terms if a distance measure between the two signatures is below a threshold. This similarity distance D(i, j) is calculated by the mean similarity distance ∆H p (i, j) of the 4 facial part signatures H p defined in equation 2. Two facial parts similarity is calculated by a weighted mean of SLBP histogram differences as follows.

D(i, j) = E p (∆H p (i, j)) (5) ∆H p (i, j) = ∑ (w,h) α w,h E f h (i) p,w,h ( f ) -h ( j) p,w,h ( f ) 2 ∑ w,h α w,h
where cell weight α is inversely proportionally to the cell lateral distance.

Evaluation 6.1 People detection

We have evaluated our people detection algorithm on the test human dataset provided by INRIA against state of the art algorithms which we refer as HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and LBP-HOG [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF]. The INRIA human dataset is composed of 1132 human images and 453 images of background scenes containing no humans. The results are displayed in figure 5 which shows that we obtain slightly better performances than the HOG-LBP technique in terms of missed detection rate vs. FPPI i.e. False Positive Per Image. In this figure, two extreme functioning modes could be chosen: approximately 2 noisy detections are obtained every 1000 background images for 50% true positive detections or 1 noisy detection every 2 frames for a detection rate of approximately 88%.

Appearance based people re-identification

Using the TSP dataset described in section 2, three kind of people are noted:

• type A -people wearing the same clothes in recording sessions.

• type B -people slightly change their appearances from one recording session to the other. For example, someone unzipping his/her jacket or someone taking his/her scarf off as illustrated by the top images of figure 6.

• type C -people with great change of appearance such as a person adding a coat with a hat as illustrated by the bottom images of figure 6. We obtain 50 possible comparison of appearances that we evaluated in section 6.2.1 and 6.2.2. We can note that people detection and tracking results are noisy which makes the people re-identification task more challenging. In this scenario, we aim to re-identify people in a camera who were previously seen in this same camera. The tracked people appearance signatures are recorded in a database during the first session. During the second session, the appearance signatures of all the tracked people are compared with the database. We have plotted in figure 7 the appearance matching distance between the same person appearances for type A, B and C people (defined above). The results show that people type A and B are successfully retrieve with rank 1, except for 1 person with rank 2, when matching distances are below 2.1. Type C people (i.e. strong change of appearance) are not re-identify. However, a uncertainty zone exists for a matching distance between 1.75 and 2.1. In this section the evaluation of re-identification approach is presented in a 2 camera network. The performance is shown using the Cumulative Matching Characteristic (CMC) curve suggested in [START_REF] Gray | Evaluating Appearance Models for Recognition, Reacquisition, and Tracking[END_REF] as the validation method for the reidentification problem. The CMC curve represents the expectation of finding the correct match in the top matches. We evaluate the re-identification in the following way:

• Mono appearance mode -Frontal and back view of people tracked in camera 1 have their appearance signatures extracted separately.

• Multi appearance mode -Both frontal and back view of people tracked in camera 2 have their appearance signatures extracted.

Every signature from camera 1 is used as a query to the database (multiple-appearance signatures extracted from camera). The CMC curves for back and frontal view signatures are presented in Fig. 8. The results show that despite automatic inaccurate people detection and the different lighting conditions of the 2 cameras, the system shows promising people appearance based re-identification results. Table 1 shows the recognition rates comparison with 3 different techniques. Using an empirically set threshold (of 0.001), our system recognises only 85% of faces correctly whereas the DAISY technique [START_REF] Velardo | Face recognition with daisy descriptors[END_REF] recognises 98% of the faces correctly. Although our system is far from being the most performing system, it recognises 98% of the people when using a rank score of 1 and 100% for a rank of 3. In other terms, there is 98% chance that the face giving the closest distance D (in equation 5) is the correct face.

Face recognition

Using the TSP dataset, we obtained similar performances. Among the 23 persons present in the TSP database, only 11 people faced long enough camera 1 for a valid trajectory to be obtained: face images of less than 50x50 pixels were not taken into account (due to motion noise and image quality artefacts) and face tracks containing less than 5 face images were discarded.

In table 1, TSP1 and TSP2 refers to the same camera (camera 1 and camera 2 respectively) recognition scenario where half of a person face images is saved in the database and the other half as the request information. The results show that this simple SLPB face recognition technique is useful enough for such a database.

Conclusion

We have presented a multi-cue people reidentification framework.

A novel simplified LBP feature is proposed to detect people, head and faces using the Adaboost training scheme. We obtain state of the art performance for people detection. We have also extended our approach on appearance based matching method to multi appearance based people re-identification. The proposed system tracks people and their faces allowing the user to associate an appearance with a face. In most networks, cameras cannot provide the full people appearance view (e.g. strong occlusion) and faces are often not visible or only partly visible. Our proposed approach would allow a user to scan throughout a network of surveillance cameras the best matching candidates and to be able to track people of interest throughout this network.

Figure 1 :

 1 Figure 1: TSP camera setup: 2 non overlapping cameras in 2 joint corridors

Figure 2 :

 2 Figure 2: Tracked people, head and faces in up: TSP camera 1 and down: TSP camera 2

  ..(8, 8)} We apply the same training algorithm on head and face image datasets for head and face detection. The training for people detection is done using 7K positive images (5K from NICTA, 1K from MIT and 1K from INRIA people training dataset) and 50 background negative PAL images. Head were trained with 1K positive images (cropped head images from INRIA and TUD people training dataset) and 10 background negative images. Faces were trained with the standard CMU face training database.

Figure 3 :

 3 Figure 3: Simplified LBP operator.

Figure 4 :

 4 Figure 4: Covariances gathered from tracking results are used to compute the MRC using Riemannian manifold space (depicted with the surface of the sphere).

Figure 5 :

 5 Figure 5: People detection evaluation: False Positive Per Image vs. miss detection rate for the INRIA test database

Figure 6 :

 6 Figure 6: Top row: type B -people appearances are successfully re-identified despite their weak change of clothing. Bottom row: type C -people appearances are too distant to be re-identified

Figure 7 :

 7 Figure 7: Evaluation of appearance matching distance in the same camera scenario

Figure 8 :

 8 Figure 8: CMC curves obtained on TSP datasets.

  in two: 5 images are used as our face database collected from one camera and the remaining 5 images are used as a request from camera 2. The images are challenging as they contain faces of different kind of poses and facial expressions.

Table 1 :

 1 Face recognition rates

	The Olivetti Research Lab i.e. ORL database is
	used to evaluate our simple face recognition algo-
	rithm using SLBP features. 40 persons constitute this
	database with 10 pictures for each subject. All face
	pictures are taken by the same camera. Most state of
	the art algorithm compare face recognition rate using
	one picture at a time. In our scenario, we obtain tracks
	of faces for each person which we aim to compare. To
	simulate our 2 cameras system, we split the database

Acknowledgements

We would like to thank the ANR project 'VideoId' who partially founded this work and the following partners of the project: Biometrics Groups at TELE-COM SudParis, Multimedia Image processing Group of Eurecom and T3S (Thales Security Systems and Solutions S.A.S.).