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

Title:	Comparing techniques of mapping pyramid algorithms onto the hypercube : a case study for the connection machine
Author:	Siddiqui, Muhammad Ali
View Online:	njit-etd1992-111 (x, 73 pages ~ 2.4 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) Hou, Edwin (Committee member)
Date:	1992-05
Keywords:	Image processing -- Digital techniques Computer interfaces Hypercube Algorithms
Availability:	Unrestricted
Abstract:	The pyramid structure is most widely used for low-level and intermediate-level image processing and computer vision because of its efficient support of both local and global operations. However, the cost of pyramid computers (PC) may be very high. They also do not support the efficient implementation of the majority of the scientific algorithms. In contrast, the hypercube network has widely been used in the field of parallel processing because it offers a high degree of fault tolerance, a small diameter and rich interconnection structure that permits fast communication at a reasonable cost. Thus, several algorithms have been developed for the efficient simulation of pyramids on hypercubes. Stout [2], Lai and White [3], and Patel and Ziavras [14] have proposed four different algorithms that map pyramids onto the hypercube. This thesis carries out a comparative analysis that involves all these algorithms. The comparison is based on results derived with the application of analytical techniques and actual program runs. A Connection Machine CM-2 system containing 16K processors was used to derive the latter type of results. Stout's algorithm is cost effective, as it requires a hypercube with a number of PEs which is equal to the total number of nodes in the base of the pyramid. Thus. it needs a 2n-dimensional hypercube to map a pyramid with n + 1 levels. Lai and White have proposed two mapping algorithms. They require double the number of PEs used by Stouts algorithm. Finally, the algorithm proposed by Patel and Ziavras requires the same number of PEs as Stout's algorithm but allows the simultaneous simulation of multiple levels. as long as the leaf level is not included in the set of the levels required to be active at the same time. A comparative analysis is carried out for all four mapping algorithms through the incorporation of analytical techniques and results obtained on the Connection Machine system CM-2 for some important image processing algorithms.