Parallel Computing (Module – 2)

1. Explain the concepts of speedup and efficiency to determine processor

utilization in a parallel program, and show how speedup and efficiency
vary with different problem sizes.

Speedup & Efficiency in Parallel Programs (7 Marks)

1. Speedup (S)
• Measures how much faster a parallel program runs compared to a serial version.
• Formula (from PPT):

2. Efficiency (E)
• Shows how well the processors are being used.
• Formula (from PPT):

• Efficiency = 1 (or 100%) means perfect utilization.

3. Why Speedup and Efficiency Decrease

• Parallel programs include overheads (communication, synchronization).
• PPT formula:

• More overhead → slower parallel runtime → lower speedup and efficiency.

4. Effect of Problem Size on Speedup & Efficiency

A. Small Problem Size

• Overhead dominates the computation.
• Speedup is low because:
o Too little work per processor
o Communication cost > computation
• Efficiency decreases when processors remain idle due to small workload.

B. Large Problem Size

• More computation available → overhead becomes smaller relative to work.
 • Speedup increases (closer to linear).
• Efficiency improves because processors stay busy longer.
• Confirmed by “Speedups and efficiencies for different problem sizes” slide.

2. Explain the concept of scalability to explain how increasing the number

of processors in a MIMD system affects program performance.

1. Concept of Scalability
• A program/system is scalable if it can maintain good performance as the number of
processors increases.
• From PPT: “A problem is scalable if it can handle ever increasing problem sizes.”
Module - 2

2. Effect of Increasing Processors

Adding more processors affects:
• Speedup

• Efficiency
• Work distribution
• Overhead (communication + synchronization)
If overhead grows slowly compared to useful work → program scales well.

3. Strong Scalability
• Problem size is kept constant while processors increase.
• Scalability is good only if efficiency stays high with more processors.
• Hardto achieve because overhead increases when too many processors share the same
small workload.
• From PPT: “If the efficiency is fixed without increasing problem size → strong scalability.”

4. Weak Scalability
• Problem size increases proportionally with processors.
• Scalability is good if efficiency remains constant as both p and problem size increase.
• Easier to achieve in practice.
• PPT: “Increasing problem size at the same rate as number of processors → weak
scalability.”
]

5. Why More Processors Can Hurt Performance

Adding processors does NOT always improve performance because:
• Communication overhead increases
• Synchronization overhead increases
• Idle time increases when tasks are too small
• Diminishing returns due to Amdahl’s Law
Thus, speedup eventually saturates.

6. When Performance Improves

Performance improves when:
 • Workload increases with processor count
• Parallelizable portion of the program is large
• Overheads are minimized
• Load balancing is good
Then speedup ≈ number of processors → high scalability.

3. Interpret the role of barriers and elapsed times in timing parallel

programs and justify with reasons why the minimum run-time is
preferred.
1. Role of Barriers in Timing Parallel Programs
• A barrier forces all threads/processes to reach the same point before proceeding.
• Ensures the timing measurement starts only after all threads are ready.
• Prevents one fast thread from starting early and giving incorrect shorter times.
• PPT refers to synchronization before taking timings.
Module - 2

2. Why Barriers Are Needed Before Timing

• Without a barrier, threads may start work at different times → inaccurate elapsed time.
• Barriers ensure fair and consistent timing for the whole parallel region.

3. Measuring Elapsed Time

• Parallel programs require measuring wall-clock time, not CPU time.
• PPT mentions tools:
o MPI_Wtime()
o omp_get_wtime()
Module - 2
• Elapsed time = end_time – start_time.
• Must place timing calls outside the parallel computation for accuracy.

4. Why Elapsed Time Matters

• Parallel programs run on many processors, so total CPU time is meaningless.
• Elapsed time shows how long the user actually waits for the job to finish.

5. Why Minimum Run-Time Is Preferred

Parallel programs often show variation between runs due to:
• OS interruptions
• Cache effects

• Scheduling differences
• Network delays (MPI programs)
• Memory interference
(These variations are implied in slides discussing timing challenges.)
Module - 2

Minimum run-time represents:

• The execution with least overhead
 • The execution closest to true computational cost
• The most stable and repeatable performance estimate

6. Average or maximum timing is not preferred because:

• Average includes noise from slow iterations.
• Maximum time reflects worst-case system interference, not program efficiency.
• Minimum time filters out external disturbances.

4. Explain GPU performance to show whether the evaluation measures

