Concurrent
But what about second lunch?
But what about second lunch?
The programming paradigm that focus on threaded programs is called concurrent programming. The basic that is needed for this is threadsafe code. With that one can split up the work into threads and look forward to the ocean of bugs that will follow.
Data-parallel
This is when the same code needs to run on many elements and where the computations are independent of each other. For example a particle system with 4000 thousand particle scan be split up and in 1000 particles each and run on 4 threads at once.
Pipeline-parallel
A game can be split up pieces where each system can run on it's own thread. For example the it can be split into simulation and rendering. First the game is updated and then the world is drawn. These steps need to be done after each other so on a single core it is easy. When run on different threads the rendering still need the result from the simulation. That can be solved by working on two frames at the same time. The simulation updates the game for frame N while the render thread draws the previous frame N-1. When the simulation thread is done it can pass on the result to the rendering thread and start working on simulating the next frame.
Task-parallel
The goal with a job-based system is to make sure the hardware threads have work to perform all the time. This is done by splitting up the things that need to be done into jobs, small separate unit's that runs quickly. The jobs are run by worker threads that each get to run on it's own separate hardware thread. Each job is simply a function to be called and a pointer to any data the function might need. The worker thread runs the function and when the function returns the job is done so it will get a new job and run.
For a job based system to work well the jobs need to behave and not lock, wait or take to long time. It should get to job done as fast as possible and then return. If it is a big job it is better for it to split it up into smaller jobs and then return so the jobs can spread out over multiple worker threads. It can create a job to wait for the completion of the spawned jobs.
Building a load-balanced task scheduler - 2012
Sponsored Feature: Do-it-yourself Game Task Scheduling - 2010
id Tech 5 Challenges - 2009
Fiber
A fiber system is like a job based system where it is possible to yield to other fiber in the middle of execution. It is a form of cooperative multi-threading where the running code that select when to yield. When it does it will capture the context of the registers and the stack and save them. The worker thread can then run a new fiber or resume one of the ones already active. The good thing with a fiber system is there is no context switching by the OS so there is minimal overhead switching between fibers. A fiber can also wait on the work it has created, a bit like a thread that spawns other threads without the cost of spawning the threads.
Links
Multi-Threading The Truth - 2017
What every systems programmer should know about lockless concurrency - 2017
Why by-convention read-only shared state is bad - 2015
Killzone Shadow Fall: Threading the Entity Update on PS4 - 2014
Lightweight In-Memory Logging - 2012
A C++ Profiling Module for Multithreaded APIs - 2011
Keeping Many Cores Busy: Scheduling the Graphics Pipeline - 2010
Introduction to Parallel Programming Models - 2009
Down the concurrency rabbit hole - 2009
Current Generation Parallelism In Games - 2008
Multithreading Optimization Basics - 2007
The Transition to Concurrency -2007
Internals of a lightweight task scheduler - 2015
Implementing a lightweight task scheduler - 2015
Multi-core programming and cache coherency
Job System 2.0
1: Basics
https://blog.molecular-matters.com/2015/08/24/job-system-2-0-lock-free-work-stealing-part-1-basics/
2:A specialized allocator
https://blog.molecular-matters.com/2015/09/08/job-system-2-0-lock-free-work-stealing-part-2-a-specialized-allocator/
3:Going lock-free
https://blog.molecular-matters.com/2015/09/25/job-system-2-0-lock-free-work-stealing-part-3-going-lock-free/
4:parallel_for
https://blog.molecular-matters.com/2015/11/09/job-system-2-0-lock-free-work-stealing-part-4-parallel_for
5:Dependencies
https://blog.molecular-matters.com/2016/04/04/job-system-2-0-lock-free-work-stealing-part-5-dependencies/