Name
Abstract | ||
|---|---|---|
A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depend- ing on the amount of resources allotted to it. According to the standard behavior of parallel applications, we assume that the mal- leable tasks are monotonic, i.e. that the execution time is decreas- ing with the number of processors while the computational work increases. This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guar- antee of for the minimization of the parallel execution time, or makespan. It improves all other existing practical results includ- ing the two-phases method introduced by Turek et al. The main idea is to transfer the difficulty of a two phases method from the scheduling part to the allotment selection. We show how to formu- late this last problem as a knapsack optimization problem. Then, the scheduling problem is solved by a dual-approximation which leads to a simple structure of two consecutive shelves. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1145/305619.305622 | SPAA |
Keywords | Field | DocType |
efficient approximation algorithm,malleable task,scheduling problem,optimization problem | Approximation algorithm,Multiprocessor scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Parallel computing,Knapsack problem,Dynamic priority scheduling,Optimization problem,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-124-0 | 55 | 2.68 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gregory Mounie | 1 | 137 | 11.22 |
| Christophe Rapine | 2 | 239 | 20.97 |
| Dennis Trystram | 3 | 55 | 2.68 |