Building the Code

The provided makefile will build the serial code for the CPU using the PGI compiler without modification simply by running the make command. In order to obtain some additional information to help with our initial performance study, we’ll modify the compiler flags to add several profiling options.

• -Minfo=all,ccff: This compiler flag instructs the compiler to print information about how it optimizes the code and additionally embed this information in the executable for use by tools that support the common compiler feedback format.

The modified makefile is shown in Fig. 1.

At this point we have an executable (cg.x) that will serially execute the CG benchmark. The expected output is found in Fig. 2. The exact time required to run the executable will vary depending on CPU performance, but the total iterations and tolerance values should always match the values shown.

Initial Benchmarking

We will now use the PGProf profiler to obtain a baseline CPU profile for the code. This will help us to understand where the executable is spending its time so that we can focus our efforts on the functions and loops that will deliver the greatest performance speed-up. The PGProf profiler is installed with the PGI Compiler and OpenACC Toolkit. To open it, use the pgprof command from your command terminal. Once the profiler window is open, select New Session from the File menu, opening the Create New Session dialog box. By the box labeled File, press the Browse button and browse to and select your executable, which will be called cg.x. Once you have selected your executable, press the Next button and then the Finish button. At this point the profiler will run the executable, sampling the state of the program at a regular frequency to gather performance information. When complete, choose the CPU Details tab in the bottom part of the window to display a table of the most important functions in the executable. The window will look similar to what is shown in Fig. 3.

At this point, double-clicking on the most time-consuming function, matvec, will bring up a dialog to choose the location of your source files. Once you have selected the directory containing your sources, a new tab will be opened to the matvec routine in matrix_functions.h. The loop on line 33 will have a symbol in the margin to the left indicating that the profiler is able to read compiler feedback about this loop. Hovering over the graph symbol will bring up a box showing information about what optimizations the compiler was able to perform on the loop and the computational intensity of the loop. See Fig. 4 for an example.

Reading compiler feedback is the only way to understand what information the compiler is able to determine about your code and what actions it takes based on this information. The compiler may choose to rearrange the loops in your code, break them into more manageable chunks, parallelize the code to run using vector instructions such as SSE or AVX, or maybe not do anything at all because it is unable to determine what optimizations will be safe and profitable. Frequently the programmer will know information about the code that the compiler is not able to learn on its own, resulting in the compiler missing optimization and parallelization opportunities. Throughout this chapter we will be providing the compiler with more information to improve the actions it takes to optimize and parallelize this code. This is, in many ways, the primary goal of OpenACC programming: providing the compiler with enough additional information about the code that it can made good decisions on how to parallelize it to any hardware.

Exploring the CPU performance table we see that there’s three functions of interest: matvec, waxpy, and dot. The fourth most time-consuming routine is allocate_3d_poisson_matrix, which is an initialization routine that is only run once, so it will be ignored. Examining the code shows that the matvec routine contains a doubly nested loop that performance a sparse matrix/vector product and the other two routines both contain a single loop that perform two common vector operations (aX + bY and dot product). These are the three loop nests where we will focus our efforts to parallelize the benchmark.

Accelerating Waxpby

On line 33 of vector_functions.h we’ll begin by parallelizing the waxpby routine. This function contains just one loop, which we will parallelize by adding the OpenACC kernels pragma immediately before the start of the loop. With this pragma added we need to inform the compiler that we are providing it with OpenACC pragmas and ask it to build the code for a target accelerator. I will be running the code on a machine that contains an NVIDIA Tesla K20c GPU, so I will choose the tesla accelerator target. Enable OpenACC for NVIDIA GPUs using the −ta=tesla command-line option. Although the compiler is targeting NVIDIA Tesla GPUs, which are intended for datacenter environments, the resulting code should run on other NVIDIA GPUs as well. The Makefile changes can be found in Fig. 5 and the compiler feedback for the waxpby routine is found in Fig. 6.

