Parallel Computing System

A parallel computing system is a system where multiple processors execute different

parts of the same problem simultaneously to reduce execution time and improve
performance.
Distributed Computing System
A distributed computing system is a system where multiple independent computers
connected through a network work together to achieve a common goal, sharing resources
and communicating through messages.
Need
Parallel and distributed systems are required because:
1. High computational demand – Applications like weather forecasting, AI,
simulations need huge processing power.
2. Big data processing – Large databases and real-time analytics require multiple
processors.
3. Reduced execution time – Faster results for time-critical applications.
4. Resource sharing – Distributed systems allow sharing of hardware and software
resources.
5. Scalability requirements – Systems must grow with increasing workload.
(Concepts based on Handbook on Parallel and Distributed Processing)
Benefits
1. Increased Speed (Speedup) – Tasks execute simultaneously.
2. Improved Throughput – More tasks completed per unit time.
3. Scalability – Add more processors to improve performance.
4. Reliability – Failure of one node doesn’t stop the system.
5. Efficient Resource Utilization
Challenges
1. Synchronization issues
2. Communication overhead
3. Load balancing
4. Deadlocks
5. Fault tolerance complexity
6. Programming complexity

Different Parallel Models

A parallel model is an abstract way to represent how processors and memory are organized
in a parallel system.
1️PRAM (Parallel Random Access Machine)
 Shared memory model.
 All processors access common memory.
 Variants: EREW, CREW, CRCW.
2️SIMD (Single Instruction Multiple Data)
 Same instruction executed on multiple data simultaneously.
 Used in image processing and graphics.
3️MIMD (Multiple Instruction Multiple Data)
 Different processors execute different instructions on different data.
 Used in distributed systems and databases.
4️ Message Passing Model
 Each processor has its own memory.
 Communication through send/receive messages (like MPI).
Different Parallel Algorithms
A parallel algorithm divides a problem into smaller tasks that run simultaneously.
1️Parallel Sorting
 Example: Bitonic sort, Parallel merge sort.
 Divides data among processors and sorts simultaneously.
2️Parallel Matrix Multiplication
 Matrices divided into blocks and computed in parallel.
3️Parallel Search
 Data divided among processors to search faster.
4️Reduction Algorithms
 Used for sum, max, min (tree-based approach).

Architecture of Parallel Systems

A parallel system architecture consists of multiple processors connected together to solve a
single problem simultaneously.
Main Components:
 1. Processors (CPUs) – Execute instructions.
2. Memory – Stores data and programs.
3. Interconnection Network – Connects processors.
4. I/O System – Handles input and output operations.
Types of Parallel Architectures:
1️Shared Memory Architecture
 All processors share a common memory.
 Communication through shared variables.
2️Distributed Memory Architecture
 Each processor has its own local memory.
 Communication through message passing.
3️Hybrid Architecture
 Combination of shared and distributed memory.
Architecture of Distributed Systems
A distributed system architecture consists of multiple independent computers (nodes)
connected through a network.
Main Components:
1. Multiple Nodes (Computers)
2. Local Memory in each node
3. Communication Network (LAN/WAN)
4. Middleware/Distributed OS
Characteristics:
 Loosely coupled systems
 Communication via messages
 Resource sharing
 Fault tolerance

Comparison of SISD, SIMD, MISD, and MIMD Architectures

These architectures are classified under Flynn’s Taxonomy, proposed by Michael J. Flynn.
Flynn classified computer architectures based on:
 Number of instruction streams
 Number of data streams
Comparison Table
Instruction Data
Architecture Description Example Use
Stream Stream
One processor executes one
Traditional single-
SISD Single Single instruction on one data item at a
core computers
time
Same instruction executed on Image processing,
SIMD Single Multiple
multiple data simultaneously graphics
Multiple instructions operate on Rare, fault-tolerant
MISD Multiple Single
the same data systems
Multiple processors execute
Distributed
MIMD Multiple Multiple different instructions on different
systems, databases
data
Detailed Explanation & Suitability
1️SISD (Single Instruction Single Data) 4️MIMD (Multiple Instruction Multiple Data)
 Sequential execution. Independent processors.
 Only one CPU. Different tasks on different data.
 No parallelism Most flexible [Link] one CPU..
Suitable For: Suitable For:
 Simple applications Distributed computing
 Small program Parallel databases
 Office applications AI & Machine Learning
