A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering, School of Advanced Technologies

Thesis (M.Eng.) - Asian Institute of Technology, 1998

Parallel Processing has an advantage over traditional supercomputers in price I performance I speed and it comprises algorithms, computer architecture, programming tools, and performance analysis. The objective of this study is to propose an efficient parallel algorithm for image matching computation on the Convex Exemplar SPP System. Three new parallel algorithms are proposed which are the improvement on each other and implemented in Convex MPICH message-passing environment. The most efficient proposed parallel algorithm is called the Parallel Help-Load Balancing Improved Algorithm and the reasons for the efficiency are computational power of the system, reduced communication in the parallel algorithm, the processors help each other, and proportional amount of data is distributed during the load balancing process. To evaluate the performance of the new efficient parallel algorithm, this study discusses the normalized performances of the proposed load balancing strategies, how system workload affects the performance of parallel algorithm, and compares the performances between the proposed efficient parallel algorithm and shared memory parallel algorithm. Results of study are categorized in the following order. First, this study presents the efficient parallel algorithm for image matching computation on Convex Exemplar in Convex MPICH. Second, results indicate that the Parallel Help-Load Balancing Improved Algorithm is the most efficient when the program is computation intensive. Finally, it is determined that the efficiency depends on system workload and its balancing.