首页 > 代码库 > 并行归并排序——MPI

并行归并排序——MPI

      并行归并排序在程序开始时,会将n/comm_comm个键值分配给每个进程,程序结束时,所有的键值会按顺序存储在进程0中。为了做到这点,它使用了树形结构通信模式。当进程接收到另一个进程的键值时,它将该键值合并进自己排序的键值列表中。编写一个程序实现归并排序。进程0应该读入n的值,将其广播给其余进程。每个进程需要使用随机数生成器来创建n/comm_sz的局部int型数据列表。每个进程先排序各自的局部列表,然后进程0收集并打印这些局部列表。然后,这些进程使用树形结构通信合并全局列表给进程0,并打印最终结果。

  技术分享

如图,一般情况下,应由进程读入数据,然后一层一层的传到每个进程,每个进程排序完成之后,由上一层的进程进行合并。我这次做的只是输入数n,由每个进程产生n/comm_sz个随机数。

这里有一个问题,如何确定一个进程的父节点和子节点?

  你最初可能认为让在处理树中的每个节点是一个单独的进程中。这样,你可以简单地从二叉堆借用一个想法任何父节点的左子节点下标2* K+1,右子节点的下标是2* K+2,一个节点的父节点是(K-1 )/ 2,这在一个完全二叉树中确定了父子关系因此,一个内部节点将数据分成两半,并发送给每个子进程进行处理。这样叶节点,只是做了排序,内部节点等待然后从两个子节点接收回数据,执行两半的合并,以及(对于所有内部节点但非根节点本身)将结果发送到父节点。

  但是这样带来一个问题,就是当叶节点进行排序时,父节点在等待子节点,没有理由让父节点空闲等待子节点进行排序,我们希望让父节点充当左子节点进行工作,如图:
