Embedding of binary trees into hypercubes

Abstract

We present a mathematical model of parallel computing in a hypercubical parallel computer. This is based on embedding binary trees or forests into the n-dimensional hypercube. We consider three different models corresponding to three different computing situations. First we assume that the processing time at each level of the binary tree is arbitrary, and develop the corresponding mathematical model of an embedding of a binary tree into the hypercube. Then we assume that the processing time at each level of the binary tree is the same for all processors involved at that level, and for this we develop the mathematical model of a loop embedding of a binary tree into the hypercube. The most general case is that in which only certain neighboring levels are active. Here we assume for simplicity that only the processors corresponding to two neighboring levels are active at the same time, and correspondingly we develop the mathematical model of a level embedding of a binary tree into the hypercube to cover this case. Both loop embeddings and level embeddings allow us to use the same processor several times during the execution of a program. © 1989.