1.

Parallel Program Design One core handles input while another

Parallel program design is the process of handles computation.
developing a program in which multiple Neat Diagram – Partitioning
tasks are executed simultaneously using Plain text
multiple processors or cores to improve Large Problem
performance, speed, and resource utilization. |
It divides a large computational problem --------------------------------
into smaller sub-problems that can run | | |
concurrently. Task 1 Task 2 Task 3
In multicore systems, parallel | | |
programming helps in: Processor 1 Processor 2 Processor 3
Reducing execution time 3. Communication
Increasing throughput Processors exchange information during
Efficient CPU utilization execution.
Solving large-scale scientific and Communication Methods
engineering problems Shared Memory
Steps in Parallel Program Design Message Passing
The design of a parallel program Shared Memory Model
generally involves the following stages: All processors access common memory.
1. Problem Identification Plain text
The problem must be analyzed to determine ---------------------
whether it can be solved using parallelism. | Shared Memory |
Characteristics of Parallelizable Problems ---------------------
Large computation / | \
Independent tasks CPU1 CPU2 CPU3
Repetitive operations Message Passing Model
Huge datasets Processors communicate through messages.
Examples Plain text
Matrix multiplication CPU1 <----> CPU2 <----> CPU3
Weather forecasting 4. Synchronization
Image processing Synchronization ensures correct execution
AI and Machine Learning order among parallel tasks.
2. Partitioning (Decomposition) Need for Synchronization
The main problem is divided into smaller Avoid data inconsistency
tasks or subtasks. Prevent race conditions
Types of Partitioning Coordinate shared resource access
a) Data Partitioning Synchronization Techniques
Large data is divided among processors. Locks
Example: Semaphores
Splitting an array into parts for parallel sum Barriers
calculation. Mutex
b) Functional Partitioning 5. Mapping (Task Scheduling)
Different functions are assigned to different Tasks are assigned to processors efficiently.
processors. Objectives
Example: Load balancing
Minimum idle time
Better processor utilization Find the sum of elements in a large array
Types using multiple processors.
Static Scheduling Sequential Approach
Dynamic Scheduling One processor adds all elements one by one.
6. Parallel Algorithm Design Plain text
Efficient algorithms are developed for Sum = A1 + A2 + A3 + ... + An
concurrent execution. Parallel Approach
Important Factors The array is divided into parts and assigned
Scalability to multiple processors.
Speedup Neat Diagram – Parallel Array Sum
Efficiency Plain text
Communication overhead Array:
Flowchart of Parallel Program Design ------------------------------------------------
Plain text | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
START ------------------------------------------------
|
v Processor Allocation:
Identify the Problem
| P1 -> 1 + 2 + 3
v P2 -> 4 + 5 + 6
Analyze Parallelism P3 -> 7 + 8
| P4 -> 9 + 10
v
Partition the Task Partial Sums:
| P1 = 6
v P2 = 15
Assign Tasks to Processors P3 = 15
| P4 = 19
v
Establish Communication Final Sum:
| 6 + 15 + 15 + 19 = 55
v Algorithm for Parallel Sum
Synchronization Plain text
| Step 1: Divide array into equal parts
v Step 2: Assign each part to processors
Execute Parallel Tasks Step 3: Each processor computes partial sum
| Step 4: Combine all partial sums
v Step 5: Display final result
Collect Results Advantages of Parallel Program Design
| Faster execution
v Better performance
STOP Efficient resource utilization
Example of Parallel Program Design Handles large problems
Example: Parallel Sum of Array Reduced processing time
Problem Statement Increased scalability
Disadvantages
Complex programming In simple words, every process waits
Synchronization overhead forever, and none of them can proceed.
Communication cost Real-Life Example of Deadlock
Debugging difficulty Consider two people crossing a narrow
Load balancing issues bridge from opposite sides.
Applications of Parallel Programming  Person A waits for Person B to
Artificial Intelligence move.
Scientific Computing  Person B waits for Person A to
Weather Prediction move.
Big Data Analytics  Neither moves.
Image and Video Processing This situation is called a deadlock.
Cryptography Diagram of Deadlock
Machine Learning Resource R1 Resource R2
Performance Metrics | |
v v
+---------+ +---------+
2. Explain in detailed manner about dead | Process | | Process |
lock and live lock with suitable examples | P1 | | P2 |
Introduction +---------+ +---------+
In operating systems and concurrent ^ ^
programming, multiple processes or threads | |
often compete for limited resources such as Waiting for R2 Waiting for R1
CPU time, memory, files, printers, and Explanation:
databases. Improper coordination among  Process P1 holds Resource R1 and
these processes may lead to serious waits for Resource R2.
problems like Deadlock and Livelock. Both  Process P2 holds Resource R2 and
situations prevent processes from waits for Resource R1.
completing their tasks efficiently, but their  Neither process can continue.
behavior is different. Necessary Conditions for Deadlock
 Deadlock occurs when two or more Deadlock occurs only when the following
