Real-time scheduling of linear speedup parallel tasks

被引：21
作者：
Drozdowski, M
机构：
[1] Institute of Computing Science, Poznań Univ. of Technology, 60-965 Poznań
来源：
INFORMATION PROCESSING LETTERS | 1996年 / 57卷 / 01期
关键词：
parallel processing; parallel tasks; preemptive scheduling;
D O I：
10.1016/0020-0190(95)00174-3
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper a problem of deterministic scheduling parallel applications in a multiprogrammed multiprocessor system is considered. We address the preemptive case. The number of processors used by a task can change over time. Any task can be executed with linear speedup on a number of processors not greater than some task-dependent constant. This problem can be solved by a low-order polynomial time algorithm for the makespan optimality criterion and tasks with different release times. The algorithm can be executed on-line.
引用
收藏
页码：35 / 40
页数：6
相关论文
共 11 条
[1]  
BLAZEWICZ J, 1986, IEEE T COMPUT, V35, P389
[2]  
Blazewicz J., 1993, SCHEDULING COMPUTER
[3]  
BLAZEWICZ J, 1994, INT J MICROCOMPUTER, V13, P89
[4]   MASSIVELY-PARALLEL METHODS FOR ENGINEERING AND SCIENCE PROBLEMS [J].
CAMP, WJ ;
PLIMPTON, SJ ;
HENDRICKSON, BA ;
LELAND, RW .
COMMUNICATIONS OF THE ACM, 1994, 37 (04) :31-41
[5]  
DROZDOWSKI M, 1995, SCHEDULING PARALLEL
[6]  
Du J., 1989, SIAM J DISCRETE MATH, V2, P473, DOI DOI 10.1137/0402042
[7]   SCHEDULING WITH DEADLINES AND LOSS FUNCTIONS [J].
MCNAUGHTON, R .
MANAGEMENT SCIENCE, 1959, 6 (01) :1-12
[8]   PREEMPTIVE SCHEDULING OF REAL-TIME TASKS ON MULTIPROCESSOR SYSTEMS [J].
MUNTZ, RR ;
COFFMAN, EG .
JOURNAL OF THE ACM, 1970, 17 (02) :324-&
[9]   APPLICATION SCHEDULING AND PROCESSOR ALLOCATION IN MULTIPROGRAMMED PARALLEL-PROCESSING SYSTEMS [J].
SEVCIK, KC .
PERFORMANCE EVALUATION, 1994, 19 (2-3) :107-140
[10]   MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS [J].
VELTMAN, B ;
LAGEWEG, BJ ;
LENSTRA, JK .
PARALLEL COMPUTING, 1990, 16 (2-3) :173-182
12