Bogdan Florin Cornea

Jaroslaw Slawinski

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

Vaidy Sunderam

Towards Adapting Parallel Programs to Different Platforms: Identifying Interaction Patterns

Keywords: MPI, static analysis, communication patterns, HPC, novel computing architectures

Modern parallel computing platforms exhibit substantial variation in communication performance between onsocket, on-node and inter-rack locations. When application interaction patterns are irregular, communication-aware process placement on such platforms can be critical for overall runtime. Understanding program interaction patterns can be valuable in order to minimize the impact of capacity variations in communications parameters. Such knowledge can also be useful in selecting the best execution platform from the available options. In this paper we propose an approach based on source code analysis which identifies parallel application communication patterns such as star, ring, mesh, or torus. Our implementation based on ROSE framework was tested on various parallel programs that exhibit different communication patterns. We present the accuracy as well as the limitations of our static identification approach. We envisage augmenting our approach with trace information from pilot runs and best effort approaches to determine a process interaction graph.

I. INTRODUCTION

Constant advances in computing platforms are a mixed blessing, especially for high performance parallel scientific and engineering applications. On the one hand, emerging platforms provide greater power and flexibility; on the other hand, they often necessitate substantial effort in the build, deployment, and runtime management phases. Sometimes they even require application modifications. In essence, as high performance computing parallel applications are tuned to match architectures existing at the time, they require periodic re-development according to latest trends for ensuring effective executability on evolving architectures.

As part of an effort to enhance executability of high performance parallel computing applications on varied target platforms [START_REF] Bourgeois | Extending executability of applications on varied target platforms[END_REF], we address the application to platform matching, from two perspectives. First, given the choice of multiple platforms on which an application may be executed, there may be a subset that is better suited not only in terms of processor types, memory configuration, or storage access, but most importantly in terms of network interconnection type. At a very basic level, the interconnect topology of a parallel machine may exactly match the interaction pattern of the application. If other characteristics (such as CPU speed, memory capacity) are equal or comparable, it can be reasonably expected that this platform will be the best choice, as this perfectly matches the application communication requirements. Second, at a more detailed level, contemporary parallel computing platforms exhibit substantial heterogeneity in their communication capacity between different pairs of processing elements. The interconnect capability between two processor cores on the same node can be orders of magnitude better than the one between processor cores on the same cloud cluster platform that happen to be allocated in different racks or even across data centers. At the same time, application processes often have vastly differing communication needs between different pairs of processes. Therefore, placing application program components (processes) on parallel computing platforms in a manner that minimizes communication traffic across slower interfaces can be beneficial.

In this paper, we outline an alternative scheme, which uses static program analysis, to characterize communication patterns in parallel programs based on the MPI standard [START_REF] Mpi | The message passing interface standard[END_REF]. This approach was preferred over a dynamic (or post-facto) one mainly because (i) it focuses on the impact of communication heterogeneity, (ii) does not require executing the analyzed application, hence the approach is platform-independent, and (iii) it constitutes an intermediate phase towards a larger goal i.e. mapping topologies on varied execution platforms.

Our approach determines whether an MPI application uses a regular or an irregular communication topology. It was implemented in C, as part of the ADAPT framework [START_REF] Bourgeois | Extending executability of applications on varied target platforms[END_REF] (Adaptive Application and Platform Translation). Obtaining the actual process placement does not constitute the focus of this paper, although we are making efforts in this direction. Determining the communication signature is valuable in the future for satisfying the requirements of the analyzed application with most suited platform capabilities. In this context, this work contributes to adapting parallel applications to the execution on target platforms, in a way that would lead to obtaining higher execution performance. This paper is structured as follows: previous work is discussed in Section II; in Section III we give details about our motivation that led to this work, present the methodology and how the latter was implemented in ADAPT; for several small programs and for two benchmarks from the NAS Parallel Benchmarks [START_REF] Bailey | The NAS Parallel Benchmarks[END_REF] (NPB)-Integer Sort (IS) and Data Traffic (DT)-we discuss the communication patterns identified with our implementation (see Section IV); we conclude and present our perspectives in Section V.

II. RELATED WORK

On contemporary platforms, large variations in interconnects and subsequently in their data transfer performance are common: core-core, socket-socket, node-node, rack-rack, datacenter-datacenter, and cloud-cloud communications can vary by orders of magnitude [START_REF] Reed | The performance of multicomputer interconnection networks[END_REF].

In order to achieve higher performance for distributed applications executed on heterogeneous architectures, most approaches aim at optimizing the way parallelism is implemented at program level [START_REF] Bhatia | Automatic experimental analysis of communication patterns in virtual topologies[END_REF]- [START_REF] Alawneh | Pattern recognition techniques applied to the abstraction of traces of inter-process communication[END_REF]. All these projects rely on execution traces to identify the communication pattern of applications. Bathia et al. [START_REF] Bhatia | Automatic experimental analysis of communication patterns in virtual topologies[END_REF] aim at identifying parallelization strategies at application level that can be optimized. Xu et al. [START_REF] Xu | Logicalization of communication traces from parallel execution[END_REF] identify the communication pattern and use this knowledge to perform event trace-compression with the purpose of obtaining application performance skeletons. Preissl et al. [START_REF] Preissl | Detecting patterns in mpi communication traces[END_REF], [START_REF] Preissl | Using mpi communication patterns to guide source code transformations[END_REF] present a method based on the ROSE framework [START_REF] Schordan | A source-to-source architecture for user-defined optimizations[END_REF], which was extended in [START_REF] Preissl | Exploitation of dynamic communication patterns through static analysis[END_REF] with the purpose of optimizing collective operations through static and dynamic analysis of applications. Although the above methods have proven efficient in identifying communication topologies, they all differ two-fold from the work presented here: first, our approach relies on identifying the communication patterns without prior execution of the code, and second, our method is network-centric, meaning that the knowledge we obtain on the communication topology is intended for a better mapping of processes to processing elements of the physical topology.

Alawneh et al. [START_REF] Alawneh | Pattern recognition techniques applied to the abstraction of traces of inter-process communication[END_REF] only tackle the abstraction of execution traces, for which they propose two techniques that identify patterns from communication traces. This method gives good results but it requires program execution (for obtaining the necessary traces) and does not tackle the application execution optimization.

A different set of approaches that reduces the impact of communication heterogeneity focuses on obtaining a "communication signature" for the parallel application that may then be used to optimize the use of the physical network. These frameworks [START_REF] Shao | A compiler-based communication analysis approach for multiprocessor systems[END_REF], [START_REF] Bronevetsky | Communication-sensitive static dataflow for parallel message passing applications[END_REF] use static code analysis and have proven very efficient in identifying parallel communication patterns. Shao et al. [START_REF] Shao | A compiler-based communication analysis approach for multiprocessor systems[END_REF] identifies the application logical topology as well as the different communication phases. Bronevetsky [START_REF] Bronevetsky | Communication-sensitive static dataflow for parallel message passing applications[END_REF] proposes a more thorough static analysis using ROSE compiler, relying on the concept of parallel control flow graphs (pCFG) to identify communication patterns. Although Shao et al. have a similar approach to the work presented in this paper, their analysis relies on a different compiler (SUIF [START_REF] Wilson | SUIF: an infrastructure for research on parallelizing and optimizing compilers[END_REF]) and can only match sends and receives at runtime. On the other hand, Bronevetsky has a completely different static approach, the only common point with our work being the use of ROSE compiler as a basis for building the static analyzer. His method gives very good results for (blocking) MPI_Send and MPI_Recv, but does not support any other MPI event.

