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³¹−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 #include "prime_list.c" to the program in which you want to use it. The 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??)