Emile Cadorel
email: emile.cadorel@imt-atlantique.fr

Hélène Coullon
email: helene.coullon@imt-atlantique.fr

Jean-Marc Menaud
email: jean-marc.menaud@imt-atlantique.fr

A workflow scheduling deadline-based heuristic for energy optimization in Cloud

Keywords: Cloud Computing, Scientific Workflow, Scheduling, Virtual Machines, Algorithm, HEFT

This article addresses the scheduling of heterogeneous scientific workflows while minimizing the energy consumption of the cloud provider, by introducing a deadline sensitive algorithm. Scheduling in a cloud environment is a difficult optimization problem. Usually, work around the scheduling of scientific workflows focuses on public clouds where infrastructure management is an unknown black box. Thus, many works offer scheduling algorithms designed to select the best set of virtual machines over time, so that the cost to the end user is minimized. This article presents a new HEFTbased algorithm that takes into account users deadlines to minimize the number of machines used by the cloud provider. The results show the real benefits of using our algorithm for reducing the energy consumption of the cloud provider.

I. INTRODUCTION

The Cloud computing is a well-known paradigm defined by the NIST as "a model for enabling convenient, ondemand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction".

Cloud providers are no longer confined to hosting everrunning services, such as web servers or databases for instance. Indeed, nowadays Clouds host many types of applications and computations such as, for instance, Big-Data, machine learning or very short batch jobs. Moreover, different types of computations may also be combined by scientists into complex heterogeneous scientific workflows or dataflows [START_REF] Bertram | Scientific workflow management and the kepler system[END_REF], [START_REF] Deelman | Workflows and e-science: An overview of workflow system features and capabilities[END_REF]. Scientific workflows model scientific applications as a set of coarse-grained tasks linked together by data dependencies. These workflows generally involve data of different sizes and time-consuming computation tasks.

To be able to host scientific workflows on Clouds, the allocation of virtual machines (VMs) and their planning over time is a major challenge for both the provider and the user (scientist). Indeed, with an optimized VMs allocation (i.e., resource sharing), a Cloud provider will be able to rent more VMs and reduce its costs. Similarly, the rental prices of VMs will be reduced, which will result in more attractive offers for the user. Most of the related work done to this day for planning scientific workflows on the Cloud considers the Cloud Provider's internal scheduler as an unknown black box. As a result, much work focuses on optimizing from the user's point of view, trying to minimize the cost of use or trying to stick to a user budget while taking into account the fixed prices of Cloud providers and their infinite resources [START_REF] Alkhanak | Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: A review, classifications, and open issues[END_REF]- [START_REF] Rodriguez | Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[END_REF].

This article presents a new scheduling algorithm for Cloud providers that aims to reduce the energy consumption of Cloud providers. To this end, the algorithm attempts to minimize the number of physical machines required to plan a set of workflows (i.e. a workload). This objective (i.e., minimizing the number of machines) replaces the usual makespan minimization (i.e., completion time) of HPC and Grid Computing scheduling algorithms [START_REF] Sun | Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling[END_REF]- [START_REF] Yu | Workflow Scheduling Algorithms for Grid Computing[END_REF]. Indeed, one of the main operating cost of a Cloud computing provider is the electrical consumption. This consumption can be reduced by limiting unused (idle consumption) or under-used (power and cooling costs) physical machines [START_REF] Buyya | Energyefficient management of data center resources for cloud computing: A vision, architectural elements, and open challenges[END_REF] 1 . Such optimization objective for workflows require the combination of consolidation and scheduling algorithms.

Our V-HEFT-deadline algorithm introduces a deadline approach for the user. Intuitively, when trying to reduce the makespan of a workflow, it is necessary to use a large number of machines, which is costly for the cloud provider. Indeed, since energy consumption cannot be represented by a linear function [START_REF] Wu | An intelligent power consumption model for virtual machines under cpu-intensive workload in cloud environment[END_REF], [START_REF] Hsu | Power signature analysis of the specpower ssj2008 benchmark[END_REF] defined by the number of machines and the running time, the use of a large number of machines for a very short time is more consuming than the use of a reduced number of machines for a slightly longer time interval. Conversely, if users can extend their deadlines instead of looking for the best possible makespan, a better energy optimization (i.e., number of machines used) can be achieved, resulting in a cost reduction for the Cloud provider. This cost reduction can then be reflected in the rental prices by a business model. One can note that such business model is above the scope of this paper but it seems realistic to, at least partially, pass on the savings made by the Cloud provider to the user in the rental price.

The workflows discussed in this document are highly heterogeneous. In addition to the different library require-ments, some tasks may need to be performed on different operating systems (OS) in the same workflow. For example, the genomic data stream designed by the ICO in [START_REF] Röst | Openswath enables automated, targeted analysis of data-independent acquisition ms data[END_REF]- [START_REF] Reiter | mprophet: automated data processing and statistical validation for largescale srm experiments[END_REF] uses data produced by a vendor-specific machine 2 . To convert the output formats of the machine to standards vendor-specific software developped for Windows must be used, while the other libraries (e.g., Openswath) must be run under Linux. This is a common issue in scientific workflows.

In this article, we consider virtual machines (VMs) for two reasons. On the one hand, the heterogeneity of operating systems and libraries makes it mandatory to load different operating systems on the same machine simultaneously. It can be noted that the management of several operating systems can also be performed on bare metal machines. However, in this case, a complete server will be reserved for each OS, which goes against the consolidation optimization sought. The virtualization mechanism allows several operating systems to be loaded on a single server and reduces the number of servers required. On the second hand, a multi-user workload is considered, thus, strong isolation, for security reasons, must be guaranteed which is made easier by the VMs.

This article presents the following contributions: (1) a detailed model of the scheduling problem under consideration; (2) an adaptation of the HEFT algorithm, namely V-HEFT-deadline, that takes into account both virtualization and deadlines and that minimizes the number of physical machines used to plan a workload; (3) a detailed evaluation compared to a VM oriented adaptation of HEFT, namely V-HEFT. The rest of this document is organized as follows. Section II presents the work related to workflow planning algorithms. Then, Section III details the problem modelization, Section IV presents our new algorithm V-HEFT-deadline and Section V offers a detailed evaluation of our algorithm compared to the V-HEFT. Finally, the section VI concludes this work and opens some perspectives.

II. RELATED WORK

In this section, we present some noteworthy work on scientific dataflow and workflow scheduling, whether for HPC, Grid and Cloud environments.

On the one hand, high-performance computing (HPC) and Grid computing show an interest in scientific workflow scheduling (heterogeneous, coarse-grained, interconnected tasks). These domains do not take virtualization into account in their scheduling algorithm. Indeed, physical machines are directly considered (Bare Metal). The algorithms for scheduling workflows in this area can be classified into three different groups: batch schedulers, list schedulers and pack schedulers.

In [START_REF] Yu | Workflow Scheduling Algorithms for Grid Computing[END_REF], Min-Min and Max-Min are presented. Both are batch algorithms (i.e. independent job scheduling). The Min-Min batch algorithm first creates a list of independent tasks 2 https://sciex.com/Documents/Downloads/Literature/Tech-Note-MSMSall-SWATH-Acquisition.pdf and schedules them, starting its decision process with the task with the lowest execution time (or the highest execution time for Max-Min). Then it deletes the tasks from the dependency graph, creating a set of new independent tasks. These two phases are repeated until all tasks are scheduled. These algorithms have been designed to plan independent task sets; therefore, they are not well suited for workflow and workflow planning, as indicated in [START_REF] Caniou | Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF].

In [START_REF] Sun | Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling[END_REF], Sun et al. claim that most HPC scheduling algorithms focus on CPU and core usage and that in practice, the user of the batch scheduler must juggle alone with other node resources, such as memory, requiring larger resources (a complete node, for example). Sun et al. consider all node resources more precisely by studying two algorithms based on list and pack scheduling. First, the list scheduling algorithm schedules the sorted task in a list and tries to minimize the time it takes to complete the submitted tasks (makespan). Secondly, the pack scheduling algorithm creates task packets that do not exceed the considered capacity and prohibits any further scheduling until all tasks in a packet are completed.

