A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks

Grégory Mounié (1, 2, 3, 4) , Christophe Rapine (1, 2, 4, 5) , Denis Trystram (1, 2, 3, 4)

1 ID-IMAG - Informatique et Distribution
2 APACHE - Parallel algorithms and load sharing
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
4 LMC - IMAG - Laboratoire de Modélisation et Calcul
5 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production

A malleable task is a computational unit which may be executed on any arbitrary number of processors whose execution time depends on the amount of resources alloted to is. This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guarantee of 3/2+epsilon for the minimization of the parallel execution time, for any fixed epsilon>0. The main idea of this approach is to focus on the determination of a good allotment, then, to solve the resulting problem with a fixed number of processors by a simple scheduling algorithm. The first phase is based on a dual approximation technique where the allotment problem is expressed as a knapsack problem for partitionning the set of tasks into two shelves of respective height 1 and 1/2.

Mots clés: Parallel Computing; Scheduling; Moldable Tasks; Malleable Tasks; Independent Tasks

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Recherche opérationnelle [math.OC]

Grégory Mounié, Christophe Rapine, Denis Trystram. A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks. SIAM Journal on Computing, 2007, 37 (2), pp.401--412. ⟨10.1137/S0097539701385995⟩. ⟨hal-00002166v2⟩