Relying on application execution to match point to point communication limits the applicability of the tool [START_REF] Shao | A compiler-based communication analysis approach for multiprocessor systems[END_REF] in the sense that it requires for the target architecture to be physically available. By considering only MPI_Send and MPI_Recv, the tool [START_REF] Bronevetsky | Communication-sensitive static dataflow for parallel message passing applications[END_REF] does not cover the wide range of message passing functions that may be used in parallel applications. Such approach is limited in the sense that it narrows down the range of applications that can be analyzed.

III. STATIC IDENTIFICATION OF PROGRAM COMMUNICATION TOPOLOGY

The development and the execution of real life parallel applications has a significant impact on performance. From an application development viewpoint, we are interested in the implementation of parallel communication, i.e., in the logical topology also referred to as communication signature or communication pattern. With respect to program execution, we are concerned only with the target architecture network connection, or the physical topology.

A. Motivation

In a parallel program, the volume and the number of messages exchanged by participating processes is heavily dependent on the physical topology of the computing system. In this context, researchers proposed many different methods for improving application execution performance, new mapping methods [START_REF] Chou | Contention-aware application mapping for network-on-chip communication architectures[END_REF]- [START_REF] Bhatele | Mapping applications with collectives over sub-communicators on torus networks[END_REF], modification of MPI [START_REF] Rashti | Multicore and network aware MPI topology functions[END_REF], congestion reduction [START_REF] Hoefler | Generic Topology Mapping Strategies for Large-scale Parallel Architectures[END_REF] or clustering of processes [START_REF] Fan | Topologyaware deployment of scientific applications in cloud computing[END_REF].

While post-facto (dynamic) methods can have some use e.g. for subsequent runs of the same application with the same set of execution parameters, or can provide better information on data dependencies, they are sometimes impractical or too expensive. Because of this, our method uses static identification of the communication patterns of parallel applications that is a prerequisite for our future work on mapping topologies on varied execution platforms. Our motivation comes from successful previous work on identifying communication patterns (see Section II), as well as from the above-mentioned research and their limitations in application portability imposed by evolving architectures.

From our point of view, logical topology identification can be used in two ways, both aiming at increasing application performance:

First, given any scientific parallel C/MPI application found within the scope of our tool (see Section III-D), we can identify the best execution platform, from a variety of available ones, having a physical topology close to, or matching, the application communication pattern. This approach does not take into account the volume nor the number of exchanged messages.

Second, given the capabilities of an execution platform, we are interested in studying various process to processor core mappings, as to obtain a better usage of the network. Process placement that utilizes the fastest links for high-traffic interfaces will likely result in the best overall performance. One approach for a topology-aware mapping is to superpose two weighted graphs: (i) the logical topology graph of the application and (ii) the physical topology graph of the platform. In this manner, recommendations can be made regarding the placement of parallel processes such that pairs exchanging high volume of messages use the network interconnect with the largest bandwidth, whereas pairs exchanging messages frequently will use network interconnects with low latency. For example, let us consider a sample from a real application which computes the fluid dynamics of a blood vessel (see Figure 1a). For the purpose of better visualizing and describing this example, the signatures were obtained post-facto through analysis of trace files generated through instrumentation and the Vampir [START_REF] Vampir | [END_REF] software tool. The program was executed on 8 processes and the communication pattern in Figures 1d and1c were obtained. Edge thickness indicates the volume (1d) or the number of messages (1c) exchanged between processes. For determining the graph in Figure 1d, the volume of communication is obtained from the communication matrix shown in Figure 1b to which we apply a threshold ε v 1 of 12 MiB, representing in this case 10 percent of the 120 MiB maximum volume of exchanged data. Similarly, a threshold ε nb 1 of 22,000 exchanged messages, representing for this example half of the maximum number of messages, is applied for obtaining the pattern in Figure 1c I, and knowing the communication topology (Figure 1d), we observe that all processes can be placed on a single computing node on platforms 1 and 2 (Table I), or split into groups of maximum 4 processes (see Figure 3a) on platform 3. When executing the application on 32 nodes, the new communication topology (see Figures 2a and2b) would benefit if process placement on platforms 1, 1 ε v and ε nb are the thresholds for volume and number of messages, respectively, above which edges are considered during the identification of the logical topology. The values of ε v and ε nb must not eliminate any process from the logical topology graph.

2, and 3 would be done as seen in Figures 3b, 3c, and3d, respectively. Fig. 2: A real life application simulating on 32 processes the fluid dynamics of a blood vessel.

Identifying application communication signature is, in our opinion, useful either when choosing the target platform, or when mapping processes on a given platform. While both aspects aim at increasing application execution performance, in this paper we present the pattern identification aspect of our ongoing project.

B. Methodology

The following logical topologies can be identified by our framework: star, ring, two-dimensional (2D) mesh and twodimensional (2D) torus. For all communication patterns defined in the following sub-sections, let P be a parallel program and let G be an undirected communication graph, with G = (V, E). V (G) is a set of vertices and E(G) is a set of edges. Each vertex represents a parallel process of P and each edge corresponds to an existing bi-directional communication between two vertices (processes) of P. We emphasize that k ∈ N and the processes used in the following formulae (apart from star) range from 0

to N -1 (k ∈ [0; N -1]). V d (G)
E star (G) = {{v 0 v k }} and V 1 (G) = {v k } (1)
with

G(V, E) = G(V, E star ) and V = V 1 ∪ {v 0 }.

Ring pattern definition

In this unidimensional logical topology, we state that program P follows a ring logical topology if ∀k ∈ [0; N -1],

E ring (G) = {{v k v j }| j = (k ± 1) mod N} and V 2 (G) = {v k } (2) with G(V, E) = G(V 2 , E ring ).

2D mesh pattern definition

Processes in program P communicate in a two-dimensional mesh logical topology if ∀i ∈ [0; c -1], j ∈ [0; l -1], E mesh2D (G) =      {v i, j v i+x, j+y } -1 ≤ x, y ≤ 1 ; 0 ≤ i + x ≤ c -1 ; 0 ≤ j + y ≤ l -1 ; |x + y| = 1      (3) with i, j, x, y, c, l ∈ N, G(V, E) = G(V, E mesh2D ).

2D torus pattern definition

Program P is following a two-dimensional torus pattern if ∀i ∈ [0; c -1], j ∈ [0; l -1], E torus2D (G) = {v i, j v (i+x) mod c,( j+y) mod l } -1 ≤ x, y ≤ 1; |x + y| = 1 (4)
with i, j, x, y, c, l ∈ N. The number of elements in set V becomes

|V | = |V 4 (G)| = c • l processes.

Mixed communication pattern

In some cases, throughout the execution, applications use several topologies. This leads to the assumption that at least two patterns from those presented earlier in this section must be correctly identified by the end of the static analysis. Communication phases can be identified such that in each phase a single logical topology would characterize the communication. This type of pattern reduces false-positive results of our approach.

