Multithreaded Java Program for Conway's game of life - contention at the border cells

Question

I am learning concurrent programming in java, and writing a simulation for Game of Life.

Here is what I am thinking:

• Use int[][] to store the states of the cells
• partition the int[][] into t segments and use t worker threads
• The t threads will read from their segment, calculate new values for all the cells in their segment and update the cells.
• Once they finished calculation they wait at a barrier for other workers to finish
• when the barrier is crossed the main thread will update the UI.
• the workers proceed to calculate the next state.

Now there is going to be contention at the common borders of the segments. If a thread overwrote the state of a border cell before its neighbor has read the previous value, the neighbor's calculation is going to be wrong.

What are my options?

• Use callable instead of runnable and have the worker threads return the new value (instead of updating the segments themselves). The main thread can update the matrix after the barrier is crossed. This option involves copying the results returned by worker threads into the matrix.
• Use two barriers. The workers thread make a copy of the border cells from their neighbors' segments and wait at the first barrier. Once this barrier is passed, they proceed to calculate the next states and update the segments in place. Then they wait at the 2nd barrier. the main thread updates the UI.

My question is, is there any other way to deal with the contention at the border cells that does not involve copying data or is more efficient that the above two options? May be using ReaderWriterLock, volatile variable or other synchronizing mechanism?

UPDATE: So far the double buffering solution by Peter is the cleanest one. But I have a question. Since the two arrays are shared data and we are not using any synchronization (synchronized access or volatile variable), won't it create visibility problem? Could multiple CPUs cache the array values and update only a part of the array with each iteration? Then the threads will get stale values for the border cells. Is this possible? If not, why. If yes, how do I solve it? It seems declaring two arrays volatile will not make their individual elements volatile.

Answer 1

It doesn't answer your actual question, but my recommendation would be your first option... having the new values returned rather than having the worker threads update them. I'd take it a step further and have the "aggregator" combine the results from the worker threads into a new board state array and then discard the first one. My reasoning being that it will improve the overall readability of the logic, since there will be little to no "global interactions" you have to worry about.

That being said, I'm a bit biased because I prefer to program in a functional manner except when there's a strong reason not to.

Answer 2

I would try the following approach:

• Have the workers perform the calculations, but only write back the values to the inner cells.
• For border cells, store the results.
• When the calculations are complete, wait at a barrier.
• When all workers are at the first barrier, release then and allow each to write the border cells.
• Wait at a second barrier while the UI updates

Storage required for a n x m tile is 2 * (n + m - 1), so generally larger tiles (8x8 or more) require proportionately less memory for the cached values.

Answer 3

I suggest having 2 int[][] arrays. Let's call them A and B. A will hold the values of all odd numbered "ticks" and B will hold the even numbered ticks.

Initialize A to whatever your initial state looks like. Then let your threads loose to calculate the next state of each cell, and place the results in the corresponding cell in B. Once all your threads are done, you have your new state in B. Now, use B to calculate the next state of each cell, and store the results in A. At any given time, one array will be read only, and the other write only, so there will never be any contention.

Advantages:

• No copying of data compared to what you do now. Only one write is happening per cell.
• No having to worry about edge/corner cases, as the algorithm is simple.
• No ongoing allocation of memory. Just allocate the two arrays when you start.

Disadvantages:

• You need to allocate twice as much memory.

Answer 4

I just stumbled upon java.util.concurrent.Exchanger<V>. It acts as a point of exchange. I can probably use it to exchange lists of cell-states between adjacent threads. That would be better than barrier because I need to synchronize only between adjacent workers.

Answer 5

To answer your update about the caching issue with double buffering, it is not a problem. CPUs have coherent cache, and they know when data has been changed in another cpu cache.