PhD Laurent Goffart

Quinet Bourrelly

Neural processes underlying the foveation and tracking of a moving visual target

Questions at the root of Science

How assemblies of neurons distributed throughout the brain enable a subject with the ability to localize and pursue an object situated in the physical world ?

How to relate activities of microscopic elements (neurons) to macroscopic behavioral (kinematic) parameters ? What does this relation tell us ?

How to relate events unfolding in mediums of different complexity order, mediums characterized by radically different constraints and temporalities ? How assemblies of neurons distributed throughout the brain enable a subject with the ability to localize and pursue an object situated in the physical world ? How to relate activities of microscopic elements (neurons) to macroscopic behavioral (kinematic) parameters ? What does this relation tell us ? How to relate events unfolding in mediums of different complexity order, mediums characterized by radically different constraints and temporalities ?

The cerebral and physical mediums are not independent from each other :

-neuronal dysfunction  behavioral consequences -repeated exposure to an environment  behavioral changes  changes in sensorimotor transformations (e.g.

Questions at the root of Science

Dividers, physical quantities and mathematics in the brain ?

When a model is adopted, results are often interpreted within its framework.

If the data do not fit with the model predictions, some tweaks or smart adjustments can be made in the model.

But we can also ask ourselves : Is there anything in the brain activity that would correspond to amplitude, duration and velocity?

This is a crucial question because we can search for such signals in the brain activity for a very long time, an even longer time if these notions have no physiological substrate.

When evidence is found, we must also verify that the empirical data have not been distorted by statistical or analytical artefacts (e.g., coding of dynamic motor error in the SC, coding of eye velocity by premotor burst neurons, coding of saccade duration in the oculomotor vermis etc.).

QUESTIONING THE BRAIN-MODEL ISOMORPHISM :

The fact that we measure and model the movement of the eyeball (a rigid body) with kinematic notions does not imply an equivalence in the brain, and notably that the firing of neurons ought to "encode" (i.e., emit signals related to) amplitude, velocity or acceleration of the eye movement. The fact that we measure and model the movement of the eyeball (a rigid body) with kinematic notions does not imply an equivalence in the brain, and notably that the firing of neurons ought to "encode" (i.e., emit signals related to) amplitude, velocity or acceleration of the eye movement.

Is it possible to study the neurophysiology of visually-guided eye movements without embedding kinematic notions within the brain functioning ?

Dividers, physical quantities and mathematics in the brain ?

  eye movement in response to the motion of a visual target rapid : saccade slow : pursuit same muscles and motor nuclei BUT largely distinct cerebral populations two premotor input : PHASIC (burst) and TONIC eye movement in response to the motion of a visual target rapid : saccade values > 0 : rightward / upward value = 0 : straight ahead values < 0 : leftward / downward

  Research, vol. 248, pp 375-384, 2019 Journal ofNeurophysiology vol. 120, pp 3234-3245, 2018 No physical movement = equilibrium of commands Movement onset = broken equilibrium Saccade = restoration of equilibrium ; pursuit = J Neurophysiol 1998 (head free cat) Quinet & Goffart J Neurophysiol 2005 (head free monkey) Two types of input drive the activity of motoneurons : * PHASIC (bursting)  saccade * TONIC (sustained)  glissade (horizontal, oblique or vertical), the left and right cFN regulate the balance of activity between excitatory input (EBNs) and inhibitory input (IBNs) to the motor and internuclear neurons in the abducens nucleus (Goffart, Chen & Sparks J Neurophysiol 2004). Horizontal saccade as restoration of equilibrium under fastigial control  impaired pursuit Fastigio-pontine perturbation Extending the bilateral hypothesis to pursuit (pursuit as sustained imbalance) Progress in Brain Research 2019 MOVIE Bourrelly, Quinet & Goffart Journal of Neurophysiology 2018 PURSUIT Perturbation  slower pursuit No alteration of pursuit latency (pursuit onset due to asymmetry in bilateral NOT activity)Extending the bilateral hypothesis to pursuit (pursuit as sustained imbalance)

Clara Bourrelly, PhD Lorenzo Guerrasio, PhD Julie Quinet, PhD Ulrich Büttner, PhD Patrick Cavanagh, PhD Lewis Chen, PhD Ziad Hafed, PhD Richard Krauzlis, PhD David Sparks, PhD


Anne Benoit

Henri Casanova

Veronika Rehn-Sonigo

Yves Robert

Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications

Keywords: in-network stream-processing, trees of operators, multiple concurrent applications, operator mapping, polynomial heuristics. Résumé

This paper investigates the operator mapping problem for in-network stream-processing applications. In-network stream-processing amounts to applying one or more trees of operators in steady-state, to multiple data objects that are continuously updated at different locations in the network. The goal is to compute some final data at some desired rate. Different operator trees may share common subtrees. Therefore, it may be possible to reuse some intermediate results in different application trees. The first contribution of this work is to provide complexity results for different instances of the basic problem, as well as integer linear program formulations of various problem instances. The second second contribution is the design of several polynomial-time heuristics. One of the primary objectives of these heuristics is to reuse intermediate results shared by multiple applications. Our quantitative comparisons of these heuristics in simulation demonstrates the importance of choosing appropriate processors for operator mapping. It also allow us to identify a heuristic that achieves good results in practice.

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.

Mots-clés: traitement de flux en réseau, arbres d'opérateurs, multiples applications concurrentes, placement d'opérateurs, heuristiques polynomiales.

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: highnetwork monitoring with an SQL interface[END_REF][START_REF] Van Rennesse | Scalable Management and Data Mining Using Astrolabe[END_REF][START_REF] Mortier | 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)

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 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: The next four constraints ensure that Ch u,p,v,k and P ar u,p,v,k are defined properly:

