$2.$ The serial solution

You are provided with a Java program that codes a serial solution to the simulation of the cellular automaton. The program hard codes the rules for the Abelian Sandpile that we will use for this assignment, but is generally applicable to other similar automata. Your first step should be to have a good look at the serial code. You will not and cannot change this code.

$2\mathrm{.}1$ INPUT

The program takes the following command line arguments in order:

input file name, output file name.

The input file is in comma separated value format $(.$csv$),$ where the first line contains the number of rows and number of columns in the data. The following lines are the rows in the file, with values for each column in the row. There are some example files provided in the input folder, but you can $($and should$)$ create more for testing. There are no checks for correct format of the file $$ you may add some to your parallel solution.

$2\mathrm{.}2$ Java classes

There are two classes in this the simple program, as follows. The AutomatonSimulation class runs the whole simulation; the Grid class represents the cellular automaton.

$2\mathrm{.}3$ Debug mode

If the DEBUG flag in the code is set to true $($you have to change the code to do this$),$ the program will output text representations of the grid at each step. It is not advisable to do this for large files...

$2\mathrm{.}4$ Running the code

Once you have had a look at the code, run it to see how it works. Experiment with different inputs with differing numbers of rows and columns and cell values.

After simulations has completed, the program outputs to the screen the number of rows and columns, the number of simulation timesteps required to reach the stable state and the total time taken. A Portable Networks Graphic $(.$png$)$ file is also written of the final stable state.

For example, if the program is executed as follows:

java $-$classpath bin serialAbelianSandpile.AutomatonSimulation

input$/65\_$by$\_65\_$all$\_4.$csv output$/65\_$by$\_65\_$all$\_4.$png

The output to the screen will be $($the time will vary depending on the computer on which you run it$)$:

Rows: $65,$ Columns: $65$

Simulation complete, writing image...

Number of steps to stable state: $1156$

Time: $27$ ms

$3.$ Your parallel solution

Your task in this assignment is to create a parallel version of the serial algorithm that is correct and runs faster. The parallel solution must avoid data races, by ensuring that threads compute nonoverlapping parts of the grid and that threads only proceed to the next timestep once all are done.

You can only use the join$()$ synchronisation mechanism in the assignment $$ no other synchronisation mechanisms are allowed $($e$.$g$.$ no barriers, synchonised methods, no atomic variables etc. Note that parallel programs need to be both correct and faster than the serial versions.

Therefore, you need to demonstrate both correctness and speedup for your assignment. If speedup over the serial solution is not achieved, you need to explain why this happens.

$3\mathrm{.}1$ Specific requirements

In this assignment, you must do the following.

$1.$ Profile the serial program, measuring the time taken to run for a range of input sizes and starting values for the cells..

$2.$ Write parallel version using the Java Fork$/$Join framework in order to speed up the algorithm. This version must have the same output text and file output as the serial solution $($although you can output other files as well, if you choose$).$

$3.$ Validate your parallel version to demonstrate that it works correctly $($i$.$e$.$ produces the same solution as the serial version$).$

$4.$ Benchmark your parallel program experimentally, timing the execution on at least two machines $($e$.$g$.$ your laptop and the departmental server$)$ with different input sizes, generating speedup graphs that show the conditions under which you get the best parallel speedup. $($Do not give timing graphs!$)$

$5.$ Write a short report including the graphs with an explanation of your findings.