Anne Benoit
email: anne.benoit@ens-lyon.fr

Alexandru Dobrila
email: adobrila@lifc.univ-fcomte.fr

Jean-Marc Nicod
email: jmnicod@lifc.univ-fcomte.fr

Laurent Philippe
email: lphilippe@lifc.univ-fcomte.fr

Throughput optimization for micro-factories subject to failures

In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks onto a set of machines. The originality of our approach is the failure model for such applications in which tasks are subject to failures rather than machines. If there is exactly one task per machine in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same machine. Several polynomial time heuristics are presented for the most realistic specialized setting, in which tasks of a same type can be mapped onto the same machine. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed.

I. INTRODUCTION

Distributed systems provide a support to tolerate faults but their correct management also implies to take faults into account. Standard distributed systems mainly focus on processor dependent faults. We commonly assume that faults are generated by the execution platform and thus that the fault model must be linked to the processors, or more generally to the resources that perform the tasks. In this case, a stochastic fault model that defines the fault probability is usually attached to the processor. This model fits distributed computing environments such as parallel platforms where failures come from the nodes of the platform.

If we look however at a more general definition of a distributed system, we can note that this model does not always fit. In some distributed platforms the fault model may be attached to the task rather than to the processor or node. For example, in production systems, a task may be complex to perform -for instance due to some hard manipulation -with an impact on its success ratio. If the same robot is able to perform different tasks, it may generate less faults on simple tasks than on difficult ones.

In this paper we are interested in studying the impact of a fault model linked to the tasks. The application context is more a production system than a distributed computing system. Our specific use case is a micro-factory but the results presented in this paper are more generally applicable to distributed production systems or to distributed systems where the fault probability is attached to tasks instead of resources.

Micro-factories are production units designed to produce pieces composed of micro-metric elements [?]. Today's microfactories are composed of micro-robots able to carry out basic operations through elementary actuators as piezo-electric beams (e.g. for gripping), stick-slip systems, etc. As these robots are usually teleoperated by a human operator only simple tasks can be done. To perform more complex operations and to improve their efficiency, micro-factories need to be automated and robots grouped in cells. Then cells will be put together and they will cooperate to produce complex assembled pieces, as it is done for macroscopic productions. Due to the pieces, actuators and cells size, it is however impossible for human operators to directly interfere with the physical system. So it needs a highly automated command. The complexity of this command makes it mandatory to develop a distributed system to support this control. So, the cell group results in a distributed system that is very similar to a distributed computing platform. However, at this scale the physical constraints are not totally controlled so there is a need to take faults into account in the automated command. As previously explained, the fault model that we consider in this work differs from the standard fault model used in computing systems.

The main issue for fault tolerant systems [START_REF] Nelson | Fault-tolerant computing: Fundamental concepts[END_REF] is to overcome the failure of a node, a machine or a processor. To deal with those faulty machines the most common method used in distributed systems is to replicate [START_REF] Cirne | On the efficacy, efficiency and emergent behavior of task replication in large distributed systems[END_REF] the data. Those models assume that failures are attached to a machine. So the probability to get one product as a result is highly increased when the task is replicated on several machines. Once all the replicated jobs are done, a vote algorithm [START_REF] Parhami | Voting algorithms[END_REF] is often used to decide which result is the right one. In real time systems, another model called Window-Constrained [START_REF] West | Analysis of a window-constrained scheduler for real-time and best-effort packet streams[END_REF] model can be used. In this model one considers that, for y messages, only x (x ≤ y) of them will reach their destination. The y value is called the Window. The looses are not considered as a failure but as a guarantee: for a given network a Window-Constrained Scheduling [START_REF] West | Dynamic windowconstrained scheduling of real-time streams in media servers[END_REF], [START_REF] West | Dynamic window-constrained scheduling for multimedia applications[END_REF] can guarantee that no more than x messages will be lost for every y sent messages. In this paper, the Window-Constrained based failure model is adapted to a distributed system, the micro-factory. So the issue is to guarantee the output of a given number of products. With failures attached to tasks, we can compute the number of products needed as input of the system and guarantee the output for the desired number of products.

The paper is organized as follows. Section II gives the characteristics and a more formal presentation of the context of micro-factories and of the failure model. Section III presents the optimization problems tackled in the paper. The complexity study and results are given in Section IV. Heuristics to solve the problem are proposed in Section V and simulation results for these heuristics are given and commented in Section VI. Finally, we conclude in Section VII.

II. FRAMEWORK

We outline in this section the characteristics of the applicative framework and target platform. Finally, we describe and motivate the failure model that we use in this work.

A. Applicative framework

We consider a set N of n tasks:

N = {T 1 , T 2 , . . . , T n }. Each task T i (1 ≤ i ≤ n) is
applied successively on a set of products, numbered from 1 to x in . We wish to produce x out products as an output, and the total number of products x in being processed may depend on the allocation (x in ≥ x out , losses due to failure as explained later in Section II-C). Note that all products are identical. When the context is not ambiguous, we may also design task T i by i for clarity, as for instance in the figures.

A type is associated to each task as the same operation may be applied several times to the same product. Thus, we have a set T of p task types with n ≥ p and a function t : [1..n] → T which returns the type of a task: t(i) is the type of task T i , for

1 ≤ i ≤ n.
The application is a directed acyclic graph (DAG) in which the vertices are tasks, and edges represent dependencies between tasks. An example of application with n = 5 tasks is represented on Figure 1. In the top branch of the DAG, we need to finish the processing of task T 1 on one product before proceeding to task T 2 . The join to task T 4 corresponds to the merge of two products, which produces a new unit of product composed of the two. Typically one instance of product from each predecessor in the graph is required to process with the joining task. Note that forks cannot be considered in this context as the output of one task is a physical component that cannot be split in two. Unlike data that can be easily replicated at every step of a DAG, an instance of a physical component is the result of all the preceding tasks and cannot be duplicated as it is material.

B. Target platform

The platform consists in a set M of m machines: M = {M 1 , M 2 , . . . , M m }. All machines can be interconnected: the platform graph is a complete graph. A machine handles some of the tasks at a given speed: machine M u can perform the task T i onto one product in a time w i,u . We also consider that tasks of the same type have the same execution time on a given machine, since they correspond to the same action to be performed on the products. Thus, we have:

∀i, i ′ ∈ [1, n], ∀u ∈ [1, m], t(i) = t(i ′ ) ⇒ w i,u = w i ′ ,u
We neglect the communication time required to transfer a product from one machine to another. If a communication may not be negligible, we can always model it as a particular task with a dedicated machine (the machine responsible of the transfer of the product).

We are interested in producing the desired number of products rather than producing a particular instance of a product. So we consider that products are not identified: two products, on which the same sequence of tasks has been done, are exactly similar and we can use one or the other indifferently for further operations.

C. Failure model

An additional characteristic of our framework is that tasks are subject to failure. It may happen that a product is lost or damaged while a task is being executed on this product. For instance electrostatic strength may be accumulated on the actuator, and thus the piece will be pushed away rather than caught. Indeed, we work at a scale such that these electrostatic strengths are stronger than gravity.

Due to our application setting, we deal only with transient failures, as defined in [START_REF] Jalote | Fault Tolerance in Distributed Systems[END_REF]. The tasks are failing for some of the products, but we do not consider a permanent failure of the machine responsible of the task, as this would lead to a failure for all the remaining products to be processed and the unability to finish them.

One classical technique used to deal with failures is replication [START_REF] Cirne | On the efficacy, efficiency and emergent behavior of task replication in large distributed systems[END_REF]. However, while replication is very useful for hardware failures of machines, we cannot use it in our framework since the products are not a data such as a numerical image that we need to process, but it is a physical object. Thus, the only solution consists in processing more products than needed, so that at the end, the required number of finished products are output.

The failure rate of task T i is characterized by the percentage of failure for this task. More precisely, the failure is denoted

f i = a i b i
, where a i is the number of products that fail each time b i products have been processed. r i = b ia i is the number of successful products, and b i is also called period of task T i . We enforce that two tasks of similar type are likely to fail at the same rate with the following equation:

∀i, i ′ ∈ [1, n] t(i) = t(i ′ ) ⇒ f i = f i ′ .
Since we advocate the computation of more products than needed, we explain in the following how to compute the number x in of products that should be processed in order to get x out products as an output, and we illustrate it on the example of Figure 2. For instance task T 2 has one failure every 6 products that are being processed by this task. Given these failure rates, the number of products that should be given as an input to task T i in order to have x out products out of the system is denoted x i . Thus, x in = max 1≤i≤n x i . The computation of x i is done backward: if we know the number of products that should be output by task T i and its failure rate, we can compute the number of input products that should be given to this task to guarantee this output. As we work only with linear chain and in-trees, each task has an unique outgoing edge, thus the number of products to be output by T i is x i+1 (or x out for T 4 in the example).

f 1 = 1 5 f 2 = 1 6 f 3 = 1 8 f 4 = 2 9 1 2 3 4 x 1 x 2 x 3 x 4 x out
To determine x i , we need to sum both the number of products which will be successfully processed (i.e., x i+1 ), and the number of products which fail during the processing phase. Thus we must compute the number of periods of the task T i , which is an integer number being greater than the number of output products divided by the number of successful products computed each period:

x i+1 r i . In the worst case, failures occur for the first a i products of the period, thus the number of products to be computed and which will fail is

a i × x i+1 r i .
Finally we can deduce the total number of products that should be computed:

x i = x i+1 + a i × x i+1 r i (1)
As an extension of this formula, we can also deduce the completion time L xi+1,i needed to exit x i+1 products out of task T i , once it has been assigned to a machine, M u . The completion time L xi+1,i is the maximum between the time needed to compute x i products on task T i (i.e., x i × w i,u ) and the sum of the time to output x i product out of the task T i-1 (i.e., L xi,i-1 ) and the completion time of the last product on task T i (i.e., w i,u ).

L xi+1,i = max (L xi,i-1 + w i,u , x i × w i,u ) (2)
III. OPTIMIZATION PROBLEMS Now that the framework has been clarified, we formalize in this section the various optimization problems that we wish to solve. Our goal is to assign tasks to machines so as to optimize some key performance criteria. The solution to a problem is thus an allocation function a : [1..n] → [1..m] which returns for each task the machine on which it is executed. Thus, if a(i) = u, task T i is executed on machine M u , and the processing of one product for this task takes a time w i,u .

We first discuss the objective criteria that we want to optimize. Then we introduce the different rules of the game that can be used in the definition of the allocation function a. Finally, Section III-C gives a summary of all problem variants, combining framework characteristics and rules of the game. The complexity of these various problems is discussed in Section IV.

A. Objective function

In our framework, several objective functions could be optimized. For instance, one may want to produce a mapping of the tasks on the machines as reliable as possible, i.e., minimize the total number of products to input in the system, x in . Rather, we consider that products are cheap, and we focus on a performance criteria, the throughput. The goal is to maximize the number of products processed per time unit, making abstraction of the initialization and clean-up phases. This objective is important when a large number of products must be produced.

Rather than maximizing the throughput of the application, we rather deal with the period, which is the inverse of the throughput. First we need to introduce the fractional number x i , which is the average number of products required to output one product out of the system for task T i . Similarly to the computation of the x i performed in Section II-C, we can compute the x i recursively for any application DAG, setting the number of final products x out = 1. Indeed, if task T i needs to output x i+1 products, then x i = bi ri × x i+1 (the fraction represents the number of products needed per successful product). Starting from the nodes with no successor (and thus x i+1 = x out = 1), we can then compute x i for all i. Note that x i ≤ x i since x i is an upper integer part which accounts for the worst case failures.

The computation of x i and x i for the example of Figure 2 is illustrated in Table I. For instance, x 4 = 9/(9 -2) = 9/7 ≃ 1.3.

x i 7 5 4 3 x i ≃ 2.2 ≃ 1.8 ≃ 1.5 ≃ 1.3
We are now ready to define the period of a machine: it is the time needed by a machine to execute all the tasks allocated onto this machine in order to produce one final product out of the system. Formally, we have

period(M u ) = a(i)=u x i w i,u (3)
The period of machine M u is the sum, for each task allocated to that machine, of the average number of products (x i ) needed to output one product, multiplied by the speed (w i,u ) of that task onto that machine. The slowest machine will slow down the whole application, thus we aim at minimizing the largest machine period. The machines realizing this maximum are called critical machines. If M c is a critical machine, then period = period(M c ) = max Mu∈M period(M u ). Note that minimizing the period is similar to maximizing the throughput.

B. Rules of the game

In this section, we classify several variants of the optimization problem that has been introduced. For one-to-one mappings, we enforce that a single task must be mapped onto each machine. Then we consider the case of specialized machines: several tasks of the same type can be mapped onto the same machine; such mappings are called specialized mappings. Finally, general mappings have no constraints: any task (no matter the type) can be mapped on any machine.

1) One-to-one mappings:

In this first class of problems, a single task is mapped on each machine. This rule of the game is enforced with the following constraint, meaning that a machine cannot compute two different tasks:

∀1 ≤ i, i ′ ≤ n i = i ′ ⇒ a(i) = a(i ′ ) (a) (b) 2 (c) 1 2 3 3 1
M 2 M 4 M 3 M 2 M 1 M 1 M 4 M 3 Figure 3.
One-to-one mapping.

On Figure 3, we have an application graph (a) that must be mapped on a platform graph (b). The result is shown in (c) where we can see that one machine can handle only one task. Thus this mapping is quiet restrictive because we must have at least as many machines as tasks.

2) Specialized mappings: We have dedicated machines that can realize only one type of tasks. But task types are not dedicated to machines, so two machines may compute different tasks of the same type.

For instance, let us consider five tasks T 1 , T 2 , T 3 , T 4 , T 5 with the following types: t(1) = t(3) = t(5) = 1 and t(2) = t(4) = 2. If the machine M 3 computes task T 1 , it could also execute T 3 and T 5 but not T 2 and T 4 . As types are not dedicated to machines, T 5 could also be assigned to another machine, for instance M 1 . This situation is described on Figure 4.

The following constraint expresses the fact that a machine cannot compute two tasks of different types:

∀1 ≤ i, i ′ ≤ n t(i) = t(i ′ ) ⇒ a(i) = a(i ′ )
3) General mappings: A machine can compute any task regardless of its type, thus there are no constraints.

An example of this case is shown on Figure 5. Here the type of tasks are the following : t(1)=t(3)=t(5)=1 and t(2)=t(4)=2.

M 2 M 2 M 1 M 3 M 4 M 1 M 4 M 3
(b)

1 2 3 5 4 (a) (c) 3 4 1 2 5 M 2 M 1 M 2 M 3 M 4 M 1 M 4 M 3

C. Problem classification

We summarize in this section the optimization problems which arises from our application. The two important parameters of a problem are :

• the rules of the game (one-to-one or specialized or general mapping); • and the degree of heterogeneity of machines and tasks:

the time to compute one product of task T i on machine M u may be identical for each task/machine (w), depend only on the task (w i ) or the machine (w u ), or be fully general (w iu ).

IV. COMPLEXITY RESULTS

Complexity results are classified depending on the mapping rules. We start with one-to-one mappings, then we focus on specialized and general ones. Finally, we compare one-to-one mappings with general and specialized ones.

A. Complexity of one-to-one mappings

Theorem 1. Given an application and a set of machines, finding the one-to-one mapping which maximizes the throughput can be done in polynomial time.

Proof: We can compute the average number of products x i needed to output one product out of task T i , as explained in Section III-A. Since the mapping is required to be one-toone, we create a bipartite graph with one node per task on one side, one node per machine on the other side. The cost of an edge from task T i to machine M u is then set to x i w i,u , which corresponds to the period of machine M u if task T i is assigned to this machine. Since the period of the mapping is the maximum of the periods of each machine, the problem is equivalent to a maximum weight matching in bipartite graphs, which can be found in polynomial time, for instance using the Hungarian method [START_REF] Cormen | Introduction to Algorithms[END_REF], [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF].

B. Complexity of specialized and general mappings

Theorem 2. Finding the optimal specialized or general mapping is NP-hard, even with constant processing costs w.