• ∀i, k, p, u xop k,p,u ≥ x k,i
• ∀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 in which we consider only the compute capacity of processors enrolled for 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 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 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 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 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 difselection 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 BottomUpBFS always ranks at the third position.

Summary of Experiments

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 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.

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.

Figure 8 :

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

Figure 9 :

 9 Figure 9: Experiment 5: Similarity of applications.

  ′ , 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, ′ ).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.

,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

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].


Laurent Goffart 1,2 Critical revision of the neurophysiology of tracking eye movements 1: Institut de Neurosciences de la Timone, CNRS -Aix-Marseille Université, Marseille, France 2: Centre Gilles Gaston Granger, CNRS -Aix-Marseille Université, Aix-en-Provence, France

7.

When we consider the discharge of motor neurons innervating the extraocular muscles, the correlation between the saccade kinematics and the train of action potentials can be interpreted relatively well because the action potentials cause the contraction of extraocular muscle fibers which in turn, yields the rotation of the eyeball. When we consider now the firing of the premotor neurons which drive the motor neurons, the interpretation of the correlation is complicated by the fact that several inputs converge onto the motor neurons: from saccade-related burst neurons located in the ipsilateral paramedian reticular formation, from saccade-related burst neurons in the contralateral medullary reticular formation and from bursttonic neurons located bilaterally in the left and right nuclei prepositus hypoglossi and medial vestibular nuclei [START_REF] Scudder | The brainstem burst generator for saccadic eye movements: a modern synthesis[END_REF][START_REF] Sparks | The brainstem control of saccadic eye movements[END_REF]. The discharges of afferent groups do not exhibit identical time courses. The command is conveyed by neurons distributed across several nuclei; the correlation between their firing rate and saccade kinematics becomes weakened with more central neurons.

2.

Attributing numerical values to the directions of gaze and target or the velocities of their movement inevitably leads to mismatches between them. Numerical differences do not imply corresponding mismatches within the brain activity.

Because of the divergence of anatomical connections, any stimulus leads to the excitation of a large number of neurons. Like visual neurons, visuomotor and motor neurons have an extended response field. This extent implies that any movement is associated with the excitation of a large set of neurons. Moreover, in most visual and visuomotor regions, neurons are laid out such that neighboring neurons respond to stimuli appearing in neighboring regions of the visual field, or fire a burst of action potentials during saccades toward neighboring locations in the physical world. Despite divergent anatomical connections, the retinotopy is preserved. CONSEQUENCE : Neighboring objects, saccades toward their location, recruit populations which involve common cells. This functional overlap is overlooked when the difference between gaze and target directions (position error) or velocities (velocity error) are proposed to be commands driving the oculomotor system.

1. When a subject looks at a visual target in the physical world, her/his eyes rotate in such away that the target image is first brought within the fovea and then maintained for a time interval which is more or less long (unstable equilibrium).

For the purpose of simplicity, most neurophysiological studies used targets whose shape is bounded and does not change over time.

Thus the targets, like the eyeballs, are rigid objects and their spatial attributes can be quantified by simple numerical values expressed within a convenient and common (mathematical) reference frame.

A saccade is the very rapid eye movement made when gaze is shifted toward another target.

In response to a moving target, two types of eye movement: a saccade (interceptive, catch-up) and a slow eye movement (pursuit).

8.

The correlation between the spike discharge and kinematics might be saved by retrogradely tracking the origin and timing of action potentials that converge more or less synchronously onto the recorded neuron. However, this kind of analysis is complicated by the fact that afferent signals are transmitted through axons of different lengths and conduction speeds. The firing of a neuron is driven by action potentials emitted at different times by neurons located in different regions. CONSEQUENCE : The time interval during which we estimate the instantaneous eye velocity is the outcome of action potentials delivered during a different but also longer time interval.

