Parallel and Distributed

Computing

Module - II
 Parallel Algorithm and Design
• A parallel algorithm divides a problem into multiple independent or semi-independent subproblems,
which can be executed simultaneously on different processors.

Goal:
✔ Reduce execution time
✔ Improve speedup and efficiency
✔ Utilize available hardware resources effectively

• Parallel algorithm design focuses on developing algorithms that can efficiently utilize multiple
processors to solve a problem faster than a sequential approach.

• Before designing a parallel algorithm, it is important to understand the basic concepts, issues, and
requirements involved in parallel computation.
 Parallel Algorithm and Design
Need for Parallel Algorithm Design

Parallel algorithm design is required because:

o Single-processor performance improvements have reached limits
o Modern systems are multi-core and multiprocessor
o Large-scale problems require faster computation
o Applications demand scalability and high throughput
 Preliminaries
Following are the terminologies used in Parallel Computing:

Task:
o A task is the smallest unit of computation that can be executed independently in a parallel
program.

Task Dependency Graph (TDG):

o A TDG is a directed acyclic graph that represents tasks as nodes and dependencies between tasks
as edges.

Critical Path:
o The critical path is the longest sequence of dependent tasks in a task dependency graph.

Critical Path Length:

o Critical path length is the total execution time of tasks along the critical path and represents the
minimum possible parallel execution time.
 Preliminaries
Concurrency:
o Concurrency is the ability of a system to have multiple tasks in progress at the same time.

Maximum Degree of Concurrency:

o The maximum degree of concurrency is the largest number of tasks that can be executed
simultaneously at any point in time.

Average Degree of Concurrency:

o The average degree of concurrency is the average number of tasks executing concurrently over
the entire execution period.
 Design Techniques
Decomposition:
• Decomposition is the process of dividing a computational problem into smaller tasks that can be
executed in parallel.

Granularity:
• Granularity refers to the amount of computation performed by a task relative to the
communication and synchronization overhead.

Fine-Grained Decomposition:
• Fine-grained decomposition divides a problem into very small tasks, resulting in high
communication and synchronization overhead.

Coarse-Grained Decomposition:
• Coarse-grained decomposition divides a problem into larger tasks, reducing communication
overhead and improving performance.
Preliminaries
 Task
o Tasks are the building blocks of parallel algorithms.

o A task is the smallest unit of computation in a parallel program that can be executed independently on a processor
or core.

o Each task performs a specific part of the overall computation and may run concurrently with other tasks.

Parallelism is achieved by:

o Dividing a problem into tasks
o Executing multiple tasks simultaneously on different processors

The number, size, and organization of tasks directly affect:

o Performance
o Speedup
o Efficiency
o Scalability
 Task
Type of Tasks

1. Independent Tasks

o Do not depend on results of other tasks

o Can execute fully in parallel

o Example: Processing different files independently

2. Dependent Tasks

o Require input from other tasks

o Must follow a specific execution order

o Example: Task B starts only after Task A finishes
 Task
Task Dependencies

o Task dependencies determine execution order and are represented using a Task Dependency Graph (TDG).

Types of dependencies:

o Data dependency – task needs data from another task

o Control dependency – execution depends on program flow

o Dependencies limit the amount of achievable parallelism.

Task Granularity

o Granularity refers to the size of a task:

o Fine-grained tasks → small computation, high overhead

o Coarse-grained tasks → large computation, low overhead

o Choosing proper task size is crucial for performance.
 Task
Task Creation

o Tasks can be created:

o Statically (at compile time)

o Dynamically (at runtime)

o Dynamic task creation improves flexibility but increases overhead.

Task Scheduling

o Task scheduling decides:

o Which processor executes which task
o When a task starts execution

o Scheduling can be:

o Static
o Dynamic

o Efficient scheduling improves load balancing and reduces idle time.

 Task
Task Communication and Synchronization

o Tasks may need to exchange data (communication)

o Tasks may need coordination (synchronization)

o Mechanisms include:
o Shared variables
o Message passing
o Barriers, locks, and semaphores
 Task Dependency Graph (TDG)
o A Task Dependency Graph (TDG) is a directed acyclic graph (DAG) that shows how tasks depend on
one another in a parallel program.
o Nodes represent tasks
o Directed edges represent dependencies
o If there is an edge A → B, task B cannot start until task A finishes

TDG helps identify:

