| Abstract |
|
Task scheduling is in general an NP-complete problem. For this reason a huge number of heuristics have been presented in the literature to obtain near optimal schedules. These heuristics mainly target homogeneous computing systems, while a few of them target heterogeneous systems. The heterogeneous heuristics presented so far target computing machines with different capabilities, while almost none of them handle heterogeneous communication systems. This paper presents a novel task scheduling algorithm called the Heterogeneous Critical Tasks Reverse Duplicator (HCTRD), which targets both heterogeneous computation and communication systems. The algorithm is based on list-scheduling and task-duplication in a bounded number of machines, and aims to achieve high performance and near lower bound complexity.
|
 Additional Information
|
Index Terms- list scheduling, task duplication, compile time scheduling, task graph scheduling, heterogeneous computing
Citation:
Tarek Hagras, Jan Janecek,
"A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems,"
ispdc,
pp. 106-113,
Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04),
2004
|