技术分享
  这样每个节点将数据分成两半,每个节点自己处理数据的左半,右子节点处理数据的右半。这样之后你就要确定每个节点的父节点和子节点,你可以根据树形通信结构来确定每个节点的父节点和子节点。
  我们要先确定每个节点在树形通信结构的高度,叶节点的高度为0,这样根节点0的高度是3。节点0需要与节点4进行通信,对于如何计算出节点0的右子节点是4,可以通过将节点0所在的高度3减1转化成二进制并左移一位,即(myRank|(1<<2)),myRank表示节点的编号,这里是0,这样就可以计算出高度为3的节点0的右子节点。下一步节点0需要与节点2通信,节点4需要与节点6通信,此时节点0和4的高度为2,因此需要计算他们的子节点时通过公式((myRank|(1<<1)),这样计算出节点0的右子节点是2,节点4的右子节点时6,一般化的公式是(myRank|(myHeight-1))。
  计算完每个节点的子节点后,还要计算每个节点的父节点,每个节点的父节点可以通过如下公式进行计算,myRank&~(1<<myHeight)。
  下面是一个小的demo来展示通信过程,他展示了高度为3的通信树节点之间的通信过程,
 1 #include <stdio.h> 2  3 void communicate ( int myHeight, int myRank ) 4 {  int parent = myRank & ~(1<<myHeight); 5  6    if ( myHeight > 0 ) 7    {  int nxt     = myHeight - 1; 8       int rtChild = myRank | ( 1 << nxt ); 9 10       printf ("%d sending data to %d\n", myRank, rtChild);11       communicate ( nxt, myRank );12       communicate ( nxt, rtChild );13       printf ("%d getting data from %d\n", myRank, rtChild);14    }15    if ( parent != myRank )16       printf ("%d transmitting to %d\n", myRank, parent);17 }18 19 int main ( void )20 {  int myHeight = 3, myRank = 0;21 22    printf ("Building a height %d tree\n", myHeight);23    communicate(myHeight, myRank);24    return 0;25 }

下面是输出结果

Building a height 3 tree
0 sending data to 4
0 sending data to 2
0 sending data to 1
1 transmitting to 0
0 getting data from 1
2 sending data to 3
3 transmitting to 2
2 getting data from 3
2 transmitting to 0
0 getting data from 2
4 sending data to 6
4 sending data to 5
5 transmitting to 4
4 getting data from 5
6 sending data to 7
7 transmitting to 6
6 getting data from 7
6 transmitting to 4
4 getting data from 6
4 transmitting to 0
0 getting data from 4

了解了通信结构之后,下面是mpi_merge_sort.c文件,利用MPI写的归并排序,

  1 #include<stdlib.h>  2 #include<stdio.h>  3 #include<time.h>  4 #include<math.h>  5 #include<string.h>  6 #include<mpi.h>  7 //读取输入的要排序的数的个数,并计算每个进程需要排序的个数  8 void read_n(int* n,int my_rank,MPI_Comm comm,int comm_sz,int* size);  9 //根据节点在通信树中的最高度为数组分配空间 10 void allocate_arrays(int** left,int** right,int** merge,int size,int height,int* myHeight,int my_rank); 11 //在left数组中生成size个随机数 12 void randnum(int* left,int size,int my_rank); 13 //以下三个函数时用于在通信树的叶节点对生成在left中的size个随机数进行快速排序 14 void swap(int *a,int *b); 15 int partition(int left[],int lo,int hi); 16 void QuickSort(int left[], int lo, int hi); 17 //父节点将接收子节点的数据与自己节点的数据进行归并 18 void merge_sort(int* left,int* right,int* merge,int size); 19 //控制通信,确定从哪个子节点中接收数据或向哪个父节点发送数据 20 void communicate ( int Height, int my_rank,int size,int* right,int* left,int* merge,MPI_Comm comm); 21  22 int main(int argc,char* argv[]){ 23     int n,comm_sz,my_rank; 24     int* left; 25     int* right; 26     int* merge; 27     int size; 28     int myHeight=0; 29     MPI_Comm comm; 30     int height=0; 31      32     MPI_Init(NULL,NULL); 33     comm=MPI_COMM_WORLD; 34     MPI_Comm_size(comm,&comm_sz); 35     MPI_Comm_rank(comm,&my_rank); 36     read_n(&n,my_rank,comm,comm_sz,&size); 37     int tt=comm_sz; 38     for(int i=0;i<comm_sz;i++){ 39         tt=tt/2; 40         if(tt==0) 41             break; 42         height++;     43     } 44     allocate_arrays(&left,&right,&merge,size,height,&myHeight,my_rank); 45     randnum(left,size,my_rank); 46     QuickSort(left,0,size-1); 47      48     communicate(height,my_rank,size,right,left,merge,comm); 49     if(my_rank==0){ 50         if(height%2!=0) 51             for(int i=0;i<n;i++) 52                 printf("%d    ",merge[i]); 53         else 54             for(int i=0;i<n;i++) 55                 printf("%d    ",left[i]); 56         printf("\n"); 57     } 58     MPI_Finalize(); 59     free(left); 60     free(right); 61     free(merge); 62      63 } 64 void read_n(int* n,int my_rank,MPI_Comm comm,int comm_sz,int* size){ 65     if(my_rank==0){ 66         printf("please intput the number of number\n"); 67         scanf("%d",n);     68     } 69     MPI_Bcast (n,1,MPI_INT,0,comm); 70     *size=*n/comm_sz; 71 } 72 void allocate_arrays(int** left,int** right,int** merge,int size,int height,int* myHeight,int my_rank){ 73     for(int i=0;i<height;i++){ 74         int parent=my_rank&~(1<<i); 75         if(parent!=my_rank) 76             break; 77         (*myHeight)++; 78     } 79     *left=malloc((1<<(*myHeight))*size*sizeof(int)); 80      81     *right=malloc((1<<(*myHeight-1))*size*sizeof(int)); 82     *merge=malloc((1<<(*myHeight))*size*sizeof(int)); 83      84 } 85 void randnum(int* left,int size,int my_rank){ 86     srand(my_rank); 87     for(int i=0;i<size;i++) 88         left[i]=rand(); 89 } 90 void swap(int *a,int *b) 91 { 92  int temp=*a; 93  *a=*b; 94  *b=temp; 95 } 96 int partition(int* left,int lo,int hi) 97 { 98  int key=left[hi];   99  int i=lo-1;100  for(int j=lo;j<hi;j++)   101  {102   if(left[j]<=key)103   {104    i=i+1;105    swap(&left[i],&left[j]);106   }107  }108  swap(&left[i+1],&left[hi]);  109  return i+1;110 }111 void QuickSort(int *left, int lo, int hi)112 {113     if (lo<hi)114     {115         int k = partition(left, lo, hi);116         QuickSort(left, lo, k-1);117         QuickSort(left, k+1, hi);118     }119 }120 void merge_sort(int* left,int* right,int* merge,int size){121     122     int lp=0,rp=0,mp=0;123     for(int i=0;i<2*size;i++){124         if(left[lp]<=right[rp]){125             merge[mp]=left[lp];126             lp++;127             mp++;    128         }else{129             merge[mp]=right[rp];130             rp++;131             mp++;        132         }133         if(lp==size||rp==size)134             break;135     }136     if(lp==size){137         memcpy(&merge[mp],&right[rp],(size-rp)*sizeof(int));138     }else{139         memcpy(&merge[mp],&left[lp],(size-lp)*sizeof(int));140     }    141 }142 void communicate ( int Height, int my_rank,int size,int* right,int* left,int* merge,MPI_Comm comm)143 {      144     for(int i=0;i<=Height;i++){145          int parent=my_rank&~(1<<i);146         if(parent==my_rank){147             int rtChild=my_rank|(1<<i);148             149             MPI_Recv(right,size,MPI_INT,rtChild,0,comm,MPI_STATUS_IGNORE);150             151             merge_sort(left,right,merge,size);152 153             int* temp;154             temp=left;155             left=merge;156             merge=temp;157             size*=2;158             159         }else{160             MPI_Send(left,size,MPI_INT,parent,0,comm);161             break;162             163         }164     }165     166 }

使用 mpicc -g -Wall -std=c99 -o mpi_merge_sort mpi_merge_sort.c 进行编译

使用 mpirun -n 4 ./mpi_merge_sort 

注意输入的进程个数一定是2的整数次幂,且输入的要排序数的个数要能整除进程个数

下面是一次的运行结果:

please intput the number of number
12
190686788    483147985    844158168    846930886    846930886    1205554746    1505335290    1681692777    1681692777    1738766719    1804289383    1804289383

 参考资料:http://penguin.ewu.edu/~trolfe/ParallelMerge/ParallelMerge.html

 

并行归并排序——MPI