Paul Bédaride

Augustin Degomme

Stéphane Genaud

Arnaud Legrand

George S Markomanolis

Martin Quinson

Mark Stillwell

Frédéric Suter

Brice Videau

Improving Simulations of MPI Applications Using A Hybrid Network Model with Topology and Contention Support

Keywords: Simulation, MPI, Performance Analysis, Collective Communications, Contention Simulation, MPI, analyse de performances, communications collectives, contention

Proper modeling of collective communications is essential for understanding the behavior of medium-to-large scale parallel applications, and even minor deviations in implementation can adversely aect the prediction of real-world performance. We propose a hybrid network model extending LogP based approaches to account for topology and contention in high-speed TCP networks. This model is validated within SMPI, an MPI implementation provided by the SimGrid simulation toolkit. With SMPI, standard MPI applications can be compiled and run in a simulated network environment, and traces can be captured without incurring errors from tracing overheads or poor clock synchronization as in physical experiments. SMPI provides features for simulating applications that require large amounts of time or resources, including selective execution, ram folding, and o-line replay of execution traces. We validate our model by comparing traces produced by SMPI with those from other simulation platforms, as well as real world environments.

Introduction

Correctly modeling collective communications, including their low-level breakdown into individual point-to-point messages and how these messages interact and interfere with one another within the network environment, is essential for understanding the higher-level behavior of medium and large scale parallel applications. In this work we demonstrate how even relatively minor deviations in low-level implementation can adversely aect the ability of simulations to predict real-world performance, and propose a new network model that extends previous LogP based approaches to better account for topology and contention in high-speed TCP networks. This is part of a larger eort to study distributed computing platforms as natural objects, recognizing that the remarkable complexity of such systems makes it increasingly dicult to make useful claims from a purely theoretical viewpoint. Indeed, the computation and communication behavior of many, if not most, existing scientic codes is understood at only the most basic level, even by the application programmers. We propose to study these systems through simulation based on empirically validated models, thus turning the tools and techniques aorded by advanced computational resources back on those resources themselves. This approach is further justied by the recent recognition of computational science and simulation as an essential third pillar of scientic methodology, on par with and distinct from experimentation and theory. Well thought out simulations can provide results that are more easily understood and analyzed than a physical experiment at signicantly lower costs. Further, because of the diculty in ensuring the precise conguration of the experimental environment, in some elds the results from simulation are regarded as more accurate and informative than those from physical experiments; A notable example of this can be seen in the eld of uid mechanics, where the overall importance of micro-bubbles in reducing drag coecients for moving objects (such as ships) had been long understood, but diculties in observational methods made it impossible to make signicant advances prior to the advent of techniques for simulation [START_REF] Xu | Numerical simulation of turbulent drag reduction using micro-bubbles[END_REF].

The real-world environment for distributed systems is plagued with similar problems, in that proper instrumentation and monitoring is extremely dicult and may alter the system behavior.

Real-world networks are also subject to transient or periodic faults caused by unknown and hard-to-detect hardware problems that can invalidate the applicability of results outside of the testing facility. Another advantage of simulation is that it makes it easier for independent third parties to analyze experiments and reproduce results, thus forwarding the cause of open science.

In this context, network modeling is a critical point. Tools that address such concerns tend to rely either on accurate packet-level simulations or on simple analytical models. Packet-level simulation has high overheads, resulting in simulations that may take signicantly longer to run than the corresponding physical experiments. Additionally, while packet-level simulation has long been considered the gold standard for modeling the behavior of network communications, this assumption has not been rigorously validated and it may be the case large disparities exist between predicted and actual behavior. Recent work suggests that well-tuned ow-based simulation may be able to provide more accurate results at lower costs [START_REF] Velho | Flow-level network models: have we reached the limits?[END_REF]. The problem with analytic approaches is that many simulators implement communications from the ground up, using simplied models that ignore phenomena such as network topology and contention or even how the collective communications are actually implemented. While these inaccuracies have been long-acknowledged within the eld, until recently there were few alternatives, and much work has been done with the intuition that while these simplifying assumptions might make it dicult to predict exact performance on a particular platform, overall application behavior would remain basically unchanged. Our own experiments have shown that this is simply not the case.

We seek to improve the accuracy of simulations of medium-to-large scale parallel distributed applications, while capturing the advantages of a ow-based approach by extending existing RR n°8300 validated models of point-to-point communication to better account for network topology and message contention. The proposed model is validated within SMPI, an implementation of the Message Passing Interface (MPI) that interfaces directly with the SimGrid simulation toolkit [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF].

With SMPI, standard MPI applications written in C or Fortran can be compiled and run in a simulated network environment, and traces documenting computation and communication events can be captured without incurring errors from tracing overheads or improper synchronization of clocks as in physical experiments. SMPI also provides a number of useful features for predicting the behavior of applications that may require large amounts of time or system resources to run, including selective execution, ram folding, and o-line simulation by replay of execution traces.

We validate our results by comparing application traces produced by SMPI using our network model with those from real world environments. Further details regarding SMPI, including comparisons with other simulation platforms are given in Section3.

In this article, we explain our eorts in proposing more realistic network models than what was proposed in other tools and how it improves upon their ability to derive more meaningful results.

We justify our results by comparing traces produced by SMPI with those from other simulation platforms, as well as traces gathered from physical experiments on real-world platforms.

More specically, our contributions are:

We propose a new ow-based network model that extends previous LogP-based approaches to better account for network topology and message contention.

We describe this model in detail and make comparisons to other models proposed within the literature.

We describe SMPI, the simulation platform, and some useful extensions that we have developed to make this tool more useful to developers and researchers alike.

We provide a number of experimental results demonstrating how these extensions improve the ability of SMPI to accurately model the behavior of real-world applications on existing platforms, and also provide comparisons with competing simulation frameworks.

We demonstrate the eectiveness on our proposal by making a thorough study of the validity of our models against hierarchical clusters using Gigabit Ethernet with TCP as it is known to be much more dicult than high-end HPC networks that are more regular. This paper is organized as follows: In Section2 we discuss related work, particularly in the area of network modeling. In Section3 we describe SMPI, our chosen implementation, along with some key features that make it suitable for simulation of large scale systems, and comparisons to competing simulation platforms. In Section4 we describe our proposed hybrid network model, focusing particularly how this model captures the complexities of network topology and message contention. In Section5 we describe experiments conducted to validate the model, including comparisons of traces produced using other approaches as well as from real-world environments.

In Section6 we demonstrate the capacity of SMPI to simulate complex MPI applications on a single machine. We conclude in Section7 and also provide a description of proposed areas of future work.

Related Work

In the High Performance Computing (HPC) eld, accurately predicting the execution time of parallel applications is of uttermost importance to assess their scalability. While much eort has been put towards understanding the high-level behavior of these applications based on abstract communication primitives, real-world implementations often provide a number of confounding

Inria

Pr

Ps

T1

T2 T3

(a) Asynchronous mode (k ≤ S).

Routine Condition Cost

MPI_Send

k ≤ S T 1 k > S T 4 + T 5 + T 1 MPI_Recv k ≤ S max(T 1 + T 2 -(t r -t s ), 0) + T 3 k > S max(o + L -(t r -t s ), 0) + o+ T 5 + T 1 + T 2 + T 3 MPI_Isend o MPI_Irecv o (c) MPI routine costs. T 1 = o+kO s T 2 = L + kg if k < s L + sg + (k -s)G otherwise T 3 = o+kO r T 4 = max(L+o, t r -t s )+o T 5 = 2o + L Figure 1:
The LogGPS model [START_REF] Ino | LogGPS: a Parallel Computational Model for Synchronization Analysis[END_REF] in a nutshell.

