# Scheduling Algorithm: Tasks Scheduling Algorithm for  Multiple Processors with Dynamic Reassignment

Authors: Pradeep Kumar Yadav; M. P. Singh; Harendra Kumar
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

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.


---

## Body

## 1. Introduction

Over the last several years, distributed computing systems have become popular as a very
attractive option for fast computing and information processing. Distributed computing system is
used to describe a system whenever there are several computers interconnected
in some fashion so that a program or procedure runs on the system with multiple
processors. In a heterogeneous computing system, the tasks of an application
program must be assigned to the heterogeneous processors to utilize the computational
capabilities and resources of the system efficiently. However, it is a
difficult problem to compute an assignment of tasks to processors for which the
total cost of running the program is minimized. Static and dynamic
algorithms can be extremely efficient in homogeneous systems. If all processors
are identical then the choice “to which node should we assign the next task?”
falls on the processor with the fewest outstanding jobs [1]. However in
heterogeneous distributed environments, where not all nodes have the same
parameters, selecting the optimal target processor requires more elaborate
algorithms.Stone [2] has suggested an efficient optimal
algorithm for the problem of assigning tasks to two processors by making use of
the well-known network flow algorithm in the related two-terminal network
graphs. If the structure of a distributed program is constrained in certain
ways, it is possible to find the optimal assignment over a system made up of
any number of processors in polynomial time. When the structure is constrained
to be a tree, the shortest tree algorithm developed by Bokhari [3] yields the
optimal assignment. Towsley [4] generalized the results of Bokhari to the case
of series-parallel structures. A further generalized program structure is a
partial K-tree in which trees are partial l-tree and series-parallel structures
are partial 2-tree [5] assuming
distributed system as fully interconnected, that is, there exists a
communication link between any two machines. However, the general N-processors
problem (N>3) in
a fully interconnected system is known to be NP-complete [6, 7]. Lee et al. [8] and
Cho and Park [9] have suggested an optimal algorithm for the general structure
problem in a linear array network with any number of processors.All the above assignment models are static because
they assume that once a task is assigned to a processor, it remains there
statically during the execution of a distributed program. These models deal
with the global information, which is assumed to be constant during the program
execution, of program’s activity. However the static model assumes that the
problem can be partitioned into several tasks each of which contains a unique
computational characteristic. In a general case each task may have multiple computational
characteristics due to the dynamic control behavior ofthe task. Such tightly and medium-coupled portions of
code task will be more difficult to break up and assign to different
processors. When the characteristics of the computation change, a new
assignment must be computed. By “characteristics of the computation” we mean
the ratios of the times that the program spends in different parts of the
program. In order to make the best use of
computational characteristics and resources in a distributed heterogeneous
computing system, it is essential to reassign tasksdynamically during program execution, so asto take advantage of changes in the local reference patterns of the program. Dynamic
algorithms are employed more frequently because they offer a better efficiency,
having the flexibility of tasks migration. In addition, usually dynamic
algorithms are neither very complicated to construct nor costly to run. Hence
dynamic algorithms have the potential to outperform static algorithms in
general. Clearly, the gains from relocating tasks must outweigh the cost of
relocation. For this relocation, detailed information on a program’s activity
over its lifetime can be collected at each time slot of lifetime. We use phase
as the unit of the time
slot for gathering more detailed information of program activity. Bokhari [10] analyzed the problem of dynamic assignment
in a two-processor system, which permits relocation of tasks from one processor
to the other at certain points during the execution of the program. This
relocation incurs a predefined relocation cost that contributes to the total
cost of running the program and code-conversion overheads. Also it is shown
that an optimal dynamic assignment corresponds to a “dynamic” partition imposed
by a minimum weight cut in an extended graph. In this paper, we consider the
dynamic task assignment problem for a general program structure and a
heterogeneous N-processors in DCS.The rest of the paper is organized as follows. Definitions
and assumptions are defined first in Section2. In Section 3, tasks
allocation problem has been discussed. The proposed method and algorithm have
been explained in Sections 4 and 5 concludes this paper.


