MPI——快速排序

yesidoaking

#include<stdio.h>#include<time.h>#include<stdlib.h>#include "mpi.h"int cmp(const void *a,const void *b){return *(int*)a-*(int*)b;}void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;}int partition(int *buf,int n){if(n==0) return 0;--n;int pri=buf[n];int i=-1;int j=0;while(j<n){if(buf[j]>=pri) {++j;continue;}++i;swap(&buf[i],&buf[j]);++j;}++i;swap(&buf[i],&buf[n]);return i;}int main(int argc,char **argv){MPI_Init(&argc,&argv);int rank,size;MPI_Comm_rank(MPI_COMM_WORLD,&rank);MPI_Comm_size(MPI_COMM_WORLD,&size);int n=atoi(argv[1]);int i;int *buf=(int*)malloc(n*sizeof(int));if(buf==NULL){printf("%d malloc failed\n");exit(1);}int *ofss=NULL;int *counts=NULL;int *retbuf=NULL;if(rank==0){int *var=(int*)malloc(n*sizeof(int));srand((int)time(0));for(i=0;i<n;++i){buf[i]=(int)rand()%n;var[i]=buf[i];printf("%d\t",buf[i]);}printf("\n");qsort(var,n,sizeof(int),cmp);for(i=0;i<n;++i)printf("%d\t",var[i]);printf("\n");free(var);ofss=(int*)malloc(size*sizeof(int));counts=(int*)malloc(size*sizeof(int));retbuf=(int*)malloc(n*sizeof(int));if(ofss==NULL || counts==NULL || retbuf==NULL){printf("malloc failed\n");exit(2);}}int mod=1;int sz=1;int block=n;int pos=0;MPI_Status st;while(1){if(rank>=sz){//printf("%d sleep\n",rank);sz<<=1;if(sz>size) sz=size;mod<<=1;continue;}if(rank!=0 && rank-(mod>>1)>=0){MPI_Recv(&pos,1,MPI_INT,rank-(mod>>1),1,MPI_COMM_WORLD,&st);MPI_Recv(&block,1,MPI_INT,rank-(mod>>1),2,MPI_COMM_WORLD,&st);MPI_Recv(buf+pos,block,MPI_INT,rank-(mod>>1),3,MPI_COMM_WORLD,&st);//printf("%d recv from %d\n",rank,rank-(mod>>1));//for(i=pos;i<pos+block;++i)//printf("%d\t",buf[i]);//printf("\n");}if(rank+mod>=size){qsort(buf+pos,block,sizeof(int),cmp);//printf("%d sort %d\t%d\n",rank,block,pos);//for(i=pos;i<pos+block;++i)//printf("%d\t",buf[i]);//printf("\n");break;}int p=partition(buf+pos,block)+pos;//printf("%d partition\n",rank);//for(i=pos;i<p;++i)//printf("%d\t",buf[i]);//printf("\n");//for(i=p;i<pos+block;++i)//printf("%d\t",buf[i]);//printf("\n");int tb=block-p+pos;//printf("%d send to %d:%d %d\n",rank,rank+mod,p,block);MPI_Send(&p,1,MPI_INT,rank+mod,1,MPI_COMM_WORLD);MPI_Send(&tb,1,MPI_INT,rank+mod,2,MPI_COMM_WORLD);MPI_Send(buf+p,tb,MPI_INT,rank+mod,3,MPI_COMM_WORLD);block=p-pos;sz<<=1;if(sz>size) sz=size;mod<<=1;}MPI_Gather(&block,1,MPI_INT,counts,1,MPI_INT,0,MPI_COMM_WORLD);MPI_Gather(&pos,1,MPI_INT,ofss,1,MPI_INT,0,MPI_COMM_WORLD);MPI_Gatherv(buf+pos,block,MPI_INT,retbuf,counts,ofss,MPI_INT,0,MPI_COMM_WORLD);if(rank==0){for(i=0;i<n;++i)printf("%d\t",retbuf[i]);printf("\n");free(counts);free(ofss);free(retbuf);}free(buf);MPI_Finalize();return 0;}