SIMULATION STUDIES OF DYNAMIC LOAD BALANCING ALGORITHMS FOR MULTIPROCESSOR NETWORKS

Abstract

Load distributing algorithms can improve a Multi-Processor Systems (MPS) performape by judiciously redistributing the workload among its nodes. Dynamic Load Balancing (DLB) becomes essential for the efficient use of MPS when handling problems with unpredictable load estimates. Since centralised load balancing approach makes use of a high degree of knowledge and becomes less feasible due t.o load balancing communication overhead, hence distributed load balancing algorithms are appreciated and these are discussed in this dissertation report. This dissertation reports work of applying various DLB strategies on three multiprocessor networks viz. Hypercube, Hypertree, Folded Mesh structure and comparing performance of these strategies on above mentioned networks. Simulation study is carried out by generating a problem task which unfolds recursively into subtasks giving an arbitrary tree structure. DLB strategies aim at balancing this task tree at every level so as to optimize total execution time and load imbalance among processors.