o Which tasks can run in parallel
o Which tasks must run sequentially

o The task corresponding to a node can be executed when all tasks connected to this node by incoming
edges have completed.
 Task Dependency Graph (TDG)
Task Dependency Graph for "Finding minimum element
among 23,12,9,30,37,27,8,17"

Leaf nodes perform independent tasks like:

• min(23,12), min(9,30), min(37,27), min(8,17)
• These tasks can execute in parallel

• Intermediate nodes combine results from

lower-level tasks:
• min(12,9), min(27,8)

• The root node computes the final result:

• min(9,8) → 8

• Arrows indicate task dependencies

• The longest path from leaf to root is the critical
path
 Critical Path
o The critical path is the longest sequence of dependent tasks in a task dependency graph (TDG).

o Tasks on the critical path must be executed sequentially and cannot be parallelized.

Key Idea

o Even if many processors are available, tasks on the critical path limit the minimum execution time.

o The critical path determines the lower bound on parallel execution time.

A lower bound is the minimum possible time or minimum number of operations required to solve a
problem, regardless of how powerful the system is.

Even if you have:

o Unlimited processors
o No communication overhead
 Critical Path Length
o The critical path length is the total execution time of all tasks along the critical path in a task
dependency graph (TDG).

o It represents the minimum possible execution time of a parallel program, even when an unlimited
number of processors are available.

Key Idea

o Tasks on the critical path must execute sequentially.

o No parallelism is possible along this path.

o Hence, critical path length sets a lower bound on execution time.

Critical Path and Length
 Concurrency
o Concurrency refers to the ability of a system to have multiple tasks in progress during the same time
period.

o It does not necessarily mean that tasks execute at the exact same instant, but that their execution
overlaps in time.

o In parallel computing, concurrency is achieved by dividing a program into multiple tasks or subtasks
that can make progress independently and, when sufficient hardware resources are available, execute
simultaneously on multiple processing units such as CPU cores or GPUs.

o Concurrency improves resource utilization and forms the basis for achieving parallelism, which can
lead to better performance and higher efficiency.
 Maximum Degree of Concurrency
o The maximum degree of concurrency is the largest number of tasks that can be executed
simultaneously at any point in time in a parallel program, considering task dependencies.

o It represents the upper limit of parallelism available in an algorithm.

Key Idea

o Determined from the Task Dependency Graph (TDG)

o Depends on how many tasks are independent at a given time

o Limits the maximum possible speedup, regardless of processor count

 Maximum Degree of Concurrency
Level 1 (Leaf Level)

Tasks:
o min(23,12)
o min(9,30)
o min(37,27)
o min(8,17)

o These 4 tasks are independent and can execute at the same time.

o Maximum Degree of Concurrency = 4

Level 2

Tasks:
o min(12,9) o In most cases, the maximum degree of concurrency is less than the total
o min(27,8)
Concurrency = 2 number of tasks due to dependencies among the tasks.
Level 3 o In general, for task dependency graphs that are trees, the maximum degree
Task: of concurrency is always equal to the number of leaves in the tree.
o min(9,8)

Concurrency = 1
 Average Degree of Concurrency
•
 Average Degree of Concurrency
•
Design Techniques
 Decomposition
o Decomposition is the process of dividing a computational problem into smaller tasks so that these
tasks can be executed concurrently on multiple processors.

o It is the first and most important step in designing a parallel algorithm.

Types

o Recursive Decomposition

o Data Decomposition

o Exploratory Decomposition

o Speculative Decomposition
 Recursive Decomposition
o Recursive decomposition is a general-purpose parallel decomposition technique used to divide a
computational problem into smaller subproblems recursively.

o It is based on the divide-and-conquer principle, where a problem is first divided into independent
subproblems, which are then solved concurrently and finally combined to produce the final result.

Ideology
o Follows the divide-and-conquer approach
o Parallelism increases as recursion unfolds

Example
o Parallel Merge Sort
o Parallel Quick Sort
Recursive Decomposition
 Data Decomposition
o Data decomposition is a parallel decomposition technique in which the input data set is divided into
smaller partitions, and the same operation is performed on each partition simultaneously by different
processors.

o It is also known as data parallelism.

Key Idea

o Divide data, not functionality

o Each processor executes identical code

o Processors work on different portions of data

 Data Decomposition
•

Processor Data Assigned Operation

P1 A[0–1], B[0–1] C[0–1] = A + B

