A lookahead heuristic for heterogeneous multiprocessor scheduling with communication costs

被引：0

作者：

Li, DC

Mizuno, A

Iwahori, Y

Ishii, N

机构：

[1] Nagoya Inst of Technology, Nagoya-shi, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 1997年 / E80D卷 / 04期

关键词：

parallel processing; heterogeneous multiprocessors; task graphs; communication costs; scheduling heuristics;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper describes a new approach to the scheduling problem that assigns tasks of a parallel program described as a task graph onto parallel machines. The approach handles interprocessor communication and heterogeneity, based on using both the theoretical results developed so far and a lookahead scheduling strategy. The experimental results on randomly generated task graphs demonstrate the effectiveness of this scheduling heuristic.

引用

页码：489 / 494

页数：6

共 10 条

[1] LOWER BOUND ON THE NUMBER OF PROCESSORS AND TIME FOR SCHEDULING PRECEDENCE GRAPHS WITH COMMUNICATION COSTS
ALMOUHAMED, MA
[J]. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1990, 16 (12) : 1390 - 1401
[2] SCHEDULING PARALLEL PROGRAM TASKS ONTO ARBITRARY TARGET MACHINES
ELREWINI, H
LEWIS, TG
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 9 (02) : 138 - 153
[3] SCHEDULING PRECEDENCE GRAPHS IN SYSTEMS WITH INTERPROCESSOR COMMUNICATION TIMES
HWANG, JJ
CHOW, YC
ANGER, FD
LEE, CY
[J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (02) : 244 - 257
[4] KASAHARA H, 1984, IEEE T COMPUT, V33, P1023, DOI 10.1109/TC.1984.1676376
[5] KOHLER WH, 1975, IEEE T COMPUT, P1235
[6] Li D., 1994, Transactions of the Information Processing Society of Japan, V35, P1624
[7] McCreary C. L., 1994, Proceedings Eighth International Parallel Processing Symposium (Cat. No.94TH0652-8), P446, DOI 10.1109/IPPS.1994.288264
[8] NORRE S, 1993, P 5 INT C PAR ARCH L, P489
[9] SIN GC, 1993, IEEE T PARALL DISTR, V4, P175
[10] WU MY, 1990, IEEE T PARALL DISTR, V1, P101

← 1 →