Irregular communication pattern

If none of the previously presented topologies is identified, we assume that the program communication graph has an irregular pattern. We represent this as a graph G(V ir , E ir ) having the following properties: V ir (G) is the set of processes, with each process having any number of neighbors and E ir (G) is the set of edges for each element in graph G. Then, ∀k, j ∈ [0; N -1], we define the edges of an irregular graph as follows:

E ir (G) = {v k v j } volume(v k v j ) ≥ ε v ; total msg (v k v j ) ≥ ε nb (5)
with k, j ∈ N. Volume(v k v j ), and total msg (v k v j ) are, respectively, the volume and the number of messages exchanged between v k and v j . As mentioned previously, ε v and ε nb are the volume and number of messages, respectively, above which edges are considered during the identification of the logical topology. The values of ε v and ε nb must not eliminate any process v k from the logical topology graph.

In order to identify program interaction patterns through static analysis, all communication patterns presented in this section have been implemented as an extension to the ADAPT framework, and are described in the next section.

C. Implementation

The architecture of our static analyzer is presented in Figure 4. The input consists all source files of a C/MPI program. The analyzer-our module for communication pattern identification-is based on the ROSE framework [START_REF] Schordan | A source-to-source architecture for user-defined optimizations[END_REF] which is a compiler infrastructure supplying very complex methods for source-to-source code analysis and transformation. The output consists of information with respect to the communication pattern identified in the application.

In a first phase, the input is pre-processed by the Edison Design Group C compiler [START_REF] Edg | Edison design group front-end compiler website[END_REF] available from ROSE. This generates several intermediate representations (IR), but we only use the Abstract Syntax Tree (AST) and the System Dependence Graph (SDG). On the one hand, the AST is an accurate representation of the input code, at a point where, at the end of an analysis or transformation, this IR can be unparsed to generate a new source code containing all transformations made on the AST. On the other hand, the SDG is a complex IR useful especially in analyzing the data and control dependencies of the input code.

In a second phase, we implement the verifier such that it traverses the AST in search of MPI communication events that need to validate or invalidate the logical topology rules presented in Section III-B. If MPI events use variable names or expressions for the source or destination, an isolated traversal is done on the SDG until the source or the destination are found to depend upon constants or key variables such as my_rank, comm_size, numprocs. The following paragraphs present they way our verifier searches in the AST and the SDG for any of the communication patterns defined in Section III-B.

The star pattern requires identifying in the AST the MPI functions for sending and receiving. From each MPI event identified in the AST, the upper nodes of the IR are analyzed. In the input code, these are the instruction blocks that contain the MPI communication. By analyzing the conditions in statements, such as for or if, it can be decided if the program communicates according to formula [START_REF] Bourgeois | Extending executability of applications on varied target platforms[END_REF] or not. Two elements that play a key role in analyzing the conditions are the number of processes and the number of iterations for the dominant communication loop.

The ring pattern uses a slightly different approach than for star pattern. Assuming that the programs use MPI_Send and MPI_Recv to communicate in a ring, for all MPI events found, which are of type SgFunctionCallExp in the AST, the focus is set on the fourth argument, i.e., the source and destination. In the case of MPI_Send and MPI_Recv, these elements could be of the following type: (i) a constant value, (ii) a macro, (iii) a mathematical expression, or (iv) a variable. When generating the AST, all macros are preprocessed and replaced with their corresponding value. When dealing with mathematical expressions, the AST node of the expression is parsed and split into operations and operands (left-hand and right-hand sides). From this point, the IR node representing each variable from the AST is identified in the SDG and its propagation can be traced back. This operation on the SDG helps express the source and destination variables with respect to common key elements such as the number of processes, the current rank, or the communication size. This asserts the applicability of formula (2) in the communication pattern.

The two-dimensional mesh pattern is identified in two ways: (i) by analyzing the use of MPI_Cart_create or (ii) by identifying the manually defined communication topology (see formula 3).

If MPI_Cart_create is found in the AST, our module extracts from the argument list 3 elements: one integer value and two arrays of integers. The integer gives the number of dimensions of the mesh, one array is for the number of processes in each dimension, and the other array of integers is for the periodicity of each dimension.

However, when the 2D mesh logical topology is not defined using MPI_Cart_create, the verifier applies formula (3) on the MPI events found in the AST. For this purpose, we assume that process ranking, or the numbering of processes, is done from top-left to bottom-right position, with 1 through c • l values in consecutive order, with c the number of columns and l the number of rows. For any analyzed applications, if V i (G k ) has a value different from the ones here-below, we state that logical topology used is not a 2D mesh.

| V i (G) |=    4 processes, i = 2 (c + l -4) • 2 processes, i = 3 (c -2) • (l -2) processes, i = 4 (6)
with i the number of neighbor processes from V i (G), c the columns and l the rows of the 2D mesh. Process ranks are expressed by using the SDG and by following a reverse propagation of each relevant variable. They are then expressed relative to constants or to MPI initialization variables (number of processes or current process rank).

The two-dimensional torus pattern is identified similarly to the two-dimensional mesh, with one difference, i.e., the use of MPI_Cart_create is expected to use periodicity. Otherwise, the manually defined communication topology is checked using the formula (4), verifying if each process is connected to four specific processes in order to comply with the 2D torus definition.

D. Scope and limitations of static analysis

The use of ROSE comes with some limitations to our implementation. First, the input application must comply with the C standard. Then, a multiple file project requires merging the AST obtained for individual files into one representation of the entire project. Third, static analysis requires that communication be initiated in the analyzed source code and not by underlying libraries. Our approach does not address the algorithmic correctness of the programs, nor does it search to optimize the code, as these constitute the focus of other research teams.

As some developers might choose not to use common implementation of algorithms, our tool might require supplementary effort for supporting the analysis of their programs. The number of processes, the source and destination of communication processes must be defined statically or with respect to MPI program variables, i.e., total number of processes and current rank. If this is not the case, or if data-dependency can not be solved using AST and SDG, our static analysis is not applicable.

Currently, only communication patterns mentioned in Section III-B are supported, but the architecture of ADAPT allows new communication topology modules to be added without effort, extending the identification capabilities of our approach. The fully connected mesh pattern was not presented in Section III-B, but it is identified when collective communications, such as MPI_Alltoall, MPI_Allgather, are used, and there is no MPI_Cart_create found in the code.

IV. EXPERIMENTS

Several applications were chosen to verify our method. For better comparing the logical topology discovery results, we consider only C/MPI applications.

A. MPI events used during the experiments

We briefly present the main characteristics of the MPI events that were identified in the applications used in this section.

As our approach is a static one, the information required to identify the communication pattern of applications is extracted from (i) the MPI event name-MPI_Send, MPI_Recv, MPI_Gather and so on-and from (ii) the arguments of the MPI call, such as the source (for MPI_Recv) or the destination (for MPI_Send).

In the message passing standard, parallel processes are organized in groups, and a group of processes that may communicate to each other is associated with a communicator. Our approach assumes that all processes of an analyzed application exchange messages as part of the same communicator.