P2 A[2–3], B[2–3] C[2–3] = A + B

P3 A[4–5], B[4–5] C[4–5] = A + B

P4 A[6–7], B[6–7] C[6–7] = A + B

 Data Decomposition
Matrix A: Matrix B: Matrix C:
A1 A2 B1 B2 C1 C2
A3 A3 B3 B4 C3 C4

So, by data decomposition following tasks will be generated to get the product of A and B, and
storing the new matrix in C.

Task 1: C1= A1*B1

Task 2: C2= A2*B3
Task 3: C3= A3*B2
Task 4: C4= A4*B4
Now, these tasks will be assigned to four processors.
 Exploratory Decomposition
o Exploratory decomposition is a parallel decomposition technique used when the structure, size, or
amount of work is not known in advance.

o Tasks are created dynamically at runtime as the computation explores a problem space.

Key Idea

o Parallelism is discovered during execution

o Tasks generate new tasks while running

Where It Is Used
o Suitable for irregular and unpredictable problems
o Graph traversal (BFS, DFS)
o Tree search
o Game tree exploration
o Web crawling
o AI search problems
Exploratory Decomposition
Simple Example: Graph Traversal

o Consider searching for a target node in a graph:

o Start from a source node

o Each visited node may reveal new neighboring nodes

o Each neighbor becomes a new task

o Multiple branches are explored in parallel

Exploratory Decomposition
 Speculative Decomposition
o Speculative decomposition is a parallel decomposition technique in which tasks are executed in
advance based on predicted or assumed execution paths, even before it is certain that their results will
be needed.

o Some of the speculative tasks may turn out to be unnecessary, but the goal is to reduce waiting time
and improve performance.

Key Idea Why Speculative Decomposition Is Used

• When execution depends on conditions or branches
o Predict future computation
• When waiting for a decision would cause processors to be idle
o Execute multiple possible paths in parallel • To keep processors busy and improve throughput

o Discard results of incorrect or unused paths

o Trade extra computation for reduced latency

 Speculative Decomposition
o Example

Speculative Execution
if (condition) Execute Task A and Task B simultaneously
Task A
Once the condition is resolved:
else
o Keep the correct result
Task B
o Discard the other result

● As soon as the condition has been evaluated, only the results of one task are used, all others are thrown
away.
● This decomposition technique is quite wasteful on resources and seldom used.
 Speculative Decomposition
Disadvantages
Characteristics of Speculative Decomposition

o Tasks are created before certainty • Extra computation overhead

o Some computation may be wasted • Increased power consumption

o Requires mechanisms to discard incorrect results • Incorrect speculation wastes resources

o Best suited for systems with idle processing power
When to Use (Exam Tip)
Advantages
• Conditional branches
o Reduces idle time
• Decision-heavy algorithms
o Improves responsiveness
• Processor pipelines
o Exploits hidden parallelism

o Effective in control-flow-heavy applications • AI search and prediction-based systems

 Speculative Decomposition
Work Known in
Technique Basis Typical Use
Advance

Sorting,
Recursive Problem structure Yes
divide-and-conquer

Numerical & scientific

Data Input data Yes
computing

Exploratory Search space No Graphs, AI search

Control-flow-heavy
Speculative Prediction Partially
programs
Mapping Techniques for Load balancing
 Mapping Techniques for Load balancing
Mapping

o Mapping is the process of assigning tasks to processors in a parallel system.

o The main goal of mapping is load balancing—ensuring that all processors get roughly equal work so that no
processor is idle while others are overloaded.

Load Balancing
Objectives of Mapping Techniques
Load balancing ensures that:
A good mapping technique aims to:
o All processors are equally utilized o Balance workload evenly
o Execution time is minimized o Minimize communication cost

o Idle time and waiting are reduced o Reduce synchronization delays

o Improve speedup and efficiency

* Poor load balancing leads to low efficiency and poor speedup.

Mapping Techniques for Load balancing
Types

o Static Mapping

Tasks are assigned to processors before execution begins.

o Dynamic Mapping

Tasks are assigned to processors during execution, based on availability.

o Guided (Adaptive) Mapping

A hybrid approach between static and dynamic mapping.

 Static Mapping
