| Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks (2002) | |||||||||||||||
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 2 + " for the minimization of the parallel execution time, for any fixed " > 0. The main idea of this approach is to focus on the determination of a good allotment, 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 height 1 and 2 . | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||