psrs.zip_3NE_PSRS_PSRS MPI_mpi psrs_parallel computing

#include <stdio.h> #include <stdlib.h> #include <mpi.h> #define INIT_TYPE 10 #define ALLTOONE_TYPE 100 #define ONETOALL_TYPE 200 #define MULTI_TYPE 300 #define RESULT_TYPE 400 #define RESULT_LEN 500 #define MULTI_LEN 600 int Spt; //< Separator, it is NumOfProcesses - 1 long DataSize; //< the number of elements in total int *arr, //< this array stores the elements to be sorted, size [DataSize*2] *arr1; //< the 50% position of 'arr', which stores the data gathered from other process int mylength; //< the number of elements distributed to one process int *index; //< index[2*i] and [2*i-1] is the index of element in 'arr' which >= temp1[i] int *temp1; /*< this array firstly stores the sample elements picked up in one process, size [SumID*Spt]. after step 6, it stores the number of elements of each segment in one process */ main(int argc,char* argv[]) { long BaseNum = 1; int PlusNum; int MyID; // initialize the MPI environment MPI_Init(&argc,&argv); // get the rank of this process MPI_Comm_rank(MPI_COMM_WORLD,&MyID); PlusNum = 60; // count the total number of elements to be sort DataSize = BaseNum*PlusNum; if (MyID==0) printf("The DataSize is : %lu\n",PlusNum); // the main process Psrs_Main(); if (MyID==0) printf("\n"); // ready to finish the MPI process MPI_Finalize(); } Psrs_Main( ) { int i,j; int MyID, //< the ID of current process SumID; //< the number of all the process int n, //< there n segments in each process c1,c2,c3,c4, k, //< the pointer of arr1, which stores the data gather from other process l; FILE *fp; int ready; MPI_Status status[32*32*2]; // array for receive the status MPI_Request request[32*32*2]; // get the rank of current process MPI_Comm_rank(MPI_COMM_WORLD, &MyID); // get the number of processes MPI_Comm_size(MPI_COMM_WORLD, &SumID); // count the separator Spt = SumID-1; // Initialize the argument // allocate memory for arr arr = (int *)malloc(2*DataSize*sizeof(int)); if (arr==0) merror("malloc memory for arr error!"); // arr & arr1 are two array with same size, they are used alternately in Mergesort arr1 = &arr[DataSize]; // allocate memory for temp1 and index if (SumID>1) { temp1 = (int *)malloc(sizeof(int)*SumID*Spt); if (temp1==0) merror("malloc memory for temp1 error!"); index = (int *)malloc(sizeof(int)*2*SumID); if (index==0) merror("malloc memory for index error!"); } // barrier until all the process finish allocating memory MPI_Barrier( MPI_COMM_WORLD); /* modified begin */ // we now start to calculate the length for each process // please notice that the last process should add the Datasize mod SumID if(MyID == SumID - 1) mylength = DataSize / SumID + DataSize % SumID; else mylength = DataSize / SumID; /* modified end */ // produce the random seed srand(MyID); // we use srand to produce random seed, then use rand() to generate random number // and we output them as the input number printf("This is node %d \n",MyID); printf("On node %d the input data is:\n",MyID); for (i=0; i<mylength; i++) { arr[i] = (int)rand(); printf("%d : ",arr[i]); } printf("\n"); // Step 1: // every processor sort their own data(n/P in total), using serial Quicksort, to get a sorted array // we use two barrier for synchronizing MPI_Barrier( MPI_COMM_WORLD); quicksort(arr,0,mylength - 1); MPI_Barrier( MPI_COMM_WORLD); // Step 2: // Every processor pick up No.w, No.2w, No.3w, ... ,No.(P-1)w element, P-1 in total, from sorted array, as representatives. // w=n/P*P if (SumID>1) { // barrier for synchronizing MPI_Barrier(MPI_COMM_WORLD); // n is the interval of representatives n = (int)(mylength/(Spt+1)); // now we use temp1 to store the representatives from each process for (i=0; i<Spt; i++) temp1[i] = arr[(i+1)*n-1]; // barrier for synchronizing MPI_Barrier(MPI_COMM_WORLD); // Step 3: // every process send selected representatives to process P0 if (MyID==0) { // Process P0 receive the representatives from other processes j = 0; // representatives are placed into temp1, for further sorting and picking for (i=1; i<SumID; i++) MPI_Irecv(&temp1[i*Spt], sizeof(int)*Spt, MPI_CHAR, i,ALLTOONE_TYPE+i, MPI_COMM_WORLD, &request[j++]); MPI_Waitall(SumID-1, request, status); // Process P0 do Quicksort to received representatives // (from P processes, have been sorted separately in each process) // there are two barrier for synchronize MPI_Barrier(MPI_COMM_WORLD); quicksort(temp1,0,SumID*Spt-1); MPI_Barrier( MPI_COMM_WORLD); // then pick up No.P-1, No.2(P-1), ..., No.(P-1)(P-1) as pivot elements, P-1 in total // Step 4: // Process P0 broadcast these P-1 pivot elements to all the other processes MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD); // barrier for synchronize MPI_Barrier(MPI_COMM_WORLD); } else { // every other process send selected representatives to process P0 MPI_Send(temp1,sizeof(int)*Spt,MPI_CHAR,0,ALLTOONE_TYPE+MyID, MPI_COMM_WORLD); MPI_Barrier( MPI_COMM_WORLD); // because there are two barrier in Process_0, so this place we need two barrier as well. MPI_Barrier( MPI_COMM_WORLD); // every other process receive pivot elements from process P0 MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD); MPI_Barrier(MPI_COMM_WORLD); } // Step 5: // every process split their own data, n/P in total, into P segments, according to the P-1 pivot elements. // we record them as the No.j+1 segment of Process_Pi, (i=0,...,P-1; j=0,...,P-1) // firstly, initialize the argument n = mylength; index[0] = 0; i = 1; // remove the useless pivot element, which is smaller than any elements of the array to be sorted while ((arr[0]>=temp1[i])&&(i<SumID)) { index[2*i-1] = 0; index[2*i] = 0; i++; } if(i==SumID) index[2*i-1] = n; // now i points to the first useful pivot element c1 = 0; // we use this loop to calculate index[i] while (i<SumID) { // c1 and c3 are the upper bound and lower bound of binary search // and the c2 is the middle element // c4 is the element to be searched c4 = temp1[i]; c3 = n; c2 = (int)((c1+c3)/2); // trying to find element in arr which >= temp1[i], using binary search while ((arr[c2]!=c4)&&(c1<c3)) { if (arr[c2]>c4) { // if the element selected is larger than destination c3 = c2-1; c2 = (int)((c1+c3)/2); } else { // if the element selected is smaller than destination c1 = c2+1; c2 = (int)((c1+c3)/2); } } while ((arr[c2]<=c4)&&(c2<n)) c2++; // now c2 points to the first element in arr which >= temp1[i] if (c2==n) { // if c2==n, that means we reached the upper bound ind