Safia Kedad-Sidhoum

Florence Monna

Grégory Mounié

Denis Trystram

Scheduling Independent Tasks on Multi-Cores with GPU Accelerators

More and more computers use hybrid architectures combining multi-core processors and hardware accelerators like GPUs (Graphics Processing Units). We present in this paper a new method for scheduling efficiently parallel applications with m CPUs and k GPUs, where each task of the application can be processed either on a core (CPU) or on a GPU. The objective is to minimize the makespan. The corresponding scheduling problem is NP-hard, we propose an efficient approximation algorithm which achieves an approximation ratio of 4 3 + 1 3k . We first detail and analyze the method, based on a dual approximation scheme, that uses a dynamic programming scheme to balance evenly the load between the heterogeneous resources. Finally, we run some simulations based on realistic benchmarks and compare the solution obtained by a relaxed version of this method to the one provided by a classical greedy algorithm and to lower bounds on the value of the optimal makespan.

Introduction

Most of the computing systems available today include parallel multi-core chips sharing a large memory with additional hardware accelerators. There is an increasing complexity within the internal nodes of such parallel systems, mainly due to the heterogeneity of the computational resources. In order to take advantage of the benefits offered by these new features, effective and automatic management of the hybrid resources will be more and more important for running applications. These new architectures have given rise to new scheduling problems. The main challenge is to create adequate generic methods and software tools that fulfill the requirements for optimizing the performances.

There exist in the literature a huge number of papers dealing with implementations of specific applications using GPUs or hybrid CPU-GPU architectures. They consist mostly in studying the gains and performances of the parallelisation of some specific numerical kernels [START_REF] Song | Enabling and scaling matrix computations on heterogeneous multi-core and multi-gpu systems[END_REF] or specific applications like multiple alignments of biological sequences [START_REF] Boukerche | A hardware accelerator for the fast retrieval of dialign biological sequence alignments in linear space[END_REF], molecular dynamics, etc. Moreover, most of existing scheduling algorithms and tools are not well-suited for general purpose applications since the architecture of the GPUs differs from CPUs and thus, the GPUs should be considered as a new type of resources to develop efficient approaches. New features have been implemented in some parallel programming environments and runtime systems: they provide hybrid (CPU/GPU) programming operators, automatic scheduling and adequate data movements. For instance, OmpSs [START_REF] Bueno | Productive programming of gpu clusters with ompss[END_REF], StarPU [START_REF] Augonnet | Starpu: A unified platform for task scheduling on heterogeneous multicore architectures[END_REF] or xKaapi [START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF] include scheduling policies that are restricted to fast greedy algorithms or work stealing.

