Anne Benoit

Yves Robert

Mapping pipeline skeletons onto heterogeneous platforms

Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous -nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer's task, but it also provides additional information which can help realize an efficient mapping of the application.

In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms: Fully Homogeneous platforms with identical processors and interconnection links; Communication Homogeneous platforms, with identical links but different speed processors; and finally, Fully Heterogeneous platforms. We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for different mapping policies: a mapping can be required to be one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages), or fully general. In particular, we show that determining the optimal interval-based mapping is NP-hard for Communication Homogeneous platfors, and this result assesses the complexity of the well-known chains-to-chains problem for different-speed processors. We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on Communication Homogeneous platforms. These heuristics are compared to the optimal result provided by the formulation of the problem in terms of the solution of an integer linear program, for small problem instances. 1

Introduction

Mapping applications onto parallel platforms is a difficult challenge. Several scheduling and loadbalancing techniques have been developed for homogeneous architectures (see [START_REF] Shirazi | Scheduling and load balancing in parallel and distributed systems[END_REF] for a survey) but the advent of heterogeneous clusters has rendered the mapping problem even more difficult. Typically, such clusters are composed of different-speed processors interconnected either by plain Ethernet (the low-end version) or by a high-speed switch (the high-end counterpart), and they constitute the experimental platform of choice in most academic or industry research departments.

In this context of heterogeneous platforms, a structured programming approach rules out many of the problems which the low-level parallel application developer is usually confronted to, such as deadlocks or process starvation. Moreover, many real applications draw from a range of wellknown solution paradigms, such as pipelined or farmed computations. High-level approaches based on algorithmic skeletons [START_REF] Cole | Bringing Skeletons out of the Closet: A Pragmatic Manifesto for Skeletal Parallel Programming[END_REF][START_REF] Rabhi | Patterns and Skeletons for Parallel and Distributed Computing[END_REF] identify such patterns and seeks to make it easy for an application developer to tailor such a paradigm to a specific problem. A library of skeletons is provided to the programmer, who can rely on these already coded patterns to express the communication scheme within its own application. Moreover, the use of a particular skeleton carries with it considerable information about implied scheduling dependencies, which we believe can help to address the complex problem of mapping a distributed application onto a heterogeneous platform.

In this paper, we therefore consider applications that can be expressed as algorithmic skeletons, and we focus on the pipeline skeleton, which is one of the most widely used. In such applications, a series of tasks enter the input stage and progress from stage to stage until the final result is computed. Each stage has its own communication and computation requirements: it reads an input file from the previous stage, processes the data and outputs a result to the next stage. For each task, initial data is input to the first stage, and final results are output from the last stage. The pipeline operates in synchronous mode: after some latency due to the initialization delay, a new task is completed every period. The period is defined as the longest cycle-time to operate a stage, and is the inverse of the throughput that can be achieved.

The problem of mapping pipeline skeletons onto parallel platforms has received some attention, and we survey related work in Section 7. In particular, Subhlok and Vondran [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF][START_REF] Subhlok | Optimal latency-throughput tradeoffs for data parallel pipelines[END_REF] have dealt with this problem on homogeneous platforms. In this paper, we extend their work and target heterogeneous clusters. Our main goal is to assess the additional complexity induced by the heterogeneity of processors, and/or of communication links. As in [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF], we aim at deriving optimal mappings, i.e. mappings which minimize the period, or equivalently maximize the throughput, of the system. Each pipeline stage can be seen as a sequential procedure which may perform disc accesses or write data in the memory for each task. This data may be reused from one task to another, and thus the rule of the game is always to process the tasks in a sequential order within a stage. Moreover, due to the possible local memory accesses, a given stage must be mapped onto a single processor: we cannot process half of the tasks on a processor and the remaining tasks on another without exchanging intra-stage information, which might be costly and difficult to implement.

In this paper, we focus on pipeline skeletons and thus we enforce the rule that a given stage is mapped onto a single processor. In other words, a processor that is assigned a stage will execute the operations required by this stage (input, computation and output) for all the tasks fed into the pipeline. The optimization problem can be stated informally as follows: which stage to assign to which processor? We consider several variants, in which we require the mapping to be one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages), or fully general.

In addition to these three mapping categories, we target three different platform types. First, Fully Homogeneous platforms have identical processors and interconnection links. Next, Communication Homogeneous platforms, with identical links but different speed processors, introduce a first degree of heterogeneity. Finally, Fully Heterogeneous platforms constitute the most difficult instance, with different speed processors and different capacity links. The main objective of the paper is to assess the complexity of each mapping variant onto each platform type. We establish several new complexity results for this important optimization problem, and we derive efficient polynomial heuristics for interval-based mappings onto Communication Homogeneous platforms. These heuristics are compared through simulation; moreover, their absolute performance is assessed owing to the formulation of the problem in terms of an integer linear program, whose solution returns the optimal result for small problem instances.

An interesting consequence of one of the new complexity results proved in this paper (see Section 3.2.2) is the following. Given an array of n elements a 1 , a 2 , . . . , a n , the well-known chainsto-chains problem is to partition the array into p intervals whose element sums are well balanced (technically, the aim is to minimize the largest sum of the elements of any interval). This problem has been extensively studied in the literature (see the pioneering papers [START_REF] Bokhari | Partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF] Hansen | Improved algorithms for partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF] Olstad | Efficient partitioning of sequences[END_REF] and the survey [START_REF] Pinar | Fast optimal load balancing algorithms for 1D partitioning[END_REF]). It amounts to load-balance n computations whose ordering must be preserved (hence the restriction to intervals) onto p identical processors. The advent of heterogeneous clusters naturally leads to the following generalization: can we partition the n elements into p intervals whose element sums match p prescribed values (the processor speeds) as closely as possible. The NP-hardness of this important extension of the chains-to-chains problem is established in Section 3.2.2.

The rest of the paper is organized as follows. Section 2 is devoted to a detailed presentation of the target optimization problems. Next in Section 3 we proceed to the complexity results. In Section 4 we introduce several polynomial heuristics to solve the mapping problem. These heuristics are compared through simulations, whose results are analyzed in Section 5. Section 6 introduces the linear formulation of the problem and assesses the absolute performance of the heuristics when the optimal solution can be found. Section 7 is devoted to an overview of related work. Finally, we state some concluding remarks in Section 8.

Framework

We outline in this section the characteristics of the applicative framework, as well as the model for the target platform. Next we detail the objective function, chosen as the maximum period of a processor to execute all the pipeline stages assigned to it. ... ... b in,u

S 2 S k S n S 1 w 1 w 2 w k w n δ 0 δ 1 δ k-1 δ k δ n
P v P out P in s v P u s u b v,out b u,v s in s out

Applicative framework

We consider a pipeline of n stages S k , 1 ≤ k ≤ n, as illustrated on Figure 1. Tasks are fed into the pipeline and processed from stage to stage, until they exit the pipeline after the last stage. The k-th stage S k receives an input from the previous stage, of size δ k-1 , performs a number of w k computations, and outputs data of size δ k to the next stage. The first stage S 1 receives an input of size δ 0 from the outside world, while the last stage S n returns the result, of size δ n , to the outside world.

Target platform

We target a heterogeneous platform (see Figure 2), with p processors P u , 1 ≤ u ≤ p, fully interconnected as a (virtual) clique. There is a bidirectional link link u,v : P u → P v between any processor pair P u and P v , of bandwidth b u,v . Note that we do not need to have a physical link between any processor pair. Instead, we may have a switch, or even a path composed of several physical links, to interconnect P u and P v ; in the latter case we would retain the bandwidth of the slowest link in the path for the value of b u,v .

Communications contention is taken care of by enforcing the one-port model [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF][START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF]. In this model, a given processor can be involved in a single communication at any time-step, either a send or a receive. However, independent communications between distinct processor pairs can take place simultaneously. The one-port model seems to fit the performance of some current MPI implementations, which serialize asynchronous MPI sends as soon as message sizes exceed a few megabytes [START_REF] Saif | Understanding the behavior and performance of non-blocking communications in MPI[END_REF].

In the most general case, we have fully heterogeneous platforms, with different processors speeds and link capacities. The speed of processor P u is denoted as s u , and it takes X/s u time-units for P u to execute X floating point operations. We also enforce a linear cost model for communications, hence it takes X/b u,v time-units to send (resp. receive) a message of size X to (resp. from) P v . We classify below particular cases which are important, both from a theoretical and practical perspective:

Fully Homogeneous-These platforms have identical processors (s u = s) and links (b u,v = b).

They represent typical parallel machines.

Communication Homogeneous-These platforms have different-speed processors (s u = s v ) interconnected by links of same capacities (b u,v = b). They correspond to networks of workstations with plain TCP/IP interconnects or other LANs.

Fully Heterogeneous-These are the most general, fully heterogeneous architectures, with s u = s v and b u,v = b u ,v . Hierarchical platforms made up with several clusters interconnected by slower backbone links can be modeled this way.

Finally, we assume that two special additional processors P in and P out are devoted to input/output data. Initially, the input data for each task resides on P in , while all results must be returned to and stored in P out . Of course we may have a single processor acting as the interface for the computations, i.e. P in = P out .

Mapping problem

The general mapping problem consists in assigning application stages to platform processors. However, some constraints can be added to the mapping to ease the implementation of the application, for instance by imposing to map a single stage onto each processor. Different instances of the mapping problem are discussed below.

One-to-one Mapping

Assume temporarily, for the sake of simplicity, that each stage S k of the application pipeline is mapped onto a distinct processor P alloc(k) (which is possible only if n ≤ p). For convenience, we create two fictitious stages S 0 and S n+1 , and we assign S 0 to P in and S n+1 to P out .

What is the period of P alloc(k) , i.e. the minimum delay between the processing of two consecutive tasks? To answer this question, we need to know which processors the previous and next stages are assigned to. Let t = alloc(k -1), u = alloc(k) and v = alloc(k + 1). P u needs δ k-1 /b t,u to receive the input data from P t , w k /s u to process it, and δ k /b u,v to send the result to P v , hence a cycle-time of δ k-1 /b t,u + w k /s u + δ k /b u,v for P u . The period achieved with the mapping is the maximum of the cycle-times of the processors, this corresponds to the rate at which the pipeline can be activated.

