RANDOMIZED 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 'good' sub-optimal mapping in a reasonable time. In this paper we present two randomized heuristics for the mapping problem one of which is based on Plaisted's randomized graph separator heuristic while the other is based on the principles of genetic algorithms. We empirically compare the performance of our algorithms with two other such existing randomized mapping algorithms. One of them is the recursive min-cut partitioning heuristic due to Sadayappan et al., while the other is a simple genetic algorithm for mapping of our earlier work.

This comparison of relative performance of the four randomized algorithms indicates that the genetic class of algorithms always produces better mappings than algorithms of the clustering class. In addition it is found that the recursive separator mapping algorithm performs as good as the recursive clustering algorithm while our new variant of genetic algorithm performs no better than our simple genetic algorithm.