Static mapping is a mapping technique in which tasks are assigned to processors before program execution begins.
Once assigned, tasks do not move between processors during execution.
Key Characteristics
o Task–processor assignment decided at compile time
o No runtime reassignment or migration
o Best when task sizes and execution times are known and uniform
o Low overhead (no dynamic scheduling)
Why Use Static Mapping?
o Predictable workload
o Minimal scheduling cost
o Simple implementation
o Good for regular, data-parallel problems
 Common Static Mapping Techniques
1) Block Distribution

o Tasks are divided into contiguous blocks, each assigned to a processor.

2) Cyclic Distribution

o Tasks are assigned in a round-robin fashion.

3) Block–Cyclic Distribution

o Combines block and cyclic: small blocks assigned cyclically.

 Block Distribution
o Block distribution is a static mapping technique in which tasks or data elements are divided into contiguous
blocks, and each block is assigned to a processor.

o Each processor gets one continuous chunk of work.

 Block Distribution
Why Block Distribution is Good
✔ Simple to implement
✔ Low scheduling overhead
✔ Good cache locality (contiguous memory access)
✔ Works well when task sizes are equal

When It Fails
o If tasks take unequal time
o If workload is irregular
o If some blocks contain heavier computations

Then some processors may finish early → causing load imbalance.

 Cyclic Distribution
o Cyclic distribution is a static mapping technique where tasks or data elements are assigned to processors in a
round-robin (circular) manner.

o Instead of giving each processor one big block, tasks are distributed one-by-one in a cyclic order.
 Block Cyclic Distribution
o Block–Cyclic distribution is a static mapping technique that combines both:
o Block distribution (contiguous chunks)
o Cyclic distribution (round-robin assignment)

o Instead of assigning one large block, we assign small blocks cyclically to processors.

Why Do We Need It?

o Block distribution → good locality but poor load balance

o Cyclic distribution → good load balance but poor locality

o Block–cyclic balances both.

 Block Cyclic Distribution
o Total elements = 16

o Number of processors = 4

o Block size = 2

o Now we divide data into blocks of size 2:

[0 1] [2 3] [4 5] [6 7] [8 9] [10 11] [12 13] [14 15]

Block Assigned Processor

[0 1] P1
[2 3] P2
[4 5] P3
[6 7] P4
[8 9] P1
[10 11] P2
[12 13] P3
[14 15] P4
 Block Cyclic Distribution
Why This Is Better
o Better load balancing than pure block
o Better locality than pure cyclic
o Works well for matrix and scientific applications
o Reduces communication imbalance

Advantages
✔ Good balance between locality and load balancing
✔ Suitable for large-scale HPC systems
✔ Handles moderate irregularity well

Disadvantages
o Slightly more complex
o Requires choosing optimal block size
 Block Cyclic Distribution
Feature Block Distribution Cyclic Distribution Block–Cyclic Distribution

Round-robin (one element at a

Assignment Method Contiguous large blocks Small blocks assigned cyclically
time)

Load Balancing Poor if workload uneven Better than block Very good

Memory Locality Excellent Poor Good

Communication Overhead Low Higher Moderate

Implementation Complexity Simple Simple Slightly complex

Large scientific/matrix
Best For Uniform workloads Slightly irregular workloads
computations
 Dynamic Mapping
• Dynamic mapping is a mapping technique where tasks are assigned to processors during runtime, rather than
before execution begins.

• Tasks are allocated based on processor availability, allowing better load balancing.

Why Dynamic Mapping is Needed

o Task execution time varies
o Problem structure is irregular
o Workload is unpredictable

Static mapping causes load imbalance.

Dynamic mapping solves this.

 Dynamic Mapping
How Dynamic Mapping Works

• Tasks are stored in a task pool (queue).

• When a processor becomes idle:

• It takes the next available task from the queue.

• This continues until all tasks are completed.

Example

10 tasks
3 processors
Tasks take different execution times

Static Mapping Problem:

One processor might get heavy tasks → finishes late.

Dynamic Mapping Solution:

Processors keep picking new tasks after finishing their current one.
 Dynamic Mapping
Task Pool: T1 T2 T3 T4 T5 T6 T7 T8 T9 T10

Processors:

• P1 → picks T1 → finishes → picks T4 → picks T7

• P2 → picks T2 → finishes → picks T5 → picks T8

• P3 → picks T3 → finishes → picks T6 → picks T9 → picks T10

 Types of Dynamic Mapping
• Work Sharing

Idle processors request tasks from a global queue.

• Work Stealing
• Idle processors steal tasks from busy processors.

• Work stealing is very common in:

• Recursive parallel algorithms
• Fork-Join frameworks
 Work Sharing Mapping
• Work Sharing is a dynamic mapping technique in which tasks are stored in a central task queue (task pool), and
processors request tasks when they become idle.

• It is called work sharing because tasks are shared among processors from a common pool.

Basic Working Principle

• All tasks are placed in a global task queue.

• Processors execute assigned tasks.

• When a processor finishes:

• It requests the next available task from the queue.

• This continues until the queue becomes empty.

 Work Sharing Mapping
Example

• 8 tasks (T1–T8)

• 3 processors

• Tasks have different execution times

Time P1 P2 P3

t1 T1 T2 T3

t2 T4 T5 T6

t3 T7 T8 Idle

• Processors keep taking tasks from the pool until empty. This prevents one processor from getting stuck with heavy tasks.
 Work Sharing Mapping
Where Work Sharing is Used

• Parallel loops

• Task-based parallel programming (OpenMP dynamic schedule)

• Web servers

• Parallel recursive algorithms

Advantages
Disadvantages
• Good load balancing
o Central task queue may become bottleneck
• Keeps processors busy
o Requires synchronization (mutex/locks)
• Simple dynamic scheduling o Communication overhead

• Works well for irregular tasks

 Work Stealing Mapping
• Work Stealing is an advanced dynamic load balancing technique used in parallel computing where each processor maintains
its own local task queue, and idle processors steal tasks from other busy processors.

• Unlike work sharing (which uses a global queue), work stealing is decentralized, making it more scalable.

• Work stealing is a dynamic mapping technique in which each processor maintains a local task queue, and when a processor
becomes idle, it steals tasks from the queue of another busy processor.

Why Work Stealing is Needed

• In dynamic and irregular problems:

• Some processors finish early

• Others still have many tasks

• Load imbalance occurs

• Instead of using a global queue (which may become a bottleneck), work stealing distributes queues locally and balances
workload efficiently.
 Work Stealing Mapping
Working Mechanism

• Each processor has its own local task queue.

• A processor executes tasks from its local queue.

• If its queue becomes empty:

• It randomly selects another processor.

• It steals a task from that processor’s queue.

• Execution continues until all tasks are completed.

P1 Queue: T1 T2 T3
P2 Queue: T4 T5
P3 Queue: T6 T7 T8 T9

If P2 becomes idle →
P2 steals a task from P3
 Work Stealing Mapping
Where Work Stealing is Used Why Work Stealing is Efficient

• Parallel quicksort o Tasks are mostly executed locally.

• Fork–Join frameworks o Stealing happens only when necessary.

• Multithreaded runtime systems o Reduces synchronization contention.

• OpenMP task scheduling o Balances irregular workloads effectively.

Advantages Disadvantages

• Better scalability than work sharing • Stealing overhead

• No central bottleneck • Communication cost during stealing

• Excellent load balancing • Random stealing may not always be optimal

• Efficient for recursive and irregular algorithms

• Reduced contention
 Work Sharing Vs Stealing
Feature Work Sharing Work Stealing

Idle processors obtain tasks from a shared global task Idle processors steal tasks from the local queue
Definition
queue. of another busy processor.

Each processor maintains its own local task

Task Storage Single global task pool
queue

Queue Structure Centralized Decentralized

Tasks are redistributed by stealing from busy

Load Balancing Approach Tasks are shared among processors from a central queue
processors

Idle processor steals task from another

Who Initiates Action? Idle processor requests task from global queue
processor

Scalability Moderate scalability High scalability

Synchronization Overhead High (due to shared queue locking) Lower (local queues reduce contention)

Bottleneck Possibility Yes – global queue may become bottleneck No central bottleneck
 Work Sharing Vs Stealing
Feature Work Sharing Work Stealing

Communication Overhead Moderate (accessing global queue) Occurs only during stealing

Task Locality May be lower due to global sharing Better locality (tasks executed locally first)

Implementation Complexity Simpler More complex

Best Suited For Moderate number of processors Large-scale multicore systems

Efficiency in Irregular Workloads Good Very good

Example Systems OpenMP dynamic scheduling Cilk, Intel TBB, Java ForkJoinPool

Excessive stealing overhead if imbalance is

Failure Scenario Heavy contention on global queue
high
 Guided (Adaptive) Mapping