The HEFT algorithm [START_REF] Topcuouglu | Performanceeffective and low-complexity task scheduling for heterogeneous computing[END_REF] is a well-known heuristic based on a list scheduling. This heuristic is divided into two parts. First, a list is created containing all the tasks of the entire workload sorted by priority. Second, each task is scheduled, one by one, on the available resources while trying to minimize the overall completion time required to execute the workflows (makespan). In the scheduling phase of HEFT, a selection of physical resources (node) is made. For this purpose, the task computation time is calculated for each resource. The resource offering the most efficient execution (best execution time) is selected and the task is scheduled on it.

On the second hand, workflows scheduling strategies have also been studied for Cloud computing environments. Typically, [START_REF] Alkhanak | Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: A review, classifications, and open issues[END_REF] focuses on minimizing end-user costs to run scientific workflows in a public Cloud where the scheduling decision is an unknown black box. In [START_REF] Rodriguez | Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[END_REF], [START_REF] Abrishami | Deadlineconstrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF] a budget must be respected according to a public Cloud offer. Such work assumes that the Cloud provider is always able to meet the customer's needs (infinite resources).

In [START_REF] Bittencourt | Hcoc: a cost optimization algorithm for workflow scheduling in hybrid clouds[END_REF], a workflow planning algorithm is presented. A deadline is taken into account by the scheduling algorithm and a hybrid Cloud environment is considered (i.e. a combination of private and public Clouds). The model takes into account complex tasks, for which the number of instructions and the amount of communication between tasks are known, as well as the capacity of all Cloud resources. The scheduling algorithm is an ad hoc solution where a list scheduling is first run on the private infrastructure. If this scheduling cannot meet the user's deadline, the public Cloud is used to obtain more resources. This second part also assumes infinite resources of the public Cloud. The objective of using deadline, in [START_REF] Bittencourt | Hcoc: a cost optimization algorithm for workflow scheduling in hybrid clouds[END_REF] is different from our objective. Indeed, deadlines are intended to determine when it is necessary for the user to pay for more resources in a public Cloud.

In [START_REF] Caniou | Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] an algorithm based on HEFT is presented. This algorithm divides a client's budget by the number of workflows to schedule in a public Cloud environment. Moreover, this paper also extends Min-Min and shows that Min-Min is less effective than HEFT in minimizing makespan. The objective considered in [START_REF] Caniou | Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] is to respect a user budget. As for [START_REF] Rodriguez | Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[END_REF], [START_REF] Abrishami | Deadlineconstrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF], a public Cloud environment is considered and the assumption of infinite resources is made.

Finally, in [START_REF] Rodriguez | Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[END_REF] presents a PSO (Particle Swarm Optimization) algorithm for workflow scheduling. In this article, the authors consider a public Cloud, and aim to minimize the cost while respecting user deadlines, and considering a given public Cloud offer (and associated prices).

One can note from the above related-work on dataflows and workflows scheduling that, as far as we know, none of the existing contributions focus on our specific scheduling problem: taking deadlines into account in the internal workflow scheduling of the Cloud provider in order to reduce its energy consumption. First of all, HPC and Grid computing do not take into account virtualization, which significantly modifies algorithms, especially resource modeling. In addition, the objective of these algorithms is to minimize the makespan. Second, in Cloud related documents, the optimization strategy is not designed for the Cloud provider's internal scheduler, which is considered as a black box, but for the end-user costs while considering renting prices for VMs.

We could have chosen any of the above heuristics to solve our scheduling problem. Because of its clear two-phase approach and simplicity, we decided to base our work on the well-known HEFT algorithm in this contribution.

III. PROBLEM MODELIZATION

In this section, we present the model that describes our scheduling problem. The problem we aim to solve is to schedule all tasks of submitted workflows on virtual resources while satisfying tasks dependencies and their resource needs, and while respecting the capacity constraints of physical machines. Our objective is to minimize the energy consumption of the Cloud provider by reducing the number of physical machines used to plan workflows.

Execution environment. We denote J , the set of tasks to be scheduled and executed. These tasks make up the different workflows. Each workflow can be represented as a DAG -Directed Acyclical Graph G = (T, D), where T ⊂ J and D is the set of data dependencies between tasks. Each edge of the graph d ∈ D is weighted, and its weight represents the size of the data to be transferred from one task to another. In this article, we assume that the number of instructions to execute a task is given. We are aware that it is difficult to obtain this information accurately in practice. However, this problem is beyond the scope of this contribution and is left to future work. Each task has constraints that can be divided into two categories: the hardware constraints that can be quantified, such as the number of cores, the amount of memory; and the software constraints (OS, library, etc.). The environment in which we want to schedule workflows is a set of clusters of physical machines, with the ability to deploy different types of virtual machines. V denotes the set of VMs under usage within the infrastructure. Virtual machines are deployed from images, which have different hardware and software capacities. Let N be the set of compute nodes (physical machines). A node is associated with a given cluster. Bandwidth between nodes is considered heterogeneous, depending on the different clusters they belong. We denote bw N n,m the bandwith between n and m, for n and m ∈ N . We denote speed N n the speed of the node n ∈ N , in a number of instructions per core, and per instant (e.g., seconds). In this paper, we do not consider any overprovisioning of the nodes; consequently one core is reserved for one VCPU.

Software and Hardware constraints. For each node n ∈ N , we denote for each instant t ∈ N, the vector H tn =< h tnv , . . . , h tn|V| >, where h tnv = 1 if and only if the VM v ∈ V is hosted by n at instant t, h tnv = 0 otherwise. We also denote for each v ∈ V, at each instant t ∈ N, the vector E tv =< e tvj , . . . , e tv|J | >, where e tvj = 1 if and only if j ∈ J is executed by v at instant t, e tvj = 0 otherwise. C is the set of different hardware capacities (e.g., RAM, CPU, HDD, etc.). For each capacity k ∈ C, we define three vectors :

• C N k , of size |N |, which represents the capacity k provided by each nodes n ∈ N , such that C N k (n) is the capacity k that n ∈ N can supply. • C V k , of size |V| represents the required amount of resource k needed by each v ∈ V, such that C V k (v)
is both the amount of resource k needed by v ∈ V, and the amount of resource this VM v can provide.

• C J k , of size |J |, defines the amount of resource k required by each j ∈ J . For each capacity k ∈ C, we define the two following constraints in such a way that over-provisioning is not considered both for physical and virtual machines:

C V k • H tn ≤ C N k (n) ∀n ∈ N , ∀t ∈ N (1)
C J k • E tv ≤ C V k (v) ∀v ∈ V, ∀t ∈ N (2)
We also consider the software requirements of the tasks. Thus, we define S as the set of software requirements (e.g., OS, library, language, etc.). For each software requirement s ∈ S, we define that a task that requires the software s must be run on a virtual machine that has the software s.

Temporal dependency constraints. Let speed V tv be the speed of v ∈ V at instant t -let us remind that the speed is in number of instructions per core (here per VCPU). We do not consider over-provisioning, so the deterioration of the VM speed is assumed to be low [START_REF] Padala | Performance evaluation of virtualization technologies for server consolidation[END_REF], and considered to be 5% of the host node speed. Thus, speed V tv = speed N n • 0.95 if and only if h tnv = 1. The problem that we tackle is to improve the scheduling of a new set of workflows in terms of energy consumption. Thus, we do not consider the dynamic migration of virtual machines to different resources in this work. We plan to integrate and study this migration in our future work. Therefore, for simplicity in the rest of the paper, the speed of the VM v is time-independent and denoted as follows speed V v . In our model, virtual machines are dynamically provisioned on demand to manage the specific constraints of each task. A VM needs a certain amount of time to start and be ready to perform tasks. Let start V v the instant when v ∈ V initiates its powering on. We define boot V v as the number of instructions to run before v ∈ V is ready for usage. Let ready V v be the instant when v ∈ V is ready to compute tasks, such that

ready V v = start V v + boot V v speed V v
. We define the instant when a task can start as follows:

