📄 assignment1c.c
字号:
/*
*
*
* Exercice 1c in4026 Parallel Algorithms
*/
#include <stdio.h>
#include <sys/time.h>
#ifdef HASSTDLIB
#include <stdlib.h>
#endif
#include "pvm3.h"
#define GROUP "distances"
#define SENDNCLIENTS 1000
#define SENDSIZEP 1001
#define SENDS 1002
#define SENDS_TEMP 1003
#define SENDD 1004
#define SENDD_TEMP 1005
#define SENDMYARSET 1006
#define SENDARSIZE 1007
#define DONE 1008
#define CONTINUE 1009
#define STOPFLAG 1010
static void client( int myinst)
{
int bufid, sizeP, arsize;
int nextra, msgtype, bytes, tid, *S, *S_temp, *D, *D_temp;
int myarset, nproc;
int msgflag, i;
/* receive nr clients */
bufid = pvm_recv(0, SENDNCLIENTS);
pvm_upkint(&nproc, 1, 1);
/* receive sizeP */
bufid = pvm_recv(0, SENDSIZEP);
pvm_upkint(&sizeP, 1, 1);
arsize = sizeP / nproc;
nextra = sizeP % nproc;
/* Number of elements this client works on
myarset is the first index of the element it has to work on
*/
if ((myinst-1) < nextra)
{
myarset = (arsize + 1) * (myinst - 1);
arsize++;
}
else
{
myarset = (arsize + 1) * (nextra) + arsize * ((myinst-1) - nextra);
}
if (myarset >= sizeP)
{ /* too many processors !*/
arsize = 0;
}
/* allocate memory space for S and D and their respective temporary arrays holding the previous values */
S = (int*) malloc (sizeP*sizeof(int));
S_temp = (int*) malloc (sizeP*sizeof(int));
D_temp = (int*) malloc (sizeP*sizeof(int));
D = (int*) malloc (sizeP*sizeof(int));
do
{
/* receive S */
bufid = pvm_recv(0, SENDS);
//pvm_bufinfo (bufid, &bytes, &msgtype, &tid);
pvm_upkint(S, sizeP, 1);
/* receive D */
bufid = pvm_recv(0, SENDD);
//pvm_bufinfo (bufid, &bytes, &msgtype, &tid);
pvm_upkint(D, sizeP, 1);
/* store old values in the temporary arrays */
for (i = 0; i<sizeP; i++)
{
S_temp[i] = S[i];
D_temp[i] = D[i];
}
/* initialize flag needed to remember if done */
msgflag = DONE;
/* compute new S and D and check if done*/
for ( i=myarset; i< (myarset+arsize); i++ )
{
if ( S_temp[i] != 0 )
{
D[i] = D_temp[i] + D_temp[S_temp[i]-1];
S[i] = S_temp[S_temp[i]-1];
}
/* if you didn't reach root yet, one more iteration is needed */
if ( S[i] != 0 ) msgflag = CONTINUE;
}
/* send myarset */
msgtype = SENDMYARSET;
pvm_initsend(PvmDataDefault);
pvm_pkint(&myarset, 1, 1);
pvm_send(0, SENDMYARSET);
/* send arsize */
msgtype = SENDARSIZE;
pvm_initsend(PvmDataDefault);
pvm_pkint(&arsize, 1, 1);
pvm_send(0, SENDARSIZE);
/* send S and D */
msgtype = SENDS_TEMP;
pvm_initsend(PvmDataDefault);
pvm_pkint(S, sizeP, 1);
pvm_send(0, SENDS_TEMP);
msgtype = SENDD_TEMP;
pvm_initsend(PvmDataDefault);
pvm_pkint(D, sizeP, 1);
pvm_send(0, SENDD_TEMP);
if ( msgflag == CONTINUE )
{
/* send CONTINUE */
msgtype = CONTINUE;
pvm_initsend(PvmDataDefault);
pvm_pkint(&msgtype,1,1);
pvm_send(0,STOPFLAG);
}
}
while ( msgflag == CONTINUE );
/* send DONE */
msgtype = DONE;
pvm_initsend(PvmDataDefault);
pvm_pkint(&msgtype,1,1);
pvm_send(0,STOPFLAG);
}
main (int argc, char *argv[])
{
int info, mytid, myinst, nproc, nclients;
int *S,*D,*S_temp,*D_temp, *alive, i, sizeP;
int arsize, myarset, worktodo;
struct timeval result, startt, endt;
int msgtype, bytes, bufid, tid;
int size_array[1];
/* Test cases: */
// N = 11
//int P[] = {5, 5, 5, 1, 0, 2, 9, 3, 10, 5, 8};
// D = [1, 1, 1, 2, 0, 2, 3, 2, 2, 1, 3]
/* Assignment test case
N = 16 */
int P[] = {14, 13, 5, 16, 11, 10, 9, 12, 0, 8, 7, 15, 4, 3, 2, 1};
// N = 24
//int P[] = {10, 11, 8, 3, 22, 11, 5, 15, 22, 9, 8, 4, 24, 18, 0, 12, 21, 7, 23, 1, 10, 15, 7, 5};
//D = [4, 3, 2, 3, 2, 3, 3, 1, 2, 3, 2, 4, 4, 5, 0, 5, 5, 4, 5, 5, 4, 1, 4, 3]
// N = 32
//int P[] = {10, 11, 8, 3, 22, 11, 5, 15, 22, 9, 8, 4, 24, 18, 0, 12, 21, 7, 23, 1, 10, 15, 7, 5, 32, 29, 26, 17, 25, 27, 26, 28};
// D = [4, 3, 2, 3, 2, 3, 3, 1, 2, 3, 2, 4, 4, 5, 0, 5, 5, 4, 5, 5, 4, 1, 4, 3, 8, 10, 11, 6, 9, 12, 11, 7]
// N = 40
//int P[] = {10, 11, 8, 3, 22, 11, 5, 15, 22, 9, 8, 4, 24, 18, 0, 12, 21, 7, 23, 1, 10, 15, 7, 5, 32, 29, 26, 17, 25, 27, 26, 28, 19, 36, 34, 14, 35, 19, 16, 14};
// D = [4, 3, 2, 3, 2, 3, 3, 1, 2, 3, 2, 4, 4, 5, 0, 5, 5, 4, 5, 5, 4, 1, 4, 3, 8, 10, 11, 6, 9, 12, 11, 7, 6, 7, 8, 6, 9, 6, 6, 6]
nproc = panpvm_init (&argc, argv);
mytid = pvm_mytid (); /* enroll */
if ((myinst = pvm_joingroup (GROUP)) < 0){
pvm_perror ("Could not join group \n");
pvm_exit ();
exit (-1);
}
/* Make the group static. freezegroup will wait until nproc tids have
joined the group. */
info = pvm_freezegroup(GROUP, nproc);
nclients = nproc - 1;
if (myinst == 0) /* The server */
{
/* Start time logging */
gettimeofday (&startt, NULL);
/* Compute size of array P */
sizeP = sizeof(P)/sizeof(size_array);
/* Allocate space for the array holding the distances */
S = (int*) malloc (sizeP*sizeof(int));
D = (int*) malloc (sizeP*sizeof(int));
/* Allocate space for the array holding temporary values */
S_temp = (int*) malloc (sizeP*sizeof(int));
D_temp = (int*) malloc (sizeP*sizeof(int));
/* Allocate space for the array remembering which clients still have work to do */
alive = (int*) malloc (nclients*sizeof(int));
/* initialize S and D */
for ( i=0; i<sizeP; i++)
{
S[i] = P[i];
if ( S[i] != 0 )
D[i] = 1;
else
D[i] = 0;
}
/* All clients are alive in the begining */
for ( i=0; i<nclients; i++ )
alive[i] = 1;
/* Send relavent information to clients */
for(myinst = 1; myinst <= nclients; myinst++)
{
/* SENDNCLIENTS */
msgtype = SENDNCLIENTS;
pvm_initsend(PvmDataDefault);
pvm_pkint(&nclients, 1, 1);
pvm_send(myinst, SENDNCLIENTS);
/* SENDSIZEP */
msgtype = SENDSIZEP;
pvm_initsend(PvmDataDefault);
pvm_pkint(&sizeP, 1, 1);
pvm_send(myinst, SENDSIZEP);
}
do
{
/* Assume this is the last iteration, unless some client didn't send its termination message; to be checked at the end of loop */
worktodo = 0;
for(myinst = 1; myinst <= nclients; myinst++)
{
if ( alive[myinst-1] )
{
/* SENDS */
msgtype = SENDS;
pvm_initsend(PvmDataDefault);
pvm_pkint(S, sizeP, 1);
pvm_send(myinst, SENDS);
/* SENDD */
msgtype = SENDD;
pvm_initsend(PvmDataDefault);
pvm_pkint(D, sizeP, 1);
pvm_send(myinst, SENDD);
}
}
for(myinst = 1; myinst <= nclients; myinst++)
{
if ( alive[myinst-1] )
{
/* receive myarset */
bufid = pvm_recv(myinst, SENDMYARSET);
pvm_upkint(&myarset, 1, 1);
/* receive arsize */
bufid = pvm_recv(myinst, SENDARSIZE);
pvm_upkint(&arsize, 1, 1);
/* receive S_temp */
bufid = pvm_recv(myinst, SENDS_TEMP);
pvm_upkint(S_temp, sizeP, 1);
/* receive D_temp */
bufid = pvm_recv(myinst, SENDD_TEMP);
pvm_upkint(D_temp, sizeP, 1);
/* Merge */
for(i=myarset; i< (myarset+arsize); i++)
{
S[i] = S_temp[i];
D[i] = D_temp[i];
}
}
}
for(myinst = 1; myinst < nproc; myinst++)
{
if ( alive[myinst-1] )
{
/* receive stop flag: CONTINUE || DONE; */
bufid = pvm_recv (myinst, STOPFLAG);
pvm_upkint (&msgtype, 1, 1);
if (msgtype == DONE)
alive[myinst-1] = 0; // this client finished its work
}
}
/* Check whether there is more work to do */
for ( i=0; i<nclients; i++ )
{
if ( alive[i] )
{
worktodo = 1;
break;
}
}
}
while ( worktodo );
/* End Time logging */
gettimeofday (&endt, NULL);
if (endt.tv_usec < startt.tv_usec)
{
int nsec = (startt.tv_usec - endt.tv_usec) / 1000000 + 1;
startt.tv_usec -= 1000000 * nsec;
startt.tv_sec += nsec;
}
if (endt.tv_usec - startt.tv_usec > 1000000)
{
int nsec = (endt.tv_usec - startt.tv_usec) / 1000000;
startt.tv_usec += 1000000 * nsec;
startt.tv_sec -= nsec;
}
result.tv_sec = endt.tv_sec - startt.tv_sec;
result.tv_usec = endt.tv_usec - startt.tv_usec;
printf("\n");
for (i = 0; i < sizeP; i++)
{
printf("D[%d]=%d ", i, D[i]);
}
printf ("\n\nThis calculation took %d.%d seconds using %d client processes.\n",result.tv_sec, result.tv_usec, nproc-1);
printf ("\n%d.%d seconds using %d client processes with %d work.\n\n",result.tv_sec, result.tv_usec, nproc-1, sizeP);
} /* end server code */
else
{
client(myinst);
} /* end client */
info = pvm_barrier(GROUP, -1);
if (info < 0){
printf ("Barrier failed with result code %d\n", info);
}
pvm_lvgroup (GROUP);
pvm_exit ();
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -