Loris Marchal
email: loris.marchal@ens-lyon.fr

Bertrand Simon
email: bertrand.simon@ens-lyon.fr

Oliver Sinnen
email: o.sinnen@auckland.ac.nz

Frédéric Vivien
email: frederic.vivien@ens-lyon.fr

• O Sinnen

Malleable task-graph scheduling with a practical speed-up model

Keywords: Scheduling, task graph, malleable tasks, speedup model, approximation algorithms, proportional mapping !

Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a theoretical model and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparse matrices and therefore work under the following practical model. Tasks are malleable (i.e., a single task can be allotted a time-varying number of processors) and their speedup behaves perfectly up to a first threshold, then speedup increases linearly, but not perfectly, up to a second threshold where the speedup levels off and remains constant. After proving the NP-hardness of minimizing the makespan of DAGs under this model, we study several heuristics. We propose model-optimized variants for PROPSCHEDULING, widely used in linear algebra application scheduling, and FLOWFLEX. GREEDYFILLING is proposed, a novel heuristic designed for our speedup model, and we demonstrate that PROPSCHEDULING and GREEDYFILLING are 2-approximation algorithms. In the evaluation, employing synthetic data sets and task graphs arising from multifrontal factorization, the proposed optimized variants and GREEDYFILLING significantly outperform the traditional algorithms, whereby GREEDYFILLING demonstrates a particular strength for balanced graphs.

INTRODUCTION

C OMPLEX computations are often described as Directed Acyclic Graphs (DAGs), where nodes represent computational tasks and edges represent dependences between these tasks. This formalism is both very common in the theoretical scheduling literature [START_REF] Drozdowski | Scheduling parallel tasks -algorithms and complexity[END_REF] and sees an increasing interest in High Performance Computing: to cope with the complexity and heterogeneity in modern computer design, many HPC applications are now expressed as task graphs and rely on dynamic runtime schedulers such as StarPU [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF], KAAPI [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multiprocessors[END_REF], StarSS [START_REF] Planas | Hierarchical task-based programming with StarSs[END_REF], and PaRSEC [START_REF] Bosilca | PaRSEC: Exploiting heterogeneity for enhancing scalability[END_REF] for their execution. Even the OpenMP standard now includes DAG scheduling constructs [START_REF]OpenMP application program interface, version 4.0[END_REF].

Task graphs are helpful to express the structure of applications and to take advantage of the potential parallelism they express, sometimes called inter-task parallelism. However, tasks are often coarse grain and each task can be executed in parallel on several processing cores. To achieve good performance, we also want to take into account this intra-task parallelism. There have been a number of studies to mix both sources of parallelism when scheduling task graphs, such as [START_REF] Radulescu | CPR: mixed task and data parallel scheduling for distributed systems[END_REF], [START_REF] Dutot | Scheduling parallel task graphs on (almost) homogeneous multicluster platforms[END_REF]. The main difficulty in this context is to come up with an expressive and yet tractable model for tasks. Task characteristics are summarized through a speed-up function that relates the execution time of a task to the number of processors it is allotted. In the present paper, we focus on a simple model where the speedup function is a continuous piecewise linear function, defined by two thresholds on the processor allotment: before a first threshold, the speedup is perfect, that is, equal to the number of processors; between the two thresholds, it is linear, but not perfect anymore; after the second threshold, it stalls and stays constant. We later show that this models well the performance of linear algebra kernels which are our present concern. This model extends the well-studied simple single-threshold model, with a perfect speedup before the threshold, and constant speedup thereafter. This simplified model has been studied both in theoretical scheduling [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF] and for practical schedulers [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF]. Contrarily to most existing studies, we also assume that tasks are preemptible (a task may be interrupted and resumed later), malleable (the number of processors allocated to a task can vary over time) and we allow fractional allocation of processors. We claim that this model is reasonable based on the following two arguments. Firstly, changing the allocation of processors is easily achieved using the time sharing facilities of operating system schedulers or hypervisors: actual runtime schedulers are able to dynamically change the allocation of a task [START_REF] Hugo | Composing multiple StarPU applications over heterogeneous machines: A supervised approach[END_REF]. Secondly, given preemption and malleability, it is possible to transform any schedule with fractional allocation to a schedule with integral allocation using McNaughton's wrap-around rule [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF] (as shown in Section 3). Hence, we can consider fractional allocations that are simple to design and analyze, and then transform them into integral ones when needed.

The here presented study is motivated and driven by task graphs coming from sparse linear algebra, and especially from the factorization of sparse matrices using the multifrontal method. Liu [START_REF] Liu | The role of elimination trees in sparse factorization[END_REF] explains that the computational dependences and requirements in Cholesky and LU factorization of sparse matrices using the multifrontal method can be modeled as a task tree, called the assembly tree. Our targets are therefore such trees and the experimental evaluation will focus on them. Having that said, the proposed algorithms in this paper are not limited to trees, but apply to series-parallel graphs (SP-graphs) or sometimes to general DAGs. We will describe and analyze them correspondingly for the sake of generality.

The contributions of this paper are as follows. We propose a practical piecewise linear speedup model which is divided into three parts. Up to a first threshold the speedup is perfect, equalling the number of processors. Then it grows linearly, but with a slope < 1 until a second threshold is reached, after which the speedup remains constant. Using such a piecewise linear function to describe the speedup seems a straightforward approximation. Our objective is to demonstrate that such a model is useful to create better schedules, in particular for proving approximation results and for designing novel, more efficient, scheduling heuristics. Section 3 details the model and Section 4 experimentally validates it, demonstrating its ability to more closely follow speedup curves typical for linear algebra kernels. For this model, we show the NP-completeness of the decision problem associated with the minimization of the makespan for a given graph (Section 5). We study previously proposed algorithms PROPMAPPING (Proportional Mapping) which is commonly used by runtime schedulers, and FLOWFLEX and propose model-optimised variants of these algorithms. Further, the novel GREEDYFILLING is proposed, designed for the new speedup model (Section 6). Both, GREEDYFILL-ING and PROPMAPPING are shown to be 2-approximation algorithms. In Section 7 we perform simulations both on synthetic series-parallel graphs and on real task trees from linear algebra applications demonstrating the general superiority of the new GREEDYFILLING and the model-optimised variants of the traditional algorithms.

RELATED WORK

In this section, we thoroughly review the related work on malleable task graph scheduling for models of tasks that are close or similar to our model. We also present some basic results on series-parallel graphs.

Models of parallel tasks

The literature contains numerous models for "parallel tasks"; names and notations vary and their usage is not always consistent. The simplest model for parallel tasks is the model of rigid tasks, sometimes simply called parallel tasks [START_REF] Günther | Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width[END_REF]. A rigid task must always be executed on the same number of processors (that must be simultaneously available). In the model of moldable tasks, the scheduler has the freedom to chose on which number of processors to run a task, but this number cannot change during the execution. This model is sometimes called multiprocessor tasks [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF]. The most general model is that of malleable tasks: the number of processors executing a task can change in any way at any time throughout the task execution. However, numerous articles use the name malleable to denote moldable tasks like, for instance, [START_REF] Günther | Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width[END_REF], [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF], [START_REF] Jansen | An approximation algorithm for scheduling malleable tasks under general precedence constraints[END_REF]. Depending on the variants, moldable and malleable tasks can run on any number of processors, from 1 to p, or each task T i may have a maximum parallelism which is often denoted by δ i [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF]. Furthermore, depending on the assumptions, tasks may be preempted to be restarted later on the same set of processors, or on a potentially different one (pre-emption+migration). It should be noted that the model of malleable tasks is a generalization of the model of moldable tasks with preemption and migration.

An important feature of the models for moldable and malleable tasks is the task speed-up functions that relate a task execution time to the number of processors it uses. Some authors, like Hunold [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF], do not make any assumption on the speed-up functions. More commonly, it is assumed that the task execution time is a non-increasing function of the number of processors [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF], [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF], [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF], [START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF]. Another classical assumption is that the work is a nondecreasing function [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF], [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF], [START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF] -the work is the product of the execution time and of the number of processors used-which defines the model sometimes called monotonous penalty assumptions. Some other works consider that the speed-up function is a concave function [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF]. Several of the models considered in the literature satisfy all above assumptions: non-decreasing concave speed-up function and non-decreasing work. This is for instance the case with the model studied by Prasanna and Musicus [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF] where the processing time p i of task i is p i (k) = pi k α with α being a task-independent constant between 0 and 1 and k the number of allotted processors [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF], [START_REF] Guermouche | Scheduling trees of malleable tasks for sparse linear algebra[END_REF]. Another instance is the simple single-threshold model, that is, the linear model [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF], [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF], [START_REF] Beaumont | Minimizing weighted mean completion time for malleable tasks scheduling[END_REF], [START_REF] Wang | A heuristic of scheduling parallel tasks and its analysis[END_REF], [START_REF] Zinder | Scheduling flexible multiprocessor tasks on parallel machines[END_REF]:

p i (k) = pi k .
Havill and Mao [START_REF] Havill | Competitive online scheduling of perfectly malleable jobs with setup times[END_REF] added to that model an overhead affine in the number of processors used:

p i (k) = pi k +(k -1)c.
This model is also closely related to the Amdahl's law where

p i (k) = p (p) i k +p (s)
i . Amdahl's law is considered in the experimental evaluation of [START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF].

Finally, the number of processors alloted to a task can, depending on the assumptions, either only take integer values, or can also take fractional ones [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF], [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF], [START_REF] Guermouche | Scheduling trees of malleable tasks for sparse linear algebra[END_REF].

Results for moldable tasks

Du and Leung [START_REF] Du | Complexity of scheduling parallel task systems[END_REF] have shown that the problem of scheduling moldable tasks with preemption and arbitrary speed-up functions is NP-hard.

In the scope of the monotonous penalty model, Lepère, Trystram, and Woeginger [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF] presented a 3 + √ 5 ≈ 5.23606 approximation algorithm for general DAGs, and a

3+ √ 5 2
+ ≈ 2.61803 + approximation algorithm for seriesparallel graphs and DAGs of bounded width.

Wang and Cheng presented [START_REF] Wang | A heuristic of scheduling parallel tasks and its analysis[END_REF] a 3 -2 p -approximation algorithm to minimize the makespan while scheduling moldable task graphs with linear speed-up and maximum parallelism δ j (problem P |prec, any, spdp-lin, δ j |C max ).

Havill and Mao [START_REF] Havill | Competitive online scheduling of perfectly malleable jobs with setup times[END_REF] consider the problem of scheduling independent moldable jobs in an online setting, with arbitrary arrival times (note that they use the term malleable). In the model where the processing time is described by

p i (k) = pi k + (k -1)c
, they propose a simple yet efficient algorithm which is in particular a 4-approximation for large k. An improved algorithm has then been proposed by Kell and Havill [START_REF] Kell | Improved upper bounds for online malleable job scheduling[END_REF] for a small number of processors.

Results for malleable tasks

The problem of scheduling independent malleable tasks with linear speedups, maximum parallelism per task, and with integer allotments, that is P |var , spdp-lin, δ j |C max , can be solved in polynomial time [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF], [START_REF] Vizing | Minimization of the maximum delay in servicing systems with interruption[END_REF] using a generalization of McNaughton's wrap-around rule [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. Drozdowski and Kubiak showed in [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF] that this problem becomes NP-hard when dependences are introduced: P |prec, var , spdp-lin, δ j |C max is NP-hard. Balmin et al. [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF] present a 2-approximation algorithm for this problem. Their algorithm builds integral allotments by first scheduling the DAG on an infinite number of processors and then using the optimal algorithm for independent tasks to build an integral-allotment schedule for each interval of the previous schedule during which a constant number of processors greater than p was used. In this paper we extend this result with Corollary 2, showing that this algorithm is also a 2 -δmin p approximation for makespan minimization with fractional allotments (where δ min is the minimum threshold over all tasks).

Makarychev and Panigrahi [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF] consider the problem P |prec, var |C max under the monotonous penalty assumption and when allotments are rational. They provide a (2 + )-approximation algorithm, of unspecified complexity (their algorithm relies on the resolution of a rational linear program; this linear program is not explicitly given). Furthermore, they prove that there is no "online algorithm with sub-polynomial competitive ratio" (an online algorithm is an algorithm that considers tasks in the order of their arrival).

Carroll and Grosu [START_REF] Carroll | Incentive compatible online scheduling of malleable parallel jobs with individual deadlines[END_REF] study the problem of scheduling independent malleable tasks in an online setting, with arbitrary arrival times and deadlines. They use the same processing time as Havill and Mao [START_REF] Havill | Competitive online scheduling of perfectly malleable jobs with setup times[END_REF], and each task comes with a value. They propose an incentive strategy to maximize the sum of the values of the tasks completed before their deadline, hence rational users truthfully declares his parameters.

Series-parallel graphs

Series-parallel graphs can be recognized and decomposed into a tree of series and parallel combinations in linear time [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]. It is well-known that series-parallel graphs capture the structure of many real-world scientific workflows [START_REF] Bharathi | Characterization of scientific workflows[END_REF]. A possible way to extend algorithms designed for series-parallel graphs to general graphs is to first transform a graph into a series-parallel graph, using a process sometimes called SPization [START_REF] González-Escribano | Mapping unstructured applications into nested parallelism[END_REF] before applying a specialized algorithm for SP-graphs. This was for example done in [START_REF] Cordasco | Assessing the Computational Benefits of AREA-Oriented DAG-Scheduling[END_REF]. However, note that no SPization algorithm guarantees that the length of the critical path is increased by only a constant ratio.

APPLICATION MODEL

We consider a workflow of tasks whose precedence constraints are represented by a task graph G = (V, E) of n nodes, or tasks: a task can only be executed after the termination of all its predecessors. We assume that G is a series-parallel graph. Such graphs are built recursively as series or parallel composition of two or more smaller SPgraphs, and the base case is a single task. Trees can be seen as a special-case of series-parallel graphs. A tree can be turned into an SP-graph by simply adding one dummy task without computation cost, that has an edge with every leaf of the tree.

δ (1) i δ (2) i δ (1) i Ω i nb. of processors p speedup s i (p)
Each task T i ∈ V is associated with a weight w i that corresponds to the work that needs to be done to complete the task. By extension, the weight of a subgraph of G is the sum of the weights of the tasks it is composed of. The start time t i of a task T i is defined as the time when the processing of its work starts for the first time. Denoted by p is the total number of identical processors available to schedule G. Tasks are assumed to be preemptible and malleable; each task T i may be allocated a fractional, timevarying amount p i (t) of processors at time t. The speedup of each task, illustrated in Figure 1, is a piecewise linear function of the number of processors allocated to the task. Task T i is associated with two integer thresholds, δ

(2) i , on the number of processors and a maximum speedup Ω i , which define the speed-up of the task:

• for a number of processors smaller than, or equal to, the first threshold, the task is perfectly parallel; • for a number of processors larger than the second threshold, the speedup is bounded by the maximum speedup; • between the two thresholds, the speedup is linear but not perfect. Formally, the speedup function is a continuous piecewise linear function defined as

s i (p) =        p if p ≤ δ (1) i δ (1) i + (p-δ (1) i )(Ωi-δ (1) i ) δ (2) i -δ (1) i if δ (1) i ≤ p ≤ δ (2) i Ω i if p ≥ δ (2) i (1)
The completion or finish time of task T i is thus defined as the smallest value

f i such that fi 0 s i (p i (t))dt = w i .
The objective is to minimize the makespan of the application, that is the latest task finish time.

Model variants. The objective of the proposed threephase model with two thresholds is to accurately match the memory hierarchy: the closer the processors, the faster they can communicate. In the following, we also use a simpler variant of our model with only two phase: when both thresholds are equal (δ

(1) i = δ (2) i ) we necessarily get Ω i = δ (1) i
and we get back to a capped perfect threshold. The problem of minimizing the makespan of a graph with this model is noted P |prec, var , frac, spdp-lin, δ j |C max and is studied in [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF], [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF].

Some of the algorithms presented in this paper also apply to some restricted variants of the problem. A notable one is the case of moldable tasks, which prohibits any variation in the set of processors used by a task: in this case, p i (t) must be constant on some time interval, and null elsewhere.

Other notations. In the following, we will often use the length of the critical path of a task T i , which is defined as the minimum time needed to complete all the tasks on any path from this task to any output task of the graph, provided that an unlimited number of processors is available. This corresponds to the classical notion of bottom-level [START_REF] Sinnen | Task Scheduling for Parallel Systems[END_REF], when the duration of each task is set to w i /Ω i . By extension, the critical path of the entire graph G is the longest critical path of all its tasks.

Extension of McNaughton wrap-around rule

When scheduling tasks with perfect speedup, it is possible to remove the assumption of fractional allocation without degrading the makespan thanks to malleability, using the so-called "Macnaughton wrap-around rule" [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. We adapt here this result to our model with two integer thresholds. For the sake of simplicity, the proof is presented only for two tasks but easily extends to any allocation. Lemma 1. Consider two tasks A and B sharing an integer number of processors p on a given interval M : A (resp. B) is allocated a fractional number of processors p A (resp. p B ). We can produce a schedule with preemption where A and B are allocated integer numbers of processors at all times, and in which both tasks perform the same amount of work.

Proof. We build a schedule where p A (resp. p B ) processors are allocated to task A (resp. B) during t units of time, and p A (resp. p B ) during M -t units of time. t is chosen such that the area dedicated to task A is the same as in the original allocation, which means:

M p A -t = M p A so t = M ( p A -p A ).
The same holds correspondingly for task B. This ensures that we can apply this transformation to both tasks without exceeding the processor limit. Now, we want to prove that in the new allocation, A performs the same amount of work (and correspondingly for B). We denote by s(•) the speedup function of task A. The work done on task A is given by:

t × s( p A ) + (M -t) × s( p A ) = M × s( p A ) -t(s( p A ) -s( p A )) = M s( p A ) - p A -p A p A -p A (s( p A ) -s( p A ))
We know that

p A -p A p A -p A = s( p A ) -s(p A ) s( p A ) -s( p A )
because s is linear between p A and p A , as the thresholds are integer. Finally, we get:

t × s( p A ) + (M -t) × s( p A ) = M × s(p A )
which completes the proof.

Note that this may add a number of preemptions proportional to the number of tasks for each interval.

EXPERIMENTAL VALIDATION OF THE MODEL

In this section, we show that the proposed model is realistic enough to model parallel tasks coming from an actual application. In order to do this, we ran such tasks on a parallel platform of 24 cores. It consists of two Haswell Intel Xeon E5-2680 processors, each one containing 12 cores running at 3.30 GHz, and embeds 128 GB of DDR4 RAM (2133MHz).

To compute the speedup graph as shown in Figure 1, we ran each task with p = 1, . . . , 24 cores. Note that on this platform, the "number of processors" has to be understood as "number of cores". We first tested a dense numerical algebra routine: the dense Cholesky factorization. We noticed that the speedup of such dense tasks was perfect, i.e., equal to the number of cores used, up to using the full platform (p = 24). However, usual parallel applications are not made (only) of tasks with perfect parallelism, and our model precisely aims at taking these speedup limitations into account. Thus, we focused on another linear algebra application, which is the multifrontal QR decomposition of sparse matrices as performed by QR_MUMPS [START_REF] Agullo | Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems[END_REF]. Each task of this application is the QR decomposition of a dense rectangular matrix. For the set of matrices described in Section 7, we computed the size of all the dense QR decompositions associated to its multifrontal QR decomposition. For each of the ten thousand resulting sizes, we timed such a task on p = 1, . . . , 24 cores. Each timing was performed 5 times using random data and we retain the average performance.

In the following, we present the speedup of three tasks which are representative of all possible sizes. The first case, presented in Figure 2a, corresponds to small matrix sizes. The green dots represent the actual speedup measured on the platform. Note that for up to 10 processors, the speedup increases with the number of processors and then the performance decreases and exhibits a larger variability for larger number of processors: when adding too many processors, more time is spent in communicating and synchronizing the processors, which hinders the performance. This behaviour is not unusual; a "smart" implementation of the task would be aware of this and would limit the number of processors to be used to 10, even if more processors are allocated to the task. Thus, we first transform the measured speedup so that it is never decreasing with the number of processors. Formally, this corrected speedup, plotted with blue dots on the figures, is given by:

correctedSpeedup(p) = max k≤p measuredSpeedup(k)
In order to fit our speedup model to this corrected speedup, we computed the values of the parameters (δ (1) , δ (2) , Ω) that minimize the sum of the squares of the distance between the model and the corrected measurements for all p values between 1 and 24. Given the limited range of possible values for the thresholds (which are integers in {1, 2, . . . , 24}) and maximum speedup (in [1; 24]), we decided to simply test all possible values of the parameters (with fixed precision for the maximum speedup) and select the ones that minimize Figures 2b and2c plots the same measured speedup, corrected speedup and fitted model for larger matrices: a medium-size matrix on Figure 2b with one large dimension and one small, and a large matrix on Figure 2c. As expected, we notice that the thresholds increase with the matrix size. For the larger matrices, the second threshold is set to 24 although it would probably be larger on a larger platform. Overall, we notice that the fitting of the model is very accurate, the median coefficient of determination being larger than 0.98 (a value of 1 means a perfect fit). Some of the available algorithms for solving our problem consider the single-threshold variant presented in the previous section. Thus, we also fitted the previous (corrected) speedup measurements with this model, composed of a first perfect linear speedup and then a plateau where the speedup is equal to the threshold. Figure 3 plots the obtained speedup model using the same matrix size as Figure 2a. We see that this model is less accurate, the median coefficient of determination being 0.90: it is too optimistic before the threshold, as the task is not perfectly parallel, and it is too pessimistic after the threshold, as better performance can be reached with a number of cores larger than the threshold.

PROBLEM COMPLEXITY

Task malleability and perfect speed-up make this problem much easier than most scheduling problems. However, quite surprisingly, limiting the possible parallelism with thresholds is sufficient to make it NP-hard. We restrict ourselves here to the model where both thresholds are equal

(δ i = δ (1) i = δ (2) i
= Ω i for all tasks i) as it is already NP-hard. Note that a similar result already appeared in [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF], however its proof is more complex and not totally specified, which makes it difficult to check; this is why we propose this new proof.

Theorem 1. The decision version of the problem of minimizing the makespan is NP-complete.

Proof. We start by proving that this problem belongs to NP. Without loss of generality, we restrict to schedules which allocate a constant share of processors to each task between any two task completions. Note that from a schedule that does not respect this condition, we can construct a schedule with the same completion times simply by allocating the average share of processors to each task in each such interval. Given a schedule that respects this restriction, it is easy to check that it is valid in time polynomial in the number of tasks.

To prove completeness, we perform a reduction from the 3SAT problem which is known to be NP-complete [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. An instance I of this problem consists of a boolean formula, namely a conjunction of m disjunctive clauses, C 1 , . . . , C m , of 3 literals each. A literal may either be one of the n variables x 1 . . . x n or the negation of a variable. We are looking for an assignment of the variables which leads to a TRUE evaluation of the formula.

Instance definition: From I, we construct an instance J of our problem. This instance is made of 2n + 1 chains of tasks and p = 3 processors. The first 2n chains correspond to all possible literals of instance I; they are denoted L xi or L xi and called literal chains. The last chain is intended to mimic a variable "processor profile", that is a varying number of available processors over time for the other chains, and is denoted by L pro . Our objective is that for every pair of literal chains (L xi and L xi ), one of them starts at some time t i = 2(i -1) and the other at time t i + 1. The one starting at time t i + 1 will have the meaning of TRUE. We will construct the chains such that (i) no two chains of the same pair can start both at time t i + 1 and (ii) at least one chain L xi or L xi corresponding to one of the three literals of any given clause starts at time t i + 1.

time processor usage

Lpro

Lx 1 Lx 1 Lx 2 Lx 2 t1 = 0 t2 M -t2 M -t1
Figure 4: Example of a possible schedule for the instance J associated to the formula

x 1 ∨ x 2 ∨ x2 .
For any chain, we consider its critical path length, that is, the minimum time needed to process it provided that enough processors are available. The makespan bound M of instance J is equal to the critical path length of the last chain L pro , and will be specified later. Thus, to reach M , all tasks of L pro must be allocated their threshold, and no idle time may be inserted between them.

In constructing the chains, we only use tasks whose weight is equal to their threshold, so that their minimum computing time is one. Then, a chain is defined by a list of numbers [a 1 , a 2 , . . .]: the i-th task of the chain has a threshold and a weight a i . As a result, the critical path length of a chain is exactly the number of tasks it contains. We define ε = 1/4n and present the general shape of a literal chain L a , where a is either x i or x i :

L a = [1, ε, ε, . . . , ε 2(n-i) , SelectClause(a) 2m tasks , ε, . . . , ε 2(n-i) , 1]
The leftmost and rightmost parts of the chain are dedicated to ensuring that in each pair of literal chains, one of them starts at time t i = 2(i -1) and the other at time t i + 1. The central part of the chain is devoted to clauses, and ensures that for each clause, at least one chain corresponding to a literal of the clause starts at time t i + 1:

SelectClause(a) = [InClause(C 1 , a),ε, . . . , InClause(C m , a), ε]
where:

InClause(C k , a) = [1 -2 3 nε] if a appears in C k [ε] otherwise
In total, the chain L a includes 4n + 2m -4i + 3 tasks. Finally, the profile chain is defined as follows:

L pro =[2, 2 -ε, . . . , 2 -(2n -1)ε 2n tasks , L 10 , L 10 , . . . , L 10 2m tasks , 2 -(2n -1)ε, . . . , 2 -ε, 2 2n tasks ] where L 10 = [1 -( 2 3 n -2)ε, 3ε].
The critical path length of L pro defines M = 2m + 4n. Figure 4 presents a valid schedule for the instance corresponding to the formula (x 1 ∨ x 2 ∨ x 2 ), which corresponds to the assignment {x 1 = x 2 = FALSE}.

From a truth assignment to a valid schedule: assume here that we are given a solution to I, i.e. a truth assignment of its variables: let v i denote the value of variable x i in this assignment. We construct the following schedule for J : for all chains, each task is allocated a number of processors equal to its threshold and no idle time is inserted between any two consecutive tasks. Chain L pro starts at time 0 while chain L xi (respectively L xi ) starts at time t i + 1 if v i is TRUE (resp. FALSE), otherwise it starts at time t i . It is straightforward to check that this schedule is valid. Here, we only concentrate on the most critical part, namely the central part which corresponds to the clauses. We count the number of processors used during time interval [2n + 2(k -1), 2n + 2k] which corresponds to clause C k :

• In the first half of this interval, at most 2 literal chains can have a task of size 1 -2 3 nε since at least one in the three literals of the clause is true. Together with the other literal chains and the profile, the maximum processor occupancy is at most (remember ε = 1/4n):

2 1 - 2 3 nε FALSE literal chains + (2n -2)ε other literal chains + 1 - 2 3 n -2 ε Lpro = 3.
(This is maximum, because 1 -2 3 nε > ε.) • In the second half of this interval, at most 3 literal chains can have a task of size (1 -2 3 nε), which may result in a maximum number of busy processors of: The resulting schedule has a makespan of M and is thus a solution to J . From a valid schedule to a truth assignment: We now assume that instance J has a valid schedule S and we aim at reconstructing a solution for I. First we prove some properties on the starting times of chains through the following lemma. The proof of this lemma has been moved to the web supplementary material. Lemma 2. In any valid schedule S for J , i) each pair of chains L xi , L xi is completely processed during time interval [t i , M -t i ], ii) one of them is started at time t i and the other one at time t i + 1, iii) all tasks of both chains are allocated their threshold, iv) there is no idle time between any two consecutive tasks of each chain.