processes wait indefinitely for four conditions exist simultaneously. These
resources held by each other. are called Coffman Conditions.
 Live lock occurs when processes 1. Mutual Exclusion
continuously change their states in At least one resource must be non-shareable.
response to each other without Only one process can use the resource at a
making any actual progress. time.
These problems reduce system performance, Example
waste CPU resources, and may cause the A printer can print for only one process at a
system to become unresponsive. time.
Deadlock 2. Hold and Wait
Definition of Deadlock A process holds one resource and waits for
A deadlock is a condition in which a set of another resource.
processes are blocked because each process Example
is holding a resource and waiting for another A process holding a printer waits for a
resource that is already held by another scanner.
process in the set.
3. No Preemption +---------------+
Resources cannot be forcibly removed from Example of Deadlock in Computer
a process. System
The process must release the resource Assume there are two processes and two
voluntarily. resources.
Example Holding Waiting
Process
An operating system cannot take away a Resource Resource
printer from a process in the middle of P1 Printer Scanner
printing. P2 Scanner Printer
4. Circular Wait Working
A circular chain of processes exists where 1. Process P1 acquires the printer.
each process waits for a resource held by the 2. Process P2 acquires the scanner.
next process. 3. P1 requests the scanner.
Example 4. P2 requests the printer.
P1 waits for P2, P2 waits for P3, and P3 5. Both processes wait forever.
waits for P1. Hence, a deadlock occurs.
Flowchart of Deadlock Occurrence Resource Allocation Graph
+------------------+ A Resource Allocation Graph (RAG) is used
| Process Requests | to represent deadlock situations.
| Resource | P1 -----> R2
+---------+--------+ ^ |
| | v
v R1 <----- P2
+------------------+ Where:
| Resource Already |  Circle represents Process.
| Allocated? |  Square represents Resource.
+----+--------+----+  Arrow from process to resource
| | means request.
Yes No  Arrow from resource to process
| | means allocation.
v v A cycle in the graph indicates the possibility
+----------------+ +----------------+ of deadlock.
| Process Waits | | Resource Given | Methods for Handling Deadlock
+--------+-------+ +----------------+ There are four major methods to handle
| deadlock.
v 1. Deadlock Prevention
+----------------------+ In this method, the system prevents at least
| Circular Waiting | one of the four necessary conditions.
| Among Processes? | Techniques
+---------+------------+  Eliminate mutual exclusion where
| possible.
Yes  Avoid hold and wait.
|  Allow preemption of resources.
v  Prevent circular wait.
+---------------+ Advantage
| DEADLOCK |  Simple approach.
Disadvantage Livelock
 Low resource utilization. Definition of Livelock
2. Deadlock Avoidance A livelock is a condition in which processes
The operating system carefully allocates continuously change their states in response
resources to avoid unsafe states. to each other, but no useful work is
Example Algorithm performed.
 Banker’s Algorithm. Unlike deadlock, processes are not blocked.
Safe State They remain active but fail to make
A system is safe if all processes can progress.
complete execution without deadlock. Real-Life Example of Livelock
Advantage Imagine two people trying to pass each other
 Better resource utilization. in a narrow corridor.
Disadvantage  Both move left.
 Requires advance information about  Both move right.
resource needs.  They continue moving repeatedly.
3. Deadlock Detection and Recovery  Neither person crosses the corridor.
The system allows deadlock to occur and This is a livelock situation.
then detects and recovers from it. Diagram of Livelock
Detection Process P1 Process P2
 Use wait-for graphs. | |
 Check for cycles. v v