• Guided (Adaptive) Mapping is a hybrid dynamic load balancing technique that combines features of static and dynamic
mapping.

Instead of assigning:

• All tasks statically (like block distribution), or

• Assigning tasks one-by-one dynamically (like work sharing),

• Guided mapping assigns large chunks initially and then reduces chunk size gradually as execution progresses.

Guided mapping is a dynamic scheduling technique where:

• Tasks are assigned in large chunks initially

• Chunk size gradually decreases as execution progresses

• This helps reduce scheduling overhead while maintaining good load balancing

• It is a hybrid approach between static and dynamic mapping.

 Guided (Adaptive) Mapping
Why Do We Need Guided Mapping.?
Problem with Static Mapping
Task Size in Static & Dynamic
• Tasks assigned once Too Large:

• If workload is uneven → load imbalance • Less overhead

• But poor load balance
Problem with Pure Dynamic Mapping
Too Small:
• Tasks assigned one-by-one
• Good balance
• Good load balance
• But high scheduling overhead
• But high scheduling overhead

Solution: Guided Mapping

• Adaptive mapping balances both.
 Guided (Adaptive) Mapping
•

Processor Iterations

P1 1–25

P2 26–50

P3 51–75

P4 76–100
 Guided (Adaptive) Mapping
• Total Work: 100 Iterations

Stage 1 (Large
Chunks)--------------------------------------------P1:
[=========================]
P2: [=========================]
P3: [=========================]
P4: [=========================]

Stage 2 (Medium Chunks)----------------------------

P1: [==========]
P2: [==========]
P3: [==========]
P4: [==========]

Stage 3 (Small Chunks)-------------------

P1: [==]
P2: [==]
P3: [==]
P4: [==]
 Guided (Adaptive) Mapping
Advantages

✔ Lower overhead than dynamic mapping

✔ Better load balance than static mapping

✔ Prevents end-of-execution idle time

✔ Scalable for moderate workloads

Disadvantages

o Not ideal for extremely irregular tasks

o Slight runtime computation for chunk size

o Implementation more complex than static mapping

 Static vs Dynamic Vs Guided
Feature Static Mapping Dynamic Mapping Adaptive (Guided) Mapping

Task Assignment Time Before execution During execution During execution

Chunk Size Fixed Usually small or single task Decreasing size (large → small)

Load Balancing Poor for irregular tasks Very good Good

Scheduling Overhead Low High Moderate

Flexibility Low High Moderate to High

Processor Utilization May cause idle time High utilization High utilization

Scalability Limited Good Good

Suitable Workload Type Regular & predictable Irregular & unpredictable Moderately irregular

Communication/Synchronization Minimal Frequent queue access Moderate

Implementation Complexity Simple Moderate Slightly complex

Example Strategy Block distribution Work sharing / Work stealing OpenMP schedule(guided)

End-of-Execution Behavior Idle processors possible Balanced Balanced

 Synchronous parallel processing
o Synchronous Parallel Processing is a parallel computation model in which multiple processing elements
execute tasks simultaneously under a coordinated control mechanism, with synchronization barriers ensuring
that all processors complete each computational phase before proceeding to the next.

o Synchronous parallel processing is a parallel execution model in which multiple processors perform operations
simultaneously and synchronize at predefined points before continuing.

Synchronous Parallel Processing is a parallel computing model where:

o Multiple processors execute tasks simultaneously

o They proceed in lock-step fashion

o All processors must reach a synchronization point (barrier) before moving to the next step

o All processors work together and wait for each other at specific points.
 Synchronous parallel processing
Types

(A) Global Clock Based System

o All processors operate under same clock cycle

o Instruction issued simultaneously

o Used in SIMD machines

(B) Barrier-Based System

o Processors execute independently within a phase

o Explicit synchronization barrier used between phases

 Global Clock Based System
A Global Clock Based System is a synchronous parallel processing model in which all processors
operate under a single shared clock signal, executing instructions simultaneously in coordinated clock
cycles.

Basic Idea
Components:
o There is a central clock
oGlobal Clock Generator
o All processing elements (PEs) receive the same clock pulse oControl Unit
oMultiple Processing Elements
o Each clock tick triggers one computation step
oShared or Distributed Memory
o No processor can move ahead independently
Clock pulses coordinate execution.
 Global Clock Based System
How It Works

Clock Cycle 1:

