Comparative Analysis of Hill Climbing Mapping Algorithms

The performance of a parallel algorithm depends in part on how well the communication structure of the algorithm is matched to the communication structure of the target parallel system. The mapping problem is the problem of generating such a match algorithmically. Solving the mapping problem optimally for any non-trivial case is NP-complete. Therefore, a heuristic approach must be used to solve the problem. Although several heuristic algorithms to this problem have been developed, their performance has been evaluated on relatively few combinations of communication and processor structures. This paper extensively evaluates the performance of hill climbing mapping algorithms through simulation on communication structures representative of existing parallel algorithms and architectures. The motivations for our study are as follows: to establish the differences in performance between variations of the hill climbing heuristic; to determine the factors which affect the performance of hill climbing with respect to optimum; and to compare hill climbing to known optimum and non-optimum mappings to determine the effectiveness of hill climbing as a mapping heuristic.