Claire Adam-Bourdarios

Glen Cowan

Cécile Germain

Isabelle Guyon

Balázs Kégl

David Rousseau

How Machine Learning won the Higgs Boson Challenge

How Machine Learning won the Higgs Boson Challenge

Claire Adam-Bourdarios 1,2 , Glen Cowan 4 , Cécile Germain 1,3 Isabelle Guyon 1,5 , Balàzs Kégl 1,2,3 , and David Rousseau 1,2 1-LRI, UPSud, Université Paris-Saclay, France. 2-LAL, IN2P3/CNRS, France.

3-CNRS/INRIA, France. 4-Royal Holloway, London, UK. 5-ChaLearn, USA.

Abstract.

In 2014 we ran a very successful machine learning challenge in High Ernergy physics attracting 1785 teams, which exposed the machine learning community for the first time to the problem of "learning to discover" (www.kaggle.com/c/higgs-boson). While physicists had the opportunity to improve on the state-of-the-art using "feature engineering" based on physics principles, this was not the determining factor in winning the challenge. Rather, the challenge revealed that the central difficulty of the problem is to develop a strategy to optimize directly the Approximate Median Significance (AMS) objective function, which is a particularly challenging and novel problem. This objective function aims at increasing the power of a statistical test. The top ranking learning machines span a variety of techniques including deep learning and gradient tree boosting. This paper presents the problem setting and analyzes the results.

Increasingly, machine learning scientists are getting away from canonical problems of classification and regression and are venturing into new domains by formulating new tasks as learning problems. In the recent years we have seen, for example, the task of learning to rank [START_REF] Chapelle | Yahoo! learning to rank challenge overview[END_REF] and learning to recommend [START_REF] Melville | Recommender systems[END_REF], which have become pervasive in applications. In this paper, we tackle a new machine learning task addressing the problem of evaluating the significance of a sientific discovery: learning to discover . Superficially, this problem is a two-class classification problem separating events of interest (called signals) that have not been encountered or characterized before in nature (but were predicted by a theory) from events produced by already observed processes (called backgrounds). However, the problem setting differs from regular classification problems in two respects: (1) Discovery: Since signals were never observed before in real data, no labeled training example from real data are available. Rather, simulated data (from a simulator implementing theoretical predictions) can be produced to generate training data. The learning machine can then address the "inverse problem" of predicting which events are signals in real data. (2) Evaluation: Typically the number of signals is expected to be orders of magnitude smaller that the number of backgrounds. Hence, the statistical significance of the detection of a number of signal events must be assessed to claim a discovery. For this reason, the evaluation function of the classifier is a metric of a statistical test.

The Discovery-Evaluation criteria define a wide scope that has previously been addressed mainly by Neyman-Pearson learning [START_REF] Scott | A Neyman-Pearson approach to statistical learning[END_REF]. In this paper, we examine a new case of the learning to discover problem, the discovery of new particles, that leads to a different framework. The problem has been used recently in a comparison of deep vs. shallow representation learning [START_REF] Baldi | Searching for exotic particles in high-energy physics with deep learning[END_REF]. With the HiggsML Machine Learning challenge organized in 20141 [START_REF] Cowan | The Higgs boson machine learning challenge[END_REF], it becomes a benchmark problem. The data were released at http://opendata.cern.ch/ after the end of the challenge. This unprecedented disclosure of precious data belonging to the ATLAS collaboration highlights the importance of the learning to discover task. The dataset, and the subject of the challenge correspond to particular physical process, the H → τ + τ -channel. However, the methodology is fully generic to the discovery of a new particle, and could generalize to other discovery settings.

From the algorithmic point of view, the novelty of the problem mainly comes from its exotic objective function, the Approximate Median Significance (AMS). The AMS presents several undesirable features to train a learning machine: it is discontinuous (discontinuity arise for each sample); it is non differentiable; it is non additive (the overall AMS is not the sum of individual contributions of the samples); it uses sample weights available only for training. This seems to have drawn a lot of interest because off-the-shelf packages do not directly support the optimization of non-standard objective functions and the participants saw an opportunity to make novel contributions and distinguish themselves from the rest of the crowd. The top ranking challenge participants greatly improved the performance over baseline methods.

The physics problem

The ATLAS and the CMS experiments jointly claimed the discovery of the Higgs boson [START_REF] Aad | Observation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC[END_REF][START_REF] Chatrchyan | Observation of a new boson at a mass of 125 GeV with the CMS experiment at the LHC[END_REF] in 2012. The Higgs boson has many different processes (called channels by physicsts) through which it can decay, that is produce other particles. Beyond the initial discovery, the study of all modes of decay increases confidence in the validity of the theory and helps characterize the new particle. The Higgs boson was first seen in three distinct decay channels which are all boson pairs. One of the next important topics is to seek evidence on the decay into fermion pairs, namely tau-leptons or b-quarks, and to precisely measure their characteristics. The first evidence of the H to tau tau channel was recently reported by the ATLAS experiment [START_REF]Evidence for Higgs Boson Decays to tau+tau-Final State with the ATLAS detector[END_REF]. The aim of the challenge is to increase the statistical significance of this discovery.

Discovery and characterization rely on experiments that run at the Large Hadron Collider (LHC) at CERN. Hundreds of millions of proton-proton collisions per second are produced. The particles resulting from each bunch crossing are detected by sensors and filtered in real-time. For each collision, the raw data produced by the sensors are ultimately digested into a vector of features containing up some tens of real-valued variables. This vector is called an event.

The vast majority of events represent known (background) processes: they are mostly produced by processes which are exotic in everyday terms, but known, having been discovered in previous generations of experiments. The learning problem is to find a region in feature space with a significant excess of signal events. Discovery of a new particle ultimately boils down to classical statistical testing. The null hypothesis is that the experiment produces only background events, and the alternative hypothesis is that it produces some signal events.

The AMS objective function

For the formal description of the Challenge, let D = (x 1 , y 1 , w 1 ), . . . , (x n , y n , w n ) be the training sample, where x i ∈ R d is a d-dimensional feature vector, y i ∈ {b, s} is the label, and w i ∈ R + is a non-negative weight. Let S = {i : y i = s} and B = {i : y i = b} be the index sets of signal and background events, respectively, and let n s = |S| and n b = |B| be the numbers of simulated signal and background events2 .

There are two properties that make our simulated set different from those collected in nature or sampled in a natural way from a joint distribution p(x, y). 3First, as many events of the signal class as needed can be simulated (within a computational budget), so the proportion n s /n b of the number of points in the two classes does not have to reflect the proportion of the prior class probabilities P (y = s)/P (y = b). This is actually a good thing: since P (y = s) P (y = b), the training sample would be very unbalanced if the numbers of signal and background events, n s and n b , were proportional to the prior class probabilities P (y = s) and P (y = b). Second, the simulator produces importance-weighted events. Since the objective function (3) will depend on the unnormalized sum of weights, to make the setup invariant to the numbers of simulated events n s and n b , the sum across each set (training, public test, private test, etc.) and each class (signal and background) is be kept fixed, that is,

i∈S w i = N s and i∈B w i = N b . (1)
The normalization constants N s and N b have physical meanings: they are the expected total number of signal and background events, respectively, during the time interval of data taking (the year of 2012 in our case). The individual weights are proportional to conditional densities ratios:

w i ∼ p s (x i )/q s (x i ), if y i = s, p b (x i )/q b (x i ), if y i = b, (2)
where p s (x i ) = p(x i |y = s) and p b (x i ) = p(x i |y = b) are the conditional signal and background densities, respectively, and q s (x i ) and q b (x i ) are instrumental densities used by the simulator.

Let g : R d → {b, s} be an arbitrary classifier. Let the selection region G = {x : g(x) = s} be the set of points classified as signal, and let G denote the index set of points that g selects (physics terminology) or classifies as signal (machine learning terminology), that is, G = {i : x i ∈ G} = i : g(x i ) = s . Then from Eqs. ( 1) and ( 2) it follows that the quantity s = i∈S∩ G w i is an unbiased estimator of the expected number of signal events selected by g, and, b = i∈B∩ G w i is an unbiased estimator of the expected number of background events selected by g, In machine learning terminology, s and b are are true and false positive rates. Given a classifier g, the AMS objective function used for the challenge is defined by

AMS = 2 (s + b + b reg ) ln 1 + s b + b reg -s (3)
where b reg is a regularization term (e.g. b reg = 10). The derivation of this formula is given in [START_REF] Cowan | Asymptotic formulae for likelihood-based tests of new physics[END_REF]. Quantitatively, a fluctuation is considered anomalous by physicists (the evidence of a discovery) if it exceeds 5σ, that is if AMS > 5, which corresponds to a p-value of the one-sided Z-test of 3 × 10 -7 .

Results of the challenge

