Name
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 tale 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 &Ogr;(nmk) time. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/378580.378640 | SPAA |
Keywords | Field | DocType |
scheduling,efficient software,parallel application,k identical processor,cluster computing,parallel system,m smp,k approximation algorithm,fully polynomial time approximation scheme,parallel execution time,malleable task,malleable tasks,hierarchical cluster,independent malleable task,hierarchical clustering,parallel systems,cost effectiveness | Approximation algorithm,Polynomial,Scheduling (computing),Computer science,Parallel computing,Software,Minification,Granularity,Computer cluster,Polynomial-time approximation scheme,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-409-6 | 14 | 0.85 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierre-françois Dutot | 1 | 166 | 13.95 |
| Denis Trystram | 2 | 1120 | 160.57 |