/*
 * 03-collectives.c  —  Scatter, compute, Reduce: the map-reduce of MPI
 * Session 11 · 2311CSC501J Parallel Processing
 *
 * WHAT THIS SHOWS
 *   You COULD build everything from Send/Recv, but you almost never should.
 *   MPI's COLLECTIVE operations move data among ALL processes at once, and the
 *   library implements them far more efficiently (often in log(P) steps) than a
 *   hand-rolled loop of point-to-point calls.
 *
 *   This program computes the sum of an array, distributed across the processes:
 *     1. MPI_Bcast   — rank 0 announces PER (elements per process) to everyone.
 *     2. MPI_Scatter — rank 0 splits the big array into equal chunks and hands
 *                      one chunk to each process (including a chunk to itself).
 *     3. LOCAL WORK  — every process sums its OWN chunk, in parallel.
 *     4. MPI_Reduce  — the partial sums are combined (MPI_SUM) back onto rank 0.
 *
 *   That is exactly the fan-out / fan-in (map-reduce) pattern: scatter = fan-out
 *   the data, reduce = fan-in the answers.
 *
 *   Other collectives worth knowing (same shape):
 *     MPI_Gather    — the inverse of Scatter: collect chunks back onto one rank.
 *     MPI_Allreduce — like Reduce, but EVERY rank receives the final result.
 *
 * HOW TO COMPILE & RUN
 *       mpicc 03-collectives.c -o collectives
 *       mpirun -np 4 ./collectives
 *   Works for any process count P; the array size is PER * P. Cannot run in a
 *   browser. See README.md for no-install online options.
 */

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

#define PER 5     /* elements each process is responsible for; total = PER * size */

int main(int argc, char **argv) {
    MPI_Init(&argc, &argv);

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int per = PER;
    /* MPI_Bcast: rank 0 (the "root") broadcasts `per` to every process. After
     * this line, all processes hold the same value. Everyone calls Bcast. */
    MPI_Bcast(&per, 1, MPI_INT, 0, MPI_COMM_WORLD);

    int total = per * size;     /* full array length */

    /* Only rank 0 builds and owns the full array. The others pass NULL — they
     * will only ever see their own scattered chunk. */
    int *data = NULL;
    if (rank == 0) {
        data = (int *) malloc(total * sizeof(int));
        printf("[rank 0] full array of %d elements: ", total);
        for (int i = 0; i < total; i++) {
            data[i] = i + 1;                 /* values 1, 2, 3, ... total */
            printf("%d ", data[i]);
        }
        printf("\n");
        /* Correct answer, for checking: 1+2+...+total = total*(total+1)/2. */
        printf("[rank 0] expected total = %d\n", total * (total + 1) / 2);
    }

    /* Each process receives `per` elements into its own small buffer. */
    int *chunk = (int *) malloc(per * sizeof(int));

    /* MPI_Scatter(sendbuf, sendcount_PER_PROC, sendtype,
     *             recvbuf, recvcount,          recvtype, root, comm)
     * Rank 0's `data` is sliced into `size` pieces of `per` ints; piece k goes
     * to rank k. Non-root ranks ignore the send arguments. */
    MPI_Scatter(data, per, MPI_INT,
                chunk, per, MPI_INT,
                0, MPI_COMM_WORLD);

    /* STEP: every process sums its own chunk — this is the parallel work. */
    int local_sum = 0;
    for (int i = 0; i < per; i++) local_sum += chunk[i];
    printf("[rank %d] my chunk sums to %d\n", rank, local_sum);

    /* MPI_Reduce combines every process's `local_sum` with MPI_SUM and places
     * the grand total into `global_sum` on the root (rank 0) only. */
    int global_sum = 0;
    MPI_Reduce(&local_sum, &global_sum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

    if (rank == 0) {
        printf("[rank 0] REDUCED total across all %d processes = %d\n",
               size, global_sum);
    }

    free(chunk);
    if (rank == 0) free(data);

    MPI_Finalize();
    return 0;
}