STUDY OF LOAD BALANCING THROUGH PARALLEL SCHEDULING ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS

Abstract

Load balancing algorithms can improve the performance of multiprocessor systems by judiciously redistributing the workload among its processors. Dynamic load balancing is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimate. Parallel scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate to schedule the work. Parallel scheduling is able to accurately balance the load by using global load information. The primary advantage of this approach is that it provides high-quality, scalable load balancing with high locality. Communication costs are thus significantly reduced compared to other existing algorithms. Parallel scheduling algorithms at runtime for Tree, Hypercube and Mesh networks are discussed in this dissertation. Simulation is carried out for performance comparison of this approach with the existing Dimension Exchange Method for N-dimensional hypercube networks. The contribution of this dissertation with regard to parallel scheduling is to modify the algorithm to make it more optimal.