The temporal blurring is complicated by the fact that the activity does not remain bounded but spreads toward neighboring cells [START_REF] Sparks | Size and distribution of movement fields in the monkey superior colliculus[END_REF][START_REF] Anderson | Two-dimensional saccade-related population activity in superior colliculus in monkey[END_REF].

CONCLUSION : correlating the firing rate of central neurons with the velocity of any movement is a questionable procedure.

4.

Attempts have been made to test whether the firing rate of neurons fits with the eye movement velocity. Yet, the velocity profile depends upon the sampling process. If the onset and rate of sampling were variable, the time course of identical saccades would show different profiles. When the time course of the neurons' firing rate differs from the time course of saccades, the notion of noise is introduced as a neural fact, as if the brain processes ought to operate like our measuring instruments, i.e., incrementally.

Mapping the change of neuronal activity with the velocity of the movement of a rigid body (eyeball or object) supposes a one-to-one correspondence between the dynamics of multiple flows of neural activity (non-rigid) and one single time series. Supposing such a homeomorphism overlooks the fact that the brain activity corresponding to any situation (measured here and now) is not reducible to a point.

5.

In addition to be spatiotemporally distributed in the brain, target-related activities do not change as fast as the measured coordinates of an object moving in the visual field.

When we study eye movements pursuing a target which suddenly disappears, we find several instances where gaze keeps moving beyond the time of target disappearance [START_REF] Mitrani | Pursuit eye movements of a disappearing moving target[END_REF]. Likewise, saccades made in response to a transient moving target direct gaze toward locations where the target never went [START_REF] Quinet | Does the brain extrapolate the position of a transient moving target?[END_REF]. These examples of persistence illustrate the mass of activity hidden behind each measured position. See also the recordings of SC neurons (Goffart et al. 2017b).

3.

The overlap could very well participate in the triggering of movements insofar as a saccade may not be launched if the visuo-oculomotor system is within a mode where opposite commands counter-balance each other. Likewise, a slow eye movement may also involve a similar symmetry breaking (though involving a different chain of neurons).

From this viewpoint, a movement is the restoration of an equilibrium of visuomotor activities while its triggering merely results from a broken symmetry (Goffart et al. 2018).

6.

  Diverse kinematical parameters (position, velocity and acceleration errors) have been considered as signals encoded in the distributed activity of neurons in the brain. Using statistical procedures fitting the relationship between a linear combination of these parameters and the neuron's firing rate over a short time interval, the activity of single neurons in various brain regions is sometimes interpreted as conveying kinematical functions, e.g.,

			Saccades toward a
			transient moving target
	FR(t-∆) = a.pos(t) + b.vel(t) + c.acc(t) + d with -100 ms < ∆ < +100 ms
	pos= eye position ; vel = eye velocity ; accel = eye acceleration
	Sun et al. Scientific Reports 2017 :
	"In our present study, we found that both saccade-and SPEM-
	related responses of individual PCs could be predicted well by linear
	combinations of eye acceleration, velocity and position. The relative
	weights of the contributions that these kinematic parameters made
	depended on the type of eye movement"
	a
	BTN	EBN	IBN
		MN
		muscle
		fibers
	EYE MOVEMENT
		MEASURED
		VALUES


Laurent Goffart

Julie Quinet

Clara Bourrelly

Cerebellar control of saccades by the size of the active population in the caudal fastigial nucleus

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Methods

The caudal fastigial nucleus (CFN) is critical for generating accurate saccades toward a visual target. Its pharmacological inactivation alters the amplitude of their horizontal component: it is hypermetric for ipsilesional saccades and hypometric for contralesional ones. A recent study reported that "ipsilesional saccades showed more endpoint variability than did normal saccades" and that the "inactivation effects on saccade noise are explained by a decrease of the feedback gain and an increase of planning and/or signal dependent motor noise" (Eggert et al., 2016). In the framework of a control of saccade amplitude by negative feedback, the hypermetria of the horizontal component of ipsilesional saccades can indeed be explained by an underestimation of the current eye displacement. However, instead of adding a notion which is rather neurophysiologically undetermined ("noise"), we propose that the endpoint variability actually reflects the size of the active population in the CFN. This conjecture derives from the results of Quinet & Goffart (2015) who showed that the size of saccades evoked by electrical microstimulation in the fastigial nucleus increases with larger current.

According to this hypothesis, if an injection of muscimol is made not exactly centered in the fastigial oculomotor region, the number of saccade-related neurons which are inactivated by the pharmacological agent should increase as it diffuses, resulting in a time-varying dysmetria. Moreover, this effect of diffusion should not be restricted to the generation of ipsilesional saccades, but should concern also the generation of contralesional ones.

