This assignment for the parallel programming course consists of writing a parallel program in Java using the Ibis system and running it on DAS-5.

The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing.  The puzzle also exists in other sizes, particularly the smaller 8-puzzle.  If the size is 3x3 tiles, the puzzle is called the 8- puzzle or 9-puzzle, and if 4x4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order by making sliding moves that use the empty space. For this assignment, you’ll be implementing a parallel version of the 24-puzzle.

15-puzzle (Wikipedia)

The goal of the assignment is to write an application which is able to determine the shortest number of slides possible, as well as the number of ways to solve the puz- zle with this number of slides, given a certain starting layout. A sequential solver is available in the course Canvas page, under Assignments. The application includes a build .gradle file for building the application with Gradle, as well as a docs and bin directory to hold any documentation, scripts and external dependencies for your application.

Although the application randomly creates initial puzzle layouts, it is deterministic: with a given setting and seed it will always generate and solve the same puzzle, allow- ing for easy benchmarking of the application. The different command line parameters drastically change the application runs. If the default parameters do not work for you, try to adjust them somewhat.

Requirements

Convert the given sequential version of the solver into a parallel application that is capable of running on multiple DAS-5 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.

You may want to read the Ibis/IPL User Manual (see the Documentation section) before embarking on parallellizing your program.  Also, you may have a look at the two provided simple IPL examples, in src/ibis/ipl/examples.

Benchmark your application by running it on the DAS-5 system.  Try to get as close to perfect speedups as you can.  Also, try to explain the reasons why you get lower/better than perfect performance.

Test your application on 1, 2, 4 and 8 nodes with 1, 4 and 16 cores per node (see below how to use the prun command to achieve this). This will spawn various numbers of Ibis instances and the different configurations will allow you to measure and report the speedups and performance patterns.

Make sure you use prun to submit your job, even for jobs using only one ma- chine.  If you run a job on the frontend instead of a node, you will both overload the frontend, which is used by a lot of people, and get useless performance measure- ments! You may use the timers provided by Java (System.currentTimeMillis or even System.currentTimeNanos) to measure the performance of sections of your code. Op- timize your program such that the grain size of the leaf jobs is controlled to improve performance (i.e., do not put very small jobs in the job queue, but calculate those di- rectly).

Write a short 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, mentioning the experimental setup for each measurement (e.g.  number of nodes, cores).  Don’t just show numbers, but present a speedup graph as well, and preferably separate graphs for different core settings (i.e. 3 graphs, for 1, 4 and 16 cores with the number of nodes on the x axis).  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 program and how you measured its performance. The program itself should contain useful comments that illustrate how it works.

Compiling and Running your Java programs

You may compile your Java program with the . /gradlew command, using the pro- vided build .gradle. You need to use Java 1.8. Be sure to use the module com- mand on the DAS-5 (e.g. module  load  java/jdk- 1 . 8 . 0). For more informa-

tion see the "DAS-5 for PPP users" documentation in the Course Documents on the Canvas PPP website.

To run a parallel program on the DAS-5 nodes, you need to make use of the prun script (see "DAS-5 for PPP users" in the Course Documents, for more information on the DAS-5 and prun). Furthermore, several run scripts are provided: bin/java-run to run the sequential version, bin/ibis-run, which allows you to run an Ibis appli- cation on your workstation, and bin/ibis-prun, to be used with prun.

sequential on your workstation/laptop (assumes Linux or MacOS):

$  bin/java-run  ida .sequential . Ida  <args>

ipl version, 2 instances, on your workstation/laptop (assumes Linux or MacOS):

$  bin/ibis-run  2  ida .ipl . Ida  <args>

sequential on a single DAS5 node:

$  prun  - 1  -np  1  bin/java-run  ida .sequential . Ida  <args>

ipl version on 8 DAS5 nodes using 1 core per node (8 Ibis instances in total):

$  prun  - 1  -np  8  bin/ibis-prun  ida .ipl . Ida  <args>

ipl version on 8 DAS5 nodes using 4 cores per node (32 Ibis instances in total):

$  prun  -np  8  -4  bin/ibis-prun  ida .ipl . Ida  <args>

bonus assignment on 8 DAS5 nodes using 4 cores per node (32 Ibis instances in total):

$  prun  -np  8  -4  bin/ibis-prun  ida .bonus . Ida  <args>

For more information on compiling and running IPL applications, see the user’s guide and programmer’s manual of the IPL (see the documentation section).

Submitting

You have to submit your code (preferably containing useful comments that illustrate how the application works and is parallelized) and the report.  Important:  Because we use automatic test scripts to test and benchmark your submissions, you must strictly follow the instructions below.

• Make sure that you create your submission zip file with "./gradlew submit". The main function of your program should be in the Ida.java file of the ida.ipl pack- age, and the main function for your bonus submission should, likewise, be in the Ida.java file of the ida.bonus package. "./gradlew submit" will pack the contents of the src, the pdf file(s) from the docs directory, and also the build.gradle file (you may have added dependencies).  We will test your program by replacing the skeleton src directory and build.gradle with the one from your submit zip, so please make sure it will work like that.

• Also, make sure that your parallel programs give the exact same output as the se- quential program. We compare your application’s standard output (System.out) with the correct output with the diff command. Note that the runtime should be printed on standard error (System.err).  The format of the runtime line should also not be changed.

• 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 de- fault values, because our automated test scripts do not know your command line options.

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.  Note that the script does not check whether your application is behaving correctly in all cases, it just checks whether the output is formatted correctly and gives the correct answer for the default parameters and a sample input file.

• Create the report as a PDF file, and make sure you place the file in the pre-created docs directory.

Documentation

• Java 1.8 documentation

• The IPL API section on the Ibis website

• The IPL utilities section on the Ibis website

• The IPL programmers manual

• The IPL users guide

• The code for the sequential implementation, available in the file for this assign- ment.

Grading

A correct implementation of all the requirements above is graded with an 8, follow- ing the grading guides outlined during the kickoff meeting. Up to 2 bonus points (to grade 10) may be given for extra work on implementation, optimizations, testing and benchmarking. For example:

• Replace the sequential workers of the default assignment by multithreaded work- ers that can make use of multi-core processors of the DAS-5. If you follow this approach, it will be interesting to compare the performance between the multi- process execution of the single-threaded application with your multi-threaded approach (for the same number of effective instances).

• Implement work stealing instead of the single centralized work queue.

To get the bonus points, it is up to your imagination 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 addi- tionally 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 steps:

• Get the sequential version of the IDA* Puzzle solver from the course Canvas page, under Assignments.

• Create a parallel application using the IPL. The  . /gradlew command will download the IPL libraries if needed.

• Test your application on the DAS, using prun; see the "DAS-5 for PPP users" documentation in the Course Documents on the Canvas PPP website.

• 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.