Scheduling on hierarchical clusters using malleable tasks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2001

Scheduling on hierarchical clusters using malleable tasks

Pierre-François Dutot
Denis Trystram

Résumé

The model of malleable 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. 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. They are more and more popular, however, designing efficient software that take full advantage of such systems remains difficult. This work describes a 2-2/k approximation algorithm for scheduling a set of independent malleable tasks for the minimization of the parallel execution time, where $k$ is a power of 2 (k > 2). For k=2, a special treatment leads to the bound of 3/2 which is the best known for non hierarchical tasks. The algorithm presented here is a fully polynomial approximation scheme running in O(nmk) time.
Fichier principal
Vignette du fichier
dt_spaa01.pdf (256.74 Ko) Télécharger le fichier

Dates et versions

inria-00001082 , version 1 (01-02-2006)

Identifiants

  • HAL Id : inria-00001082 , version 1

Citer

Pierre-François Dutot, Denis Trystram. Scheduling on hierarchical clusters using malleable tasks. Symposium on Parallel Algorithms and Architectures, Jul 2001, Crete island, greece, pp.199-208. ⟨inria-00001082⟩
148 Consultations
167 Téléchargements

Partager

Gmail Facebook X LinkedIn More