Lab: MPI

One of the key differences between parallel computing and distributed computing is that you're introducing more than one computer into the mix. This means that you need to log into other computers, automatically, yet securely. Passwords are terrible for this: do you put your password into code, where anyone can read them? Instead, we use an approach called Secure Shell (abbreviated as SSH) as a way of securely logging into another computer without the need for a password.

Here's the idea, for those of you that haven't come across this before: you're going to use a program called ssh-keygen that will generate two files of random-seeming characters. One of those files is called a "private key," and you keep it hidden from everyone else. The other file is called a "public key," and you can share its contents with the world. By using some really clever encryption algorithms, you can demonstrate to anyone holding the public key that you've got the matching private key, without actually having to divulge the contents of the private key file. So that's how you can securely connect to other computers. First, you share your public key with them. After you've done so, you can prove that you're the holder of the private key, and hence it's ok for you to log in.

Write a program that sends a value (perhaps a -1) in a circle, starting with process zero, and going through all the processes until it ends up back at 0 again. Here is what sample output should look like:

Process 1 received token -1 from process 0
Process 2 received token -1 from process 1
Process 3 received token -1 from process 2
Process 4 received token -1 from process 3
Process 0 received token -1 from process 4

Make sure to avoid deadlock. Whenever each process receives a value, it should print a line of text indicating which process it is, and what the value was.

One challenge you may or may not run into in the above exercise is that the results of the output may be interleaved, sometimes out of order. System.out.println is synchronized and thread-safe, but here we have multiple single-threaded processes all writing into the same output buffer, and the timing on how the results get flushed may not happen in the order that you expect. If you think that the terminal window is showing you the output in an incorrect order, add a short Thread.sleep call somewhere in your code so that each process takes a short break before sending the value off to the next process.

A classic example is computing the value of pi using numerical integration. Basically, we trying to calculate the area under the curve \(f(x) = 4 / (1 + x^2)\) between \(x = 0\) and \(1\), which happens to be pi. The more intervals we divide it into, the more accurate the answer. The root process broadcasts the number of intervals (n) to all processes, which compute part of the sum, then the reduce function does the summation.

Here is pseudocode for the algorithm to compute pi; see if you can translate it to MPI! In case you are wondering if your solution is right, the answer I get for \(n = 1000\) is \(3.141593\).

root process only:
    ask the user for a value n
broadcast the value n to all processes
width <- 1 / n
sum = 0
forall 1 <= i <= n (in parallel - divide the i values between processes somehow):
    sum <- sum + 4 / (1 + (width * (i - 0.5)) ** 2)
mypi <- width * sum
sum all processes' mypi using reduce
print sum

One important thing to note is that the above data generator dumps the output to the /tmp directory. It is critical that you leave your randomly generated data there and don't move it to your department home directories. /tmp is a local directory on every computer, whereas your home directory exists on a single server and is mounted by every computer you log into. If you copy your generated data to your home directory or any subdirectory, three very bad things happen:

1. You will clog up our limited server space with gigabytes of random data. You collectively run the risk of filling up the server, and preventing CS students in all classes from being able to save their work.
2. You will clog up our network connections as you read gigabytes of data from these files. You collectively run the risk of overloading our network, preventing CS students in all classes from being able to access their work.
3. This is the worst of all: Mike Tie will come after you.

If you are using multiple computers, since /tmp is not shared between them, you'll need to copy the file to /tmp on all computers that you're using. Don't copy it to your home directory as a temporary spot. (If you goof and do so, don't panic. Just delete it right away.) To get the data on multiple computers, there are a variety of options. Here are two: you can use the scp program from the command line, which lets you use ssh to copy files from one computer to another. Online tutorials are plentiful; here is one scp tutorial. Another approach is just to rerun the data generator program on each computer. I'm using a seed in there for the random number generator, so it will create the same file each time.

While you're working on your assignment, you may be using multiple computers. Make sure that you aren't slowing down other people from working. You can completely test your code by running MPI only on your local computer, i.e. by setting up your hostfile so that it only runs locally. You'll undoubtedly want to try it eventually on multiple computers to see it fly, but only do that at the end, and make sure that others aren't using those computers at the time. One approach (besides just looking in the labs) is to ssh into a machine and type just a single w at the command prompt. It will show you the logged in users. You should see yourself; if you see others, the machine is being used.

Enjoy, and have fun with it!