Grid Computing

What is Grid Computing?

• Grid computing is a computing infrastructure that
combines computer resources spread over
different geographical locations to achieve a
common goal.
• Distributed architecture combining
resources from multiple locations.
• Performs tasks by dividing them into subtasks for
concurrent processing.
• Acts as a virtual supercomputer through resource
sharing.
 What is Grid Computing?
• Nodes contribute CPU power, memory, and
storage
• Subset of Distributed and Parallel Computing
• Tasks include data analysis, simulations,
large-scale computations
• For Example :Meteorologists use grid
computing for weather modeling. It enables fast
processing ofmassive weather data by distributing
computations across geographically dispersed
systems and combining results
efficiently.
Grid Computing
 Working of Grid Computing
• A grid computing network consists of three
main types of components:
• Control Node: A computer, usually a server or
a group of servers which administrates the whole
network and keeps the account of the resources in
the network pool.
• Provider: Contributes its unused resources to
the network pool.
• User: Requests and uses resources from
the network.
• A computer can act as both user or provider
depending on its current need.
 Working of Grid Computing
Networks can be:
• Homogeneous: Same platform and OS.
• Heterogeneous: Different platforms and OSs.
• Middleware manages communication,
resource sharing, and scheduling across the grid.
• The control node ensures providers are
not overloaded with tasks.
 Importance of Grid Computing

• Scalability – dynamically add

computational capacity
• Resource Utilization – efficiently use idle machines
• Complex Problem Solving – handle heavy
computations like climate models
• Collaboration – enable global teamwork
• Cost Efficiency – reuse existing hardware
 Evolution of Grid Computing

• Proposed by Ian Foster & Carl Kesselman

(1999)
• Initial idea: compute power consumed like
electricity
• Now seen as collaborative distributed
computing
• Foundation for modern cloud computing
 Types of Grid Computing

• Computational Grid – High-performance

computing for scientific tasks
• Scavenging Grid – Utilizes idle CPUs from
normal computers
• Data Grid – Distributed storage access as
unified resource
 Advantages of Grid Computing

• High resource utilization

• Parallel task execution
• Scalability and collaboration across domains
 Disadvantages of Grid Computing

• Software still evolving

• Complex system management
• Limited flexibility
• Security risks due to distribution
Architecture and Middleware Overview
A typical grid architecture consists of four main layers:
• Grid Fabric: Physical layer with desktops, servers,
clusters, networks, and storage devices.
• Core Middleware: Provides security, job submission,
information services, storage access, and accounting. Ensures
authentication, single sign-on, and secure communication.
• User-Level Middleware: Offers programming tools,
APIs, libraries, compilers, and manages resource
allocation and scheduling.
• Grid Applications: User-facing layer for web portals
and scientific/business applications running on the grid.
• Adaptive Management: Handles monitoring,
optimization, and dynamic control across all layers.
Architecture
 Middleware in Grid Computing

• Middleware sits between the application layer

and the hardware infrastructure.
• It enables communication and coordination
between grid components.
• Facilitates efficient distribution of computing
tasks across multiple systems.
 Types of Middleware

• Message-Oriented Middleware (MOM):

Provides messaging infrastructure for
communication between components.
• Remote Procedure Call (RPC) Middleware: Allows
remote invocation of functions across the grid.
• Grid Services Middleware: Offers standardized
services such as resource discovery, allocation,
and security.
 Uses of Middleware – I

• Resource Management: Manages computing,

storage, and network resources by allocating
and monitoring workloads.
• Data Management: Handles data
transfer, replication, and centralized
storage for reliability.
• Job Scheduling: Determines optimal task
execution locations and allocates resources
efficiently.
 Uses of Middleware – II

• Workflow Management: Defines dependencies

and coordinates task execution in grid
applications.
• Security: Provides authentication,
authorization, and encryption for safe grid
operations.
• Monitoring & Management: Monitors grid
status, job execution, and enables system
administration.
 Middleware Layer Overview

• Middleware acts as the communication bridge

