开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 并行计算 > 查看源码
psrs_sort.c
资源名称：mpi.zip　[点击查看]
上传用户：hhyinxing
上传日期：2013-09-10
资源大小：833k
文件大小：8k
源码类别：

并行计算

开发平台：

Unix_Linux

psrs_sort.c：源码内容
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <mpi.h>
  5. #define INIT_TYPE 10
  6. #define ALLTOONE_TYPE 100
  7. #define ONETOALL_TYPE 200
  8. #define MULTI_TYPE 300
  9. #define RESULT_TYPE 400
  10. #define RESULT_LEN 500
  11. #define MULTI_LEN 600
  13. int Spt;
  14. long DataSize;
  15. int *arr,*arr1;
  16. int mylength;
  17. int *index;
  18. int *temp1;
  20. main(int argc,char* argv[])
  21. {
  22.     long BaseNum = 1;
  23.     int PlusNum;
  24.     int MyID;
  26.     MPI_Init(&argc,&argv);
  27.     MPI_Comm_rank(MPI_COMM_WORLD,&MyID);
  29.     PlusNum=60;
  30.     DataSize = BaseNum*PlusNum;
  32.     if (MyID==0)
  33.         printf("The DataSize is : %lun",PlusNum);
  34.     Psrs_Main();
  36.     if (MyID==0)
  37.         printf("n");
  39.     MPI_Finalize();
  40. }
  43. Psrs_Main( )
  44. {
  45.     int i,j;
  46.     int MyID,SumID;
  47.     int n,c1,c2,c3,c4,k,l;
  48.     FILE * fp;
  49.     int ready;
  50.     MPI_Status status[32*32*2];
  51.     MPI_Request request[32*32*2];
  53.     MPI_Comm_rank(MPI_COMM_WORLD,&MyID);
  54.     MPI_Comm_size(MPI_COMM_WORLD,&SumID);
  56.     Spt = SumID-1;
  58. /*初始化参数*/
  59.     arr = (int *)malloc(2*DataSize*sizeof(int));
  60.     if (arr==0) merror("malloc memory for arr error!");
  61.     arr1 = &arr[DataSize];
  63.     if (SumID>1)
  64.     {
  65.         temp1 = (int *)malloc(sizeof(int)*SumID*Spt);
  66.         if (temp1==0) merror("malloc memory for temp1 error!");
  67.         index = (int *)malloc(sizeof(int)*2*SumID);
  68.         if (index==0) merror("malloc memory for index error!");
  69.     }
  71.     MPI_Barrier( MPI_COMM_WORLD);
  73.     mylength = DataSize / SumID;
  74.     srand(MyID);
  76.     printf("This is node %d n",MyID);
  77.     printf("On node %d the input data is:n",MyID);
  78.     for (i=0;i<mylength;i++)
  79.     {
  80.         arr[i] = (int)rand();
  81.         printf("%d : ",arr[i]);
  82.     }
  83.     printf("n");
  85. /*每个处理器将自己的n/P个数据用串行快速排序(Quicksort)，得到一个排好序的序列，对应于算法13.5步骤（1）*/
  86.     MPI_Barrier( MPI_COMM_WORLD);
  87.     quicksort(arr,0,mylength - 1);
  88.     MPI_Barrier( MPI_COMM_WORLD);
  90. /*每个处理器从排好序的序列中选取第w，2w，3w，…，(P-1)w个共P-1个数据作为代表元素，其中w=n/P*P，对应于算法13.5步骤（2）*/
  91.     if (SumID>1)
  92.     {
  93.         MPI_Barrier(MPI_COMM_WORLD);
  95.         n = (int)(mylength/(Spt+1));
  96.         for (i=0;i<Spt;i++)
  97.             temp1[i] = arr[(i+1)*n-1];
  99.         MPI_Barrier(MPI_COMM_WORLD);
  101.         if (MyID==0)
  102.         {
  103. /*每个处理器将选好的代表元素送到处理器P0中，对应于算法13.5步骤（3） */
  104.             j = 0;
  105.             for (i=1;i<SumID;i++)
  106.                 MPI_Irecv(&temp1[i*Spt], sizeof(int)*Spt, MPI_CHAR, i,ALLTOONE_TYPE+i, MPI_COMM_WORLD, &request[j++]);
  107.             MPI_Waitall(SumID-1, request, status);
  109. /* 处理器P0将上一步送来的P段有序的数据序列做P路归并，再选择排序后的第P-1，2(P-1)，…，(P-1)(P-1)个共P-1个主元，，对应于算法13.5步骤（3）*/
  110.             MPI_Barrier(MPI_COMM_WORLD);
  111.             quicksort(temp1,0,SumID*Spt-1);
  112.             MPI_Barrier( MPI_COMM_WORLD);
  114.             for (i=1;i<Spt+1;i++)
  115.                 temp1[i] = temp1[i*Spt-1];
  116. /*处理器P0将这P-1个主元播送到所有处理器中，对应于算法13.5步骤（4）*/
  117.             MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD);
  118.             MPI_Barrier(MPI_COMM_WORLD);
  119.         }
  120.         else
  121.         {
  122.             MPI_Send(temp1,sizeof(int)*Spt,MPI_CHAR,0,ALLTOONE_TYPE+MyID, MPI_COMM_WORLD);
  123.             MPI_Barrier( MPI_COMM_WORLD);
  124.             MPI_Barrier( MPI_COMM_WORLD);
  125.             MPI_Bcast(temp1, sizeof(int)*(1+Spt), MPI_CHAR, 0, MPI_COMM_WORLD);
  126.             MPI_Barrier(MPI_COMM_WORLD);
  127.         }
  129. /*每个处理器根据上步送来的P-1个主元把自己的n/P个数据分成P段，记为处理器Pi的第j+1段，其中i=0,…,P-1，j=0,…,P-1，对应于算法13.5步骤（5）*/
  130.         n = mylength;
  131.         index[0] = 0;
  132.         i = 1;
  133.         while ((arr[0]>=temp1[i])&&(i<SumID))
  134.         {
  135.             index[2*i-1] = 0;
  136.             index[2*i] = 0;
  137.             i++;
  138.         }
  139.         if (i==SumID) index[2*i-1] = n;
  140.         c1 = 0;
  141.         while (i<SumID)
  142.         {
  143.             c4 = temp1[i];
  144.             c3 = n;
  145.             c2 = (int)((c1+c3)/2);
  146.             while ((arr[c2]!=c4)&&(c1<c3))
  147.             {
  148.                 if (arr[c2]>c4)
  149.                 {
  150.                     c3 = c2-1;
  151.                     c2 = (int)((c1+c3)/2);
  152.                 }
  153.                 else
  154.                 {
  155.                     c1 = c2+1;
  156.                     c2 = (int)((c1+c3)/2);
  157.                 }
  158.             }
  159.             while ((arr[c2]<=c4)&&(c2<n)) c2++;
  160.             if (c2==n)
  161.             {
  162.                 index[2*i-1] = n;
  163.                 for (k=i;k<SumID;k++)
  164.                 {
  165.                     index[2*k] = 0;
  166.                     index[2*k+1] = 0;
  167.                 }
  168.                 i = SumID;
  169.             }
  170.             else
  171.             {
  172.                 index[2*i] = c2;
  173.                 index[2*i-1] = c2;
  174.             }
  175.             c1 = c2;
  176.             c2 = (int)((c1+c3)/2);
  177.             i++;
  178.         }
  179.         if (i==SumID) index[2*i-1] = n;
  181.         MPI_Barrier( MPI_COMM_WORLD);
  183. /*每个处理器送它的第i+1段给处理器Pi，从而使得第i个处理器含有所有处理器的第i段数据(i=0,…,P-1)，，对应于算法13.5步骤（6）*/
  185.         j = 0;
  186.         for (i=0;i<SumID;i++)
  187.         {
  188.             if (i==MyID)
  189.             {
  190.                 temp1[i] = index[2*i+1]-index[2*i];
  191.                 for (n=0;n<SumID;n++)
  192.                     if (n!=MyID)
  193.                 {
  194.                     k = index[2*n+1]-index[2*n];
  195.                     MPI_Send(&k, sizeof(int), MPI_CHAR, n, MULTI_LEN+MyID,MPI_COMM_WORLD);
  196.                 }
  198.             }
  199.             else
  200.             {
  201.                 MPI_Recv(&temp1[i], sizeof(int), MPI_CHAR, i,MULTI_LEN+i, MPI_COMM_WORLD, &status[j++]);
  202.             }
  203.         }
  205.         MPI_Barrier(MPI_COMM_WORLD);
  207.         j = 0;
  208.         k = 0;
  209.         l = 0;
  211.         for (i=0;i<SumID;i++)
  212.         {
  213.             MPI_Barrier(MPI_COMM_WORLD);
  215.             if (i==MyID)
  216.             {
  217.                 for (n=index[2*i];n<index[2*i+1];n++)
  218.                     arr1[k++] = arr[n];
  219.             }
  221.             MPI_Barrier(MPI_COMM_WORLD);
  223.             if (i==MyID)
  224.             {
  225.                 for (n=0;n<SumID;n++)
  226.                     if (n!=MyID)
  227.                 {
  228.                     MPI_Send(&arr[index[2*n]], sizeof(int)*(index[2*n+1]-index[2*n]),MPI_CHAR, n, MULTI_TYPE+MyID, MPI_COMM_WORLD);
  229.                 }
  231.             }
  232.             else
  233.             {
  234.                 l = temp1[i];
  235.                 MPI_Recv(&arr1[k], l*sizeof(int), MPI_CHAR, i ,MULTI_TYPE+i, MPI_COMM_WORLD, &status[j++]);
  236.                 k=k+l;
  237.             }
  239.             MPI_Barrier(MPI_COMM_WORLD);
  240.         }
  241.         mylength = k;
  242.         MPI_Barrier(MPI_COMM_WORLD);
  244. /*每个处理器再通过P路归并排序将上一步的到的数据排序；从而这n个数据便是有序的，，对应于算法13.5步骤（7） */
  245.         k = 0;
  246.         multimerge(arr1,temp1,arr,&k,SumID);
  247.         MPI_Barrier(MPI_COMM_WORLD);
  248.     }
  250.     printf("On node %d the sorted data is : n",MyID);
  251.     for (i=0;i<mylength;i++)
  252.         printf("%d : ",arr[i]);
  253.     printf("n");
  254. }
  257. /*输出错误信息*/
  258. merror(char* ch)
  259. {
  260.     printf("%sn",ch);
  261.     exit(1);
  262. }
  265. /*串行快速排序算法*/
  266. quicksort(int *datas,int bb,int ee)
  267. {
  268.     int tt,i,j;
  269.     tt = datas[bb];
  270.     i = bb;
  271.     j = ee;
  273.     if (i<j)
  274.     {
  275.         while(i<j)
  276.         {
  277.             while ((i<j)&&(tt<=datas[j])) j--;
  278.             if (i<j)
  279.             {
  280.                 datas[i] = datas[j];
  281.                 i++;
  282.                 while ((i<j)&&(tt>datas[i])) i++;
  283.                 if (i<j)
  284.                 {
  285.                     datas[j] = datas[i];
  286.                     j--;
  287.                     if (i==j) datas[i] = tt;
  288.                 }
  289.                 else datas[j] = tt;
  290.             } else datas[i] = tt;
  291.         }
  293.         quicksort(datas,bb,i-1);
  294.         quicksort(datas,i+1,ee);
  295.     }
  296. }
  299. /*串行多路归并算法*/
  300. multimerge(int *data1,int *ind,int *data,int *iter,int SumID)
  301. {
  302.     int i,j,n;
  304.     j = 0;
  305.     for (i=0;i<SumID;i++)
  306.         if (ind[i]>0)
  307.     {
  308.         ind[j++] = ind[i];
  309.         if (j<i+1) ind[i] = 0;
  310.     }
  311.     if ( j>1 )
  312.     {
  313.         n = 0;
  314.         for (i=0;i<j,i+1<j;i=i+2)
  315.         {
  316.             merge(&(data1[n]),ind[i],ind[i+1],&(data[n]));
  317.             ind[i] += ind[i+1];
  318.             ind[i+1] = 0;
  319.             n += ind[i];
  320.         }
  321.         if (j%2==1 )
  322.             for (i=0;i<ind[j-1];i++) data[n++]=data1[n];
  323.         (*iter)++;
  324.         multimerge(data,ind,data1,iter,SumID);
  325.     }
  326. }
  329. merge(int *data1,int s1,int s2,int *data2)
  330. {
  331.     int i,l,m;
  333.     l = 0;
  334.     m = s1;
  335.     for (i=0;i<s1+s2;i++)
  336.     {
  337.         if (l==s1)
  338.             data2[i]=data1[m++];
  339.         else
  340.         if (m==s2+s1)
  341.             data2[i]=data1[l++];
  342.         else
  343.         if (data1[l]>data1[m])
  344.             data2[i]=data1[m++];
  345.         else
  346.             data2[i]=data1[l++];
  347.     }
  348. }