In this simple instance, the optimization problem can be stated as follows: determine a one-toone allocation function alloc : [1, n] → [1, p] (augmented with alloc(0) = in and alloc(n + 1) = out) such that

T period = max 1≤k≤n δ k-1 b alloc(k-1),alloc(k) + w k s alloc(k) + δ k b alloc(k),alloc(k+1) (1)
is minimized. We denote by One-to-one Mapping the previous optimization problem.

Interval Mapping

However, one-to-one mappings may be unduly restrictive. A natural extension is to search for interval mappings, i.e. allocation functions where each participating processor is assigned an interval of consecutive stages. Intuitively, assigning several consecutive tasks to the same processors will increase their computational load, but may well dramatically decrease communication requirements.

In fact, the best interval mapping may turn out to be a one-to-one mapping, or instead may enroll only a very small number of fast computing processors interconnected by high-speed links.

Interval mappings constitute a natural and useful generalization of one-to-one mappings (not to speak of situations where p < n, where interval mappings are mandatory). A major objective of this paper is to assess the performance of general interval mappings as opposed to pure one-to-one allocations.

For the sake of completeness, we formally write the optimization problem associated to interval mappings. We need to express that the intervals achieve a partition of the original set of stages S 1 to S n . We search for a partition of [1..n] into m intervals I j = [d j , e j ] such that d j ≤ e j for 1 ≤ j ≤ m, d 1 = 1, d j+1 = e j + 1 for 1 ≤ j ≤ m -1 and e m = n. Interval I j is mapped onto processor P alloc(j) , and the period is expressed as

T period = max 1≤j≤m δ d j -1 b alloc(j-1),alloc(j) + e j i=d j w i s alloc(j) + δ e j b alloc(j),alloc(j+1) (2)
Here, we assume that alloc(0) = in and alloc(m + 1) = out. The optimization problem Interval Mapping is to determine the best mapping, over all possible partitions into intervals, and over all processor assignments.

General Mapping

The most general mappings may be more complicated than interval-based mappings: a processor P u can be assigned any subset of stages. Let us consider the following example with n = 3 stages and p = 2 processors. We also use a third processor P 0 = P in = P out for input/output, with no processing capacity (s 0 = 0).

If the platform is Fully Homogeneous, let us consider a case in which the second stage requires two times more computation than the other stages: w 1 = w 3 = 1 and w 2 = 2, and where the communications are negligible (δ i = 0). The platform parameters (s, b) are set to 1. An intervalbased mapping needs to map either the two first stages or the two last ones on a same processor, which will have a cycle time of 1 + 2 = 3 (computations of the two stages). An intuitive solution would however be to map the first and third stages on one processor, and the second stage alone, relaxing the interval constraint, hoping to reach a cycle time of 2 for both processors (with a good load-balancing), which will work in parallel. Figure 3 illustrates such a mapping, and the desired behavior of the application. During a cycle, P 1 processes a task for S 3 and then a task for S 1 (communications from/to P 0 can be neglected), while P 2 processes a task for S 2 . Communications occur between each cycle, when P 1 sends output from S 1 and P 2 sends output from S 2 .

P 2 S 3 S 1 S 2 S 3 S 1 S 2 P 1
However, we always assumed in this paper that a stage is implemented in a static and synchronous way, using the one-port model, which is a realistic hypothesis on the implementation of the application. With such a model, if P 1 starts to send the output from S 1 , it will be blocked until P 2 completes the receive, while P 2 is sending its own output before receiving the next task for S 2 . This leads to a deadlock with a straightforward implementation.

The solution would be to create a process for each stage, and map the independent processes on processors, possibly several processes on a single processor. In order to obtain asynchronous communications, each process should run three threads, one for input, one for computation and one for output. Each thread knows where to expect its input from, and where to redirect its output to, so it can post asynchronous messages and poll for completion. When an input is completed, it hands over the data to the computation thread, and so on. Overall, the computation advances asynchronously, in a greedy fashion: each action is executed as soon as it is ready. Computations and communications are preemptive. On each processor and at any time step, several processes share the CPU for computations related to different stages, and several communications take place simultaneously and share the bandwidth (of the link and/or the network card). This scheme requires as many communication buffers as there are stages/processes assigned to the processor.

With such an implementation, we would like to define the cycle-time of a processor by the time needed to execute one instance of each of its stages, and the period as the maximum of the processor cycle-times. If P u handles the set of stages stages(u), and stage i is mapped on processor alloc(i), the period is defined by:

T period = max 1≤u≤p    i∈stages(u) ∆ u alloc(i-1) δ i-1 b alloc(i-1),u + w i s u + ∆ alloc(i+1) u δ i b u,alloc(i+1)    (3)
where ∆ v u = 1 if u = v and 0 otherwise. In equation (3), we pay the input communication for a stage S i only if stage S i-1 is not mapped on the same processor (and similarly for the output communication).

However, it is very difficult to assess whether the above period will actually be achieved in a real-life implementation. Delays may occur due to the dependency paths (P u sending data to P v that returns it to P u , and the like), leading to idle times (waiting on polling). Races may occur and slow down, say, two simultaneous communications involving non-disjoint processor pairs. Finally, control overhead and cost of switching processes may prove very high. At least an optimistic view is that the achieved period will be only slightly larger than the above theoretical bound, but this would require to be validated experimentally.

If we restrict ourselves to the one-port model, and consider the 3-stages example again with the first and third stages mapped on the first processor, the straightforward implementation leads to a period of 4 because P 1 always wait for a task to go through S 2 on P 2 before it goes through P 3 . This leads to the execution scheme of Figure 4.

... In this execution scheme, we enforced a natural rule that is implied by a non-preemptive implementation. Let S i (k) denote the processing in stage S i for the incoming task number k. Then, if S i and S j are two stages assigned to P u with i < j, then P u executes S j (k) before S i (k + 1). With this rule, the cycle-time of a processor is the duration of the path that goes from the input of its first stage all the way to the output of its last stage. Let us define first(u) and last(u) as the first and last index, respectively, which are assigned to P u .

S 3 S 1 P 1 P 2 S 1 S 2

cycle-time(P

u ) = δ first(u)-1 b alloc(first(u)-1),u + last(u) i=first(u) w i s alloc(i) + ∆ alloc(i+1) alloc(i) δ i b alloc(i),alloc(i+1) (4)
T period = max 1≤u≤p cycle-time(P u ) (5)
In equation ( 4), we always pay the first communication and the last one, by definition of first(u) and last(u), but we need to take care that some consecutive stages might be mapped onto the same processor.

Obviously, this period is longer than the one obtained with equation ( 3), but with these assumptions, we know how to implement the application in a natural way, and we can ensure that this (longer) period will be achieved. All actions can be organized (scheduled statically) and the period can be characterized analytically. This allows us to avoid the complex dynamic scheme.

In this case, it does not seem very interesting to map non consecutive stages on a same processor, because it has to wait for the processing of the intermediate stages, which leads to idle time. Actually, we will see in Section 3 that interval-based mappings are always as good as general mappings on Communication Homogeneous platforms. We still consider the general optimization problem, since general mappings may outperform interval-based ones in some particular cases, even with the definition of the period of equation ( 5).

Consider the following example with n = 3 stages and p = 2 processors. The target architecture is characterized by s 1 = b 0,2 = b 1,2 = 1 and s 2 = b 0,1 = 10. As for the application, we have

δ 0 = δ 3 = w 2 = 10 and δ 1 = δ 2 = w 1 = w 3 = 1. If we map S 2 on P 1 , then T period ≥ w 2 s 1 = 10. If we map S 1 on P 2 , then T period ≥ δ 0 b 0,2 = 10.
Similarly, if we map S 3 on P 2 , then T period ≥ δ 3 b 0,2 = 10. There exists a single mapping whose period is smaller than 10: indeed, we can map S 1 and S 3 on P 1 and S 2 on P 2 , and the period becomes

T period = δ 0 b 0,1 + w 1 s 1 + δ 1 b 1,2 + w 2 s 2 + δ 2 b 1,2 + w 3 s 1 + δ 3 b 0,1 = 7 (6)
In equation ( 6), we have computed the length of the cycle that P 1 repeats for every incoming task:

• read data for task number k from P in • compute S 1 (k), i.e. stage 1 for that task • send data to P 2 , wait for P 2 to process it (stage S 2 (k)) and to return the results • compute stage S 3 (k), send output data to P out • proceed to task number k + 1 and repeat entire cycle, starting with input data for S 1 (k + 1) Because the operation of P 2 is entirely included into that of P 1 , P 1 has the longest cycle-time, thereby defining the period. This is how we derived that T period = 7 in the example, in full accordance to equations ( 4) and (5).

This little example shows that general mappings may be superior to interval-based mappings, and provides a motivation to study the corresponding optimization problem, denoted as General Mapping.

In this paper, we mostly concentrate on interval-based mappings, because they realize the best trade-off between efficiency and simplicity. One-to-one mappings are not general enough, in particular when resources are in limited number, or when communications have a higher cost. General mappings require important changes in the model and its implementation, and may be too complex to deal with efficiently for the application programmer. We still address the complexity of all mapping problems, including general mappings, but for practical developments we limit ourselves to one-to-one and interval-based mappings. Also, we privilege Communication Homogeneous platforms, which are the most representative of current experimental architectures.

Complexity results

To the best of our knowledge, this work is the first to study the complexity of the various mapping strategies (One-to-one Mapping, Interval Mapping and General Mapping), for each of the different platform categories (Fully Homogeneous, Communication Homogeneous and Fully Heterogeneous). Table 1 summarizes all our new results.

For Fully Homogeneous or Communication Homogeneous platforms, determining the optimal One-to-one Mapping can be achieved through a binary search over possible periods, invoking a greedy algorithm at each step. The problem surprisingly turns out to be NP-hard for Fully Heterogeneous platforms. The binary search algorithm for One-to-one Mapping is outlined in Section 3.1.

