c.c

《并行算法实践》附带的mpi源程序

    j=n_all-1;
    while(location[j]!=-1)
    {
        if(!((j==n_all-1)&&(flag==0)))
        {
            printf("%.2lf,%.2lf\n",pointx[j],pointy[j]);
            xtem=pointx[j];
            ytem=pointy[j];
        }
        j=location[j];
    }

	/*判断是不是重合*/
    if(!((j==n_all-1)&&(flag==0)))
    {
        printf("%.2lf,%.2lf\n",pointx[j],pointy[j]);
        xtem=pointx[j];
        ytem=pointy[j];
    }

    if((rank==3*sub_group)&&!((xtem==tempx[1])&&(ytem==tempy[1])))
        printf("%.2lf,%.2lf\n",tempx[1],tempy[1]);
    return;
}


main(int argc,char *argv[])
{
    int i;
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&group_size);
    MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);

	/*本程序至少要4个处理器才能正常执行*/
    if (group_size < 4)
    {
        if (my_rank==0)
        {
            printf("Need 4 or more processors to run!\n");
        }
        MPI_Finalize();
        exit(0);
    }

    if(my_rank==0)
    {
        printf("please input all the vertexes!\nfirst is number!\n");
        printf("please input the Number:");
        scanf("%d",&n_all);
        printf("please input the vertex:\n");
        for(i=0;i<n_all;i++)
        {
            scanf("%lf",&pointx[i]);
            scanf("%lf",&pointy[i]);
        }
    }
	/*处理器0接收输入的顶点坐标*/

    sub_group = group_size / 4;

    MPI_Bcast(&n_all,1,MPI_INT,0,MPI_COMM_WORLD);
	/*广播顶点总数*/
	/*第1行的行主处理器,向第2,3,4行的行主处理器发送顶点坐标，对应于算法17.6步骤(1.1)*/
    if(my_rank==0)
    {
        for(i=1;i<4;i++)
        {
            MPI_Send(pointx,n_all,MPI_DOUBLE,i*sub_group,i,MPI_COMM_WORLD);
            MPI_Send(pointy,n_all,MPI_DOUBLE,i*sub_group,i,MPI_COMM_WORLD);
        }
    }
    if((my_rank>0)&&(my_rank<4*sub_group)&&(my_rank%sub_group==0))
    {
        MPI_Recv(pointx,n_all,MPI_DOUBLE,0,my_rank/sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(pointy,n_all,MPI_DOUBLE,0,my_rank/sub_group,MPI_COMM_WORLD,&status);
    }

    MPI_Barrier(MPI_COMM_WORLD);

	/*计算极点,并把他们的坐标分别存储在4个行主处理器中*/
	/*第1行的行主处理器计算YMIN*/
    if(my_rank==0)
        getymin();
	/*第2行的行主处理器计算XMAX*/
    if(my_rank==sub_group)
        getxmax();
	/*第3行的行主处理器计算YMAX*/
    if(my_rank==2*sub_group)
        getymax();
	/*第4行的行主处理器计算XMIN*/
    if(my_rank==3*sub_group)
        getxmin();

    MPI_Barrier(MPI_COMM_WORLD);

	/*将四条由极点组成的边存储到每一行的行主处理器上*/
    if((my_rank>0)&&(my_rank<4*sub_group)&&(my_rank%sub_group==0))
    {
		/*各行主处理器发送消息给进程0, 告知极点坐标*/
        MPI_Send(&tempx[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);
        MPI_Send(&tempy[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);
    }
    if(my_rank==0)
    {
        for(i=1;i<4;i++)
        {
            MPI_Recv(&xtemp[i],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD,&status);
            MPI_Recv(&ytemp[i],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD,&status);
        }
        xtemp[0]=tempx[1];
        ytemp[0]=tempy[1];
        tempx[1]=xtemp[3];
        tempy[1]=ytemp[3];

        for(i=1;i<4;i++)
        {
			/*进程0将相关的极点坐标发送给各行主处理器*/
            MPI_Send(&xtemp[i-1],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD);
            MPI_Send(&ytemp[i-1],1,MPI_DOUBLE,i*sub_group,i*sub_group,MPI_COMM_WORLD);
        }
    }
    else
    {
        if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
        {
			/*各行主处理器接收进程0的消息,得到并存储由极点构成的边*/
            MPI_Recv(&tempx[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD,&status);
            MPI_Recv(&tempy[1],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD,&status);
        }
    }

    MPI_Barrier(MPI_COMM_WORLD);

	/*确定四边形中的顶点，并将其余顶点归入四个三角区中*/
	/*四个行主处理器同时判断顶点是否处于自身所在的区域 */

	/*保留属于该区域内的点，每个行主处理器得到要处理的新的表列*/
	/*下面得到属于此范围的点*/
    if(my_rank==0)
        getincludedvertex(-1);
    if(my_rank==sub_group)
        getincludedvertex(-1);
    if(my_rank==2*sub_group)
        getincludedvertex(1);
    if(my_rank==3*sub_group)
        getincludedvertex(1);

    MPI_Barrier(MPI_COMM_WORLD);

    if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
    {
        for(i=1;i<sub_group;i++)
        {
			/*各行主处理器向该行的其他处理器发送新的表列中的顶点数量*/
            MPI_Send(&n_all,1,MPI_INT,my_rank+i,i,MPI_COMM_WORLD);
        }
    }
    else if (my_rank<4*sub_group)
    {
		/*各处理器从该行的主处理器接收新的表列中的顶点数量*/
        MPI_Recv(&n_all,1,MPI_INT,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
    }

    MPI_Barrier(MPI_COMM_WORLD);

    if((my_rank<4*sub_group)&&(my_rank%sub_group==0))
    {
        for(i=1;i<sub_group;i++)
        {
			/*各行主处理器向该行的其他处理器发送新的表列中的顶点坐标*/
            MPI_Send(pointx,n_all,MPI_DOUBLE,my_rank+i,i,MPI_COMM_WORLD);
            MPI_Send(pointy,n_all,MPI_DOUBLE,my_rank+i,i,MPI_COMM_WORLD);
        }
    }
    else if (my_rank<4*sub_group)
    {
        MPI_Recv(pointx,n_all,MPI_DOUBLE,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(pointy,n_all,MPI_DOUBLE,my_rank/sub_group*sub_group,my_rank%sub_group,MPI_COMM_WORLD,&status);
    }

    MPI_Barrier(MPI_COMM_WORLD);

	/*每一行上的处理器对属于同一区域的点计算极角；将有最小极角点的序号作为自己的Nexindex值建立各进程中点的nextindex索引*/
    if((n_all>1)&&(my_rank<4*sub_group))
    {
        for(i=my_rank%sub_group;i<n_all-1;i+=sub_group)
        {
            if(my_rank/sub_group==0)
                nextindex(i,-1,0);
            if(my_rank/sub_group==1)
                nextindex(i,0,-1);
            if(my_rank/sub_group==2)
                nextindex(i,1,0);
            if(my_rank/sub_group==3)
                nextindex(i,0,1);
        }
    }

    MPI_Barrier(MPI_COMM_WORLD);

	/*将个进程中点的nextindex索引发送到中心结点*/
    if((my_rank<4*sub_group)&&(my_rank%sub_group!=0))
    {
        for(i=my_rank%sub_group;i<n_all-1;i+=sub_group)
            MPI_Send(&location[i],1,MPI_INT,my_rank/sub_group*sub_group,my_rank,MPI_COMM_WORLD);
    }
    else if (my_rank<4*sub_group)
    {
        for(i=1;i<n_all-1;i++)
        {
            if(i%sub_group!=0)
            {
                MPI_Recv(&location[i],1,MPI_INT,my_rank+i%sub_group,my_rank+i%sub_group,MPI_COMM_WORLD,&status);
            }
        }
    }

    MPI_Barrier(MPI_COMM_WORLD);
    location[n_all-1]=-1;

    MPI_Barrier(MPI_COMM_WORLD);

	/*每个行主处理器按照点的Nextindex索引输出自己处理器上的点)*/
    if(my_rank==0)
    {
		/*第1行输出各顶点的坐标*/
        output(my_rank);
		/*将最后的一个点传送给第2行主处理器判断是不是相同*/
        MPI_Send(&pointx[0],1,MPI_DOUBLE,sub_group,sub_group,MPI_COMM_WORLD);
        MPI_Send(&pointy[0],1,MPI_DOUBLE,sub_group,sub_group,MPI_COMM_WORLD);
		/*将起始点传送给第4行主处理器判断是不是相同*/
        MPI_Send(&pointx[n_all-1],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
        MPI_Send(&pointy[n_all-1],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
    }
    if(my_rank==sub_group)
    {
		/*接收第1行主处理器发送过来的最后一个点,也即本行起始点,以判断是不是相同*/
        MPI_Recv(&tempx[0],1,MPI_DOUBLE,0,sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(&tempy[0],1,MPI_DOUBLE,0,sub_group,MPI_COMM_WORLD,&status);
		/*将最后的一个点传送给第3行主处理器判断是不是相同*/
        MPI_Send(&pointx[0],1,MPI_DOUBLE,2*sub_group,2*sub_group,MPI_COMM_WORLD);
        MPI_Send(&pointy[0],1,MPI_DOUBLE,2*sub_group,2*sub_group,MPI_COMM_WORLD);
    }
    if(my_rank==2*sub_group)
    {

        MPI_Recv(&tempx[0],1,MPI_DOUBLE,sub_group,2*sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(&tempy[0],1,MPI_DOUBLE,sub_group,2*sub_group,MPI_COMM_WORLD,&status);

        MPI_Send(&pointx[0],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
        MPI_Send(&pointy[0],1,MPI_DOUBLE,3*sub_group,3*sub_group,MPI_COMM_WORLD);
    }
    if(my_rank==3*sub_group)
    {

        MPI_Recv(&tempx[0],1,MPI_DOUBLE,2*sub_group,3*sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(&tempy[0],1,MPI_DOUBLE,2*sub_group,3*sub_group,MPI_COMM_WORLD,&status);

        MPI_Recv(&tempx[1],1,MPI_DOUBLE,0,3*sub_group,MPI_COMM_WORLD,&status);
        MPI_Recv(&tempy[1],1,MPI_DOUBLE,0,3*sub_group,MPI_COMM_WORLD,&status);
    }

    MPI_Barrier(MPI_COMM_WORLD);

	/*第2行输出各顶点的坐标*/
    if(my_rank==sub_group)
        output(my_rank);

    MPI_Barrier(MPI_COMM_WORLD);

	/*第3行输出各顶点的坐标*/
    if(my_rank==2*sub_group)
        output(my_rank);

    MPI_Barrier(MPI_COMM_WORLD);

	/*第4行输出各顶点的坐标*/
    if(my_rank==3*sub_group)
        output(my_rank);

    MPI_Barrier(MPI_COMM_WORLD);

    MPI_Finalize();
}