DYNAMIC LOAD REDISTRIBUTION ALGORITHM FOR REAL-TIME APPLICATIONS IN MESSAGE PASSING SYSTEM

Abstract

Load imbalance is a fundamental problem that arises in making effective use of the total computing power of a distributed system. Load imbalance occurs at a given time when one or more processors have very few tasks to handle while other processors may have many. Insufficient parallelism, poor

task distribution, or non-equal size tasks; are different reasons for load imbalance. This imbalance reduces the performance of parallel systems. To achieve good performance the workload must be redistributed among all processors, this process is called load balancing. The purpose of load balancing strategies is to improve the performance of the system by redistributing the workload among processors and minimize data communications. This will lead to a reduced execution time. Load balancing algorithms may be either static or dynamic. Static load balancing algorithms use only statistical information about the system to make load balancing decisions. On the other hand, dynamic load balancing algorithms attempt to dynamically balance the load to reflect the current system state. Dynamic load balancing can be classified to be either centralized or decentralized (distributed). In centralized algorithms, the global load information is collected at a single processor, called the master processor. This processor controls the load redistribution based on the information it receives from all other processors. On the contrary, decentralized algorithms perform load redistribution by an algorithm that is replicated in every processor. Each processor broadcast its load information to all other processors, and takes into account its load status before migration. Since every processor in the system keeps track of the global load information a load balancing decision can be made by any processor.