CPSC 441, Fall 2014
Lab 9, Part 2: More MPI Programming
This lab continues Lab 9, 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 two billion in the shortest time possible. There is also an extra credit opportunity. We have discussed this problem in class.
Your program for this lab should be named ex4.c. Remember that you can work on this program with a partner. Work for this lab is due this Friday, December 7. It must be a folder in your homework directory inside /classes/cs441/homework The name of that folder must be lab9. Everyone must submit ex1.c and ex2.c. The other two files, ex3.txt and ex4.c, can be submitted either individually or with a partner. If you are working with a partner on ex3.txt and ex4.c, only one of you should submit those files; please make sure that both names are in the files. Note that your response to Exercise 5 will be included as a comment in ex4.c.
Of course, your homework directory is not directly accessible from the netXX 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 into your regular account. For example, let's say you are working in your netXX account and that you want to copy a folder named lab9 that is in your current directory onto the desktop in a regular account with username zz9999. You can do that with the scp commnand
scp -r lab9 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 files should be copied over a network connection to the specified computer. (If there is no ":" in the destination, scp copies the folder into another folder on the same computer; if the ":" is in the first parameter to scp, 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 lab9 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 such as csfac7. 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.
Load-Balanced Prime Counting
We discussed the problem of counting primes in class. The sample program primes1.c counts primes below some upper limit, but it is not load-balanced and it uses an inferior algorithm for primality testing.
In primes1.c, the problem of counting primes in a given range is solved by breaking the problem into as many tasks as there are processes to work on the tasks. To write a program that does better load balancing, you need to break the problem into a larger number of tasks and apply the supervisor/worker program. Instead of working on just one task, each process will work on a series of tasks assigned to it by the supervisor. In outline, the algorithm becomes:
Assign a task to each worker
While the number of results received is less than the number of tasks:
Receive a result from some task
if not all tasks have been assigned
Send the next task to the worker from which the result was received
Use the result that was returned by the worker.
A reasonable number of tasks is 1000. You might want to use a smaller number of taskes while debugging. Each task still involves counting primes in some range. And the final result is still computed by adding up the results from all of the tasks.
The is_prime(N) function in primes1.c tests if N is prime by checking if it is divisible by any number in the range 2 through the square root of N. A better algorithm will only check whether N is divisible by any prime number in the range 2 through the square root of N. 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. To do that, you will need a list of primes less than the square root of 2000000000; there are fewer than 5000 of them. You can use the file prime_list.c; there is a copy in the directory /classes/cs441. This file creates an array, prime_list, that contains all primes less than the square root of ten billion (just in case someone wants to go further than two billon, but in that case you would also have to modify the program to use unsigned ints or even unsigned long ints instead of ints). 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 at the point where the #include occurs
The Assignment
Exercise 4: Write an improved prime-counting 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 2,000,000,000. The goal is to make the computation as fast as possible. Your program should use load balancing, with the supervisor/worker pattern. You will also want to implement the improved algorithm for primality-testing. Your program should be named ex4.c.
With an upper limit of two billion and running 80 processes on 20 computers, my solution to this exercise took about 81 seconds.
Exercise 5: Write a short report explaining how your program works and giving the results of any timing experiments that you did with the program. Include the report in a comment at the top of the file ex4.c.
(Extra credit? It addition to knowing the number of primes less than two billion, it's interesting 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. To find the longest gap size, you need to get more information back from the workers to the supervisor. It's easy for a worker to find the size of the longest gap in an individual task, and send that information back to the supervisor. But you have to deal with the fact that the longest gap might overlap two tasks. To handle that case, the workers in my program send back three pieces of information to the supervisor: the longest gap in a task, the size of the gap at the start of the task, and the size of the gap at the end of the task. The gap at the end of one task must be combined with the gap at the start of the next task. The supervisor collects all of the data from the individual tasks into an array, and it uses that array to find the size of the largest gap overall. Here are some results from my program:
range number of primes longest gap between primes ------------- ---------------- ------------------------- 2 to 100000 9592 71 2 to 1000000 78498 113 2 to 10000000 664579 153
It would be nice to know the two prime numbers separated by the largest gap, but my program doesn't do that.)