Dynamic Load Balancing In Parallel Algorithms Using Message Passing Interface

Abstract

Parallel algorithms are increasingly becoming favorable when it comes to solving large sizes of problems. Problems of such sizes are produced by discrete optimization problems (DOP). DOP, present considerably large problem sizes in all areas of science including mathematics, physics, engineering and artificial intelligence (AI). On serial computers, DOP are typically solved using AI algorithms, of which the depthfirst search (DFS) is a strong candidate. This thesis therefore proposes to solve DOP by implementing a parallel adapted version of the DFS, termed parallel DFS. The performance of parallel DFS depends mainly on the load (work) distribution algorithm (scheme) which is in charge of dynamically allocating and distributing work among processors. Such schemes are termed dynamic load balancing schemes (DLB schemes). The study of the commonly used DLB schemes and their performance is the focal point of this thesis, with emphasis made on using the parallel DFS to solve DOP. The approach adopted in this thesis is different from various related work, in which focus were made on underlying parallel architectures rather than DLB schemes, which also influences the performance of parallel algorithms. The study of the commonly used DLB schemes was carried out by adopting a thorough theoretical and practical analysis approach. Results obtained from comparison of the DLB schemes are used to propose a new DLB scheme. This new DLB scheme is based on one of the commonly used DLB schemes and is termed random polling or simply RP. The presented new DLB scheme is therefore termed ARP (Adapted Random Polling). ARP is also theoretically and practically analyzed and compared with the commonly used DLB schemes. Based on the average achieved speedup, it is shown that ARP may be considered as an addition to the commonly used DLB schemes in both the small and large parallel cluster scenarios. iv The main contributions of this thesis can therefore be summarized as follows: 1. Construction of a parallel cluster to be used as a test bed 2. Development of a parallel algorithm adapting the depth first search (DFS) algorithm to operate on parallel clusters (parallel DFS) 3. Application of the parallel DFS to the 8-puzzle problem 4. A new DLB scheme (the ARP DLB scheme), derived from the RP DLB scheme 5. Comparison between the ARP DLB scheme and the commonly used DLB schemes, which are the ARR and RP DLB schemes