Recovery Methods Move Left <-----> Move Left
 Terminate one or more processes. | |
 Preempt resources. v v
Advantage Move Right <-----> Move Right
 Efficient resource usage. | |
Disadvantage +--------Repeat-------+
 Recovery is expensive. Explanation:
4. Ignore Deadlock  Both processes remain active.
This approach is called the Ostrich  They continuously react to each
Algorithm. other.
The operating system ignores deadlock  No process completes execution.
because it occurs rarely. Flowchart of Livelock
Example +----------------------+
UNIX and Windows systems often use this | Process Tries Access |
method. +----------+-----------+
Advantages of Deadlock Handling |
1. Improves system reliability. v
2. Prevents indefinite waiting. +----------------------+
3. Enhances system efficiency. | Resource Busy? |
4. Reduces resource wastage. +-----+-----------+----+
Disadvantages of Deadlock | |
1. System performance decreases. Yes No
2. Processes remain blocked forever. | |
3. Resource utilization becomes poor. v v
4. May lead to system crash. +----------------+ +----------------+
 | Release and | | Access Granted | 1. Improves process progress.
| Retry Resource | +----------------+ 2. Reduces unnecessary CPU usage.
+--------+-------+ 3. Enhances system throughput.
| 4. Avoids infinite activity loops.
v Disadvantages of Livelock
+----------------------+ 1. CPU time gets wasted.
| Another Process Also | 2. Processes never complete.
| Retries Simultaneously| 3. System efficiency decreases.
+----------+-----------+ 4. Increased response time.
| Difference Between Deadlock and
Yes Livelock
| Feature Deadlock Livelock
v Processes
+--------------+ Processes wait
Definition continuously
| LIVELOCK | indefinitely
change states
+--------------+ Process
Example of Livelock in Computer Blocked Active
State
Systems CPU
Consider two processes trying to avoid Low High
Usage
deadlock.
No useful
1. Process P1 checks if Resource R1 is Progress No progress
progress
free.
2. Process P2 checks if Resource R2 is Resources
Resources
free. Resource repeatedly
remain
3. Both release their resources to help Usage released and
occupied
the other process. requested
4. Both retry simultaneously. Waiting for Repeatedly
5. This repeats continuously. Example each other’s retrying
The processes remain active but do not resource operations
complete execution. Comparison Diagram
Causes of Livelock DEADLOCK LIVELOCK
1. Excessive process coordination.
2. Overreaction between processes. P1 waits for P2 P1 reacts to P2
3. Improper retry mechanisms. P2 waits for P1 P2 reacts to P1
4. Poor synchronization strategy.
Methods to Prevent Livelock No movement Continuous
1. Randomized Retry movement
Processes retry after random delays.
2. Priority Mechanism Blocked state Active state
Assign priorities to processes. Applications and Importance
3. Proper Synchronization Understanding deadlock and livelock is
Use efficient synchronization techniques. important in:
4. Back-off Algorithms 1. Operating Systems.
Processes wait for increasing time intervals 2. Database Management Systems.
before retrying. 3. Distributed Systems.
Advantages of Livelock Prevention 4. Networking.
 Single Processor

3 . Parallel For Directive with Example Iteration 1 ---> Completed

