MPI Pipeline Vector Sort

Let's implement a pipeline-based sorting algorithm using MPI.

In this scenario, we have n + 1 MPI processes: 1 master and n workers.
Each worker will eventually hold one number from the original unsorted array, and the array will be sorted in ascending order across the ranks of the workers.

Here's how we can approach this:

Master Process: The master process initializes the array and sends one element to each worker.

Worker Processes: Each worker initially holds a placeholder value (like -1). They will receive a number from the previous rank, compare it with their stored value, and pass the appropriate number to the next rank.

Sorting Logic: If a received number is less than the stored value, the worker updates its stored value and passes the old value to the next rank. If the received number is greater or equal, the worker simply passes it on.

Completion: The algorithm completes when all workers have their final values, and these values are in ascending order across the ranks.

pipeline-vector-sort.c

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
 
#define MASTER 0
 
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);
 
    // Assuming the size of the array is world_size - 1
    int n = world_size - 1;
    int *array;
 
    // Master process
    if (world_rank == MASTER) {
        array = (int*) malloc(n * sizeof(int));
 
        // Initialize the array with random numbers
        for (int i = 0; i < n; i++) {
            array[i] = rand() % 100; // Random numbers between 0 and 99
        }
 
        // Send each element to the corresponding worker
        for (int i = 1; i <= n; i++) {
            MPI_Send(&array[i-1], 1, MPI_INT, i, 0, MPI_COMM_WORLD);
        }
 
        free(array);
    } 
    // Worker processes
    else {
        int value = -1; // Initial placeholder value
        int received;
 
        for (int i = 0; i < n - world_rank + 1; i++) {
            MPI_Recv(&received, 1, MPI_INT, world_rank - 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
 
            if (received < value || value == -1) {
                int temp = value;
                value = received;
                received = temp;
            }
 
            if (world_rank < world_size - 1) {
                MPI_Send(&received, 1, MPI_INT, world_rank + 1, 0, MPI_COMM_WORLD);
            }
        }
 
        // Final value for this worker
        printf("Worker %d final value: %d\n", world_rank, value);
    }
 
    MPI_Finalize();
    return 0;
}

The master process initializes an array with random numbers and distributes each number to a worker.

Each worker, starting with rank 1, receives a number, compares it with its current value, and sends the appropriate number to the next worker.

This process continues until each worker has its final sorted value.

The workers print their final values, which should be in sorted order across the ranks.

You should specify the number of processes (n + 1, where n is the size of the array to be sorted). The output should display the sorted elements, each held by a different worker.