between Application and Hardware layers.
• Includes: Job Scheduling, Data Management,
Security, Monitoring, Workflow Coordination.
• Ensures interoperability and seamless task
execution across distributed resources.
 Scheduling Algorithms Overview

• Heuristic Algorithms: Min–Min, Max–Min,

Sufferage
• Metaheuristic Algorithms: Genetic algorithm
and Particle Swam Optimization.
• Metrics: Makespan, Load Balance, Cost
 Heuristic Algorithms

• Min–Min: Assign smallest completion time

first
• Max–Min: Assign longest minimum
completion task first
• Sufferage: Prioritize task that suffers most
without best machine
 Min–Min Algorithm Overview
• This is a static task scheduling algorithm used
for load balancing.
• The Min–Min algorithm first finds the
minimum execution time for all tasks across
available resources.
• It then selects the task with the least
execution time among them and assigns it to
the resource that yields the minimum
completion time.
• The same procedure is repeated iteratively
until all tasks are scheduled.
 Min–Min Algorithm Example: Initial
Execution Data
• Initial execution data for three tasks across
two virtual machines.
Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 140 ms 20 ms 60 ms

VM2 100 ms 100 ms 70 ms

 Min–Min Algorithm Example: Initial
Execution Data
• Initial execution data for three tasks across
two virtual machines.
Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 140 ms 20 ms 60 ms

VM2 100 ms 100 ms 70 ms

 Step 1: Select the Smallest Execution
Time
• T2 (20 ms on VM1) selected for
execution. VM1 now busy for 20 ms (R₁ =
20).
Virtual Machines T1 T2 T3

VM1 140 20 60

VM2 100 100 70

Step 2: Recalculate Completion Times
• T3 (70 ms on VM2) selected next. VM2 now
busy for 70 ms (R₂ = 70).
Virtual Machines T1 T2 T3

VM1 160 ∞ 80

VM2 100 ∞ 70
 Step 3: Remaining Task
• T1 (160 ms on VM1) selected last and executed. All
tasks scheduled.

Virtual Machines T1 T2 T3

VM1 160 ∞ ∞

VM2 170 ∞ ∞
 Final Schedule and Makespan
• Final Makespan = max(20, 70, 160) = 160 ms
• CTij = Rj + ETij

Order Task VM Start (ms) Finish (ms)

1 T2 VM1 0 20

2 T3 VM2 0 70

3 T1 VM1 20 160
 Max–Min Algorithm Overview
• Static task scheduling algorithm for load balancing.

• Steps:
• 1. Find the minimum execution time for each task.
• 2. Choose the task with the maximum execution time
among them.
• 3. Assign it to the machine with minimum completion time.
• 4. Repeat until all tasks are scheduled.

• Why 'Max–Min'?
• The heaviest task (maximum execution time) →
allocated to the best machine (minimum completion
time).
 Max–Min Algorithm Example: Initial
Execution Data
• Given Data:
• • T1 executes in 140 ms (VM1) or 100 ms (VM2)
• • T2 executes in 20 ms (VM1) or 100 ms (VM2)
• • T3 executes in 60 ms (VM1) or 70 ms (VM2)

Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 140 ms 20 ms 60 ms

VM2 100 ms 100 ms 70 ms

 Step 1 – First Selection
• Find minimum time for each task:
• • (100 ms, T1, VM2), (20 ms, T2, VM1), (60 ms, T3,
VM1)
• Select maximum among these → (100 ms, T1,
VM2)
• Execute T1 on VM2 for 100 ms.
Updated
• Virtual Table:Task 1 (T1)
Machines Task 2 (T2) Task 3 (T3)

VM1 ∞ 20 60

VM2 ∞ 200 170

 Step 2 – Next
Task
• Find minimum times: (20 ms, T2, VM1), (60 ms, T3,
VM1)
• Max among these = (60 ms, T3, VM1)
• Execute T3 on VM1 for 60 ms.
• Updated Table:
Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 ∞ 80 ∞

VM2 ∞ 200 ∞
 Step 3 – Remaining Task
• Remaining task: (80 ms, T2, VM1)
• Execute T2 on VM1 for 80 ms.
• All tasks completed.

Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 ∞ 80 ∞

VM2 ∞ 200 ∞
 Final Schedule and Makespan
• Order | Task | VM | Start (ms) | Finish (ms)
• 1 | T1 | VM2 | 0 | 100
• 2 | T3 | VM1 | 0 | 60
• 3 | T2 | VM1 | 60 | 140

• Formulas:
• CT₍ᵢⱼ₎ = Rⱼ + ET₍ᵢⱼ₎
• Makespan = max(100, 60, 80) = 100 ms
 Suffrage Algorithm Overview
• The Suffrage algorithm prioritizes tasks based on
how much they would “suffer” if not assigned to
their best resource.
• It calculates both the minimum and second
minimum completion times for each task, and the
difference between them defines the Suffrage
value.
• The task with the maximum Suffrage value is
assigned to the machine that gives the
minimum completion time.
The process repeats until all tasks are scheduled.
 Suffrage Algorithm Example: Initial
Execution Data
• Each task has three possible execution times
on three virtual machines.
Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 14 ms 10 ms 13 ms

VM2 8 ms 12 ms 17 ms

VM3 15 ms 9 ms 11 ms
 Step 1 – Compute Suffrage Values
• For each task:
• • T1 → FST_MCT = 8 (VM2), SEC_MCT = 14
(VM1)
→ SV₁ = 6
• • T2 → FST_MCT = 9 (VM3), SEC_MCT = 10
(VM1)
→ SV₂ = 1
• • T3 → FST_MCT = 11 (VM3), SEC_MCT =
13 (VM1) → SV₃ = 2
 Step 2 – Select and Assign
Task
• Select the task with the maximum suffrage
value.
• Assign T1 → VM2 (8 ms).
• Update Ready Time of VM2: R₂ = 8 ms.
• Recalculate suffrage for remaining tasks (T2,
T3).
 Final Schedule and Makespan
• Makespan = max(8, 9, 13) = 13 ms

Order Task VM Start (ms) Finish (ms)

1 T1 VM2 0 8
2 T2 VM3 0 9
3 T3 VM1 0 13
 Job Scheduling in Grid Computing
● In a grid-computing environment, multiple computers
located in different places work together as if they were
one giant virtual supercomputer.
● Applications are typically represented as workflows made
up of smaller, interdependent jobs.
● These jobs often rely on the outputs of earlier ones, the
entire workflow is modeled as a Directed Acyclic Graph
(DAG). Each node represents a task, and each edge
shows a data dependency between tasks.
 Objective of Job Scheduling
● Efficient scheduling is crucial because grid environments
are heterogeneous (processors have different speeds,
and communication links have different bandwidths).
● The objective of scheduling is to assign every task to a
processor and determine the execution order so that the
overall completion time (makespan) is minimized.
● Finding the optimal schedule is NP-hard, so heuristics
and meta-heuristics such as genetic algorithms are used
to find near-optimal solutions.
 Genetic Algorithm Overview
● Inspired by Darwin’s theory of natural selection.
● It evolves a population of potential solutions through selection and
genetic operations to reach better solutions.
● A GA for job scheduling proceeds as follows:
1. Initialization – Generate an initial population of schedules, where each
schedule (chromosome) represents:
a. A valid task execution order (topological sequence of the workflow DAG).
b. A corresponding assignment of tasks to grid nodes (e.g., CPU1, CPU2, …)
2. Evaluation – Compute the fitness(= 1 / makespan) of each schedule.
3. Selection – Choose the fittest individuals (lower makespan) to
reproduce.
4. Crossover – Exchange genetic material, randomly pick pairs of selected
schedules and swap task-to-node mappings.
5. Mutation – Randomly alter some parts of schedule to maintain diversity
or to discover new, improved schedules..
6. Termination – Stop when, No improvement in best fitness is observed
for several iterations.
 Genetic Algorithm Example