Not suitable for high-performance computing. Cloud computing
Best for complex and large-scale applications.
2️SIMD (Single Instruction Multiple Data)
 One control unit.
 Multiple processing elements.
 Same operation on large data sets.
Suitable For:
 Image processing
 Video rendering
 Scientific computations
 Matrix operations
Best for data-parallel problems where same task repeats on large datasets.
3️MISD (Multiple Instruction Single Data)
 Different instructions process the same data.
 Rarely used in practice.
Suitable For:
 Fault-tolerant systems
 Safety-critical systems (like aerospace)
Limited commercial use.
Programming Environments for Parallel and Distributed Systems
A programming environment provides tools, libraries, and frameworks to develop and
execute programs on parallel and distributed systems.
1️MPI (Message Passing Interface)
 Standard library for distributed memory systems.
 Processes communicate using send and receive messages.
  Highly scalable.
 Used in scientific and cluster computing.
Best for large distributed systems.
2️OpenMP (Open Multi-Processing)
 Used for shared memory systems.
 Uses compiler directives (pragmas).
 Easy to implement parallelism in C/C++/Fortran.
Suitable for multi-core processors.
3️PVM (Parallel Virtual Machine)
 Converts a group of computers into a virtual parallel machine.
 Supports heterogeneous systems.
 Message-passing based.
4️Threads (POSIX Threads / Multithreading)
 Lightweight processes.
 Share common memory.
 Used in shared memory parallel systems.
5️CUDA (Compute Unified Device Architecture)
 Developed by NVIDIA.
 Used for GPU-based parallel programming.
 Ideal for data-intensive computations.
6️Distributed Frameworks
 Hadoop
 Spark
 Remote Procedure Call (RPC) systems
Used for large-scale distributed data processing.

Parallel Database Systems

A parallel database system is a database system that uses multiple processors and storage
devices to execute database operations simultaneously, improving performance and
scalability.
Architecture of Parallel Database Systems
Parallel database architecture is mainly classified into three types:
1️Shared Memory Architecture
 Multiple processors share a common memory and disk.
 Communication through shared memory.
  Suitable for small-scale systems.
Advantages:
 Easy to manage.
 Fast communication.
Limitation:
 Limited scalability.
2️Shared Disk Architecture
 Each processor has private memory.
 All processors share a common disk.
 Requires synchronization mechanisms.
Advantages:
 High availability.
 Easier data sharing.
Limitation:
 Disk contention problem.
3️Shared Nothing Architecture
 Each processor has its own memory and disk.
 Communication through message passing.
 Most scalable architecture.
Advantages:
 High scalability.
 Better performance for large databases.
Limitation:
 Complex data partitioning.
Working of Parallel Database Systems
Parallel databases improve performance using the following techniques:
1. Data Partitioning
Data is divided across multiple nodes using:
 Range partitioning
 Hash partitioning
 Round-robin partitioning
2. Parallel Query Processing
Steps:
1. Query parsing
2. Query optimization
3. Execution plan generation
4. Parallel execution on multiple processors
5. Result merging
Operations like selection, projection, join, aggregation are executed simultaneously.
3. Transaction Management
To maintain ACID properties:
Concurrency control (locking protocols) Design of a Parallel Sorting
Algorithm
Let us design a Parallel Merge Sort algorithm.
Idea
 Divide the array into P equal parts.
 Each processor sorts its part simultaneously.
 Merge the sorted parts in parallel.
Algorithm: Parallel Merge Sort
Step 1: Partition
Divide an array of size N into P subarrays, each of size N/P.
Step 2: Local Sorting
Each processor independently sorts its assigned subarray using a sequential sorting algorithm
(like merge sort or quicksort).
Step 3: Parallel Merging
Sorted subarrays are merged in pairs simultaneously.
 First level: P → P/2 merges
 Second level: P/2 → P/4 merges
 Continue until one final sorted array remains
Pseudo Logic
Input: Array A of size N
Processors: P

1. Divide A into P parts

2. In parallel:
Each processor sorts its N/P elements
3. Perform log P merging steps in parallel
4. Output final sorted array
Time Complexity Analysis
1️Local Sorting Time
Each processor sorts N/P elements:
T1=O(NPlog⁡NP)T₁ = O\left(\frac{N}{P} \log \frac{N}{P}\right)T1=O(PNlogPN)
2️Merging Time
Parallel merging requires:
O(log⁡P)O(\log P)O(logP)
levels of merging.
Total Time Complexity
T(N)=O(NPlog⁡NP+log⁡P)T(N) = O\left(\frac{N}{P} \log \frac{N}{P} + \log P \right)T(N)=O(PN
logPN+logP)
Speedup
Sequential merge sort takes:
O(Nlog⁡N)O(N \log N)O(NlogN)
Ideal speedup:
Speedup≈PSpeedup ≈ PSpeedup≈P
(when communication overhead is minimal)