For the point to point blocking communications MPI_Send and MPI_Recv the relevant arguments are the sender and receiver ranks, the exchanged data size and type. The collective communication MPI_Bcast broadcasts a message from the root process-usually rank 0-to all processes (of the communicator). Broadcasting is characteristic to "star" type of communication. The MPI_Reduce event, as opposed to broadcast, collects at process "root" the values from all processes in the communicator, by applying an arithmetic operator. This occurs in "star" communications as well. The MPI_Barrier function is used to synchronize processes in a communicator. When reached, it blocks the execution until all other processes have reached the same routine. It does not give any information regarding the communication topology. MPI_Sendrecv_replace performs a Send and a Recv operation using a single buffer. By itself it does not provide sufficient information about the communication topology. A call to MPI_Cart_create function creates a new communicator containing information about the communication topology. In C, this function has 5 arguments among which we mention the number of dimensions for the new Cartesian grid, an array indicating the number of processes in each dimension, and an array stating if the grid is periodic or not in each of the dimensions. MPI_Scatter is a collective communication that scatters a message over all processes from a communicator. The opposite of this collective communication is MPI_Gather, and they both indicate a "star" communication. The identification of collective events such as MPI_Alltoall, MPI_Alltoallv, MPI_Allreduce generally indicate that the processes communicate in a fully-connected mesh.

B. Asserting the star pattern

For this experiment, we use three C/MPI applications (see Table II, programs 1-3). All three programs implement differently the calculus of π (PI).

For the trivial case of test code #1, our tool indicates that it uses a star topology by verifying formula [START_REF] Bourgeois | Extending executability of applications on varied target platforms[END_REF]. The information extracted by our tool from the AST which led to this conclusion are presented in Table III. The result is expressed according to the number of processes (p_numtasks) and the number of iterations for the dominant communication loop (10 in this case), both values identified in the AST.

For the test code #2, the source and the destination parameters from the AST that correspond to MPI_Bcast and MPI_Reduce respectively, are verified by using formula (1) and an identification is done.

Similarly, a correct identification is done for the test code #3.

C. Ring pattern

The approach implemented in ADAPT was tested on programs 4 and 5 (see Table II). We begin describing this approach on the test code #4 for having the highest complexity of these two programs.

Our method identifies in MPI_Send and MPI_Recv their destination and source, respectively. These relevant arguments are variables right and left which must be expressed with respect to a common variable or constant. The expression elements-SgVarRefExp in the AST-must be found such that the left-hand side operand is either right or left, and the right-hand side operand is related to constants or to MPI initialization variables. The traversal of the AST indicates the name of the argument to look for, while the SDG points precisely to the data-dependency for both right and left. Our method identified the correct pattern due to the identification throughout the code of the following expressions containing right and left: 1: right = 0; 2: right = procnum + 1; 3: left = procnum -1; 4: left = numprocs -1;

where numprocs is the variable extracted from MPI_Comm_size argument list.

For test code #5, a similar method is used to identify the occurrence of the relevant variable world_rank as part of an expression's right-hand side operand. It is therefore found as dependent on the number of processes, which is the variable named world_size. This simply requires more indepth analysis of the respective right-hand side operand in the IR.

D. Two-dimensional mesh pattern

For the test code #6 listed in Table II, our framework identified a 2D mesh based on the following elements: (i) MPI_Cart_create, with arguments ndim, dims, cyclic, and (ii) MPI_Barrier as the only MPI event used. Our tool followed the reverse propagation of variables in the SDG and obtained: The occurrence of any other MPI event would have meant that the pattern is mixed or irregular.

E. Mixed pattern: two-dimensional torus + star

For the input code #7, ADAPT identifies several communication patterns based on MPI_Cart_create, MPI_Bcast, MPI_Scatter, MPI_Sendrecv_reduce, MPI_Gather. This leads to an indication of 3 phases in the program, each characterized by one pattern: (i) star, (ii) irregular point-topoint, (iii) star. The arguments of MPI_Cart_create indicate that, in fact, the irregular pattern is a 2D torus:

1: dimensions: 2 (set by macro) 2: nodes/dimension: (int)sqrt((double) grid->Size) 3: periodicity/dimension: 1 (by rows and columns).

Line 3 is the result of reversed variable propagation performed on the input by ADAPT using the SDG, starting from instruction line: Dimensions[0] = Dimensions [START_REF] Bourgeois | Extending executability of applications on varied target platforms[END_REF] = grid->p_proc. Any additional MPI event would have added another communication phase characterized by a regular or an irregular pattern.

F. Verifying our approach on NAS IS (mixed pattern: ring + full mesh + star)

On this input code, our framework identifies 3 topologies: (i) ring, (ii) fully connected mesh, and (iii) star. The decision is based on the following MPI events identified in the code: Irecv, Send, Allreduce, Alltoall, AlltoallV, Bcast, Reduce. We observe that a result was obtained which takes into account if several regular topologies are found, and does not determine that the overall result of the analysis is an irregular topology. This code shows that our method lacks a finer grained verifier that estimates the time percentage spent communicating in each topology, which we intend to address in our future work.

G. Verifying our approach on NAS DT (star pattern)

For this benchmark available in NPB as of version 3.2, the identification result indicates the presence of point-to-point communication. By analyzing the conditionals containing the MPI event, and by verifying the data and control dependencies among variables or function calls, the identification result validates formula (1), i.e., the NAS Data Traffic benchmark communicates in a star topology.

We observe that by identifying the communication pattern in a static manner, our result is scalable in the way that it analyses the MPI event types found in the code as well as the conditional statements that they depend on. This approach consists of one advantage in comparison to trace-based identification, i.e., it reduces the possibility of identifying additional communication phases when the problem size increases.

V. CONCLUSIONS AND FUTURE WORK

As part of the ADAPT project for achieving adaptation of C/MPI applications for execution on various computational resources, in this paper we propose a novel mechanism for automatically analyzing parallel applications and determining their communication signature. Our approach is based on the ROSE framework and it statically identifies regular communication topologies, i.e., star, ring, 2D mesh, 2D torus, as well as mixed and irregular communication patterns. Several parallel programs were used to verify the proposed method.

For the automatic process of mapping application communication signature to platform capabilities, our team is undergoing research on two directions: (i) providing microbenchmarks for determining target platforms capabilities, and (ii) implementing in ADAPT a decision-making mechanism determining if static analysis using ROSE is applicable or if it is recommended to use historical runs and trace-based simulation instead. An approach using trace-based simulation is envisaged for parallel applications where communication is handled entirely by underlying libraries. We are working on an approach that estimates the percentage of occurrence of each communication phase throughout the execution of the program. The presented work is part of a framework for predicting the performance of distributed applications based on process-to-processor mapping. The current contribution is not yet available as a standalone tool, although we are taking this aspect into consideration. Our future work aims at proposing a best process placement on the physical architecture, hence estimating a best application to platform performance.

  for process mapping. By filtering out low traffic-in terms of volume or number of messages-the application communication can be characterized by (i) a regular pattern, such as star, ring or mesh, (ii) by an irregular one, (iii) or by communication phases characterized by different patterns. Assuming that the candidate (a) The blood vessel. (b) Volume of exchanged messages.

