DocumentCode :
3163743
Title :
Embedding all binary trees in the hypercube
Author :
Wagner, A.S.
Author_Institution :
Dept. of Comput. Sci., British Columbia Univ., Vancouver, BC, Canada
fYear :
1991
fDate :
2-5 Dec 1991
Firstpage :
104
Lastpage :
111
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
Type :
conf
DOI :
10.1109/SPDP.1991.218291
Filename :
218291
Link To Document :
بازگشت