For each literal chain which starts at time t i + 1, we associate the value TRUE in an assignment of the variables of I, and we associate the value FALSE to all other literals. Thanks to the previous lemma, we know that exactly one literal in the pair (x i , x i ) is assigned to TRUE. Furthermore, not three tasks of size 1 -2 3 nε can be scheduled at time Algorithm 1: PROPMAPPING (G = (V, E, w), p)

1 if top-level composition is series composition of K sub-graphs then 2

Allocate p k = p processors to each subgraph

3 else top-level composition is parallel composition of K sub-graphs G 1 , ..., G K 4 Allocate p k = w G k j w G j p processors to subgraph G k , 1 ≤ k ≤ K, where w G k is weight of G k 5 Call PROPMAPPING (sub-graph k, p k ) for each sub-graph k 2n + 2(k -1)
because of the profile chain L pro , as this would lead to a number of occupied processors of:

3 1 - 2 3 nε 3 FALSE literal chains + (2n -3) ε other literal chains + 1 - 2 3 n -3 ε Lpro = 4 - 2 3 nε = 4 - 1 6 > 3 = p.
Thus, at least one literal of each clause is set to TRUE in our assignment. This proves that it is a solution to I.

HEURISTICS DESCRIPTION AND COMPETITIVE

ANALYSIS

