Parallel Algorithms

Course Code: 0613-413

 Overview
▪ Define parallel algorithms and explain how they differ
from sequential algorithms.
▪ Identify real-world scenarios that require parallel
computing.
▪ Classify computers using Flynn's Taxonomy (SISD,
SIMD, MISD, MIMD).
▪ Explain the challenges of designing parallel algorithms
(data dependency, communication overhead).
 What is an Algorithm?
Everyday Analogy Formal Definition
An algorithm is a finite sequence of
A recipe is an algorithm! well-defined instructions that:
Step 1: Gather ingredients Takes inputs from the user
Step 2: Boil water Performs computation step by step
Step 3: Add noodles Produces an expected output
Step 4: Serve hot
The architecture of the computer
Each step takes an input and produces an determines which type of algorithm is most
output. Follow the steps in order → get the suitable.
desired result.
 Sequential vs Parallel Algorithms
Depending on the architecture of computers, we have two types of algorithms −

Sequential Algorithm Parallel Algorithm

Problem split into sub-problems
Steps executed one after Multiple processors work
another. simultaneously
Single processor runs the Results combined into final
whole task. output
Simple to design and debug. Much faster for large-scale tasks
Slower for very large problems.
Example:
Example: 10 friends each washing 1 shirt at
Washing 10 shirts alone — wash the same time — done in 1/10 of
one, hang it, then wash the next. the time!
 Why Do We Need Parallel Computing?
In today's digital world, huge amounts of data are generated every second. A single
processor often cannot process this data quickly enough. Parallel computing solves
this problem by using multiple processors to work on different parts of a task at the
same time.
▪ Parallel computing is used because it makes processing faster by dividing a large
task into smaller parts and running them at the same time, which saves time
(reduces wall clock time).
▪ It can also reduce cost by using many smaller processors instead of a single
powerful one. It helps overcome memory limitations by distributing data across
multiple processors.
▪ Overall, parallel computing is important because it improves performance and is
considered the future of modern computing systems.
 Why Do We Need Parallel Computing?
Examples of Where Parallel Computing Is Needed
▪ Large Databases: Search and process billions of records quickly. Example:
Google searching through billions of web pages.
▪ Aircraft Testing: Simulate flight conditions and analyze aircraft performance.
Example: Testing aircraft designs before building real prototypes.
▪ Astronomy: Process large amounts of telescope and space data. Example:
Analyzing images from space telescopes.
▪ Biomedical Analysis: Analyze DNA sequences and support drug discovery.
Example: Identifying genes related to diseases.
▪ Weather Forecasting: Run thousands of weather and climate simulations.
Example: Predicting storms and rainfall accurately.
▪ Web Services: Handle millions of users and requests simultaneously. Example:
Facebook, YouTube, and Amazon serving millions of users at once.
 What is Parallelism?
▪ Parallelism is the process of processing several set of instructions
simultaneously.
▪ It reduces the total computational time. Parallelism can be implemented by using
parallel computers, i.e. a computer with many processors.
▪ Parallel computers require parallel algorithm, programming languages, compilers
and operating system that support multitasking.
 Different types of Parallelism
Data Parallelism: Data parallelism involves executing the same task concurrently
on different subsets of the same dataset across multiple computing cores. Each
core performs identical operations on its assigned portion of data.
▪ Example − Array Summation: Consider summing an array of size N:

▪ Single-core: One thread sums

elements [0] ... [N-1]
▪ Dual-core: Thread A sums [0] ...
[N/2-1], Thread B sums [N/2] ...
[N-1]
▪ Both threads perform the same
operation (addition) on different
data subsets
 Different types of Parallelism
Task Parallelism: Task parallelism involves executing different tasks concurrently
on multiple computing cores. Each core performs distinct operations, potentially on
the same or different datasets.
• Example − Statistical Operations

▪ Each thread performs a unique

statistical operation on the array
▪ Threads execute different
algorithms simultaneously
▪ Operations are independent and
can run concurrently
Different types of Parallelism
 Challenges in Parallel Algorithm Design
Data Dependency: Sub-problems often depend on each other's results. A
processor may need data that another processor hasn't finished computing yet
— it must wait, reducing the benefit of parallelism. Example: Computing the
average score in a class — you need ALL scores before calculating the average.
You can't split this without coordination.
Communication Overhead: Processors must exchange data with each other
during computation. Research shows that the time spent communicating
between processors often exceeds the actual processing time — making good
CPU utilization critical. Example: Like 10 workers building a house but constantly
texting each other for updates instead of working — the messaging slows
everyone down.
Model of Computation: Flynn’s Classical Taxonomy
A computer works by following a set of instructions called an algorithm.
These instructions tell the computer what to do step by step using data.
Based on how instructions and data are handled, computers are divided into
four types:
Single Instruction stream, Single Data stream (SISD) computers
Single Instruction stream, Multiple Data stream (SIMD) computers
Multiple Instruction stream, Single Data stream (MISD) computers
Multiple Instruction stream, Multiple Data stream (MIMD) computers
 Flynn’s Classical Taxonomy: SISD

