GDC2013 - Job Graph: Task Graphing in Mortal Kombat

• Gavin Freyberg, Director of Technology at NetherRealm Studios, talked about their proprietary multithreading engine.
• All gaming hardware has multiple processors. The future is even wider and all games will need to run multithreading processes.
• Task graphing defines game system flow in terms of tasks and dependencies between them.
• Task and Job mean the same thing. Their job graph defines fixed function graphs, can have set of connection points between graphs, link graphs at runtime to form a meta-graph, keeps graphs independent unless dependencies state otherwise, and support child graphs.
• Characteristics of job graph - object-oriented approach to asynchronous behavior, data-driven, runs on SPU, scheduling burden is spread across threads, graphs have single entry and exit points, has basic priority schemes, predication of jobs possible, dependencies are left empty, context data are embedded in instance, use lock-free code
• It's important to create a visualizer of threads. The job graph visualizer is a standalone app that visualizes graph run. Its limitations are that it cannot have cycles in meta-graph, all depdency satisfiers must be known and well-controlled, and the perfect scheduling of jobs is NP-hard.
• The job graph components...
• The core system - fully data-driven, act on user-defined context data, dependencies are the glue that hold everything together
• Graph leader - describes an instance (data offset, data counts), encapsulates runtime state (return state, internal branching state, external wait state, dependencies, predicate state, context data)
• Token stream - describe execution of graph, are tokens for passing controls and job execution
• Dependencies - atomic counter and a list
• Work pool - contains multiple list of pending work, contains lock-free allocator for queues job data structures
• Loop - conditionally acquire exclusive resources (pop work or release if exhausted), exclusive resource doesn't go to work pool until something needs it
• Runtime system - owns the work pool, contains collection of instance lists, has special 2-pass instance launch process
• Migrating code to the job graph was easy. It involves breaking code into jobs based on dependencies, using exclusive resources as a porting aid, increasing priority of the critical path, and setting up relationships outside of the meta-graph.
• Results of job graph - explicit dependencies, low system overhead, supports runtime, allows conditional graph flows, can easily solve problems like 1 frame lag
• The main problem with using job graph was its overhead. It uses up 3% of CPU spread across all execution units.
• Mortal Kombat used a lot of middleware like Scaleform, fmod, and Havok. Middlewares were all encapsulated as a job in the graph.