Proof: We consider the following decision problems: given a period K, is there a general/specialized mapping whose period does not exceed K? The problem is obviously in NP: given a period and a mapping, it is easy to check in polynomial time whether it is valid or not. The NP-completeness is obtained by reduction from 2-PARTITION [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Let I 1 be an instance of 2-PARTITION: given a set {a 1 , ..., a n } of n integers, does it exist a subset I such that i∈I a i = 1 2 1≤j≤n a j ? We construct the instance I 2 with n tasks ordered as a linear chain, 2 machines, and w = 1. All tasks are of the same type, thus there is no difference between general and specialized mappings, and both problems are tackled simultaneously. We assume that a 1 ≥ a 2 ≥ ... ≥ a n (the sort can be done in polynomial time), and then we fix:

• f n = an-1 an ; ∀1 ≤ i ≤ n -1, f i = ai-ai+1 ai ; • K = 1 2 1≤j≤n a j ; First we prove by induction that x i = a i for 1 ≤ i ≤ n. For i = n, we have x n = 1 × b n /r n = a n . For 1 ≤ i ≤ n -1, if x j = a j for j > i, then x i = x i+1 ×b i /r i = a i+1 ×a i /a i+1 = a i .
The size of I 2 is polynomial in the size of I 1 . Suppose that I 1 has a solution I. We construct the allocation function a such that: ∀i, a(i) = 1 ⇐⇒ i ∈ I. Since w = 1 and x i = a i for all i, the period of the mapping is thus P = max{ i∈I a i , i / ∈I a i }, that means P = K and I 2 has a solution.

Suppose now that I 2 has a solution. Let I = {a i |a(i) = 1}. By hypothesis, we have i∈I a i ≤ K and i / ∈I a i = 2K -i∈I a i ≤ K. We can conclude that i∈I a i = 1 2 1≤j≤n a j . Then, I 1 has a solution. This concludes the proof.

C. Comparison of mapping rules

In this section, we compare the three mapping strategies, namely one-to-one, specialized and general mappings. The first thing that we want to point out is that one-to-one mappings are a particular case of specialized mappings, which are themselves a particular case of general mapping. Thus, an optimal one-to-one mapping cannot be better than an optimal specialized mapping, which itself cannot be better than a general mapping.

Why not restrict to general mappings? The problem of these general mappings is that they are not realistic, because if a machine is processing tasks of different types, one needs to reconfigure the machine between operations, and this cost is unaffordable in most micro-factories. Thus, in the following, an emphasis is given to one-to-one and specialized mappings.

Since the optimal one-to-one mapping can be found in polynomial time (see Theorem 1), why not restrict to such mappings? The problem arises when m ≤ n, i.e., there are many tasks and not so many machines. In such cases, it is mandatory to execute several tasks on the same machine.

When there are enough machines (m ≥ n), one-to-one allocations are a good way to tackle the problem (see the following theorem), but they can be arbitrarily worse than a specialized allocation in the general case. Theorem 3. If m ≥ n, and for problems with w i (w i,u = w i for 1 ≤ u ≤ m), there is an optimal specialized or general mapping which performs a one-to-one allocation of tasks onto machines. In other words, one-to-one mappings are dominant in this case.

Proof: The proof is simply done by an exchange argument. Suppose that there is an optimal mapping which is not a one-to-one mapping. For instance, tasks T i and T j are mapped onto the same machine, M u . Since m ≥ n, there is at least one free machine, say M v , and the period can be decreased from x i w i + x j w j to max(x i w i , x j w j ) if task T j is assigned to M v instead of M u . This concludes the proof.

Note that this is not true if the completion time also depends on the processor. For instance, consider a problem with w u (w i,u = w u for 1 ≤ i ≤ n) in which there is one machine with w 1 = 1 and a second one with w 2 = K, where K is arbitrary large. If the application consists in two tasks of same type with no failures, then the optimal throughput can be obtained by mapping both tasks onto machine 1, resulting in a period of 1 + 1 = 2, while a one-to-one mapping must use machine 2 and thus its period cannot be better than K, which can be arbitrarily greater than 2.

V. HEURISTICS

As explained in Section IV-C, general mappings are not realistic in the context of micro-factories, because of the unaffordable reconfiguration costs. When the number m of machines is greater than the number p of task types, it is always possible to find a specialized mapping, since each machine is able to process all the tasks of a same type. The key point is thus to find m (or less) groups of tasks of the same type to be assigned to the m machines of the platform. The best solution may be a one-to-one mapping (cases in which such mappings are optimal, see Theorem 3).

As shown before, finding the optimal specialized mapping is NP-hard (see Theorem 2). Thus, we present in the following five heuristics that returns a mapping, by grouping tasks of same type onto machines.

H1: Random heuristic -The m groups are made by using a random assignment function. We randomly choose p tasks, such that t(i) = t(i ′ ) for all chosen tasks T i and T i ′ , and we randomly assign them to p machines of the platform (recall that p is the number of task types). Then we can randomly assign the rest of the tasks T j either on a machine which is free or already specialized to the same task type t(j). H2: Task group heuristic -p groups are made by assigning all the tasks of the same type to the same group. While the number of groups is less than m, the number of machines, the group which consists in the larger number of tasks is divided into two groups to balance the workload. Then, an assignment of groups to machines is performed using the oneto-one mapping algorithm. H3: Binary search heuristic 1 -This heuristic aims at optimizing the potential of the machines, i.e., the goal is to assign to each machine a set of tasks for which it is efficient. Thus, we start by sorting, for each machine M u , the set of w i,u , for 1 ≤ i ≤ n, in ascending order. Then, rank i,u represents the rank of T i in the ordered set for M u .

The heuristic performs a binary search on the period between 0 (best case) and the time required to perform sequentially all the tasks on a machine (worst case). For each value of the search, all tasks are assigned greedily (from T 1 to T n ) to machines. For task T i , we try to assign it to a machine such that rank i,u is minimum. If the rank equals one, this means that the potential of M u for this task is optimal. In case of equality (several machines of identical rank for T i ), machines are sorted by nondecreasing values of w i,u . Of course, the assignment can be done only if the machine was not already specialized to a type which is different from t(i), and if the fixed period is not exceeded. Otherwise we try to assign T i to the next machine, according to their priority order for this task. If no machine is able to process T i , then no assignment is found and we try a larger period. If all tasks can be correctly assigned, we try a smaller period. H4: Binary search heuristic 2 -Similarly to the previous heuristic, H4 performs a binary search on the period. However, the greedy assignment procedure is different. For each task T i , the heuristic tries to assign it to the machine M u which minimizes w i,u , if the machine is not already specialized to a type which is different from t(i), and the period is not exceeded. No ranking is computed, the idea is to forget about the potential of the machines, but simply try to execute each task as fast as possible, thus using efficient machines. H5: Binary search heuristic 3 -This heuristic is the same as H4 except that, for the assignment, the machines are sorted by their heterogeneity level in descending order. The idea is to preserve homogeneous machines for the last tasks. The heterogeneity level of M u is computed as the standard deviation of its w i,u values. Each task is assigned to the most heterogeneous machine capable of handling it. Note that for this heuristic, slow machines may be used instead of powerful ones, because of their heterogeneity level.

The next section presents experimental results that compare these heuristics.

VI. EXPERIMENTS

In this section, we compare together the 5 heuristics that give sub-optimal solutions to the specialized mapping problem with w i,u . The performance of each heuristic is measured by its period in ms (see Section III-A). Only the most significant results are presented in this paper. The full set of experiments is available in [START_REF] Benoit | Throughput optimization for micro-factories subject to failures[END_REF].

Recall that m is the number of machines, p the number of types, and n the number of tasks. Each point in the figures is an average value of 50 simulations where the w i,u are randomly chosen between 100 and 1000 ms, for 1 ≤ i ≤ n and 1 ≤ u ≤ m. Similarly, failure rates f i (1 ≤ i ≤ n) are randomly chosen between 0.5 and 2 % (i.e., 1/200 and 1/50).

A. First set of experiments: m and p fixed

In the first set of experiments, m and p are fixed, and we plot the period for each heuristic as a function of the number of tasks n. Figure 6 shows that the random heuristic H1 returns very large periods, compared to the 4 other heuristics. This remains true for all experiments: H1 shows very poor performance. Thus H1 is removed from the curves for readability.

To analyze the impact of the platform heterogeneity ratio, the same experiments (m = 10 and p = 5) have been run with a smaller duration interval (w i,u between 100 and 200 ms) in order to simulate less heterogeneous platforms. Results of these simulations are presented in Figures 7 and8. In both results, H3 is clearly the best and the performances of H2, H4 and H5 are equivalent. These two results are slightly alike except for the scale. We can though deduce that the heterogeneity ratio of the platform has little influence concerning the comparison of these heuristics. In the following, we thus present results only in the heterogeneous setting with w i,u varying between 100 and 1000.

Figures 9 and 10 show that the performance of H2 is very similar to that of H4 and H5 when the difference between the number of machines (respectively 20 and 100) and the number of types (respectively 18 and 90) is small. Indeed, H2 tries to use all the machines and thus it splits the groups until it has as many groups as machines. In these experiments, the way the groups are split does not influence the performance so much because only 2 (respectively 10) extra groups will be created. H3 is clearly the best heuristic in such a case. With H3, we optimize the potential of each machine so we make the best use of a given platform.

On the contrary, when the number of machines m is much greater than the number of types p, the performance of H2 decreases, as we can see in Figures 11 and12. In these experiments, H3 and H4 are both reaching a satisfying period, while H5 is slightly less good. Heterogeneous setting: 100 < wi,u < 1000. Experiment with fixed m and n.

B. Second set of experiments: m and n fixed

In the last experiment (Figure 13), we fix m = n = 100, and we plot the period as a function of the number of types p. Moreover, we randomly chose values w i,u such that the duration of a task is machine-independent (w i,u = w i,u ′ for 1 ≤ u, u ′ ≤ m). In this case, we know that there is an optimal one-to-one mapping (see Theorem 3) and we are able to compute it (see Theorem 1). Thus we are able to assess the absolute performance of the heuristics by computing the optimal period, obtained with a one-to-one mapping (Hungarian algorithm).

C. Summary

The results show that H3 and H4 return a mapping whose period is very close to the optimal, which is a very good result. Indeed, we expect this behavior to be similar in a more heterogeneous context, thus assessing the performance of our heuristics. H5 is always returning greater period, thus showing that faster machines must be considered first to find a good mapping (recall that H5 selects machines by heterogeneity level instead of speed, and may use slower machines).

VII. CONCLUSION

In this paper, we have investigated a throughput optimization problem in the context of micro-factories subject to failures. The problem consists in assigning tasks to machines, either performing a one-to-one mapping (one task per machine), or a specialized mapping (several tasks of the same type per machine), or a general mapping. On the theoretical side, we proved that the optimal one-to-one mapping can be found in polynomial time, while the problem becomes NP-hard for specialized and general mappings. Since general mappings are not usable in practice because of reconfiguration costs, we focused on specialized mappings and proposed several polynomial heuristics to solve the problem. Experimental results suggest that some heuristics return mappings with a throughput close to the optimal, and the sophisticated heuristics return results much better than a random mapping.

As future work, we plan to investigate other mapping rules, as for instance the mapping of one task onto several machines. In such a case, different instances of the task would be handled by different machines. This would allow to obtain a better throughput when a task is time consuming (bottleneck). Also, it would be interesting to consider a failure model in which the failure rate is also machine-dependent (rates f i,u depending on both the task T i and the machine M u on which the task is mapped). Finally, other objective functions could be considered, as for instance the total time required to obtain a given number of products, or the average time needed to output one product.

Figure 1 .

 1 Figure 1. Example of application.

Figure 2 .

 2 Figure 2. Example of a linear chain application with failure.

Figure 4 .

 4 Figure 4. One machine can do different tasks if they are of the same type.Here the type of tasks are the following : t(1)=t(3)=t(5)=1 and t(2)=t(4)=2.

Figure 5 .

 5 Figure 5. One machine can handle any task. Here the type of tasks are the following : t(1)=t(3)=1, t(2)=t(4)=2 and t(5) = 3.

Figure 6 .Figure 7 .

 67 Figure 6. m = 10, p = 5.Behavior of H1.

Figure 8 . m = 10 , p = 5 .Figure 9 .Figure 10 .Figure 11 .Figure 12 .Figure 13

 8105910111213 Figure 8. m = 10, p = 5.Homogeneous setting: 100 < wi,u < 200.

Table I VALUES

 I OF x i AND x i FOR THE EXAMPLE OF FIGURE 2, WITH xout = 1.

	Task number	1	2	3	4


J.-B Aupet
email: [jbaupet@lifc.univ-fcomte.fr

R Kassab
email: rkassab@lifc.univ-fcomte.fr

J.-C Lapayre
email: jclapayre]@lifc.univ-fcomte.fr

WAVA: a New Web Service for Automatic Video Data Flow Adaptation in Heterogeneous Collaborative Environments

Keywords: Adaptation, Asynchronous, Collaborative Environments, Multimedia, Real-time, Streaming, Synchronous, Terminal, Video, Web service

The progressive needs of video streaming for different applications in varied domains have created a new set of heterogeneous environments especially in Virtual Collaborative Environments. In order to get the best performance of such environments, video streaming has to be adapted to the different parameters that characterize these environments, namely: bandwidth, CPU, GPU, screen resolution, etc. In this paper, we define a new Web Service, named Wava (Web Service for Automatic Video Data Flows Adaptation). Wava allows multimedia platforms and collaborative application servers to adjust the adaptation at two levels: at the static level during initialization and at the dynamic level according to the variation of the environment.

Introduction

Multimedia environments providing access to media contents from heterogeneous environments are commonly called UMA "Universal Multimedia Access". In heterogeneous environments systems clients differ in their hardware and software capabilities and limitations. These differences might be found on the communication level, for example the variation of bandwidth from 50 kb to 20 Mb. Variations may also involve the terminal specifications e.g. CPU, memory, display capabilities and GPU encoding-decoding capacities. Therefore when we talk about video adaptation systems we should take all conditions into account. By heterogeneous applications we mean the variation of usage, entertainment or work (for example tele-medicine) and programming languages. These applications are distinguished beetween two types: synchronous and asynchronous applications. In order to solve these differences, and because we mostly work on the Internet, XML files and Web Services are involved.

In the first section of this paper we present the state of the art in this domain. In the following section, we define our new Web Service Wava (Web Service for Automatic Video Adaptation) which allows platforms to adapt the stream at two levels: at the static level (during initialization) and at the dynamic level according to the variation of the environment, and its performance. The last section presents the conclusion and future work.

State of the Art

The development of multimedia applications puts in evidence the necessity of new research. The arrival of HD video by the Internet and the increase of multiple formats of video generate a lot of studies in each part of this domain. In this section, we focus our study on adapatative systems and especially on UMA (Universal Media Access) systems based (Wang 2007).

Adaptation with the UMA Model

The General architecture of the UMA system consists of four main components described in (Wang 2007) and illustrated in the figure 1:

Multimedia server

Research which focuses on the adaptation aspect performed by the multimedia server [START_REF] Leopold | Quality Controlled Temporal Video Adaptation[END_REF]) considers the server is responsible of coding and forming the high quality Scalable Video bitstream [START_REF] Ruiz | Improving User-Perceived QoS in Mobile and Wireless IP Networks Using Real-Time Adaptative Multimedia Applications[END_REF]. That means that it can be scaled (adapted) to be in adequacy with specifications. In addition, the server can adapt the video. However, the adaptation process consumes larger amount of calculation power than a real time system can actually bear. In order to further adapt the video bitstream in a convenient way, the middleware has to decode and then to recode the bitstream to the adapted format. Therefore, the server transmits specific bitstream description helping the middleware to avoid the decoding-recoding step. The server role in adaptation system can be summarized to, forming scalable bitstream [START_REF] Ruiz | Improving User-Perceived QoS in Mobile and Wireless IP Networks Using Real-Time Adaptative Multimedia Applications[END_REF], performing adaptation, and transmitting video information with the SVC (figure 2).