We see from the compiler feedback that although it generated a GPU kernel, something went wrong when it tried to parallelize the loop. Specifically, the compiler believes that a data dependency could exist between iterations of the loop. A data dependency occurs when one loop iteration depends upon data from another loop iteration. Close examination of the loop body reveals that each iteration of the loop is completely data-independent of each other iteration, meaning that the results calculated in one iteration will not be used by any other. So why does the compiler believe that the loop has a data dependency? The problem lies in the low-level nature of the C and C++ programming languages, which represent arrays simply as pointers into memory; pointers which can potentially point to the same memory. The problem is that the compile cannot prove that the three arrays used in the loop do not alias, or overlap, with each other, so it has to assume that parallelizing the loop would be unsafe. We can provide the compiler with more information in one of two ways. One possibility is to give the compiler more information about the pointers by promising that they will never alias. This can be done by adding the C99 restrict keyword. While this is not a C++ keyword, the PGI compiler will accept this keyword in C++ codes. ¹ We could also give the compiler more information about the loop itself using the OpenACC loop directive. The loop directive gives an OpenACC compiler additional information about the very next loop. We can use the loop independent clause to inform the OpenACC compiler that all iterations of the loop are independent, meaning that no two iterations depend up the data of the other, thus overriding the compiler’s dependency analysis of the loop. Both solutions are promises that the programmer makes to the compiler about the code. If the promise is broken then unpredictable results can occur. In this code, we cannot make the guarantee that our vectors will not alias, since at times the function is called with y and w being the same vector, so we will use loop independent instead. The final code for waxpby appears in Fig. 7 along with compiler feedback in Fig. 8. Notice from the compiler feedback that the compiler has now determined that the loop at line 41 is parallelizable.

Looking more closely at the compiler feedback, notice that the compiler did more than just parallelize the loop for my GPU. The compiler understands that my target accelerator has a physically distinct memory from my host CPU, so it will be necessary to relocate my input arrays to the GPU for processing and my output array back for use later. The output for line 40 tells us that it recognizes that xcoefs and ycoefs are input arrays, so it generates a copy in to the GPU, and wcoefs is an output array, so it generates a copy out of the GPU. What the feedback is actually showing are data clauses, additional information about how the data within our compute region is used. In this case, the compiler was able to correctly determine the size, shape, and usage of our three arrays, so it generated implicit data clauses for those arrays. Sometimes the compiler will be overly cautious about data movement, so it is necessary for the programmer to override its decisions by adding explicit data clauses to the kernels directive. Other times the compiler cannot actually determine the size or shape of the arrays used within a region, so it will abort and ask for more information, as you will see when we work on the matvec routine.

Before moving on, it is always important to recompile and rerun the code to check for any errors that we may have introduced. It is much simpler to find and correct errors after making small changes than waiting until after we’ve made a lot of changes. After rerunning the code you should see that you’re still getting the same answers, but the code has now slowed down. If we rerun the executable within the PGProf profiler now, we’ll see the reason for the slowdown. Fig. 9 shows the GPU timeline that the profile gathered when I reran the executable, zoomed in a bit for clarity. What we see across the timeline are individual GPU operations (kernels) and associated data transfers. Notice that for each call to waxpby we now copy two arrays to the device and one array back for use by other function. This is really inefficient. Ideally we’ll want to leave our data in GPU memory for as long as possible and avoid these intermediate data transfers. The only way to do that is to accelerate the remaining functions so that the data transfers become unnecessary.

Accelerating Dot

