First MPI Assignment: Due Monday 12/7/2015
/*
A prime number is any number > 1 that's divisible only by 1 and itself.
There are many sophisticated ways to test for primes. A simple one is
to test if the number is divisible by 2 or any odd number between
3 and n/2.
Here is a conventional, 1-process implementation:
*/
int isprime(unsigned long long n)
{
unsigned long long i;
if (n==2) return 1;
if ((n<2) || (n%2 == 0)) return 0;
for(i=3;i<=n/2 && ((n%i)>0);i+=2);
return (i>n/2);
}
/*
Is this algorithm a good candidate for parallel speedup? You should
show that it is by deriving the complexity of computation versus
the complexity of communication. Then you should implement a
multi-processor solution to demonstrate your hypothesis.
Each process will be responsible for checking if the number is
divisible by a range of values, and send the result back to the rank-0
process. For the final communication, when the results are
gathered from each process, use MPI_REDUCE with operation MPI_LAND
(logical and), instead of the normal send/receive operations.
MPI_REDUCE is similar to MPI_Bcast: all processes must call it.
Read the description of this function in the textbook and online
docs carefully.
The C datatype unsigned long long (64 bit non-negative integer)
corresponds to the MPI datatype MPI_UNSIGNED_LONG_LONG. However,
unlike the 'Writable' and 'Serializable' classes of Hadoop and RMI,
MPI does not change the underlying binary representation: the name is
only used for compatibility. In fact, Beowulf clusters typically consist
of identical machines, so even byte ordering (endian) conversions are
not needed.
Here are some known large prime for you to test, others are easy to
look up.
2147483647
2147483629
2147483587
Also test your program on non-primes, and compare the answer with
that returned by the conventional function above. Compare the
elapsed time of the conventional function and your multi-processor
implementation. You should see speed up for the large numbers above.
*/