Hey all,
I'm a bit of a newbie to cluster computing. I setup a nice little cluster with
Lam, and I'm attempting my first program to utilize it.
Basically, I figured that, for something simple, I'd hack up a prime finder. I
managed to make one that has master giving numbers, and slaves testing each
number it gets, by dividing it by every integer up to the numbers square root
(that was a confusing sentence). I friend suggested a few improvements, such
as a) giving each node a range of numbers, rather than just one, and b)
keeping a list on all the nodes of the previously found primes, and only
dividing by those. These sound good to me.
The first problem I have is that my chunks don't chunk right..... Basically, I
get multiply responses, etc. This is more of a technical question than one of
algorithms, but I figured I'd give it a chance.
Second, I realized that not all my nodes are the same speed. At the moment,
the code just says: for i = number of nodes, mpi_send (the number to test).
But if node 3 finished before node2, it sits around and waits. Can anyone
tell me a way to fix this?
And finally, how can I keep the current list of primes updated on all of the
nodes? What if a node is in the middle of checking? How can it recieve?
My code is as follows:
----------
//NOTE: a regular int can only go to 4,294,967,295, so I used type uint64_t
//which goes to 9,223,372,036,854,775,807.
//So if you're planning to find primes higher than that, you'll need different
//variables... ;-)
#include <stdint.h>
#include <stdio.h>
#include <math.h>
#include <mpi.h>
#define ITERS 5 //if negative, it goes and goes
#define DEBUG 1 //1 means yes, at least to me
#define STARTNUM 1244666627 //MUST BE ODD!!!!!
#define CHUNKSIZE 1 //default size of chunks
#define NUMNODES 4 //number of nodes, including master
int main(int argc, char *argv[]) {
int rank, size, numtimes, x;
uint64_t i=STARTNUM,t;
double startwtime = 0.0, endwtime;
int chunk[NUMNODES-1];
for (x=0;x<NUMNODES;x++)
chunk[x]=CHUNKSIZE;
/*Set your custom chunk sizes here. This is in case you
*have nodes with different speeds, you can make them all
*work together by fixing the chunk size */
//chunk[1]=250; //make the chunk sizes for each respective
//chunk[2]=1100;//node. All nodes undefined will be equal to CHUNKSIZE
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) { //split to master
startwtime = MPI_Wtime();
for (numtimes=0;numtimes!=ITERS;numtimes++) {
for (x=1;x<size;x++) {
MPI_Send(&i, 1, MPI_DOUBLE, x, 1, MPI_COMM_WORLD);
i+=chunk[x];//increment it by the size of that node's chunk
}
}
} else { //slaves
for (numtimes=0;numtimes!=ITERS;numtimes++) {
MPI_Recv(&i, 1, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
if (DEBUG==1)
printf("Node %d got an assignment: i=%d.\n",rank,i);
for (t=i;(t-i)<chunk[rank];t+=2) {
printf("Node %d is testing %d.\n",rank,t);
//sleep(1);
if (isprime(t)==1)
printf("%d says %d\n",i,rank); //just stick it on stdout
if (DEBUG==1)
printf("Node %d says %d is prime!!!\n",rank,i);
else
if (DEBUG==1)
printf("Node %d says %d is not prime.\n",rank,i);
}
}
}
if (rank == 0) {
endwtime = MPI_Wtime();
printf("wall clock time = %f\n", endwtime - startwtime);
}
MPI_Finalize();
return 0;
}
int isprime(uint64_t i) { //check if prime. Returns 1 if so, 0 if not.
uint64_t k;
int prime_cnt;
prime_cnt=1;
for (k=2; k<=sqrt(i);k++) {
if ((i%k) == 0) {
prime_cnt--;
break;
}
}
return prime_cnt;
}
--------
Thanks A LOT!
-Jack C
jack {at} crepinc.com
http://www.crepinc.com
|
