10/31/08

Bad multithreading

Thread 1 Thread 2

Lecture 20: Multicore Strategies for Games Prof. Aaron Lanterman School of Electrical and Computer Engineering Georgia Institute of Technology
Thread 3 Thread 4 Thread 5
Slide from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation

Good multithreading

Physics
Another paradigm: cascades
Thread 1: Input Thread 2: Physics Thread 3: AI Thread 4: Rendering

Particle Systems

Game Thread Main Thread Rendering Thread

Animation/ Skinning

Thread 5: Present
Advantages: Synchronization points are few and well-defined Disadvantages: Increases latency (for constant frame rate) Needs simple (one-way) data flow For balance, each chunk needs to take a similar amount of time

Networking

File I/O
Typical task: File decompression
Most common CPU heavy thread on the Xbox 360 Easy to multithread Allows use of aggressive compression to improve load times Dont throw a thread at a problem better solved by offline processing
Texture compression, file packing, etc.
Typical task: Rendering Separate update and render threads Rendering on multiple threads usually works poorly
GPU can have trouble if multiple threads try to talk to it at once (Xbox 360 command buffers are supposed to be OK)
Special case of cascades paradigm
Pass render state from update to render
Slideadapted from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Separate rendering thread
Typical task: Graphics fluff
Extra graphics that doesnt affect play
Procedurally generated animating cloud textures Cloth simulations Procedurally generated vegetation, etc. Extra particles, better particle physics, etc.
Update Thread Buffer 0 Buffer 1 Render Thread
Can run at lower frame rate Easy to synchronize One game had one thread manipulating cloth, another thread handling cloth shadows On single-core machines, can drop or simplify the fluff without effecting gameplay
Slide adapted from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Typical tasks: Physics? Could cascade from update to physics to rendering
Makes use of three threads May be too much latency
Careful with simultaneous multi-threading
Not the same as double the number of cores Can give a small performance boost
if first thread is underutilizing execution resources because of dependency stalls
Can cause a performance drop
Two threads may fight over L1 cache
Could run physics on many threads
Uses many threads while doing physics May leave threads mostly idle elsewhere
Can avoid scheduler latency
Have a thread that is ready to run but OS waits for current scheduling quantum to expire before running the thread Hardware threads can wake up faster; works well if you have a thread that mostly sleeps but needs to wake quickly on demand

Rares Kameo

Case study: Kameo (1)
Started out as single threaded

Was going to be an original Xbox game, but decided to and make it a 360 launch title
CPU usage split was 51/49 for update/render, so rendering was put on separate thread
Two render-description buffers created to communicate from update to render Linear read/write access for best cache usage Doesn't copy const data
Screenshots from www.rareware.com

Case study: Kameo (2)

Decompression thread:
Saved space on DVD and improved load times Cost was some spare CPU cycles

Case Study: Kameo (3)

Screenshot from www.rareware.com
Core Thread Software threads

80-99%

Game update File I/O Rendering XAudio File decompression
Actually two threads for file I/O
One for reading and one for decompressing, because some calls can block for ~0.5s doing directory lookups
Multithreading added about six months before launch - but it worked!
Total usage was ~2.2-2.5 cores
Bizarre Creations Project Gotham Racing 3
Case Study: Project Gotham Racing 3
Screenshot from projectgothamracing3.com/screenshots
Core Thread Software threads 1 Update, physics, rendering, UI Audio update, networking Crowd update, texture decompression Texture decompression XAudio
See http://media.xbox360.gamespy.com/media/741/741362/vids_1.html for movie clips
Total usage was ~2.0-3.0 cores
Available synchronization objects
Critical sections (locks) Events Semaphores Mutexes Dont suspend threads
Some games have used this for synchronization Can easily lead to deadlocks Interacts badly with Visual Studio debugger
Synchronization tips/costs:
Synchronization is moderately expensive when there is no contention
Hundreds to thousands of cycles
Synchronization can be arbitrarily expensive when there is contention! Goals:
Synchronize rarely Hold locks briefly Minimize shared data
Beware hidden synchronization
Memory allocation (i.e., malloc in C)
All sorts of ways to alleviate the problem
Things to avoid (at least for now)

Threads terminating other threads
Cant do it on Xbox 360, discouraged on Windows
File access Using D3DCREATE_MULTITHREADED if developing with unmanaged code False sharing - artefact of cache structure
Performance issue, not a correctness issue Bruce Dawson, Multicore Memory Coherence: The Hidden Perils of Sharing Data, PowerPoint Presentation
Information from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Mutexes (arent as fast as critical section locks) Lockless programming (probably not worth extra complexity and bug-proneness)
Bruce Dawson, Lockless Programming Considerations for Xbox 360 and Microsoft Windows
msdn2.microsoft.com/en-us/library/bb310595.aspx

What about OpenMP?

#pragma omp parallel default(none) shared(n,x,y) private(i) { #pragma omp for for (i=0; i < n; i++) x[i] += y[i]; }

Take a step back

Always ask: should I be doing this on the CPU at all? GPU has ridiculous amounts of computing power
Look for tasks with high compute per CPUGPU communication ratio
Industry tends to shy away from OpenMP and similar solutions Prefers more direct control
(Example from somewhere on web; cant remember where)
HLSL is HLSL whether youre using managed or unmanaged code on the CPU

Bad multithreading

Thread 1 Thread 2 Thread 3 Thread 4
Lecture 14: Multicore Strategies for Games Prof. Aaron Lanterman School of Electrical and Computer Engineering Georgia Institute of Technology

Thread 5

