Effect of task duplication on the assignment of dependency graphs

被引：6

作者：

Manoharan, S ^{[1
]}

机构：

[1] Univ Auckland, Dept Comp Sci, Auckland 1, New Zealand

来源：

PARALLEL COMPUTING | 2001年 / 27卷 / 03期

关键词：

task duplication; work-greedy assignments; scheduling; task allocation;

D O I：

10.1016/S0167-8191(00)00096-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper analyses the effect of task duplication on the assignment of task dependency graphs onto concurrent processor systems. It augments work-greedy assignment schemes with task duplication (TD). Such augmentation results in a time-complexity increase which is well below that of comparable assignment schemes with TD. The paper shows empirical results comparing the augmented assignment schemes. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：257 / 268

页数：12

共 13 条

[1] COMPARISON OF LIST SCHEDULES FOR PARALLEL PROCESSING SYSTEMS
ADAM, TL
CHANDY, KM
DICKSON, JR
[J]. COMMUNICATIONS OF THE ACM, 1974, 17 (12) : 685 - 690
[2] SCHEDULING WITH SUFFICIENT LOOSELY COUPLED PROCESSORS
ANGER, FD
HWANG, JJ
CHOW, YC
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 9 (01) : 87 - 92
[3] SCHEDULING PARALLEL PROGRAM TASKS ONTO ARBITRARY TARGET MACHINES
ELREWINI, H
LEWIS, TG
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 9 (02) : 138 - 153
[4] TASK-SCHEDULING IN MULTIPROCESSING SYSTEMS
ELREWINI, H
ALI, HH
LEWIS, T
[J]. COMPUTER, 1995, 28 (12) : 27 - &
[5] 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
[6] KRUATRACHUE B, 1987, 87603 OR STAT U COMP
[7] MULTIPROCESSOR SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS
LEE, CY
HWANG, JJ
CHOW, YC
ANGER, FD
[J]. OPERATIONS RESEARCH LETTERS, 1988, 7 (03) : 141 - 147
[8] ASSIGNING DEPENDENCY GRAPHS ONTO PROCESSOR NETWORKS
MANOHARAN, S
THANISCH, P
[J]. PARALLEL COMPUTING, 1991, 17 (01) : 63 - 73
[9] AN ASSESSMENT OF ASSIGNMENT SCHEMES FOR DEPENDENCY GRAPHS
MANOHARAN, S
TOPHAM, NP
[J]. PARALLEL COMPUTING, 1995, 21 (01) : 85 - 107
[10] TOWARDS AN ARCHITECTURE-INDEPENDENT ANALYSIS OF PARALLEL ALGORITHMS
PAPADIMITRIOU, CH
YANNAKAKIS, M
[J]. SIAM JOURNAL ON COMPUTING, 1990, 19 (02) : 322 - 328

← 1 2 →