Introduction to Parallel
Algorithms
A parallel algorithm executes multiple instructions simultaneously
across different processing devices, combining individual outputs
to produce a final result.
Parallel Algorithm Models
Data-Parallel Model Task Graph Model
Every process performs the same operation on different Computations are represented as a graph; tasks run in
data subsets, ideal for large, independent datasets. parallel if dependencies are met.
Work Pool Model Pipeline Model
Idle processors dynamically request tasks from a shared Data streams through sequential processes, each
pool, balancing load for varied task sizes. performing a specific task as data arrives.
Data-Parallel Model: Image Recoloring
Description
Recoloring an image or rendering 3D graphics can be
divided, with each pixel's color computed independently.
Parallel Approach
Processors are assigned different pixel blocks, applying
the same coloring function simultaneously with minimal
communication.
Benefit
Simple and fast when tasks are identical.
Task Graph Model: Parallel Quicksort
Description
Uses divide-and-conquer to split sorting problems
into smaller lists.
Parallel Approach
Sub-lists are sorted in parallel on different processors,
followed by a final merging step.
Benefit
Fits problems with clear steps and dependencies.
Work Pool Model: Parallel Tree Search
Description
Exploring a large search tree for a specific solution
node, common in AI or optimization.
Parallel Approach
A master process creates a root task; child nodes are
added to a shared work pool. Available "slave"
processors explore sub-trees.
Benefit
Dynamically distributes workload, useful when different
branches require varied computation times.
Pipeline Model: LU Factorization
Description
A mathematical method to solve linear equations,
broken into sequential steps.
Parallel Approach
A producer processor generates tasks from an input
matrix, passing them to a chain of consumer
processors for factorization.
Benefit
Overlapping computation and communication speeds
up the process, similar to a physical assembly line.
Parallel Random
Access Machines
(PRAM)
PRAM is an abstract model for parallel algorithms, featuring
multiple processors attached to a single shared memory unit.
To manage simultaneous memory access, PRAM defines constraints:
• Exclusive Read Exclusive Write (EREW)
• Exclusive Read Concurrent Write (ERCW)
• Concurrent Read Exclusive Write (CREW)
• Concurrent Read Concurrent Write (CRCW)
Here, n number of processors can perform independent operations on n number of data in a particular unit of time.
This may result in simultaneous access of same memory location by different processors.
To solve this problem, the following constraints have been enforced on PRAM model −
• Exclusive Read Exclusive Write (EREW) − Here no two
processors are allowed to read from or write to the same
memory location at the same time.
• Exclusive Read Concurrent Write (ERCW) − Here no two
processors are allowed to read from the same memory
location at the same time, but are allowed to write to the same
memory location at the same time.
• Concurrent Read Exclusive Write (CREW) − Here all the
processors are allowed to read from the same memory
location at the same time, but are not allowed to write to the
same memory location at the same time.
• Concurrent Read Concurrent Write (CRCW) − All the processors
are allowed to read from or write to the same memory location
at the same time.
Data Structures for Parallel Algorithms
Selecting the right data structure is crucial for efficient parallel algorithm performance, as operations can vary
greatly in time complexity.
Linked List Arrays Hypercube Network
Flexible for dynamic data, but Provide constant-time access to A topology for interconnected
sequential access can be slow for elements, making them efficient for processors, optimizing
parallel operations. parallel processing. communication in parallel systems.
Parallel Algorithm Design Techniques
Choosing the right design technique is vital, as many parallel programming problems have multiple solutions.
Divide and Conquer Greedy Method
Dynamic Programming Backtracking
Why Parallel Algorithms?
1 2 3
Multi-core CPUs & GPUs High-Performance Large Datasets
Modern devices leverage
Computing Crucial for faster processing of
parallel algorithms for efficient Essential for massive big data volumes.
use of many cores. computing needs like weather
forecasting simulations.
4 5
Real-time Systems Sequential Limitations
Enables instant decision-making in applications like Overcomes the speed limits of single CPU cores.
self-driving cars.
Key Challenges in Parallel Algorithms
• Communication Overhead
• Data Dependencies
• Synchronization Issues
• Scalability Limitations