Before about 2005 most CPUs contained one core. This meant that the programmer could explicitly control the order that everything happened. This is illustrated in the following pseudocode:
// main loop do { for every character step forward one time interval; for every combination of game objects check for collision; if collision has occurred take appropriate action; render frame; } until game ended;
However, if we want to use the power of multi-cores, we need to give each core different tasks to do but how to we divide this work up?
Most languages provide a way to do this, many allow the programmer to insert an instruction to start a new thread, when the program reaches this instruction the new thread will start executing instructions from some specified point in the program. This may, or may not, be executed in a separate core. When this thread has been started the original thread will continue with the code, so two threads are now running. Either of these threads can start further threads, and so on, so we can have a virtually unlimited number of threads.
How do we split up our game into different threads? For instance, should we start each game character running in a separate thread?
Writing parallel code in this way has lots of problems both for design and debuging.
Some of the problems of parallel code are:
- Deadlock bug - Two tasks require output from the other to coninue which results in a stalemate and they both stop.
- Race bug - Two tasks need to access the same piece of information from memory, one task might update the memory before the other has finished using it. This can be dealt with by "locking" a piece of memory but this can then cause the deadlock bug and it slows down the program.
New programming languages:
X10 - Prevents deadlock bug by classifying tasks in a hierarchy of "parents" or "children". It contains a command called "finish" that allows parents to wait for cildren, but not vice versa.
TM - Transactional Memory - The systems work out which tasks require the same piece of memory and lock those peices of memory at only the times required by each task.