▪ A SISD (Single Instruction, Single Data) computer consists of one control unit, one processing
unit, and one memory unit.
▪ In this type of computer, the processor receives a single stream of instructions from the control
unit and operates on a single stream of data coming from the memory unit.
▪ During execution, the processor fetches one instruction at a time and processes one data item at
each step. After completing one operation, it moves on to the next instruction and the next data.
▪ This makes SISD a simple and sequential processing system where only one operation is
performed at a time.
▪ Your old single-core desktop PC — doing one thing at a time.
Flynn’s Classical Taxonomy: SIMD
 Flynn’s Classical Taxonomy: SIMD
▪ A SIMD (Single Instruction, Multiple Data) computer consists of one control unit,
multiple processing units, and a shared memory or an interconnection network.
▪ In this type of system, a single control unit sends the same instruction to all
processing units at the same time. Each processor then performs that instruction on
different data items taken from the memory.
▪ Although all processors receive the same instruction, they work on different pieces
of data simultaneously, which makes the system faster for large-scale data
processing.
▪ Each processing unit may also have its own local memory to store data and
instructions.
▪ Communication between processors takes place through shared memory or an
interconnection network. In SIMD, some processors may be active while others
wait, depending on the instruction given by the control unit.
▪ GPU (Graphics Card): Apply the same color filter to millions of pixels simultaneously
Flynn’s Classical Taxonomy: MISD
 Flynn’s Classical Taxonomy: MISD
▪ A MISD (Multiple Instruction, Single Data) computer has multiple control units,
multiple processing units, and one shared memory.
▪ In this system, each processor has its own control unit and receives different
instructions.
▪ However, all processors work on the same single data from the shared memory.
Each processor processes the data at the same time based on its own instructions.
▪ This type of system is very rare in real-life applications.
▪ Real example: Space Shuttle's flight control system — multiple computers
cross-check computations on the same sensor data for reliability.
Flynn’s Classical Taxonomy: MIMD
 Flynn’s Classical Taxonomy: MIMD
▪ A MIMD (Multiple Instruction, Multiple Data) computer has multiple control units,
multiple processors, and a shared memory or interconnection network.
▪ In this system, each processor has its own control unit, local memory, and ALU.
Each processor receives different instructions and works on different data at the
same time.
In MIMD (Multiple Instruction, Multiple Data) systems, many processors work
independently on different instructions and different data at the same time.
▪ If all processors share the same memory, it is called a multiprocessor system.
• If processors are connected through a network instead of shared memory, it is
called a multicomputer system.
Multicomputers are of two types:
• Multicomputer system: processors are close together (same place).
• Distributed system: processors are far apart (different cities or locations).
 Flynn's Taxonomy — Quick Comparison
Type Instruction Data Processors Real Example Commo
Streams Streams n?

SISD Single Single One Old desktop PC Commo

n

SIMD Single Multiple Many GPU / Graphics Card Very

Commo
n
MISD Multiple Single Many Space Shuttle FCS Rare

MIMD Multiple Multiple Many Modern servers, Most

(independent) clusters Commo
n
 Parallel Computing in Weather Forecasting
Problem: Predicting tomorrow's weather requires solving millions of atmospheric
equations across the entire globe — impossible for a single processor in useful time.

1 2 3 4

Assign to Exchange
Divide the Globe Combine Results
Processors Boundary Data
Each processor Adjacent
Earth's atmosphere
handles a section processors share All results are
is divided into a 3D
of the grid — data at borders merged to produce
grid of thousands of
working (communication the final global
cells
simultaneously overhead weather forecast
(sub-problems)
(parallelism!) challenge)

Result: A forecast that would take a single computer 10 years runs in 30 minutes on a parallel
supercomputer!
 Summary
▪ An algorithm is a sequence of steps that takes inputs and produces outputs.
▪ Parallelism = executing multiple instructions simultaneously to save time.
▪ Parallel algorithms face challenges: data dependency and communication overhead
▪ Flynn’s Taxonomy classifies computers: SISD → SIMD → MISD → MIMD
▪ MIMD computers are either Multiprocessors (shared memory) or Multicomputers
(network)
 References
▪ TutorialsPoint
▪ Kumar, V. et al. (2003). Introduction to Parallel Computing. Addison-Wesley.