Fig. 1 :

 1 Fig.1:A real life application simulating on 8 processes the fluid dynamics of a blood vessel. platforms are listed in TableI, and knowing the communication topology (Figure1d), we observe that all processes can be placed on a single computing node on platforms 1 and 2 (TableI), or split into groups of maximum 4 processes (see Figure3a) on platform 3. When executing the application on 32 nodes, the new communication topology (see Figures2a and 2b) would benefit if process placement on platforms 1,

  (a) The communication graph on 32 processes. (b) The communication pattern on 32 processes. X,Y axis are the processes. White through red is the overall message volume.

  (a) On Puma, 8 processes are placed on a star topology.

Fig. 3 :

 3 Fig.3: Using the knowledge on communication topology acquired from a real life application to place processes on the processing elements (PE).

  is the set of all vertices from G where each element has d communication neighbors. Star pattern definition Processes in program P communicate in a star logical topology if and only if ∀k ∈ [1; N -1],

Fig. 4 :

 4 Fig. 4: ADAPT module for identifying program communication patterns.

TABLE I :

 I Example of available execution platforms. Intranode (on-node) network capability is much higher than internode one.

		Name	Topology Cores	Inter-node 2
				per	network
				node
	1	Titan	3D torus	16	Cray Gemini
	2 SuperMUC	tree	8	Infiniband
	3	Puma	star	4	Gigabit Ethernet

TABLE III :

 III Test code #1: result of the static analysis for calculus of π.

	Phase MPI	Source	Destination
		event	process	process
	1	Send	p1, p2, .. p10	p0
	2	Recv p1, p2 .. p numtasks	p0

TABLE II :

 II Characteristics of C/MPI programs[START_REF]Test codes[END_REF] used in the experimental section.

	Code	Pattern	Communication type	MPI event(s)	Notes
	1	star	Point-to-point	Send, Recv	Calculus of π
	2	star	Collective	Bcast, Reduce	-
	3	star	Collective	Reduce	-
	4	ring	Point-to-point	Send, Recv	using variables
	5	ring	Point-to-point	Send, Recv	using expressions
	6	2D mesh	-	Barrier	MPI Cart create
	7	mixed: 2D torus, star Point-to-point, collective	Sendrecv replace,	MPI Cart create
				Gather, Scatter, Bcast
	8	mixed:	Point-to-point, collective	Irecv, Send,
		ring, full mesh, star		Allreduce, Alltoall, Alltoallv,	NAS IS
				Bcast, Reduce
	9	star	Point-to-point	Send, Recv	NAS DT
	1: Topology defined using MPI_Cart_create;
	2: dimensions (dim): 2
	3: nodes/dimension: 3x2 (dims[0]=nrow=2;
	dims[1]=mcol=2)
	4: periodicity/dimension: 0 (cyclic[0]=0;
	cyclic[1]=0)

By inter-node we refer to the communication between processing units located on different computing nodes, or node boards. It opposes the intranode, or on-node, communication which takes place between processing units located on the same computing node.

ACKNOWLEDGMENT

This work is partially funded by the US National Science Foundation grant OCI-1124418.


Wiem Elghazel
email: wiem.elghazel@femto-st.fr

Kamal Medjaher
email: kamal.medjaher@ens2m.frzerhouni@ens2m.fr

Noureddine Zerhouni

Jacques Bahi
email: jacques.bahi@univ-fcomte.fr

Ahmad Farhat
email: ahmadfarhat91@hotmail.com

Christophe Guyeux
email: guyeux@gmail.com

DISC Mourad Hakem
email: mhakem@femto-st.fr

Random Forests for Industrial Device Functioning Diagnostics Using Wireless Sensor Networks

come

INTRODUCTION

In machine learning, classification refers to identifying the class to which a new observation belongs, on the basis of a training set and quantifiable observations, known as properties. In ensemble learning, the classifiers are combined to solve a particular computational intelligence problem. Many research papers encourage adapting this solution to improve the performance of a model, or reduce the likelihood of selecting a weak classifier. For instance, Dietterich argued that averaging the classifiers' outputs guarantees a better performance than the worst classifier [START_REF] Dietterich | An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization[END_REF]. This claim was theoretically 978-1-4799-5380-6/15/$31.00 ©2015 IEEE.

proven correct by Fumera and Roli [START_REF] Fumera | A theoretical and experimental analysis of linear combiners for multiple classifier systems[END_REF]. In addition to this, and under particular hypotheses, the fusion of multiple classifiers can improve the performance of the best individual classifier [START_REF] Tumer | Error correlation and error reduction in ensemble classifiers[END_REF].

Two of the early examples of ensemble classifiers are Boosting and Bagging. In Boosting algorithm [START_REF] Schapire | A brief introduction to boosting[END_REF], the distribution of the training set changes adaptively based on the errors generated by the previous classifiers. In fact, at each step, a higher degree of importance is accorded to the misclassified instances. At the end of the training, a weight is accorded to each classifier, regarding its individual performance, indicating its importance in the voting process. As for Bagging [START_REF] Breiman | Bagging predictors[END_REF], the distribution of the training set changes stochastically and equal votes are accorded to the classifiers. For both classifiers, the error rate decreases when the size of the committee increases.

In a comparison made by Tsymbal and Puuronen [START_REF] Tsymbal | Bagging and boosting with dynamic integration of classifiers[END_REF], it is shown that Bagging is more consistent but unable to take into account the heterogeneity of the instance space. In the highlight of this conclusion, the authors emphasize the importance of classifiers' integration. Combining various techniques can provide more accurate results as different classifiers will not behave in the same manner faced to some particularities in the training set. Nevertheless, if the classifiers give different results, a confusion may be induced [START_REF] Kanemoto | Diversity and integration of rotating machine health monitoring methods[END_REF]. It is not easy to ensure reasonable results while combining the classifiers. In this context, the use of random methods could be beneficial. Instead of combining different classifiers, a random method uses the same classifier over different distributions of the training set. A majority vote is then employed to identify the class.

In this article, the use of random forests (RF) is proposed for industrial functioning diagnostics, particularly in the context of devices being monitored using a wireless sensor network (WSN). A prerequisite in diagnostics is to consider that data provided by sensors are either flawless or simply noisy. However, deploying a wired sensor network on the monitored device is costly in some well-defined situations, specifically in large scale, moving, or hardly accessible areas to monitor. Such situations encompass nuclear power plants or any structure spread in deep water or in the desert. Wireless sensors can be considered in these cases, due to their low cost and easy deployment.

WSNs monitoring is somehow unique in the sense that 1 sensors too are subjected to failures or energy exhaustion, leading to a change in the network topology. Thus, monitoring quality is variable too and it depends on both time and location on the device. Various strategies can be deployed on the network to achieve fault tolerance or to extend the WSN's lifetime, like nodes scheduling or data aggregation. However, the diagnostic processes must be compatible with these strategies, and with a device coverage of a changing quality. The objective of this research work is to show that RF achieve a good compromise in that situation, being compatible with a number of sensors which may be variable over time, some of them being susceptible to errors. More precisely, we will explain why random methods are relevant to achieve accurate diagnostics of an industrial device being monitored using a WSN. The functioning of RF will then be recalled and applied in the monitoring context. An algorithm will be provided, and an illustration on a simulated WSN will finally be detailed. This study differs from previous works as it adresses RF for industrial prognostics based on incomplete data provided by a WSN.

