Efficient load balancing strategies on a network of computers: A case study with two scientific computing problems

Parallel computing has been recently taken over by distributed computing technologies especially in academia due to the cheaper and low cost maintenance of these machines. However, algorithm design techniques for cluster or heterogeneous machines still follow the approaches used in parallel computers, such as on shared memory machines. One of the crucial and critical issues in distributed computing is load balancing the tasks among the various processors. Load balancing is a difficult and challenging problem. The strategies/techniques vary greatly based on the applications.; In this thesis, we consider two scientific computing applications. Fast Fourier Transform (FFT) and multidimensional matrix multiplication. We design a parallel/distributed algorithm for the FFT problem by exploiting data locality so as to minimize communication. We implemented the algorithm on a Beowulf cluster. In comparison to the well known existing parallel algorithm, our algorithm, produces 15% speedup.; For the multidimensional matrix multiplication problem there are two issues to consider: representing the multidimensional data structure efficiently so as to minimize storage space and adopting a load balancing strategy for the partitioning of the data onto the heterogeneous machines. We will develop two strategies, static and dynamic. In static partitioning, the data is distributed before runtime. Dynamic partitioning follows a hierarchical manager-worker model where the tasks are allocated by the manager on-demand. The results indicate the dynamic strategy produces better results since it considers the underlying architecture of the heterogeneous machines for efficient load balancing.