sort.C

#define NUM_OF_ENTRIES_PER_RANK		100
 
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <mpi.h>
 
#include <limits.h>
 
#include <iostream.h>
#include <fstream.h>
 
 
//
// Class declarations.
//
 
 
 
class Entry {
private:
		 	int value; 
 
public:
 
  	Entry() 
         { value = 0; }
 
	  Entry(int x) 
         { value = x; }
 
	  Entry(const Entry &e) 
         		{ value = e.getValue(); }
 
	  Entry& operator= (const Entry &e)
         { value = e.getValue(); return (*this); }
 
  int getValue() const { return value; }
 
	  int operator> (const Entry &e) const 
         { return (value > e.getValue()); }
};
 
 
class BlockOfEntries {
private:
	  Entry **entries;
	  int numOfEntries;
 
public:
	  BlockOfEntries(int *numOfEntries_p, int offset);
  ~BlockOfEntries();
  	int getnumOfEntries() 
       { return numOfEntries; }
	  void setLeftShadow(const Entry &e) 
       { *(entries[0]) = e; }
	  void setRightShadow(const Entry &e) 
		       { *(entries[numOfEntries-1]) = e; }
 
	  const Entry& getLeftEnd() 
       		{ return *(entries[1]); }
	  const Entry& getRightEnd() 
       { return *(entries[numOfEntries-2]); }
 
	  void 	singleStepOddEntries(); 
  void 	singleStepEvenEntries();
  	void 	verifyEntries(int myRank, int baseLine);
  	void 	printEntries(int myRank);
};
 
 
 
//
// Class member definitions.
//
const Entry MAXENTRY(INT_MAX);
const Entry MINENTRY(INT_MIN);
 
 
 
//
//	BlockOfEntries::BlockOfEntries
//
//	Function:	- create the block of entries.
//
BlockOfEntries::BlockOfEntries(int *numOfEntries_p, int myRank)
 
 
{
//
// Initialize the random number generator's seed based on the caller's rank;
// thus, each rank should (but might not) get different random values.
//
 
 
 
  	srand((unsigned int) myRank);
 
	  numOfEntries = NUM_OF_ENTRIES_PER_RANK;
  *numOfEntries_p = numOfEntries;
 
 
 
//
// Add in the left and right shadow entries.
//
 
  	numOfEntries += 2; 
 
 
 
//
// Allocate space for the entries and use rand to initialize the values.
//
 
 
 
  	entries = new Entry *[numOfEntries]; 
  	for(int i = 1; i < numOfEntries-1; i++) {
        		entries[i] = new Entry; 
       *(entries[i]) = (rand()%1000) * ((rand()%2 == 0)? 1 : -1);
	}
 
 
 
//
// Initialize the shadow entries.
//
    	entries[0] = new Entry(MINENTRY);
    	entries[numOfEntries-1] = new Entry(MAXENTRY);
}
 
 
 
//
//	BlockOfEntries::~BlockOfEntries
//
//	Function:	- delete the block of entries.
//
BlockOfEntries::~BlockOfEntries()
 
{
  	for(int i = 1; i < numOfEntries-1; i++) {
          		delete entries[i];
	  }
  delete entries[0];
  	delete entries[numOfEntries-1];
  	delete [] entries;
}
 
 
 
//
//	BlockOfEntries::singleStepOddEntries
//
//	Function: 	- Adjust the odd entries.
//
void 
BlockOfEntries::singleStepOddEntries()
 
 
{
	for(int i = 0; i < numOfEntries-1; i += 2) {
       		if (*(entries[i]) > *(entries[i+1]) ) { 
       Entry *temp = entries[i+1];
       entries[i+1] = entries[i];
       entries[i] = temp;
    		}
	  }
}
 
 
 
//
//	BlockOfEntries::singleStepEvenEntries
//
//	Function: 	- Adjust the even entries.
//
void 
BlockOfEntries::singleStepEvenEntries()
 
 
{
 
   	for(int i = 1; i < numOfEntries-2; i += 2) {
        		if (*(entries[i]) > *(entries[i+1]) ) { 
        Entry *temp = entries[i+1];
        entries[i+1] = entries[i];
        entries[i] = temp;
		    } 
	  }
}
 
 
 
