The OpenMP standard that rules
Jumanazarov Mardonbek
Plan:
As multi-core architectures grow in size and popularity, thread-level parallelism details become critical factors in software performance. In this chapter, we first introduce the basics of Open Multi-Processing (OpenMP), a shared-memory programming standard, and explain why a fundamental understanding of how OpenMP works is essential. We'll examine sample problems, ranging from a simple, common "Hello, World" example to a complex, multi-threaded, stencil implementation with OpenMP parallelization. We'll thoroughly analyze the interactions between OpenMP directives and the underlying OS kernel, as well as the memory hierarchy and hardware functionality. Finally, we'll explore a promising high-level OpenMP programming approach for future extreme-scale applications.
We demonstrate that the high-level OpenMP paradigm is effective for algorithms containing many short computational cycles. Compared to more standard threading approaches, the high-level OpenMP paradigm results in reduced thread overhead, synchronization waits, cache thrashing, and memory usage. Given these advantages, it's crucial for a modern parallel computing programmer (you) to be familiar with the shared-memory and distributed-memory programming paradigms. We discuss the distributed-memory programming paradigm in Chapter 8, which covers the Message Passing Interface (MPI).
NOTE: The accompanying source code for this chapter can be found at https://github.com/EssentialsofParallelComputing/Chapter7.
1. Introduction to OpenMP
OpenMP is one of the most widely supported open standards for threading and shared-memory parallel programming. In this section, we explain the standard itself, its ease of use, expected benefits, challenges, and memory models.
The version of the OpenMP standard you see today took considerable time to develop, and it is still evolving. OpenMP originated when several hardware vendors introduced their implementations in the early 1990s. In 1994, an unsuccessful attempt was made to standardize these implementations in the draft ANSI X3H5 standard. Only with the introduction of large-scale multi-core systems in the late 1990s did the OpenMP-based approach regain its popularity, leading to the first OpenMP standard in 1997.
Today, OpenMP offers a standard and portable API for writing shared-memory parallel programs using threads; It is known to be easy to use, provides quick implementation, and requires only a small amount of code, typically considered in the context of pragmas or directives. A pragma (C/C++) or directive (Fortran) tells the compiler where to initiate OpenMP threads. The terms pragma and directive are often used interchangeably. Pragmas are preprocessor instructions in C and C++. Directives are written as Fortran comments to ensure the program maintains standard language syntax when OpenMP is not used. Although using OpenMP requires a compiler that supports it, most compilers come with support for it.
1. Introduction to OpenMP
OpenMP, the open source multiprocessing framework, makes parallelization accessible to beginners, making it easy and fun to begin scaling an application beyond a single core. With simple use of OpenMP pragmas and directives, a block of code can quickly execute in parallel. Figure 7.1 shows a conceptual view of the required effort and resulting performance for OpenMP and MPI (discussed in Chapter 8). Using OpenMP will often be an exciting first step in scaling an application.
Figure 7.1 Conceptual visualization of the programming effort required to improve performance using MPI or OpenMP
1. Introduction to OpenMP
OpenMP Concepts
While moderate parallelism is easy to achieve with OpenMP, exhaustive optimization can be difficult. The source of this difficulty is the relaxed memory model[1], which allows for race conditions between threads. By relaxed, we mean that the values of variables in main memory are not updated immediately. It would be too expensive to do so every time the variables change. Because of the update latency, slight differences in the timing of memory operations performed by each thread on shared variables can lead to different results from execution to execution. Let's look at a few definitions.
[1] More precisely, the relaxed-consistency, shared-memory model. – Note. transl.
1. Introduction to OpenMP
The OpenMP standard was originally used to parallelize highly regular loops using threads on shared-memory multiprocessors. In a threaded parallel construct, each variable can be either shared or private. The terms "shared" and "private" have specific meanings for OpenMP. Here are their definitions:
A true understanding of these terms requires a fundamental understanding of how memory is handled in a threaded application. As shown in Figure 7.2, each thread has private memory on its stack and shares memory on the heap.
1. Introduction to OpenMP
Figure 7.2. The thread memory model helps us understand which variables are shared and which are private. Each thread, shown by the wavy lines, has its own instruction pointer, stack pointer, and stack memory, but shares heap and static memory data.
1. Introduction to OpenMP
OpenMP directives define work sharing, but say nothing about memory or data location. As a programmer, you must understand the implicit rules for variable memory space. The OS kernel can use several memory management techniques for OpenMP and threading. The most common method is the concept of first-touch, where memory is allocated closest to the thread that first touched it. Here's how we define the terms work sharing and first-touch:
The importance of first touch is that many high-end HPC nodes have multiple memory locations. When multiple memory domains exist, non-uniform memory access (NUMA) often occurs between the CPU and its processes accessing different parts of memory, which adds an important consideration for code performance optimization.
DEFINITION: On some compute nodes, memory blocks are closer to some processors than others. This situation is called non-uniform memory access (NUMA) and often occurs when a node has two CPU sockets, each with its own memory. A processor accessing memory in a different NUMA domain typically takes twice as long (a penalty) as accessing its own memory.
1. Introduction to OpenMP
Moreover, because OpenMP has a weakened memory model, it requires a barrier or flush operation to transfer the memory view from one thread to another. The flush operation ensures that the value moves between two threads, preventing race conditions. The OpenMP barrier flushes all locally modified values and synchronizes the threads. This updating of values is performed by a complex operation in the hardware and operating system.
In a multi-core system with shared memory, modified values in the cache must be flushed to main memory and updated. Newer CPUs use specialized hardware to determine what has actually changed, so the cache across dozens of cores is updated only when necessary. But this operation is still expensive and forces threads to stall while waiting for updates. In many ways, it's similar to the kind of operation you have to perform when you want to remove a flash drive from a computer; You must tell the operating system to flush all flash caches and then wait. Source code that uses frequent barriers and underruns in combination with smaller parallel sections often has excessive synchronization, resulting in poor performance.
OpenMP addresses a single node, rather than multiple nodes with distributed memory architectures. Consequently, its memory scalability is limited by the memory on a node. For parallel applications with large memory requirements, open multiprocessing, OpenMP, should be used in conjunction with a distributed memory parallel technology. We'll discuss the most common of these, the MPI standard, in Chapter 8.
1. Introduction to OpenMP
Table 7.1 shows several common OpenMP concepts, terminology, and directives. We'll demonstrate their use throughout the rest of this chapter.
Table 7.1: Roadmap of OpenMP topics in this chapter
Concept / Section | Directive | Description |
Topic | OpenMP | |
OpenMP pragma | #pragma omp | Used to define OpenMP directives in C/C++ for parallel programming. |
Parallel sections (see Listing 7.2) | #pragma omp parallel | Creates threads within the section according to this directive. |
Shared loop work (see Listing 7.7) | #pragma omp for (Fortran: #pragma do for) | Splits the loop iterations evenly among threads. Scheduling expressions include static, dynamic, guided, and auto. |
Parallel section with shared work (see Listing 7.7) | #pragma omp parallel for | Combines parallel and work-sharing directives; can be used inside subroutine calls. |
Reduction (see Section 7.3.5) | #pragma omp parallel for reduction (+: sum), (min: xmin), (max: xmax) | Performs parallel reduction operations such as sum, min, or max across threads. |
Synchronization (see Listing 7.15) | #pragma omp barrier | Introduces a synchronization point: all threads stop here until each reaches this point, then proceed together. |
Sequential sections (see Listings 7.4 and 7.5) | #pragma omp masked | Executed only by thread 0 without any barrier at the end. |
| #pragma omp single | Executed by a single thread with an implicit barrier at the end of the block. Used when a function in a parallel section should run only on one thread. |
Locks | #pragma omp critical or atomic | Used for advanced implementations; ensures mutual exclusion in specific code regions. |
1. Introduction to OpenMP
[1] The #pragma omp masked pragma was the #pragma omp master pragma. With the release of the OpenMP v5.1 standard in November 2020, the term master was replaced with masked to address concerns that it was offensive to many in the technical community. We are strong advocates of inclusivity and, therefore, use the new syntax throughout this chapter. Readers are cautioned that it may take some time for this change to be implemented in compilers. Please note that the examples accompanying this chapter will use the older syntax until most compilers are updated.
A Simple OpenMP Program
Now we'll show you how to apply each OpenMP concept and directive. In this section, you'll learn how to create a code fragment with multiple threads (virtual cores) using the OpenMP parallel pragma to solve a traditional "Hello, World" problem distributed across threads. You'll see how easy it is to use OpenMP and potentially achieve performance gains. There are several approaches to managing the number of threads in a parallel region, including:
1. Introduction to OpenMP
export OMP_NUM_THREADS=16
omp_set_threads(16)
#pragma omp parallel num_threads(16)
The simple example in listings 7.1–7.6 shows how to get the thread ID and number of threads. Listing 7.1 shows our first attempt at writing a "Hello, World" program.
1. Introduction to OpenMP
To compile with GCC:
gcc -fopenmp -o HelloOpenMP HelloOpenMP.c
where -fopenmp is a compiler flag to enable OpenMP.
1. Introduction to OpenMP
Next, we'll set the number of threads the program will use by setting an environment variable. We could also call omp_set_num_threads() or simply let OpenMP choose the number of threads based on the hardware we're running on. To set the number of threads, use this command, which sets the environment variable:
export OMP_NUM_THREADS=4
Now run the executable by running ./HelloOpenMP. We'll get:
Goodbye, slow serial world, and hello, OpenMP!
I have 1 thread(s), and my thread ID is 0.
Not quite what we wanted; we only have one thread. To achieve multiple threads, we need to add a parallel section. Listing 7.2 shows how to add a parallel section.
NOTE: Throughout this chapter, you'll see annotations labeled >> Spawn Threads >> and Implicit Barrier. These are visual cues that indicate where threads are spawned and where the compiler inserts barriers. In subsequent listings, we'll use the same annotations labeled "Explicit Barrier" to indicate where we've inserted a barrier directive.
1. Introduction to OpenMP
1. Introduction to OpenMP
With these changes in mind, we get the following result:
Goodbye, slow serial world, and hello, OpenMP!
I have thread(s), and my thread ID is 3
Goodbye, slow serial world, and hello, OpenMP!
I have thread(s), and my thread ID is 3
Goodbye, slow serial world, and hello, OpenMP!
Goodbye, slow serial world, and hello, OpenMP!
I have thread(s), and my thread ID is 3
I have thread(s), and my thread ID is 3
As you can see, all threads report that they are thread number 3. This is because the nthreads and thread_id variables are shared. The value assigned to these variables during execution corresponds to what is written by the last thread executing the instruction. We have a typical race condition, as shown in Figure 1. 7.3 This problem is widespread in threaded programs of any type.
1. Introduction to OpenMP
Figure 7.3. The variables in the example above are defined before the parallel section, so they are shared variables on the heap.
Each thread writes to them, and the final value is determined by which of them writes last. Shading shows a time progression, with write operations in different clock cycles performed by different threads in a non-deterministic manner. This situation and similar conditions are called race conditions because the results can vary from execution to execution.
1. Introduction to OpenMP
Also note that the printout order is random and depends on the order of writes from each processor and how they are flushed to the standard output device. To obtain the correct thread numbers, we define the thread_id variable in the loop, making its scope private to the thread, as shown in the following listing.
1. Introduction to OpenMP
And we get
Let's say we didn't actually want to print each thread. Let's minimize the printing and put the print statement in a single OpenMP statement, as shown in the listing below. This ensures that the result is written by only one thread.
1. Introduction to OpenMP
And the result is now this:
The number of threads is 4
My thread ID is 2
1. Introduction to OpenMP
The thread ID has a different value for each execution. Here, we actually wanted the output thread to be the first thread, so we changed the OpenMP expression in the listing below and used masked instead of single .
Running this source code now returns what we were trying to do from the very beginning:
Goodbye, slow serial world, and hello, OpenMP!
I have 4 threads, and my thread ID is 0.
1. Introduction to OpenMP
We can make this operation even more concise and use fewer pragmas, as shown in Listing 7.6. The first print instruction doesn't have to be in a parallel section. Furthermore, we can restrict the second printout to thread zero by simply applying a conditional block to the thread number. The implicit barrier is associated with the omp parallel pragma.
1. Introduction to OpenMP
We learned several important things from this example.
The OpenMP standard is constantly being updated, and new versions are released regularly. Before using an OpenMP implementation, you should know its version and supported features. OpenMP began with the ability to use threads on a single node. The OpenMP standard has added new capabilities, such as vectorization and offloading tasks to accelerators like GPUs. The table below shows some of the major features added over the past decade.
1. Introduction to OpenMP
It's worth noting that, due to significant hardware changes since 2011, the pace of change in OpenMP has accelerated. While changes in versions 3.0 and 3.1 focused primarily on the standard CPU threading model, changes in versions 4.0, 4.5, and 5.0 since then have focused primarily on other forms of hardware parallelism, such as accelerators and vectorization.
2. Typical OpenMP use cases: loop level, high level, and MPI plus OpenMP
OpenMP has three specific use cases to meet the needs of three different types of users. The first decision you need to make is which case is appropriate for your situation. The strategy and methods differ for each of these cases: loop-level OpenMP, high-level OpenMP, and OpenMP for enhancing MPI implementations. In the following sections, we'll discuss each in detail, including when to use them, why, and how to use them. Figure 7.4 shows the recommended reading for each use case.
Figure 7.4 Recommended reading sections for each scenario depend on your application's use case.
2. Typical OpenMP use cases: loop level, high level, and MPI plus OpenMP
Loop-Level OpenMP for Fast Parallelization
A typical use case for loop-level OpenMP is when your application requires only moderate speedup and ample memory resources. By this, we mean that its requirements can be met by the memory of a single hardware node. In this case, using loop-level OpenMP is often sufficient. The following list summarizes the characteristics of loop-level OpenMP:
In such cases, we use loop-level OpenMP because it requires little effort and is fast. With a separate parallel for pragma, the problem of race conditions between threads is reduced. By placing OpenMP parallel for pragmas or parallel do directives before key loops, loop parallelism can be easily achieved. Even when the ultimate goal is a more efficient implementation, this loop-level approach is often the first step in introducing thread parallelism into an application.
NOTE: If your use case requires only moderate speedup, skip to Section 7.3 for examples of this approach.
2. Typical OpenMP use cases: loop level, high level, and MPI plus OpenMP
High-Level OpenMP for Improved Parallel Performance
Next, we'll discuss another scenario, high-level OpenMP, where higher performance is required. Our high-level OpenMP design is radically different from the strategies for standard, loop-level OpenMP. Standard OpenMP starts bottom-up and applies parallelism constructs at the loop level. Our approach for high-level OpenMP takes a system-wide design perspective using a top-down approach that takes into account the memory system, the system kernel, and the hardware. The OpenMP language remains unchanged, but the method of using it changes. The end result is that we eliminate many of the thread startup and synchronization costs that hinder the scalability of loop-level OpenMP.
If you need to extract every last drop of performance from your application, then high-level OpenMP is for you. As a starting point for your application, begin by exploring loop-level OpenMP in Section 7.3. Then, you'll need to gain a deeper understanding of OpenMP variable scoping in Sections 7.4 and 7.5. Finally, dive into Section 7.6 to see how the high-level OpenMP approach, diametrically opposed to the loop-level approach, leads to performance gains. In that section, we'll look at the implementation model and a step-by-step method for achieving the desired structure. Detailed implementation examples for high-level OpenMP follow.
2. Typical OpenMP use cases: loop level, high level, and MPI plus OpenMP
MPI plus OpenMP for Maximum Scalability
We can also use OpenMP to complement distributed memory parallelism (as described in Chapter 8). The basic idea of using OpenMP on a small subset of processes adds another layer of parallel implementation that facilitates extreme scaling. This can be within a node or, even better, across a set of processors that evenly distribute fast access to shared memory, commonly referred to as a non-uniform memory access (NUMA) region.
We first discussed NUMA regions in OpenMP concepts in Section 7.1.1 as an additional consideration for performance optimization. By using threading only within a single memory region, where all memory accesses have the same cost, we can avoid some of the complexities and performance pitfalls of OpenMP. In a more modest hybrid implementation, OpenMP can be used to manage two to four hyperthreads per processor. We'll discuss this scenario, a hybrid MPI + OpenMP approach, in Chapter 8 after covering the basics of MPI.
To gain the OpenMP skills necessary for this low-thread hybrid approach, it's sufficient to study the cycle-level OpenMP methods in Section 7.3. Then, gradually move to a more efficient and scalable OpenMP implementation that allows MPI ranks to be replaced by increasingly larger numbers of threads. This requires at least several steps toward high-level OpenMP, as described in Section 7.6. Now that you know which specific sections are important for your application's use case, let's move on to the details of how each strategy works.
3. Examples of standard OpenMP loop level
In this section, we'll look at examples of loop-level parallelization. The loop-level use case was introduced in Section 7.2.1; here we'll show you the implementation details. Let's get started.
Parallel sections are initiated by inserting pragmas around blocks of code that can be shared between independent threads (i.e., do loops and for loops). For memory handling, the OpenMP standard relies on the OS kernel. This reliance on memory handling is often a significant factor that limits OpenMP from achieving its full potential. We'll look at the reason why. Each variable in a parallel construct can be either shared or private. Furthermore, OpenMP has a relaxed memory model. Each thread has a temporary memory map, so it doesn't incur the cost of maintaining memory for each operation. When the temporary map finally needs to be reconciled with main memory, an OpenMP barrier or an underflow operation is required to synchronize the memory. Each of these synchronizations incurs some cost due to the time required for emptying and the need for fast threads to wait for slower threads to complete. Understanding how OpenMP works will help reduce these performance bottlenecks.
Performance isn't the only concern for an OpenMP programmer. You must also be aware of correctness issues caused by race conditions between threads. Threads can progress on processors at different speeds, and when combined with poor memory synchronization, serious bugs can suddenly appear even in well-tested code. Building robust OpenMP applications requires careful programming and the use of specialized tools, as described in Section 7.9.2.
3. Examples of standard OpenMP loop level
In this section, we'll look at several loop-level OpenMP examples to get a feel for its practical use cases. The source code accompanying this chapter contains even more variations of each example. We strongly encourage you to experiment with each example on your preferred architecture and compiler. We ran all examples on a dual-socket Skylake Gold 6152 system and a 2017 Mac laptop. Threads are allocated per core, and thread affinity is enabled using the following OpenMP environment variables to reduce performance variability between runs:
export OMP_PLACES=cores
export OMP_CPU_BIND=true
We'll explore thread placement and affinity in Chapter 14. For now, to help you gain experience with loop-level OpenMP, we'll present three different examples: vector addition, a thread triad, and stencil code. We will show the parallel speedup of these three examples after the last example in Section 7.3.4.
3. Examples of standard OpenMP loop level
Loop-Level OpenMP: Vector Addition Example
The vector addition example (Listing 7.7) demonstrates the interaction between three components: OpenMP work-sharing directives, implicit variable scoping, and operating system memory allocation. These three components are essential for the correctness and performance of an OpenMP program.
3. Examples of standard OpenMP loop level
3. Examples of standard OpenMP loop level
This particular implementation style provides modest parallel performance on a single node. Note that this implementation could be improved. The first touch of the entire array memory occurs by the main thread during initialization before the main loop, as shown on the left in Figure 7.5. This can result in its memory being allocated in a different memory location, where memory access times are longer for some threads.
Now, to improve OpenMP performance, we insert pragmas into the initialization loops, as shown in Listing 7.8. These loops are allocated in the same static thread partition, so threads that touch memory in the initialization loop will have memory allocated by the operating system near them (shown on the right side of Figure 7.5).
3. Examples of standard OpenMP loop level
Fig. 7.5 Adding the OpenMP single pragma to the main vector addition loop (left) causes the first touch of arrays a and b to occur on the main thread; data is allocated near thread zero. Array c is first touched during the execution loop, and therefore the memory for array c is located close to each thread. On the right, adding the OpenMP pragma to the initialization loop causes the memory for arrays a and b to be located near the thread in which the work is performed.
3. Examples of standard OpenMP loop level
3. Examples of standard OpenMP loop level
Threads in the second NUMA region no longer experience slower memory access times. This improves memory bandwidth for threads in the second NUMA region and improves load balancing between threads. First Touch is an operating system policy mentioned previously in Section 7.1.1. Good first touch implementations can often improve performance by 10–20%. To confirm this, see Table 7.2 in Section 7.3.4, which shows the performance improvements in these examples.
With NUMA enabled in the BIOS, the Skylake Gold 6152 CPU experiences a nearly twofold performance penalty when accessing remote memory. As with most tunable parameters, individual system configurations may vary. To examine your configuration in Linux, you can use the numactl and numastat commands. You may need to install the numactl-libs or numactl-devel packages to run these commands.
3. Examples of standard OpenMP loop level
Figure 7.6 shows the results for the Skylake Gold benchmark platform mentioned above. The inter-node distances listed at the end roughly reflect the memory access cost on the remote node. This can be thought of as the relative number of hops required to access memory. Here, the memory access cost is slightly greater than double (21 versus 10). Note that sometimes the default configuration of two NUMA region systems is reported as 20 versus 10, rather than their actual cost.
Knowing the NUMA configuration can give you a hint as to what is more important to optimize. If you only have a single NUMA region or the difference in memory access costs is small, you may not need to worry as much about first-touch optimizations. If the system is configured for interleaved access to NUMA regions, optimizing for faster local memory access will not help. In the absence of specific information, or when attempting to optimize generally for larger HPC systems, first-touch optimizations should be used for faster local memory access.
3. Examples of standard OpenMP loop level
Figure 7.6. Output from the numactl and numastat commands. The distance between memory regions is highlighted. Note that NUMA utilities use the term "node" differently than we have defined it. In their terminology, each NUMA region is a node. We reserve the term node for a single distributed memory system, such as another desktop computer or a shelf in a rack-mounted system.
3. Examples of standard OpenMP loop level
Stream Triad Example
The following listing shows another similar example of stream triad benchmarking. This example runs multiple iterations of the compute kernel to obtain average performance:
3. Examples of standard OpenMP loop level
Again, to implement OpenMP threaded computations, we only need one pragma in line 25. The second pragma, inserted in line 17, further improves performance by improving memory allocation through proper first-touch techniques.
3. Examples of standard OpenMP loop level
Loop-Level OpenMP: A Stencil Example
The third example of loop-level OpenMP is the stencil operation, first introduced in Chapter 1 (Figure 1.10). The stencil operator adds surrounding neighbors and takes the average value for the new cell value. Listing 7.10 presents more complex access patterns involving memory reads, and as the procedure is optimized, it demonstrates the effect of threads accessing memory that other threads have written to. In this first implementation of loop-level OpenMP, each parallel for block is synchronized by default, preventing potential race conditions. In later, more optimized versions of stencil, we will add explicit synchronization directives.
3. Examples of standard OpenMP loop level
3. Examples of standard OpenMP loop level
3. Examples of standard OpenMP loop level
In this example, we inserted a flush loop on line 46 to flush the cache of the x and xnew arrays. This is done to simulate performance when the code has no variables in the cache from a previous operation. The case without data in the cache is called a cold cache, and when there is data in the cache, it is called a warm cache. Both cold and warm caches are valid cases for analysis in different use cases. It's just that both cases are possible in a real application, and without in-depth analysis, it can be difficult to understand exactly what will happen.
3. Examples of standard OpenMP loop level
Performance of Loop-Level Examples
Let's review the performance of the previous examples in this section. As shown in Listings 7.8, 7.9, and 7.10, introducing loop-level OpenMP requires minor changes to the source code. As Table 7.2 shows, performance improves by approximately 10x. This is a fairly good return on the effort required. However, for a system with 88 threads, the achieved parallel efficiency is clearly modest, at around 19%, as shown below, leaving some room for improvement. To calculate the speedup, we first take the serial execution time divided by the parallel execution time, as follows:
Stencil speedup = (serial execution time) / (parallel execution time) = 17.0x faster.
If we achieve the ideal speedup on 88 threads, it would be 88x. We take the actual speedup and divide by the ideal speedup of 88 to calculate the parallel efficiency:
Stencil parallel efficiency = (stencil speedup) / (ideal speedup) = 17 / 88 = 19%.
Parallel efficiency is much higher with fewer threads; with four threads, it is 85%. The effect of thread-side memory allocation is small but significant. In the running times in Table 7.2, the first optimization, simple loop-level OpenMP, uses the OpenMP parallel for pragma only on compute cycles. The second optimization, first-touch, adds the OpenMP parallel for pragma to initialization cycles. Table 7.2 summarizes the performance improvements for simple OpenMP with the first-touch optimization added. The running times were set to OMP_PLACES=cores and OMP_CPU_BIND=true.
3. Examples of standard OpenMP loop level
Table 7.2 shows execution time in ms. Speedup on a dual-socket Skylake Gold 6152 node with GCC version 8.2 is 10x on 88 threads. Adding the OpenMP pragma on initialization to properly allocate memory on first touch provides additional speedup.
Profiling a stencil application threaded using OpenMP, we observe that 10–15% of the execution time is accounted for by OpenMP overhead, consisting of thread waits and thread startup costs. OpenMP overhead can be reduced by adopting a high-level OpenMP design, as discussed in Section 7.6.
3. Examples of standard OpenMP loop level
An example of a global sum-based reduction using OpenMP threading
Another common loop type is a reduction. Reduction is a common parallel programming pattern, introduced in Section 5.7. Reductions are any operation that starts with an array and computes a scalar result. In OpenMP, this can also be easily handled in a loop-level pragma by adding a reduction clause, as shown in the following listing.
3. Examples of standard OpenMP loop level
The reduce operation calculates a sum local to each thread and then sums all threads. The reduce variable sum is initialized to the appropriate value for the operation. In the source code shown in Listing 7.11, the reduce variable is initialized to zero. Initializing the sum variable to zero in line 3 is still necessary for proper operation when not using OpenMP.
Potential Difficulties of Loop-Level OpenMP
Loop-level OpenMP can be applied to most, but not all, loops. For the OpenMP compiler to apply the work-sharing operation, the loop must have a canonical form. The canonical form is the traditional, simplest implementation of a loop, which programmers are familiar with from the beginning. Its requirements are as follows:
3. Examples of standard OpenMP loop level
The last requirement can be verified by reversing the order of the loop or changing the order of the loop operations. If the answer changes, the loop will have loop-borne dependencies. Similar constraints on loop-borne dependencies exist for CPU optimization and GPU threading implementations. The similarities of this requirement to loop-borne dependencies are described as the "fine-grained vs. coarse-grained" parallelism used in distributed memory and message-passing approaches. Here are some definitions:
Many programming languages offer a modified loop type that signals to the compiler that loop-level parallelism is permitted in some form. In the meantime, this information is brought in by passing a pragma or directive before the loop.
4. The Importance of Variable Scope for Correctness in OpenMP
To convert an application or routine to high-level OpenMP, you need to understand variable scope. The OpenMP specifications are vague on many of the details of scope organization. Figure 7.7 shows the scope rules for compilers. Generally, a variable on the stack is considered private, while variables allocated on the heap are shared (Figure 7.2). For high-level OpenMP, the most important issue is how to manage scope within a called routine in a parallel region.
Fig. 7.7 Brief description of the rules for organizing thread visibility for OpenMP applications
4. The Importance of Variable Scope for Correctness in OpenMP
4. The Importance of Variable Scope for Correctness in OpenMP
In line 4 of Listing 7.11, we added a reduction expression to the directive to indicate the special treatment required for the sum variable. Line 2 of Listing 7.12 shows the private directive. Other expressions can be used in the parallel directive and other program blocks, for example:
We highly recommend using tools such as Intel® Inspector and Allinea/ARM MAP, which are used to develop more efficient code and implement high-level OpenMP. We discuss some of these tools in Section 7.9. Before implementing high-level OpenMP, it's important to be familiar with a number of essential tools. Once you have run your application through these tools, you can gain a deeper understanding of the application, which will allow you to more smoothly transition to a high-level OpenMP implementation.
5. Function-level OpenMP: making the entire function thread-parallel
We'll introduce the high-level OpenMP concept in Section 7.6. However, before attempting to use high-level OpenMP, we need to look at how to extend loop-level implementations to encompass larger sections of code. The goal of extending loop-level implementations is to reduce overhead and improve parallel efficiency. When extending a parallel region, it ultimately encompasses the entire subroutine. By converting an entire function into an OpenMP parallel region, OpenMP provides much less control over thread-scoped variables. Parallel region expressions are no longer helpful, since there's no room to add expressions that define the scope. So, how do you control variable scope?
While the default variable scope options in functions generally work well, there are cases where they fail. The only OpenMP control provided by pragmas for functions is the threadprivate directive, which makes the declared variable private. Most variables in a function are on the stack and are already private. If an array in a subroutine is dynamically allocated, the pointer it is assigned to is a local variable on the stack, meaning it is private and different for each thread. We want this array to be shared, but there is no directive for this. Using the compiler-specific scoping rules shown in Figure 7.7, we add the save attribute to the Fortran pointer declaration, forcing the compiler to put the variable on the heap and therefore share the variable between threads. In C, a variable can be declared static or file-scoped. The following listing shows several examples of thread-scoped variables for Fortran, and Listing 7.14 shows examples for C and C++.
5. Function-level OpenMP: making the entire function thread-parallel
5. Function-level OpenMP: making the entire function thread-parallel
The pointer to the y array in line 6 is the variable scope of the subroutine location. In this case, it is in a parallel region, making it private. Both the pointer to x and the variable x1 are private. The scope of the variable x2 in line 10 is more complex. It is shared in Fortran 90 and private in Fortran 77. Initialized variables in Fortran 90 are on the heap and are initialized (in this case, to zero) only the first time they are seen! The variables x3 and z in lines 11 and 12 are shared because they are on the heap. The memory allocated for x in line 14 is on the heap and is shared, but the pointer is private, which means the memory is only accessible by thread zero.
5. Function-level OpenMP: making the entire function thread-parallel
The pointer to array y in the argument list on line 5 is on the stack. It has variable scope at the calling location. In the parallel section, the pointer to y is private. The memory for array x is on the heap and is shared, but the pointer is private, so the memory is accessible only from thread zero. The memory for array x1 is on the heap and is shared, and the pointer is shared, so the memory is accessible and shared by all threads.
You should always be alert to unintended consequences of variable declarations and definitions that affect thread scope. For example, initializing a local variable with a value in a Fortran 90 routine automatically assigns the save attribute to the variable, and the variable is now shared[1]. To avoid any problems or confusion, we recommend adding the save attribute explicitly to the declaration.
[1] This is not a Fortran 77 requirement! But even in Fortran 77, some compilers, such as the DEC Fortran compiler, require every variable in a subroutine to have a save attribute, which causes obscure bugs and portability issues. Knowing this, we could ensure compilation in the Fortran 90 standard and potentially eliminate the private scope issue by initializing the array pointer, which causes it to be moved to the heap, making the variable shared.
6. Improving Parallel Scalability with High-Level OpenMP
Why use high-level OpenMP? The central strategy of high-level OpenMP is to improve standard loop-level parallelism by minimizing fork/join overhead and memory latency. Reducing thread latency is often seen as another important motivating factor for high-level OpenMP implementations. By explicitly dividing work between threads, threads no longer implicitly wait for other threads and can therefore proceed to the next part of the computation. This allows explicit control of the synchronization point. In Figure 7.8, unlike the typical fork/join model of standard OpenMP, high-level OpenMP keeps threads dormant but alive, significantly reducing overhead.
6. Improving Parallel Scalability with High-Level OpenMP
Figure 7.8: High-level visualization of OpenMP threading. Threads are spawned once and remain dormant when not needed. Thread boundaries are manually set, and synchronization is kept to a minimum.
In this section, we'll review the specific steps required to implement OpenMP at a high level. We'll then show you how to move from a loop-level implementation to a high-level implementation.
6. Improving Parallel Scalability with High-Level OpenMP
How to Implement High-Level OpenMP
Implementing high-level OpenMP often takes longer because it requires advanced tools and extensive testing. High-level OpenMP implementations can also be complex because they are more susceptible to race conditions than standard loop-level implementations. Furthermore, it is often unclear how to transition from the starting point (loop-level implementation) to the final point (high-level implementation).
A more tedious high-level OpenMP implementation is widely used when efficiency is desired and the overhead of thread spawning and synchronization is eliminated. For more information on high-level OpenMP, see Section 7.11. Implementing efficient high-level OpenMP multiprocessing (OpenMP) is possible with a thorough understanding of the memory boundaries associated with all loops in your application, using profiling tools, and methodically following the steps below. We propose and demonstrate an implementation strategy that is progressive, methodical, and ensures a successful, smooth transition to a high-level OpenMP implementation. The steps to implement high-level OpenMP are:
6. Improving Parallel Scalability with High-Level OpenMP
Figures 7.9 and 7.10 show pseudocode corresponding to the four steps above, starting with a typical loop-level implementation using the omp parallel do pragmas and moving on to more efficient high-level parallelism.
6. Improving Parallel Scalability with High-Level OpenMP
Figure 7.9. High-level OpenMP starts with a loop-level OpenMP implementation and merges parallel sections to reduce thread spawning costs. We use animal images to show where changes are made and the relative speed of the actual implementation. Regular loop-level OpenMP, represented by the turtle, is faster, but there is overhead in each parallel do pragma, which limits the speedup. The dog shows the relative speedup from merging parallel sections.
6. Improving Parallel Scalability with High-Level OpenMP
Figure 7.10. The next high-level OpenMP steps add nowait statements to the do and for loops, which reduce synchronization overhead. We then calculate loop boundaries ourselves and use them explicitly in the loops to avoid even more synchronization. Here, the cheetah and hawk identify changes made to both implementations. The hawk (right) is faster than the cheetah (left), as OpenMP overhead is reduced.
6. Improving Parallel Scalability with High-Level OpenMP
In our steps toward implementing high-level OpenMP, thread startup time is reduced in the first step of high-level OpenMP. All code is placed in a single parallel region to minimize forking and joining overhead. In high-level OpenMP, threads are generated once with the parallel directive, at the beginning of program execution. Unused threads do not die but remain dormant during the sequential portion. To ensure this, the sequential portion is executed by the main thread, allowing for virtually no changes to the sequential portion of the code. Once the program completes the sequential portion or restarts the parallel region, the same threads that were forked at the beginning of the program are invoked or reused.
Step 2 concerns synchronization, which is added by default to every for loop in OpenMP. The simplest way to reduce synchronization overhead is to add a nowait statement to all loops where possible while maintaining correctness. The next step is to explicitly divide the work between threads. Typical code for explicit work splitting in C is shown below. (The Fortran equivalent, which takes array indexing starting with 1, is shown in Figure 7.10.)
tbegin = N * threadID /nthreads
tend = N * (threadID+1)/nthreads
The effect of manual array splitting is to reduce cache waste and race conditions by preventing threads from sharing the same memory space.
6. Improving Parallel Scalability with High-Level OpenMP
Step 3, optimization, means explicitly stating that some variables are shared or private. By giving threads specific memory space, the compiler (and the programmer) can remove guesswork about the state of variables. This is done by enforcing the variable scoping rules shown in Figure 7.7. Furthermore, compilers cannot properly parallelize loops that contain complex loop-borne dependencies and loops that are not in canonical form. High-level OpenMP assists the compiler by more clearly describing the thread-specific scope of variables, thereby enabling parallelization of complex loops. This leads to the last part of this step in the high-level OpenMP approach. Arrays will be shared among threads. Explicitly sharing arrays ensures that a thread only touches its assigned memory and allows us to begin to address memory locality issues.
And in the final step, ensuring code correctness, it's important to apply the race condition detection and remediation tools listed in Section 7.9. In the next section, we'll walk you through the process of implementing these steps. The programs in this chapter's GitHub source code repository will be helpful in following this step-by-step process.
6. Improving Parallel Scalability with High-Level OpenMP
A High-Level OpenMP Implementation Example
A full high-level OpenMP implementation can be completed in several steps. First, in addition to finding the most expensive loop in your code, you should look at where the bottleneck(s) are in your application. Then, you can find the code loop at the innermost level and add standard OpenMP loop directives. It's important to understand the variable scope in the most expensive loops and inner loops, referring to Figure 7.7 for guidance.
In Step 1, you should focus on reducing the cost of thread startup. This is done in Listing 7.15 by combining parallel sections to include the entire iteration loop in a single parallel section. We begin slowly moving the OpenMP directives outward, expanding the parallel section. The initial OpenMP pragmas on lines 49 and 57 can be combined into a single parallel section between lines 44–70. The length of the parallel section is defined by the curly brackets in lines 45 and 70, as a result the parallel section starts only once instead of 10,000 times.
6. Improving Parallel Scalability with High-Level OpenMP
6. Improving Parallel Scalability with High-Level OpenMP
6. Improving Parallel Scalability with High-Level OpenMP
Portions of code that must be executed sequentially are placed under the control of the main thread, allowing the parallel region to expand into larger chunks of code spanning both sequential and parallel regions. At each step, use the tools described in Section 7.9 to ensure consistent correct operation of the application.
In the second part of the implementation, you begin the transition to high-level OpenMP by moving the main parallel OpenMP loop to the beginning of the program. You can then proceed to calculating the upper and lower bounds of the loop. Listing 7.16 (and the online examples in stencil_opt5.c and stencil_opt6.c) show how to calculate the upper and lower bounds specific to the parallel region. Keep in mind that arrays start at different points depending on the language: Fortran starts at 1, while C starts at 0. Loops with the same upper and lower bounds can use the same thread without requiring recalculation of the bounds.
NOTE: Remember to place barriers where necessary to prevent race conditions. Also, be careful when placing these pragmas, as too many of them can negatively impact overall application performance.
6. Improving Parallel Scalability with High-Level OpenMP
6. Improving Parallel Scalability with High-Level OpenMP
6. Improving Parallel Scalability with High-Level OpenMP
6. Improving Parallel Scalability with High-Level OpenMP
To get the right answer, it's crucial to start with the innermost loop and understand which variables should remain private or be shared between threads. As you begin to expand the parallel region, sequential portions of code will be placed in a masked region. This region has a single thread, and it does all the work, while the other threads remain alive but dormant. Placing sequential portions of code in the main thread requires zero or very few changes. After the program completes execution in the sequential region or enters the parallel region, the previously dormant threads resume execution, parallelizing the current loop.
In the final step, comparing the results for the steps toward a high-level OpenMP implementation in Listings 7.14 and 7.15, as well as in the online stencil examples provided, you will see that the number of pragmas has been significantly reduced, while performance has improved (Figure 7.11).
6. Improving Parallel Scalability with High-Level OpenMP
Figure 7.11 Optimizing OpenMP pragmas simultaneously reduces the number of required pragmas and improves the performance of the stencil kernel
7. Hybrid Streaming and Vectorization with OpenMP
In this section, we'll combine the topics from Chapter 6 with those introduced in this chapter. This combination provides higher-quality parallelism and leverages the vector processor. An OpenMP threaded loop can be combined with a vectorized loop by adding a simd expression to the parallel for statement, as in #pragma omp parallel for simd. The following listing demonstrates this for a threaded triad.
7. Hybrid Streaming and Vectorization with OpenMP
7. Hybrid Streaming and Vectorization with OpenMP
A hybrid implementation of the stencil example with streaming and vectorization places the for pragma in the outer loop and the simd pragma in the inner loop, as shown in the listing below. Both streaming and vectorized loops work best with loops over large arrays, as is typically the case in the stencil example.
7. Hybrid Streaming and Vectorization with OpenMP
7. Hybrid Streaming and Vectorization with OpenMP
Comparing the GCC compiler results with and without vectorization shows significant speedup with vectorization:
4 threads, GCC 8.2 compiler, Skylake Gold 6152
Threads only: Timing init 0.006630 flush 17.110755 stencil 17.374676
total 34.499799
Threads & vectors: Timing init 0.004374 flush 17.498293 stencil 13.943251
total 31.454906
8. Advanced OpenMP Usage Examples
The examples shown so far were simple loops over a data set with relatively few complications. In this section, we'll show you how to tackle three more advanced examples that require more effort.
The examples in this section reveal various ways to solve more complex situations and give you a deeper understanding of OpenMP.
Stencil example with separate passes for x and y directions
Here, we'll explore potential difficulties encountered when implementing OpenMP for a two-step stencil operator with split-direction, in which a separate pass is performed for each spatial direction. Stensiles (or stencils) are the building blocks of numerical scientific applications and are used to calculate dynamic solutions to partial differential equations.
8. Advanced OpenMP Usage Examples
In a two-step stencil, where values are computed on edges, the data arrays have different data sharing requirements. Figure 7.12 shows such a stencil with two-dimensional edge arrays. Furthermore, it often happens that one dimension of these two-dimensional arrays must be shared among all threads or processes. Manipulating x-edge data is simpler because it is consistent with the thread-specific data decomposition, but we don't need the full x-edge array in each thread. Y-edge data poses a different challenge because the data permeates all threads, requiring shared use of the two-dimensional y-edge array. High-level OpenMP allows for quick privatization of the required dimension. Figure 7.12 shows how some matrix dimensions can be made private, shared, or both.
8. Advanced OpenMP Usage Examples
Figure 7.12. A thread-aligned x-edge of a stencil requires separate storage for each thread. The pointer must be on the stack, and each thread must have its own pointer. The y-edge must share data, so we define a single pointer in a static data area where both threads can access it.
8. Advanced OpenMP Usage Examples
The first-touch principle inherent to most kernels (defined in Section 7.1.1) states that memory is likely to be thread-local (except for interthread edges at page boundaries). We can improve memory locality by making array sections completely private to a thread where possible, such as x-edge data. As the number of processors increases, increasing data locality is crucial to minimizing the widening performance gap between processors and memory. The following listing shows a sequential implementation to begin with.
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
When using OpenMP with the stencil operator, it is necessary to determine whether the memory for each thread should be private or shared. In Listing 7.18 (above), the memory for the x-direction can be completely private, allowing for faster computation. In the y-direction (Figure 7.12), the stencil requires access to the data of the adjacent thread; therefore, this data must be shared between threads. This leads us to the implementation shown in the following listing.
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
To define the memory on the stack, as shown in the x-direction, we need a pointer to a pointer to a double-precision number (double **xface) so that the pointer resides on the stack and is private to each thread. We then allocate the memory using a special two-dimensional malloc call on line 98 in Listing 7.20. We only need enough memory for each thread, so on lines 91 and 92 we calculate the thread bounds and use them in the two-dimensional malloc call. The memory is allocated from the heap and can be shared, but each thread only has its own pointer; therefore, each thread cannot access the memory of other threads.
Instead of allocating memory from the heap, we could use automatic allocation, such as double xface[3][6], which automatically allocates memory on the stack. The compiler automatically sees this declaration and places the memory space on the stack. In cases where the arrays are large, the compiler can move the memory requirement to the heap. Each compiler has its own threshold for deciding whether memory should be allocated on the heap or the stack. If the compiler moves a memory location to the heap, only one thread has a pointer to that location. Essentially, it is private, even if it resides in shared memory.
8. Advanced OpenMP Usage Examples
For the y faces, we define a static pointer to a pointer (static double **yface) so that all threads can access the same pointer. In this case, only one thread must perform this memory allocation, and all other threads can access this pointer and the memory itself. In this example, you can use Figure 7.7 to see the different memory sharing options. In this case, you would go to Parallel Region -> C Subroutine and select one of the file-scoped variables, extern or static, to make the pointer shared between threads. It's easy to make mistakes here, such as in variable scope, memory allocation, or synchronization. For example, what happens if we simply define a regular double **yfaces pointer? Now each thread will have its own private pointer, but memory will only be allocated to one of them. The pointer for the second thread will point to nothing, which will cause an error when using it.
In Figure Figure 7.13 shows the performance of the threaded version of the code on a Skylake Gold processor. For a small number of threads, we achieve a superlinear speedup before dropping off at more than eight threads. This superlinear speedup is sometimes due to improved cache performance, as data is shared between threads or processors.
8. Advanced OpenMP Usage Examples
Fig. 7.13 The thread-based version of the split stencil has superlinear speedup for 2–8 threads
Definition: Sublinear speedup is performance that exceeds the ideal scaling curve for strong scaling. This can occur because smaller array sizes fit into a higher cache level, resulting in improved cache performance.
8. Advanced OpenMP Usage Examples
Kahan Summation Implementation with OpenMP Threading
For the high-precision Kahan summation algorithm presented in Section 5.7, we cannot use a pragma to force the compiler to generate a multithreaded implementation due to loop dependencies. Therefore, we will follow a similar algorithm to the vectorized implementation in Section 6.3.4. In the first phase of the computation, we first sum the values in each thread. Then, we sum the values across all threads to obtain the final sum, as shown in the following listing.
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
Streaming Implementation of the Prefix Scan Algorithm
In this section, we consider a streaming implementation of the prefix scan operation. The prefix scan operation, introduced in Section 5.6, is important for algorithms with irregular data. This is because the count used to determine the starting location for ranks or threads allows the remaining computations to be performed in parallel. As discussed in this section, prefix scans can also be performed in parallel, providing another benefit of parallelization. The implementation process consists of three phases.
The implementation described in Listing 7.22 works for a sequential application and when called from an OpenMP parallel region. The benefit of this is that it is possible to use the code in the listing for both sequential and flow cases, reducing the duplication of code required for the operation.
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
8. Advanced OpenMP Usage Examples
This algorithm should theoretically scale as follows:
Parallel_timer = 2 * serial_time/nthreads
The performance of the Skylake Gold 6152 architecture peaks at approximately 44 threads, which is 9.4 times faster than the serial version.
9. Flow-generation tools needed for sustainable implementations
Developing a robust OpenMP implementation is difficult without specialized tools for detecting thread race conditions and performance bottlenecks. The importance of using tools increases significantly as you strive to achieve a higher-performance OpenMP implementation. Both commercial and publicly available tools exist. A typical list of tools when integrating advanced OpenMP implementations into your application includes:
The first two tools were described in previous chapters; we refer you to them. In this section, we will discuss the last two tools, as they are more relevant to OpenMP applications. These tools are essential for identifying bottlenecks and understanding their location within your application, and therefore, for knowing the best place to begin making effective code changes.
9. Flow-generation tools needed for sustainable implementations
Using the Allinea/ARM MAP Profiler to Quickly Get a High-Level Profile of Your Application
One of the best tools for obtaining a high-level profile of your application is the Allinea/ARM MAP profiler. Figure 7.14 shows a simplified view of its interface. For an OpenMP application, it displays thread startup and wait costs, highlights application bottlenecks, and displays the amount of useful CPU floating-point memory used. This profiler makes it easy to compare results obtained before and after code changes. Allinea/ARM MAP is excellent for providing a quick, high-level overview of your application. However, many other profilers can be used in addition to it. Some of them are discussed in Section 17.3.
9. Flow-generation tools needed for sustainable implementations
Figure 7.14 Results from the Allinea/ARM MAP profiler, showing that the majority of the computational time is spent in a specific line of code. We often use indicators like these to show the location of bottlenecks.
9. Flow-generation tools needed for sustainable implementations
Finding Thread Race Conditions with Intel® Inspector
In OpenMP implementations, it's important to find and fix thread race conditions to create a robust, production-quality application. Tooling is essential for this purpose, as even the best programmer can't catch every thread race condition. As an application scales, memory errors become more frequent and can cause the application to crash. Detecting these memory errors early saves time and energy in future runs.
There are few tools that are effective at identifying thread race conditions. We demonstrate the use of one such tool, Intel® Inspector, to detect and pinpoint the locations of these race conditions. Having tools for understanding thread memory race conditions is also helpful when scaling to a larger number of threads. Figure 7.15 shows a sample screenshot of Intel® Inspector.
9. Flow-generation tools needed for sustainable implementations
Figure 7.15: Intel® Inspector report showing thread race detections. Here, the items listed as "Data race" under the "Type" heading in the top-left pane show all locations where a race condition currently exists.
9. Flow-generation tools needed for sustainable implementations
Before making changes to the original application, regression testing is crucial. Ensuring correctness is crucial for the successful implementation of OpenMP threading. It is impossible to implement correct OpenMP code if the application or the entire routine is not in a proper working state. This also requires that the section of code involving OpenMP threading also be regression tested. Without the ability to conduct regression testing, it becomes difficult to achieve consistent results. Therefore, these tools, along with regression testing, enable a deeper understanding of dependencies, efficiency, and correctness in most applications.
10. Example of a support algorithm based on operational tasks
The task-based parallel strategy was first introduced in Chapter 1 and illustrated in Figure 1.25. Using a task-based approach, you can divide work into individual tasks, which can then be distributed to separate processes. Many algorithms are more naturally expressed in terms of the task-based approach. OpenMP has supported this type of approach since version 3.0. Subsequent releases of the standard have made further improvements to the task-based model. In this section, we present a simple task-based algorithm to illustrate the methods in OpenMP.
One approach to a reproducible global sum is to sum the values pairwise. The conventional array approach requires allocating a working array and some complex indexing logic. Using the task-based approach, as shown in Figure 1.25, 7.16 avoids the need for a working array by recursively splitting the data in half in the descending loop until an array length of 1 is reached, and then summing the pairs in the ascending loop.
10. Example of a support algorithm based on operational tasks
Fig. 7.16. The operational task-based implementation recursively splits the array in half in a downward loop. Once the array size is 1, the task sums the data pairs in an upward loop.
10. Example of a support algorithm based on operational tasks
Listing 7.23 shows the code for the task-oriented approach. The spawning of the operational task must be performed in a parallel section, but only by a single thread, leading to nested pragma blocks in lines 8 through 14.
10. Example of a support algorithm based on operational tasks
Achieving good performance with an operational task-based algorithm requires significantly more tuning to prevent the creation of too many threads and maintain task granularity at a reasonable level. For some algorithms, operational task-based algorithms are a much more appropriate parallel strategy.
11. Exercises
1. Convert the vector addition example from Listing 7.8 to high-level OpenMP, following the instructions in Section 7.2.2.
2. Write a procedure to obtain the maximum value in an array. Add an OpenMP pragma to add thread parallelism to the procedure.
3. Write a high-level OpenMP version of the reduce from the previous exercise.
We've covered a significant amount of material in this chapter. This solid foundation will help you develop an efficient OpenMP application.