loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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)
Assessing the Impact and Limits of Steady-State Scheduling for Mixed Task and Data Parallelism on Heterogeneous Platforms
Cork, Ireland
July 05-July 07
ISBN: 0-7695-2210-6
ASCII Text
x 
 
O. Beaumont, A. Legrand, L. Marchal, Y. Robert, "Assessing the Impact and Limits of Steady-State Scheduling for Mixed Task and Data Parallelism on Heterogeneous Platforms," Parallel and Distributed Computing, International Symposium on, pp. 296-302, 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.12,
author = {O. Beaumont and A. Legrand and L. Marchal and Y. Robert},
title = {Assessing the Impact and Limits of Steady-State Scheduling for Mixed Task and Data Parallelism on Heterogeneous Platforms},
journal ={Parallel and Distributed Computing, International Symposium on},
volume = {0},
year = {2004},
isbn = {0-7695-2210-6},
pages = {296-302},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPDC.2004.12},
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 - Assessing the Impact and Limits of Steady-State Scheduling for Mixed Task and Data Parallelism on Heterogeneous Platforms
SN - 0-7695-2210-6
SP296
EP302
A1 - O. Beaumont,
A1 - A. Legrand,
A1 - L. Marchal,
A1 - Y. Robert,
PY - 2004
KW - null
VL - 0
JA - Parallel and Distributed Computing, International Symposium on
ER -
 
O. Beaumont, LaBRI, UMR CNRS
A. Legrand, LIP, UMR CNRS-INRIA
L. Marchal, LIP, UMR CNRS-INRIA
Y. Robert, LIP, UMR CNRS-INRIA

In this paper, we consider steady-state scheduling techniques for mapping a collection of task graphs onto heterogeneous systems, such as clusters and grids.We advocate the use of steady-state scheduling to solve this difficult problem. Due to space limitations, we concentrate on complexity results. We show that the problem of optimizing the steady-state throughput is NP-Complete in the general case. We formulate a compact version of the problem that belongs to the NP complexity class but which does not restrict the optimality of the solution.

We provide many positive results in the extended version [5]. Indeed, we show how to determine in polynomial time the best steady-state scheduling strategy for a large class of application graphs and for an arbitrary platform graphs, using a linear programming approach.

Citation:
O. Beaumont, A. Legrand, L. Marchal, Y. Robert, "Assessing the Impact and Limits of Steady-State Scheduling for Mixed Task and Data Parallelism on Heterogeneous Platforms," ispdc, pp.296-302, 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.