Organizing a challenge can be thought of as designing a large scale numerical experiment in which research is "crowd-sourced". Given a well-posed scientific question, challenges are very effective in obtaining an answer. This has been the case for the Higgs-Boson challenge. The challenge helped making both qualitative and quantitative advances to the problem of optimizing the AMS. First, from the quantitative point of view, the AMS of the top ten participants ranged in [3.76, 3.80], while the benchmark (based on a software widely used in High Energy physics called TMVA4 , ranked only 782 with an AMS of ∼3.50. This brings us closer (albeit still far) from the target set forth by physicists of AMS=5. The winning solution of Gabor Melis [START_REF] Melis | Dissecting the winning solution of the higgsml challenge[END_REF] uses a deep learning method (an ensemble of 70 3-layers neural networks, fully interconnected, with 600 hidden units per layer), confirming that deep learning methods can be very competitive. But, most top ranking participants used ensembles of decision trees, and particularly the XGBoost software 5 . The ease of interpretability of the model helped the crowwork team in feature construction and hyper-parameter tuning to attain an AMS of 3.76 [START_REF] Chen | Higgs boson discovery with boosted trees[END_REF]. The major advantage of the XGBoost over straightforward gradient boosting relies on explicit regularization, reducing the need of manual hyper-parameter tuning. However, the solution of Melis is clearly more robust as indicated by the fact that it dominated all other solutions, regardless of the choice on the threshold monitoring the tradeoff between true positive rate and false positive rate. This robustness may be attributable to the use of a voting ensemble and the use of "drop-out", a method consisting in silencing neurons at random during training. The price to be payed for such a deep learning solution is months of architecture and hyper-parameter tuning, using a fast GPU-powered computer. In contrast, the boosted decision tree solutions are obtained relatively fast (in minutes) with little need for hyperparameter tuning: the completely untuned XGBoost achieved ∼3.64 on the test set, ranking in the 200th.

Second, several important qualitative (conceptual) advances were made. Most of the participants (including the winner), followed a bi-level optimization approach, optimizing a surrogate cost function (logistic loss or AUC) and adjusting the cut-off classification threshold to optimize the AMS by cross-validation. For the logistic loss, [START_REF] Kotlowski | Consistent optimization of AMS by logistic loss minimization[END_REF] provides a theoretical justification for the default approach to post-fit the cut-off, proving asymptotic consistency and bounding the rate of convergence. However some effort was put into finding other ways of optimizing the AMS. For example, the 9th solution [START_REF] Diaz-Morales | Ensemble of maximized weighted auc models for the maximization of the median discovery significance[END_REF] uses a weighted version of the AUC as a surrogate cost function, thus approximating the AMS with an additive loss. Another principled approach to exploit all classical additive cost functions with a simple sample reweighing has been proposed by [START_REF] Mackey | Weighted classification cascades for optimizing discovery significance in the higgsml challenge[END_REF] who applies a variational method to optimize iteratively a set of linearized versions of the AMS.

We also had an interesting "negative" result. The promise that deep learning methods can save on human effort by learning internal representation in place of feature engineering was not held in the challenge. In the winning solution, the AMS drops by 13% if the derived (human engineered) features are not exploited. A recent benchmark of deep and shallow networks also show disappointing results for deep learning for the Higgs in tau tau task [START_REF] Baldi | Searching for exotic particles in high-energy physics with deep learning[END_REF], with a 6% performance drop. Although the results for learning internal representations are more encouraging for other high energy physics tasks, the ratio gain to sample size indicates that learning representations is extremely data demanding.

Another noteworthy development of the challenge concerns cross-validation. All top ranking participant carefully avoided to rely on the performances shown on the public leaderboard (computed on a too small data sample to provide reliable performance evaluation). Rather they repeated multiple times 10-fold cross-validation and averaged the results. For computation efficiency reasons, they used the learning machines thus trained as part of a voting ensemble. A interesting additional twist helped Melis win the challenge: Since the AMS is not an additive loss, it is different (i) to compute the AMS on the (very small) held out sets, then averaging the results or (ii) to collect statistics about false positive and false negative on the the held out sets, average them, then compute the AMS. The latter provides much smoother results.

In conlusion, the challenge revealed that participants who are skilled data scientitists with only elementary knowledge of physics could contribute to significantly improve the power of the AMS using machine learning. Deep Learning is a favorite technique but boosted decision trees are a strong contender, with several practical advantages. Bi-level optimization using a surrogate cost function beats direct optimization of the AMS, but variational methods, which tackle the problem head front, provide a new avenue of research worth exploring further.

www.kaggle.com/c/higgs-boson and https://higgsml.lal.in2p3.fr

We use roman s to denote the label and in indices of terms related to signal (e.g., ns), and s for the estimated number of signal events selected by a classifier. The same logic applies to the terms related to background.

We use small p for denoting probability densities and capital P for denoting the probability of random events.

http://tmva.sourceforge.net

https://github.com/dmlc/xgboost


Mathias Ettinger

François Broquedis

Thierry Gautier

Stephane Ploix

Bruno Raffin

VtkSMP: Task-based Parallel Operators for VTK Filters

Keywords: parallelism, parallel runtimes, work stealing, scientific visualization, VTK Programmation parallèle, vol de tâches, visualisation scientifique, VTK

NUMA nodes are potentially powerful but taking benefit of their capabilities is challenging due to their architecture (multiple computing cores, advanced memory hierarchy). They are nonetheless one of the key components to enable processing the ever growing amount of data produced by scientific simulations.

In this paper we study the parallelization of patterns commonly used in VTK algorithms and propose a new multi-threaded plugin for VTK that eases the development of parallel multi-core VTK filters. We specifically focus on task-based approaches and show that with a limited code refactoring effort we can take advantage of NUMA node capabilities. We experiment our patterns on a transform filter, base isosurface extraction filter and a min/max tree accelerated isosurface extraction. We support 3 programming environments, OpenMP, Intel TBB and X-KAAPI, and propose different algorithmic refinements according to the capabilities of the target environment. Results show that we can speed execution up to 30 times on a 48-core machine.

Introduction

The size of data produced by scientific simulations is growing at a steep rate. Postprocessing tools, including scientific visualization libraries, are urged to evolve accordingly to cope with these datasets.

Simple PCs as well as large supercomputers are today built around multi-core processor architectures, and future architectures are expected to host many-core processors, i.e. processors with hundreds of cores. Taking advantage of this processing power requires a core-level parallelization.

Though many parallel algorithms have been proposed to supplement sequential ones, many commonly used libraries are still not supporting efficient multi-core parallel executions. The VTK scientific visualization library is one of them. Beside the important effort required to revisit a large sequential code base, the lack of a standard parallel programming environment probably hampered parallelization efforts. Efficiently supporting large scale parallelism is a major challenge today [CGS + 13].

The challenge is to provide a programming model that enables the programmer to swiftly shift from its sequential programming habits to parallel ones while enabling efficient executions. Task parallelism based on the MPI standard, is classically used for large parallel executions. But on shared memory machines it can lead to data replications that affect memory footprint and performance. GPUs can be very efficient for high throughput data parallelism. But even if some task parallelism is enabled at the block level, it is often quite cumbersome to exploit. As a result, efficient implementations of irregular applications are difficult. The associated programming environments like Cuda or OpenCL are close to the GPU specific architecture, requiring to deeply rewrite sequential codes for GPU executions.

Work-stealing scheduling associated with task based programming is today emerging as sound approach for parallel shared memory programming. The user expresses potential parallelism though tasks, the scheduler taking care of balancing the workload between the participating compute resources. Parallelism is eventually extracted only if idle computing resources are available to steal part of these taks from busy resources. Environments like Cilk, TBB or KAAPI are based on this model. The OpenMP standard, Initially focused on loop parallelization, also support tasks (with dependencies since OpenMP 4), and implementation based on work stealing runtime provide high performance even at large core count.

In this paper we explore the potential of task based programming for VTK scientific visualization algorithms. This paper is an extended and updated version of the initial EGPGV 2013 paper [EBG + 13]. Driven by genericity and code reusability, we identify some high-level parallel operators that can replace sequential patterns in VTK filter code. We study 3 different parallelization patterns. The first one targets loops with independent iterations (foreach loop) that produce independent data chunks of known size that can be directly written in a global data structure without concurrency-related issues. Next, we look at foreach loops that produce data with unknown memory footprint. A merge of partial results can thus be necessary to produce a compact data structure. Eventually, we propose to parallelize a tree traversal, a common accelerated data structure that shows an irregular access pattern. The abstraction level proposed enable to select different runtimes, like KAAPI, TBB or OpenMP, at compile time. Experiments performed on 48 core machine show the potential of such approach with different runtimes This work led to the development of a new module, named vtkFiltersSMP, integrated into VTK version 6. Technical details are available through following wiki http://www.vtk.org/Wiki/VTK/VTK_ SMP.

Section 2 discuss existing approaches. Sections ?? reminds the base concepts of work stealing and taks based programming. Our approach is presented in section 4, with experimental results in section 5. A discussion (sections 6) and conclusion (section 7) closes this paper.

Related Work

Message passing as popularized by the MPI standard, is a classical parallel programming model well adapted for distributed memory machines. It however requires to explicitly manage data distribution across processes. For stencil like algorithms needing a visibility of the state of neighbors, data on the border of the partitioned domains are duplicated to reduce the data exchange overhead. These ghost cells increase the complexity of the code and the memory usage, while on a shared memory system these data duplication could be avoided. Ahrens et al. [ABM + 01] relied on MPI to propose a two level parallelization of VTK applications. Given that the input data can be partitioned (using ghost cells if necessary), their model supports data parallelism through a duplication of the processing pipeline. Additionally, when supported by the filters and the data, data blocks can be streamed down the pipeline, enabling concurrent executions of the different stages. It however does not support dynamics load balancing, relying on the user to define the partitioning policy.

Hyperflow [VOS + 10, VOC + 12] adopts similar goals but with a more modern context. They propose a thread level streaming and pipeline duplication strategy, thus supporting shared memory architectures. This thread level parallelization enables to avoid ghost cells, given that the necessary protection steps are taken to avoid race conditions. If the programmer provides a GPU implementation for some filters, the Hyperflow runtime is also able to defer computation to the GPUs available on the machine.

Similarly an early approach for shared memory machines have been proposed in [ALS + 00]. The authors propose a thread based interface for VTK, hiding some details of thread handling. But directly Inria programming at a thread level is today recognized as a low level approach that is error-prone [START_REF] Lee | The problem with threads[END_REF].

VTK has been initially developed based on a sequential execution model, leading to intrinsic limitations when facing the parallelization at large scale. For instance the visualization pipeline is built by assembling filters. Pipe-line execution is under the control of executives. This abstraction level brings modularity to the application, frees the programmer from scheduling issues, and enables VTK runtime to make smart decisions for optimizing performance. However this model becomes too complex when parallelization at large scale must be enabled. Hyperflow developed a specific executive to enable more parallelism at the pipe-line level.

Some recent initiatives explored alternative models for scientific visualization frameworks designed from the ground for large scale parallelism. These frameworks are known as the VTK-m frameworks. The collective paper [SMM + 12] presents an overview of these different approaches. We detail them in the following. Most of these frameworks are somehow interoperable with VTK.

Piston [START_REF] Sewell | Piston: A portable cross-platform framework for data-parallel visualization operators[END_REF] proposes a programming framework based on vector operators (data parallelism) as laid out in Guy Blelloch's seminal work [START_REF] Blelloch | Vector Models for Data-Parallel Computing[END_REF]. This approach requires to revisit all algorithms from this data parallel point of view. If data parallelism fits well several scientific visualization algorithms, it becomes more challenging as the level of regularity decreases. This model is well adapted to generate kernels for GPUs. Folding data parallel algorithms onto MIMD multi-core architectures is often easy, given that we do not attempts too aggressively to suppress the numerous synchronization barriers associated with data parallel model. For that purpose Piston is developed on top of the Thrust library [thr12]. Thrust offer parallel versions of operators on STL like vectors and list data structures for executions on GPUs through Cuda, but also on multi-core CPUs with OpenMP and Intel TBB. For performance purpose, Piston relies on simple sequences of operations and does not propose any specific high level model for ensuring some higher level of modularity when composing different opération as VTK does.

The Dax toolkit [dax, MAGM11] also adopts the data parallel model and abandons the visualization pipeline à la VTK in favor of a simple sequence of worklets calls. A worklet is a stateless sequential code to be executed on small elementary data. A given worklet is executed in parallel on all elementary data that constitute the input data set. A worklet does not directly manage memory allocation and layout, but rather accesses data through an abstraction layer, defering memory issues to the framework. However worklets derive from base worklets depending on the type of data access pattern and output generated. For instance WorkletMapField performs a basic mapping operation that applies a function (the operator in the worklet) on all the field values at a single point or cell and creates a new field value at that same location. WorkletGenerateTopology generates a cell connectivity. When invoked, the dispatcher is given an array containing the number of output cells derived from each input cell. Each invocation produces exactly one cell. Dax was initially developed for the GPU, but now supports OpenMP via Thrust as well as Intel TBB. Also notice that in the initial paper [START_REF] Moreland | Dax toolkit: A proposed framework for data analysis and visualization at extreme scale[END_REF] Dax relied on a data-flow model where worklets were assembled into a direct acyclic graph, the framework having the possibility to perform some optimizations when scheduling the different processing steps. But this approach was abandoned in favor of an explicit sequential pipe-line under the control of the user without further automatic optimization. Both Dax and Piston find that the traditional VTK pipe-line tends to prevent an efficient execution of the different steps on massively parallel architectures.

EAVL [eav,[START_REF] Meredith | Eavl: The extremescale analysis and visualization library[END_REF] similarly focuses on data parallel operators. EAVL adopts a functor/iterator model where a functor encodes an operation and an iterator defines an execution pattern. EAVL main originality comes from the data model. Data layouts stay under the explicit control of the user, but it departs from the traditional VTK model by offering much more flexibility. This model is based on sets of coordinates objects and sets of cell objects. A separate logical structure object describes the basis of arrangement for the points or cells. Additionally a set of fields can be associated with some parts of the mesh. The goal of this data model is to enable to design memory efficient data structures according to the target architecture as well as to support non traditional data sets. EAVL also supports MPI parallelization and parallel file readers for formats like Silo, BOV and NetCDF. On these aspects though the information we found did not enabled us to have a clear understanding of the approach proposed. Current EAVL implementation supports CUDA and OpenMP backends.

DIY [PRG + 11] ("Do-It-Yourself" Parallel Analysis) is also part of the VTK-m suite, but takes a different approach. DIY focuses on large scale distributed memory parallelization relying on MPI as communication library. DIY does not address the fine grain thread parallelism that may be required at a node level. The goal of DIY is to provide patterns of data movements for supporting the parallel implementation of analysis and visualization algorithms. The user work in a familiar C/C++/Fortran environment with a MPI like view of its computing infrastructure. The data sets are partitioned by DIY (using the Zoltan library) into blocks respecting the requirements expressed by the user (need for ghost cells for in instance), DIY taking care of actually distributing these blocks to processes and performing some dynamics load balancing if required. Thus, the user does not need to explicitly map blocks to resources. He expresses his algorithm through operations on blocks and request communications between blocks rather than processes. DIY provides several collective block level communication routines like DIY_Exchange_neighbors or DIY_Merge_blocks. The implementation relying on modern algorithms like radix-k for tree-based merging. Notice that to identify the required communication pattern, Peterka et al. provide in this paper an analysis of the different classes of visualization algorithms in terms of data movements. Similarly the paper by Moreland et al. [START_REF] Moreland | A classification of scientific visualization algorithms for massive threading[END_REF] propose a classification of visualization algorithms but with a thread level parallelization in mind.

The Work-Stealing Paradigm

Work-stealing is emerging as an alternative of choice for shared memory programming. Relying on a dynamic load balancing runtime, these libraries can cope with irregular applications and unsteady core availability. They also propose a programming model based on tasks and not threads to delimit the potential parallelism. The runtime thus takes care of distributing these tasks on the processing cores, relying on low overhead mechanisms, like a distributed task heap.

Let us remind the base concepts of task based programming and work stealing. The programmer expresses the potentiel parallelism in his code by delimiting tasks that can be executed concurrently. Tasks can be created dynamically. Each processing core maintains a list of tasks. When a core generates a task, it pushes it in its local list. A task of this list becomes ready to be executed once synchronization constraints have been resolved. When a core becomes idle (no local task left), it randomly selects another target core and steals part of the tasks ready to be executed in this core's task list. If no task can be stolen, an other victim is targeted. This scheduling algorithm has proven performance [START_REF] Blumofe | Scheduling multithreaded computations by work stealing[END_REF]. Today several parallel programming environments are task based like Cilk [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF], TBB [START_REF] Reinders | Intel threading building blocks[END_REF] or X-KAAPI [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF][START_REF] Le Mentec | X-Kaapi C programming interface[END_REF]. They also come with higher level constructions easing the parallelisation of common patterns (loop with independent iterations for instance). Their implementations ensure high performance on multicore processors and shared memory machines.

The OpenMP standard, initially focused on loop parallelization, support tasks without dependencies since version 3 and with dependencies since version 4. Several OpenMP runtimes rely on work stealing schedulers. The OpenMP [START_REF]OpenMP application programming interface version 4[END_REF] standard relies on code annotations that the programmer uses to identify possible sources of parallelism, e.g. indicating when the iterations of a loop are independent and can thus be executed concurrently. Then the compiler and runtime can extract parallelism. OpenMP 4.0 has also taken care of heterogeneous architectures, by adding the target construct, which enable offloading to accelerators, such as GPU or Xeon Phi. From a scheduling point-of-view, OpenMP gives the choice to use both static and dynamic scheduling, and also the possibility to use the runtime's default scheduler. Current tasks implementations are not totally mature but quite encouraging, as shown in [VBB + 14]. OpenMP compatibility is also provided by some work-stealing libraries, such as X-KAAPI [START_REF] Broquedis | Libkomp, an efficient openmp runtime system for both fork-join and data flow paradigms[END_REF] or StarPU [dt] which support OpenMP 3.1 and above. Inria Some scientific visualization frameworks like Dax or Piston indirectly rely on work stealing, but do not expose tasks in their programming model that fits to a data parallel model. Some papers like [START_REF] Tchiboukdjian | Cache-efficient parallel isosurface extraction for shared cache multicores[END_REF] or [START_REF] Ingo | Fast construction of sah bvhs on the intel many integrated core (mic) architecture[END_REF] have intended to fully take benefit of the task model for fine tuning some visualization algorithms.

Work-stealing has also been experimented for balancing the work load in between the different cores of a GPU for some specific algorithms like octree construction for particle sorting [START_REF] Cederman | On dynamic load balancing on graphics processors[END_REF]. But the GPU not being fully programmable (scheduler in particular), no full fledged task based programming model and runtime has been developed on such architecture as far as we know. This is not the case on Xeon Phi accelerator that support Cilk and TBB for instance.

Parallelization of VTK Algorithms

Our goal is to identify patterns of code within VTK filters that appears to be good candidates for parallelization. The pattern we focused on are described in the following sections.

The first and most simple one is the loop with independent iterations. VTK filters mainly iterate over cells and/or points to compute their output. Since the computation for an iteration does not need results from previous ones, parallelization of this pattern is pretty straightforward. Indeed, each iteration can be seen as an independent task to compute. The runtime system is then responsible for efficiently schedule these tasks over all the available computing resources. We implement this pattern using a ForEach construct. This way, algorithms that can predict the size of their outputs can directly rely on ForEach constructs without any further effort. Some filters produce an amount of output data that cannot be determined beforehand. In such cases we use a different approach : the strategy for these algorithms is to have each thread to perform its own computation in a private space, called Thread Local Storage, followed by a parallel merge operation. Since this operation does not exist in a sequential execution, it has to be very efficient in order to limit parallel overhead.

The last pattern we study in this paper concerns acceleration data structures. Such structures are often implemented as trees (binary trees, octrees, kD-trees. . . ). We experimented a parallelization of a generic tree traversal. Given a few set of operations that a tree needs to implement, we guaranty its traversal in parallel with respect to its sequential depth first execution and branch cutting capabilities.

ForEach

Given some requirements, iteration over independent loop is very easy to parallelize. Indeed, using n as the size of the loop, one can see such loop as n independent tasks. Thus giving each core n numberofcores elements to compute is the easiest way to parallelize this pattern. However this approach can lead to load imbalance issues. If a few iterations take much more time than the others, some cores may finish their computation before the others and have to wait for them. Dynamic scheduling and work-stealing techniques can efficiently reduce these problems.

But giving work to each processor is not the only thing to care when dealing with independent loops. One has to make sure to allocate enough memory for output data structures and to use thread-safe methods while computing each element. Moreover, handling writing offset may be a non-trivial task. Thus these aspects are left to the user. Our plugin guaranties to divide the loop's iteration range the best way according to the chosen runtime.

Our plugin provides the vtkSMPTools::For operator. As for Intel TBB's tbb::parallel_for, one has to move the sequential body of the loop into a freshly build class (e.g. figure 1). It has the advantage to separate the algorithm (the pattern) and the computation. It also exhibits pieces of code that need to be carefully managed (memory allocation, thread safe methods, etc.). Writing the class is a matter of checking the sequential behaviour. To call the operator one only needs the range of the computation and an instance of the aforementioned class. This operator can be found in the vtkCommonCore module as well as every abstraction layer (in specific directories) for each supported runtime.

Grain Tuning

When the operator's work is very regular, we face a scalability issue due to steals. Indeed, each steal adds a little overhead to the computation, and generates transfers on the memory bus to retrieve suitable data. The number of steals can grow significantly as we get closer to the end of the computation.

These steals grabbing a small work load tend to induce more overhead than computation speed-up. To avoid the performance drops occurring with this behavior, the work-stealing scheduler defines a threshold representing the minimal range for a computation, i.e. the grain. The problem is thus to set the grain to its optimal value : if the grain is too coarse, load balancing becomes ineffective, and if the grain is too fine, load balancing induces too much overhead. Previous studies [START_REF] Victor | Work-preserving speed-up of parallel matrix computations[END_REF] showed that the maximum amount of parallelism reachable is when the grain is Q( p n). Indeed the number of tasks created is, at most, n grain and these tasks are limited to a range containing at least grain iterations. Thus the critical path (i.e. the sequential part of the computation) is Q(grain + n grain ). The optimum of this function appears when the grain reaches p n. Experiments confirm that a p n grain leads to the best performances.

Thread Local Storage and Merge

Failing to meet the requirements for the ForEach pattern is often due to the impossibility of knowing the size of the output without actually performing the computation. For such algorithms, and those who fails at using thread-safe methods, there is still a possibility to use the ForEach.

The idea behind this second approach is to use private output data structures per core. This way, parallel execution is closer to the sequential one and restrictions for thread-safe methods are less strict. There is some drawbacks :

• these data structures need to be initialized efficiently;

• each of these data structures will contain partial results that will need to be merged afterward. Inria

Initialization

These templated structures, called Thread Local Storage (TLS), provide a Local() method that creates a new object if needed and ensures that each thread accesses its own separate object. These structures are intended to be used within parallel operators to ensure that each thread writes data in separate memory space. Due to some runtimes limitations, using such structures outside of a parallel operator might not give the expected results.

We provide two classes that implements TLS : vtkSMPThreadLocal and vtkSMPThreadLocalObject. The former is intended to manage generic data and the latter is designed for vtkObjects. It takes care of reference counting, so one does not have to register the objects if he does not need to access them when the TLS is destroyed.

For performance reasons, objects for a particular thread within a TLS are not constructed until they are first accessed. There is no built-in way to tell if an access is the first one or not. Therefore if a code relies on initializing a per-thread data structure once, and using it assuming it is initialized, then it will have to keep track of whether or not such structure is initialized. Since it is so common to do so, functors can embed an Init and a Reduce method. If both methods exists, the Init one is executed once per thread before any computation, and the Reduce one is executed once the functor iterates over each element of the computation. Thus, with a well written Init method, the operator() can assume that every data structure used has been initialized properly.

Such capabilities are also useful in case of severe load from other jobs. When cores are so loaded that they could not perform a steal, they do not attempt to initialize their TLS, leading to time sparing.

Code for these TLS is also found in the vtkCommonCore module.

Merge

Once initialization is done and actual computation performs in parallel, each TLS contains a part of the final expected result. Since this result is often a mesh, our plugin provides capabilities to fuse partial meshes into a single one. This is performed in parallel for efficiency reasons. This operation cannot mimic the behaviour of vtkAppendFilter, which sticks together the points and cells of several meshes, because of duplicates points at the border of each partial meshes. If we kept all those points in the output of the filter, the mesh would lose its manifoldness (if any). Results would give strange outputs when filtered through decimation or subdivision, for example.

To track and remove duplicates points of partial meshes, we used VTK built-in Locators. We extended the behaviour of vtkMergePoints to support parallel operations. Basically, this locator keeps track of existent points thanks to a spatially-guided hash table. The bounding box of the resulting mesh is regularly divided into a 3D grid and each voxel of this grid is mapped to an entry in the table. Each entry stores the indices of the points that belongs to this voxel. Knowing the index of the entry associated to a point requires simple mathematics involving point and bounding box coordinates.

The simplest use of our locator for a parallel merge of all partial meshes is, for each thread, to insert their points one by one into the locator. This solution obviously produces wrong results if no care is taken. Our solution is to use an hash table of mutexes, in addition to the one dedicated to points ids, as shown in figure 2. Each insertion of point is thus preceded by a lock operation. Since conflicts only occurs for points that lay on the boundary of a mesh, overheads are still low. However, memory footprint is twice as important as the sequential object.

Using only one locator in the case of filters that already need one per thread is not highly productive. So we used the idea from flat combining [START_REF] Hendler | Flat combining and the synchronization-parallelism tradeoff[END_REF] to benefit from these arrays of buckets1 . With an iteration over each voxel, one thread can merge all equivalent buckets in a row. Locks that were protecting voxels from concurrent accesses are thus no longer needed. The only requirement that is still present is the need of an atomic increment on the number of points in the output vtkPoints. But this approach imposes a constraint to our framework : a thread must be able to retrieve data from any other. Moreover our case-study shows that more than 90% of the buckets are empty. Taking care of these two particularities leads to initiating the merge of voxel's buckets only by a thread which actually has data in these buckets.

To do so, each thread looks for the first non-empty bucket it owns. If no other thread already merged the buckets associated to the same voxel, it retrieves the data associated to this voxel from the other threads, and performs the merge in the output data structures. Otherwise it discards this bucket and look for the next one which contains data.

Our framework provides both merge capabilities. Filters that use a locator to produce their output points usually end up using thread local locator while parallelized. In such cases, the last technique can use the locator to perform point insertion bucket by bucket. Otherwise the function build a new locator and uses it as described for the first technique.

Acceleration Data Structures

Due to their inner complexity, several algorithms have an accelerated version. It mainly consists of the addition of a data structure that will ease computation. The purpose of this structure is to decrease the amount of data that needs to be analyzed. They are not automatically used because they may introduce overhead for their initialization, or increase the memory footprint. But what makes them efficient is that they speed up the computation of the algorithm each time they are used. Best results are thus obtained when data are requested several times, with different values.

In the case of our study we focused on trees, which are common acceleration data structures in the visualization field. Their aim is to reduce the size of the iteration over the end-elements (cells, pixels, objects, 3D space) by cutting unproductive content.

Use of trees can be accelerated at two different steps. The first one is when building the tree. But since this step is highly dependent on the type of the tree and its usage, it might be a per-implementation study. The second one is during the tree traversal. This one is much more easy to provide as a generic operator, since the traversal can be seen as a sequence of node indices to explore.

One cannot simply build this sequence and apply our ForEach on it : indeed each node must be treated after its ancestor has finished its computation. And in most cases, the computation of a node may result Inria in the choice of not going further in the exploration of its descendants.

A simple solution is to use tasks spawning on each node. That is :

• the computation of a node is considered as a task;

• each node creates a task per descendant that need to be explored;

• these tasks are spawned and the runtime is then responsible of an efficient scheduling policy;

• the tree traversal starts with the spawn of the root task.

First levels are quite slow to traverse since there are fewer tasks than available resources, but the number of tasks is rapidly increasing and they can be efficiently scheduled on the whole machine.

Adaptive tasks

Creating much more tasks than available computational resources is a good way to simplify the scheduling policy and balance the work load. But it has a cost : creating and managing tasks may become costly compared to the actual computation of a task, especially in visualization where nodes often perform only a few comparisons to decide whether or not they should spawn their descendants.

The answer of some work-stealing runtimes such as TBB or X-KAAPI is to provide a way for creating adaptive tasks. Such tasks have the particularity to be splittable on demand by an idle resource, thus limiting the number of created tasks to the number of cores actually executing them.

Using these tasks, we propose an adaptive tree traversal which behaves as follow :

• Create a task that traverses the entire tree and start the (sequential) execution;

• On a demand for splitting the task, find the top-most untreated node that would be the last computed in sequential depth-first order;

• Consider this node and its sub-tree as treated and create a task that traverse this sub-tree.

Newly created tasks behave like a fresh tree and their traversal follows the same rules as above. Thus they can also be split if a processor is idle. In this scheme, the number of splits that occurs (i.e. the total number of tasks created) is Q(number of processors) which may be much less than the number of traversed nodes.

Experimental Results

Following sections provides results for our operators based on the parallelization of two VTK filters.

Evaluation Platform

We conducted our experiments on a CC-NUMA machine made of AMD Magny Cours processors holding 12 cores each. Each processor is divided into two chips of 6 cores each. The machine has 4 sockets for a total of 48 cores. Figure 3 shows the internal organization of a socket obtained thanks to the HWLOC [BCOM + 10] library. Each socket, or node, is made of two 6-core processors. Each core has access to 64 KB of L1 cache, 512 KB of L2 cache and 5 MB of L3 cache. The first two caches are private while the third one is shared between the 6 cores of a chip from a Magny Cours processor. A 32 GB memory bank is attached to each processor of this platform for a total of 256 GB of main memory. We will refer to this configuration as AMD48 in the following of this section. Our input dataset comes from the Stanford 3D Scanning Repository2 . It is the Lucy mesh that contains 28 M cells (triangles) for 14 M points. We load it as a vtkPolyData object and provide it with point normals to test specific behaviour of vtkTransformFilter.

vtkTransformFilter

An example of VTK algorithm that performs a loop with independent iterations over cells and/or points is the vtkTransformFilter. It applies scales, translations and rotations on a mesh. The computation is performed by a vtkTransform that contains the description of the transformations to be applied. The vtkTransform is supplied to the vtkTransformFilter, and iterates on the input data to produce the output.

We modified vtkTransformFilter to perform the needed memory management before every computation, and we built the vtkSMPTransform class which mimic the behaviour of the vtkTransform, except that the sequential loop was turned into a parallel ForEach.

Figure 4a shows the performance obtained on our AMD48 machine. AMD48 is a NUMA machine with shared memory, so we additionally studied the influence of data placement. Since memory pages of output data are touched only after each point or cell transform computation, we put two vtkTransform-Filter in a row in our visualization benchmark. As a consequence, the first filter load data from a unique memory node, leading to memory contention, and the second one has the memory pages of its input data interleaved on each memory node thanks to the first filter. Thus the second filter makes a better usage of memory bandwidth. Results are shown in figure 4b.

As expected, mapping the data close to their computing core enhances speed-up and drops memory contention. Results also show that work-stealing runtimes are at least as efficient as OpenMP for highly regular loops -which is known to be the stomping ground of the latter. Moreover, a side effect of work-stealing runtimes is that they tend to smooth the memory contention issue.

vtkContourFilter

A widely-used filter that cannot calculate the size of its output structure before the actual computation is the vtkContourFilter. Its purpose is to compute one or several isosurfaces on any kind of datasets. In its current implementation, vtkContourFilter is mainly a switch between several specific implementations depending on the type of the input dataset. The implementation parallelized in this study is the generic one, which is applied if the input dataset does not have a specific algorithm that handles it.

The algorithm works as follows:

• for each cell in the mesh, compare the scalar values associated to the points of this cell with the isovalue being computed;

• if the isovalue is either above the maximum or below the minimum of these values, do not compute anything;

• otherwise create the part of the output mesh that correspond to the values pattern.

Since the created portion of the output mesh depends on both the scalar distribution above and below the isovalue and the topology of the cell, it is not possible to know how many points and cells3 will be created per input cell. The parallelized version of vtkContourFilter thus makes use of TLS and fuse the partial pieces of mesh. Figure 5 shows the execution of the surface creation (with merge) on our AMD48 platform. Speedups are computed against the sequential for loop execution time. Since isocontouring is an algorithm that can often face load balancing issues, in this experiment we provided a very high load-imbalanced input dataset.

To do so we computed scalars values in such a way that only a few first cells can possibly contain points whose scalar values are both above and below the isovalues. Thus using a static partitioning of the iteration range leads to the first core being the only one to create the output mesh. As expected, work-stealing runtimes have a better load balancing and outperforms the static partitioning of OpenMP. Moreover, dynamic scheduling tuned with the right chunk-size (grain) gives similar results.

Focus on the Merge Operator

The vtkContourFilter is a good place to experiment the behaviour of our Merge operator, since the isosurface computation makes use of one locator per thread.

Figure 6 plots the execution time for both merge implementations. The method using one locator per thread is faster than the one using only one global locator. It also requires twice as less memory since the array of vtkMutexLock is not required in this case. There is one drawback though : all the parallelized filters that would make use of the Merge operator could not be able to use a thread local locator.

Accelerated vtkContourFilter

We tested our parallel acceleration tree with the classical min-max tree used for isosurface extraction. A min-max tree stores at each node the min and max values of all scalar values contained in its sub tree. The tree is built in a bottom-up fashion after choosing a size for leaves, i.e. the number of points associated to each leaf. If the isovalue is not included in the min-max interval of a given node, no further test is needed for all the points of the sub-tree.

As stated earlier, such data structure shows its power when reused several times on the same input. Indeed, extrema on each node do not depend on the isovalue being computed.

Results presented in figure 7 show the difference between the task spawning technique and the workstealing one. In this experiment we computed 11 isovalues through our input mesh, with the accelerated version of the vtkContourFilter. The speed-up is for the parallel traversal and merge time, computed against the sequential traversal time.

Even if the overhead for the creation of one task is very low, our parallel tree traversal is slightly better. This is due to the number of tasks created, which depends on the number of computational resources and not on the size of the input.

Discussion

The Pipe-line Model

Is the VTK pipe-line model not adapted to large scale parallelism ? We made some attempts to enable pipe-line parallelism for multi-block datasets. These blocks can safely be processed in parallel. By default, even if a filter is parallelized, it cannot start processing a block if all blocks have not been processed by the upstream filter. The filter needs to have the full data set available before to start. This creates an implicit synchronization between each filter. Our goal was to remove this synchronization to enable a filter to process a block as soon as available. A VTK feature prevented good performance though. The vtkTimeStamp class, used within every vtkObject is widely used during filters execution. Our first implementation using a global counter increment led to incorrect results. Using an atomic counter increment to solve this issue was inefficient due to the high number of operations involved in parallel. To address this issue, a solution was to deactivate the use of vtkTimeStamp during the executive parallel operation. But it can not be a global deactivation because some features (such as updating the bounding box of the output dataset) rely on it. The final solution was to deactivate it only for vtkInformation object because they were the one causing the most update on their vtkTimeStamp. But parallelizing vtkCompositeDataPipeline with this approach has an inherent weakness related to cache consistency. Each time a dataset reaches such parallel executive, it is processed, block by block, until all the data went though the filter. Not only it creates a synchronisation point that can lead to overheads if load balancing fails, but it also does not take into account the fact that each output block will be reused as an input by the next filter, ruining cache consistency.

The VTK-m approaches all went away from this model for a simpler one. One motivation is that encapsulation in opaque filters prevents an efficient control on the data movements between filters, or more precisely to correctly handle the task/data affinity. The model also tends to favor the sequence of short filters, while efficient parallelizations rather call for long parallel sequences with as few as possible synchronization, communication and sequential section phases. This is a major performance issue that will very likely worsen on next generation architectures. The programming model should be designed such that the programmer be aware and able to master the main performance pitfalls.

Data Parallel versus Task Parallel Programming

The data parallel paradigm is adopted by DAX, EAVL and PISTON. The reasons are twofolds: many operations related to scientific visualization are data parallel [START_REF] Moreland | A classification of scientific visualization algorithms for massive threading[END_REF]; and GPUs have demonstrated that this model could lead to high performance at a good flop/watt ratio.

We believe that task-based programming as developed for Cilk, TBB or OpenMP is a better option. First, they support all data parallel operations, but also enable to express less regular patterns with tasks that can be efficiently executed with work-stealing runtimes. One major limitation is that GPU's, as designed by NVIDIA or AMD, do not enable task based programming. The scheduler is not exposed and not programmable. The GPU processors have a double parallelism level associating a number of streaming multiprocessors that run asynchronously, each one executing synchronous threads. Thus, a task model could be supported by GPUsl as demonstrated by [START_REF] Cederman | On dynamic load balancing on graphics processors[END_REF][START_REF] Toss | A new programming paradigm for gpgpu[END_REF], but so far vendors did not follow that path.

An other point of view is to argue that next generation chips, being CPU or GPU based, will support multiple cores, each core executing vector/SIMD instructions. Even if compilation technologies have progressed to automatically fill vector units, efficient programming still needs human involvement. Programming directly with data parallelism enable to expose to the user only one level of parallelism. In opposite, task based programming needs to be complemented with vector programming inside tasks to reach high performance, as it is for instance the case with the Xeon Phi accelerator. Even if data parallelism efficiency and simplicity fade away for irregular applications (this includes many acceleration data structures used in computer graphics), wasting some compute cycles may not be so critical given that we will have an abundance of threads.

Memory Layouts and Data Movements

Often scientific visualization algorithms are data intensive. Data layout and data movements have in this case a significant impact on performance on NUMA architecture given the complexity of their memory Inria hierarchy. Similar issue occurs on GPUs where the user needs to explicitly manage most of the data movements between the different memory levels. Non of the VTK-m solution really addresses this problem in their model. EAVL offers a very flexible data structure model that can favor efficient mapping on the target architecture, but it does not expose some specific memory model. Work-stealing approaches, like TBB and Cilk, often consider that the underlying model is a uniform shared memory with a local cache per worker. Given the random nature of work stealing, the user does not know in advance who does what. Some attempts have been made to propose some architecture aware stealing policies [TDG + 10, DBGR13] or alternative, more cache efficient, dynamics scheduling policies [START_REF] Blelloch | Provably efficient scheduling for languages with fine-grained parallelism[END_REF]. For instance in [START_REF] Durand | An Efficient OpenMP Loop Scheduler for Irregular Applications on Large-Scale NUMA Machines[END_REF] the authors propose a two level stealing policy with KAAPI where an idle worker attempts to first steal work from other workers running on the same socket, before stealing to a distant socket. But so far such ideas has not made their way into main stream programming environments.

In OpenMP, the OMP_PLACES environment variable gives the user the possibility to define a set of "places" corresponding to specific hardware threads. One can also use several abstract names, such as cores or sockets, if he wants places to respectively match cores or sockets on the target machine. For each parallel region, a team of threads is created to execute it, and the user can then use the proc_bind clause to specify how he wants the threads to be dispatched among the places (e.g. close to have the thread mapped as close as possible of the master thread, or spread to have a sparse distribution of the threads among the places).

I/Os

Through the various experiments we performed, we noticed that one bottleneck comes from reading the input data from files. VTK reader are single threaded. Given the default first touch policy Linux uses, all read data are thus stored in the memory bank attached to the processor that actually reads the file. The first filter operating on these data, even if efficiently parallelized, will need to have all its threads access the same memory bank, leading to some performance degradation. This effect can be mitigated by forcing a different policy (with a tool like bind for instance). We tried to parallelize a reader but encountered thread-safety issues. A pragmatic approach is to rely on the MPI parallelization of VTK, having one MPI process per socket and a thread-level filter parallelization operating on each socket. This brings some dynamics load balancing capabilities within each socket with the advantage of having all data local to each socket, i.e. to the local memory bank, while enabling parallel file reading between sockets.

In-situ processing brings a different perspective on this issue. In that case data are not read from disk, but are directly provided by the simulation processes running locally on the node. If some visualization algorithms are executed locally on each node, having load balancing capabilities may improve the use of the local resources shared by the simulation and the in-situ processings (given that an asynchronous approach is enabled).

Conclusion

We presented the basis of a framework for VTK that aims at creating parallel filters. It targets multi-cores platforms and takes advantage of reusability of sequential code. It relie on the task-based programming paradigm and on work-stealing runtimes.

This work led to the development of a new module, named vtkFiltersSMP, integrated into VTK version 6. Technical details are available through following wiki http://www.vtk.org/Wiki/VTK/VTK_ SMP.

This work is concomitant with other initiatives exploring new frameworks for large scale parallel analytics and visualization like the VTK-m software suite. Most of these approaches adopt a data parallel approach, that fit well the GPU architecture. To our opinion a task-based approach is more flexible, and today good runtimes, based on work-stealing, ensure a high performance. Such model is already fully supported on Xeon Phi accelerators. GPUs are made of asynchronous cores, but the exposed programming model does not enable to support properly and efficiently such model so far. In both cases, CPUs or GPUs, we believe that it is difficult to avoid a two level parallelization model, one for distributing work to cores and an other one to load the vector/SIMD units each core owns. Given the limited size of these vector units, the algorithms that are efficient at this scale are not the same than the one relevant at large scale.

Other issues remains, like developing a sound memory model that is not to complex for the programmer while still exposing enough key architecture features to lead to efficient programs. On this aspect the CPU and GPU differ deeply, making the development of a common layer difficult. Another issue is the distributed programming level, a world today dominated by MPI. We can underline some attempts to propose alternative models like the Swift/T [WAW + 13] environment relying on a taks-based programming model with a work stealing strategy for work load distribution.

}Figure 1 :

 1 Figure 1: Implementation of the parallel vtkTransform::TransformVectors(...).

Figure 2 :

 2 Figure 2: Inner representation of vtkMergePoints (left) and our first implementation of vtkSMPMerge-Points (right). Each vtkIdList is designated as bucket.

Figure 3 :

 3 Figure 3: A socket from the AMD48 evaluation platform.

  First filter (input data on a unique NUMA node). Second filter (input data interleaved on all NUMA nodes).

Figure 4 :

 4 Figure 4: Speedups for execution of parallelized loops within vtkTransformFilter. Comparison between several runtimes of the execution of the ForEach loop vs. the sequential for loop.

Figure 5 :

 5 Figure5: Speed-ups for execution of parallelized loop within vtkContourFilter. The difference between the runtimes is due to the high load of the first core.

  Figure 6: Comparison of our two merge implementations.

Figure 7 :

 7 Figure 7: Execution time speed-up of vtkContourFilter, with our parallel tree traversal.

RR n°8245

A bucket represents a vtkIdList in a voxel.RR n°8245

http://graphics.stanford.edu/data/3Dscanrep/ Inria

One or several points, one or two lines, one or two triangles. . .RR n°8245

This work has been partly funded by EDF * Inria † Grenoble INP ‡ EDF

Aknowledgments

The development of VTKSMP has been partly funded by EDF R&D. This research report is an extension of the paper [EBG + 13]. This extension work has been funded by CEA.


Contemporary ethnographic practice and the value of serendipity

Isabelle Rivoal (Laboratoire d'Ethnologie et de Sociologie comparative -CNRS / Univ. Paris Ouest Nanterre la Défense) Noel Salazar (University of Leeuwen) Serendipity, 'the art of making an unsought finding' (Van Andel 1994: 631), as juxtaposed to purposeful discovery by experiment or retrospective prophecy, is a much sought after ideal in scientific practice [START_REF] Kirk | Reliability and validity in qualitative research[END_REF]. The eighteenthcentury English novelist Horace Walpole is believed to have coined the term, based on a Persian fairy tale, The Three Princes of Serendip, in which the main characters travel around making fantastic and unexpected discoveries (Bourcier and van Andel 2011: 41). Importantly, Walpole not only stressed the element of fortune or chance as part of the experience, but also that the discoverer needs to be 'sagacious' (knowledgeable) enough to link together apparently innocuous elements in order to come to a valuable conclusion or insight [START_REF] Merton | The bearing of empirical research upon the development of social theory[END_REF][START_REF] Merton | The travels and adventures of serendipity: A study in historical semantics and the sociology of science[END_REF]). While serendipity is often misunderstood as referring only to the accidental nature and the delight and surprise of something unexpected, the masterful synthesis into insight by drawing (novel) connections is equally important [START_REF] Fine | Three principles of Serendip: Insight, chance, and discovery in qualitative research[END_REF]. This requires sufficient background knowledge, an inquisitive mind, creative thinking and good timing. As it involves both chance and sagacity, serendipity has been paraphrased as 'accidental wisdom' [START_REF] Calhoun | Accidental wisdom: Robert Merton's serendipitous findings[END_REF]).

Serendipity has a long history in science as having played a key role in many significant discoveries. Decades ago, sociologist Robert Merton described the 'serendipity component' in qualitative research, a pattern that 'involves the unanticipated, anomalous and strategic datum which exerts pressure upon the investigator for a new direction of inquiry which extends theory' (Merton 1948: 506). This line of thinking inspired Barney Glaser and Anselm Strauss (1967) to develop serendipity as a scientific method in their 'grounded theory'. They widely diffused the idea that fruitful empirical research not only tests theoretically derived hypotheses; it also originates new ones. Their basic argument is that research questions should be defined narrowly enough so that the research remains focused and broadly enough to allow for flexibility and serendipity (based on a combination of both chance and intuitive reasoning).

In anthropology, serendipity, together with reflexivity and openness, is widely accepted as a key characteristic (and strength) of the ethnographic method.

According to Frank Pieke, it even is 'the essence of fieldwork research ' (2000: 138).

The epistemological weight placed on serendipity in anthropology differs from the mere sagacious discovery Walpole described because it not only refers to an advantageous by-product of (participant) observation but is also deemed to shape the ethnographic process. Put differently, 'anthropologists are trained to observe what they are not prepared to see, [and] it is their main competence' (Olivier de Sardan 1995: 77). Indeed, the embodied capacity to 'conceptual distance', before starting reflexive interpretations, has long been the hallmark of the anthropological method.

Marcel Mauss, for instance, argued that without being aware of one's own 'sociological perception' there can be no understanding: 'The young ethnographer embarking upon fieldwork must be aware of what he or she knows already, in order to bring to light what is not yet known ' (2007: 8). Serendipity has become a convenient notion to point out the very experience of suddenly coming to 'see' something which had previously been out of sight: the striking realisation that 'this is what it is about' ethnographic narratives refer to as the 'Geertzian moment' (cf. [START_REF] Geertz | The interpretation of cultures: Selected essays[END_REF].

Over the past few decades, following the call for an epistemological deconstruction of fieldwork as both a geographical, temporal and social unity of study and a narrative of cultural encounter (Clifford and Marcus 1986), numerous anthropologists have criticized the traditional approach to ethnographic fieldwork and writing. Relating this criticism to serendipity, two anthropologists recently published an edited volume entitled Serendipity in Anthropological Research: The Nomadic Turn (Hazan and Hertzog 2011). As the back cover explains, the book 'conceives of anthropological research as a lifelong nomadic journey of discovery in which the world yields an infinite number of unexplored issues and innumerable ways of studying them, each study producing its own questions and demanding its own methodologies'. The authors advocate for ethnographic fieldwork to change from a quest for alternative social and cultural cosmologies into a journey for exploring unexplored issues. Such propositions indicate that the focus of anthropological knowledge seems, indeed, to be shifting, raising questions about what the discipline is all about.

In this special issue, we want to point out some of the changes in the framing of contemporary ethnographic research, with a shifting focus from place to time, from journeys to projects and situations, and from (expected) discoveries to methodological creativity. Rooted in the intellectual endeavour of investigating human unity through cultural diversity, anthropology has long focused on descriptions of 'Otherness'. Ethnographers who enter the discipline today, however, are more concerned with 'the challenge of the contemporary', to quote Dalsgaard (this issue). The challenge is to know how the people under study will manage to (re)invent sociocultural forms that suit the rapidly changing (global) context in which they liveand possibly find ethnographic vantage points to describe this.

Fieldwork as a serendipitous journey, or not any longer?

It seems that one of the prominent challenges for 'doing ethnography' nowadays is the uncertainty related to the definition of 'fieldwork', set to explore temporalities and their social refraction in people's livesbe it modern bureaucracies and regulations in detention centres, as in Le Courant's research, legal processes and the assertion of First Nations against modern states, as in Giabiconi's case, or craft and time in New Papua Guinea's politics, as in Dalsgaard's study (all in this issue). Field boundaries have often become looser than they were before and young scholars express uneasiness in adjusting to this 'situation' (Fogel and Rivoal 2009). All three articles in this special issue thoroughly reflect on the idea of gaining access to 'the field' and the disquiet felt with any requested compromise. According to Dalsgaard, fieldwork 'emerges', for Giabiconi, one has to find the key to 'enter' the field, while it is more a matter of 'learning and practice' in Le Courant's experience. Clearly, fieldwork is multi-dimensional, requiring ethnographers to weave place, time and context together in ways that make any attempt at defining fieldwork in methodological terms difficult.

Serendipitous research requires 'time'making time to observe, understand and ponder, and stretching time, if needed, to go back and forth between the traditionally separated periods of data gathering and analysisbut this is a dimension of time that Dalsgaard brands as too linear to account for research loops. In the context of contemporary challenges, ethnographic intuition takes on temporal inflexions, much like the curiosity towards a peculiar or unfamiliar concatenation of events or circumstances. Serendipitous discoveries may be equated to 'epiphanies' [START_REF] Garratt | Régime of truth' as a serendipitous event: An essay concerning the relationship between research data and the generation of ideas[END_REF] or, on the contrary, be seen as knowledgeably constructed affordances. Reflecting on the role of improvisation in jazz music, for example, Denis Laborde (2011: 153) suggests that serendipity is not only about meanings and situations, but may as well account for creating the illusion of spontaneity. In research, serendipity as such cannot be really 'planned', but the conditions facilitating the process can be manipulated.

There has always been a tendency in anthropology for the 'field' to shape the research design, rather than the other way around. Accidental sagacity has been intimately bound up with innovation in anthropology and beyond (Hazan and Hertzog 2011). It may seem ironic, but disasters often offer great potential for what Pertti and Gretel Pelto have called 'serendipity, disguised as catastrophe ' (1978: 185).

While conducting ethnographic fieldwork on cultural mobility in Yogyakarta, Indonesia, Noel Salazar (2010a) had to endure a volcanic eruption, a major earthquake and a minor tsunami. This series of unfortunate (and certainly unexpected) events heavily disrupted his original research plans but offered him Many scholars, including anthropologists, agree that the current sociopolitical and economic context in which science and knowledge production is embedded has induced undesired transformations in how academics in general have to work. Questions about how quickly science can produce new knowledge and innovation have become a widely acknowledged concern [START_REF] Pels | Unhastening science: Autonomy and reflexivity in the social theory of knowledge[END_REF]. Much of the current critique revolves around the managerial and entrepreneurial performance culture that pervades the academic landscape today. The call of slow science advocates, however, is not necessarily one for more serendipity because that would imply stressing not only the need for more time (to increase the likelihood of chance events to occur) but also the need for better scientific training and excellence (to increase sagacity).

The three princes of Serendip

The critical task for the future is how to make what is generated by the exemplary works of established scholars through a rhetoric of serendipity, opportunity, and circumstantial, unexpected rupture encountered in what begins as the pursuit of traditional ethnography into an alternative paradigm of ethnographic method as legitimate as the traditional one. (Marcus 2002: 198) Reflecting on the exchanges with his own graduate students, George Marcus notes that many are theoretically inspired by established scholars, but that these exemplars seldom offer a model to turn dissertations into innovative works. According to him, anthropological research is little served by the traditional rhetoric of discovery (which stresses chance but tends to omit sagaciousness), but instead must 'make method out of a rhetoric of circumstance' (Marcus 2002: 198). There will always be leaps of intuition, inferences that are not entirely supported, but anthropologists should, nonetheless, explain to their audiences, and especially to students in anthropology, how they came to their conclusions. The growing appeal of the notion of serendipity certainly highlights the lines along which contemporary scholars are endeavouring new ways of becoming anthropologists. Anthropology has already stepped outside the ivory tower of academia and being a young anthropologist entails both gaining ethnographic authority and defining one's own societal role as an anthropologist-a dilemma all authors explore convincingly in this special issue. We focus here on three points that need particular scrutiny in the light of appraising the future of the discipline.

(1) The anthropologist as neo-nomad. If we take a close look at what is advocated for by those propagating a 'nomadic turn' in anthropology (Hazan and Hertzog 2011), we see that the issue at stake is less a matter of fieldwork methods than a question of study objects and relevant research questions. The nomadic ethnographer is not set to decipher 'Otherness' anymore. Of course, this does not mean that cultures, cosmologies or alternate ways of inhabiting the world are not of interest anymore to anthropology. However, these are no longer the obvious and defined horizons of the discipline. What is at stake behind the urge for a renewed 'explorative disposition'? Such an ambitious project certainly calls for a disentanglement of the socio-cultural stances that have been the bedrock of anthropology, in order to embrace a serendipitous attitude, closer to the task Gilles Deleuze and Félix Guattari have set for philosophy, namely to create concepts (that are always novel) and to explain universals [START_REF] Deleuze | What is philosophy?[END_REF]. Exploring unknown universals seems to be at the core of the new anthropological project. Not surprisingly, such a project calls for new methodologies and a radical reappraisal of the ideal of Malinowskian-style fieldwork, designed to fit a drastically different conception of what concepts are to be held for: collective representations or a different Weltanschauung (comprehensive worldview) to be investigated and compared as a way to settle universals.

(2) The anthropologist as artist vs. activist. Is 'nomadic anthropology' challenging the anthropologist as an expert of and broker between 'cultures'? The traditional expertise of the profession has certainly dropped in value with processes of globalisation and the on-going commodification of the exoticprocesses that have been scrupulously analysed by anthropologists (Salazar 2010b). What kind of knowledge are anthropologists producing when they are accounting for what is happening, here and now, at one locality or the other? How do they handle the 'qualitative distance' necessary to conduct research as opposed to producing expertise? A couple of years ago, Marilyn Strathern made an epistemological distinction between a model of management and a model of research. She argued that both models differ in the temporal perspective they set out to address problems.

Because experts are aiming at controlling uncertainties in the present time, they focus on ways to combine things in order to resolve or transcend past divisions. Research goes in the other direction: starting from an undivided past and exploring how it spreads from a core identity and generates multiple futuresresearch is the path toward creation [START_REF] Strathern | A community of critics? Thoughts on new knowledge[END_REF]. Is serendipity, then, a new word for creativity in the social sciences? Is it a panacea to avoid the pitfall of using ethnographies as mere contemporary contextualisations for events unfolding here and there? When is cultural expertise blurring the line between anthropologists and journalists or activists? What would the future of anthropology look like if we consider anthropologists along the lines of 'serendipitous creators', trying to carve out concepts as explanations for 'the chaos out there' [START_REF] Deleuze | What is philosophy?[END_REF]?

(3) Multiple realities and methodologies: Engaging the unity of the discipline. The question at stake in this last point deals more with considerations concerning the inability of anthropologists to make themselves heard in the public arena [START_REF] Eriksen | Engaging anthropology: The case for a public presence[END_REF]). If creativity is deemed the new anthropological horizon, the methodological unity of the anthropological project is challenged. Hence the need to address the methodological question thoroughly. This goes beyond exploring new ways of doing fieldwork, reflecting on new research methods or ways of understanding. Successful ethnographies used to be based on the ability to be part of the observed social world, developing relational skills and interest in playing different roles, to the point of 'atopy'the ethnographical synthesis of multiple social positions [START_REF] Naepels | Une étrange étrangeté: Remarques sur la situation ethnographique[END_REF].

