Record Details

A RANDOMIZED HEURISTICS FOR THE MAPPING PROBLEM - THE GENETIC APPROACH

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A RANDOMIZED HEURISTICS FOR THE MAPPING PROBLEM - THE GENETIC APPROACH
 
Creator CHOCKALINGAM, T
ARUNKUMAR, S
 
Subject parallel
genetic algorithms
randomized heuristics
mapping problem
combinatorial optimization
 
Description 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.
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-22T19:50:24Z
2011-12-26T12:52:33Z
2011-12-27T05:38:42Z
2011-07-22T19:50:24Z
2011-12-26T12:52:33Z
2011-12-27T05:38:42Z
1992
 
Type Article
 
Identifier PARALLEL COMPUTING, 18(10), 1157-1165
0167-8191
http://dx.doi.org/10.1016/0167-8191(92)90062-C
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6340
http://hdl.handle.net/10054/6340
 
Language en