Middleware.

The main purpose of middleware is the adaptation process, it receives the scalable bitstream, operates the adaptation and then sends the scaled bitstream to the terminal. In real time systems, studies are concentrated on middleware and proposed adaptation solutions like UF (Utility Function) [START_REF][END_REF], (Kim 2005), (Wang 2007) or gBSD (generic Bitstream Synt. Desc.) (Iqbal 2007). The main factor used in the adaptation process is the constraints (Feedback) received from the terminal. The feedback consists of terminal-transmitted information necessary for helping the middleware in the adaptation process to choose the right video bitstream.

Communication system

The revolution of communication systems in the last decade has created various media, paved the way for real-time Collaborative systems. From this viewpoint, it is very important to analyze the communication mediums for the adaptation. Terminals can use a medium to communicate and pass to an other. This step is the main reason for performing the adaptation. For example, a mobile client could change his Internet connection from GPRS to Wi-Fi (Ruiz 2002). If the system allows a client to notify the system of these changes, it is called an adaptable system. If the system is able to notify itself about the changes of the environment, it is called an adaptive system.

Terminal

In addition to decoding the video, terminals have one of the most important tasks in adaptation systems that is creating feedback. Terminal application has to calculate the feedback and send it to the middleware or the server, which in turn should make the right decision. Many factors can influence the feedback, such as computation capacity of the terminal or free resources to store video and others. The most important resources to take into account are: Bandwidth and its variation, the available RAM and Hard disk capacity to store buffered video, the CPU capacity and load, ang GPU Capacity for Displayable Resolution and codecs supported Software.