used in MIMD systems, such as speedup, efficiency, and scalability, are
applicable to GPU or not.
1. GPU Performance Characteristics (from PPT)
• GPUs execute programs using SIMD-style groups (warps) where multiple threads run the
same instruction on different data.
• GPU hardware uses massive parallelism, scheduling thousands of threads with very low
overhead.
• Performance depends on:
o Number of active warps
o Memory bandwidth
o Branch divergence (threads taking different paths)
o Occupancy (how many thread groups are kept busy)

2. Are MIMD Evaluation Measures Applicable to GPUs?

A. Speedup — Yes, but interpreted differently

• Speedup = Tserial/TGPUT_\text{serial} / T_\text{GPU}Tserial/TGPU
• GPUs achieve large speedups due to thousands of concurrent threads.
• HOWEVER:

o A true “serial version” may not exist because GPUs require host+device
programming (heterogeneous model).
o Speedup is often compared against a CPU baseline, not a pure serial GPU version.
Conclusion: Speedup is applicable, but comparisons must be done carefully.

B. Efficiency — Not directly meaningful

• MIMD efficiency = Speedup / Number of processors.
• GPUs do not expose individual “processors” the way MIMD cores do.
• Threads execute in warps and do not act as independent processors.
• Hardware schedules warps automatically; programmer cannot assign workload per core.
Conclusion: Efficiency is not a useful metric for GPUs.
Efficiency ≠ meaningful because GPU hardware parallelism is not MIMD-style.

C. Scalability — Partially applicable

Scalability in MIMD = performance when increasing number of processors.
For GPUs:
• You do not increase cores; you increase number of threads.
• More threads → higher occupancy → better performance until GPU hardware is saturated.
 • But adding more threads beyond hardware limit does not increase speed (warp scheduler
just switches among them).
Conclusion:
• Weak scalability applies (larger problems → better performance).
• Strong scalability does not apply like MIMD because the GPU's number of cores is fixed.

3. Why MIMD Measures Don’t Transfer Perfectly to GPUs

• GPU uses SIMD execution, not independent instruction streams.
• Thread divergence reduces performance unpredictably → not seen in MIMD metrics.
• GPU performance dominated by:
o memory bandwidth
o warp occupancy
o branch divergence
o coalesced memory accesses
These factors are not part of MIMD speedup/efficiency models.

5. Explain why efficiency is typically not measured for GPU programs,

while speedup is. How is timing usually performed for GPU programs,
and why do multiple runs help reduce variability?
1. Why Efficiency Is NOT Measured for GPU Programs
Efficiency = Speedup / Number of processors, but GPUs do not expose a clear number
of independent processors like MIMD systems.
GPU threads execute in SIMD warps, not as independent CPU-like cores → efficiency
becomes meaningless.
Thousands of GPU threads do not map directly to hardware units, so dividing speedup by
“number of processors” gives an invalid metric.
GPU performance depends on warp scheduling, memory bandwidth, occupancy, and
branch divergence, not on processor count.
Therefore, efficiency does not reflect true GPU utilization and is never used in GPU
performance evaluation.

2. Why Speedup IS Measured for GPU Programs

Speedup compares CPU execution time vs GPU execution time, which is meaningful
because GPUs are designed for high throughput.
Speedup clearly shows performance gain from using the GPU and is independent of the
unclear GPU processor count.

3. How Timing Is Performed for GPU Programs

GPU programs use host–device timing, usually measured on the CPU (host).
Common timing functions:
o cudaEventRecord() and cudaEventElapsedTime() in CUDA
o omp_get_wtime() or MPI_Wtime() for hybrid programs
Timing must include both:
• Kernel execution time
• Data transfer time (CPU ↔ GPU), if evaluating overall performance.
GPU timing must ensure synchronization, because kernel launches are asynchronous (the
CPU returns before GPU finishes).
4. Why Multiple Runs Reduce Variability
GPU run-time varies due to:
o Memory traffic
o Cache behavior
o OS interference
o Background GPU tasks
Running the program multiple times helps capture stable performance.
The minimum run-time is usually taken, since it represents the execution with the least
interference and closest to the real kernel performance.

6. Explain the concepts of speedup and efficiency to evaluate the

performance of a parallel program that takes 120 seconds on one
processor and 40 seconds on four processors
OR
Apply the concepts of speedup and efficiency to decide which system is
better:
System A: 8 processors, execution time = 40s (sequential time = 160s)
System B: 4 processors, execution time = 60s (sequential time = 160s)

(Refer Notes)

