LB_Migrate

Abstract

Parallel and distributed environments are used to solve large scientific and engineering problems that often are irregular and data parallel. However, performance of many parallel applications is affected by computation overheads, communication time and load imbalance. Among these factors, load imbalance is caused by the irregular nature of the problem, its algorithm, the difference in processor characteristics, and runtime loads. A number of applications achieve load balancing by one-time assignment of task. However, a number of applications have workloads that are unpredictable, and vary over the course of their execution. For such type of applications, load balancing is achieved by dynamic assignment of tasks at runtime. A large group of scientific applications has parallel loops as major source of concurrency. However, due to the irregular execution times of the loops, it is difficult to achieve optimal performance without dynamic load balancing. There are number of dynamic load balancing tools and libraries have been developed for different kind of applications. However these libraries fail to address all three degradation factors i.e. problem, algorithmic, and systemic. In this thesis a dynamic load balancing library called LB_Migrate is presented which addresses the degradation factors in application with parallel loops. The library provides a range of dynamic scheduling techniques and data migration strategies to achieve effective load balancing. It is designed to be independent of the host application data structure hence providing the flexibility to be used with different applications. The analysis of the experimental results using LB_Migrate with different applications indicates consistent performance improvement, and low overhead cost by the use of the library.