Feedback is the major factor to choose the adapted video, many techniques are used to calculate it: produced as a mark from the terminal, created either by testing the hardware of a terminal or by using mathematical methods such as PSNR (Wang 2004) or VQA (Zhai 2008) (see part 2.4).

Use of adaptation in video applications

Collaborative environments are used more and more due to the increase of data transmission capacity. Now a user can easily be noticed by chat or voice-chat, and more and more by video-conferencing. Video applications vary from entertainment purposes like watching films on VOD and channels of television but also for medical applications, such as video conferencing for Telediagnosis (Jung 2005), e-learning. . . These applications are classified in two main categories, real time (synchronous) video applications and stored video (asynchronous) applications.

Stored video applications Thess kind of applications are easier to perform, there is no need to consider the time factor in all parts of the system. A video is available on the server and the application has to adapt it with terminal capabilities.

Real time applications These applications need special solutions to ensure the time contract and quality of service are respected. Collaborative applications must ensure synchronous data exchange and consistency. The obvious the goal of the middleware is: saving time for the adaptation process.

Multidimensional video adaptation

In terms of performance, the adaptation process has three main factors or three main dimensions which are: time, resolution, and quality. And they are referred as: temporal, spatial and SNR, respectively:

-Temporal [START_REF] Kim | An optimal framework of video adaptation and its application to rate adaptation transcoding[END_REF]) and [START_REF] Kropfberger | Quality Variations of Different Priority-based Temporal Video Adaptation Algorithms[END_REF]

PSNR and VQA in depth

PSNR: Peak Signal to Noise Ratio is a method to calculate the noise ratio of a signal depending on the measurement of MSE (Mean Squared error) (Wang 2004). However, PSNR does not compute the real performance of a video stream. For this reason, it is not applicable to measure the performance of the multidimensional video adaptation process. Furthermore, it has been proven that there can be different videos with different qualities that have the same PSNR. These experiments was correlated by HVS (Human Visual System) in (Zhai 2008), which depends on human notice for giving the result. HVS is also called perceptually VQA.

VQA: Video Quality Assessment is a value that is calculated in subjective(HVS) or objective (mathematical) manner (Zhai 2008). In this paper, we focus on the objective method in calculating VQA, because it can be calculated mathematically. The differences between these VQA types are the amount of video features sent with the adapted video.

A New Web Service for Automatic Video Adaptation: WAVA

When users have to communicate, they do not have to be impacted by the weaknesses of the others. Clients does not feel the latency of the adaptation process. But hey can not determine themselves the optimal feedback all the time. With regard to this, we propose a solution that automatically and periodically detects the changes of the environment without user's interaction. In order to provide transparent processing, enhance the performance and facilitate the usage of the system, we propose the following architecture.

WAVA Architecture

In the beginning of our work, we used a client-server JAVA application, where the client sends his mark manually and the server reacts according to this mark. We automatized this process by making a simple detection of the load of the CPU and the network congestion. In another experience, we created a client application that reads the terminal performances (CPU frequency and load, Screen resolution, network bandwidth) and sends the corresponding mark to the server. The latency generated by the calculation did not allow an efficient and satisfactory work. Furthermore in a collaborative environments, heterogeneous client can connect to the system. The best solution to resolve this problem is the use of Web Services. Because of their portability and independence from programming languages, Web Services can handle any kind of platforms. Furthermore, we save the feedback calculation time of the terminal. When the client chooses a video, the collaborative system automatically detects terminals performances with the WAVA marks and sends back adapted videos. So we propose a new Web Service design that detects each terminal property and calculates the related mark. Depending on this mark, the server decides whether it sends a high or low quality video matching the terminal's exigences.

The quality is determined by the decrease of the resolution and frame rate. It is possible to integrate this system in a web page with a script that reads the terminal performance and sends an XML file in a Virtual Awareness Card format like in (Aupet 2009) to the WAVA web service. Subsequently WAVA uses an algorithm to produce the corresponding mark. At the media server we have two choices. The first is to make a video pool that contains all the videos in all the codec formats, which match with all the marks: the same video will be repeated for all formats. The second choice is to use one video source that would be converted in real-time either by the server or by the middleware to adapt it to the marks received from the Web Service. We have chosen the second solution for the video conferences, where we have the camera as the only source. So we directly adapt the stream to match the feedback.

WAVA Processing

The Mark represents the terminal performance. We classify CPUs, graphic cards, resolutions, and bandwidth into groups. Each group contains the individuals that perform in an identical manner in terms of video streaming. Then, a mark is attached to each group. We apply this design by using a database which stores devices attaching to their marks. The database is automatically filled with the unknown devices of terminal by giving a mark calculated with the average mark of the terminal performance. We distinguish two categories of mark: the static mark that does not change during a session, call them Global Marks (Mg).

This mark refers to CPU (Mcpu), resolution (Mres), and graphic card (Mgrph), and obviously remain unchangeable during one session. Mg is calculated as the minimum value of Mcpu, Mres and Mgrph. The second category of mark is the dynamic mark that refers to the bandwidth (Mbw) that changes during the video streaming session. In order to get the final mark (M), we calculate the minimum value between Mg and Mbw. We always use the smallest value because we need the system work optimally: we adapt our collaborative system to the weakest value. After calculating the mark, WAVA sends it and saves the global mark. Periodically WAVA receives the bandwidth information of users, calculate the new Mbw, then calculates the mark which remains the minimum between the Mg and the updated Mbw.

WAVA Performance

In order to test our system, we make a pool of videos in different formats to test several terminals. With these videos we have tested the proportion of packet loss during the streaming transfer. We used the Mpeg-H.264 codec to produce these videos in five different qualities. We changed the resolution and frame rate. Results are in the figure 6a.

Periodically the bandwidth mark is sent and the new adaptation mark is updated to provide the best video quality that fits the real conditions of the user. We describe a scenario-based test (fig. 7) to show the decrease of packets loss by using WAVA Web Service. We can show the technical performance of WAVA in figure 6b. In facts, when the adaptation is well done, participants can work efficiently.

Conclusion and future work

In this paper, we showed that video adaptation is one of the main matters of multimedia development in heterogeneous collaborative environments. Therefore researche has been conducted in this domain which focused on the UMA model. We proposed a new Web Service based system for automatic video adaptation (WAVA). The Web Service is used to calculate the best adaptation that matches the system capabilities, for both, static parameters (during initialization) and dynamic parameters depending on the variation of the environment. We implemented and tested our system, and we exposed the performance results. Wava significantly improves the use of mobile terminals for collaborative work. Our future work focuses on how to test Wava not only with a mark for each terminal, but also for a whole collaborative environment. We imagine a process to adapt media during a session of medical tele-diagnosis between remote mobile practitioners: we are working on new distributed algorithms for shared marks calculation and optimising adaptation to each participant.

Fig. 1 .

 1 Fig. 1. UMA Adaptation System Fig. 2. System Chart

  ): Frame rate (from 1 up to 30 fps fig. 3a.) -Spatial: Screen and GPU Resolution capabilities (figure 3b.) -SNR: Signal-to-Noise Ratio (Low, mid, high): Extended for video by PSNR and VQA in depth.

Fig. 3 .

 3 Fig. 3. Bandwidth consumption depending on: a. Frame rate and b. Resolution

Fig. 4 .

 4 Fig. 4. WAVA Processing