1. Make use of MPI function prototypes to explain a Greetings program

demonstrating message passing between processes.
1. MPI Function Prototypes Used in a Greetings Program
A basic MPI greetings program has one process (rank 0) send and receive messages to/from all
other processes.
The important MPI function prototypes are:

(a) MPI_Init
int MPI_Init(int *argc, char ***argv);

– Initializes the MPI environment.

(b) MPI_Comm_rank
int MPI_Comm_rank(MPI_Comm comm, int *rank);

– Returns the rank (ID) of the calling process.

(c) MPI_Comm_size
int MPI_Comm_size(MPI_Comm comm, int *size);
– Returns the total number of processes.

(d) MPI_Send
int MPI_Send(void *buf, int count, MPI_Datatype datatype,
int dest, int tag, MPI_Comm comm);
– Sends a message to a destination process.

(e) MPI_Recv
int MPI_Recv(void *buf, int count, MPI_Datatype datatype,
int source, int tag, MPI_Comm comm,
MPI_Status *status);

– Receives a message from a sender.

(f) MPI_Finalize
int MPI_Finalize(void);
– Terminates the MPI environment.
2. Greetings Program Logic (Message Passing)

● Process 0 (Master)
• Sends a greeting message to every other process using MPI_Send.
• Receives acknowledgment messages from each process using MPI_Recv.

● Other Processes (Workers)

• Receive the greeting from process 0 using MPI_Recv.
• Send a reply message back to process 0 using MPI_Send.

4. Pseudocode of Greetings Program

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

if (rank == 0) {
for (int p = 1; p < size; p++) {
MPI_Send("Hello!", 6, MPI_CHAR, p, 0, MPI_COMM_WORLD);
}

for (int p = 1; p < size; p++) {

MPI_Recv(msg, 50, MPI_CHAR, p, 0, MPI_COMM_WORLD, &status);
}
}
else {
MPI_Recv(msg, 50, MPI_CHAR, 0, 0, MPI_COMM_WORLD, &status);
MPI_Send("Reply from process", 20, MPI_CHAR, 0, 0, MPI_COMM_WORLD);
}

MPI_Finalize();

2. Mention the advantages of MPI in parallel computing.

Advantages of MPI in Parallel Computing
1. Portability
– MPI runs on almost every parallel system: clusters, supercomputers, multicore CPUs.
– Programs written once can run anywhere.
2. Scalability
– Supports thousands to millions of processes.
– Ideal for large distributed-memory systems and HPC applications.
3. Explicit Control Over Communication
– Programmers control data movement using MPI_Send, MPI_Recv, collectives, etc.
– Allows optimization for performance-critical applications.
4. Supports Complex Communication Patterns
– Point-to-point, collective operations, broadcast, scatter/gather, reductions.
– Enables flexible parallel algorithms.
5. Efficient for Distributed Memory Systems
– Designed for systems where each processor has private memory.
– Low communication overhead with high-speed interconnects.
6. Rich Functionality
– Timing routines, synchronization, datatypes, virtual topologies, groups &
communicators.
– Helps structure complex parallel programs.
7. Fault Isolation & Independence
– Each process runs independently; failure of one doesn’t corrupt others.
– Good for debugging and reliability.
 3. Explain the difference between shared-memory and distributed memory
systems with neat diagrams.

1. Shared-Memory Systems

Concept
• All processors access a single global shared memory.
• Communication occurs through shared variables.
• Used in multicore CPUs and SMP machines.

Diagram

Characteristics
• Simple to program.
• Faster communication → no messages needed.
• Requires synchronization (locks, semaphores, barriers).
• Does not scale well beyond a few processors.

2. Distributed-Memory Systems

Concept
• Each processor has its own private memory.
• Communication occurs via message passing (e.g., MPI).
• Used in clusters, supercomputers.

Diagram
Characteristics
• Highly scalable → can handle thousands of processors.
• No shared data → communication must be explicit.
• Suited for large parallel applications.

4. Define the SPMD model. How does MPI support the SPMD approach?

1. Definition of SPMD Model

SPMD = Single Program, Multiple Data
It is a parallel programming model where:
1. All processes run the same program.
2. Each process operates on different parts of the data.
3. Behavior differs based on process rank (ID).
4. Control flow is chosen using rank-based branching:
5. if (rank == 0) { ... }
6. else { ... }

2. Features of SPMD
• One executable file → many parallel instances.
• Each process works independently.
• Suitable for both shared-memory and distributed-memory systems.
• Reduces programming complexity since there is one source code.

