seek.cpp

利用分治算法求一个数组首个零的位置

#include <mpi.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>



#define MAX_SLAVE_NUM	32

#define	MAX_ARRAY_LEN	1024

#define ARRAY_LEN_DEFAUL 256

#define ROOT	0



int iSlaveNum, iArrayLen;

int *iData, head;

int iTaskSize, numprocs, myid, ans[3];

MPI_Status status;





int iDiv()

//返回：1、2、3：分得一、二、三个小任务

{

	int k = iSlaveNum - (2*myid+1);

	if(k>0)

		return 3;

	else if(k==0)

		return 2;

	else

		return 1;

}



void mySeek()

//整理该子树的零点位置

{	

	int i, k;



	for(k=0; k<iTaskSize; k++)

		if(iData[k] == 0)

		{

			ans[0]=k+head;

			break;

		}

	i=iDiv();

	if(i>=2)

	{

		//接收左子数据：左子的第一个零位置

		MPI_Recv(&ans[1], 1, MPI_INT, 2*myid+1, 1, MPI_COMM_WORLD, &status);

		if(i==3)

			//接收右子数据：右子的第一个零位置

			MPI_Recv(&ans[2], 1, MPI_INT, 2*myid+2, 1, MPI_COMM_WORLD, &status);



	}

	//取ans[]最小值，放入ans[0]

	if(i==3)

	{

		if(ans[1]>ans[2])

			ans[1]=ans[2];		

		if(ans[0]>ans[1])

			ans[0]=ans[1];

	}else if(i==2)

	{

		if(ans[0]>ans[1])

			ans[0]=ans[1];

	}

//	printf("(%d)",ans[0]);



}



void masterInit()

{

	int i;

	iData = new int[iArrayLen];

	srand( (unsigned)time( NULL ) );

	ans[0]=iArrayLen+10;



	printf("\nArray list:\n======   ==============================================================");

	for( i = 0;   i < iArrayLen; i++ )

	{

		iData[i]=rand()%10000;

		if(i>0 && (iData[i-1] & iData[i] < i*40))

			iData[i] = 0;

		if(i%8==0)

			printf("\n[%3d]\t", i);

		printf( "%6d\t", iData[i] );

	}

	printf("\n======   ==============================================================\n");

}



void main(int argc, char *argv[])

{

	int i;

	MPI_Init(&argc,&argv);

	MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

	MPI_Comm_rank(MPI_COMM_WORLD,&myid);

	if(numprocs>=MAX_SLAVE_NUM)

		printf("WARNING:\tsalve num is too large! It will be 32");

	iSlaveNum=numprocs-1;

	printf("\n<myid=%d>", myid);



	if( argc>1 )

	{

		iArrayLen=atoi(argv[1]);

	}

	if( (argc<2) || (iArrayLen>MAX_ARRAY_LEN) )

	{

		iArrayLen=ARRAY_LEN_DEFAUL;

		printf("usage: exeName [array_Length]\n");

		printf("array_length<=1024\n\n");

	}

	

	if(myid == 0)

	{

		printf("\n\n<slaveNum: %d>\n", iSlaveNum);

		masterInit();



		if(iSlaveNum == 0)

		{//if no slave procs

			for(i=0; i<iArrayLen; i++)

				if(iData[i]==0)

				{

					ans[0] = i;

					break;

				}

		}else

		{

			//分配任务

			iTaskSize = iArrayLen/iSlaveNum;

			for(i=1; i<=iSlaveNum; i++)

				//向所有slave发送数据：数组总长

				MPI_Send(&iArrayLen, 1, MPI_INT, i, 1, MPI_COMM_WORLD);

			for(i=1; i<=iSlaveNum; i++)

				//向所有slave发送数据：与它相关的数组元素

				MPI_Send(&iData[(i-1)*iTaskSize], iTaskSize, MPI_INT, i, 2, MPI_COMM_WORLD);

			//主进程作零头工作

			if( (i=iArrayLen%iSlaveNum)!=0 )

			{

				for(i=iArrayLen-i; i<iArrayLen; i++)

					if(iData[i]==0)

					{

						ans[0] = i;

						break;

					}

			}

			mySeek();

		}

		if(ans[0]<iArrayLen)

			printf("\nAnswer: %d\n", ans[0]);

		else

			printf("\nNO zero value!\n");

	}

	else

	{

		//接收根结点数据：数组长度值

		MPI_Recv(&iArrayLen, 1, MPI_INT, ROOT, 1, MPI_COMM_WORLD, &status);

		ans[0]=iArrayLen+10;

		iTaskSize = iArrayLen / iSlaveNum;

		head = (myid - 1) * iTaskSize;

		iData = new int[iTaskSize];

		//接收根结点数据：特定段的数组值

		MPI_Recv(iData, iTaskSize, MPI_INT, ROOT, 2, MPI_COMM_WORLD, &status);



		mySeek();

		//向父节点发送数据：本棵子树的零位置

		MPI_Send(&ans[0], 1, MPI_INT, (myid-1)/2, 1, MPI_COMM_WORLD);

	}

	MPI_Finalize();



}