qwertyuiopasdfghjklzxcvbnmqwe

rtyuiopasdfghjklzxcvbnmqwertyu
iopasdfghjklzxcvbnmqwertyuiopa
sdfghjklzxcvbnmqwertyuiopasdfg
hjklzxcvbnmqwertyuiopasdfghjkl
PARALLEL AND DISTRIBUTED COMPUTING

Comprehensive Notes With detailed Explanation

zxcvbnmqwertyuiopasdfghjklzxcv
10/9/2025

Laiba Arshad

bnmqwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnmqwe
rtyuiopasdfghjklzxcvbnmqwertyu
iopasdfghjklzxcvbnmqwertyuiopa
sdfghjklzxcvbnmqwertyuiopasdfg
hjklzxcvbnmqwertyuiopasdfghjkl
zxcvbnmqwertyuiopasdfghjklzxcv
bnmqwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnmqwe
rtyuiopasdfghjklzxcvbnmrtyuiopa
Contents
Parallel and Distributed Computing....................................................................................................1
🔹 Introduction...................................................................................................................................1
⚙️1. Parallel Computing...................................................................................................................1
🌐 2. Distributed Computing.............................................................................................................2
🔸 Parallel vs Distributed Computing (Comparison)......................................................................2
🧾 Conclusion......................................................................................................................................3
⚙️Speedup and Amdahl’s Law.............................................................................................................3
🧠 What is Speedup?..........................................................................................................................3
🧩 Why Speedup is Important:..........................................................................................................4
📊 Types of Speedup:..........................................................................................................................4
⚡ Amdahl’s Law....................................................................................................................................4
🧮 Formula:.........................................................................................................................................5
💡 Example:........................................................................................................................................5
🚫 Amdahl’s Law Tells Us:................................................................................................................5
💻 Hardware Architectures in Parallel and Distributed Computing....................................................6
🧩 1. Multiprocessors (Shared Memory Architecture)........................................................................6
🔹 Definition:......................................................................................................................................6
💡 Simple Example:............................................................................................................................6
⚙️How It Works:...............................................................................................................................6
⚡ Advantages:....................................................................................................................................7
⚠️Disadvantages:...............................................................................................................................7
🧠 Example:........................................................................................................................................7
🌐 2. Networks of Workstations (Distributed Memory Architecture)................................................7
🔹 Definition:......................................................................................................................................7
💡 Simple Example:............................................................................................................................7
⚙️How It Works:...............................................................................................................................8
⚡ Advantages:....................................................................................................................................8
⚠️Disadvantages:...............................................................................................................................8
 🧠 Example:........................................................................................................................................8
3. Clusters (Latest Hybrid Variation).................................................................................................8
🔹 Definition:......................................................................................................................................8
💡 Simple Example:............................................................................................................................9
⚙️How It Works:...............................................................................................................................9
⚡ Advantages:....................................................................................................................................9
⚠️Disadvantages:...............................................................................................................................9
🧠 Example:........................................................................................................................................9
🔍 Comparison Table...........................................................................................................................10
🏁 Conclusion........................................................................................................................................10
🧠 Software Architectures in Parallel and Distributed Systems (Detailed Explanation)..................10
🧵 1. Threads and Shared Memory.................................................................................................11
🧮 2. Processes and Message Passing...............................................................................................12
🧠 3. Distributed Shared Memory (DSM).......................................................................................13
🌐 4. Distributed Shared Data (DSD)..............................................................................................14
📊 Comparison Table...........................................................................................................................15
🧭 Relation to Hardware Architectures..........................................................................................15
⚙️Real-Life Analogy.......................................................................................................................15
⚙️Parallel Algorithms (In Detail)...............................................................................................................16
🧠 1. Introduction....................................................................................................................................16
💡 Simple Definition............................................................................................................................16
🧩 2. Need for Parallel Algorithms...........................................................................................................16
✅ Advantages of Using Parallel Algorithms:.......................................................................................16
🔍 3. Comparison: Sequential vs Parallel Algorithm................................................................................16
⚙️4. Structure of a Parallel Algorithm...................................................................................................17
🔹 Step 1: Problem Decomposition.....................................................................................................17
🔹 Step 2: Task Assignment.................................................................................................................17
🔹 Step 3: Communication..................................................................................................................17
🔹 Step 4: Synchronization..................................................................................................................17
🔹 Step 5: Combination.......................................................................................................................18
⚡ 5. Key Concepts in Parallel Algorithms...............................................................................................18
 🧮 a) Speedup......................................................................................................................................18
🧩 b) Efficiency....................................................................................................................................18
⚖️c) Scalability..................................................................................................................................19
💬 d) Overhead....................................................................................................................................19
🧮 6. Types of Parallelism........................................................................................................................19
🧩 1. Data Parallelism..........................................................................................................................19
⚙️2. Task Parallelism.........................................................................................................................19
🔄 3. Pipeline Parallelism.....................................................................................................................20
💡 7. Examples of Parallel Algorithms......................................................................................................20
🧩 Example 1: Parallel Sum..................................................................................................................20
🧮 Example 2: Parallel Matrix Multiplication.......................................................................................21
🔄 Example 3: Parallel Merge Sort.......................................................................................................21
🔍 8. Performance Metrics......................................................................................................................21
🧠 9. Challenges in Designing Parallel Algorithms...................................................................................21
⚖️10. Relation to Amdahl’s Law............................................................................................................22
🔧 11. Relation to Hardware and Software Architectures.......................................................................22
🌍 12. Real-Life Applications....................................................................................................................22
🧾 13. Advantages and Disadvantages....................................................................................................23
✅ Advantages.....................................................................................................................................23
❌ Disadvantages.................................................................................................................................23
✨ 14. Conclusion....................................................................................................................................23
⚙️Concurrency and Synchronization (In Detail)........................................................................................23
🧠 1. Introduction....................................................................................................................................23
💡 2. What is Concurrency?.....................................................................................................................24
🔹 Simple Definition:...........................................................................................................................24
🧩 Example 1:......................................................................................................................................24
🧩 Example 2 (Programming Level):....................................................................................................24
⚙️3. Concurrency vs Parallelism............................................................................................................25
🧩 4. Benefits of Concurrency..................................................................................................................25
⚠️5. Problems in Concurrency..............................................................................................................25
💥 a) Race Condition............................................................................................................................25
 ⚰️b) Deadlock....................................................................................................................................26
🌀 c) Starvation....................................................................................................................................26
🧩 d) Inconsistency..............................................................................................................................26
🧭 6. What is Synchronization?...............................................................................................................26
🔹 Simple Definition:...........................................................................................................................26
🧩 Real-Life Example:..........................................................................................................................27
⚙️7. Types of Synchronization..............................................................................................................27
🧩 A. Process Synchronization.............................................................................................................27
🧩 B. Thread Synchronization..............................................................................................................27
🔧 8. Methods / Mechanisms of Synchronization...................................................................................28
🔹 1. Locks (Mutexes)..........................................................................................................................28
🔹 2. Semaphores................................................................................................................................28
🔹 3. Monitors.....................................................................................................................................28
🔹 4. Condition Variables.....................................................................................................................28
🔹 5. Message Passing.........................................................................................................................29
🧩 9. Critical Section Problem..................................................................................................................29
⚙️10. Synchronization in Parallel and Distributed Systems...................................................................29
🧮 11. Common Synchronization Problems and Solutions......................................................................30
💡 12. Example: Producer–Consumer Problem.......................................................................................30
⚙️Solution using Semaphores:..........................................................................................................30
🧠 13. Relation to Parallel Algorithms.....................................................................................................30
🧾 14. Advantages and Disadvantages....................................................................................................31
✅ Advantages.....................................................................................................................................31
❌ Disadvantages.................................................................................................................................31
✨ 15. Conclusion....................................................................................................................................31
⚙️Data and Work Partitioning...................................................................................................................31
🧠 1. Introduction....................................................................................................................................32
💡 Simple Definition:...........................................................................................................................32
🧩 Why Partitioning is Important........................................................................................................32
🔍 2. Two Main Types of Partitioning......................................................................................................32
🧩 3. Data Partitioning.............................................................................................................................32
 📘 Definition:.......................................................................................................................................32
🧠 Example 1:......................................................................................................................................33
🧠 Example 2:......................................................................................................................................33
🔹 Advantages of Data Partitioning.....................................................................................................33
🔸 Disadvantages.................................................................................................................................33
🧮 Types of Data Partitioning..............................................................................................................34
⚙️4. Work (Task) Partitioning................................................................................................................34
📘 Definition:.......................................................................................................................................34
🧠 Example 1:......................................................................................................................................34
🧠 Example 2:......................................................................................................................................34
🔹 Advantages of Work Partitioning....................................................................................................35
🔸 Disadvantages.................................................................................................................................35
🔄 5. Comparison: Data vs Work Partitioning..........................................................................................35
⚙️6. Steps Involved in Partitioning........................................................................................................35
🧮 7. Load Balancing................................................................................................................................36
💬 8. Partitioning in Parallel Algorithms..................................................................................................36
🧩 9. Partitioning in Distributed Systems.................................................................................................36
🧠 10. Challenges in Partitioning.............................................................................................................37
🧾 11. Granularity in Partitioning............................................................................................................37
💡 12. Real-Life Examples........................................................................................................................37
⚖️13. Relation to Concurrency and Synchronization............................................................................38
✨ 14. Conclusion....................................................................................................................................38
🧠 Common Parallelization Strategies..................................................................................................38
🟦 1. Task Parallelism (Functional Parallelism).............................................................................38
🟩 2. Data Parallelism.......................................................................................................................39
🟨 3. Pipeline Parallelism.................................................................................................................39
🟧 4. Hybrid Parallelism..................................................................................................................40
🟥 5. Speculative Parallelism...........................................................................................................40
🟦 6. Loop-Level Parallelism...........................................................................................................41
⚙️Summary Table...............................................................................................................................41
💡 Connection to Previous Topics...................................................................................................42
🧠 Granularity in Parallel Computing..................................................................................................42
📘 Definition:....................................................................................................................................42
⚙️Understanding the Concept........................................................................................................42
🟩 1. Fine-Grained Parallelism............................................................................................................42
🟦 2. Coarse-Grained Parallelism........................................................................................................43
🟨 3. Medium-Grained (Mixed) Parallelism.......................................................................................44
🧩 Comparison Table...........................................................................................................................44
🔁 Relation with Other Topics.............................................................................................................45
💡 Real-Life Example.......................................................................................................................45
⚙️Load Balancing in Parallel and Distributed Computing..............................................................45
📘 Definition:....................................................................................................................................45
💡 Why Load Balancing is Important.............................................................................................45
🟩 Types of Load Balancing.................................................................................................................46
🟦 1. Static Load Balancing..............................................................................................................46
🟩 2. Dynamic Load Balancing........................................................................................................47
🧩 Load Balancing Techniques............................................................................................................47
⚖️Goals of Load Balancing.................................................................................................................48
🧠 Real-Life Example...........................................................................................................................48
🔁 Relation with Other Topics.............................................................................................................48
✅ Summary:.....................................................................................................................................48
⚙️Examples of Parallel Algorithms...................................................................................................49
🟩 1. Parallel Search.........................................................................................................................49
🟦 2. Parallel Sorting........................................................................................................................49
🟨 3. Parallel Matrix Multiplication................................................................................................50
🟧 4. Parallel Prefix Sum (Scan)......................................................................................................51
🟥 5. Parallel Graph Algorithms.....................................................................................................51
🟫 6. Parallel Image Processing.......................................................................................................52
🧩 Comparison Table...........................................................................................................................52
🔁 Relation with Previous Topics........................................................................................................52
💡 Simple Real-Life Example...........................................................................................................53
⚙️Shared-Memory Programming......................................................................................................53
 📘 Definition:....................................................................................................................................53