∀i ∈ J start i = max j∈predi (end j + max( d ji bw N locj ,loci , ready V v )), (3)
where v is the VM hosting the task i, loc i refers to the node hosting the VM of the task i ∈ J , and bw N n,m is the bandwidth between two physical nodes.

To explain more precisely why the Equation 3 uses the bandwidth between physical nodes, we must specify that in our model, VMs are only considered as computing resources. As a result, communications between different tasks are directly performed between nodes without a virtualization layer. This assumption made possible an overlap of communications and computations, which improves the quality (e.g., execution time) of workflows executions. Figure 1 illustrates this claim with an example where a given virtual machine of a first user consumes almost all the CPU and RAM resources of a given node, which makes impossible to start another virtual machine of a second user simultaneously without making over-provisionning. We assume that communications require a very low CPU load, so this load is not taken into account when calculating the resource usage (C N core ) of the node. In the first scenario (at the top of the figure), communications are performed within the VMs. In this case, the execution is fully sequential. Indeed, the first VM must be stopped before the second VM can be started. In the second scenario, on the contrary, since communications are made outside the VMs, it is possible to start the second VM while communications are performed for both users. As a result, the total execution time is reduced. Consequently, bandwidth between physical nodes are used in Equation 3U ser1 1 2 3

1 3 2 3 U ser2 (1) U ser1 1 2 3 3 1 2 3 U ser2
(2) In addition, the execution time of a task i depends on its weight W i (number of instructions) divided by the speed of the resource that will execute the task.

1 boot 2 computation 3 communication V M lif etime
∀i ∈ J exec i = W i speed V loci • 0.95 (4)
Finally, each workflow G = (T, D) has a deadline such that all tasks forming the workflow must be performed before the deadline.

Cost modelization. Our contribution aims at minimizing the operational costs of the Cloud computing provider. We assume that this cost is directly correlated to the data center's power consumption. It has already been shown [START_REF] Wu | An intelligent power consumption model for virtual machines under cpu-intensive workload in cloud environment[END_REF], [START_REF] Hsu | Power signature analysis of the specpower ssj2008 benchmark[END_REF] that the CPU's energy consumption is not a linear function defined by the load and the running time. Therefore, reducing the number of nodes for a longer period of time is not equivalent to using more nodes for a shorter period. To properly model the cost and therefore the gain of our solution, the consumption of a node is defined accordingly to [START_REF] Wu | An intelligent power consumption model for virtual machines under cpu-intensive workload in cloud environment[END_REF] and as follows:

t ∈ N P max n + ( P idle n -P max n ln 0.01 ) • ln cpu load tn , (5)
cpu load tn = v ∈ V (C J core (v) • E tv ) × h tnv C N core (n) , (6)
where P idle n is the idle consumption of the node, P max n is the power consumption of the node when fully used. The cpu load calculated by Equation 6is the percentage of cores used on a CPU at a given time. The value 0.01 is an arbitrarily small value to keep the logarithm calculable, and represents the minimal cpu load.

One can note that we have conducted experiments on the Ecotype cluster (Seduce3 platform) that perfectly match this model.

Objective. Our model aims at minimizing the number of nodes required to schedule a set of workflows in order to reduce the cost of the Cloud provider.

IV. V-HEFT-deadline ALGORITHM

In this section, we present our deadline aware scheduling heuristic V-HEFT-deadline based on V-HEFT, which is similar to HEFT [START_REF] Topcuouglu | Performanceeffective and low-complexity task scheduling for heterogeneous computing[END_REF] algorithm, but with VM oriented ressource selection phase.

As part of our algorithm, a set of workflows -each associated with a deadline -is submitted at a given time to the Cloud provider. The algorithm is launched following a regular clock and takes into account the VMs already hosted on the Cloud infrastructure.

Priorities and deadlines. In HEFT and V-HEFT, a priority is calculated for each task i of each workflow such that tasks with higher priorities are scheduled first. This priority is established according to the average completion time (on all possible nodes) of a task, denoted time J i , as well as its average communication time (between all possible nodes), denoted com J ij . The rank of a task is shown in Equation [START_REF] Sun | Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling[END_REF].

rank i = time J i + max j∈succ J i com J ij + rank j (7)
As illustrated in the main algorithm of V-HEFT in Algorithm 1, once all the tasks are sorted by rank (COMPUTERANKLIST function), the scheduling algorithm is launched. This algorithm will be detailed later in this section.

Algorithm 1 V-HEFT algorithm function HEFT (tasks, nodes) task list ← COMPUTERANKLIST (tasks, nodes) Eq. ( 7) for all t ∈ task list do SCHEDULEEARLIEST(t, nodes)

The first operation performed by V-HEFT-deadline, as indicated in Algorithm 2, is to order the workflows by difficulty (function SORTWORKFLOWS). This difficulty is defined by the difference between the deadline and the average execution time (on all possible nodes) of the critical path of the workflow as follows deadline -max j∈J rank j . Then, V-HEFT-deadline processes each workflow by decreasing difficulty unlike V-HEFT that directly rank all tasks of all submitted workflows. For each workflow to schedule, the function V-HEFTdeadline-WORKFLOW shown in Algorithm 3 is called. The first step of this function is to calculate the priority of each task (COMPUTERANKLIST function) of the input workflow The second step is to calculate the deadlines for each task of the current workflow. As already explained, in V-HEFTdeadline, the user submits a workflow with a global deadline, Algorithm 3 V-HEFT-deadline single workflow scheduling function V-HEFT-deadline-WORKFLOW (tasks, nodes, deadline) task list ← COMPUTERANKLIST (tasks, nodes) Eq. ( 7) dead list ← COMPUTEDEADLINES (tasks, nodes, deadline) Eq. ( 8) ons ← FILTERUSEDNODES(nodes) of f s ← FILTERUNUSEDNODES(nodes) return SCHEDULEBACKTRACK(0, 0, task list, dead list, ons, of f s) including all the tasks that make up this workflow. We also consider (as already explained in Section III) that the number of instructions necessary to perform each task is given when the workflow is submitted to the scheduler. It is therefore possible to calculate a time limit per task that must not be exceeded in order to meet the overall initial deadline of the workflow. Each task deadline will be used to avoid a full exploration of a scheduling that will necessarily lead to an overdue global deadline.

Each task deadline is calculated in the COMPUTEDEAD-LINES function of Algorithm 3. To calculate this time, it is necessary to start with the final tasks of the workflow that do not have successor. Indeed, for the final tasks, the time not to be exceeded is the overall deadline of the workflow. Then for any other task i ∈ J that has successors, the deadline is represented by Equation 8, where succ J i ⊂ T ⊂ J is the set of successor of i, and such that

∀ j ∈ succ J i , ∃ d ij ∈ D. ∀i ∈ J where |succ J i | > 0, dead J i = min j∈succ J i dead J j -min n,m∈N Wj speed N n •0.95 + dij bw N n,m (8)
Finally, the V-HEFT-deadline algorithm maintains two lists of physical machines (ons and of f s lists) so that the scheduling algorithm knows which physical machines are under usage for tasks or not. The rest of this section details the scheduling algorithm of V-HEFT-deadline (and V-HEFT).

Backtrack scheduling algorithm. V-HEFT-deadline tries to minimize the number of nodes used to schedule the workflows of a workload. To this end, our solution extends the V-HEFT algorithm with a partial backtracking heuristic. This heuristic consists in trying to perform scheduling on nodes that are under usage by other tasks. As soon as this attempt fails, because the tasks deadlines are no longer met, a backtrack is performed and a new node is considered. This new algorithm is defined in the recursive function SCHEDULEBACKTRACK of Algorithm 4 (initially called in Algorithm 3). This function takes as input the id of the first task (backTo), the id of the current task, the task list of the current workflow, the list of tasks deadlines, the list of nodes under usage and the list of unused nodes.