factors that may break basic assumptions and undermine the applicability of these higher level models. For example, implementations of the MPI standard can select dierent protocols and transmission mechanisms (e.g., eager vs. rendez-vous) depending on message size and network capabilities. Such optimizations generally result in complex heterogeneous performance. Also, HPC platforms usually rely on a complex network interconnection topology, including switch hierarchies or mesh-based arrangements where connections between nodes map onto abstract Ndimensional gures such as toruses or hypercubes. Packet-level network simulations are usually implemented as discrete-event simulations with events for packet emission or reception as well as network protocol events. Such simulations reproduce the real-world communication behavior down to movements of individual packets, which will contain both user data and control information, such as ow-control digits, or its. Some tools following this approach, e.g., NS2, NS3, or OMNet++, have been widely used to design network protocols or understand the consequences of protocol modications [START_REF] Minkenberg | Trace-Driven Co-Simulation of High-Performance Computing Systems Using OMNeT++[END_REF]. However, such ne-grain network models are dicult to instantiate with realistic parameter values RR n°8300

for large-scale networks and generally suer from scalability issues. While parallel discreteevent simulation techniques [START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF][START_REF] Mubarak | Modeling a million-node dragony network using massively parallel discrete-event simulation[END_REF] may speed up such simulations, the possible improvements remain quite limited as the underlying systems are usually not well separable. That is, datainterdependencies necessitate the use of shared data structures, which cut down on the eciency of parallel simulation.

When packet-level simulation becomes too costly or intractable, the most common approach is to resort to simpler delay models that ignore the network complexity. Among these models, the most famous are those of the LogP family [START_REF] Culler | LogP: Towards a Realistic Model of Parallel Computation[END_REF][START_REF] Alexandrov | LogGP: Incorporating Long Messages Into the LogP Model One Step Closer Towards a Realistic Model for Parallel Computation[END_REF][START_REF] Kielmann | Fast Measurement of LogP Parameters for Message Passing Platforms[END_REF][START_REF] Ino | LogGPS: a Parallel Computational Model for Synchronization Analysis[END_REF]]. The LogP model was originally proposed by Culler et al. [START_REF] Culler | LogP: Towards a Realistic Model of Parallel Computation[END_REF] as a realistic model of parallel machines for algorithm design. It was claimed as more realistic than more abstract models such as PRAM or BSP. This model captures key characteristics of real communication platforms while remaining amenable to complexity analysis.

In the LogP model, a parallel machine is abstracted with four parameters: L is an upper bound on the latency of the network, i.e., the maximum delay incurred when communicating a word between two machines; o denotes the CPU overhead, i.e., the time that a processor spends processing an emission or a reception and during which it cannot perform any other operation;

g is the gap between messages, whose reciprocal is the processor communication bandwidth for short messages; and P represents the number of processors. Assuming that two processors are ready to communicate, the time to transfer a message of size k is then o+(k -1) max(g, o)+L+o.

Ideally, these four parameters should be sucient to design ecient algorithms. Indeed, this model accounts for computation/communication overlap since for short messages, as the sender is generally released before the message is actually received on the receiver side. While this model somehow reects the way specialized HPC networks used to work in the early 90s, it ignores many important aspects.

The LogGP model proposed in [START_REF] Alexandrov | LogGP: Incorporating Long Messages Into the LogP Model One Step Closer Towards a Realistic Model for Parallel Computation[END_REF] introduces an additional parameter G to represent the eective bandwidth for long messages, which is generally larger than that for short messages.

The communication time for short messages is unchanged but is equal to o + (k -1)G + L + o for long ones. This simple distinction between short and long messages was extended in [START_REF] Kielmann | Fast Measurement of LogP Parameters for Message Passing Platforms[END_REF] with the parameterized LogP model in which L, o, and g depend on the message size. The rationale is that the overall network performance results from complex interactions between the middleware, the operating system, the transport layer, and the network layer. Hence, performance is generally neither strictly linear nor continuous. This model also introduces a distinction between the sender overhead o s and the receiver overhead o r . While such models may account for most of the idiosyncrasies of a parallel machine, they become quite dicult to use to design algorithms. For instance, they assume that senders and receivers synchronize and include that synchronization cost in the overhead. However, some MPI implementations use schemes that may not require synchronization, depending on message size.

Finally, Ino et al. proposed in [START_REF] Ino | LogGPS: a Parallel Computational Model for Synchronization Analysis[END_REF] the LogGPS model that extends LogGP by adding two parameters s and S to capture the lack of linearity and the existence of a synchronization threshold. Overheads are represented as ane functions o + kO s where O s (resp. O r ) is the overhead per byte at the sender (resp. receiver) side. This model is described in Figure1, where t s (resp. t r ) is the time at which MPI_Send (resp. MPI_Recv) is issued. When the message size k is smaller than S, messages are sent asynchronously (Figure1(a)). Otherwise, a rendezvous protocol is used and the sender is blocked at least until the receiver is ready to receive the message (Figure1(b)). Regarding message transmission time, the s parameter is used to distinguish small messages from large messages and is thus continuously piece-wise linear in message size (Figure1(c)).

To summarize, the main characteristics of these models derived from the seminal LogP model are: the expression of overhead and transmission times as continuous piece-wise linear functions of message size; accounting for partial asynchrony for small messages, i.e., sender and Inria receiver are busy only during the overhead cycle and can overlap communications with computations the rest of the time; a single-port model, i.e., a sequential use of the network card which implies that a processor can only be involved in at most one communication at a time; and no topology support, i.e., contention on the core of the network is ignored as all processors are assumed to be connected through independent bidirectional communication channels. Most of these hypothesis are debatable for many modern computing infrastructures. For example, with multi-core machines, many MPI processes can mapped to the same node. Furthermore, the increase in the number of processors no longer allows one to assume uniform network communications. Finally, protocol switching typically induces performance modications on CPU usage similar to those on eective bandwidth, while only the latter are captured by these models.

An alternative to expensive packet-level models and simplistic delay models is ow-level models. These models account for network heterogeneity and have thus been used in simulations of grid, peer-to-peer, and cloud computing systems. Communications, represented by ows, are simulated as single entities rather than as sets of individual packets. The time to transfer a message of size S between processors i and j is then given by T i,j (S) = L i,j + S/B i,j , where L i,j (resp. B i,j ) is the end-to-end network latency (resp. bandwidth) on the route connecting i and j. Estimating the bandwidth B i,j is dicult as it depends on interactions with every other ow. It generally amounts to solving a bandwidth sharing problem, i.e., determining how much bandwidth is allocated to each ow. While such models are rather exible and account for many non-trivial phenomena (e.g., RTT-unfairness of TCP or cross-trac interferences) [START_REF] Velho | Flow-level network models: have we reached the limits?[END_REF],

they still ignore protocol oscillations, slow start, and more generally all transient phases between two steady-state operation points. Some specic examples of unrepresented phenomena that can have major impacts on performance include saturation of the network to the point congestion would cause packet loss, and massive reemissions conditioned by timeout events.

These models have not been used extensively in the HPC eld so far for at least two reasons.

First, until a few years ago contention could be neglected for high-end machines. Second, such models are quite complex to implement and are often considered as too slow and complex to scale to large platforms. As we demonstrate, neither of these assumptions remains true today, and ow-based approaches can lead to signicant improvements over classical LogP models.

While the aforementioned approaches model point-to-point communications, the modeling of collective communications is another critical point when studying MPI applications. Some projects model them with simple analytic formulas [START_REF] Badia | Dimemas: Predicting MPI Applications Behaviour in Grid Environments[END_REF][START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF]. This allows for quick estimations and may provide a reasonable approximation for simple and regular collective operations, but is unlikely to accurately model the complex optimized versions that can be found in most MPI

