The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Multilevel embeddings for massively-parallel hypercubes
Author:	Shah, Devenkumar P.
View Online:	njit-etd1993-141 (x, 51 pages ~ 1.6 MB pdf)
Department:	Department of Electrical and Computer Engineering
Degree:	Master of Science
Program:	Electrical Engineering
Document Type:	Thesis
Advisory Committee:	Ziavras, Sotirios (Committee chair) Carpinelli, John D. (Committee member) Parker, Bruce David (Committee member)
Date:	1993-05
Keywords:	Hypercube networks (Computer networks) Parallel processing (Electronic computers
Availability:	Unrestricted
Abstract:	Hierarchically structured arrays of processors have widely been used in the low and intermediate phases of image processing and computer vision. Since the pyramid structure efficiently supports local and global operations extensively required by these phases, it has been widely used for relevant algorithms. Multilevel systems keep all the advantages of the pyramid structure while providing a general hierarchical structure that is easier to be used for the development of several algorithms and may also provide higher performance. Although the cost of pyramid machines may be tremendously high, they have limited applications. In contrast, the hypercube network is widely used in the field of parallel processing because of its small diameter and its rich interconnection structure. Several algorithms have been developed that embed pyramids into the hypercube. This thesis extends and also implements three pyramid embedding algorithms in order to embed multilevel structures into the hypercube. These embedding algorithms are evaluated for the Connection Machine system CM-2 that comprises a 10-dimensional hypercube. The results for multilevel structures are compared with those for the pyramid; three image processing algorithms are used for this purpose. The results prove that the embedding of multilevel structures, other than the pyramid, yields better performance in most of the cases. This thesis also studies the implementation of stochastic pyramids on the hypercube. The structure of stochastic pyramids adapt to the contents of the image. Therefore artifacts present in the regular pyramid due to its rigid structure are alleviated. Connection Machine results are produced for the problem of connected component extraction using stochastic pyramids.