Fig. 5 .

 5 Fig. 5. Wava Algorithm

Fig. 6 .

 6 Fig. 6. a.Packets loss -b.Wava Performance

Acknowledgements

The authors thank the European Community (European FEDER) for financing this work by the InterRegIV project SERVASTIC : Teleneurology in Mobile Environments.


Sékou Diakité

Loris Marchal

Jean-Marc Nicod

Laurent Philippe

Steady-State for Batches of Identical Task Graphs

In this paper, we focus on the problem of scheduling batches of identical task graphs on a heterogeneous platform, when the task graph consists in a tree. We rely on steady-state scheduling, and aim at reaching the optimal throughput of the system. Contrarily to previous studies, we concentrate upon the scheduling of batches of limited size. We try to reduce the processing time of each instance, thus making steady-state scheduling applicable to smaller batches. The problem is proven NP-complete, and a mixed integer program is presented to solve it. Then, different solutions, using steady-state scheduling or not, are evaluated through comprehensive simulations.

Introduction

Computing Grids gather large-scale distributed and heterogeneous resources, and make them available to large communities of users [START_REF]The Grid 2: Blueprint for a New Computing Infrastructure[END_REF]. Such platforms enable large applications from various scientific fields to be deployed on large numbers of resources. These applications come from domains such as high-energy physics [START_REF] Chervenak | The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets[END_REF], bioinformatics [START_REF] Oinn | Taverna: a tool for the composition and enactment of bioinformatics workflows[END_REF], medical image processing [START_REF] Germain | Gridenabling medical image analysis[END_REF], etc. Distributing an application on such a platform is a complex duty. As far as performance is concerned, we have to take into account the computing requirements of each task, the communication volume of each data transfer, as well as the platform heterogeneity: the processing resources are intrinsically heterogeneous, and run different systems and middlewares; the communication links are heterogeneous as well, due to their various bandwidths and congestion status.

Applications are usually described by a (directed) graph of tasks. The nodes of this graph represent the computing tasks, while the edges between nodes stand for the dependencies between these tasks, which are usually materialized by files: a task produces a file which is necessary for the processing of some other task. In this paper we consider Grid jobs made of a collection of input data sets that must all be processed by the same application. We thus have several instances of the same task graph to schedule. Such a situation arises when the same computation must be performed on independent data [START_REF] Lee | Exploring protein fold space by secondary structure prediction using data distribution method on grid platform[END_REF] or independent parameter sets [START_REF] Pitt-Francis | Enabling computer models of the heart for highperformance computers and the grid[END_REF]. Moreover, the targeted applications we plan to schedule do not include any replication phases in the process. Hence, DAGs considered in this paper have no fork nodes, and consists in chains or in-trees. This corresponds to application like medical [START_REF] Ludtke | EMAN: Semiautomated Software for High-Resolution Single-Particle Reconstructions[END_REF] or media [START_REF] Peng | Optimization of media processing workflows with adaptive operator behaviors[END_REF] image processing workflows.

The problem consists in finding a schedule for these task trees which minimizes the overall processing time, or makespan. This problem is known to be NP-hard. To overcome this issue, some of us proposed to use steady-state scheduling [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]. In steady-state scheduling, we assume that instances to be performed are so numerous that after some initialization phase, the flow of computation will become steady in the platform. By characterizing resource activities in this steady state, we are able to derive a periodic schedule that maximizes the throughput of the system, that is the number of task graph instances completed within one time unit. As for makespan minimization, this schedule is asymptotically optimal. This means that for a very large number of instances to process, the initialization and clean-up phases that wrap the steady-state phase become negligible, and the makespan of the steady-state schedule becomes close to the optimal. However, when the number of instances is important but bounded, existing steady-state approaches do not give optimal performances -initialization and clean-up phases cannot be neglected when scheduling a finite number of instances -and lead to a huge number of ongoing instances. In this paper, we propose an adaptation of the steady-state scheduling that allows to use it on batches of jobs of finite size, without compromising its asymptotically optimality.

The rest of the paper is organized as follows. In Section 2 we give a short reminder on the steady-state techniques and their drawbacks. In Section 3 we formalize the problem we are dealing with, and asses its complexity. In Section 4, we propose an exact solution to this problem. Simulations showing its impact are reported in Section 5.

2 Steady-state scheduling for task graphs

Platform and application model

In this section, we detail the model used in the following study. First, we denote by G P = (V P , E P ) the undirected graph representing the platform, where V P = {P 1 , . . . , P p } is the set of all processors. The edges of E P represent the communication links between these processors. The time needed to send a unit-size message between processors P i and P j is denoted by c i,j . We use a bidirectional one-port model: if processor P i starts sending a message of size S to processor P j at time t, then P i cannot send any other message, and P j cannot receive any other message, until time t + S × c i,j .

The application is represented by a directed acyclic graph (DAG) G A = (V A , E A ), where V A = {T 1 , . . . , T n } is the set of tasks, and E A represents the dependencies between these tasks, that is, F k,l = (T k , T l ) ∈ E A is the file produced by task T k and consumed by task T l . The dependency file F k,l has size data k,l . We use an unrelated computation model: computation task T k needs a time w i,k to be entirely processed by processor P i .

We assume that we have a large number of similar task graphs to compute. Each instance is described by the same task graph G A , but has a different input data from the others. This corresponds to the case when the same computation has to be performed on different input data sets.

Principle

In this section, we briefly recall steady-state techniques and their use for task graph scheduling. The steady-state approach has been pioneered by Bertsimas and Gamarnik [START_REF] Bertsimas | Asymptotically optimal algorithms for job shop scheduling and packet routing[END_REF].

The present study is based on a steady-state approach for scheduling collections of identical task graphs proposed in [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]. The steady state is characterized using activities variables: α k i represent the average number of tasks T k processed by processor P i within one time unit in steady state. We similarly define activities for data transfers: β k,l i,j represent the average number of files F k,l sent by P i to P j within one time unit in steady state.

By focusing in the steady state, we can write constraints on these activity variables, due to speed limitation of the processors and links. We also write "conservation laws" to state that files F k,l have to be produced by tasks T k and are necessary to the processing of tasks T l . We obtain a set of constraints that totally describe a valid steady-state schedule. We add the objective of maximizing the throughput, that is the overall number of DAGs processed by time unit, to get a linear program. Solving this linear program over the rational numbers allows us to compute the optimal steady-state throughput.

Then, from an optimal solution of this linear program, we construct a periodic schedule that achieves this optimal throughput. The construction of this schedule is complex, especially for handling communications, and we refer the interesting reader to [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF] for a detailed description. In the solution of linear program, the average number of tasks (or files) processed (or transfered) in a time unit may be rational. However, we cannot split the processing of a task, or the transfer of a file, into several pieces. Thus, we compute the lowest common multiple L of all denominators of these quantities. We then multiply all quantities by L, to get a period where every quantities of tasks or files is integer. A period describes the activity of each processor (how many task of each types is performed) and of each link: communications are assembled into groups that can be scheduled simultaneously without violating the one-port model constraints. In the following, we will consider these communications groups as one special task, assigned to a fictitious processor P p+1 ; a dependency between a task T and a file F is naturally transformed into a dependency between T and the special task representing the group of communication which contains the file transfer F .

Platform graph

P 1 P 3 P 2 F 1,2 T 2 T 1 Task graph A 1 A 2 Allocations T 2 T 1 T 2 T 1 Figure 1. Handling dependencies
Although bounded, the length L of the period may be large. The steady-state schedule is made of a pipelined succession of periods, as described in Figure 1. Dependencies between files are taken into account when reconstructing the schedule: a file F k,l produced by T k during period 1 will be transfered to another processor during period 2 and then used by task T l during period 3. Figure 1 describes a steady-state schedule obtained for a simple task graph: in a period both processors P 1 and P 2 process a task T 1 , while P 3 processes two tasks T 2 , achieving a throughput of 2 instances every L time units. In the periodic schedule, each task or file transfer is provided with its instance number in superscript, and dependencies are materialized with arrows for instances 2n and 2n + 1.

Once the periodic schedule is built, it can be used to process any number of tasks. A final schedule consists in three phases:

1. an initialization phases, where all the preliminary results needed to treat a period are pre-computed; 2. the steady-state phase, composed of several periods; 3. a clean-up phase, where all remaining tasks are processed so that all instances are completed.

