Voltar

## Implementação do sample sort em C utilizando MPI - Estrutura de dados

0 Curtidas
```/*********************************************************************
Objective      : To sort unsorted integers by sample sort algorithm
Write a MPI program to sort n integers, using sample
sort algorithm on a p processor of PARAM 10000.
Assume n is multiple of p. Sorting is defined as the
task of arranging an unordered collection of elements
into monotonically increasing (or decreasing) order.

postcds: array[] is sorted in ascending order ANSI C
provides a quicksort function called qsort(). Its
function prototype is in the standard header file

Description    : 1. Partitioning of the input data and local sort :

The first step of sample sort is to partition the data.
Initially, each one of the p processors stores n/p
elements of the sequence of the elements to be sorted.
Let Ai be the sequence stored at processor Pi. In the
first phase each processor sorts the local n/p elements
using a serial sorting algorithm. (You can use C
library qsort() for performing this local sort).

2. Choosing the Splitters :

The second phase of the algorithm determines the p-1
splitter elements S. This is done as follows. Each
processor Pi selects p-1 equally spaced elements from
the locally sorted sequence Ai. These p-1 elements
from these p(p-1) elements are selected to be the
splitters.

3. Completing the sort :

In the third phase, each processor Pi uses the splitters
to partition the local sequence Ai into p subsequences
Ai,j such that for 0 <=j
#include
#include

#include "mpi.h"

#define SIZE 10

/**** Function Declaration Section ****/

static int intcompare(const void *i, const void *j)
{
if ((*(int *)i) > (*(int *)j))
return (1);
if ((*(int *)i) < (*(int *)j))
return (-1);
return (0);
}

main (int argc, char *argv[])
{
/* Variable Declarations */

int          Numprocs,MyRank, Root = 0;
int          i,j,k, NoofElements, NoofElements_Bloc,
NoElementsToSort;
int          count, temp;
int          *Input, *InputData;
int          *Splitter, *AllSplitter;
int          *Buckets, *BucketBuffer, *LocalBucket;
int          *OutputBuffer, *Output;
FILE          *InputFile, *fp;
MPI_Status  status;

/**** Initialising ****/

MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &Numprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &MyRank);

if(argc != 2) {
if(MyRank ==0) printf(" Usage : run size\n");
MPI_Finalize();
exit(0);
}

if (MyRank == Root){

NoofElements = atoi(argv[1]);
Input = (int *) malloc (NoofElements*sizeof(int));
if(Input == NULL) {
printf("Error : Can not allocate memory \n");
}

/* Initialise random number generator  */
printf ( "Input Array for Sorting \n\n ");
srand48((unsigned int)NoofElements);
for(i=0; i< NoofElements; i++) {
Input[i] = rand();
printf ("%d   ",Input[i]);
}
}
printf ( "\n\n ");

/**** Sending Data ****/
MPI_Bcast (&NoofElements, 1, MPI_INT, 0, MPI_COMM_WORLD);
if(( NoofElements % Numprocs) != 0){
if(MyRank == Root)
printf("Number of Elements are not divisible by Numprocs \n");
MPI_Finalize();
exit(0);
}

NoofElements_Bloc = NoofElements / Numprocs;
InputData = (int *) malloc (NoofElements_Bloc * sizeof (int));

MPI_Scatter(Input, NoofElements_Bloc, MPI_INT, InputData,
NoofElements_Bloc, MPI_INT, Root, MPI_COMM_WORLD);

/**** Sorting Locally ****/
qsort ((char *) InputData, NoofElements_Bloc, sizeof(int), intcompare);

/**** Choosing Local Splitters ****/
Splitter = (int *) malloc (sizeof (int) * (Numprocs-1));
for (i=0; i< (Numprocs-1); i++){
Splitter[i] = InputData[NoofElements/(Numprocs*Numprocs) * (i+1)];
}

/**** Gathering Local Splitters at Root ****/
AllSplitter = (int *) malloc (sizeof (int) * Numprocs * (Numprocs-1));
MPI_Gather (Splitter, Numprocs-1, MPI_INT, AllSplitter, Numprocs-1,
MPI_INT, Root, MPI_COMM_WORLD);

/**** Choosing Global Splitters ****/
if (MyRank == Root){
qsort ((char *) AllSplitter, Numprocs*(Numprocs-1), sizeof(int), intcompare);

for (i=0; i<Numprocs-1; i++)
Splitter[i] = AllSplitter[(Numprocs-1)*(i+1)];
}

MPI_Bcast (Splitter, Numprocs-1, MPI_INT, 0, MPI_COMM_WORLD);

/**** Creating Numprocs Buckets locally ****/
Buckets = (int *) malloc (sizeof (int) * (NoofElements + Numprocs));

j = 0;
k = 1;

for (i=0; i<NoofElements_Bloc; i++){
if(j < (Numprocs-1)){
if (InputData[i] < Splitter[j])
Buckets[((NoofElements_Bloc + 1) * j) + k++] = InputData[i];
else{
Buckets[(NoofElements_Bloc + 1) * j] = k-1;
k=1;
j++;
i--;
}
}
else
Buckets[((NoofElements_Bloc + 1) * j) + k++] = InputData[i];
}
Buckets[(NoofElements_Bloc + 1) * j] = k - 1;

/**** Sending buckets to respective processors ****/

BucketBuffer = (int *) malloc (sizeof (int) * (NoofElements + Numprocs));

MPI_Alltoall (Buckets, NoofElements_Bloc + 1, MPI_INT, BucketBuffer,
NoofElements_Bloc + 1, MPI_INT, MPI_COMM_WORLD);

/**** Rearranging BucketBuffer ****/
LocalBucket = (int *) malloc (sizeof (int) * 2 * NoofElements / Numprocs);

count = 1;

for (j=0; j<Numprocs; j++) {
k = 1;
for (i=0; i<BucketBuffer[(NoofElements/Numprocs + 1) * j]; i++)
LocalBucket[count++] = BucketBuffer[(NoofElements/Numprocs + 1) * j + k++];
}
LocalBucket[0] = count-1;

/**** Sorting Local Buckets using Bubble Sort ****/
/*qsort ((char *) InputData, NoofElements_Bloc, sizeof(int), intcompare); */

NoElementsToSort = LocalBucket[0];
qsort ((char *) &LocalBucket[1], NoElementsToSort, sizeof(int), intcompare);

/**** Gathering sorted sub blocks at root ****/
if(MyRank == Root) {
OutputBuffer = (int *) malloc (sizeof(int) * 2 * NoofElements);
Output = (int *) malloc (sizeof (int) * NoofElements);
}

MPI_Gather (LocalBucket, 2*NoofElements_Bloc, MPI_INT, OutputBuffer,
2*NoofElements_Bloc, MPI_INT, Root, MPI_COMM_WORLD);

/**** Rearranging output buffer ****/
if (MyRank == Root){
count = 0;
for(j=0; j<Numprocs; j++){
k = 1;
for(i=0; i<OutputBuffer[(2 * NoofElements/Numprocs) * j]; i++)
Output[count++] = OutputBuffer[(2*NoofElements/Numprocs) * j + k++];
}

/**** Printng the output ****/
if ((fp = fopen("sort.out", "w")) == NULL){
printf("Can't Open Output File \n");
exit(0);
}

fprintf (fp, "Number of Elements to be sorted : %d \n", NoofElements);
printf ( "Number of Elements to be sorted : %d \n", NoofElements);
fprintf (fp, "The sorted sequence is : \n");
printf( "Sorted output sequence is\n\n");
for (i=0; i<NoofElements; i++){
fprintf(fp, "%d\n", Output[i]);
printf( "%d   ", Output[i]);
}
printf ( " \n " );
fclose(fp);
free(Input);
free(OutputBuffer);
free(Output);
}/* MyRank==0*/

free(InputData);
free(Splitter);
free(AllSplitter);
free(Buckets);
free(BucketBuffer);
free(LocalBucket);

/**** Finalize ****/
MPI_Finalize();
}```

Fonte