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:
- No two or more tasks can modify the same data at the same time.
- Tasks should complete before any dependent tasks are executed.
- Two or more tasks running in parallel should not block each other.
- 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:
- Update positions (motion)
- Collision detection (collisions following motion)
- Game logic (scripts, event handling etc)
- Physics (physical collision response)
- Animation (state changes based on game logic and collisions)
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.