Tasks Scheduling Algorithm for Multiple Processors with Dynamic Reassignment

Distributed computing systems [DCSs] offer the potential for improved performance and resource sharing. To make the best use of the computational power available, it is essential to assign the tasks dynamically to that processor whose characteristics are most appropriate for the execution of the tasks in distributed processing system. We have developed a mathematical model for allocating “M” tasks of distributed program to “N” multiple processors (M>N) that minimizes the total cost of the program. Relocating the tasks from one processor to another at certain points during the course of execution of the program that contributes to the total cost of the running program has been taken into account. Phasewise execution cost [EC], intertask communication cost [ITCT], residence cost [RC] of each task on different processors, and relocation cost [REC] for each task have been considered while preparing a dynamic tasks allocation model. The present model is suitable for arbitrary number of phases and processors with random program structure.

Consider a distributed program consisting of a set T={t₁,t₂,t₃,..,t_M} of M tasks to be allocated to a set P={p₁,p₂,p₃,…,p_N} of N processors divided into K phases. The basis for dynamic program model is the concept of the phases of a task program. With each phase the following information is associated:

(1)The executing task during this phase and its execution cost on each processor in a heterogeneous system.

(2)Residence costs of the remaining tasks, except for the executing task, on each processor. These costs may come from the use of storages.

(3)Intertask communication cost between the executing task and all other tasks if they are on different processors.

(4)An amount of relocation cost for reassigning each task from one processor to the others at the end of the phases.

In general, the objective of task assignment is to minimize the completion cost of a distributed program by properly mapping the tasks to the processors. The cost of an assignment A, TCOST(A), is the sum of execution, intertask communication, residence, and relocation costs.

   Contributed By:    ARUP ROY,  LECTURER (CSE)  , MALLABHUM INSTITUTE OF TECHNOLOGY.