Introduction Iteration 2 ---> Completed
In modern computing systems, improving Iteration 3 ---> Completed
execution speed and performance is very Iteration 4 ---> Completed
important. One of the major techniques used
to improve performance is Parallel Total Time = High
Programming. Parallel programming
allows multiple tasks to execute Parallel Execution Diagram
simultaneously using multiple processors or Multiple Threads
multiple cores.
A commonly used concept in parallel +-------------------+
programming is the Parallel For Directive. | Thread 1 |
It is mainly used in shared memory | Iteration 1 & 2 |
programming models such as OpenMP. The +-------------------+
parallel for directive divides loop iterations
among multiple threads so that the work can +-------------------+
be completed faster. | Thread 2 |
The parallel for directive is widely used in | Iteration 3 & 4 |
scientific computing, image processing, +-------------------+
machine learning, simulations, matrix
operations, and data analysis applications. +-------------------+
| Thread 3 |
Definition of Parallel For Directive | Iteration 5 & 6 |
A Parallel For Directive is a programming +-------------------+
construct used to distribute loop iterations
among multiple threads for concurrent Total Execution Time = Reduced
execution.
It enables a loop to run in parallel instead of Syntax of Parallel For Directive
sequentially. The parallel for directive is mainly used in
OpenMP.
Need for Parallel For Directive Syntax
In sequential execution, loop iterations are #pragma omp parallel for
executed one after another. for(i = 0; i < n; i++)
For large loops, execution time becomes {
very high. // Statements
The parallel for directive solves this problem }
by:
1. Dividing loop iterations among Explanation of Syntax
threads. Statement Description
2. Executing multiple iterations #pragma
simultaneously. Compiler directive for OpenMP
omp
3. Reducing overall execution time. parallel for Executes loop in parallel
4. Improving CPU utilization. Loop whose iterations are
for loop
divided among threads
Sequential Execution Diagram
 v
Working of Parallel For Directive +----------------------+
The working process includes the following | End Program |
steps: +----------------------+
1. The compiler identifies the parallel
for directive. Example of Parallel For Directive
2. Multiple threads are created. Sequential Program
3. Loop iterations are divided among #include <stdio.h>
threads.
4. Threads execute simultaneously. int main()
5. Results are combined after {
completion. int i;

Flowchart of Parallel For Directive for(i = 0; i < 5; i++)

+----------------------+ {
| Start Program | printf("Iteration %d\n", i);
+----------+-----------+ }
|
v return 0;
+----------------------+ }
| Identify Parallel | Output
| For Directive | Iteration 0
+----------+-----------+ Iteration 1
| Iteration 2
v Iteration 3
+----------------------+ Iteration 4
| Create Multiple | In this program, iterations execute one after
| Threads | another.
+----------+-----------+
| Parallel Program Using Parallel For
v Directive
+----------------------+ #include <stdio.h>
| Divide Loop | #include <omp.h>
| Iterations |
+----------+-----------+ int main()
| {
v int i;
+----------------------+
| Execute Iterations | #pragma omp parallel for
| Simultaneously | for(i = 0; i < 5; i++)
+----------+-----------+ {
| printf("Iteration %d executed by
v Thread %d\n",
+----------------------+ i, omp_get_thread_num());
| Combine Results | }
+----------+-----------+
| return 0;
} Large chunks are assigned initially and
smaller chunks later.
Sample Output Example
Iteration 0 executed by Thread 0 #pragma omp parallel for schedule(guided)
Iteration 1 executed by Thread 1
Iteration 2 executed by Thread 2 4. Runtime Scheduling
Iteration 3 executed by Thread 3 Scheduling policy is decided during runtime.
Iteration 4 executed by Thread 0 Example
The order may vary because multiple #pragma omp parallel for schedule(runtime)
threads execute simultaneously.
Clauses Used with Parallel For Directive
Diagram Showing Loop Division Several clauses are used to control
Loop Iterations execution.

Iteration 0 --> Thread 0 1. private Clause

Iteration 1 --> Thread 1 Creates private copies of variables for each
Iteration 2 --> Thread 2 thread.
Iteration 3 --> Thread 3 Example
Iteration 4 --> Thread 0 #pragma omp parallel for private(i)

Scheduling in Parallel For Directive 2. shared Clause

Scheduling determines how loop iterations Variables are shared among all threads.
are assigned to threads. Example
Types of Scheduling #pragma omp parallel for shared(sum)
1. Static Scheduling
Iterations are divided equally before 3. reduction Clause
execution. Combines results from multiple threads.
Example Example
#pragma omp parallel for schedule(static) #pragma omp parallel for reduction(+:sum)
Advantage
 Low scheduling overhead. 4. schedule Clause
Disadvantage Specifies scheduling method.
 Load imbalance may occur. Example