Algorithm 4 is the main part of the V-HEFT-deadline algorithm. If the deadline constraint cannot be met by considering nodes under usage only, the algorithm backtracks to the first task that was not scheduled on an unused node given as input, backTo. It can be noted that in our scheduling algorithm, the maximum number of backtracks is equal to the number of unused nodes at entry point. As already explained, V-HEFT-deadline manages each workflow one after the other by decreasing difficulty, unlike V-HEFT which handles all the tasks of all workflows in a single sorted list. In V-HEFT-deadline this cannot be done, because the backtrack part would go back to tasks that have little impact on the task that has not been scheduled. For this reason, if all tasks are processed together, all nodes will be used and a result close to V-HEFT will be observed but with worse complexity. For this reason, V-HEFT-deadline schedules the workflows one by one, sorted by decreasing difficulty.

Resource selection. Another essential part of the V-HEFT and V-HEFT-deadline algorithms is the resource selection function SCHEDULEEARLIEST. This function is called each time a task is to be scheduled, and is detailed in Algorithm 5. Obviously, the V-HEFT-deadline SCHEDULEEAR-LIEST function takes deadlines into account, which is not the case for V-HEFT. This resource selection phase is specific to the problem modeled in Section III. Due to virtualization and software constraints, virtual machines must be powered up. A VM is powered up for only two reasons: (1) the VMs already used by the owner of the current workflow cannot meet the requirements of the current task to be scheduled (or he does not have one), and for isolation and safety reasons, VMs of other users cannot be used; (2) by starting a new VM the quality of the schedule (makespan) is enhanced.

The function GETPLACEONNODE called in Algorithm 5 is used to find a suitable place to perform a task inside an existing or a new VM onto a specific node (physical machine). First, this function looks for a placement on the existing VMs of the user that minimizes the ending time of the task. Then, the function selects a new VM (that takes into account the constraints of the task) and calculates the ending time of the task on this new VM (taking into account its boot time). The place inside a VM that offers the earliest ending time is selected. The placement found inside a VM may extend the lifetime of that VM, thus the function must also know the capacities of the node hosting the VM.

Finally, in Algorithm 5, the function RESOURCEPROVI-SIONNING reserves the place on the node, updates all capacities information, and eventually stores the new selected VM. One can note that this reservation may be released when the V-HEFT-deadline algorithm backtrack on previous task scheduling.

Complexity. The complexity of the function GET-PLACEONNODE is common to both V-HEFT and V-HEFTdeadline algorithms, thus this function is not taken into account for the complexity. The complexity of V-HEFT is a function of the number of tasks in the workflow and the number of nodes on which the scheduling solution will be done. Therefore, its worst-case complexity V-HEFT is O(|J | × |N |), and is exactly equals to its average-case complexity.

The complexity of our new algorithm V-HEFT-deadline, is different due to the partial backtracking. The worst case, is when all the nodes are needed to schedule the workflow and when the backtrack is performed when reaching the last task of the workflow. The worst-case complexity is then

O( |J | i=1 (|N |+ i k=1 k)).
However, this complexity is on average far lower than the worst case, as only under usage nodes will be explored for most of the tasks. Section V validates this claim.

V. EVALUATION

In this section, we present a detailed evaluation of our V-HEFT-deadline algorithm. All evaluations are performed on realistic workflows generated by the pegasus workflow generator 4 [START_REF] Rodriguez | Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[END_REF].

A. Initial workload scheduling

This section presents the experimental results when considering an homogeneous group of physical machines (i.e., a cluster), and when no existing tasks are already running on the cluster (i.e., initial workload). This simplified use case offers the possibility to precisely analyze the behavior 4 https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator of V-HEFT-deadline without too many parameters to take into account. This section shows that introducing a deadline within V-HEFT is a way to optimize the number of machines used to schedule a set of workflows, thereby reducing the energy consumption of the Cloud provider. This section also shows that the execution time of V-HEFT-deadline is very competitive and scalable compared to V-HEFT.

Experimental setup. The Montage workflow depicted in Figure 2 is a typical synthetic case-study used to evaluate scheduling algorithms [START_REF] Bittencourt | Hcoc: a cost optimization algorithm for workflow scheduling in hybrid clouds[END_REF], [START_REF] Abrishami | Deadlineconstrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF]. It is a complex workflow that integrates most of the workflow classes characterized by Bharati et al. in [START_REF] Bharathi | Characterization of scientific workflows[END_REF]. The simulated workload is composed of a variable number of Montage workflows and the simulated infrastructure is composed of 20 homogeneous nodes with the hardware configuration of the Grid'5000 Econome cluster (see the first row of Table I). To correctly select a set of deadlines for our V-HEFT-deadline algorithm, we ran V-HEFT to get its approximate minimum makespan. Using the Pegasus workflow generator, only one information is provided about a task: its execution time (in seconds). We assume in our experiments that this time was produced by a single CPU core with a computing capacity of 2GFlops (floating operations per second). This assumption is used to transform information on the execution time into a number of instructions (as required by our model). We also assume that each Montage task has been calculated with a sufficient amount of memory, and we consider in our experiments that the memory requirements are always fulfilled. Furthermore, we consider a single VM template that uses 4 cores. Finally, the boot time of the VM template has been configured to 10 seconds on a 2 GFlops CPU core. Quality evaluation. Figure 3 represents the number of nodes used, respectively by V-HEFT and V-HEFT-deadline, to schedule workloads with variable amounts of Montage workflows. V-HEFT-deadline has been run with four dif- ferent deadlines proportional to the makespan computed by V-HEFT: (1) D=1.3, (2) D=1.5, (3) D=2, and (4) D=3. This result illustrates that relaxing the deadline offers more possibilities for V-HEFT-deadline to reduce the number of nodes needed by the schedule. As a result, when users can extend their deadlines, The Cloud provider can benefits from an energy consumption reduction. Obviously this cost reduction may be passed on the rental price for the user who then has interest in relaxing her/his deadline. One can note that even by extending the deadline from 1 (V-HEFT) to 1.5 the number of nodes can be divided by 2. When the deadline is extended from 1 to 3, only five of the twenty available nodes are used to schedule the workloads while V-HEFT would use 20 machines.

Energy consumption evaluation. Figure 4 shows estimated immediate power consumption (in Watt) of the nodes for the execution of 100 Montage workflows, scheduled by both V-HEFT and V-HEFT-deadline algorithm with different deadlines. This consumption has been estimated according to real power consumptions measured on a cluster of Grid'5000 (Ecotype). One can note that, as expected, power consumption is reduced when the deadlines are delayed.

The cost for the Cloud provider is mainly correlated to the energy consumption (Joules). The energy consumption is the sum of power consumptions (per second) during the execution of the workload. As already explained, it has been shown that energy consumption cannot be modeled by a linear function [START_REF] Wu | An intelligent power consumption model for virtual machines under cpu-intensive workload in cloud environment[END_REF], [START_REF] Hsu | Power signature analysis of the specpower ssj2008 benchmark[END_REF] defined by the number of machines and the running time (see Equation 5). As a result, reducing the number of nodes may induce a reduction of the global energy consumption (i.e., the cost) even if the time required to finish the workload is longer. Table II illustrates this claim by showing the results obtained for the four different deadlines in terms of the number of nodes used to schedule the workload, the total makespan needed to run the workload, as well as the energy consumption. In this experiment, unused machines are considered powered off, and nodes are turned off when they have finish their computations. As expected, the makespan increases with the deadline by using V-HEFT-deadline, thus the overall time spent to execute the complete workload is longer than V-HEFT. However, the total energy consumption is almost reduced of 17% when using V-HEFT-deadline compared to V-HEFT. Therefore, the number of nodes has a direct impact on the energy consumption of the Cloud provider. One can note, though, that the execution with D=2, has a cost a bit higher than the execution with the D=1.5, meaning that the diminution of the number of nodes does not always counterbalance the makespan extension.

