AlgKons

Back to Øvinger og Nøtter.

Playing with parallel processing

The purpose of this exercise is to play with parallel processing. We only give a brief introduction and some inspiration in Java, but you are of course free to use any language you would like. As a first introduction, you can take a look at the following Java class, written by Rune Jensen: Mptest.

You can get an interresting printout by running Mptest on a computer with multiple processors, and it may be valuable to understand what Mptest does.

Exercise

It is now time to create something on your own. Parallel prefix is a central subject in the lectures on parallel algorithms, and you should implement it on your own now. We do not have a synchronous parallel machine available, so we have to simulate it, and imagine that each thread is a processor. You are free to implement something that is similar to parallel prefix any way you like, but we will provide some hints to how it could be done below. Remember that there are many other possibilities.

We can simulate that something happens synchronously by making sure that the threads wait for each other when they must be synchronous. Java 5.0 have several new features for synchronizing. One of them is a new class named CyclicBarrier. You can read about it here: onjava.com, and it is of course also information in the API.

With a CyclicBarrier we can make all threads wait until a certain number of threads have called await, which really is a sort of synchronization. You can see an example of this here: Barrier.java. Your task is to realize when you need synchronization in your implementation of parallel prefix (the choice may be dependent on whether you simulate an EREW, CREW or so). After you have made this choice, implement it, and experiment to evaluate the efficiency of such a solution, as shown in Mptest.

Good luck!

Simon and Truls