Keywords: traitement de flux en réseau, arbres d'opérateurs, multiples applications concurrentes, placement d'opérateurs, heuristiques polynomiales

Stratégies d'allocation de ressources pour plusieurs applications pipelinées concurrentes

Résumé : Dans ce rapport, on s'intéresse à des applications qui traitent des flux de données de manière pipelinée. Chaque application consiste en un arbre d'opérateurs qu'on applique sur les données successives. En régime permanent, les opérateurs interrogent des bases de données qui sont mises à jour périodiquement. L'objectif est de calculer le résultat final à un débit fixé. Des arbres d'opérateurs distincts peuvent partager des résultats. De ce fait, il peut être possible de réutiliser quelques résultats intermédiaires pour traiter différentes applications.

La première contribution de ce travail est l'obtention de résultats de complexité pour les différentes instances du problème, ainsi que la formulation de ces instances en terme de programme linéaire. La deuxième contribution est le développement de plusieurs heuristiques polynomiales. La réutilisation des résultats intermédiaires partagés par plusieurs applications est un objectif premier de ces heuristiques. Nos comparaisons par simulation des heuristiques démontrent toute l'importance du choix des processeurs pour le placement des opérateurs. De même elles nous permettent d'identifier une heuristique performante, qui obtient de bons résultats dans la pratique.

Introduction

We consider the execution of applications structured as trees of operators, where the leaves of the tree correspond to basic data objects that are distributed over servers in a distributed network. Each internal node in the tree denotes the aggregation and combination of the data from its children, which in turn generates new data that is used by the node's parent. The computation is complete when all operators have been applied up to the root node, thereby producing a final result. We consider the scenario in which the basic data objects are constantly being updated, meaning that the tree of operators must be applied continuously. The goal is to produce final results at some desired rate. This problem is called stream processing [START_REF] Badcock | Models and issues in data stream systems[END_REF] and arises in several domains.

An important domain of application is the acquisition and refinement of data from a set of sensors [START_REF] Srivastava | Operator Placement for In-Network Stream Query Processing[END_REF][START_REF] Madden | The design of an acquisitional query processor for sensor networks[END_REF][START_REF] Bonnet | Towards sensor database systems[END_REF]. For instance, [START_REF] Srivastava | Operator Placement for In-Network Stream Query Processing[END_REF] outlines a video surveillance application in which the sensors are cameras located at different locations over a geographical area. The goal of the application could be to identify monitored areas in which there is significant motion between frames, particular lighting conditions, and correlations between the monitored areas. This can be achieved by applying several operators (e.g., filters, pattern recognition) to the raw images, which are produced/updated periodically. Another example arises in the area of network monitoring [START_REF] Cranor | Gigascope: highperformance network monitoring with an SQL interface[END_REF][START_REF] Van Rennesse | Scalable Management and Data Mining Using Astrolabe[END_REF][START_REF] Cooke | Reclaiming Network-wide Visibility Using Ubiquitous End System Monitors[END_REF]. In this case routers produce streams of data pertaining to forwarded packets. More generally, stream processing can be seen as the execution of one of more "continuous queries" in the relational database sense of the term (e.g., a tree of join and select operators). A continuous query is applied continuously, i.e., at a reasonably fast rate, and returns results based on recent data generated by the data streams. Many authors have studied the execution of continuous queries on data streams [START_REF] Babu | Continuous Queries over Data Streams[END_REF][START_REF] Liu | Continual Queries for Internet Scale Event-Driven Information Delivery[END_REF][START_REF] Chen | Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries[END_REF][START_REF] Plale | Dynamic Querying of Streaming Data with the dQUOB System[END_REF][START_REF] Kräme | A Temporal Foundation for Continuous Queries over Data streams[END_REF].

In practice, the execution of the operators must be distributed over the network. In some cases the servers that produce the basic objects may not have the computational capability to apply all operators. Besides, objects must be combined across devices, thus requiring network communication. Although a simple solution is to send all basic objects to a central compute server, it often proves unscalable due to network bottlenecks. Also, this central server may not be able to meet the desired target rate for producing results due to the sheer amount of computation involved. The alternative is then to distribute the execution by mapping each node in the operator tree to one or more servers in the network, including servers that produce and update basic objects and/or servers that are only used for applying operators. One then talks of in-network stream-processing. Several in-network stream-processing systems have been developed [START_REF] Daniel J Abadi | The Design of the Borealis Stream Processing Engine[END_REF][START_REF] Cherniack | Scalable distributed stream processing[END_REF][START_REF] Huebsch | Querying the Internet with PIER[END_REF][START_REF] Liang Chen | GATES: a grid-based middleware for processing distributed data streams[END_REF][START_REF] Nath | IrisNet: An Architecture for Internet-scale Sensing Services[END_REF][START_REF] Van Rennesse | Scalable Management and Data Mining Using Astrolabe[END_REF][START_REF] Chen | NiagaraCQ: A scalable continuous query system for internet databases[END_REF][START_REF] Logothetis | Wide-Scale Data Stream Management[END_REF]. These systems all face the same question: where should operators be mapped in the network?

In this paper we address the operator-mapping problem for multiple concurrent in-network stream-processing applications. The problem for a single application was studied in [START_REF] Pietzuch | Network-Aware Operator Placement for Stream-Processing Systems[END_REF] for an ad-hoc objective function that trades off application delay and network bandwidth consumption. In a recent paper [START_REF] Benoit | Resource Allocation Strategies for Constructive In-Network Stream Processing[END_REF] we have studied a more general objective function, enforcing the constraint that the rate at which final results are produced, or throughput, is above a given threshold. This corresponds to a Quality of Service (QoS) requirement of the application and the objective is to meet this requirement while using as few resources as possible. In this paper we extend the work in [START_REF] Benoit | Resource Allocation Strategies for Constructive In-Network Stream Processing[END_REF] in two ways. First we study a "non-constructive" scenario, i.e., we are given a set of compute and network elements, and we attempt to use as few resources as possible while meeting QoS requirements. Instead, in [START_REF] Benoit | Resource Allocation Strategies for Constructive In-Network Stream Processing[END_REF], we studied a "constructive" scenario in which resources could be purchased and the objective was to spend as little money as possible. Second, and more importantly, while in [START_REF] Benoit | Resource Allocation Strategies for Constructive In-Network Stream Processing[END_REF] we studied the case of a single application, in this paper we focus on multiple concurrent applications that contend for the servers. Each application has its own QoS requirement and the goal is to meet them all. In this case, a clear opportunity for higher performance with a reduced resource consumption is to reuse common sub-expression between operator trees when applications share basic objects [START_REF] Pandit | Efficient in-network evaluation of multiple queries[END_REF]. We restrict our study to trees of operators that are general binary trees and discuss relevant special cases (e.g., left-deep trees [START_REF] Yannis | Query optimization[END_REF]). We consider target platforms that are either fully homogeneous, or with a homogeneous network but heterogeneous servers, or fully heterogeneous. Our specific contributions are twofold: (i) we formalize operator mapping problems for multiple in-network stream-processing applications and give their complexity;

(ii) we propose a number of algorithms to solve the problems and evaluate them via extensive simulation experiments.

The rest of this paper is organized as follows. In Section 2 we define our application and platform models, and we formalize a number of operator mapping problems. In Section 3 we discuss the computational complexity of our mapping problems and in Section ?? we give integer linear programming formulations. In Section 5 we propose several heuristics, which we evaluate in Section 6. Finally we conclude in Section 7 with a summary of our results and future directions.

Framework

Application Model

We consider K applications, each needing to perform several operations organized as a binary tree (see Figure 1). Operators are taken from the set OP = {op 1 , op 2 , . . . }, and operations are initially performed on basic objects from the set OB = {ob 1 , ob 2 , . . . }. These basic objects are made available and continuously updated at given locations in a distributed network. Operators higher in the tree rely on previously computed intermediate results, and they may also require to download basic objects periodically. For an operator op p we define objects(p) as the index set of the basic objects in OB that are needed for the computation of op p , if any; and operators(p) as the index set of operators in OP whose intermediate results are needed for the computation of op p , if any. We have the constraint that |objects(p)| + |operators(p)| ≤ 2 since application trees are binary. An application is fully defined by the operator at the root of its tree. For instance, if we consider Fig. 1, we have one application rooted on op 3 , and another application rooted on op 5 . Operator op 1 needs to download objects ob 1 and ob 2 , while operator op 2 downloads only object ob 1 but also requires an intermediate result from operator op 1 .

The tree structure of application k is defined with a set of labeled nodes. The i th internal node in the tree of application k is denoted as n (k) i , its associated operator is denoted as op(n (k) i ), and the set of basic objects required by this operator is denoted as ob(n

(k) i ). Node n (k) 1 is the root node. Let op p = op(n (k) i ) be the operator associated to node n (k) i . Then node n (k) i has |operators(p)| child nodes, denoted as n (k) 2i , n (k)
2i+1 if they exist. Finally, the parent of a node n (k) i , for i > 1, is the node of index ⌊i/2⌋ in the same tree. The applications must be executed so that they produce final results, where each result is generated by executing the whole operator tree once, at a target rate. We call this rate the application throughput, ρ (k) , and the specification of the target throughput is a QoS requirement for each application. Each operator in the tree of the k th application must compute (intermediate) results at a rate at least as high as the target application throughput ρ (k) . Conceptually, operator op p executes two concurrent threads in steady-state:

