Parallel Game Of Life - Information exchange between threads

Question

I am trying to implement a parallel version of 'Game Of Life'.

This parallel version divides the game's board into regions, each governed by a single thread which is responsible of calculating this region's next state and conduct the state update afterwards.

One of the constraints I am facing here is the fact that - "Each thread is allowed to access only its own region cells. All other information should be communicated from the neighboring threads by some other memory".

So, the way I understand this, even if one thread attempts to read only from a cell outside it's region, it must somehow request this state from the specific thread which is running this cell.

We are encouraged to consider the producer/consumer solution for this task, and so I have considered using a public static produce/consumer queue into which state requests shall be enqueued, but some other related issues are not clear to me:

• If thread A is conducting a job at the moment, how can I ask it to halt it's work and hand thread B it's information request and resume it's previous job afterwards? Is it even possible?

• Which thread is responsible for this queue? a unique thread which manages the queue in parallel to the regular regions threads? I am not sure.

Answer 1

The easiest solution is to imagine there are multiple steps in each round. Let's say there are N threads.

1. step 1: each thread makes a list of cells it needs to discover. It puts the "question" in one of the N queues that there are (one for each thread).

2. wait for all the threads to finish

3. step 2: each thread fill the responses for its queue of question

4. wait for all the threads to finish

5. step 3: each thread computes the new state of its region

6. wait for all the threads to finish