Parallel Region, Gangs, and Workers

The single #pragma at line 4 in Figure 15.1 is actually a syntax sugar of two #pragma (Figure 15.4). We explain the parallel construct here and will explain the loop construct in the next section.

The parallel construct is one of the two constructs (the other is the kernels construct) that can be used to specify which part of the program is to be executed on the accelerator. When a program encounters a parallel construct, the execution of the code within the structured block of the construct (also called a parallel region) is moved to the accelerator. Gangs of workers on the accelerator are created to execute the parallel region, as shown in Figure 15.3. Initially only one worker (let us call it a gang lead) within each gang will execute the parallel region. The other workers are conceptually idle at this point. They will be deployed when there is more parallel work at an inner level. The number of gangs can be specified by the num_gangs clause, and the number of workers within each gang can be specified by the num_workers clause.

In this example (Figure 15.5), a total of 1,024×32=32,768 workers are created. The a=23 statement will be executed in parallel and redundantly by 1,024 gang leads. You may ask why anyone would want to write accelerator code like this. The usefulness of the parallel construct will become clear when it is used with the loop construct.

If a parallel construct does not have an explicit num_gangs clause or an explicit num_workers clause, then the implementation will pick the numbers at runtime. Once a parallel region starts executing, the number of gangs and the number of workers within each gang remain fixed during the execution of the parallel region. This is similar to CUDA in which once a kernel is launched, the number of blocks in the grid and the number of threads in a block cannot be changed.

Gang Loop

Suppose you have a loop where all the iterations can be independently executed in parallel and you want to speed up its execution by running it on the accelerator. Can you write the code like Figure 15.6?

As we learned from the previous section, although the loop will be executed on the accelerator, you won’t get any speedup because all 2,048 iterations will be executed sequentially and redundantly by the 1,024 gang leads. To get speedup, you need to distribute the 2,048 iterations among the gangs. And to do that, you need to use the gang loop construct, as shown in Figure 15.7.

A gang loop construct is always associated with a loop. The gang loop construct is a work-sharing construct. The compiler and runtime will make sure that the iterations of a gang loop are shared among all gang leads encountered in the loop construct. In Figure 15.7, because 1,024 gang leads will encounter the loop construct, each lead will be assigned two iterations. Now the execution of the parallel loop will be more efficient and likely to achieve speedup.

Worker Loop

What if you also have an inner loop that can be executed in parallel? Well, that is when the worker loop construct can be beneficial.

The worker loop construct is also a work-sharing construct. The compiler and runtime will make sure that the iterations of a worker loop are shared among all workers within a gang. In Figure 15.8, the 32 workers in a gang will work collectively on the 512 iterations of the j loop in each of the two iterations of the i loop assigned to the gang. A total of 2,048×512=1 M instances of foo() will be executed in the sequential version or the parallel version. In the parallel version, 1,024×32=32 K workers are used and each worker will execute 1 M÷32 K=32 instances of foo().

OpenACC Versus CUDA

Readers who are familiar with CUDA C may ask how the OpenACC code in Figure 15.8 is different from the CUDA C code in Figure 15.9? They may wonder, can’t I just write the CUDA C version and achieve the same effect?

Yes, they are similar in this case. And as a matter of fact, some OpenACC implementations may actually generate the CUDA C version in Figure 15.9 from the OpenACC version in Figure 15.8 and pass it to the CUDA C compiler. But one clear advantage of the OpenACC version is that it is much closer to the sequential version than the CUDA C version. Only a few code modifications are required. Compared with CUDA C, OpenACC gives you less control of how the final code on the accelerator will be. However, the strength of OpenACC lies in its ability to tackle more complicated existing sequential code, especially when the original code you want to port to execute on the accelerator is not a perfectly nested loop nest.

Take the code snippet in Figure 15.10 for example. Let’s assume both loops are parallel loops. If you want to move the whole code snippet to execute on the accelerator, it is much easier with OpenACC. If the code can give you the same result when statements 1, 2, 5, 6, 9, and 10 are executed redundantly by multiple gang leaders, then you can do what is shown in Figure 15.11.

The first pragma in Figure 15.11 creates 32 gangs. Statements 1 and 2 are executed by all gangs. Note that in the original code, these statements are executed only once. However, after the annotation, the compiler will generate code that executes these statements 32 times. This is equivalent to moving a statement into a loop. As long as the statement can be executed extra times without producing incorrect results, this is not a problem.

The second pragma in Figure 15.11 assigns the work of the for loop to the 32 gangs. Each gang will further distribute its share of the work to multiple workers. The exact number of workers in each gang will likely be decided at runtime when the number of iterations and the number of execution units are known.

If statements 1, 2, 5, 6, 9, and 10 can only be executed once, then you can still make the annotations shown in Figure 15.12. In this case, only one gang with 32 workers will be created. The gang leader will execute statements 1, 2, 5, 6, 9, and 10. It will assign the work for the two for loops to its 32 workers. Obviously, the number of workers will be much lower than the previous case, which employs 32 gangs, each of which has multiple workers.