• It periodically downloads the most recent copies of the basic objects in objects(p), if any. Note that these downloads may simply amount to constant streaming of data from sources that generate data streams. Each download has a prescribed cost in terms of bandwidth based on application QoS requirements (e.g., so that computations are performed using sufficiently up-to-date data). A basic object ob j has a size d j (in bytes) and needs to be downloaded by the processors that use it for application k with frequency f (k) j . Therefore, these basic object downloads consume an amount of bandwidth equal to rate

(k) j = d j × f (k) j
on each network link and network card through which this object is communicated for application k. Note that if a processor requires object ob j for several applications with different update frequencies, it downloads the object only once at the maximum required frequency rate j = max k {rate (k) j }.

• It receives intermediate results computed by operators(p), if any, and it performs some computation using basic objects it is continuously downloading, and/or data received from other operators. The operator produces some output, which is either an intermediate result which will be sent to another operator, or the final result of the application (root operator). The computation of operator op p (to evaluate the operator once) requires w p operations, and produces an output of size δ p .

Platform Model

The target distributed network is a fully connected graph (i.e., a clique) interconnecting a set of processors P. These processors can be assigned operators of the application tree and perform some computation. Some processors also hold and update basic objects. Each processor P u ∈ P is interconnected to the network via a network card with maximum bandwidth B u . The network link between two distinct processors P u and P v is bidirectional and has bandwidth b u,v (= b v,u ) shared by communications in both directions. In addition, each processor P u ∈ P is characterized by a compute speed s u . Resources operate under the full-overlap, bounded multi-port model [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF]. In this model, a processor P u can be involved in comput-ing, sending data, and receiving data simultaneously. The "multi-port" assumption states that each processor can send/receive data simultaneously on multiple network links. The "bounded" assumption states that the total transfer rate of data sent/received by processor P u is bounded by its network card bandwidth B u . The case in which some dedicated processors are only providing basic objects but cannot be used for computations is obtained simply by setting their compute speed to 0.

Mapping Model and Constraints

Our objective is to map internal nodes of application trees onto processors. As explained in Section 2.1, if the operator associated to a node requires basic objects, the processor in charge of this internal node must continuously download up-to-date basic objects, which consumes bandwidth on its processor's network card. Each used processor is in charge of one or several nodes. If there is only one node on processor P u , while the processor computes for the t-th final result it sends to its parent (if any) the data corresponding to intermediate results for the (t -1)-th final result. It also receives data from its children (if any) for computing the (t + 1)-th final result. All three activities are concurrent (see Section 2.2). Note however that different nodes can be assigned to the same processor. In this case, the same overlap happens, but possibly on different result instances (an operator may be applied for computing the t 1 -th result while another is being applied for computing the t 2 -th). A particular case is when several nodes with the same operator are assigned to the same processor. In this case, computation is done only once for this operator, but it should occur at the highest required rate among those of the corresponding applications.

A basic object can be duplicated, and thus available and updated at multiple processors. We assume that duplication of basic objects is achieved in some out-of-band manner specific to the target application (e.g., due to the use of a distributed database infrastructure that allows consistent data replication). In this case, a processor can choose among multiple data sources when downloading a basic object, or perform a local access if the basic object is available locally. Conversely, if two nodes require the same basic object and are mapped to different processors, they must both continuously download that object (and incur the corresponding network overheads.)

We use an allocation function, a, to denote the mapping of the nodes onto the processors in P:

a(k, i) = u if node n (k) i
is mapped to processor P u . Conversely, ā(u) is the index set of nodes mapped on P u : ā(u) = {(k, i) | a(k, i) = u}. Also, we denote by a op (u) the index set of operators mapped on P u :

a op (u) = {p | ∃(k, i) ∈ ā(u) op p = op(n (k) i )}.
We introduce the following notations:

Ch(u) = {(p, v, k)}
is the set of (operator, processor, application) tuples such that processor P u needs to receive an intermediate result computed by operator op p , which is mapped to processor P v , at rate ρ (k) ; operators op p are children of a op (u) in the operator tree. P ar(u) = {(p, v, k)} is the set of (operator, processor, application) tuples such that P u needs to send to P v an intermediate result computed by operator op p at rate ρ (k) ; p ∈ a op (u) and the sending is done to the parents of op p in the operator tree. Do(u) = {(j, v, k)} is the set of (object, processor, application) tuples where P u downloads object ob j from processor P v at rate ρ (k) . The formal definition of Ch(u) and P ar(u) is as follows. We first define two sets of tuples, ACh(u) and AP ar(u), used to account for communications for the same data but for different applications:

