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

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

并行计算

开发平台：

Unix_Linux

c.c：源码内容
  1. #include <stdio.h>
  2. #include <mpi.h>
  3. #include <math.h>
  5. int my_rank,group_size,sub_group;
  6. int n_all;
  7. double pointx[30],pointy[30];
  8. double tempx[2],tempy[2],xtemp[4],ytemp[4];
  9. MPI_Status status;
  10. int location[30];
  12. /*获得y坐标最小的点,坐标值保存到保存到tempx,tempy数组中*/
  13. void getymin( )
  14. {
  15.     int i,index=0;
  16.     double tempvalue=pointy[0];
  18.     for(i=1;i<n_all;i++)
  19.     {
  20.         if(pointy[i]<tempvalue)
  21.         {
  22.             tempvalue=pointy[i];
  23.             index=i;
  24.         }
  25.         else
  26.         {
  27. /*若y坐标相同,则取x坐标小者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
  28.             if(pointy[i]==tempvalue)
  29.                 if(pointx[index]>pointx[i])
  30.                     index = i;
  31.         }
  32.     }
  33.     tempx[0]=pointx[index];
  34.     tempy[0]=pointy[index];
  36. /*如果y坐标最小的极点只有1点,就复制该点*/
  37.     tempx[1]=tempx[0];
  38.     tempy[1]=tempy[0];
  40. /*考察极点是否多于1点*/
  41.     for(i=0;i<n_all;i++)
  42.         if((pointy[i]==tempy[1])&&(pointx[i]>tempx[1]))
  43.     {
  44. /*极点多于1点,取x坐标大者,保存最后一个极点的坐标*/
  45.         tempx[1]=pointx[i];
  46.         tempy[1]=pointy[i];
  47.     }
  48.     return;
  49. }
  52. /*获得y坐标最大的点,保存到tempx,tempy数组中*/
  53. void getymax()
  54. {
  55.     int i,index=0;
  56.     double temp=pointy[0];
  58.     for(i=1;i<n_all;i++)
  59.     {
  60.         if(pointy[i]>temp)
  61.         {
  62.             temp=pointy[i];
  63.             index=i;
  64.         }
  65.         else
  66.         {
  67. /*若y坐标相同,则取x坐标大者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
  68.             if(temp==pointy[i])
  69.                 if(pointx[i]>pointx[index])
  70.                     index=i;
  71.         }
  72.     }
  73. /*保存YMAX极点坐标*/
  74.     tempx[0]=pointx[index];
  75.     tempy[0]=pointy[index];
  77. /*如果y坐标最大的极点只有1点,就复制该点*/
  78.     tempx[1]=tempx[0];
  79.     tempy[1]=tempy[0];
  81. /*考察极点是否多于1点*/
  82.     for(i=0;i<n_all;i++)
  83.     {
  84.         if((pointy[i]==tempy[1])&&(pointx[i]<tempx[1]))
  85.         {
  86. /*极点多于1点,取x坐标小者,保存最后一个极点的坐标*/
  87.             tempx[1]=pointx[i];
  88.             tempy[1]=pointy[i];
  89.         }
  90.     }
  92.     return;
  93. }
  96. /*获得x坐标最小的点,坐标保存到tempx,tempy数组中*/
  97. void getxmin()
  98. {
  99.     int i,index=0;
  100.     double temp=pointx[0];
  102.     for(i=1;i<n_all;i++)
  103.     {
  104.         if(pointx[i]<temp)
  105.         {
  106.             temp=pointx[i];
  107.             index=i;
  108.         }
  109.         else
  110.         {
  111. /*若x坐标相同,则取y坐标大者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
  112.             if(pointx[i]==temp)
  113.                 if(pointy[index]<pointy[i])
  114.                     index=i;
  115.         }
  116.     }
  117. /*保存XMIN极点坐标*/
  118.     tempx[0]=pointx[index];
  119.     tempy[0]=pointy[index];
  121. /*如果x坐标最小的极点只有1点,就复制该点*/
  122.     tempx[1]=tempx[0];
  123.     tempy[1]=tempy[0];
  125. /*考察极点是否多于1点*/
  126.     for(i=0;i<n_all;i++)
  127.     {
  128.         if((pointx[i]==tempx[1])&&(pointy[i]<tempy[1]))
  129.         {
  130. /*极点多于1点,取y坐标小者,保存最后一个极点的坐标*/
  131.             tempx[1]=pointx[i];
  132.             tempy[1]=pointy[i];
  133.         }
  134.     }
  135.     return;
  136. }
  139. /*获得x坐标最大的点,其坐标值保存保存到tempx,tempy数组中*/
  140. void getxmax()
  141. {
  142.     int i,index=0;
  143.     double temp=pointx[0];
  145.     for(i=1;i<n_all;i++)
  146.     {
  147.         if(pointx[i]>temp)
  148.         {
  149.             temp=pointx[i];
  150.             index=i;
  151.         }
  152.         else
  153.         {
  154. /*若x坐标相同,则取y坐标小者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
  155.             if(temp==pointx[i])
  156.                 if(pointy[index]>pointy[i])
  157.                     index=i;
  158.         }
  159.     }
  160. /*保存XMAX极点坐标*/
  161.     tempx[0]=pointx[index];
  162.     tempy[0]=pointy[index];
  164. /*如果x坐标最大的极点只有1点,就复制该点*/
  165.     tempx[1]=tempx[0];
  166.     tempy[1]=tempy[0];
  168. /*考察极点是否多于1点*/
  169.     for(i=0;i<n_all;i++)
  170.     {
  171.         if((pointx[i]==tempx[1])&&(pointy[i]>tempy[1]))
  172.         {
  173. /*极点多于1点,取y坐标大者,保存第2个极点的坐标*/
  174.             tempx[1]=pointx[i];
  175.             tempy[1]=pointy[i];
  176.         }
  177.     }
  178.     return;
  179. }
  182. /*temp[x],temp[y]设置两个值的作用是为了有多个最值时，保存首尾两个，后面划分
  183. 区域时分别以这两个为端点，中间就没有其他的点了*/
  185. /*确定是属于哪一部分*/
  186. void getincludedvertex(int tag)
  187. {
  188.     double linea,lineb,dist;
  189.     int i,count=0;
  191. /*若该边已退化成一个点, 则除此点外无其它点在处理区域内*/
  192.     if((tempx[1]==tempx[0])&&(tempy[1]==tempy[0]))
  193.     {
  194.         n_all=1;
  195.         pointx[0]=tempx[1];
  196.         pointy[0]=tempy[1];
  197.     }
  198.     else
  199.     {
  200. /*根据两端点坐标确定直线的斜率和参数*/
  201.         linea=(tempy[1]-tempy[0])/(tempx[1]-tempx[0]);
  202.         lineb=tempy[1]-linea*tempx[1];
  203. /*根据点在直线的哪一侧来确定该顶点是否在处理区域内*/
  204.         for(i=0;i<n_all;i++)
  205.         {
  206.             dist=linea*pointx[i]+lineb-pointy[i];
  207.             if(tag*dist<0)
  208.             {
  209.                 pointx[count]=pointx[i];
  210.                 pointy[count++]=pointy[i];
  211.             }
  212.         }
  213. /*调整各点的位置以加入两个端点*/
  214.         for(i=0;i<count;i++)
  215.         {
  216.             pointx[count-i]=pointx[count-1-i];
  217.             pointy[count-i]=pointy[count-1-i];
  218.         }
  219. /*将两个端点放在两端*/
  220.         pointx[0]=tempx[0];
  221.         pointy[0]=tempy[0];
  222.         pointx[count+1]=tempx[1];
  223.         pointy[count+1]=tempy[1];
  224.         count+=2;
  225. /*更新n_all为要处理的新的表列中的点的数量*/
  226.         n_all=count;
  227.     }
  228. }
  231. /*确定此点的后一点的序号，并放入location[]中*/
  232. void nextindex(int i,int x,int y)
  233. {
  234.     double x1,y1,temp,valuemax=0;
  235.     int j;
  237.     x1=pointx[i];
  238.     y1=pointy[i];
  240. /*遍历各顶, 将有最小极角点的序号作为自己的Nextindex值*/
  241.     for(j=0;j<n_all;j++)
  242.     {
  243.         if(((pointx[j]-x1)*x+(pointy[j]-y1)*y)>0)
  244.         {
  245. /*由极角的余弦或其余角的正弦来判断极角大小*/
  246.             temp=((pointx[j]-x1)*x+(pointy[j]-y1)*y)/(sqrt((pointx[j]-x1)*(pointx[j]-x1)+(pointy[j]-y1)*(pointy[j]-y1)));
  247.             if(temp>valuemax)
  248.             {
  249.                 location[i]=j;
  250.                 valuemax=temp;
  251.             }
  252.         }
  253.     }
  254.     if(valuemax==0)
  255.         location[i]=-1;
  256. }
  259. /*输出点的序列*/
  260. void output(int rank)
  261. {
  262.     int j=0,index,temp;
  263.     double xtem,ytem;
  264.     int flag=0;
  266.     printf("输出的是第%d部分的点n",rank/sub_group);
  267.     if(rank==0)
  268.         flag=1;
  269.     if(flag==0)
  270.         if(!((pointx[n_all-1]==tempx[0])&&
  271.         (pointy[n_all-1]==tempy[0])))
  272.             flag=1;
  274. /*将nextindex反向,使输出的点按逆时针方向,以保证各行主处理器输出顺序相邻*/
  275.     index=location[j];
  276.     while(location[index]!=-1)
  277.     {
  278.         temp=location[index];
  279.         location[index]=j;
  280.         j=index;
  281.         index=temp;
  282.     }
  283.     location[index]=j;
  284.     location[0]=-1;
  286. /*按照索引顺序输出各点*/
  287.     j=n_all-1;
  288.     while(location[j]!=-1)
  289.     {
  290.         if(!((j==n_all-1)&&(flag==0)))
  291.         {
  292.             printf("%.2lf,%.2lfn",pointx[j],pointy[j]);
  293.             xtem=pointx[j];
  294.             ytem=pointy[j];
  295.         }
  296.         j=location[j];
  297.     }
  299. /*判断是不是重合*/
  300.     if(!((j==n_all-1)&&(flag==0)))
  301.     {
  302.         printf("%.2lf,%.2lfn",pointx[j],pointy[j]);
  303.         xtem=pointx[j];
  304.         ytem=pointy[j];
  305.     }
  307.     if((rank==3*sub_group)&&!((xtem==tempx[1])&&(ytem==tempy[1])))
  308.         printf("%.2lf,%.2lfn",tempx[1],tempy[1]);
  309.     return;
  310. }
  313. main(int argc,char *argv[])
  314. {
  315.     int i;
  316.     MPI_Init(&argc,&argv);
  317.     MPI_Comm_size(MPI_COMM_WORLD,&group_size);
  318.     MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
  320. /*本程序至少要4个处理器才能正常执行*/
  321.     if (group_size < 4)
  322.     {
  323.         if (my_rank==0)
  324.         {
  325.             printf("Need 4 or more processors to run!n");
  326.         }
  327.         MPI_Finalize();
  328.         exit(0);
  329.     }
  331.     if(my_rank==0)
  332.     {
  333.         printf("please input all the vertexes!nfirst is number!n");
  334.         printf("please input the Number:");
  335.         scanf("%d",&n_all);
  336.         printf("please input the vertex:n");
  337.         for(i=0;i<n_all;i++)
  338.         {
  339.             scanf("%lf",&pointx[i]);
  340.             scanf("%lf",&pointy[i]);
  341.         }
  342.     }
  343. /*处理器0接收输入的顶点坐标*/
  345.     sub_group = group_size / 4;
  347.     MPI_Bcast(&n_all,1,MPI_INT,0,MPI_COMM_WORLD);
  348. /*广播顶点总数*/
  349. /*第1行的行主处理器,向第2,3,4行的行主处理器发送顶点坐标，对应于算法17.6步骤(1.1)*/
  350.     if(my_rank==0)
  351.     {
  352.         for(i=1;i<4;i++)
  353.         {
  354.             MPI_Send(pointx,n_all,MPI_DOUBLE,i*sub_group,i,MPI_COMM_WORLD);
  355.             MPI_Send(pointy,n_all,MPI_DOUBLE,i*sub_group,i,MPI_COMM_WORLD);
  356.         }
  357.     }
  358.     if((my_rank>0)&&(my_rank<4*sub_group)&&(my_rank%sub_group==0))
  359.     {
  360.         MPI_Recv(pointx,n_all,MPI_DOUBLE,0,my_rank/sub_group,MPI_COMM_WORLD,&status);
  361.         MPI_Recv(pointy,n_all,MPI_DOUBLE,0,my_rank/sub_group,MPI_COMM_WORLD,&status);
  362.     }
  364.     MPI_Barrier(MPI_COMM_WORLD);
  366. /*计算极点,并把他们的坐标分别存储在4个行主处理器中*/
  367. /*第1行的行主处理器计算YMIN*/
  368.     if(my_rank==0)
  369.         getymin();
  370. /*第2行的行主处理器计算XMAX*/
  371.     if(my_rank==sub_group)
  372.         getxmax();
  373. /*第3行的行主处理器计算YMAX*/
  374.     if(my_rank==2*sub_group)
  375.         getymax();
  376. /*第4行的行主处理器计算XMIN*/
  377.     if(my_rank==3*sub_group)
  378.         getxmin();
  380.     MPI_Barrier(MPI_COMM_WORLD);
  382. /*将四条由极点组成的边存储到每一行的行主处理器上*/
  383.     if((my_rank>0)&&(my_rank<4*sub_group)&&(my_rank%sub_group==0))
  384.     {
  385. /*各行主处理器发送消息给进程0, 告知极点坐标*/
  386.         MPI_Send(&tempx[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);
  387.         MPI_Send(&tempy[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);
  388.     }
  389.     if(my_rank==0)
  390.     {
  391.         for(i=1;i<4;i++)
  392.         {
  393.             MPI_Recv(&xtemp[i],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD,&status);
  394.             MPI_Recv(&ytemp[i],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD,&status);
  395.         }
  396.         xtemp[0]=tempx[1];
  397.         ytemp[0]=tempy[1];
  398.         tempx[1]=xtemp[3];
  399.         tempy[1]=ytemp[3];
  401.         for(i=1;i<4;i++)
  402.         {
  403. /*进程0将相关的极点坐标发送给各行主处理器*/
  404.             MPI_Send(&xtemp[i-1],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD);
  405.             MPI_Send(&ytemp[i-1],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD);
  406.         }
  407.     }
  408.     else
  409.     {
  410.         if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
  411.         {
  412. /*各行主处理器接收进程0的消息,得到并存储由极点构成的边*/
  413.             MPI_Recv(&tempx[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD,&status);
  414.             MPI_Recv(&tempy[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD,&status);
  415.         }
  416.     }
  418.     MPI_Barrier(MPI_COMM_WORLD);
  420. /*确定四边形中的顶点，并将其余顶点归入四个三角区中*/
  421. /*四个行主处理器同时判断顶点是否处于自身所在的区域 */
  423. /*保留属于该区域内的点，每个行主处理器得到要处理的新的表列*/
  424. /*下面得到属于此范围的点*/
  425.     if(my_rank==0)
  426.         getincludedvertex(-1);
  427.     if(my_rank==sub_group)
  428.         getincludedvertex(-1);
  429.     if(my_rank==2*sub_group)
  430.         getincludedvertex(1);
  431.     if(my_rank==3*sub_group)
  432.         getincludedvertex(1);
  434.     MPI_Barrier(MPI_COMM_WORLD);
  436.     if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
  437.     {
  438.         for(i=1;i<sub_group;i++)
  439.         {
  440. /*各行主处理器向该行的其他处理器发送新的表列中的顶点数量*/
  441.             MPI_Send(&n_all,1,MPI_INT,my_rank+i,i,MPI_COMM_WORLD);
  442.         }
  443.     }
  444.     else if (my_rank<4*sub_group)
  445.     {
  446. /*各处理器从该行的主处理器接收新的表列中的顶点数量*/
  447.         MPI_Recv(&n_all,1,MPI_INT,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
  448.     }
  450.     MPI_Barrier(MPI_COMM_WORLD);
  452.     if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
  453.     {
  454.         for(i=1;i<sub_group;i++)
  455.         {
  456. /*各行主处理器向该行的其他处理器发送新的表列中的顶点坐标*/
  457.             MPI_Send(pointx,n_all,MPI_DOUBLE,my_rank+i,i,MPI_COMM_WORLD);
  458.             MPI_Send(pointy,n_all,MPI_DOUBLE,my_rank+i,i,MPI_COMM_WORLD);
  459.         }
  460.     }
  461.     else if (my_rank<4*sub_group)
  462.     {
  463.         MPI_Recv(pointx,n_all,MPI_DOUBLE,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
  464.         MPI_Recv(pointy,n_all,MPI_DOUBLE,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
  465.     }
  467.     MPI_Barrier(MPI_COMM_WORLD);
  469. /*每一行上的处理器对属于同一区域的点计算极角；将有最小极角点的序号作为自己的Nexindex值建立各进程中点的nextindex索引*/
  470.     if((n_all>1)&&(my_rank<4*sub_group))
  471.     {
  472.         for(i=my_rank%sub_group;i<n_all-1;i+=sub_group)
  473.         {
  474.             if(my_rank/sub_group==0)
  475.                 nextindex(i,-1,0);
  476.             if(my_rank/sub_group==1)
  477.                 nextindex(i,0,-1);
  478.             if(my_rank/sub_group==2)
  479.                 nextindex(i,1,0);
  480.             if(my_rank/sub_group==3)
  481.                 nextindex(i,0,1);
  482.         }
  483.     }
  485.     MPI_Barrier(MPI_COMM_WORLD);
  487. /*将个进程中点的nextindex索引发送到中心结点*/
  488.     if((my_rank<4*sub_group)&&(my_rank%sub_group!=0))
  489.     {
  490.         for(i=my_rank%sub_group;i<n_all-1;i+=sub_group)
  491.             MPI_Send(&location[i],1,MPI_INT,my_rank/sub_group*sub_group,my_rank,MPI_COMM_WORLD);
  492.     }
  493.     else if (my_rank<4*sub_group)
  494.     {
  495.         for(i=1;i<n_all-1;i++)
  496.         {
  497.             if(i%sub_group!=0)
  498.             {
  499.                 MPI_Recv(&location[i],1,MPI_INT,my_rank+i%sub_group,my_rank+i%sub_group,MPI_COMM_WORLD,&status);
  500.             }
  501.         }
  502.     }
  504.     MPI_Barrier(MPI_COMM_WORLD);
  505.     location[n_all-1]=-1;
  507.     MPI_Barrier(MPI_COMM_WORLD);
  509. /*每个行主处理器按照点的Nextindex索引输出自己处理器上的点)*/
  510.     if(my_rank==0)
  511.     {
  512. /*第1行输出各顶点的坐标*/
  513.         output(my_rank);
  514. /*将最后的一个点传送给第2行主处理器判断是不是相同*/
  515.         MPI_Send(&pointx[0],1,MPI_DOUBLE,sub_group,sub_group,MPI_COMM_WORLD);
  516.         MPI_Send(&pointy[0],1,MPI_DOUBLE,sub_group,sub_group,MPI_COMM_WORLD);
  517. /*将起始点传送给第4行主处理器判断是不是相同*/
  518.         MPI_Send(&pointx[n_all-1],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
  519.         MPI_Send(&pointy[n_all-1],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
  520.     }
  521.     if(my_rank==sub_group)
  522.     {
  523. /*接收第1行主处理器发送过来的最后一个点,也即本行起始点,以判断是不是相同*/
  524.         MPI_Recv(&tempx[0],1,MPI_DOUBLE,0,sub_group,MPI_COMM_WORLD,&status);
  525.         MPI_Recv(&tempy[0],1,MPI_DOUBLE,0,sub_group,MPI_COMM_WORLD,&status);
  526. /*将最后的一个点传送给第3行主处理器判断是不是相同*/
  527.         MPI_Send(&pointx[0],1,MPI_DOUBLE,2*sub_group,2*sub_group,MPI_COMM_WORLD);
  528.         MPI_Send(&pointy[0],1,MPI_DOUBLE,2*sub_group,2*sub_group,MPI_COMM_WORLD);
  529.     }
  530.     if(my_rank==2*sub_group)
  531.     {
  533.         MPI_Recv(&tempx[0],1,MPI_DOUBLE,sub_group,2*sub_group,MPI_COMM_WORLD,&status);
  534.         MPI_Recv(&tempy[0],1,MPI_DOUBLE,sub_group,2*sub_group,MPI_COMM_WORLD,&status);
  536.         MPI_Send(&pointx[0],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
  537.         MPI_Send(&pointy[0],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
  538.     }
  539.     if(my_rank==3*sub_group)
  540.     {
  542.         MPI_Recv(&tempx[0],1,MPI_DOUBLE,2*sub_group,3*sub_group,MPI_COMM_WORLD,&status);
  543.         MPI_Recv(&tempy[0],1,MPI_DOUBLE,2*sub_group,3*sub_group,MPI_COMM_WORLD,&status);
  545.         MPI_Recv(&tempx[1],1,MPI_DOUBLE,0,3*sub_group,MPI_COMM_WORLD,&status);
  546.         MPI_Recv(&tempy[1],1,MPI_DOUBLE,0,3*sub_group,MPI_COMM_WORLD,&status);
  547.     }
  549.     MPI_Barrier(MPI_COMM_WORLD);
  551. /*第2行输出各顶点的坐标*/
  552.     if(my_rank==sub_group)
  553.         output(my_rank);
  555.     MPI_Barrier(MPI_COMM_WORLD);
  557. /*第3行输出各顶点的坐标*/
  558.     if(my_rank==2*sub_group)
  559.         output(my_rank);
  561.     MPI_Barrier(MPI_COMM_WORLD);
  563. /*第4行输出各顶点的坐标*/
  564.     if(my_rank==3*sub_group)
  565.         output(my_rank);
  567.     MPI_Barrier(MPI_COMM_WORLD);
  569.     MPI_Finalize();
  570. }