VII Semester

Course: Parallel Computing

Course Code: BCS702

Credits: 03& 2022 Scheme

.IN
Module 3: Distributed Memory Programming with MPI

C
N
Course Instructor
SY

K PRASANTH

Assistant Professor, Dept. of CSE,

EPCET
U
VT

[Link]@[Link]

Department of Computer Science & Engineering, EPCET

Studied smart, not hard — thanks to [Link]

 MODULE-3
Distributed Memory Programming With MPI

Distributed Memory Programming with MPI – MPI Functions

Distributed Memory Programming with MPI: An Introduction to MPI Functions

The world of parallel computing, especially Multiple Instruction, Multiple Data (MIMD) systems, can be
broadly categorized into two architectural types from a programmer’s perspective:

1. Distributed-MemorySystems(Figure 3.1):

.IN
C
N
SY
U
VT

1. Distributed-Memory Systems (Figure 3.1):

o Consist of a collection of core–memory pairs connected by a network.
o The key characteristic is that the memory associated with each core is directly accessible only to
that specific core. To access data located in another core’s memory, communication must occur
explicitly, typically through message passing.
o Programs running on these core–memory pairs are generally referred to as processes.
2. Shared-Memory Systems (Figure 3.2):
o Consist of a collection of cores that share access to a globally accessible memory.
o Each core can directly access any memory location, which simplifies data sharing among
cores.

This chapter focuses on distributed-memory systems and how to program them using message passing.

Studied smart, not hard — thanks to [Link]

Message-Passing Interface (MPI)

Introduction:
The Message-Passing Interface (MPI) is the standard framework for message-passing programming. Rather than
being a new programming language, MPI defines a set of library functions that can be called from existing
languages such as C and Fortran.

.IN
Communication Concept:
In message-passing programs, processes communicate explicitly through function calls:
C
 One process uses a send function to transmit data.

N
Another process uses a receive function to obtain that data.
SY

MPI Functions and Their Role:

The study of MPI focuses on understanding various functions and core concepts related to message-passing:

 Send and Receive Functions: MPI provides different types of send and receive operations, each with
U

specific blocking behaviors, buffering strategies, and performance characteristics. These are fundamental
VT

to achieving effective point-to-point communication.

 Collective Communication: Beyond simple two-process communication, MPI includes functions for
coordinated communication among multiple processes. Examples include broadcasting data from one
process to all others or gathering data from several processes into one.

MPI Functions(Process to Process):

MPI Function Description

MPI_Init Initializes the MPI environment. Must be called before any other MPI function.
MPI_Finalize Terminates the MPI environment. No MPI function can be called after this.
MPI_Comm_size Determines the total number of processes in a communicator.
MPI_Comm_rank Determines the rank (ID) of the calling process in a communicator.
MPI_Send Sends a message (blocking) from one process to another.
MPI_Recv Receives a message (blocking) from another process.

Studied smart, not hard — thanks to [Link]

Fundamental Issues in Message-Passing Programming:
When working with MPI, certain key issues must be addressed to ensure efficient distributed-memory
programming:

 Data Partitioning: Properly dividing and distributing data across multiple processes helps minimize
communication overhead and maximize parallel efficiency.

I/O in Distributed-Memory Systems:

This involves specific considerations for managing input and output operations in environments where each
process maintains its own local memory and I/O streams. Since these resources are not inherently shared among
processes, special techniques are required to coordinate data reading, writing, and synchronization efficiently
across the distributed system.

.IN
Parallel Program Performance:
This focuses on revisiting and applying performance evaluation concepts—such as speedup, efficiency, and
scalability—within the context of MPI programs. Understanding these metrics helps in analyzing how
effectively parallel resources are utilized and how well the program scales with increasing numbers of processes.
C
N
The trapezoidal rule in MPI

The trapezoidal rule is a numerical method used to approximate the area under the curve of a function ( y = f(x)
SY

) between two vertical lines ( x = a ) and ( x = b ).

Basic Idea:
U

1. Divide the interval ([a, b]) into equal subintervals.

2. Approximate the area above each subinterval using a trapezoid.
VT

o The base of each trapezoid corresponds to the subinterval.

o The vertical sides are lines drawn through the endpoints of the subinterval, extending up to the
graph of the function.
o The fourth side is a secant line connecting the two points on the graph at the ends of the
subinterval.

Formulas:

Studied smart, not hard — thanks to [Link]

Pseudo code for Serial Program:

/*Input:a,b,n*/ h
= (b - a) / n;
approx=(f(a)+f(b))/2.0;//Halfoff(a)andhalfoff(b) for (i =
1; i <= n - 1; i++) {
x_i = a+i *h;
approx +=f(x_i);//Addf(x_i)for Intermediate points(counted once)
}
approx=h* approx;//Multiplybyhat theend

.IN
C
N
SY
U
VT

Parallelizing the Trapezoidal Rule

"Parallelizing" refers to the process of transforming a serial program into a parallel one. To achieve this, we
follow a four-step design process:

Parallelizing the Trapezoidal Rule

Studied smart, not hard — thanks to [Link]

"Parallelizing" means converting a serial program into a parallel one. This is done using a four-step design
process:

1. Partition the problem solution into tasks:

o One task type involves calculating the area of a single trapezoid.
o Another task type involves summing all the individual trapezoidal areas.
2. Identify communication channels between tasks:
o Each “calculate trapezoid area” task must send its result to the “sum areas” task for
aggregation.
3. Aggregate tasks into composite tasks:
o Since the number of trapezoids is usually much greater than the number of available cores, the
trapezoid calculations are grouped.
o A practical approach is to divide the total interval ([a, b]) into comm_sz (number of processes)

.IN
subintervals.
o Each process then applies the trapezoidal rule to its assigned subinterval and computes a
C
local_integral.
4. Map composite tasks to cores:
N
o Each of the comm_sz processes calculates a local_integral for its assigned subinterval.
SY

o One process (typically process 0) is designated to collect all local_integral values and sum them
to obtain the total_integral.
U

Simplifying Assumption:
VT

It is assumed that comm_sz (the number of processes) evenly divides n (the total number of trapezoids). This
ensures that each process is responsible for exactly n / comm_sz trapezoids, simplifying the distribution of work
among processes.

Studied smart, not hard — thanks to [Link]

Pseudo code 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;//Startingpointforthisprocess local_b =
local_a + local_n * h; // Ending point for this process

local_integral=Trap(local_a,local_b,local_n,h);//Calculatelocalintegral if
(my_rank != 0)
Sendlocal_integraltoprocess0; else

.IN
/* my_rank == 0 */
total_integral=local_integral;//Process0startswithitsownintegral for
C
(proc = 1; proc < comm_sz; proc++) {
N
Receivelocal_integralfromproc;
total_integral+=local_integral;//Accumulateintegralsfromotherprocesses
SY

}
}
U

if(my_rank==0) print
VT

result;

Variable Naming Convention (Context-Specific):

• Local Variables: Variables whose contents are significant only within the process that uses them (e.g., local_a,
local_b, local_n).

• Global Variables: Variables whose contents are conceptually significant to all processes, even if they each
have their own copies (e.g., a, b, n). This differs from typical serial programming usage (where “global” means
accessible throughout the program), but the context here clarifies the meaning.

MPI Program (Program 3.2): First Version of Trapezoidal Rule

The provided C code demonstrates the parallel implementation of the trapezoidal rule using MPI, with the values
of a, b, and n hardcoded for simplicity.