Lately, the aesthetical stance has gained power among ethnographers aimed at using their imagination as much as their training for distanced observation (Willis 2000: xi).

Fieldwork has become a mise-en-scene George Marcus says, nothing but a ready-made meta-method which only serves to enhance the solidarity of a profession that idealises itself throughout an idealised practice [START_REF] Marcus | Notes toward an ethnographic memoir of supervising graduate research through anthropology's decades of transformation[END_REF]. James Faubion echoes the charge against the fieldwork-as-a-metamethod, offering new ways to save the specificity of anthropology: it is time for anthropologists to shift from the idealisation of fieldwork and its serendipity (meaning here: having the time to carve out social relations, to soak in culture and learn to act accordingly) towards a common way of problematizing the inquiry and conceptualising its objects with another kind of serendipity [START_REF] Faubion | The ethics of fieldwork as an ethics of connectivity, or the good anthropologist (isn't what she used to be)[END_REF]. Framed by these critics, serendipity has to be conceptualised anew as part of 'experimentation', used and manipulated as a research tool or process rather than as a concept merely indicating how observation unfolds. In other words, sagacity has to be reinstated as a principal component of serendipity.

The serendipitous future of anthropology

So is there a future for exploring exciting new horizons in anthropology? While recognizing the increasing external pressures, good ethnographic work can and should never be completely orderly. It involves 'serendipity, creativity, being in the right place at the right or wrong time, much hard work, and old-fashioned luck' (Fetterman 2010: 2). Despite the changing circumstances, 'it is important to cultivate a certain willingness to seize unforeseen opportunities' as Daniel Miller suggested during the 2012 EASA Young Scholars Forum (see also this issue), a general sensibility towards ways of making anthropology out of realities which might otherwise remain mere distractions. And that also entails some readiness to 'depart from research plans and research designs that we carry into the field when we run into opportunities that simply should not be missed' (Hannerz 2006: 32). Serendipity, then, becomes 'an engine for moving anthropology forward, but at the same time it holds in store the promise and the prospect of derailing elsewhere towards other shows how such an approach unpacks, serendipitously, the relationship between fieldworker and the field as it changes over time.

