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

Title:	Performance analysis of pyramid mapping algorithms for the hypercube
Author:	Liou, Jing-Chiou
View Online:	njit-etd1993-112 (ix, 69 pages ~ 1.9 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) Karvelas, Dionissios (Committee member)
Date:	1993-01
Keywords:	Hypercube networks (Computer networks) Computer interfaces
Availability:	Unrestricted
Abstract:	Comparative performance analysis of algorithms that map pyramids and multilevel structures onto the hypercube are presented. The pyramid structure is appropriate for low-level and intermediate-level computer vision algorithms. It is not only efficient for the support of both local and global operations but also capable of supporting the implementation of multilevel solvers. Nevertheless, pyramids lack the capability of efficient implementation of the majority of scientific algorithms and their cost may become unacceptably high. On a different horizon, hypercube machines have widely been used in the field of parallel computing due to their small diameter, high degree of fault tolerance, and rich interconnection that permits fast communication at a reasonable cost. As a result, hypercube machines can efficiently emulate pyramids. Therefore, the characteristics which make hypercube machines useful scientific processors also make them efficient image processors. Two algorithms which have been developed for the efficient mapping of the pyramid onto the hypercube are discussed in this thesis. The algorithm proposed by Stout [4] requires a hypercube with a number of processing elements (PEs) which is equal to the number of nodes in the base of the pyramid. This algorithm can activate only one level of the pyramid at a time. In contrast, the algorithm proposed by Patel and Ziavras [7] requires the same number of PEs as Stout's algorithm but allows the concurren simulation of multiple levels, as long as the base level is not involved in the set of pyramid levels that need to be simulated at the same time. This low-cost algorithm yields higher performance through high utilization of PEs. However it performs slightly worse than Stout's algorithm when only one level is active at a time. Patel and Ziavras' algorithm performs much better than Stout's algorithm when all levels, excluding the leaf level, are active concurrently. The comparative analysis of these two algorithms is based on the incorporation of simulation results for some image processing algorithms which are perimeter counting, image convolution, and segmentation.