Performance evaluation. Figure 5 shows the execution time taken by both V-HEFT and V-HEFT-deadline to compute the scheduling solution of the previous experiment. First, one can note that adding a backtrack system in V-HEFTdeadline does not deteriorate the efficiency of the algorithm because V-HEFT-deadline iterates on already used nodes instead of all nodes for V-HEFT. We can compute the number of scheduling operations performed by each algorithm by using the complexity we introduce in Part IV. In the case of the scheduling of 100 workflows, for V-HEFT algorithm, the number of operations is j × n, with j = 100 and n = 20, that is to say 2000 operations -by a factor of 25 which is the number of tasks forming the Montage workflow. For V-HEFT-deadline algorithm, the number of operations depends on the number of nodes under usage when a workflow is scheduled. The number of operations can be estimated by using the values returned by our experiments when scheduling a variable number of workflows (Figure 3). As a result, the number of scheduling operations needed with a deadline D = 1.3 is approximatly 930, which is 46.5%, of the number of operations of V-HEFT algorithm. This number is validated by experiments where the time taken by V-HEFT-deadline algorithm (1.211 seconds) is half the time taken by V-HEFT algorithm (2.423 seconds).

B. Realistic case study

In this section, we evaluate V-HEFT-deadline on a set of more realistic scenarios from both workload and infrastructure perspectives. Experimental setup. First, we consider a multi-site infrastructure composed of three different clusters. This infrastructure is a subset of the Grid'5000 testbed that uses the Renater5 network for communications, which allows inter-cluster communications with a bandwidth of 10 Gbps. Table I gives a description of the three clusters and their associated nodes. Second, the considered type of workload is more heterogeneous and realistic in this experiment. Table III details the considered workloads composed of five different kind of workflows (all available within Pegasus). We assume that, in a real-case, the percentage of complex workflows is less important than simple ones. Finally, benchmarks also use different deadlines for each kind of workflow. In the scenario A the deadlines are approximately the makespan returned by V-HEFT execution.

In the following experiments, each set of workflows are owned by a specific user, i.e., all the pipeline workflows belongs to the first user, Montage workflows belongs to the second one, etc. The four workloads presented in the Table III are submitted twice, meaning that the scheduling algorithm is called two times. Thus, tasks under execution are taken into account in this experiments. The first submission is done at t = 500, and the second one at t = 1500. Finally, at t = 0 half of the nodes are powered on and are half used. This simulated workload ends at t = 1000.

Evaluation. Figure 6 shows the estimated immediate power consumption (in Watt) of the nodes for the execution of the different scenarios (A to D). As for the first experiment V-A, the unused nodes are considered powered off and nodes are powered off as soon as they have finished there tasks. Table IV shows the results obtained for the four different scenarios in terms of the number of nodes, the total makespan and the energy consumption needed to run each workload twice. Moreover, the execution time of the scheduling algorithm is given.

As expected, the global makespan of the solution returned by our algorithm is less good than the makespan of the V-HEFT solution. However, the makespan minimization is not the optimization objectives of V-HEFT-deadline. One can observe that even in the scenario A, where the deadlines are almost the makespan returned by V-HEFT, the number of nodes used to schedule the workload is reduced. Actually, as V-HEFT minimizes the makespan for each task it favours empty nodes that offers the best makespan even when already used nodes offers almost the same makespan. As a result, the nodes are not used at their full capacity (under used). In contrast, our algorithm will favour nodes that are already used, and will smooth the power consumption of the nodes over the time as we can observe in Figure 6.

In the scenarios B and C, one can note that the number of nodes used to schedule the workload is greater than in the scenario A, despite the deadline relaxing of Inspiral workflows. This effect is due to the scheduling at two different times. Indeed, as the first schedule is not aware of the second one, the resources usage of the Inspiral workflows will be smoothed and the local makespan of their execution will exceed the arrival of the second scheduling. This involves a lower number of available resources for the III. scheduling of the second set of workflows at t = 1500, and causes an increase on the number of needed nodes. The last scenario D validates this observation. In this scenario the deadlines of the Pipeline workflows are relaxed to give them more time to be executed even if the resources are used by Inspiral workflows. As expected, the number of used resources is reduced, and the global makespan delayed.

As in the simple evaluation, the total energy consumption observed is directly correlated to the number of nodes used to schedule the workload. In the scenarios B and C, the energy consumption is a bit higher than in A, for the same reasons than explained earlier. In all cases, the energy consumption is reduced compared to the V-HEFT (Table IV).

VI. CONCLUSION

This paper tackles the scheduling of heterogeneous scientific workflows while minimizing the energy consumption of Cloud providers. The V-HEFT-deadline algorithm has been presented as a solution to this scheduling problem. V-HEFTdeadline adds deadlines to workflows so that the number of servers needed to run the workload is reduced, as well as the energy consumption. This algorithm is based on V-HEFT, a variant of HEFT that takes virtualization into account. The V-HEFT-deadline algorithm has been compared to V-HEFT to assess the impact of the deadlines on the energy consumption of the Cloud provider. Experiments have been conducted on different case studies. Experiments on realistic workloads have shown a reduction in the number of nodes by up to 28% for an estimated 10% energy consumption reduction for the Cloud provider. In future work, we plan to improve our model to take into account the dynamic migrations of virtual machines as well as a more complex and realistic network model with limited bandwidth. We also plan to study the benefits of our algorithm in the context of power cap contracts between the Cloud computing provider and the energy provider.

Figure 1 :

 1 Figure 1: Representation of the gain between communication done on the VMs (1) and on the node (2)

Algorithm 2 V

 2 -HEFT-deadline algorithm function V-HEFT-deadline (workf lows, deadlines) workf low list ← SORTWORKFLOWS (workf lows, deadlines) for all d ∈ workf low list do V-HEFT-deadline-WORKFLOW(d.tasks, d.nodes, deadlines[d])

Figure 2 :

 2 Figure 2: Montage workflow

Figure 3 :

 3 Figure 3: Comparison of the number of nodes used between V-HEFT and V-HEFT-deadline (with four different deadlines D).

Figure 4 :

 4 Figure 4: Comparison of immediate power consumption between V-HEFT and V-HEFT-deadline (with four different deadlines D).

Figure 5 :

 5 Figure 5: Comparison of execution time between V-HEFT and V-HEFT-deadline (with four different deadlines D).

Figure 6 :

 6 Figure 6: Comparison of the power consumption through time between the different scenari of TableIII.

  Algorithm 4 V-HEFT-deadline backtrack scheduling

	function SCHEDULEBACKTRACK (backT o, id, tasks, deads, ons, of f s)
	task ← tasks [id]
	deadline ← deads [id]
	if SCHEDULEEARLIEST(task, ons, deadline) then
	if SCHEDULEBACKTRACK(backT o, id+1, tasks,
	deads, ons, of f s) then
	return T rue
	if id = backT o then
	if SCHEDULEEARLIEST(task, ons + of f s, deadline) then
	new ons ← FILTERUSEDNODES(ons + of f s)
	new of f s ← FILTERUNUSEDNODES(of f s)
	if SCHEDULEBACKTRACK(backT o+1, id+1, tasks, deads,
	new ons, new of f s) then
	return T rue
	return F alse

Table I :

 I Description of the simulated nodes

	Location	Name	Number of nodes CPU	Network
	N antes	econome 22	Intel Xeon E5-2660 (Sandy Bridge, 2.20GHz, 2 CPUs/node, 8 cores/CPU) 10 Gbps
	Rennes	parapide	21	Intel Xeon X5570 (Nehalem, 2.93GHz, 2 CPUs/node, 4 cores/CPU)	20 Gbps
	Grenoble	yeti	4	Intel Xeon Gold 6130 (Skylake, 2.10GHz, 4 CPUs/node, 16 cores/CPU)	10 Gbps

Table II :

 II -Results of the scheduling of complete workload composed of Montage workflows.

		V-HEFT		V-HEFT-deadline
	Deadline	-	×1.3	×1.5	×2	×3
	Nb nodes	20	14 (70%)	11 (55%)	8 (40%)	5 (25%)
	Makespan	157	200 (×1.27)	233 (×1.48)	311 (×1.98)	462 (×2.94)
	Energy (Joules)	333,777	298,352 (89.4%)	282,602 (84.7%) 282,887 (84.8%) 278,266 (83.4%)

