Hypercube embedding heuristics: An evaluation |
| |
Authors: | Woei-Kae Chen Matthias F M Stallmann Edward F Gehringer |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, North Carolina State University, 27695-7911 Raleigh, North Carolina;(2) Department of Computer Science, North Carolina State University, 27695-8206 Raleigh, North Carolina |
| |
Abstract: | The hypercube embedding problem, a restricted version of the general mapping problem, is the problem of mapping a set of communicating processes to a hypercube multiprocessor. The goal is to find a mapping that minimizes the length of the paths between communicating processes. Unfortunately the hypercube embedding problem has been shown to be NP-hard. Thus many heuristics have been proposed for hypercube embedding. This paper evaluates several hypercube embedding heuristics, including simulated annealing, local search, greedy, and recursive mincut bipartitioning. In addition to known heuristics, we propose a new greedy heuristic, a new Kernighan-Lin style heuristic, and some new features to enhance local search. We then assess variations of these strategies (e.g., different neighborhood structures) and combinations of them (e.g., greedy as a front end of iterative improvement heuristics). The asymptotic running times of the heuristics are given, based on efficient implementations using a priority-queue data structure.This research is partially supported by the Office of Naval Research under Contract N00014-88-K-0555, which is gratefully acknowledged. |
| |
Keywords: | Mapping problem hypercube embedding greedy heuristics local search simulated annealing priority queues |
本文献已被 SpringerLink 等数据库收录! |
|