HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Hierarchical Scheduling for Moldable Tasks

Pierre-François Dutot 1
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Abstract : The model of moldable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level of granularity than in other models (corresponding typically to numerical routines) where the tasks can themselves be executed in parallel on any number of processors. Clusters of SMP (symmetric Multi-Processors) are a cost effective alternative to parallel supercomputers. Such hierarchical clusters are parallel systems made from m SMP composed each by k identical processors. These architectures are more and more popular, however designing efficient software that take full advantage of such systems remains difficult. This work describes approximation algorithms for scheduling a set of tree precedence constrained moldable tasks for the minimization of the parallel execution time, with a scheme which is first used for two multi-processors and several bi-processors and then extended to the general case of any number of multi-processors. The best known approximation ratio for trees in the homogeneous case is 2.62, and although the hierarchical problem is harder our results are close as we obtain a ratio of 3.41 for two multi-processors, 3.73 for several bi-processors and 5.64 for the general case of several SMPs with a large number of processors. To our knowledge, this is the first work on precedence constrained moldable tasks on hierarchical platforms.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

Contributor : Pierre-François Dutot Connect in order to contact the contributor
Submitted on : Wednesday, February 1, 2006 - 6:44:19 PM
Last modification on : Friday, February 4, 2022 - 3:09:25 AM
Long-term archiving on: : Saturday, April 3, 2010 - 10:02:09 PM


  • HAL Id : inria-00001077, version 1



Pierre-François Dutot. Hierarchical Scheduling for Moldable Tasks. Euro-Par, Aug 2005, Lisbonne, Portugal, pp.302-311. ⟨inria-00001077⟩



Record views


Files downloads