#pragma omp parallel for
2. Dynamic Scheduling schedule(dynamic)
Iterations are assigned dynamically during
execution. Example Using Reduction Clause
Example #include <stdio.h>
#pragma omp parallel for #include <omp.h>
schedule(dynamic)
Advantage int main()
 Better load balancing. {
Disadvantage int i, sum = 0;
 Higher overhead.
#pragma omp parallel for
3. Guided Scheduling reduction(+:sum)
for(i = 1; i <= 10; i++)
 { Difference Between Sequential Loop and
sum = sum + i; Parallel Loop
} Sequential
Feature Parallel Loop
Loop
printf("Sum = %d", sum); Multiple
One iteration
Execution iterations
return 0; at a time
simultaneously
} Speed Slow Faster
Output
CPU Usage Low High
Sum = 55
The reduction clause safely combines partial Performance Lower Better
sums from all threads. Thread
Single thread Multiple threads
Usage
Advantages of Parallel For Directive
1. Reduces execution time. Comparison Diagram
2. Improves CPU utilization. SEQUENTIAL LOOP
3. Supports concurrent execution.
4. Easy to implement. Iteration 1
5. Efficient for large loops. Iteration 2
6. Improves system performance. Iteration 3
7. Useful in scientific computations. Iteration 4
8. Supports multicore processors.

Disadvantages of Parallel For Directive PARALLEL LOOP

1. Synchronization overhead.
2. Difficult debugging. Thread 1 --> Iteration 1
3. Race conditions may occur. Thread 2 --> Iteration 2
4. Performance depends on hardware. Thread 3 --> Iteration 3
5. Not suitable for dependent loops. Thread 4 --> Iteration 4

Applications of Parallel For Directive Important Considerations

Parallel for directive is used in many fields. While using parallel for directive, the
1. Matrix Operations programmer must ensure:
Used in matrix multiplication and matrix 1. Loop iterations are independent.
addition. 2. Shared variables are handled
2. Image Processing carefully.
Used in filtering and image enhancement. 3. Synchronization issues are avoided.
3. Scientific Simulations 4. Proper scheduling is selected.
Used in weather prediction and simulations. 5. Race conditions are prevented.
4. Machine Learning
Used in training large datasets. Race Condition in Parallel Loops
5. Data Analytics A race condition occurs when multiple
Used for processing big data. threads access the same variable
6. Numerical Computation simultaneously.
Used in mathematical calculations. Example
sum = sum + i;
If many threads modify sum simultaneously, Fully
incorrect results may occur. Direct
Feature Associative
The reduction clause solves this issue. Mapping
Mapping
lines.
Performance Improvement Example Poor cache
Assume: Cache Better cache utilization
 Sequential loop execution time = 20
Utilization utilization. due to fixed
seconds. mapping.
 Using 4 threads with parallel for
More
directive. Very less
Collision conflict
Approximate execution time: chance of
Problem misses
20 / 4 = 5 seconds collision.
occur.
Thus, performance improves significantly.
Requires No
Replacement replacement replacement
4. Policy algorithms like choice
Fully LRU, FIFO. needed.
Direct Implementation Difficult to Easy to
Feature Associative
Mapping Difficulty implement. implement.
Mapping
Each block Lower hit
Any block of Performance Higher hit ratio.
of main ratio.
main memory A memory Block 5 may
memory is
Definition can be placed block can be always map
mapped to a Example
in any cache stored in any to cache line
fixed cache
line. cache block. 1.
line.
Very high Less
Flexibility Diagram of Direct Mapping
flexibility. flexibility.
Memory
Memory block Main Memory Blocks Cache Lines
block maps
Mapping can occupy any
to only one
Method location in Block 0 -------------> Line 0
specific
cache. Block 1 -------------> Line 1
cache line.
Tag + Line Block 2 -------------> Line 2
Address Block 3 -------------> Line 3
Tag + Word Number +
Structure Block 4 -------------> Line 0
Word
Entire cache is Only one
 Fixed mapping is used.
Cache Search searched cache line is
 Multiple blocks may map to the
simultaneously. checked.
same cache line.
Complex Simple
Hardware
hardware hardware
Complexity
required. required.
Less Diagram of Fully Associative Mapping
Cost Expensive.
expensive.
Speed Slower due to Faster Main Memory Block 5
searching all access time.
 Can be placed in

Line 0
Line 1
Line 2
Line 3

 Any memory block can be stored

anywhere in cache.