Let’s quickly look at the dot routine as well, because the compiler will help us in other was when we use the OpenACC kernels pragma. Just as before, we will add a kernels pragma around the interesting loop and recompile the code. Fig. 10 shows the OpenACC version of the function and Fig. 11 shows the compiler feedback. Notice in the compiler feedback that at line 29 it generated an implicit reduction. Every iteration of the loop calculates its own value for xcoefs[i]*ycoefs[i], but the compiler recognizes that we don’t actually care about each of those results, but rather the sum of those results. A reduction takes the n distinct values that get calculated in the loop and reduces them down to the one value we care about: the sum. It is important to understand that due to the imprecise nature of floating point arithmetic a parallel reduction may result in a slightly different, but equally correct, answer than adding the numbers one at a time sequentially. How much this will vary will depend on the actual numbers being added together, how many numbers are being summed, and the order the operations happen, but the difference could be a few bits or even several digits. Remember, both the sequential and parallel sum are correct because floating point arithmetic is imprecise by its nature. Because we used the kernels pragma to parallelize this loop, the compiler handled the complexity of identifying this reduction for us. Had we used the more advanced parallel pragma instead, it would have been our responsibility to inform the compiler of the reduction. Before moving on to the next section, don’t forget to rerun the code to check for mistakes.

Accelerating Matvec

The final routine that needs to be accelerated is the matvec routine. As was said earlier, were this more than a teaching exercise this routine would have been the correct place to start our effort, since it is the most dominant routine by far, but this routine has some interesting complexities that require us to take additional steps when expressing the parallelism contained within. Let’s start by taking the same approach as the other two routines: add the restrict keyword to our arrays and wrap our loop nest with a kernels pragma. When we attempt to build this routine, however, the compiler issues an error message, as shown in Fig. 12.

The most important part of the compiler output here is the accelerator restriction at line 34, which states that it doesn’t know how to calculate the size of the arrays used inside the kernels region, specifically the three arrays used within the innermost loop. In the previous two examples, the compiler could determine based on the number of loop iterations how much data needed to be relocated to the accelerator, but because the loop bounds inside of matvec are hidden within our matrix data structure, it is impossible for the compiler to determine how to relocate the key arrays. This is a case where we will need to add explicit data clauses to our kernels pragma to give the compiler more information about our data structures. Table 1 lists the five most common data clauses and their meanings. We’ve already seen the copyin and copyout clauses implicitly used by the compiler in the previous functions.

In order for the compiler to parallelize the loop nest in matvec for my GPU, which requires the offloading of data, we’ll need to tell the compiler the shape of at least the three arrays used within the inner loop. All three of these arrays are used only for reading, so we can use a copyin data clause, but we’ll need to tell the compiler the shape of the arrays, which we can learn by looking at how they are allocated in the allocate_3d_poisson_matrix function, located in matrix.h. The data clauses accept a list of variables with information about the size and shape of the variables. In C and C++ the size and shape of the arrays are provided using square brackets ([ and ]) containing the starting index and number of elements to transfer, e.g., [0:100] to start copying at index 0 and copy 100 elements of the array. In Fortran the syntax uses parentheses and used the first and last index to copy, for instance (1:100) to start at index 1 and copy all elements up to element 100 in the array. The difference in syntax between these programming languages is intentional to fit with the conventions of the base programming languages. Since Fortran variables are self-describing, the size and shape information can be left off if the entire variable needs to be moved to the device.

Fig. 13 shows the modified code for the matvec function. Notice the addition of a copy data clause to the kernels direction, which informs the compiler both how to allocate space for the affected variables on the accelerator, but also that the data is only needed as input to the loops. With this change, we’re now able to run the full CG calculation in parallel on the accelerator and get correct answers, but notice in Fig. 14 that the runtime is now longer than our original code.

Let’s rerun the executable using the PGProf profiler to see if we can determine why the code is so much slower than it was before, even though it is now running in parallel on our GPU. Fig. 15 shows the GPU timeline returned from PGProf, zoomed in for clarity.

Describing Data Movement of Matrix and Vector