The important point here is that to achieve the same effect with CUDA, more significant code changes are required between the two cases. In the first case, statements 1 and 2 need to be pushed into the loop so that a kernel can be formed with statements 1, 2, 3, and 4. Similarly, another kernel needs to be formed with statements 5, 6, 7, 8, 9, and 10. In the second case, statements 1, 2, 5, 6, 9, and 10 will remain as the host code, whereas statements 1 and 2 will form a kernel and statements 7 and 8 will form a second kernel. We leave the detailed implementation of the kernels in both cases as exercises.

Vector Loop

Recall that OpenACC was designed to support multiple levels of parallelism found in a typical accelerator. The vector clause on a loop construct is often used to express the innermost vector or SIMD (single instruction, multiple data) mode loop in an accelerator region, as illustrated in Figure 15.13.

On a GPU, a possible implementation is to map a gang to a CUDA block, a worker to a CUDA warp, and a vector element to a thread within a warp. However, this is not mandated by the OpenACC specification and an implementation (compiler/runtime) may choose a different mapping based on the code pattern within an accelerator region for best performance.

Prescriptive Versus Descriptive

Like the parallel construct, the kernels construct also allows a programmer to specify which part of a program he or she wants to be executed on an accelerator. And a loop construct can be used inside a kernels construct. One major difference between the two is that a kernels region may be broken into a sequence of kernels, each of which will be executed on the accelerator, while the whole parallel region will become a kernel and be executed on the accelerator. Typically, each loop nest in a kernels construct may become a kernel, as illustrated in Figure 15.14.

In the figure, the kernels region may be broken into three kernels, one for each loop, and they will be executed on the accelerator in order. It is also possible that some implementations may decide not to generate a kernel for the k loop and therefore this kernels region will contain two kernels—one for the i loop and the j loop each and the k loop is executed on the host.

A kernels region may contain multiple kernels and each may use a different number of gangs, a different number of workers, and different vector lengths. Therefore, there is no num_gangs, num_workers, or vector_length clause on the kernels construct. You can specify them on the enclosed loop construct if you want to, as illustrated in Figure 15.14.

Now let’s take a look at another major difference between the parallel construct and the kernels construct. In Figure 15.14, how many times will the k loop be executed? Previously we’ve learned that the non-work-sharing code inside a parallel construct will be executed redundantly by the gang leads (see Figures 15.5 and 15.6). If the k loop in Figure 15.14 were inside a parallel construct, then the statement d[k] = c[k] is executed 2,048 times the number of gangs. This is different in a kernels construct, in which case it is just 2,048 times.

The parallel construct and the kernels construct were designed from two different perspectives. The kernels construct is more descriptive. It describes the intention of the programmer. The compiler is responsible for mapping and partitioning the program to the underlying hardware. Notice we use the word “may” when we explain the kernels code in Figure 15.14. It is possible that an OpenACC-compliant compiler decides not to generate any kernels at all for the kernels region in Figure 15.14. The loop constructs used for the i and j loops tells the compiler to generate such code that the loop iterations will be shared among the gang leaders only if the compiler decides to generate kernels for these loops. There are two common reasons why a compiler decides not to generate a kernel for a loop construct. One reason is safety. The compiler checks whether parallelizing the loop will give the same execution result as the sequential version does. A series of analyses will be performed on the loop and the rest of the program. If the compiler finds it is not safe to parallelize the loop or cannot decide whether it is safe due to lack of information, then the compiler will not parallelize the loop and hence will not generate a kernel for the loop construct. The other reason is performance. The ultimate goal for using OpenACC directive is to get speedup. The compiler may decide not to parallelize and execute a loop on the accelerator if it finds doing so will only slow down the program. Since the compiler will mostly take care of the parallelization issues, the descriptive approach makes porting programs to OpenACC relatively easier. The downside is the quality of the generated accelerated code depends significantly on the capability of the compiler used. A high-quality compiler is expected to give feedbacks to the programmer on how it compiles kernels constructs and why it does not parallelize certain loops. With this information, the programmer can be sure whether his or her intension is achieved and may provide more hints to the compiler to achieve his or her goal. In the next section, we will show a few ways to help an OpenACC compiler.

The parallel construct is more prescriptive. The compiler does what the programmer instructs it to do. The programmer ultimately has more control of where to generate kernels and how to parallelize and schedule loops. Different OpenACC compilers should perform the similar transformations to a parallel construct. The downside is that there is no safety net. If a loop has data dependence between different iterations and is unsafe to be parallelized, then a programmer should not put such a serial loop inside a loop construct. This is the same philosophy taken by OpenMP, which is another successful directive-based approach for parallel programming. Programmers who are familiar with OpenMP should feel comfortable using parallel constructs.

Ways to Help an OpenACC Compiler

To parallelize a loop inside a kernels region, an OpenACC compiler generally needs to prove there is no cross-iteration data dependence in the loop. There is no data dependence in the i loop in Figure 15.15. All iterations can be executed in parallel and give the same result as when the iterations are executed sequentially. An OpenACC compiler should have no trouble deciding the i loop is parallelizable. In the j loop, each iteration uses the value of array element a[] defined in the previous iteration, therefore, the result will be different if the loops are executed in parallel. An OpenACC compiler should have no trouble deciding the ‘j’ loop is not parallelizable.

