Anne Benoit

Alexandru Dobrila

Jean-Marc Nicod

Laurent Philippe

Keywords: workload balancing, distributed systems, fault tolerance, scheduling, optimization heuristics équilibrage de charge, systèmes distribués, tolérance aux pannes, ordonnancement, heuristiques d'optimisation

In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.

Équilibrage de charge et optimisation du débit dans les systèmes hétérogènes sujets aux pannes

Résumé : Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécutives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée.

Introduction

Most of the distributed environments are subject to failures, and each component of the environment has its own failure rate. Assuming that a fault may be tolerated, as for instance in asynchronous systems [START_REF] Bahi | Coupling dynamic load balancing with asynchronism in iterative algorithms on the computational grid[END_REF] or production systems, the failures have an impact on the system performance. When scheduling an application onto such a system, either we can account for failures to help improve the performance in case of failures, or ignore them. In some environments, such as computing grids, this failure rate is so high that we cannot ignore failures when scheduling applications that last for a long time as a batch of input data processed by pipelined tasks for instance. This is also the case for micro-factories where a production is composed of several instances of the same micro-component that must be processed by cells.

In this paper, we deal with scheduling and mapping strategies for coarsegrain workflow applications [START_REF] Wieczorek | Towards a general model of the multi-criteria workflow scheduling on the grid[END_REF][START_REF] Yu | A taxonomy of workflow management systems for grid computing[END_REF], for which each task of the workflow is of a given type, and subject to failures. The considered resources are typically execution resources grouped in a distributed platform, a grid or a micro-factory, on which we schedule either a batch of input data processed by pipelined tasks or a production (streaming application). Each resource provides functions or services with heterogeneous fault rates and efficiencies. In a streaming application, a series of jobs enters the workflow and progresses from task to task until the final result is computed. Once a task is mapped onto a set of dedicated resources (known in the literature as multi-processor tasks [START_REF] Blazewicz | Scheduling multiprocessor tasks to minimize schedule length[END_REF][START_REF] Gröflin | Feasible job insertions in the multiprocessor-task job shop[END_REF]), the computation requirements and the failure rates for each resource when processing one job are known. After an initialization delay, a new job is completed every period and it exits the workflow. The period is therefore defined as the longest cycle-time of a resource, and it is the inverse of the throughput that can be achieved. We target coarse-grain applications and platforms on which the cost of communications is negligible in comparison to the cost of computations.

In the distributed computing system context, a use case of a streaming application is for instance an image processing application where images are processed in batches, on a SaaS (Software as a service) platform. In this context, failures may occur because of the nodes, but they also may be impacted by the complexity of the service [START_REF] Litke | Efficient task replication and management for adaptive fault tolerance in mobile grid environments[END_REF]. On the production side, a use case is a microfactory [START_REF] Verettas | Pocketfactory: a modular and miniature assembly chain including a clean environment[END_REF][START_REF] Descourvières | Towards automatic control for microfactories[END_REF][START_REF] Tanaka | Development of desktop machining microfactory[END_REF] composed of several cells that provides functions as assembly or machining. But, at this scale, the physical constraints are not totally controlled and it is mandatory to take faults into account in the automated command. A common property of these systems is that we cannot use replication, as for instance in [START_REF] Cirne | On the efficacy, efficiency and emergent behavior of task replication in large distributed systems[END_REF][START_REF] Weissman | Fault tolerant scheduling in distributed networks[END_REF][START_REF] Parhami | Voting algorithms[END_REF], to overcome the faults. For streaming applications, it may impact the throughput to replicate each task. For a production which deals with physical objects, replication is not possible. Fortunately, losing a few jobs may not be a big deal; for instance, the loss of some images in a stream will not alter the result, as far as the throughput is maintained, and losing some microproducts is barely more costly than the occupation of the processing resources that have been dedicated to it.

The failure model is based on the Window-Constrained [START_REF] West | Analysis of a window-constrained scheduler for real-time and best-effort packet streams[END_REF] model, often used in real-time environment. In this model, only a fraction of the messages will reach their destination. The losses 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.

The paper is organized as follows. Section 2 presents the framework and formalizes the optimization problems tackled in the paper. An exhaustive complexity study is provided in Section 3: we exhibit some particular polynomial problem instances, and prove that the remaining problem instances are NPhard problems. In Section 4, we design a set of polynomial-time heuristics to solve the most general problem instance, building upon complexity results, and in particular linear program formulations to solve sub-problems. Moreover, we conduct extensive simulations to assess the relative and absolute performance of the heuristics. Finally, we conclude in Section 5.

Framework and optimization problems

In this section, we define the problems that we tackle. First we present the application and platform models. Then, we discuss the objective function and the rules of the game, before introducing formally the optimization problems.

Applicative framework

The application model is a stream of job instances that are executed one after another on the platform. All the job instances have the same structure, a workflow, but different inputs. The workflow is composed of a set N of n tasks: N = {T 1 , T 2 , . . . , T n } that are linked by precedence constraints. From the tasks point of view, the application model may also be seen as a pipeline where the tasks are successively applied to the job instances and the workflow can be modeled by a linear chain in which the vertices are tasks, and edges represent dependencies between tasks. An example of application tasks is represented on Figure 1.

In the workflow, we note x i the average number of jobs processed by task T i to ouput one job out of the system, x in the number of jobs that input the platform and x out the number of jobs that output the platform. Here, we want to maximize the throughput and, as some job losses may occur because of failures, we need to input more jobs in the platform than what we get out of the system (x in > x out ). Note that x i+1 depends on x i and of the properties, failures and computing power, of the machines that process T i .

A type is associated to each task as the same operation may be applied several times to the same job. 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. T n T 1 T i T i+1
Figure 1: Example of application.

Target platform

The target platform is distributed and heterogeneous. It consists of a set M of m machines (a cell in the micro-factory or a host in a grid platform):

M = {M 1 , M 2 , . . . , M m }.
The task processing time depends on the machine that performs it: it takes w i,u units of time to machine M u to execute task T i on one job. Each machine is able to process all the task types. But, to avoid costly context or setup changes during execution, the machines may be specialized to process only one task type. Moreover, the machine are interconnected by a complete graph but we do not take communication times into account as we consider that the processing time is much greater than the communication time (coarse-grain applications).

An additional characteristic of our framework is that failures may occur. It may happen that a job (or data, or product) is lost (or damaged) while a task is being executed on this job instance. For instance, an electrostatic charge may be accumulated on an actuator and a the piece will be pushed away rather than caught or a message will be lost due to network contention. 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 job instances, 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 jobs to be processed and the inability to finish them. As explained above, in order to deal with failures, we process more inputs than needed, so that at the end, the required throughput is reached.

