A RANDOMIZED HEURISTICS FOR THE MAPPING PROBLEM - THE GENETIC APPROACH

被引：16

作者：

CHOCKALINGAM, T

ARUNKUMAR, S

机构：

[1] Department of Computer Science and Engineering, Indian Institute Technology, Bombay

来源：

PARALLEL COMPUTING | 1992年 / 18卷 / 10期

关键词：

GENETIC ALGORITHMS; RANDOMIZED HEURISTICS; MAPPING PROBLEM; COMBINATORIAL OPTIMIZATION;

D O I：

10.1016/0167-8191(92)90062-C

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The combinatorial optimization problem of assigning parallel tasks onto a multiprocessor so as to minimize the execution time is termed as the mapping problem. This problem even in its simplest form is known to be NP-hard. Several heuristic solutions that have been proposed seek to obtain a 'good' sub-optimal mapping at a reasonable time. In this paper we present a randomized heuristic for the mapping problem which is based on the principles of genetic algorithms. The adaptation of the genetic search strategy to this problem and its implementation has been discussed. We empirically compare the performance of our randomized mapping algorithm with an existing random start algorithm based on the recursive min-cut partitioning heuristic. The results indicate that the genetic algorithm for mapping is a promising alternative in the domain of randomized heuristics.

引用

页码：1157 / 1165

页数：9

共 9 条

[1]

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

[2]

CHEN WK, 1990, INT J PARALLEL PROG, V18, P505

[3]

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

[4]

Goldberg DE, 1989, GENETIC ALGORITHMS S

[5]

Holland John H., 1973, SIAM J COMPUT, V2

[6]

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

[7]

Kernighan B. W., 1970, Bell System Technical Journal, V49, P291

[8]

LEE SY, 1987, IEEE T COMPUT, V36, P433, DOI 10.1109/TC.1987.1676925

[9]

SADAYAPPAN P, 1987, JUN INT C SUP ATH, P475

← 1 →