I was reading about how task schedulers work in game engines. What is unclear to me is what kind of work is usually scheduled inside these tasks.

Do engines usually tick an actor inside a separate task? And if that actor triggers a pathfinding request, would that be a subtask? Should a pathfinding task allocate its own memory or access a global navmesh data for example?

I guess what I would like are real life examples on how such parallel systems can and are used in practice. Maybe some best practices based on examples would be nice. Most literature I found was quite theoretical and left me with so many questions.

  • 3
    \$\begingroup\$ Your question is too broad, and covers too many fields. try to make your question more concise. What precisely is it you want to know? \$\endgroup\$ – Ian Young Nov 8 '17 at 11:29
  • \$\begingroup\$ I think the question is pretty clear. If you have a task scheduling system, what kind of work do games usually delegate to these tasks and what is usually kept in, let's say, the main loop or a dedicated worker thread? \$\endgroup\$ – Björn M.P. Nov 8 '17 at 11:45
  • \$\begingroup\$ "Most literature I found was quite theoretical and left me with so many questions." This is because parallel computing is a heavily theoretical field, and to be honest, has little to do with game design and a lot to do with game engine design. There is no way to answer your question without getting quite technical. \$\endgroup\$ – Ian Young Nov 8 '17 at 12:16
  • 2
    \$\begingroup\$ There are nearly as many answers to the question "what kind of work is done by tasks" as there are task systems. ;) To narrow this down to the scope of a Q&A answer that will be useful to you and future users, it's often better to frame it in terms of "what kind of work do you need to do in your game, @BjörnM.P.?" What specific engine feature are you developing that's leading you to consider task scheduling as a solution? What needs must it serve, under what kind of load and context? Then we can propose architecture options suited to that specific problem. \$\endgroup\$ – DMGregory Nov 8 '17 at 12:29
  • \$\begingroup\$ In my case it would be a 2D engine with a lot of pawns doing pathfinding and AI. The entities in the engine are component based. So there is a sprite component, physics component, etc. \$\endgroup\$ – Björn M.P. Nov 8 '17 at 13:21

Parallelism is still a hotly debated subject in game engine design, and yes, is very heavily based in theory. I'll try to keep this as non-technical as I can.

Here are some (but not all) general rules about parallel computing:

  1. No two or more tasks can modify the same data at the same time.
  2. Tasks should complete before any dependent tasks are executed.
  3. Two or more tasks running in parallel should not block each other.
  4. The cost of starting a task should not outweigh that of executing the task itself.

It's definitely worth trying to wrap your head around Amdahl's Law, as it is extremely important when considering parallel design.

Following is the typical game engine update cycle:

  1. Update positions (motion)
  2. Collision detection (collisions following motion)
  3. Game logic (scripts, event handling etc)
  4. AI/Path-finding
  5. Physics (physical collision response)
  6. Animation (state changes based on game logic and collisions)
  7. Rendering

Some of these tasks are dependent on preceding stages.

E.g. Physics is useless, unless collisions are detected.

Rendering, however, only cares about objects current state. Any state changes can be picked up on the next render cycle. This is achieved through the use of proxies and observer types.

Animation is the same, as is motion, AI and path-finding.

So, we can say that a single repeating task should be to detect collisions and perform physics.

This is thread #1

Next, we run the rendering system on the main thread (there are compelling technical reasons for this). Let's call this thread #0.

AI and rendering, in some cases is not independent, so we add a task to perform animation on thread #0, preceding rendering.

Game logic can go on thread #2, and respond to game events being generated

Path-finding and AI operations can go on thread #3

These tasks are more or less independent of one another, and so can be said to run in free step

If you find yourself in a situation where inter-thread synchronisation is necessary, you can block execution, until a task on another thread is complete, but typically this points to bad architecture or data design and is commonly known as lock step.

Another way is to run through the update cycle, and parallelise the individual jobs to do, so as to divide updating the positions and orientations of 100 objects between N tasks. This is known as data parallelism and is how modern graphics cards work.

With regards to task scheduling, see the above rules: If the tasks are embarrassingly parallel i.e. the nature of the task lends itself well to being assigned time on a thread, and does not interfere with other tasks, then do so.

But consider rule #4: if you have 4 threads and 100 objects, do you:

  • (a) create 100 small tasks and split them between the threads(4x 25 tasks), or
  • (b) create 4 tasks to process 25 objects each?

If the cost of creating and scheduling the task is comparable to executing it, then Amdahl's Law comes into effect, and you end up losing performance, if you choose (a). Therefore you choose (b), and cut down as much overhead as possible. Creation of threads are not free, and neither is locking down the scheduler/thread pool to assign or retrieve tasks. Therefore the task cost must be greater than the cost of scheduling. In most cases, this will be true, not it is not by any means guaranteed.

So, the tl;dr of the matter is: Schedule jobs, which are independent(if possible), and consist of a high enough computational cost to justify it's own task. In the case where the task set up cost is too high to justify a set of single tasks, group the jobs together into a larger task, and have that executed on it's own thread in parallel with with similar tasks of the same workload.

  • 1
    \$\begingroup\$ Ok, this is a good general description on how threads are used. Doom 3 for example uses a dedicated render thread while the main loop produces render commands and feeds them in a queue to this render thread. What I would like to know is about the specific use of a task scheduler, where many tasks are scheduled in a queue and consumed by one of the worker threads. In 3D engines I remember that bone pose updates in a model are often scheduled as individual tasks. My question would then be, what else do games usually delegate to these kind of tasks? \$\endgroup\$ – Björn M.P. Nov 8 '17 at 13:07
  • \$\begingroup\$ I can't definitively answer that, but I have updated the end of my answer to include some general information about task scheduling. \$\endgroup\$ – Ian Young Nov 8 '17 at 13:51
  • \$\begingroup\$ I would also point out that the Doom 3 Engine, whilst useful for education purposes, is very old, and it's design philosophy is quite dated. try looking at the source for Unreal 4, which is both modern, and in common use. \$\endgroup\$ – Ian Young Nov 8 '17 at 13:59
  • \$\begingroup\$ What is old becomes new again. \$\endgroup\$ – Ray_Garner Dec 7 '18 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.