How MPI Supports the SPMD Model

MPI naturally implements SPMD because:

1. All MPI processes start the same program

• Using mpirun –np p ./[Link] launches p identical copies of the program.

2. MPI assigns a unique rank to every process

• MPI_Comm_rank() gives each process an ID.
Processes use this rank to decide which part of the program to execute.
3. Each process can access the total number of processes
• Using MPI_Comm_size(), processes divide the work among themselves.

4. Rank-based branching supports different roles

Example:
• Rank 0 → master
• Others → workers

5. MPI message-passing enables cooperation

• Processes communicate using:
o MPI_Send()
o MPI_Recv()

o Collective operations (broadcast, scatter, gather)

6. SPMD fits distributed memory (MPI’s target

environment)
• Each process has its own private memory and communicates explicitly, exactly as required
by SPMD.

5. Explain i) Message matching, ii) Status-p argument

i) Message Matching
Message matching refers to how MPI pairs a send operation with the correct receive
operation.

Key Points
1. For every MPI_Send(), MPI must find the correct MPI_Recv() that is expecting that
message.
2. Message matching is based on three fields:
o Source (sending rank)
o Tag (message identifier)
o Communicator (MPI_COMM_WORLD, etc.)
3. A receive operation completes only when all three fields match.
4. Ensures that a process does not accidentally receive the wrong message, especially when
multiple messages are in transit.
5. Helps maintain correctness in large programs with many point-to-point communications.

Example
MPI_Send(msg, count, MPI_INT, dest=2, tag=10, comm);
MPI_Recv(msg, count, MPI_INT, source=0, tag=10, comm, &status);

Both operations match because source = 0, tag = 10, communicator = same.

ii) Status-p Argument

The status-p argument is the last parameter in MPI_Recv() that stores information about the
received message.

Function Prototype
MPI_Recv(void *buf, int count, MPI_Datatype type,
int source, int tag, MPI_Comm comm,
MPI_Status *status);

What the Status Object Contains

1. source → rank of the sender
2. tag → actual tag of the received message
3. error → error code
 4. Can also be used to query:
o number of elements received using MPI_Get_count()

Why Status-p Is Useful

• The actual sender may be MPI_ANY_SOURCE.
• The actual message tag may be MPI_ANY_TAG.
• The receiver can check what it actually received after the call completes.
• Helps in debugging and flexible handling of messages.

Example Usage
MPI_Status status;
MPI_Recv(buf, 100, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);

printf("Message received from %d with tag %d\n",

status.MPI_SOURCE, status.MPI_TAG);

6. Apply the trapezoidal rule to estimate the area under a curve and
describe how it is parallelized using MPI with reference to its
pseudocode.

A. Trapezoidal Rule (Serial Version)

The trapezoidal rule estimates the area under a curve f(x) between aaa and b by dividing the
interval into n small trapezoids.

Formula
Step size:

Area:

This is the serial computation of numerical integration.

B. How Trapezoidal Rule Is Parallelized Using MPI

MPI applies domain decomposition:

1. Divide the interval

• Total interval [a,b][a, b][a,b] is split among processes.
• Each process gets a subinterval:

• Each process computes area of its local trapezoids.

2. Each process computes partial area

Each process uses the trapezoidal rule formula on its part:
3. Combine results
• All partial areas are sent to process 0.
• Process 0 sums them to obtain the final area.
• Uses MPI_Reduce() or MPI_Send/MPI_Recv.

C. MPI Pseudocode (Exam-Friendly)

Common Setup
MPI_Init()
MPI_Comm_rank(comm, &rank)
MPI_Comm_size(comm, &p)

a, b, n // only rank 0 knows initially

broadcast a, b, n to all processes
h = (b - a) / n
local_n = n / p

Compute local interval

local_a = a + rank * local_n * h
local_b = local_a + local_n * h

Compute local area

local_area = (f(local_a) + f(local_b)) / 2.0
for i = 1 to local_n - 1:
x = local_a + i * h
local_area += f(x)
local_area = local_area * h

Reduce to obtain final result

MPI_Reduce(local_area, total_area, 1, MPI_DOUBLE, MPI_SUM, 0, comm)

Finalize
if (rank == 0):
print total_area
MPI_Finalize()

D. Why MPI Parallelization Works Well

1. Each process works on independent subintervals → no race conditions.
2. Only final partial sums need communication → low overhead.
3. Trapezoidal rule is naturally parallel, so near-linear speedup is possible.

