这是一篇关于并行Java：24个谜题的Java代写

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 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 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 puzzle 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, allowing 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 machine. 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 measurements! You may use the timers provided by Java (System.currentTimeMillis or even System.currentTimeNanos) to measure the performance of sections of your code. Optimize 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 directly).

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 provided build.gradle. You need to use Java 1.8. Be sure to use the module command on the DAS-5 (e.g. module load java/jdk-1.8.0). For more information 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 application 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 package, 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 sequential 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 default 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.