MPI 实现直接选择排序
选择排序
1/主线程完成读数据 分发 回收和过程控制
2/从线程完成从自己的数据集上选出最小的数值
3/主线程 从收到的数据中选出最小的更新 通知相应线程 发来新的最小值 选择出下一个最小值 循环至完成
#include "mpi.h"#include <unistd.h>#include <fcntl.h>#include <ctype.h>#include <stdio.h>#include <stdlib.h>#define TAG 0#define INT_MAX 999999999#define ROOT 0 int readValue(char* file,int* values) {int fd,size,count=0;char buffer[80],num[11];fd=open(file,O_RDONLY);do {size=read(fd,buffer,sizeof(buffer));int j=0;for(int i=0;i<size;++i) {if(buffer[i]<'9'&&buffer[i]>'0') {num[j++]=buffer[i];} else {num[j]='\0';values[count++]=atoi(num);j=0;}}} while(size!=0);close(fd);return count;}void defineIntVector(MPI_Datatype* type,int length) {MPI_Type_vector(length,1,1,MPI_INT,type);MPI_Type_commit(type);}int getMin(int *mp,int *array,int end,int ex) {int min=array[0];*mp=0;for(int i=1;i<=end;++i) {if(min>array[i]) {min=array[i];*mp=i;}}if(ex) {array[*mp]=array[end];array[end]=min;}return min;}int main(int argc,char *argv[]) {int *values;int *mins;int self,size,length,part,min,mp;MPI_Datatype MPI_VECTOR;MPI_Status status;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&self);MPI_Comm_size(MPI_COMM_WORLD,&size);//read value and broadcast to other processesif(0==self) {values=(int *)malloc(100*sizeof(int));length=readValue("/home/gt/parellel/sort/data.in",values);//each process recieves a part of all data data expands to a std lengthpart=length/(size-1);if(0==length%part) {} else {part+=1;for(int i=length;i<part*(size-1);++i) {values[i]=INT_MAX;}}//broadcast length of each partMPI_Bcast(&part,1,MPI_INT,ROOT,MPI_COMM_WORLD);//minium value from each processdefineIntVector(&MPI_VECTOR,part);//send out all the datafor(int i=1;i<size;++i) {MPI_Ssend(&values[(i-1)*part],1,MPI_VECTOR,i,TAG,MPI_COMM_WORLD);}//gather all min from process//firstmins=(int *)malloc(size*sizeof(int));min=INT_MAX;MPI_Gather(&min,1,MPI_INT,mins,1,MPI_INT,ROOT,MPI_COMM_WORLD);MPI_Barrier(MPI_COMM_WORLD);values[0]=getMin(&mp,mins,size-1,0);for(int i=1;i<length;++i) {//inform correspond process to provide another minMPI_Ssend(&mp,1,MPI_INT,mp,TAG,MPI_COMM_WORLD);//get resultMPI_Recv(&mins[mp],1,MPI_INT,mp,TAG,MPI_COMM_WORLD,&status);values[i]=getMin(&mp,mins,size-1,0);}for(int i=1;i<size;++i) {mp=INT_MAX;MPI_Ssend(&mp,1,MPI_INT,i,TAG,MPI_COMM_WORLD);}for(int i=0;i<length;++i) {printf("%d ",values[i]);}printf("\n");free(mins);} else {MPI_Bcast(&part,1,MPI_INT,ROOT,MPI_COMM_WORLD);values=(int *)malloc(part*sizeof(int));defineIntVector(&MPI_VECTOR,part);MPI_Recv(values,1,MPI_VECTOR,ROOT,TAG,MPI_COMM_WORLD,&status);min=getMin(&mp,values,part-1,1);--part;MPI_Gather(&min,1,MPI_INT,mins,1,MPI_INT,ROOT,MPI_COMM_WORLD);MPI_Barrier(MPI_COMM_WORLD);while(1) {MPI_Recv(&mp,1,MPI_INT,ROOT,TAG,MPI_COMM_WORLD,&status);if(INT_MAX==mp) {//signal for end processbreak;}min=getMin(&mp,values,part-1,1);--part;MPI_Ssend(&min,1,MPI_INT,ROOT,TAG,MPI_COMM_WORLD);}}free(values);MPI_Finalize();return 0;}