💡 Key Idea:......................................................................................................................................53
🧩 Main Concepts in Shared-Memory Programming........................................................................53
🟩 1. Threads.....................................................................................................................................54
🟦 2. Pthreads (POSIX Threads).....................................................................................................54
🟨 3. Locks (Mutexes).......................................................................................................................55
🟥 4. Semaphores..............................................................................................................................55
🧠 Example: Using Shared Memory with Threads and Locks..........................................................56
🔁 Relationship with Other Topics......................................................................................................57
💡 Real-Life Example...........................................................................................................................57
✅ Summary..........................................................................................................................................57
🌐 Distributed-Memory Programming.........................................................................................................57
🧠 What is Distributed-Memory Programming?......................................................................................57
💡 Real-Life Example............................................................................................................................58
⚙️Key Features of Distributed-Memory Systems..................................................................................58
🔹 Message Passing.................................................................................................................................58
📘 Definition:.......................................................................................................................................58
🧩 Basic Operations in Message Passing..............................................................................................59
💻 Example (Concept):.........................................................................................................................59
🧩 MPI (Message Passing Interface)........................................................................................................59
📘 Definition:.......................................................................................................................................59
⚙️Main Features of MPI:...................................................................................................................59
💻 Basic MPI Functions........................................................................................................................59
💡 Simple Example (Conceptual).........................................................................................................60
🧠 Advantages of MPI..........................................................................................................................60
⚠️Disadvantages...............................................................................................................................60
🧩 PVM (Parallel Virtual Machine)...........................................................................................................60
📘 Definition:.......................................................................................................................................60
⚙️Main Features of PVM:..................................................................................................................61
💻 How PVM Works:............................................................................................................................61
🧠 Advantages of PVM........................................................................................................................61
 ⚠️Disadvantages...............................................................................................................................61
🔁 MPI vs. PVM Comparison....................................................................................................................61
✅ Summary.............................................................................................................................................62
💡 Real-World Examples......................................................................................................................62
💻 Other Parallel Programming Systems......................................................................................................62
🧠 1. Distributed Shared Memory (DSM)................................................................................................62
📘 Definition:.......................................................................................................................................62
💡 How It Works..................................................................................................................................63
⚙️Advantages....................................................................................................................................63
⚠️Disadvantages...............................................................................................................................63
🧠 Example:.........................................................................................................................................63
🌐 2. Aurora: Scoped Behavior and Abstract Data Types........................................................................63
📘 Definition:.......................................................................................................................................63
💡 Key Concepts:.................................................................................................................................64
⚙️Advantages of Aurora....................................................................................................................64
🧠 Example (Conceptual):....................................................................................................................64
🏢 3. Enterprise: Process Templates........................................................................................................64
📘 Definition:.......................................................................................................................................64
💡 Key Idea:.........................................................................................................................................65
⚙️How It Works:................................................................................................................................65
🧩 Advantages:....................................................................................................................................65
🧠 Example:.........................................................................................................................................65
🔬 4. Research Topics in Parallel and Distributed Systems......................................................................65
✅ Summary.............................................................................................................................................66
 Parallel and Distributed Computing

🔹 Introduction

In today’s world, computers need to process a huge amount of data and perform many tasks very
quickly. To achieve this, instead of depending on a single processor, we divide the work among
multiple processors or even multiple computers.
This idea is known as Parallel and Distributed Computing.

⚙️1. Parallel Computing

🟢 Definition:

Parallel computing means using multiple processors (or cores) inside a single computer to
perform many tasks at the same time.
Each processor works on a different part of a problem, and all processors work together to get
the final result faster.

🧩 Example:

Imagine you have to solve a 1000-piece puzzle.

Instead of one person doing it alone, you call 4 friends, and each person works on 250 pieces.
You’ll complete it much faster — that’s parallel computing!

💡 How it Works:

 A big task is divided into smaller parts.

 Each part is processed simultaneously by a different processor.
 The results are combined to get the final answer.

⚡ Advantages of Parallel Computing:

1. Speed: Tasks finish much faster.

 2. Efficiency: Makes full use of multiple CPU cores.
3. Solves Complex Problems: Useful for scientific and engineering calculations.
4. Better Performance: Improves system responsiveness.

⚠️Disadvantages of Parallel Computing:

1. Complex Programming: Writing parallel programs is difficult.

2. Synchronization Issues: All processors must work together properly.
3. Cost: Multi-core processors and systems are expensive.
4. Debugging Problems: Finding and fixing errors is harder.

🌐 2. Distributed Computing

🟢 Definition:

Distributed computing means using many computers (connected through a network) to work
together on a common task.
Each computer works on a part of the problem and shares results with others.

🧩 Example:

Think about Google or YouTube — they don’t rely on one computer.

Thousands of computers around the world process your search or video requests together.
That’s distributed computing!

💡 How it Works:

 A large task is divided into smaller sub-tasks.

 Each sub-task is sent to different computers over a network.
 All computers work independently and share results back to the main system.

⚡ Advantages of Distributed Computing:

1. Scalability: More computers can be added to handle more work.

2. Reliability: If one computer fails, others still continue working.
3. Cost-Effective: Uses normal computers connected together, not one powerful machine.
4. Resource Sharing: Different computers can share storage, data, and power.

⚠️Disadvantages of Distributed Computing:

1. Network Dependency: Depends heavily on a good internet connection.

2. Communication Delays: Data transfer between computers can be slow.
3. Security Issues: Data moves through networks, so it can be at risk.
4. Complex Management: Hard to manage and coordinate many computers.
🔸 Parallel vs Distributed Computing (Comparison)

Feature Parallel Computing Distributed Computing

System Type Uses multiple processors in one Uses multiple computers connected via a
computer network
Communicatio Processors share the same memory Computers communicate through
n network
Speed Very fast for tasks with heavy Good for tasks spread across locations
calculations
Failure Impact If one processor fails, system may If one computer fails, others still work
stop
Example Multi-core processor in your Google servers across the world
laptop

🧾 Conclusion

Both Parallel and Distributed Computing are used to make computers more powerful and
faster.

 Parallel computing increases speed within a single system.

 Distributed computing connects multiple systems to share work.

We use them when we need high performance, large data handling, or faster results, but we
must handle their complexity and costs carefully.

⚙️Speedup and Amdahl’s Law

🧠 What is Speedup?

🔹 Definition:

Speedup tells us how much faster a program runs when we use multiple processors compared
to just one processor.

It measures the performance improvement we get by using parallel computing.

🧮 Formula:

Speedup(S)=Execution Time on 1 processorExecution Time on N processorsSpeedup (S) = \

frac{Execution\ Time\ on\ 1\ processor}{Execution\ Time\ on\ N\
processors}Speedup(S)=Execution Time on N processorsExecution Time on 1 processor

💡 Simple Example:

Let’s say a task takes 10 minutes on a single processor.

If it takes 2 minutes when using 4 processors, then:

S=102=5S = \frac{10}{2} = 5S=210=5

So the speedup = 5×, meaning the parallel system is 5 times faster.

🧩 Why Speedup is Important:

 It helps us understand how efficiently multiple processors are being used.

 It tells us whether using more processors actually improves performance or not.
 If speedup increases linearly with processors, the system is working very efficiently.

📊 Types of Speedup:

1. Linear Speedup:
If doubling the processors halves the execution time.
Example: 1 processor → 10 min, 2 processors → 5 min.
👉 Perfect condition (rare in real life).
2. Sub-linear Speedup:
When adding more processors doesn’t fully double the speed.
Example: 1 processor → 10 min, 2 processors → 6 min.
👉 Common in real systems (because of communication and synchronization delays).
3. Super-linear Speedup:
Sometimes speedup is even better than expected (rare case).
Example: 1 processor → 10 min, 2 processors → 4 min.
👉 Happens due to better use of memory or caching.

⚡ Amdahl’s Law
🔹 Definition:
Amdahl’s Law tells us that no matter how many processors we use, the maximum speedup is
limited by the part of the program that cannot be parallelized.

In simple words:

Even if we use 100 processors, the part of the task that must be done sequentially (one after
another) will limit the overall speed.

🧮 Formula:

Speedup=1(1−P)+PNSpeedup = \frac{1}{(1 - P) + \frac{P}{N}}Speedup=(1−P)+NP1

Where:

 P = Fraction (percentage) of program that can be parallelized

 N = Number of processors
 (1 - P) = Fraction of program that must run sequentially

💡 Example:

Suppose:

 80% of a program can be parallelized (P = 0.8)

 20% must run sequentially (1 - P = 0.2)
 You have 4 processors (N = 4)

Speedup=1(0.2)+0.84=10.2+0.2=10.4=2.5Speedup = \frac{1}{(0.2) + \frac{0.8}{4}} = \frac{1}

{0.2 + 0.2} = \frac{1}{0.4} = 2.5Speedup=(0.2)+40.81=0.2+0.21=0.41=2.5

So even with 4 processors, the speedup is only 2.5× faster, not 4×.
That’s because the 20% sequential part limits the improvement.

🚫 Amdahl’s Law Tells Us:

 There’s always a limit to how much speed we can gain.

 If the sequential part is large, adding more processors won’t help much.
 Only if most of the program can be parallelized will more processors make a big
difference.
🧠 Example Connection:

If you run a large program on 4 processors (parallel computing) and it finishes faster,
you can use Speedup to measure how much faster, and Amdahl’s Law to understand why it
doesn’t become perfectly 4× faster.

💻 Hardware Architectures in Parallel and Distributed

