Subversion Repositories programming

/*******************************************************************************
 * hw4_prob1.c - implement a partitioning algorithm for Problem 1 of
 *               CS370 Homework #4.
 ******************************************************************************/

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

const int ROOT_NODE = 0;

#define TAG_LESS_NUM  0xaaaa
#define TAG_LESS_DATA 0xbbbb
#define TAG_MORE_NUM  0xcccc
#define TAG_MORE_DATA 0xdddd

int main (int argc, char *argv[])
{
    int myid, p;

    const int n = 1000; // or whatever you want

    int *array;
    int *less, *more;

    int i,j,k;
    int seed;
    int recv_num;

    MPI_Status status;

    MPI_Init (&argc, &argv);
    MPI_Comm_rank (MPI_COMM_WORLD, &myid);
    MPI_Comm_size (MPI_COMM_WORLD, &p);

    if (myid == ROOT_NODE)
    {
        // Allocate n elements in array[]
        array = allocate (n);

        // Initialize the elements in array[]

        seed = array[0];
    }
    else
    {
        // Allocate n/p elements in array[]
        array = allocate (n/p);
    }

    // Allocate n/p elements in less[] and more[]
    less = allocate (n/p);
    more = allocate (n/p);

    // Send the seed to everyone
    MPI_Bcast (&seed, 1, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    // Block partition to each process
    MPI_Scatter (array, n/p, MPI_INT, array, n/p, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    j=0; // "less" index
    k=0; // "more" index

    for (i=0; i<n/p; i++)
    {
        if (array[i] < seed)
        {
            less[j] = array[i];
            j++;
        }
        else if (array[i] > seed)
        {
            more[k] = array[i];
            k++;
        }
    }

    if (myid == ROOT_NODE)
    {
        // Copy j elements from less[] into array[] (root node only)
        memcpy (array, less, j*sizeof(int));

        // recieve "less" array from each node, in turn
        for (i=1; i<p; i++)
        {
            MPI_Recv (&recv_num, 1, MPI_INT, i, TAG_LESS_NUM, MPI_COMM_WORLD, &status);
            MPI_Recv (&array[j], recv_num, MPI_INT, i, TAG_LESS_DATA, MPI_COMM_WORLD, &status);
            j += recv_num; // update index
        }

        // Copy k elements from more[] into array[] (root node only)
        memcpy (array, more, (n-k)*sizeof(int));
        k = n-k;

        // recieve "more" array from each node, in turn
        for (i=1; i<p; i++)
        {
            MPI_Recv (&recv_num, 1, MPI_INT, i, TAG_MORE_NUM, MPI_COMM_WORLD, &status);
            k -= recv_num;
            MPI_Recv (&array[k], recv_num, MPI_INT, i, TAG_MORE_DATA, MPI_COMM_WORLD, &status);
        }

        // Since we've got every element > seed and
        // every element < seed, so the only thing remaining
        // is the seed itself (possibly more than 1)
        while (j < k)
        {
            array[j] = seed;
            j++;
        }
    }
    else
    {
        // Send the "less" array
        MPI_Send (&j, 1, MPI_INT, 0, TAG_LESS_NUM, MPI_COMM_WORLD);
        MPI_Send (less, j, MPI_INT, 0, TAG_LESS_DATA, MPI_COMM_WORLD);

        // Send the "more" array
        MPI_Send (&k, 1, MPI_INT, 0, TAG_MORE_NUM, MPI_COMM_WORLD);
        MPI_Send (more, k, MPI_INT, 0, TAG_MORE_DATA, MPI_COMM_WORLD);
    }

    if (myid == ROOT_NODE)
    {
        // Print the results, or whatever you want
        // to do with the data here
    }

    // Free all of the memory we used
    free (less);
    free (more);
    free (array);

    MPI_Finalize ();
    return 0;
}