## 2. Definitions and Assumptions

### 2.1. Definitions

(i)
Phase: a phase of a distributed program is a contiguous period of time during
which only one task is executed.
During this period, the executing task may communicate with any number of the
remaining task. A task may not be moved from one processor to another during a phase;
it may be moved only between them.  A
task may complete its execution in more than two phases; therefore, the number
of phases of the executing program is always more than the number of the
tasks.(ii)
Execution cost: the execution costekij is the amount of the work to be
performed by the executing task  ti on the processor  pi  during
the kth phase.(iii)
Intertask communication cost: the
intertask communication costckij is incurred due to the data units
exchanged between the executing task ti and residing task tj if
they are on different processors during the process of execution in kth phase.(iv)
Residence cost: residence costrkij (where 1≤i≤M&1≤j≤N) is the amount of time spent by the residing task
(other than executing task) ti on the processor pi in kth
phase. These costs may come from the use of storage.(v)
Relocation cost: relocation costrelik is the cost of reassigning the ith task from one processor to another
processor at the end of kth phase.


### 2.2. Assumptions

(i)
The
program to be executed is assumed to be collection of tasks that are free, in
general, to reside on either of the processors. A task may be a module of
executable program.(ii)
The
given program runs in various phases with one of its task executing on a
processor in each phase and each of the other tasks residing on any of the
processors.(iii)
In
each phase, execution cost (EC), residence cost (RC) of nonexecuting tasks,  intertask communication cost (ITCC) of
executing task with nonexecuting tasks, and relocation cost (REC) for
reassigning each task from one processor to the others at the end of  phases are known.(iv)
Some
of the tasks have restrictions for being allocated on some particular processor
because of the nonavailability of desired facilities which may include access
to particular peripheral device, access to a particular task, and high speed
arithmetic capability of the processor. The execution costs of such tasks are
taken to be infinite on
those processors where these tasks can not be executed.


## 2.1. Definitions

(i)
Phase: a phase of a distributed program is a contiguous period of time during
which only one task is executed.
During this period, the executing task may communicate with any number of the
remaining task. A task may not be moved from one processor to another during a phase;
it may be moved only between them.  A
task may complete its execution in more than two phases; therefore, the number
of phases of the executing program is always more than the number of the
tasks.(ii)
Execution cost: the execution costekij is the amount of the work to be
performed by the executing task  ti on the processor  pi  during
the kth phase.(iii)
Intertask communication cost: the
intertask communication costckij is incurred due to the data units
exchanged between the executing task ti and residing task tj if
they are on different processors during the process of execution in kth phase.(iv)
Residence cost: residence costrkij (where 1≤i≤M&1≤j≤N) is the amount of time spent by the residing task
(other than executing task) ti on the processor pi in kth
phase. These costs may come from the use of storage.(v)
Relocation cost: relocation costrelik is the cost of reassigning the ith task from one processor to another
processor at the end of kth phase.


## 2.2. Assumptions

(i)
The
program to be executed is assumed to be collection of tasks that are free, in
general, to reside on either of the processors. A task may be a module of
executable program.(ii)
The
given program runs in various phases with one of its task executing on a
processor in each phase and each of the other tasks residing on any of the
processors.(iii)
In
each phase, execution cost (EC), residence cost (RC) of nonexecuting tasks,  intertask communication cost (ITCC) of
executing task with nonexecuting tasks, and relocation cost (REC) for
reassigning each task from one processor to the others at the end of  phases are known.(iv)
Some
of the tasks have restrictions for being allocated on some particular processor
because of the nonavailability of desired facilities which may include access
to particular peripheral device, access to a particular task, and high speed
arithmetic capability of the processor. The execution costs of such tasks are
taken to be infinite on
those processors where these tasks can not be executed.


## 3. Problem Statement

Consider a distributed program consisting of a setT={t1,t2,t3,…,tM} of M tasks to be
allocated to a set P={p1,p2,p3,…,pN}
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, that is, (1)TCOST(A)=EC(A)+RC(A)+ITCC(A). In order to
make the best use of the resources in a DCS, we would like to find an
assignment having minimum cost.


## 4. Proposed Method and Algorithm

The problem for allocating a program dynamically that
has been divided intoK number of phases is to determine the optimal task
allocation strategy by considering the phasewise EC for executing task and RC
for nonexecuting tasks during the phases. The phasewise processing efficiency
of individual processor is given in the form of matrix EMC(,,)=(ekij)
of order (K×M×N) and RC of each residing task is reflected through matrix RCM(,,)=(rkij) of order (K×M×N). ITCC between executing task and
another tasks is taken
in the form of matrix ITCCM(,,)=(ckij) of order (K×M).
The kth column of this matrix represents the ITCC between the executing task
and all other residing tasks for the kth phase. Relocation costs for
reassigning the tasks from one processor to another at the end of the phases is
shown by matrix RECM(,)=relik of order (M×K) where relik is the relocation cost for reassigning the ith task from one processor to the
another at the end of kth phase. In this paper, we have considered that the relocation cost relik is a constant when ith task relocates from one processor to another at the end of the kth phase.
The model starts from the first phase for allocating the tasks and moves to the
next phase.  Let ts be the sth executing task
and tg(s≠g) be the gth residing tasks during kth phase. The execution
for the executing task ts and residing task  tg to the
processors in the kth phase have been depicted in Figure 1.Figure 1
Allocation of the tasks inkth phase.The executing taskts (represented by*) must
be assigned to processor pr  during kth phase for which sum of its
execution and relocation costs is minimum. This minimum cost for the task ts is represented by TECk. When residing task tg resides on a processor, it has three-type costs, that is. residing, relocation,
and communication cost with the executing task ts. Therefore, the residing
task tg must be assigned to that processor ph where it
has minimum costs mentioned above. This minimum cost for the task tg is
represented by  TRC(g)k. Similarly, all other residing tasks are
assigned to the processors. The total cost TRCk due to the residing
tasks in the kth phase will be: (2)TRCk=∑i=1i≠sMTRC(i)k. The total cost (TCOST)k for the  kth phase is  the sum of
TECk and TRCk, that is, (3)(TCOST)k=TECk+TRCk. The total optimal cost, TCOST, for the program will
be as follows: (4)TCOST=∑k=1K(TCOST)k. Using the arrays
representation for the execution, residing, intertask communication, and relocation
costs, a mathematical model has been developed for allocating the distributed
program dynamically which has been splitting into any number of tasks partition
and completing their execution in any  number of phases. The process of allocating the
tasks to the processors is given in the form of Algorithm 1.Algorithm 1:To assign a distributed program consisting
of a set T={t1,t2,t3,…,tM}
of M tasks which is divided into K phases to a set of n processors P={p1,p2,p3,…,pN} in order to minimize the total cost.
Step-1: Input:K, M, N, ECM(,   ,), RCM( , , ), RECM( , ), ITCCM( , , )Step-2: Start with phase k=1.Step-3: Calculate NECM(,  ,) by adding the ECM(,  ,) with RCM(,  ,) for kth phase.Step-4: Assign the
executing task ts to processor pr for which cost is
minimum say TECkStep-5: Add the effect of
communication cost of executing tasks ts with other residingtasks
by addingkth column of ITCCM(,   ,) to all the column of NECM(,   ,)except therth column at which this task is assigned.Step-6: Assign the
residing tasks tg(g=1,2,…,M,g≠s) to processors ph at
which time isminimum sayTRC(g)kCalculate:TRCk=∑i=1i≠sMTRC(i)kStep-7: Store executing and residing tasks
and their position on processors in a lineararrayPOSS(,)k.Calculate:(TCOST)k=TECk+TRCkStep-8:k=k+1.Step-9: Repeat step-3.Step-10: Modify the cost of
NECM(,  ,) by adding the relocation cost relsk−1 to all eksj,j=1,2,…,N,j≠r.Step-11: Modify the cost of
NECM(,   ,) by adding the relocation cost relgk−1 to ekgj,j=1,2,…,N,j≠h.Step-12: Repeat step-4 to
step-6.Step-13: Store executing and residing tasks
and their position on processors in linear arrayPOSS(,)k+1.Calculate:(TCOST)k+1=TECk+1+TRCk+1Step-14: If k≠Kthenrepeat step-8 to step-14.elseStep-15: Calculate:TCOST=∑k=1K(TCOST)kStep-16: End.Implementation of the Model
Example 1.
Consider
a program made up of four tasks{t1,t2,t3,t4} to
be allocated on two processors {p1,p2} in five phases.
Task t1  completes its execution in two phases (in phase 1 and phase
5). The various matrices to be taken as input are described phasewise in Tables 1
and 2.Table 1
Phasewise ECM(,   ,) and RCM(,   ,).
PhasesTasksExecution costResidence costECM(,   ,)RCM(,   ,)p1p2p1p21t126——t2——32t3——22t4——412t1——21t2∞4——t3——13t4——233t1——21t2——12t346——t4——214t1——13t2——32t3——12t432——5t12∞——t2——31t3——21t4——12Table 2
ITCCM(,   ,) and RECM( , ).
Phasewise communicationRelocation cost of thecost between executing tasktasks at the end of phaseand other residing tasksITCCM(,   ,)RECM( , )Phases1234512345Taskst1—621—2332—t22—4202323—t332—221224—t4240—32422On applying the present tasks
allocation model, we get the following optimal assignment as follows:(5)POSS(,)1={(t1,p1),(t2,p1),(t3,p1),(t4,p2)},TCOST1=TEC1+TRC1=10.POSS(,)3={(t1,p2),(t2,p1),(t3,p1),(t4,p2)},TCOST2=TEC2+TRC2=15.POSS(,)3={(t1,p2),(t2,p1),(t3,p1),(t4,p2)},TCOST3=TEC3+TRC3=12.POSS(,)4={(t1,p2),(t2,p2),(t3,p1),(t4,p2)},TCOST4=TEC4+TRC4=12.POSS(,)5={(t1,p1),(t2,p2),(t3,p1),(t4,p1)},TCOST5=TEC5+TRC5=10.TCOST=∑k=1K(TCOST)k=59.
The result of Example 1 is shown by Figure 2. Here circles labeled with tasks number represent tasks (tasks represented by* are
executive task and others are residing tasks). Costs associated with tasks
are their execution costs (for tasks represented by*)  or residence costs. The edges connecting the executing task
with  other residing tasks during the same phase represent the communication and
weights of these edges represent
communication costs between the executing task and other residing tasks.
The edges connecting the task of a phase to the task of the next phase
represent the relocation of the tasks and the weights of these edges represent
the costs of relocating the tasks. For example, the task t2 is
relocating from processor p2 to processor p1 between the
phase 2 and phase 3. The above result shows that the assignments of the tasks
are changing phase to phase.  Optimal
cost for this task program is 59.Figure 2
Optimal assignment graph(TCOST=59).Example 2.
Consider a program made up of seven tasks{t1,t2,t3,t4,t5,t6,t7} to be
executed on three processors {p1,p2,p3} in
eight phases. The various matrices to be taken as input are described phasewise
in Tables 3 and 4.Table 3
Phasewise ECM(,   ,) and RCM(,   ,).
PhasesTasksExecution costsResidence costsECM(,   ,)RCM(,   ,)p1p2p3p1p2p31t1———312t2264———t3———342t4———432t5———432t6———211t7———3122t1648———t2———213t3———322t4———342t5———332t6———144t7———2323t1———231t2———222t3———342t463∞———t5———321t6———322t7———3114t1———212t2———112t3———331t4———124t5———221t6864———t7———1135t1———211t2———212t3668———t4———222t5———432t6———123t7———2126t1———322t2———141t3———121t4———211t5542———t6———221t7———1127t1———121t2∞68———t3———231t4———231t5———122t6———132t7———2218t1———211t2———112t3———242t4———233t5———114t6———322t7478———Table 4
ITCCM(,   ,) and RECM( , ).
Phasewise communication cost of  executingRelocation cost of the tasks at the end oftask with other residing tasksphasesITCCM(,   ,)RECM( , )Phases1234567812345678Taskst12—3242403341323—t2—02220—32153334—t34304—2221132344—t422—213231432432—t521022—022322242—t6622—20222343243—t72334203—3443342—The present tasks allocation model
gives the following optimal assignment as follows:(6)POSS,1={X},TCOST1=TEC1+TRC1=21,POSS,2={B},TCOST2=TEC2+TRC2=22,POSS,3={C},TCOST3=TEC3+TRC3=22,POSS,4={D},TCOST4=TEC4+TRC4=31,POSS,5={E},TCOST5=TEC5+TRC5=20,POSS,6={F},TCOST6=TEC6+TRC6=21,POSS,7={G},TCOST7=TEC7+TRC7=24,POSS,8={H},TCOST8=TEC8+TRC8=24,TCOST=∑k=1K(TCOST)k=185,where (7)X=(t1,p2),(t2,p1),(t3,p1),(t4,p3),(t5,p3),(t6,p1),(t7,p2),B=(t1,p2),(t2,p1),(t3,p2),(t4,p3),(t5,p3),(t6,p1),(t7,p2),C=(t1,p2),(t2,p2),(t3,p3),(t4,p2),(t5,p3),(t6,p1),(t7,p2),D=(t1,p2),(t2,p2),(t3,p3),(t4,p2),(t5,p3),(t6,p1),(t7,p2),E=(t1,p2),(t2,p2),(t3,p2),(t4,p2),(t5,p3),(t6,p1),(t7,p2),F=(t1,p2),(t2,p1),(t3,p3),(t4,p2),(t5,p3),(t6,p1),(t7,p2),G=(t1,p2),(t2,p2),(t3,p3),(t4,p2),(t5,p3),(t6,p1),(t7,p2),H=(t1,p2),(t2,p2),(t3,p3),(t4,p1),(t5,p1),(t6,p1),(t7,p1). The results of Example 2 are shown by Figure 3. Task t2 completes its execution in two phases (in phase
1 and phase 7). The execution cost for the task t2 is 2 in phase 1
and 4 in phase 7. The above result for the executing task t2 shows that the assignments
for both the phases are different, that is; it depends on the characteristic of the
computation. The optimal cost for tasks program is 185.Figure 3
Optimal assignment graph(TCOST=185).


## 5. Conclusion

We have
presented an efficient solution technique for tasks execution dynamically in
DCS. Starting with the definitions of the phase of a modular program, we have
developed a mathematical-based assignment technique for allocating the tasks of
a program, divided intok-phases to N>2 processors. The present model is compared
with Kumar et al. [11] and Bokhari [10].
Kumar et al. [11] have developed a mathematical model for
allocating “M” tasks of a program to “N” processors (M>N), divided into any
number of phases. In this paper, authors have considered only execution, residence,
and intertask communication costs. It is also observed that the model [11] does
not work for the system program having relocation cost for reassigning
each task from one processor to the others at the end of phases. Bokhari
[10] has developed a
graph theoretical approach for finding out the optimal dynamic assignment of a
modular program for the two-processor system considering execution, residence,
intertask communication, and relocation costs. The model [10] can not find out
the solution when the system is NP-hard (N>2) while the present model
is applicable for the DCS having any number of phases and processors with
random program structure. The study of the time complexity of the present model
has also been made and compared with Bokhari [10] and Cho and Park [9]. For Bokhari
[10], the time complexity of the solution of the dynamic task assignment
problem for the two-processor system is O(M3K3). The time
complexity of the present tasks model for
any number of processors is
O(M2N2K) which is time-saving as compared to O(M2N2K2log NMK) for the Cho and Park [9].



---

*Source: 578180-2008-04-24.xml*