Parallel Compu⿿ng (BCS702) MODULE 2

MODULE -2
GPU Programming, Programming Hybrid
systems, MIMD systems, GPUs, Performance
2.1 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.

.IN
• So the code that runs on the host typically allocates and initializes storage on both the CPU
and the GPU.
• It will start the program on the GPU, and it is responsible for the output of the results of
the GPU program.
•
C
Thus GPU programming is really heterogeneous programming, since it involves
programming two different types of processors.
N
• The GPU itself will have one or more processors.
• Each of these processors is capable of running hundreds or thousands of threads.
SY

• In the systems we’ll be using, the processors share a large block of memory, but each
individual processor has a small block of much faster memory that can only be accessed
by threads running on that processor. These blocks of faster memory can be thought of as
a programmer- managed cache.
U

• 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.
• The threads in a SIMD group may not run in lockstep. That is, they may not all execute
VT

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. Suppose also that the threads
are executing the following code:
/ / Thread p r i v a te v a r i a b l e s
int rank_in_gp , my_x ;
...
if ( rank_in_gp < 16)
my_x += 1 ;
else
my_x —= 1 ;

Prof. Manjusha, Assistant Professor, CSE, SVIT. 1

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

Then the threads with rank < 16 will execute the first assignment, while the threads with rank >= 16
are idle. After the threads with rank < 16 are done, the roles will be reversed: the threads with rank < 16
will be idle, while the threads with rank >= 16 will execute the second assignment.

• Idling half the threads for two instructions isn’t a very efficient use of the available resources.
So it’s up to≥ the programmer to minimize branching, where the threads within a SIMD group
take different branches.
• Another issue in GPU programming that’s different from CPU programming is how the threads
are scheduled to execute.
• GPUs use a hardware scheduler 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.
• In the preceding example, before executing the test, we would want the variable
rank_in_gp stored in a register by each thread. So, to maximize use of the hardware, we
usually create a large number of SIMD groups. When this is the case, groups that aren’t ready

.IN
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.

2.2 Programming Hybrid systems

C
• It is possible to program systems such as clusters of multicore processors using a combination
N
of a shared-memory API on the nodes and a distributed-memory API for internode
communication.
SY

• 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. Rather, such systems are often programmed using a single, distributed-memory API
for both inter- and intra-node communication.
U

2.3 MIMD systems ( I/O)

VT

Input and output have mostly been avoided because parallel I/O is complex and beyond the scope of
this discussion, and most programs developed here involve minimal I/O that can be handled by standard C
functions printf, fprintf, scanf, and fscanf. However, even limited use of these functions
can be problematic, as C's standard I/O is designed for serial execution and doesn't define behaviour when
used by multiple processes or threads. When multiple threads share standard streams, their simultaneous
access leads to unpredictable results.
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.

Prof. Manjusha, Assistant Professor, CSE, SVIT. 2

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

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. For input,
the data read by each process/thread may be different on each run, even if the same input is used.
To partially address these issues, following assumptions are made 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

.IN
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.
C
2.4 GPUs ( I/O)
N
• In most cases, the host code in our GPU programs will carry out all I/O. Since we’ll only be
SY

running one process/thread on the host, the standard C I/O functions should behave as they do
in ordinary serial C programs.
• The exception to the rule that we use the host for I/O is that when we are debugging our GPU
code, we’ll want to be able to write to stdout and/or stderr.
U

• In the systems we use, each thread can write to stdout, and, as with MIMD programs, the
order of the output is nondeterministic.
• Also in the systems we use, no GPU thread has access to stderr, stdin, or secondary
VT

storage.

2.5 Performance
Main purpose in writing parallel programs is usually increased performance. In this section,
we’ll start by looking at the performance of homogeneous MIMD systems. So we’ll assume that all of
the cores have the same architecture (not case with GPU).

2.5.1 Speedup and e�ciency 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

Prof. Manjusha, Assistant Professor, CSE, SVIT. 3

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

Table 2.1 Speedups and efficiencies of a

parallel program.

p 1 2 4 8 16
S 1.0 1.9 3.6 6.5 10.8
E = S/p 1.0 0.95 0.90 0.81 0.68

of our parallel program is Tparallel T=serial/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.

For example, shared-memory programs will almost always have critical sections, which will require
that we use some mutual exclusion mechanism, such as a mutex. The calls to the mutex functions are
the overhead that’s not present in the serial program, and the use of the mutex forces the parallel program

.IN
to serialize execution of the critical section. Distributed-memory programs will almost always need to
transmit data across the network, which is usually much slower than local memory access. Furthermore,
it’s likely that the overheads will increase as we increase the number of processes or threads. For
example, more threads will probably mean more threads need to access a critical section, and more
C
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
N
SY

then linear speedup has S = p.

Furthermore, as p increases the parallel overhead increases. This is S/p will probably get smaller
and smaller as p increases. Table 2.2 shows an example of the changes in S and S/p as p increases.
U
VT

This value, S/p, is sometimes called the efficiency of the parallel program. If we substitute the
formula for S, we see that the efficiency is

