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
CAMP, WJ
PLIMPTON, SJ
HENDRICKSON, BA
LELAND, RW
[J]. 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
MCNAUGHTON, R
[J]. MANAGEMENT SCIENCE, 1959, 6 (01) : 1 - 12
[8] PREEMPTIVE SCHEDULING OF REAL-TIME TASKS ON MULTIPROCESSOR SYSTEMS
MUNTZ, RR
COFFMAN, EG
[J]. JOURNAL OF THE ACM, 1970, 17 (02) : 324 - &
[9] APPLICATION SCHEDULING AND PROCESSOR ALLOCATION IN MULTIPROGRAMMED PARALLEL-PROCESSING SYSTEMS
SEVCIK, KC
[J]. PERFORMANCE EVALUATION, 1994, 19 (2-3) : 107 - 140
[10] MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS
VELTMAN, B
LAGEWEG, BJ
LENSTRA, JK
[J]. PARALLEL COMPUTING, 1990, 16 (2-3) : 173 - 182

← 1 2 →