The Interval Mapping problem is more complex to deal with. For Fully Homogeneous platforms (see Section 3.2.1), we simply recall the optimal dynamic programming algorithm of Subhlok and Vondran [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF][START_REF] Subhlok | Optimal latency-throughput tradeoffs for data parallel pipelines[END_REF]. For Communication Homogeneous platforms (see Section 3.2.2), the problem turns out to be NP-hard. Quite interestingly, this result is a consequence of the fact that the natural extension of the chains-to-chains problem [START_REF] Pinar | Fast optimal load balancing algorithms for 1D partitioning[END_REF] to different-speed processors is NP-hard. Furthermore, in Section 3.2.3, we also prove the nice theoretical result that interval-based mappings are dominant for Communication Homogeneous platforms: no need to consider general mappings for such platforms, we can restrict the search to interval-based mappings.

Finally, all three optimization problems are NP-hard for Fully Heterogeneous platforms. The proof of these results is provided in Section 3.3.

One-to-one Mapping

Theorem 1. For Fully Homogeneous and Communication Homogeneous platforms, the optimal One-to-one Mapping can be determined in polynomial time.

Proof. We provide a constructive proof: we outline a binary-search algorithm that iterates until the optimal period is found. At each step, a greedy algorithm is used to assign stages to processors in a one-to-one fashion. The greedy algorithm succeeds if and only if the period is feasible. If the algorithm does succeed, we decrease the target period, otherwise we increase it, and then proceed to the next step. For theory-oriented readers, we easily check that the number of steps is indeed polynomial in the problem size: in a word, we use a binary search over an interval whose length can be bounded by the maximum values of the application/platform parameters, hence a number of steps proportional to the logarithm of this value, which in turn is the encoding size of the problem. For more practice-oriented readers, only a few seconds are needed to obtain the period with a precision of 10 -4 for a reasonable problem size. See for instance the practical experiments reported in Section 5.

Let us now describe the most interesting part of the procedure, namely the greedy assignment algorithm for a prescribed value T period of the achievable period. Recall that there are n stages to map onto p ≥ n processors in a one-to-one fashion. Also, we target Communication Homogeneous platforms with different-speed processors (s u = s v ) but with links of same capacities (b u,v = b).

First we retain only the fastest n processors, which we rename P 1 , P 2 , . . . , P n such that s 1 ≤ s 2 ≤ . . . ≤ s n . Then we consider the processors in the order P 1 to P n , i.e. from the slowest to the fastest, and greedily assign them any free (non already assigned) task that they can process within the period. Algorithm The proof that the greedy algorithm returns a solution if and only if there exists a solution of period T period is done by a simple exchange argument. Indeed, consider a valid one-to-one assignment of period T period , denoted A, and assume that it has assigned stage S k 1 to P 1 . Note first that the greedy algorithm will indeed find a stage to assign to P 1 and cannot fail, since S k 1 can be chosen. If the choice of the greedy algorithm is actually S k 1 , we proceed by induction with P 2 . If the greedy algorithm has selected another stage S k 2 for P 1 , we find which processor, say P u , has been assigned this stage in the valid assignment A. Then we exchange the assignments of P 1 and P u in A. Because P u is faster than P 1 , which could process S k 1 in time in the assignment A, P u can process S k 1 in time too. Because S k 2 has been mapped on P 1 by the greedy algorithm, P 1 can process S k 1 in time. So the exchange is valid, we can consider the new assignment A which is valid and which did the same assignment on P 1 than the greedy algorithm. The proof proceeds by induction with P 2 as before. We point out that the complexity of the greedy algorithm is bounded by O(n 2 ), because of the two loops over processors and stages.

Interval Mapping

Fully Homogeneous platforms

Proposition 1. For Fully Homogeneous platforms, the optimal Interval Mapping can be determined in polynomial time.

Proof. This result is due to Subhlock and Vondran [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF][START_REF] Subhlok | Optimal latency-throughput tradeoffs for data parallel pipelines[END_REF]. We briefly outline a variant of their dynamic programming algorithm that returns the optimal period. Consider an application with n stages S 1 to S n to be mapped onto a fully-homogeneous platform composed of p (identical) processors. Let s and b respectively denote the processor speed and the link bandwidth.

We compute recursively the value of c(i, j, k), which is the optimal period that can be achieved by any interval-based mapping of stages S i to S j using exactly k processors. The goal is to determine

min 1≤k≤p c(1, n, k)
The recurrence relation can be expressed as

c(i, j, k) = min q + r = k 1 ≤ q ≤ k -1 1 ≤ r ≤ k -1 min i≤ ≤j-1 {max (c(i, , q), c( + 1, j, r))} with the initialization c(i, j, 1) = δ i-1 b + j k=i w k s + δ j b c(i, j, k) = +∞ if k > j -i + 1
The recurrence is easy to justify: to compute c(i, j, k), we search over all possible partitionings into two subintervals, using every possible number of processors for each interval. The complexity of this dynamic programming algorithm is bounded by O(n 3 p 2 ).

It is not possible to extend the previous dynamic programming algorithm to deal with Communication Homogeneous platforms. This is because the algorithm intrinsically relies on identical processors in the recurrence computation. Different-speed processors would execute sub-intervals with different cycle-times. Because of this additional difficulty, the Interval Mapping problem for Communication Homogeneous platforms seems to be very combinatorial: we prove that it is NP-hard below (Section 3.2.2. Furthermore we prove that interval-based mappings are dominant for such platforms (Section 3.2.3), which means that there exist interval-based mappings which are optimal among all possible general mappings (hence the entry titled same complexity in Table 1).

NP-completeness of the Interval Mapping problem for Communication Homogeneous platforms

Theorem 2. For Communication Homogeneous platforms, the (decision problem associated to the) Interval Mapping optimization problem is NP-complete.

Theorem 2 is a consequence of Theorem 3 which assesses the complexity of the heterogeneous 1D partitioning problem. We introduce this problem and prove Theorem 3 before returning to the proof of Theorem 2.

Given an array of n elements a 1 , a 2 , . . . , a n , the 1D partitioning problem, also known as the chains-to-chains problem, is to partition the array into p intervals whose element sums are almost identical. More precisely, we search for a partition of [1..n] into p consecutive intervals I 1 , I 2 , . . . , I p , where

I k = [d k , e k ] and d k ≤ e k for 1 ≤ k ≤ p, d 1 = 1, d k+1 = e k + 1 for 1 ≤ k ≤ p -1 and e p = n. The objective is to minimize max 1≤k≤p i∈I k a i = max 1≤k≤p e k i=d k a i .
This problem has been extensively studied in the literature because it has various applications. In particular, it amounts to load-balance n computations whose ordering must be preserved (hence the restriction to intervals) onto p identical processors. Then each a i corresponds to the execution time of the i-th task, and the sum of the elements in interval I k is the load of the processor which I k is assigned to. Several algorithms and heuristics have been proposed to solve this load-balancing problem, including [START_REF] Bokhari | Partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF]Approximate algorithms for partitioning problems[END_REF][START_REF] Hansen | Improved algorithms for partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF] Iqbal | Efficient algorithms for a class of partitioning problems[END_REF][START_REF] Olstad | Efficient partitioning of sequences[END_REF]. We refer the reader to the survey paper by Pinar and Aykanat [START_REF] Pinar | Fast optimal load balancing algorithms for 1D partitioning[END_REF] for a detailed overview and comparison of the literature.

The advent of heterogeneous clusters leads to the following generalization of the 1D partitioning problem: the goal is to partition the n elements into p intervals whose element sums match p prescribed values (the processor speeds) as closely as possible. Let s 1 , s 2 , . . . , s p denote these values. We search for a partition of [1..n] into p intervals I k = [d k , e k ] and for a permutation σ of {1, 2, . . . , p}, with the objective to minimize:

max 1≤k≤p i∈I k a i s σ(k)
.

