Please use this identifier to cite or link to this item:
|Title:||Embedding of binary trees into hypercubes|
|Citation:||Bier, T.,Loe, K.-F. (1989-06). Embedding of binary trees into hypercubes. Journal of Parallel and Distributed Computing 6 (3) : 679-691. ScholarBank@NUS Repository.|
|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.|
|Source Title:||Journal of Parallel and Distributed Computing|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 12, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.