loading...
A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems
Cork, Ireland July 05-July 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPDC.2004.3Third International Symposium on Para ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Tarek Hagras, Jan Janeček, "A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems," Parallel and Distributed Computing, International Symposium on, 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.
 
 
BibTex
x
 
@article{ 10.1109/ISPDC.2004.3,
author = {Tarek Hagras and Jan Janeček},
title = {A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems},
journal ={Parallel and Distributed Computing, International Symposium on},
volume = {0},
year = {2004},
isbn = {0-7695-2210-6},
pages = {106-113},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPDC.2004.3},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Computing, International Symposium on
TI - A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems
SN - 0-7695-2210-6
SP106
EP113
A1 - Tarek Hagras,
A1 - Jan Janeček,
PY - 2004
KW - list scheduling
KW - task duplication
KW - compile time scheduling
KW - task graph scheduling
KW - heterogeneous computing
VL - 0
JA - Parallel and Distributed Computing, International Symposium on
ER -
 
Tarek Hagras, Czech Technical University in Prague
Jan Janeček, Czech Technical University in Prague
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
Usage of this product signifies your acceptance of the Terms of Use.