Computing
In computing, the hardware architecture defines how processors are connected and how
they share memory and data while working together.
There are mainly three types:

1. Multiprocessors (Shared Memory Systems)

2. Networks of Workstations (Distributed Memory Systems)
3. Clusters (Latest Hybrid Approach)

Let’s go through each one step by step 👇

🧩 1. Multiprocessors (Shared Memory Architecture)

🔹 Definition:

A multiprocessor system is a single computer that has two or more processors (CPUs)
connected to a shared main memory.
All processors can access the same memory, so they can easily share data and work together on
the same task.

💡 Simple Example:

Imagine a big whiteboard in a classroom 🧠

 All students (processors) can read and write on the same board (memory).
 If one student writes something, others can see it immediately.

That’s how shared memory systems work.

⚙️How It Works:
  Processors are connected through a common bus or interconnection network.
 Each processor has its own small cache (for fast access), but all share the main memory.
 Operating system manages how processors access memory to avoid conflicts.

⚡ Advantages:

1. Easy Communication: All processors use the same memory — no need for message
passing.
2. Simpler Programming: Easier to write programs because everyone accesses the same
data.
3. Fast Data Sharing: No delay in transferring data between processors.

⚠️Disadvantages:

1. Limited Scalability: Only a few processors can share memory efficiently (usually up to
32–64).
2. Memory Conflict: If many processors try to use memory at the same time, it causes
delay.
3. Costly Hardware: Building shared-memory systems is expensive.

🧠 Example:

 Your modern laptop or desktop with 8 or 16 CPU cores uses shared memory
architecture.
 All cores share the same RAM and work together.

🌐 2. Networks of Workstations (Distributed Memory

Architecture)
🔹 Definition:

In a distributed memory system, each computer (or node) has its own private memory and its
own processor.
They are connected through a network (like Ethernet or Internet) and communicate by
sending messages.
💡 Simple Example:

Imagine many students sitting in different classrooms.

Each one has their own whiteboard (memory).
If one student wants to share something, they must send a message to others.

That’s how distributed memory systems work.

⚙️How It Works:

 Each processor works on its part of the problem.

 To share information, processors send data through the network.
 Commonly used in Distributed Computing systems and supercomputers.

⚡ Advantages:

1. Highly Scalable: You can add many computers (nodes).

2. Cost-Effective: Uses ordinary computers connected through a network.
3. Fault Tolerance: If one computer fails, others keep working.

⚠️Disadvantages:

1. Complex Programming: Programmers must manually manage data sharing.

2. Communication Delay: Sending data over a network is slower than shared memory.
3. Harder Synchronization: Keeping all systems in sync is challenging.

🧠 Example:

 Google search servers or Amazon Web Services (AWS).

Thousands of computers across data centers communicate over networks to process user
requests.
 Message Passing Interface (MPI) is often used for communication.

3. Clusters (Latest Hybrid Variation)

🔹 Definition:

A cluster combines the best of both architectures.

It is a group of independent computers (nodes) connected by a high-speed network, but each
node itself can be a multiprocessor (shared memory system).

👉 So, each node has shared memory inside, and all nodes communicate outside via messages.

💡 Simple Example:

Imagine a school with many classrooms.

 Inside each classroom, students share one whiteboard (shared memory).

 To share with another classroom, they send messages (distributed memory).

That’s exactly how cluster systems work.

⚙️How It Works:

 Each node (computer) has multiple processors sharing the same memory.
 All nodes are connected by a fast local network (like Gigabit Ethernet or InfiniBand).
 A cluster looks like one big computer to the user but is actually made up of many small
systems.

⚡ Advantages:

1. High Performance: Combines parallel and distributed computing strengths.

2. Scalable: You can add more nodes to increase power.
3. Cost Efficient: Built using normal computers instead of one super-expensive machine.
4. Fault Tolerance: If one node fails, others can take over.

⚠️Disadvantages:

1. Complex Management: Requires special software to manage nodes.

2. Network Bottlenecks: Communication between nodes can slow things down.
3. Setup Cost: Needs powerful networking equipment.
🧠 Example:

 Beowulf Clusters (used in research labs)

 Google Cloud Data Centers
 Supercomputers like IBM’s Blue Gene or NASA’s clusters use this approach.

🔍 Comparison Table
Feature Multiprocessor Network of Workstations Cluster (Hybrid System)
(Shared Memory) (Distributed Memory)
Memory Shared among all Each node has its own Shared within nodes,
processors memory distributed between nodes
Communicatio Through shared Through messages over a Combination of both
n memory network
Scalability Limited Very high High
Cost Expensive Cheaper Moderate
Performance Very fast for small Slower due to network Very fast and scalable
scale delay
Example Multi-core PC Google Servers NASA Supercomputer
Cluster

🏁 Conclusion
 Multiprocessors → Many processors inside one computer sharing one memory.
 Distributed systems → Many computers, each with its own memory, connected through
a network.
 Clusters → A combination of both: each computer has multiple processors, and all are
connected for teamwork.

👉 As we move from multiprocessors → distributed → clusters,

we gain more power, scalability, and flexibility, but also more complexity.

🧠 Software Architectures in Parallel and Distributed Systems

(Detailed Explanation)
In parallel and distributed computing, software architecture defines how the tasks, data, and
communication between processors or computers are organized.
It tells us how programs will run simultaneously and how they will share or exchange data
to complete large problems efficiently.

There are four main types of software architectures:

 1. Threads and Shared Memory
2. Processes and Message Passing
3. Distributed Shared Memory (DSM)
4. Distributed Shared Data (DSD)

Let’s understand each one in detail 👇

🧵 1. Threads and Shared Memory

🧩 What are Threads?

 A thread is the smallest unit of a program that can be executed independently.

 Threads are like mini-programs inside a bigger program that can run at the same time.
 They all share the same memory space — meaning they can directly read and write to
the same variables and data.

🧠 How it Works

 All threads exist inside one process (one running program).

 Since they share the same memory, they can quickly communicate with each other by
accessing the same variables.

💡 Example

Imagine a photo editing app:

 One thread adjusts the brightness,

 Another changes the contrast,
 Another adds filters.
All threads work on the same image (shared memory) — so the process is fast and
efficient.

⚙️Where It’s Used

 In parallel computing, where a single computer has multiple cores or processors.

 In applications that need speed and real-time performance — like video games,
multimedia software, and scientific simulations.

✅ Advantages

 Very fast communication, as threads directly share data.

 Efficient use of CPU cores.
 Suitable for tasks that run on the same computer.
❌ Disadvantages

 Difficult to manage — if two threads try to update the same data at once, it can cause
errors (race conditions).
 Debugging multithreaded programs is challenging.
 If one thread crashes, it may affect the entire program.

🧮 2. Processes and Message Passing

🧩 What are Processes?

 A process is an independent program with its own memory and resources.

 Unlike threads, processes do not share memory — each has its own separate data
space.

🧠 How it Works

 Since processes don’t share memory, they must communicate by sending and
receiving messages through a network or communication channel.
 This is done using methods like Message Passing Interface (MPI), sockets, or remote
procedure calls (RPC).

💡 Example

In an online shopping system:

 One process handles user login,

 Another manages the shopping cart,
 Another processes payments.
These processes communicate by sending messages (like “payment successful” or
“update cart”).

⚙️Where It’s Used

 In distributed systems, where different computers work together over a network.

 Examples: Banking systems, servers, cloud computing.

✅ Advantages

 Isolation: Each process is independent, so one failure doesn’t crash the others.
 Security: Processes can’t access each other’s memory directly.
 Flexibility: Works well across multiple computers in a network.

❌ Disadvantages
  Slower communication, since data must be sent through messages.
 More programming complexity — developers must design message handling carefully.
 Network issues can delay communication between processes.

🧠 3. Distributed Shared Memory (DSM)

🧩 What it is

 DSM is a hybrid model — it tries to combine the ease of shared memory with the
flexibility of distributed systems.
 Many computers are connected via a network, but software makes it look like they all
share one big memory.

🧠 How it Works

 Each computer has its own memory, but when one computer needs data from another,
DSM automatically transfers that data over the network.
 To the programmer, it appears as if all data is in one place, even though it’s spread
across many machines.

💡 Example

In a weather simulation system:

 Many computers calculate different parts of the atmosphere.

 When one needs information about another area, it simply reads it — DSM handles the
network communication automatically.

⚙️Where It’s Used

 In scientific computing, high-performance computing (HPC), and large-scale

simulations.

✅ Advantages

 Easy for programmers — they can code as if all memory is shared.

 Combines multiple computers’ power for large problems.
 Supports both scalability and parallelism.

❌ Disadvantages

 Slower than real shared memory, because data has to move through the network.
 Difficult to keep data consistent (when one computer updates data, others must be
informed).
  Needs complex software for memory synchronization.

🌐 4. Distributed Shared Data (DSD)

🧩 What it is

 DSD focuses on sharing data, not entire memory spaces.

 The data is stored on multiple machines, but accessible to all users or programs in the
network.
 Used when multiple people or systems need to work on the same data.

🧠 How it Works

 Each computer or user can access, read, or update shared data.

 The system ensures that changes made by one user are visible to everyone else.

💡 Example

Think of Google Docs:

 Many users edit the same document at once.

 Each user’s computer sends updates to the cloud.
 The cloud service synchronizes the document so all users see the latest version.

⚙️Where It’s Used

 In cloud computing, databases, and collaborative applications.

 Examples: Google Drive, Dropbox, shared databases, GitHub.

✅ Advantages

 Real-time data sharing among users or systems.

 Supports collaboration and data availability across the world.
 Data is usually replicated for safety and faster access.

❌ Disadvantages

 Data consistency issues if many users update the same data at once.
 Network delays can affect synchronization.
 Needs strong security to prevent unauthorized data access.
📊 Comparison Table
Architectur Memory Communicatio Common Example Advantages Disadvantage
e Type n Method Use s
Threads & Shared Direct Parallel Video Very fast, Hard to
Shared (same memory computing editing, efficient manage, race
Memory computer access games conditions
)
Processes Separate Network Distributed Banking, Independen Slower
& Message memory messages systems servers t, secure communicatio
Passing n
Distributed Simulate Network- High- Weather Easy for Complex
Shared d shared based performanc simulatio programme consistency
Memory e systems n rs
(DSM)
Distributed Shared Network Cloud Google Real-time Sync and
Shared data only updates systems Docs, collaboratio network
Data databases n issues
(DSD)

🧭 Relation to Hardware Architectures

Hardware Software Description

Architecture
Multiprocessors (Shared Threads and Shared Both use one memory for all processors or
Memory) Memory threads.
Networks of Workstations Processes and Each computer has its own memory; data
(Distributed Memory) Message Passing sent via network.
Clusters DSM or DSD Combination of both — multiple
computers sharing data or memory through
a network.