Studied smart, not hard — thanks to [Link]

The Trap function (Program 3.3, not shown but described as a serial trapezoidal rule implementation) computes
the integral for a specified subinterval.

int main(void){
int my_rank, comm_sz, n = 1024, local_n;
doublea=0.0,b=3.0,h,local_a,local_b;
double local_int, total_int;
intsource;
MPI_Init(NULL, NULL); // Initializes the MPI environment
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);//Gets the rank(ID)of the calling process
MPI_Comm_size(MPI_COMM_WORLD, &comm_sz); // Gets the total number of processes

.IN
h=(b-a) / n;/* h isthesame forall processes */
local_n= n/ comm_sz; /* So is the number of trapezoids per process */

//Determine the local sub interval for this process

C
local_a = a + my_rank * local_n * h;
N
local_b= local_a+local_n * h;
SY

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

(my_rank != 0) {
// All processes except rank 0 send their local integral to rank 0
U

MPI_Send(&local_int,1,MPI_DOUBLE,0,0,MPI_COMM_WORLD);
VT

}else {
//Process rank 0 initializes total_int with its own local integral

total_int = local_int;
//Process rank 0 receives local integrals from all other processes
for (source = 1; source < comm_sz; source++) {
MPI_Recv(&local_int, 1, MPI_DOUBLE, source, 0,
MPI_COMM_WORLD,MPI_STATUS_IGNORE);
total_int+=local_int;//Adds received integral to the total }
}

if(my_rank==0) {
// Only process rank 0 prints the final result
printf("Withn=%dtrapezoids,ourestimate\n",n);

Studied smart, not hard — thanks to [Link]

 printf("of the integral from %f to %f = %.15e\n",
a,b, total_int);
}
MPI_Finalize();//TerminatestheMPIenvironment return
0;
}/* main*/

Dealing with I/O

Dealing with I/O in MPI Programs

The previous version of the parallel trapezoidal rule program had a major limitation: its input parameters (a, b,
and n) were hardcoded. This section explains how to handle user input and output in MPI programs, considering
the challenges that arise in a parallel environment.

.IN
Output
C
In both the "greetings" program and the trapezoidal rule example, it was assumed that process 0 could write to
stdout (using printf) as expected.
N
MPI Standard and Implementations:
SY

While the MPI standard does not explicitly define which processes can access I/O devices, nearly all MPI
implementations allow all processes in MPI_COMM_WORLD to access stdout and stderr.
This means that printf() and fprintf(stderr, ...) can be called by any process.
U

Nondeterminism:
Most MPI implementations do not manage concurrent access to shared I/O devices like stdout. As a result, the
VT

output can become nondeterministic:

 If multiple processes write to stdout at the same time, the order of their outputs becomes unpredictable.
 Sometimes, outputs from different processes may interleave, making the results difficult to read or
interpret.

Example (Program 3.4):

The following simple MPI program demonstrates nondeterministic output:

#include <stdio.h>
#include <mpi.h> // Include MPI header

int main(void) {
int my_rank, comm_sz;

MPI_Init(NULL, NULL); // Initialize MPI

MPI_Comm_size(MPI_COMM_WORLD, &comm_sz); // Get total number of processes
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); // Get rank of current process

// Output statement by each process

printf("Proc %d of %d > Does anyone have a toothpick?\n", my_rank, comm_sz);

Studied smart, not hard — thanks to [Link]

 MPI_Finalize(); // Finalize MPI
return 0;
}

When run with five processes, the output may appear ordered (Proc 0, Proc 1, …). However, with six or more
processes, the order often becomes unpredictable, such as Proc 0, 1, 2, 5, 3, 4. This behavior occurs due to
competition for shared stdout resources.

Handling Nondeterministic Output:

If a predictable or ordered output is required, the programmer must explicitly manage it. A common solution is:

 Have all processes (except process 0) send their output to process 0.

 Let process 0 print all collected output in the desired order (for example, by process rank).
This was the approach used in the "greetings" program.

Input

In contrast to output, most MPI implementations restrict access to standard input (stdin).

.IN
Process 0 Only:
Usually, only process 0 in MPI_COMM_WORLD can access stdin.
This design avoids ambiguity about how input should be distributed—whether lines or characters should be split
among processes. Centralizing input to process 0 simplifies program design.
C
Reading Input in MPI Programs:
N
To handle input (for example, using scanf), programs typically branch based on process rank:
SY

1. Process 0 reads the required input data.

2. Process 0 sends this data to all other processes.

Get_input Function Example (Program 3.5):

U

