MPI的奇偶排序

奇偶排序是什么? 冒泡大家都知道吧, 奇偶排序就是一种特殊的冒泡,它可以用来实现并行化的排序.

以下的MPI程序使用奇偶排序来排序数组, 数组的每一段由各进程在本地生成.

#include <mpi.h>
#include <string.h>
#include <stdio.h>
#define LOCAL_SIZE 5
int elements[LOCAL_SIZE];
int relements[LOCAL_SIZE];
int nelements[LOCAL_SIZE];

int comp(const void *a, const void* b){
	return (*((int*)a)-*((int*)b));
}
void merge(int *a,int *b,int *c,int isBig){
	int i,j,k;
	if(isBig){
		i=j=k=LOCAL_SIZE-1;
		for(;k>=0;k--){
			if(a[i]>=b[j]){
				c[k]=a[i--];
			}else{
				c[k]=b[j--];
			}
		}
	}
	else{
		i=j=0;
		for(k=0;k<LOCAL_SIZE;k++){
			if(a[i]<=b[j]){
				c[k]=a[i++];
			}else{
				c[k]=b[j++];
			}
		}
	}
	memcpy(a,c,sizeof(int)*LOCAL_SIZE);
}
int main(int argc, char *argv[])
{
	int rank,np,oddt,event,i,j;
	MPI_Status status;
	MPI_Init(&argc,&argv);
	MPI_Comm_size(MPI_COMM_WORLD,&np);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
	srand(rank*997);
	for(i=0;i<LOCAL_SIZE;i++){
		elements[i]=rand()%10000007;
	}
	qsort(elements,LOCAL_SIZE,sizeof(int),comp);
	if(rank%2==0){
		event=rank+1;
		oddt=rank-1;
	}else{
		event=rank-1;
		oddt=rank+1;
	}
	if(event==-1 || event==np) event=MPI_PROC_NULL;
	if(oddt==-1 || oddt ==np) oddt=MPI_PROC_NULL;
	for(i=0;i<np-1;i++){
		if(i%2==0){
			if(event!=MPI_PROC_NULL){
				MPI_Sendrecv(elements,LOCAL_SIZE,MPI_INT,event,0,relements,LOCAL_SIZE,MPI_INT,event,0,MPI_COMM_WORLD,&status);
				merge(elements,relements,nelements,event<rank);
			}
		}else{
			if(oddt!=MPI_PROC_NULL){
				MPI_Sendrecv(elements,LOCAL_SIZE,MPI_INT,oddt,1,relements,LOCAL_SIZE,MPI_INT,oddt,1,MPI_COMM_WORLD,&status);	
				merge(elements,relements,nelements,oddt<rank);
			}
		}
	}
	if(rank==0){
		for(i=0;i<np;i++){
			if(i!=0){
				MPI_Recv(elements,LOCAL_SIZE,MPI_INT,i,i,MPI_COMM_WORLD,&status);
		       	}
			for(j=0;j<LOCAL_SIZE;j++){
				printf("%d ",elements[j]);
			}
		}
		puts("");
	}
	else{
		MPI_Send(elements,LOCAL_SIZE,MPI_INT,0,i,MPI_COMM_WORLD);
	}
	MPI_Finalize();
	return 0;
}

奇偶排序的核心思想是利用p个进程,把一段大的数组均分给这个p个进程,各进程上分别进行排序之后,再进行交换汇总. 相邻的两个进程把各自的结果交换,然后其中一个进程用mergesort取结果中的大的一半,另一个用mergesort取小的一半,这样交互若干次之后就得到了排序后的结果.若一个数被分配在第0个进程中,那么通过最多p-1次交换,就可以被交换到第p-1个进程中,所以最多的交换次数就是p-1.

以下用图形来说明奇偶排序的过程.
8个进程,每个进程分配了4个整数,各自在本地对这4个数排序后进行:
1. 偶交换:

2. 奇交换:

如此7次交换之后,0号进程里的4个数就成了最小的4个,7号进程里的4个数就是最大的那4个了.

MPI的奇偶排序》上有 1 条评论

  1. 谢谢博主的分享,学习到了很多!另外报告一个我遇到的问题,到3个以上就开始出现死锁现象了……如果我能够改好的话再回来评论。再次感谢!

发表评论

电子邮件地址不会被公开。

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>