IMPROVED CLUSTERING ALGORITHM FOR PARALLELIZING SOFTWARE SYSTEMS IN MULTIPROCESSORS ENVIRONMENT

Abstract

A variety of techniques and tools exist to parallelize software systems on different parallel architectures (SIMD, MIMD). With the advances in high-speed networks, there has been a dramatic increase in the number of client/server applications. A variety of client/server applications are deployed today, ranging from simple telnet sessions to complex electronic commerce transactions. Industry standard protocols, like Secure Sockets Layer (SSL), Secure Electronic Transaction (SET), etc., are in use for ensuring privacy and integrity of data, as well as for authenticating the sender and the receiver during message passing. ConseqUently, a majority of applications using parallel processing techniques are becoming synchronization-centric, i.e., for every message transfer, the sender and receiver must synchronize. However, more effective techniques and tools are needed for the clustering of such synchronization-centric applications to extract parallelism. Dinesh Kadamuni and Jeffery J.P. Tsai [1] have given a clustering algorithm which 1) reduces parallel execution time, 2) reduces the performance degradation caused by synchronizations, and 3) avoids deadlocks during clustering. In this thesis, we propose an improved algorithm that leads to better clustering in the backward-merge step and thereby leads to higher reduction in parallel time. The benefit of improved algorithm is higher for CCRs upto 1.0 At higher CCRs also the benefit is greater than or equal to the Conventional algorithm The effectiveness of the approach has been demonstrated through simulation results for Random graphs, divide-conquer and LaPlace-Equation-Solver