7. Explain how input and output are handled in MPI programs.

1. Input Handling
Only Process 0 reads from standard input (stdin)
– MPI follows the rule that only process 0 should access stdin in distributed-memory
systems.
– Prevents conflicting or duplicated inputs.
Process 0 distributes input to other processes
– Uses MPI communication functions such as:
o MPI_Bcast() (broadcast input to all)
o MPI_Send() / MPI_Recv()
– Ensures every process receives the same correct data.
Other processes do NOT read directly from stdin
– They only receive data sent by process 0.
– This avoids nondeterministic behavior.

2. Output Handling
 All processes can write to stdout, but it is not recommended
– Output order becomes unpredictable because processes execute independently.
– PPT states: Only a single process/thread should normally write to stdout, except for
debugging output.
Process 0 is typically responsible for final output
– Ensures clean, ordered program output.
– Worker processes send results to process 0 using:
o MPI_Gather()
o MPI_Reduce()
o or point-to-point sends
Debugging output can be printed by any process
– Should always include the rank (ID) to identify the source of the message.

3. File Input/Output
Each process may open its own private file,
– But no two MPI processes should open the same file for writing, unless MPI-IO is
used.
– Ensures no race conditions on file access.

8. Design tree-based communication logic to trace the flow of data during

MPI_Reduce and MPI_Allreduce operation across 8 MPI process.

Let processes be:

P0, P1, P2, P3, P4, P5, P6, P7
Tree-based communication works in log₂(p) steps = 3 steps for 8 processes.

A. MPI_Reduce (Root = P0)

Goal: Combine all values → result stored only at P0.

Step 1 (Pairs send → tree leaves collapse)

P1 → P0
P3 → P2
P5 → P4
P7 → P6

Step 2 (Intermediate nodes combine & send)

P2 → P0
P6 → P4

Step 3 (Final combine)

P4 → P0

Tree Diagram for MPI_Reduce

P0
/ \
P1 P2
/ \
P3 P4
/ \
P5 P6
\
P7

Final result stored at:

P0

B. MPI_Allreduce (Result sent to ALL processes)

Goal: All processes get the final reduced value.
MPI_Allreduce = MPI_Reduce + Tree-based Broadcast

1. Reduction Phase (same as MPI_Reduce)

Result computed at P0 after 3 steps (as above).

2. Broadcast Phase (Tree broadcast from P0 → all processes)

Step 1
P0 → P1
P0 → P2

Step 2
P1 → P3
P1 → P5
P2 → P4
P2 → P6

Step 3
P3 → P7

Tree Diagram for Allreduce (Broadcast Phase)

P0
/ \
P1 P2
/ \ / \
P3 P5 P4 P6
|
P7

Final result stored at:

P0, P1, P2, P3, P4, P5, P6, P7 (all processes)

9. List the differences between point-to-point and collective

communication.
Point-to-Point
Feature Collective Communication
Communication

Communication that involves Communication that occurs

a group of processes working between exactly two
Definition
together within a processes — one sender and
communicator. one receiver.

MPI_Bcast, MPI_Scatter,
MPI_Gather, MPI_Reduce, MPI_Send, MPI_Recv,
Functions Used
MPI_Allgather, MPI_Isend, MPI_Irecv, etc.
MPI_Barrier, etc.

One-to-all, all-to-one, or all-

Data Exchange Type One-to-one.
to-all.

Often implicitly Synchronization must be

Synchronization synchronized among all explicitly handled by the
participating processes. programmer.

Easier to use for group Provides more control and

Ease of Use operations (like broadcasting flexibility for specific
or reduction). communication patterns.

Usually optimized internally

May lead to more overhead if
Performance by MPI for efficiency across
used for group operations.
many processes.
MPI_Bcast(&data, 1, MPI_Send(&data, 1,
MPI_INT, 0, MPI_INT, 1, 0,
Example MPI_COMM_WORLD); – MPI_COMM_WORLD); – Sends
Broadcasts data from root to data from process 0 to 1.
all.

10. Illustrate the role of MPI_Allgather in implementing parallel Matrix-

vector multiplication.

Matrix–vector multiplication computes:

If A is distributed by rows across MPI processes, each process needs the entire vector x to
compute its part of y.
MPI_Allgather provides exactly this.

1. Initial Data Distribution

• Matrix A is split by rows:
• P0 → rows 0 … m
• P1 → rows m+1 … 2m
• ...
• Pp−1 → last rows
• Vector x is split into chunks:
• P0 has x0
• P1 has x1
•…
• Pp−1 has xp−1

2. Need for MPI_Allgather

Each process must compute:

This requires all elements of x, but each process initially has only one segment.
MPI_Allgather is used because it:
Collects vector pieces from all processes
Distributes the complete vector x to every process
Works efficiently using a tree-based collective algorithm (as described in Allgather section)
an_introduction_to_parallel_pro…

3. What MPI_Allgather Does

Before Allgather
P0: x0
P1: x1
P2: x2
P3: x3

MPI_Allgather(...)
Each process sends its piece and receives all pieces.

After Allgather
P0: x0 x1 x2 x3
P1: x0 x1 x2 x3
P2: x0 x1 x2 x3
P3: x0 x1 x2 x3
Now every process has the full input vector.
4. Local Computation After Allgather
Each process computes its local rows:
for each local row i:
y[i] = dot(A[i], x_full)
No further communication is needed.

5. Why MPI_Allgather Is Essential

• Avoids sending the vector x repeatedly to each process.
• Uses tree-structured communication (log p steps), making it scalable.
• Ensures all processes have the same vector, preventing synchronization issues.

11. Explain the syntax of MPI_Type_create_struct. Specify how

displacements and datatypes are specified.
the syntax of the function is:
an_introduction_to_parallel_pro…
int MPI_Type_create_struct(
int count, /* number of items */
int array_of_blocklengths[], /* lengths of each block */
MPI_Aint array_of_displacements[],/* byte displacements of each item */
MPI_Datatype array_of_types[], /* MPI datatypes of each item */
MPI_Datatype *newtype /* output: new datatype */
);

1. Meaning of Each Argument

(a) count
• Number of elements in the derived datatype.
• Example: For variables a, b, n, count = 3.

(b) array_of_blocklengths[]
• Specifies how many consecutive elements of each type appear at each position.
• If each variable is a single value:
• int blocklengths[3] = {1, 1, 1};
an_introduction_to_parallel_pro…

(c) array_of_displacements[]
• Displacements of each element in bytes from the start of the data structure.
• Specifies where each component is stored relative to the first.
• Displacements must be computed using MPI_Get_address.
Example:
• MPI_Aint a_addr, b_addr, n_addr;
• MPI_Get_address(&a, &a_addr);
• MPI_Get_address(&b, &b_addr);
• MPI_Get_address(&n, &n_addr);

•
• disp[0] = 0;
• disp[1] = b_addr - a_addr;
• disp[2] = n_addr - a_addr;
an_introduction_to_parallel_pro…
This ensures portable, architecture-independent offsets.
(d) array_of_types[]
• Stores
the basic MPI datatypes of the elements.
Example for (a, b, n):
• MPI_Datatype types[3] = { MPI_DOUBLE, MPI_DOUBLE, MPI_INT };

an_introduction_to_parallel_pro…

(e) newtype
• Output datatype built by MPI.
• Must be committed before use using:
MPI_Type_commit(&newtype);

Why Displacements Are Needed

• They allow MPI to gather/scatter non-contiguous variables stored in memory.
• MPI uses the displacement array to pack and unpack messages correctly.

12. Explain the performance evaluation metrics for MPI (speedup,

efficiency, scalability).
13. Compute and compare the speedup for problem size n=1024 using 4
and 8 processes. Calculate the efficiency for problem size n=2048 using 8
and 16 processes. Interpret the results to assess scalability across
different process counts.
 INTERPRETATION: Scalability Across Process Counts

1. Speedup Observations
• Speedup improves significantly from 4 → 8 processes.
• But speedup is sub-linear due to MPI communication overheads.

2. Efficiency Observations
• Efficiency is high for both 8 and 16 processes (89% → 81%).
• Efficiency drops slightly as process count increases—expected due to:
o More communication
o More synchronization
o More overhead per process

3. Scalability Conclusion
• The program shows good scalability for problem size n = 2048.
• Efficiency remains above 80% even for 16 processes → strong scalability trend.
• Larger problem size → better efficiency → weak scalability is also good.

Final Assessment
• Program is scalable, but diminishing returns appear at higher process counts.
• Matches the behavior shown in the PPT speedup/efficiency/scalability curves.

14. Develop one phase of a parallel odd-even transposition sort for five
processes using safe communication, and justify how MPI_Sendrecv or
MPI_Sendrev_replace prevents deadlocks in this scenario.

A. System Setup
We have 5 MPI processes, each holding one element:
P0 P1 P2 P3 P4

