How to Embed Trees in Hypercubes.

Many parallel machines based on the interconnections of the boolean hypercube are now commercially available. A distinctive feature of the hypercube is its universality-computer programs written for simpler architectures, such as grids for example, can be transported onto the hypercube with minimal overhead. These simulations are typically obtained by embedding the simpler architecture within the hypercube. This paper presents efficient embeddings of binary trees in the hypercube. It provides a novel and optimal embedding of a complete binary tree in which all but one tree edges are mapped onto adjacent processors on the hypercube, and the remaining edge is routed through an unused processor. With suitably designed processors and protocols, communication through the forwarding processor should incur no extra delay. The author also presents efficient embeddings of binary trees that are not complete, and shows that any N-node binary tree can be embedded with edges of length log log N+0(1) in a hypercube with no more than 2N processors. The results extend to graphs with small separators. (Author)