The remainder of this article is organized as follows. Section 2 summarizes the related work. In Section 3, we overview the research works in industrial diagnostics. We present the random forest algorithm in Section 4 and give simulation results in Section 5. This research work ends with a conclusion section, where the contribution is summarized and intended future work is provided.

RELATED WORK

Many research works have contributed in improving the classification's accuracy. For instance, tree ensembles use majority voting to identify the most popular class. They have the advantage of transforming weak classifiers into strong ones by combining their knowledge to reduce the error rate.

Usually, the growth of each tree is governed by random vectors sampled from the training set, and bagging is one of the early examples of this. In this method, each tree is grown by randomly selecting individuals from the training set without replacing them [START_REF] Breiman | Bagging predictors[END_REF]. The use of bagging can be motivated by three main reasons: (1) it enhances accuracy with the use of random features, (2) it gives ongoing estimates of the generalization error, strength, and correlation of combined trees, and (3) it is also good for unstable classifiers with large variance.

Meanwhile, Freund introduced the adaptive boosting algorithm Adaboost, which he defined as [START_REF] Freund | Experiments with a new boosting algorithm[END_REF]: "a deterministic algorithm that selects the weights on the training set for input to the next classifier based on the misclassifications in the previous classifiers". The fact that the classifier focuses on correcting the errors at each new step remarkably improved the accuracy of classifications.

Shortly after, in [START_REF] Amit | Shape quantization and recognition with randomized trees[END_REF] randomness was again used to grow the trees. The split was defined at each node by searching for the best random selection of features in the training set. Ho [START_REF] Ho | The random subspace method for constructing decision forests[END_REF] introduced the random subspace, in which he randomly selects a subset of vectors of features to grow each tree. Diettrich introduced the random split selection where at each node, a split is randomly selected among k best splits [START_REF] Dietterich | An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization[END_REF].

For these methods, and like bagging, a random vector sampled to grow a tree is completely independent from the previous vectors, but is generated with the same distribution.

Random split selection [START_REF] Dietterich | An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization[END_REF] and introducing random noise into the outputs [START_REF] Breiman | Using adaptive bagging to debias regressions[END_REF] both gave better results than bagging. Nevertheless, the algorithms implementing ways of re-weighting the training set, such as Adaboost [START_REF] Freund | Experiments with a new boosting algorithm[END_REF], outperform these two methods [START_REF]Random forests[END_REF]. Therefore, Breiman combined the strengths of the methods detailed above into the random forest algorithm. In this method, individuals are randomly selected from the training set with replacement. At each node, a split is selected by reducing the dispersion generated by the previous step and consequently lowering the error rate. This algorithm is further detailed in Section 4.

OVERVIEW OF DIAGNOSTICS

With their constantly growing complexity, current industrial systems witness costly downtime and failures. Therefore, an efficient health assessment technique is mandatory. In fact, in order to avoid expensive shutdowns, maintenance activities are scheduled to prevent interruptions in system operation. In early frameworks, maintenance takes place either after a failure occurs (corrective maintenance), or according to predefined time intervals (periodic maintenance). Nevertheless, this still generates extra costs due to "too soon" or "too late" maintenances. Accordingly, considering the actual health state of the operating devices is important in the decision making process. Maintenance here becomes condition-based, and is only performed after the system being diagnosed in a certain health state.

Diagnostics is an understanding of the relationship between what we observe in the present and what happened in the past, by relating the cause to the effect. After a fault takes place, and once detected, an anomaly is reported in the system behavior. The fault is then isolated by determining and locating the cause (or source) of the problem. Doing so, the component responsible for the failure is identified and the extent of the current failure is measured. This activity should meet several requirements in order to be efficient [START_REF] Dash | Challenges in the industrial applications of fault diagnostic systems[END_REF]. these requirements are enumerated in the following.

(1) Early detection: in order to improve industrial systems' reliability, fault detection needs to be quick and accurate. Nevertheless, diagnostic systems need to find a reasonable trade-off between quick response and fault tolerance. In other words, an efficient diagnostic system should differentiate between normal and erroneous performances in the presence of a fault.

(2) Isolability: fault isolation is a very important step in the diagnostic process. It refers to the ability of a diagnostic system to determine the source of the fault and identify the responsible component. With the isolability attribute, the system should discriminate between different failures. When an anomaly is detected, a set of possible faults is generated. While the completeness aspect requires the actual faults to be a subset of the proposed set, resolution optimization necessitates that the set is as small as possible. A tradeoff then needs to be found while respecting the accuracy of diagnostics.

(3) Robustness and resources: it is highly desirable that the diagnostic system would degrade gracefully rather than fail suddenly. For this finality, the system needs to be robust to noise and uncertainties. In addition to this, a trade-off between system performance and computational complexity is to be considered. For example, on-line diagnostics require low complexity and higher storage capacities. (4) Faults identifiability: a diagnostics system is of no interest if it cannot distinguish between normal and abnormal behaviors. It is also crucial that not only the cause of every fault is identified, but also that new observations of malfunctioning would not be misclassified as a known fault or as normal behavior. While it is very common that a present fault leads to the generation of other faults, combining the effects of these faults is not that easy to achieve due to a possible non-linearity. On the other hand, modeling the faults separately may exhaust the resources in case of large processes.

(5) Clarity: when diagnostic models and human expertise are combined together, the decision making support is more reliable. Therefore, it is appreciated that the system explains how the fault was triggered and how it propagated, and keeps track of the cause/effect relationship. This can help the operator use their experience to evaluate the system and understand the decision making process. ( 6) Adaptability: operating conditions, external inputs, and environmental conditions change all the time. Thus, to ensure relevant diagnostics at all levels,the system should adapt to changes and evolve in the presence of new information.

Existent diagnostic models have several limitations. Some of which are summarized in Table 1. The degradation process can be considered as a stochastic process. The evolution of the degradation is a random variable that describes the different levels of the system's health state, from good condition to complete deterioration. The deterioration process is multi-state and can be divided into two main categories [START_REF] Moghaddass | An integrated framework for online diagnostic and prognostic health monitoring using a multistate deterioration process[END_REF]:

1. Continuous-state space: the device is considered failed when the predefined threshold is reached. 2. Discrete-state space: the degradation process is divided into a finite number of discrete levels.

As condition-based maintenance relies on reliable scheduling of maintenance activities, an understanding of the degradation process is required. For this finality, in this paper, we consider the discrete-state space deterioration process

RANDOM FORESTS

The RF algorithm is mainly the combination of Bagging [START_REF] Breiman | Bagging predictors[END_REF] and random subspace [START_REF] Ho | The random subspace method for constructing decision forests[END_REF] algorithms, and was defined by Leo Breiman as "a combination of tree predictors such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest" [START_REF]Random forests[END_REF]. This method resulted from a number of improvements in tree classifiers' accuracy.

This classifier maximizes the variance by injecting randomness in variable selection, and minimizes the bias by growing the tree to a maximum depth (no pruning). The steps of constructing the forest in this paper are detailed in Algorithm 1.

Algorithm In a RF, the root of a tree i contains the instances from the training subset S i , sorted by their corresponding classes. A node is terminal if it contains instances of one single class, or if the number of instances representing each class is equal. In the alternative case, it needs to be further developed (no pruning). For this purpose, at each node, the feature that guarantees the best split is selected as follows.