implementations. An orthogonal approach is to thoroughly benchmark collective operations to measure the distribution of communication times with regard to the message size and number of concurrent ows. Then, these distributions are used to model the interconnection network as a black box [START_REF] Grove | Communication benchmarking and performance modelling of mpi programs on cluster computers[END_REF]. This approach has several drawbacks. First, it does not accurately model communication/computation overlap. Second, it cannot take the independence of some concurrent communications into account. Finally, it does not allow for performance extrapolation on a larger machine with similar characteristics. A third approach consists in tracing the execution of collective operations and then replaying the obtained trace using one of the aforementioned delay models [START_REF] Hoeer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF][START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF]. However, current implementations of the MPI standard dynamically select from up to a dozen dierent communication algorithms when executing a collective operation.

Thus, using the right algorithm becomes critical when trying to predict performance.

Studying the behavior of complex HPC applications or operations and characterizing HPC platforms through simulation has been at the heart of many research projects and tools for decades. Such tools dier by their capabilities, their structure, and by the network models they implement. BigSIM [START_REF] Zheng | BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines[END_REF], LAPSE [START_REF] Dickens | Parallelized Direct Execution Simulation of Message-Passing Parallel Programs[END_REF], MPI-SIM [START_REF] Bagrodia | Parallel Simulation of Large-Scale Parallel Applications[END_REF], or the work in [START_REF] Riesen | A Hybrid MPI Simulator[END_REF] rely on simple delay models RR n°8300

(ane point-to-point communication delay based on link latency and bandwidth). Other tools, such as Dimemas [START_REF] Badia | Dimemas: Predicting MPI Applications Behaviour in Grid Environments[END_REF], LogGOPSim [START_REF] Hoeer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], or PHANTOM [START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF] use variants of the LogP model to simulate communications. Note that BigSIM also oers an alternate simulation mode based on a complex and slow packet-level simulator. This approach is also followed by MPI-NeTSim [START_REF] Peno | MPI-NeTSim: A network simulation module for MPI[END_REF] that relies on OMNeT++. Finally PSINS [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF] and PEVPM [START_REF] Grove | Communication benchmarking and performance modelling of mpi programs on cluster computers[END_REF] provide complex custom models derived from intensive benchmarking to model network contention.

3 The SMPI Framework

The goal of our research is to use modeling and simulation to better understand the behavior of real-world large-scale parallel applications, which informs the choice of an appropriate simulation platform. That is, simulations for studying the ne-grain properties of network protocols may have little in common with simulations for studying the scalability of some large-scale parallel computing application. Likewise, models used in algorithm design are expected to be much simpler than those used for performance evaluation purposes. Our choice of SMPI as an implementation environment reects this goal, as SMPI allows for relatively easy conversion of real-world applications to simulation, and provides a number of useful features for enabling largescale simulations. SMPI implements about 80% of the MPI 2.0 standard, including most of the network communication related functions, and interfaces directly with the SimGrid simulation tool kit. In this section we describe SMPI in greater detail, focusing rst on its general approach and then later highlighting some of these features.

Full simulation of a distributed application, including CPU and network emulation, carries with it high overheads, and for many cases it can be a more resource intensive approach than direct experimentation. This, coupled with the fact that a major goal in many simulations is to study the behavior of large-scale applications on systems that may not be available to researchers, means that there is considerable interest in more ecient approaches. The two most widely applied of these are o-line simulation and partial on-line simulation, both of which are available through SMPI.

In o-line simulation or post-mortem analysis the application to be studied is rst modied to add monitoring and instrumentation code if necessary, and is run in a real-world environment.

Data about the program execution, including periods of computation, the start and end of any communication events, and possibly additional information such as the memory footprint at various points in time, is logged to a trace le. For distributed applications that run in parallel across multiple computational resources, it may be necessary to combine individual traces into a single unied trace le, in which case it is very important to make sure that any clock skew is properly accounted for so that the traces are correctly synchronized and the true order of events is preserved. These traces can then be replayed in a simulated environment, considering dierent what-if ? scenarios such as a faster or slower network, or more or less powerful processors on some nodes. This replay is usually much faster than direct execution, as the computation and communications are not actually executed but abstracted as trace events. A number of tools [START_REF] Hoeer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF][START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF][START_REF] Núñez | New Techniques for Simulating High Performance MPI Applications on Large Storage Networks[END_REF][START_REF] Zhai | PHANTOM: Predicting Performance of Parallel Applications on Large-Scale Parallel Machines Using a Single Node[END_REF][START_REF] Hermanns | Verifying Causality between Distant Performance Phenomena in Large-Scale MPI Applications[END_REF] support the o-line approach.

O-line simulation carries with it a number of caveats: It assumes that programs are essentially deterministic, and each node will execute the same sequence of computation and communication events regardless of the order in which messages are received. A bigger challenge is that it is extremely dicult to predict the result of changing the number of nodeswhile there is considerable interest and research in this area [START_REF] Ernemann | Scaling of workload traces[END_REF][START_REF] Hoeer | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], the diculty of predicting the execution prole of programs in general, and the fact that both applications and MPI implementations are likely to vary their behavior based on problem and message size, suggests that reliably guaranteeing Inria results that are accurate within any reasonable bound may be impossible. Another problem with this approach is that instrumentation of the program can add delays, particularly if the program carries out large numbers of ne-grained network communications, and if this is not carefully accounted for then the captured trace may not be representative of the program in its natural state.

By contrast, the partial on-line approach relies on the execution of the program within a carefully-controlled real-world environment: computational sections are executed in full speed on the available hardware, but timing and delivery of messages are determined by the simulation environment (in the case of SMPI this is provided by SimGrid). This approach is much faster than full emulation (although slower than trace replay), yet preserves the proper ordering of computation and communication events. This is the standard approach for SMPI, and a number of other simulation toolkits and environments also provide this facility [START_REF] Peno | MPI-NeTSim: A network simulation module for MPI[END_REF][START_REF] Dickens | Parallelized Direct Execution Simulation of Message-Passing Parallel Programs[END_REF][START_REF] Bagrodia | Parallel Simulation of Large-Scale Parallel Applications[END_REF][START_REF] Riesen | A Hybrid MPI Simulator[END_REF].

In a previous work [START_REF] Bobelin | Scalable Multi-Purpose Network Representation for Large Scale Distributed System Simu-RR n°8300 lation[END_REF] we showed that this partial online approach (coupled to a precise model of the platform) is only slightly slower than LogGoPSim, a performance-oriented o-line simulator that disregards contention eects and only models the network latency. To support simulations at very large scale, SMPI provides a method of trading o accuracy for performance by benchmarking the execution of the program on some nodes, while skipping it on others and inserting a computation time in the simulated system clock based on the benchmarked value.

This corrupts the solution produced by the application, but for data independent applications (those not containing large numbers of branching statements within the parallel code) is likely to result in a reasonably accurate execution prole. A related technique, also provided by SMPI, is memory folding, whereby multiple simulated processes can share a single copy of the same malloc'd data structure. Again, this can corrupt results and potentially result in inconsistent or illegal data values, but allows larger scale simulations than what would be possible otherwise, and may be reasonable for a large class of parallel applications, particularly in engineering or the sciences. These features are disabled by default, and have to be enabled by an expert user by adding macros and annotations to the application source code. Potential areas for future work include improving this process so that it can be semi-automated, and building more sophisticated models based on benchmarked values.

A Hybrid Network Model

In this section, we report the issues that we encountered when comparing the predictions given by existing models to real measurement on a commodity cluster with a hierarchical Ethernet-based interconnection network. avoid any measurement bias, the message size is exponentially sampled from 1 byte to 100MiB.

We ran two ping and one ping-pong experiments. The ping experiments aim at measuring the time spent in the MPI_Send (resp. MPI_Recv) function by ensuring that the receiver (resp.

sender) is always ready to communicate. The ping-pong experiment allows us to measure the transmission delay. We ran our analysis on the whole set of raw measurements rather than on averaged values for each message size to prevent behavior smoothing and variability information loss. The rationale is to study the asynchronous part of MPI (from the application point of view) without any a priori assumptions of where switching may occur. This approach allows us to clearly identify dierent modes interpreted as follows:

Small (when k ≤ 1, 420): this mode corresponds to messages that t in a TCP packet and are sent asynchronously by the kernel. As it induces memory copies, the duration signicantly depends on the message size.

Medium (when 1, 420 < k ≤ 10, 000 or 10, 000 < k ≤ 65, 536 = S a ): these messages are still sent asynchronously but incur a slight overhead compared to small messages, hence a discontinuity at k = 1420. The distinction at k = 10, 000 does not really correspond to any particular threshold on the sender side but is visible on the receiver side where a small gap is noticed. Accounting for it is harmless and allows for a better linear tting accounting for MPI/TCP peculiarities.

Detached (when 65, 536 < k ≤ 327, 680 = S d ): this mode corresponds to messages that do not block the sender but require the receiver to post the reception before the communication actually takes place.

Large (when k > 327, 680): for such messages, both sender and receiver synchronize using a rendez-vous protocol before sending data. Except for the waiting time, the durations on the sender side and on the receiver side are very close.

As illustrated by Figure2, the duration of each mode can be accurately modeled through linear regression. These observations justify the model implemented in SMPI that is described in Figure3. We distinguish three modes of operation: asynchronous, detached, and synchronous. While distinguishing these modes may be of little importance when simulating applications that only send particular message sizes, obtaining good predictions in a wide range of settings, and without conducting custom tuning for every simulated application, requires accurately accounting for all such peculiarities. This will be exemplied in Section5.

Inria

P s P r T 2 T 4 T 1 (b) SMPI Detached mode (Sa < k ≤ S d ) P s P r T 4 T 2 (c) SMPI Synchronous mode (k > S d ) Routine Condition Cost MPI_Send k ≤ S T 1 k > S max(T 4 , 0) + T 2 MPI_Recv k ≤ S min(t s + T 2 -t r , 0) + T 3 k > S max(-T 4 , 0) + T 2 If k ∈ I i : T 1 = o (i) s +kO (i) s T 2 = L (i) +k/B (i) T 3 = o (i) r +kO (i) r T 4 = t r -t s (d) SMPI communication costs

Topology and contention model

For most network models, dealing with contention comes down to assuming one of the simple single-port or multi-port models. In the single-port model each node can communicate with only one other node at a time, while in the multi-port model, each node can communicate with every other node simultaneously without any slowdown. Both models oversimplify the reality.

Some ow-level models follow a bounded multi-port approach, i.e., the communication capacity of a node is limited by the network bandwidth it can exploit, that better reects the behavior of communications on wide area networks. However, within a cluster or cluster-like environment the mutual interactions between send and receive operations cannot safely be ignored.

To quantify the impact of network contention of a point-to-point communication between two processors in a same cabinet, we articially create contention and measure the bandwidth as perceived by the sender and the receiver. We place ourselves in the large message mode where the highest bandwidth usage is observed and transfer 4 MiB messages.

In a rst experiment we increase the number of concurrent pings from 1 to 19, i.e., half the size of the cabinet. As the network switch is well dimensioned, this experiment fails to create contention: We observe no bandwidth degradation on either the sender side or the receiver side.

Our second experiment uses concurrent MPI_Sendrecv transfers instead of pings. We increase the number of concurrent transfers from 1 to 19 and measure the bandwidth on the sender (B s ) and receiver (B r ) side. A single-port model, as assumed by LogP models, would suppose that B s + B r = B on average since both directions strictly alternate. A multi-port model, as assumed by delay models, would estimate that B s + B r = 2 × B since communications do not interfere with each other. However, both fail to model what actually happens, as we observe that B s + B r ≈ 1.5 × B on this cluster.

We model this bandwidth sharing eect by enriching the simulated cluster description. Each processor is provided with three links: an uplink and a downlink, so that send and receive operations share the available bandwidth separately in each direction; and a specic link, whose bandwidth is 1.5 × B, shared by all the ows to and from this processor.

Preliminary experiments on other clusters show that this contention parameter seems constant for a given platform, with a value somewhere between 1 and 2. Determining this parameter requires benchmarking each cluster as described in this section. Our set of experiments is available on the previously indicated web page. We are currently working on a more generic benchmarking solution that one could easily use to determine the exact contention factor for any cluster.

This modication is not enough to model contention at the level of the whole graphene cluster. As described in [12], it is composed of four cabinets interconnected through 10Gb links.

Experiments show that these links become limiting when shared between several concurrent pairwise communications between cabinets. This eect is captured by describing the interconnection of two cabinets as three distinct links (uplink, downlink, and limiting link). The bandwidth of this third link is set to 13 Gb as measured.

This topology model could certainly be further rened. One intuitive lead is to consider the bandwidth limitation due to the switch backplane that may be reached during a full cluster bipartite communication. But such a renement seems to be pointless as the experiments presented in Section5 tend to show that this limit is never reached, or is at least hidden by other inaccuracy sources, such as packet dropping.

Collective communications model

Many MPI applications spend a signicant amount of time in collective communication operations. They are thus crucial to application performance. Several algorithms exist for each collective operation, each of them exhibiting very dierent performance depending on various parameters such as the network topology, the message size, and the number of communicating processes [START_REF] Faraj | STAR-MPI: self tuned adaptive routines for MPI collective operations[END_REF]. A given algorithm can commonly be almost an order of magnitude faster than another in a given setting and yet slower than this same algorithm in another setting. Every widely-used MPI implementation thus provides several algorithms for each collective operation and carefully selects the best one at runtime. For instance, OpenMPI provides a dozen distinct algorithms for the MPI_Alltoall function, and the code to select the right algorithm for a given setting is several thousand lines long.

Simulation of the most commonly used algorithms for collective communications is not very dicult as most are rather simple (in concept if not necessarily in detail). However, capturing the selection logic of the various MPI implementations is much more complex. This logic is highly dependent on the implementation and generally embedded deep within the source code.

Inria SMPI implements most of the collective algorithms by reusing the relevant source code of Star MPI [START_REF] Faraj | STAR-MPI: self tuned adaptive routines for MPI collective operations[END_REF]. It also provides a simple algorithm selector that mimics the behavior of OpenMPI in most cases. It was devised using both code inspection and execution trace comparisons.

While sucient in most cases, it leaves room for further improvements. In future work, we hope to provide additional selection algorithms, ideally one for each available MPI implementation.

Then, we will provide a generic way to specify the selection algorithm to use, enabling the tuning of collective algorithms within SMPI. Finally, we would like to provide a semi-automatic benchmarking solution to discover the selection algorithm used in a given MPI implementation by extensive testing.

Model [In]Validation Study

Setup Description

All the experiments presented hereafter have been done on the graphene cluster that was described in the previous section. The studied MPI applications were compiled and linked using OpenMPI 1.6. For comparison with simulated executions purposes, we instrumented these applications with TAU [START_REF] Shende | The Tau Parallel Performance System[END_REF]. The simulated executions have been performed either o-line or on-line as SMPI supports both modes. The le describing the simulated version of the graphene cluster was instantiated with values obtained independently from the studied applications. We used the techniques detailed in the previous section to obtain these values. In what follows we compare execution times measured on the graphene cluster to simulated times obtained with the hybrid model proposed in Section4, the LogGPS model that supersedes all the delay-based models, and a uid model that is a basic linear ow-level model.

We did not limit our study to overall execution times as they may hide compensation eects, and do not provide any information as to whether an application is compute or communication bound or how dierent phases may or may not overlap. Our experimental study makes use of Gantt charts to compare traces visually as well as quantitatively. We rely on CSV les, R, and org mode to describe the complete workow going from raw data the graphs presented in this paper, ensuring full reproducibility of our analysis.

Collective Communications

