A load balanced distributed computing system

The main objective of this study is to transform a network of workstations into a load balanced distributed computing system (LBDCS), LBDCS is to impr ove the performance of generally underutilized timeshared workstations and highly CPU intensive independent or parallel applications. It affects the i nitial placement of the tasks and task migrations later during their execut ions. One of the important implementation features of LBDCS is that it does not use any intermediary such as PVM (parallel virtual machine) or MPI (me ssage passing interface) for inter-task communication. It defines various metrics to characterize the level of load and dynamicall y monitors the system and applications to detect the load imbalances, The e mployed load balancing algorithm makes use of predicted load indices which are computed as weighted averages of the past system and application loads. Performance analysis of the system has been conducted using a number of hyp othetical applications and two simple real life applications (in this case matrix multiplication and merge-sort). Hypothetical applications provide fl exibility for testing the system under tunable application conditions. Usin g load balancing, an average speedup and efficiency close to 70% of their t heoretical upper bounds are observed for different applications. Copyright (C) 1999 John Wiley gr Sons, Ltd.