02152 Concurrent Systems        Fall 2008
CP Lab 2: Data Parallel Algorithm in Java

Home

Plan

Material

Purpose

Time and Place

Assistance for this programming lab will be available in the G-databar, Building 308, rooms 15+16, Thursday September 11, 15.00-17.00.

Preparations

You do not have to do any particular preparation, but you should know how to crate Java threads ([Proc 4] or [Andrews 5.4.1])

The algorithm of this lab represents a case of iterative parallelism described in [Andrews 1.4].

Instructions

1. First do CP Mini lab 2 (unless you already did so).

2. Fetch the program Search.java that is a Java program that will search a file for occurrences of a given pattern (using a very naive approach that suffices here).
3. Compile the program and run the it with

   java Search file pattern

   where file is a file name, and pattern is the string to be located.

   The program measures the elapsed search time (loading of file not included) and prints the number of occurrences. Run the program on a large file and vary the search pattern.

   You may e.g. try to find DNA-patterns in part of the human cromosome 2.

4. Now modify the program to allow for the search to be performed concurrently by a number of threads. The number of threads to use is given by a third parameter to the program.

   You should, in particular, be careful to analyze which part of the character array each thread should work on.

5. Test that your program works correctly. As part of this, you may try to find the number of occurrences of xxxx (four x-es) in the file xtest.txt [It should be 2605].
6. Once the program is running correctly, you should conduct a series of experiments where, for the same file and pattern, you vary the number of threads. For each thread number, you should run the search several times. For the 1-thread case, you should choose the search problem so that the the running time is in the order of seconds.

   The measurements can be recorded by supplying the name of a data file as a fourth argument to the program. Each program run will append the number of threads and the running time in milliseconds to the data file. These data can be, for instance, be shown by the gnuplot program.

   To make a graph of the results, simply enter enter gnuplot and at the prompt give the plot command.

   gnuplot> plot "datafile"

   Information on advanced plotting can be obtained by help plot within gnuplot or by consulting one of the tutorials, eg. the one by Kawano or Gavin.

7. For each number of threads, you should get a fairly stable lower bound, but also some outlying ``bad cases'' (also known as out-lies). Can you explain these?

8. On a G-databar machine, you should experience a performance improvement when using multiple threads. The reason is that the machines have multiple processors and that the Solaris operating system will try to give each thread an equal share of the total computing resources. That is, the more threads, the more CPU-cycles.

    
   Discuss other scheduling strategies, for which you might not experience a performance improvement.

9. For which number of threads do you get the best result? Can you explain this?
10. Try to run the search with a large amount of threads (10,100,1000,10000) and explain the results.

Caveat:

Always beware that measuring computing times on a timeshared system is like measuring length with an elastic ruler.

Hans Henrik Løvengreen, Sep 8, 2008