Table III :

 III -Percentages and deadlines of the workflows composing the workloads

	Name	%	deadlines (A) deadlines (B)	deadlines (C)	deadlines (D)
	Montage	30%	150	150	150	150
	CyberShake 10%	1000	1000	1000	1000
	Inspiral	6%	1500	2000 (×1.3)	2200 (×1.45) 2200 (×1.45)
	Sipht	4%	4000	4000	4000	4000
	Pipeline	50%	250	250	250	400 (×1.6)

Table IV :

 IV -Results of the scheduling of the different scenari

		V-HEFT	deadlines (A)	deadlines (B)	deadlines (C)	deadlines (D)
	Makespan	5202	5422	5422	5422	5431
	Nb nodes	47	35 (74%)	35 (74%)	36 (77%)	34 (72%)
	Time (s)	27.258	9.601 (35.2%)	9.705 (35.6%)	10.185 (37.4%)	9.338 (34.3%)
	Energy (Joules) 9,183,968 8,395,508 (91.4%)	8,487,680 (92.4%)	8,555,411 (93.2%)	8,276,282 (90.1%)

https://www.sallan.org/pdf-docs/McKinsey Data Center Efficiency.pdf

https://seduce.fr/

https://pasillo.renater.fr/weathermap/weathermap metropole.html


Claire Bernard
email: bernard@iamm.fr

Valter Hoxha
email: hoxha@iamm.fr

François Lerin
email: lerin@iamm.fr

From total State to Anarchical Market?

Keywords:

Medicinal and Aromatic Plants (MAPs) is an important sector of the agrarian economy today in Albania, counting for approximately M$25 exports, 60 000 harvesters and collectors, various localized value chains and first transformation industries. Wild MAPs collection mainly occurs in common mountainous pastures and forest lands,. The real economic take off and massive collection the resource occurred during the communist regime, to fulfil the need of export cash-flows. It was a total State organized system structured by cooperatives and State farms. After the regime collapse, the MAPs sector was basically driven by commercial forces and markets. This drastic change is, for the theory of collective action of great interest, because neither one system nor the other totally abolished the existence of the commons as commons.

Methodology and sources used

This paper is based on a twofold methodology. First an enquiry based on original archives from the communist regime period (and secondary sources from before and after); second, on field work done about the actual situation for collection of wild aromatics and medicinal plants, in different part of the country.

Conclusion

Our communication will highlight major institutional problems related to the management of commons throughout the conventions and agreements, organizing the MAPs collection. An historical (and yet not done) analysis of these two antagonist systems, based on field studies for the contemporary situation and on Albanian archives for the past periods (1860-1991) is of great interest for today challenges. Both in terms of rural development and agro-biodiversity conservation, there is a need to find innovative ways for a collective action to sustainably rule these commons. Neither State nor markets are able to deal with identified pressures against MAPs resources.

FONCIMED.

  Réseau CIHEAM-INRA de recherche et d"échange sur le foncier méditerranéen. 10ème Séminaire Annuel "Le foncier, un actif du développement territorial et de la durabilité des communautés rurales?", Thessaloniki, 2-4 Novembre 2017 FONCIMED. Network CIHEAM-INRA for research and exchange on Mediterranean land tenure. 10th Annual Seminar "Land tenure as an asset for territorial development and the sustainability of rural communities?", Thessaloniki, 2-4 November 2017 Séance 3-Le foncier comme bien commun 71


C Douthe¹

M Bagnéris²

L Du

R Mesnil¹

BUILDING FREEFORM: A WORKSHOP EXPERIMENT FROM DESIGN TO FABRICATION

Keywords: Workshop, structural design, Design/build

In the following of an already old tradition of design/build workshops in architecture, the works presented here illustrate an attempt of introducing design/build teaching experiments in structural engineering education. This one-week experiment was conducted yearly during the last nine years at the Ecole des Ponts ParisTech, France. The workshop, called "Building free-form", is organised by founding members of the thin[k]shell project, an academic initiative for mixing advanced research, teaching and practical realisations with industrial partners. This project will be first detailed, because it is essential to the framework and objectives of the workshop. Then the evolution throughout the years of the pedagogy and of the supporting objects (first textile structures, then elastic gridshells) will be detailed. Finally, last year experiment centred on the use of robotic fabrication and its impact on the whole design process will be presented. Main aspects of workshop programs, teaching material and financial issues will be given for each type of structures, as well as some feedback on the various editions.

THE THIN[K]SHELL PROJECT

In the following of an already old tradition of design/build workshops in architecture (see for example the experiments of M. Vrontissi [START_REF] Vrontissi | Architectural Design Methodology informing Structural Design[END_REF] in Volos Greece, those of J. Ramon in Talca Chile [START_REF] Adria | Talca: Matter of education[END_REF], M. Kawaguchi in Tokyo-Japan [START_REF] Kawaguchi | Symposium of IASS 2004, From Models to realization[END_REF]), we present here feedback on an attempt of introducing design/build teaching experiments in structural engineering education at the Ecole des Ponts. We focus on a one-week workshop called "Building freeform", hold yearly during the last nine years.

This workshop is a typical illustration of initiatives hold in the framework of the thin[k]shell project at the Ecole des Ponts. Or, to be more accurate, the educational principles of the thin[k]shell project are a direct emanation of the experience gained in the teaching of the "building freeform" workshop. The spectrum of the project is however wider and extends to expeditions in the field of structural engineering beyond education. It promotes an integrated vision of research, education and fabrication which embraces the whole design process from the very first sketches to the construction of full scale buildings, from material/assembly testing to the development of original numerical tools. The team (about 15 persons) gathered around the development of the first prototypes of elastic gridshells in composite materials [START_REF] Caron | Gridshells in composite materials: Construction of a 300 m² Forum for the Solidays' Festival in Paris[END_REF].

Nowadays, it combines expertise in the field of architecture, material science, structural engineering, historical buildings, architectural geometry and numerical fabrication.

The thin[k]shell project was initiated by members of the laboratoire Navier, but is now developing with fruitful collaborations with partner laboratories (the Geometry and Curvature group of LAMA, the IMAGINE group from Laboratoire d'Informatique Gaspard Monge (LIGM), or the laboratoire Géométrie et Structures pour l'Architecture (GSA) from the School of Architecture Paris-Malaquais) and many industrial partners.

This integrated vision of research, education and fabrication is promoted throughout the courses taught by the members of the project at the Ecole des Ponts (especially the "Structural design" and "Advanced structural design" courses, the "Design by Data" postgraduate program, and the workshops "Crossing my bridge", "Fold me a shelter" or "Building an arch", see figure 1) and in other higher education programs in the schools of Architecture of Grenoble, Paris-Malaquais, Marne-la-vallée. About eight PhD candidates are currently concerned by the design of structures and provide regularly small scale projects related to their research to master students for exploration, experimentation or numerical development. This is beneficial to the candidates who can hence test ideas, process, tools or methodologies before they might be introduced in a larger scale workshop or prototype (this, of course, helps also improving the academic productivity of the team and academic publications). This is also beneficial to the master students who get initiated with up-to-date research, digital fabrication processes or metrological advances and who may then apply for PhD funding.

The concepts with the highest potential get then further developed and come out with full scale realizations associating clients and/or industrial partners. The 3 days' temporary pavilion of the Solidays festival 2011 (see figure 2 left) was led by a group of 8 final year students (a two-semesters adventure with "officially" a half day per week dedicated to the project) and the design office T/E/S/S [START_REF] Caron | Gridshells in composite materials: Construction of a 300 m² Forum for the Solidays' Festival in Paris[END_REF]. The temporary cathedral of Créteil had to hold for two years and therefore required deeper investigation and was thus designed by T/E/S/S and the laboratoire Navier [START_REF] Peloux | Construction of a large composite gridshell structure: a lightweight structure made with pultruded GFRP tubes[END_REF]. Last realization is an exploration of the possibilities offered by developable surfaces for the construction of freeform without formwork or scaffolding (see figure 2 right). 2 THE "BUILDING FREEFORM" WORKSHOP: PAST RECORDS

