Portfolio of Michael T. Mayers

Introduction

Today I am going to share my current thoughts on a scene design supporting concurrency evolved from experiences on the last game I worked on. My previous design had at least some parallelism in that it had separate threads for update and render.

New is my formal realization that this previous method was in fact a 2 stage pipeline and that more pipeline stages will promote more task and data parallelism at the cost of more latency. It mimics a CPU/GPU multi staged pipeline where all stages execute concurrently. Every stage of this pipeline produces a result which is usable in the next stage. These results must be multi-buffered for threaded access (similar to a double buffered GPU commandlist). Only one stage can touch a result buffer at a time. When the previous stage is done writing to a result buffer the next stage may begin reading and acting upon it.

This model attempts to combine traits of both the “Synchronous function parallel model” and “Data parallel model” as described in Multithreaded Game Engine Architectures( Ville Mönkkönen: gamasutra.com-sep-2006). Our model differs from the Synchronous function parallel model in that it executes input and control concurrently with physics and animation, with each stage operating on data sets from different frames. There is also a pipeline model described in Multi Threading Models (GeorgiaTech). Under “Disadvantages”, it states “limits degree of parallelism, throughput driven by slowest stage”. Our new pipeline model described here at least attempts to address that disadvantage by opening up the possibility for per stage data-parallelism.

Review current system

Lets illustrate how our game entities are structured. This will aid in explaining some of the design decisions we will have to make later. Here is some c++ pseudo-code:

What Next?

From the above code we can see that our game entities (class Entity) are composites made from a collection of EntityComponentInst objects, with one EntityComponentInst per family. A family is just a grouping of components that have similar functions and are executed together as one. Examples of a family would be “input”, “control”, “camera”, “physics”, “animation”, “particles”, “audio”, etc… A given family may have many component types (classes) assigned to it, for example the “control” family may include player control components and AI control components among others. The scene maintains a list of active components per family and families are usually updated in a specific order. Originally components were executed in family order to improve instruction cache behavior. This will also give us some properties beneficial to parallelism.

Take a moment to look at the pictures below to get an idea of where we are headed. It is not import yet to fully grok what they are portraying.

To map this entity/component/family architecture to the pipeline model, we will constrain certain families to certain stages. On a given stage, components assigned to that stage can optionally be updated in family order. As an example, if the “input” component family requires updating before the “control” component family, then all “input” components can optionally be guaranteed to finish before any “control” components. To accomplish this we will use a family barrier. This family barrier will become important when we use inner-stage data parallelism. For now, realize that not all families will require this and since it will block until all threads for a given family have finished, we will only use it when absolutely necessary. Family barriers will never be necessary when a component in a later stage depends upon data calculated in a component assigned to an earlier stage.

Weird issues

If any given component needs to mutate the state of another component, it will likely require the use of a queued message. If some conditions are met then this message will be dequeued and processed the same frame, otherwise it will be dequeued and processed on the next frame. Conditions that allow same frame processing are:

• If the receiving component’s family is assigned to a later stage than the sending component’s family.
• Both components are assigned to the same stage, the receiving component’s family sorts after the sender’s family, and there is a family barrier between the two component types.
• Both components are assigned to the same stage, and that stage is currently single-threaded for that frame.

Symmetrically, if a component needs to query the state of another component, some constraints need to be put in place. If certain conditions are met, then you can query a component’s post update state this frame. Otherwise you will get that component’s post update state from the previous frame. Conditions that enable same-frame querying are:

• If the querying component’s family is assigned to a later stage than the queried component’s family.
• Both components are assigned to the same stage, the querying component’s family sorts after the queried component’s family, and there is a family barrier between the two component types.
• Both components are assigned to the same stage and that stage is currently single-threaded for that frame.

These two methods are necessary to guarantee consistency when dealing with data parallelism. They promote more data parallelism within the pipeline stage by hiding inner-stage data dependencies and preventing pipeline data hazard stalls. One technique you can use to help deal with the strange (but consistent) delivery timing of messages is: In a component’s update method, always process queued messages before doing anything else. This will at least enforce the correct ordering of state mutation.

Another method that will likely prove useful is the dual use of predictive and reactive distribution of work. Pipeline stages will attempt to predict how many data-parallel subtasks to split their workload into. Execution timing history may be kept to aid in the prediction process.

Latency

There is a 1 frame latency hit per pipeline stage. With 4 stages @ 60hz this equates to 66.6ms (4/60ths or 1/15th of a second) total latency – not including device driver command buffering or display latency. This seems reasonable to me (depending on the game of course). For some reference on latency, see this article. Obviously, at 120hz+ the latency gets better.

A picture is worth a thousand words

Here is a block diagram:




Notes:

• Only 1 job each may be executed concurrently for stages 1, 2 and 4. For stages 1 and 2, jobs may be split into subtasks for data parallel execution. Stage 4 communicates with hardware and should have no concurrency. If you are using Direct3D 11 and want multithreaded deferred contexts then they would execute as subtasks on stage 3 (AV preprocessing).
• This will support particles emitted from or influenced by post physics/skeletal animated data if the “particle” family sorts after the “physics” and “animation” families.
• There is a “Frame Persistant Data Boundary” that marks the boundary between data retained for further updating and data that dead ends at the AV renderers.

Thread Pools

I was thinking a Thread Pool would be good for servicing the pipeline stages. This is vaguely similar to the pattern I use in my mulithreaded dataflow graphs. The primary difference being the dataflow graphs have a lot more unhidden data dependencies than this pipeline model. The dataflow graph scheduler does a lot of dependency tracking. The graphs have static topology and are for the most part statically scheduled. The dataflow scheduler tries to schedule modules in parallel, but the data dependencies fight it. Multiple dataflow graphs have more freedom to execute concurrently. In contrast, the jobs processed by the pipeline model’s stages will vary more in number and will have minimal data dependencies that would benefit from a more dynamic scheduler.

Visualize the timing

Here is an example timing diagram: (estimated)

Other desired properties

It would be nice if we could maintain a few properties of the last system I worked on:

• ZERO heap memory allocations per frame. Use fine-grain-locked object pools and objects on the stack instead of the heap.
• Object data memory locality. Pools can be contiguous, strategic object placement within the pools can help data cache locality.
• Instruction cache locality. The old system updated entire families in whole and in sequence via per family lists. Since the update was single threaded and like objects with like v-tables were updated in sequence, it had decent instruction cache locality. When multiple threads are involved (in data parallel mode) I could see this property degenerating if not addressed. Perhaps by aggregating components into pairs or triples (keeping an eye on instruction cache usage and keeping the overall loop iteration code footprint down), we can get the best of instruction cache locality and data parallelism. Fortunately newer multicore CPU’s tend to have separate L1/L2 instruction caches per core which we can utilize.

References

Here is some reference material: (though I do not see much mention of the generalized “pipeline” model)
Multithreaded Game Engine Architectures( Ville Mönkkönen: gamasutra.com-sep-2006)
Multithreaded game design – help(gamedev.net-feb-2008)
Multithreading Models(GeorgiaTech)
Concurrency Patterns (WikiPedia>