Conway's Game Of Life Problem Parallel (OpenMP)

Question

I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.

The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).

The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of positions of live cells.

The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).

My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).

My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size > 10000).

Thank you !

Answer 1

There is a simple solution. Instead of storing a hashmap of all positions, store the set of only the positions that are currently alive. Live cells are included in the set; dead cells are not. When you want to know whether a particular cell is alive or not, look up that position in the set; if it is found, then the cell is alive, otherwise the cell is dead. You can store the set as a hashtable.

You said that you expect only about O(size^2) cells to be alive. My proposal reduces the space complexity to O(size^2), instead of O(size^3). Also, the running time to check whether a particular cell is alive will be O(1). The running time to enumerate all live cells will be O(size^2).

It follows that the running time to compute the next state of the world will be O(size^2). Since each cell has only 4 neighbors, you only need to enumerate O(5 * size^2) = O(size^2) many cells (all of the live cells and their neighbors) to see which will be alive in the next iteration. To tell whether a cell will be alive in the next iteration can be done by examining its state and the state of its 4 neighbors, which can be done in O(1) time.

This approach should also generalize nicely to a parallel/distributed implementation.

This all assumes that the number of live cells is limited to O(size^2) for all iterations. That might be a dubious assumption in practice: the number of live cells can quickly grow to O(size^3), for some initial configurations (in particular, it might take only O(lg size) iterations to go from O(size^2) to O(size^3) live cells).