Parallel Computing with GPUs

David Kaeli
Perhaad Mistry
R di D
Rodrigo Dominguez
i
Dana Schaa
Matthew Sellitto

Department of Electrical and Computer Engineering

Northeastern University
B
Boston, MA
 Objectives of this class
 Develop a new appreciation for thinking in parallel

 Provide an overview of many-core

many core and parallel
computing

 Present recent advances in GPU computing in terms

of both hardware and software

 Provide programming exercises and hands

hands-on
on
experience writing GPU programs

 Learn
L th
the b
basics
i off pthreads,
th d CUDA and
d OpenCL
O CL

 Discuss recent hardware advances by NVIDIA and

AMD
 Course Schedule
 April 7 - Parallel hardware and software - control and data
flow, shared memory vs. message passing, thread-level vs.
data-level
data level parallelism, pthreads programming

 April 14 - Introduction to GPU Computing with CUDA

Topics - GPU programming,
programming NVIDIA hardware

 April 28 - Intermediate CUDA Programming Topics -

Syntax sample programs,
Syntax, programs debugging

 May 5 - Introduction to OpenCL Computing Topics -

Syntax examples
Syntax,

 May 12 - OpenCL programming on AMD GPUs and X86

CPU T
CPUs Topics
i - Hands-on
H d programming
i anddd
debugging
b i
 Today’s Class

 Parallel hardware and software

 Multi-core CPUs
 SIMD
 Vectors
 GPUs
 Programming models
 Thread-based programming with pThreads

 Concepts
 Control and data flow
 Shared memory vs. message passing
 Thread-level vs. data-level parallelism
The move to multi-
multi-core computing
 The CPU industry has elected to jump off the
cycle-time scaling bandwagon
 Power/thermal constraints have become a limiting
factor
 Clock speeds have not changed
 The
Th memory wallll persists
i t andd multi-core
lti places
l
further pressure on this problem
 Microprocessor manufacturers are producing