All processors fetch instruction.

Clock Cycle 2:

All processors execute instruction.

Clock Cycle 3:

All processors access memory.

o Each step happens simultaneously.

o This is called lock-step execution.

 Barrier-Based System
How It Works
• Divide problem into parallel tasks.
• All processors execute their assigned
tasks.
• At certain stages, processors
synchronize.
• No processor moves forward until all
reach the synchronization barrier.
 Barrier-Based System
Example

4 processors are multiplying rows of a matrix.

Phase 1:
Time →------------------------------------------------
Each processor computes partial multiplication. P1: Compute | Wait | Compute | Wait
Barrier: P2: Compute | Wait | Compute | Wait
P3: Compute | Wait | Compute | Wait
All processors must finish before combining results.
P4: Compute | Wait | Compute | Wait
Phase 2:
↑ Synchronization Barrier
Processors combine computed values.

If P3 is slow → P1, P2, P4 must wait.

 Synchronous parallel processing
Where It Is Used Example in Real Systems
o SIMD architectures
o GPUs follow synchronous execution in many kernels
o Scientific simulations o SIMD processors operate synchronously
o Iterative algorithms (e.g., Jacobi method) o OpenMP barrier synchronization
o GPU programming

o Parallel loops with barriers

Disadvantages
Advantages
o Slow processors delay fast ones
o Simple control flow
o Idle time at synchronization points
o Easier to implement
o Poor performance for irregular workloads
o Deterministic results

o Suitable for regular problems

SIMD Architecture and Programming Principles
What is SIMD?

Single Instruction Multiple Data

It is a parallel architecture where:

o One instruction stream

o One control unit

o Multiple processing elements (PEs)

o Each PE executes the same instruction

But on different data

This classification comes from Flynn’s taxonomy proposed by Michael J. Flynn.

SIMD Architecture and Programming Principles
Core Idea of SIMD

Instead of doing:

A[0] + B[0]

A[1] + B[1]

A[2] + B[2]

A[3] + B[3]

SIMD does:

ADD (A[0..3], B[0..3])

SIMD Architecture and Programming Principles
Architecture
SIMD Architecture and Programming Principles
Components

1. Control Unit (CU) 3. Interconnection Network

o Fetches instruction o Connects PEs
o Allows data communication
o Decodes instruction

o Broadcasts instruction to all PEs

4. Memory
o Shared or distributed

2. Processing Elements (PEs)

o Execute same instruction simultaneously

o Each has its own local register or memory

SIMD Architecture and Programming Principles
Example One instruction
Multiple data
Perform the Matrix Addition
Parallel execution
A = [2, 4, 6, 8] This is called data parallelism.

B = [1, 3, 5, 7]

In SIMD:
Key Characteristics of SIMD
All processors execute: ADD A[i], B[i] o Synchronous execution
o Centralized control unit
Processor Operation Result
o Lock-step execution
PE1 2+1 3
o Efficient for vector operations
PE2 4+3 7
o Best for matrix, graphics, scientific computations
PE3 6+5 11

PE4 8+7 15
 Programming Principles OF SIMD
1. Data Parallelism 3. Memory Alignment

o Divide dataset into equal chunks. SIMD works best when:

o Data is contiguous
o Instead of dividing instructions,
o Properly aligned (16/32/64 bytes)
Misaligned data → performance loss
for i = 0 to n-1
C[i] = A[i] + B[i]
4. Masking (Conditional Execution)
2. Vectorization Suppose:

Scalar - C[i] = A[i] + B[i] if (A[i] > 0)

B[i] = A[i]
Convert this into Vector
Not all PEs should execute.
SIMD uses mask registers:
C[0..3] = A[0..3] + B[0..3]
o Active PEs execute
o Inactive PEs remain idle
SIMD and synchronous parallel processing
Why SIMD Is Synchronous Clock Cycle View:

SIMD uses:

o Single control unit Clock Cycle Action

o Global instruction broadcast Cycle 1 Fetch instruction

o Lock-step execution Cycle 2 Decode

This means: Cycle 3 Execute on all PEs

All PEs execute instruction in same clock cycle. Cycle 4 Store result

That is exactly Synchronous Parallel Processing

SIMD and synchronous parallel processing
•

Example for SIMD

Modern CPUs:
o Intel AVX
o ARM NEON

GPUs:
Thousands of cores executing same shader
instruction.