Parallel programming Practical 2011/2012

The Java assignment

Introduction

This assignment for the parallel programming course consists of writing a parallel program in Java using the Ibis systeem and running it on the DAS-3. Your task is to write a parallel branch-and-bound program that uses the IDA* search strategy to solve the 15-puzzle.

Send any questions you have for this assignment to Timo van Kessel:

The 15-puzzle is played on a 4 X 4 board, in which fifteen tiles are placed. A move consists of sliding one of the fifteen tiles into the remaining space. The object is to reach the goal state shown in Figure 1(b).

The IDA* search strategy

The Iterative Deepening A* algorithm is a depth first search technique. A pseudo code implementation is given below:

 FUNCTION Solve(state, depth) : Boolean; BEGIN
  IF depth+Estimate(state) <= MaxDepth THEN
    IF Goal(state) THEN
      PrintSolution;
      RETURN true;
    ELSE
      FOR s IN Moves(state) DO
	IF Solve(s, depth+1) THEN
	  RETURN true;
	FI;
      OD;
    FI;
  FI;
  RETURN false; END;

MaxDepth := Estimate(Start); WHILE NOT Solve(Start, 0) DO
  MaxDepth +:= 1; OD; 

IDA* repeatedly performs a depth-first search. Initially the maximum depth to search with is set to the estimated number of moves to solve the starting position. As long as no solution is found the global variable MaxDepth is increased by one, and the search continues. In the case of solving the 15-puzzle with an Estimate() function using Manhattan distances MaxDepth can be even increased by two.

The Manhattan distance is the distance between two points (x, y) and (u, v) given by the metric

Solve() implements IDA* using the following functions:

It is straightforward to parallelize the IDA* algorithm, because the loop iterations over the possible moves in Solve() are independent of each other. For efficiency, however, the grain size of the leaf jobs should be controlled to avoid creating many very small jobs.

The Ibis Portability Layer (IPL)

The Ibis Portability Layer (IPL) is a communication library, and part of the Ibis project at the VU. The IPL is capable of providing applications with a simple yet powerful way of communicating between Java applications. See the Ibis site for more information. A good starting point for the IPL might be the programmers's manual and user's guide included in the distribution (and the template of the assignment). If you have any questions on the IPL after reading the manual, please send mail to the practical mail address, not the Ibis mailing lists.

Requirements

Convert the given sequential version of the solver into a parallel application that it is capable of running on multiple DAS-3 machines in parallel. To communicate, use the Ibis Portability Layer (IPL). Implement a work queue to handle passing work to the machines. You can use a single work queue, located on one of the machines. You can, for instance, elect one of the machines as "master" using the election mechanism of the IPL

Write a small report (in English, about five pages) describing your experiences with Java, the difficulties you encountered and how you solved them. Include measurements of your program. Report elapsed execution times as well as speedups. Don't just show numbers, but present a speedup graph as well. If the program does not achieve linear speedup, give an explanation including a performance breakdown for the slowdown. The document should also describe how you implemented the programs and how you measured their performance. The programs themselves should contain useful comments that illustrate how they work.

Compiling an Running your Java programs

You can compile your Java programs with javac or with ant using the provided build.xml. Be sure to use the "module" command on the DAS-3 to set the applications used. For more information see the DAS-3 section of this website.

To run a parallel program on the DAS nodes, you need to make use of the prun script (see the DAS-3 site for more information on the DAS-3 and prun). Furthermore, to run your application, you can simply use java or use the provided java-run script (which adds all jars to the classpath automatically). It expects to find a lib directory in the current directory.

sequential on one machine:

ppp@fs0 ida $ prun -v -1 -np 1 bin/java-run ida.sequential.Ida

ipl version on 8 machines:

ppp@fs0 ida $ prun -v -1 -np 8 bin/java-run ida.ipl.Ida

bonus assignment, 8 machines:

ppp@fs0 ida $ prun -v -1 -np 8 bin/java-run ida.bonus.Ida

For more information on compiling and running IPL applications, see the users's guide and programmer's manual of the IPL included in the distribution (and the assignment template).

