PARALLEL COMPUTING(BCS702)

1. Define Distributed Memory. Explain the 2 architectural types using MPI.

Ans: Distributed Memory refers to a computer architecture in which each processor has its
own private memory that cannot be directly accessed by other processors.

• Processors communicate and exchange data explicitly through message passing,

usually using libraries such as MPI (Message Passing Interface).
Architectural Types using MPI:
1. Distributed-Memory Systems:
• A distributed-memory system consists of multiple core–memory pairs connected
through a communication network.
• Each core has its own local memory, which can be accessed only by that core.
• If one core needs data from another core’s memory, it must explicitly communicate—
typically by sending and receiving messages.
• The programs that run on each core–memory pair are referred to as processes.

2. Shared-Memory Systems:
• A shared-memory system has multiple cores that all share access to a single, globally
accessible memory.
• Any core can directly read or write to any memory location.
• This makes data sharing simpler because no explicit communication is required.
2. Define MPI. Explain Key MPI Functions

Ans: Message-Passing Interface (MPI): The Message-Passing Interface (MPI) is the

standard and most widely used method for programming distributed-memory systems.
It provides a set of library functions that allow processes to communicate by explicitly
sending and receiving messages.

Key MPI Functions:

1. Send and Receive Functions:

• Used for communication between two processes (called point-to-point

communication).

• Example functions:

o MPI_Send() – sends data.

o MPI_Recv() – receives data.

• Different versions exist for performance and speed control.

2. Collective Communication:

• Used when many processes need to communicate together.

• Examples:

o MPI_Bcast() – sends data from one process to all others.

o MPI_Gather() – collects data from all processes to one.

o MPI_Scatter() – divides data and sends parts to all processes.

o MPI_Reduce() – combines results from all processes (like sum or max).

3. Important Issues in MPI Programming:

a. Data Partitioning: Data must be divided among different processes, helps reduce
communication and improves speed.

b. Input/Output (I/O): Each process has its own local memory and [Link] gives special
methods for parallel I/O.

c. Program Performance: We measure MPI program performance using:

o Speedup – how much faster than serial.

o Efficiency – how well processors are used.

o Scalability – how it performs with more processors.

3. Differentiate between OpenMP and MPI.

Ans:

4. Explain the concept of trapezoidal rule in MPI with formulas.

Ans: Trapezoidal Rule in MPI:
The trapezoidal rule estimates the area under a curve y=f(x) between two vertical lines x=a
and x=b.
MPI (Message Passing Interface) is used to parallelize this computation — dividing the
integration work among multiple processes.
Basic Idea:
1. Divide the interval [a,b] into n equal subintervals.
2. Approximate the area above each subinterval by a trapezoid.
Each trapezoid has:
• Base = width of subinterval = h
• Heights = values of f(x) at the two ends of that subinterval
The total area ≈ sum of all trapezoid areas.
Formulas
1. Length of each subinterval:

2. Area of one trapezoid:

If the subinterval endpoints are xi and xi+1,

3. Total area (approximation of the integral):

For n equal subintervals over [a,b]:

Where,

5. Define Parallelizing. Explain the 4 Step process for converting serial program to
parallel one.
Ans: "Parallelizing" refers to the process of converting a serial program into a parallel one.
Four-Step Process to Convert a Serial Program to a Parallel One:
1. Partition the problem solution into tasks:
We break down the problem into smaller independent tasks:
• Task 1: Compute the area of each individual trapezoid.
• Task 2: Sum the areas of all trapezoids to get the total area.
2. Identify communication channels between tasks:
Each "calculate trapezoid area" task needs to send its result to the "sum areas" task.
3. Aggregate tasks into composite tasks:

• Since we typically use many more trapezoids than available cores, we need to group
the trapezoid calculations.
• A natural way is to divide the total interval [a,b] into comm_sz (number of processes)
subintervals.
• Each process then applies the trapezoidal rule to its assigned subinterval, calculating a
local_integral.

4. Map composite tasks to cores:

• Each of the comm_sz processes calculates a local_integral for its assigned subinterval.
• One process (e.g., process 0) is designated to collect all the local_integral values and
sum them to get the total_integral.

6. Write a Pseudocode for serial program with 2 graphs for trapezoidal rule and one
trapezoid.

Ans: Pseudocode for Serial Program:

/* Input: a, b, n */

h = (b - a) / n;

approx = (f(a) + f(b)) / 2.0; // Half of f(a) and half of f(b)