Pedagogical objectives

The "Building freeform" workshop was thus initiated by a group of academics working in the field of structural design and pretty much influenced by the thoughts of the structural morphology group of the International Association of Shell and Spatial Structures, especially by R. Motro [START_REF] Bagnéris | Structural morphology issues in free form design[END_REF]. In this founder paper, R. Motro explains that structural design is at the frontier of: form (geometry), forces (static), structure (topology and relations between elements), material (mechanical behaviour) and technology (fabrication process). The general idea of the workshop was thus to get the students initiated with the constant compromise that exists in structural design between those five fields and how much it has become necessary to embrace those five fields to succeed in the design of contemporary freeform architecture.

Indeed, this branch of architecture which denotes fascinating doubly curved structures and envelop, seems to be within easy reach thanks to contemporary digital fabrication tools. However, they remain enigmatic and hard to comprehend by the designers, who are often extremely dependent on a technological process in comparison with "classic" buildings where they can really explore various design alternatives. The workshop organization has evolved throughout the years, but it always started with an overview of the possibilities offered by doubly curved structures, both from technological and conceptual perspectives. The major part of the week being then devoted to the design and fabrication of medium to full scale pavilions, with various typologies: tensile structures, then elastic gridshells and finally rigid gridshells.

The tensile structure years

During the first years, the workshop focused hence on the construction of a tensile pavilion with a 10 m² to 30 m² covered surface (see figure 3). Tensile structures were chosen for their didactic aspect because they are very hierarchic structures that allow to address every steps of the design process and every fields of structural design, as well as their interactions:

1. Definition of a form in equilibrium under self-stress (form-force interaction), 2. Definition of the supporting members (force-structure interaction), 3. Dimensioning of members (introduction of material parameters), 4. Definition of the cutting pattern (form-material-technology interaction), 5. Design of details (forces-material-technology interaction), 6. Mounting of the structure (structure-technology interaction). Especially, tensile structures offer the possibility to address all these issues at real scale, to work with the real materials, with realistic details (although knocked up) and with structures larger than human. The physical experiment is thus not biased by any scaling and students encounter all problems linked with structural design from design to fabrication, including control of geometry, management of tolerances and the necessity of tuning.

Practically, the week was organized as shown in table 1. After some introductory conferences, the students start working in groups of three and to prepare pavilion proposals based on physical models and drawings on scale. They defend then their proposal and make critics on the other proposals in order to choose collegially the prize-winners that will be built at full scale. This collective evaluation of proposals was very effective and forced them to stand back to assess the feasibility of the structures that they will all have to build together, based on what they have just learnt about the design of free-form structures. By orienting some questions and explaining clearly the learning objectives of the workshop, democracy always brought an acceptable solution, except once where authority was necessary to rebut a proposal which would have directed all the design effort toward a post design instead of toward tensile architecture… Then, in the second part of the week, the students work all together on one or two structures and experience the necessity for tasks separation, coordination and interoperability of tools or procedures, which is really key in free-form architecture. The workshop started with 15 students in 2009 and ended with 32 in 2015, all final year students (one third from architecture school, the rest from the Civil Engineering department). Supports included experimental facilities, one full time academic per 10 students and about 1000 € consumable: the PVC textile was kindly offered by Serge Ferrari textile. The formfinding and cutting pattern were done with dedicated codes, for Sketch-up and Autocad respectively, provided by the teaching staff.

Extension to elastic gridshells

Considering the success of the tensile structures formula, the authors attempted to apply it to the realization of an elastic gridshell, a structural typology closely linked with their research expertise [START_REF] Caron | Gridshells in composite materials: Construction of a 300 m² Forum for the Solidays' Festival in Paris[END_REF][START_REF] Peloux | Construction of a large composite gridshell structure: a lightweight structure made with pultruded GFRP tubes[END_REF]. The goal was to investigate ways of direct transmission from laboratory to the next generation of engineers. For financial reasons, the experimentations started at reduced scale: first 2x2 m grids made of 5 mm circular GFRP profiles, then 4x4m made of 20 mm bamboo stems and finally a 6x8 m grid made of 10 mm circular GFRP profiles (thanks to the offer of Solution Composites for the composite materials). The themes addressed were very close to those of the textile pavilion:

1. Form-finding, mapping of the grid on the desired surface, 2. Definition of supports (free edge, opening, anchorage…), 3. Sizing of members and structural analysis, 4. Construction process. However, concerning detailing, especially grid connections, the main choices had to be made before the workshop, so that the consumables could be supplied on time. In comparison with the tensile pavilion, an essential part of structural design could not be investigated by the students. This is why the size of the prototype was progressively increased, trying to find a size at which one will shift from mock-up to realistic detailing, with little success (the small size of the grid members did not allow for knocked up details and most of the time pluming pipe connectors were used) until 2016. It is worth mentioning here the "SheltAir pavilion" built by G. Quinn et al in Berlin 2018 where very convincing details with similar circular composite profiles were designed and will certainly inspire future editions of the workshops. 2016 represents indeed a turning year in the workshop organization and pedagogy. Guided by this desire of working at real scale, with real material like for the tensile pavilion, we took the chance to work with two sponsors: Würth France who supplied all the hardware and the Association Filière bois Haut Languedoc Sud Massif Central who provided the premium quality wood for the structure. Thanks to this financial support, it was possible to get over the gridshell size limit and to build a representative structure (50 m² on the ground), with realistic cross-sections (12x48mm), realistic details and a realistic construction process. This size change was not harmless to the pedagogy of the workshop:

materials and consumable still had to be supplied in advanced, -industrial sponsors had expectations on the quality of the results, -working at such scale implies additional workload for fabrication and assembling. Therefore, we decided to reorganize the week and to tell the students a story: the school, owner of the yard, wanted a small pavilion for demonstrating the lab know-how on elastic gridshells, the academic staff had conducted concept design studies and they, the students, had now been selected for conducting the developed and technical designs as well as the fabrication of the pavilion. After the introductory conferences, the results of the preliminary studies that had been conducted during the summer were presented and a notebook with preliminary sketches of all the details was given them. The competition phase of previous editions of the workshop was hence skipped, depriving them of the trial and error experimental way of learning and the associated self-criticism and step back. However, doing so, they were allowed to go deeper into the design and their understanding of the structure and all aspects linked with construction methods. On Tuesday, the 30 students were thus separated into five sub-groups (each supervised by an academic) which had all the charge of some aspect of the final design and had to experiment fabrication to be able then to systematize it:

form and structure (definition of the final form and structural analysis) -bracing (distribution over the structure and design of the tensioning system), -foundation (design of anchorage, including slab characterization and setting-up), -wooden grid (material characterization, framing, connection verification), -covering (design and fabrication of covering casket system in PEHD) Then on Wednesday, a general coordination meeting was organized before producing shop drawings and launching fabrication. Thursday was dedicated to the of the grid, then Friday to the forming, bracing and covering.

To face the production requirements, it was also decided to introduce into the workshop some initiation to digital fabrication: robotized milling for the grid (cutting at length and opening of slotted holes), 3-axes milling cutter for the covering, laser cutter for the tensioning system of the bracing. The goal was not to learn them to master those tools but to understand how they can be used for the standard production of unique pieces and how to calibrate the necessary tolerances and to verify the accuracy of the produced pieces. However, due to the unforeseen high humidity of wood, the pieces got stacked in the conveyer of the milling robot and part of the fabrication at to be done last minute with hand tools: a good introduction to the necessity of redundancy in systems! The 2016 edition was a real success, enthusiastic for all: students, organizers, industrial partners and administration of the school and laboratory who had gained a full scale prototype illustrating the most recent works on elastic gridshells covered with planar quads [START_REF] Douthe | Isoradial meshes: covering elastic gridshells with planar facets[END_REF]. The students enjoyed being part of a large team work, even if the initial design was not their own. Preparation time was however about four times higher (around 6 months in cumulative) and therefore required the mobilization of additional persons for the supervision. This turn out to be very federative for the thin[k]shell group, also very time-consuming.

