Here's a fun project I worked on to try and keep some of my skills sharp. Conway's Game of Life is a simple simulation of sorts that operates on a few very basic rules. I've been fascinated with it for a while because of how versatile it can be and the things people can create with it. I knew the rules were simple so I decided I would take a shot at creating a simple implementation. The original implementation was super simple and very easy to implement, but I wanted to take it a step further and set it up to handle much larger grids. So instead of using a single thread to process the whole array, the next best thing is to use multiple threads and decompose the problem. My first thought was to create multiple threads each frame and explicitly tell each thread which portion of the grid to work on. While this does work, the overhead for spawning multiple threads each frame caused some serious performance issues. In fact it was less performant than the single threaded version. I haven't done a lot of multi-threading work in C# and this was a good reminder that those underlying system calls take just as long in high level languages. So instead of creating new threads each frame, I needed a rudimentary job system with semi-general purpose worker threads. Originally I toyed with mutex locks to keep the workers and the control thread synchronized, but I couldn't readily come up with a good design for that. The solution that I did come up with was much easier to implement and very straight forward. During my parallel programming class we had an assignment to implement a basic ecosystem simulation where different parts of the ecosystem needed to be simulated at different stages in each frame. We used wait barriers to keep everything synchronized, and that problem was similar enough to this problem that wait barriers worked really well. With this design I only need one mutex lock for the work queue, and three barriers for each processing stage. Some careful loop placement in the worker threads allows for more work units on the queue than worker threads, and my basic job system works very well! Getting rid of the many system calls per frame, but keeping multiple threads brought the performance back up to where I wanted to see it, and now the simulation runs well at larger scales. Check out some of the code highlights after the video, or check out the full source code on github!
Here's the code that manages all the worker threads.
private void LockedThreadProcedure()
{
try
{
//Set up and start the worker threads.
for(int i = 0; i < threadCount; ++i)
{
Thread t = new Thread(ConsumerThreadProcedure);
t.Start(i);
workerThreads.Add(t);
}
while (true)
{
while (running)
{
Console.WriteLine("Setting up the work orders");
//set up the work load.
ClearArray(b2);
Stopwatch clock = new Stopwatch();
clock.Start();
int numberChunks = DIMENSIONX / workChunkSize;
for(int i = 0; i < numberChunks; ++i)
{
WorkOrder w = new WorkOrder();
w.rowCount = workChunkSize;
w.rowIndex = i * workChunkSize;
WorkQueue.Enqueue(w);
}
PrepBarrier.SignalAndWait();
Console.WriteLine("Waiting for workers to finish");
WorkBarrier.SignalAndWait();
Console.WriteLine("Processing data");
//Process the results from the worker threads.
++generation;
LoadArrayIntoBitmap(b2);
ClearArray(b1);
for (int i = 0; i < DIMENSIONX; ++i)
{
for (int j = 0; j < DIMENSIONY; ++j)
{
b1[i, j] = b2[i, j];
}
}
UpdateGenerationLabel(generation);
SetPictureBoxImage(img);
UpdatePictureBox();
clock.Stop();
long elapsedtime = clock.ElapsedMilliseconds;
if (elapsedtime < (long)threadSleepTime)
{
long delta = (long)threadSleepTime - elapsedtime;
Thread.Sleep((int)delta);
}
ProcessBarrier.SignalAndWait();
}
}
}
catch(ThreadAbortException ex)
{
//If this thread is aborted, we need to also stop all the worker threads.
foreach(Thread t in workerThreads)
{
t.Abort();
t.Join();
}
return;
}
}
And here's the actual code for the worker threads.
private void ConsumerThreadProcedure(object data)
{
int myID = (int)data;
try
{
while (true)
{
PrepBarrier.SignalAndWait();
//This second loop is necessary so that the worker thread keeps trying to
//consume data if there is data left on the queue. The previous version
//worked only because there were 8 threads and exactly 8 pieces of work to
//be done each frame. If the grid was increased in size it would break because
//not all of the work would be done each frame. This fixes that issue.
while (true)
{
WorkOrder w = null;
lock (queueLock)
{
if (WorkQueue.Count > 0)
{
//grab the work
w = WorkQueue.Dequeue();
}
else
{
break;
}
}
Console.WriteLine("Thread: " + myID.ToString() + " has acquired its lock and will begin working");
if (w != null)
{
//Process the work order.
for (int i = w.rowIndex; i < w.rowIndex + w.rowCount; ++i)
{
for (int j = 0; j < DIMENSIONY; ++j)
{
if (b1[i, j] == 1)
{
ProcessAlivePixel(i, j);
}
else
{
ProcessDeadPixel(i, j);
}
}
}
}
}
WorkBarrier.SignalAndWait();
ProcessBarrier.SignalAndWait();
}
}
catch(ThreadAbortException ex)
{
return;
}
}