Introduction
There is “A Fundamental Turn Toward Concurrency in Software,” or so says the title of a recent article by Herb Sutter in Dr. Dobb's Journal. This article is prompted by the emergence of dual-core processors and the expectation that multi-core processors will eventually become the norm. Modern computer games stress the limits of current desktop platforms so game developers will likely be early adopters of dual-core and multi-core technology.
Threading Prince of Persia: Warrior Within for GDC 2005, Martin Sevigny, Ubisoft Technical Director, had this to say about threading: “Dual-core is going to help us produce much more ‘living' games with more animation, AI, physics, all sorts of cool stuff that we were not able to do before.” The following article is not a case study of a particular game. Rather, it is intended as a generic study based on experience with real games. The goal is to present some of the pitfalls to threading games along with possible solutions.
Defining the Problem
The inherent complexity of game engines makes them more difficult to thread than other applications. Various subsystems [e.g., artificial intelligence (AI), physics, character animation, collision detection, rendering, audio, etc.] manage aspects of the game engine. As a player moves through the virtual world of the game, a video forms. However, there is no predefined sequence of events. The actions of the player are effectively random from the game's perspective. The game is a real-time, event-driven process. This creates a problem for threading – the frame sequence is inherently sequential. In other words, each frame depends on the preceding frame. Therefore, multiple frames cannot be computed independently and in parallel to boost frame rates and improve performance. Techniques to predict more than a frame in advance would introduce latency and negatively impact the player experience.
Since it is impossible to exploit inter-frame parallelism, one must look within a frame for potential threading targets. Simultaneously computing the AI, character animation, collision detection, etc. would be ideal. However, most of today's engines were designed without considering parallel computation. As a result, dependencies exist among the subsystems that limit the effectiveness of threading (Figure 1). Here are just a few examples:
- Some characters cannot move until the AI subsystem tells them what to do.
- Sounds (e.g., foot steps, gunshots, speech, etc.) cannot be emitted until all events and actions for the frame are decided.
- Collision detection is a continuous process that can interrupt other computations.
- Rendering cannot occur until the final state of the frame is decided.
|
 |  |
 |
 | Figure 1. This graph gives an example of the interaction of components in a game engine. Notice the dependencies that exist between components within the engine itself: each subsystem can receive information from any other subsystem to affect results both within a frame or in future frames. |
The extensive inter-frame and intra-frame dependencies described above limit the opportunities to exploit parallel computing. Inter-frame dependence means that multiple frames cannot be computed in parallel. Within a frame, dependencies between subsystems (e.g., AI and character animation) mean that one must go deeper into the code to find threading opportunities. This has two disadvantages, but it is necessary to define a couple of parallel computing concepts before discussing these disadvantages.
Amdahl's Law
Parallel speedup is limited by the amount of serial computation. This simple concept, known as Amdahl's Law, is illustrated in Figure 2. If 50% of an application is inherently serial, parallelizing the other 50% yields a maximum theoretical speedup of 1.3 on two processors. The frame calculation shown in Figure 2 is an over-simplification but it illustrates how Amdahl's Law can impact intra-frame parallelism. Even if each subsystem can be parallelized effectively, the work of the audio and graphics subsystems is still a serial bottleneck; the slower the subsystem, the worse the bottleneck. The examples in Figure 2 also assume perfect parallelism. The cost of thread creation, synchronization, and other parallel overhead is ignored. Maximum speedup will be lower if these factors are considered. Tools exist to assist in determining bottlenecks in your application. One such example is Intel's VTune Performance Analyzer, which can be used to identify application bottlenecks and suggest additional performance opportunities.
 | Amdahl's Law
 |