We now move to the description and analysis of three heuristics. Two of them come from the literature (PROPMAPPING and FLOWFLEX) while a third one, called GREEDYFILLING is novel. For both pre-existing heuristics, we present their original version as well as some optimizations for our model.

Performance analysis of proportional mapping

A widely used algorithm for this problem is "proportional mapping" [START_REF] Pothen | A mapping algorithm for parallel sparse cholesky factorization[END_REF]. In this algorithm, a sub-graph is allocated a number of processors that is proportional to the ratio of its weight to the sum of the weights of all sub-graphs under consideration. Based on the structure of the considered SP-graph G, Algorithm 1 allocates a share of processors to each sub-graph and eventually each task. Any given graph G (with SP-graph characteristics) can be decomposed into its series and parallel components using an algorithm from [START_REF] Valdes | The recognition of series parallel digraphs[END_REF], and thus be processed by Algorithm 1. Observe that thresholds are not considered in this proportional mapping.

The schedule corresponding to this proportional mapping simply starts each task as soon as possible (i.e., after all its predecessors have completed), as given in Algorithm 2. Indeed, given the proportional mapping of processors, there are always enough processors available to do that. It is worth noting that the created schedule is compatible with the moldable model: each task uses the same number of processors throughout its entire execution. As such, Algorithm 2 can also be used for the moldable model.

