基于MPI的PSRS算法的实现

/* Copyright（c） 2009 LuoMin CSU P.R.China
 * All right reserved
 *
 * Abstract:
 *
 */
#include “mpi.h“
#include 
#include 
#include 

/////////////冒泡排序/////////////

void Sort（int *a int len）
{
	int i;
	bool change;
	int temp;

	for（i=len-1 change=true; i>=1; --i）
	{
		change = false;
		
		for（int j=0; j		{
			if（a[j] > a[j+1]）
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				change = true;
			}
		}
	}
}

int main（int argc char **argv）
{
	
	int Size;
	int MyId;
	MPI_Status status;
	int n ;

	int l;

	int *Number; //保存全局数据的缓冲区
	int *Local;  //保存分配到得数据
	int *Sample; //选择样本
	int *AllSample; // 所有的样本
	
	
	
	
	double startTime endTime; //记录程序运行的墙上时间

	MPI_Init（&argc &argv）;
	MPI_Comm_size（MPI_COMM_WORLD &Size）;
	MPI_Comm_rank（MPI_COMM_WORLD &MyId）;

	
	if （ MyId ==0）
	{
		fprintf（stdout “Please input number of elements to be sorted\n“）;
		fflush（stdout）;
		
		if （ Size ==1）
		{
			fprintf（stdout “The number must be integer times of %d\n“ Size*Size）;
			fflush（stdout）;
			scanf（“%d“ &n）;
			fflush（stdin）;
		}
		else
		{
			n = Size*Size-1;
		

			while（ n%（Size*Size））
			{
				fprintf（stdout “The number must be integer times of %d\n“ Size*Size）;
				fflush（stdout）;
				scanf（“%d“ &n）;
				fflush（stdin）;
			}
		}
		
		
		
		l = n/Size; // 待处理的数据数目

		startTime = MPI_Wtime（）;
	}

	MPI_Bcast（&l1MPI_INT 0 MPI_COMM_WORLD）;
	
	MPI_Barrier（MPI_COMM_WORLD）;

	if（MyId==0）
	{
		//fprintf（stdout“Please input %d integer numbers\n“ n）;
		
		//fflush（stdout）;
		
		Number = new int[n];

		srand（time（NULL））;
		for （ int i=0; i		{
			Number[i] = rand（）%100;
		}
		fflush（stdin）;

		Local = new int[l];
		for （ int k=0; k		{
			Local[k] = Number[k]; //根进程自己分派的数据
			
		}		
		//// //均匀划分///////
		for （  int j=1; j		{
			MPI_Send（Number+j*l l MPI_INT j j MPI_COMM_WORLD）;//向其他进程发送待排序数据
		}
		////////////////////////
	}
	else
	{		
			Local = new int[l];
			MPI_Recv（Local l MPI_INT 0 MyId MPI_COMM_WORLD &status）;		
		
	}

	MPI_Barrier（MPI_COMM_WORLD）;


	/////局部排序//////
	Sort（Local l）;
	//////////////////
	

	///////选择样本选择0进程进行样本排序//////
	Sample = new int[Size]; 

	int w = l/Size;

	for（int i=0; i	{

		Sample[i] = Local[i*w];
	}
	
	if （MyId == 0）
	{
		AllSample = new int[Size*Size];
	}
	
	//MPI_Barrier（MPI_COMM_WORLD）;

	MPI_Gather（Sample Size MPI_INT AllSampleSize MPI_INT 0 MPI_COMM_WORLD）;
	
	MPI_Barrier（MPI_COMM_WORLD）;

	if（MyId == 0）
	{
		Sort（AllSample Size*Size）;
		/*fprintf（stdout “All sample: “）;
		for（ int i=0; i		{
		
			fprintf（stdout “%d “ AllSample[i]）;
		
			fflush（stdout）;
		}*/
		
	//////////选择主元///////////
	

		delete []Sample;		

		Sample = new int[Size-1];
		
		
		for（ int k=0; k		{
			Sample[k] = AllSample[（k+