《并行计算》课程辅导：排序

1 排序 排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。 所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若给定的文件含有n个记录｛R1，R2，…，Rn｝，它们的关键字分别为｛K1，K2，…，Kn｝，要把这n个记录重新排列成为｛Ri1，Ri2，…，Rin｝，使得｛Ki1≥Ki2≥…≥Kin｝（或｛Ki1≤Ki2≤…≤Kin｝）。 本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。 枚举排序 枚举排序及其串行算法 枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort）。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]比较，记录比其小的数的个数，依此类推。这样的比较操作共n(n-1)次，所以串行秩排序的时间复杂度为O（n2）。 算法13.1 枚举排序串行算法 输入：a[1]…a[n] 输出：b[1]…b[n] Begin for i=1 to n do (1) k=1 (2) for j=1 to n do if a[i]>a[j] then k=k+1 end if end for (3) b[k]= a[i] end for End 枚举排序的并行算法 对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 算法13.2 枚举排序并行算法 输入：无序数组a[1]…a[n] 输出：有序数组b[1]…b[n] Begin (1) P0播送a[1]…a[n]给所有Pi (2) for all Pi where 1≤i≤n para-do (2.1) k=1 (2.2) for j = 1 to n do if (a[i] > a[j]) or (a[i] = a[j] and i>j) then k = k+1 end if end for (3) P0收集k并按序定位 End 在该并行算法中，使用了n个处理器，由于每个处理器定位一个元素，所以步骤⑵的时间复杂度为O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时⑴中的通信复杂度为O（n2）；所以总的计算复杂度为O（n），总的通信复杂度为O（n2）。 MPI源程序请参见所附光盘。 快速排序 快速排序及其串行算法 快速排序（Quick Sort）是一种最基本的排序算法，它的基本思想是：在当前无序区R[1，n]中取一个记录作为比较的“基准”（一般取第一个、最后一个或中间位置的元素），用此基准将当前的无序区R[1，n]划分成左右两个无序的子区R[1，i-1]和R[i，n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R[1，i-1]和R[i，n]非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。 算法13.3 单处理机上快速排序算法 输入：无序数组data[1,n] 输出：有序数组data[1,n] Begin call procedure quicksort(data,1,n) End procedure quicksort(data,i,j) Begin (1) if (i<j) then (1.1)r = partition(data,i,j) (1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j); end if End procedure partition(data,k,l) Begin (1) pivo=data[l] (2) i=k-1 (3) for j=k to l-1 do if data[j]≤pivo then i=i+1 exchange data[i] and data[j] end if end for (4) exchange data[i+1] and data[l] (5) return i+1 End 快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏的情况下，划分的结果是一边有n-1个元素，而另一边有0个元素（除去被选中的基准元素）。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是Θ（n2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O（nlogn）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。 快速排序的并行算法 快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。算法13.4中描述了使用2m个处理器完成对n个输入数据排序的并行算法。 算法13.4 快速排序并行算法 输入：无序数组data[1,n]，使用的处理器个数2m 输出：有序数组data[1,n] Begin para_quicksort(data,1,n,m,0) End procedure para_quicksort(data,i,j,m,id) Begin (1) if (j-i)≤k or m=0 then (1.1) Pid call quicksort(data,i,j) else (1.2) Pid: r=patrition(data,i,j) (1.3) P id send data[r+1,m-1] to Pid+2m-1 (1.4) para_quicksort(data,i,r-1,m-1,id) (1.5) para_quicksort(data,r+1,j,m-1,id+2m-1) (1.6) Pid+2m-1 send data[r+1,m-1] back to Pid end if End 在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O（n），通信复杂度也为O（n）。同串行算法一样，在最坏情况下其计算复杂度降为O（n2）。正常情况下该算法的计算复杂度也为O（n），只不过具有更高的常数因子。 MPI源程序请参见所附光盘。 PSRS排序 PSRS算法原理 并行正则采样排序，简称PSRS(Parallel Sorting by Regular Sampling)它是一种基于均匀划分（Uniform Partition）原理的负载均衡的并行排序算法。假定待排序的元素有n个，系统中有p个处理器，那么系统首先将n个元素均匀地分割成p段，每段含有n/p个元素，每段指派一个处理器，然后各个处理器同时施行局部排序。为了使各段中诸局部有序的元素在整个序列中也能占据正确的位置，那么就首先从各段中抽取几个代表元素，再从他们产生出p-1个主元，然后按这些主元与原各局部有序中的元素之间的偏序关系，将各个局部有序段划分成p段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集合在一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序序列了。 PSRS算法形式化描述 设有n个数据，P个处理器，以及均匀分布在P个处理器上的n个数据。 则PSRS算法可描述如下： 算法13.5 PSRS排序算法 输入：n个待排序的数据，均匀地分布在P个处理器上 输出：分布在各个处理器上，得到全局有序的数据序列 Begin (1) 每个处理器将自己的n/P个数据用串行快速排序(Quicksort)，得到一个排好序的 序列； (2) 每个处理器从排好序的序列中选取第w，2w，3w，…，(P-1)w个共P-1个数据作为 代表元素，其中w=n/P2； (3) 每个处理器将选好的代表元素送到处理器P0中，并将送来的P段有序的数据序列 做P路归并，再选择排序后的第P-1，2(P-1)，…，(P-1)(P-1)个共P-1个主元； (4) 处理器P0将这P-1个主元播送到所有处理器中； (5) 每个处理器根据上步送来的P-1个主元把自己的n/P个数据分成P段，记
为处 理器Pi的第j+1段，其中i=0，…，P-1，j=0，…，P-1； (6) 每个处理器送它的第i+1段给处理器Pi，从而使得第i个处理器含有所有处理器的 第i段数据(i=0，…，P-1)； (7) 每个处理器再通过P路归并排序将上一步的到的数据排序；从而这n个数据便是有 序的。 End 在该算法中，针对其中的计算部分⑴中的快速排序的代价为O（klogk），其中k=n/p；第⑵步中各个处理器选择P个主元的代价为O（P）；⑶中对P2个主元进行归并并选取新的主元所需代价为O（P2+logP）；⑸中对数据划分的代价为O（P+n/p）；最后第⑺步中各个处理器进行并行归并的代价为O（n/p+logP）。针对通信部分⑶中处理器P0收集P2个主元的代价为O（P2）；(4)中播送新选择的P个主元的代价为O（P）；最后第(6)步的多对多播送的通信复杂度与具体的算法实现相关，其最大不会超过O（n）。 MPI源程序请参见章末附录。 小结 本章主要讨论了几个典型的并行排序算法，关于枚举匹配算法的具体讨论可参考［1］；快速排序算法可以参考文献［2］和［3］中的介绍；文献［4］和［5］讨论了PSRS排序算法。 参考文献 Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis Universite de Franche-comte, France:1980 Lorin H. Sorting and sort systems. Don Mills, Ontario: Addison-Wesley, 1975, 347~365 陈国良 编著. 并行算法的设计与分析（修订版）. 高等教育出版社, 2002.11 Shi H, Schaeffer J. Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 Li X, Lu P, Schaeffer J, Shillington J, Wong P S, Shi H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993 附录 PSRS算法MPI源程序 1. 源程序psrs_sort.c #include <stdio.h> #include <stdlib.h> #include <mpi.h> #define INIT_TYPE 10 #define ALLTOONE_TYPE 100 #define ONETOALL_TYPE 200 #define MULTI_TYPE 300 #define RESULT_TYPE 400 #define RESULT_LEN 500 #define MULTI_LEN 600 int Spt; long DataSize; int *arr,*arr1; int mylength; int *index; int *temp1; main(int argc,char* argv[]) { long BaseNum = 1; int PlusNum; int MyID; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD, &MyID); PlusNum=60; DataSize = BaseNum*PlusNum; if (MyID==0) printf("The DataSize is : %lu\n",PlusNum); Psrs_Main(); if (MyID==0) printf("\n"); MPI_Finalize(); } Psrs_Main( ) { int i,j; int MyID,SumID; int n,c1,c2,c3,c4,k,l; FILE * fp; int ready; MPI_Status status[32*32*2]; MPI_Request request[32*32*2]; MPI_Comm_rank(MPI_COMM_WORLD, &MyID); MPI_Comm_size(MPI_COMM_WORLD, &SumID); Spt = SumID-1; /*初始化参数*/ arr = (int *)malloc(2*DataSize*sizeof(int)); if (arr==0) merror("malloc memory for arr error!"); arr1 = &arr[DataSize]; if (SumID>1) { temp1 = (int *)malloc(sizeof(int)* SumID*Spt); if (temp1==0) merror("malloc memory for temp1 error!"); index = (int *)malloc(sizeof(int)* 2*SumID); if (index==0) merror("malloc memory for index error!"); } MPI_Barrier( MPI_COMM_WORLD); mylength = DataSize / SumID; srand(MyID); printf("This is node %d \n",MyID); printf("On node %d the input data is:\n",MyID); for (i=0;i<mylength;i++) { arr[i] = (int)rand(); printf("%d : ",arr[i]); } printf("\n"); /*每个处理器将自己的n/P个数据用串行快速 排序(Quicksort)，得到一个排好序的序 列，对应于算法13.5步骤（1）*/ MPI_Barrier( MPI_COMM_WORLD); quicksort(arr,0,mylength - 1); MPI_Barrier( MPI_COMM_WORLD); /*每个处理器从排好序的序列中选取第w，2w， 3w，…，(P-1)w个共P-1个数据作为代 表元素，其中w=n/P*P，对应于算法13.5 步骤（2）*/ if (SumID>1) { MPI_Barrier(MPI_COMM_WORLD); n = (int)(mylength/(Spt+1)); for (i=0;i<Spt;i++) temp1[i] = arr[(i+1)*n-1]; MPI_Barrier(MPI_COMM_WORLD); if (MyID==0) { /*每个处理器将选好的代表元素送 到处理器P0中，对应于算法 13.5步骤（3） */ j = 0; for (i=1;i<SumID;i++) MPI_Irecv(&temp1[i*Spt], sizeof(int)*Spt, MPI_CHAR, i,ALLTOONE_TYPE+i, MPI_COMM_WORLD, &request[j++]); MPI_Waitall(SumID-1, request, status); /* 处理器P0将上一步送来的P段 有序的数据序列做P路归并， 再选择排序后的第P-1，2(P-1)，…，(P-1)(P-1)个共P-1个主元，，对应于算法13.5步骤（3）*/ MPI_Barrier( MPI_COMM_WORLD); quicksort(temp1,0,SumID*Spt-1); MPI_Barrier( MPI_COMM_WORLD); for (i=1;i<Spt+1;i++) temp1[i] = temp1[i*Spt-1]; /*处理器P0将这P-1个主元播送到 所有处理器中，对应于算法13.5步骤（4）*/ MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD); MPI_Barrier( MPI_COMM_WORLD); } else { MPI_Send(temp1,sizeof(int)*Spt, MPI_CHAR,0, ALLTOONE_TYPE+MyID, MPI_COMM_WORLD); MPI_Barrier( MPI_COMM_WORLD); MPI_Barrier( MPI_COMM_WORLD); MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD); MPI_Barrier( MPI_COMM_WORLD); } /*每个处理器根据上步送来的P-1个主 元把自己的n/P个数据分成P段， 记为处理器Pi的第j+1段，其中i=0,…,P-1，j=0,…,P-1，对应于算法13.5步骤（5）*/ n = mylength; index[0] = 0; i = 1; while ((arr[0]>=temp1[i])&&(i<SumID)) { index[2*i-1] = 0; index[2*i] = 0; i++; } if (i==SumID) index[2*i-1] = n; c1 = 0; while (i<SumID) { c4 = temp1[i]; c3 = n; c2 = (int)((c1+c3)/2); while ((arr[c2]!=c4)&&(c1<c3)) { if (arr[c2]>c4) { c3 = c2-1; c2 = (int)((c1+c3)/2); } else { c1 = c2+1; c2 = (int)((c1+c3)/2); } } while ((arr[c2]<=c4)&&(c2<n)) c2++; if (c2==n) { index[2*i-1] = n; for (k=i;k<SumID;k++) { index[2*k] = 0; index[2*k+1] = 0; } i = SumID; } else { index[2*i] = c2; index[2*i-1] = c2; } c1 = c2; c2 = (int)((c1+c3)/2); i++; } if (i==SumID) index[2*i-1] = n; MPI_Barrier( MPI_COMM_WORLD); /*每个处理器送它的第i+1段给处理器 Pi，从而使得第i个处理器含有所 有处理器的第i段数据 (i=0,…,P-1)，，对应于算法13.5步 骤（6）*/ j = 0; for (i=0;i<SumID;i++) { if (i==MyID) { temp1[i] = index[2*i+1]- index[2*i]; for (n=0;n<SumID;n++) if (n!=MyID) { k = index[2*n+1]- index[2*n]; MPI_Send(&k, sizeof(int), MPI_CHAR, n, MULTI_LEN+MyID, MPI_COMM_WORLD); } } else { MPI_Recv(&temp1[i], sizeof(int), MPI_CHAR, i,MULTI_LEN+i, MPI_COMM_WORLD, &status[j++]); } } MPI_Barrier(MPI_COMM_WORLD); j = 0; k = 0; l = 0; for (i=0;i<SumID;i++) { MPI_Barrier( MPI_COMM_WORLD); if (i==MyID) { for (n=index[2*i]; n<index[2*i+1]; n++) arr1[k++] = arr[n]; } MPI_Barrier( MPI_COMM_WORLD); if (i==MyID) { for (n=0;n<SumID;n++) if (n!=MyID) { MPI_Send(&arr[ index[2*n]], sizeof(int)* (index[2*n+1]-index[2*n]),MPI_CHAR, n, MULTI_TYPE+MyID, MPI_COMM_WORLD); } } else { l = temp1[i]; MPI_Recv(&arr1[k], l*sizeof(int), MPI_CHAR, i ,MULTI_TYPE+i, MPI_COMM_WORLD, &status[j++]); k=k+l; } MPI_Barrier( MPI_COMM_WORLD); } mylength = k; MPI_Barrier(MPI_COMM_WORLD); /*每个处理器再通过P路归并排序将上 一步的到的数据排序；从而这n个 数据便是有序的，，对应于算法13.5 步骤（7） */ k = 0; multimerge(arr1,temp1,arr,&k,SumID); MPI_Barrier(MPI_COMM_WORLD); } printf("On node %d the sorted data is : \n",MyID); for (i=0;i<mylength;i++) printf("%d : ",arr[i]); printf("\n"); } /*输出错误信息*/ merror(char* ch) { printf("%s\n",ch); exit(1); } /*串行快速排序算法*/ quicksort(int *datas,int bb,int ee) { int tt,i,j; t = datas[bb]; = bb; j = ee; if (i<j) { while(i<j) { while ((i<j)&&(tt<=datas[j])) j--; if (i<j) { datas[i] = datas[j]; i++; while ((i<j)&& (tt>datas[i])) i++; if (i<j) { datas[j] = datas[i]; j--; if (i==j) datas[i] = tt; } else datas[j] = tt; } else datas[i] = tt; } quicksort(datas,bb,i-1); quicksort(datas,i+1,ee); } } /*串行多路归并算法*/ multimerge(int *data1,int *ind,int *data,int *iter,int SumID) { int i,j,n; j = 0; for (i=0;i<SumID;i++) if (ind[i]>0) { ind[j++] = ind[i]; if (j<i+1) ind[i] = 0; } if ( j>1 ) { n = 0; for (i =0;i<j,i+1<j;i=i+2) { merge(&(data1[n]),ind[i], ind[i+1],&(data[n])); ind[i] += ind[i+1]; ind[i+1] = 0; n += ind[i]; } if (j%2==1 ) for (i=0;i<ind[j-1];i++) data[n++]=data1[n]; (*iter)++; multimerge(data,ind,data1,iter, SumID); } } merge(int *data1,int s1,int s2,int *data2) { int i,l,m; l = 0; m = s1; for (i=0;i<s1+s2;i++) { if (l==s1) data2[i]=data1[m++]; else if (m==s2+s1) data2[i]=data1[l++]; else if (data1[l]>data1[m]) data2[i]=data1[m++]; else data2[i]=data1[l++]; } } 2. 运行实例 编译：mpicc psrs_sort.c –o psrs 运行：可以使用命令 mpirun –np SIZE psrs来运行该串匹配程序，其中SIZE是所使用的处理器个数，本实例中使用了SIZE=3个处理器。 mpirun –np 3 psrs 运行结果： The DataSize is : 60 This is node 0 On node 0 the input data is: 0 : 21468 : 9988 : 22117 : 3498 : 16927 : 16045 : 19741 : 12122 : 8410 : 12261 : 27052 : 5659 : 9758 : 21087 : 25875 : 32368 : 26233 : 15212 : 17661 : On node 0 the sorted data is : 0 : 2749 : 3498 : 4086 : 5627 : 5659 : 5758 : 7419 : 8410 : 9084 : 9758 : 9988 : 703 : 908 : 2294 : 9212 : This is node 1 On node 1 the input data is: 16838 : 5758 : 10113 : 17515 : 31051 : 5627 : 23010 : 7419 : 16212 : 4086 : 2749 : 12767 : 9084 : 12060 : 32225 : 17543 : 25089 : 21183 : 25137 : 25566 : On node 1 the sorted data is : 10113 : 12060 : 12122 : 12261 : 12767 : 15212 : 16045 : 16212 : 16838 : 16927 :17515 : 10239 : 10595 : 12508 : 12914 : 14363 : 16134 : This is node 2 On node 2 the input data is: 908 : 22817 : 10239 : 12914 : 25837 : 27095 : 29976 : 27865 : 20302 : 32531 : 26005 : 31251 : 12508 : 14363 : 10595 : 9212 : 17811 : 16134 : 2294 : 703 : On node 2 the sorted data is : 17543 : 17661 : 19741 : 21087 : 21183 : 21468 : 22117 : 23010 : 25089 : 25137 : 25566 : 25875 : 26233 : 27052 : 31051 : 32225 : 32368 : 17811 : 20302 : 22817 : 25837 : 26005 : 27095 : 27865 : 29976 : 31251 : 32531 : 说明：本程序中通过变量DataSize指定了待排序序列的长度为60，顺序输出各个处理器的局部数据就可以得到全局有序的序列。