Source code for all the examples in this book can be downloaded from http://booksite.mkp.com/9780123884268. A wiki (a website collaboratively developed by a community of users) is available to share information, make comments, and find teaching material; it can be reached at any of the following aliases on gpucomputing.net:

Programming a sequential processor requires writing a program that specifies each of the tasks needed to compute some result. See Example 1.1, “seqSerial.cpp, a sequential C++ program”:

Example 1.1 performs five tasks:

Notice that the processor runs each task consecutively one after the other. Inside of tasks 2–4, the processor iterates through the loop starting with the first index. Once all the tasks have finished, the program exits. This is an example of a single thread of execution, which is illustrated in Figure 1.1 for task 2 as a single thread fills the first three elements of array a.

This program can be compiled and executed with the following commands:

In all cases, the program will print “Test succeeded!”

For comparison, let's create and run our first CUDA program seqCuda.cu, in C++. (Note: CUDA supports both C and C++ programs. For simplicity, the following example was written in C++ using the Thrust data-parallel API as will be discussed in greater depth in this chapter.) CUDA programs utilize the file extension suffix “.cu” to indicate CUDA source code. See Example 1.5, “A Massively Parallel CUDA Code Using the Thrust API”:

Example 1.5 is compiled with the NVIDIA nvcc compiler under Windows, Linux, and MacOS. If nvcc is not available on your system, download and install the free CUDA tools, driver, and SDK (Software Development Kit) from the NVIDIA CUDA Zone (http://developer.nvidia.com). See Example 1.6, “Compiling and Running the Example”:

Again, running the program will print “Test succeeded!”

Congratulations: you just created a CUDA application that uses 50,000 software threads of execution and ran it on a GPU! (The actual number of threads that run concurrently on the hardware depends on the capabilities of the GPGPU in your system.)

Aside from a few calls to the CUDA Thrust API (prefaced by thrust:: in this example), the CUDA code looks almost identical to the sequential C++ code. The highlighted lines in the example perform parallel operations.

Unlike the single-threaded execution illustrated in Figure 1.1, the code in Example 1.5 utilizes many threads to perform a large number of concurrent operations as is illustrated in Figure 1.2 for task 2 when filling array a.

CUDA offers several APIs to use when programming. They are from highest to lowest level:

Regardless of the API or mix of APIs used in an application, CUDA can be called from other high-level languages such as Python, Java, FORTRAN, and many others. The calling conventions and details necessary to correctly link vary with each language.

Which API to use depends on the amount of control the developer wishes to exert over the GPU. Higher-level APIs like the C++ Thrust API are convenient, as they do more for the programmer, but they also make some decisions on behalf of the programmer. In general, Thrust has been shown to deliver high computational performance, generality, and convenience. It also makes code development quicker and can produce easier to read source code that many will argue is more maintainable. Without modification, programs written in Thrust will most certainly maintain or show improved performance as Thrust matures in future releases. Many Thrust methods like reduction perform significant work, which gives the Thrust API developers much freedom to incorporate features in the latest hardware that can improve performance. Thrust is an example of a well-designed API that is simple yet general and that has the ability to be adapted to improve performance as the technology evolves.

A disadvantage of a high-level API like Thrust is that it can isolate the developer from the hardware and expose only a subset of the hardware capabilities. In some circumstances, the C++ interface can become too cumbersome or verbose. Scientific programmers in particular may feel that the clarity of simple loop structures can get lost in the C++ syntax.

Use a high-level interface first and choose to drop down to a lower-level API when you think the additional programming effort will deliver greater performance or to make use of some lower-level capability needed to better support your application. The CUDA runtime in particular was designed to give the developer access to all the programmable features of the GPGPU with a few simple yet elegant and powerful syntactic additions to the C-language. As a result, CUDA runtime code can sometimes be the cleanest and easiest API to read; plus, it can be extremely efficient. An important aspect of the lowest-level driver interface is that it can provide very precise control over both queuing and data transfers.

Expect code size to increase when using the lower-level interfaces, as the developer must make more API calls and/or specify more parameters for each call. In addition, the developer needs to check for runtime errors and version incompatibilities. In many cases when using low-level APIs, it is not unusual for more lines of the application code to be focused on the details of the API interface than on the actual work of the task.

Happily, modern CUDA developers are not restricted to use just a single API in an application, which was not the case prior to the CUDA 3.2 release in 2010. Modern versions of CUDA allow developers to use any of the three APIs in their applications whenever they choose. Thus, an initial code can be written in a high-level API such as Thrust and then refactored to use some special characteristic of the runtime or driver API.

Let's use this ability to mix various levels of API calls to highlight and make more explicit the parallel nature of the sequential fill task (task 2) from our previous examples. Example 1.7, “Using the CUDA Runtime to Fill an Array with Sequential Integers,” also gives us a chance to introduce the CUDA runtime API:

The modified sections of the code are in bold. To minimize changes to the structure of main(), the call to thrust::sequence() is replaced by a call to a routine fill(), which is written using the runtime API. Because array a was allocated with thrust::device_vector<>(), a call to thrust::raw_pointer_cast() is required to get the actual location of the data on the GPU. The fill() subroutine uses a C-language calling convention (e.g., passing an int* and the length of the vector) to emphasize that CUDA is accessible using both C and C++. Astute readers will note that a better C++ programming practice would be to pass a reference to the Thrust device vector for a number of reasons, including: better type checking, as fill() could mistakenly be passed a pointer to an array in host memory; the number of elements in the vector a can be safely determined with a.size() to prevent the parameter n from being incorrectly specified; and a number of other reasons.

Before discussing the runtime version of the fill() subroutine, it is important to understand some basic CUDA concepts:

A kernel should utilize many threads to perform the work defined in the kernel source code. This utilization is called thread-level parallelism, which is different than instruction-level parallelism, where parallelization occurs over processor instructions. Figure 1.2 illustrates the use of many threads in a parallel fill as opposed to the single-threaded fill operation illustrated in Figure 1.1.

An execution configuration defines both the number of threads that will run the kernel plus their arrangement in a 1D, 2D, or 3D computational grid. An execution configuration encloses the configuration information between triple angle brackets “<<<” and “>>>” that follow after the name of the kernel and before the parameter list enclosed between the parentheses. Aside from the execution configuration, queuing a kernel looks very similar to a subroutine call. Example 1.7 demonstrates this syntax with the call to fillKernel() in subroutine fill().

You now have the basic concepts needed to understand our first kernel.

From the programmer's point of view, execution starts on the host processor in main() of Example 1.7. The constant integer N is initialized and the Thrust method device_vector<int> is used to allocate N integers on the GPGPU device. Execution then proceeds sequentially to the fill() subroutine. A simple calculation is performed to define the number of blocks, nBlocks, based on the 512 threads per block defined by nThreadsPerBlock. The idea is to provide enough threads at a granularity of nThreadsPerBlock to dedicate one thread to each location in the integer array d_a. By convention, device variables are frequently noted by a preceding “d_” before the variable name and host variables are denoted with an “h_” before the variable name.

The CUDA kernel, fillKernel(), is then queued for execution on the GPGPU using the nBlocks and nThreadsPerBlock execution configuration. Both d_a and n are passed as parameters to the kernel. Host execution then proceeds to the return from the fill() subroutine. Note that fillKernel() must be preceded by the __global__ declaration specifier or a compilation error will occur.

At this point, two things are now happening:

Once fillKernel() starts running on the GPU, each thread first calculates its particular thread ID (called tid in the code) based on the grid defined by the programmer. This example uses a simple 1D grid, so tid is calculated using three constant variables that are specific to each kernel and defined by the programmer via the execution configuration:

The value of tid is then checked to see if it is less than n, as there might be more threads than elements in the a array. If tid contains a valid index into the a array, then the element at index tid is set to the value of tid. If not, the thread waits at the end of the kernel until all the threads complete. This example was chosen to make it easy to see how the grid locations are converted into array indices.

After all the threads finish, fillKernel() completes and returns control to the device driver so that it can start the next queued task. In this example, the GPU computes the reduction (the code of which is surprisingly complicated, as discussed in Chapter 6), and the sum is returned to the host so that the application can finish sequentially processing tasks 4 and 5.

From the preceding discussion, we can see that a CUDA kernel can be thought of in simple terms as a parallel form of the code snippet in Example 1.9, “A Sequential Illustration of a Parallel CUDA Call”:

Though Thrust relies on the runtime API, careful use of C++ templates allows a C++ functor (or function object, which is a C++ object that can be called as if it were a function) to be translated into a runtime kernel. It also defines the execution configuration and creates a kernel call for the programmer. This explains why Example 1.5, which was written entirely in Thrust, does not require specification of an execution configuration or any of the other details required by the runtime API.

Observation has shown that there are three general rules to creating high-performance GPGPU programs:

These rules make sense, given the bandwidth and latency limitations of the PCIe bus and GPGPU memory system as discussed in the following subsections.

Big-O notation is a convenient way to describe how the size of the problem affects the consumption by an algorithm of some resource such as processor time or memory as a function of its input. In this way, computer scientists can describe the worst case (or, when specified, the average case behavior) as a function to compare algorithms regardless of architecture or clock rate. Some common growth rates are:

There are many excellent texts on algorithm analysis that provide a more precise and comprehensive description of big-O notation. One popular text is Introduction to Algorithms (by Cormen, Leiserson, Rivest, and Stein; The MIT Press, 2009). There are also numerous resources on the Internet that discuss and teach big-O notation and algorithm analysis.

Most computationally oriented scientists and programmers are familiar with the BLAS (the Basic Linear Algebra Subprograms) library. BLAS is the de facto programming interface for basic linear algebra. NVIDIA provides a GPGPU version of BLAS with their CUBLAS library. In fact, GPGPU computing is creating a resurgence of interest in new high-performance math libraries, such as the MAGMA project at the University of Tennessee Innovative Computing Laboratory (http://icl.cs.utk.edu/magma/). MAGMA in particular utilizes both the host and a GPU device to attain high performance on matrix operations. It is available for free download.

BLAS is structured according to three different levels with increasing data and runtime requirements:

Table 1.2 illustrates the amount of work that is performed by each BLAS level, assuming that N floating-point values are transferred from the host to the GPU. It does not take into account the time required to transfer the data back to the GPU.

Table 1.2 tells us that level-3 BLAS operations should run efficiently on graphics processors because they perform O(N) work for every floating-point value transferred to the GPU. The same work-per-datum analysis applies to non-BLAS-related computational problems as well.

To illustrate the cost of a level-1 BLAS operation, consider the overhead involved in moving data across the PCIe bus to calculate cublasScal() on the GPU and then return the vector to the host. The BLAS Sscal() method scales a vector by a constant value. CUBLAS includes a thunking interface for FORTRAN compatibility. It works by transferring data from the host to the GPU, performing the calculation, and then transferring the data back to the host from the GPU. Thunking is inefficient, as it requires moving 4N bytes of data (where N is the number of floats in the vector) twice across the PCIe bus to perform N multiplications, as shown in Example 1.10. The best possible performance would be the transfer bandwidth divided by 8 (to account for two transfers of 4N bytes of data each way), as the time to perform the multiplication would be tiny compared to the data transfers. Such an application might achieve 1 Gflop (1 billion floating-point operations per second) floating-point performance assuming an 8-GB/s transfer rate between the host and GPU. ¹ Modest laptop processors and even some cell phones can exceed this calculation rate.

This analysis applies to all programs, not just level-1 and level-2 BLAS calculations. Getting good performance requires keeping as much data as possible on the GPU. After that, attaining high performance requires performing as many calculations per datum like the level-3 BLAS operations. Creating a pipeline of many lower arithmetic density computations can help, but this will only increase performance when each operation can keep the GPU busy long enough to overcome the kernel startup latency. Alternatively, it is possible to increase performance—sometime significantly—by combining multiple low-density operations like BLAS level-2 and level-2 operation into a single functor or kernel.

Amdahl's law is named after computer architect Gene Amdahl. It is not really a law but rather an approximation that models the ideal speedup that can happen when serial programs are modified to run in parallel. For this approximation to be valid, it is necessary for the problem size to remain the same when parallelized. In other words, assume that a serial program is modified to run in parallel. Further, assume that the amount of work performed by the program does not change significantly in the parallel version of the code, which is not always true. Obviously, those portions of the application that do not parallelize will not run any faster, and the parallel sections can run much, much faster depending on the hardware capabilities. Thus, the expected speedup of the parallel code over the serial code when using n processors is dictated by the proportion of a program that can be made parallel, P, and the portion of that cannot be parallelized, (1 − P). This relationship is shown in Equation 1.1, “Amdahl's law”.

Amdahl's law tells us that inventive CUDA developers have two concerns in parallelizing an application:

Part of the beauty of CUDA lies in the natural way it encapsulates the parallelism of a program inside computational kernels. Applications that run well on GPGPU hardware tend to have a few computationally intensive sections of the code (e.g., hotspots) that consume most of the runtime. According to Amdahl's law, these are programs with kernels that can deliver good parallel speedups (P >> 1 − P).

Observation has also shown that refactoring an application to use CUDA also tends to speed up performance on moderately parallel hardware such as multicore processors because CUDA allows developers to better see parallelism so that they can restructure the code to reduce the time spent in the serial (1 − P) sections. Of course, this assumes observation that the overhead consumed in transferring data to and from the GPGPU does not significantly affect application runtime.

The examples in this chapter have thus far demonstrated data parallelism or loop-level parallelism that parallelized data operations inside the for loops. Task parallelism is another form of parallelization that reduces the (1 − P) serial time by having multiple tasks executing concurrently. CUDA naturally supports task parallelism by running concurrent tasks on the host and GPU. As will be discussed in Chapter 7, CUDA provides other ways to exploit task parallelism within a GPU or across multiple GPUs.

Even the simple GPU examples, like Example 1.5 and Example 1.7, can be modified to demonstrate task parallelism. These examples performed the following tasks:

The representative timeline in Figure 1.4 shows that the previous examples do not take advantage of the asynchronous kernel execution when task 2 is queued to run on the GPU.

However, there is no reason why task 4 cannot be started after task 2 queues the kernel to run on the GPU. In other words, there is no dependency that forces task 4 to run after any other task, except that it must run before the check for correctness in task 5. In other words, task 5 depends on the results from task 4. Similarly, task 2 must run sometime after task 1, which allocates the array on the GPU.

Switching tasks 3 and 4 allows both the host and GPU to run in parallel, as shown in Figure 1.5, which demonstrates that it is possible to leverage CUDA asynchronous kernel execution to exploit both task and data parallelism in even this simple example. The benefit is a further reduction in application runtime.

The following example demonstrates a hybrid application that application runs simultaneously on both the CPU and GPU. Modern multicore processors are also parallel hardware that supports both data parallel and task parallel execution. OpenMP (Open Multi-Processing) is an easy way to utilize multithreaded execution on the host processor. The NVIDIA nvcc compiler supports OpenMP. Though this book is not about the OpenMP API, CUDA programmers need to know that they can exploit this host processor parallelism as well as the massive parallelism of the GPGPU. After all, the goal is to deliver the fastest application performance. It is also important to be fair when making benchmark comparisons between CPUs and GPUs by optimizing the application to achieve the highest performance on both systems to make the comparison as fair as possible.

Example 1.11, “An Asynchronous CPU/GPU Source Code” is the source code that switches the order of execution between task 3 and 4. The OpenMP parallel for loop pragma was used in task 4 to exploit data parallelism on the host processor:

To compile with OpenMP, add “-Xcompiler -fopenmp” to the nvcc command-line argument as shown in Example 1.12 to compile Example 1.11. Because we are timing the results, the “−O3” optimization flag was also utilized.

The output from seqAsync (Example 1.13, “Results Showing a Successful Test”) shows that the sum is correctly calculated as it passes the golden test:

As always in programming, the most important metric for success is that the application produces the correct output. Regression testing is a critical part of this evaluation process that is unfortunately left out of most computer science books. Regression tests act as sanity checks that allow the programmer to use the computer to detect if some error has been introduced into the code. The computer is impartial and does not get tired. For these reasons, small amounts of code should be written and tested to ensure everything is in a known working state. Additional code can then be added along with more regression tests. This greatly simplifies debugging efforts as the errors generally occur in the smaller amounts of new code. The alternative is to write a large amount of code and hope that it will work. If there is an error, it is challenging to trace through many lines of code to find one or more problems. Sometimes you can get lucky with the latter approach. If you try it, track your time to see if there really was a savings over taking the time to use regression testing and incremental development.

The examples in this chapter use a simple form of regression test, sometimes called a golden test or smoke test, which utilizes an alternative method to double-check the parallel calculation of the sum of the integers. Such simple tests work well for exact calculations, but become more challenging to interpret when using floating-point arithmetic due to the numerical errors introduced into a calculation when using floating-point. As GPGPU technology can perform several trillion floating-point operations per second, numerical errors can build up quickly. Still, using a computer to double-check the results beats staring at endless lines of numbers. For complex programs and algorithms, the regression test suite can take as much time to plan, be as complex to implement, and require more lines of code than the application code itself!

While hard to justify to management, professors or to you (especially when working against a tight deadline), consider the cost of delivering an application that does not perform correctly. For example, the second startup I co-founded delivered an artificial learning system that facilitated the search for candidate drug leads using some of the technology discussed later in this book. The most difficult question our startup team had to answer was posed by the research executive committee of a major investor. That question was “how do we know that what you are doing on the computer reflects what really happens in the test tube?” The implied question was, “how do we know that you aren't playing some expensive computer game with our money?” The solution was to perform a double-blind test showing that our technology could predict the chemical activity of relevant compounds in real-world experiments using only on a very small set of measurements and no knowledge of the correct result. In other words, our team utilized a form of sanity checking to demonstrate the efficacy of our model and software. Without such a reality check, it likely that the company would not have received funding.

A challenge with regression testing is that some errors can still silently pass through the test suite and make it to the application that the end-user sees. For example, Andy Regan at ICHEC (the Irish Center for High-End Computing) pointed out that increasing the value of N in the examples in this chapter can cause the sum to become so large that it cannot be contained in an integer. Some systems might catch the error and some systems will miss the error.

Given that GPUs can perform a trillion arithmetic operations per second, it is important that CUDA programmers understand how quickly numerical errors can accumulate or computed values overflow their capacity. A quick introduction to this topic is my Scientific Computing article “Numerical Precision: How Much Is Enough?” (Farber, 2009), which is freely available on the Internet.

Thrust provides the ability to perform a reduction where smaller data types are converted into a larger data type, seqBig.cu, demonstrates how to use a 64-bit unsigned integer to sum all the 32-bit integers in the vector. The actual values are printed at the end of the test. See Example 1.14, “A Thrust Program that Performs a Dual-Precision Reduction”:

The nvcc compiler has the ability to compile and run an application from a single command-line invocation. Example 1.15, “Results Showing a Successful Test” shows the nvcc command line and the successful run of the seqBig.cu application:

Can you find any other silent errors that might occur as the size of N increases in these examples? (Hint: what limitations does tid have in the runtime example?)

Debugging programs is a fact of life—especially when learning a new language. With a few simple additions, CUDA enables GPGPU computing, but simplicity of expression does not preclude programming errors. As when developing applications for any computer, finding bugs can be complicated.

Following the same economy of change used to adapt C and C++, NVIDIA has extended several popular debugging tools to support GPU computing. These are tools that most Windows and UNIX developers are already proficient and comfortable using such as gdb, ddd, and Visual Studio. Those familiar with building, debugging, and profiling software under Windows, Mac, and UNIX should find the transition to CUDA straightforward. For the most part, NVIDIA has made debugging CUDA code identical to debugging any other C or C++ application. All CUDA tools are freely available on the NVIDIA website, including the professional edition of Parallel Nsight for Microsoft Visual Studio.

Parallel Nsight also provides a debugging experience familiar to Microsoft Visual Studio users yet includes powerful GPU features like thread-level debugging and the CUDA memory checker. It installs as a plug-in within Microsoft Visual Studio. Parallel insight also provides a number of features:

Parallel Nsight allows both debugging and analysis on the machine as well as on remote machines that can be located at a customer's site. The capabilities of Parallel Nsight vary with the hardware configuration seen in Table 1.3.

Figure 1.6 shows Parallel Nsight stopped at a breakpoint on the GPU when running the fillkernel() kernel in seqRuntime.cu. The locals window shows the values of various variables on the GPU.

A screenshot does not convey the interactive nature of Parallel Nsight, as many of the fields on the screen are interactive and can be clicked to gain more information. Visual Studio users should find the Parallel Nsight comfortable, as it reflects and utilized the look and feel of other aspects of Visual Studio. Parallel Nsight is an extensive package that is growing and maturing quickly. The most current information, including videos and the user forums, can be found on the Parallel Nsight web portal at http://www.nvidia.com/ParallelNsight as well as the help section in Visual Studio.

This chapter covered a number of important applied topics such as how to write, compile, and run CUDA applications on the GPGPU using both the runtime and Thrust APIs. With the tools and syntax discussed in this chapter, it is possible to write and experiment with CUDA using the basics of the Thrust and runtime APIs. Audacious readers may even attempt to write real applications, which is encouraged, as they can be refactored based on the contents of later chapters and feedback from the performance profiling tools. Remember, the goal is to become a proficient CUDA programmer and writing code is the fastest path to that goal. Just keep the three basic rules of GPGPU programming in mind:

Understanding basic computer science concepts is also essential to achieving high performance and improving yourself as a computer scientist. Keep Amdahl's law in mind to minimize serial bottlenecks as well as exploiting both task and data parallelism. Always try to understand the big-O implications of the algorithms that you use and seek out alternative algorithms that exhibit better scaling behavior. Always attempt to combine operations to achieve the highest computational density on the GPU while minimizing slow PCIe bus transfers.