/* this include file is mandatory */ #include /* PVM sample program; NOT INTENDED TO BE EFFICIENT as a prime finder, either in algorithm or implementation PVM (Parallel Virtual Machine) is a popular package using the "message passing" paradigm for communicating between processors in parallel applications; as the name implies, processors communicate by passing messages using "send" and "receive" functions finds and reports the number of primes less than or equal to N uses a pipeline approach: node 0 looks at all the odd numbers (i.e. has already done filtering out of multiples of 2) and filters out those that are multiples of 3, passing the rest to node 1; node 1 filters out the multiples of 5, passing the rest to node 2; in this simple example, we just have node 2 filter out all the rest and then report the number of primes note that we should NOT have a node run through all numbers before passing them on to the next node, since we would then have no parallelism at all; on the other hand, passing on just one number at a time isn't efficient either, due to the high overhead of sending a message if it is a network (tens of microseconds until the first bit reaches the wire, due to software delay); thus efficiency would be greatly improved if each node saved up a chunk of numbers before passing them to the next node */ #define MAX_N 100000 #define PIPE_STAGES 3 #define PIPE_MSG 0 /* type of message containing a number to be checked */ #define END_MSG 1 /* type of message indicating no more data will be coming */ int NNodes, /* number of nodes in computation*/ N, /* find all primes from 2 to N */ Me, /* my node number */ MyTID, /* my PVM task ID */ *SibTID, /* PVM task IDs of siblings */ ToCheck; /* current number to check for passing on to next node; stylistically this might be nicer as a local in Node*(), but I have placed it here to dramatize the fact that the globals are NOT shared among the nodes, thus no problem */ Init(Argc,Argv) int Argc; char **Argv; { int DebugWait,I; /* get command-line arguments */ N = atoi(Argv[1]); DebugWait = atoi(Argv[2]); /* this loop is here to synchronize all nodes for debugging; if DebugWait is specified as 1 on the command line, all nodes wait here until the debugging programmer starts gdb at all nodes and within gdb sets DebugWait to 0 to then proceed; see http://heather.cs.ucdavis.edu/~matloff/pardebug.html */ while (DebugWait) ; /* mandatory to begin any PVM program: "enroll" in PVM, and receive notification of our PVM task ID */ MyTID = pvm_mytid(); /* pvm_siblings() will tell us how many "siblings" we have, and their PVM task IDs; two tasks are siblings if they were spawned the same "parent" */ NNodes = pvm_siblings(&SibTID); /* we could do error checking for NNodes == PIPE_STAGES here, but skip it to keep this example simple */ /* now find my node number */ for (Me = 0; Me < NNodes; Me++) if (SibTID[Me] == MyTID) break; } Node0() { int I, Error; /* not checked in this example */ for (I = 1; I <= N/2; I++) { ToCheck = 2 * I + 1; if (ToCheck > N) break; if (ToCheck % 3 > 0) { /* we will send a message to node 1, consisting of the integer ToCheck PVM maintains a data structure, not visible to the programmer, to contain a message; we first must tell PVM to set up the structure (or to clear it if it already exists); we just use the default encoding */ pvm_initsend(PvmDataDefault); /* in PVM one "builds" the message via successive calls to "packing" functions, each call adding something to the end of the message; the functions are documented under "pvm_pack" in the pvm library man pages, at http://www.epm.ornl.gov/pvm/man/manpages.html our call follows below; we use pvm_pkint() because the data being added to the message is an int or several int's; the first argument is the address of the first int in our data; the second is the number of int's; the third is the "stride," i.e. number of int's between each successive data item (see explanation at the end of this file) */ pvm_pkint(&ToCheck,1,0); /* no more data to add to the message, so go ahead and send it, using pvm_send(); node 1 has PVM task ID SibTID[1]; in general a PVM application will have several message types, so we name them in #define's, and indicate the type (called a "tag") in the second argument here */ pvm_send(SibTID[1],PIPE_MSG); } } /* now send the "all done" message; it has no data, so we don't do any packing */ pvm_initsend(PvmDataDefault); pvm_send(SibTID[1],END_MSG); } Node1() { int ToCheck, /* current number to check from Node 0 */ BufID,Size,Tag,TID, Error; /* not checked in this example */ while (1) { /* receive the message from node 0, via pvm_recv(); the first parameter is node 0's PVM task ID; the second parameter is the message type, -1 meaning we will accept any type at this time (-1 in the first parameter would mean any node); the function returns an ID number for a buffer where the incoming message lies */ BufID = pvm_recv(SibTID[0],-1); /* so, what type of message was it? call pvm_bufinfo() to find out; we tell it the buffer ID, and it tells us the number of bytes in the message, the tag, and the task ID of the sending node */ pvm_bufinfo(BufID,&Size,&Tag,&TID); /* are we done? */ if (Tag == END_MSG) break; /* now, what was the message itself? to find out, we unpack; the parameter structure is like that of the packing function */ pvm_upkint(&ToCheck,1,0); if (ToCheck % 5 > 0) { pvm_initsend(PvmDataDefault); pvm_pkint(&ToCheck,1,0); pvm_send(SibTID[2],PIPE_MSG); } } pvm_initsend(PvmDataDefault); pvm_send(SibTID[2],END_MSG); } Node2() { int ToCheck, /* current number to check from Node 0 */ Error, /* not checked in this example */ BufID,Size,Tag,TID, PrimeCount,I,IsComposite; PrimeCount = 3; /* must account for the primes 2, 3 and 5, which won't be detected below */ while (1) { BufID = pvm_recv(SibTID[1],-1); pvm_bufinfo(BufID,&Size,&Tag,&TID); if (Tag == END_MSG) break; pvm_upkint(&ToCheck,1,0); IsComposite = 0; for (I = 7; I*I <= ToCheck; I += 2) if (ToCheck % I == 0) { IsComposite = 1; break; } if (!IsComposite) PrimeCount++; } /* print results */ printf("number of primes = %d\n",PrimeCount); } main(argc,argv) int argc; char **argv; { Init(argc,argv); /* note: instead of having a switch statement, we could write three different programs, each running on a different node */ switch (Me) { case 0: Node0(); break; case 1: Node1(); break; case 2: Node2(); }; /* mandatory for all PVM programs */ pvm_exit(); exit(1); } /* explanation of "stride" in the call to pvm_pkint(): the rough idea here is to "take every k-th item," where we call k the "stride" in many cases we send a whole array of int's (or char's, etc.), instead of just one int as we did here; to see what "stride" means, first suppose we have an array X, declared as int X[100]; and that we wish to send a message consisting of the 4 int's X[5], X[7], X[9] and X[11]; our call to pvm_pkint() would be pvm_pkint(&X[5],4,2); what we are telling pvm_pkint() is "Starting at the address &X[5], take every 2nd int until you've got 4 int's" a common application of this idea arises in matrix problems; the C language uses row-major order for two-dimensional arrays, so if we wish to send a message consisting of one column of, say, a 4x12 matrix, the stride would be 12 */