Odd–even transposition sort alternates between:

• Even phase: (0,1), (2,3) compare–exchange
• Odd phase: (1,2), (3,4) compare–exchange
We illustrate one phase (say, EVEN phase).
 B. ONE EVEN PHASE for 5 Processes

Communication Pairs
Even phase neighbor pairs:
• P0 ↔ P1
• P2 ↔ P3
• P4 has no partner (since 5 is odd)

Goal
Each pair exchanges values; each process keeps either:
• the smaller (ascending order), or
• the larger (descending order)

C. Safe Communication Using MPI_Sendrecv

Correct pattern using MPI_Sendrecv

For each pair:
MPI_Sendrecv(&my_value, 1, MPI_INT, partner, 0,
&recv_value, 1, MPI_INT, partner, 0,
MPI_COMM_WORLD, MPI_STATUS_IGNORE);

Process behavior example (P0 and P1)

P0:
MPI_Sendrecv(my_value to P1, receive from P1)
if (my_value > recv_value) my_value = recv_value;

P1:
MPI_Sendrecv(my_value to P0, receive from P0)
if (my_value < recv_value) my_value = recv_value;

Similarly
• P2 ↔ P3 perform the same exchange
• P4 does nothing this phase

D. Why MPI_Sendrecv Prevents Deadlocks

Deadlock risk in naive send/recv

If both partners do:
MPI_Send(...)
MPI_Recv(...)
then both processes:
• block on Send, waiting for the other to call Recv,
• causing a deadlock (neither reaches Recv).

MPI_Sendrecv solves this

MPI_Sendrecv:
• Performs send and receive in one atomic operation
• Never blocks waiting for the partner to switch from send to receive
• Communication is fully matched internally by MPI
Thus:
No circular waiting
Both processes progress simultaneously
Safe for neighbor exchanges in odd-even sort
 E. MPI_Sendrecv_replace Alternative
MPI_Sendrecv_replace(&my_value, 1, MPI_INT,
partner, 0, partner, 0,
MPI_COMM_WORLD, MPI_STATUS_IGNORE);
• Sends old value and replaces it with received value in the same buffer
• Also prevents deadlocks for the same reason:
o combined send+receive → no blocking mis-match

15. Explain MPI_Scatter and MPI_Gather .write a function to read and

distribute a vector using MPI_Scatter and Gather.

Scatter:
MPI_Scatter can be used in a function that reads in an entire
vector on process 0 but only sends the needed components
to each of the other processes.

Reading and distributing a vector:

Gather:
Collect all of the components of the vector onto process 0,
and then process 0 can process all of the components.

Print a distribution vector:

𝑇𝑐𝑜
𝑇𝑐𝑜(𝑛
16. Estimate the parallel overhead𝑇𝑐𝑜 𝑛,𝑝
𝑝)for 𝑛=4096and 𝑝=4.
 17. Compare the advantages and disadvantages of using bubble sort versus
odd-even transposition sort in a parallel distributed-memory system.

A. Advantages of Bubble Sort

Very simple algorithm
– Easy to implement and understand.
Local compare–swap operation
– Each step only compares neighboring elements (good conceptually).

B. Disadvantages of Bubble Sort in Distributed Memory

Inherently sequential
– Later passes depend on results of earlier passes → poor parallelization.
High communication overhead
– Elements must move across many processes, causing repeated MPI communication.
Poor scalability
– Many rounds of dependent communication → does not scale to large process counts.
Difficult to synchronize
– Hard to avoid deadlocks or inconsistent states when many processes exchange data.

C. Advantages of Odd–Even Transposition Sort

Designed for parallelism
– Sorting happens in phases, and each phase allows safe, simultaneous neighbor
exchanges.
Structured communication
– Processes only talk to direct neighbors → ideal for distributed memory and MPI.
Deadlock-free communication
– Works cleanly with MPI_Sendrecv, avoiding blocking send–recv patterns.
Better scalability than bubble sort
– Each phase is parallel; communication is predictable.

D. Disadvantages of Odd–Even Transposition Sort

Still O(n²)
– Same complexity as bubble sort; slow for very large datasets.
Requires p phases for p processes
– Communication each phase → overhead increases with process count.
Not suitable for high-performance large-scale sorting
– More advanced parallel sorts (bitonic, sample sort) outperform it.

18. Compare the butterfly-structured global sum and tree-structured