To avoid unnecessary data movement in each of the three functions we’ve parallelized we will add unstructured data directives to the functions that manage the data in our Matrix and Vector structures. It is important to remember that OpenACC’s data model is host-first, meaning that data directives that allocate data on the device must appear after host allocations (malloc, allocate, new, etc.) and data directives that deallocate device data must appear before host deallocations (free, deallocate, delete, etc.). Given this, let’s add enter data directives to the allocate_3d_poisson_matrix and allocate_vector functions, in matrix.h and vector.h respectively. Since allocate_3d_poisson_matrix does some additional initialization, it is simplest to add the directives to the end of the routine so that the device copy of the data structure will contain the initialized data.

Fig. 16 shows an abbreviated listing of the allocate_3d_poisson_matrix function with the enter data directives added. It may seem strange at first to copy A to the device and then all of the member arrays inside A. The A structure contains two scalar numbers, plus 3 pointers that are used on the device. The copyin of A at line 71 copies the structure, with the 5 elements that I just described. When the 3 pointers are copied, however, they will contain pointers back to the host memory, since the pointers were simply copied to the device. It is then necessary to copy the data pointed to by those pointers, which is what the pragma at line 72 achieves. Line 72 gives the three arrays contained in A shapes and copies their data to the device. When removing the data from the device in the free_matrix function, these operations should be done in the reverse order, as shown in Fig. 17.

The allocate_vector and free_vector functions can be similarly modified to relocate Vector structures to the accelerator as well. Since allocate_vector does not initialize the vector with any data, the create data clause can be used to allocate space without causing any data copies to occur, as shown in Fig. 18.

At this point the benchmark will run with all Matrix and Vector data structures residing on the device for the entire calculation, but it will give incorrect results because the code fails to initialize the vector data structures on the accelerator. To fix this, it is necessary to modify the initialize_vector function to update the device data with the initialized host data. This can be done with the OpenACC update directive. The update directive causes the data in the host and device copies of a variable to be made consistent, either by copying the data from the device copy to the host, or vice versa. On architectures with a unified memory for both the host and accelerator devices update operations are ignored.

The update directive accepts a device or self clause to declare which copy of the data should be modified. Since we want to update the device’s data using the data from the host, the device clause is used, specifying that the device’s copy of the coefficients array should updated. An update directive can be used in the initialize_vector function to copy the data in the initialized host vector to the device, as shown in Fig. 19. When using the update directive, the amount of data to update is specified in the same way as the data clauses, as shown earlier. In the case of Fortran arrays, if the entire array needs to be updated then the bounds can be left off.

One point of confusion for new OpenACC programmers is why the clause for updating the host’s arrays is called self. OpenACC 1.0 used the host keyword to specify that the host array should be updated with the data from the device array, but since OpenACC 2.0 opened up the possibility of nesting OpenACC regions within other OpenACC compute regions, it is possible that the thread performing the update isn’t on the host, but rather is on a different accelerator. Fig. 20 shows a pseudo-code example of a kernels region nested within another kernels region. When the update on line 4 occurs, the device running the outer kernels region will copy the values from its copy of A to the device that will run the kernels region on line 5. At line 8 the device running the outer kernels region needs to copy back the results from the inner region. Saying update the host copy is not correct, since the kernels region at line 1 might not be running on the host, so OpenACC 2.0 introduced the idea of update self, as-in update my copy of the data with the device data. The host keyword still exists in OpenACC 2.0 and beyond, but it has been defined to always mean self instead.

At this point building and running the benchmark code results in a large performance improvement on the example system. Examining the PGProf timeline (Fig. 21) shows that the data is copied to the device at the very beginning of the execution and only the resulting norm is copied back periodically. This is because we’ve expressed to the compiler that it should generate our data structures directly on the accelerator and the compute regions that were added in the previous section check for the presence of the data and, upon finding the data on the device, reuse the existing device data. On accelerators with discrete memory, such as the GPU used in this example, expressing data motion is often the step where programmers will see the greatest speed-up, since the significant bottleneck of copying data over the PCIe bus is removed. It is tempting to think that because this step creates such a large speed-up it should be done first. Doing so is often error prone, however, since it would be necessary to introduce update directives each time an unaccelerated loop is encountered. It is simpler instead to first put all of the loops on the device, at least within a significant portion of the code, and then eliminate unnecessary data transfers. Forgetting to eliminate an unneeded data transfer is simply a performance bug, which is simple to identify with the profiler, while forgetting an update directive because data directives were added to the program too soon is a correctness bug that is often much more difficult to find.