Another way to express the problem is that intervals are now weighted by the s i values, while we had s i = 1 for the homogeneous version. Can we extend the efficient algorithms described in [START_REF] Pinar | Fast optimal load balancing algorithms for 1D partitioning[END_REF] to solve the heterogeneous 1D partitioning problem, Hetero-1D-Partition for short? In fact, the problem seems combinatorial, because of the search over all possible permutations to weight the intervals. Indeed, we prove the NP-completeness of (the decision problem associated to) Hetero-1D-Partition. Proof. The Hetero-1D-Partition-Dec problem clearly belongs to the class NP: given a solution, it is easy to verify in polynomial time that the partition into p intervals is valid and that the maximum sum of the elements in a given interval does divided by the corresponding s value does not exceed the bound K. To establish the completeness, we use a reduction from NUMERICAL MATCHING WITH TARGET SUMS (NMWTS), which is NP-complete in the strong sense [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. We consider an instance I 1 of NMWTS: given 3m numbers x 1 , x 2 , . . . , x m , y 1 , y 2 , . . . , y m and z 1 , z 2 , . . . , z m , does there exist two permutations σ 1 and σ 2 of {1, 2, . . . , m}, such that

x i + y σ 1 (i) = z σ 2 (i) for 1 ≤ i ≤ m?
Because NMWTS is NP-complete in the strong sense, we can encode the 3m numbers in unary and assume that the size of I 1 is O(m + M ), where M = max i {x i , y i , z i }. We also assume that m i=1 x i + m i=1 y i = m i=1 z i , otherwise I 1 cannot have a solution.

We build the following instance I 2 of Hetero-1D-Partition-Dec (we use the formulation in terms of task weights and processor speeds which is more intuitive):

• We define n = (M + 3)m tasks, whose weights are outlined below:

A 1 111...1 C D | A 2 111...1 C D | . . . | A m 111...1 C D M M M
Here, B = 2M , C = 5M , D = 7M , and

A i = B + x i for 1 ≤ i ≤ m.
To define the a i formally for 1 ≤ i ≤ n, let N = M + 3. We have for 1 ≤ i ≤ m:

       a (i-1)N +1 = A i = B + x i a (i-1)N +j = 1 for 2 ≤ j ≤ M + 1 a iN -1 = C a iN = D
• For the number of processors (and intervals), we choose p = 3m. As for the speeds, we let s i be the speed of processor P i where, for 1 ≤ i ≤ m:

   s i = B + z i s m+i = C + M -y i s 2m+i = D
Finally, we ask whether there exists a solution matching the bound K = 1. Clearly, the size of I 2 is polynomial in the size of I 1 . We now show that instance I 1 has a solution if and only if instance I 2 does.

Suppose first that I 1 has a solution, with permutations σ 1 and σ 2 such that x i + y σ 1 (i) = z σ 2 (i) . For 1 ≤ i ≤ m:

• We map each task A i and the following y σ 1 (i) tasks of weight 1 onto processor P σ 2 (i) .

• We map the following M -y σ 1 (i) tasks of weight 1 and the next task, of weight C, onto processor P m+σ 1 (i) .

• We map the next task, of weight D, onto the processor P 2m+i .

We do have a valid partition of all the tasks into p = 3m intervals. For 1 ≤ i ≤ m, the load and speed of the processors are indeed equal:

• The load of P σ 2 (i) is A i + y σ 1 (i) = B + x i + y σ 1 (i) and its speed is B + z σ 2 (i) .
• The load of P m+σ 1 (i) is M -y σ 1 (i) + C, which is equal to its speed.

• The load and speed of P 2m+i are both D.

The mapping does achieve the bound K = 1, hence a solution to I 1 .

Suppose now that I 2 has a solution, i.e. a mapping matching the bound K = 1. We first observe that s i < s m+j < s 2m+k = D for 1 ≤ i, j, k ≤ m. Indeed s i = B + z i ≤ B + M = 3M , 5M ≤ s m+j = C + M -y j ≤ 6M and D = 7M . Hence each of the m tasks of weight D must be assigned to a processor of speed D, and it is the only task assigned to this processor. These m singleton assignments divide the set of tasks into m intervals, namely the set of tasks before the first task of weight D, and the m -1 sets of tasks lying between two consecutive tasks of weight D. The total weight of each of these m intervals is A i + M + C > B + M + C = 10M , while the largest speed of the 2m remaining processors is 6M . Therefore each of them must be assigned to at least 2 processors each. However, there remains only 2m available processors, hence each interval is assigned exactly 2 processors.

Consider such an interval A i 111...1 C with M tasks of weight 1, and let P i 1 and P i 2 be the two processors assigned to this interval. Tasks A i and C are not assigned to the same processor (otherwise the whole interval would). So P i 1 receives task A i and h i tasks of weight 1 while P i 2 receives M -h i tasks of weight 1 and task C. The weight of P i 2 is M -h + C ≥ C = 5M while s i ≤ 3M for 1 ≤ i ≤ m. Hence P i 1 must be some P i , 1 ≤ i ≤ m while P i 2 must be some P m+j , 1 ≤ j ≤ m. Because this holds true on each interval, this defines two permutations σ 2 (i) and σ 1 (i) such that P i 1 = P σ 2 (i) and P i 2 = P σ 1 (i) . Because the bound K = 1 is achieved, we have:

• A i + h i = B + x i + h i ≤ B + z σ 2 (i) • M -h i + C ≤ C + M -y σ 1 (i) Therefore y σ 1 (i) ≤ h i and x i + h i ≤ z σ 2 (i) , and
m i=1 x i + m i=1 y i ≤ m i=1 x i + m i=1 h i ≤ m i=1 z i
By hypothesis, m i=1 x i + m i=1 y i = m i=1 z i , hence all inequalities are tight, and in particular

m i=1 x i + m i=1 h i = m i=1 z i . We can deduce that m i=1 y i = m i=1 h i = m i=1 z i -m i=1
x i , and since y σ 1 (i) ≤ h i for all i, we have y σ 1 (i) = h i for all i.

Similarly, we deduce that x i + h i = z σ 2 (i) for all i, and therefore

x i + y σ 1 (i) = z σ 2 (i) .
Altogether, we have found a solution for I 1 , which concludes the proof.

Back to the proof of Theorem 2. Obviously, the Interval Mapping optimization problem belongs to the class NP. Any instance of the Hetero-1D-Partition problem with n tasks a i , p processor speeds s i and bound K can be converted into an instance of the Interval Mapping problem with n stages of weight w i = a i , letting all communication costs δ i = 0, targeting a Communication Homogeneous platform with the same p processors and homogeneous links of bandwidth b = 1, and trying to achieve a period not greater than K. This concludes the proof. Proof. Consider an application with n stages S 1 to S n to be mapped onto a communicationhomogeneous platform composed of p processors P 1 to P p . The speed of P i is s i , and all links have same bandwidth b. Consider an optimal mapping for this application. If this mapping is intervalbased, we are done. Otherwise, there exist processors which are not assigned a single interval of stages. Let i 1 be the index of the first stage S i 1 that is mapped onto such a processor, say P u , and let i 2 be the last index such that the interval [i 1 , i 2 ] is mapped on P u . Stages S 1 to S i 1 -1 are mapped by intervals onto other processors. Rather than going on formally, let us illustrate the algorithm through the following example, where we have i 1 = 6, i 2 = 7 and u = 4: The idea is to transform the mapping so that P 4 will be assigned a single interval, without increasing the cycle-time of any processor. Recall that we use equations ( 4) and ( 5) to compute the period of a general mapping. There are two cases to consider:

Dominance of interval mappings for Communication Homogeneous platforms

P 1 S
• If the speed of P 4 is larger than (or at least equal to) the speed of P 5 , P 6 and P 7 , then we assign stages S 8 to S 12 to P 4 . This will indeed decrease its cycle-time, because these stages are processed in shorter time and no more communication is paid in between. Then we iterate the transformation with i 2 = 15.

• Otherwise, choose the fastest processor among P 4 , P 5 , P 6 and P 7 . Assume that it is P 6 . Then P 6 is assigned the extra stages S 11 to S 15 , and all the other subsequent stages that were assigned to P 4 . Because the communications are homogeneous, nothing is changed in the price paid by the following communications between P 4 and other processors that now go between P 6 and these processors. The cycle-time of P 4 has been reduced since we removed stages from it. The cycle-time of P 6 has not increased the period of the new mapping compared to the initial mapping. To see this, note that its first assigned stage first( 6) is the same. If its last assigned stage was already assigned to it before the transformation (last(6)), then its cycletime has decreased (because some stages are processed faster in between) or is unchanged. If its last assigned stage was originally assigned to P 4 (last(4)), then its new cycle-time is smaller than the old cycle-time of P 4 since first(6) > first(4) and some stages are eventually processed faster between first(6) and last(4). In both cases, we safely increase the value of i 1 and proceed to the next transformation, without increasing the period of the mapping.

After a finite number of such transformations, we obtain an interval-based mapping, whose period does not exceed the period of the original mapping, which concludes the proof.

Fully Heterogeneous platforms

Theorem 5. For Fully Heterogeneous platforms, the (decision problems associated to the) three mapping strategies ( One-to-one Mapping, Interval Mapping and General Mapping) are all NP-complete.

Proof. For all strategies, the problem clearly belongs to the class NP: given a solution, it is easy to verify in polynomial time that all stages are processed, and that the maximum cycletime of any processor does not exceed the bound on the period. To establish the completeness, we use a reduction from MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM (MMBWSP) [START_REF] Ausiello | Complexity and Approximation[END_REF][START_REF] Crescenzi | A compendium of NP optimization problems[END_REF]. We consider an instance I 1 of MMBWSP: given a set C = {c We build the following instance I 2 of our mapping problem (note that the same instance will work out for the three variants One-to-one Mapping, Interval Mapping and General Mapping):

• For the application: n = 2m -1 stages which for convenience we denote as

→ S 1 → S 1 → S 2 → S 2 → . . . → S m-1 → S m-1 → S m →
For each stage S i or S i we set δ i = w i = 1 (as well as δ 0 = δ n = 1), so that the application is perfectly homogeneous.

• For the platform (see Figure 5):

-we use p = m + m 2 processors which for convenience we denote as P i , 1 ≤ i ≤ m and P i,j , 1 ≤ i < j ≤ m. We also use an input processor P in and an output processor P out . The speed of each processor P i or P ij has the same value s = 1 2K (note that we have a computationhomogeneous platform), except for P in and P out whose speed is 0.

-the communication links shown on Figure 5 5K and are referred to as slow links. The intuitive idea is that slow links are too slow to be used for the mapping.

Finally, we ask whether there exists a solution with period 3K. Clearly, the size of I 2 is polynomial (and even linear) in the size of I 1 . We now show that instance I 1 has a solution if and only if instance I 2 does.

Suppose first that I 1 has a solution. We map stage S i onto P π(i) for 1 ≤ i ≤ m, and stage

S i onto processor P π(i),π(i+1) for 1 ≤ i ≤ m -1. The cycle-time of P 1 is 1 + 2K + d(c π(1) ,c π(2) ) 2 ≤ 1 + 2K + K 2 ≤ 3K. Quite similarly, the cycle-time of P m is smaller than 3K. For 2 ≤ i ≤ m -1, the cycle-time of P π(i) is d(c π(i-1) ,c π(i) ) 2 + 2K + d(c π(i) ,c π(i+1) ) 2 ≤ 3K. Finally, for 1 ≤ i ≤ m -1, the cycle-time of P π(i),π(i+1) is d(c π(i) ,c π(i+1) ) 2 + 2K + d(c π(i) ,c π(i+1) ) 2
≤ 3K. The mapping does achieve a period not greater than 3K, hence a solution to I 2 .

Suppose now that I 2 has a solution, i.e. a mapping of period not greater than 3K. We first observe that each processor is assigned at most one stage by the mapping, because executing two stages would require at least 2K + 2K units of time, which would be too large to match the period. This simple observation explains why the same reduction works for the three strategies, One-toone Mapping, Interval Mapping and General Mapping. Next, we observe that any slow link of bandwidth 1 5K cannot be used in the solution: otherwise the period would exceed 5K.

P 2,4 1
1 2 d(c 2 ,c 4 ) 2 d(c 1 ,c 4 ) 2 d(c 1 ,c 4 ) 2 d(c 1 ,c 2 ) 2 d(c 1 ,c 2 ) 2 d(c 2 ,c 4 ) 2 d(c 1 ,c 3 )
Figure 5: The platform used in the reduction for Theorem 5.

The input processor P in has a single fast link to P 1 , so necessarily P 1 is assigned stage S 1 (i.e. π(1) = 1). As observed above, P 1 cannot execute any other stage. Because of fast links, stage S 1 must be assigned to some P 1,j ; we let j = π(2). Again, because of fast links and of the one-to-one constraint, the only choice for stage S 2 is P π(2) . Necessarily j = π(2) = π(1) = 1, otherwise P 1 would execute two stages.

We proceed similarly for stage S 2 , assigned to some P 2k (let k = π(3)) and stage S 3 assigned to P π [START_REF] Beaumont | A realistic model and an efficient heuristic for scheduling with heterogeneous processors[END_REF] . Owing to the one-to-one constraint, k = 1 and k = j, i.e. π : [1. We have built the desired permutation, there remains to show that d(c π(i) , c π(i+1) ) ≤ K for

1 ≤ i ≤ m -1. The cycle time of processor P π(i) is d(c π(i) ,c π(i+1) ) 2 + 2K + d(c π(i) ,c π(i+1) ) 2
≤ 3K, hence d(c π(i) , c π(i+1) ) ≤ K. Altogether, we have found a solution for I 1 , which concludes the proof.

Heuristics

In this section several heuristics for Communication Homogeneous platforms are presented. We restrict to such platforms because, as already pointed out in Section 1, clusters made of differentspeed processors interconnected by either plain Ethernet or a high-speed switch constitute the typical experimental platforms in most academic or industry research departments.

Because of Theorem 4, we can restrict to interval-based mappings without any loss of generality. However, the complexity of determining the optimal interval-based mapping for Communication Homogeneous platforms is still open, this is why we propose several polynomial heuristics to tackle the problem. In the following, we denote by n the number of stages, and by p the number of processors.

Greedy heuristics

The first heuristics are greedy, i.e. they assign a stage, or an interval of stages, to a given processor, and this choice is independent of further choices. In these heuristics, we systematically assign L = n/p consecutive stages per processor (except for the last processor if n is not divisible by p). In other words, the heuristics always assign the same set of intervals, the difference between them lies in the allocations that they enforce. In fact, there is a single exception to this rule: for one of the random heuristics, the size of the interval is randomly determined.

The number of processors which will be used in the final solution is thus n/L . Note that if n ≤ p, then L = 1 and these heuristics perform a One-to-one Mapping algorithm.

H1a-GR: random -For each interval that needs to be assigned, we randomly choose a free processor which will handle it. As soon as a processor is handling an interval, it is not free any more and cannot be used to process another interval.

H1b-GRIL: random interval length -This variant of the greedy random H1a-GR is working similarly, but it further chooses the size of the interval to be assigned randomly. The distribution used is homogeneous, with an average length of L and a length between 1 and 2L -1. Notice that this heuristic is identical to H1a when L = 1.

H2-GSW: biggest w -In this heuristic, the choice is more meaningful since we select the interval with the most demanding computing requirement, and place it on the fastest processor. Intervals are sorted by decreasing values of i∈Interval w i , processors are sorted by decreasing speed s u , and the matching is achieved.

H3-GSD: biggest δ in + δ out -This heuristic is quite similar to H2-GSW except that the intervals are sorted according to their communication requirements, δ in + δ out , where in is the first stage of the interval, and out -1 the last one.

H4-GP: biggest period on fastest processor -This heuristic is balancing the computation and communication requirements of each interval: the processors are sorted by decreasing speed s u and, for the current processor u, we choose the interval with the biggest period (δ in + δ out )/b + i∈Interval w i /s u . Then we keep going with the remaining processors and intervals.

Sophisticated heuristics

This second set of heuristics presents more elaborated heuristics, trying to make clever choices.

H5-BS121: binary search for One-to-one Mapping -This heuristic implements the optimal algorithm for the One-to-one Mapping case, described in Section 3.1. When p < n, we cut the application in intervals similarly as in the greedy heuristics. All these heuristics perform a One-to-one Mapping on this new application, so H5-BS121 should always be better than all the greedy heuristics.

H6-SPL: splitting intervals -This heuristic sorts the processors by decreasing speed, and starts by assigning all the stages to the first processor in the list. This processor becomes used. Then, at each step, we select the used processor j with the largest period and we try to split its interval of stages, giving some stages to the next fastest processor j in the list (not yet used). This can be done by splitting the interval at any place, and either placing the first part of the interval on j and the remainder on j , or the other way round. The solution which minimizes max(period(j), period(j )) is chosen if it is better than the original solution.

Splitting is performed as long as we improve the period of the solution.

H7a-BSL and H7b-BSC: binary search (longest/closest) -The last two heuristics perform a binary search on the period of the solution. For a given period P , we study if there is a feasible solution, starting with the first stage (s = 1) and constructing intervals (s, s ) to fit on processors. For each processor u, and each s ≥ s we compute the period (s, s , u) of stages s..s running on processor u and check whether it is smaller than P (then it is a possible assignment). The first variant H7a-BSL choose the longest possible interval (maximizing s ) fitting on a processor for a given period, and in case of equality, the interval and processor with the closest period to the solution period. The second variant H7b-BSC does not take into account the length of the interval, but only finds out the closest period.

The code for all these heuristics can be found on the Web at: http://graal.ens-lyon.fr/~abenoit/code/skeleton-heuristics.c

Experiments

Several experiments have been conducted in order to assess the performance of the heuristics described in Section 4. We have generated a set of random applications with n = 1 to 50 stages, and two sets of random platforms, one set with p = 10 processors and the other with p = 100 processors. The first case corresponds to a situation in which several stages are likely to be mapped on the same processor because there are much fewer processors than stages. However, in the second case, we expect the mapping to be a One-to-one Mapping, except when communications are really costly. The heuristics have been designed for Communication Homogeneous platforms, so we restrict to such platforms in these experiments. In all the experiments, we fix b = 10 for the link bandwidths. Moreover, the speed of each processor is randomly chosen as an integer between 1 and 20. We keep the latter range of variation throughout the experiments, while we vary the range of the application parameters from one set of experiments to the other. Indeed, although there are four categories of parameters to play with, i.e. the values of δ, w, s and b, we can see from equation (2) that only the relative ratios δ b and w s have an impact on the performance. Each experimental value reported in the following has been calculated as an average over 100 randomly chosen application/platforms pairs. For each of these pairs, we report the performance of the 9 heuristics described in Section 4.

We report four main sets of experiments. For each of them, we vary some key application/platform parameter to assess the impact of this parameter on the performance of the heuristics. The first two experiments deal with applications where communications and computations have the same order of magnitude, and we study the impact of the degree of heterogeneity of the communications, i.e. of the variation range of the δ parameter: in the first experiment the communication are homogeneous, while in the second one δ varies between 1 to 100. The last two experiments deal with imbalanced applications: the third experiment assumes large computations (large value of the w to δ ratio), and the fourth one reports results for small computations (small value of the w to δ ratio).

Experiment 1: balanced communication/computation, and homogeneous communications

In the first set of experiments, the application communications are homogeneous, we fix δ i = 10 for i = 0..n. The computation time required by each stage is randomly chosen between 1 and 20. Thus, the communications and computations are balanced within the application. We notice that the sophisticated heuristics perform much better than the greedy ones when p = 10: they correspond to the lowest three curves. Heuristic H7b is the best for this configuration, before H7a and H6. H2 and H4 give the same result as H5 (binary search returning the optimal algorithm for a One-to-one Mapping), since the communications are homogeneous, and H3 is less good because it tries to make a choice among communications which are all identical. Finally, we see that all our heuristics are largely outperforming the random ones.

When p = 100, the optimal One-to-one Mapping algorithm returns the best solution (H5), obtained similarly by H2 and H4. The sophisticated heuristics are less accurate (but H7 gives a result very close to H5), and the random ones are not even represented on the plot: they always return a maximum period greater than 3.5, while we decided to zoom on the interesting part of the plots.

Experiment 2: balanced communication/computation, and heterogeneous communications

In this second set of experiments, the application communications are heterogeneous, chosen randomly between 1 and 100. Similarly to Experiment 1, the computation time required by each stage is randomly chosen between 1 and 20. Thus, the communications and computations are still relatively balanced within the application.

In the case with p = 10, the sophisticated heuristics are the best ones, and H6 outperforms the binary search heuristics H7a and H7b. Also, the first binary search H7a is better than H7b, while it was the other way round with homogeneous computations. The splitting heuristic H6 is definitively better in this heterogeneous case. We also notice that H5 is better than all the greedy heuristics, which is due to the fact that it implements the optimal algorithm for a One-to-one Mapping (or fixed-length Interval Mapping).

For p = 100, the sophisticated heuristics behave in the same way, but we notice that all the greedy heuristics find the optimal One-to-one Mapping solution, similarly to H5. In both cases, all our heuristics are much more efficient than the random ones.

Experiment 3: large computations

In this experiment, the applications are much more demanding on computations than on communications, making communications negligible compared to the computation requirements. We choose the communication time between 1 and 20, while the computation time of each application is chosen between 10 and 1000. In this case, both plots are showing the same behavior as in Experiment 1. In fact, even though communications are not the same for each application, their relative importance is negligible in front of the computations, and thus the system behaves as if communications were homogeneous. Thus, the One-to-one Mapping heuristics are clearly the best with p = 100, while H7b returns the smallest maximum period for p = 10.

Experiment 4: small computations

The last experiment is the opposite to Experiment 3 since the computations are now negligible compared to the communications. The communication time is still chosen between 1 and 20, but the computation time is now chosen between 0.01 and 10. In this case, since communications are important, the sophisticated heuristics perform better. This is because these heuristics often choose different length intervals in order to reduce the communication cost, while all the greedy and random heuristics are always making the same choice of intervals.

Similarly to the heterogeneous case (Experiment 2), H6 is the best heuristic, H7a and H7b are just a little bit ahead. Also, for One-to-one Mapping situations, the greedy heuristics returns the same result as H5.

However, in this situation, H3 is better than H2. This never happened before because computations were always the most relevant parameter to optimize. Also, we notice that the random heuristics are quite close to the greedy ones, because they choose the same intervals and so they pay the same communication cost. The clever choices performed by the greedy heuristics allow to save a little on the computation side.

Summary

To summarize our experimental results, we first point out that our heuristics are always much more efficient than random mappings. Moreover, we identify three heuristics which may each turn out to be the most efficient, depending upon the application and platform characteristics.

When there are more processors than pipeline stages, we can expect that a One-to-one Mapping might be a good choice. Actually, if the computations are the costly part of the application on a given platform, and communications are of lesser importance, then the greedy One-to-one Mapping heuristics return the best result, which we expect to be close to the optimal. This is also the case when communications are fully homogeneous between stages, because splitting between more stages does not add a large overhead. The optimal binary search H5 for One-to-one Mapping should be used in such cases.

The same balance between communications and computations leads to a different result when there are fewer processors, because it is then necessary to share the computation load between processors, and the decision where to split intervals can be really relevant. All the greedy heuristics are using intervals of fixed length and cannot make any clever choices. In such cases, H7b (Binary Search Closest) is the most efficient heuristic.

Moreover, as soon as communications are costly or with a high degree of heterogeneity, the greedy heuristics do not return satisfying results, because they may cut intervals on costly links between stages. Thus the more sophisticated Interval Mapping heuristics performs better. In such cases, the splitting heuristic H6 is the best choice.

Assessing the absolute performance of the heuristics

We introduce an integer linear program which allows to compute the optimal mapping for a given platform and application. We compare the results of the heuristics to the solution of this linear program, when available. The large number of integer variables in the linear program makes it impossible to solve large problem instances.

Linear program formulation

We present here an integer linear program to compute the optimal interval-based mapping on Fully Heterogeneous platforms. We assume n stages and p processors, plus two fictitious extra stages S 0 and S n+1 respectively assigned to P in and P out . First we need to define a few variables:

• For k ∈ [0..n + 1] and u ∈ [1..p] ∪ {in, out}, x k,u is a boolean variable equal to 1 if stage S k is assigned to processor P u ; we let x 0,in = x n+1,out = 1, and x k,in = x k,out = 0 for 1 ≤ k ≤ n.

• For k ∈ [0..n], u, v ∈ [1.
.p] ∪ {in, out} with u = v, z k,u,v is a boolean variable equal to 1 if stage S k is assigned to P u and stage S k+1 is assigned to P v : hence link u,v : P u → P v is used for the communication between these two stages. If k = 0 then z k,in,v = 0 for all v = in and if k = n then z k,u,out = 0 for all u = out.

• For k ∈ [0.

.n] and u ∈ [1.

.p] ∪ {in, out}, y k,u is a boolean variable equal to 1 if stages S k and S k+1 are both assigned to P u ; we let y k,in = y k,out = 0 for all k, and y 0,u = y n,u = 0 for all u.

• For u ∈ [1..p], first(u) is an integer variable which denotes the first stage assigned to P u ; similarly, last(u) denotes the last stage assigned to P u . Thus P u is assigned the interval [first(u), last(u)]. Of course 1 ≤ first(u) ≤ last(u) ≤ n.

• T period is the period of the pipeline.

We list below the constraints that need to be enforced. For simplicity, we write u instead of u∈ [1..p]∪{in,out} when summing over all processors. First there are constraints for processor and link usage:

• Every stage is assigned a processor: ∀k ∈ [0..n + 1], u x k,u = 1.

• Every communication either is assigned a link or collapses because both stages are assigned to the same processor:

∀k ∈ [0..n], u =v z k,u,v + u y k,u = 1
• If stage S k is assigned to P u and stage S k+1 to P v , then link u,v : P u → P v is used for this communication:

∀k ∈ [0..n], ∀u, v ∈ [1..p] ∪ {in, out}, u = v, x k,u + x k+1,v ≤ 1 + z k,u,v
• If both stages S k and S k+1 are assigned to P u , then y k,u = 1:

∀k ∈ [0..n], ∀u ∈ [1..p] ∪ {in, out}, x k,u + x k+1,u ≤ 1 + y k,u
• If stage S k is assigned to P u , then necessarily first u ≤ k ≤ last u . We write this constraint as:

∀k ∈ [1..n], ∀u ∈ [1..p], first u ≤ k.x k,u + n.(1 -x k,u ) ∀k ∈ [1..n], ∀u ∈ [1..p], last u ≥ k.x k,u
• If stage S k is assigned to P u and stage S k+1 is assigned to P v = P u (i.e. z k,u,v = 1) then necessarily last u ≤ k and first v ≥ k + 1 since we consider intervals. We write this constraint as:

∀k ∈ [1..n -1], ∀u, v ∈ [1..p], u = v, last u ≤ k.z k,u,v + n.(1 -z k,u,v ) ∀k ∈ [1..n -1], ∀u, v ∈ [1..p], u = v, first v ≥ (k + 1).z k,u,v
• There remains to express the period of each processor and to constrain it by T period :

∀u ∈ [1..p], n k=1      t =u δ k-1 b t,u z k-1,t,u   + w k s u x k,u +   v =u δ k b u,v z k,u,v      ≤ T period
Finally, the objective function is to minimize the period T period . We have O(np 2 ) variables, and as many constraints. All variables are boolean or integer, except the period, which is rational. We present some experiments comparing the heuristics to the linear program solution, when the number of variables is small enough to allow for a resolution in reasonable time.

LP Experiments

We compared the performance of the heuristics with the optimal solution returned by the linear program. Because of the large number of integer variables, experiments have been constrained to small platforms and applications. Also, in the following, we use only 10 instances of each application; we used 100 instances in the previous experiments but the LP programs can be quite long to solve. The results now represent an average over these 10 instances of the problem.

LP limitation

The largest experiment has been conducted with p = 8 processors. We tried to solve the linear program with up to n = 8 stages. The parameters are chosen randomly as in Experiment 1, with homogeneous communications and balanced communication/computation ratios (Section 5.1).

However, from n = 4 stages, the LP program requires quite a long time to be solved: it took up to 14 hours of computation time to solve a single instance of the problem. Because it was already very long for n = 4, we did not experiment with higher values of n. In practice, the use of the linear program in such cases is very limited because of the extremely long time required for the resolution.

We plotted (Figure 10) the result obtained with the LP program and some of the relevant heuristics. We see that the best heuristics, in this case the optimal One-to-one Mapping obtained with H5 and the binary search H7b, are very close to the result of the LP. The table displays the exact results, and we can see that there is only a tiny difference between the optimal result of the LP and the result returned by our heuristics. This can be explained by the precision of the binary search which was set to 0.0001. A more accurate result could have been obtained with the heuristics by increasing the precision.

LP on small platforms

Since we could not perform large experiments with the LP on platforms with many processors, we restricted ourselves to smaller platforms in order to study the absolute performance of the heuristics. The results seemed quite encouraging on the previous experiment with up to 4 stages and 8 processors, since we almost always found the optimal mapping. This experiment has been conducted on a platform with p = 4 processors, and applications with up to n = 10 stages. We plot the results for the homogeneous case (similar to Experiment 1, Section 5.1) and for the heterogeneous case (similar to Experiment 2, Section 5.2), which are the two most relevant cases. We restrict the plots (Figure 11) to some of the best heuristics identified in the previous experiments. In the homogeneous case, we point out that the best heuristic H7b is very close to the optimal result returned by the LP program. The maximum difference is for n = 10, with a difference of 0.11, which represents an error of less than 3%. This result is quite promising, even though we cannot conduct experiments for larger platforms because of the LP limitation.

The results are even better in the heterogeneous case, where the splitting heuristic H6 is almost always returning the optimal mapping, with a largest error less than 0.05%. Altogether, despite its intrinsic limitation to small platforms, the LP formulation enables us to assess the absolute performance of our heuristics. The results are very satisfying since the heuristics are always very close to the optimal result. In addition, their execution time remains small for large application/platform pairs, while the LP is not usable for platforms with more than 8 processors, due to the large number of integer variables.

Related work

As already mentioned, this work is an extension of the work of Subhlok and Vondran [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF][START_REF] Subhlok | Optimal latency-throughput tradeoffs for data parallel pipelines[END_REF] for homogeneous platforms. We have also discussed the relationship with the chains-to-chains problem [START_REF] Bokhari | Partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF]Approximate algorithms for partitioning problems[END_REF][START_REF] Hansen | Improved algorithms for partitioning problems in parallel, pipeline, and distributed computing[END_REF][START_REF] Iqbal | Efficient algorithms for a class of partitioning problems[END_REF][START_REF] Olstad | Efficient partitioning of sequences[END_REF][START_REF] Pinar | Fast optimal load balancing algorithms for 1D partitioning[END_REF] in Section 3.2.2.

We classify several related papers along the following four main lines:

Scheduling task graphs on heterogeneous platforms-Several heuristics have been introduced

to schedule (acyclic) task graphs on different-speed processors, see [START_REF] Maheswaran | A dynamic matching and scheduling algorithm for heterogeneous computing systems[END_REF][START_REF] Topcuoglu | Task scheduling algorithms for heterogeneous processors[END_REF] among others. Unfortunately, all these heuristics assume no restriction on the communication resources, which renders them somewhat unrealistic to model real-life applications. Recent papers [START_REF] Hollermann | Scheduling problems in a practical allocation model[END_REF][START_REF] Hsu | Task allocation on a network of processors[END_REF][START_REF] Sinnen | Comparison of contention-aware list scheduling heuristics for cluster computing[END_REF] suggest to take communication contention into account. Among these extensions, scheduling heuristics under the one-port model [START_REF] Johnsson | Optimum broadcasting and personalized communication in hypercubes[END_REF][START_REF] Krumme | Gossiping in minimal time[END_REF] are considered in [START_REF] Beaumont | A realistic model and an efficient heuristic for scheduling with heterogeneous processors[END_REF]: just as in this paper, each processor can communicate with at most one other processor at a given time-step.

Mapping pipelined computations onto special-purpose architectures-There are two lines of work related to mapping pipeline computations onto special architectures: the first deal with special-purpose architectures and FPGA arrays. A representative example is the work by Fabiani and Lavenier [START_REF] Fabiani | Placement of linear arrays[END_REF]. They study the placement of linear computations onto reconfigurable arrays. The other line of work is related to the design of fault-tolerant or power-aware mapppings for embedded systems. Representative examples are [START_REF] Zhu | Power-aware scheduling for multi-processor real-time systems[END_REF][START_REF] Aydin | Power-aware scheduling for periodic real-time systems[END_REF].

Mapping pipelined computations onto clusters and grids-The papers quoted in this paragraph are the most closely related to our work. They consider the problem of mapping communicating tasks onto heterogeneous platforms, but the applicative framework is different.

In [START_REF] Taura | A heuristic algorithm for mapping communicating tasks on heterogeneous resources[END_REF], Taura and Chien consider applications composed of several copies of the same task graph, expressed as a DAG (directed acyclic graph). These copies are to be executed in pipeline fashion. Taura and Chien also restrict to mapping all instances of a given task type (which corresponds to a stage in our framework) onto the same processor. In other words, they consider the same problem as ours, except that the linear pipeline is replaced by a general DAG. Their problem is shown NP-complete, and they provide an iterative heuristic to determine a good mapping. At each step, the heuristic refines the current clustering of the DAG. Beaumont et al [START_REF] Beaumont | Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms[END_REF] consider the same problem as Taura and Chien, i.e. with a general DAG, but they allow a given task type to be mapped onto several processors, each executing a fraction of the total number of tasks. The problem remains NP-complete, but becomes polynomial for special classes of DAGs, such as series-parallel graphs. For such graphs, it is possible to determine the optimal mapping owing to an approach based upon a linear programming formulation. The drawback with the approach of [START_REF] Beaumont | Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms[END_REF] is that the optimal throughput can only be achieved through very long periods, so that the simplicity and regularity of the schedule are lost, while the latency is severely increased.

Another important series of papers comes from the DataCutter project [START_REF]DataCutter Project: Middleware for Filtering Large Archival Scientific Datasets in a Grid Environment[END_REF]. One goal of this project is to schedule multiple data analysis operations onto clusters and grids, decide where to place and/or replicate various components [START_REF] Beynon | Performance optimization for data intensive grid applications[END_REF][START_REF] Beynon | Optimizing execution of component-based applications using group instances[END_REF][START_REF] Spencer | Executing multiple pipelined data analysis operations in the grid[END_REF]. A typical application is a chain of consecutive filtering operations, to be executed on a very large data set. So the task graphs targeted by DataCutter are more general than our linear pipeline framework, but still much more regular than arbitrary DAGs, which allows them to design several heuristics to efficiently solve the previous placement and replication optimization problems.

Mapping skeletons onto clusters and grids-Benoit et al [START_REF] Benoit | Evaluating the performance of pipelinestructured parallel programs with skeletons and process algebra[END_REF][START_REF] Benoit | Scheduling skeleton-based grid applications using PEPA and NWS[END_REF] have explored the use of stochastic process algebra to decide for the best mapping of pipeline and deal skeletal applications. However, in this work, no formal method has been developed in order to find a mapping; instead, the authors performed a relative comparison between several (given) mappings. They provided a performance model for each mapping, based on process algebra, and they determined which one was the best according to the period, estimated through performance results of the model.

Conclusion

In this paper, we have thoroughly studied a difficult mapping problem onto heterogeneous platforms. We restricted ourselves to the class of applications which have a pipeline structure, and studied the complexity of the problem for different variants of mapping strategies and different types of platforms. To the best of our knowledge, it is the first time that pipeline mapping is studied from a theoretical perspective, while it is quite a standard and widely used pattern in many real-life applications.

For a One-to-one Mapping, we provided a polynomial algorithm which finds the optimal solution. However, restricting each processor to execute a single stage may not be the best choice, mainly when communications are very costly, hence take very long time between two consecutive stages. In this case, we would rather place the two consecutive stages onto the same processor, which is allowed in the Interval Mapping variant of the problem. For this latter case, we provided several efficient polynomial heuristics for Communication Homogeneous platforms. Finally, we point out that the absolute performance of the heuristics is quite good, since their result is close to the optimal solution returned by an integer linear program.

There remains much work to extend the results of this paper. On the practical side, we still need to design efficient heuristics for Fully Heterogeneous platforms and assess their performance, which is a challenging problem. In the longer term, we plan to perform real experiments on heterogeneous platforms, using an already-implemented skeleton library, in order to compare the effective performance of the application for a given mapping (obtained with our heuristics) against the theoretical performance of this mapping.

A natural extension of this work would be to consider other widely used skeletons. For example, when there is a bottleneck in the pipeline operation due to a stage which is both computationallydemanding and not constrained by internal dependencies, we can nest another skeleton in place of the stage. For instance a farm or deal skeleton would allow to split the workload of the initial stage among several processors. Using such deal skeletons may be either the programmer's decision (explicit nesting in the application code) or the result of the mapping procedure. Extending our mapping strategies to automatically identify opportunities for such deal skeletons [START_REF] Cole | Bringing Skeletons out of the Closet: A Pragmatic Manifesto for Skeletal Parallel Programming[END_REF], and implement these, is a difficult but very interesting perspective.

Figure 1 :

 1 Figure 1: The application pipeline.

Figure 2 :

 2 Figure 2: The target platform.

Figure 3 :

 3 Figure 3: Example of general mapping.

Figure 4 :

 4 Figure 4: Example of general mapping with the one-port model.

Definition 1 (Theorem 3 .

 13 Hetero-1D-Partition-Dec). Given n elements a 1 , a 2 , . . . , a n , p values s 1 , s 2 , . . . , s p and a bound K, can we find a partition of [1..n] into p intervals I 1 , I 2 , . . . , I p , with I k = [d k , e k ] and d k ≤ e k for 1 ≤ k ≤ p, d 1 = 1, d k+1 = e k + 1 for 1 ≤ k ≤ p -1 and e p = n, and a permutation σ of {1, 2, . . . , p}, such that max 1≤k≤p i∈I k a i s σ(k) ≤ K ? The Hetero-1D-Partition-Dec problem is NP-complete.

Theorem 4 .

 4 For Communication Homogeneous platforms, interval-based mappings are dominant.

  1 , c 2 , . . . , c m } of m cities, an initial city s ∈ C, a final city f ∈ C, distances d(c i , c j ) ∈ N satisfying the triangle inequality, and a bound K ≥ 2 on the largest distance, does there exist a simple path from the initial city s to the final city f passing through all cities in C, i.e. a permutation π : [1..m] → [1..m] such that c π(1) = s, c π(m) = f , and d(c π(i) , c π(i+1) ) ≤ K for 1 ≤ i ≤ m -1? To simplify notations, and without loss of generality, we renumber cities so that s = c 1 and f = c m (i.e. π(1) = 1 and π(m) = m).

  have a larger bandwidth than the others, and are referred to as fast links. More precisely, b P in ,P 1 = b Pm,Pout = 1, and b P i ,P ij = b P ij ,P j = for 1 ≤ i < j ≤ m. All the other links have a very small bandwidth b = 1

. 3 ]

 3 → [1..m] is a one-to-one mapping. By induction, we build the full permutation π : [1..m] → [1..m]. Because the output processor P out has a single fast link to P m , necessarily P m is assigned stage S m , hence π(m) = m.

