#include #include #include #include /* This program started out as parmerge.c, which in turn started out as ForkJoin.c, pp. 63-68, from the PVM User's Guide and Tutorial for Networked Parallel Computing, MIT Press, 1994. Obviously I've modified it extensively from that base, however. */ /* The basic algorithm, although modified, for this implementation of matrix multiplication is from "Parallel Programming: Techniques and Applications using Networked Workstations and Parallel Computers", Barry Wilkinson & Michael Allen, Prentice-Hall, 1999. It is the algorithm called "Recursive Implementation", section 10.2.3, pp. 307-309. Although this implementation is not recursive since I'm limited to eight processors... or, processes. */ /* defines and prototypes for the PVM library */ #include "pvm3.h" int main(int argc, char* argv[]) { int d2(int x, int y, int n); void block_mult(int *a, int *b, int *c, int dim); void block_add(int *a, int *b, int *c, int rowC, int colC, int dim); int greater(int a, int b); time_t t; /* number of tasks to spawn, use 8 as the default */ int ntask = 8; /* return code from pvm calls */ int info; /* my task id */ int mytid; /* my parents task id */ int myparent; /* children task id array */ int child[8]; /* upper bound to integral random numbers; i.e. 0-range */ int range = 10; int p, q, n, m, i, j, k, x, y, z, buf, len, tag, tid, size; int *a, *b, *c, *mydata; int nhost, narch; char *workers; struct pvmhostinfo *hostp[32]; info = pvm_config(&nhost, &narch, hostp); if (strcmp(hostp[0]->hi_arch, "WIN32") == 0) { workers = "parmatm.exe"; } else if (strcmp(hostp[0]->hi_arch, "LINUX") == 0) { workers = "parmatm"; } else { workers = "parmatm"; } /* find out my task id number */ mytid = pvm_mytid(); /* check for error */ if (mytid < 0) { /* print out the error */ pvm_perror(argv[0]); /* exit the program */ return -1; } /* find my parent's task id number */ myparent = pvm_parent(); /* exit if there is some error other than PvmNoParent */ if ((myparent < 0) && (myparent != PvmNoParent)) { pvm_perror(argv[0]); pvm_exit(); return -1; } /* if I don't have a parent then I am the parent */ if (myparent == PvmNoParent) { /* find out how many args */ if (argc == 2) { m = n = p = q = abs(atoi(argv[1])); } else if (argc == 4) { p = abs(atoi(argv[1])); n = abs(atoi(argv[2])); q = abs(atoi(argv[3])); m = greater(greater(p,q),n); } else { pvm_perror("usage: parmatm n OR parmatm p n q"); pvm_exit(); return -1; } /* make sure dimension is legal */ if (m < 1) { pvm_exit(); return -1; } /* if just scalar, just return result now */ if (m == 1) { t = time(NULL); srand(t); x = rand() % range; y = rand() % range; z = x * y; printf("%d x %d = %d\n", x,y,z); pvm_exit(); return 0; } /* if dimension is odd, we'll force it even */ if (m % 2 == 1) m++; /* Allocate space for matrices */ a = (int*) malloc(sizeof(int)*(m*m)); b = (int*) malloc(sizeof(int)*(m*m)); c = (int*) malloc(sizeof(int)*(m*m)); mydata = (int*) malloc(sizeof(int)*(m*m)); /* Zero-fill padded-matrices */ for (i = 0; i < m; i++) for (j = 0; j < m; j++) { a[d2(i,j,m)] = 0; b[d2(i,j,m)] = 0; c[d2(i,j,m)] = 0; mydata[d2(i,j,m)] = 0; } /* Generate random matrices */ t = time(NULL); srand(t); for (i = 0; i < p; i++) for (j = 0; j < n; j++) a[d2(i,j,m)] = rand() % range; for (i = 0; i < n; i++) for (j = 0; j < q; j++) b[d2(i,j,m)] = rand() % range; /* print out input matrices */ for (i = 0; i < p; i++) { for (j = 0; j < n; j++) printf("%d ",a[d2(i,j,m)]); printf("\n"); } printf("\n\n"); for (i = 0; i < n; i++) { for (j = 0; j < q; j++) printf("%d ",b[d2(i,j,m)]); printf("\n"); } x = m/2; /* this is the dimension of matrices sent to workers */ /* spawn the child tasks and send the dimension of the matrices to be sent to workers */ for (i = 0; i < ntask; i++) { info = pvm_spawn(workers, (char**)0, PvmTaskDefault, NULL, 1, &child[i]); /* make sure spawn succeeded */ if (info == 0) { pvm_exit(); return -1; } info = pvm_initsend(PvmDataDefault); if (info < 0) { pvm_perror("calling pvm_initsend"); pvm_exit(); return -1; } info = pvm_psend(child[i], 0, &x, 1, PVM_INT); if (info < 0) { pvm_perror("calling pvm_psend"); pvm_exit(); return -1; } } /* farm out input submatrices for workers to multiply */ for (i = 0; i < ntask; i++) { for (j = (((i/2) & 2) >> 1) * m/2; j < (((i/2) & 2) >> 1) * m/2 + m/2; j++) for (k = ((i/2) & 1) * m/2; k < ((i/2) & 1) * m/2 + m/2; k++) mydata[d2(j % (m/2),k % (m/2),m/2)] = a[d2(j,k,m)]; info = pvm_initsend(PvmDataDefault); if (info < 0) { pvm_perror("calling pvm_initsend"); pvm_exit(); return -1; } info = pvm_psend(child[i], 0, mydata, (m*m)/4, PVM_INT); if (info < 0) { pvm_perror("calling pvm_psend"); pvm_exit(); return -1; } for (j = (((i % 4) & 2) >> 1) * m/2; j < (((i % 4) & 2) >> 1) * m/2 + m/2; j++) for (k = ((i % 4) & 1) * m/2; k < ((i % 4) & 1) * m/2 + m/2; k++) mydata[d2(j % (m/2),k % (m/2),m/2)] = b[d2(j,k,m)]; info = pvm_initsend(PvmDataDefault); if (info < 0) { pvm_perror("calling pvm_initsend"); pvm_exit(); return -1; } info = pvm_psend(child[i], 0, mydata, (m*m)/4, PVM_INT); if (info < 0) { pvm_perror("calling pvm_psend"); pvm_exit(); return -1; } } /* receive product submatrices from workers; sum appropriate pairs to form final product matrix */ for (i = 0; i < ntask/2; i++) { j = ((i & 2) * 2) + (i & 1); info = pvm_precv(child[j], 0, a, (m*m)/4, PVM_INT, &x, &y, &z); if (info < 0) { pvm_perror("calling pvm_precv"); pvm_exit(); return -1; } info = pvm_precv(child[j+2], 0, b, (m*m)/4, PVM_INT, &x, &y, &z); if (info < 0) { pvm_perror("calling pvm_precv"); pvm_exit(); return -1; } block_add(a,b,c,(i/2) * m/2,(i & 1) * m/2,m); } printf("\n\n"); /* print out final product matrix */ for (i = 0; i < p; i++) { for (j = 0; j < q; j++) printf("%d ",c[d2(i,j,m)]); printf("\n"); } pvm_exit(); return 0; /* I'm a worker */ } else { /* receive dimension of submatrices to be sent from parent; worker's m = m/2 in parent */ info = pvm_precv(myparent,0,&m,1,PVM_INT,&x,&y,&z); if (info < 0) { pvm_perror("calling pvm_precv"); pvm_exit(); return -1; } /* Allocate space for worker matrices */ /* remember: workers m = m/2 of parent's m */ a = (int*) malloc(sizeof(int)*(m*m)); b = (int*) malloc(sizeof(int)*(m*m)); c = (int*) malloc(sizeof(int)*(m*m)); /* receive submatrices from parent */ info = pvm_precv(myparent, 0, a, m*m, PVM_INT, &x, &y, &z); if (info < 0) { pvm_perror("calling pvm_precv"); pvm_exit(); return -1; } info = pvm_precv(myparent, 0, b, m*m, PVM_INT, &x, &y, &z); if (info < 0) { pvm_perror("calling pvm_precv"); pvm_exit(); return -1; } block_mult(a,b,c,m); /* send product submatrix to parent */ info = pvm_initsend(PvmDataDefault); if (info < 0) { pvm_perror("calling pvm_initsend"); pvm_exit(); return -1; } info = pvm_psend(myparent, 0, c, m*m, PVM_INT); if (info < 0) { pvm_perror("calling pvm_psend"); pvm_exit(); return -1; } pvm_exit(); return 0; } } /* necessary because C seems kinda difficult about working with arrays treated as two dimensional whose size is not known at compile time...? */ int d2(int x, int y, int n) { return (x*n+y); } /* I got this next function, block_mult, with a few minor modifications, from the PVM User's Guide and Tutorial for Networked Parallel Computing, MIT Press, 1994. It is from the program mmult.c, p. 79. */ /* multiplies two m x m matrices */ void block_mult(int *a, int *b, int *c, int dim) { int i, j, k; for (i = 0; i < dim; i++) for (j = 0; j < dim; j++) { c[d2(i,j,dim)] = 0; for (k = 0; k < dim; k++) c[d2(i,j,dim)] = c[d2(i,j,dim)] + a[d2(i,k,dim)] * b[d2(k,j,dim)]; } } /* adds two m/2 x m/2 matrices inserting the product submatrix into the appropriate submatrix of the final product matrix */ void block_add(int *a, int *b, int *c, int rowC, int colC, int dim) { int i,j; for (i = rowC; i < rowC + dim/2; i++) for (j = colC; j < colC + dim/2; j++) { c[d2(i,j,dim)] = a[d2(i % (dim/2),j % (dim/2),dim/2)] + b[d2(i % (dim/2),j % (dim/2),dim/2)]; } } int greater(int a, int b) { return (a > b) ? a : b; }