Scheduling on hierarchical clusters using malleable tasks

Pierre-François Dutot 1 Denis Trystram 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 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.
Complete list of metadatas

https://hal.inria.fr/inria-00001082
Contributor : Pierre-François Dutot <>
Submitted on : Wednesday, February 1, 2006 - 6:27:21 PM
Last modification on : Wednesday, March 13, 2019 - 2:58:27 PM
Long-term archiving on : Saturday, April 3, 2010 - 10:04:02 PM

Identifiers

  • HAL Id : inria-00001082, version 1

Collections

INRIA | IMAG | UGA

Citation

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⟩

Share

Metrics

Record views

243

Files downloads

224