Reduce Vector Length

Since I’m running this benchmark on an NVIDIA GPU, I’ll use my understanding of NVIDIA GPUs and the application to make better decisions about how to parallelize the loop. For instance, I know that NVIDIA GPUs perform best when the vector loop accesses data in a stride-1 manner, meaning each successive loop iteration accesses a successive array element. Although the outer loop accesses the row_offsets array stride-1, the inner loop accesses the Acols, Acoefs, and xcoefs arrays in stride-1, making it a better target for vectorization. Adding a loop pragma above the inner loop allows us to specify what level of parallelism to use on that loop. Additionally we can specify the vector length that should be used. The compiler appears to prefer vector lengths of 128, but our inner loop always operates on 27 non-zero elements, which results in wasting 101 vector lanes each time we operate on that loop. It’d be better to reduce the vector length, given what we know about the loop count, to reduce wasted resources. Ideally we’d just reduce the vector length to 27, since we know this is the exact number of loop iterations, but this NVIDIA GPU has a hardware vector length, referred to by NVIDIA as the warp size, of 32, so let’s reduce the vector length to 32, thus wasting only 5 vector lanes rather than 101. Fig. 24 shows the matvec loops with the inner loop mapped to vector parallelism and a vector length of 32. Notice the device_type clause on the loop directive. This clause specifies that the clauses I list are only applied to the nvidia device type, meaning that they won’t affect the compiler’s decision making on other platforms.

As we see from the output in Fig. 25, this change actually negatively affected the overall performance. It is tempting to reverse this change to the code, since it didn’t help our runtime, but I feel quite confident that the decision to vectorize the innermost loop is the right decision, so instead I will turn to the profiler to better understand why I didn’t get the speed-up I expected.

Increase Parallelism

In order to determine why customizing the vector length didn’t have the desired effect, we’ll use the PGProf guided analysis mode to help determine the performance limiter. Guided analysis should be enabled by default, so after starting a new session with the current executable, select the Analysis tab and follow the suggestions provided. The analysis should eventually point toward GPU occupancy as the limiting factor, as shown in Fig. 26. Occupancy is a term used by NVIDIA to describe how well the GPU is saturated compared to how much work it could theoretically run. NVIDIA GPUs are comprised of 1 or more streaming multiprocessors, commonly referred to as SMs. An SM can manage up to 2048 concurrent threads, although not all of these threads will be actively running at the same time. The profiler output is showing that of the possible 2048 active threads, the SM only has 512 threads, resulting in 25% occupancy. The red line in Fig. 26 shows why this is: the SM can manage at most 16 threadblocks, which equate to OpenACC gangs, but it would require 64 to achieve full occupancy due to the size of the gang, which we can see from the “Threads/Block” line only has 32 threads. What all of this is showing is that by reducing the vector length to 32, the total threads per GPU threadblock is reduced to 32 too, so we need to introduce more parallelism in order to better fill the GPU.

We can increase the parallelism within the gang in one of two ways: increase the vector length or increase the workers. We know from the previous section that increasing the vector length doesn’t make any sense, since there’s not enough work in the inner loop to support a longer vector length, so we’ll try increasing the number of workers. The total work within the GPU threadblock can be thought of as the number of workers × the vector length, so the most workers we could use is 32, because 32 × 32 = 1024 GPU threads. Fig. 27 shows the final matvec loop code and Fig. 28 shows the speed-up from changing the number of workers within each gang.

On this particular test system 8 workers of 32 threads appears to be the optimal gang size. Since the device_type clause is used, these optimizations will only apply when building for NVIDIA GPUs, leaving other accelerators unaffected.