In the case of perfect parallelism (i.e., δ

≥ p, ∀T i ∈ G), there is no idle time as all tasks of a parallel composition terminate at exactly the same time (due to the proportional mapping). Hence, this schedule achieves the optimal Algorithm 2: PROPSCHEDULING (G = (V, E, w, p)

1 Call PROPMAPPING (G, p) to determine p i for each task T i ∈ V 2 foreach T i ∈ V do 3
Start T i with p i processors as soon as possible, i.e., after all its predecessors completed makespan M ∞ = i∈V wi p . For the general case the following theorem holds.

Ωi

Proof. We first note that the optimal makespan when all tasks have perfect parallelism, M ∞ , is a lower bound on the optimal makespan with thresholds M OPT . We have thus M ∞ ≤ M OPT ≤ M and we want to show that M ≤ (1 + r)M OPT .

The critical path cp of G, as defined in Section 3, is a longest path in G, where the length is defined as the sum of the work of each task on the path divided by its maximum speedup, len(cp) = i∈cp wi Ωi . Naturally, the critical path length is another lower bound on the optimal makespan, len(cp) ≤ M OPT .

Consider the schedule produced by PROPSCHEDULING. There is at least one path Φ in G from the entry task to the exit task, with no idle time between consecutive tasks. In other words, on Φ the execution of a task starts when the execution of the preceding task finishes. Such a path always exists because we start tasks as early as possible, so this property is always true between the tasks of a serial composition, and it is true for at least one task in each parallel composition. The execution length of Φ is the makespan M , because it includes no idle time and that it goes from entry to exit task. It is given by

M = i∈Φ w i s i (min{p i , δ (2)
i }) Let us divide the tasks of Φ into two sets: the set A of tasks executed with their threshold processors p i = δ

(2) i and the set B of tasks executed with the allocated number of processors p i < δ

(2) i , with A ∪ B = Φ. We then have M = i∈A w i s i (δ (2) i ) + i∈B w i s i (p i ) = i∈A w i Ω i + i∈B w i s i (p i )
The first term (called M A ) is per definition smaller than or equal to the length of the critical path len(cp). The second term (M B ) consists only of tasks that are executed with their proportionally allocated processors. Therefore, these tasks are allocated as many processors as in the schedule achieving the optimal makespan M ∞ when ignoring thresholds. This means that

M ∞ ≥ i∈B w i p i = i∈B w i s i (p i ) s i (p i ) p i ≥ min i∈B s i (p i ) p i M B
With the definition of the s i 's given in Equation ( 1), we know that functions x → si(x)

x are non-increasing, so min i∈B si(pi) pi

≥ 1 r . Therefore, rM ∞ ≥ M B
We then get the desired inequality:

M ≤ len(cp) + rM ∞ ≤ (1 + r)M OPT .
The complexity of PROPSCHEDULING is O(|V |), as it consists of a simple traversal of the SP-graph.

Optimizations of proportional mapping

The main drawback of PROPMAPPING is that it assumes perfect speedup. When applied to actual tasks with imperfect speedup functions, some tasks may finish later than expected by the algorithm. In some cases, sibling tasks (tasks that share the same successor) may complete earlier, thus leaving some processors idle, which induces performance loss. In order to address this issue, a natural idea is to redistribute the processors left idle by the termination of some task T i to T i 's siblings, that is, to the tasks that share the same successor T j and are still running. This is for example what is done in [START_REF] Hugo | A runtime approach to dynamic resource allocation for sparse direct solvers[END_REF]. We design such an algorithm, called PROPMAPREBALSIBLINGS, which redistributes the processing power of terminated tasks to their siblings, proportionally to the weight of the target tasks.

Note that both the original PROPMAPPING or this optimization are agnostic of both thresholds. Thus, we introduce a new variant of PROPMAPPING called PROPMAPRE-BALTHRESHOLD that takes advantage of the speedup model introduced above. It also consists of redistributing processors left idle when a task terminates while its successor is not ready yet. The main difference with the previous variant is that idle processors are not redistributed only to siblings, but to all currently running tasks for which p i < δ FreeTasks ← FreeTasks ∪ {T }

A novel algorithm: Greedy-Filling

Proportional mapping is a common approach. However, it does not make use of the malleability of tasks and it is restricted to SP-graphs. In this section we study an algorithm, called GREEDYFILLING, which may schedule any DAG and takes advantage of the tasks' malleability. It considers one Algorithm 4: PROPMAPREBALTHRESHOLD (G = (V, E, w, δ (2) ), p,) FreeTasks ← FreeTasks ∪ {T } Algorithm 5: GREEDYFILLING (G = (V, E, w, δ (1) , δ (2) ), p) Remove T k from FreeTasks, add its successors whose predecessors have all completed task at a time and greedily allocates it the largest possible processing power.

We now detail this algorithm, presented in Algorithm 5. First, each task is given a priority. In practice, we use for each task T i its critical path (i.e. bottom-level, see Section 3), as it is a lower bound on the overall completion time once task T i has started. The algorithm builds the schedule in chronological order while maintaining the set of free tasks. The difference is that, instead of sharing the resources according to the weight of tasks, we consider them in the order defined by priorities. We allocate each task T i up to δ

(1) i processors if possible, so as to stay in the perfect parallelism zone. If there are processors in excess, we reconsider the tasks in the same order, increasing their allocation up to δ

(2) i .
It is interesting to note that since the total number of processors p and all thresholds are integers (δ Proof. This proof is a transposition of the classical proof by Graham [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF]. In any schedule produced by GREEDYFILL-ING, let T 1 be a task whose completion time is equal to the completion time of the whole task graph. We consider the last time t 1 prior to the start of the execution of T 1 at which not all processors were fully used. If the execution of T 1 did not start at time t 1 this is only because at least one ancestor T 2 of T 1 was executed at time t 1 . Then, by induction we build a dependence path Φ = T k → . . . → T 2 → T 1 such that all processors are fully used during the execution of the entire schedule except, maybe, during the execution of the tasks of Φ.

(1) i , δ (2) i ∈ N, ∀T i ∈ V ),
We consider the execution of any task T i of Φ. At any time during the execution interval(s) of T i (due to malleability it might be executed in disconnected intervals), either all processors are fully used, or some processors are (partially) idle and then, because of Step 9, δ

i processors are allocated to T i . Therefore, during the execution of T i , the total time during which not all processors are fully used is at most equal to wi Ωi and there are at most p -δ

(2) i idle processors. Let Idle denote the sum of the idle areas in the schedule, i.e., idle periods multiplied by idle processors. Then we have:

Idle ≤ k i=1 w i Ω i × (p -δ (2)
i ) ≤ (p -δ (2) min )
× k i=1 w i Ω i ≤ (p -δ (2) min )len(cp) ≤ (p -δ (2)
min )M OPT . Let Used denote the sum of the busy areas in the schedule. As s i is concave (cf. Equation (1), the busy area dedicated to schedule the task T i is maximized when T i is allocated to δ (2) i processors. Then, the area is equal to

δ (2) i wi Ωi and Used ≤ i δ (2) i w i Ω i . Now, let r = max i δ (2) i
Ωi . Note that M OPT ≤ i wi p . Then we have:

Used ≤ i w i r ≤ rpM OPT .
Let M be the makespan of the considered schedule. Then we have:

M = 1 p (Idle + Used ) ≤ 1 + r - δ (2) min p M OPT .
Note that the above proof makes little reference to how the schedule of G has been constructed. The only important characteristic is that the algorithm never leaves a processor deliberately idle if there are tasks that could be scheduled. Hence, the above approximation factor will also apply to other algorithms which adhere to that characteristic: Corollary 1. Any scheduling algorithm which never deliberately leaves a processor idle if it could benefit to any available task is a

1 + r -δ (2)
min /p approximation for makespan minimization, with δ

(2) min = min Ti∈V δ (2) i and r = max i δ (2)
i /Ω i . The proof of Theorem 3 can easily be adapted to the single threshold model, which gives the following result. This is particularly useful to prove that the FLOWFLEX algorithm, presented below, is an approximation algorithm.

Corollary 2. In the single threshold model (δ

i = δ (1) i = δ (2) i = Ω i ),

The FlowFlex algorithm

We now introduce FLOWFLEX, a scheduling algorithm introduced in [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF] and designed for a model similar to the single threshold variant described in Section 3, which considers that

δ i = δ (1) i = δ (2) i
= Ω i for all tasks i. FLOWFLEX first allocates to each task its maximal number of processors δ i , as if there was an infinite number of processors available. Then, in each time interval where the allocation is constant, if the total number of allocated processors exceeds p, the allocation is scaled down proportionally. This algorithm is detailed in Algorithm 6.

In its original version, FLOWFLEX assumes a perfect speedup before the threshold. Thus, scaling down the shares of the tasks proportionally preserves the simultaneous completion of the amount of work performed in the original interval. This is no longer true with imperfect speedup functions. This is why we introduce an optimized version FLOWFLEXREBALANCE that redistributes idle processors among running tasks once a task completes the amount of work it had to process in a given interval. The redistribution is done proportionally to the thresholds δ i , which corresponds to the original allocation before scaling. This optimized variant is described in Algorithm 7.

The

EXPERIMENTAL COMPARISON

In this section we compare through simulation the new heuristic (GREEDYFILLING), reference heuristics (PROPMAPPING and FLOWFLEX) and the proposed extensions of these reference heuristics (PROPMAPREBALTHRESHOLD, PROPMAPREBALSIBLINGS and FLOWFLEXREBALANCE). These simulations use either synthetic graphs of synthetic tasks, or actual task trees whose task execution times were recorded through actual executions, as detailed below. Each algorithm has been simulated in C++: given a graph of tasks, and a speed-up function for each task, the schedule is computed. We compare all heuristics through their makespan (total completion time). Redistribute p k over the pj of the tasks of L, proportionally to their threshold δ (2) 16 until L is empty

Datasets

First, we consider a set of 30 synthetic random SP-graphs composed each of 200 nodes. In order to compute a random SP-graph of x > 1 nodes, we follow the following recursive strategy: toss k uniformly in [1, x -1]; with a probability of 1/2, build a series composition of two random SP-graphs of respectively k and x -k nodes and, otherwise, build a parallel composition of these graphs. Then, in order to generate a random task (i.e., a random graph of x = 1 node), we choose its weight w uniformly in [1; 1000]. The first threshold, δ (1) , is defined by δ (1) = w/100 ; hence, δ (1) ∈ [1; 10]. The second threshold, δ (2) , is uniformly drawn in [δ (1) , 2δ (1) ]. The slope between the thresholds is uniformly drawn in [0.5, 1]. Therefore, in this dataset (called SYNTH), each task perfectly follows our speedup model. Second, we consider a set of 24 trees whose size vary from 39 to 5900 nodes. These elimination trees have been generated (with either colamd [START_REF] Davis | A column approximate minimum degree ordering algorithm[END_REF] or scotch [START_REF] Pellegrini | Sparse matrix ordering with Scotch[END_REF] ordering) using QR_MUMPS [START_REF] Agullo | Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems[END_REF] on matrices from the University of Florida Sparse Matrix Collection [START_REF] Davis | The university of florida sparse matrix collection[END_REF], such that each task of a tree corresponds to the dense QR factorization of the associated matrix. The completion time of a task solely depends on the dimensions of the matrix. In order to determine the actual behavior of such a task, we benchmarked the time necessary to perform this task for a number of processors ranging from 1 to 24, as detailed in Section 4. Thus, in this dataset (called TREES), a task is characterized both by its parameters in our model (δ (1) , δ (2) and Ω) and by the set of its completion times recorded through actual executions for up to 24 processors. The actual execution times are used in the experiments to determine the finish times of the scheduled trees (makespans).

Results

In order to compare the performance of these algorithms, we use a generic tool called performance profile [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. For a given dataset, we compute the performance of each heuristic on each graph and for each considered value for the total number of available processors (namely 1, 2, 4, 6, 8, 10, 12, 16, 20 and 24). Then, instead of computing an average above all the cases, a performance profile reports a cumulative distribution function. Given a heuristic and a threshold τ expressed in percentage, we compute the fraction of test cases in which the performance of this heuristic is at most τ % larger than the best observed performance, and plot these results. Therefore, the higher the curve, the better the method: for instance, for an overhead τ = 5%, the performance profile shows how often a given method lies within 5% of the smallest makespan obtained.

In Figure 5, we present the performance profiles for the SYNTH dataset on the left, and the makespan obtained by each heuristic on a sample graph on the right. On this latter plot, the y-axis has been normalized by the classical lower bound on makespan: the maximum of the critical path and of the total work divided by the number of processors.

The first result is that GREEDYFILLING clearly outperforms the other algorithms: it has the best result in almost 95% of the test cases. On the other hand of the spectrum, FLOWFLEX and PROPMAPPING are the two worst heuristics. Both of them are clearly outperformed by their variants. Of all these variants, the best one is obviously PROPMAPRE-BALTHRESHOLD which achieves very good performance. Although the difference with GREEDYFILLING is striking, one should remark that PROPMAPREBALTHRESHOLD achieves a makespan within 5% of the best one in more than 93% of the instances. The overall hierarchy could have been expected as GREEDYFILLING is the only heuristic to be aware of both thresholds, and among the other, only PROPMAPREBALTHRESHOLD makes use of δ (2) . In turn these results suggest that the proposed speedup model with two thresholds can be used effectively to shorten the produced schedules.

The right-hand side of Figure 5 presents the typical results for a sample graph. The respective performance of heuristics is roughly independent of the number of available processors, and GREEDYFILLING presents the best results. Maximal overhead Fraction of test cases Figure 6: Performance profiles for up to 24 processors on TREES. Note the scale difference to Figure 5.

Overall, the shape of the curves were predictable: when there are very few available processors, there is little possibility of wasting computational resources and all heuristics achieve near-perfect performance; when the number of processors is very large all heuristics that are aware of the second threshold provide similar processor allocation and achieve similar near-perfect performance. The hardest part is in the intermediate zone when the most significant differences can be observed.

We present the performance profile for the TREES dataset in Figure 6, with additional representative samples in Figures 7 and 8. The legend of these graphs is the same as the one of Figure 5. The first observation to be made is that the difference between the graphs has significantly decreased. For each of the four heuristics GREEDY-FILLING, PROPMAPREBALTHRESHOLD, PROPMAPREBAL-SIBLINGS, and FLOWFLEXREBALANCE, in 80% of the cases the overhead is at most 2% and in 63% of the cases it is at most 1%.

An explanation for this is that the trees of this dataset often contain a task (near the root one) whose completion time is far beyond the rest of the graph, as illustrated on the right in Figures 7 and8.

Within the small difference between the algorihtm, the results are similar to the previous data set (ignoring GREEDYFILLING for the moment): FLOWFLEX and PROPMAPPING are the two worst heuristics; both heuristics are clearly outperformed by their variants; PROPMAPRE-BALTHRESHOLD achieves the best performance among these variants, but this time the performance of PROPMAPRE-BALSIBLINGS is almost indistinguishable from that of PROPMAPREBALTHRESHOLD. GREEDYFILLING also performs better than the previously proposed algorithms FLOWFLEX and PROPMAPPING, but its relative performance compared with the proposed variants has changed: its performance on actual trees (Figure 6) is now slightly behind these variants, when it was clearly the best solution on synthetic ones (Figure 5). The better performance of PROPMAPREBALSIBLINGS compared to GREEDYFILLING may be surprising because PROPMAPREBALSIBLINGS does not have any knowledge on the computed (estimated) thresholds. This performance is actually due to the structure of the graphs, as detailed below.

One should recall that the performance profiles gather results over the whole dataset. Varying performance of an algorithm can depend upon the structure of the tree and the processing power available. GREEDYFILLING achieves very good results when the structure of the graph is wellbalanced, which is generally the case in the SYNTH dataset (Figure 5) as the graphs are generated recursively, as well as in the actual tree of Figure 7. This remark comes from the fact that GREEDYFILLING tries to maximize the efficiency of the allocation from the beginning of the schedule: if possible, it limits the allocation to every task to its first threshold, so that the overall speedup remains perfect. This explains why GREEDYFILLING is the best heuristic for medium numbers of processors in Figure 7: the tree is well-balanced, and for this range of processors, maintaining a perfect speedup is more efficient than balancing the allocation in the way PROPMAPREBALSIBLINGS does. However, GREEDYFILLING performance degrades relatively when some branches in the tree are far from being critical and should have their execution delayed, even if this means exceeding the first threshold on other tasks and having a non-perfect speedup. Therefore it only achieves average performance on the TREES dataset (Figure 6), where other heuristics frequently have slightly better performance. For instance, the tree of Figure 8 has a highly critical branch on the right side, and GREEDYFILLING does not allocate enough processors to this branch at the beginning of the schedule, which leads to performance worse than that of the simple PROPSCHEDU-LING for average numbers of processors. With few processors, GREEDYFILLING fully prioritizes the critical branch as the first thresholds are not reached yet, and therefore achieves very good performance. In such a tree and with sufficient processing power, PROPMAPREBALSIBLINGS and PROPMAPREBALTHRESHOLD are the better choice as they progress quicker on the critical branches.

PROPMAPREBALTHRESHOLD achieves very good performance for synthetic graphs and is then only surpassed by GREEDYFILLING. It also achieves the best performance (with PROPMAPREBALSIBLINGS) for actual graphs. Therefore, PROPMAPREBALTHRESHOLD is never a bad choice (for the tested configurations). No other heuristic has this characteristic. One can also note that if PROPMAPREBALSIB-LINGS achieves rather bad performance for synthetic graphs, it represents one of the best heuristics for actual graphs. This heuristic furthermore presents a practical advantage over PROPMAPREBALTHRESHOLD, whose effect is not taken in account in our model: it preserves the locality of the computations, allocating idle processors on tasks from the same branch as the node they were executing.

In order to measure the benefits of the double-threshold model, we adapted GREEDYFILLING, which first allocates each free task to their threshold, before distributing the processors in excess among the free tasks, to the single threshold model. In order to simulate this variant on both datasets, we have computed for each task the value of the single δ j threshold that fits the best the measured speedup, see Section 4. We then compare in Figure 9 the performance of GREEDYFILLING in the single-threshold model and the double-threshold model. The single-threshold model leads, as expected, to a lower performance. On the SYNTH dataset, the double-threshold model obtains better results than the single threshold model for more than 80% of the test cases. This proportion is equal to around 70% for the TREES dataset. The improvement is more important on the SYNTH dataset, because, as discussed previously, the structure of the trees in the dataset TREES impacts the performance of GREEDYFILLING. On both settings, GREEDYFILLING significantly benefits from the better accuracy of the doublethreshold model. Note that in the case of the SYNTH dataset, the improvement of GREEDYFILLING over the other heuristics (as illustrated of Figure 5) is mainly due to the use of the double-threshold model: with the single-threshold model, GREEDYFILLING would perform much worse, comparabily to the other heuristics.

CONCLUSION

In this paper, we have proposed a simple, but practical speedup model for graphs of malleable tasks, which is an interesting trade-off between tractability and accuracy. We have first provided an NP-hardness proof of the makespan minimization problem under this model. This was followed by a study of heuristic solutions, where we proposed modeloptimized variants of the existing algorithms PROPMAP-PING and FLOWFLEX. Designed for the new speedup model, we also proposed the novel GREEDYFILLING algorithm and demonstrated that GREEDYFILLING and PROPMAPPING are 2-approximation algorithms. To evaluate the algorithms, we performed simulations both on synthetic series-parallel graphs and on real task trees from linear algebra applications. They demonstrated the general superiority of the new GREEDYFILLING and the model-optimised variants of the traditional algorithms. In general, employing the new speedup model helps to improve the scheduling results. In a future work, a similar study could be conducted for computing systems that do not allow to reconfigure task mapping, i.e., for moldable tasks.

Figure 1 :

 1 Figure 1: Illustration of the proposed speedup model and its notations.

Figure 2 :

 2 Figure 2: Speedup and fitted model for different matrix sizes

Figure 3 :

 3 Figure 3: Speedup and single-threshold model for matrix size 1984x1834.

Theorem 2 .

 2 PROPSCHEDULING is a (1 + r)-approximation algorithm for makespan minimization where r = max i δ (2) i

  redistribution is done according to the weight of the tasks. Both variants are detailed in Algorithm 3 and Algorithm 4, and have a complexity of O(|V | 2 ).

Algorithm 3 : 4 t 5 foreach task Ti ∈ FreeTasks do 6 allocate pi processors to Ti until time t 7 FreeTasks ← FreeTasks \ {Tn} 8 foreach task Ti ∈ FreeTasks siblings of Tn do 9 pi ← pi + share of pn proportional to the weight of Ti 10 foreach

 345678910 PROPMAPREBALSIBLINGS (G = (V, E, w), p)1 Call PROPMAPPING (G, p) to determine pi for each task Ti ∈ G 2 FreeTasks ← source tasks 3 while FreeTasks = ∅ do ← time when the first task Tn ∈ FreeTasks is completed using pn processors T ∈ successors(Tn) such that T has no unprocessed predecessors do 11

Theorem 3 .

 3 all allocated processors p i are integers too. GREEDYFILLING is a 1 + r -

  any scheduling algorithm which never deliberately leaves a processor idle if it could benefit to any available task is a 2δmin p approximation for makespan minimization where δ min is the smallest threshold among all tasks. The complexity of GREEDYFILLING is O(|V | 2 ) as the main loop is iterated O(|V |) times, going over O(|V |) tasks each time. The total management and ordering of FreeTasks can be done in O(|V | log |V |), e.g. with a priority queue.

  complexity of FLOWFLEX is O(|V | 2 ) as there are at most |V | constant intervals, and each iteration of the main loop is linear in |V |. The complexity of FLOWFLEXRE-BALANCE O(|V | 3 ) as the redistribution procedure is done linearly in |V |.

Algorithm 6 :

 6 FLOWFLEX (G = (V, E, w, δ), p)

Figure 5 :

 5 Figure5: Performance profiles for up to 24 processors on SYNTH (left, where the best performance is top-left) and performance of the heuristics on a sample graph (right, where the best performance is bottom). Note that the following figures use the same legend.

Figure 7 :

 7 Figure 7: Performance of the heuristics and visual representation of the tree lp-nug30-colamd, where the area of a node is proportional to its sequential execution time.

Figure 8 :

 8 Figure 8: Performance of the heuristics and visual representation of the tree GL7-d24-scotch, where the area of a node is proportional to its sequential execution time.

Figure 9 :

 9 Figure 9: Performance profiles comparing the performance of GREEDYFILLING with the double-threshold model and the single-threshold model, on both datasets.

1

  Call PROPMAPPING (G, p) to determine pi for each task Ti ∈ G 2 FreeTasks ← source tasks 3 while FreeTasks = ∅ do 4 foreach task i ∈ FreeTasks do Surplus i ← 0

	5 6	Surplus ← p -i∈FreeTasks pi foreach Ti such that pi < δ (2) i do
	7	p i ← pi+(share of Surplus proportional to the
		weight of Ti)
	8	t ← time when the first task Tn ∈ FreeTasks is
		completed with p n processors
	9	foreach task i ∈ FreeTasks do
	10	allocate p i processors to Ti until time t
	11	FreeTasks ← FreeTasks \ {Tn}
	12	foreach T ∈ successors(Tn) such that T has no
		unprocessed predecessors do
	13

13 foreach Tj in L do 14 pj

  ← schedule obtained by allocating δ i processors to T i and starting tasks as soon as they are free 2 Sort tasks by non-decreasing completion times t i / * We assume t i ≤ t i+1 , t 0 = 0. I is number of allocation constant intervals * / 3 t ← 0 4 for i = 0 to I do 5 foreach T j do work j ← amount of work completed by task T j in interval [t i ; t i+1 ] of S 6 L ← set of tasks T j such that work j > 0 Starting at time t, allocate p j processors to T j until it completes work j at some time t j ← schedule obtained by allocating pi processors to Ti and starting tasks as soon as they are available 2 Sort tasks by non-decreasing completion times ti / * We assume ti ≤ ti+1 and t0 = 0 * / 3 t ← 0 4 for i = 0 to n -1 do Tj do work j ← amount of work completed by task Tj in interval [ti; ti+1] of S. ← set of tasks Tj such that work j > 0 Starting at time t, allocate pj processors to each Tj ∈ L until one task T l completes a work of work l ← pj + p l × δj/ k∈L δ k

	7	foreach T j in L do
	8	p j ← p × δ j / k∈L δ k
	9
	10	t ← max j∈L t j
	Algorithm 7: FLOWFLEXREBALANCE (G DAG =
	(V, E, w, δ), p)
	7	foreach Tj in L do
	8	pj ← p × δj/ k∈L δ k
	9	repeat
	10
	11	t ← time when task T l has completed the work
		work l
	12	Remove T l from L
	15

1 S 1 S 5 foreach 6 L

ACKNOWLEDGMENTS

The authors would like to thank Abdou Guermouche for providing the QR-MUMPS datasets as well as technical support for the experimental work. This work was partially supported by the SOLHAR project and by the LABEX MILYON (ANR-10-LABX-0070), both being operated by the French National Research Agency (ANR). Experiments presented in this paper were carried out using the PLAFRIM experimental testbed (https://www.plafrim.fr/), being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d'Aquitaine, Université de Bordeaux and CNRS (and ANR in accordance to the programme d'investissements d'Avenir).