⚙️Real-Life Analogy

Imagine a company office:

 Threads and Shared Memory: All employees share one desk — fast but crowded!
 Processes and Message Passing: Each employee has their own desk — they pass notes
to communicate.
 DSM: Everyone has their own desk, but there’s a big whiteboard that automatically
syncs between rooms.
  DSD: Everyone works on the same online document stored in the cloud.

⚙️Parallel Algorithms (In Detail)

🧠 1. Introduction
A Parallel Algorithm is an algorithm that allows multiple operations to be performed
simultaneously.
Instead of solving a problem step by step (as in a sequential algorithm), a parallel algorithm
divides the problem into smaller independent parts and executes them at the same time on
multiple processors or cores.

💡 Simple Definition

A Parallel Algorithm is one that splits a large task into smaller subtasks, which are processed
simultaneously by multiple processors to achieve faster results.

🧩 2. Need for Parallel Algorithms

In the modern world, computers are expected to process huge amounts of data quickly — such
as in artificial intelligence, big data, climate modeling, and scientific simulations.
Sequential algorithms take too long for such complex tasks.
Parallel algorithms solve this problem by dividing the work among many processors.

✅ Advantages of Using Parallel Algorithms:

1. Speedup – Tasks are completed faster.

2. Efficiency – Makes better use of multi-core processors.
3. Handles Large Data – Suitable for high-performance applications.
4. Scalability – Performance increases as you add more processors.

🔍 3. Comparison: Sequential vs Parallel Algorithm

Feature Sequential Algorithm Parallel Algorithm
Execution One task at a time Many tasks at once
Processor Single processor Multiple processors
Speed Slower Faster
Communication Not needed Necessary between processors
Example Bubble sort on one CPU Parallel merge sort on multiple CPUs

4. Structure of a Parallel Algorithm

A well-designed parallel algorithm follows these main steps:

🔹 Step 1: Problem Decomposition

 Break the main problem into smaller, independent subproblems.

 Each subproblem should be small enough to be handled by a separate processor.

🧩 Example:
Sorting 1 million numbers → divide them into 10 sets of 100,000 → sort each set in parallel.

🔹 Step 2: Task Assignment

 Assign each subproblem to a different processor or core.

 The goal is to balance the workload so no processor stays idle.

🧠 Example:
If you have 4 processors, each gets 25% of the data.

🔹 Step 3: Communication

 Some subtasks may need to share intermediate results with others.

 Communication happens through shared memory or message passing.

💬 Example:
One processor may need results from another before combining final output.

🔹 Step 4: Synchronization

 Synchronization ensures that all processors finish their assigned work before moving to
the next stage.
 This prevents errors caused by missing or incomplete data.
⏰ Example:
In matrix multiplication, all partial results must be ready before computing the final matrix.

🔹 Step 5: Combination

 After each processor finishes its part, the results are combined to form the final output.

🧮 Example:
Each processor sorts a subset, and then the program merges all subsets into one sorted list.

⚡ 5. Key Concepts in Parallel Algorithms

🧮 a) Speedup

It measures how much faster a parallel algorithm performs compared to a sequential one.

Speedup (S)=TsTp\text{Speedup (S)} = \frac{T_s}{T_p}Speedup (S)=TpTs

Where:

 TsT_sTs = Time taken by sequential algorithm

 TpT_pTp = Time taken by parallel algorithm

🧠 Example:
If sequential time = 100 seconds, parallel time = 25 seconds →
Speedup = 100 / 25 = 4×

🧩 b) Efficiency

Shows how effectively the processors are being used.

Efficiency (E)=SP=TsP×Tp\text{Efficiency (E)} = \frac{S}{P} = \frac{T_s}{P \times T_p}Efficiency (E)=PS

=P×TpTs

Where P is the number of processors.

🧠 Example:
If Speedup = 4 using 8 processors → Efficiency = 4/8 = 0.5 (50%)
⚖️c) Scalability

Refers to how well performance improves when we increase the number of processors.
A good parallel algorithm scales well, meaning it keeps getting faster as we add more
processors.

💬 d) Overhead

Extra time required for communication, synchronization, and data management between
processors.

🧠 Example:
If processors spend too much time exchanging messages, performance drops even if you add
more CPUs.

🧮 6. Types of Parallelism
Parallel algorithms can use different types of parallelism, depending on how the work is
divided.

🧩 1. Data Parallelism

 The same operation is applied to different chunks of data at the same time.
 Each processor handles a part of the data.

🧠 Example:
If you have a list of 1,000 numbers to double, divide it among 4 processors → each doubles 250
numbers.

✅ Used in: Image processing, scientific simulations, AI model training.

⚙️2. Task Parallelism

 Different processors perform different operations (tasks) on the same or different data.
🧠 Example:
In a video editing app:

 One processor adds filters,

 Another adjusts brightness,
 Another adds subtitles.

✅ Used in: Multitasking systems and simulations.

🔄 3. Pipeline Parallelism

 Tasks are divided into stages; each stage works on a different part of the input at the
same time.
 Like a factory assembly line.

🧠 Example:
In a CPU:

1. Fetch instruction
2. Decode
3. Execute
4. Write result

Each step works in parallel on different instructions.

✅ Used in: Processors, data streaming, video encoding.

💡 7. Examples of Parallel Algorithms

Let’s look at a few popular examples 👇

🧩 Example 1: Parallel Sum

To find the sum of 8 numbers: [2, 4, 6, 8, 10, 12, 14, 16]

 Sequentially: Add one by one → 7 additions.

 Parallel: Divide numbers among 4 processors.
o P1: (2+4) = 6
o P2: (6+8) = 14
 o P3: (10+12) = 22
o P4: (14+16) = 30
Then add results → 6 + 14 + 22 + 30 = 72.

✅ Result: Same output, less time.

🧮 Example 2: Parallel Matrix Multiplication

 Matrices are divided into smaller sub-matrices.

 Each processor multiplies its assigned part.
 All partial results are combined into the final matrix.

✅ Used in: Artificial Intelligence, scientific calculations, 3D graphics.

🔄 Example 3: Parallel Merge Sort

 Data is split into subarrays.

 Each subarray is sorted by a separate processor.
 The results are merged together.

✅ Used in: Big data sorting, database indexing.

🔍 8. Performance Metrics
Metric Meaning Ideal Value
Speedup (S) How much faster the algorithm runs in parallel The higher, the better
Efficiency (E) How well processors are used Close to 1 (100%)
Scalability How performance improves with more High
processors
Overhead Extra time for communication/synchronization Low

🧠 9. Challenges in Designing Parallel Algorithms

1. Data Dependency:
Some parts of the problem depend on others and can’t be done in parallel.
2. Communication Overhead:
Too much communication between processors can slow performance.
 3. Load Balancing:
If work isn’t divided equally, some processors may stay idle.
4. Synchronization:
Keeping all processors in sync is difficult.
5. Debugging and Testing:
Parallel programs are harder to debug due to multiple execution paths.

10. Relation to Amdahl’s Law

Amdahl’s Law helps to estimate maximum possible speedup of a parallel algorithm.
It shows that if a portion of the program is sequential, it limits the total speedup.

Speedup=1(1−P)+PN\text{Speedup} = \frac{1}{(1 - P) + \frac{P}{N}}Speedup=(1−P)+NP1

Where:

 PPP = Fraction of program that can be parallelized

 NNN = Number of processors

🧠 Example:
If 80% of a program can be parallelized using 4 processors:

S=1(1−0.8)+0.84=10.2+0.2=2.5×S = \frac{1}{(1 - 0.8) + \frac{0.8}{4}} = \frac{1}{0.2 + 0.2} =

2.5×S=(1−0.8)+40.81=0.2+0.21=2.5×

✅ So, the maximum speedup is 2.5× (even with 4 processors).

🔧 11. Relation to Hardware and Software Architectures

Architecture Description Relation to Parallel Algorithms
Multiprocessors (Shared One computer with many cores Parallel algorithms run using threads
Memory) sharing one memory and shared memory.
Clusters / Distributed Many computers connected Parallel algorithms use message
Systems through a network passing (MPI).
Software Architectures Threads, processes, DSM, DSD Provide the tools to implement
parallel algorithms efficiently.

🌍 12. Real-Life Applications

 Field Application
Scientific Research Climate modeling, physics simulations
Artificial Intelligence Neural network training, deep learning
Medical Field DNA analysis, MRI image processing
Engineering Structural design simulations
Business Big data analytics, financial forecasting
Entertainment Graphics rendering, gaming engines

🧾 13. Advantages and Disadvantages

✅ Advantages

1. Faster execution time.

2. Can process massive data.
3. Improves hardware utilization.
4. Allows real-time problem-solving.
5. Increases scalability and flexibility.

❌ Disadvantages

1. Complex to design and debug.

2. Needs high communication between processors.
3. Synchronization delays.
4. Costly hardware and maintenance.
5. Not every problem can be parallelized.

✨ 14. Conclusion
Parallel Algorithms are the foundation of high-performance computing.
They enable modern systems — from supercomputers to cloud platforms — to perform complex
calculations quickly by dividing and conquering tasks.

However, designing an efficient parallel algorithm requires balance between computation and
communication, good load distribution, and careful synchronization.

In short:
Parallel Algorithms make computers faster and smarter — but they also make programming
more challenging.
⚙️Concurrency and Synchronization (In Detail)

🧠 1. Introduction
When multiple tasks or processes run at the same time in a system, we call it concurrency.
But when these tasks share resources (like memory, files, or data), there is a risk of conflicts or
errors — that’s where synchronization comes in.

So basically:

Concurrency = Doing multiple things at once

Synchronization = Keeping them working together correctly

💡 2. What is Concurrency?
Concurrency means that two or more tasks are being executed overlapping in time.
It doesn’t necessarily mean they’re running exactly at the same instant (like parallelism), but
they make progress independently.

🔹 Simple Definition:

Concurrency is when multiple processes or threads execute during the same period, sharing
system resources like CPU and memory.

🧩 Example 1:

Imagine you’re using your computer:

 You are downloading a file,

 Listening to music,
 And typing a document.

All these tasks appear to happen at once — that’s concurrency.

Even if your CPU executes one task at a time (very fast), it switches between them, giving the
illusion of simultaneous execution.
🧩 Example 2 (Programming Level):

If two threads in a program are:

 One thread printing numbers (1–10)

 Another printing alphabets (A–J)

Both can run “concurrently,” meaning they share the CPU time in turns.

⚙️3. Concurrency vs Parallelism

Feature Concurrency Parallelism
Meaning Multiple tasks make progress at the Multiple tasks execute exactly at the same time
same time
Processors Can be on a single processor (time- Requires multiple processors or cores
sharing)
Goal Manage multiple tasks effectively Speed up computation
Example A single-core CPU running multiple A quad-core CPU executing four programs
apps simultaneously

✅ In short:

All parallel systems are concurrent, but not all concurrent systems are parallel.

🧩 4. Benefits of Concurrency
1. Better CPU Utilization – No CPU time wasted waiting for I/O.
2. Faster Response – Systems stay responsive even under heavy load.
3. Simpler Program Design – Each task can be written independently.
4. Efficient Multitasking – Supports multiple users or background tasks.
5. Scalability – Easy to scale on multi-core systems.

5. Problems in Concurrency
When multiple tasks share resources (like memory, variables, or files), conflicts can occur.

These problems are known as race conditions, deadlocks, or inconsistency errors.

💥 a) Race Condition

Occurs when two or more processes try to change the same data at the same time, and the final
result depends on the timing.

🧠 Example:
Two threads trying to update a variable balance = balance + 100 at the same time.
If not synchronized, one update might get lost — wrong result!

⚰️b) Deadlock

Occurs when two processes wait for each other’s resources and neither can continue.

🧠 Example:

 Process A has Resource 1 and needs Resource 2.

 Process B has Resource 2 and needs Resource 1.
→ Both wait forever = Deadlock.

🌀 c) Starvation

When one process never gets CPU time or access to resources because others keep getting
priority.

🧩 d) Inconsistency

If multiple threads read and write shared data without coordination, the data may become
inconsistent or corrupted.

🧭 6. What is Synchronization?
Synchronization is the method used to control the execution order of concurrent processes so
that they do not interfere with each other.
It ensures that only one process accesses shared resources at a time — keeping data consistent
and preventing race conditions.

🔹 Simple Definition:

Synchronization is a technique that coordinates concurrent processes to ensure correct execution

when they share resources.

🧩 Real-Life Example:

Think of a bank ATM system:

 Two people cannot withdraw money from the same account at the exact same time.
 If they do, both might get full balance → error!

The system must synchronize access to that account record so only one withdrawal happens at a
time.

⚙️7. Types of Synchronization

Synchronization can be classified into two main types:

🧩 A. Process Synchronization

Used when independent processes (not sharing memory) need to coordinate their activities.

✅ Example:
In a producer-consumer problem:

 The producer creates data.

 The consumer uses data.
→ Synchronization ensures the consumer doesn’t try to read before data is produced.

🧩 B. Thread Synchronization
Used when multiple threads share the same memory space and need to access shared data.

✅ Example:
In a multi-threaded program, two threads updating the same variable must be synchronized to
avoid conflicts.

🔧 8. Methods / Mechanisms of Synchronization

There are different tools and methods to synchronize concurrent processes.

🔹 1. Locks (Mutexes)

A lock allows only one thread or process to access a shared resource at a time.

🧠 Example:

 Thread A locks the variable to update it.

 Thread B must wait until A unlocks it.

✅ Useful for protecting critical sections of code.

🔹 2. Semaphores

A semaphore is a variable that controls access to shared resources.

It has two operations:

 wait() → decreases the semaphore (before entering critical section)

 signal() → increases it (after leaving)

🧩 Example:
A semaphore initialized to 1 allows one process at a time.
If set to N, it allows N processes concurrently.

🔹 3. Monitors

A monitor is a high-level construct that allows safe access to shared data.

It combines locks and condition variables automatically.
🧠 Example:
Languages like Java provide synchronized blocks and methods using monitors.

🔹 4. Condition Variables

Used to make a thread wait until a specific condition becomes true.

Helps coordinate actions among threads.

🔹 5. Message Passing

Instead of sharing memory, processes send messages to communicate.

This avoids direct interference with each other.

🧠 Example:
Used in distributed systems and MPI (Message Passing Interface).

🧩 9. Critical Section Problem

The critical section is the part of the program where shared resources are accessed.
Synchronization ensures that only one process enters the critical section at a time.

✅ Solution Requirements:

1. Mutual Exclusion: Only one process can enter the critical section.
2. Progress: If no one is in the critical section, one process must be allowed to enter.
3. Bounded Waiting: No process should wait forever.

⚙️10. Synchronization in Parallel and Distributed Systems

System Type Synchronization Method Example

Parallel System (Shared Memory) Locks, mutexes, semaphores Threads in a CPU share data

Distributed System (Different Message passing, distributed Clustered servers exchanging

Machines) semaphores updates
In parallel computing, synchronization ensures all processors finish a phase before moving to
the next.

In distributed systems, synchronization ensures all nodes agree on shared data (e.g., blockchain
consensus).

🧮 11. Common Synchronization Problems and Solutions

Problem Description Solution
Race Condition Two threads modify data simultaneously Use locks or mutex
Deadlock Two processes wait on each other Avoid circular waits, use
timeouts
Starvation A process never gets access Use fair scheduling
Priority Low-priority process holds a lock needed by a high- Priority inheritance
Inversion priority one

💡 12. Example: Producer–Consumer Problem

Scenario:

 The Producer creates data (puts it in a buffer).

 The Consumer uses data (takes it from the buffer).

Both must work together without conflict.

⚙️Solution using Semaphores:

wait(empty);
wait(mutex);
// Produce item and add to buffer
signal(mutex);
signal(full);

and

wait(full);
wait(mutex);
// Consume item from buffer
signal(mutex);
signal(empty);

✅ Synchronization ensures producer doesn’t overwrite full buffer and consumer doesn’t read
empty one.
🧠 13. Relation to Parallel Algorithms
Aspect Parallel Algorithms Concurrency &
Synchronization
Goal Execute multiple tasks faster Execute multiple tasks
safely
Focus Divide work among processors Coordinate shared access
Example Parallel sorting, matrix multiplication Locks, semaphores,
thread safety
Connection Parallel algorithms need synchronization to avoid data
conflicts when running concurrently

🧾 14. Advantages and Disadvantages

✅ Advantages

 Ensures correct program behavior

 Prevents race conditions and data corruption
 Maintains consistency in shared data
 Enables reliable parallel and distributed systems

❌ Disadvantages

 Increases program complexity

 May reduce performance due to waiting
 Risk of deadlocks if not handled properly
 Harder to debug and maintain

✨ 15. Conclusion
Concurrency and Synchronization are core concepts in modern computing.
They enable systems to handle multiple operations efficiently while ensuring data integrity
and coordination.

Without synchronization, concurrent systems would be unreliable and produce incorrect results.

In short:
Concurrency gives speed and multitasking,
Synchronization ensures correctness and stability.
⚙️Data and Work Partitioning

🧠 1. Introduction
In Parallel and Distributed Computing, the main goal is to divide a big problem into smaller
parts so that multiple processors can work on them simultaneously.
This process of dividing the work or data is known as partitioning (or decomposition).

💡 Simple Definition:

Partitioning means dividing a large task (or dataset) into smaller, independent parts that can be
processed in parallel by different processors.

🧩 Why Partitioning is Important

Without proper partitioning:

 Some processors may do too much work while others stay idle.
 Communication overhead increases.
 The system becomes inefficient and slow.

✅ Proper partitioning helps to:

 Balance the workload

 Reduce waiting time
 Improve speedup, efficiency, and scalability

🔍 2. Two Main Types of Partitioning

Partitioning can be divided into two main categories:

1. Data Partitioning
2. Work (Task) Partitioning

Both aim to distribute the computation load evenly, but they focus on different aspects of the
problem.
🧩 3. Data Partitioning
📘 Definition:

Data Partitioning means dividing the input data into smaller parts (subsets), and assigning each
subset to a different processor for processing.

Here, each processor performs the same operation but on different parts of the data.

That’s why data partitioning is also called Data Parallelism.

🧠 Example 1:

Suppose we want to find the average of 1 million numbers.

 We can divide the numbers into 4 equal sets of 250,000 numbers each.
 Each processor calculates the average of its portion.
 Then we combine all partial results to find the final average.

✅ Result: Work completed 4× faster than a single processor.

🧠 Example 2:

In image processing, each processor can handle a different part of the image — like one
processor processes the top-left corner, another handles the bottom-right, etc.

🔹 Advantages of Data Partitioning

 Easy to implement for large datasets

 Reduces memory bottleneck
 All processors perform similar operations (uniform workload)
 Highly scalable

🔸 Disadvantages

 Requires large data that can be split evenly

  Processors must often communicate intermediate results
 May need synchronization when combining results

🧮 Types of Data Partitioning

Type Description Example

Block Partitioning Data divided into equal-sized Each processor gets an equal-sized block of
blocks array
Cyclic Partitioning Data divided in round-robin Processor 1 → elements 1,5,9,…; Processor 2
fashion → 2,6,10,…
Block-Cyclic Combines block and cyclic Useful for load balancing when tasks vary in
Partitioning methods size
Random Partitioning Data assigned randomly For irregular or unpredictable workloads

⚙️4. Work (Task) Partitioning

📘 Definition:

Work Partitioning means dividing the total work or computation (i.e., the tasks or operations)
among multiple processors.

Here, each processor may perform a different operation (not necessarily the same one).
That’s why work partitioning is also called Task Parallelism.

🧠 Example 1:

In a video editing software:

 Processor 1 → Extracts frames

 Processor 2 → Applies filters
 Processor 3 → Adds audio
 Processor 4 → Exports video

Each performs a different task on the same data stream.

🧠 Example 2:

In a web server:
  One thread handles user requests
 Another processes database queries
 Another sends responses

All threads work in parallel but perform different functions.

🔹 Advantages of Work Partitioning

 Utilizes heterogeneous systems (processors can do different types of tasks)

 Improves overall system throughput
 Reduces idle time when tasks vary in complexity

🔸 Disadvantages

 More complex to design and manage

 Harder to ensure load balancing (some tasks take longer than others)
 Requires more inter-task communication

🔄 5. Comparison: Data vs Work Partitioning

Feature Data Partitioning Work Partitioning
Focus Divide data among processors Divide tasks/operations among processors
Type of Data Parallelism Task Parallelism
Parallelism
Operation All processors perform same Different processors perform different
operation on different data operations
Example Each processor sorts part of a list One processor reads data, another sorts,
another writes output
Complexity Easier to implement More complex to manage
Scalability Highly scalable for large data May require coordination between tasks

✅ In simple words:

 Data Partitioning → same work, different data

 Work Partitioning → different work, same or related data
⚙️6. Steps Involved in Partitioning
1. Decomposition:
o Break the main problem into smaller subproblems.
o Example: Divide a matrix into smaller blocks.
2. Dependency Analysis:
o Check which tasks or data depend on others.
o Independent parts can be executed in parallel.
3. Assignment:
o Assign each subproblem to a processor.
o Try to balance the workload.
4. Synchronization:
o Coordinate tasks if some need results from others.
5. Communication:
o Exchange necessary data between processors when required.
6. Combination:
o Combine partial results into a final output.

🧮 7. Load Balancing
A key goal of partitioning is load balancing, which means ensuring each processor gets an
equal amount of work.

If one processor finishes early while others are still working, the system’s efficiency decreases.

✅ Example:
If Processor 1 gets a large block and Processor 2 gets a small one → total performance suffers.
Hence, equal partitioning or dynamic task allocation is used.

💬 8. Partitioning in Parallel Algorithms

Example Algorithm Partitioning Type Description
Parallel Merge Sort Data Partitioning Each processor sorts a subset of data
Matrix Multiplication Data Partitioning Each processor multiplies a section of the matrix
Video Rendering Work Partitioning Each processor performs different stages of processing
MapReduce Data Partitioning Each node processes part of the data independently

🧩 9. Partitioning in Distributed Systems

In distributed systems (like cloud computing), data and tasks are divided among different
machines connected by a network.

Partitioning Type Example in Distributed System

Data Partitioning Each server stores and processes part of a large database (e.g., Google Bigtable)
Work Partitioning One machine collects data, another analyzes it, another visualizes it

✅ Example:
In Hadoop (a distributed computing framework), data partitioning is done automatically using
the MapReduce model:

 Map phase: divides data

 Reduce phase: combines results

🧠 10. Challenges in Partitioning

1. Data Dependency:
Some parts depend on results from others → limits parallelism.
2. Load Imbalance:
Uneven distribution leads to idle processors.
3. Communication Overhead:
Too much data exchange reduces performance.
4. Granularity:
Too small partitions cause overhead; too large reduce concurrency.
5. Synchronization Delay:
Processors may need to wait for others to finish.

🧾 11. Granularity in Partitioning

Granularity means the size of each partitioned task or data unit.

Type Description Example

Fine-grained Many small tasks; high communication Each processor handles a few data items
Coarse-grained Few large tasks; low communication Each processor handles large data blocks

✅ Trade-off:
Fine-grained = more parallelism but more communication.
Coarse-grained = less communication but less flexibility.
💡 12. Real-Life Examples
Domain Example Partitioning Type
Scientific Computing Dividing a large matrix into smaller submatrices Data
Web Search Engines Each server indexes a different set of web pages Data
Machine Learning Each GPU trains part of a neural network Data
Video Games Different threads handle physics, rendering, and sound Work
Banking Systems One server processes transactions, another manages logs Work

⚖️13. Relation to Concurrency and Synchronization

Concept Relation
Concurrency Partitioning creates multiple tasks that can run concurrently
Synchronization Ensures the partitioned tasks work together correctly when sharing results
Parallel Use partitioning to divide work and data among processors for faster computation
Algorithms

✨ 14. Conclusion
Data and Work Partitioning are fundamental steps in designing any parallel or distributed
algorithm.

They determine how efficiently a system can use its processors and how well it scales as we add
more resources.

In short:

 Data Partitioning = Divide data, same task.

 Work Partitioning = Divide tasks, same or shared data.

Both together help achieve maximum speedup, efficiency, and scalability in modern
computing systems.

🧠 Common Parallelization Strategies

Parallelization means dividing a big task into smaller parts that can run at the same time on
multiple processors.
To make a program faster, we must decide how to split the work — that’s what parallelization
strategies are all about.

There are several common strategies used in Parallel and Distributed Computing to achieve
this efficiently.
🟦 1. Task Parallelism (Functional Parallelism)

Meaning:
In this strategy, different tasks or functions are executed in parallel.
Each processor performs a different operation on the same or different data.

Example:
Suppose you’re editing a video —

 One processor handles audio processing

 Another works on video rendering
 Another adds filters or effects

All these tasks run at the same time but perform different functions.

Used in:

 Multimedia processing
 Web servers (handling multiple requests)
 Robotics (different sensors running parallel tasks)

🟩 2. Data Parallelism

Meaning:
In data parallelism, the same operation is performed on different pieces of data at the same
time.
Each processor handles a portion of the total data.

Example:
If you want to find the sum of 1 million numbers,

 Divide the numbers into 4 parts,

 Give each part to a different processor,
 Each processor calculates its partial sum,
 Then combine all partial sums for the final result.

Used in:

 Scientific computations
 Image and video processing
 Machine learning (training models on large datasets)
🟨 3. Pipeline Parallelism

Meaning:
The work is divided into stages, where each stage performs part of the task.
As soon as one stage finishes, its output becomes the input for the next stage — just like an
assembly line in a factory.

Example:
In video streaming:

 Stage 1 → reads video frames

 Stage 2 → compresses the frames
 Stage 3 → sends frames over the network

Each stage runs in parallel, processing different parts of the data.

Used in:

 Video and audio encoding

 CPU instruction pipelines
 Production lines in factories

🟧 4. Hybrid Parallelism

Meaning:
Hybrid parallelism is a combination of data and task parallelism.
It uses both techniques together to get better performance.

Example:
In a weather simulation:

 Task parallelism: One group of processors handles temperature, another handles wind
speed.
 Data parallelism: Within each group, the data (like different regions) is divided among
processors.

Used in:

 Complex simulations (like climate modeling)

 High-performance scientific computing
🟥 5. Speculative Parallelism

Meaning:
In this method, the system executes multiple possible tasks in parallel before knowing which
one is needed.
If one task gives the correct result, the others are discarded.

Example:
In artificial intelligence, different possible solutions might be calculated simultaneously, and the
best one is chosen.

Used in:

 Artificial intelligence
 Predictive systems
 Compiler optimization

🟦 6. Loop-Level Parallelism

Meaning:
This strategy focuses on parallelizing loops in a program.
If the loop iterations are independent, they can be executed at the same time.

Example:

for i in range(1000):
A[i] = B[i] + C[i]

Each iteration can be handled by a separate processor since they don’t depend on each other.

Used in:

 Numerical analysis
 Image pixel processing
 Array computations

⚙️Summary Table
Strategy What it Does Example
Task Parallelism Runs different tasks at the same time Video editing (audio + video +
effects)
Data Parallelism Runs the same task on different data Sum of large datasets
Pipeline Breaks task into stages like an Video streaming
Parallelism assembly line
Hybrid Parallelism Combines data + task parallelism Weather simulation
Speculative Runs multiple possible tasks before AI predictions
Parallelism knowing result
Loop-Level Runs independent loop iterations at Array computations
Parallelism once

💡 Connection to Previous Topics

 In Parallel Algorithms, these strategies help design efficient algorithms that divide
work properly.
 In Data and Work Partitioning, you decide how to split data/work — these strategies
are the methods to actually perform that division.
 In Concurrency and Synchronization, once tasks are running in parallel,
synchronization ensures they don’t interfere with each other.

🧠 Granularity in Parallel Computing

📘 Definition:

Granularity refers to how much work is done by each part (or task) of a parallel program
before communication or synchronization happens.

In simple words:

It tells us how big or small each piece of work is when we divide a task into parts to run in
parallel.

So, granularity = amount of computation per communication between processors.

⚙️Understanding the Concept

When a large program is divided into smaller tasks for parallel execution:

 If tasks are large and do a lot of work, it’s called coarse-grained.

 If tasks are small and do little work, it’s called fine-grained.

Granularity helps decide how many processors should be used and how tasks communicate
with each other.
🟩 1. Fine-Grained Parallelism
Meaning:

 The work is divided into very small tasks.

 Each processor performs a tiny amount of computation before communicating or
synchronizing with others.

Advantages:

 Better load balancing (tasks are evenly distributed).

 Can achieve very high parallelism (many processors used).

Disadvantages:

 High communication overhead (too many small tasks need constant communication).
 Managing and synchronizing many small tasks is complex.

Example:
Adding two large arrays element by element:

 Each processor handles a few elements only.

 After every small computation, processors must communicate results.

Used in:

 Real-time systems
 Simulations requiring close coordination

🟦 2. Coarse-Grained Parallelism
Meaning:

 The work is divided into larger tasks.

 Each processor does a lot of computation before needing to communicate.

Advantages:

 Less communication overhead (fewer messages between processors).

 Easier to manage and synchronize.

Disadvantages:
  May lead to load imbalance (some processors finish early, others late).
 May not fully utilize all processors.

Example:
Dividing an image into 4 large parts and assigning each processor one part to process
completely.
Each processor works mostly independently.

Used in:

 Scientific simulations
 Batch processing
 Data analysis with large datasets

🟨 3. Medium-Grained (Mixed) Parallelism

Meaning:
This lies between fine and coarse granularity.
Tasks are of moderate size, giving a balance between computation and communication.

Advantages:

 Balanced performance
 Moderate communication cost
 Easier to manage than fine-grained systems

Example:
Dividing a 1000x1000 image into 10x10 blocks —
Each processor handles one block (not too small, not too big).

Used in:

 Image processing
 Computer graphics
 Distributed data processing

🧩 Comparison Table
Type Task Size Communication Performance Example
Frequency
Fine-Grained Very Very High May slow due to Element-wise
 Small overhead operations
Coarse- Large Low Fast but less Large data chunks
Grained balanced
Medium- Moderate Balanced Good balance Image block
Grained processing

🔁 Relation with Other Topics

 In Data and Work Partitioning, you decide how big each partition should be → this is
directly about granularity.
 In Common Parallelization Strategies, you choose whether to make tasks small (fine-
grained) or large (coarse-grained).
 In Concurrency and Synchronization, fine-grained systems need more
synchronization, while coarse-grained systems need less.

💡 Real-Life Example

Think of granularity like cooking with friends:

 Fine-grained: Everyone chops one small vegetable — too much coordination, slows
things down.
 Coarse-grained: Each person cooks one full dish — less coordination, faster overall.
 Medium-grained: Each person handles one part of a meal (like salad, dessert) —
balanced teamwork.

⚙️Load Balancing in Parallel and Distributed Computing

📘 Definition:

Load Balancing means distributing work evenly among all processors or computers in a
parallel or distributed system so that no processor stays idle while others are overloaded.

In simple words:

Load balancing ensures that every processor gets a fair amount of work — not too much, not
too little — so the system runs efficiently and quickly.

💡 Why Load Balancing is Important

In parallel and distributed systems, many processors work together on a single large task.
If one processor finishes early and sits idle while another is still busy, time is wasted.

Goal of load balancing:

 Keep all processors busy

 Reduce waiting time
 Increase system performance and speedup

🟩 Types of Load Balancing

There are mainly two types of load balancing:

🟦 1. Static Load Balancing

Meaning:
In static load balancing, the work is divided before execution begins.
The amount of work assigned to each processor is fixed at the start and does not change during
execution.

How it works:

 Tasks are divided equally based on known data (like size or complexity).
 The distribution stays the same throughout the process.

Advantages:

 Simple and easy to implement.

 Less communication needed between processors.

Disadvantages:

 Not suitable when tasks take different amounts of time (can cause imbalance).
 If one processor is slower or gets a harder task, it can delay the entire process.

Example:
Suppose you divide 100 tasks among 5 processors → each gets 20 tasks.
If one processor gets heavier tasks, it will finish later than others.

Used in:
  Systems where workload is predictable.
 Scientific simulations with known data sizes.

🟩 2. Dynamic Load Balancing

Meaning:
In dynamic load balancing, the system continuously checks how busy each processor is during
execution and redistributes tasks if needed.

How it works:

 If one processor finishes early, it can take extra work from overloaded processors.
 The system tries to keep all processors equally busy.

Advantages:

 Adapts to changing workloads.

 Improves system efficiency and reduces idle time.

Disadvantages:

 Needs more communication between processors.

 More complex to design and manage.

Example:
If one processor finishes its tasks early, it can take remaining work from another processor that
still has pending tasks.

Used in:

 Cloud computing
 Distributed networks
 Real-time processing systems

🧩 Load Balancing Techniques

1. Round Robin:
o Tasks are assigned one by one in a circular order.
o Simple but doesn’t consider processor speed.
2. Randomized Allocation:
o Tasks are assigned to processors randomly.
 o Easy to implement but may not be optimal.
3. Centralized Load Balancing:
o One master node manages and distributes tasks to worker nodes.
o Efficient but can cause a bottleneck if the master is overloaded.
4. Distributed Load Balancing:
o All nodes cooperate and share information to balance the load.
o No single point of failure; more scalable.
5. Work Stealing:
o Idle processors “steal” tasks from busy processors automatically.
o Common in dynamic systems.

⚖️Goals of Load Balancing

Goal Explanation
Fairness Every processor gets equal work
Efficiency No processor remains idle
Scalability System can handle more processors easily
Fault Tolerance If one processor fails, others take over its work
Reduced Communication Delay Less waiting time between dependent tasks

🧠 Real-Life Example
Imagine a group project with 5 members:

 If one person does most of the work while others relax, the project finishes late
(imbalance).
 If everyone does equal work, the project finishes faster (balanced).

This is the same idea behind load balancing — fair work distribution for faster results.

🔁 Relation with Other Topics

 In Data and Work Partitioning, you decide how to divide the workload — load
balancing ensures this division is fair.
 In Parallel Algorithms, good load balancing improves speedup and efficiency.
 In Granularity, smaller tasks (fine-grained) make dynamic load balancing easier,
while larger tasks (coarse-grained) may need static balancing.
✅ Summary:

Load balancing ensures that all processors work efficiently and none stay idle, which improves
performance, resource use, and speed in parallel and distributed systems.

⚙️Examples of Parallel Algorithms

Parallel algorithms are designed to perform multiple operations at the same time using
several processors.
Let’s look at some of the most common and important examples 👇

🟩 1. Parallel Search

Definition:
Parallel search means finding an item in a large dataset by dividing the data into smaller parts
and letting multiple processors search simultaneously.

How it works:

1. The data (like an array or database) is divided into several chunks.

2. Each processor searches its own chunk at the same time.
3. As soon as one processor finds the item, all others stop.

Example:
Suppose you have a list of 1 million numbers and you need to find the number 500.

 If you use 4 processors, each searches 250,000 numbers.

 The search finishes 4 times faster (ideally).

Real-world example:

 Searching files in cloud storage.

 Looking for keywords in large text databases.

Advantages:

 Much faster than sequential searching for large datasets.

 Easy to implement using shared or distributed memory.

🟦 2. Parallel Sorting
Definition:
Parallel sorting means sorting large data by dividing it among multiple processors, sorting
each part, and then merging the results.

Common parallel sorting algorithms:

 Parallel Merge Sort

 Parallel Quick Sort
 Bitonic Sort
 Odd-Even Transposition Sort

Example (Parallel Merge Sort):

1. Divide the array into 4 parts.

2. Each processor sorts its part independently.
3. Finally, the sorted parts are merged together to form the complete sorted list.

Example:
Sorting a list of 1 million numbers using 4 processors →
Each sorts 250,000 numbers, then results are combined.

Used in:

 Database management systems

 Big data analytics
 Scientific simulations needing ordered data

🟨 3. Parallel Matrix Multiplication

Definition:
Matrix multiplication is a common operation in scientific and AI computations.
Parallel matrix multiplication divides matrices into smaller submatrices and multiplies them
simultaneously.

How it works:

 Each processor calculates part of the final matrix.

 The results are combined at the end.

Example:
For multiplying two 1000×1000 matrices using 4 processors:
Each processor handles one quarter of the matrix multiplication.

Used in:
  Machine learning
 Graphics processing
 Scientific computing

Benefits:

 Saves huge computation time

 Ideal for GPU and cluster systems

🟧 4. Parallel Prefix Sum (Scan)

Definition:
Prefix sum means computing cumulative sums in parallel.
It’s often used in algorithms like sorting, searching, and data compression.

Example:
Given numbers: [1, 2, 3, 4]
The prefix sum result is [1, 3, 6, 10].

In parallel computing:

 Each processor handles a portion of the array.

 Intermediate sums are shared and combined efficiently.

Used in:

 Data analysis
 Compilers
 GPU algorithms

🟥 5. Parallel Graph Algorithms

Definition:
Used to process large graphs (networks) faster — for example, finding shortest paths or
connectivity.

Examples:

 Parallel Breadth-First Search (BFS)

 Parallel Dijkstra’s Algorithm
Example:
In a social network graph, finding all users connected to a specific person can be done faster by
multiple processors exploring different connections at once.

Used in:

 Social network analysis

 Web crawling
 AI and pathfinding

🟫 6. Parallel Image Processing

Definition:
In image processing, each pixel or block of pixels can be processed independently — making it
perfect for parallel execution.

Example:
For applying a filter to a 4K image:

 Divide the image into 8 parts.

 Each processor applies the filter to its part simultaneously.

Used in:

 Medical imaging
 Computer vision
 Photography and video editing software

🧩 Comparison Table
Algorithm Purpose How Parallelism is Used Example Use
Parallel Search Find data quickly Split data among Keyword
processors search
Parallel Sorting Sort large datasets Each processor sorts part Database
of the data sorting
Parallel Matrix Multiply matrices Each processor handles AI training
Multiplication faster submatrix
Parallel Prefix Sum Compute cumulative Each handles partial sum Data analysis
results
Parallel Graph Process large graphs Explore nodes/edges in Social
Algorithms parallel network
Parallel Image Process pixels Divide image into regions Filter
Processing simultaneously application

🔁 Relation with Previous Topics

 These examples show how parallel algorithms use concepts like data partitioning,
granularity, and load balancing.
 For instance:
o In Parallel Search, data is partitioned.
o In Parallel Sorting, granularity defines how many elements each processor sorts.
o In Matrix Multiplication, load balancing ensures every processor gets equal
work.

💡 Simple Real-Life Example

Think of cleaning a huge room:

 If one person cleans the whole room → it takes long (sequential).

 If 4 people each clean a corner → it’s faster (parallel).

This is exactly how parallel algorithms improve speed and efficiency.

⚙️Shared-Memory Programming
📘 Definition:

In shared-memory programming, multiple processors (or threads) share the same memory
space.
Each processor can directly read and write data from a common memory area.

In simple words:

All threads or processors work together on a common task using the same memory — they can
see and modify each other’s data.

💡 Key Idea:

Shared-memory systems are easy to program because data does not need to be sent or received
between processors.
However, they require synchronization (like locks and semaphores) to prevent conflicts when
multiple threads access the same data.

🧩 Main Concepts in Shared-Memory Programming

🟩 1. Threads

Definition:
A thread is the smallest unit of execution inside a program.
Multiple threads can run in parallel, performing different parts of the same program at the same
time.

Example:

 In a web browser:
o One thread loads a webpage.
o Another thread plays a video.
o Another handles user input.

In shared-memory systems:
All threads share the same memory, so they can access the same variables or data structures.

Benefits:

 Efficient use of CPU resources.

 Faster execution of multi-task programs.
 Lightweight compared to full processes (they share memory, so no need for inter-process
communication).

🟦 2. Pthreads (POSIX Threads)

Definition:
Pthreads stands for POSIX Threads, which is a standard API (Application Programming
Interface) for creating and managing threads in C and C++ programs.

It provides functions to:

 Create threads
 Synchronize threads (using locks or condition variables)
  Control thread execution (start, join, cancel, etc.)

Example (concept):

pthread_create(&thread_id, NULL, function_name, NULL);

This command starts a new thread that runs function_name.

Advantages:

 Gives low-level control over thread behavior.

 Portable and widely supported in operating systems like Linux and UNIX.

Used in:

 Parallel computing applications.

 Real-time systems.
 Scientific computing and simulation.

🟨 3. Locks (Mutexes)

Definition:
A lock (also called a mutex, short for mutual exclusion) is used to protect shared data from
being accessed by multiple threads at the same time.

Why needed:
If two threads try to update the same variable simultaneously, results can be wrong or
unpredictable — this is called a race condition.

How it works:

 When a thread wants to use shared data, it locks it.

 No other thread can access that data until it’s unlocked.

Example (concept):

pthread_mutex_lock(&lock);
// Critical section (shared data)
pthread_mutex_unlock(&lock);

Advantages:

 Prevents data corruption.

 Ensures only one thread accesses shared resources at a time.
Disadvantages:

 If used incorrectly, can cause deadlocks (when two threads wait for each other forever).

🟥 4. Semaphores

Definition:
A semaphore is another synchronization tool used to control access to shared resources.
It uses a counter to keep track of how many threads can access a resource at the same time.

Types of Semaphores:

1. Binary Semaphore (0 or 1): Works like a lock (only one thread at a time).
2. Counting Semaphore: Allows a certain number of threads to access the resource
simultaneously.

Example:
Imagine a system with 3 printers:

 Semaphore value = 3
 Only 3 threads can print at once.
 When one printer becomes free, the semaphore increases again.

How it works (concept):

sem_wait(&sem); // Decrease counter (wait if 0)

... // Use resource
sem_post(&sem); // Increase counter (release)

Advantages:

 Allows limited sharing of resources.

 Prevents overloading a system resource.

Disadvantages:

 More complex than locks.

 Improper use can cause deadlocks or starvation.

🧠 Example: Using Shared Memory with Threads and Locks