We begin our validation process with the study of an isolated MPI collective operation. We focus on the MPI_Alltoall function call that, as its name says, sends data from all to all processors. We selected this function as it is the most likely to be impacted by network contention. Here we aim at assessing the validity of contention modeling as the message size varies rather than the impact of using dierent collective operations. Toward this end, we enforce the use a single algorithm, i.e., the ring algorithm, for all message sizes. We ran the experiment ve times and only kept the best execution time for each message size. Indeed, we noticed that rst communication is always signicantly slower than those that follow, which tends to indicate that TCP require some warm-up time. This phenomenon has also been noticed in experiments assessing the validity of the BigSIM simulation toolkit. The same workaround was applied.

Figure4 shows the evolution of simulated and actual execution times for the MPI_Alltoall operation when the number of MPI processes varies for the three contention models. Results are presented for two message sizes: medium messages of 100 kiB and large messages of 4 MiB. We can see that for large messages, the hybrid and uid models both achieve excellent predictions.

In opposition to LogGPS, these two models account for network topology and contention, even when transferring data across cabinets (for 64 and 128 processes). Unsurprisingly, the LogGPS RR n°8300 q q q q q q q q q q q q 0.01 0.10 1.00 10.00 q q q q q q q q q q q q q q q q q q q q q q q DT LU CG model is overly optimistic in such setting and completely underestimates the overall execution time. Its prediction error can be up to a factor of 4 when 128 processors are involved in the All-to-All operation. For medium messages, the hybrid model is again the best contender, with a prediction error under 5% for up to 64 nodes, while the LogGPS model is again too optimistic. For such a message size, the lack of latency and bandwidth correction factors in the uid model leads to a clear underestimation of the execution time. Interestingly, when 128 processes are involved in the collective communication, the actual execution time increases dramatically while simulated times continue to follow the same trend. The reason for such a large increase can be explained by packet dropping in the main switch that leads to timeouts and re-emissions, hence incurring signicant delays. For larger messages, TCP seems to be more stable, and if packet are dropped it has little inuence on the larger total execution time.

Inria

NAS Parallel Benchmarks

The NAS Parallel Benchmarks (NPB) are a suite of programs commonly used to assess the performance of parallel platforms. From this benchmark suite, we selected three applications with dierent characteristics. The DT (Data Trac) benchmark is a communication intensive application. In its Black Hole variant, DT consists in sending large messages of several MiB of data from multiple sources towards a single sink. DT implies many long lasting communications, but its scheme tends to prevent contention. For DT the class refers not only to the size of the problem but also to the number of communicating processes: classes A, B, and C involve 21, 43, and 85 processes respectively. The LU benchmark is an iterative computation of a LU factorization. At each iteration, it exhibits a communication scheme that forms a wave going from the rst process to the last one and back. This pattern is very sensitive to noise as each process has to wait for the reception of a message before sending its own data. The third studied benchmark is CG (Conjugate Gradient). It has a complex communication scheme that is composed of a large number of point-to-point transfers of small messages. Moreover, processors are organized in a hierarchy of groups. At each level communications occur within a group and then between groups. This benchmark is then very sensitive to the mapping of the MPI processes on to the physical processors with regard network organization, particularly in non-homogeneous topologies. For this series of experiments, we use the o-line simulation capacities of SMPI, i.e., execution traces of the benchmark are rst acquired from a real system and then replayed in a simulated context.

Figure5 shows the comparison of the actual execution times measured on the graphene cluster for various instances of the three NPB benchmarks with the simulated times obtained with the studied models.

For the DT benchmark, which is composed of a few well distributed communications of large messages, the three models lead to comparable results and give good estimations of the actual execution times. These results conrm the observations made for the All-to-All collective operations. To some extent the DT benchmark corresponds to a reduction. The LogGPS model always underestimates the execution time, while the accuracy of the uid model increases along with the size of the problem. Our hybrid is the most accurate across the whole set of experiments.

For the LU benchmark we can see that for the class C instances the three models lead to similar predictions and correctly estimate the evolution of the execution time. A more interesting discrimination occurs for the smaller class B instances. As mentioned earlier, the simulation of small messages is more problematic for the uid and LogGPS models. Their representation of asynchronous sends is too simple to be accurate, especially for the uid model. This iterative benchmark alternates computations and communications at a high rate. Similar or close completion times as shown by Figure5 may hide a bad, but lucky, estimation of each component of the execution time. To be sure that estimation errors on computation times are not compensated by errors on the communication times, we propose to compare (a part of ) the Gantt charts of the actual and simulated executions. Such a comparison is given by Figure6 that shows a period of 0.2 seconds of the execution of the LU benchmark with 32 processes. The upper part of this gure displays the actual execution while the lower corresponds to the simulation of the same phase with the hybrid model.

Such Gantt charts are dicult to align perfectly due to the size of the initial execution traces and clock skew that requires a synchronization for the real trace. Real executions are also subject to system noise that does not occur in simulation causing some small discrepancies related to the computation time. This then prevents the observation of a perfect match. However, Figure6

clearly shows that despite the small time scale, the simulation correctly renders the general communication pattern of this benchmark. The execution time is 14.4 seconds while the prediction of the hybrid model is only of 9.9 seconds. We see two outstanding zones of MPI_Send and MPI_Wait. Such operations typically take few microseconds to less than a millisecond. Here they take 0.2 seconds. Our guess is that, due to a high congestion, the switch drops packets and slows down one (or several) process to the point where it stops sending until a timeout of .2 seconds is reached. Because of the communication pattern, blocking one process impacts all the other processes. This phenomenon occurs 24 times leading to a delay of 4.86 seconds. Without this bad behavior, the real execution would take 9.55 seconds, which is extremely close to the prediction of the hybrid model. The same Inria phenomenon was for class C. This behavior of the interconnection network can be considered as a bug that needs to be xed in a production environment.

RR n°8300

Sweep3D

Here we consider another benchmark representative of the heart of real applications. The Sweep3D kernel solves a time-independent discrete ordinates 3D Cartesian geometry neutron transport problem. This Fortran code makes heavy use of pipelining techniques, and thus overlaps communications with computation. Eight waves traverse the 3D grid, each starting from one corner and moving towards the opposite corner. In terms of MPI communications it corresponds to a complex pattern of point-to-point communications, with some collective operations. In our experiments, the Sweep3D application is simulated on-line by SMPI. q q q q q q q q q q q q q q 0.0 0.5 10x10x400-10mk-3mmi 5x5x400-10mk-3mmi Figure8 presents the achieved results for two small instances of the Sweep3D benchmark.

With regard to the previous experiments, these results show two interesting dierences. First, the measured execution times are very short, less than 1.4 seconds for the longest run. It allows us to see whether models can be distinguished even over such a short time period. Second, such small instances of the benchmark do not scale at all and are even badly impacted by the addition of extra processors. This then tells us if simulation can be useful not only to predict good and expected scalability results, but also to detect when a scalability limit has been reached or exceeded. The answer to both questions is yes. We see that small messages are badly handled by the simple uid model, which is far less accurate than the hybrid and LogGPS models. These two models provide very similar estimations of the execution time. It is also interesting to note that all three models, including the imprecise uid models, are able to reect the increasing trend of the execution time. This shows the benets of partial on-line simulation to analyze the performance of MPI applications.

RR n°8300 6 Simulating a Real Application

In this section we aim at demonstrating the capacity of SMPI to simulate a real, large, and complex MPI application. BigDFT is a Density Functional Theory (DFT) code that develops a novel approach for electronic structure simulation based on the Daubechies wavelets formalism [START_REF] Genovese | Daubechies Wavelets as a Basis Set for Density Functional Pseudopotential Calculations[END_REF]. The code is HPC-oriented, i.e., it uses MPI, OpenMP and GPU technologies. So far, BigDFT is the sole electronic structure code based on systematic basis sets which can use hybrid supercomputers. For our experiments, we disable the OpenMP and GPU extensions at compile time to study behaviors related to MPI operations. BigDFT alternates between regular computation bursts and important collective communications. Moreover the set of collective operations that is used is determined by the problem size.

