Name
Abstract | ||
|---|---|---|
A malleable task is a computational unit that may be executed on any arbitrary number of processors, whose execution time depends on the amount of resources allotted to it. 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 and 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 partitioning the set of tasks into two shelves of respective heights 1 and (1)/(2). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/S0097539701385995 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
scheduling,malleable tasks,polynomial approximation,performance guarantee | Journal | 37 |
Issue | ISSN | Citations |
2 | 0097-5397 | 6 |
PageRank | References | Authors |
0.48 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gregory Mounie | 1 | 137 | 11.22 |
| Christophe Rapine | 2 | 239 | 20.97 |
| Denis Trystram | 3 | 1120 | 160.57 |