Figure 6 :

 6 Figure 6: Experiment 1: homogeneous communications.

20

 20

Figure 7 :

 7 Figure 7: Experiment 2: heterogeneous communications.

Figure 8 :

 8 Figure 8: Experiment 3: large computations.

Figure 9 :

 9 Figure 9: Experiment 4: small computations.

Figure 11 :

 11 Figure 11: LP on small platforms.

Table 1 :

 1 Complexity results for the different instances of the mapping problem.

		Fully Homogeneous	Comm. Homogeneous Fully Heterogeneous
	One-to-one Mapping	polynomial (bin. search)	polynomial (bin. search)	NP-complete
	Interval Mapping	polynomial (dyn. prog [32, 33])	NP-complete	NP-complete
	General Mapping	same complexity as Interval Mapping	NP-complete

  1 details the procedure.

procedure Greedy Assignment begin Work with fastest n processors, numbered P 1 to P n , where s 1 ≤ s 2 ≤ . . . ≤ s n Mark all stages S 1 to S n as free for u = 1 to n do Pick up any free stage S k s.t. δ k-1 /b + w k /s u + δ k /b ≤ T period Assign S k to P u . Mark S k as already assigned If no stage found return "failure" end end Algorithm 1: Greedy assignment algorithm for a given period T period .