| T p | Parallel runtime |
| Ts | Serial runtime |
| %S | Percentage of time spent in serial code |
| N | Number of processors |
Task | Fraction | Serial or Parallel |  | AI | 0.1 | Parallel | Character animation | 0.2 | Parallel | Particle dynamics | 0.1 | Parallel | Physics | 0.2 | Parallel | Collision detection | 0.1 | Parallel | Audio | 0.1 | Serial | Video | 0.2 | Serial | |
Figure 2. According to Amdahl's Law, parallel speedup is limited by the amount of serial computation. The simple diagram at top left shows that if only 50% of the total runtime is spent in parallel execution, the maximum theoretical speedup is only 1.3 on two processors. The example frame computation assumes that each subsystem is threaded but the audio and video computations are strictly serial. Even though only 30% of the total frame computation is serial, the maximum theoretical speedup is only 1.5. Also note that this example assumes perfect parallelism in each engine. Parallel overhead is ignored. |
Granularity
Granularity is another important concept in parallel computing. It is loosely defined as the amount of work per parallel task. Unlike Amdahl's Law, there is no equation to determine granularity. It is a relative and somewhat subjective metric. When dividing a problem into independent tasks, a fine-grained decomposition produces a large number of small tasks. A coarse-grained decomposition produces a smaller number of large tasks. For threading to be beneficial, the amount of work per thread must be larger than the parallel overhead associated with the thread. Therefore, coarse granularity usually yields better parallel performance.
Attempts to decompose a 3D game engine into independent tasks have, so far, produced successively finer granularity. Dividing the frames among threads gives the coarsest granularity, but the video sequence evolves over time in this type of game, and time is inherently sequential. Within a frame there are a number of tasks that could be computed in parallel except for the intricate pattern of dependencies (Figure 1). The only option remaining is to thread within the individual subsystems required to calculate each frame. This grain size may be too fine for threading to benefit some games.
As a practical example, consider that a typical 3D game engine outputs many frames per second (FPS). At 30 FPS, each frame takes only 0.0333 seconds to compute. Let's assume that the particle dynamics subsystem can be effectively parallelize and that it accounts for 5% of each frame computation (0.0017 seconds). A computation that takes so little time is unlikely to benefit from parallelism after considering the overhead of thread creation, scheduling, synchronization, and management.
Solving the Problem
Amdahl's Law and fine granularity will limit the benefit of threading in many 3D game engines. However, increasing the amount of work per frame can lessen their impact. For example, adding more visual effects, increasing the number of characters, and using a smarter but more compute-intensive AI not only improves game play, it can improve the ratio of time spent in parallel versus serial computation. It also increases the amount of work per thread, thus improving granularity.
This solution is relatively easy to implement, and by taking advantage of a second processor, it is possible to improve game play without sacrificing frame rates. However, this is hardly a perfect solution. It is not scalable because the effects of Amdahl's Law and fine granularity cannot be completely eliminated. The audio and graphics subsystems still constitute a serial bottleneck. Also, adding more computation may not be appropriate for games that target consoles with limited resources.
Redesigning game engines to take advantage of multiple processors is another alternative. An engine designed with parallelism in mind should scale better than a legacy engine retrofitted with threads. However, developing new games engines is time-consuming. Also, it is not possible to completely eliminate the dependencies between subsystems (Figure 1). However, it might be possible to perform these computations asynchronously, as shown in Figure 3.
In this model, each subsystem performs its computations continuously with the latest information available. This would permit each subsystem to be updated on different threads with frequencies independent of the render loop. Dependencies still exist. For example, character animation still requires input from the AI. Rather than sit idle waiting for AI to complete its current calculation, however, the animation subsystem grabs the latest AI update. A separate thread periodically sends the latest frame to be rendered. (For more details and an example implementation using a simple collision detection system, see the references in the Suggested Reading at the end of this article.)
This method is not without disadvantages. First, the threads will occasionally need to access shared data. Data sharing could limit the effectiveness of this method depending on the level of synchronization required. Second, an asynchronous engine is definitely more complex than existing sequential engines. Designing an asynchronous engine will require some experimentation and calibration. Some subsystems take longer to compute than others. Some subsystems must be updated more frequently than others. It could also be advantageous to map more than one subsystem to the same thread, especially if those subsystems are tightly coupled. Fortunately, the industry is developing tools to assist with writing parallel code. For example, the Intel® Thread Checker identifies race conditions, such as storage conflicts and deadlocks, and other thread-specific problems that affect program correctness before they happen. The errors reported by the Intel® Thread Checker often indicate sections of code that require synchronization. For example, two threads simultaneously writing to the same memory location can cause data corruption. This type of race condition, known as a storage conflict, is prevented by synchronizing access to the shared variable or by giving each thread a private copy of the variable.
After the threading problems are fixed and the code is working correctly, performance improvements should be validated. For this, a developer can use the internal performance profilers to validate that the new code is providing the benefits expected. If these internal tools do not exist or a developer wishes to further validate the changes, the developer can use the Intel® Thread Profiler, to identify performance problems such as lock contention, load imbalance, excessive system overhead, etc., that limit multithreaded performance. Once identified, there are several common techniques to address parallel performance problems. For example, making some variables or data structures private to each thread can eliminate the need for synchronization.
Figure 3 illustrates the importance and difficulty of calibrating the computation frequency of each subsystem. The collision detection (CD) subsystem is mapped to thread-3 (T3). When the second CD computation begins (indicated by the first dotted blue line), the character animation (CA) is still in progress. Therefore, the first CD computation is still valid. Performing the second CD computation wastes processor resources and provides no additional information. New CA information is available by the third CD computation (indicated by the second dotted blue line), even though AI is still in progress. Similarly, the first and second render computations proceed with updated CA information but the third render computation does not. Without updated CA information, is rendering a new frame necessary? These examples show how the computation frequency of each subsystem can impact parallel efficiency.
|
 | |
|
| Figure 3. In this model, the artificial intelligence (AI), character animation (CA), and collision detection (CD) subsystems are mapped to separate threads that run asynchronously. A fourth thread periodically gathers the latest frame information and sends it off to be rendered. |
Conclusions
Threading real-time, event-driven games to take advantage of multiple processors is a complicated task. Retrofitting a legacy game engine with threads is possible but parallel performance may vary widely. Redesigning game engines with parallelism in mind is a better long-term solution.