The failure rate of task T i performed onto machine M u is the percentage of failure for this task and is denoted f i,u = li,u bi,u , where l i,u is the number of lost products each time b i,u products have been processed (l i,u ≤ b i,u ).

Objective function

Our goal is to assign tasks to machines so as to optimize some key performance criteria. A task can be allocated to several machines, and q(i, u) is the quantity of task T i executed by machine M u ; if q(i, u) = 0, T i is not assigned to M u .

Recall that x i is the average number of jobs processed by task T i to output one job out of the system. We must have, for each task T i , m u=1 q(i, u) = x i , i.e., enough jobs are processed for task T i in the system.

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 number x in of products to input in the system. Rather, we consider that losing one instance is not a big deal, and we focus on a performance criteria, the throughput. The goal is to maximize the number of instances processed per time unit, making abstraction of the initialization and clean-up phases. This objective is important when a large number of instances must be processed. Actually, rather than maximizing the throughput of the application, we deal with the equivalent optimization problem that minimize the period, the inverse of the throughput.

Unfortunately, we cannot compute the number x i of jobs needed by task T i , before allocating that task to some machines. Remember that each task T i has an unique successor T i+1 and that x i+1 is the amount of jobs needed by T i+1 as input. Since T i is distributed on several machines with different failure rates, we have m u=1 (q(i, u) × (1f i,u )) = x i+1 , where q(i, u) × (1f i,u ) represents the amount of jobs output by the machine M u if q(i, u) jobs are treated by that machine. For each task, we sum all the instances treated by all the machines.

We are now ready to define the cycle-time ct u of machine M u : it is the time needed by M u to execute all the tasks T i with q(i, u) > 0:

ct u = n i=1 q(i, u) × RR n°7532
w i,u . The objective function is to minimize the maximum cycle-time, which corresponds to the period of the system: min max 1≤u≤m ct u .

Rules of the game

Different rules of the game may be enforced to define the allocation, i.e., the q(i, u) values. For one-to-many mappings, we enforce that a single task must be mapped onto each machine:

∀1 ≤ i, i ′ ≤ n, i = i ′ , q(i, u) > 0 ⇒ q(i ′ , u) = 0.
For instance, on Figure 2, 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. This mapping is quite restrictive because we must have at least as many machines as tasks. Note that a task can be split in several instances and each instance is executed by different machines.

We relax this rule to allow for specialized mappings, in which several tasks of the same type can be mapped onto the same machine:

∀1 ≤ i, i ′ ≤ n s.t. t(i) = t(i ′ ), q(i, u) > 0 ⇒ q(i ′ , u) = 0.
For instance, on Figure 3, we have five tasks with types t(1) = t(3) = t(5) = 1 and t(2) = t(4) = 2. Machine M 3 computes task T 1 , therefore it can also execute T 3 and T 5 but not T 2 and T 4 . As types are not dedicated to machines, T 5 can also be assigned to another machine, for instance M 1 . Note that if each task has a different type, the specialized mapping and the one-to-many mapping are equivalent.

Finally, general mappings have no constraints: any task (no matter the type) can be mapped on any machine, as illustrated on Figure 4. 2)=t(4)=2 and t(5) = 3.

