A comparison of scheduling algorithms for multiprocessortasks with precedence constraints

被引:0
作者
Duemmler, Joerg [1 ]
Kunis, Raphael [1 ]
Ruenger, Gudula [1 ]
机构
[1] Tech Univ Chemnitz, Dept Comp Sci, D-09107 Chemnitz, Germany
来源
21ST EUROPEAN CONFERENCE ON MODELLING AND SIMULATION ECMS 2007: SIMULATIONS IN UNITED EUROPE | 2007年
关键词
multiprocessortask programming; scheduling; distributed memory; scalable computing;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Many parallel applications from scientic computing show a modular structure and are therefore suitable for the multiprocessortask programming model with precedence constraints. This programming model has been shown to yield better results than a pure dataparallel or a pure taskparallel execution on distributed memory platforms in many cases. The efficient execution of multiprocessortask programs requires an appropriate schedule, which takes the structure of the application and the performance characteristics of the target platform into account. Many heuristics and approximation algorithms have been proposed to fulfil this scheduling task. In this paper we consider popular scheduling algorithms that have been implemented in a scheduling toolkit. Specifically, we introduce Allocation-and-Scheduling-based algorithms and compare their runtime for large task graphs consisting of up to 1000 nodes and target systems with up to 256 processors. Furthermore we consider the quality of the produced schedules and derive a guideline describing which scheduling algorithm is most suitable in which situation.
引用
收藏
页码:663 / +
页数:2
相关论文
共 9 条
[1]   Approaches for integrating task and data parallelism [J].
Bal, HE ;
Haines, M .
IEEE CONCURRENCY, 1998, 6 (03) :74-+
[2]  
DUMMLER J, UNPUB SCHEDULING TOO
[3]  
LEPERE R, 2001, LECT NOTES COMPUTER, V2161
[4]  
Radulescu A, 2001, PROC INT CONF PARAL, P69
[5]  
RADULESCU A, 2001, IPDPS 01 P 15 INT PA, P39
[6]   A framework for exploiting task and data parallelism on distributed memory multicomputers [J].
Ramaswamy, S ;
Sapatnekar, S ;
Banerjee, P .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (11) :1098-1116
[7]   Compiler support for task scheduling in hierarchical execution models [J].
Rauber, T ;
Rünger, G .
JOURNAL OF SYSTEMS ARCHITECTURE, 1999, 45 (6-7) :483-503
[8]   A transformation approach to derive efficient parallel implementations [J].
Rauber, T ;
Rünger, G .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2000, 26 (04) :315-339
[9]  
VALDES J, 1979, RECOGNITION SERIES P