● We have three tasks (T₁, T₂, T₃) and two grid nodes (VM₁, VM₂).
Each task must be assigned to either VM₁ or VM₂.
● Each of the 3 tasks has 2 options, total schedules = 2^3 = 8.
● Aim: to assign each task to a virtual machine, VM so that the
makespan is minimized.
● The Expected Completion Time (ECT) matrix is:

Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 140 ms 20 ms 60 ms

VM2 100 ms 100 ms 70 ms

Genetic Algorithm Example:Step 1(Initialisation)
Initial population of schedules
Randomly pick four schedules (sample)
ID (T₁,T₂,T₃) → VM Workload on VM₁ Workload on VM₂ Makespan (max)

S₁ [VM₁, VM₁, VM₁] 140+20+60=220 0 220

S₂ [VM₁, VM₁, VM₂] 140+20=160 70 160

S₃ [VM₁, VM₂, VM₁] 140+60=200 100 200

S₄ [VM₁, VM₂, VM₂] 140 100+70=170 170

S₅ [VM₂, VM₁, VM₁] 20+60=80 100 100

S₆ [VM₂, VM₁, VM₂] 20 100+70=170 170

S₇ [VM₂, VM₂, VM₁] 60 100+100=200 200

S₈ [VM₂, VM₂, VM₂] 0 100+100+70=270 270

Genetic Algorithm Example: Step 2(Selection)
Use fitness-proportionate selection (Rank-Based).
Schedules with higher fitness have a higher chance to reproduce.

ID Mapping (T₁,T₂,T₃) Makespan Fitness (1/Makespan)

S₂ [VM₁, VM₁, VM₂] 160 0.00625

S₄ [VM₁, VM₂, VM₂] 170 0.00588
S₅ [VM₂, VM₁, VM₁] 100 0.01000
S₇ [VM₂, VM₂, VM₁] 200 0.00500

Selected Parents:

● Parent 1: S₅ [VM₂, VM₁, VM₁]

● Parent 2: S₂ [VM₁, VM₁, VM₂]
Genetic Algorithm Example: Step 3(Crossover)
Choose a crossover point at position 2 (after the second gene).

Perform single-point crossover:

Parent Chromosome

P₁ (S₅) [VM₂, VM₁, VM₁]

P₂ (S₂) [VM₁, VM₁, VM₂]

After Crossover:
Child New Chromosome New Schedule

C₁ [VM₂, VM₁, VM₂] T₁→VM₂, T₂→VM₁, T₃→VM₂

C₂ [VM₁, VM₁, VM₁] All tasks on VM₁

Genetic Algorithm Example: Step 4 (Mutation)
Perform mutation:
● Randomly select one gene, say, 3rd gene (corresponding to Task T₃).
● Randomly reassign it to a different VM.

Stage Chromosome Changed Gene Description

Before Mutation [VM₂, VM₁, VM₂] Gene 3 (T₃) Task 3 was on VM₂

After Mutation [VM₂, VM₁, VM₁] Gene 3 (T₃) Task 3 reassigned

to VM₁
Genetic Algorithm Example: Step 5 (Evaluation)
Evaluate offsprings:

Child Before Mutation After Mutation Effect on Makespan

C₁ [VM₂, VM₁, VM₂] [VM₂, VM₁, VM₁] 170 → 100 ms

C₂ [VM₁, VM₁, VM₁] [VM₁, VM₁, VM₁] 220 → 220 ms

Observation:
● C₁ (after mutation) actually matches S₅, the known optimal mapping.
● The GA has now “discovered” the best schedule.
Genetic Algorithm Example: Step 6 (New generation)
Next generation:
● Keeping the elite individual (S₅) unchanged (elitism).

● Replacing the worst (S₇, 0.00500) with the best new child (C₁, 0.01000).

Generation 2 Population Makespan Fitness

S₅ [VM₂,VM₁,VM₁] 100 0.01000

C₁ [VM₂,VM₁,VM₁] 100 0.01000
S₂ [VM₁,VM₁,VM₂] 160 0.00625
S₄ [VM₁,VM₂,VM₂] 170 0.00588

Observations: Now the population has converged around the optimal

mapping.
Genetic Algorithm Example: Step 6 (Convergence)
After a few generations, all chromosomes become identical (S₅-like).
Final Best Schedule (Makespan = 100 ms)
[T1→VM2, T2→VM1, T3→VM1]
Interpretation:
● VM₁ executes two light jobs (T₂, T₃) sequentially: 20 + 60 = 80 ms

● VM₂ executes the heavy job (T₁): 100 ms

→ Both VMs finish nearly together → perfectly balanced load.
 Particle Swarm Optimisation Overview
● Particle Swarm Optimization (PSO) is a population-based meta
heuristic algorithm inspired by social behavior of bird flocks and fish
schools.
● Instead of evolving chromosomes (as in Genetic Algorithms), PSO
models a group of particles, each representing a candidate solution (a
possible schedule of tasks across the available grid resources.)
● In PSO, all particles “fly” through the search space to find the best
position (optimal solution). Each particle has a position and a
velocity, which determine where it is in the search space and how it
moves.
● During each iteration, particles adjust their positions based on:
1. Their own experience — how good their best solution so far has
been (personal best, or pBest).
2. The experience of the entire swarm — the best solution any
particle has found so far (global best, or gBest).
 PSO in Grid Computing
● In the context of grid computing, a particle represents a mapping of
tasks to virtual machines.
● For a workflow with n tasks and m machines: Each particle’s position
vector indicates which machine executes each task.
● Each particle’s velocity vector indicates how likely a task is to move to
another machine in the next iteration.
● For example, in a grid with 3 tasks (T₁, T₂, T₃) and 2 machines (VM₁,
VM₂), a particle’s position might look like:
Position = [1, 2, 1]
● The fitness function for each particle measures how good the
schedule is, typically using the makespan (total completion time of all
tasks):
Fitness = 1/Makespan
 PSO Algorithm
1. Initialization: Generate a population (swarm) of random particles.
Each particle has a random position (schedule) and a small random
velocity. Evaluate the makespan of each particle and record both its
pBest (personal best position) and the gBest (global best position
among all particles).
2. Velocity Update: For each task assignment in each particle, update
velocity using:
vᵢⱼ(t+1) = w vᵢⱼ(t) + c₁r₁(pBestᵢⱼ − xᵢⱼ(t)) + c₂r₂(gBestⱼ − xᵢⱼ(t))
where:
vᵢⱼ – velocity of particle i for task j
xᵢⱼ – current position (VM number assigned to task j)
w – inertia weight controlling exploration vs. exploitation
c₁, c₂ – acceleration constants for cognitive and social learning
r₁, r₂ – random numbers uniformly distributed in [0, 1]
pBestᵢⱼ – best position of particle i (personal best)
gBestⱼ – best global position found by the swarm (global best)
 PSO Algorithm
3. Position Update: Update each task’s machine assignment:
xᵢⱼ(t⁺¹) = xᵢⱼ(t) + vᵢⱼ(t⁺¹)
In discrete scheduling, position values are rounded or thresholded to valid
VM indices (e.g., 1 or 2).
4. Evaluation: Compute the new makespan for each updated particle and
update pBest and gBest accordingly.
5. Termination: Repeat velocity and position updates until a stopping
condition is met (maximum iterations or convergence). The final gBest
represents the optimal or near-optimal task–machine mapping.
 PSO Example
● Problem setup (independent tasks for clarity)
● Three tasks (T₁, T₂, T₃) and two grid nodes (VM₁, VM₂).
● Aim: to assign each task to VM₁ or VM₂, so that the makespan is minimized.
● PSO Parameters: Swarm size: 4 particles, Inertia weight (w) = 0.5, Cognitive
coefficient (c1) = 1.5, Social coefficient (c2) = 1.5, Random numbers (r1, r2)
= 0.6 for all updates, Initial velocities = 0 (all particles start stationary)
● Discrete update rule: after computing the new position, round the result to the
nearest valid VM index (1 or 2)
● The Expected Completion Time (ECT) matrix is:

Virtual Machines Task 1 (T1) Task 2 (T2) Task 3 (T3)

VM1 140 ms 20 ms 60 ms

VM2 100 ms 100 ms 70 ms

 PSO Example:Step 1
Initialization(positions, makespans, fitness): Start with 4 diverse schedules.

Particle Position (T₁,T₂,T₃) → (VM) VM₁ load VM₂ load Makespan Fitness
(ms) (ms)

P₁ [1, 1, 2] (T₁→VM₁, 140+20= 70 160 0.00625

T₂→VM₁, T₃→VM₂) 160

P₂ [2, 1, 1] 20+60= 100 100 0.01000

80

P₃ [2, 2, 1] 60 100+100 200 0.00500

=200

P₄ [1, 2, 2] 140 100+70= 170 0.00588

170

pBest (personal best) initially = current position for each particle

gBest (global best) initially = the best among all = P₂ = [2,1,1] (makespan 100)
 PSO Example:Step 2

Velocity & position update (Iteration 1)

For Particle 1 ([1, 1, 2] (T₁→VM₁, T₂→VM₁ )T₃→VM₂)

Task (x) (pBest-x) (gBest-x) (v') (x' = x + v') Rounded

T₁ 1 0 +1 (0.9) (1.9) 2

T₂ 1 0 0 (0) (1.0) 1

T₃ 2 0 −1 (-0.9) (1.1) 1

pBest (personal best) initially = current position for each particle

gBest (global best) initially = the best among all = P₂ = [2,1,1] (makespan 100)
 PSO Example:Step 2

Velocity & position update (Iteration 1)

For Particle 1 ([1, 1, 2] (T₁→VM₁, T₂→VM₁ )T₃→VM₂)

Task (x) (pBest-x) (gBest-x) (v') (x' = x + v') Rounded

T₁ 1 0 +1 (0.9) (1.9) 2

T₂ 1 0 0 (0) (1.0) 1

T₃ 2 0 −1 (-0.9) (1.1) 1

Apply the same logic quickly to the rest

P₂: already equals gBest → deltas 0 → stays [2,1,1]
P₃: [2,2,1] → T₂→1 → [2,1,1]
P₄: [1,2,2] → T₁→2, T₂→1, T₃→1 → [2,1,1]
 PSO Example:Step 3 & 4
Evaluate new positions (Iteration 1 results)
Particle New VM₁ load (ms) VM₂ load (ms) Makespan Fitness
Position

P₁ [2, 1, 1] 20+60=80 100 100 0.01000

P₂ [2, 1, 1] 20+60=80 100 100 0.01000

P₃ [2, 1, 1] 20+60=80 100 100 0.01000

P₄ [2, 1, 1] 20+60=80 100 100 0.01000

Observations: Update pBest for each (all improved or stayed

best), gBest remains [2,1,1]. The swarm has converged in 1
iteration.
 PSO Example:Step 3 & 4
Evaluate new positions (Iteration 1 results)
Particle New VM₁ load (ms) VM₂ load (ms) Makespan Fitness
Position

P₁ [2, 1, 1] 20+60=80 100 100 0.01000

P₂ [2, 1, 1] 20+60=80 100 100 0.01000

P₃ [2, 1, 1] 20+60=80 100 100 0.01000

P₄ [2, 1, 1] 20+60=80 100 100 0.01000

Observations: Final result (same optimum as GA)

VM₁ does the two short tasks (20 + 60 = 80 ms), while VM₂ handles the longer task
(100 ms), so both machines finish at ~100 ms → balanced and minimal.
 Real-time Grid computing Model
● Previous examples show how GA and PSO optimize
schedules mathematically, using a simplified grid
computing model.
● In real-time grid computing, the same algorithms are used,
but the fitness calculation also includes data transfer times,
task dependencies, and machine heterogeneity.
● The principle remains the same, only the evaluation model
becomes more realistic.
● Think of it, how to implement???
● Hint: Fitness = 1 / (α * makespan + β * transfer_time)

*****