Prof. Manjusha, Assistant Professor, CSE, SVIT. 4

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

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. That
is, the efficiency can be thought of as the fraction of the parallel run-time that’s spent, on average, by
each core working on solving the original problem. The remainder of the parallel run-time is the parallel
overhead. This can be seen by simply multiplying the efficiency and the parallel run-time:

For example, suppose we have Tserial = 24 ms, p =8, and Tparallel = 4 ms.

and, on average, each process/thread spends 3/4 · 4 = 3 ms on solving the original problem,
and 4−3=1 ms in parallel overhead.

.IN
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. C
Therefore if Toverhead denotes this parallel overhead, it’s often the case that
N
Tparallel = Tserial/p + Toverhead
As the Tparallel, S, and E depend on p, the number of processes or threads. Note that Tparallel, S, E, and Tserial
SY

all depend on the problem size. For example, if we halve and double the problem size of the program,
whose speedups are shown in Table 2.1, we get the speedups and efficiencies shown in Table 2.2. The
speedups are plotted in Fig.2.1 , and the efficiencies are plotted in Fig. 2.2.
U

We see that in this example, when we increase the problem size, the speedups and the efficiencies
VT

increase, while they decrease when we decrease the problem size.

Figure 2.1 : Speedups of parallel program on di�erent problem sizes.

Prof. Manjusha, Assistant Professor, CSE, SVIT. 5

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

Figure 2.2: Efficiencies of parallel program on different problem sizes

.IN
This behaviour is quite common, because in many parallel programs, as the problem size is
increased but the number of processes/threads is fixed, the parallel overhead grows much more slowly
than the time spent in solving the original problem.
C
2.5.2 Amdahl’s law
N
• Back in the 1960s, Gene Amdahl made an observation later known as Amdahl’s law.
• It says, roughly, that unless virtually all of a serial program is parallelized, the possible speedup
SY

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. If the serial run-time is Tserial = 20 seconds,
U

then the run-time of the parallelized part will be 0.9 × Tserial/p = 18/p and the run-⿿me of the
“unparallelized” part will be 0.1 ×Tserial = 2.
VT

The overall parallel run-⿿me will be

and the speed up will be

Now as p gets larger and larger, 0.9 × Tserial/p = 18/p gets closer and closer to 0, so the total
parallel run-time can’t be smaller than 0.1 × Tserial = 2. That is, the de nominator in S can’t be smaller
than 0.1 × Tserial = 2. The fraction S must therefore satisfy the inequality

Prof. Manjusha, Assistant Professor, CSE, SVIT. 6

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

This means 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/10, so we couldn’t get a speedup better than 10. Therefore if a fraction r
of our serial program is “inherently serial,” that is, cannot possibly be parallelized, then we can’t
possibly get a speedup better than 1/r. Thus even if r is quite small—say, 1/100—and we have a
system with thousands of cores, we can’t possibly get a speedup better than 100.
This is pretty intimidating. Should we give up and go home? Well, no. There are several reasons not to
be too worried by Amdahl’s law.
1. It doesn’t take into consideration the problem size. For many problems, as we increase the
problem size, the “inherently serial” fraction of the program decreases in size; a more
mathematical version of this statement is known as Gustafson’s law.
2. There are thousands of programs used by scientists and engineers that routinely obtain huge

.IN
speedups on large distributed-memory systems.
3. In many cases, obtaining a speedup of 5 or 10 is more than adequate, especially if the effort
involved in developing the parallel program wasn’t very large2.5.3 Scalability in MIMD
systems C
• 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
N
system (e.g., a system with fewer cores).
• However, in MIMD parallel program performance, scalability has a somewhat more formal
SY

definition. 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.
U

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
VT

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.

Prof. Manjusha, Assistant Professor, CSE, SVIT. 7

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

There are a couple of cases that have special names.

• 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.

2.5.4 Taking ῿mings of MIMD programs

How to find Tserial and Tparallel.

There are a lot of different approaches, and with parallel programs the details may depend on the API. However,
there are a few general observations we can make that may make things a little easier.

• 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.

.IN
Perhaps surprisingly, the way we take these two timings is usually different.

• For the first timing, we usually need very detailed information: How much time did the program spend
C
in this part of the program? How much time did it spend in that part?
• For the second, we usually report a single value. Right now we’ll talk about the second type of timing
N
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.
SY

For example, if we write a program that implements bubble sort, we’re probably only interested in the time
it takes to sort the keys, not the time it takes to read them in and print them out. So we probably can’t use
something like the Unix shell command time, which reports the time taken to run a program from start to finish.
U

Third, we’re usually not interested in “CPU time.” This is the time reported by the standard C function clock. It’s
the total time the program spends in code executed as part of the program. It would include the time for code
we’ve written; it would include the time we spend in library functions, such as pow or sin; and it would include
VT

the time the operating system spends in functions we call, such as printf and scanf. It would not include time
the program was idle, and this could be a problem.

