Title :
Embedding all binary trees in the hypercube
Author_Institution :
Dept. of Comput. Sci., British Columbia Univ., Vancouver, BC, Canada
Abstract :
An O(N2) heuristic algorithm is presented that embeds all binary trees, with dilation 2 and small average dilation, into the optimal sized hypercube. The heuristic relies on a conjecture about all binary trees with a perfect matching. It provides a practical and robust technique for mapping binary trees into the hypercube and ensures that the communication load is evenly distributed across the network assuming any shortest path routing strategy. One contribution of this work is the identification of a rich collection of binary trees that can be easily mapped into the hypercube
Keywords :
computational complexity; hypercube networks; trees (mathematics); binary trees; communication load; computation graphs; optimal sized hypercube; perfect matching; shortest path routing strategy; Binary trees; Computer science; Heuristic algorithms; Hypercubes; Multiprocessing systems; Network topology; Robustness; Routing; Tree graphs; Vegetation mapping;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218291