Shortcomings

We have seen that the length of the period of the steady-state schedule may be quite large, and that a large number of periods may be needed to process a single task graph in steady state. This induces a number of drawbacks:

Long latency. For a given task graph, the time between the processing of the first task and the last task, also called latency, may be large since several periods are necessary to process the whole instance. This may be a drawbacks for interactive applications. Large buffers. Since the processing time of each instance is large, a large number of instances must be started before the first one is completely processed. Thus, at every time step, a large number of ongoing jobs have to be stored in the system, and the platform must provide large buffers to handle all temporary data. Long initialization and clean-up phases. Since the length of the period is large and contains many task graph instances, the number of tasks that must be processed before entering steady state is large. Thus, the initialization phase will be long. Similarly, after the steady-state phase, many tasks remain to be processed to complete the schedule, leading to a long clean-up phase. As these phases are done using some heuristic scheduling algorithms, their execution time might be far from the optimal, leading to poor performance of the overall schedule.

In spite of these drawbacks, we have shown in [START_REF] Diakité | Comparison of batch scheduling for identical multitasks jobs on heterogeneous platforms[END_REF] that steady-state scheduling is of practical interest as soon as the number of task graph instances is large enough. In this study, we aim at reducing this threshold, that is to obtain a steady-state schedule which is also interesting for small batches of task graphs.

One could envision two solutions to overcome these drawbacks: (i) decrease the length of the period, or (ii) decrease the number of periods necessary to process one instance. However, there is limited hope that the first solution could be implemented if we want to reach the optimal throughput: the length of the period directly follows from the solution of the linear program. In this study, we focus on the second one, that is on reducing the latency of the processing of every instances.

3 Problem formulation and complexity

Motivation

We aim at scheduling identical DAGs (in-trees) on an heterogeneous platform with unrelated machines. Our typical workload consists in a few hundreds of DAGs. When the period of the steady-state is small compared to the length of the steady-state phase, initialization and clean-up phases are short, and steady-state scheduling is a very good option. When the period obtained is large compared to the steady-state phase, it is questionable to use steady-state as initialization and clean-up may render the advantage of steady-state unprofitable. The overall metric is the time needed to process all the DAGs (total makespan). By using steady-state scheduling, we focus on throughput maximization. It is possible to get a solution with optimal throughput [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]; our goal is to refine this solution to make it profitable for small batches of DAGs.

The solution proposed in [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF] consists in a periodic schedule. The length of the period of this schedule is a key parameter for our objective. However, since we want to keep an optimal throughput, we do not try to reduce this length, but we prohibit any increase in the period length, which would go against our final objective.

T 2n 1 T 2n+1 1 T 2n 2 Steady-state schedule F 2n 1,2 F 2n+1 1,2 T 2n+1 2 T 2n+2 1 T 2n+4 1 T 2n+3 1 T 2n+5 1 F 2n-2 1,2 F 2n-1 1,2 F 2n+2 1,2 F 2n+3 1,2 T 2n-2 2 T 2n-1 2 T 2n-3 2 T 2n-4 2 Figure 2.
A periodic schedule with inter-period and intra-period dependencies

We have seen that a large number of periods may be needed to completely process one instance. More precisely, after building the steady-state period, each dependency in the task graph can be satisfied within a period, or between two consecutive period, as illustrated in Figure 2. In this figure, we have taken the period of Figure 1, and we have modified its utilization of the schedule, so that one dependency can be satisfied within a period: in the new schedule, the results of file transfer F 1,2 can by used by task T 2 immediately, in the same period, instead of waiting for the next period. This is done by reorganizing the period: the "first" transfer F 1,2 of a period is now used to compute the "second" task T 2 . We say that F 1,2 → T 2 is an intra-period dependency, contrarily to other dependencies that are inter-period. Of course, this single modification has little impact on the total makespan, but if we could transform all inter-period dependencies into intra-period dependencies (or a large number), our objective would be greatly improved.

The number of inter-period dependencies, that is the dependencies which originate in one period and terminate in the following one, is an important factor. The number of periods needed to completely process an instance (and thus the latency) strongly depends on the number of such dependencies. As for the makespan, the number of instances that have to be started in the initialization phase, and finished in the clean-up phases is exactly the number of inter-period dependencies. Thus, reducing the number of such dependencies is an important goal in order to overcome the drawbacks of the original steady-state implementation. Note that in the original version of the steady-state schedule, the number of these dependencies is huge: all dependencies are inter-period dependencies.

In order to get a practical implementation of steady-state scheduling for bounded sets of task graphs, we choose to forget about direct makespan minimization. We start from a period with optimal throughput (computed as in [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]), and focus on reducing the number of period dependencies in the schedule.

Formalization of the problem

We start from the description of a steady-state period. A period consists in q instances of the task graph G A . The u th instance of task T k is denoted T u k . We call σ(P i ) the set of instances of tasks processed by processor P i . For sake of simplicity, we denote by

w u k the duration of T u k , that is w u k = w i,k , with T u k ∈ σ(P i ).

Dependencies between task instances naturally follows the edges of the task graph:

for each edge T k → T l ∈ E A , for all u = 1, . . . , q, we have a dependency T u k → T u l . The period is provided with a length L, which must not be smaller than the occupation time of any processor: T u k ∈σ(Pi) w u k ≤ L for all P i . The solution to our problem consists in starting times t (T u k ) for each instance of task T u k . We must ensure that two tasks scheduled on the same processor do not overlap:

∀P i , ∀T u k , T v l ∈ σ(P i ), with t (T u k ) = t (T v l ) , t (T u k ) ≤ t (T v l )) ⇒ t (T u k ) + w u k ≤ t (T v l ) (1)
The number of inter-period dependencies for a given solution can be easily computed. A dependency T u k → T u l is an intra-period dependency if and only if T u k finishes before the beginning of T u l , that is if

t (T u k ) + w u k ≤ t (T u l ) with T u l ∈ σ(P i ). (2)
Thus, inter-period dependencies are all dependencies that do not satisfy this criterion.

Complexity of the problem

In this section, we assess the complexity of the problem presented in the previous section, namely the ordering of the tasks on each processor, with the objective of minimizing the number of inter-period dependencies. We first define the decision problem associated to the minimization of the number of inter-period dependencies.

Definition 1 (INTER-PERIOD-DEP).

Given a period described by σ, consisting in q instances of a task graph G A (which is a tree), on p processors, with computation times given by w, and an integer bound B, is it possible to find starting times t (T u k ) for each task instance such that the resultant number of inter-period dependencies is not larger than B?

This problem is NP-complete. The proof of this result, based on a reduction from the 3-PARTITION problem, is available in the companion research report for details [START_REF] Diakité | Steady-state for batches of identical task graphs[END_REF].

Optimal algorithm with MIP formulation

In this section, we present a linear program to solve the problem presented in Section 3. This linear program makes use of both integer and rational variables, hence it is a Mixed Integer Program. Solving a MIP is NP-complete, however efficient solvers exists for this problem [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF], which makes it possible to solve small instances.

In the following, we assume that we have only one instance of the task graph in the period, for sake of readability. Furthermore, we denote by w j the processing time of T j on the processor which executes it. Our approach can be extended to an arbitrary number of instances, at the cost of using more indices.

For any pair of tasks (T j , T k ) executed on the same processor (that is such that T j , T k ∈ σ(P i ) for some P i ), we define a binary variable y j,k . We will ensure that y j,k = 1 if and only if T j is processed before T k .

We also add one binary variable e j,k for each dependency T j → T k . This binary variable expresses if the dependency is an intra-period dependency (e j,k = 1) or an inter-period dependency (e j,k = 0).

Finally, we use the starting time t j of each task T j as a variable. We now write constraints so that these variables describe a valid period.

-We ensure that the y variables correctly define the ordering of the t j 's:

∀P i , ∀T j , T k ∈ σ(P i ), t j -t k ≥ -y j,k × L (3)
y j,k + y k,j = 1 (4)
-We also check that a given dependency is an intra-period dependency if and only if e j,k = 1:

∀T j → T k , t k -(t j + w j ) ≥ (e j,k -1) × L (5)
-We make sure that no task is processed during the processing of task T j , that is during [t j , t j + w j ]:

