Genetic algorithm based heuristics for the mapping problem

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 sub-optimal mapping that can be considered as a `good' mapping within a reasonable time. The class of genetic algorithms for this problem is found to produce better mappings than other existing algorithms. However, the execution times of this class of algorithms are far from being competitive when compared to some of the local search heuristics. In this paper, we show that the primary advantage of genetic algorithms, viz. the generalized search operators, enables easy combinations of these global search algorithms with local search heuristics to provide an efficient hybrid algorithm for the mapping problem without compromising the solution quality. The hybrid genetic mapping heuristic performs well both in terms of the quality of the mappings produced and the time taken to obtain them.