d(c i ,c j )


Jérémy Frey
email: jeremy.frey@inria.fr

VIF: Virtual Interactive Fiction (with a twist)

Keywords: Storytelling, Physiological Computing, Brain-Computer Interface, Adaptive Systems, Virtual Reality

Nowadays computer science can create digital worlds that deeply immerse users; it can also process in real time brain activity to infer their inner states. What marvels can we achieve with such technologies? Go back to displaying text. And unfold a story that follows and molds users as never before.

ACM Classification Keywords

Introduction

On the one hand, we have devices that are more than ever capable to create a variety of illusions and to draw attention up to the point that users will forget about the real worldthe notion of virtual presence [START_REF] Slater | How we experience immersive virtual environments: the concept of presence and its measurement[END_REF]. The paragons of such devices are probably at this moment head-mounted displays (HMD), that, literally, replace what people see with a virtual world -so called virtual reality (VR). Combined with headphones, the reality gets obliterated for most 1 .

On the other hand, physiological computing is mature enough to asses mental states and emotions [START_REF] Stephen | Fundamentals of physiological computing[END_REF]. In particular, mobile brain imaging techniques alike electroencephalography (EEG) can be employed to measure a variety of constructs such as workload or attention; cognitive processes that were harder to monitor in the past [START_REF] Frey | Review of the use of electroencephalography as an evaluation method for human-computer interaction[END_REF]. Physiological sensors are not restricted to the laboratory, nowadays they can be used the field through carefully crafted wearables, e.g. [START_REF] Gervais | Tobe: Tangible Out-of-Body Experience[END_REF]. These technologies make computers comprehend users [START_REF] Picard | Affective computing[END_REF].