hi h l
high-volume CPU
CPUs with
ith 8
8-16
16 cores on-chip
hi
 AMD Bulldozer has up to 16 cores
 SIMD/vector extensions – SSE ((streaming
g SIMD
extensions) and AVX (advanced vector
extensions)
 Also seeing
g multi-core in the embedded domain
 Why are Graphics Processors of interest?
 Graphics
G hi Processing
P i Units
U it
 More than 65% of Americans played a video game in 2009
 High-end
High end - primarily used for 3
3-D
D rendering for videogame graphics
and movie animation
 Mid/low-end – primarily used for computer displays
 Manufacturers include NVIDIA, AMD/ATI, IBM-Cell
 Very competitive commodities market
NVIDIA Comparison of CPU and GPU
Hardware Architectures (SP GFLOPS)

T12 - Fermi

GT200 - 285

G80

3GHz – Xeon Westmere

W t
3GHz – Core2
Quadcore
Duo

Source: NVIDIA
Comparison of CPU and GPU
Hardware Architectures
CPU/GPU Single Cores GFLOPs/ $/GFLOP
precision Watt
TFLOPs
NVIDIA 285 1.06 240 5.8 $0.09
NVIDIA 295 1.79 480 6.2 $
$0.08
NVIDIA 480 1.34 480 5.4 $0.41
AMD HD 6990 5 10
5.10 3072 11 3
11.3 $0 14
$0.14
AMD HD 5870 2.72 1600 14.5 $0.16
AMD HD 4890 1 36
1.36 800 72
7.2 $0 18
$0.18
Intel I-7 965 0.051 4 0.39 $11.02

S
Source: NVIDIA AMD and
NVIDIA, d IIntel
t l
 And parallel software?

 Hardware vendors have tried to roll their

own
 NVIDIA
NVIDIA’s s CUDA
 AMD’s CTM and Brook+
 Intel Ct Technology
 Software vendors are developing new
parallelization technology
 Multi
Multi-core
core aware operating systems – Microsoft
(BarrelFish), Apple (Grand Central Dispatch),
others
 Parallelizing compilers – Microsoft Visual, LLVM,
Open64, Portland Group, IBM XLC, others
 Portable frameworks for heterogeneous
computing
co put g – Kronos/OpenCL
o os/Ope C
 Hybrids – AccelerEyes (Matlab)
 So how to start writing parallel programs?
 If we use a shared memory system model
 A single contiguous memory address space
 Hardware/architecture provide for memory coherency
and consistency
 Threading can be used to manage synchronization and
serialization where needed
 Significantly reduces the burden of parallelizing programs
 If we use a distributed systems model
 Multiple memory address spaces are available
 Coherency and synchronization across these spaces is
managed
g by y explicit
p ((versus implicit)
p ) synchronization
y
 The programmer has the task of issuing explicit
communication commands to manage synchronization of
tasks and distributed memory
 Issues with Control Flow
 Imagine a world without control flow?
 Parsing is heavily control dependent
 Many
Man desktop applications are dominated b
by
control flow

 We
W would ld only
l hhave computation
i without
ih
any interpretation of the answers

 Control flow significantly impacts our ability

to carry out operations in parallel

 Can we avoid control flow?

Reasoning about Parallelism
We need to start thinking parallel

 To begin to utilize parallel systems such as

multi-core CPUs, many-core GPUs and
cl sters you
clusters, o need to understand
nderstand parallelism
 We will explore this through some simple
exercises
 We will explore some questions that will help
you understand the challenges we must
overcome tot exploit
l it parallel
ll l resources
Let’s Bake Some Cakes
 You are trying to bake 3 blueberry pound cakes
 Cake ingredients are as follows:

o 1 cup butter, softened

o 1 cup sugar
o 4 large
l eggs
o 1 teaspoon vanilla extract
o 1/2 teaspoon salt
o 1/4 teaspoon nutmeg
o 1 1/2 cups flour 1 cup blueberries
 Cake Baking 101

The recipe for a single cake is as follows:

 Step 1: Preheat oven to 325°F (160°C). Grease and

flour your cake pan.
 Step 2: In large bowl
bowl, beat together with a mixer butter
and sugar at medium speed until light and fluffy. Add
eggs, vanilla, salt and nutmeg. Beat until thoroughly
blended. Reduce mixer speed to low and add flour, 1/2
cup at a time,
i b
beating
i jjust untilil bl
blended.
d d
 Step 3: Gently fold in blueberries. Spread evenly in
prepared baking pan. Bake for 35 minutes.
 Step 4: Allow to cool for 20 minutes in pan. Remove from
pan
 Cake Baking 101

 Your task is to cook 3 cakes as efficiently as possible

 Assume that you only have one oven (large enough to
hold one cake), one large bowl, one cake pan, and one
mixer
 Come up with a schedule to make three cakes as quickly
as possible
 Identify the bottlenecks in completing this task
Cake Baking 101

 Assume now that you have three bowls, 3 cake

pans and 3 mixers. How much faster is the
process now that you have additional
resources?
Cake Baking 101

 Assume now that you have two friends that

will help you cook, and that you have three
ovens that can accommodate all three
cakes.
k
 How will this change the schedule you
arrived at in first scenario?
 Back to Cake Baking 101

 Compare the cake-making task to

computing 3 iterations of a loop on a
parallel computer

 Identify data-level parallelism and task-

level parallelism in the cake-making loop
 Cost/Performance

 Next, consider the following costs associated with cake baking

Ovens = $200/oven
Cake pans = $10/pan
Mixers = $25/mixer
Cooks = $75/cook
Bowls = $5/bowl
 Consider the following latencies
Grease and flour pan = 5 minutes
Mixingg time = 40 minutes
Cooking time = 30 minutes
Cooling time = 20 minutes
 Find the best cost vs. performance given these objectives:
P f
Performance in
i cakes/minute
k / i t
Performance in cakes /$
Parallelizing our lives

 Many of the tasks we perform in our everyday

lives include significant parallelism
 Can you name some of these?
 Write down a list of your daily activities (e.g.,
shower get dressed,
shower, dressed eat breakfast
breakfast, dry your hair)
 Identify at least 12-15 activities
 Consider which of these activities could be carried
out concurrently
 Identify pairs of parallelizable activities
What is wrong with our world?

 Next, consider why many of these cannot

presently
tl b
be carried
i d outt iin parallel
ll l
 What would need to be changed in our physical
world (e
(e.g.,
g showers
showers, cars
cars, Ipods) to allow us to
complete many of these activities in parallel
 How often is p parallelism inhibited byy our inability
y
of carrying out two things at the same time?
 Estimate how much more quickly it would
take to carry out these activities if you could
change these physical systems
What is wrong with our world? Nothing!!

There is rampant parallelism in the natural world!

Let’s pick some apples

If I want to pick all the

apples, but have only
one picker and one
ladder, how will I pick all
the apples?
Let’s pick some apples

What happens if I get a

second picker (a shorter
picker) but keep one
ladder, how will I pick all
the apples?
Let’s pick some apples

What happens if I get a

second picker and a
second ladder, how will
I pick all the apples?
Let’s pick some apples – heterogeneity…

What changes if the

trees have a very
different number of
apples on them?
 Parallel processing terminology
 Task
 A logically discrete section of computational work
 A task is typically a program or program-like
program like set of
instructions that is executed by a processor
 Serial Execution
 Execution
E ec tion of a program one statement at a time
 Virtually all parallel tasks will have sections of a parallel
program that must be executed serially
 Parallel
P ll l E Execution
i
 Execution of a program by more than one task, with
each task beingg able to execute the same or different
statements at the same moment in time
 Communications
 Parallel tasks typically need to exchange data through
a shared memory bus or over a network
 Parallel processing terminology
 Granularity
G l i
 A qualitative measure of the ratio of computation to communication
 Coarse: relatively large amounts of computational work are done
between communication events
 Fine: relatively small amounts of computational work are done
between communication events
 Parallel Overhead
 The amount of time required to coordinate parallel tasks, as
opposed to doing useful work
 Synchronizations and data communication
 Middleware execution overhead
 Massively Parallel
 Hardware that comprises a given parallel system - having many
processors
 The meaning of "many" keeps increasing
 Embarrassingly Parallel
 Solving
S l i many similar,
i il bbutt iindependent
d d t ttasks
k simultaneously;
i lt l littl
little
to no need for coordination between the tasks 
 Parallel processing terminology

 Threads Model
 In parallel programming
programming, a single process can have
multiple, concurrent execution paths
 The main program performs some serial work, and then
creates a number of tasks (threads) that can be
scheduled and run concurrently
 Each thread has local data, but also shares the entire
resources of main program
 Saves the overhead associated with replicating a
program's resources for each thread
 Each thread also benefits from a global memory view
because it shares the memory space of the main
program
 Parallel processing terminology

 Types of Synchronization:
 Barrier
 Usually implies that all tasks are involved
 Each task performs its work until it reaches the barrier. It then
stops, or "blocks"
 When the last task reaches the barrier
barrier, all tasks are
synchronized

 Lock / semaphore
 Can involve any number of tasks
 Typically used to serialize (protect) access to global data or a
section of code
 The first task to acquire the lock "sets" it - this task can then
safely (serially) access the protected data or code
 Parallel processing terminology
 Data
D P
Parallelism
ll li
 Most parallel execution
operates
p on a data set
 The data set is typically
organized as an array or multi-
dimensional matrix
 A set of tasks work collectively
on the same data structure
 Each task/thread works on a
different partition of the same
data structure
 Tasks perform the same
operation on their partition of
work, for example, “multiply
every array element by delta"
 The grain of computation
 Programs can be decomposed into:
 Processes or Threads
 Functions
 Kernels
 Loops
 Basic blocks
 Instructions

 CPUs are designed using pipelining

 Decomposing computation
 Programs can be decomposed into parallel
subproblems:
 Decomposing computation
 Single programs can be further
decomposed into parallel subproblems
using
i threads:
th d
 What is a thread?

 Process:
• An address space
p with 1 or more threads
executing within that address space, and
the required system resources for those
threads
• A program that is running
 Thread:
• A sequence of control within a process
• Shares the resources of the process
 Advantages and Drawbacks of Threads

 Advantages:
• The overhead for creating a thread is significantly
less than that for creating a process
• Multitasking, wherein one process serves multiple
clients
• Switching between threads requires the OS to do
much less work than switching between processes
– lightweight
li ht i ht
• Hardware can be designed to further reduce this
overhead
 Advantages and Drawbacks of Threads
 Drawbacks:
• Not as widely available on all platforms
• Writing multithreaded programs requires more
careful thought
• More difficult to debug than single threaded
programs
• For single processor/core machines, creating
several threads in a program may not necessarily
produce an increase in performance (the
overhead of thread management may dominate)
 POSIX Threads (pthreads
(pthreads))

 IEEE's POSIX Threads Model:

• Programming models for threads on a UNIX
platform
• pthreads are included in the international
standards ISO/IEC9945-1

 pthreads programming model:

• Creation of threads
• Managing thread execution
• Managing the shared resources of the process
 Pthreads – The basics: Main thread
• Initial thread created when main() (in C) or
PROGRAM (in Fortran) are invoked by the process
loader
oade

• Once in main(), the application has the ability to

create daughter threads

• If the main thread returns,, the process

p terminates
even if there are running threads in that process,
unless special precautions are taken

• To explicitly avoid terminating the entire process, use

pthread_exit()
 Pthreads – The basics
 Thread termination methods:
 Implicit termination:
 thread function execution is completed
 Explicit termination:
 calling pthread_exit() within the thread
 calling
g pt
pthread
ead_ca ce () to terminate other threads
cancel()

 For numerically intensive routines, it is suggested

that the application
pp calls p threads if there are p
available processors

 The program in C++ calls the pthread.h

pthread h header file

 Pthreads related statements are preceded by the

pthread_ prefix
fi (except
( t for
f semaphores)
h )
 Pthreads – [Link]
1. //
//****************************************************************
2. // This is a sample threaded program in C++. The main thread creates
3. // 4 daughter threads. Each child thread simply prints out a message
4. // before exiting. Notice that we have set the thread attributes to joinable and
5. // of system scope.
6. //****************************************************************
7. #include <iostream.h>
8. #include <stdio.h>
9. #include <pthread.h>
10.
11. #define NUM_THREADS 4
12.
13. void *thread_function( void *arg );
14.
15. int main(
( void )
16. {
17. int i, tmp;
18. int arg[NUM_THREADS] = {0,1,2,3};
19.
20. pthread t thread[NUM_THREADS];
pthread_t thread[NUM THREADS];
21. pthread_attr_t attr;
22.
23. // initialize and set the thread attributes
24. pthread_attr_init( &attr );
25
25. pthread attr setdetachstate( &attr
pthread_attr_setdetachstate( &attr, PTHREAD_CREATE_JOINABLE
PTHREAD CREATE JOINABLE );
26. pthread_attr_setscope( &attr, PTHREAD_SCOPE_SYSTEM );
27.
Pthreads – [Link]
28 // creating threads
29 for ( i=0; i<NUM_THREADS; i++ )
30 {
31 tmp = pthread_create( &thread[i], &attr, thread_function, (void
*)&arg[i] );
32
33 if ( tmp != 0 )
34 {
35 cout << "Creating thread " << i << " failed!" << endl;
36 return 1;
;
37 }
38 }
39
40 // joining threads
41 for ( i
i=0;
0; i<NUM_THREADS;
i<NUM THREADS; i++ )
42 {
43 tmp = pthread_join( thread[i], NULL );
44 if ( tmp != 0 )
45 {
46 cout << "Joining
Joining thread " << i << " failed!
failed!" << endl;
47 return 1;
48 }
49 }
50
51 return
t 0
0;
52 }
53
 Pthreads – [Link]
54 //***********************************************************
55 // This is the function each thread is going to run. It simply asks
56 // the thread to print out a message. Notice the pointer acrobatics.
57 //***********************************************************
58 void *thread_function( void *arg )
59 {
60 int id;
61
62 id = *((int *)arg);
63
64 printf( "Hello from thread %d!\n", id );
65 pthread exit( NULL );
pthread_exit(
66 }
 Discussion on [Link]
 How to compile:
• On our Redhat Linux system, use:
g++ -pthread
pthread [Link]
filename cpp –oo filename

 Creating a thread:
int pthread_create( pthread_t *thread, pthread_attr_t *attr,
void *(*thread_function)(void *), void *arg );

• First argument – pointer to the identifier of the created thread

• Second argument – thread attributes
• Third argument – pointer to the function the thread will execute
• Fourth argument
g – the argument
g of the executed function
(usually a struct)
• Returns 0 for success
 Discussion on [Link]
 Waiting for the threads to finish:
int pthread_join(pthread_t
pthread join(pthread t thread,
thread void **thread
**thread_return)
return)

• Main thread will wait for daughter thread thread to finish

• First argument – the thread to wait for
• Second argument – pointer to a pointer to the return
value from the thread
• Returns 0 for success
• Threads should always be joined; otherwise, a thread
might keep on running even when the main thread has
already terminated

• Compile
p and run the example
p
 Threads Programming Models
 Pipeline model – threads are run one after
the other

 Master-slave model – master (main) thread

doesn't do any work, it just waits for the slave
th d tto fi
threads finish
i h working
ki

 Equal-worker model – all threads do the

same work
 Thread Synchronization Mechanisms
 Mutual exclusion (mutex):
• Guards against multiple threads modifying the
same shared data simultaneouslyy

• Provides locking/unlocking critical code sections

where shared data is modified

• Each thread waits for the mutex to be unlocked

(by the thread who locked it) before performing the
code section
Thread Synchronization Mechanisms

 Basic Mutex Functions:

int pthread_mutex_init(pthread_mutex_t *mutex, const
pthread_mutexattr_t *mutexattr);
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_destroy(pthread_mutex_t *mutex);

• A new data type named pthread_mutex_t is

designated for mutexes
• A mutex
t isi lik
like a kkey (t
(to access th
the code
d section)
ti )
that is handed to only one thread at a time
• The attribute of a mutex can be controlled by
using
i th the pthread_mutex_init()function
f ti
• The lock/unlock functions work in tandem
Thread Synchronization Mechanisms
#i l d <pthread.h>
#include h d h
pthread_mutex_t my_mutex; // should be of global scope
...
int main()
{
int tmp;
...
// initialize the mutex
tmp = pthread_mutex_init(
pthread mutex init( &my
&my_mutex,
mutex, NULL );
...
// create threads
...
pthread_mutex_lock(
p ( &my
y_mutex );
do_something_private();
pthread_mutex_unlock( &my_mutex );
...
return 0;
}
 Whenever a thread reaches the lock/unlock block, it first
determines if the mutex is locked. If locked, it waits until it is
unlocked Otherwise
unlocked. Otherwise, it takes the mutex,
mutex locks the succeeding
code, then frees the mutex and unlocks the code when it's done.
Thread Synchronization Mechanisms
 Consider the code in the mutex example

 One
O thread
th d iincrementst the
th shared
h d variable
i bl
(shared_target) and the other decrements

 Illustrates many of the basics for managing

shared data

 Experiment with the number of threads and the

number of iterations

 What is the relationship between these parms?

Thread Synchronization Mechanisms

 Counting Semaphores:

• Permit a limited number of threads to execute a

section of the code

• Similar to mutexes

• Should include the semaphore.h header file

• Semaphore functions do not have pthread_

pthread
prefixes; instead, they have sem_ prefixes
Thread Synchronization Mechanisms
 Basic Semaphore Functions:
• Creating a semaphore:
int sem_init(sem_t *sem, int pshared, unsigned int
value);
 initializes a semaphore object pointed to by sem
 pshared is a sharing option; a value of 0 means the
semaphore is local to the calling process
ggives an initial value value to the semaphore
p
• Terminating a semaphore:
int sem_destroy(sem_t *sem);
 frees
f the
th resources allocated
ll t d tto th
the semaphore
h sem
 usually called after pthread_join()
 an error will occur if a semaphore is destroyed for
which a thread is waiting
Thread Synchronization Mechanisms
• Semaphore
S h control:
l
int sem_post(sem_t *sem);
int sem_wait(sem_t
sem wait(sem t *sem);
sem);

 sem_post atomically increases the value of a

semaphore
p by
y 1,, i.e.,, when 2 threads call
sem_post simultaneously, the semaphore's value
will also be increased by 2 (there are 2 atoms
calling)
 sem_wait atomically decreases the value of a
semaphore by 1; but always waits until the
semaphore has a non-zero value first
Thread Synchronization Mechanisms
#include <pthread.h>
#include <semaphore.h>
void *thread_function( void *arg );
...
sem_t semaphore; // also a global variable just like mutexes
...
int main()
{
int tmp;
...
// initialize the semaphore
tmp = sem_init( &semaphore, 0, 0 );
...
// create threads
pthread create( &thread[i], NULL, thread_function,
pthread_create( thread function, NULL );
...
while ( still_has_something_to_do() )
{
sem_post( &semaphore );
...
}
...
pthread_join( thread[i], NULL );
sem_destroy( &semaphore );
return 0;
}
Thread Synchronization Mechanisms
void *thread_function( void *arg )
{
sem_wait( &semaphore );
perform_task_when_sem_open();
...
pthread_exit( NULL );
}

• The main thread increments the semaphore's

count value in the while loop

• The threads wait until the semaphore's count

value is non-zero before performing
perform_task_when_sem_open()
f k h ()

• Daughter thread activities stop only when

pthread_join()is called
Thread Synchronization Mechanisms
 Look through the semaphore code provided

 The application performs a simple simulation of a

producer/consumer: producing and buying milk

 Experiment
E i t with
ith iincreasing
i ththe number
b off th
threads
d
Condition Variables

• Used for communicating information about

the state of shared data

• Can make the execution of sections of a

code by a thread depend on the state of a
data structure or another running thread

• Condition variables are used for signaling,

not for mutual exclusion; a mutex is
needed to synchronize access to shared
data
Another pthreads example

• Run the pthreads [Link] program

• Experiment with its performance

• Compile and run the serial pi program

(make sure to pass an input parameter –
an integer)
a tege )

• Now attempt to parallelize it with pthreads!

(homework)
(h k)
A parallel implementation of [Link]
#include <stdio.h>
#include <pthread.h>
int n, num_threads;
double d d, pi;
pthread_mutex_t reduction_mutex;
pthread_t *tid;
void *PIworker(void
PIworker(void *arg)
arg) { int i,
i myid;
double s, x, mypi; myid = *(int *)arg;
s = 0.0;
for (i=myid+1; i<=n; i+=num_threads)
{ x = (i-0.5)*d; s += 4.0/(1.0+x*x);
}
mypi = d*s;
pthread_mutex_lock(&reduction_mutex);
h d l k( d i )
pi += mypi;
pthread_mutex_unlock(&reduction_mutex);
A parallel implementation of [Link]
pthread exit(0);
pthread_exit(0);
}
main(int argc, char **argv) { int i; int *id; n =
atoi(argv[1]);
num_threads
h d = atoi(argv[2]);
i( [2])
d = 1.0/n;
pi = 0.0;
id = (
(int *)
) calloc(n,sizeof(int));
( , ( )); t
id = (pthread_t *) calloc(num_threads,
sizeof(pthread_t));
if(pthread_mutex_init(&reduction_mutex,NULL))
{ fprintf(stderr,
p ( , "Cannot init lock\n");
\ ); exit(0);
( ); };
for (i=0; i<num+_threads; i++)
{ id[i] = i;
if(pthread_create(&tid[i],NULL, PIworker,(void
*)&id[i]))
)&id[i])) { exit(1);
};
};
for (i=0; i<num_threads; i++)
pthread_join(tid[i],NULL);
th d j i (tid[i] NULL)
printf("pi=%.15f\n", pi); }
SIMD Execution
• Single Instruction Multiple Data [Flynn]
• Also referred to as vectorization
• Effectively used for over 35 years to exploit data
data-level
level
parallelism (CDC Star100 and ILLIAC-IV)
• Execute the same instruction on different data
• X86 extensions MMX
MMX, SSE,
SSE 3DNow
3DNow, AVX
• AltiVEC (PowerPC), Vis (SPARC)
SIMD Execution – Advantages

• Exploits rampant data parallelism

• Better code density
• Lower code decoding overhead
• Potentially better memory efficiency –
i li it d
implicit data
t llocality
lit
• Efficient for streaming and multimedia
applications
• Can effectively handle irregular data
patterns (e.g., swizzles)
SIMD Execution – Disadvantages

 Not all algorithms can be vectorized

 Gathering data into SIMD registers and scattering it to
the correct destination locations is tricky and can be
inefficient (swizzles start to address this issue)
 Specific instructions like rotations and three-operand
adds
dd are uncommon in i SIMD iinstruction
t ti sets t
 Instruction sets are architecture-specific: old processors
and non-x86 processors lack SSE entirely -
programmers mustt provide id non-vectorized
t i d
implementations (or different vectorized
implementations) for them
 The early MMX instruction set shared a register file with
the floating-point stack, which caused inefficiencies
when mixing floating-point and MMX code
 SIMD Execution – SSE

 Supported by most C/C++/Fortran

compilers

 On our Linux system, use the –msse

switch

 Using pi serial code, experiment with

using
g this switch

 Increase the number of loops to get timing

statistics
Comparison of CPU and GPU
Hardware Architectures

CPU: Cache heavy, GPU: ALU heavy,

focused on individual massively parallel,
thread performance throughput-oriented
 Traditional CPU/GPU Relationship
CPU
(host)
GPU w/
local DRAM
(device)
 A wide range of GPU applications
Film Protein folding
3D image analysis
Quantum chemistry
Adaptive radiation therapy Financial
Ray tracing
Acoustics GIS
Radar
Astronomy Holographics cinema
Reservoir simulation
Audio Intrusion detection
Robotic vision / AI
Automobile vision Machine learning
Robotic surgery
Bioinfomatics Mathematics research
Satellite data
Biological simulation Military analysis
Broadcast Mine planning Seismic imaging
Cellular automata Molecular dynamics Surgery simulation
Fluid dynamics MRI reconstruction Surveillance
Computer vision Multispectral imaging Ultrasound
Cryptography N-body simulation Video conferencing
CT reconstruction
t ti Network
Net ork processing Telescope
Data mining Neural network Video
Digital cinema / projections Oceanographic research Visualization
Electromagnetic simulation Optical inspection Wi l
Wireless
Equity trading Particle physics X-Ray
 GPU as a General Purpose
Computing Platform
Speedups are impressive and ever increasing!

Genetic Algorithm Real Time Elimination Lattice-Boltzmann Method Total Variation Modeling
of Undersampling Artifacts for Numerical Fluid Mechanics
2600 X 2300 X 1840 X 1000 X

Fast Total Variation for Monte Carlo Simulation Stochastic Differential K-Nearest Neighbor
Computer Vision Of Photon Migration Equations Search
1000 X 1000 X 675 X 470 X

Source: CUDA Zone at [Link]/cuda/

 NVIDIA
Streaming Processor Array
GT200
Grid of thread blocks architecture
TPC TPC TPC TPC TPC TPC TPC TPC TPC TPC

Multiple thread blocks

blocks,
many warps of threads
Texture Processor
Cluster Streaming Multiprocessor
SP SP • 240 shader cores
• 1.4B transistors
SM SP SP • Upp to 2GB onboard
SFU SFU memory
e Unit

SP SP • ~150GB/sec BW
• 1.06 SP TFLOPS
SP SP
• CUDA and OpenCL
p
Texture

SM
support
• Programmable
memory spaces
• Tesla S1070
SM provides 4 GPUs in a
Individual threads 1U unit
 AMD GPU Architecture

• 5-way VLIW Architecture

• 4 Stream Cores and 1 special
Stream Cores function Stream Core
Special
functions
1 32
32-bit
bit FP
• Separate
p Branch Unit
MAD
per clock • All 5 cores co-issue
• Scheduling across the cores is
done by the compiler
• Each core delivers a 32-bit result
per clock
4 32
32-bit
bit FP MAD per clock
• Thread processor writes 5 results
2 64-bit FP MUL or ADD per clock
per clock
1 64-bit FP MAD per clock
4 24-bit
24 bit Int MUL or ADD per clock
 AMD/ATI Radeon HD 5870

• Codename “Evergreen”
• 20 SIMD Engines
• 1600 SIMD cores
• L1/L2 memory architecture
• 153GB/sec memory bandwidth
• 2.72 TFLOPS SP
• Ope
OpenCL
C aand
d DirectX11
ect
• Provides for vectorized operation
AMD Memory System

 Distributed memory controller

 Optimized
O ti i d ffor latency
l t hiding
hidi
and memory access efficiency
 GDDR5 memory at 150GB/s
 Up to 272 billion 32-bit
fetches/second
 Up to 1 TB/sec L1 texture
fetch bandwidth
 Up to 435 GB/sec between
L1 & L2
 C for CUDA

 The language that started the GPGPU

excitement

 CUDA only runs on NVIDIA GPUs

 Highest performance programming

framework for NVIDIA GPUs ppresently
y

 Learning curve similar to threaded C

programming
 Large performance gains require mapping
program to specific underlying architecture
OpenCL – The future for many
many--core computing

 Open Compute Language

 A framework for writing programs that execute on
h t
heterogeneous systems
t
 Very similar to CUDA
 Presently runs on NVIDIA GPUs and AMD multi-core
CPUs/GPUs, Intel CPUs and some embedded CPUs
 Being developed by Khronos Group – a non-profit
 Modeled as four parts
• Platform Model
• Execution Model
• Memory Model
• Programming Model
 OpenCL Platform Model
 The model consists of a host connected to
one or more OpenCL devices
 A device is divided into one or more compute
units
 Compute units are divided into one or more
processing
i elements
l t
 OpenCL Execution Model
 2 main parts:
 Host programs execute on the host
 Kernels execute on one or more OpenCL
devices
 Each instance of a kernel is called a work-
item
 Work-items are organized as work-groups
 When a kernel is submitted
submitted, an index space
of work-groups and work-items is defined
 Work-items can identifyy themselves based on
their work-group ID and their local ID within
the work-group
 OpenCL Execution Model
 A context refers
f to the
h environment
i iin which
hi h
kernels execute
 Devices ((the elements p
performing
g the execution))
 Program objects (the program source that implements
the kernel)
 Kernels (OpenCL functions that run on OpenCL
devices)
 Memory objects (data that can be operated on by the
device)
 Command queues are used to coordinate execution of
the kernels on the devices
 Memory commands (data transfers)
 Synchronization

 Execution between host and device(s)

( ) is
asynchronous
 OpenCL Memory Model
 Multilevel memory exposed
to programmer
 Registers (per thread)
 Local memory
 Shared among g threads in a
single block
 On-chip, small
 As fast as registers
 Global memory
 Kernel inputs and outputs
 Off-chip,
Off hi llarge
 Uncached (use coalescing)
 OpenCL Programming Model
 Data parallel
 One-to-one mapping between work-items and
elements in a memory object
 Work-groups can be defined explicitly (like CUDA) or
implicitly (specify the number of work-items and
OpenCL creates the work-groups)
work groups)
 Task parallel
 Kernel is executed independent of an index space
 Other ways to express parallelism: enqueueing
multiple tasks, using device-specific vector types, etc.
 Synchronization
 Possible between items in a work-group
 Possible between commands in a context command
queue
Putting it all together…..
A Look at the Future for GPUs

 AMD Fusion
 CPU/GPU on a single
i l chip
hi
 Shared-memory model
 Reduces communication overhead

 NVIDIA Fermi
 ECC on device memory
 20X speedup on atomic sync operations
 Programmable caching
AMD Fusion – The Future for CPU/GPU
Computing

x86 CPU owns GPU Optimized for

the Software World Modern Workloads

 Windows, MacOS  Enormous parallel

and Linux franchises computing capacity
 Thousands of apps  Outstanding
 Established performance-per -
programming and watt-per-dollar
memory model  Very efficient
hardware threading
 Mature tool chain
 SIMD architecture well
 Extensive backward
matched to modern
compatibility for
workloads: video,
applications and OSs
audio, graphics
 High barrier to entry
PC with a Discrete GPU

15GB/sec
Memory

PCIe 12GB/sec

150GB/sec
Device
GPU Memory
PC with a Discrete GPU

20 GB/sec
Memory

20GB/sec

Fusion
GPU
PCIe 12GB/sec

150GB/sec
Device
Discrete Memory
GPU
Two New AMD Cores Tuned for
Target Markets

Mainstream
Performance &
“Bulldozer” Client and
Scalability
Server Markets

Flexibility,
“Bobcat” Low Power &
Low Cost Low Power Lower Cloud
Markets Cost Optimized
NVIDIA Fermi – Dedicated GPGPU device

 Fermi
 480 CUDA cores

 8X the current double

precision
i i FP
performance
 16 Concurrent kernels

 ECC support
 Summary

 Parallel computing is here to stay

 Multi-core
M lti CPU and
CPUs d many-core GPUs
GPU are
everywhere
 This class first provided background in
parallel thinking and computation
 pthreads parallel programming was covered
was introduced
 Our next class will focus on the CUDA
programming environment and NVIDIA
hardware