While this application can be simulated by SMPI without any modication to the source code, its large memory footprint means that to run the simulation on a single machine would require an improbably large amount of system ram. Applying the memory folding techniques mentioned in Section3 and detailed in [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF], we were able to simulate the execution of BigDFT with 128 processes, whose peak memory footprint is estimated to 71 GiB, on a single laptop with 12GB of memory. Figure9 shows the execution trace corresponding to this simulated execution. In addition to this particular application, we were also able to simulate another geodynamics application called SpecFEM3D [START_REF] Peter | Forward and Adjoint Simulations of Seismic Wave Propagation on Fully Unstructured Hexahedral Meshes[END_REF] and the full LinPACK suite. SMPI also is tested upon 80% of the MPICH test suite every night to make non-regression tests. We can thus claim that SMPI is not limited to toy applications but can eectively be used for the analysis of real scientic applications.

Conclusion and Future Work

We have demonstrated that accurate modeling and performance prediction for a wide range of parallel applications requires proper consideration of many aspects of underlying communication architecture, including the breakdown of collective communications into their component pointto-point messages, the interconnect topology, and contention between competing messages that are sent simultaneously over the same link. Even relatively minor inaccuracies may compromise Inria the soundness of the simulation, yet none of the models previously used in the literature give due consideration to these factors. We have described the implementation of a proposed network model that improves on this situation within SMPI, and shown that SMPI-based simulations do a better job of tracking real-world behavior than those implemented using competing simulation toolkits.

Our priority in this work was the validation of the model at a small scale and for TCP over Ethernet networks. Such a tool would prove very useful for eorts such as the European Mont-Blanc project [START_REF]The mont-blanc project[END_REF][START_REF] Rajovic | The low-power architecture approach towards exascale computing[END_REF], which aims to prototype exascale platforms using low-power embedded processors interconnected by Ethernet. A next step will be to analyze its adequacy for simulating larger platforms when we can get access to such large machines for experimental purposes.

The study should then extend to other kinds of interconnects (such as InniBand) and more complicated topologies.

While experimental data have been collected by hand for the present analysis, the need to collect more and more traces to test against various platforms is a strong incentive to automate this task. Thus, one future work will be to build a systematic validation/invalidation framework based on the automatic collection of traces.

As a base line, we advocate for an open-science approach, which should enable other scientists to reproduce the experiments done in this paper. For that purpose, the traces and scripts used to produce our analysis are available [START_REF]Improving simulations of MPI applications using a hybrid network model with topology and contention support[END_REF]. Accordingly, SMPI and all the software stack are provided as open-source software available for download from the public Internet. We also intend to distribute the MPI benchmarks used to measure platform parameters and check model validity, and the R scripts exploiting the resulting data along with the next packaged version of SimGrid.

  Rendez-vous mode (k > S).

4 . 1 Figure 2 :

 412 Figure 2: MPI_Send and MPI_Recv duration as a function of message size.

Figure 3 :

 3 Figure 3: The "hybrid" network model of SMPI in a nutshell.

Figure 4 :

 4 Figure 4: Comparison between simulated and actual execution times for the MPI_Alltoall operation.

Figure 5 :

 5 Figure 5: Comparison between simulated and actual execution times for three NAS parallel benchmarks.

Figure 6 :

 6 Figure 6: Part of the Gantt chart of the execution of the LU benchmark with 32 processes. The upper part displays the actual execution while the lower is the simulation with the hybrid model.

Figure 7 :

 7 Figure 7: Two seconds Gantt-chart of the real execution of a class B instance of CG for 128 process.

Figure 8 :

 8 Figure 8: Comparison between simulated and actual execution times for two Sweep3D instances.

Figure 9 :

 9 Figure 9: Simulated execution trace of BigDFT with 128 processes.

  The observed discrepancies motivate the denition of a new hybrid model building upon LogGPS and uid models, that captures all the relevant eects observed during this study. All the presented experiments were conducted on the graphene cluster of the Grid'5000 experimental testbed. This cluster comprises 144 2.53GHz Quad-Core Intel Xeon x3440 nodes spread across four cabinets, and interconnected by a hierarchy of 10 Gigabit Ethernet switches. A full description of the interconnection network is available online[12].

1

  More information on how to instantiate the parameters of the SMPI model and about the study of non-

blocking operations is available at http://mescal.imag.fr/membres/arnaud.legrand/research/smpi/smpi_loggps.php RR n°8300

8 Acknowledgments This work is partially supported by the SONGS ANR project (11-ANR-INFRA-13) and the CNRS PICS N • 5473. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES


Phu Duc

Monique Chau

François Thonnat