For the k loop, there is no data dependence if x[] and y[] are not aliased. However, this cannot be decided by examining the function foo() alone. If an OpenACC compiler does not perform interprocedural analysis or the call site of function foo() is not available, then the compiler has to conservatively assume there is data dependence. If x[] and y[] are indeed never aliased, we can add the C restrict qualifier to the declaration of pointer argument x and y as illustrated in Figure 15.16. An OpenACC compiler should then be able to use this information to decide if the k loop is parallelizable.

Now what to do with the 1 loop? This loop is parallelizable if the value of n is no less than m. Let’s assume this is always true in this program. However, there is no C language construct to express such information. In this case, we can add an independent clause to the loop construct, as illustrated in Figure 15.17. The independent clause simply tells the compiler that the associated loop is parallelizable and no analysis is required. You can also add the independent clause to the ‘i’. You could also add the clause to the ‘j’ loop construct, but that would not be correct.

Data Clauses

So far you have seen copy, copyin, and copyout clauses used on parallel and kernels constructs. These are called data clauses. A data clause has a list of arguments separated by a comma. Each argument can be a variable name or a subarray specification. The OpenACC compiler and runtime will create a copy of the variable or subarray in the device memory. Reference to the variable or subarray within the parallel or kernels constructs will be made to the device copy.

The code snippet in Figure 15.18 is from the matrix multiplication example in Figure 15.4. Here, three pieces of memory are allocated on the device. Arrays M and N are the input data, so they are declared as copyin. The copyin from the host memory to the device memory happens right before the parallel region starts execution. Array P is the output data, so it is declared as copyout. The copyout from the device memory to the host memory happens right after the parallel region ends. The copy clause can be used to declare data that needs to be both copied in and copied out.

Notice that the subarray specification is used for M, N, and P here. That’s because M, N, and P are actually pointers and we need to specify the range of memory that needs to be copied. The value before and after the : specifies the starting array element and the number of array elements, respectively. So M[0:Mh∗Mw] means M[0], M[1], M[2], …, and M[Mh∗Mw-1]. A common programmer error is mistaking the second value as the last array element.

Some variables do not need to be copied in or copyied out—their values are generated and consumed within a kernel. In such cases, the create clause can be used.

Another commonly used data clause is the deviceptr clause. This clause takes a list of pointers as its argument and declares that these are actually device pointers so that the data does not need to be allocated or moved between the host and the device for memory pointed by these pointers. When a program uses both OpenACC and CUDA kernels (or CUDA libraries, such as cuFFT, cuBLAS, etc.), the deviceptr clause becomes handy. Figure 15.19 shows an example of doing the matrix multiplication twice, first using a CUDA kernel and then using an OpenACC parallel region—both work on the same device memory allocated by cudaMalloc().

Data Construct

In OpenACC, host memory and device memory are separated. Data transfer between the host and the accelerator can play a significant role in the overall performance of an OpenACC application. For example, when a computationally intense loop nest of an iterative solver, implemented using a parallel loop, transfers data back and forth between host and the accelerator at every iteration, then there may be a loss of performance. The OpenACC data construct allows one to exploit reuse by avoiding data transfers during multiple executions of parallel or kernels regions.

Figure 15.20 shows a simplified implementation of a 2D Jacobi relaxation. Each element in the array field is updated by taking the average of each element with its eight neighbors. This is repeated 256 times. Another array tmpfield is used to make the relaxation parallel. In each pass, the values are read from one array and the average is computed and then it is written into the same position in the second array. Since the two arrays do not overlap, the updates are completely data parallel. Lines 6-24 implement one pass of the relaxation. Each pass is executed in an OpenACC parallel region. We group the 256 passes into 128 pairs. Each pair contains two parallel regions—one updates tmpfield with field, and the other updates field with tmpfield. Recall that there is no synchronization between gangs. Therefore, we need two parallel constructs to make sure the writes to one array are completed before the array can be used as the source of updates in the next pass.

We want the data to stay on the device during all the 256 passes. This is achieved by using the data construct in line 28. The data region specified by the data construct is from line 30-38, including all called functions. The copy(field) clause says we need to create a device copy of array field, copy its data from the host to the device when the data region starts, and copy its data back to the host when the data region ends. And for the enclosed parallel constructs at lines 31 and 33, just use this copy of field. The create(tmpfield) clause says we need to create a device copy of array tmpfield for this data region, and use this copy for the enclosed parallel constructs at lines 31 and 33.

Now the data is on the device all the time during the passes. What if we want to check the intermediate result on the host occasionally? We can do it by using the update directive, as illustrated at line 36. This says the value of the host array ‘fields’ should be updated with that of the device copy at this point. Since the update is performed conditionally in the code, the data transfer won’t happen if not required. The update directive can also be used to update the value of the device copy with that of the host copy.