Our objective within this work is to propose a new algorithm for a general purpose scheduling for the execution of independent tasks on hybrid CPU-GPU architectures designed for High Performance Computing (HPC). The considered input is a set of independent sequential tasks whose execution times are known. This hypothesis is realistic, since some computing platforms such as StarPU have a module which estimates at compile time the different execution times of the considered tasks. The method that we propose in this work determines the allocation and schedule of the tasks to the computing units, CPUs and GPUs. We analyze in detail this methodology for the case of m cores (CPUs) and k GPUs. This leads to an efficient approximation algorithm which achieves a ratio 4 3 + 1 3k + ǫ using dual approximation [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems theoretical and practical results[END_REF] with a dynamic programming scheme. The cost of the algorithm is in O n 2 k 3 m 2 . As this method is costly, we derive a relaxed algorithm and compare it experimentally with one of the most popular algorithm (HEFT [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF]).

The outline of the paper is as follows. In Section 2, a formal description of the scheduling problem with k GPUs is provided and some related works are presented. We propose in Section 3 a new approach for solving the problem and its analysis in Section 4. We report the results of experiments in Section 5 where a relaxed version of our method is compared to the classical HEFT algorithm on simulations built from realistic workloads. The experimental analysis shows that the proposed method has a more stable behavior than HEFT for a similar performance. Finally, some perspectives are discussed in Section 6.

Problem Definition and Related Works

We consider a multi-core parallel platform with m identical CPUs and k identical GPUs. The m CPUs are considered independent from the GPUs that are commanded by some extra driving CPUs, not mentioned here because they do not execute any task. An application is composed of n independent sequential tasks denoted by T 1 , . . . , T n . Each of these tasks has two processing times depending on which type of processor it is allocated to. The processing time of task T j is denoted by p j if T j is processed on a CPU and p j if it is processed on a GPU. We assume that both processing times of a task are known in advance (or at least can be estimated at compile time). The makespan is defined as the maximum completion time of the last finishing task. For the problem considered, in the optic of High Performance Computing, the objective is to minimize the makespan of the schedule. The problem will be denoted by (P m, P k) || C max .

Observe that if both processing times are equal (p j = p j ) for j = 1, . . . , n, (P m, P 1) || C max is equivalent to the classical P || C max problem, which is NP-hard. Thus, the problem of scheduling with GPUs is also NP-hard and we are looking for efficient approximation algorithms.

(P m, P k) || C max is a special case of R || C max . Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF] propose a PTAS for the problem R || C max with running time bounded by the product of (n + 1) m/ǫ and a polynomial of the input size. Let us notice that if parameter m is not fixed, then the algorithm is not fully polynomial. The authors also prove that unless P = N P , there is no polynomial-time approximation algorithm for R || C max with an approximation factor less than 3/2 and present a 2-approximation algorithm. This algorithm is based on rounding the optimal solution of the preemptive version of the problem. Shmoys and Tardos [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] generalize this technique to obtain the same approximation factor for the generalized assignment problem. Furthermore, they generalize the rounding technique to hold for any fractional solution. Recently, Shchepin and Vakhania [START_REF] Shchepin | An optimal rounding gives a better approximation for scheduling unrelated machines[END_REF] introduce a new rounding technique which yields an improved approximation factor of 2 -1 m . This is so far the best approximation result for R || C max . If we look at the more specific problem of scheduling unrelated machines of few different types, Bonifaci and Wiese [START_REF] Bonifaci | Scheduling unrelated machines of few different types[END_REF] present a PTAS to solve this problem. However, the time complexity of the polynomial algorithm is not provided so that the algorithm does not seem to be potentially useful from a practical perspective. Finally, it is worth noticing that if all the tasks of the addressed problem have the same acceleration on the GPUs, the problem reduces to a Q || C max problem, with two machines speeds. The first PTAS for Q || C max was given by Hochbaum and Shmoys [START_REF] Hochbaum | A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach[END_REF]. The overall running time of the algorithm is O((log m + log(3/ǫ))(m/ǫ)(n/ǫ)1/ǫ).

Our objective within this work is to build a bridge between purely theoretical algorithms with good performance guarantees and practical low cost heuristics. Thus, we propose a tradeoff solution with a provable performance guarantee and a reasonable time complexity.

Rationale of the solving method