1. The information acquired by choosing a feature can be computed through:

(a) The entropy of Shannon, which measures the quantity of information

Entropy(p) = - c k=1 P (k/p) × log(P (k/p)) (1)
where p is the number of examples associated to a position in the tree, c is the total number of classes, k/p denotes the fraction of examples associated to a position in the tree and labelled class k, P (k/p) is the proportion of elements labelled class k at a position p.

(b) The Gini index, which measures the dispersion in a population

Gini(x) = 1 - c k=1 P (k/p) 2 (2)
where x is a random sample, c is the number of classes, k/p denotes the fraction of examples associated to a position in the tree and labelled class k, P (k/p) is the proportion of elements labelled class k at a position p.

2. The best split is then chosen by computing the gain of information from growing the tree at given position, corresponding to each feature as follows:

Gain(p, t) = f (p) - n j=1 P j × f (p j ) (3)
where p corresponds to the position in the tree, t denotes the test at branch n, P j is the proportion of elements at position p and that go to position p j , f (p) corresponds to either Entropy(p) or Gini(p).

The feature that provides the higher Gain is selected to split the node.

The optimal training of a classification problem can be NPhard. Tree ensembles have the advantage of running the algorithm from different starting points, and this can better approximate the near-optimal classifier.

In his paper, Leo Breiman discusses the accuracy of random Forests. In particular, he gave proof that the generalized error, although different from one application to another, always has an upper bound and so random forests converge [START_REF]Random forests[END_REF].

The injected randomness can improve accuracy if it minimizes correlation while maintaining strength. The tree ensembles investigated by Breiman use either randomly selected inputs or a combination of inputs at each node to grow the tree. These methods have interesting characteristics as:

-Their accuracy is at least as good as Adaboost -They are relatively robust to outliers and noise -They are faster than bagging or boosting -They give internal estimates of error, strength, correlation, and variable importance -They are simple and the trees can be grown in parallel There are four different levels of diversity which were defined in [START_REF] Sharkey | Combining diverse neural nets[END_REF], level 1 being the best and level 4 the worst.

• Level 1: no more than one classifier is wrong for each pattern.

• Level 2: the majority voting is always correct.

• Level 3: at least one classifier is correct for each pattern.

• Level 4: all classifiers are wrong for some pattern.

RF can guarantee that at least level two is reached. In fact, a trained tree is only selected to contribute in the voting if it does better than random, i.e. the error rate generated by the corresponding tree has to be less than 0.5, or the tree will be dropped from the forest [START_REF]Random forests[END_REF].

In [START_REF] Verikas | Mining data with random forests: A survey and results of new tests[END_REF], Verikas et al. argue that the most popular classifiers (Support Vector Machine SVM, MultiLayer Perceptron MLP, and Relevance Vector Machine RVM) provide too little insight about the variable importance to the derived algorithm. They compared each of these methodologies to the random forest algorithm to find that in most cases RF outperform other techniques by a large margin.

EXPERIMENTAL STUDY

Data collection

In this paper, we consider two sets of experiments. The sensor network is constituted by 110 nodes, sensing respectively the levels of temperature (50 sensors), pressure (50), and humidity [START_REF] Ho | The random subspace method for constructing decision forests[END_REF] on the industrial device under consideration.

Set of experiment 1-In this set of experiments, we consider that no level of correlation is introduced betweent the different features. Moreover, we suppose that at time t:

• Under normal conditions, temperature sensors follow a Gaussian law of parameter (20 × (1 + 0.005t), 1), while these parameters are mapped to (35, 1) in case of a malfunction of the industrial device. Finally, these sensors return the value 0 when they break down.

• The Gaussian parameters are (5 × (1 + 0.01t), 0.3) when both the industrial device and the pressure sensors are in normal conditions. The parameters are changed to (15, 1) in case of industrial failure, while the pressure sensors return 1 when they are themselves broken down.

• Finally, the 10 humidity sensors produce data following a Gaussian law of parameter (52.5 × (1 + 0.001t), 12.5) when they are sensing a well-functioning device. These parameters are set to (70, 10) in case of device failure, while malfunctioning humidity sensors produce the value 0.

Set of experiment 2-For this set, a linear correlation is injected between the studied features. A comprhensive study of correlation between features in maintenance prediction is given in [START_REF] Mosallam | Nonlinear relation mining for maintenance prediction[END_REF].

• Under normal conditions, temperature sensors follow a Gaussian law of parameter (20 × (1 + 0.005t), 1), while these parameters are mapped to (35, 1) in case of a malfunction of the industrial device. Finally, these sensors return the value 0 when they break down.

• When both the industrial device and the pressure sensors are in normal conditions, the value of pressure is computed as (x ÷ 2 + 10), where x is the value of temperature. The parameters are changed to (15, 1) in case of industrial failure, while the pressure sensors return 1 when they are themselves broken down.

• For a well-functioning device, the 10 humidity sensors produce data in the form of (x×525+12). These parameters are set to (70, 10) in case of device failure, while malfunctioning humidity sensors produce the value 0.

For both data sets, the probability that a failure occurs at time t follows a Bernoulli distribution of parameter t ÷ 35000.

Five levels of functioning are attributed to each category of sensors, depending on the abnormality of the sensed data. These levels are defined thanks to 4 thresholds, which are 22.9, 24.5, 26, and 28 degrees for the temperature (a temperature lower than 22.9°C is normal, while a sensed value larger than 28°C is highly related to a malfunctioning), 5.99, 6.4, 7.9, and 9 bars for the pressure parameter, and finally 68, 80, 92, and 95 percents for the humidity.

Data is generated as follows.

• For each time unit t = 1..100 during the industrial device monitoring, -For each category c (temperature, pressure, humidity) of sensors:

* For each sensor s belonging to category c:

• If s has not yet detected a device failure: 1. s picks a new data, according to the Gaussian law corresponding to a well-functioning device, which depends on both t and c, 2. a random draw from the exponential law detailed previously is realized, to determine if a breakdown occurs on the location where s is placed.

• Else s picks a new datum according to the Bernoulli distribution of a category c sensor observing a malfunctioning device.

The global failure level F t of a set of 110 sensed data produced by the wireless sensor network at a given time t is defined as follows. For each sensed datum d t i , i = 1..110, let f t i ∈ {1, .., 5} be the functioning level related to its category (pressure, temperature, or humidity). Then F t = max f t i | i = 1..110.

Random forest design

The random forest, constituted in this set of experiments by 100 trees, is defined as follows. For each tree T i , i = 1..100:

• A sample of 67% of dates τ 1 , . . . , τ 67 ∈ {1, ..., 100} is extracted • The root of the tree T i is the tuple ( {j | F τj = n, j = 1..67}) n=1..5 , where X is the cardinality of the finite set X. Thus, its n-th coordinate corresponds to the number of times the device has been in the global failure n in this sample of observation dates.

• The category c having the largest Gain for the dates in the root node is selected. The dates are divided into five sets depending on thresholds related to c. Then, 5 edges labeled by both c and failure levels l 0 i = {1, .., 5} are added to T i , as depicted in Figure 1 .

