A TASK CLUSTER BASED LOAD BALANCING ALGORITHM FOR TASK ALLOCATION IN DISTRIBUTED SYSTEMS

With the recent enhancements in massive parallel processing technologies, the problem of scheduling tasks in multiprocessor systems is becoming progressively important. The problem of scheduling task graph in parallel and distributed computing system is a well defined NP-complete problem. The problem of task assignment, in heterogeneous computing systems, has been premeditated for many years with many distinctions. In a Distributed Computing Systems (DCSs), a program is split into small tasks and distributed among several computing elements to minimize the overall system cost.? In real life situation when number of tasks is much larger than number of processors, a task clustering approach is very useful for allocating tasks on the basis of some predetermined criteria.?This paper deals with the problem of task allocation in a DCS such that the load on each processing node is almost balanced. The present work aims at the development of an effective algorithm for allocating ‘m’ tasks to ‘n’ processors in a given distributed system using task clustering. The model includes Inter Task Communication Cost (ITCC) along with the Execution Cost (EC). A new concept of Load Balancing Factor (LBF) is introduced to judge the degree of load balancing. Value one, of LBF, signifies a perfect load balancing.?