Bremond {duc-Phu

Thonnat

Automatic Parameter Adaptation for Multi-Object Tracking

Keywords: Object tracking, parameter adaptation, machine learning, controller

Object tracking quality usually depends on video context (e.g. object occlusion level, object density). In order to decrease this dependency, this paper presents a learning approach to adapt the tracker parameters to the context variations. In an offline phase, satisfactory tracking parameters are learned for video context clusters. In the online control phase, once a context change is detected, the tracking parameters are tuned using the learned values. The experimental results show that the proposed approach outperforms the recent trackers in state of the art. This paper brings two contributions: (1) a classification method of video sequences to learn offline tracking parameters, (2) a new method to tune online tracking parameters using tracking context.

Introduction

Many approaches have been proposed to track mobile objects in a scene. However the quality of tracking algorithms always depends on scene properties such as: mobile object density, contrast intensity, scene depth and object size. The selection of a tracking algorithm for an unknown scene becomes a hard task. Even when the tracker has already been determined, it is difficult to tune online its parameters to get the best performance.

Some approaches have been proposed to address these issues. The authors in [START_REF] Kuo | Multi-target tracking by online learned discriminative appearance models[END_REF] propose an online learning scheme based on Adaboost to compute a discriminative appearance model for each mobile object. However the online Adaboost process is time consuming. In [START_REF] Borji | Adaptive Object Tracking by Learning Background Context[END_REF], the authors present an online learning approach to adapt the object descriptors to the current background. However, the training phase requires the user interaction. This increases significantly the processing time and is not practical for the real time applications. Some approaches integrate different trackers and then select the convenient tracker depending on video content [START_REF] Santner | PROST: Parallel Robust Online Simple Tracking[END_REF] [START_REF] Yoon | Visual Tracking via Adaptive Tracker Selection with Multiple Features[END_REF]. These approaches run the tracking algorithms in parallel. At each frame, the best tracker is selected to compute the object trajectories. These two approaches require the execution of different trackers in parallel which is expensive in terms of processing time. In [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF], the authors propose a tracking algorithm whose parameters can be learned offline for each tracking context. However the authors suppose that the context within a video sequence is fixed over time. Moreover, the tracking context is manually selected.

These studies have obtained relevant results but show strong limitations. To solve these problems, we propose in this paper a new method to tune online the parameters of tracking algorithms using an offline learning process. In the online phase, the parameter tuning relies entirely on the learned database, this helps to avoid slowing down the processing time of the tracking task. The variation of context over time during the online phase is also addressed in this paper.

This paper is organized as follows. Section 2 and 3 present in detail the proposed approach. Section 4 shows the results of the experimentation and validation. A conclusion as well as future work are given in the last section.

Offline Learning

The objective of the learning phase is to create a database which supports the control process of a tracking algorithm. This database contains satisfactory parameter values of the controlled tracking algorithm for various scene conditions. This phase takes as input training videos, annotated objects, annotated trajectories, a tracking algorithm including its control parameters. The term "control parameters" refers to parameters which are considered in the control process (i.e. to look for satisfactory values in the learning phase and to be tuned in the online phase). At the end of the learning phase, a learned database is created. A learning session can process many video sequences. Figure 1 presents the proposed scheme for building the learned database.

The notion of "context" (or "tracking context") in this work represents elements in the videos which influence the tracking quality. More precisely, a context of a video sequence is defined as a set of six features: density of mobile objects, their occlusion level, their contrast with regard to the surrounding background, their contrast variance, their 2D area and their 2D area variance. For each training video, we extract these contextual features from annotated objects and then use them to segment the training video in a set of consecutive chunks. Each video chunk has a stable context. The context of a video chunk is represented by a set of six code-books (corresponding to six features). An optimization process is performed to determine satisfactory tracking parameter values for the video chunks. These parameter values and the set of code-books are inserted into a temporary learned database. After processing all training videos, we cluster these contexts and then compute satisfactory tracking parameter values for context clusters.

In the following, we describe the four steps of the offline learning process: (1) contextual feature extraction, (2) context segmentation and code-book modeling, (3) tracking parameter optimization and (4) context clustering.

Contextual Feature Extraction

For each training video, the context feature values are computed for every frame.

1. Density of Mobile Objects: A high density of objects may lead to a decrease of object detection and tracking performance. The density of mobile objects at t is defined by the sum of all object areas over the 2D camera view.

2. Occlusion Level of Mobile Objects: An occlusion occurrence makes the object appearance partially or completely invisible. The occlusion level of mobile objects at instant t is defined as the ratio between the 2D overlap area of objects and the object 2D areas.

3. Contrast of Mobile Objects: The contrast of an object is defined as the color intensity difference between this object and its surrounding background. An object with low contrast decreases the discrimination of the appearance between different objects. The contrast of mobile objects at instant t is defined as the mean value of the contrasts of objects at instant t.

4. Contrast Variance of Mobile Objects: When different object contrast levels exist in the scene, a mean value cannot represent correctly the contrast of all objects in the scene. Therefore we define the variance of object contrasts at instant t as their standard deviation value.

5. 2D Area of Mobile Objects: 2D area of an object is defined as the number of pixels within its 2D bounding box. Therefore, this feature characterizes the reliability of the object appearance for the tracking process. The 2D area feature value at t is defined as the mean value of the 2D areas of mobile objects at instant t.

6. 2D Area Variance of Mobile Objects: Similar to the contrast feature, we define the variance of object 2D areas at t as their standard deviation value.

Context Segmentation and Code-book Modeling

The contextual variation of a video sequence influences significantly the tracking quality. Therefore it is not optimal to keep the same parameter values for a long video. In order to solve this issue, we propose an algorithm to segment a training video in consecutive chunks, each chunk is defined as having a stable context (i.e. the values of a same context feature in each chunk are close to each other). This algorithm is described as follows.

First, the training video is segmented in parts of l frames. Second, the contextual feature values of the first part is represented by a context code-book model. From the second video part, we compute the distance between the context of the current part and the context code-book model of the previous part. If their distance is lower than a threshold T h 1 (e.g. 0.5), the context code-book model is updated with the current video part. Otherwise, a new context codebook model is created to represent the context of the current video part. At the end of the context segmentation algorithm, the training video is divided into a set of chunks (of different temporal lengths) corresponding to the obtained context code-book models. The following sections present how to represent a video context with a code-book model; and how to compute the distance between a context code-book model and a context.

1. Code-book Modeling: During the tracking process, low frequent contextual feature values play an important role for tuning tracking parameters. For example, when mobile object density is high in few frames, the tracking quality can decrease significantly. Therefore, we decide to use a code-book model [START_REF] Kim | Background modeling and subtraction by codebook construction[END_REF] to represent the values of contextual features because this model can estimate complex and low-frequency distributions. In our approach, each contextual feature is represented by a code-book, called feature code-book, denoted cb k , k = 1..6. So a video context is represented by a set of six feature code-books, called context code-book model, denoted CB, CB = {cb k , k = 1..6}. A feature codebook is composed of a set of code-words describing the values of this feature. The number of code-words depends on the diversity of feature values.

Code-word definition: A code-word represents the values and their frequencies of a contextual feature. A code-word i of code-book k (k = 1..6), denoted cw k i , is defined as follows:

cw k i = {µ k i , m k i , M k i , f k i } (1)
where µ k i is the mean of the feature values belonging to this code-word; m k i and M k i are the minimal and maximal feature values belonging to this word; f k i is the number of frames when the feature values belong to this word. For each frame t, the code-book cb k (k = 1..6) is updated with the value of context feature k computed at t. 1 presents the algorithm to compute the distance between a context c and a context code-book model CB = {cb k , k = 1..6}. The function distance(µ k t , cw k i ) is defined as a ratio between µ k t and µ k i . This distance is normalized in the interval [0, 1].

Context Distance: Table

Tracking Parameter Optimization

The objective of the tracking parameter optimization task is to find the values of the control parameters which ensure the tracking quality higher a given threshold for each video chunk. These parameters are called "satisfactory parameters".

k i in code-book cb k if (distance(µ k t , cw k i ) < ) { count++; break; } if (count / l < 0.5) return 1; countT otal + = count; return ( 1 -countT otal/(l * 6) )
Table 1. Algorithm for computing the distance between a context code-book CB and a video context c This task takes as input annotated objects, annotated trajectories, a tracking algorithm, a video chunk and control parameters for the considered tracker. The annotated objects are used as object detection results. Depending on the search space size and the nature of the control parameters, we can select suitable optimization algorithm (e.g. enumerative search, genetic algorithm).

Context Clustering

The context clustering step is done at the end of each learning session when the temporary learned database contains the processing results of all training videos. In some cases, two similar contexts can have different satisfactory parameter values because optimization algorithm only finds local optimal solutions. A context clustering is thus necessary to group similar contexts and to compute satisfactory parameter values for the context clusters.

In this work, we decide to use the Quality Threshold Clustering algorithm for this step because this algorithm does not require the number of clusters as input. Once contexts are clustered, all the code-words of these contexts become the code-words of the created cluster. The tracking parameters for a cluster is defined as a combination of tracking parameters belonging to clustered contexts.

Online Parameter Adaptation

In this section, we describe the proposed controller which aims at tuning online the tracking parameter values for obtaining satisfactory tracking performance. The online parameter adaptation phase takes as input the video stream, the list of detected objects at every frame, the learned database and gives as output the satisfactory tracking parameter values for every new context detected in the video stream (see figure 2). In the following sections, we describe the two main steps of this phase: the context detection and parameter tuning steps.

Context Detection

This step takes as input for every frame, the list of the current detected objects and the image. For each video chunk of l frames, we compute the values of the contextual features. A contextual change is detected when the context of the current video chunk does not belong to the context cluster (clusters are learned in the offline phase) of the previous video chunk. In order to ensure the coherence between the learning phase and the testing phase, we use the same distance defined in the learning phase (section 2.2) to perform this classification. If this distance is lower than threshold T h 1 , this context is considered as belonging to the context cluster. Otherwise, the "Parameter tuning" task is activated.

Parameter Tuning

The parameter tuning task takes as input an active signal and the current context from the "context detection" task, and gives as output satisfactory tracking parameter values. When this process receives an activate signal, it looks for the cluster in the learned database to which the current context belongs. Let D represent the learned database, a context c of a video chunk of l frames belongs to a cluster C i if both conditions are satisfied:

contextDistance(c, C i , l) < T h 1 ( 2
)
∀C j ∈ D, j = i : contextDistance(c, C i , l) ≤ contextDistance(c, C j , l) (3)
where T h 1 is defined in section 2.2. The function contextDistance(c, C i , l) is defined in table 1. If such a context cluster C i is found, the satisfactory tracking parameters associated with C i are considered as good enough for parameterizing the tracking of the current video chunk. Otherwise, the tracking algorithm parameters do not change, the current video chunk is marked to be learned offline later.

4 Experimental Results

Parameter Setting and Object Detection Algorithm

The proposed control method has two predefined parameters. The distance threshold T h 1 to decide whether two contexts are close enough (sections 2.2 and 3.2) is set to 0.5. The minimum number of frames l of a context segment (sections 2.2 and 3.1) is set to 50 frames. A HOG-based algorithm [START_REF] Corvee | Body parts detection for people tracking using trees of Histogram of Oriented Gradient descriptors[END_REF] is used for detecting people in videos.

Evaluation Metrics

In this experimentation, we select the tracking evaluation metrics used in several publications [START_REF] Kuo | Multi-target tracking by online learned discriminative appearance models[END_REF][9] [START_REF] Li | Learning to Associate: HybridBoosted Multi-Target Tracker for Crowded Scene[END_REF]. Let GT be the number of trajectories in the ground-truth of the test video. The first metric M T computes the number of trajectories successfully tracked for more than 80% divided by GT. The second metric P T computes the number of trajectories that are tracked between 20% and 80% divided by GT. The last metric M L is the percentage of the left trajectories.

Controlled Tracker

In this paper, we select an object appearance-based tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] to test the proposed approach. This tracker takes as input a video stream and a list of objects detected in a predefined temporal window. The object trajectory computation is based on a weighted combination of five object descriptor similarities: 2D area, 2D shape ratio, RGB color histogram, color covariance and dominant color. For this tracker, the five object descriptor weights w k (k = 1..5) are selected for testing the proposed control method. These parameters depend on the tracking context and have a significant effect on the tracking quality.