∀P i , ∀T j , T k ∈ σ(P i ), t k -(t j + w j ) ≥ (y j,k -1) × L (6)
-Finally, we check that all tasks are processed within the period:

∀T j , t j + w j ≤ L (7)
Together with the objective of minimizing the number of inter-period dependencies (i.e., maximizing the number of intra-period dependencies), we get the following MIP: Maximize e j,k under the constraints (3), ( 4), ( 5), ( 6) and ( 7) [START_REF]The Grid 2: Blueprint for a New Computing Infrastructure[END_REF] We can prove that the previous linear program computes a valid schedule with a minimal number of inter-period dependencies (see the companion research report for details [START_REF] Diakité | Steady-state for batches of identical task graphs[END_REF]).

Experimental results

In this Section, we present experimental results that show how minimizing the interperiod dependencies improves the original steady-state algorithm. We compare four algorithms that schedule batches of identical jobs on a heterogeneous platform. The first algorithm is the original steady-state implementation and the second algorithm the steady-state implementation with the optimization using mixed integer programming to minimize the number of inter-period dependencies described above (called steady-state+MIP). The third algorithm is also a steady-state implementation with inter-period dependencies minimization, but we replace the MIP optimization with a simple greedy algorithm; we do not detail this algorithm, called steady-state+heuristic, but refer the interested reader to the extended research report [START_REF] Diakité | Steady-state for batches of identical task graphs[END_REF]. The fourth algorithm is a classical list-scheduling algorithm based on HEFT [START_REF] Topcuoglu | Task scheduling algorithms for heterogeneous processors[END_REF]: as soon as a task or a communication is freed of its dependencies, the algorithm schedules it on the resource that guarantees the Earliest Finish Time (EFT). The EFT evaluation depends on the load of the platform and takes both the computation time and the communication time into account. Note that in steady-state strategies, the initialization and clean-up phases are implemented using this list-scheduling technique.

Simulation settings

In the following, we report simulation results obtained with a simulator implemented above SimGrid and its MSG API [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF]. The experiences consist in the simulation of 245 platform/application scenarios for batches from 1 to 1000 jobs. The platforms are randomly generated; parameters allows platforms from 4 to 10 nodes. Each nodes can process a subset of the 10 different task types with a computing cost between 1 and 11 time units. Network links generation ensures that the platform graph is connected, links bandwidth are homogeneous. The applications are also randomly generated, generation parameters allows in-trees with 5 to 15 nodes. Nodes types are selected between the 10 different task types. Dependency generation ensures that the application graph is an in-tree, dependency file sizes vary from 1 to 2.

For some of the scenarios, large periods and large numbers of dependencies may arise and the optimal dependency reduction with the MIP becomes too costly to compute, even though an efficient MIP solver is used (CPLEX [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF]). In the following, we thus distinguish two cases: SIMPLE scenarios are the ones when we are able to solve the MIP (139 scenarios), and GENERAL scenarios gathers all cases, and we do not include MIP results (245 scenarios).

Number of inter-period dependencies

In the simulations, we count the number of inter-period dependencies that the different strategies (MIP or heuristic) are able to transform into intra-period dependencies. When we are able to solve the MIP, it suppresses 39% of the inter-period dependencies, whereas the heuristic is able to suppress only 29% to 30% of them (29% in all cases, and 30% in SIMPLE cases). This shows that both the MIP and the heuristic strategies achieve a good performance for our metric. As we have outlined in the introduction, this does not necessarily result into an improvement for the global behavior of the schedule. Thus, we also compare the performance of these strategies on other metrics, namely the obtained throughput and the number of running instances.

Scheduling efficiency

Figure 3(a) shows the performance of the four scheduling algorithms on a given scenario. The efficiency, that is the ratio of the optimal throughput, obtained by each algorithm is given for different batch sizes. The list-scheduling heuristic has a constant behavior, as soon as the size of the batch exceeds a few tens, whereas the performance of the steady-state strategies evolves with this size: the more jobs to schedule, the more efficient these strategies. With a very large size of batch, these strategies would all reach an efficiency of 100%, i.e., they would give the optimal steady-state throughput. In this study, we focus on batches with medium size. On this particular example, all steadystate strategies achieve 90% of the optimal throughput as soon as there are 300 jobs to schedule. Figures 4(a) and 4(b) display the proportion of scenarios where the algorithms reach 90% of the optimal throughput, depending on the size of the batch, both in the SIMPLE and GENERAL cases. We notice that the list-scheduling algorithm behavior does not depend on the batch size, and reaches a good performance (90% of the optimal throughput) only for 43% of the cases (in general). On the contrary, steady-state strategies give much better performance, reaching a good throughput in 60% of the cases for batches with more than 400 jobs. Here, we are interested in comparing the performance of the different steady-state strategies. We notice that the performance of steady-state+MIP and steady-state+heuristic is better than steady-state: for medium-size batches, the number of jobs needed to get a good performance is smaller than in the original steadystate algorithm. This gap is noticeable even if it is not very large. In the SIMPLE case, (Figure 4(a)), we are able to compare steady-state+MIP with steady-state+heuristic: although the MIP strategy always gives better results, the heuristic performs very well, and the gap between both strategies is not always noticeable. b) presents the evolution of the number of running job instances on a given platform/application scenario. At a given time t, a running instance is a job which has been started (some tasks have been processed), but is not terminated at time t. Thus, temporary data for this instance have to be stored in some buffers of the platform. This figure illustrates the typical behavior of the steady-state algorithms. During the initialization phase, the number of job instances grows: instances are started to prepare the next phase. During the steady-state phase, the number of job instances is roughly constant. Finally, in the termination phase, remaining instances are processed and the number of running instances drops to zero. One of the drawbacks of steady-state scheduling presented in Section 2.3 is illustrated here: compared to another approach like list-scheduling, it induces a large number of running instances (on this example, 54 instead of 8). This example also shows that reducing the number of inter-period dependencies reduces the number of running instances for steady-state scheduling: with the MIP optimization, we get a maximum of 29 running instances, and 31 with the heuristic. We compared the maximum number of running instances in steady-state for the optimized versions (MIP and heuristic) and the original one: on average, steady-state+MIP induces a decrease of 35% and steady-state+heuristic reaches a decrease between 22% and 26% (respectively in the GENERAL and SIMPLE cases). Thus, our optimization makes steady-state scheduling more practical as it reduces the size of the required buffers.

Running time of the scheduling algorithms

Figures 5(a) and 5(b) present the average time needed to compute the schedule of a batch depending on its size, in the SIMPLE and GENERAL cases. We first notice that the list-scheduling heuristic is extremely costly when the size of the batch is above a few hundreds. Its supra-linear behavior is due to the complexity of finding a ready task to schedule in a number of considered tasks that grows linearly in the size of the batch.

In the SIMPLE cases, the time needed to optimally solve the inter-period dependency minimization using the MIP is negligible, and the time needed to compute the periodic schedule is always below 2 seconds for all strategies. In the GENERAL cases, the period of the schedule is larger, and it induces more computation: initialization and termination phases are longer (and may increase with the size of the batch), thus the computation of their schedule takes some time. The optimization of the steady-state phase by the heuristic is also time-consuming. Anyway, the computation of the schedule with steady-state approaches never exceeds 20 seconds. In this study, we have presented an adaptation of steady-state scheduling techniques for scheduling batches of task graphs in practical conditions, that is when the size of the batch is limited. The optimization we propose consists in a better usage of the period of the steady-state schedule. Instead of directly targeting the minimization of the makespan, we choose to reduce the number of inter-period dependencies. This problem is NP-complete, which justifies a solution based on Mixed Integer Programming.

Our simulations show that this objective was relevant: when decreasing the number of inter-period dependencies, the throughput of the solution on medium-size batches is improved. Furthermore, the obtained solution requires less buffer space, since fewer instances are processed simultaneously, making the schedule even more practical. In future work, we plan to concentrate on small-size batches: since the optimal throughput is not reachable for these batches, it would be interesting to study non-conservative approaches, i.e., periodic schedules based on sub-optimal throughput, but which are more convenient to use thanks to their short period.

  Evolution of the number of running instances.

Figure 3 .

 3 Figure 3. Examples of results for efficiency and number of running instances.

Figure 4 .

 4 Figure 4. Cumulated efficiency

Figure 5 .

 5 Figure 5. Scheduling time in seconds