We show examples of inactivation experiments performed in the head-restrained monkey where the magnitude of dysmetria does not change with time and others where it increased. Depending upon the experiment, this time-varying effect affects either ipsilesional or contralesional saccades. Thus, the so-called "noise" inferred from the variability of endpoints after CFN inactivation seems to result from an increase of the number of neurons which are silenced by the pharmacological agent (muscimol).

Stationary dysmetria

Stationary dysmetria NON stationary hypometria NON stationary hypermetria

Four rhesus monkeys were used in this study. The movements of one eye were recorded with the scleral search coil in magnetic field technique. The saccades were initiated from a fixation target located straight ahead that the monkeys had to fixate for a variable interval (750 -1500 by 250ms). Two hundred milliseconds after the disappearance of the central target (gap paradigm), a transient target (duration=100ms) appeared in the peripheral visual field (horizontal and vertical eccentricity of 0, 8 or 16°). The monkeys' task was to look at the location where the target was flashed. The target location varied pseudo-randomly between the trials. A series of (3-4) experiments were performed before each inactivation experiment in order to estimate the control performance. A total of 25 injections of muscimol were made locally in the cFN. The injections were made after the saccaderelated regions were identified and localized using standard electrophysiological techniques (unit recording and microstimulation).

  Cerebellar control of saccades by the size of the active population in the caudal fastigial nucleus Introduction Laurent Goffart, Julie Quinet* & Clara Bourrelly Institut de Neurosciences de la Timone, CNRS & Aix-Marseille Université, Marseille, France * : new address : Dept of Ophthalmology, University of Alabama, Birmingham, AL, USA

Fondation

  National de la Recherche Scientifique European Research Council (grant « Position » coordinator : Patrick Cavanagh) Fondation de France Fondation Berthe Fouassier (to JQ) Both cFN contribute to accelerate and decelerate the horizontal component of any saccade. The possibility to independently alter the horizontal component of ipsilesional or contralesional saccades suggests independent output channels from the CFN to the saccade-related premotor neurons. The number of active neurons in both cFN matters in the regulation of the dynamics of the horizontal component of saccades (Goffart et al. 2003). It participates to its dynamics by recruiting the appropriate number of premotor burst neurons, excitatory and inhibitory. The late burst emitted by some neurons in the ipsilateral cFN (Ohtsuka & Noda 1991; Fuchs et al. 1993) is neither "a brake" but the signature of a later recruitment. Becker W, Jürgens R. Human oblique saccades: quantitative analysis of the relation between horizontal and vertical components. Vision Res 30: 893-920, 1990. Eggert T, Robinson FR, Straube A. Modeling inter-trial variability of saccade trajectories: Effects of lesions of the oculomotor part of the fastigial nucleus. PLOS Comp Biol 12, 2016. Fuchs AF, Robinson FR, Straube A. Role of the caudal fastigial nucleus in saccade generation. I. Neuronal discharge patterns. J Neurophysiol 70: 1712-1740, 1993. Goffart L, Chen LL, Sparks DL. Saccade dysmetria during functional perturbation of the caudal fastigial nucleus in the monkey. Ann NY Acad Sci 1004: 220-228, 2003. Ohtsuka K, Noda H. Saccadic burst neurons in the oculomotor region of the fastigial nucleus of macaque monkeys. J Neurophysiol 65: 1422-1434, 1991. Quinet J, Goffart L. Cerebellar control of saccade dynamics: contribution of the fastigial oculomotor region. J Neurophysiol 113: 3323-3336, 2015.

  As the drug diffuses, the number of inactivated neurons increases = # of active neurons diminishes Reduced number of active cFN neurons  enhanced duration unchanged enhanced Enhanced peak velocity is due to less inhibition from contralateral IBN Enhanced duration is due to : -residual input from descending commands ( ) -prolonged inhibition of OPN by ipsilateral IBN (driven by ) and opposite cFN ( ) Prolonged inhibition of OPN increases the duration of vertical component As the drug diffuses, the number of inactivated neurons increases = # of active neurons diminishes Reduced number of active neurons  reduced peak velocity insufficient duration  enhanced hypermetria peak velocity cFN inactivation primarily reduces the horizontal amplitude of contralesional oblique saccades. This hypometria is associated with a reduction of horizontal peak velocity. Changes in the duration of both components can be observed and they are correlated when they happen. hor. ampl. (°) Change in hor. dur. (ms) Change in hor. ampl. (°) IPSILESIONAL OBLIQUE SACCADES : cFN inactivation primarily increases the horizontal amplitude of ipsilesional oblique saccades. The hypermetria is associated with an augmentation of horizontal peak velocity. Changes in the duration of both components are observed and correlated.