Lab 5

Introduction

OptsRus will now put all of its optimization knowledge to work in its biggest challenge to date: optimizing an artificial life simulator. Given original C code from the client, OptsRus can use parallelize the code to exploit multicore machines, as well as perform other optimizations to improve performance.

Background

You will be optimizing Conway’s “Game of Life” (GoL), a famous, simple algorithm for computing artificial life (cellular automota), that through very simple rules can generate very complex and interesting behavior. You can read more about the history and details of GoL here: https://en.wikipedia.org/wiki/Conway%27s Game of Life You can also play with a GoL emulator here: http://www.bitstorm.org/gameoflife/

Setup

Ensure you're in the ece454 directory within VSCode. Make sure you have the latest skeleton code from us by running: git pull upstream main.

This may create a merge, which you should be able to do cleanly. If you don't know how to do this read Pro Git. Be sure to read chapter 3.1 and 3.2 fully. This is how software developers coordinate and work together in large projects. For this course, you should always merge to maintain proper history between yourself and the provided repository. You should never rebase in this course, and in general you should never rebase unless you have a good reason to. It will be important to keep your code up-to-date during this lab as the test cases may change with your help.

You can build the GoL executables with Meson:

meson setup build
meson compile -C build

Input and output files are in a simple image format called .pbm. The executable initboard can create an arbitrary-sized input file by running:

build/initboard <num_rows> <num_cols> <generated_file_name>

The executable gol is run as follows:

build/gol <num_iterations> <infilename> <outfilename>

If you want to visualize an input or output file, you can convert it to a JPG for viewing in a browser with the command:

convert filename.pbm filename.jpg

Visualizing can potentially help you think of opportunities for optimization.

Optimizing

Your main task in this homework is to speedup GoL using everything you learned in the course. You can parallelize (if you want) and use as many threads as you like (the tester physical limit is 4). You are also free to perform any optimization you wish on your program, including rewriting all aspects of the program or adjusting meson.build.

Rules

• You must work individually
• Given some input file and some number of iterations, your program must produce the identical output file as the original unmodified GoL program.
• Your program must be faster than the reference implementation
• The code must be your own, i.e., you cannot directly incorporate GoL-specific acceleration code or libraries written by others. However, you can study them and come up with a similar implementation. You must be able to explain exactly what is happening with the code when asked by the TA.
• Your program must be able to execute on successfully on both the tester machine and the ug lab machine.

Assumptions

• You can assume the dimensions of all input game boards to be N x N, where N is a power of two.
• You can assume a maximum world size of 10000x10000. However, your program should at least exit gracefully if a larger size is attempted.
• Your code does not have to handle cases for worlds sizes less than 32x32.

Measurement

For this homework your implementation should be measured from start to finish, using /usr/bin/time. In other words, we will include the entire computation in the measurement, including reading and writing files, initialization, thread creation or other overheads associated with parallelization. We will measure your speedup only by running GoL for 10,000 iterations on the 1k.pbm file provided. Please test your speedup with the command below which provides the "wall clock" timing of your program in seconds. Afterwards, submit to the auto-tester to compare against others. If you find this execution is prohibitively long for quick optimization prototypes, feel free to experiment with smaller files, or fewer Life generations, but recall that your speedup is based on the configuration below.

/usr/bin/time -f "%e real" ./gol 10000 inputs/1k.pbm outputs/1k.pbm

Correctness

As stated above, for the same input, the output of your optimized/parallelized program must match the output of the original program. We will test the correctness of your code using several input files of varying sizes and initial configurations. We have provided one (read-only) output file 1k_verify_out.pbm, which you can use to verify your program in the "speedup" configuration above. Verify correctness by running:

diff outputs/1k.pbm outputs/1k_verify_out.pbm

Be sure to frequently test/debug your current program state on different inputs. Consider generating a few new input files (and the original output file) beyond those we have provided.

Marking Scheme

The total available marks are divided into 2 portions (70% + 30%). The first portion is for non-competitive portion and modest improvement over reference implementation. You will receive full marks if your solution compiles and runs successfully and is at least 100x faster than reference solution. A plain text file containing a short description (no more than 150 words) of how your program and your optimization work, and what you have tried need to be included as well. The report is only for reference purposes to support you if we suspect you are cheating. The second portion is competitive. This lab is designed to have significant room for performance optimizations. For this portion, we will be using an automated scoring system similar prior labs. Once you submit your work using the usual git push command, your submission will be placed onto a queue for auto-grading. The competitive portion mark will be scored based on the following formula:

$$\sqrt{\frac{\text{your speedup} - \text{50}}{\text{top speedup} - \text{50}}}$$

Marks will only be assigned if the program run successfully!

Submission

Simply push your code using git push origin main (or simply git push) to submit it. You need to create your own commits to push, you can use as many as you'd like. You'll need to use the git add and git commit commands. You may push as many commits as you want, your latest commit that modifies the lab files counts as your submission. For submission time we will only look at the timestamp on our server. We will never use your commit times (or file access times) as proof of submission, only when you push your code to GitHub.