## CPSC 441, Fall 2014

Lab 10, Part 2: More MPI Programming

This lab continues Lab 10, Part 1. For this lab, you will write a more substantial MPI program. The goal is a program that finds the number of primes less than the largest value of type int as quickly as possible. We have discussed this problem in class.

You are encouraged to work with a partner on this problem.

### Saving and Turning In Your Work

Your work for Lab 10 is due on Friday of this week, the last day of
classes for the semester. It
should be copied into your homework folder
in the directory */classes/cs441/homework*.
Please copy your C programs for exercises 1, 2, and 4 into that
folder. For Exercises 3 and 5, which require a written response,
you can turn in your work on paper or you can type in your response
and place your response in your homework folder.

For work that is being submitted by two people, please make sure that both names are on the work!

Of course, your homework directory is not directly accessible from
the temporary account that you are using for MPI programming. Furthermore,
that account will be deleted after the end of the semester, and you will
probably want to save copies of your work in your regular account.
The easiest way to do that is probably to use *scp* to copy your
work from your temporary account into your regular account. For
example, let's say that you want to copy a folder named *MPI*
that is in your current directory onto the desktop in an account
with username *zz9999* on *math.hws.edu*. The *scp*
command that you need is:

scp -r MPI zz9999@math.hws.edu:Desktop

The "-r" stands for "recursive", and it allows you to copy
an entire directory; you don't need it if you are coping a single file.
The ":" in the destination is what tells *scp* that
the destination is on another system. (If there is no ":" in the destination,
*scp* copies the folder into another folder on the same computer; if the ":"
is in the source, then *scp* will copy from a remote system to the local
computer.) If you want to copy the folder into your home directory instead
of the Destop folder, just leave out the destination folder (but not the ":"!).

scp -r MPI zz9999@math.hws.edu:

The *scp* program uses *ssh* to connect to a remote system, and
you will be asked to enter your Linux password. I used *math.hws.edu*
as the remote system in the example, but in fact you can use any computer
on which your Linux account is valid, including any of the lab machines.
You could even use *localhost*.

Once you have your work in your regular account, you can copy it from
there to your homework folder in the usual way. You could also use *scp*
to copy your work directly from your temporary account to your
homework folder.

### The Assignment

We discussed the problem of counting primes in class. The sample program
primes1.c counts primes below some upper
limit specified as a constant in the program, but it is not load-balanced and
it uses an inferior algorithm for primality testing. You should write an
improved program. During testing, you should keep the upper limit at a relatively
small value. Once it is working, you can try it for larger upper limits and,
in the end, for an upper limit equal to the largest value of type *int*.

With an upper limit of one billion and running 80 processes on
20 computers, *primes1.c* took 92 seconds in one trial and 87 seconds
in another trial. You will want to do significantly better than that.

**Exercise 4:**
Write an MPI program that will find the number of primes less than the largest
value of type *int*, that is *2 ^{31}−1*, or 2147483647.
The goal is to make the computation as fast as possible.
Your program should definitely use load balancing, with the master/slave pattern
that we discussed in class. You will probably also want to implement the
improved basic algorithm for primality testing that we covered in class.
(That is, instead of dividing the number being tested by numbers up to its
square root, only divide it by

*primes*up to its square root. If you do that, you will need a list of primes less than the square root of 2147483647; there are fewer than 50000 of them. You can use the file

*prime_list.c*, which was recently added to the directory

*/nfshome/MPI*. This file creates an array that contains all primes less than the square root of 2147483647. You can include the array into your program by getting a copy of the file and adding the directive

`to the program in which you want to use it. The C`

**#include "prime_list.c"**`#include`directive literally just includes the contents of a specified file.)

**Exercise 5:**
Write a short report explaining how your program works and and giving the results of
any timing experiments that you did with the program. You should definitely try
your program using 80 processes on all 20 machines -- or maybe even 160 processes,
if you believe in hyperthreading. (You will probably have various
versions of the program along the way; you might want to report results from several
of them.)

(**Extra credit?** It addition to knowing the number of
primes less than 2147483647, I would sort of like to know the length of the
longest "gap" between primes, that is, the longest number of consecutive non-primes
between two primes. For example, there is a gap of length 5 between 23 and 29, since
24, 25, 26, 27, and 28 are non-primes. I haven't done the computation myself. Any chance
some in the class will do it??)