for (i = 1; i <= n - 1; i++) {

x_i = a + i * h;

approx += f(x_i); // Add f(x_i) for intermediate points (counted once)

approx = h * approx; // Multiply by h at the end

7. Differentiate between shared memory and distributed memory.

Ans:
10. Write a note on MPI derived datatypes.

Ans: MPI Derived Datatypes:

Definition: An MPI Derived Datatype is a user-defined data structure in Message Passing

Interface (MPI) that allows a programmer to describe a collection of data items in memory by
specifying their data types and relative locations (displacements).

Concept:

• Instead of sending each variable or array element separately, MPI lets you define a
single “blueprint” that represents a complex data layout (for example, mixed data
types or non-contiguous memory locations).
• This derived datatype can then be used in communication functions such as
MPI_Send, MPI_Recv, or MPI_Bcast to send or receive all the data in one operation.

Working Mechanism:

• Sender side:
MPI automatically gathers (packs) the specified data items from scattered memory
locations into a single contiguous buffer and sends them as one message.

• Receiver side:
MPI automatically unpacks the received data and places it into the correct locations in
memory according to the same datatype definition.

Example

In a trapezoidal rule program, three separate broadcasts are normally required:

MPI_Bcast(&a, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);

MPI_Bcast(&b, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);

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

Using a derived datatype, these can be combined into one broadcast:

• Define a datatype that represents two doubles and one integer.

• Use it in a single MPI_Bcast call to send all three variables at once.

11. Explain collective communication in MPI.

Ans: Collective Communication in MPI:

Definition: Collective communication in MPI (Message Passing Interface) refers to

communication operations that involve a group of processes within a communicator. Unlike
point-to-point communication (between two processes), collective communication is
performed by all processes in the group simultaneously.

Purpose: Collective communication is used to exchange data, synchronize, or combine

information among multiple processes efficiently. MPI provides built-in functions that handle
these operations automatically.

Types of Collective Communication Operations:

1. Broadcast (MPI_Bcast)

o Sends the same data from one process (root) to all other processes in the
communicator.

o Example: Sharing input values like a, b, and n to all processes.

2. Scatter (MPI_Scatter)

o Divides an array of data on the root process and sends a portion to each
process.

o Example: Distributing different parts of an array for parallel processing.

3. Gather (MPI_Gather)

o Collects data from all processes and stores it in an array on the root process.

o Example: Collecting partial results from all processes after computation.

4. Allgather (MPI_Allgather)

o Similar to MPI_Gather, but the gathered data is shared with all processes.

5. Reduce (MPI_Reduce)

o Combines values from all processes using an operation (like sum, max, min)
and returns the result to the root process.

o Example: Summing up partial results from all processes.

12. Write a pseudo code for parallel program.

Ans: Pseudocode for Parallel program:

Get a, b, n;

h = (b - a) / n;

local_n = n / comm_sz; // Number of trapezoids for this process

local_a = a + my_rank * local_n * h; // Starting point for this process

local_b = local_a + local_n * h; // Ending point for this process

local_integral = Trap(local_a, local_b, local_n, h); // Calculate local integral

if (my_rank != 0)

Send local_integral to process 0;

else // my_rank == 0

total_integral = local_integral; // Process 0 starts with its own result

for (proc = 1; proc < comm_sz; proc++) {

Receive local_integral from proc;

total_integral += local_integral; // Accumulate results from others

if (my_rank == 0)

print total_integral; // Display final result

13. Explain the working of 8 processes in tree structure.

Ans: Working of 8 Processes in a Tree-Structured Communication:

A tree-structured communication (also called binary reduction tree) is an efficient way to

perform global operations like summation across multiple processes in MPI.
Instead of all processes sending their results directly to process 0, communication is
organized in phases that resemble the merging of nodes in a binary tree.

How It Works (Example with 8 Processes: P0–P7)

Phase 1:
• Processes 1, 3, 5, and 7 send their values to 0, 2, 4, and 6, respectively.
• The receiving processes add the received values to their own.
o P0 = P0 + P1
o P2 = P2 + P3
o P4 = P4 + P5
o P6 = P6 + P7

4 sends and 4 additions occur concurrently.

Phase 2:
• Processes 2 and 6 send their new sums to 0 and 4, respectively.
• The receiving processes again add the values.
o P0 = (P0 + P1) + (P2 + P3)
o P4 = (P4 + P5) + (P6 + P7)

2 sends and 2 additions occur concurrently.

Phase 3:
• Process 4 sends its total sum to process 0.
• Process 0 adds the value:
o P0 = (P0 + P1 + P2 + P3) + (P4 + P5 + P6 + P7)

1 send and 1 addition.

14. Write a note on MPI_Reduce function.

Ans: MPI_Reduce Function:
Definition: MPI_Reduce is a collective communication function in MPI that performs a
global reduction operation (such as sum, maximum, minimum, product, etc.) across all
processes in a communicator and returns the final result to a single destination process.
Syntax: int MPI_Reduce(
void* input_data_p, /* input data */
void* output_data_p, /* output data */
int count, /* number of elements */
MPI_Datatype datatype,/* data type of elements */
MPI_Op operator, /* reduction operation */
int dest_process, /* root process to store result */
MPI_Comm comm /* communicator */
);
Purpose: MPI_Reduce takes values from all processes in the communicator comm,
applies the specified operator (like sum, max, min, etc.) and stores the final single result in
the destination process (dest_process).
Operator (MPI_Op): The operator argument determines what reduction operation to
perform. MPI provides several predefined operators, such as:
o MPI_SUM → Sum of all values
o MPI_MAX → Maximum value
o MPI_MIN → Minimum value
o MPI_PROD → Product of all values
o MPI_LOR → Logical OR
o MPI_LAND → Logical AND
Example (Trapezoidal Rule):

• Instead of manually sending and receiving partial results, we can use MPI_Reduce:

MPI_Reduce(&local_int, &total_int, 1, MPI_DOUBLE, MPI_SUM, 0,

MPI_COMM_WORLD);
• Each process provides its local integral (local_int).
• MPI automatically performs the sum (MPI_SUM) across all processes.
• The final result (total_int) is stored only on process 0.