Slide from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation

Good multithreading

Physics
Another paradigm: cascades
Thread 1: Input Thread 2: Physics Thread 3: AI Thread 4: Rendering Thread 5: Present
Advantages: Synchronization points are few and well-defined Disadvantages: Increases latency (for constant frame rate) Needs simple (one-way) data flow For balance, each chunk needs to take a similar amount of time
Game Thread Main Thread Rendering Thread

Particle Systems

Animation/ Skinning

Networking

File I/O
Typical task: File decompression
Most common CPU heavy thread on the Xbox 360 Easy to multithread Allows use of aggressive compression to improve load times Dont throw a thread at a problem better solved by offline processing
Texture compression, file packing, etc.
Typical task: Rendering Separate update and render threads Rendering on multiple threads usually works poorly
GPU can have trouble if multiple threads try to talk to it at once (Xbox 360 command buffers are OK)
Special case of cascades paradigm
Pass render state from update to render
Slideadapted from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Separate rendering thread
Typical task: Graphics fluff
Extra graphics that doesnt affect play
Procedurally generated animating cloud textures Cloth simulations Dynamic ambient occlusion Procedurally generated vegetation, etc. Extra particles, better particle physics, etc.
Update Thread Buffer 0 Buffer 1 Render Thread
Easy to synchronize One game had one thread manipulating cloth, the another thread handling cloth shadows On single-core machines, can drop or simplify the fluff without effecting gameplay
Slide adapted from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Typical tasks: Physics? Could cascade from update to physics to rendering
Makes use of three threads May be too much latency
Careful with simultaneous multi-threading
Not the same as double the number of cores Can give a small performance boost
if first thread is underutilizing execution resources because of dependency stalls
Can cause a performance drop
Two threads may fight over L1 cache
Could run physics on many threads
Uses many threads while doing physics May leave threads mostly idle elsewhere
Can avoid scheduler latency
Have a thread that is ready to run but OS waits for current scheduling quantum to expire before running the thread Hardware threads can wake up faster; works well if you have a thread that mostly sleeps but needs to wake quickly on demand

Rares Kameo

Case study: Kameo (1)
Started out as single threaded
Was going to be an original Xbox game, but decided to and make it a 360 launch title
CPU usage split was 51/49 for update/render, so rendering was put on separate thread
Two render-description buffers created to communicate from update to render Linear read/write access for best cache usage Doesn't copy const data
Screenshots from www.rareware.com

Case study: Kameo (2)

Decompression thread:
Saved space on DVD and improved load times Cost was some spare CPU cycles

Case Study: Kameo (3)

Screenshot from www.rareware.com
Core Thread Software threads

80-99%

Game update File I/O Rendering XAudio File decompression
Actually two threads for file I/O
One for reading and one for decompressing, because some calls can block for ~0.5s doing directory lookups
Multithreading added about six months before launch - but it worked!

Total usage was ~2.2-2.5 cores
Bizarre Creations Project Gotham Racing 3
Case Study: Project Gotham Racing 3
Screenshot from projectgothamracing3.com/screenshots
Core Thread Software threads 1 Update, physics, rendering, UI Audio update, networking Crowd update, texture decompression Texture decompression XAudio
See http://media.xbox360.gamespy.com/media/741/741362/vids_1.html for movie clips
Total usage was ~2.0-3.0 cores
Available synchronization objects
Critical sections (locks) Events Semaphores Mutexes Dont suspend threads
Some games have used this for synchronization Can easily lead to deadlocks Interacts badly with Visual Studio debugger
Synchronization tips/costs:
Synchronization is moderately expensive when there is no contention
Hundreds to thousands of cycles
Synchronization can be arbitrarily expensive when there is contention! Goals:
Synchronize rarely Hold locks briefly Minimize shared data
Beware hidden synchronization
Memory allocation (i.e., malloc in C)
All sorts of ways to alleviate the problem
Setting thread priority in C#
t.Priority = ThreadPriority.Normal;
File access Using D3DCREATE_MULTITHREADED if developing with unmanaged code False sharing - artefact of cache structure
Performance issue, not a correctness issue Bruce Dawson, Multicore Memory Coherence: The Hidden Perils of Sharing Data, PowerPoint Presentation
Information from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Highest, AboveNormal, BelowNormal, Lowest
Defaults to normal OS may ignore you Be careful about boosting thread priority
If the priority is too high, you could cause the system to hang and become unresponsive If the priority is too low, the thread may starve
Final bullet from Bruce Dawson & Chuck Walbourn, Microsoft Game Technology Group, Coding for Multiple Cores, PowerPoint presentation
Things to avoid (at least for now)
Threads terminating other threads
Cant do it on Xbox 360, discouraged on Windows

What about OpenMP?

#pragma omp parallel default(none) shared(n,x,y) private(i) { #pragma omp for for (i=0; i < n; i++) x[i] += y[i]; }
Mutexes (arent as fast as critical section locks) Lockless programming (probably not worth extra complexity and bug-proneness)
Xbox 360 CPU may rearrange reads/writes Bruce Dawson, Lockless Programming Considerations for Xbox 360 and Microsoft Windows

msdn2.microsoft.com/en-us/library/bb310595.aspx
Industry tends to shy away from OpenMP and similar solutions Prefers more direct control
(Example from somewhere on web; cant remember where)

Take a step back

Always ask: should I be doing this on the CPU at all? GPU has ridiculous amounts of computing power
Look for tasks with high compute per CPUGPU communication ratio
HLSL is HLSL whether youre using managed or unmanaged code on the CPU