Imagine a program that counts numbers:
  4 threads work together to count from 1 to 1,000.
 They all update a shared variable count.

Without a lock:

 Two threads might read the same value (e.g., 50) and both write back 51 → final count
becomes incorrect.

With a lock:

 Each thread waits until the previous one finishes updating the variable → result stays
correct.

🔁 Relationship with Other Topics

Concept Purpose Connection
Threads Perform tasks in parallel Work together using shared memory
Pthreads Library to manage threads Used for creating and controlling threads
Locks Ensure safe access to shared data Prevent race conditions
Semaphores Manage multiple access control Used when limited resources exist

💡 Real-Life Example
Think of a shared whiteboard in a classroom:

 Multiple students (threads) want to write on it.

 The teacher gives only one marker (lock) to one student at a time.
 Or, if there are 3 markers (semaphore = 3), then up to 3 students can write at once.
This ensures no one overwrites someone else’s work — that’s shared-memory control in
action.

✅ Summary
Term Meaning Purpose
Shared Memory Common memory area for all threads Easier data sharing
Thread Small unit of execution Run multiple tasks at once
Pthreads Library for thread management Create and synchronize threads
Lock (Mutex) Allows one thread to access data Prevent data corruption
Semaphore Controls how many threads can access Manage limited resources
 data

🌐 Distributed-Memory Programming

🧠 What is Distributed-Memory Programming?

In Distributed-Memory Programming, each processor (or computer) in a system has its own
private memory.
Unlike shared-memory systems, no global memory is shared — meaning one processor cannot
directly access another processor’s memory.

So, if processors need to work together, they must communicate by sending and receiving
messages — this is known as Message Passing.

💡 Real-Life Example

Think of it like a group of people working in separate rooms:

 Each person (processor) has their own notebook (memory).

 To share information, they must send a message or note to others.

This is exactly how distributed-memory systems work!

⚙️Key Features of Distributed-Memory Systems

Feature Description
Memory Each processor has its own private memory.
Communication Done explicitly through messages.
Synchronization Achieved by sending and receiving data at the right time.
Scalability Highly scalable — can add more machines easily.
Failure Isolation If one node fails, others can continue working.

🔹 Message Passing
📘 Definition:
Message Passing is a way for processors to communicate and share data in a distributed-
memory environment by sending and receiving messages.

Each processor:

 Performs its own computation.

 Sends data to other processors when needed.
 Receives data from others when required.

🧩 Basic Operations in Message Passing

Operation Meaning
Send Transmit a message to another processor.
Receive Accept a message from another processor.
Broadcast Send the same message to multiple processors.
Gather Collect data from multiple processors.
Scatter Distribute data among multiple processors.

💻 Example (Concept):

Let’s say we have 4 computers (P1, P2, P3, P4) working together.

 P1 reads the input data.

 P1 sends part of the data to P2, P3, and P4.
 Each processor processes its part.
 All results are sent back to P1 for final combination.

This method ensures all processors work simultaneously and share data through messages.

🧩 MPI (Message Passing Interface)

📘 Definition:

MPI is a standard library for message passing used in distributed-memory systems.

It provides a set of functions for communication between multiple processors.

MPI is the most popular and widely used tool for parallel programming in clusters and
supercomputers.
⚙️Main Features of MPI:

 Portable across many systems (works on Windows, Linux, macOS).

 High performance for communication.
 Supports both point-to-point and group communication.
 Handles synchronization automatically.

💻 Basic MPI Functions

Function Description
MPI_Init() Starts the MPI environment.
MPI_Comm_size() Finds how many processes are running.
MPI_Comm_rank() Finds the ID of each process.
MPI_Send() Sends a message to another process.
MPI_Recv() Receives a message from another process.
MPI_Finalize() Ends the MPI environment.

💡 Simple Example (Conceptual)

Suppose you have 4 computers:

 Each computer calculates the sum of part of a large array.

 Then all computers send their partial sums to one computer (say P0).
 P0 adds them all to get the final total.

This communication is handled by MPI’s MPI_Send and MPI_Recv functions.

🧠 Advantages of MPI

 Works on any distributed-memory system.

 Fast and efficient for large-scale computations.
 Provides fine control over communication.

⚠️Disadvantages

 More complex to program compared to shared-memory models.

 Programmers must manage all message exchanges manually.
🧩 PVM (Parallel Virtual Machine)
📘 Definition:

PVM stands for Parallel Virtual Machine.

It is a software system that allows a collection of computers (different types and OS) to act like
one big virtual machine.

Each computer (or node) runs a PVM daemon that helps it communicate with others.

⚙️Main Features of PVM:

 Makes a network of computers appear as one virtual computer.

 Supports different operating systems (Windows, Linux, Unix, etc.).
 Handles task distribution, communication, and synchronization automatically.
 Easier to use than MPI, but slightly slower.

💻 How PVM Works:

1. Each computer runs a PVM daemon (background process).

2. These daemons connect all computers into a single virtual machine.
3. Programs send and receive messages using PVM functions like:
o pvm_send() → send data
o pvm_recv() → receive data
o pvm_spawn() → start new tasks

🧠 Advantages of PVM

 Easy to set up and use.

 Supports heterogeneous systems (different hardware).
 Automatic load balancing and fault recovery.

⚠️Disadvantages

 Slower than MPI for high-performance applications.

 Not as widely supported today as MPI.
🔁 MPI vs. PVM Comparison
Feature MPI PVM
Type Standard library Software system
Performance Faster, high performance Slower, more flexible
Ease of Use Complex Easier
Portability Highly portable Supports mixed systems
Communication Explicit, efficient Handled through daemons
Use Case Scientific computing, clusters Academic and heterogeneous systems

✅ Summary
Concept Description
Distributed-Memory Each processor has its own private memory and communicates via
Programming message passing.
Message Passing Technique to exchange data between processors through messages.
MPI (Message Passing Standard high-performance library for distributed programming.
Interface)
PVM (Parallel Virtual Software system that connects many computers into one virtual
Machine) machine.

💡 Real-World Examples

 MPI is used in weather prediction, scientific simulations, and supercomputers.

 PVM is used in university research, heterogeneous systems, and academic projects.

💻 Other Parallel Programming Systems

Besides Shared-Memory (Threads, Pthreads) and Distributed-Memory (MPI, PVM), there are
other systems and models that provide easier and more flexible ways to build parallel
programs.
These systems try to simplify communication, data sharing, and synchronization between
processors.

🧠 1. Distributed Shared Memory (DSM)

📘 Definition:
Distributed Shared Memory (DSM) is a programming model that tries to make a
distributed-memory system act like a shared-memory system.

In DSM:

 Each processor has its own local memory (like in distributed systems).
 But the software provides a virtual shared memory — meaning all processors can
appear to access the same memory space.

It gives programmers the simplicity of shared memory and the scalability of distributed
systems.

💡 How It Works

 DSM software manages communication automatically.

 When one processor needs data from another, the DSM system transfers it in the
background.
 This hides the complexity of message passing from the programmer.

⚙️Advantages

 Easier to program (no manual message passing).

 Works across multiple machines.
 Combines the benefits of shared and distributed memory.

⚠️Disadvantages

 Slightly slower because the system manages memory synchronization.

 Harder to maintain consistency of data copies across all machines.

🧠 Example:

Suppose we have 4 computers with separate memories.

With DSM:

 All can access a shared variable X as if it were in one memory.

 If computer 1 updates X, DSM updates it for others automatically.

Used in:
  Multiprocessor servers
 Cluster systems
 Parallel simulations

🌐 2. Aurora: Scoped Behavior and Abstract Data Types

📘 Definition:

Aurora is an experimental parallel programming system that introduces the idea of scoped
behavior and abstract data types (ADTs) to organize and control parallelism.

It was designed to make parallel programs easier to understand, develop, and maintain.

💡 Key Concepts:

🔹 Scoped Behavior

 Defines which parts of a program can run in parallel and what data they can access.
 Each “scope” has its own set of variables and parallel activities.
 Helps avoid conflicts between parallel tasks.

🔹 Abstract Data Types (ADTs)

 These are data structures that bundle data and operations together (like objects).
 Aurora uses ADTs to manage parallel tasks safely by limiting how different parts of
the program access data.

⚙️Advantages of Aurora

 Better control over parallel execution.

 Helps avoid synchronization problems.
 Makes parallel programs more modular and reusable.

🧠 Example (Conceptual):

Imagine a banking system:

  Each account can be an abstract data type.
 Multiple threads can process transactions in parallel, but only the owner scope can
modify the balance — this prevents data corruption.

🏢 3. Enterprise: Process Templates

📘 Definition:

Enterprise is another parallel programming environment that uses the concept of process
templates.

A process template defines a pattern or blueprint for creating multiple processes that do
similar work.

💡 Key Idea:

Instead of writing the same process multiple times, a template is written once and instantiated
(copied) as many times as needed.

⚙️How It Works:

 The programmer defines a template for a process (like a worker function).

 The system creates many copies of that template, each working on a different part of the
data.
 This supports massive parallelism efficiently.

🧩 Advantages:

 Reduces programming effort.

 Easy to scale — just increase the number of template instances.
 Ideal for data-parallel applications (same operation repeated on large data).

🧠 Example:
In a weather simulation:

 A process template defines how to calculate temperature for one grid cell.
 The system creates hundreds of processes, each working on a different region of the
world.

🔬 4. Research Topics in Parallel and Distributed Systems

Here are some interesting areas of research and project ideas related to parallel computing:

Area Description / Example Topics

Performance Optimization Improving communication speed in distributed systems.
Load Balancing Developing smarter algorithms to evenly distribute work among
processors.
Fault Tolerance Ensuring systems continue working even when some processors fail.
Energy Efficiency Designing parallel systems that consume less power.
Big Data Processing Using parallel systems to analyze large datasets faster (e.g., Hadoop,
Spark).
Cloud and Edge Computing Managing distributed resources efficiently over the internet.
Machine Learning Speeding up AI model training using GPUs or clusters.
Parallelization
Parallel Algorithms Creating new algorithms for sorting, searching, and matrix operations.
Synchronization Models Researching new ways to coordinate concurrent processes safely.
Hybrid Systems Combining shared-memory and distributed-memory approaches (e.g.,
MPI + OpenMP).

✅ Summary
System Key Idea Advantages Example Use
DSM (Distributed Combines shared & Easier programming, Cluster computing
Shared Memory) distributed models scalable
Aurora Scoped behavior & ADTs Safe, structured Research systems
parallelism
Enterprise Process templates Simple large-scale Simulations, data
 parallelism processing
Research Topics Emerging areas in parallel Innovation & Academic & industrial
computing optimization research