Obsidian + 🪴 Quartz 4.0

HPC - Lecture 9 - Collective communication and topologies (REVISE)

5 min read

HPC - Lecture 9 - Collective communication and topologies

Ring Algorithm

MPI_Send and MPI_Recv are the main functions for transferring information between MPI processes (point-to-point communication). Using these functions, a ring algorithm can be implemented to sum values across different processes.

token = sum;
for (i = 1; i < nproc; i++) {
    MPI_Send(&token, 1, MPI_INT, (myid + nproc + 1) % nproc, 10, MPI_COMM_WORLD);
    MPI_Recv(&token, 1, MPI_INT, (myid + nproc - 1) % nproc, 10, MPI_COMM_WORLD, &status);
    sum = sum + token;
}

This communication pattern, known as a shift among processes, is common in many parallel applications.

Deadlock in Point-to-Point Communication

When the message size is large enough (e.g., integers), processes may deadlock. A deadlock is a situation where each process waits for another to complete communication before proceeding.

Under the hood, MPI_Send behavior depends on the message size relative to the system buffer:

  • Buffered: For small sizes, data is copied into a system buffer and MPI_Send returns immediately. This incurs overhead due to copying but prevents immediate blocking.
  • Synchronous: For large sizes, data is copied directly into the receive buffer. MPI_Send returns only when the message has been received. This has less overhead but requires the matching MPI_Recv to be ready.

If all processes call a synchronous MPI_Send simultaneously, they will all wait for an MPI_Recv that can only be executed after the send completes, resulting in a deadlock.

Solutions for Deadlock

  • Solution 1 (Ordering): Alternate the order of send/receive based on the process ID (e.g., even ranks send then receive, odd ranks receive then send).
  • Solution 2 (MPI_Sendrecv): Use MPI_Sendrecv, which combines the simultaneous sending and receipt of messages into a single function.
int MPI_Sendrecv(void *Sdata, int Scount, MPI_Datatype Sdatatype, int dest, int Stag,
                 void *Rdata, int Rcount, MPI_Datatype Rdatatype, int source, int Rtag,
                 MPI_Comm comm, MPI_Status *status)

Collective Communication

Collective operations involve groups of processes. They are blocking functions (they return when all processes have finished).

Broadcast

MPI_Bcast sends the contents of the root process’s data to all processes in the same communicator (one-to-all).

int MPI_Bcast(void *data, int count, MPI_Datatype datatype, int root, MPI_Comm comm)

Cost: Collective operations implement cascade algorithms. The cost is:

Scatter and Gather

  • MPI_Scatter: Sends contiguous data from the root process to all processes in order of rank (one-to-all).
  • MPI_Gather: Collects values from a group of processes into the root process (all-to-one).
int MPI_Scatter(void *Sbuf, int Scount, MPI_Datatype Stype, void *Rbuf, int Rcount, MPI_Datatype Rtype, int root, MPI_Comm comm)
int MPI_Gather(void *Sbuf, int Scount, MPI_Datatype Stype, void *Rbuf, int Rcount, MPI_Datatype Rtype, int root, MPI_Comm comm)

Barrier and Reduction

  • MPI_Barrier: Blocks the calling process until all processes with the same communicator have made the call.
  • MPI_Reduce: Performs a global arithmetic or logical operation between values and collects them into the root process.
  • MPI_Allreduce: Performs the reduction and distributes the result to all processes (all-to-all).

MPI Reduction Operations:

  • MPI_MAX, MPI_MIN, MPI_SUM, MPI_PROD
  • MPI_LAND (logical and), MPI_BAND (bitwise and)
  • MPI_LOR (logical or), MPI_BOR (bitwise or)

Associativity

All reduction operations must be associative. Note that floating-point addition is not strictly associative; the result may vary depending on the summation order across algorithm steps.

Virtual Topologies

In the default MPI_COMM_WORLD, processes are not organized into structures. Virtual topologies (rings, grids) allow for logical organization based on the problem’s geometric characteristics. These have no relation to the physical cluster interconnection.

Grid Topology

Processes in a grid exchange data only with neighbors:

  • 1D Grid (Ring): 2 neighbors.
  • 2D Grid: 4 neighbors.
  • 3D Grid: 6 neighbors.

MPI Cartesian Functions

  • MPI_Cart_create: Creates a grid of processes and assigns a new communicator.
  • MPI_Cartdim_get: Returns the number of directions (dimensions) in the grid.
  • MPI_Cart_get: Returns the number of jobs in each direction, periodicity, and coordinates of the calling process.
  • MPI_Cart_sub: Creates communicators for groups of processes (e.g., along rows or columns).
int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart)
int MPI_Cart_sub(MPI_Comm comm, int *directions, MPI_Comm subcomm)

In MPI_Cart_sub, directions[i] = 1 indicates that direction belongs to the subgrid.

Graph View