The Game of Life

Recently, my colleague, Dick Bowler and I wrote a sample application that implements Conway's Game of Life. The purpose of the sample was to visually demonstrate the performance of a single threaded version of an algorithm vs. a scalable multi-threaded version. The app was to display two game boards side-by-side; the first board would have the computation for the next generation handled by a single thread and the second would be multi-threaded. We had fun implementing this sample and learned a few things along the way.

First, we decided to be adventurous and mix native C++ and C++/CLI. We planned to use C++/CLI for the user interface (to pick up the Windows Forms classes from the .NET Base Class Library) and C++ for the game board calculations. Second, we wanted to write code that would scale in performance as it ran on additional processor cores. To this end, we decided to use Intel's Threading Building Blocks library to implement the parallel algorithm code. Finally, we wanted the display to update in real time as the boards were recomputed so that the user could watch successive generations as they evolved.

Going in, as a longtime C/C++ developer, I was skeptical of C++/CLI, and I disliked the strange syntactic extensions to the language. It seemed like another "embrace and extend" tactic where the language would be altered into a proprietary dialect. However, after using C++/CLI for a bit, I must say that the combination worked OK for this application. I was able to manage the syntactic differences ("ref class," "gcnew," handles, etc) fairly easily and was able to easily mix native and managed types. I had access to the same Base Class Library as when using C# and yet could drop down to native C++ code when needed, without having to use COM interop. Overall, I still don’t like the syntactic changes, and the associated loss in portability, but the combination worked as well as we had hoped.

Previously, I have implemented sample programs that partition applications only at a high level - worker threads, user interface thread, etc - and have realized that while they are an improvement over entirely single-threaded applications, applications partitioned in this way will also hit a performance wall as the number of processors increases. Eventually, each of the applications threads could be running on its own processor core, and the application would receive no further benefit from additional processor cores. With the Game of Life sample, we intended to use the Threading Building Blocks to show how applications should continue to extract parallelism at the algorithmic level. In other words, if developers can code algorithms to be multi-threaded, the applications will scale further than those applications that just have high-level partitioning. Intel's Threading Building Blocks (TBB) library is a good tool for implementing parallel algorithms. The TBB library is available for multiple operating systems and compilers and allows developers to implement algorithm-level parallelism in a processor-independent way.

For me, getting the application to update the UI for successive generations was, surprisingly, the hardest part of the application. Each game board window was responsible for updating its contents every time a new board was computed. First, we tried to post a message to the window for it to update itself with the new board data. While this worked, the application UI effectively froze as incoming events were drowned in the requests for board updates. This was definitely unacceptable. After all, we have complained many times in this series of blogs about unresponsive applications :). After some thought we figured a way out: after computing the next board to display, draw directly into the board's graphic context (more like a computer game would as it draw successive frames) instead of posting a message to the window’s message queue.

Anyway, this series of samples has been fun, and we look forward to developing a few more. If you're interested in C++/CLI, TBB, or graphically representing the results of your algorithm in real time, check out the sample.

Michael Jeronimo

Comments

[Yousef]

Thanks for the great illustrative TBB example, although it's partially written with horrible C++/CLI which I think you've done since you're using some MS Compiler/GUI toolkit.
I wonder if you can provide an alternative standard C++/Qt approach.
Thanks in advance,

[Mike Dean]

Don't be so hard on him. He probably doesn't know HOW to program without the Microsoft crutches. A better question, though, would have been to see it programmed with just C++ and boost in addition to the TBB version, like real programmers do.