On the other other hand, is lying interactive fiction (IF), stories that depend on the actions of the readers/players2 , a genre that is gaining increased attention from outside its original community [START_REF] Montfort | Interactive Fiction Communities From Preservation through Promotion and Beyond[END_REF]. The form of IF evolved from choicebased adventure games to complex generative systems that can narrate a living world [START_REF] Montfort | Curveship's automatic narrative style[END_REF]. Besides advances in natural language processing, IF attracted new game-makers thanks to writing tools -based on markup languages or graphical programming -easier to handle 3 . Putting hands back together, physiological sensors and brain computer interfaces could be added to the repertoire of IF makers in order to craft more resonating stories, that can both adapt and react to players. A narrative branch could be generated based on the (past) affect of the user, in order to favor or avoid an emotion. The events or the phrasing could be driven by the attentional state of the user to increase comprehension and seek a state of flow. Even more involving and pervasive, the user could be asked to perform breathing exercises and get actually relaxed before starting an adventure in a gloomy dungeon -a journey of initiation for the wannabe warrior that will echo within the reader.

While rich inputs derived from physiology are already investigated with traditional video games [START_REF] Nijholt | Turning shortcomings into challenges: Brain-computer interfaces for games[END_REF][START_REF] Lennart | Directions in Physiological Game Evaluation and Interaction[END_REF], the "form factor" of IF should ease the integration of these modalities to the fabric of the story. Indeed, readers are used to filling the gaps between ellipses or suggested details; through their imagination they seize the content and make it their own. To change the mood of a scene, whereas a AAA video game will have to smoothly adapt assets that where expensive to build in the first place, a writer will lightly tune the right adjective. Simple and seamless.

