New version page

UConn CSE 2102 - Homework #8

Documents in this Course
Load more

Previewing page 1


Unformatted text preview:

CSE 3100 Systems ProgrammingHomework #8 Due: 12/4/2018Complete your work in the hw8 folder. Remember to pull, add, commit, and push.Exercise 1. Life (100 points)Conway’s game of Life is a famous cellular automaton simulation devised by John Conway in 1970. It isa very simple zero-player game where the evolution of the game is strictly dictated by the initial boardconfiguration and an update rule. Despite its simplicity, the game can give rise to surprisingly complexpatterns over time. The game takes place on a board with m rows and n columns. The board is assumedto be toroidal with row m − 1 being followed by row 0 and column n − 1 being followed by column 0. Theneighbors of cell (i, j) are the 8 cells surrounding it, namely (i − 1, j − 1), (i − 1, j), (i − 1, j + 1), (i, j − 1),(i, j + 1), (i + 1, j − 1), (i + 1, j), and (i + 1, j + 1). Note that computing the coordinates of the neighborsshould be done using arithmetic modulo m and modulo n, respectively, to “wrap around” in the respectivedirections if needed.Each cell of the board holds a simple boolean value indicating whether the cell is alive or not. The gameevolves through generations. In generation k, every cell on the board goes through a survival process todetermine whether it will be alive in generation k + 1. The status of cell (i, j) in generation k + 1 is basedon the status of (i, j) and its neighbors in generation k, as follows:When (i, j) is alive in generation k. If the number of living neighbors in generation k is:0 or 1 then (i, j) dies in generation k + 1 as there are too few live neighbors,2 or 3 then (i, j) remains alive in generation k + 1,4 or more then (i, j) dies in generation k + 1 as there are too many live neighbors.When (i, j) is dead in generation k and the number of live neighbors is 3, a new cell is born at (i, j) ingeneration k + 1.To produce interesting behavior one can start with an initial board containing a specific pattern. Anumber of starting configurations are included in the git repository; for instance, the file start1.txt containsthe so-called “glider” pattern. You will also find in the git repository a sequential implementation thatsimulates the game of Life starting from an initial configuration given as its first command line argument(so you can simulate the game starting from the glider pattern by running “./life start1.txt”). Thesequential implementation animates on the terminal 1000 iterations (the default can be changed by specifyinga second command line argument) and saves the final board to a text file named final.txt.Your task is to implement in lifeMT.c a multi-threaded version of the simulator, as follows:• You should modify the Makefile so that it builds a multi-threaded executable named lifeMT• Your multi-threaded executable should take the same command line arguments as the sequential ver-sion, and should save the final board in a text file named finalMT.txt• Your executable must use at least two worker threads to update the board• You must use appropriate synchronization mechanisms to produce a correct final boardFeel free to experiment with the division of work between threads. The board can be divided by rows,by columns, or in even smaller rectangular regions. To prevent unnecessary work, you can maintaining a“dirty” bit for each region indicating whether or not any modification has taken place within the region orits adjacent cells in previous iteration – if a region is “clean” then none of its cells need to be modified incurrent iteration either. Threads can update pre-defined sets of regions, or you can use a queue of “dirty”regions from which worker threads dynamically pick their update tasks. Most creative solutions will receiveextra


View Full Document
Loading Unlocking...
Login

Join to view Homework #8 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework #8 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?