broadcast in terms of: *Direction of communication *Purpose (data
aggregation vs. distribution) *Communication pattern and efficiency
with 8 processors.
Let the processors be:
P0, P1, P2, P3, P4, P5, P6, P7

1. Direction of Communication

A. Butterfly-Structured Global Sum (Reduction)

• Communication direction: many → one → all (progressive combining)
 • In each step, processors pair up and exchange partial sums.
• Data moves toward all processors, but each step aggregates upward.

Example (8 processors):
Step 1: (P0↔P1), (P2↔P3), (P4↔P5), (P6↔P7)
Step 2: (P0↔P2), (P1↔P3), (P4↔P6), (P5↔P7)
Step 3: (P0↔P4), (P1↔P5), (P2↔P6), (P3↔P7)

Each step doubles the reach of the partial sum.

B. Tree-Structured Broadcast
• Communication direction: one → many
• Data starts from root (e.g., P0) and spreads outward.
• Each step doubles the number of receivers.

Example (8 processors):
Step 1: P0 → P1, P2
Step 2: P1 → P3, P4; P2 → P5, P6
Step 3: P3 → P7

Broadcast is top-down, unidirectional.

2. Purpose

A. Butterfly Global Sum → Data Aggregation

• Purpose: compute a global sum (or any reduction).
• All processors contribute data; the operation aggregates it.
• Final result ends up at:
o a single root (if MPI_Reduce), or
o all processors (if MPI_Allreduce).

B. Tree Broadcast → Data Distribution

• Purpose: distribute one value from the root to all processors.
• Used to share configuration values, inputs, or results.

3. Communication Pattern & Efficiency (8 processors)

A. Butterfly Reduction

Pattern:
• Logarithmic steps:

• Each process participates in communication each step.

• Pairs exchange and combine data in a structured pattern.

Efficiency:
• Very efficient: O(log p) time.
• Balanced workload → no idle processors.
• Suitable for reductions like sum, max, min, dot product.

B. Tree Broadcast
Pattern:
• Also takes:

• Root sends first, then newly informed processes forward data outward.

Efficiency:
• Also O(log p).
• Scales well for distributing data across many processors.
• Minimizes communication bottleneck at the root.

5. Final 2–3 Line Conclusion (Ready to Write)

• Butterfly global sum aggregates values using pairwise exchanges in log p steps, making it
ideal for reductions.
• Tree broadcast distributes a single value outward from the root in log p steps, ideal for
sending shared data.
• Both are efficient O(log p) communication patterns but differ in direction and purpose.

Programs
1. Fibonacci series

#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, size, n = 10;

int fib[10];

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

MPI_Comm_size(MPI_COMM_WORLD, &size);
 // Only process 0 computes Fibonacci series

if (rank == 0) {

fib[0] = 0;
fib[1] = 1;

for (int i = 2; i < n; i++)

fib[i] = fib[i-1] + fib[i-2];

printf("Fibonacci series:\n");

for (int i = 0; i < n; i++)

printf("%d ", fib[i]);

printf("\n");

MPI_Finalize();

return 0;

2. Prime Number

#include <stdio.h>

#include <mpi.h>

#include <math.h>

int isPrime(int n) {

if (n <= 1) return 0;

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

int main(int argc, char* argv[]) {

int rank, size, num;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

num = rank * 5 + 7; // arbitrary number per process

if (isPrime(num))
printf("Process %d: %d is prime\n", rank, num);
 else

printf("Process %d: %d is NOT prime\n", rank, num);

MPI_Finalize();

return 0;

3. MPI_Send&MPI_Receive

#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, size;

int msg;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

MPI_Comm_size(MPI_COMM_WORLD, &size);

if (rank == 0) {

msg = 100;

MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);

printf("Process 0 sent %d to Process 1\n", msg);

else if (rank == 1) {

MPI_Recv(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

printf("Process 1 received %d from Process 0\n", msg);

MPI_Finalize();

return 0;

4. Deadlock
#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, msg;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);
 if (rank == 0) {

MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);

MPI_Recv(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

else if (rank == 1) {

MPI_Send(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);

MPI_Recv(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

}

MPI_Finalize();

return 0;

5. Broadcast

#include <stdio.h>
#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, size;
int data;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

if (rank == 0) {
data = 20;
printf("Process 0 broadcasting value %d\n", data);
}

MPI_Bcast(&data, 1, MPI_INT, 0, MPI_COMM_WORLD);

printf("Process %d received broadcast value %d\n", rank,

data);
 MPI_Finalize();
return 0;
}