N.I. Lobachevsky State University of Niznhi Novgorod

NVIDIA
:
:
:
?

.

.

.

.



, . , . . .

.
( ) . G=(V,E) u: V R. X E . G . , G , . . .

.
(Robert Prim), 1957 . , 1930 . (Vojtěch Jarník). , (Edsger Dijkstra) 1959 . , .

, . ( ). , , . , , , , , . , .. , , , ( , ). , (, , ).

, . , ( ).

 

 

 

 

N , N
{

  1. .
  2. , .
  3. .
  4. .

}

 

void InitMas(int** p,int N)

{

int Max=1000;

int* Nodes=new int[N];

int Count=1;

for(int i=0;i

Nodes[i]=0;

 

Nodes[0]=1;

for(int k=1;k

{

int y=rand()%(N-Count);

for(int i=1;i

if(Nodes[i]==0)

if(y==0)

{

y=rand()%(Count);

for(int j=0;j

if(Nodes[j]==1)

{

if(y==0)

{

p[j][i]=rand()%(Max)+1;

p[i][j]=p[j][i];

}

else y--;

Nodes[i]=1;

Count++;

}

}

else y--;

}

 

for(int i=0;i

for(int j=i;j

if(i==j) p[j][i]=p[i][j]=0;

else if(!((p[i][j]>0)&&(p[i][j]<=Max)))

{

p[i][j]=rand()%(Max+1);

p[j][i]=p[i][j];

}

delete Nodes;

}

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

{

int n;

int minonstep;

int **graph;

int **result;

int* used;

double start;

int rank, size;

float h;

int Max=1000;

MPI_Init(&argc, &argv);

MPI_Status status;

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

MPI_Comm_size(MPI_COMM_WORLD, &size);

if(rank==0)

{

cout<<"Input number of nodes";

cout<<"\n";

cin>>n;

}

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

graph = new int* [n];

for( int i = 0; i < n; i++)

graph[i] = new int [n];

 

if(rank==0)

{

result = new int* [n];

for( int i = 0; i < n; i++)

result[i] = new int [n];

for(int i=0;i

for (int j=0;j

result[i][j]=0;

 

InitMas(graph,n);

}

for(int i=0;i

MPI_Bcast(graph[i], n, MPI_INT, 0, MPI_COMM_WORLD);

MPI_Bcast(&Max, 1, MPI_INT, 0, MPI_COMM_WORLD);

used=new int[n];

used[0]=1;

for(int i=1;i

used[i]=0;

h = n /(float)size;

int y=1;

int position = 0;

int p[3];

MPI_Barrier(MPI_COMM_WORLD);

start = MPI_Wtime();

 

 

for(int k=1;k

{

p[2]=Max+1;

for (int i = ceil(rank * h); i < (rank + 1) * h; i++)

if (used[i]!=0)

for(int j=0;j

if((graph[i][j]

{

p[0]=i;

p[1]=j;

p[2]=graph[i][j];

}

if(rank!=0)

{

MPI_Send(p,3, MPI_INT, 0, 6, MPI_COMM_WORLD);

MPI_Recv(&minonstep, 1,MPI_INT, MPI_ANY_SOURCE,13, MPI_COMM_WORLD,&status);

y=2;

used[minonstep]=1;

for (int i=rank+1; i

{

MPI_Send(&minonstep,1,MPI_INT,i,13,MPI_COMM_WORLD);

y++;

}

}

else

{

for(int i=1;i

{

int d[3];

MPI_Recv(d,3,MPI_INT,MPI_ANY_SOURCE,6,MPI_COMM_WORLD, &status);

if(d[2]

{

p[0]=d[0];

p[1]=d[1];

p[2]=d[2];

}

}

used[p[1]]=1;

result[p[0]][p[1]]=graph[p[0]][p[1]];

result[p[1]][p[0]]=graph[p[1]][p[0]];

y=2;

for (int i=1; i

{

MPI_Send(&p[1],1,MPI_INT,i,13,MPI_COMM_WORLD);

y++;

}

}

}

 

if(rank==0)

{

double end = MPI_Wtime();

double time = end - start;

cout<<"\n";

cout<<"\n"<

char let;

cin>> let;

delete result;

}

delete graph,used;

MPI_Finalize();

}

:


. , (x,y) c x , . "k" (n-k) . n/p , n :



O(log2p) , :


, - ( 3 , ).

(log2p) :



:

 

 


:
Intel Core 2 Duo, 2.33 MHz
Microsoft Windows 7
MS Visual Studio 2005
- 36 /.
=4 .
= 2.4
: 0.00015

, , 8410.

 

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012