void Get_input(
int my_rank, /* in */
VT

int comm_sz, /* in */
double* a_p, /* out */
double* b_p, /* out */
int* n_p) { /* out */

int dest;
if (my_rank == 0) {
// Only process 0 interacts with the user
printf("Enter a, b, and n\n");
scanf("%lf %lf %d", a_p, b_p, n_p);

// Send a, b, and n to all other processes

for (dest = 1; dest < comm_sz; dest++) {
MPI_Send(a_p, 1, MPI_DOUBLE, dest, 0, MPI_COMM_WORLD);
MPI_Send(b_p, 1, MPI_DOUBLE, dest, 0, MPI_COMM_WORLD);
MPI_Send(n_p, 1, MPI_INT, dest, 0, MPI_COMM_WORLD);
}
} else {
// Other processes receive a, b, and n from process 0
MPI_Recv(a_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Recv(b_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Recv(n_p, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
}

Studied smart, not hard — thanks to [Link]

This function follows the same communication pattern as the "greetings" program, where process 0 sends data
and all other processes receive it.

Integrating Get_input:
To use this function, call Get_input in the main MPI program after initializing my_rank and comm_sz:

MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
Get_input(my_rank, comm_sz, &a, &b, &n); // Call to get input
h = (b - a) / n; // Calculate h after a, b, n are set

Collective Communication in MPI

In distributed-memory programming using MPI, collective communication refers to operations that involve all
processes within a communicator.
This contrasts with point-to-point communication (such as MPI_Send and MPI_Recv), which involves only two
processes.

Collective communication functions are highly optimized in MPI implementations to make use of underlying

.IN
hardware and network topology. This optimization relieves programmers from manually designing complex
communication patterns.

Improving the Trapezoidal Rule: Beyond Point-to-Point

C
The initial parallel trapezoidal rule program used a simple point-to-point communication approach for the global
N
sum—each process (except process 0) sent its local_integral to process 0, which then summed them up. This
created a bottleneck, as process 0 handled comm_sz - 1 receive operations while other processes remained idle.
SY

Tree-Structured Communication (Manual Approach)

To improve this, we can design more efficient communication patterns. A common method is to use a tree-
U

structured global sum, similar to a binary reduction tree (as illustrated in Figure 3.6). This approach reduces the
communication load on a single process by allowing multiple processes to combine and forward partial results
VT

in a hierarchical manner, leading to better scalability and performance in parallel programs.

Studied smart, not hard — thanks to [Link]

How it works (example with 8 processes):

1. Phase 1: Processes 1, 3, 5, and 7 send their values to processes 0, 2, 4, and 6, respectively. The receiving
processes add the received values to their own. (4 sends and 4 additions occur concurrently.)
2. Phase 2: Processes 2 and 6 send their new sums to processes 0 and 4, respectively. The receivers add the
values. (2 sends and 2 additions occur concurrently.)
3. Phase 3: Process 4 sends its accumulated sum to process 0, which adds the value. (1 send and 1 addition.)

Benefits:
This approach significantly reduces the workload on process 0. In the 8-process example, process 0 performs
only 3 receives and 3 additions, compared to 7 in the original point-to-point scheme. Moreover, many of these
operations happen simultaneously across different processes, improving performance and efficiency.

.IN
Scalability:
For comm_sz processes, the original approach requires (comm_sz - 1) receives and additions on process 0. In
contrast, a tree-structured sum requires only log₂(comm_sz) receives and additions on process 0. This is a major
C
improvement—for example, reducing 1023 operations to just 10 when using 1024 processes.
N
The Challenge of Manual Implementation:
SY

Although efficient, manually implementing tree-structured communication is complex. Many possible tree
configurations exist (for instance, various pairings as shown in Figure 3.7), and the best structure can depend on
the number of processes and the underlying hardware. Developing and testing all these alternatives would be
U

impractical for most application developers.

VT

MPI_Reduce: The General Global Reduction

Studied smart, not hard — thanks to [Link]

Because manually implementing optimal global sum and similar operations is complex, MPI provides collective
communication functions that manage these patterns internally.

This design transfers the responsibility of optimization from the programmer to the MPI library implementers,
who can use their in-depth knowledge of the hardware and system architecture to achieve efficient
communication.

The MPI_Reduce function is a generalized global reduction operation. It performs a specified reduction (such as
sum, maximum, or minimum) across all processes in a communicator and returns the result to a designated
destination process.

Function prototype:

int MPI_Reduce(
void* input_data_p, /* in */

.IN
void* output_data_p, /* out */
int count, /* in */
MPI_Datatype datatype,/* in */
MPI_Op operator, /* in */ C
int dest_process, /* in */
MPI_Comm comm /* in */
);
N
Operation Value Meaning
SY

MPI_MAX Maximum
MPI_MIN Minimum
MPI_SUM Sum
U

MPI_PROD Product
MPI_LAND Logical AND
VT

MPI_BAND Bitwise AND

MPI_LOR Logical OR
MPI_BOR Bitwise OR
MPI_LXOR Logical Exclusive OR
MPI_BXOR Bitwise Exclusive OR
MPI_MAXLOC Maximum and location of maximum
MPI_MINLOC Minimum and location of minimum

• Purpose: MPI_Reduce takes values from all processes in the communicator (comm), applies a specified
operator (such as sum, max, min, or product), and stores the resulting single value on the destination process
(dest_process).

• operator (MPI_Op): This argument is key to the function’s generality. MPI defines several standard reduction
operators (see Table 3.2), including MPI_SUM, MPI_MAX, MPI_MIN, MPI_PROD, MPI_LOR (logical OR),
and MPI_LAND (logical AND). Users can also define their own custom reduction operators if needed.

Studied smart, not hard — thanks to [Link]

• Example (Trapezoidal Rule): In the trapezoidal rule program, the MPI_Send and MPI_Recv loop from Program
3.2 can be replaced by a single MPI_Reduce call:

MPI_Reduce(&local_int, &total_int, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

Each process calls this function and provides its own local_int value. MPI_Reduce internally performs the
summation and stores the final total_int only in the output_data_p variable of process 0.

• Arrays: MPI_Reduce can also operate on arrays by setting the count parameter to the number of elements in
the array.

Collective vs. Point-to-Point Communications (Important Differences)

• Participation:
All processes in the specified MPI communicator (MPI_Comm) must call the same collective function. If one
process calls a collective routine (e.g., MPI_Reduce) while another calls a point-to-point routine (e.g., MPI_Recv
or MPI_Send), the program will behave incorrectly — usually resulting in a hang or crash.

.IN
• Compatible Arguments:
All processes participating in a collective communication must provide compatible arguments. For example, in
C
MPI_Reduce, every process must specify the same destination process (dest_process). If one process specifies
dest_process as 0 and another as 1, the behavior is undefined and will cause an error.
N
SY

OutputBuffer Usage:

The output_data_p argument is only written to on the destination process. However, all processes must still
U

provide a valid argument for output_data_p, even if it is unused or set to NULL for those not receiving the result.
VT

Matching:
• Point-to-point communications are matched by message tags and communicators.
• Collective communications do not use tags. They are matched solely by the communicator and the order of
invocation. This means that the nth collective call in one process must correspond to the nth collective call in all
other participating processes. For example, if process b receives the sum from the first MPI_Reduce call and
process d receives the sum from the second, the matching is determined by call order, not variable names.

Aliasing Restriction:
It is illegal in MPI to use the same buffer for both input_data_p and output_data_p in MPI_Reduce (e.g.,
MPI_Reduce(&x, &x, ...)). MPI forbids aliasing — where two arguments refer to the same memory location —
due to potential conflicts with Fortran’s strict aliasing rules. Violating this rule can lead to unpredictable behavior
such as incorrect results, crashes, or non-portable performance.

Studied smart, not hard — thanks to [Link]

MPI_Allreduce: Result for All Processes
In many cases, all processes need the result of a global reduction rather than just one. While this could be
implemented by combining MPI_Reduce with MPI_Bcast, MPI provides a dedicated function for this purpose:
MPI_Allreduce.

int MPI_Allreduce(
void* input_data_p, /* in */
void* output_data_p, /* out */
int count, /* in */
MPI_Datatype datatype, /* in */
MPI_Op operator, /* in */
MPI_Comm comm /* in */
);

• Difference from MPI_Reduce:

.IN
The argument list of MPI_Allreduce is identical to that of MPI_Reduce, except there is no dest_process
argument, because the final reduced result is stored in the output_data_p of all processes within the
communicator. C
• Benefit:
MPI_Allreduce is designed for efficiency — it allows every process to obtain the same reduction result without
N
extra steps. Internally, MPI_Allreduce implementations are highly optimized to distribute results quickly,
often using reverse tree or butterfly communication patterns (as illustrated in Figures 3.8 and 3.9).
SY

This eliminates the need for a two-step process (first calling MPI_Reduce, then MPI_Bcast), or writing complex
U
VT

manual communication code for result sharing.

Studied smart, not hard — thanks to [Link]

MPI_Bcast (broadcast) is a collective communication operation that distributes data from one source process to
all other processes within a communicator.

int MPI_Bcast(
void* data_p, /* in/out */
int count, /* in */
MPI_Datatype datatype, /* in */
int source_proc, /* in */
MPI_Comm comm /* in */
);

Purpose:
The process with rank source_proc sends the contents of data_p to all other processes in the communicator
comm.

data_p Argument:

.IN
On the source process, data_p acts as an input (it contains the data to be broadcast).
 On all other processes, data_p acts as an output (it receives the data).
This dual role is why data_p is labeled as “in/out” in the function signature.

Example (Get_input modification – Program 3.6):

C
In the trapezoidal rule program, the earlier version used loops with MPI_Send and MPI_Recv to distribute the
input values a, b, and n.
N
Using MPI_Bcast, process 0 can simply:
SY

1. Read a, b, and n from the user.

2. Call MPI_Bcast three times (once for each variable) to send them to all processes efficiently.

This greatly simplifies the code and ensures all processes receive identical data without multiple explicit
U

send/receive calls.
VT

When performing parallel operations on large data structures like vectors, how the data is distributed among
processes is crucial.

Studied smart, not hard — thanks to [Link]

In the case of vector addition (z = x + y), each process needs its portion of x and y to compute its portion of z.
The individual additions of components are the tasks.

For an n-component vector distributed among comm_sz processes, assuming n is divisible by comm_sz, each
process handles local_n = n / comm_sz elements. The partitioning determines which elements each process
operates on.

In block distribution, each process gets a contiguous block of elements. For example, if there are 8 elements and
4 processes: process 0 gets elements 0–1, process 1 gets 2–3, process 2 gets 4–5, and process 3 gets 6–7. This is
the most common method because it minimizes communication overhead.

In cyclic distribution, elements are distributed in a round-robin fashion. For 8 elements and 4 processes: process
0 gets 0 and 4, process 1 gets 1 and 5, process 2 gets 2 and 6, and process 3 gets 3 and 7. This is useful when the
workload per element is uneven or data-dependent.

In block-cyclic distribution, each process receives blocks of consecutive elements in a cyclic order. This hybrid
method balances load when computation per element varies moderately.

.IN
The chosen data distribution affects load balancing, communication cost, and cache locality. Efficient parallel
programs carefully select the distribution scheme based on these trade-offs.
C
1. BlockPartition (Table 3.4,left):Eachprocessgetsacontiguousblockoflocal_ncomponents.
 Process0 getscomponents 0tolocal_n-1.
N
 Process1getscomponentslocal_nto2*local_n-1,andsoon.
SY

2. CyclicPartition (Table 3.4,middle): Componentsareassignedina round-robinfashion.

 Process0 gets components0, comm_sz, 2*comm_sz,etc.
 Process1 gets components1, comm_sz+1, 2*comm_sz+1,etc.
U

3. Block-CyclicPartition(Table3.4,right):Ahybridwhereblocksofbcomponentsareassignedin a cyclic
VT

fashion. (e.g., block 0 to P0, block 1 to P1, block 2 to P2, block 3 to P0, etc.).

In block partitioning, each process gets a contiguous block of local_n components. Process 0 receives
components 0 to local_n - 1, process 1 receives components local_n to 2 * local_n - 1, and so on.

In cyclic partitioning, components are assigned in a round-robin fashion. Process 0 gets components 0, comm_sz,
2 * comm_sz, etc., while process 1 gets components 1, comm_sz + 1, 2 * comm_sz + 1, and so on.

In block-cyclic partitioning, blocks of b components are distributed cyclically among processes—for example,
block 0 to process 0, block 1 to process 1, block 2 to process 2, block 3 to process 0, and so forth. This method
combines the benefits of both block and cyclic distributions.

Once the data is partitioned, each process performs vector addition on its local_n components. The addition loop
is the same as in the serial version but operates only on the data assigned to that process.

When process 0 initially holds the entire vector and needs to distribute different contiguous blocks of that vector
to other processes (as in block distribution for x and y in vector addition), MPI provides the MPI_Scatter
collective communication function.

Studied smart, not hard — thanks to [Link]

int MPI_Scatter(
void* send_buf_p, /* in /
int send_count, / in /
MPI_Datatype send_type, / in /
void recv_buf_p, /* out /
int recv_count, / in /
MPI_Datatype recv_type, / in /
int src_proc, / in /
MPI_Comm comm / in */
);

MPI_Scatter automatically divides the data in send_buf_p on the source process into equal parts and sends one
part to each process, including the sender itself. Each process receives its block into recv_buf_p, making it ideal
for distributing data efficiently in parallel programs.

The purpose of MPI_Scatter is to divide the data referenced by send_buf_p on the source process into comm_sz

.IN
equal parts. The first part is sent to process 0, the second to process 1, and so on. Each process, including the
source process itself, receives its assigned portion into recv_buf_p.

The parameter send_count specifies the number of elements sent to each process, not the total number of
C
elements in send_buf_p.
N
For example, in the Read_vector function (Program 3.9), process 0 reads the entire vector into a buffer. Then,
MPI_Scatter distributes local_n components (where local_n = n / comm_sz) to each process. Each process stores
its received portion in its own local_vector, which only needs enough space for local_n elements.
SY

This straightforward use of MPI_Scatter is intended for block distributions where n is evenly divisible by
comm_sz. For more complex data distributions, such as cyclic or block-cyclic patterns, or when n is not evenly
divisible by comm_sz, more advanced techniques are required to handle the data correctly.
U

#include <stdio.h>
VT

#include <stdlib.h>
#include <mpi.h>

void Read_vector(
double local_a[], /* out */
int local_n, /* in */
int n, /* in */
char vec_name[], /* in */
int my_rank, /* in */
MPI_Comm comm /* in */
){
double* a = NULL;
int i;

if (my_rank == 0) {
a = malloc(n * sizeof(double));
if (a == NULL) {
printf("Memory allocation failed!\n");
MPI_Abort(comm, 1);
}

printf("Enter the vector %s:\n",

Studied smart, not hard — thanks to [Link]

To collect data distributed across multiple processes onto a single process, such as when printing a distributed
vector, MPI provides the MPI_Gather collective communication function.

int MPI_Gather(
void* send_buf_p, /* in /
int send_count, / in /
MPI_Datatype send_type, / in /
void recv_buf_p, /* out /
int recv_count, / in /
MPI_Datatype recv_type, / in /
int dest_proc, / in /
MPI_Comm comm / in */
);

The purpose of MPI_Gather is to gather data from all processes in a communicator and concatenate it into a
single buffer on the destination process. The data from each process’s send_buf_p is sent to the destination
process, where it is stored in recv_buf_p. The gathered data is arranged in rank order—data from process 0

.IN
appears first, followed by data from process 1, process 2, and so on.

This function is particularly useful in parallel programs when combining distributed results into one array for
C
output, further computation, or verification on a single process.
N
The parameter recv_count specifies the number of data items each process contributes to the destination process,
SY

not the total number of items received by the destination. For example, if each process sends local_n items, then
recv_count should be set to local_n. Consequently, the total buffer size required on the destination process for
recv_buf_p must be comm_sz × recv_count to accommodate all incoming data.
U

For instance, in the Print_vector function (Program 3.10), each process provides its local portion of the vector
VT

(local_b). Process 0 allocates a buffer large enough to hold the entire vector, receiving all local portions
concatenated in rank order. This allows the complete vector to be printed or further processed from a single
location.

vector. MPI_Gather collects all local_bs into b on process 0, which then prints the full vector.

Similar to MPI_Scatter, this basic usage of MPI_Gather works correctly primarily for block distributions where
all blocks are the same size.

When all processes need a complete copy of the concatenated dataset—for example, a full vector assembled
from distributed parts—MPI_Allgather is used. This function collects data from all processes and distributes the
combined result to every process in the communicator.

Studied smart, not hard — thanks to [Link]

 .IN
This is especially useful in iterative algorithms, where a global data structure—such as the vector x in matrix-
vector multiplication—must be accessible to all processes in every iteration. Using MPI_Allgather ensures that
each process has the complete, up-to-date data without requiring separate gather and broadcast steps.
C
N
intMPI_Allgather(
void* send_buf_p,/* in */int
SY

send_count,/*in*/
MPI_Datatypesend_type,/*in*/ void*
U

recv_buf_p,/* out */
int recv_count,/* in */
VT

MPI_Datatyperecv_type,/*in*/
MPI_Comm comm /* in */
);

The purpose of MPI_Allgather is to concatenate the contents of each process’s `send_buf_p` and store the
full, concatenated result in every process’s `recv_buf_p`.

The key difference from MPI_Gather is that instead of collecting data to a single destination process,
MPI_Allgather makes the collected data available to all processes in the communicator.

The purpose of MPI_Allgather is to concatenate the contents of each process’s send_buf_p and store the full,
concatenated result in every process’s recv_buf_p.

Studied smart, not hard — thanks to [Link]

The key difference from MPI_Gather is that instead of collecting data to a single destination process,
MPI_Allgather makes the collected data available to all processes in the communicator.

Matrix-Vector Multiplication Example (y = Ax):

 Serial Logic: Each element of y is computed as y[i] = dot_product(A[i_row], x). Computing each y[i]
requires the full vector x.
 Parallel Strategy: The matrix A is distributed by rows (block distribution). Each process gets local_m
rows of A and computes its corresponding local_m components of y.
 The x Problem: To compute its portion of y, each process needs the entire vector x. If x is distributed
across processes, each process initially has only a segment of x.
 Solution with MPI_Allgather: Each process sends its local segment of x, and MPI_Allgather collects all
segments and distributes the complete x vector to every process. This approach avoids using a separate

.IN
MPI_Gather followed by MPI_Bcast and leverages MPI’s internal optimizations for efficiency.

Program 3.12 demonstrates parallel matrix-vector multiplication using MPI_Allgather to ensure all processes
C
have access to the complete x vector.
N
MPI provides mechanisms to handle common data movement and aggregation patterns in parallel programs,
SY

significantly simplifying complex communication logic for application developers.

MPI-derived datatypes
U
VT

MPI derived datatypes optimize communication by reducing the overhead associated with sending multiple
small messages. In distributed-memory systems, communication between nodes is much more expensive than
computation on local data. Sending the same amount of data in many small messages is far costlier than
sending it in a single larger message due to communication overheads like protocol negotiation and packet
headers. For example, sending 1000 doubles individually can be 50 to 100 times slower than sending all 1000
in a single MPI_Send call.

A key goal in MPI programming is to reduce the total number of messages sent. MPI provides three primary
ways to consolidate data for communication:

1. Count argument: This groups contiguous array elements into a single message (e.g., MPI_Send(x, 1000,
MPI_DOUBLE, ...)).
2. Derived datatypes: These allow grouping non-contiguous or mixed-type data into a single logical message.

Studied smart, not hard — thanks to [Link]

3. MPI_Pack/MPI_Unpack: A more manual method to buffer disparate data into a contiguous buffer before
sending.

This section focuses on derived datatypes.

An MPI derived datatype allows you to describe a collection of data items in memory by specifying their
types and relative locations (displacements). Instead of sending individual pieces of data one by one, you
define a single "blueprint" for a complex data structure.

When you use this derived datatype in a communication function like MPI_Send or MPI_Bcast, MPI
automatically interprets the blueprint and transmits the complete structure as a single message, reducing
communication overhead and simplifying code.

.IN
 Sender: The MPI implementation uses the blueprint to gather the specified data items from their scattered
locations in memory into a contiguous buffer (packing) before transmitting them as a single message.
C
 Receiver: The MPI implementation uses the same blueprint to distribute the received data items into their
correct, possibly scattered, destinations in the receiver’s memory (unpacking).
N
SY

For example, in the trapezoidal rule program, we previously had to call MPI_Bcast three times to send a
(double), b (double), and n (int). Using a derived datatype, we can define a single type representing "two doubles
and one int" and use just one MPI_Bcast call.
U

A derived datatype is formally a sequence of basic MPI datatypes, each with a corresponding displacement
VT

(offset from a base address).

Assume a, b, and n are stored at addresses 24, 40, and 48 bytes respectively on process 0:

 a (MPI_DOUBLE) at displacement 0 (relative to itself)

 b (MPI_DOUBLE) at displacement 16 bytes (40 - 24)
 n (MPI_INT) at displacement 24 bytes (48 - 24)

This can be represented as: {(MPI_DOUBLE, 0), (MPI_DOUBLE, 16), (MPI_INT, 24)}.

The function to build such a structured derived datatype is MPI_Type_create_struct:

int MPI_Type_create_struct(
int count, /* in: Number of elements in the datatype */
int array_of_blocklengths[], /* in: Block length for each element */
MPI_Aint array_of_displacements[], /* in: Displacement (bytes) for each element */
MPI_Datatype array_of_types[], /* in: MPI datatype for each element */
MPI_Datatype* new_type_p /* out: Pointer to store the new derived datatype */
);

Studied smart, not hard — thanks to [Link]

Arguments explained for the a, b, n example:

1. count: The number of distinct elements in the datatype. For a, b, n, count = 3.

2. array_of_blocklengths: An array of integers where array_of_blocklengths[i] specifies the number of
occurrences of the i-th type. For scalar elements, the block length is 1.

o Fora,b,n:int array_of_blocklengths[3] ={1,1, 1};

2. array_of_displacements: This is an array of MPI_Aint (a special integer type large enough to hold
memory addresses/offsets), specifying the offset in bytes of each element from the start address of the
first element in the structure.

To get these addresses, use MPI_Get_address:

.IN
int MPI_Get_address(
void* location_p, /* in: Pointer to the variable */
MPI_Aint* address_p /* out: Pointer to store its address */
); C
Example code to get displacements:
N
MPI_Aint a_addr, b_addr, n_addr;
MPI_Get_address(&a, &a_addr);
array_of_displacements[0] = 0; // a is at the base
SY

MPI_Get_address(&b, &b_addr);
array_of_displacements[1] = b_addr - a_addr; // displacement of b from a
MPI_Get_address(&n, &n_addr);
array_of_displacements[2] = n_addr - a_addr; // displacement of n from a
U

3. array_of_types: An array of MPI_Datatypes specifying the MPI type of each element.

For a, b, n:
VT

MPI_Datatype array_of_types[3] = {MPI_DOUBLE, MPI_DOUBLE, MPI_INT};

Putting it together (building the type):

MPI_Datatype input_mpi_t;
// Initialize array_of_blocklengths, array_of_displacements, array_of_types
MPI_Type_create_struct(3, array_of_blocklengths, array_of_displacements, array_of_types,
&input_mpi_t);

Committing and using the derived datatype:

After creating a derived datatype, it must be committed before it can be used in any communication function:

int MPI_Type_commit(MPI_Datatype* new_mpi_t_p /* in/out */);

The purpose of MPI_Type_commit is to allow the MPI implementation to optimize its internal representation of
the new datatype, preparing it for efficient use in communication.

Studied smart, not hard — thanks to [Link]

Once committed, the derived datatype can be used like a basic MPI datatype in communication functions. For
example:

// Process 0 sends the values, others receive

MPI_Bcast(&a, 1, input_mpi_t, 0, comm);

Here, the count argument is 1 because we are sending one instance of the newly defined input_mpi_t datatype,
which itself encapsulates three individual data items.

Derived datatypes may involve internal memory allocation by the MPI library. To release these resources when
the type is no longer needed, use:

int MPI_Type_free(MPI_Datatype* old_mpi_t_p /* in/out */);

This should be called when the derived datatype is no longer required, typically before MPI_Finalize().

These steps can be encapsulated in a helper function, such as Build_mpi_type, which is then used by an updated
Get_input function (Program 3.13). Using derived datatypes in this way simplifies and optimizes I/O and
communication patterns in MPI programs by reducing the number of individual messages.

.IN
Performance evaluation of MPI programs C
Evaluating the performance of parallel programs, particularly those written with MPI, is essential to determine
whether they achieve speedup over their serial counterparts and how efficiently they utilize available parallel
N
resources.
SY

Program: get_input function with a derived datatype

U

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

void Build_mpi_type(
double* a_p, /* in */
double* b_p, /* in */
int* n_p, /* in */
MPI_Datatype* input_mpi_t_p /* out */)
{
int array_of_blocklengths[3] = {1, 1, 1};
MPI_Datatype array_of_types[3] = {MPI_DOUBLE, MPI_DOUBLE, MPI_INT};
MPI_Aint a_addr, b_addr, n_addr;
MPI_Aint array_of_displacements[3];

MPI_Get_address(a_p, &a_addr);
MPI_Get_address(b_p, &b_addr);
MPI_Get_address(n_p, &n_addr);

array_of_displacements[0] = 0;
array_of_displacements[1] = b_addr - a_addr;
array_of_displacements[2] = n_addr - a_addr;

MPI_Type_create_struct(3, array_of_blocklengths,
array_of_displacements,
array_of_types,
input_mpi_t_p);
MPI_Type_commit(input_mpi_t_p);

Studied smart, not hard — thanks to [Link]

}

void Get_input(int my_rank, double* a_p,

double* b_p, int* n_p)
{
MPI_Datatype input_mpi_t;

Build_mpi_type(a_p, b_p, n_p, &input_mpi_t);

if (my_rank == 0) {
printf("Enter a, b, and n: ");
fflush(stdout);
scanf("%lf %lf %d", a_p, b_p, n_p);
}

/* Broadcast the custom structure to all processes */

MPI_Bcast(a_p, 1, input_mpi_t, 0, MPI_COMM_WORLD);

MPI_Type_free(&input

When measuring the performance of parallel programs, the focus is usually on the wall-clock time taken by the

.IN
parallelized portion of the code, rather than the total execution time, which may include I/O, initialization, and
other overheads.

MPI provides the function MPI_Wtime() to measure wall-clock time: C

double MPI_Wtime(void);
N
This function returns the number of seconds elapsed since an arbitrary point in the past, allowing timing of code
sections.
SY

Example usage:

double start, finish;

U

// Code to be timed
start = MPI_Wtime();
VT

/* Parallel section of code */

finish = MPI_Wtime();

The elapsed time for the timed section is then finish - start.

printf("Proc%d>Elapsedtime=%eseconds\n",my_rank,finish -start);

For timing serial code, especially when MPI libraries are not linked, a POSIX function like gettimeofday or a
macro such as GET_TIME (from timer.h) can be used to obtain microsecond-resolution wall-clock time.

Example usage:

#include "timer.h"

double start, finish;

Studied smart, not hard — thanks to [Link]

// Start timing
GET_TIME(start);

/* Code to be timed */

GET_TIME(finish);

printf("Elapsed time = %e seconds\n", finish - start);

GET_TIME is a macro, so it operates directly on its double argument. Make sure the compiler can locate timer.h

if it is not in a standard include path.

Wall-clock time versus CPU time:

.IN
 Wall-clock time (measured with MPI_Wtime or GET_TIME) accounts for the total elapsed time, including
periods when processes are idle or waiting. This is crucial for parallel programs, as operations like
C
MPI_Recv may spend significant time waiting for messages.
N
 CPU time (e.g., C’s clock function) measures only the time the CPU spends executing code, including
user, library, and OS routines, but excludes idle time. This is less informative for parallel performance
SY

analysis because it does not capture communication delays or synchronization waits.

Reporting a single time for parallel programs:

U
VT

Since multiple processes run concurrently, each reports its own local elapsed time. To obtain a meaningful single
measure of parallel execution time, we consider the time taken by the slowest process to finish the timed section.

1. Synchronization: Use MPI_Barrier(comm); before starting the timer on all processes. This ensures all
processes reach the barrier before any proceeds, reducing discrepancies due to varying start times.
2. Global maximum reduction: Each process computes its local elapsed time. Then, use MPI_Reduce with
the MPI_MAX operator to determine the maximum local elapsed time among all processes and store it on
process 0. This maximum represents the overall parallel execution time.

doublelocal_start,local_finish,local_elapsed,elapsed;
// ...
MPI_Barrier(comm);//Ensureallprocessesareready
local_start = MPI_Wtime();

Studied smart, not hard — thanks to [Link]

 /* Code to be timed */
local_finish=MPI_Wtime();
local_elapsed =local_finish -local_start;
MPI_Reduce(&local_elapsed,&elapsed,1,MPI_DOUBLE,MPI_MAX,0,comm);//Findmax
elapsed
if(my_rank==0)
printf("Elapsedtime =%eseconds\n",elapsed);// Onlyprocess0 prints

Variability and reporting:

Timings of parallel programs can vary significantly between runs due to unpredictable interactions with the
operating system and other processes. It is common practice to report the minimum run-time over several runs,
as this usually represents performance on a “quiet” system, minimally affected by external interference.

.IN
Hybrid systems:

When running MPI on multicore nodes, it is common to run only one MPI process per node to reduce contention
for the interconnect. This approach often leads to better and more consistent run-times.
C
Results (Matrix-Vector Multiplication Example):
N
Example run-times for the parallel matrix-vector multiplication can be summarized in a table (e.g., Table 3.5),
SY

illustrating the performance achieved with different numbers of processes.

.
U
VT

Impact of problem size (n):

 As n (the order of the matrix) increases for a fixed number of processes (comm_sz), run-times generally
increase.
 For small comm_sz, doubling n roughly quadruples the run-time, consistent with the O(n²) serial
complexity (since an n × n matrix requires approximately 2n² floating-point operations).
 For large comm_sz, this straightforward relationship starts to break down due to parallel overheads and
communication costs.

Studied smart, not hard — thanks to [Link]

Impact of number of processes (comm_sz):

 As comm_sz increases for a fixed problem size n, run-times usually decrease.

 For large n, doubling comm_sz roughly halves the run-time, indicating good parallel scaling.
 For small n, increasing comm_sz provides little benefit and can even slightly worsen performance. For
example, with n = 1024, increasing comm_sz from 8 to 16 shows minimal change, suggesting that for
small problems, parallel overhead dominates any gains from additional processes.

The Parallel Run-time Formula:

.IN
C
N
p: Number of processes (comm_sz).
SY

T_overhead(n, p): Overhead due to parallelization, including communication, synchronization, and load
imbalance. In MPI programs, a significant portion often comes from communication operations (e.g.,
MPI_Allgather in this case).
U

For small p and large n:

VT

 The term T_serial(n)/p dominates.

 Doubling p roughly halves T_parallel. For example, T_parallel(8192, 2) ≈ 2.0 × T_parallel(8192, 4),
indicating good parallel efficiency.

For large p and small n:

 The T_overhead term dominates.

 Increasing p further provides diminishing returns or can even degrade performance. For example,
T_parallel(1024, 8) versus T_parallel(1024, 16) may show little improvement or a slowdown. The
communication overhead outweighs the benefit of distributing the computation.

Speedup and efficiency:

 These are standard metrics used to quantify parallel performance relative to a serial baseline.

Studied smart, not hard — thanks to [Link]

Scalability describes how a parallel program’s performance changes as the problem size and/or number of
processes increases.

A program is generally considered scalable if the problem size can be increased at a rate that allows efficiency to
remain roughly constant as the number of processes grows.

.IN
Types of scalability:

 Strong scalability: A program is strongly scalable if it can maintain constant efficiency without increasing
C
the problem size as the number of processes increases. For example, if efficiency remains 0.75 regardless
of n or p, the overhead T_overhead is negligible or grows very little with p.

N
Weak scalability: A program is weakly scalable if it can maintain constant efficiency when the problem
size increases proportionally with the number of processes. In this case, the work per process remains
constant, and T_overhead per process also remains relatively constant.
SY

Matrix-vector multiplication scalability:

 The matrix-vector multiplication program is not strongly scalable; efficiency generally decreases as p
U

increases for a fixed n.

 However, it appears weakly scalable. When both n and p are doubled (e.g., from n = 2048, p = 4 to n =
VT

4096, p = 8, or from n = 4096, p = 8 to n = 8192, p = 16), efficiency tends to increase or stay relatively
constant, especially for larger p values.
 This indicates that increasing the problem size proportionally as more resources become available helps
the program maintain efficiency.

A parallel sorting algorithm

A parallel sorting algorithm in a distributed-memory environment aims to sort a collection of keys that are
initially spread across multiple processes. At the end of the algorithm, the sorted keys remain distributed among
the processes in a defined order.

 Input: There are a total of n keys, with each of p processes (comm_sz) initially holding n/p keys
(assuming n is evenly divisible by p). There is no restriction on which keys reside on which process
initially.
 Output: When the algorithm finishes:
1. The n/p keys on each individual process must be sorted (e.g., in increasing order).
2. For any processes q and r with 0 ≤ q < r < p, every key on process q must be less than or equal to
every key on process r. Conceptually concatenating the sorted lists from process 0 to process p – 1
yields the globally sorted list.

Studied smart, not hard — thanks to [Link]

For simplicity, the keys are assumed to be ordinary integers.

Some simple serial sorting algorithms can be useful to review before discussing parallel sorting.

Bubble Sort (Program 3.14): This algorithm sorts an array a of n elements. It repeatedly compares adjacent
elements and swaps them if they are out of order. In each pass, the largest unsorted element "bubbles" to its
correct position at the end of the unsorted portion of the array.

voidBubble_sort(inta[]/*in/out*/,intn/*in*/){ int
list_length, i, temp;
for(list_length=n;list_length>=2;list_length--){ for (i
= 0; i < list_length - 1; i++) {
if(a[i]>a[i+1]){
temp = a[i];a[i]

.IN
= a[i+1];
a[i+1] = temp;
} C
}
N
}
} // Bubble_sort
SY

Parallelism DeficiencyBubble sort is inherently sequential because of the dependencies between compare-and-
swap operations. The order of comparisons is critical for correctness. For example, if a[i-1] = 9, a[i] = 5, and
U

a[i+1] = 7:
VT

 Correct sequence: compare (9,5) → swap → (5,9,7), then compare (9,7) → swap → (5,7,9).
 Incorrect sequence if out of order: compare (5,7) → no swap → (9,5,7), then compare (9,5) → swap →
(5,9,7). The 7 is now incorrectly placed.

This strict ordering makes bubble sort difficult to parallelize effectively.

Odd-Even Transposition Sort (Program 3.15) is a variant of bubble sort that allows more parallelism by
decoupling compare-and-swap operations. It proceeds in phases:

 Even phases: compare-and-swap on pairs (a[0],a[1]), (a[2],a[3]), (a[4],a[5]), …

 Odd phases: compare-and-swap on pairs (a[1],a[2]), (a[3],a[4]), (a[5],a[6]), …

Example with start array 5, 9, 4, 3:

 Even phase: compare (5,9) and (4,3) → swaps produce 5,9,3,4 (4,3 becomes 3,4; 5,9 unchanged)
 Odd phase: compare (9,3) → swap → 5,3,9,4
 Even phase: compare (5,3) and (9,4) → swap → 3,5,4,9
 Odd phase: compare (5,4) → swap → 3,4,5,9 (sorted)

This phased approach allows multiple comparisons to occur in parallel within each phase.

Studied smart, not hard — thanks to [Link]

Theorem: For a list of (n) elements, odd-even transposition sort guarantees a sorted list in at most (n) phases.

Reasoning:

 Each phase (even or odd) moves elements closer to their correct positions.
 In the worst case, the smallest element might need to “bubble” from the last position to the first, requiring
up to (n-1) moves.
 Because each phase allows multiple independent swaps, the process completes in at most (n) phases,
ensuring the entire list is sorted.

This bound is tight for the worst-case initial ordering, but in practice fewer phases may suffice for partially sorted
lists.

voidOdd_even_sort(inta[]/*in/out*/,intn/*in*/){ int
phase, i, temp;
for(phase = 0; phase < n; phase++) {
if(phase%2==0){// Even phase

.IN
for(i=1;i<n;i +=2){//Compare-swap (a[i-1],a[i])fori=1,3,5,... if (a[i-1]
> a[i]) { C
temp=a[i];a[i]=a[i-1];a[i-1]=temp;
}
N
}
SY

}else{ // Odd phase

for(i=1;i<n-1;i+=2){//Compare-swap(a[i],a[i+1])fori=1,3,5,... if (a[i] >
a[i+1]) {
U

temp=a[i];a[i]=a[i+1];a[i+1]=temp;
VT

}
}
}
}
} // Odd_even_sort

In Parallel Odd-Even Transposition Sort, the main advantage is that all compare-and-swap operations within a
single phase can be executed concurrently across multiple processes.

 Each process can handle one or more pairs of elements depending on the data distribution.
 Even phases perform simultaneous compare-swaps on pairs (a[0],a[1]), (a[2],a[3]), …
 Odd phases perform simultaneous compare-swaps on pairs (a[1],a[2]), (a[3],a[4]), …

This parallelism reduces the overall sorting time compared to a purely sequential bubble sort, while maintaining
the correctness guaranteed by the n-phase bound theorem.

Studied smart, not hard — thanks to [Link]

 .IN
Applying Foster’s Methodology to Parallel Odd-Even Transposition Sort:

 Tasks: Each task is responsible for computing the value of a[i] at the end of a given phase j.

C
Communications: A task that computes a[i] must exchange data with its neighbors, a[i-1] and a[i+1],
because compare-swaps depend on adjacent elements. The values from the current phase are required as
N
input for the next phase.
SY

This task-communication mapping helps structure the parallel algorithm efficiently, ensuring that dependencies
are maintained while allowing maximum concurrency within each phase.


U

Case 1: n = p (one key per process)

VT

 Each process holds exactly one key.

 Even phases:
o Process i exchanges its key with process i-1 if i is odd, or with i+1 if i is even.
 Odd phases:
o The pairings are reversed compared to the even phase.
 After exchanging, each process keeps the appropriate key to maintain the locally sorted order.

Problem: This approach is highly inefficient because each process handles only one key, resulting in a large
number of communication steps relative to the amount of work done per process. The communication overhead
dominates, making it impractical for large p.

Case 2: n/p > 1 (multiple keys per process)

This is the more practical scenario for parallel odd-even transposition sort. Each process holds a block of n/p
keys.

1. Local Sort:
o Each process first sorts its n/p local keys using a fast serial sorting algorithm (e.g., qsort).
2. Phased Compare-Exchange (Global Sort):

Studied smart, not hard — thanks to [Link]

 o The algorithm proceeds in phases, similar to serial odd-even sort, but now processes exchange
blocks of keys with their partners.
o In each phase, processes pair up based on their ranks (even-odd or odd-even).
o Each pair of processes (e.g., process q and process r) exchanges their entire local lists of n/p keys.
o After exchanging, each process now has 2 × n/p keys (its own plus its partner’s). They then decide
which n/p keys to keep:
 If my_rank < partner , keep the smaller half of the combined keys.
 If my_rank > partner , keep the larger half of the combined keys.
o This ensures that keys “move” in the correct direction across process boundaries to achieve global
sortedness.

Example (Table 3.8):

 p = 4 processes, n = 16 total keys → 4 keys per process.

 After each phase, keys are partially sorted locally and progressively move toward their globally correct
positions.

.IN
C
N
SY
U

• Phase 1 (Odd): P1 pairs with P2.

VT

 P1 and P2 exchange their 4 keys.

 P1 keeps the smaller half, P2 keeps the larger half.

• Phase 2 (Even): P0 pairs with P1, P2 pairs with P3 again.

 P0 and P1 exchange keys; P0 keeps smaller half, P1 keeps larger half.

 P2 and P3 exchange keys; P2 keeps smaller half, P3 keeps larger half.

• Phase 3 (Odd): P1 pairs with P2 again.

 P1 and P2 exchange keys; P1 keeps smaller half, P2 keeps larger half.

After all phases (n = 16, p = 4 → 4 phases max), each process holds its sorted block, and the global order is
correct.

This demonstrates how local sorting + phased block compare-exchange achieves a fully sorted distribution
across processes.

Studied smart, not hard — thanks to [Link]

Parallel Odd-Even Transposition Sort Algorithm

Theorem: For a list of n keys distributed across p processes, parallel odd-even transposition sort guarantees a
globally sorted list after p phases.

General Algorithm Structure

// Step 1: Local sort
SortLocalKeys(); // e.g., using qsort

// Step 2: Phased compare-exchange

for(phase = 0; phase < comm_sz; phase++) {
partner = Compute_partner(phase, my_rank); // Determine communication partner

if (partner != MPI_PROC_NULL) {
// Exchange keys with partner safely
SafeExchangeKeys(my_keys, partner);

if (my_rank < partner) {

KeepSmallerKeys();
} else {
KeepLargerKeys();

.IN
}
}
}

Computing Partner Rank

int Compute_partner(int phase, int my_rank) {
C
int partner;
N
if (phase % 2 == 0) { // Even phase
if (my_rank % 2 != 0) partner = my_rank - 1;
SY

else partner = my_rank + 1;

} else { // Odd phase
if (my_rank % 2 != 0) partner = my_rank + 1;
else partner = my_rank - 1;
}
U

// Handle boundary processes

VT

if (partner < 0 || partner >= comm_sz) partner = MPI_PROC_NULL;

return partner;
}

Unsafe Communication Pattern

MPI_Send(my_keys, n/comm_sz, MPI_INT, partner, 0, comm);
MPI_Recv(temp_keys, n/comm_sz, MPI_INT, partner, 0, comm, MPI_STATUS_IGNORE);

 Both processes may block simultaneously if message is large, causing deadlock.

Checking Safety

 Replace MPI_Send with MPI_Ssend.

 If program hangs with MPI_Ssend, the original MPI_Send usage was unsafe.

Safe Communication Pattern (Staggered Send/Receive)

if (my_rank % 2 == 0) {
MPI_Send(my_keys, size, MPI_INT, partner, 0, comm);
MPI_Recv(temp_keys, size, MPI_INT, partner, 0, comm, MPI_STATUS_IGNORE);
} else {
MPI_Recv(temp_keys, size, MPI_INT, partner, 0, comm, MPI_STATUS_IGNORE);
MPI_Send(my_keys, size, MPI_INT, partner, 0, comm);
}

Studied smart, not hard — thanks to [Link]

  Ensures at least one process is ready to receive before the other sends, breaking deadlocks.
 Works for both even and odd numbers of processes.

.IN
MPI_Sendrecv: MPI provides a built-in function to safely perform simultaneous send and receive operations.
C
MPI_Sendrecv Overview
N
MPI_Sendrecv combines sending and receiving in a single call, making parallel communication simpler and
safer by preventing deadlocks.
SY

int MPI_Sendrecv(
void* send_buf_p, /* in: buffer to send */
int send_buf_size, /* in: number of elements to send */
MPI_Datatype send_buf_type, /* in: datatype of send buffer */
int dest, /* in: rank of destination process */
U

int send_tag, /* in: message tag for send */

void* recv_buf_p, /* out: buffer to receive into */
VT

int recv_buf_size, /* in: number of elements to receive */

MPI_Datatype recv_buf_type, /* in: datatype of receive buffer */
int source, /* in: rank of source process */
int recv_tag, /* in: message tag for receive */
MPI_Comm communicator, /* in: communicator */
MPI_Status* status_p /* out: status object */
);

Key Points:

1. Performs a blocking send and receive in one atomic call.

2. MPI handles the internal scheduling, so deadlocks caused by simultaneous send/receive operations are
avoided.
3. Replaces complex manual communication patterns like staggered send/receive based on rank parity.

Example in Parallel Odd-Even Transposition Sort:

MPI_Sendrecv(
my_keys, n/comm_sz, MPI_INT, partner, 0,
temp_keys, n/comm_sz, MPI_INT, partner, 0,
comm, MPI_STATUS_IGNORE
);

Studied smart, not hard — thanks to [Link]

  Each process exchanges its block of keys with its partner safely.
 No need for if-else logic based on rank parity.

This approach simplifies the code while ensuring safe and deadlock-free communication.

MPI_Sendrecv(
my_keys, local_n, MPI_INT, partner, 0,
recv_keys, local_n, MPI_INT, partner, 0,
comm, MPI_STATUS_IGNORE
);

local_n = n / comm_sz
my_keys holds the keys to be sent
recv_keys will hold the keys received from the partner

After the MPI_Sendrecv call, each process has:

local_n keys in my_keys (its original keys)
local_n keys in recv_keys (from its partner)

.IN
Both my_keys and recv_keys are locally sorted. Combine these two local arrays and extract the appropriate
local_n keys.

void Merge_low(int my_keys[], int recv_keys[], int temp_keys[], int local_n) {

int m_i, r_i, t_i;
C
m_i = r_i = t_i = 0;
N
while (t_i < local_n) {
if (my_keys[m_i] <= recv_keys[r_i]) {
SY

temp_keys[t_i] = my_keys[m_i];
m_i++;
} else {
temp_keys[t_i] = recv_keys[r_i];
r_i++;
U

}
t_i++;
}
VT

for (m_i = 0; m_i < local_n; m_i++)

my_keys[m_i] = temp_keys[m_i];
}
Called by the process that needs to keep the smaller keys (my_rank < partner).

To keep the larger local_n keys (my_rank > partner), merge from the end of the arrays and take the largest
elements.

Further optimization can avoid copying arrays by swapping pointers if the data is stored strategically.

For comm_sz = 1, the time corresponds to a fast serial sort like quicksort (the initial local sort), not the serial
odd-even sort. Efficient local sorting is important within the parallel framework.

Studied smart, not hard — thanks to [Link]