TASK ALLOCATION ONTO A HYPERCUBE BY RECURSIVE MINCUT BIPARTITIONING

被引：43

作者：

ERCAL, F ^{[1
]}

RAMANUJAM, J ^{[1
]}

SADAYAPPAN, P ^{[1
]}

机构：

[1] OHIO STATE UNIV,DEPT COMP & INFORMAT SCI,COLUMBUS,OH 43210

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1990年 / 10卷 / 01期

关键词：

D O I：

10.1016/0743-7315(90)90004-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An efficient recursive task allocation scheme, based on the Kernighan-Lin mincut bisection heuristic, is proposed for the effective mapping of tasks of a parallel program onto a hypercube parallel computer. It is evaluated by comparison with an adaptive, scaled simulated annealing method. The recursive allocation scheme is shown to be effective on a number of large test task graphs-its solution quality is nearly as good as that produced by simulated annealing, and its computation time is several orders of magnitude less. © 1990.

引用

页码：35 / 44

页数：10

共 26 条

[1]

BERMAN F, 1987, CHARACTERISTICS PARA, P307

[2]

BOKHARI SH, 1981, IEEE T COMPUT, V30, P207, DOI 10.1109/TC.1981.1675756

[3]

BOLLINGER SW, 1988 P INT C PAR PRO, V1, P1

[4]

CERNY V, 1984, HUTFT8451 U HELS RES

[5]

EFE K, 1982, COMPUTER, V15, P50, DOI 10.1109/MC.1982.1654050

[6]

Fiduccia C. M., 1988, PROC 19 AUTOM C, P241, DOI DOI 10.1109/DAC.1982.1585498

[7]

FLOWER JW, 1985, CALTECH292 TECH REP

[8]

FOX GC, 1987, HYPERCUBE MULTIPROCE, P244

[9]

FOX GC, 1985, CALTECH327 TECH REP

[10]

KASAHARA H, 1984, IEEE T COMPUT, V33, P1023, DOI 10.1109/TC.1984.1676376

← 1 2 3 →