Efficient Load Balancing Algorithms for Parallel and Distributed Systems

Abstract

Parallel and Distributed computing is essential for modern research as the demand for more and more computing power is continuously increasing. A number of aspects within parallel and distributed computing have been explored in recent years, however two of the most pertinent issues relate to the design of scalable interconnection network topology and task allocation for load balancing. This work addresses these two problems. The first part of the thesis presents the design and evaluation of a highly scalable and economical interconnection network topology known as the STH (Serially Twisted Hypercube). It begins with a brief survey of various interconnection network topologies proposed in literature followed by the design principles on which the proposed STH interconnection network will be based upon. Various properties of the proposed topology are derived and then compared with other topologies on a number of interconnection networks evaluation parameters. The second part of the thesis deals with the task allocation problem taking into account load balancing. Exploiting the full potential of a parallel and distributed system requires efficient allocation of the program tasks to the diversely capable machines within the system. If the task allocation strategy is not properly framed, machines in the system may spend most of their time waiting for each other instead of performing useful computations. This part of the thesis focuses on static task allocation considering load balancing in heterogeneous distributed computing systems sometimes also referred to as heterogeneous multicomputer systems (HMS). The thesis first presents a brief literature survey on the proposed solutions and then classifies them according to the solution techniques. It then presents two mathematical models based on fuzzy logic to solve the task allocation problem. Finally based on the proposed models the the thesis presents two algorithms to solve the aforementioned problem. The algorithms are coded in C and the proposed models are verified by executing the corresponding programs with several sets of randomly generated data. Experimental results prove that the algorithms successfully allocate tasks to the machines whilst balancing the allocated task load. Analysis of the proposed method also proves that its complexity is low compared to similar existing approaches.