The principle of the algorithm is to use the dual approximation technique [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems theoretical and practical results[END_REF]. A g-dual approximation algorithm for a generic problem takes a real number λ (guess) as an input and either delivers a schedule of makespan at most gλ, or answers correctly that there exists no schedule of length at most λ.

We target g = 4 3 + 1 3k . Let λ be the current real number input for the dual approximation. In the following, we assert that there exists a schedule of length lower than λ. Then, we have to show how it is possible to build a schedule of length at most 4λ 3 + 1 3k . The idea of the algorithm is to partition the set of tasks on the CPUs into two sets, each consisting in two shelves, a first set with a shelf of length λ and the other of length λ 3 , and a second set with two shelves of length 2λ 3 . The partition ensures that the makespan on the CPUs is lower than 4λ 3 . The same partition can be applied to the set of tasks on the GPUs. Since the tasks are independent, the scheduling strategy is straightforward when the assignment of the tasks has been determined and yields directly a solution of length at most 4λ 3 . The main problem is to assign the tasks in each shelf on the CPUs or on the GPUs in order to obtain a feasible solution. The way to determine the partition is described in Section 4.2.

Theoretical Analysis

Structure of an Optimal Schedule

We introduce an allocation function π(j) of a task T j which corresponds to the processor where the task is processed. The set C (resp. G) is the set of all the CPUs (resp. GPUs). Therefore, if a task T j is assigned to a CPU, we can write π(j) ∈ C. We define W C as being the computational area of the CPUs on the Gantt chart representation of a schedule, i.e. the sum of all the processing times of the tasks allocated to the CPUs:

W C = j / π(j)∈C p j .
To take advantage of the dual approximation paradigm, we have to make explicit the consequences of the assumption that there exists a schedule of length at most λ. We state below some straightforward properties of such a schedule. They should give the insight for the construction of the solution.

Property 1. In an optimal solution, the execution time of each task is at most λ, and the computational area on the CPUs is at most mλ, and the computational area on the GPUs is at most kλ.

Property 2. In an optimal solution, if there exist two consecutive tasks on a CPU, if one of these tasks has an execution time greater than 2λ 3 , then the other one has an execution time lower than λ 3 . The same can be said of two consecutive tasks on a GPU. Property 3. Two tasks with processing times on CPU greater than λ 3 and lower than 2λ 3 can be executed successively on the same CPU within a time at most 4λ 3 . This is also valid on a GPU. The basic idea of the solution that we propose comes from the analysis of the shape of an optimal schedule. From Property 2, the tasks whose execution times on CPU (respectively on GPU) are strictly greater than 2λ 3 do not use more than m CPUs (respectively k GPUs), and hence can be executed concurrently in the first set in a shelf denoted by S 1 (respectively S 5 ). We denote by µ the number of CPUs and κ the number of GPUs executing these tasks.

The tasks whose execution times are lower than 2λ 3 and strictly greater than λ 3 on CPU (respectively on GPU) cannot be executed on the µ CPUs occupied by S 1 from Property 1 (respectively the κ GPUs occupied by S 5 ). Moreover, from Property 3, 2(m -µ) of these tasks on CPU (respectively 2(k -κ) tasks on GPU) can be executed in time at most 4λ 3 on the remaining (m -µ) CPUs in the second set and fill two shelves S 3 and S 4 of equal length 2λ 3 (resp. on (k -κ) GPUs and fill two similar shelves S 7 and S 8 ).

The remaining tasks have execution times lower than λ 3 on CPU (resp. on GPU) and can be executed within a time at most λ 3 in the first set on the CPUs in another shelf denoted by S 2 (resp. on the GPUs in a shelf S 6 ).

Thus, we are looking for a schedule on the CPUs in two sets of two shelves: S 1 of length λ, S 2 as well as S 3 and S 4 of length 2λ 3 , and a similar schedule on the GPUs, with 4 shelves S 5 to S 8 .

Lemma 1. The length of S 2 is lower than λ 3 .

Proof. We start by modifying the starting times of the tasks in S 2 , in order to have all the tasks justified to the right of the schedule, so that all the processors complete their tasks exactly at time 4λ 3 (like in figure 1). This operation induces on each CPU an idle time interval between the completion of the tasks of S 1 and the starting of the tasks of S 2 . We define the load of a CPU as the sum of the execution times of the tasks processed on it. By definition the load is equal to 4λ 3 minus the length of the idle time interval on the CPU. Now consider the following algorithm to schedule the tasks of processing time lower than λ 3 :

-Consider the tasks in an arbitrary order T 1 , . . . , T f , f being the total number of tasks remaining to be allocated in S 2 . -Allocate task T i to the least loaded processor, at the latest possible date.

Update its load.

The only problem that may occur when allocating task T i is that T i cannot be completed before the starting time of the tasks of S 2 . However at each step, the least loaded processor has a load at most λ; otherwise according to Property 1 it would contradict the fact that the total work area of the tasks is bounded by mλ. Hence, the idle time interval on the least loaded CPU has a length at least λ 3 and can contain T i .

⊓ ⊔

The proof is similar for the shelf S 6 and will be detailed in section 4.2.

Partitioning the Tasks into Shelves

In this section, we detail how to fill the shelves (see Figure 1) on the CPUs and on the GPUs by specifying an initial assignment of the tasks to the processors. In order to obtain a 2-sets and 4-shelves schedule on the CPUs and the same sets on the GPUs, we look for an assignment satisfying the following four constraints:

-(C 1 ) The total computational area W C on the CPUs is at most mλ.

-(C 2 ) The set T 1 of tasks on the CPUs with an execution time strictly greater than 2λ 3 in the allotment uses a total of at most m processors. We still denote by µ the number of processors they use. These tasks are intended to be scheduled in S 1 .

-(C 3 ) The set T 2 of tasks on the CPUs with an execution time lower than 2λ 3 and strictly greater than λ 3 in the allotment uses a total of at most 2(m -µ) processors. These tasks are intended to be scheduled in S 3 and S 4 .

-(C 4 ) The total computational area on the GPU is at most kλ.

-(C 5 ) The set T 3 of tasks on the GPUs with an execution time strictly greater than 2λ 3 in the allotment uses a total of at most k processors. We still denote by κ the number of processors they use. These tasks are intended to be scheduled in S 5 .

-(C 6 ) The set T 4 of tasks on the GPUs with an execution time lower than 2λ 3 and strictly greater than λ 3 in the allotment uses a total of at most 2(k -κ) processors. These tasks are intended to be scheduled in S 7 and S 8 . Let us notice that if constraints (C 3 ) and (C 6 ) are satisfied, then constraints (C 2 ) and (C 5 ) will also be satisfied. Hence, constraints (C 2 ) and (C 5 ) are relaxed.

We define for each task T j a binary variable x j such that x j = 1 if T j is assigned to a CPU or 0 if T j is assigned to the GPU. Determining if an allotment satisfying (C 1 ), (C 3 ), (C 4 ) and (C 6 ) exists reduces to solving a three-dimensional knapsack problem that can be formulated as follows:

W * C = min n j=1 p j x j (C 1 ) s.t. 1 2
2λ/3 pj >λ/3

x j + pj >2λ/3

x j m (C 3 ) 1 2 2λ/3 pj >λ/3 (1 -x j ) + pj >2λ/3 (1 -x j ) k (C 6 ) n j=1 p j (1 -x j ) kλ (C 4 ) x j ∈ {0, 1}
We propose a dynamic programming algorithm that solves the knapsack problem in O n 2 m 2 k 3 . For this purpose, we first have to reduce the states on the GPUs to a smaller number. We use the time intervals of length λ 3n and introduce the integer number ν j of these time intervals required for a task T j if it is executed on the GPUs: ν j = pj λ/(3n) . N = π(j)∈G ν j denotes the total integer number of these intervals on the GPUs. We can define the error on the processing time of each task ǫ j = p j -ν j λ 3n created by this approximation. This result allows us to consider only N states in the dynamic programming regarding the workload on the GPUs, and the error ǫ j on each task is at most λ 3n so if all the tasks were assigned to one of the GPU, we would have underestimated the processing time on this GPU by at most n λ 3n = λ 3 . Then, constraint (C 4 ) of the linear program becomes

N = π(j)∈G ν j 3kn
The truncated computational area of the GPUs is at most kλ and thus, the full computational area remains lower than kλ + λ 3 . Thus, an upper bound on the length of shelf S 6 can be determined as follows.

Lemma 2. The length of S 6 is lower than λ 3 + λ 3k .

Proof. The proof is similar to the one of Lemma 1. We modify the starting time of the tasks of S 6 , currently λ, so that all the working processors complete their tasks at 4λ 3 + λ 3k , creating an idle time interval between the end of S 5 and the starting time of S 6 . The load of a GPU is equal to 4λ 3 + λ 3k minus the length of the idle time interval.

With the same algorithm as for S 2 , the only problem that may occur is again that a task T i remaining to be allocated cannot be completed before the starting time of the tasks of S 6 . But at each step, the least loaded processor has a load at most λ + λ 3k ; otherwise it would contradict the fact that the total work area of the tasks is bounded by k λ + λ 3k . Hence, the idle time interval on the least loaded GPU has a length at least λ 3 and can contain the task T i . So S 6 has a length lower than λ 3 + λ 3k .

⊓ ⊔

Once this reduction done, we define W C (j, µ, µ ′ , κ, κ ′ , N ) as the minimum sum of all the processing times of the tasks on the CPUs when the first j tasks are considered, with among the tasks assigned to the CPUs, µ of them having processing times p j greater than 2λ 3 and µ ′ with λ 3 < p j 2λ 3 , respectively κ and κ ′ of these tasks being assigned to the GPUs such that N time intervals are occupied on the GPUs.

We use a dynamic programming which allows us to compute the value of W C (j, µ, µ ′ , κ, κ ′ , N ) with the values of W C with j -1 tasks considered that were previously computed. If task T j is assigned to a CPU, the resulting sum of all the processing times of the tasks on the CPUs is then

F CP U (j, µ, µ ′ , κ, κ ′ , N ) = p j + W C j -1, µ -I (pj> 2λ 3 ) , µ ′ -I ( 2λ 3 pj > λ 3 ) , κ, κ ′ , N

Computational Experiments

The HEFT algorithm is an efficient algorithm in practice but it does not provide any performance guarantee. The algorithm we presented in the previous section on the other hand provides a very satisfying performance ratio of 4 3 + 1 3k , can be implemented and works in a reasonable amount of time, but its running time may make it a bit slow for users who want an quick response, and do not necessarily need a performance guarantee so precise of 4 3 + 1 3k . The method described before can be modified in order to obtain a performance ratio of 2 in a time O(n 2 k), which would make it comparable to HEFT in terms of running time and still provide a performance guarantee. The idea is based on leaving aside the constraints ordering the tasks into shelves. The only constraint that remains is the one on the computational area on the GPUs being lower than kλ, λ being the current guess of the dual approximation. With the optimal computational area on the CPUs under this constraint determined by dynamic programming, we can build a schedule with a makespan lower than twice the optimal value. This algorithm was implemented and compared to HEFT with an experimental analysis based on various classes of instances. All the algorithms are implemented in C++ programming language and run on a 3.4 GHz PC with 15.7 Gb RAM.

We run a series of experiments on random instances of different sizes: 10 to 1000 tasks, with a step of 10 tasks, 2 a CPUs, a varying from 0 to 6, and 2 b GPUs, b varying from 0 to 3. For each combination of these sizes, 30 instances were considered, bringing us to a total of 10500 instances tested in total. The processing times on the CPUs are randomly generated using the uniform distribution U[10,100] so that p j ∈ {1, . . . , 100} for each task T j . The distribution of the acceleration factors on the GPUs have been measured in [START_REF] Seifu | Scheduling on heterogeneous cluster environments[END_REF] using the classical numerical kernels of Magma [START_REF] Agullo | Numerical linear algebra on emerging architectures: The plasma and magma projects[END_REF] in a multi-core multi-GPU machine hosted by the Grid'5000 infrastructure experimental platform [START_REF] Bolze | Grid'5000: A large scale and highly reconfigurable experimental grid testbed[END_REF]. We extracted a distribution of the acceleration factors which reflects the qualitative speed-up on real kernels: we assign to each task an acceleration factor α j of 1/15 or 1/35 with a probability of 1/2. The resulting processing times on the GPUs are thus p j = α j p j . We calculated the mean, maximal and minimal deviations of the Dynamic Programming (DP) based approximation algorithm and the HEFT algorithm from the optimal values derived from the binary search of our approximation programming. As we can see in Table 1, the maximal deviations of DP are usually below the maximal deviations of HEFT and more importantly these deviations respect the theoretical performance guarantee in the case of DP whereas the maximal deviations of HEFT sometimes go over the 100% barrier corresponding to a performance ratio of 2. We can see in Figure 2 that on average, DP even outperforms HEFT for large numbers of tasks.

Concluding Remarks

In this paper, we presented an analysis for scheduling algorithms using a generic methodology (in the opposite of specific ad hoc algorithms). We proposed fast algorithms with a constant approximation ratio in the case of independent tasks on a multi-core machines with GPUs. In the case of a single (resp. multiple) GPU(s) a ratio of 4 3 + ǫ (resp. 4 3 + 1 3k + ǫ) is achieved. The main idea of the approach is to determine an adequate partition of the set of tasks on the CPUs and the GPUs using a dual approximation scheme. A simulation and experimental analysis have been provided for different kernels to assess the computational efficiency of the proposed methods. We are currently implementing the algorithms presented here in the runtime systems xKaapi and StarPU.

As further investigations of this work, we plan to extend the analysis to more generic problems where the tasks are linked by a precedence relation. We believe that the same algorithmic scheme could be adapted to provide faster scheduling algorithms at a price of a worse guarantee. For instance, we expect a ratio 2 with a complexity of (O)(nlog(n)). These algorithms built using the proposed scheme are good candidates for the integration into runtime systems like StarPU and xKaapi.

Fig. 1 .

 1 Fig. 1. Partitioning the set of tasks into shelves

Fig. 2 .

 2 Fig. 2. Mean deviations of DP and HEFT for various n

Table 1 .

 1 .73 70.37 70.00 69.14 70.00 70.00 67.42 50.82 42.77 54.47 91.77 63.07 HEFT 123.53 98.44 92.55 94.34 91.90 110.37 91.78 113.48 98.10 98.77 103.15 116.46 96.31 Maximal deviations (%) for DP and HEFT

	n	120 160 220 260 280 360 380 660 700 760 780	920 940
	DP 76.88 72

⋆ This work is supported by a CNRS-Google contract and a french national program GDR-RO.

where I (pj> 2λ

3 ) and I ( 2λ 3 pj > λ

3 ) are indicating functions:

If task T j is assigned to a GPU, the sum of all the processing times of the tasks on the CPUs is then

The dynamic programming is then based on the following recursive equation:

In order to satisfy the constraints imposing that µ m tasks with a processing time greater than 2λ 3 are processed on the CPUs and no more than 2(m -µ) tasks with a processing time lower than 2λ 3 and greater than λ 3 are processed on the CPUs and that the computational area of the GPUs is not greater than 4kλ 3 , we have border conditions:

If the optimal value of the computational area on the CPUs

is greater than mλ, then there exists no solution with a makespan at most λ, and the algorithm answers "NO" to the dual approximation. Otherwise, we construct a feasible solution with a makespan at most 4λ 3 + λ 3k , with the corresponding shelves on the CPUs and the corresponding µ, µ ′ ,κ, κ ′ and N values.

We have described one step of the dual-approximation algorithm, with a fixed guess. A binary search will be used to try different guesses to approach the optimal makespan as follows.

Binary Search. We first take an initial lower bound B min and an initial upper bound B max of our optimal makespan. We start by solving the problem with λ equal to the average of these two bounds and then we adjust the bounds: if the previous algorithm returns "NO", then λ becomes the new lower bound, but if the algorithm returns a schedule of makespan at most 4λ 3 , then λ becomes the new upper bound. The number of iterations of this binary search can be bounded by log (B max -B min ) .

Cost Analysis. Solving the dynamic program for a fixed value of λ requires to consider O n 2 m 2 k 3 states, since 1 j n, 1 µ m, 1 µ ′ 2(m -µ), 1 κ k, 1 κ ′ 2(k -κ), and 0 N 3kn. Therefore, the time complexity of each step of the binary search is O n 2 m 2 k 3 .

Experimental Analysis

In order to show the efficiency of our method, we run experiments on random instances and compared them to the classical reference greedy algorithm HEFT used on several actual systems (HEFT stands for Heterogeneous Earliest Finishing Time [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF]). For instance, the scheduling decisions in StarPU [START_REF] Augonnet | Starpu: A unified platform for task scheduling on heterogeneous multicore architectures[END_REF] are based on estimations of the execution times of the tasks on both CPU and GPU resources that are scheduled by HEFT.

Analysis of HEFT

HEFT proceeds in two phases, starting by a prioritization of the tasks that are sorted by decreasing average execution time and then the processor selection is obtained with the heterogeneous earliest finish time rule. We can note that HEFT is not a list scheduling algorithm since some computing resources may stay idle even if a task could be executed on it.

If we consider the problem with m and k = 1, HEFT leads to a solution with a makespan that can be as far as a ratio of m/2 from the optimal value while the worst case performance ratio of our algorithm is bounded by a small constant. Lemma 3. The worst case performance ratio of HEFT is larger than m/2.

Proof. We show on the following instance that the prioritizing phase can provide a schedule whose makespan is far from the optimum. Let us consider an instance with a list of the following tasks:

m tasks such that p = 1 and p = ǫ.

-

• a single task of type A such that p = 1 -i/m and p = 1 -i/m; • m -1 tasks of type B such that p = 1 -i/m and p = 1/m 2 . These tasks are executed faster on the GPUs.

On this instance, HEFT fills first the m CPUs. Then, it fills alternatively the GPU with one task of type A and the m CPUs with m tasks of size B. HEFT ends with a makespan equal to m/2 + 3/2 -1/m. It is easy to check that the optimal makespan is equal to OP T = 1.

⊓ ⊔