Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99266
Title: Embedding of binary trees into hypercubes
Authors: Bier, T.
Loe, K.-F. 
Issue Date: Jun-1989
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
URI: http://scholarbank.nus.edu.sg/handle/10635/99266
ISSN: 07437315
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

42
checked on Oct 12, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.