//
//	BlockOfEntries::verifyEntries
//
//	Function: 	- Verify that the block of entries for rank myRank
//			  is sorted and each entry value is greater than
//			  or equal to argument baseLine.
//
 
 
void 
BlockOfEntries::verifyEntries(int myRank, int baseLine)
 
 
{
	  for(int i = 1; i < numOfEntries-2; i++) {
       if (entries[i]->getValue() < baseLine) {
           cout << "Rank " << myRank
                   << " wrong answer i = " << i
                   << " baseLine = " << baseLine
                   << " value = " << entries[i]->getValue()
                  << endl;
           MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
       }
 
 
 
		       if (*(entries[i]) > *(entries[i+1]) ) {
            cout << "Rank " << myRank
                 << " wrong answer i = " << i
                 << " value[i] = " 
                 << entries[i]->getValue()
                 << " value[i+1] = " 
                 << entries[i+1]->getValue()
                 << endl;
           MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
        }
    }
}
 
 
 
//
//	BlockOfEntries::printEntries
//
//	Function: 	- Print myRank's entries to stdout.
//
void 
BlockOfEntries::printEntries(int myRank)
{
    	cout << endl;
    	cout << "Rank " << myRank << endl;
    for(int i = 1; i < numOfEntries-1; i++)
          		cout << entries[i]->getValue() << endl;
}
 
 
 
int 
main(int argc, char **argv) 
 
 
 
{
    	int  	myRank, numRanks;
 
 
	MPI_Init(&argc, &argv);
	
MPI_Comm_rank(MPI_COMM_WORLD, &myRank);	MPI_Comm_size(MPI_COMM_WORLD, &numRanks);
 
 
 
//
// Have each rank build its block of entries for the global sort.
//
 
   	int numEntries;
   	BlockOfEntries *aBlock = new BlockOfEntries(&numEntries,            myRank);
		
 
//
// Compute the total number of entries and sort them.
//
 
       	numEntries *= numRanks;
       for(int j = 0; j < numEntries / 2; j++) {
 
 
//
// Synchronize and then update the shadow entries.
//
 
       		MPI_Barrier(MPI_COMM_WORLD);
 
       		int 		recvVal, sendVal;
       MPI_Request 	sortRequest;
       MPI_Status 	status;
 
//
// Everyone except numRanks-1 posts a receive for the right's    rightShadow.
//
 
      		if (myRank != (numRanks-1)) {
           MPI_Irecv(&recvVal, 1, MPI_INT, myRank+1,
                      MPI_ANY_TAG, MPI_COMM_WORLD,
                     &sortRequest);
      }
 
 
 
//
// Everyone except 0 sends its leftEnd to the left.
//
		 
 
     if (myRank != 0) {
           sendVal = aBlock->getLeftEnd().getValue();
           MPI_Send(&sendVal, 1, MPI_INT,
                    myRank-1, 1, MPI_COMM_WORLD);
      		}
 
      		if (myRank != (numRanks-1)) {
           MPI_Wait(&sortRequest, &status);            aBlock->setRightShadow(Entry(recvVal));
      }
 
 
//
// Everyone except 0 posts for the left's leftShadow.
//
 
      		if (myRank != 0) {
           MPI_Irecv(&recvVal, 1, MPI_INT, myRank-1,
                MPI_ANY_TAG, MPI_COMM_WORLD,
                &sortRequest);
      }
 
 
//
// Everyone except numRanks-1 sends its rightEnd right.
//
 
      		if (myRank != (numRanks-1)) {
           sendVal = aBlock->getRightEnd().getValue();
           MPI_Send(&sendVal, 1, MPI_INT,
                    					myRank+1, 1, MPI_COMM_WORLD);
		      }
 
 
      		if (myRank != 0) {
           MPI_Wait(&sortRequest, &status);			           aBlock->setLeftShadow(Entry(recvVal)); 
      		}
 
 
//
// Have each rank fix up its entries.
//
 
		      aBlock->singleStepOddEntries();		      aBlock->singleStepEvenEntries();
	   }
 
 
//
//  Print and verify the result.
//
 
	   if (myRank == 0) {
      		int	sendVal;
 
		      aBlock->printEntries(myRank);
		      aBlock->verifyEntries(myRank, INT_MIN);
 
		      sendVal = aBlock->getRightEnd().getValue();
      if (numRanks > 1)
           MPI_Send(&sendVal, 1, MPI_INT, 1, 2, MPI_COMM_WORLD);
	   } else {
      		int 		         recvVal;
      		MPI_Status 	 Status;
      		MPI_Recv(&recvVal, 1, MPI_INT, myRank-1, 2, 
                  					MPI_COMM_WORLD, &Status);
		      aBlock->printEntries(myRank);
		      aBlock->verifyEntries(myRank, recvVal);
		      if (myRank != numRanks-1) {
            			recvVal = aBlock->getRightEnd().getValue();			            MPI_Send(&recvVal, 1, MPI_INT, myRank+1, 2, 		   					                       MPI_COMM_WORLD);
      		}
	   }
 
 
 
	   delete aBlock;
   	MPI_Finalize();
   exit(0);
}