Back to Search Start Over

Hypercube embedding heuristics: An evaluation

Hypercube embedding heuristics: An evaluation

Authors :
Chen, Woei-Kae
Stallmann, Matthias F. M.
Gehringer, Edward F.
Source :
International Journal of Parallel Programming; December 1989, Vol. 18 Issue: 6 p505-549, 45p
Publication Year :
1989

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.

Details

Language :
English
ISSN :
08857458 and 15737640
Volume :
18
Issue :
6
Database :
Supplemental Index
Journal :
International Journal of Parallel Programming
Publication Type :
Periodical
Accession number :
ejs14896153
Full Text :
https://doi.org/10.1007/BF01381720