Transcript Waterman_2x

The Effects of Parallel
Programming on Gaming
Anthony Waterman
Topics to Discuss
• Are online games conceptually parallel?
• What portions of a game benefit from parallelization?
• Graphics Processing Units (GPUs)
• General-Purpose Computing on Graphics Processing Units (GPGPU)
• History of Parallel Programming in Consoles
• Parallelization = Game Development Success?
Online Client-Server Games are Conceptually Parallel
•
•
•
Clients are identical programs with different data
(SPMD - Single Program Multiple Data)
Multiple client computers take input from a user,
execute local game functions, and communicate
necessary information to the master server
Server
Client A
Client B
Client C
Server takes information from the clients, executes
local server-side functions, and communicate
necessary information back down to the clients
Both the clients and the server contribute to as well as make up the overall state of the game
Additional Similarities Between
Client/Server & Classical Parallel Programming
• Communication between processors/computers is time consuming
Communication time can create bottle necks in both applications
• Both applications can use local sequential functions to compensate
•
Client/Server
Game
Classical Parallel
Application
(Prime Number Sieve)
Communication
• Game lag
• Significantly slower
Bottleneck appears as: • Sluggish response time
completion time
Solution:
• Local prediction of
• Locally calculated
upcoming game state
starting values
What portions of a game benefit from parallelization?
• Graphics
•
Graphics in video games are not
accomplished in the same way
movies/videos are done
•
•
•
In a video game, what the player sees is created
as the game is played
Processors must decide what color each pixel
needs to be in order to show the correct image
Graphics Processing Units (GPUs) are
responsible for nearly all video game
graphics
Graphics Processing Units (GPUs)
•
A GPU is essentially a chip with tiny built-in
processors or cores often referred to as
shaders designed to process graphics
•
•
•
Shaders are simplistic by design and are used to
process large magnitudes of image data to create
the desired picture
Generally divided into two types (though others
exist)
• Vertex Shaders – process 3D data in order to
display it on a 2D screen
• Pixel Shaders – determine the color and
attributes of a pixel
The number of shaders vary by GPU, but the most
recent console GPUs have 768 (Xbox One) and
1152 (PS4)
What portions of a game benefit from parallelization?
• Physics
•
Many modern games have simulated
physics
•
Simulation Games are generally built
around a complex physics environment
•
What happens in the game is a direct result of a
multitude physics equations and parameters
Possible Implementation for a Rocket Engineering Game
• Basic Algorithm for Physics Simulations
•
Setup
•
•
•
Each component and connection has structural strengths, attributes, current velocity, etc.
Each processor is responsible for modeling 1 or more components/connections
Algorithm
•
•
•
•
•
•
Force analysis on each component/connection
• Computation intensive, requires some communication to solve for forces from other components
Strength computations to determine if any component/connection will fail
• Highly computation intensive and parallelizable***
Update components/connections if failures have occurred
Summation of forces on each set of connected components to determine acceleration
Apply acceleration to update each component’s current velocity and position
Move forward one time step and repeat
Possible Implementation for a Rocket Engineering Game
Check Forces
Analyze Force
Vectors
Versus
Component/
Connection
Strengths
Update
Components/
Connections
Force
Summation
for Each Set
of Connected
Components
to Determine
Acceleration
Apply
Accelerations
to Update
Component
Velocities
and Positions
…
…
…
…
…
…
…
…
…
…
Advance
Time
Step
What portions of a game benefit from parallelization?
• Artificial Intelligence (AI)
•
•
•
•
AI is an essential component to most
video games
AI programs generally involve large
data sets and robust decision trees,
making them prime candidates for
parallel computation
Another parallelizable function closely
linked to AI is pathfinding
Pathfinding uses decision tree
algorithms to find the most
direct/desired path by checking a vast
number of possible paths
What portions of a game benefit from parallelization?
• World Generation
•
Example: Minecraft
•
On the PC version of
Minecraft, maximum blocks
that can be generated in a
world is approximately
921,600,000,000,000,000.
•
*This example is only to show
the scale of what could be
accomplished. Minecraft
generates small portions of
the world procedurally.
What portions of a game benefit from parallelization?
• Character Generation
•
•
•
•
Custom created characters are
common among RPGs
Using the same slider type
architecture, characters could
be created using parallel
computing
This could be especially useful
for generating multiple
characters at once
Machine created characters
should be created intelligently
General-purpose computing on graphics processing units (GPGPU)
•
What is GPGPU?
•
•
GPGPU is the use of graphics processing unit’s inherent parallel structure to perform nongraphic calculations
•
GPGPU is used in the #2 ranked supercomputer in the world, the Titan which takes
advantage of Nvidia GPUs
•
In gaming, GPGPU can help with some of the more computation intensive tasks such as AI
and physics modeling
• PlayStation 4 is one console that is confirmed to use their GPU in physics simulation
applications
GPGPU applications are constrained by limited number of operations the GPU cores are able to
process
General-purpose computing on graphics processing units (GPGPU)
History of Parallel Programming in Consoles
First use of multiple processors
Non-parallel applications (Late 1980’s)
4th Generation of gaming consoles
•
•
•
Super Nintendo Entertainment System (SNES)
Sega Genesis/Mega Drive
Used Central Processing Unit (CPU) +
Graphics Processing Unit (GPU) +
Sound Processor
•
Distinct processors carried out specific tasks
History of Parallel Programming in Consoles
•
Multiple Processors (Parallel
applications)
•
Sega Saturn (1994) (5th Gen)
• First console to use 2 CPUs
•
•
Game developers lacked the ability
to program parallel game
components
Processors were primarily given
separate tasks
History of Parallel Programming in Consoles
•
Xbox 360 (2005) (7th Gen)
•
•
•
Tri-core CPU with shared memory
GPU consisting of 48 cores
PlayStation 3 (2006) (7th Gen)
•
•
Cell microprocessor using a "Power Processing
Element" (PPE) and 6 available “Synergistic
Processing Elements” (SPEs)
• First commercial use of the cell microprocessor
architecture in any system, not consoles
exclusively
GPU consisting of 32 cores (Some graphics tasks
handled by Cell CPU)
History of Parallel Programming in Consoles
• Current Generation of Consoles (8th)
•
Xbox One (2013) (8th Gen)
•
•
•
CPU consists of 2 quad-core processors, 8 cores
total
GPU consisting of 768 cores ***
PlayStation 4 (2013) (8th Gen)
•
•
CPU consists of 2 quad-core processors, 8 cores
total
GPU consisting of 1,152 cores ***
Recent Parallelization Popularity (CPU) 2000-2015
CPU Cores
7
8
8
8
7
6
5
3
4
3
2
1
1
1
0
Xbox
PlayStation 2
Xbox 360
PlayStation 3
Xbox One
PlayStation 4
Microsoft
Sony
Microsoft
Sony
Microsoft
Sony
6th Generation
7th Generation
8th Generation
Recent Parallelization Popularity (GPU) 2000-2015
GPU Cores
1152
1200
768
1000
800
600
400
200
16
6
48
32
0
Xbox
PlayStation 2
Xbox 360
PlayStation 3
Xbox One
PlayStation 4
Microsoft
Sony
Microsoft
Sony
Microsoft
Sony
6th Generation
7th Generation
8th Generation
Parallelization = Game Development Success?
•
•
Not all games require parallelization in order to be
successful
Parallelization provides benefits:
•
•
•
•
•
•
Better graphics
More accurate simulations
Smarter artificial intelligence
Etc.
Some games, most notably Independent or Indie
games, succeed through captivating gameplay and
story
Parallelization is a tool that expands a developers
options in terms of game design
Questions?