In conclusion, anthropologists, whether they are seasoned seniors or freshly minted graduates, should take time and rely on the discipline's accumulated wisdom to engage with research questions that they are genuinely interested in but that also have societal relevance. The three articles of this special issue masterfully illustrate how scientific inquiry in general and ethnographic research in particular is necessarily

  instead a unique opportunity to study ethnographically the lived experience of disaster (which is rarely done, for the simple reason that such research cannot be planned on beforehand). Urged by colleagues at the University of Pennsylvania, his home institution at the time, he kept a widely read public weblog in which he shared first-hand ethnographic interpretations of what was happening in the immediate aftermath of the catastrophes (http://cli.gs/quake2006). The shared experience of dealing with loss and disorientation brought him much closer to his informants and shed new light on his original research questions. Doctoral students in anthropology, who engage in fieldwork as an almost mandatory rite of passage, are faced with a dilemma. On the one hand, there is the expectation to conform to the almost mythical image of the lone fieldworker who stumbles upon people or places that capture the anthropological imagination. On the other hand, their fieldwork experience is structurally limited in time, resources and objectives (linked to an increasing number of rules set by funding agencies, government institutions, universities or other external agents) (O'Dell and Willim2012). Under such conditions, serendipity is not entirely impossible but less likely to occur (certainly when reduced time for fieldwork is combined with reduced effort in appropriating sufficient 'background knowledge' in anthropological theory and methods).

  destinations' (Hazan and Hertzog 2011: 9). The time is more than ripe to appraise some new horizons for anthropological inquiry and to launch an open-ended dialogue. The 2012 EASA Young Scholars Forum, held at the University of Paris Ouest Nanterre la Défense, which lay at the basis of this special issue, offered a space for reflection in which the value of serendipity was assessed in the context in which 'young' anthropologists are currently operating. Stefan Le Courant uses his work as a volunteer legal assistant and ethnographer among undocumented migrants in a detention centre in France to reflect on the 'boundaries' of fieldwork. He zooms in on the epistemological issues that this double engagement raises. To him, serendipity is closely related to the continuous oscillation between different researcher positionalities. Julie Giabiconi explores the tensions between dimensions of the personal self, the ethnographic self and the academic self in her fieldwork among a Dene First Nation in Canadaa classical anthropological study object. She argues that the profound uncertainty and disquiet infusing the everyday practice of the ethnographer can function as a heuristic tool to produce new (and relevant) anthropological knowledge. Finally, Steffen Dalsgaard proposes to conceptualize the 'field' as temporally constituted and to use a methodology of 'multi-temporal ethnography' to address the 'timeliness' of anthropological theory. Drawing on his fieldwork in Papua New Guinea, Dalsgaard

a slow but methodological and thoughtful process, an on-going quest for serendipity...


DATA ACQUISTION FOR ANALYTICAL PLATFORM AUTOMATING SCIENTIFIC WORKFLOWS AND BUILDING AN OPEN DATABASE PLATFORM FOR CHEMICAL ANALYSIS METADATA

TARGET:

The project DAAP "Data AcquisiJon for AnalyJcal Plaborm" engages the collaboraJon in the AnalyJcal Chemistry research community. The plaborm allows shared data among scienJsts by accessing private Linked Database Plaborm (LDP) or public Linked Database Plaborm. The first step is to reference the resources available to researchers using a wiki, to define the ontology by the domain scienJsts and to benefit from Linked Data technologies.

Knowledge producJon

Knowledge sharing

PERSPECTIVE: open data access, relevant informaNon extracNon, data fusion

Efficient knowledge producNon with the scienNfic community

Step 1: Protocols are described on the private wiki DAAP by the researcher.

Step 2: Experimental data is stored within the University server.

Step 3: A plugin extracts the metadata from experimental data, imports the metadata into the RDF database and links metadata to the domain ontology.

Step 4: Researchers can simultaneously query the data in the database according to the domain ontology and find the related experimental data.

Step 5: Ager publishing a paper, data and knowledge are available on the public wiki DAAP.

Step 6: Experts organize a meeJng to review and validate the shared new knowledge and the shared resources according to the domain ontology.

Step 7: Researchers can query the domain ontology using Linked Data technologies.

Step 8: The ontology is presented as an infobox within wiki DAAP pages. In case of disagreement, users can change it. The divergence in ontology will then be discussed in step 6.

Description of unstructured knowledge on the public wiki DAAP

Review and validation of new knowledge

Conception of infoboxes make data available automatically on the wiki

Share official knowledge base

Share protocols and measurements

Backup processing scripts , backup data (generated to artifact data*) referred in the scientific papers

Backup the data files on the storage server of Paris-Saclay University

Defining the query to select data; writing the processing script (Matlab, R or

Sharing new knowledge

Publication of results

Keys :

Using

*

  The artifact data: The data is computed from the experimental dat a.

Lip(Sys)²-Chimie AnalyJque PharmaceuJque § , Univ. Paris-Sud, Université Paris-Saclay, F-92290 Châtenay-Malabry, France. § (FKA EA4041 Groupe de Chimie AnalyJque de Paris-Sud)

Bordercloud 245, quai de la Bataille de Stalingrad, F-92130 Issy-les-Moulineaux, France.

LRI-Laboratoire de Recherche en InformaJque, Bât 650, rue Noetzlin, F-91190 Gif-sur-Yve8e, France.

LAL-Laboratoire de l'Accélérateur Linéaire, Bât 200, voie de la faculté, F-91440 Bures-sur-Yve8e, France.