MPI Derived Datatypes
A derived datatype is an MPI construct that allows a user to define a pattern of
memory locations that may not be contiguous and treat that pattern as a single
unit of data for communication operations.
Key Concepts
Non-Contiguous Data: The primary use is for data that is not stored contiguously
in memory, such as a column of a matrix stored in row-major order, a row of a
matrix in column-major order, or the elements of a C struct with internal
padding.
Controlling Communication: Derived datatypes enable a single MPI communication
call (like MPI_Send or MPI_Recv) to handle multiple, non-contiguous data items,
which is generally more efficient than making many separate communication calls.
Packing/Unpacking: The MPI library handles the complexity of gathering the non-
contiguous data into a single, contiguous buffer for transmission (the packing
operation) and scattering it to the correct memory locations upon receipt (the
unpacking operation).
The following functions are used to create derived datatypes from basic MPI
types:
MPI_Type_contiguous: Used to create a datatype that is simply a contiguous
sequence of a base datatype.
MPI_Type_vector: Used to specify a regularly strided pattern of data. This is
typically useful for communicating a column of a matrix.
MPI_Type_indexed: Used to specify blocks of data with non-regular spacing or
displacements.
MPI_Type_struct: The most general and flexible constructor, used to combine
elements of different base types and arbitrary displacements. This is typically
used to communicate C structs or records.
Lifecycle
After a derived datatype is constructed using one of the above functions, it
must be made ready for use by calling:
MPI_Type_commit: This function makes the new datatype handle available for use
in subsequent communication operations.
Performance Evaluation of MPI Programs
The performance evaluation of MPI programs focuses on measuring how effectively
an algorithm is parallelized and how efficiently the parallel system (hardware
and MPI implementation) utilizes its resources.
The primary goal of parallel programming is to achieve a shorter execution time
than the best sequential program. Key metrics quantify this improvement:
1. Speedup (psi)Speedup is the ratio of the execution time of the best serial
algorithm (T(n, 1)) to the execution time of the parallel algorithm on p
processors (T(n, p)).
psi = T(n,1)/T(n,p)
Ideally, the speedup should be close to the number of processors
2. Efficiency (epsilon): Efficiency measures the fraction of time that the
processors are usefully employed in the parallel computation.
e(n,p)=psi/p
A value of epsilon = 1 (or 100%) indicates perfect speedup, meaning all
processors are utilized fully and no time is lost to parallel overhead.
Performance Laws and Models
1. Amdahl's LawAmdahl's Law provides the theoretical maximum speedup possible
for a fixed problem size (n) when using p processors. It is based on the
fraction of the computation that must be performed sequentially (f).
psi<=1/f+(1-f)/p
2. Gustafson-Barsis's LawAlso known as scaled speedup, this law addresses the
case where the problem size ($n$) is allowed to increase with the number of
processors (p).Formula: Given the fraction of total execution time spent in
serial code ($s$) when running on p processors:
psi<=p+(1-p)s
3. Karp-Flatt Metric ($e$)This metric provides an experimentally determined
serial fraction ($e$) based on the measured speedup ($\psi$) on $p$ processors.
It helps diagnose whether poor performance is due to inherently sequential code
or parallel overhead.
e=(1/psi-1/p)/(1-1/p)
4. Isoefficiency RelationThe Isoefficiency Relation determines how quickly the
problem size (T(n, 1)) must be increased as the number of processors ($p$)
increases to maintain a constant efficiency ($\epsilon$).Constraint: For
efficiency to remain constant, the sequential execution time T(n, 1) must
satisfy:
T(n, 1) >= [Link](n, p)
Parallel Sorting Algorithm
Parallel Quicksort
The parallel version of Quicksort is effective on distributed memory machines
where the data is initially partitioned across $p$ processors. It uses the
principle of recursion and message passing to sort the array.
1. Initial Partitioning (Scatter)
The root process (usually rank 0) typically holds the initial unsorted list.
The data is divided into $p$ roughly equal-sized chunks.
The root process distributes one chunk to each of the $p$ processes using an
operation like MPI_Scatter.
2. Local Sort
Each of the $p$ processes, working independently and in parallel, runs a highly
optimized sequential sort (like the sequential quicksort algorithm) on its local
chunk of data. This is a local computation phase with no communication overhead.
3. Parallel Recursive Partitioning (The Pivot Step)
The core parallel phase recursively divides the processor set (and the data)
into two groups until each process has a final, sorted sub-list. This typically
involves log_2 p stages.
Select Pivot: A pivot element is chosen to partition the entire data set. This
is often done by having one process select a pivot and broadcast it to all other
processes.
Local Partition: Each process partitions its entire local chunk into two sub-
lists:Low List ($L$): Elements less than or equal to the [Link] List ($R$):
Elements greater than the pivot.
Data Exchange and Redistribution:
The processors are logically divided into two groups, usually based on their
rank (e.g., lower half and upper half).
Lower-half processes send their High List ($R$) to a partner process in the
upper half.
Upper-half processes send their Low List ($L$) to a partner process in the lower
half.
After the exchange, each lower-half process only has elements $\le$ the pivot,
and each upper-half process only has elements $>$ the pivot.
Recursion: The two groups of processors independently and recursively repeat the
partition-and-exchange process on their new, combined lists until the groups can
no longer be divided (i.e., until the group size is 1).
4. Final ResultAfter the $\log_2 p$ stages of parallel partitioning are
complete, the entire array is sorted across all processors. The final sorted
array can be assembled by having each process send its final, sorted sub-list
back to the root process (rank 0) using an operation like MPI_Gather or by
having the data stay distributed if the next stage of the parallel program can
use the partitioned data.