Far from being a trendy gimmick, the use of HMD and VR let readers focus entirely on the text, preventing stimuli external to the narrative to reach them and distract them from the story 4 . The simplicity of the scene will hopefully reduce perceptual load, freeing more cognitive resources to let them build their own representations, increasing engagement. At the same time, HMD could be used to design simple game mechanisms based on gaze and head tracking, yet another input modality for readers to physically interact with IF (see System Description below).

First and foremost, this technology is really a mean to put upfront one medium that shaped for ages humanity [START_REF] Bettelheim | The Uses of Enchantment: The Meaning and Importance of Fairy Tales[END_REF]. If the word is mightier than the tools, now it shall be exalted by computer science to help twist our minds for the better.

Description of the system

This section describes a proof of concept that implements a basic set of features to support the ideas discussed previously. The program and its source code are available on https://github.com/jfrey-xx/vif.

Rendering

The graphics are kept simple on purpose. As an emanation of IF -even in 3D and in stereoscopy -the virtual world is mostly composed of text blocks. Generative typography and colors can impersonate the narrator or characters. They can also be used to give a biofeedback -e.g. "your heart beat" could pulse toward the camera and change color along each heartbeat (Figure 1) -depending on the control or awareness given to users (see also [START_REF] Gervais | Tobe: Tangible Out-of-Body Experience[END_REF]).

Other graphical elements are present, but only to fulfill particular functions. A grid on the floor gives a sense of position in space. The day/night cycle has two purposes: to give a sense of orientation (the trajectory of the sun gives cardinal directions) and to give a sense of time (Figure 6).

Interaction

The main contribution comes from the events that can be triggered depending on the physiology and on the mental state of the players -e.g. three deep breaths, getting relaxed, . . . However, alike choice-based adventures, players can also select explicitly interactive chunks of words -e.g. "open the box" / "feed the box to my pony". They use their gaze to do so (Figure 5). Time passing by can be measured to drive the narration and the text could change accordingly to the time of the day -e.g. wolves are obviously out at night. The virtual world surrounding players, the text can be positioned at various places, both related to the orientation of the player or to cardinal directions (e.g. "behind", "North"). Then the field of view of the player can be taken into account in order to show or hide text blocks based on what is seen (Figure 8). Sentences that could creep from behind: ideal for an horror novel.

Sensors

Wearables such as belts measuring breathing (Figure 4) or smartwatches measuring heart rate can be plugged to the system. However, since players are already equipped with HMD, this latter piece of hardware can be used at the same time to embed sensors. For instance, thanks to affordable hardware coming from the DIY movement, a (very) early prototype of a HMD with integrated EEG electrodes was crafted to measure brain activity (Figure 3). Regular EEG caps could also be combined with HMD (Figure 2). Eventually, a whole array of physiological measures may be inferred directly from a device placed on the head -see, e.g. [START_REF] Hernandez | Cardiac and Respiratory Parameter Estimation Using Head-mounted Motion-sensitive Sensors[END_REF].

Writing 101

Game-makers with a background in programming can suit the engine behind VIF to their needs, for example add new typographic effects. However, for regular users that simply wish to create new content, a text parser based on a markup language has been implemented (Figure 7).

Beyond: going social

Since communications between the game engine and physiological measures rely on a network protocol, it would be trivial to share and sync data between multiple instances of the system. Doing so would extend the system with multiplayer elements. Several in-game characters could then be personified by others users -the states and choices of everyone influencing the overall story -; direct or intimate interactions that could deeply connect players, help them share an experience.

Inspirations

The idea of using processed physiological signals as a pervasive element roots to the affective computing movement [START_REF] Picard | Affective computing[END_REF], even though since these debuts the spectrum of available measures has widened beyond emotions through physiological computing [START_REF] Stephen | Fundamentals of physiological computing[END_REF] and neuroadaptive technologies [START_REF] Zander | Towards passive brain-computer interfaces: applying brain-computer interface technology to human-machine systems in general[END_REF].

My personal (re)discovery of the IF genre comes from the productions of the Inkle Studios5 . Whereas I could not achieve a CYOA book when I was a child, their clever games designs kept me engaged throughout the stories, giving a clue on how to hook readers. Later on I found interesting perspectives on the whys and hows we may rely so much on stories within the preliminary chapters of [START_REF] Bettelheim | The Uses of Enchantment: The Meaning and Importance of Fairy Tales[END_REF], Bruno Bettelheim's book describing how significant fairy tales could be during child development.

However, these cornerstones are a mere retcon of what aroused my interest for interactive and adaptive fictions in the first place. All started as it should, with a story within a story. In Ender's Game [START_REF] Scott | Ender's Game[END_REF], Orson Scott Card describes how a RPG-like video game used by the military to monitor young recruits' mental health is "hijacked" by an alien race in order to reach out for the hero and plead for empathy 6 .

Superpowers

As per workshop requirement, few lines about my abilities. During my PhD I started to explore how physiological computing can contribute to human-computer interaction and foster new communication channels among people. In particular, I have been using EEG and machine learning to measure constructs such as workload, comfort or attention -dimensions of the user experience that I was able to grasp thanks to my background in cognitive science. With hacking spells, I helped to craft sensors more practical to use in the field, an opportunity to investigate multi-users scenarios and playful contexts. I also participated in the development of novel physiological feedback, that could be integrated seamlessly to the physical surroundings through spatial augmented reality and tangible user interfaces. Sciencefiction reader at night to fetch ideas, daydreamer to create

H. 1 . 2 [

 12 User/Machine Systems]: Human information processing; H.5.1 [Multimedia Information System]: Artificial, augmented, and virtual realities

Figure 2 :

 2 Figure 2: The Oculus Rift DK1 HMD a is combined with Neuroelecronics Enobio EEG cap b and OpenBCI amplifier c to both immerse and monitor user's brain activity.

Figure 3 :Figure 4 :

 34 Figure 3: Prototype of a HMD device that directly embeds EEG electrodes -here a Vrvana Totem a . Picture © Alexandre Girardeau. a http://www.vrvana.com/

Figure 5 :

 5 Figure 5: Users can interact with text elements in a more traditional way, using their gaze.

Figure 6 :

 6 Figure 6: Besides text, graphical elements are kept minimal. The environment serves purposes, e.g. to give a sense of time or a sense of orientation.

Figure 7 :

 7 Figure 7: Game-makers / writers can use their favorite text editor and a markup language to create new content.

Figure 8 :

 8 Figure 8: Events can occur depending on what players see and on texts' position, resulting in emerging game mechanisms that are physically involving.

Even though the focus is here on textual stories with (optional) ambient sounds, any other combination of input modalities -e.g. narrate a story and display (optional) colors -is of course suitable.

In the present document I consider a broad definition of IF, that encompasses both Choose-Your-Own-Adventure (CYOA) games and games where users have to actually type text to interact.

[START_REF] Stephen | Fundamentals of physiological computing[END_REF] One could find a variety of commented IF works on https://emshort. wordpress.com/.

Resulting in an immersive book indeed.

http://www.inklestudios.com/

Note that novel's background is itself a (too) serious game. new ones, I am not afraid to get my hands dirty to implement them, more eager to do so when they sound crazy or stupid, even when I have already too many projects running for my own good. In the end I seek to use computer science as a mean to enhance well-being and facilitate human relationships on the whole. Mandatory website: http://phd.jfrey.info/.

Acknowledgements

After months toying with the idea, I finally had the opportunity (and the liberty!) to implement a first version of this project while I was visiting the MuSAE Lab in late 2015, under the kind supervision of Tiago H. Falk. During my stay in Montreal, the HMD+EEG cocktail would never have come to life without the vivid Breathe@Work crew that gathered during the Hacking Health event, and for that to happen, I was lucky to meet two wonderful communities there, namely NeuroTechX and Highway 101. Since VIF is but a spin-off of the Tobe toolkit, I shall not to forget my usual co-authors [5]. Finally, Joan Sol Roo is the one who made me realize the connection with Ender's Game, that explained it all.