UMA (Uniform Memory Access)

Definition
In UMA architecture, all processors share a common main memory, and memory access
time is the same for every processor.
Diagram
CPU1 CPU2 CPU3 CPU4
| | | |
-----------------------
Shared Memory
Characteristics
 Single shared memory.
 Equal access time for all processors.
 Also called SMP (Symmetric Multiprocessing).
 Easy to program.
Advantages
 Simple design.
 Fast communication between processors.
Disadvantages
 Memory bottleneck.
 Limited scalability.
2️NUMA (Non-Uniform Memory Access)
Definition
In NUMA architecture, each processor has local memory, but processors can access other
processors’ memory.
Access time depends on memory location (local = fast, remote = slow).
Diagram
CPU1 ---- Local Memory1
\
\____ Interconnection Network ____/
/
CPU2 ---- Local Memory2
Characteristics
 Physically distributed memory.
 Logically shared.
 Faster local access, slower remote access.
Advantages
 Better scalability than UMA.
 Reduced memory contention.
Disadvantages
 Complex memory management.
 Variable access time.
3️Distributed Memory Architecture
Definition
In distributed memory architecture, each processor has its own private memory, and
processors communicate through message passing over a network.
Diagram
CPU1 + Memory1 <---> CPU2 + Memory2 <---> CPU3 + Memory3
(Message Passing via Network)
Characteristics
 No shared memory.
 Communication via messages.
 Loosely coupled systems.
Advantages
 Highly scalable.
 Suitable for large systems and clusters.
Disadvantages
 Programming complexity.
 Communication overhead.
Comparison Summary
 Feature UMA NUMA Distributed
Memory Access Time Uniform Non-uniform Private memory
Scalability Low Medium High
Communication Shared memory Shared (variable speed) Message passing
Complexity Simple Moderate Complex
Shared Memory vs Message Passing Model
Parallel systems mainly use two programming models:
 Shared Memory Model
 Message Passing Model
Shared Memory Model
Definition
All processors access a common shared memory.
Communication happens through shared variables.
Working
 Processors read/write to the same memory.
 Synchronization using locks, semaphores, etc.
Advantages
 Easy to program.
 Faster communication (no explicit message transfer).
 Suitable for multi-core systems.
Limitations
 Limited scalability.
 Memory contention problem.
 Difficult synchronization (race conditions).
Message Passing Model
Definition
Each processor has its own private memory.
Processors communicate by sending and receiving messages.
Working
 Data is explicitly sent between processors.
 Uses functions like send() and receive() (e.g., MPI).
Advantages
 Highly scalable.
 No shared memory conflicts.
 Suitable for distributed systems.
Limitations
 Programming complexity is higher.
 Communication overhead.
 Slower compared to shared memory for small systems.

Query Processing and Transaction Management in Parallel

Databases
A parallel database system improves performance by executing queries and transactions
simultaneously on multiple processors.
1️Query Processing in Parallel Databases
Query processing means executing a user query efficiently using parallelism.
Steps in Parallel Query Processing
1️Query Parsing
  SQL query is checked for syntax and converted into internal form.
2️Query Optimization
 System selects the best execution plan.
 Decides how to divide the query across processors.
3️Data Partitioning
 Data is divided using:
o Range partitioning
o Hash partitioning
o Round-robin partitioning
4️Parallel Execution
 Operations like selection, projection, join, aggregation are executed simultaneously
on different nodes.
5️Result Merging
 Partial results from all processors are combined to produce final output.
Benefits
 Faster query execution
 Improved throughput
 Efficient handling of large datasets
2️Transaction Management in Parallel Databases
Transaction management ensures database correctness while multiple users access data
simultaneously.
It maintains ACID properties:
 Atomicity
 Consistency
 Isolation
 Durabili
Key Mechanisms
1️Concurrency Control
 Uses locking protocols (Two-Phase Locking).
 Prevents data conflicts.
2️Two-Phase Commit (2PC)
 Ensures all nodes either commit or abort a transaction together.
3️Deadlock Detection
 Identifies and resolves deadlocks.
4️Recovery Mechanisms
 Logging and checkpointing used for crash recovery.