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;

}