Any article reporting the run-time of a parallel program, the reported time is usually “wall clock” time.
Thais is the time that has elapsed between the start and finish of execution of the code that the user is interested
in. Such source code must look something like this:

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

Prof. Manjusha, Assistant Professor, CSE, SVIT. 8

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

• OpenMP API for shared-memory programming has a function omp_get_wtime. Both functions
return wall clock time instead of CPU time.

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.

When we’re timing parallel programs, we need to be a little more careful about how the timings are taken. In
our example, the code that we want to time is probably being executed by multiple processes or threads, and our
original timing will result in the output of p elapsed times:

.IN
However, 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
C
clock on another node. We usually settle for a compromise that looks something like this:
N
SY
U
VT

Here, 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, but such a function usually can only
guarantee that all the processes/threads have started the call when the first process/thread returns. We then execute
the code as before, and each process/thread finds the time it took. 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.

We also need to be aware of the variability in timings. When we run a program several times, it’s extremely likely
that the elapsed time will be different for each run. This will be true, even if each time we run the program we use
the same input and the same systems. It might seem that the best way to deal with this would be to report either a
mean or a median run-time. However, it’s unlikely that some outside event could actually make our program run
faster than its best possible run-time. So instead of reporting the mean or median time, we usually report the
minimum time.

Prof. Manjusha, Assistant Professor, CSE, SVIT. 9

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

Running more than one thread per core can cause dramatic increases in the variability of timings. More
importantly, if we run more than one thread per core, the system will have to take extra time to schedule and
deschedule cores, and this will add to the overall run-time. Therefore we rarely run more than one thread per core.

Finally, as a practical matter, since our programs won’t be designed for high- performance I/O, we’ll usually not
include I/O in our reported run-times.

2.5.5 GPU Performance

• Since the cores on the GPU are fundamentally different from conven- tional CPUs, it doesn’t make
sense to talk about linear speedup of a GPU program relative to a serial CPU program.
• A GPU program is scalable if we can increase the size of the GPU and obtain speedups over the
performance of the program on a smaller GPU.
• If we run the inherently serial part of a GPU program on a conventional, serial processor, then Amdahl’s
law can be applied to GPU programs, and the resulting upper bound on the possible speedup will be the
same as the upper bound on the possible speedup for a MIMD program.

.IN
• That is, if a fraction r of the original serial program isn’t parallelized, and this fraction is run on a
conventional serial processor, then the best possible speedup of the program running on the GPU and
the serial processor will be less than 1/r.
• It’s likely that the “inherently serial” fraction will depend on the problem size, and if it gets smaller as
C
the problem size increases, the bound on the best possible speedup will increase.
• Also, many GPU programs obtain huge speedups, and, finally, a relatively small speedup may be
perfectly adequate.
N
The same basic ideas about timing that we discussed for MIMD programs also apply to GPU programs.
SY

• However, since a GPU program is ordinarily started and finished on a conventional CPU, as long as
we’re interested in the performance of the entirety of the program running on the GPU, we can usually
just use the timer on the CPU, starting it before the GPU part(s) of the program are started, and stopping
U

it after the GPU part(s) are done.

• There are more complicated scenarios—e.g., running a program on multiple CPU-GPU pairs—that
require more care, but we won’t be dealing with these types of programs.
VT

• If we only want to time a subset of the code running on the GPU, we’ll need to use a timer defined by
the API for the GPU.

2.6 Parallel program design

So we’ve got a serial program. How do we parallelize it? We know that in general we need to divide the work
among the processes/threads so that each process/thread gets roughly the same amount of work and any parallel
overhead is minimized. In most cases, we also need to arrange for the processes/threads to synchronize and
communicate. Unfortunately, there isn’t some mechanical process we can follow; if there were, we could write a
program that would convert any serial program into a parallel program, but, as we noted in Chapter 1, in spite of
a tremendous amount of work and some progress, this seems to be a problem that has no universal solution.
However, Ian Foster provides an outline of steps in his online book Designing and Building Parallel
Programs [21]:

1. Par��oning. Divide the computa⿿on to be performed and the data operated on by the computa⿿on
into small tasks. The focus here should be on iden⿿fying tasks that can be executed in parallel.
2. Communica�on. Determine what communica⿿on needs to be carried out among the tasks
iden⿿῿ed in the previous step.
3. Agglomera�on or aggrega�on. Combine tasks and communica⿿ons iden⿿῿ed in the ῿rst step into
larger tasks. For example, if task A must be executed before task B can be executed, it may make

Prof. Manjusha, Assistant Professor, CSE, SVIT. 10

Studied smart, not hard — thanks to [Link]

Parallel Compu⿿ng (BCS702) MODULE 2

sense to aggregate them into a single composite task.

4. Mapping. Assign the composite tasks iden⿿῿ed in the previous step to processes/threads. This
should be done so that communica⿿on is minimized, and each process/thread gets roughly the
same amount of work.
This is some⿿mes called Foster’s methodology.

.IN
C
N
SY
U
VT

Prof. Manjusha, Assistant Professor, CSE, SVIT. 11

Studied smart, not hard — thanks to [Link]