Training Phase

In the training phase, we use 15 video sequences belonging to different contexts (i.e. different levels of density and occlusion of mobile objects as well as of their contrast with regard to the surrounding background, their contrast variance, their 2D area and their 2D area variance). These videos belong to four public datasets (ETISEO, Caviar, Gerhome and PETS) and to the two European projects (Caretaker and Vanaheim). They are recorded in various places: shopping center, buildings, home, subway stations and outdoor.

Each training video is segmented automatically in a set of context segments. In the tracking parameter optimization process, we use an Adaboost algorithm to learn the object descriptor weights for each context segment because each object descriptor similarity can be considered as a weak classifier for linking two objects detected within a temporal window. The Adaboost algorithm has a lower complexity than the other heuristic optimization algorithms (e.g. genetic algorithm, particle swam optimization). Also, this algorithm avoids converging to the local optimal solutions. After segmenting the 15 training videos, we obtain 72 contexts. By applying the clustering process, 29 context clusters are created.

Testing Phase

All the following test videos do not belong to the set of the 15 training videos.

Caretaker video

The first tested video sequence belongs to the Caretaker project1 whose video camera is installed in a subway station. The length of this sequence is 1 hour 42 minutes. It contains 178 mobile objects. The graph in figure 3 presents the variation of contextual feature values and of the detected contexts in the test sequence from frame 2950 to frame 3200. The values of object 2D areas are normalized for displaying. From frame 2950 to 3100, the area and area variance values of objects are very small most of the time (see the brown and light blue curves). The context of this video chunk belongs to cluster 12. In this cluster, the color histogram is selected as the most important object descriptor for tracking mobile objects (w 3 = 0.86). This parameter tuning result is reasonable because compared to the other considered object descriptors, the color histogram descriptor is quite reliable for discriminating and tracking objects of low resolution (i.e. low 2D area). From frame 3101 to 3200, a larger object appears, the context belongs to cluster 9. For this context cluster, the dominant color descriptor weight is the most important (w 5 = 0.52). In this case, the object appearance is well visible. The dominant color descriptor is then reliable for tracking object.

The proposed controller helps to increase the MT value from 61.24% to 71.32%, and to decrease the value of ML from 24.72% to 20.40%.

Caviar Dataset

The Caviar videos are recorded in a shopping center corridor. They have 26 sequences in which 6 sequences belong to our training video set. The other 20 sequences including 143 mobile objects are used for testing. Figure 4 shows the correct tracking results of four persons while occlusions happen. Table 2 presents the tracking results of the proposed approach and of some recent trackers from the state of the art. The proposed controller increases significantly the performance of the tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF]. The M T value increases 78.3% to 85.5% and the M L value decreases 5.7% to 5.3%. We obtain the best M T value compared to state of the art trackers.

PETS 2009 Video

In this test, we use the CLEAR metrics presented in [START_REF] Bernardin | EvaluatingMultiple Object Tracking Performance: The CLEAR MOTMetrics[END_REF] to compare with other tracking algorithms. The first metric MOTA computes Multiple Object Tracking Accuracy. The second metric MOTP computes Multiple Object Tracking Precision. The higher these metrics, the better the tracking quality is. We select the sequence S2 L1, camera view 1, time 12.34 for testing because this sequence is experimented in several state of the art trackers. This sequence has 794 frames, contains 21 mobile objects and several occlusion cases. With the proposed controller, the tracking result increases significantly. Table 3 presents the metric results of the proposed approach and of different trackers from the state of the art. The metric M represents the average value of MOTA and MOTP. With the proposed approach, we obtain the best values in all the three metrics.

Conclusion and Future Work

In this paper, we have presented a new control approach for tuning online the tracker parameters. The proposed offline learning phase helps to decrease effectively the computational cost of the online control phase. The experiments show a significant improvement of the tracking performances while using the proposed controller. Although we test with an appearance-based tracker, other tracker categories can still be controlled by adapting the context definition to Approaches MT (%) PT (%) ML (%) Xing et al. [START_REF] Xing | Multi-object tracking through occlusions by local tracklets filtering and global tracklets association with detection responses[END_REF] 84.3 12.1 3.6 Li et al. [START_REF] Li | Learning to Associate: HybridBoosted Multi-Target Tracker for Crowded Scene[END_REF] 84.6 14.0 1.4 Kuo et al. [START_REF] Kuo | Multi-target tracking by online learned discriminative appearance models[END_REF] 84.6 14.7 0.7 Appearance Tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] without the proposed controller 78.3 16.0 5.7 Appearance Tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] with the proposed controller 85. [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] 9.2 5.3

Fig. 1 .

 1 Fig. 1. The offline learning scheme

  function contextDistance(c, CB, l) Input: context code-book model CB, context c, l (number of frames of context c) Output: context distance between code-book model CB and context c countT otal = 0; For each code-book cb k in CB (k = 1..6) count = 0; For each value µ k t of context c at time t For each codeword cw

Fig. 2 .

 2 Fig. 2. The online parameter adaptation scheme

Fig. 3 .

 3 Fig. 3. Variations of the contextual feature values and of the detected contexts in the subway sequence from frame 2950 to frame 3350.

Fig. 4 .

 4 Fig. 4. Tracking results of four persons in the sequence ShopAssistant2cor (Caviar dataset) are correct, even when occlusions happen.

Table 2 .

 2 Tracking results for the Caviar dataset. The proposed controller improves significantly the tracking performance. The best values are printed in bold.

http://cordis.europa.eu/ist/kct/caretaker synopsis.htm

Acknowledgments

This work is supported by The PACA region, The General Council of Alpes Maritimes province, France as well as The Vanaheim, Panorama and Support projects.

Approaches

MOTA MOTP M Berclaz et al. [START_REF] Berclaz | Multiple object tracking using kshortest paths optimization[END_REF] 0.80 0.58 0.69 Shitrit et al. [START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] 0.81 0.58 0.70 Henriques et al. [START_REF] Henriques | Globally optimal solution to multi-object tracking with merged measurements[END_REF] 0.85 0.69 0.77 Appearance Tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] without the proposed controller 0.62 0.63 0.63 Appearance Tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] with the proposed controller 0.87 0.72 0.80 the principle of these trackers. In future work, we will extend the context notion which should be independent from the object detection quality.