In other words, we only consider in this node a sub-sample of dates having their functioning level for category c equal to l 0 i , and we divide the sub-sample into 5 subsets, depending on their global functioning levels: the tuple is constituted by each cardinality of these subsets, see Fig. 1.

• The process is continued, with: this vertex as a new root, the reduced set of observed dates, and the categories minus c. It is stopped when either all the categories have been regarded, or when tuple of the node has at least 4 components equal to 0.

Providing a diagnostic on a new set of observations

Finally, given a new set of observations at a given time, the diagnostics of the industrial device is obtained as follows.

Let T be a tree in the forest. T will be visited starting from its root until reaching a leaf as described below.

1. All the edges connected to the root of T are labeled with the same category c, but with various failure levels. The selected edge e is the one whose labeled level of failure regarding c corresponds to the c-level of failure of the observations.

2. If the obtained node n following edge e is a leaf, then the global level of failure of the observations according to T is the coordinate of the unique non zero component of the tuple.

If not, the tree walk is continued at item 1 with node n as new root.

The global diagnostics for the given observation is a majority consensus of all the responses of all the trees in the forest.

Numerical simulations

The training set is obtained by simulating 100 observations for 10 successive times, which results in 1000 instances. The resulting data base is then used to train 100 trees that will constitute the trained random forest.

Figure 2 presents the delay between the time the system enters a failure mode and the time of its detection. This is done in the absence of correlations between the different features. The 0 time value of delay, the negative values, and positive value refer to in-time predictions, early predictions and late predictions of failures, respectively. The plotted values are the average result per number of simulations which varies from 1 to 100. With time, sensor nodes start to fail in order to simulate missing data packets. As a result, the RF algorithm was able to detect 54% of the failures either in time or before their occurrence.

For each of the 100 performed simulations, we calculated the average number of errors in fault detection, produced by the trees in the forest. Figure 3 shows that this error rate remained below 15% through the simulation. This error rate includes both "too early" and "too late" detections. When certain sensor nodes stop functioning, this leads to a lack on information, which has an impact on the quality of predictions; this explains a sudden increase in the error rate with time. We can conclude from the low error rate in the absence of some data packets that increasing the number of trees in the RF helps improve the quality and accuracy of predictions.

As described in Section 5, a correlation was introduced between the features. Figure 4 shows the number of successful diagnostics when the number of tree estimators in the forest changes. As shown in this figure, the RF method guarantees a 60% success rate when the number of trees is limited to 5.

As this number grows, the accuracy of the method increases to reach 80% when the number of trees is around 100.

Comparing to the previous results, the correlation between the features helps decrease the incertainties in diagnostics when the number of trees increases. The algorithm is able to understand the relationship between two features. Thus, when some values describing a feature are missing, the algorithm can deduct them from the available information about the rest features.

CONCLUSION

Instead of using wired sensor networks for a diagnostics and health management method, it is possible to use wireless sensors. Such a use can be motivated by cost reasons or due to specific particularities of the monitored device. In the context of a changing number and quality of provided features, the use of random forests may be of interest. These random classifiers were recalled with details in this article, and the reason behind their use in the context of a wireless sensors network monitoring was explained. Finally, algorithms and first examples of use of these random forests for diagnostics using a wireless sensor network were provided. The simulation results showed that the algorithm guarantees a certain level of accuracy even when some data packets are missing.

In future work, the authors' intention is to compare various tools for diagnostics to the random forests, either when considering wireless sensor networks or wired ones. Comparisons will be carried out on both theoretical and practical aspects. The algorithm of random forests, for its part, will be extended to achieve prognostics and health management too. Finally, the method for diagnosing an industrial device will be tested on a life size model, to illustrate the effectiveness of the proposed approach.

  . They are directed to (at most) 5 new vertices containing the tuples {j | F τj = n and d τ i j i has a c level equal to l i } n=1,..,5

Figure 1 .

 1 Figure 1. Example of a tree in the random forest.

Figure 2 .

 2 Figure 2. Delay in failure detection with respect to the number of simulations.

Figure 3 .

 3 Figure 3. Error rate in diagnostics with respect to the number of simulations

Figure 4 .

 4 Figure 4. Number of successful diagnostics with respect to the number of trees.

Table 1 .

 1 Limitations of diagnostic models

	Diagnostic model Drawbacks
	Markovian process -Aging is not considered
		-Different stages of degradation
		process cannot be accounted for
		-Large volume of data is required
		for the training
		-The assumptions are not always
		practical
	Bayesian networks -Prior transitions are not considered
		-Complete reliance on accurate
		thresholds
		-Many state transitions are needed
		for efficient results
		-Unable to predict unanticipated
		states
	Neural networks	-Significant amount of data for the
		training
		-Retraining is necessary with every
		change of conditions
		-Pre-processing is needed to reduce
		inputs
	Fuzzy systems	-Increasing complexity with every
		new entry
		-Domain experts are required
		-Results are as good as the develop-
		ers' understanding

ACKNOWLEDGMENTS

This work is supported by the region of Franche-Comté, which we thank.

BIOGRAPHY[

Wiem Elghazel received her Bachelor degree in computer science from University of science in Tunisia, and her Masters degree in A.I. and decision making support from INSA Lyon. Her research work included efficient packet transfer and energy consumption in wireless sensor networks. Currently, she is a PhD student at femto-st laboratry, AS2M department (Automatique et Systèmes Micro-Mécatroniques) in Besançon. She is studying the dependability of wireless sensor netwrks to provide accurate data as a solid ground for accurate remaining useful life estimates in industrial prognostics and health management.

Ahmad Farhat received the M.Sc degree in Computer Science and Risk Management from Lebanese University in 2014. Currently, he is a PhD student at femto-st laboratry in Besançon and Lebanese University in Beirut. He is studying the dependability of wireless sensor networks to provide accurate data as a solid ground for accurate remaining useful life estimates in industrial prognostics and health management.

Jacques Bahi was born in July 25th, 1961. He received the M.Sc. And PhD degrees in applied mathematics from the University of Franche-Comté, France in 1991.From 1992 to 1999, he was an Associate Professor of applied mathematics at the Mathematical Laboratory of Besançon. His research interests were focused on parallel synchronous and asynchronous algorithms for differential algebraic equations and singular systems. Since September 1999, he has been a full professor of computer science at the University of Franche-Comté. He published about 150 articles in peer reviewed journals and international conferences and 2 scientific books. Dr. Bahi is the head of the Distributed Numerical Algorithms team of the Computer Science Laboratory of Besançon, he supervised 21 PhD students. He is a member of the editorial board of 2 international journals and is regularly a member of the scientific committees of many international conferences. Currently, he is interested in: 1) high performance computing, 2) distributed numerical algorithms for ad-hoc and sensor networks, and 3) dynamical systems with application to data hiding and privacy.

Christophe Guyeux has taught mathematics and computer science in the Belfort-Montbéliard University Institute of Technologies (IUT-BM) this last decade.

He has defended a computer science thesis dealing with security, chaos, and dynamical systems in 2010 under Jacques Bahi's leadership, and is now an associated professor in the computer science department of complex system (DISC), FEMTO-ST Institute, University of Franche-Comté. Since 2010, he has published 2 books, 17 articles in international journals, and 27 articles dealing with security, chaos, and bioinformatics.