1) I want the MPI version of the following 'c' code :
/*
This program is an implementation of Kruskal's Algorithm for
determining a minimal spanning tree for a connected, non-directed,
weighted graph. This implementation is designed specifically
for the test data required by the project.
*/
#include <stdio.h>
#define N 6 /* number of vertices */
#define M 15 /* number of edges in graph */
int U[N];
/* function prototypes */
void makeset (int i);
int find (int i);
void merge (int p, int q);
int equal (int p, int q);
void initial (int n);
void test_univ (void);
void pause (void); /* used mainly for test purposes */
/* function definitions */
int main()
{ int W[N][N] = {0,2,4,1,3,2, /* weighted graph */
2,0,6,4,5,1,
4,6,0,4,2,1,
1,4,4,0,5,4,
3,5,2,5,0,6,
2,1,1,4,6,0};
int E[M][3]; /* complete set of edges */
int F[N-1][3]; /* set of edges in min. span. tree */
int num_edges = 0; /* num of edges in min. span. tree */
int next_edge = 0; /* next edge not yet considered */
int weight = 0; /* minimal spanning tree weight */
int a, b, c, i, j, k; /* counter/placeholder variables */
/* initialize set of edges */
k = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (j > i)
{ E[k][0] = i; /* first vertex of edge */
E[k][1] = j; /* second vertex of edge */
E[k][2] = W[i][j]; /* weight of edge */
k++;
}
/* display set of edges - before sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %3d", E[i][j]);
printf("\n");
}
pause();
/* sort set of edges in non-decreasing order by weight - bubblesort */
for (i = M - 1; i > 0; i--)
for (j = 0; j < i; j++)
if (E[j][2] > E[j+1][2])
{ a = E[j][0];
b = E[j][1];
c = E[j][2];
E[j][0] = E[j+1][0];
E[j][1] = E[j+1][1];
E[j][2] = E[j+1][2];
E[j+1][0] = a;
E[j+1][1] = b;
E[j+1][2] = c;
}
/* display set of edges - after sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %3d", E[i][j]);
printf("\n");
}
/* create n disjoint subsets */
initial (N);
/* initialize set of edges in min. span. tree to empty */
for (i = 0; i < N - 1; i++)
for (j = 0; j < 3; j++)
F[i][j] = -1; /* '-1' denotes 'empty' */
test_univ();
/* find minimal spanning tree */
while (num_edges < N - 1)
{ a = E[next_edge][0];
b = E[next_edge][1];
i = find(a);
j = find(b);
if (!equal(i, j))
{ merge (i, j);
F[num_edges][0] = E[next_edge][0];
F[num_edges][1] = E[next_edge][1];
F[num_edges][2] = E[next_edge][2];
num_edges++;
test_univ();
}
next_edge++;
}
/* display edges comprising minimal spanning tree */
printf("\nMinimal Spanning Tree Edges:\n");
printf("F = (");
for (i = 0; i < N - 1; i++)
{ printf("(V%d,V%d)", F[i][0], F[i][1]);
if (i < N - 2)
printf(", ");
weight = weight + F[i][2];
}
printf(")\n");
printf("Minimal Spanning Tree Weight = %d\n", weight);
return (0);
}
/*************** makeset() ***************/
void makeset (int i)
{ U[i] = i;
}
/*************** find() ***************/
int find (int i)
{ int j;
j = i;
while (U[j] != j)
j = U[j];
return (j);
}
/*************** merge() ***************/
void merge (int p, int q)
{ if (p < q)
U[q] = p;
else
U[p] = q;
}
/*************** equal() ***************/
int equal (int p, int q)
{ if (p == q)
return (1);
else
return (0);
}
/*************** initial() ***************/
void initial (int n)
{ int i;
for (i = 0; i < n; i++)
makeset(i);
}
/*************** test() ***************/
void test_univ (void)
/* test universe values */
{ int i;
printf("\nThe disjoint subsets are:\n");
for (i = 0; i < N; i++)
printf(" %3d", U[i]);
printf("\n");
}
/*************** pause() ***************/
void pause (void)
{ int i;
printf("Press ENTER to continue...\n");
i = getchar();
}
2) I have a problem in the execution of the following program. On
compilation it's giving the syntax error before the mpi_offset in the
mpio.h which is the header file. I've full download of the mpi
libraries.
I also want the sequential 'c' code of this program. Basically this is
program based on the Prim's algorithm for the minimum spanning tree. |
Clarification of Question by
anujkansal-ga
on
31 Mar 2005 12:17 PST
For the point#2 the program is as follows:
#include <math.h>
#include <time.h>
#include <mpi.h>
//#include <\mpi\mpi2m.c>
typedef struct{
float v;
int x,t;
} minvp;
#define max_p 8
#define dim_n 2
#define max_n 1000 //nodes @ each process
float frandSin(double);
float distance(float *,float *);
int main(int argc,char *argv[]) {
int c1,c2,c3,rank,proc,size,offset=0;
int cnt=0,stop=max_n*max_p-1;
minvp min;
float mjn;
int index[max_p]; //dim_n=8 -> {7,8,9,10,11,12,13,14}
int edges[max_p*2-2]; // -> {1,2,3,4,5,6,7,0,0,0,0,0,0,0};
int point[max_n]; //point in tree
float recnt[ 2+dim_n]; //most recent point
float rebuf[(2+dim_n)*max_p]; //recv buffer for P0
int taken[max_n]; //order of chosen
int graph[max_n]; //predecessor in tree
float nodes[dim_n*max_n]; //dim X n
minvp dist[max_n]; //minimum distance trace
double tic=clock();
MPI_Comm comm;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&size);
for (c1=0; c1<max_p; c1++) {
index[c1]=max_p+c1-1;
if (c1<max_p-1) {
edges[c1]=c1+1;
edges[max_p-1+c1]=0;
}
}
MPI_Graph_create(MPI_COMM_WORLD,max_p,index,edges,1,&comm);
index[0]=1;
for (c1=0; c1<max_n; c1++) {
dist[c1].v=1e20;
point[c1]=0;
}
for (c1=0; c1<dim_n*max_n; c1++)
nodes[c1]=frandSin(cos((float)rank+.2));
if (rank==0) {
export_init();
min.x=0; min.t=-1;
recnt[0]=0; recnt[1]=0;
memcpy(&recnt[2],nodes,4*dim_n);
}
do {
MPI_Bcast(recnt,2+dim_n,MPI_FLOAT,0,comm); //0->all: send recent point info
if (rank==(int)floor(cnt/max_n)) //update chronolgical takenlist
taken[cnt%max_n]=recnt[1];
if (rank==(int)recnt[0]) { //all: if point in nodes of recent
point[min.x]=1; //point in tree now
graph[min.x]=min.t; //bad tricks
}
mjn=1e20; min.v=1e20; proc=0;
for (c1=0; c1<max_n; c1++) { //all: update minimum tracker
if (!point[c1]) {
mjn=distance(&nodes[dim_n*c1],&recnt[2]);
if (dist[c1].v>mjn) {
dist[c1].v=mjn;
dist[c1].t=cnt;
}
if (dist[c1].v<min.v) {
min.v=dist[c1].v;
min.x=c1;
min.t=dist[c1].t;
proc=1;
}
}
}
recnt[0]=min.v; //all->0: send local minimum
recnt[1]=(double)min.x;
if (proc) memcpy(&recnt[2],&nodes[min.x*dim_n],4*dim_n);
MPI_Gather(recnt,2+dim_n,MPI_FLOAT,rebuf,2+dim_n,MPI_FLOAT,0,comm);
if (rank==0) { //0: find gobal minimum
min.v=1e20;
for (c1=0; c1<max_p; c1++)
if (rebuf[c1*(2+dim_n)]<min.v) {
min.v=rebuf[c1*(2+dim_n)];
proc=c1;
}
recnt[0]=(float)proc;
recnt[1]=rebuf[proc*(2+dim_n)+1]+(float)proc*max_n;
memcpy(&recnt[2],&rebuf[proc*(2+dim_n)+2],4*dim_n);
}
offset+=max_n;
if (!rank&&!(cnt%1000)) printf(".");
} while (cnt++!=stop);
index[0]=max_n; index[1]=dim_n; index[2]=max_n;
for (c1=0; c1<max_p; c1++) { //export graph & coordinates
if (rank==c1) {
export_flush(1,index,4,taken);
export_flush(1,index,4,graph);
export_flush(2,&index[1],6,nodes);
}
MPI_Barrier(comm);
}
if (!rank) printf("\nelapsed_time =\n %10.5f\n",(clock()-tic)/CLOCKS_PER_SEC);
MPI_Finalize();
return 0;
}
float distance(float *vec1,float *vec2) {
int c1;
float dist, norm=0;
for (c1=0;c1<dim_n;c1++) {
dist=(vec1[c1]-vec2[c1]);
norm+=dist*dist;
}
return sqrt(norm);
}
float frandSin(double seed) {
static double drandSin_cnt;
float t0=sin(++drandSin_cnt+seed)*1e4;
return t0-floor(t0);
}
This is the program which is giving errors on the compilation.
I also want the sequentil 'c' code using this program as mentioned
earlier in Point#2
|