(a) (b) (c) 1 2 2 2 3 3 1 M 4 M 2 M 1 M 1 M 4 M 2 M 3 M 3
M 2 M 3 M 4 M 2 M 3 M 1 M 4 M 1 Figure 3: Specialized mapping. t(1)=t(3)=t(5)=1 and t(2)=t(4)=2. (b) 1 2 3 5 4 5 5 1 1 (a) (c) 3 4 2 M 3 M 2 M 3 M 2 M 4 M 1 M 4 M 1 Figure 4: General mapping. t(1)=t(3)=1, t(

RR n°7532

Problem definition

For the optimization problem that we consider, the three important parameters are: (i) the rules of the game (one-to-many (o2m) or specialized (spe) or general (gen) mapping); (ii) the failure model (f if failures are all identical, f i if the failure for a same task is identical on two different machines, f u if the failure rate depends only on the machine, and the general case f i,u ); and (iii) the computing time (w if the processing times are all identical, w i if it differs only from one task to another, w u if it depends only on the machine, and w i,u in the general case). We are now ready to formally define the optimization problem:

Definition 1 (MinPer(R, F, W )).
Given an application and a target platform, with a failure model

F = {f |f i |f u |f i,u | * } and computation times W = {w|w i |w u |w i,u | * }, find a mapping, i.e., values of q(i, u) such that for each task T i (1 ≤ i ≤ n), m u=1 q(i, u) = x i , following rule R = {o2m|spe|gen| * } which minimizes the period of the application, max 1≤u≤m i=1 n q(i, u) × w i,u .
For instance, MinPer(o2m, f i , w i ) is the problem of minimizing the period with a one-to-many mapping, where both failure rates and execution time depend only on the tasks. Note that * is used to express the problem with any variant of the corresponding parameter; for instance, MinPer( * , f i,u , w) is the problem of minimizing the period with any mapping rule, where failure rates are general, while execution times are all identical.

Complexity results

In this section, we assess the complexity of the different instances of the problem that we named the MinPer(R, F, W ) problem. First we establish some properties on the solution of the problems with F = f i in Section 3.1. Then, building upon these properties, we provide the complexity of these problems in Section 3.2. Finally, we discuss the most general problems with F = f i,u in Section 3.3.

Even though the general problem is NP-hard, we show in Section 3.4 that once the allocation of tasks to machines is known, we can optimally decide how to share tasks between machines, in polynomial time. Also, we give an integer linear program to solve the problem (in exponential time) in Section 3.5.

Particularities of the MinPer( * , f i , * ) problems

In this section, we focus on the MinPer( * , f i , * ) problems, and we first show how these problems can be simplified. Indeed, in this case, the number of products that should be computed for task T i at each period, x i , is independent of the allocation of tasks to machines. We can therefore ignore the failure probabilities, and focus on the computation of the period of the application.

The following Lemma 1 allows us to further simplify the problem: tasks of similar type can be grouped and processed as a single equivalent task. Lemma 1. For MinPer( * , f i , w i ) or MinPer( * , f i , w u ), there exists an optimal solution in which all tasks of the same type are executed onto the same set of RR n°7532 machines, in equal proportions:

∀1 ≤ i, j ≤ n with t(i) = t(j), ∃ α i,j ∈ Q such that ∀1 ≤ u ≤ m, q(i, u) = α i,j × q(j, u) . (1)
Proof. Let OP T be an optimal solution to the problem, of period P . Let t be a task type, and, without loss of generality, let T 1 , . . . , T k be the k tasks of type t, with k ≤ n, and let M 1 , . . . , M v be the set of machines specialized to type t in the optimal solution OP T (i.e., they have been allocated only tasks from T 1 , . . . , T k ), with v ≤ m. In the optimal solution, q(i, u) is the proportion of task T i assigned to machine M u . For each task T i , 1 ≤ i ≤ k, we have 1≤u≤v q(i, u) = x i , and for each machine M u , 1 ≤ u ≤ v, we have 1≤i≤k q(i, u)w i,u ≤ P , where w i,u may be either w i or w u , depending upon the problem instance.

We build a new optimal solution, OP T ′ , which follows Equation ( 1). The proportion of task T i assigned to machine M u in this solution is q ′ (i, u), and

x * = 1≤i≤k x i .
Let us start with the MinPer( * , f i , w u ) problem. We define q ′ (i, u)

= xi x * × P wu . For task T i , 1≤u≤v q ′ (i, u) ≥ xi x * × 1≤u≤v 1≤i≤k q(i, u)
, by definition of OP T , and therefore 1≤u≤v q ′ (i, u) ≥ x i : we have distributed all the work for this task. Moreover, by construction, 1≤i≤k q ′ (i, u)w u = P : solution OP T ′ is optimal (its period is P ). We have built an optimal solution which satisfies Equation ( 1), with α i,j = xi xj , by redistributing the work of each task on each machine in equal proportion.

The reasoning is similar for the MinPer( * , f i , w i ) problem, except that w i is now depending on the task, and therefore we define q ′ (i, u) = xi wix * × P . We still have the property that all the work is distributed, and the period of each machine is still P . The only difference relies in the values of α i,j , which are now also depending upon the w i : α i,j = xi xj × wj wi . For each problem instance, we have built an optimal solution which follows Equation (1), therefore concluding the proof.

Corollary 1. For MinPer( * , f i , w i ) or MinPer( * , f i , w u ), we can group all tasks of same type t as a single equivalent task T (eq) t such that

x (eq) t = 1≤i≤n|t(i)=t x i .
Then, we can solve this problem with the one-to-many rule, and deduce the solution of the initial problem.

Proof. Following Lemma 1, we search for the optimal solution which follows Equation [START_REF] Bahi | Coupling dynamic load balancing with asynchronism in iterative algorithms on the computational grid[END_REF]. Since all tasks of the same type are executed onto the same set of machines in equal proportions, we can group them as a single equivalent task. The amount of work to be done by the set of machines corresponds to the total amount of work of the initial tasks, i.e., for a type t, 1≤i≤n|t(i)=t x i .

The one-to-many rule decides on which set of machines each equivalent task is mapped, and then we share the initial tasks in equal proportions to obtain the solution to the initial problem: if task T i is not mapped on machine M u , then q(i, u) = 0, otherwise

q(i, u) = x i x (eq) t(i) × P w i|u , RR n°7532
where w i|u = {w i | w u }, depending upon the problem instance.

3.2 Complexity of the MinPer( * , f i , * ) problems

We are now ready to establish the complexity of the MinPer( * , f i , * ) problems.

Recall that n is the number of tasks, m is the number of machines, and p is the number of types.

Results are summarized in Table 1. The MinPer( * , f i , w i ) problems can all be solved in polynomial time, as well as MinPer(gen, f i , w u ), while this latter problem with w u becomes NP-hard for one-to-many and specialized mappings. For the most general case of w i,u , one-to-many and specialized mappings are NP-hard since they were NP-hard with w u , and a linear program allows us to solve MinPer(gen, f i , w i,u ), which remains polynomial.

We start by providing polynomial algorithms for one-to-many and specialized mappings with w i (Theorem 1 and Corollary 2). Then, we discuss the case of general mappings, which can also be solved in polynomial time (Theorem 2). Finally, we tackle the instances which are NP-hard (Theorem 3).

Theorem 1. MinPer(o2m, f i , w i ) can be solved in polynomial time O(m × log n).
Proof. First, note that solving this one-to-many problem amounts to decide on how many machines each task is executed (since machines are identical), and then split the work evenly between these machines to minimize the period. Hence, if T i is executed on k machines, q(i, u) = xi k , where M u is one of these k machines, and the corresponding period is xi k × w i . We exhibit a dynamic programming algorithm which computes the optimal solution in polynomial time. We compute P (i, k), which is the period that can be achieved to process tasks T 1 , . . . , T i with k machines. The solution to the problem is P (n, m), and the recurrence writes:

P (i, k) = min 1≤k ′ ≤k max P (i -1, k -k ′ ), x i k ′ × w i ,
with the initialization P (1, k) = xi k × w i (we use all remaining machines to process the last task), and P (i, 0) = +∞ (no solution if there are still some tasks to process but no machine left). There are n × m values of P (i, k) to compute, and the computation takes a time in O(m). Therefore, the complexity of this algorithm is of order O(n × m 2 ).

Note that it is also possible to solve the problem greedily. The idea is to assign initially one machine per task (note that there is a solution only if m ≥ n), sort the tasks by non-increasing period, and then iteratively add a machine to the task whose machine(s) have the greater period, while there are some machines available. Let g i be the current number of machines assigned to task T i : the corresponding period is xi gi ×w i . At each step, we insert the task whose period has been modified in the ordered list of tasks, which can be done in O(log n) (binary search). The initialization takes a time O(n log n) (sorting the tasks), and then there are mn steps of time O(log n). Since we assume m ≥ n, the complexity of this algorithm is in O(m × log n). To prove that this algorithm returns the optimal solution, let us assume that there is an optimal solution of period P opt that has assigned o i machines to task T i , while the greedy algorithm has assigned g i machines to this same task, and its period is P greedy > P opt . Let T i be the task which enforces the period in the greedy solution (i.e., P greedy = x i w i /g i ).

The optimal solution must have given at least one more machine to this task, i.e., o i > g i , since its period is lower. This means that there is a task T j such that o j < g j , since 1≤i≤n o i ≤ 1≤i≤n g i = m (all machines are assigned with the greedy algorithm). Then, note that since o j < g j , because of the greedy choice, x j w j /o j ≥ x i w i /g i (otherwise, the greedy algorithm would have given one more machine to task T i ). Finally, P opt ≥ x j w j /o j ≥ x i w i /g i = P greedy , which leads to a contradiction, and concludes the proof.

Corollary 2. MinPer(spe, f i , w i ) can be solved in polynomial time O(n + m × log p).
Proof. For the specialized mapping rule, we use Corollary 1 to solve the problem: first we group the n tasks by types, therefore obtaining p equivalent tasks, in time O(n). Then, we use Theorem 1 to solve the problem with p tasks, in time O(m × log p). Finally, the computation of the mapping with equal proportions is done in O(n), which concludes the proof.

Theorem 2. MinPer(gen, f i , * ) can be solved in polynomial time.

Proof. We exhibit a linear program to solve the problem for the general case with w i,u . Note however that the problem is trivial for w i or w u : we can use Corollary 1 to group all tasks as a single equivalent task, and then share the work between machines as explained in the corollary.

In the general case, we solve the following (rational) linear program, where the variables are P (the period), and q(i, u), for 1 ≤ i ≤ n and 1 ≤ u ≤ m.

Minimize P subject to (i) q(i, u) ≥ 0 for 1 ≤ i ≤ n, 1 ≤ u ≤ m (ii) 1≤u≤m q(i, u) = x i for each task T i with 1 ≤ i ≤ n (iii) 1≤i≤n q(i, u) × w i,u ≤ P for each machine M u with 1 ≤ u ≤ m (2)
The size of this linear program is clearly polynomial in the size of the instance, all n × m + 1 variables are rational, and therefore it can be solved in polynomial time [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF].

Finally, we prove that the remaining problem instances are NP-hard (one-tomany or specialized mappings, with w u or w i,u ). Since MinPer(o2m, f i , w u ) is a special case of all other instances, it is sufficient to prove the NP-completeness of the latter problem. Theorem 3. The MinPer(o2m, f i , w u ) problem is NP-hard in the strong sense.

Proof. We consider the following decision problem: given a period P , is there a one-to-many mapping whose period does not exceed P ? 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 3-PARTITION [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF], which is NP-complete in the strong sense.

We consider an instance I 1 of 3-PARTITION: given an integer B and 3n positive integers a 1 , a 2 , . . . , a 3n such that for all i ∈ {1, . . . , 3n}, B/4 < a i < B/2 f i f i,u w i w u or w i,u w i w u or w i,u o2m or spe polynomial NP-hard NP-hard NP-hard gen polynomial polynomial polynomial polynomial Table 1: Complexity of the MinPer problems. and with n i=1 a i = nB, does there exist a partition I 1 , . . . , I n of {1, . . . , 3n} such that for all j ∈ {1, . . . , n}, |I j | = 3 and i∈Ij a i = B? We build the following instance I 2 of our problem with n tasks, such that x i = B, and m = 3n machines with w u = 1/a u . The period is fixed to P = 1. Clearly, the size of I 2 is polynomial in the size of I 1 . We now show that I 1 has a solution if and only if I 2 does.

Suppose first that I 1 has a solution. For 1 ≤ i ≤ n, we assign task T i to the machines of I i : q(i, u) = a u for u ∈ I i , and q(i, u) = 0 otherwise. Then, we have 1≤u≤m q(i, u) = u∈Ii a u = B, and therefore all the work for task T i is done. The period of machine M u is 1≤i≤n q(i, u) × w u = a u /a u = 1, and therefore the period of 1 is respected. We have a solution to I 2 .

Suppose now that I 2 has a solution. Task T i is assigned to a set of machines, say I i , such that u∈Ii q(i, u) = B, and q(i, u) ≤ a u for all u ∈ I i . Since all the work must be done, by summing over all tasks, we obtain q(i, u) = a u , and the solution is a 3-partition, which concludes the proof.

Complexity of the MinPer( * , f i,u , * ) problems

When we consider problems with f i,u instead of f i , we do not know in advance the number of jobs to be computed by each task in order to have one job exiting the system, since it depends upon the machine on which the task is processed. However, we are still able to solve the problem with general mappings, as explained in Theorem 4. For one-to-many and specialized mappings, the problem is NP-hard with w u , since it was already NP-hard with f i in this case (see Theorem 3). We prove that the problem becomes NP-hard with w i in Theorem 5, which illustrates the additional complexity of dealing with f i,u rather than f i . Results are summarized in Table 1.

Theorem 4. MinPer(gen, f i,u , * ) can be solved in polynomial time.

Proof. We modify the linear program (2) of Theorem 2 to solve the case with general failure rates f i,u . Indeed, constraint (ii) is no longer valid, since the x i are not defined before the mapping has been decided. It is rather replaced by constraints (iia) and (iib):

(iia) 1≤u≤m q(n, u) × (1 -f n,u ) = 1 ; (iib) 1≤u≤m q(i, u) × (1 -f i,u ) = 1≤u≤m q(i + 1, u) for each T i with 1 ≤ i < n .
Constraint (iia) states that the final task must output one job, while constraint (iib) expresses the number of jobs that should be processed for task T i , as a RR n°7532 function of the number for task T i+1 . There are still n × m + 1 variables which are rational, and the number of constraints remains polynomial, therefore this linear program can be solved in polynomial time [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF].

Theorem 5. The MinPer(o2m, f i,u , w i ) problem is NP-hard.

Proof. We consider the following decision problem: given a period P , is there a one-to-many mapping whose period does not exceed P ? 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 SUBSET-PRODUCT-EQ (SPE), which is NP-complete (trivial reduction from SUBSET-PRODUCT [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]).

We consider an instance I 1 of SPE: given an integer B, and 2n positive integers a 1 , a 2 , . . . , a 2n , does there exist a subset I of {1, . . . , 2n} such that |I| = n and i∈I a i = B? Let C = 1≤i≤2n a i .

We build the following instance I 2 of our problem with 2n + 2 tasks, and 2n + 2 machines, so that the mapping has to be a one-to-one mapping (i.e., one task per machine). We ask whether we can obtain a period P = 1. Tasks T 1 and T n+2 are such that they should be allocated to machines M 2n+1 and M 2n+2 : the other machines never successfully compute a job for these tasks. We have:

•

w 1 = B/C 2 and w n+2 = 1/B; • f 1,2n+1 = f n+2,2n+2 = 0 for 1 ≤ u ≤ 2n + 2 (i.e.
, no failures in this case);

• f 1,u = f n+2,v = 1 for u = 2n + 1 and v = 2n + 2 (i.e., total failure in this case). The values of the failure probabilities mean that machine M 2n+1 (resp. M 2n+2 ) never fails on task T 1 (resp. T n+2 ), while all the other machines always fail on these tasks, i.e., the number of failed product is equal to the number of products entering the machine. No final product is output if these tasks are mapped onto such a machine.

For the other tasks (2 ≤ i ≤ n + 1 and n + 3 ≤ i ≤ 2n + 2), we have:

• w i = 1/C 2 (i.e.
, the period is always matched);

• f i,2n+1 = f i,2n+2 = 0 (i.e., no failure on M 2n+1 and M 2n+2 );

• f i,u = 1 -1 a 2 u for 2 ≤ i ≤ n + 1 and 1 ≤ u ≤ 2n; • f i,u = 1 -1 au for n + 3 ≤ i ≤ 2n + 2 and 1 ≤ u ≤ 2n. B C 2 → 1 C 2 → • • • → 1 C 2 → 1 B → 1 C 2 → • • • → 1 C 2 T 1 T 2 . . . T n+1 T n+2 T n+3 . . . T 2n+2
Clearly, the size of I 2 is polynomial in the size of I 1 . We now show that I 1 has a solution if and only if I 2 does. Suppose first that I 1 has a solution, I. We build the following allocation for I 2 :

• T 1 is mapped on M 2n+1 ;

• T 2 is mapped on M 2n+2 ;

• for n + 3 ≤ i ≤ 2n + 2, T i is mapped on a machine M u , with u ∈ I;

• for 2 ≤ i ≤ n + 1, T i is mapped on a machine M u , with u / ∈ I. Note first that because of the values of f i,u , the number of jobs to be computed for a task never exceeds C 2 . Indeed, M 2n+1 and M 2n+2 never fail, and each task is mapped onto a distinct machine M u , with 1 ≤ u ≤ 2n, with a failure probability

f u = 1 -1 a 2 u or f ′ u = 1 -1 au . Note that f ′ u ≤ f u (indeed, a u ≥ 1 and a 2
u ≥ a u ), and therefore, for a task T i , the number of products to compute is

x i ≤ 1≤u≤2n 1/(1 -f u ) = 1≤u≤2n a 2 u = C 2 , see Section 2.3.
Therefore, the period of machines M 1 , . . . , M 2n , which are processing a task T i with w i = 1/C 2 , is not greater than

x i × w i = C 2 × 1/C 2 = 1 = P .
Now, we need to check the period of tasks T 1 and T n+2 . For T n+2 , we have

x n+2 = n+2≤i≤2n+2 1/(1 -f i,alloc(i) ), where M alloc(i) is the machine on which T i is mapped. Therefore, x n+2 = u∈I a u = B, since I is a solution to I 1 . Since w n+2,2n+2 = 1/B, the period of machine M 2n+2 is B × 1/B = 1 = P . Finally, for T 1 , x 1 = 1≤i≤2n+2 1/(1-f i,alloc(i) ) = u / ∈I a 2 u × u∈I a u . We have u / ∈I a 2 u = (C/B) 2
, and therefore x 1 = C 2 /B, and the period of machine M 2n+1 is exactly 1 as well. We have a solution to I 2 .

Suppose now that I 2 has a solution. It has to be a one-to-one mapping, since there are no more machines than tasks. If T 1 is not mapped on M 2n+1 , or if T n+2 is not mapped on M 2n+2 , the period of the corresponding machine is at least 2P , and hence the solution is not valid. The other tasks are therefore mapped on machines M 1 , . . . , M 2n . Let I be the set of n machines on which tasks T n+3 , . . . , T 2n+2 are mapped. The period for task T n+2 is respected, and therefore, u∈I a u × 1 B ≤ 1, and

u∈I a u ≤ B .
Then, for the period of task

T 1 , we obtain u / ∈I a 2 u × u∈I a u × B C 2 ≤ 1, therefore u / ∈I a u × C × B C 2 ≤ 1, and finally u / ∈I a u ≤ C B .
Since u∈I a u × u / ∈I a u = C, the two inequalities above should be tight, and therefore u∈I a u = B, which means that I 1 has a solution. This concludes the proof.

Fixed allocation of tasks to machines

If the allocation of tasks to machines is known, then we can optimally decide how to share tasks between machines, in polynomial time. We build upon the linear program of Theorem 4, and we add a set of parameters: a i,u = 1 if T i is allocated to M u , and a i,u = 0 otherwise (for 1 ≤ i ≤ n and 1 ≤ u ≤ m). The variables are still the period P , and the amount of task per machine q(i, u). The linear program writes:

Minimize P subject to (i) q(i, u) ≥ 0 for 1 ≤ i ≤ n, 1 ≤ u ≤ m (iia) 1≤u≤m q(n, u) × (1 -fn,u) = 1 (iib) 1≤u≤m q(i, u) × (1 -fi,u) = 1≤u≤m q(i + 1, u) for 1 ≤ i < n (iii) 1≤i≤n q(i, u) × wi,u ≤ P for 1 ≤ u ≤ m (iv) q(i, u) ≤ ai,u × Fmax for 1 ≤ i ≤ n and 1 ≤ u ≤ m (3)
We have added constraint (iv), which states that q(i, u) = 0 if a i,u = 0, i.e., it enforces that the fixed allocation is respected. F max = 1≤i≤n max 1≤u≤m f i,u is an upper bound on the q(i, u) values, it can be pre-computed before running the linear program. The size of this linear program is clearly polynomial in the size of the instance, all n × m + 1 variables are rational, and therefore it can be solved in polynomial time [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF].

Integer linear program

The linear program of Equation (3) allows us to find the solution in polynomial time, once the allocation is fixed. We also propose an integer linear program (ILP), which computes the solution to the MinPer(spe, f i,u , w i,u ) problem, even if the allocation is not known. However, because of the integer variables, the resolution of this program takes an exponential time. Note that this ILP can also solve the MinPer(o2m, f i,u , w i,u ): one just needs to assign a different type to each task.

Compared to the linear program of the previous section, we no longer have the a i,u parameters, and therefore we suppress constraint (iv). Rather, we introduce a set of Boolean variables, x(u, t), for 1 ≤ u ≤ m and 1 ≤ t ≤ p, which is set to 1 if machine M u is specialized in type t, and 0 otherwise. We then add the following constraints:

(iva) 1≤t≤p x(u, t) ≤ 1 for each machine M u with 1 ≤ u < m ; (ivb) q(i, u) ≤ x(u, t i ) × F max for 1 ≤ i ≤ n and 1 ≤ u ≤ m .
Constraint (iva) states that each machine is specialized into at most one type, while constraint (ivb) enforces that q(i, u) = 0 when machine M u is not specialized in the type t i of task T i .

This ILP has n × m + 1 rational variables, and m × p integer variables. The number of constraints is polynomial in the size of the instance. Note that this ILP can be solved for small problem instances with ILOG CPLEX [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF].

RR n°7532 4 Heuristics and simulations

From the complexity study of Section 3, we are able to find an optimal mapping for MinPer(gen, * , * ). In this section, we provide practical solutions to solve MinPer(spe, f i,u , w i,u ), which is NP-hard. Indeed, general mappings are not feasible in some cases, since it involves reconfiguring the machines between the execution of two tasks whose type is different. This additional setup time may be unaffordable. We design in Section 4.1 a set of polynomial time heuristics which return a specialized mapping, building upon the complexity results of Section 3. Finally, we present exhaustive simulation results in Section 4.2.

Polynomial time heuristics

Since we are able to find the optimal solution once the tasks are mapped onto machines, the heuristics are building such an assignment, and then we run the linear program of Section 3.4 to obtain the optimal solution in terms of q(i, u). The first heuristic is random, and serves as a basis for comparison. Then, the next three heuristics (H2, H3 and H4) are based on an iterative allocation process in two stages. In the first top-down stage, the machines are assigned from task T 1 to task T n depending on their speed w i,u : the machine with the best w 1,u is assigned to T 1 and so on. The motivation is that the workload of the first task is larger than the last task because of the job failures that arise along the pipeline. In the second bottom-up stage, the remaining machines are assigned from task T n to task T 1 depending on their reliability f i,u : the machine with the best f n,u is assigned to T n and so on. The motivation is that it is more costly to lose a job at the end of the pipeline than at the beginning, since more execution time has been devoted to it. We iterate until all the machines have at least one task to perform. Finally, H5 performs only a top-down stage, repetitively. The heuristics are described below.

H1: Random heuristic. The first heuristic randomly assigns each task to a machine when the allocation respects the task type of the chosen machine.

H2: without any penalization. The top-down stage assigns each task to the fastest possible machine. At the end of this stage, each task of the same type is assigned onto the same machine, the fastest. Then, the already assigned machines are discarded from the list. In the same way, the bottom-up stage assigns each task of the same type to the same machine starting from the more reliable one. We iterate on these two steps until all machines are specialized.

H3: workload penalization. The difference with H2 is in the execution of the top-down stage. Each time a machine is assigned to a task, this machine is penalized to take the execution of this task into account and its w i,u is changed to w i,u × (k + 1) where k is the number of tasks already mapped on the machine M u . This implies that several machines can be assigned to the same task type in this phase of the algorithm: if a machine is already loaded by several tasks then we may find a faster machine and assign it to this task type. The bottom-up stage has the same behavior as for H2.

H4: cooperation work. In this heuristic, a new machine is assigned to each task, depending on its speed, during the top-down stage then the bottom-up stage has the same behavior as the heuristic H2.

H5: Focus on speed. The heuristic H5 focuses only on the speed by repeating the top-down stage previously presented in the heuristic H3 until all the machines are allocated to at least one task.

Simulations

In this section, we evaluate the performance of the five heuristics. The period returned by each heuristic is measured in ms. Recall that m is the number of machines, p the number of types, and n the number of tasks. Each point in a figure is an average value of 30 simulations where the w i,u are randomly chosen between 100 and 1000 ms, for 1 ≤ i ≤ n and 1 ≤ u ≤ m, unless stated otherwise. Similarly, failure rates f i,u are randomly chosen between 0.2 and 10 % (i.e., 1/500 and 1/10), unless stated otherwise.

Heuristics versus linear program. In this set of experiments, the heuristics are compared to the integer linear program which gives the optimal solution. The platform is such that m = 20, p = 5 and 21 ≤ n ≤ 61. Figure 5 shows that the random heuristic H1 has poor performance. Therefore, for visibility reasons, H1 does not appear in the rest of the figures. Heuristics against the linear program -Normalization.

We focus in Figure 6 on the heuristics H2 to H5. Results show that the heuristics are not far from the optimal. The same experiment is used in Figure 7 with the normalization of the heuristics upon the linear program. The best heuristics H2 and H4 are between 1.5 and 2 from the optimal solution. With this configuration, although exponential, the linear program always finds a result. Note that, for a platform with 20 machines and 10 types instead of 5, the percentage of success of the linear program is less than 50% with 61 tasks.

General behavior of the heuristics. In a second set of simulations, we focus on the behavior of the heuristics alone. First we focus on the difference between having more tasks than machines or the contrary. A platform with 50 machines and 25 types of tasks is set. In Figure 8, the number of tasks varies between 10 and 50. Results show that H2 is slightly less performing than the other heuristics. This difference increases as the number of types get closer to the number of machines, as shown in Figure 9. Heuristics with more machines than tasks. Heuristics with more machines than tasks.

When the number of tasks is higher than the number of machines, H2 and H4 become clearly the best heuristics (see Figure 10). Indeed, at the end of the first allocation stage, H3 and H5 will almost have used all the machines and the second stage will thus not be decisive. This is why the lines of H3 and H5 are superimposed in this case.

To study the impact of the speed of the machines, we set a platform with almost homogeneous machines (100 ≤ w i,u ≤ 200). Results are presented in Figure 11 and shows that the homogeneity in terms of the machine speeds does not change the overall comportment of the heuristics. H2 and H4 are still the best even if the gap with H3 and H5 is reduced. Heuristics with more tasks than machines. Homogeneous machines.

RR n°7532

To conclude with general behavior, we studied the impact of the number of types with two platforms of 40 machines and a number of tasks ranging from 10 to 110. The number of task types is set to 5 for the first one (Figure 12) and to 35 for the second one (Figure 13). When the number of types is small compared to the number of machines (Figure 12), the opportunity to split groups is high. In this case, H2 and H4 are the best heuristics because the workload is shared among a bigger set of machines and not only on those that are efficient for a given task. In the contrary, when the number of types is close to the number of machines, the number of split tasks decrease. Indeed, each machine must be specialized to one type. In the experiment shown in Figure 13, only 5 machines can be used to share the workload once each machine is dedicated to a type. That explains why the performances of the heuristics are pretty much alike. Impact of the failure rate. In this last set of simulations, we study the impact of the failure rate on the heuristics. Figures 14 and15 show that when the failure rate is high (0 ≤ f i,u ≤ 30%), only H2 and H4 have a good performance. Remember that our heuristics have two stages, the first one optimizes the w i,u and the second one the f i,u . In the case of H3 and H5, the first stage does not encourage the reuse of a machine already assigned to a task (the penalization is high). Thus, in the particular case of the platform set in Figures 14 and15, H3 and H5 assign all the machines at the end of their first stage and cannot optimize the failure in the second stage because no more machines are available. Failure 0 ≤ fi,u ≤ 30%.

RR n°7532

Summary. Even though it is clear that H1 performs really poorly, the other heuristics can all be the most appropriate, depending upon the situation. Note that the comparison between the heuristics is made easier if the gap between the number of types and the number of machines is big. Indeed, with a small number of types, the tasks can be split many times because more machines are potentially dedicated to a same type. The choices made by a heuristic either to split a task or not have more impact on the result.

Conclusion

In this paper, we investigate the problem of maximizing the throughput of coarse-grain pipeline applications where tasks have a type and are subject to failures. We propose mapping strategies to solve the problem considering three rules of the game: one-to-many mappings (each machine processes at most one task), specialized mappings (several tasks of the same type per machine), or general mappings. In any case, the jobs associated to a task can be distributed upon the platform so as to balance workload between the machines. From a theoretical point of view, an exhaustive complexity study is proposed. We prove that an optimal solution can be computed in polynomial time in the case of general mappings whatever the application/platform parameters, and in the case of one-to-many and specialized mappings when the faults only depend on the tasks, while our optimization problem becomes NP-hard in any other cases. Since general mappings do not provide a realistic solution because of unaffordable setup times when reconfiguration occurs, we propose to solve the specialized mapping problem by designing several polynomial heuristics. Also, we give an integer linear programming formulation of the problem that allows us to compute an optimal solution on small problem instances and to evaluate the performance of these heuristics on such instances. The simulations show that some heuristics return specialized mappings with a throughput close to the optimal, and that using random mappings never gives good solutions. As future work, we plan to investigate other objective functions, as the latency, or other failure models in which the failure rate associated to the task and/or the machine is correlated with the time to perform that task.

Figure 2 :

 2 Figure 2: One-to-many mapping.

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: m = 20, p = 5. Heuristics against the linear program.

Figure 8 :

 8 Figure 8: m = 50, p = 25.

Figure 9 :

 9 Figure 9: m = 25, p = 15.

Figure 10 :

 10 Figure 10: m = 50, p = 25.

Figure 11 :

 11 Figure 11: m = 40, p = 30, 100 ≤ w i,u ≤ 200.

Figure 12 :

 12 Figure 12: m = 40, p = 5.Small number of types.

Figure 13 :

 13 Figure 13: m = 40, p = 35.High number of types.

Figure 14 :

 14 Figure 14: m = 15, p = 5. Failure 0 ≤ fi,u ≤ 10%.

Figure 15 :

 15 Figure 15: m = 15, p = 5.

RR n°7532

Acknowledgment

Anne Benoit is with Institut Universitaire de France. This work was supported in part by the ANR StochaGrid and RESCUE projects.


L A Laboratoire D'economie De

Production

Note De Travail

Arnaud Buchs

Water Crisis and Water Scarcity as Social Constructions The Case of Water Use in Almeria (Andalusia, Spain)

Introduction

Two opposite conceptions of water scarcity exist: scarcity seen as a natural phenomenon linked to a deficit of water resources and scarcity described as a geographically and historically situated social fact (Aguilera-Klink et al., 2000;[START_REF] Anand | Scarcity, entitlements and the economics of water in developing countries[END_REF]. This research is in line with the second category of studies and validates the hypothesis that scarcity is directly linked with uses.

This research aims at deciphering water rarefaction in the Almeria region. Following [START_REF] Bardhan | Scarcity, conflicts and cooperation: essays in the political and institutional economics of development[END_REF], who considers that water scarcity is "mainly a product of the failure of institutions", scarcity is analysed here as a failure of standardisation which appears as the result of a representation of water as an inexhaustible allocation resource, taken for granted. The institutionalisation of uses and rules all along History has been mainly responsible for the rarefaction of resources and for the unsustainability of the development scheme implemented.

After introducing our fieldwork and our theoretical corpus, we present the institutional evolution of the water sector in Spain and its implications on water uses in Almeria. We show that emergent scarcity is correlated with the idea that technique can solve the problem of water rarefaction, which has led to overexploitation. This conception of water is supported by the rhetoric of water scarcity developed to justify the expansion of hydraulic infrastructures.

I/ Materials

2-Theoretical background: historical institutionalism

This research applies a historical institutionalist approach, which considers the description of water uses and their regulation over a long period. As [START_REF] Bakker | Deconstructing discourses of drought[END_REF], we reckon that regulation is: "inherently (but by no means solely) a discursive practice, as well as an institutional framework embodying rules". Our hypothesis stating that the study of water standards and norms offers a relevant perspective to apprehend the evolution of water uses can be justified from an analytical point of view. Indeed, norms are seen as both enabling and constraining instituted processes ("working rules") [START_REF] Commons | Institutional economics[END_REF][START_REF] Commons | Institutional economics[END_REF]; [START_REF] Billaudot | Une vision institutionnaliste, historique et pragmatique de l'objet de la science économique[END_REF]. They constitute the outcomes of compromises and tradeoffs between the various users and typify the economic and political orientations proper to a given territory and population. Then, analyzing them enables us to understand the evolution of uses and their potential limitations [START_REF] Buchs | Les normes de l'eau comme objet d'instrumentalisation des politiques de l'eau. Panorama et perspectives en Méditerranée[END_REF]. The theoretical tools we have chosen articulate both technical and social norms and show that norms can express a prevailing vision of water and, by and large, nature (from values to rules).

II/ Results and discussion

1-Water scarcity as the consequence of "hydraulicist" standardisation

Even though the recent texts and documents framing water uses testify to the improvements in integrating environmental factors, water uses remain rooted in the technique-driven tradition of the outdated "hydraulic paradigm" (Saurí, Moral Ituarte, 2001). At the national level, the 1985 Water Law, which replaced the previous one dating back to 1879, introduced a major change in water uses' regulating processes in Spain, notably through the implementation of the principle of hydrological planning. For the MHD, hydrological planning is implemented through the South River Basin Hydrological Plan (CHSE, 1998). This process is paired with territorial planning, more particularly the 1997-2007 Plan for Infrastructures in Andalusia, which aims at increasing the resources by 2,470 Hm 3 /yr (COPT, 1999). For the Campo de Dalías, planning is framed by the Western Almeria Land-Use Development Plan [START_REF] Copt | Plan de Ordenación del territorio de la Comarca del Poniente almeriense[END_REF]. In these documents, water is considered merely as an input and the development of infrastructures, without taking into account spatial and environmental policies, is promoted. These documents belong to a tradition which encourages the development of the local agricultural sector with no limitations. Indeed, the expansion of modern agriculture in Almeria began with the 1941 designation of the Campo de Dalías as a "national interest" irrigatable land area by the National Institute for Colonisation, which had been founded in 1939. In 1953, the Institute approved the first General Transformation Plan, the purpose of which was to foster population settlements by transforming the area in order to irrigate it. As soon as the end of the 1950s, modern agriculture started superseding traditional agriculture (first plastic greenhouses in 1963, preparation of the ground in several layers -"enarenado" -and prevalence of microirrigation from 1976 onwards). In less than forty years, the Almeria region moved from a penultimate place ranking to a 24th place ranking out of the 52 Spanish regions in terms of GDP per capita. This growth has essentially been due to agricultural development: this sector accounts for an estimated 40% of direct or indirect participation in the region's GDP (Molina Herrera, 2005). Even though the agricultural production methods in Almeria are among the most water-efficient ones, paradoxically, technical evolutions have led to an expansion of irrigated areas and thus, an increase of the total withdrawals. What some consider as an "economic miracle" is coupled with an "ecological disaster". Despite the measures taken from 1984 onwards in order to curb the agricultural sector's expansion (i.e. the 117/1984 Directive, the 15/1984 Law and the 2618/1986 Royal Directive), the total greenhouses' surface area in the Almeria Province increased from 10,905 ha in 1985 to 25,983 ha in 2007(Sanjuan Estrada, 2007), this is why more than half of the total area devoted to intensive agriculture is thought to be illegal. Considering the Campo de Dalías only, greenhouses are spread over 18,337 ha and the massive aquifer depletion is estimated at (at least) 40-60 Hm 3 /yr (Pulido Bosch, 2005).

At the local and national levels, water standardisation promotes this idea that natural constraints can be ignored thanks to technical efficiency. This hydraulicist standardisation, which is based on a vision of water as an abundant resource which can in no way become a limiting factor, does not aim at adapting uses to resources but at satisfying needs which apparently cannot be reduced. Most of the farmers we have met agree with this idea as, what is even more distressing, do most regulating bodies, whose deficient supervision is often criticised ("desgovierno hidraulico").

2-The rhetoric of water scarcity to justify hydraulic infrastructures

The 1993 and 2001 National Hydrological Plans developed the rhetoric of water scarcity.

Thanks to water transfers, the objective was to solve the problem of "structural deficits" (or "cyclical drought") manifested in a "hydrological imbalance" between "dry Spain" and "humid Spain". This orientation was supported by the White Paper on Water in Spain, which aims at: "determining the territorial balance of resources and needs, and identifying the possible imbalances". It defines hydrological systems as being "structurally deficient", "whatever the infrastructures they could be equipped with and even if water-saving policies are optimised to their theoretical maximum". These territories can solve their current lack of resources "only thanks to water transfers from other zones" (MMA, 1998, p. 387). In 2004, the former Prime Minister declared that: "Almeria needs water and will get more water. Almeria and Andalusia need the National Hydrological Plan to go ahead" (inauguration of the Ebro transfer's first infrastructures, 18/02/2004, Huercál Overa).

These examples demonstrate the justification of hydraulic infrastructures and the minimisation of incentives to curb demand. From this point of view, the 2005 National Hydrological Plan, considered as ecologically innovative, remains grounded in the supply side. Moreover, it is based on the overestimated water needs calculated using theoretical endowments per use introduced in the former Plan (MOPT, 1992). More insidiously, interviews reveal that desalinisation could even accelerate groundwater depletion by providing farmers with a backup plan.

In the Campo de Dalías, intensive water use is justified and supported by the Western Almeria Land-use Development Plan, which radically defends productivist agriculture and considers water consumption as an exogenous factor which has to be satisfied. Thus: "it is logical not to impose limitations or to scale the sector down to adapt it to the possibilities offered by natural resources, but, on the contrary, it is more coherent and pertinent to design a general model to use resources, in particular water, in a sustainable perspective without questioning the sector's evolution" [START_REF] Copt | Plan de Ordenación del territorio de la Comarca del Poniente almeriense[END_REF]quoted by Moral Ituarte, 2001; our translation). It seems that the Andalusian farmers' way of using water is not negotiable.

Conclusions

The History of Almeria from 1940 onwards shows a willingness to tame water in order to satisfy, first, a political objective, i.e. the occupation of a hostile territory deserted by the local populations thanks to the mobilisation of water resources; then, the objective has become more economic and has been linked with the need to develop and encourage a production model based on extremely profitable intensive agriculture. From the 1980s onwards, the local and national authorities have tried to mitigate some limitations by integrating the environmental perspective with no shift of paradigm. This policy takes part in a standardisation process in compliance with the hydraulic paradigm. Nonetheless, sustainable water use is not possible without taking the entire water cycle, in which human activities are embedded, into account. Integrated and territorialised approaches enhancing water as common heritage or as a common resource have to be promoted, while reconsidering our conception of nature as endogenous. Alternatives and conflicts at the end of the hydraulic age. Geoforum,

  Our three-month qualitative field work was based on semi-directive interviews and on information collection (triangulation of sources: water users, local authorities and researchers). The Almeria province ranks first in the EU market regarding horticultural production and gathers the world's biggest concentration of greenhouses. It is situated at the South-East of Andalusia and is part of the Mediterranean Hydrographical District (MHD). The study was focused on the Campo de Dalías area, where most greenhouses are located. The climate is semi-arid and the average annual rainfall was roughly 246 mm over the 1976-2006 period, with an important variability (109 mm in 1985, 412 mm in 2008) (Las Palmerillas, 2009).

  The main objective stated in the 2001 National Hydrological Plan is the transfer of the Ebro via Catalonia, Valencia, Murcia and Almeria, and this recalls the 1993 National Hydrological Plan, which suggested restructuring the Spanish hydrographical territory by connecting the different basins and building more than 200 dams. Nevertheless, the anticipated transferred volumes are considerably lower than in 1993, with 1,050 Hm 3 /yr as opposed to 3,768 Hm 3 /yr (1,855 Hm 3 of which only from the Ebro)[START_REF] Mma | Libro blanco del agua en España[END_REF]. The White Paper on Water in Spain (MMA, 1998) supports this view. It is a database pertaining to resources and uses, as well as the available techniques, and concludes with the analysis of "potential transfers" in the framework of the National Hydrological Plan.Following the 2004 government changeover, the hydrological plan was modified in 2005, and desalinisation was substituted for the Ebro transfer (AGUA programme). Initially, the programme dealt with 105 projects promoting infrastructural improvement, network set-up and the creation of desalinisation plants all along the Mediterranean coast, and aimed at supplying a supplementary volume of 1,063 Hm 3 /yr for a total estimated cost of roughly €3,798 million (as opposed to more than €4,200 million for the previous plan)[START_REF] Marino (mmamrm | Programa AGUA[END_REF]. Just for the MHD, nine desalinisation plants were planned (including the already-existing Carboneras plant -42 Hm 3 /yr).Estimated costs and volumesof the AGUA programme in the Mediterranean hydrographical district (MHD), updated on the 02/03/2009.

  MINISTERIO DE OBRAS PÚBLICAS Y TRANSPORTES (MOPT), 1992. Orden de 24 de septiembre de 1992 por la que se aprueban las instrucciones y recomendaciones técnicas complementarias para la elaboración de los Planes Hidrológicos de Cuencas Intercomunitarias. BOE n° 249, Madrid. MOLINA HERRERA J. (eds.), 2005. La economía de la provincia de Almería. Almeria: Instituo Cajamar. 704 p. MORAL ITUARTE L. del, 2001. Planification hydrologique et politique territoriale en Espagne. Hérodote, n° 102. pp. 87-112. PULIDO BOSCH A. (eds.), 2005. Recarga en la Sierra de Gádor e hidrogeoquímica de los acuíferos del Campo de Dalías. Almeria: Estación experimental Cajamar. 337 p. SANJUAN ESTRADA J.F., 2007. Detección de la superficie invernada en la provincia de Almería a través de imágenes ASTER. Almeria: FIAPA. 65 p. SAURÍ D., MORAL ITUARTE L. del, 2001. Recent developments in Spanish water policy.