ACh(u) = n (p, v, k) | ∃i, p ′ p ∈ aop(v); p ′ ∈ aop(u); p ∈ operators(p ′ ); opp = op(n (k) i ); op p ′ = op(n (k) ⌊i/2⌋ o AP ar(u) = n (p, v, k) | ∃i, p ′ p ∈ aop(v); p ′ ∈ aop(u); p ∈ operators(p ′ ); opp = op(n (k) i ); op p ′ = op(n (k) ⌊i/2⌋ o
Then we determine which application has the higher throughput for redundant entries, where arg max randomly chooses one application if there are equalities:

kchosen(p, v, X) = arg max k∈K n ρ (k) | ∃(p, v, k) ∈ X o Finally, X(u) = {(p, v, kchosen(p, v, AX)) | op p ∈ OP, P v ∈ P}.
X stands for Ch or P ar, and we have thus thus fully defined Ch(u) and P ar(u).

Given these notations, we can now express constraints for the application throughput: each processor must compute and communicate fast enough to respect the prescribed throughput of each application which is being processed by it. The computation constraint is expressed below. Note that each operator is computed only once at the maximum required throughput.

∀Pu ∈ P X p∈aop(u) max (k,i)∈ā(u) | op(n (k) i )=opp " ρ (k) " wp su ! ≤ 1 . (1)
Communication occurs only when a child or the parent of a given node and this node are mapped on different processors. In other terms, we neglect intra-processor communications. An operator computing for several applications may send/receive results to/from different processors. If the parent/child nodes corresponding to the different applications are mapped onto the same processor, the communication is done only once, at the most constrained throughput. This throughput, as well as the processors with which P u needs to communicate, are obtained via Ch(u) and P ar(u). In these expressions v = u since we neglect intraprocessor-communications.

The first part of Eq. 2 expresses constraints on receiving, while the second part refers to sending:

∀Pu ∈ P X (p,v,k)∈Ch(u) " ρ (k) δp bv,u « ≤ 1 ; ∀Pu ∈ P X (p,v,k)∈P ar(u) " ρ (k) δp bu,v « ≤ 1 . (2)
P u must have enough bandwidth capacity to perform all its basic object downloads, to support downloads of the basic objects it may hold, and also to perform all communication with other processors, all at the required rates. This is expressed in Eq. 3. The first term corresponds to basic object downloads; the second term corresponds to download of basic objects from other processors; the third term corresponds to inter-node communications when a node is assigned to P u and its parent node is assigned to another processor; and the last term corresponds to inter-node communications when a node is assigned to P u and some of its children nodes are assigned to another processor.

∀Pu ∈ P X (j,v,k)∈Do(u) rate (k) j + X Pv ∈P X (j,u,k)∈Do(v) rate (k) j + X (p,v,k)∈Ch(u) δpρ (k) + X (p,v,k)∈P ar(u) δpρ (k) ≤ Bu (3)
Finally, we need to express the fact that the link between processor P u and processor P v must have enough bandwidth capacity to support all possible communications between the nodes mapped on both processors, as well as the object downloads between these processors. Eq. 4 is similar to Eq. 3, but it considers two specific processors:

∀Pu, Pv ∈ P X (j,v,k)∈Do(u) rate (k) j + X (j,u,k)∈Do(v) rate (k) j + X (p,v,k)∈Ch(u) δpρ (k) + X (p,v,k)∈P ar(u) δpρ (k) ≤ bu,v (4)
RR n 6864

Optimization Problems

The overall objective of the operator-mapping problem is to ensure that a prescribed throughput per application is achieved while minimizing a cost function. Several relevant problems can be envisioned. Proc-Nb minimizes the number of processors enrolled for computations (processors that are allocated at least one node); Proc-Power minimizes the compute capacity and/or the network card capacity of processors enrolled for computations (e.g., a linear function of both criteria); BW-Sum minimizes the sum of the bandwidth capacities used by the application; and finally BW-Max minimizes the maximum percentage of bandwidth used on all links (minimizing the impact of the applications on the network for other users).

Different platform types may be considered depending on the heterogeneity of the resources. We consider the case in which the platform is fully homogeneous (s u = s, B u = B and b u,v = b), which we term Hom. The heterogeneous case in which network links can have various bandwidths is termed Het.

Each combination of problems and platforms could be envisioned, but we will see that Proc-Power on a Hom platform is actually equivalent to Proc-Nb. Proc-Nb makes more sense in this setting, while Proc-Power is used for Het platforms only. Both types of platforms are considered for the BW-Sum and BW-Max problems.

Complexity

Problem Proc-Nb is NP-complete in the strong sense. This is true even for a simple case: a Hom platform and a single application (|K| = 1), that is structured as a left-deep tree, in which all operators take the same amount of time to compute and produce results of size 0, and in which all basic objects have the same size. We refer the reader to a technical report for the proof [START_REF] Benoit | Resource Allocation Strategies for Constructive In-Network Stream Processing[END_REF], which relies on a straightforward reduction to 3-Partition, which is known to be NP-hard in the strong sense [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. It turns out that the same proof holds for Proc-Power on a Hom platform.

The BW-Max problem is NP-hard because downloading objects with different rates on two processors is the same problem as 2-Partition, which is known to be NP-hard [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Here is a sketch of the straightforward proof, which holds even in the case of a single application. Consider an application in which all operators produce zero-size results, and in which each basic object is used only by one operator. Consider three processors, with one of them holding all basic objects but unable to compute any operator. The two remaining processors are able to compute all the operators, and they are connected to the first one with identical network links. Such an instance can be easily constructed. The problem is then to partition the set of operators in two subsets so that the bandwidth consumption on the two network links in use is as equal as possible. This is exactly the 2-Partition problem.

The BW-Sum problem is NP-hard because it can be reduced to the Knapsack problem, which is NP-hard [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Here is a proof sketch for a single application. Consider the same application as for the proof of the NP-hardness of BW-Max above. Consider two identical processors, A and B, with A holding all basic objects. Not all operators can be executed on A and a subset of them need to be executed on B. Such an instance can be easily constructed. The problem is then to determine the subset of operators that should be executed on A. This subset should satisfy the constraint that the computational capacity of A is not exceeded, while maximizing the bandwidth cost of the basic objects associated to the operators in the subset. This is exactly the Knapsack problem.

All these problems can be solved thanks to an integer linear program (see Section 4). However, they cannot be solved in polynomial time (unless P=NP). Therefore, in the Section 5 we describe polynomial-time heuristics for one of these problems.

Linear Programming Formulation

In this section, we give an integer linear program (ILP) formulation of the Proc-Power-Het, BW-Sum-Het and BW-Max-Het problems, in terms of an integer linear program (ILP). These are the most general versions of our operator-mapping problems. More restricted versions, e.g., with Hom platforms, can be solved using the same ILPs. We describe the input data to the ILP, its variables, its constraints, and finally its objective functions.

In all that follows, i and i ′ are indices spanning nodes in set of nodes of an application tree; p and p ′ are indices spanning operators in OP; j is an index spanning objects in OB; u, u ′ , and v are indices spanning processors in P; k is an application index spanning K.

Input Data

Parameters δ i , w i for operators, rate (k) j for object download rates, and s u , B u , b u,v for processors and network elements, are rational numbers and defined in Section 2. ρ (k) is a rational number that represents the throughput QoS requirement for application k. For convenience, we also introduce families of boolean parameters: par, oper, and object, that pertain to application trees; and obj, that pertain to location of objects on processors. We define these parameters hereafter:

par(k, i, i ′ ) is equal to 1 if internal node n (k) i is the parent of n (k)
i ′ in the tree of application k, and 0 otherwise.

oper(k, i, p) is equal to 1 if op(n (k) i ) = p, and 0 otherwise. object(k, i, j) is equal to 1 if node n (k) i needs object ob j (i.e., p ∈ objects(op(n (k) i ))
), and 0 otherwise. obj(u, j) is equal to 1 if processor P u owns a copy of object ob j , and 0 otherwise.

Variables

x k,i,u is a variable equal to 1 if node n (k) i
is mapped on P u , and 0 otherwise. d j,u,v,k is a variable equal to 1 if processor P u downloads object ob j for application k from processor P v , and 0 otherwise.

y k,i,u,i ′ ,u ′ is a variable equal to 1 if n (k) i is mapped on P u , n (k) i ′ is mapped on P u ′ , and n (k) i is the parent of n (k) i ′ in the application tree.
used u is a variable equal to 1 if there is at least one node mapped to processor P u , and 0 otherwise. xop k,p,u is a variable equal to 1 if op p of application k is mapped to processor P u , and 0 otherwise. yop k,p,u,p ′ ,u ′ is a variable equal to 1 if op p of application k is mapped on processor P u , op p ′ of application k is mapped on processor P u ′ , and op p is a parent of op p ′ in application k, and 0 otherwise. Ch u,p,v,k is a variable equal to 1 if (p, v, k) ∈ Ch(u), and 0 otherwise. P ar u,p,v,k is a variable equal to 1 if (p, v, k) ∈ P ar(u), and 0 otherwise. rho u,p is a rational variable equal to the throughput of op p if it is mapped on processor P u , and 0 otherwise. ratemax j,u,v is a rational variable equal to the download rate of object ob j by processor P u from processor P v , and 0 otherwise.

Constraints

We first give constraints to guarantee that the allocation of nodes to processors is valid, and that each required download is done from a server that holds the relevant object. ∀k, i u x k,i,u = 1: each node is placed on exactly one processor; ∀j, u, v, k d j,u,v,k ≤ obj(v, j): object ob j can be downloaded from processor P v only if P v holds it; ∀i, j, u, k 1 ≥ v d j,u,v,k ≥ x k,i,u .object(k, i, j): processor P u must download object ob j from exactly one processor P v if there is a node n (k) i mapped on processor P u that requires ob j .

The next two constraints aim at properly defining variables y. Note that a straightforward definition would be y k,i,u,i ′ ,u ′ = par(k, i, i ′ ).x k,i,u .x k,i ′ ,u ′ , but this leads to a non-linear program. Instead we write, for all k, i, u, i ′ , u ′ :

y k,i,u,i ′ ,u ′ ≤ par(k, i, i ′ ); y k,i,u,i ′ ,u ′ ≤ x k,i,u ; y k,i,u,i ′ ,u ′ ≤ x k,i ′ ,u ′ : y k,i,u,i ′ ,u ′ is
forced to be 0 if one of these three conditions does not hold.

y k,i,u,i ′ ,u ′ ≥ par(k, i, j). x k,i,u + x k,i ′ ,u ′ -1 : y k,i,u,i ′ ,u ′ is
forced to be 1 only if the three conditions are true (otherwise the right term is lower than or equal to 0).

The following two constraints ensure that used u is properly defined:

∀u used u ≤ k,i
x k,i,u : processor P u is not used if no node is mapped to it; ∀k, i, u used u ≥ x k,i,u : processor P u is used if at least one node n i is mapped to it.

The following four constraints ensure that xop k,p,u and yop k,p,u are properly defined: ∀i, k, p, u xop k,p,u ≥ x k,i,u .oper(k, i, p): xop is forced to be 1 if operator op p of application k is mapped on processor P u ; ∀k, p, u xop k,p,u ≤ i x k,i,u .oper(k, i, p): xop is forced to be 0 if operator op p of application k is not mapped on processor P u ;

∀k, p, p ′ , u, u ′ , i, i ′ yop k,p,u,p ′ ,u ′ ≤ xop k,p,u ; yop k,p,u,p ′ ,u ′ ≤ xop k,p ′ ,u ′ ; yop k,p,u,p ′ ,u ′ ≤ par(k, i, i ′ ); yop k,p,u,p ′ ,u ′ ≤ oper(k, i, p); yop k,p,u,p ′ ,u ′ ≤ oper(k, i ′ , p ′ ): yop k,p,u,p ′ ,
u ′ is forced to be 0 if one of these conditions does not hold; ∀k, p, p ′ , u, u ′ , i, i ′ yop k,p,u,p ′ ,u ′ ≥ par(k, i, i ′ ).oper(k, i, p).oper(k.i ′ , p ′ ).(xop k,p,u +xop k,p ′ ,u ′ -1): yop k,p,u,p ′ ,u ′ is forced to be 1 only if all five conditions are true.

The next four constraints ensure that Ch u,p,v,k and P ar u,p,v,k are defined properly:

∀u, p, v, k Ch u,p,v,k ≤ p ′ yop k,p ′ ,
u,p,v : in application k, if the parent operator of operator op p , which is mapped on P v , is not mapped on processor P u , Ch is forced to be 0; ∀p ′ , u, p, v, k Ch u,p,v,k ≥ yop k,p ′ ,u,p,v : in application k, if operator op p of application k is mapped to P v and its parent operator in the application tree is mapped to P u , Ch is forced to be 1. ∀u, p, v, k P ar u,p,v,k ≤ p ′ yop k,p ′ ,v,p,u : in application k, if the parent operator of operator op p , which is mapped to P u , is not mapped to processor P v , P ar is forced to be 0; ∀p ′ , u, p, v, k P ar u,p,v,k ≥ yop k,p ′ ,v,p,u : in application k, if operator op p is mapped to P u and its parent operator in the application tree is mapped to P v , P ar is forced to be 1.

The following two constraints ensure that the throughput QoS requirement of each application, ρ (k) , is met: ∀k, u, p rho u,p ≥ xop k,p,u .ρ (k) : the throughput of processor P u , to which operator op p of application k is mapped, has to satisfy the throughput QoS requirement of application k; ∀k, p, u, v ratemax p,u,v ≥ d p,u,v,k .rate (k) p : the update rate of operator op p on processor P u has to satisfy the throughput QoS requirement of application k;

The following constraint ensures that the compute capacity of each processor is not exceeded while meeting QoS throughput requirements:

∀u p rho u,p wp su ≤ 1.
The following two constraints ensure that the bandwidth capacity of network elements are not exceeded: Bandwidth constraint for the processor network cards:

∀u p,v,k Ch u,p,v,k .rho u,p .δ p + p,v,k P ar u,p,v,k .rho u,p .δ p + j,v,k d j,u,v,k .ratemax j,u,v + j,v,k d j,v,u,k .ratemax j,v,u ≤ B u (5)
Bandwidth constraints for links between processors:

∀u, v p,k Ch u,p,v,k .rho u,p .δ p + p,k P ar u,p,v,k .rho u,p .δ p + j,k d j,u,v,k .ratemax j,u,v + j,k d j,v,u,k .ratemax j,v,u ≤ b u,v (6)

Objective Function

We have to define the objective function to optimize. We have a different definition for each problem:

Proc-Power-Het:

min u,p rho u,p w p s u . (7)
BW-Sum-Het:

min u,v,p,k Ch u,p,v,k .rho u,p .δ p + u,v,p,k P ar u,p,v,k .rho u,p .δ p + u,v,j,k d j,u,v,k .ratemax j,u,v + u,v,j,k d j,v,u,k .ratemax j,v,u . (8)
BW-Max-Het: For this problem we need to add one variable, bwmax, and |P| 2 constraints:

∀u, v p,k Ch u,p,v,k .rho u,p .δ p + p,k P ar u,p,v,k .rho u,p .δ p + j,k d j,u,v,k .ratemax j,u,v + j,k d j,v,u,k .ratemax j,v,u ≤ bwmax (9)
and the objective becomes: min (bwmax).

Heuristics

In this section we propose several polynomial heuristics1 for the Proc-Power problem, in which we consider only the compute capacity of processors enrolled for computation. Two heuristics use a random approach to process application nodes, while the others are based on tree traversals. As for the choice of an appropriate resource for the current node, four different processor selection strategies are implemented (and shared by all heuristics). Two selection strategies are blocking and two are non-blocking. Blocking means that once chosen for a given operator op 1 , a processor cannot be reused later for another operator op 2 , and it is only possible to add relatives (i.e., father or children) of op 1 to this processor. On the contrary, non-blocking strategies impose no such restrictions. We start with a description of the four processor selection strategies, and then we move to a brief overview of each heuristic.

Processor Allocation Strategies

(1) Fastest processor first (blocking) -Every time we have to chose a processor, the fastest remaining (not already chosen) processor is chosen.

(2) Biggest network card first (blocking) -Every time we have to chose a processor, the remaining processor with the biggest network card is chosen.

(3) Fastest remaining processor (non-blocking) -The actual amount of computation is subtracted from the computation capability, and the processor with the most remaining computation power is chosen.

(4) Biggest remaining network card (non-blocking) -In this strategy the current (already assigned) communication volume is subtracted from the network card capacity to evaluate the processor whose remaining communication capacity is the biggest. This processor is chosen.

Significance of Node Reuse

Our heuristics, except RandomNoReuse (H1), are designed for node reuse. This means that we try to benefit from the fact that different applications may have common subtrees, i.e., subtrees composed of the same operators. Instead of recomputing the result for such a subtree, we aim at reusing the result. For this purpose we try to add additional communications as can be seen in Figure 2. The processor that computes the left op 1 in application 1 sends its result not only to the processor that computes op 2 , but also to the processor that computes op 4 . The operator op 1 on the right of application 1 no longer has to be computed. In the same way, we save the whole computation of the subtree rooted by op 2 in application 2 when we add the communication between op 2 in application 1 and op 3 in application 2. We give hereafter a brief overview of each heuristic:

H1: RandomNoReuse

The H1 heuristic does not reuse any result. While there are unassigned operators, H1 randomly picks one of them. If the father is already mapped, it tries to map the operator on the father's processor, or it tries the children's processors, if those are already mapped. If none of these mappings is possible, H1 chooses a new processor according to the processor selection strategy, and maps the operator. If this is not possible, H1 fails.

H2: Random

The H2 random heuristic is more sophisticated as it tries to reuse common results. If the randomly chosen operator has not already been mapped, possibly for another application, we use the same mechanism as in H1: first try to map the operator on its father's processor or one of the children's, and in case of failure choose a new processor. But, if the operator has already been mapped somewhere else in the forest, we try to add a link from the already mapped operator to the father of the actual operator to reuse the common result. When this is possible, we mark the whole subtree (rooted at the operator) as mapped. Otherwise, we choose a new processor.

H3: TopDownBFS

The H3 heuristic performs a breadth-first-search (BFS) traversal of all applications. We use an artificial root node to link all applications, i.e., all application roots become children of the artificial root. For each operator, we check whether the operator has not been mapped yet and whether its father has. In this case, H3 tries to map the operator on the same processor as its father, and in case of success continues the BFS traversal. In the case where the actual operator has already been mapped onto one or more processors, H3 tries to add a communication link between the mapped operator and the father of the actual operator: the mapped operator sends its result not only to its father but also to the father of the actual operator. If none of these two conditions holds, or if the mapping was not possible, H3 tries to map the operator onto a new processor. The processor is chosen according to the processor selection strategy. When the mapping is successful, the BFS traversal is continued, otherwise H3 fails.

H4: TopDownDFS

The H4 heuristic uses the same mechanism as H3, but operators are treated in depth-firstsearch (DFS) manner. Thus, each time a mapping of a node is successful, the heuristic continues the DFS traversal of the current application tree.

H5: BottomUpBFS

As the H4 heuristic, the H5 heuristic makes a BFS traversal of the application forest. For this purpose we use the same mechanism of a new artificial root that links all applications.

For each operator, H5 verifies whether it has already been mapped on a processor. In this case a communication link is added (if possible), connecting the mapped operator and the father of the unmapped operator. If the operator is not yet mapped and if it has some children, we try to map the operator to one of its children's processors. If no such possibility is successful, or if the operator is at the bottom of a tree, H5 tries to map the operator onto a new processor (where the processor is chosen according to the processor selection strategy). When the mapping is successful, the BFS traversal continues, otherwise H5 fails.

H6: BottomUpDFS

The H6 heuristic is similar to H5, but instead of a BFS traversal, it performs a DFS traversal of the application forest. This makes the heuristic a little bit more complicated, as there are more cases to be considered. For each node we check if its operator has already been mapped on a processor, and none of its children are. In this case we go up in the tree until we reach the last node n 1 such that there exists a node n 2 somewhere else in the forest which is already mapped, and such that op(n 1 ) = op(n 2 ). In this case we try to add a communication between n 2 and the father of n 1 to benefit from the calculated result. If the children have already been mapped we simply try to map the operator to one of the children's processors. If this is not possible or if the additional communication was not possible or again if the operator has not been mapped anywhere in the forest, H6 tries to map the operator onto a new processor, according to the processor selection strategy. Otherwise H6 fails.

Experimental Results

We have conducted several experiments to assess the performance of the different heuristics described in Section 5. In particular, we are interested in the impact of node reuse on the number of solutions found by the heuristics.

Experimental Plan

Except for Experiment 1, all application trees are fixed to a size of at most 50 operators, and except for Experiment 5, we consider 5 concurrent applications. The leaves in the tree correspond to basic objects, and each basic object is chosen randomly among 10 different types. The size d of each object type is also chosen randomly and varies between 3MB and 13MB. The download frequencies of objects for each application, f , as well as the application throughput, ρ, are chosen randomly such that 0 < f ≤ 1 and 1 ≤ ρ ≤ 2. The parameters for operators are also chosen randomly. In all experiments (except Experiment 4), the computation amount w i for an operator lies between 0.5MFlop/sec and 1.5MFlop/sec, and the output size of each operator δ i is randomly chosen between 0.5MB and 1.5MB. Throughout most of our experiences we use the following platform configuration (variants will be mentioned explicitly when needed.) We dispose of 30 processors. Each processor is equipped with a network card, whose bandwidth limitation varies between 50MB and 180MB. We use the same range for computation power, i.e., CPU speeds of 50MIPS to 180MIPS. The different processors are interconnected via heterogeneous communication links, whose bandwidth are between 60MB/s and 100MB/s. The 10 different types of objects are randomly distributed over the processors. Execution time and communication time are scaled units, thus execution time is the ratio between computation amount and processor speed, while communication time is the ratio between object size (or output size) and link bandwidth.

To assess performances, we study the relative performance of each heuristic compared to the best solution found by any heuristic. This allows to compare the cost, in amount of resources used, of the different heuristics. The relative performance for the heuristic h is obtained by:

1 |runs| |runs| r=1 a h (r)
, where a h (r) = 0 if heuristic h fails in run r and a h (r) = cost best (r) cost h (r) . cost best (r) is the best solution cost returned by one of the heuristics for run r, and cost h (r) is the cost involved by the solution proposed by heuristic h. Note that in the definition of the relative performance we do account for the case when a heuristic fails on a given instance. The number of runs is fixed to 50 in all experiments. The complete set of figures summarizing all experimental results is available on the web [START_REF]Diagrams of all experiments[END_REF].

Results

Experiment 1: Number of Processors

In a first set of experiments, we test the influence of the number of available processors, varying it from 1 to 70. Figure 3(a) shows the number of successes of the different heuristics using selection strategy 3 (biggest remaining network card). Between 1 and 20 processors, the number of solutions steeply increases for TopDownDFS, TopDownBFS and BottomUpBFS and for higher numbers of processors all three heuristics find solutions for most of the 50 runs. BottomUpDFS finds solutions when more than 30 processors are available. Random already finds solutions when only 20 processors are available, but for the runs with more than 30 processors, it finds fewer solutions than BottomUpDFS. RandomNoReuse is not successful at all, it does not find any solution. To summarize, TopDownBFS finds the most solutions, shortly followed by TopDownDFS and BottomUpBFS. Comparing the success rates of the different selection strategies, all heuristics find the most solutions using strategy 3, followed by strategy 4, strategy 2, and finally strategy 1. But the differences are small. More interesting is the relative performance of the heuristics using the different processor selection strategies in comparison to the number of solutions. Figure 4(a) shows the relative performance using strategy 3. Comparing with Figure 4(b), we can conclude that for the same number of successful runs, the performances of the heuristics significantly differ according to the selected processor selection strategy. Using strategy 3 (and also strategies 2 and 4), TopDownDFS performs better than TopDownBFS, which performs better than BottomUpBFS. However, BottomUpBFS outperforms both TopDown heuristics when strategy 1 is used. The performance of BottomUpDFS and of the random ones mirrors exactly the number of successful runs. As for the heuristics without reuse of common subtrees, we see that they do not find results until at least 35 processors are available (strategy 3) or even 60 (strategy 2). Independently of the processor selection strategy, both TopDown heuristics outperform all other heuristics in success and performance, but the results are poor (see Figure 3(b)).

Experiment 2: Number of Applications

In this set of experiments we vary the number of applications, K. As the number of application increases, all heuristics are less successful with strategies 1 and 2 than with strategies 3 and 4, and relative performance is poorer as well. Regardless of the strategy used, both TopDown heuristics show a better relative performance than BottomUpBFS, with the only exception using strategy 1 with a small number of applications (Figure 5(a)). BottomUpDFS and both random heuristics perform poorly. For instance, BottomUpDFS only finds solutions with up to 4 applications. The best strategy seems to be strategy 3 in combination with TopDownBFS for more than 10 applications and TopDownDFS for less than 10 applications (see Figure 5(b)).

Experiment 3: Application Size

When increasing the application sizes, strategy 3 is the most robust. Up to application sizes of 40 operators, the other strategies are competitive, but for applications bigger than 40 oper-ators both TopDown heuristics and BottomUpBFS achieve the best relative performance and find the most solutions. The success ranking of the three heuristics is the same, independently of the strategy: TopDownBFS finds more solutions than TopDownDFS, which, in turn, finds more solutions than BottomUpBFS. RandomNoReuse finds solutions for applications with fewer than 20 operators, BottomUpBFS up to 40 operators and Random up to 50 operators, but the number of solutions from the latter is poor. As far as relative performance is concerned, both TopDown heuristics achieve the best results for application sizes bigger than 20 using strategy 3. BottomUpDFS is competitive when using strategy 1 for applications smaller than 40 operators (compare Figures 6(a) and 6(b)). As for the heuristics without reuse of common subtrees, they no longer find results when application sizes exceed 40 operators. TopDown heuristics perform better, and the best strategy is one of the two non-blocking ones (3 or 4).

Experiment 4: Communication-to-Computation Ratio (CCR)

For this experimental set we introduce a new parameter, the CCR, which is the ratio between the mean amount of communications and the mean amount of computations, where the communications correspond to the output sizes of operators (δ i ) and the computations to the computational volume w i of the operators. When increasing the CCR, strategies 3 and 4 react very sensitively. As can be seen in Figure 7(a), TopDownBFS, TopDownDFS and BottomUpBFS have a 100% success rate for CCR ≤ 60, but then the success decreases drastically until no solution is found at all for a CCR of 180 (using strategy 2, TopDownBFS still finds 32 solutions). BottomUpDFS is largely outperformed by Random, and Random-NoReuse fails completely. In this experiment, strategy 2 seems to be the most successful processor selection strategy (see Figure 7(b)). TopDownBFS achieves the best results, followed by BottomUpBFS for CCR < 120, and by TopDownDFS for CCR > 120. Interestingly, the relative performances of the heuristics using the different strategies do not directly mirror their success rates. Compare Figures 8(a) and 8(b): BottomUpBFS finds fewer solutions using strategy 1 than 2, but its relative performance using strategy 1 and CCR smaller than 80 is better than when using strategy 2. Furthermore, TopDownBFS using strategy 1 always finds the most solutions of all heuristics, but its relative performance is only the best when the CCR becomes bigger than 120. Also, TopDownDFS finds fewer solutions than TopDownBFS and BottomUpBFS using strategy 2 and CCR= 30, but its relative performance is the best.

Experiment 5: Similarity of Applications

In this last experiment, we use only two applications for each run and the processing platform is smaller, consisting of only 10 processors. We study the influence on our heuristics when applications are very similar or completely different. For this purpose we create applications that differ in more and more operators. Strategies 1 and 2 are more sensitive to application differences and we observe the following ranking for the success of the heuristics: strategy 3 > strategy 4 > strategies 1 and 2, which have similar success rates (compare Figures 9(a) and 9(b).) The ranking of the heuristics within the different strategies is the same: TopDownBFS is the most successful, followed by TopDownDFS and BottomUpBFS. Bot-tomUpDFS and Random keep the fourth place, while RandomNoReuse fails. TopDownBFS has the best relative performance using the blocking strategies, whereas in the non-blocking cases TopDownDFS achieves the best results, which is important as its success rate is slightly poorer. BottomUpBFS always ranks at the third position.

Summary of Experiments

Our results show that a random approach for multiple applications is not feasible. Neglecting the possibility to reuse results from common subtrees dramatically limits the success rate and also the quality of the solution in terms of cost. The TopDown approach turns out to be the best, whereupon in most cases BFS traversal achieves the best result. The BottomUp approach is only competitive using a BFS traversal. The DFS traversal seems unable to reuse results efficiently (it often finds itself with no bandwidth left to perform necessary communications.) Furthermore we see a strong dependency of the processor selection strategy on solution quality. The blocking strategies outperform the non-blocking strategies when the CCR is large. In the other cases, TopDownBFS in combination with strategy 3 proves to be a solid combination.

Conclusion

In this paper, we have studied the operator mapping problem of multiple concurrent innetwork stream-processing applications onto a collection of heterogeneous processors. These stream-processing applications come as a set of operator trees, that have to continuously download basic objects at different sites of the network and at the same time have to process this data to produce some final result. We have considered the problem under a nonconstructive scenario, in which a fixed set of computation and communication resources is available and the goal is to minimize a cost function. Four different optimization problems were identified. All are NP-hard but can be formalized as integer linear programs. On the practical side we focused on one of the optimization problems, for which we designed a set of polynomial-time heuristics. We evaluated these heuristics via extensive simulations, and our experiments showed the importance of node reuse across applications. Reusing nodes leads to an important number of additional solutions, and also the quality of the solutions improves considerably. We concluded that top-down traversals of the application trees is more efficient INRIA than bottom-up approaches, and in particular the combination of a top-down traversal with a breadth-first search (i.e., our heuristic TopDownBFS) achieved good results across the board.

As future work, we could develop heuristics for the other optimization problems defined in Section 2.4. We could also envision a more general cost function w i,u (time required to compute operator i onto processor u), in order to express even more heterogeneity. This would lead to the design of more sophisticated heuristics. Also, we believe it would be interesting to add a storage cost for objects downloaded onto processors, which could lead to new objective functions. Finally, we could address more complicated scenarios with many (conflicting) relevant criteria to consider simultaneously, some related to performance (throughput, response time), some related to safety (replicating some computations for more reliability), and some related to environmental costs (resource costs, energy consumption).

2 Figure 1 :

 21 Figure 1: Sample applications structured as binary trees of operators.

Figure 2 :

 2 Figure2: Example for the reuse of nodes. op 1 is only computed once and its result is reused for the computation of op 2 and op 4 . op 3 uses the result of op 2 in application 1 for its computation.

  Successful runs without reuse, strategy 3

Figure 3 :

 3 Figure 3: Experiment 1: Increasing number of processors. Number of successful runs.

  Relative performance, strategy 1

Figure 4 :

 4 Figure 4: Experiment 1: Increasing number of processors. Relative performance.

Figure 5 :

 5 Figure 5: Experiment 2: Increasing number of applications.

Figure 6 :

 6 Figure 6: Experiment 3: Relative performance for increasing application sizes.

  Successful runs, strategy 2

Figure 7 :

 7 Figure 7: Experiment 4: Communication-Computation Ratio CCR. Number of successful runs.

  Relative performance, strategy 2

Figure 8 :

 8 Figure 8: Experiment 4: Communication-Computation Ratio CCR. Relative performance.

  Successful runs, strategy 3

Figure 9 :

 9 Figure 9: Experiment 5: Similarity of applications.

RR n 6864

To ensure the reproducibility of our results, the code for all heuristics is available on the web[START_REF]Source Code for the Heuristics[END_REF].INRIA


Dr Silvio Galli
email: sgalli@chu-besancon.fr.

M Béreau

E Magnin

T Moulin

Functional movement disorders

Keywords: Functional neurological disorder, Functional movement disorder, Psychogenic, Conversion disorder

Functional movement disorders (FMD) represent a complex and disabling entity characterized by a broad range of clinical symptoms not explained by a classical neurological disease. In 2013, the Diagnostic and Statistical Manual of Mental Disorders (DSM-5) added a clinical criterion based on incongruence and inconsistency, supported by recent literature highlighting the role of "positive clinical signs". These clinical signs allow a "rule-in" procedure in making a diagnosis of FMD so that the diagnosis is no longer a "rule-out" or "by default" diagnosis made after exclusion of other neurological conditions. This review summarizes current evidence on common clinical features and highlights bedside signs in FMD, such as tremor, dystonia, myoclonus and parkinsonism. Tics, chorea and hemiballism are also briefly discussed.

Introduction:

(FMD) are frequent and disabling. They include mainly tremor, dystonia, myoclonus and parkinsonism and belong to a larger entity called functional neurological disorders (FND).

FND comprise neurological symptoms that cannot be explained by a classical neurological disease. Consequently, FND are embodied by a broad phenomenological spectrum that encompasses non-epileptic seizures, sensorimotor deficits, gait abnormalities as well as abnormal movements. Importantly, FND are involuntary by nature and must be distinguished from factitious disorders and malingering [START_REF] Galli | Conversion, Factitious Disorder and Malingering: A Distinct Pattern or a Continuum?[END_REF]. However, clinicians use a variety of terms, including "psychogenic", "conversive", "dissociative" or "hysteria", thus maintaining some stigma. In the latest version of the Diagnostic and Statistical Manual of Mental Disorders (DSM-5) [START_REF]American Psychiatric Association. Diagnostic and statistical manual of mental disorders[END_REF], the term FND is used in the interests of standardization. It refers to pathophysiological mechanisms highlighted by recent neuro-imaging findings supporting a dysfunction in complex neural networks [START_REF] Aybek | Neural correlates of recall of life events in conversion disorder[END_REF][START_REF] Aybek | Imaging studies of functional neurologic disorders[END_REF]. The term functional is thus now added to the term "conversion" based on Sigmund Freud's theories (the symptom represented a conversion of an intra-psychic conflict into a physical sign) [START_REF] De Bustos | Clinical Manifestations of Hysteria: An Epistemological Perspective or How Historical Dynamics Illuminate Current Practice[END_REF]. Furthermore, DSM diagnostic criteria for FND have been modified, with removal of the previously required association with a psychological precipitant, which may be difficult to investigate in clinical practice and is rather unspecific [START_REF]American Psychiatric Association. Diagnostic and statistical manual of mental disorders[END_REF]. Simulation was also formally discarded, since a diagnosis of certainty could only be based on either confession by the patient, or evidence of feigning, which are both extremely rare in clinical practice [START_REF]American Psychiatric Association. Diagnostic and statistical manual of mental disorders[END_REF]. An important step forward is the integration of "clinical findings providing evidence of incompatibility between the symptom and recognized neurological or medical conditions". Indeed, recent literature has focused on the so-called "positive clinical signs" such as Hoover's sign in functional paresis, or closed eyes during non-epileptic seizure. Some of these signs especially sensorimotor showed an excellent specificity (92-100%) but a low sensibility (8-100%) with acceptable inter-observer agreement [START_REF] Daum | The value of "positive" clinical signs for weakness, sensory and gait disorders in conversion disorder: a systematic and narrative review[END_REF][START_REF] Daum | Interobserver agreement and validity of bedside "positive signs" for functional weakness, sensory and gait disorders in conversion disorder: a pilot study[END_REF]. Therefore, the diagnosis of FND includes positive criteria and is no longer a purely exclusionary approach. Some practitioners have even proposed to show these signs to patients, in order to facilitate understanding and acceptation of the diagnosis [START_REF] Stone | Trick or treat?: Showing patients with functional (psychogenic) motor symptoms their physical signs[END_REF].

The aim of the present article is to review "positive clinical signs" in FMD. We focus on tremor, dystonia, myoclonus and Parkinsonism, and briefly discuss tic, chorea and hemiballism. We do not discuss gait disorders, because although they can be considered as FMD, they may also belong to other forms of FND such as sensorimotor deficit.

Epidemiology

The prevalence of FND in neurological inpatients is consistently reported to be between 1 and 9%, while incidence is between 4 and 12 per 100,000 population per year [START_REF] Marsden | Hysteria, a neurologist's view[END_REF][START_REF] Lempert | Psychogenic disorders in neurology: frequency and clinical spectrum[END_REF][START_REF] Akagi | The epidemiology of hysterical conversion[END_REF]. Medically unexplained symptoms represent 30% of neurological consultations and often have a chronic course [START_REF] Carson | Do medically unexplained symptoms matter? A prospective cohort study of 300 new referrals to neurology outpatient clinics[END_REF][START_REF] Carson | The outcome of neurology outpatients with medically unexplained symptoms: a prospective cohort study[END_REF]. Symptoms have been reported to persist or worsen in 39% during follow up of 7.4 years, according to the type of symptom [START_REF] Gelauff | The prognosis of functional (psychogenic) motor symptoms: a systematic review[END_REF]. In Neurology departments specialized in abnormal movement, the prevalence of FMD ranged from 3.3 to 3.6%, with 40.6 to 50% of patients having tremor, 17.2 to 18% dystonia, 4.3 to 14% myoclonus and 7 to 39.8% Parkinsonism [START_REF] Factor | Psychogenic movement disorders: frequency, clinical profile, and characteristics[END_REF][START_REF] Thomas | Psychogenic movement disorders[END_REF][START_REF] Polara | Prevalence of functional (psychogenic) parkinsonism in two Swiss movement disorders clinics and review of the literature[END_REF]. It is probably under estimated in the elderly [START_REF] Batla | Functional movement disorders are not uncommon in the elderly[END_REF]. Mean age at FMD onset is 40 to 50 years with preponderance of female patients (2.5 females for 1 male) [START_REF] Factor | Psychogenic movement disorders: frequency, clinical profile, and characteristics[END_REF][START_REF] Thomas | Psychogenic movement disorders[END_REF].

In the setting of FND, compared to the general population, psychiatric comorbidity have been reported to be frequent; up to 43% having major depression, 61% anxiety disorder (both in 28% of cases) and 45% personality disorder [START_REF] Feinstein | Psychiatric outcome in patients with a psychogenic movement disorder: a prospective study[END_REF]. Overall, prevalence of psychiatric comorbidity can reach 89% of FND and it is frequently associated with sexual abuse, physical negligence and self-harm behaviour [START_REF] Sar | Childhood trauma, dissociation, and psychiatric comorbidity in patients with conversion disorder[END_REF]. Furthermore, childhood trauma and recent life events seem to play a role in the occurrence and severity of the disorder [START_REF] Roelofs | The Impact of Early Trauma and Recent Life-Events on Symptom Severity in Patients With Conversion Disorder[END_REF]. Generally, FMDs are considered sporadic disorders but family history is described and may be an additional risk factor [START_REF] Stamelou | Familial psychogenic movement disorders[END_REF]. Few studies have focused on differences between cultures and only one has compared American and Spanish populations, and found no significant differences (e.g. in terms of symptoms, age, or sex ratio) [START_REF] Cubo | Transcultural comparison of psychogenic movement disorders[END_REF].

Common clinical characteristics :

FMD share some common characteristics (see Table 1), which were the basis for the diagnostic criteria developed by Fahn and Williams in 1988, defining four categories, namely documented, clinically established, clinically probable and clinically possible [START_REF] Fahn | Psychogenic dystonia[END_REF]. These criteria were subsequently updated in 2009 by Gupta and Lang, who proposed a simplified classification of diagnostic certainty incorporating electrophysiological assessment [START_REF] Gupta | Psychogenic movement disorders[END_REF][START_REF] Gasca-Salas | Neurologic diagnostic criteria for functional neurologic disorders[END_REF].

Classically, onset of FMD is sudden and often with a precipitating trigger [START_REF] Edwards | Functional (psychogenic) movement disorders: merging mind and brain[END_REF]. The course of the disorder includes periods of remission (which may be complete) and is variable over time, with worsening and sometimes even a change in the nature of the disorder [START_REF] Hallett | Functional (psychogenic) movement disorders -Clinical presentations[END_REF]. A "selective" handicap for a certain type of activity is often present, reflecting discordance with the physical examination of the patient and the socio-professional impact of the disorder. In general, FMD are inconsistent, with variability, distractibility and the possible presence of entrainment (this sign is discussed in further detail below) [START_REF] Barbey | Functional movement disorders[END_REF]. Recently, the "whack-a-mole" sign has been described, whereby, if the involuntary movements of one body part are suppressed by holding it, then the involuntary movements will migrate to other limbs, and possibly even occur with greater magnitude [START_REF] Park | The "Whack-a-Mole" Sign in Functional Movement Disorders[END_REF]. FMD present some discordances with abnormal movements of organic origin that are established and responsive to suggestibility, either by administration of a placebo or other means. The association of different types of FMD is possible and FMD may also be associated with other types of FND. The following sections describe the clinical signs specific to each type of FMD (see Table 2).

Tremor:

Tremor is defined as a rhythmic and oscillatory movement of a body part resulting from synchronised alternating contraction of agonist and antagonist muscles. Functional tremor is the most common FMD. By contrast with organic tremor, functional tremor often displays wide variability in terms of amplitude, frequency, or direction, and may be present at rest, during action or on posture [START_REF] Deuschl | Diagnostic and pathophysiological aspects of psychogenic tremors[END_REF]. Functional tremor mainly affects the upper limbs, although the fingers are usually spared. The following is a (non-exhaustive) list of useful clinical tests to diagnose functional tremor:

•

Entrainment: This is likely the most useful clinical test to confirm the functional origin of tremor. The exact definition of the entrainment test varies across studies, and may sometimes be confused with distractibility. Basically, the subject is asked to perform a voluntary, repetitive movement with the contralateral limb at a given frequency (for example, tapping thumb and index, moving the tongue from one side to the other, flexionextension of the wrist, or auditory stimuli). The affected limb should be in the position where the tremor is most prominent, and the examiner should do the movement to set the imposed frequency, varying the tapping speed. The objective is to check whether the tremor takes up the frequency of the unaffected body part, and secondly, whether the patient has any difficulty following the requested rhythm with the healthy limb. Some authors have suggested that the test is positive if there is a change in tremor frequency (acceleration or slowing) or a pause [START_REF] Roper | How to use the entrainment test in the diagnosis of functional tremor[END_REF] ; however, this more close resembles distractibility than "pure" entrainment. The entrainment test is based on the fact that it is difficult for a normal or functional subject to generate and maintain two different rapid rhythms for a prolonged period. In organic tremor, the generation of the movement is independent [START_REF] Mcauley | Electrophysiological aids in distinguishing organic from psychogenic tremor[END_REF]. The sensitivity of the entrainment test is low (from 8.3 to 16%, and up to 39% with electrophysiological assessment), but specificity is high (from 75 to 95%) [START_REF] Kenney | Distinguishing psychogenic and essential tremor[END_REF][START_REF] Schwingenschuh | Moving toward "laboratory-supported" criteria for psychogenic tremor[END_REF].

• Distractibility: This test consists in diverting the subject's attention away from the tremor by asking them to perform different manoeuvers; for example, counting backwards from 7 to 0, performing ballistic movements with the contralateral limb, or repeatedly touching the thumb with the second, fifth then third fingers as fast as possible [START_REF] Kenney | Distinguishing psychogenic and essential tremor[END_REF]. In functional tremor, the tremor should diminish or stop altogether during these manoeuvers.

Distractibility tests are based on the same principle as the entrainment test, namely that it is extremely difficult to generate and maintain two different rhythms concurrently. Sensitivity of distractibility testing is quite high (between 58 and 73%), as is specificity (73 to 84%) [START_REF] Kenney | Distinguishing psychogenic and essential tremor[END_REF].

• Suggestibility: This consists in inducing a change in the symptom through the suggestion of ideas. For example, in their study, Kenney et al [START_REF] Kenney | Distinguishing psychogenic and essential tremor[END_REF] explained to patients that hyperventilating had been shown to increase tremor, or the application of a vibrating source to the body had been shown to improve tremor greatly. Then, they asked to the patient to hyperventilate for 10 seconds, or applied a vibrating tuning fork to the patient's forehead until vibration stopped spontaneously. The prevalence of this sign is 33% [START_REF] Kim | Historical and clinical features of psychogenic tremor: a review of 70 cases[END_REF], with a reported sensitivity of 42 to 50%, and specificity of 82 to 88% [START_REF] Kenney | Distinguishing psychogenic and essential tremor[END_REF].

• Coactivation: Coactivation can be tested in the same way as rigidity, namely by having the patient perform slow arrhythmic, passive movements of one or two joints. In functional tremor there might be an increased baseline tone which will thus fluctuate or even disappear with relaxation, as will the tremor itself [START_REF] Deuschl | Diagnostic and pathophysiological aspects of psychogenic tremors[END_REF]. No study has evaluated the sensitivity or specificity of this sign. Raethjen et al [START_REF] Raethjen | Two different pathogenetic mechanisms in psychogenic tremor[END_REF] compared accelerometry and electromyography (EMG) recordings in 15 patients with functional tremor manifesting in both hands. They reported that 7/15 patients showed significant coherency between the two hands, while the remaining 8 patients maintained independent oscillations. Those who had coherency between hands had a tremor below 6 Hz, which is close to "voluntary" tremor. In addition, this is coherent with the fact that it is impossible to voluntarily produce two oscillations of different frequencies. Conversely, those without coherency had oscillations in the 7-10 Hz band, which is a frequency similar to that of physiological tremor. This is the result of co-contraction and reflects hyperexcitability of motor neurons [START_REF] Rossi | Clonus in man: a rhythmic oscillation maintained by a reflex mechanism[END_REF].

Dystonia :

Dystonia is defined as a sustained or intermittent muscle contractions causing abnormal movements, postures or both. It is typically patterned and twisting, influenced par volontary action and associated with overflow muscle activation [START_REF] Albanese | Phenomenology and classification of dystonia: a consensus update[END_REF]. The origin of dystonia was long considered to be functional but there is now a distinction between organic dystonias (with some genetic forms now better characterized) and functional dystonia [START_REF] Munts | How psychogenic is dystonia? Views from past to present[END_REF].

The distinction is still difficult but some clinical features can be of help; a functional origin of dystonia is suspected when it is fixed at onset, whereas organic dystonia is often mobile at the initial phase. Sudden onset precipited by a minor physical trauma is strongly suggestive of functional origin [START_REF] Lang | Psychogenic dystonia: a review of 18 cases[END_REF]. Functional dystonia is suspected in the presence of an atypical localisation and age of onset, for example adult onset foot dystonia [START_REF] Fahn | Psychogenic dystonia[END_REF]. Functional dystonia spreads to other parts of the body (head, neck and trunk) with episodic exacerbation and might show an exaggerated and rapid improvement after botulinum toxin injections. Different phenotypes have been described according to the fixed or paroxysmal characteristics and the body's part affected [START_REF] Ganos | The phenomenology of functional (psychogenic) dystonia[END_REF]. The following are other important clinical clues (see Figure 1):

• Fixed dystonia : When dystonic posture reduce joint mobility; the absence of sensory tricks orients towards functional dystonia. Sensory tricks are voluntary manoeuvres that reduce the severity of dystonia. They can be observed in focal or generalized dystonia, and in primary or secondary dystonia, and may take several forms (for example, in focal cervical dystonia, the patient may hold their head with their hand) [START_REF] Ramos | Tricks in dystonia: ordering the complexity[END_REF]. These manoeuvers are usually absent in functional dystonia [START_REF] Munhoz | Gestes antagonistes in psychogenic dystonia[END_REF]. Furthermore patients present exaggerated pain during passive movements, as well as an active resistance [START_REF] Lang | Psychogenic dystonia: a review of 18 cases[END_REF].

• Paroxysmal dystonia : Defined by a sudden self-limited episodes of dystonia, it functional origin can be pointed out by an important variability between episodes especially for duration and phenomenology. Adulte age onset and atypical trigger may be helpful such as medical examination worsening symptomatology. Its were highlighted by Ganos et al [START_REF] Ganos | Psychogenic paroxysmal movement disorders-clinical features and diagnostic clues[END_REF] who described a group of functional paroxysmal movement disorders including dystonia, tremor, jerks and complex generalised movements.

• Body distribution : head, neck, upper limbs and especially lower limbs can be affected in functional dystonia.

Commonly for the lower limbs, there is a plantar flexion with inversion of the foot. The "psychogenic toe" sign has been described by Espay et al [START_REF] Espay | The psychogenic toe signs[END_REF] in focal dystonia of the big toe.

A noteworthy feature is the presence of passive spontaneous plantar flexion of the big toe on forced dorsiflexion of the second to fifth toes, which is observed in functional dystonia but not in organic (striatal) toe. This indicates preserved physiological synkinetic movements of coordination (as in the Hoover sign for paresis of the leg), whereas these signs are absent in abnormal movement (paralysis) that is not of functional origin.

Concerning upper limbs, fixed wrist and finger flexion with relative sparing of the thumb and index fingers are common, preserving pincer function [START_REF] Espay | Phenotype-Specific Diagnosis of Functional (Psychogenic) Movement Disorders[END_REF].

For the neck, controlateral lowering shoulder and an elevation of ispilateral shoulder relative to a laterocolis is typical in functional cervical dystonia.

Functional facial dystonia very often involves the lower part of the face, with unilateral contraction of the orbicularis muscle of the mouth downwards, with deviation of the ipsilateral cheek [START_REF] Stone | Functional movement disorders of the face: A historical review and case series[END_REF][START_REF] Fasano | Psychogenic facial movement disorders: Clinical features and associated conditions[END_REF]. This sign is called the "lip-pulling test" and may be accompanied by ipsilateral involvement of the platysma [START_REF] Fasano | Functional facial and tongue movement disorders[END_REF]. In the hemifacial spasm; frontalis and orbicularis oculis have an ispilateral contraction leading to an eyebrown elevation and eye closure called "other Babinski sign" [START_REF] Stamey | The other Babinski sign in hemifacial spasm[END_REF]. In functional dystonia, the eyebrown is raised controlateraly to the closed eye [START_REF] Fasano | Functional facial and tongue movement disorders[END_REF]. This can be accompagnied by a fluctuant resistance to passive opening eyelids. Futhermore, tongue may be helpful deviating in the "wrong way" towards the affected side in case of functional hemispam [START_REF] Fasano | Functional facial and tongue movement disorders[END_REF].

Parkinsonism:

Parkinsonism is characterised by bradykinesia in combination with at least one of rest tremor or rigidity [START_REF] Postuma | Validation of the MDS clinical diagnostic criteria for Parkinson's disease[END_REF][START_REF] Postuma | MDS clinical diagnostic criteria for Parkinson's disease[END_REF]. Functional parkinsonism is difficult to diagnose but Lafaver et al [START_REF] Lafaver | Diagnosis and treatment of functional (psychogenic) Parkinsonism[END_REF] proposed definite criteria based on examination findings like slowness and variable resistance supported by laboratory examination. The following clinical clues can help establishing the diagnosis [56-59] :

• Tremor: Tremor is present not only at rest, but also during action and on posture. Many of the characteristics are shared with functional tremor (see above), notably distractibility. Extended to the leg, tremor suggests functional parkinsonism [START_REF] Sage | Psychogenic parkinsonism: clinical spectrum and diagnosis[END_REF]. Classically, tremor in Parkinson's disease temporarily abates with a change of posture, and reappears maintaining an attitude ("re-emergent tremor") [START_REF] Belvisi | Re-emergent tremor in Parkinson's disease[END_REF]; these features are not observed in tremor of functional origin.

• Rigidity: The patient presents increased tone characterised by active and variable resistance against passive movement, which is amenable to distractibility.

"Cogwheel" rigidity is uncommon in patients with functional parkinsonism.

• Hypokinesia: Patients present excessively slow, deliberate movements, often associated with grimacing, tiredness or sighing called the "huffing and puffing sign" [START_REF] Laub | Diagnostic performance of the "huffing and puffing" sign in functional (psychogenic) movement disorders[END_REF].

During repetitive movements, the slowness is not progressive or accompanied by decrementing amplitude, a phenomenon known as the sequence effect and which is classically observed in Parkinson's disease.

• Postural/gait instability: Arm-swing in a patient with functional symptoms is diminished (mainly on the most affected side), with a stiff, extended arm, which is different from Parkinson's disease, where the arm is usually slightly flexed. When asked to run, there is no increase in arm-swing, contrary to parkinsonian patients. Postural stability testing (the pull test) often yields bizarre, atypical reactions. The patient may make exaggerated, inappropriate movements in an attempt to regain balance, e.g. wave or fling their arms and flail or reel backwards, without actually falling. In case of associated gait impairment, the"chair test" can be useful confronting abnormal ambulation with an easy propulsion when the patient is sitting on a swivel chair with wheels [START_REF] Okun | The "chair test" to aid in the diagnosis of psychogenic gait disorders[END_REF].

Myoclonus:

Myoclonus is defined as brief, sudden and involuntary contraction or inhibition of a muscle, generally caused by the central nervous system. Features that suggest a functional origin include variability or incoherence in amplitude, frequency and topographic distribution [START_REF] Kirkpatrick | Psychogenic myoclonus[END_REF][START_REF] Monday | Psychogenic myoclonus[END_REF]. Generally, the movement is more complex and prolonged and can occur at rest, during action, or, like organic myoclonus, may be reflex-induced. In this latter case, a long latency between the reflex movement and the myoclonus could be one of the clinical signs specific to functional origin, but no study has examined this point specifically. One of the most demonstrative example is functional axial jerk mimicking propriospinal myoclonus. The majority of "propriospinal myoclonus" adressed in a tertiary referral center finally has been reported to be functional [START_REF] Van Der Salm | Axial jerks: a clinical spectrum ranging from propriospinal to psychogenic myoclonus[END_REF]. Recently Van der salm et al [START_REF] Van Der Salm | Axial jerks: a clinical spectrum ranging from propriospinal to psychogenic myoclonus[END_REF][START_REF] Van Der Salm | Propriospinal myoclonus: Clinical reappraisal and review of literature[END_REF] proposed diagnostic criteria for functional axial jerk including anamnestic, clinical, neuroimaging and electrophysiological criteria. For instance facial movements or vocalizations associated with axial jerks argue in favor of functional myoclonus [START_REF] Van Der Salm | Axial jerks: a clinical spectrum ranging from propriospinal to psychogenic myoclonus[END_REF][START_REF] Esposito | Idiopathic spinal myoclonus: a clinical and neurophysiological assessment of a movement disorder of uncertain origin[END_REF].

Tics, chorea and hemiballism:

Regarding tics, there is a paucity data with only a small number of subjects studied to date. A functional origin is the observed etiology in 10% of all tics [START_REF] Mejia | Secondary tics and tourettism[END_REF]. Clinical clues include adult onset, non-stereotypical phenomenology, absence of premonitory sensation, inability to transiently suppress the tics, and prominent distractibility [START_REF] Baizabal-Carvallo | The clinical features of psychogenic movement disorders resembling tics[END_REF]. Demartini et al [START_REF] Demartini | A positive diagnosis of functional (psychogenic) tics[END_REF] also add to this definition the absence of pali-, echo-and copro-phenomena, and the fact that the tic can disrupt an ongoing action, termed "blocking tics", which is rare in organic tics. Tic is felt as intentional movement in order to suppress inner tension whereas functional tic is experienced totaly as involontary [START_REF] Ganos | Tics and Tourette syndrome[END_REF][START_REF] Cath | European clinical guidelines for Tourette syndrome and other tic disorders. Part I: assessment[END_REF][START_REF] Lang | Patient perception of tics and other movement disorders[END_REF]. Head is less commonly affected and absence of rostro-caudal distibution is seen in functional tics. More recently Ganos et al [START_REF] Ganos | I swear it is Tourette's!": On functional coprolalia and other tic-like vocalizations[END_REF] question some functional clinical clues such as adult onset (6 patients developed symptoms under 18 years-old) or sensory premonition (present in 9/13 patients). Finally, distinction between organic or functional tics is challenging because of sharing commun features. Diagnosis should be based more on a combination of symptoms. For chorea and hemiballism, in addition to the characteristics shared with other functional paroxysmal movement disorders, there are no other specific clinical signs yet reported to suggest a functional origin [START_REF] Ganos | Psychogenic paroxysmal movement disorders-clinical features and diagnostic clues[END_REF].

Conclusion :

In the era of technical progress in medicine, huge advances have been made in diagnostic procedures in domains like genetics, electrophysiology and imaging. This is of tremendous help but should not lead to a devaluation of the importance of the clinical examination. In particular, in the field of functional neurological disorders, the semiology and clinical examination remains of paramount importance and represents a reliable way to establish a diagnosis. Future multimodal diagnostic algorythms, combining semiology, electrophysiology imaging and biomarkers might increase the diagnostic certainty, which will only improve clinical care and research opportunities in this field. Currently, testing these positive signs at the bedside not only improves the diagnosis certainty but also allows a good communication with the patient, which is a very important first step towards treatment [START_REF] Stone | Trick or treat?: Showing patients with functional (psychogenic) motor symptoms their physical signs[END_REF][START_REF] Espay | Current concepts in diagnosis and treatment of functional neurological disorders[END_REF].

Declaration of interest: none Funding source: This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Table 1 -Anamnestic clues suggesting functional movement disorders, adapted from [26,29].

 1

	Sudden onset (maximal at the beginning)
	Waxing and waning course (spontaneous remission)
	Paroxysmal nature
	Migration around the body
	Association or change of type of FMD over time
	Association with other FND
	Psychiatric comorbidity
	Physical or psychological trauma (during childhood or/and recently)

FMD : Functional movement disorders; FND : functional neurological disorders

Abbreviations

FND: functional neurological disorder, FMD: functional movement disorder