Ming-Yi Fang and Wen-Tsuen Chen
Department of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 30043, R.O.C.
The commercial introduction of hypercube-based machines has spurred researches into embodying a winde variety of algorithms for different problems on the hypercube. To efficiently execute these algorithms on the hypercube, we have to match the algorithm's underlying network structures into the hypercube so as to minimize the communication overhead. One-to-one embeddings into hypercubes have been much studied for several network structures. However, in practice, we are often faced with hypercubes of limited size, where many-to-one mappings are highly demanded and load balancing is of primary concern. In this paper, many-to-one embeddings of large binary trees to hypercube multiprocessors is investigated. An efficient embedding procedure, which maps binary trees into a hypercube with constant overhead, is presented. The result can also be extended to the embedding of augmented binary trees which incorporate extra links to connect nodes that lie in the same level of the tree so as to reduce average path distance and to provide redundant paths for fault tolerance as well.
Keywords: tree embedding, hypercube, load balance, complete binary tree, X-tree, Hypertree
Received July 2, 1991; revised December 2, 1991.
Communicated by Ferng-Ching Lin.