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)
A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems
Cork, Ireland
July 05-July 07
ISBN: 0-7695-2210-6
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.
Index Terms:
list scheduling, task duplication, compile time scheduling, task graph scheduling, heterogeneous computing
Citation:
Tarek Hagras, Jan Janeček, "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
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb