GPU programming, Programming hybrid

systems, MIMD systems, Performance

Module 2
GPU programming
• GPUs are usually not “standalone” processors. They don’t ordinarily
run an operating system and system services, such as direct access to
secondary storage.

• So programming a GPU also involves writing code for the CPU “host”
system, which runs on an ordinary CPU.

• The memory for the CPU host and the GPU memory are usually
separate. So the code that runs on the host typically allocates and
initializes storage on both the CPU and the GPU.

• CPU will start the program on the GPU, and it is responsible for the
output of the results of the GPU program.

• Thus GPU programming is really heterogeneous programming, since

it involves programming two different types of processors.
• The GPU itself will have one or more processors. Each of these
processors is capable of running hundreds or thousands of threads.

• The processors share a large block of memory (VRAM or portion of

DRAM), but each individual processor has a small block of much
faster memory that can only be accessed by threads running on that
processor.

• The threads running on a processor are typically divided into groups:

the threads within a group use the SIMD model, and two threads in
different groups can run independently (MIMD).

• The threads in a SIMD group may not run in lockstep. That is, they
may not all execute the same instruction at the same time.
• However, no thread in the group will execute the next instruction
until all the threads in the group have completed executing the
current instruction.

• If the threads in a group are executing a branch, it may be necessary

to idle some of the threads.

• For example, suppose there are 32 threads in a SIMD group, and each
thread has a private variable rank_in_gp that ranges from 0 to 31.
• Another issue in GPU programming that’s different from CPU
programming is how the threads are scheduled to execute.

• GPUs use a hardware scheduler (unlike CPUs, which use software to

schedule threads and processes), and this hardware scheduler uses
very little overhead.

• However, the scheduler will choose to execute an instruction when all

the threads in the SIMD group are ready.

• Groups that aren’t ready to execute (e.g., they’re waiting for data
from memory, or waiting for the completion of a previous instruction)
can be idled, and the scheduler can choose a SIMD group that is
ready.
Programming hybrid systems

• Before moving on, we should note that it is possible to program

systems such as clusters of multicore processors using a combination
of a shared-memory API on the nodes and a distributed-memory API
for internode communication.

• However, this is usually only done for programs that require the
highest possible levels of performance, since the complexity of this
“hybrid” API makes program development much more difficult.
• Input and output
MIMD systems :

• We’ve generally avoided the issue of input and output. There are a
couple of reasons.

• First and foremost, parallel I/O, in which multiple cores access

multiple disks or other devices.

• Second, the vast majority of the programs we’ll develop do very little
in the way of I/O.

• The amount of data they read and write is quite small and easily
managed by the standard C I/O functions printf, fprintf, scanf, and
fscanf.
• However, even the limited use we make of these functions can
potentially cause some problems.

• Since these functions are part of standard C, which is a serial

language, the standard says nothing about what happens when
they’re called by different processes.

• On the other hand, threads that are forked by a single process do

share stdin, stdout, and stderr.

• However, as we’ve seen, when multiple threads attempt to access

one of these, the outcome is nondeterministic, and it’s impossible to
predict what will happen.
• When we call printf from multiple processes/threads, we, as
developers, usually want the output to appear on the console of a
single system, the system on which we started the program.

• However, with processes, there is no guarantee, and we need to be

aware that it is possible for a system to do something else:

• for example, only one process has access to stdout or stderr, or even
no processes have access to stdout or stderr.

• What should happen with calls to scanf when we’re running multiple
processes/threads is a little less obvious.

• Should the input be divided among the processes/threads? Or should

only a single process/thread be allowed to call scanf?
• The vast majority of systems allow at least one process to call
scanf—usually process 0—while most allow multiple threads to call
scanf. Once again, there are some systems that don’t allow any
processes to call scanf.

• When multiple processes/threads can access stdout, stderr, or stdin,

as you might guess, the distribution of the input and the sequence of
the output are usually nondeterministic.

• For output, the data will probably appear in a different order each
time the program is run, or, even worse, the output of one
process/thread may be broken up by the output of another
process/thread.

• To partially address these issues, we’ll be making these assumptions

and following these rules when our parallel programs need to do I/O:
• In distributed-memory programs, only process 0 will access stdin. In
shared memory programs, only the master thread or thread 0 will
access stdin.

• In both distributed-memory and shared-memory programs, all the

processes/threads can access stdout and stderr.

• However, because of the nondeterministic order of output to stdout,

in most cases only a single process/thread will be used for all output
to stdout.

• Only a single process/thread will attempt to access any single file

other than stdin, stdout, or stderr. So, for example, each
process/thread can open its own, private file for reading or writing,
but no two processes/threads will open the same file.

• Debug output should always include the rank or ID of the

process/thread that’s generating the output.
Performance
• Of course our main purpose in writing parallel programs is usually
increased performance. So what can we expect? And how can we
evaluate our programs? In this section, we’ll start by looking at the
performance of homogeneous MIMD systems.

• Speedup and efficiency in MIMD systems:

• Usually the best our parallel program can do is to divide the work
equally among the cores while at the same time introducing no
additional work for the cores.

• If we succeed in doing this, and we run our program with p cores, one
thread or process on each core, then our parallel program will run p
times faster than the serial program runs on a single core of the same
design.
• If we call the serial run-time Tserial and our parallel run-time Tparallel,
then it’s usually the case that the best possible run-time of our
parallel program is
Tparallel = Tserial/p

• When this happens, we say that our parallel program has linear
speedup.

• In practice, we usually don’t get perfect linear speedup, because the

use of multiple processes/threads almost invariably introduces some
overhead (mutex in shared memory and data communication in
distributed).

• it’s likely that the overheads will increase as we increase the number
of processes or threads. More threads need to access a critical
section, and more processes will probably mean more data needs to
be transmitted across the network.
So if we define the speedup of a parallel program to be

then linear speedup has S = p.

• Furthermore, since as p increases we expect the parallel overhead to

increase, due to which efficiency (E) of the system reduces.
• If the serial run-time has been taken on the same type of core that
the parallel system is using, we can think of efficiency as the average
utilization of the parallel cores on solving the problem.

• Many parallel programs are developed by explicitly dividing the work

of the serial program among the processes/threads and adding in the
necessary “parallel over head,” such as mutual exclusion or
communication.
• Amdahl’s law: It says, roughly, that unless virtually all of a serial
program is parallelized, the possible speedup is going to be very
limited—regardless of the number of cores available.

• Suppose, for example, that we’re able to parallelize 90% of a serial

program. Furthermore, suppose that the parallelization is “perfect,”
that is, regardless of the number of cores p we use, the speedup of
this part of the program will be p (S=p).

• If the serial run-time is Tserial = 20 seconds, then the run-time of the

parallelized part will be 0.9 × Tserial/p = 18/p and the run-time of the
“unparallelized” part will be 0.1 ×Tserial = 2. The overall parallel
run-time will be.
• That is, S ≤ 10. This is saying that even though we’ve done a perfect
job in parallelizing 90% of the program, and even if we have, say,
1000 cores, we’ll never get a speedup better than 10.

• More generally, if a fraction r of our serial program remains

unparallelized, then Amdahl’s law says we can’t get a speedup better
than 1/r. In our example, r =1−0.9 =1/0.1, so we couldn’t get a
speedup better than 10.
Scalability in MIMD systems:-

• A program is scalable if, by increasing the power of the system it’s run
on (e.g., increasing the number of cores), we can obtain speedups
over the program when it’s run on a less powerful system (e.g., a
system with fewer cores).

• In discussions of MIMD parallel program performance, Suppose we

run a parallel program with a fixed number of processes/threads and
a fixed input size, and we obtain an efficiency E.

• Suppose we now increase the number of processes/threads that are

used by the program. If we can find a corresponding rate of increase
in the problem size so that the program always has efficiency E, then
the program is scalable.
• As an example, suppose that Tserial = n, where the units of Tserial are in
microseconds, and n is also the problem size. Also suppose that
Tparallel = n/p +1. Then

• To see if the program is scalable, we increase the number of

processes/threads by a factor of k, and we want to find the factor x
that we need to increase the problem size by, so that E is unchanged.

• The number of processes/threads will be kp; the problem size will be

xn, and we want to solve the following equation for x:
• Well, if x = k, there will be a common factor of k in the denominator
xn+ kp = kn+kp =k(n+p),and we can reduce the fraction to get

• In other words, if we increase the problem size at the same rate that
we increase the number of processes/threads, then the efficiency will
be unchanged, and our program is scalable.

• If, when we increase the number of processes/threads, we can keep

the efficiency fixed without increasing the problem size, the program
is said to be strongly scalable.

• If we can keep the efficiency fixed by increasing the problem size at

the same rate as we increase the number of processes/threads, then
the program is said to be weakly scalable.
Taking timings of MIMD programs

• You may have been wondering how we find Tserial and Tparallel. There
are a lot of different approaches, and with parallel programs the
details may depend on the API.

• The first thing to note is that there are at least two different reasons
for taking timings. During program development, we may take
timings to determine if the program is behaving as we intend.

• On the other hand, once we’ve completed development of the

program, we’re often interested in determining how good its
performance is.

• Second, we’re usually not interested in the time that elapses between
the program’s start and the program’s finish. We’re usually interested
only in some part of the program.
• Third, we’re usually not interested in “CPU time.” This is the time
reported by the standard C function clock.

• Thus when you see an article reporting the run-time of a parallel

program, the reported time is usually “wall clock” time. That is, the
authors of the article report the time that has elapsed between the
start and finish of execution of the code that the user is interested in.

• The function Get_current_time() is a hypothetical function that’s

supposed to return the number of seconds that have elapsed since
some fixed time in the past.
• The actual function that is used will depend on the API. For example,
MPI has a function MPI_Wtime that could be used here, and the
OpenMP API for shared-memory programming has a function
omp_get_wtime.

• There may be an issue with the resolution of the timer function. The
resolution is the unit of measurement on the timer. It’s the duration
of the shortest event that can have a nonzero time.

• Some timer functions have resolutions in milliseconds (10−3 seconds),

and when instructions can take times that are less than a nanosecond
(10−9 seconds), a program may have to execute millions of
instructions before the timer reports a nonzero time.

• Many APIs provide a function that reports the resolution of the timer.
• What we’re usually interested in is a single time: the time that has
elapsed from when the first process/thread began execution of the
code to the time the last process/thread finished execution of the
code.

• We often can’t obtain this exactly, since there may not be any
correspondence between the clock on one node and the clock on
another node. We usually settle for a compromise that looks
something like this:
• We first execute a barrier function that approximately synchronizes
all of the processes/threads. We would like for all the
processes/threads to return from the call simultaneously, Then all the
processes/threads call a global maximum function, which returns the
largest of the elapsed times, and process/thread 0 prints it out.
GPU performance
In MIMD (Multiple Instruction, Multiple Data) parallel computing, we usually
measure performance by comparing:

🡪The time of the parallel program with

🡪The time of the serial program running on the same kind of CPU core.

For GPUs, this comparison is not very meaningful because GPU cores are very
different from CPU cores:

• CPU cores are powerful, general-purpose, and designed for serial work.
• GPU cores are lightweight, specialized, and designed for massive parallelism. So
efficiency and linear speedup comparisons don’t make sense in the usual way.

Scalability on GPUs : Formal scalability definitions (like in MIMD) don’t directly apply.
Instead, informal scalability is used: A GPU program is called scalable if making the
GPU bigger (more cores, more memory, etc.) gives proportionally better performance.
• Amdahl’s law says that if a fraction r of a program is inherently serial, the
maximum possible speedup is limited to 1/r.

• This applies to GPUs too, if the serial part of the program runs on the CPU and the
parallel part runs on the GPU.

• Example:
• If 10% (r = 0.1) of a program is serial, the maximum possible speedup is 10×, no
matter how powerful the GPU is.

• Most GPU programs are launched and controlled by a CPU. If we want the overall
runtime, we can simply:

🡪Start a CPU timer before calling the GPU kernel(s),

🡪Stop it after the GPU finishes.

• If we only want to time just the GPU computation, we need special GPU timers
(provided by CUDA, OpenCL, etc.).