THE 2017 EDITION

Scientific context and relation with industrial partners

Strengthened by the 2016 experience, we decided to pursue the idea that the workshop could be a way to link closely research and education: while the students learn about structural design, they can also take part in the thoughts of the laboratory on the possibilities offered by digital fabrication to the design of curved envelops. Indeed, in the last three years, considerable effort has been made by the members of the thin[k]shell group to re-appropriate geometry and to integrate the most recent developments of the new born field called "architectural geometry" into practical tools for designers. close collaboration with Prof. L. Hauswirth from the UPEM helped a lot and has still extremely promising prospects, including the organization of workshops for the mathematic students around applications to structural engineering. In parallel to these theoretical developments, the Ecole des Ponts ParisTech invested in two robotic cells for building a Co-Innovation Lab around digital fabrication applied to civil engineering. And hence came naturally the idea that the workshop should illustrate the knowledge of the members on advanced discrete geometry, structural design and robotic fabrication.

The 2017 pavilion is thus based on an original structural system, called shell-nexorade hybrid, which derives from a surface initially meshed by planar quads which is transformed so that members are only connected by pairs [START_REF] Mesnil | Form-finding of reciprocal frames with the method of translations[END_REF] (see figure 6). The pavilion hence tackles main fabrication constraints of free form architecture: covering with quadrilateral panels, straight members, simple T-joints for connection. To achieve this, an intricate game of eccentricities between members (beam-beam and beam-panel) is necessary and realised by the machining by collaborative 6-axes robots of the extremities and the top surfaces of the members. Industrial partners are really key to the project and were associated upstream of the design. As a matter in fact, the authors believe that successful realisations of freeform structures require a collaboration of all actors of the construction process: owner, designer and contractor, from the beginning. All roles are here endorsed by the academic staff of the week, especially that of the contractor which relies on a tailor made production process, but precisely this is where industrial partners were indispensable:

-Simonin SAS, supplied the wood and served as consultant for wood machining, -HAL Robotics, developed the software linking geometry to machine control command, -ABB, set the robotic cell, helped calibrating the robots, guarantying process accuracy, -Würth France, supplied hardware and served as consultant for connection design. All partners attended the workshop and could explain their contribution to the pavilion design and more generally their role into the design process of complex structures. For example, for connections, a screw that goes beyond Eurocode 5 was used because it allows to transmit normal forces along the grain of the wooden member. It was hence an opportunity to introduce in the teaching the procedure of European Technical Agreement and the method for bringing innovation in structural engineering practice.

Pedagogical objectives

Pedagogically, the principle remains the same: the academic staff (2 professors, 5 PhD students and 3 technicians) does the concept and development designs while the students are in charge of the technical design and fabrication/assembly of the pavilion. The week starts with one day conferences about double curved structures, digital fabrication and the concept design of the pavilion. On Tuesday and Wednesday, the students separate in sub-groups:

geometry and structural analysis (interaction between form and forces) -connection (experimental characterization of material and connection capacity, verification of each connection), -construction process and geometric control (3d photogrammetric reconstruction, plumblines as well as triangulation with double decametres) design of anchorage plates, including concrete slab characterization and setting-up), -robotized manufacturing applied to wood machining (analysis of the production process and fabrication of the last members and panels). Each group is co-supervised by an academic and an external partner, which again allows for experience sharing between students, researchers and private industries. Thursday and Friday are then devoted to the assembly of the pavilion.

Contrary to the 2016 edition, no notebook with connection drawings is given to the students, because the 2017 workflow is fully integrated numerically into the 3d modelling environment of Rhinoceros/grasshopper. No shop drawings are produced or printed: the geometry being completely three dimensional, it is directly transformed into machine commands for the robots who mill the beams and bore inclined predrilling holes for screws (see figure 7). This disappearing of drawing is not obvious, and we insisted all the week on the necessity to introduce geometric control procedure and on the difficulty linked with the interoperability of all the numerical developments, which is another key issue for the successful realization of freeform architecture. It must be noticed here that the ambition of building in one week a pavilion that should last for one year and illustrate actual research developments goes beyond a one-week workshop. Time spent for the pavilion was evaluated to approximately 18 months of a full time person, without counting the time of the 32 students during the week. This is a fantastic adventure that truly united the research group and helped progressing technically all the involved PhD students. Students were immersed in an enthusiastic framework and never complained being only a wheel of a complex organization. As a matter in fact, one month after the completion of the workshop, the school celebrated the 20 years of its settlement on the campus and the students of the workshop were the only ones who had the chance to present their work in pecha-kucha plenary session, which they have done brilliantly.

CONCLUSIONS

We presented here a feedback on a design/build workshop lead over the last nine years. This workshop is about structural design with application to doubly curved structures. It aims at experimenting the necessary compromise between form, forces, structure, material and technology in the design process. We insisted on the interest of working at full scale, with the real material (or at least realistic material) for the relevance of the work on detailing and construction process. We explored various situation scenarios to make the students familiar with the various phases from design to fabrication.

Figure 1 :

 1 Figure 1: Design built workshop at Ecole des Ponts: crossing my bridge (left) and fold me a shelter (right), photo by courtesy C.Douthe (left) and A. Lebee (right)

Figure 2 :

 2 Figure 2: Full scale prototype: Solidays forum 2011 (left) and Metal Euplectela Folie (right), photo by courtesy LdPeloux (left) and C. Douthe (right)

Figure 3 :

 3 Figure 3: "El paraiso de la siesta": Lycra model and final structure (photo by courtesy C. Douthe)

Figure 4 :

 4 Figure 4: 2015 edition with mock-up like grid (left) and 2016 edition with its full scale wooden grid (right) (photo by courtesy C. Douthe left and S. Lenne right)

Figure 5 :

 5 Figure 5: Example of preliminary sketch given to the students (left), robotized milling of members (right) (photo by courtesy L. du Peloux (left) & C. Douthe (right))

Figure 6 :

 6 Figure 6: Initial PQ-mesh (left), structure obtained by translation of the edges: the opposite edges of the quads remain co-planar (middle), zoom on resulting eccentricities between members (right)

Figure 7 :

 7 Figure 7: [right] Workflow in the robotic cell: fixed feeder (1), stationary circular saw (2), milling (3-7), fixed wood rooter (8). [left] First row: tool collision detection and second row: toolpath and robot simulation.

Figure 7 :

 7 Figure 7: Photo of participants (staff, partners on side, students in the middle) in front of the 2017 pavilion.

Table 1 :

 1 Typical organisation of the one-week workshop during the first years

	Monday 8h30-10h30: Overview of double curved	14h-16h: Design of textile structures,
		structures (conf. by C. Douthe).	technology, details and standards… (conf. by
		11h00-12h: Form-finding (conf. by C.	M. Bagnéris)
		Douthe).	16h -18h: Presentation of the project and
			team work by group of 3 students.
	Tuesday 8h30 -10h: Design of doubly curved shapes	13h30 -18h : team work by group of 3
		(conf. by M. Bagnéris).	students:
		10h30 -12h: Team work by group of 3 students.	Proposal outlines for the pavilion competition (lycra models and drawing on scale 1/20)
	Wed.	8h30 -10h30: Collective evaluation of	13h30 -18h30: Experiments and fabrication
		proposals by students and staff.	of prototype details, Definition of the cutting
		Collegial choice of prize-winners.	pattern and full scale printing of laise, setting
		10h30 -12h: Team work by group of 10	up of anchorage, etc.
		students: organisation and separation of tasks
		(geometry, details, dimensioning, construction
		process)
	Thursday 8h30 -12h: Finalisation of shop drawing:	13h30 -18h: Fabrication
		Definition of the cutting pattern and full scale
		printing of laise
	Friday	8h30 -12h: Assembly	13h -14h: Tuning of the structure
			14h-15h: Collective evaluation of the built
			object and feedback on the workshop
			15h -17h: Tidying, gathering of production
			(photo, sketches, prototypes, shop drawing,
			reports of team work)