Implementing a wave algorithm in MPI involves creating a pattern where each process communicates with its neighbors in a specific sequence.

This can be used to model wave-like propagation of information across the processes.

In this example, let's consider a simple scenario where each process sends a message to its next neighbor, waits to receive a message from its previous neighbor, and then sends a confirmation back.

This pattern creates a “wave” of communication that passes through the processes from start to end and then back. It's a basic representation of wave algorithms commonly used in parallel computing for synchronization and data propagation.

mpi-wave-algorithm.c

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);
 
    int world_rank, world_size;
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);
 
    int token;
 
    // Create a wave of communication from the first to the last process
    if (world_rank != 0) {
        MPI_Recv(&token, 1, MPI_INT, world_rank - 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        printf("Process %d received token %d from process %d\n", world_rank, token, world_rank - 1);
    } else {
        // Start the wave
        token = -1;
    }
 
    MPI_Barrier(MPI_COMM_WORLD);
 
    if (world_rank != world_size - 1) {
        token++;
        MPI_Send(&token, 1, MPI_INT, world_rank + 1, 0, MPI_COMM_WORLD);
        printf("Process %d sent token %d to process %d\n", world_rank, token, world_rank + 1);
    }
 
    // Create a wave of confirmation back from the last to the first process
    if (world_rank != world_size - 1) {
        MPI_Recv(&token, 1, MPI_INT, world_rank + 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        printf("Process %d received confirmation %d from process %d\n", world_rank, token, world_rank + 1);
    }
 
    MPI_Barrier(MPI_COMM_WORLD);
 
    if (world_rank != 0) {
        MPI_Send(&token, 1, MPI_INT, world_rank - 1, 0, MPI_COMM_WORLD);
        printf("Process %d sent confirmation %d to process %d\n", world_rank, token, world_rank - 1);
    }
 
    MPI_Finalize();
    return 0;
}

The program starts with the first process initializing the wave by sending a token to the next process.

Each process waits to receive the token from its previous neighbor, prints a message, and then sends the token to its next neighbor.

After reaching the last process, a confirmation wave is sent back in the reverse order.

Each process in the reverse wave receives a confirmation token from its next neighbor and sends it to its previous neighbor.

MPI_Barrier is used to synchronize processes between the forward and reverse waves.

This implementation demonstrates a basic wave algorithm where communication flows from the first to the last process and then back. The output will show the flow of tokens and confirmations through the processes.