A Replica Based Co-Scheduler (RBS) for Fault Tolerant Computational Grid - Cloud, Grid and High Performance Computing: Emerging Applications - page 107

Table 1. Chromosome Structure

Node No. for Module1 Node No. for Module2 Node No. for Module3 Node No.

for
Module 4

Node No. for Module5

time of the job, the resultant allocation pattern
corresponds to a chromosome suggesting the al-
location of job modules on the appropriate nodes
[8]. This information is helpful as it is eventually
used by the RBS. Taking this allocation of the job
modules as suggested by TSM as the prerequisite,
RBS replicates the modules of the sick nodes to
the healthy nodes as a precautionary measure to
overcome the loss due to possible node failures
thus increasing the fault tolerance of the system.
For the job submitted for execution, TSM
generates a population of chromosomes populated
randomly. This is done by dynamic generation of
the chromosomes of size (number of genes) equal
to the number of modules of the job such that
each gene represents the allocation of a module
to a node. Starting from the left hand side, the
first gene corresponds to the node allocation for
the first module, the second gene referring to the
node allocation for the second module and so on
till the last gene corresponding to the last module
as shown in Table 1.
Table 2 presents an example of a job with five
modules on a cluster with six nodes. The gene
positions here can be read as module 1 being al-
located to node 6, module 2 on node 2, module 3
on node 6, module 4 on node 1 and module 5 on
node 5.
For the population, TSM uses GA to evolve
towards a chromosome offering the minimum

turnaround time using operators selection , cross-
over and mutation . This chromosome gives us the
allocation pattern using which the job can be
scheduled to minimize the turnaround time of the
job. This process is done for all the clusters match-
ing the specialization of the job resulting in a
chromosome generated for each cluster offering
the minimum turnaround time to the job. These
costs are compared to select the cluster offering
the least turnaround time corresponding to some
allocation pattern responsible for it [8].
For any cluster of the grid, the allocation of
modules to the individual nodes depends on three
factors viz. processing speed of the node, time to
finish execution of already allocated modules to a
node and the communication cost in terms of the
bytes exchange required between the modules.
This cost becomes the fitness function for the
allocation of a job with M modules and can be
represented as

M i-1

( )

NEC = E w B D x x T

∑ i=1 ∑

ijkn .x +

. . +

kin ijk ihj kln ijk hjl prkn

h=1

(i)

Here E ijkn represents the processing time of the
node P k under consideration calculated for node P k
for module m i of size I i of job J j on cluster C n as

Table 2. A Sample Allocation of Nodes to the Modules

6 2 6 1 5