Submitting

You have to submit your code (preferably containing useful comments that illustrate how the application works) and the report.

Important: Because we use automatic test scripts to test and benchmark your submissions, you must strictly follow the instructions below.

1. Make sure that your submission has the exact same directory structure as the provided template in /home/ppp/pub/ on the DAS-3. The main function of your program should be in the Ida.java file of the ida.ipl package.
2. Also, make sure that your parallel programs give the exact same output as the sequential program. We compare your application's output with the correct output with the diff command. This also includes the destinction between printing to standard out and standard error. If there is any difference (except for the run time you print), your submission will be rejected!
3. If you reimplement (parts of) your program for the bonus assignment, please put your new program in the ida.bonus package. Additionally, if you add extra command line options to the application, make sure that you use reasonable default values, because our automated test scripts do not know your command line options.
4. To help you with these checks a sanity-check script is provided in the bin directory of the template. Please do not submit anything which does not pass this test. The script has a single parameter, the address of the ipl server (for testing the ipl assignment). Note that the script does not check whether your application is behaving correctly, it just checks whether the output is formatted correctly.
5. Please structure your code and scripts so that your submission includes all needed dependencies (like the IPL), and simply running "ant" in the root of your applications leads to the compiling of your application. The standard "java-run" script should also work. One way to ensure all this is to not change the template :)
6. Create the report as a PDF file, and make sure you place the file in the pre-created docs directory.
7. Edit the build.xml file and fill in your name and your VU net-ID in the appropriate variables at the top of the build file. Then create a "distribution" of your code suitable for submission by using the "ant dist" command in the root of your applications. Submissions not created with the "ant dist" command will be rejected Make sure that the entire distribution compiles correctly, including the bonus assignment. If you tried, but did not finish the bonus assignment, please do not submit unfinished code that lead to compilation errors.
8. You are allowed a total of 3 submission attempts for the Java assignment. We run a check on your submission(s), and notify you of the results (i.e., pass/fail for the sanity checks) within a few days. Note that passing the sanity check does not guarantee a passing grade, but guarantees the assignment can be considered ready for grading.

Documentation

• Java 1.6 documentation
• The ipl section at the Ibis website
• The reader
• The code for the sequential implementation, available on the DAS3 (fs0.das3) in /home/ppp/pub/java

Grading

A correct implementation of all the requirements above is graded with 8. Up to 2 bonus points (to grade 10) can ben given for extra work on implementation, optimizations, testing and benchmarking. For example:

1. Replace the sequential workers of the default assignment by multithreaded workers that can make use of multi-core processors of the DAS-3.
2. Implement work stealing instead of the single centralized work queue.

To get the bonus points, it is up to your fantasy on how you improve the parallel application or your evaluation of the application. Optimizing the sequential algorithm however, does not count as a parallel optimization for the bonus assignment. If you reimplement (parts of) your program for the bonus assignment, please put your new program in the ida.bonus package. This way, it is easier for us to grade it, and additionally you do not break the entire assignment when you make a mistake in the extra code.

TODO list

In order to complete this part of the practical, please follow the following receipt:

• Get the sequential version of the IDA* Puzzle solver from /home/ppp/pub on the fs0.das3
• Create a parallel application using the IPL. The IPL is already provided in the template.
• Test your application on the DAS, using prun (see the DAS-3 site for more info on the DAS-3 and prun).
• Benchmark your parallel application
• Write a report about the practical. Include the difficulties you encountered, how you solved them, and the performance of the resulting application. Include both run-time and speedups graphs and listings
• Optionally you can try to get the bonus for this assignment. Include a description of your extra work for the bonus in your report.
• Test your assignment with the sanity-check script
• Create a "distribution" containing your code and documentation using the provided "dist" ant target (set the "name" property at the top of the build.xml file to your name!) and submit it using blackboard.
• Wait/check for the pass/fail notification of your assignment, update the code and/or report if wanted/needed, and re-submit. Note that you have a total of 3 attempts to submit your final solution. Only the last submission found on the site at the submission deadline will be graded.