Dr. Dobb's | Getting Started with OpenMP

Getting Started with OpenMP

Tools like OpenMP can make threading a lot easier

December 24, 2008
URL:http://www.drdobbs.com/getting-started-with-openmp/212501973

As you probably know by now, to get the maximum performance benefit from a processor with Hyper-Threading Technology, an application needs to be executed in parallel. Parallel execution requires threads, and threading an application is not trivial. What you may not know is that tools like OpenMP can make the process a lot easier.

A Quick Introduction to OpenMP

The designers of OpenMP wanted to provide an easy method to thread applications without requiring that the programmer know how to create, synchronize, and destroy threads or even requiring him or her to determine how many threads to create. To achieve these ends, the OpenMP designers developed a platform-independent set of compiler pragmas, directives, function calls, and environment variables that explicitly instruct the compiler how and where to insert threads into the application. Most loops can be threaded by inserting only one pragma right before the loop. Further, by leaving the nitty-gritty details to the compiler and OpenMP, you can spend more time determining which loops should be threaded and how to best restructure the algorithms for maximum performance. The maximum performance of OpenMP is realized when it is used to thread "hotspots," the most time-consuming loops in your application.

The power and simplicity of OpenMP is best demonstrated by looking at an example. The following loop converts a 32-bit RGB (red, green, blue) pixel to an 8-bit gray-scale pixel. The one pragma, which has been inserted immediately before the loop, is all that is needed for parallel execution.


#pragma omp parallel for
for (i=0; i < numPixels; i++)

{
   pGrayScaleBitmap[i] = (unsigned BYTE)
            (pRGBBitmap[i].red * 0.299 +
             pRGBBitmap[i].green * 0.587 +
             pRGBBitmap[i].blue * 0.114);
}

Let's take a closer look at the loop. First, the example uses 'work-sharing,' the general term used in OpenMP to describe distribution of work across threads. When work-sharing is used with the for construct, as shown in the example, the iterations of the loop are distributed among multiple threads so that each loop iteration is executed exactly once and in parallel by one or more threads. OpenMP determines how many threads to create and how to best create, synchronize, and destroy them. All the programmer needs to do is to tell OpenMP which loop should be threaded.

OpenMP places the following five restrictions on which loops can be threaded:

The loop variable must be of type signed integer. Unsigned integers, such as DWORD's, will not work.
The comparison operation must be in the form loop_variable <, <=, >, or >= loop_invariant_integer
The third expression or increment portion of the for loop must be either integer addition or integer subtraction and by a loop invariant value.
If the comparison operation is < or <=, the loop variable must increment on every iteration, and conversely, if the comparison operation is > or >=, the loop variable must decrement on every iteration.
The loop must be a basic block, meaning no jumps from the inside of the loop to the outside are permitted with the exception of the exit statement, which terminates the whole application. If the statements goto or break are used, they must jump within the loop, not outside it. The same goes for exception handling; exceptions must be caught within the loop.

Although these restrictions may sound somewhat limiting, non-conforming loops can easily be rewritten to follow these restrictions.

The Basics of Compilation

Using the OpenMP pragmas requires an OpenMP-compatible compiler and thread-safe libraries. A perfect choice is the Intel C++ Compiler version 7.0 or newer. (The Intel Fortran compiler also supports OpenMP.) Adding the following command-line option to the compiler instructs it to pay attention to the OpenMP pragmas and to insert threads.

If you omit /Qopenmp on the command-line, the compiler will ignore OpenMP pragmas, providing a very simple way to generate a single-threaded version without changing any source code. The Intel C++ Compiler supports the OpenMP 2.0 specification. Be sure to browse the release notes and compatibility information supplied with the Intel C++ Compiler for the latest updates. The complete OpenMP specification is available from www.openmp.org.For conditional compilation, the compiler defines _OPENMP. If needed, this define can be tested as shown below.

 

#ifdef _OPENMP
        fn();
    #endif<

The general form of all OpenMP pragmas is:

If the line does not start with pragma omp it is not an OpenMP pragma. The full list of pragmas is located in the specification found at www.openmp.org.The C-runtime thread-safe libraries are selected using the /MD or /MDd (for debug) command-line compiler options. These options are selected, when using Microsoft Visual C++, in the Code Generation Category for C/C++ Project Settings by selecting either Multithreaded DLL or Debug Multithreaded DLL.

A Few Simple Examples

The following examples illustrate how simple OpenMP is to use. In common practice, additional issues need to be addressed, but these are great to get you going.

Problem 1: The following loop clips an array to the range 0...255. You need to thread it using an OpenMP pragma.

Solution: Simply insert the following pragma immediately before the loop.
Problem 2: The following loop generates a table of square roots for the numbers 0...100. You need to thread it using OpenMP.

Solution: The loop variable is not a signed integer, so that needs to be changed and the pragma needs to be added.

Avoiding Data Dependencies and Race Conditions

When a loop meets all five loop restrictions and the compiler threads the loop, it may still not work correctly due to the existence of data dependencies. Data dependencies exist when different iterations of a loop-more specifically a loop iteration that is executed on a different thread-reads or writes shared memory. Consider the following example that calculates factorials.


// Do NOT do this. It will fail due to data dependencies.
    // Each loop iteration writes a value that a different
    iteration reads.
    #pragma omp parallel for
    for (i=2; i < 10; i++)
    {
       factorial[i] = i * factorial[i-1];
    }

The compiler will thread this loop, but it will fail because at least one of the loop iterations is data-dependent upon a different iteration. This situation is referred to as a race condition. Race conditions can only occur when using shared resources (like memory) and parallel execution. To address this problem either rewrite the loop or pick a different algorithm, one that does not contain the race condition.Race conditions are tricky to detect because, in a given instance, the variables might "win the race" in the order tha t happens to make the program function correctly. Just because a program works once doesn't mean that it will always work. Testing your program on various machines, some with Hyper-Threading Technology and some with multiple physical processors, is a good starting point. Tools such as the Intel Thread Checker can also help, as can a sharp eye. Traditional debuggers are useless for detecting race conditions because they cause one thread to stop the "race" while the other threads continue to significantly change the runtime behavior

Managing Shared and Private Data

Nearly every loop (at least if it's a useful one) reads or writes memory, and it's the programmer's job to tell the compiler which pieces of memory should be shared among the threads and which pieces should be kept private. When memory is identified as shared, all threads access the exact same memory location. When memory is identified as private, however, a separate copy of the variable is made for each thread to access in private. When the loop ends, these private copies are destroyed. By default, all variables are shared except for the loop variable, which is private. Memory can be declared as private in the following two ways.

Declare the variable inside the loop-really inside the parallel OpenMP directive-without the static keyword.
Specify the private clause on an OpenMP directive.

The following loop fails to function correctly because the variable temp is shared. It needs to be private.


// WRONG. Fails due to shared memory.

    // Variable temp is shared among all threads, so while one thread
    // is reading variable temp another thread might be writing to it

    #pragma omp parallel for
    for (i=0; i < 100; i++)
    {
       temp = array[i];
       array[i] = do_something(temp);
    }

The following two examples both declare the variable temp as private memory, which fixes the problem.


// This works. The variable temp is now private
    #pragma omp parallel for
    for (i=0; i < 100; i++)
    {
       int temp; // variables declared within a
    parallel construct
        // are, by definition, private
       temp = array[i];
       array[i] = do_something(temp);
    }
    // This also works. The variable temp is declared private
    #pragma omp parallel for private(temp)
    for (i=0; i < 100; i++)
    {
       temp = array[i];
       array[i] = do_something(temp);
    }

Every time you instruct OpenMP to parallelize a loop, you should carefully examine all memory references, including the references made by called functions. Variables declared within a parallel construct are defined as private except when they are declared with the static declarator, because static variables are not allocated on the stack.

Reductions

Loops that accumulate a value are fairly common, and OpenMP has a specific clause to accommodate them. Consider the following loop that calculates the sum of an array of integers.


sum = 0;
    for (i=0; i < 100; i++)
    {
       sum += array[i]; 
           // this  variable needs to be shared to generate
           // the correct results, but private to avoid
           // race conditions from parallel execution
    }

The variable sum in the previous loop must be shared to generate the correct result, but it also must be private to permit access by multiple threads. To solve th is case, OpenMP provides the reduction clause that is used to efficiently combine the mathematical reduction of one or more variables in a loop. The following loop uses the reduction clause to generate the correct results.


 sum = 0;
    #pragma omp parallel for reduction(+:sum)
    for (i=0; i < 100; i++)
    {
       sum += array[i];
        }

Under the hood, OpenMP provides private copies of the variable sum for each thread, and when the threads exit, it adds the values together and places the result in the one global copy of the variable.The following table lists the possible reductions, along with the initial variables-which is also the mathematical identify value-for the temporary private variables.

Multiple reductions in a loop are possible by specifying comma-separated variables and reductions on a given parallel construct. The only requirements are:

the reduction variables can be listed in just one reduction
they cannot be declared constant, and
they cannot be declared private in the parallel construct.

Loop Scheduling

Load balancing, the equal division of work among threads, is among the most important attributes for parallel application performance. Load balancing is extremely important, because it ensures that the processors are busy most, if not all, of the time. Without a balanced load, some threads may finish significantly before others, leaving processor resources idle and wasting performance opportunities.

Within loop constructs, poor load balancing is usually caused by variations in compute time among loop iterations. It is usually easy to determine the variability of loop iteration compute time by examining the source code. In most cases, you will see that loop iterations consume a uniform amount of time. When that's not true, it may be possible to find a set of iterations that consume similar amounts of time. For example, sometimes the set of all even iterations consumes about as much time as the set of all odd iterations. Similarly it can happen that the set of the first half of the loop consumes about as much time as the second half. On the other hand, it may be impossible to find sets of loop iterations that have a uniform execution time. Regardless of which case an application falls into, you should provide this extra loop scheduling information to OpenMP so that it can better distribute the iterations of the loop across the threads (and therefore processors) for optimum load balancing.

OpenMP, by default, assumes that all loop iterations consume the same amount of time. This assumption leads OpenMP to distribute the iterations of the loop among the threads in roughly equal amounts and in such a way as to minimize the chances of memory conflicts due to false sharing. This is possible because loops generally touch memory sequentially, so splitting up the loop in large chunks -- like the first half and second half when using two threads -- will result in the least chance for overlapping memory. While this may be the best choice for memory issues, it may be bad for load balancing. Unfortunately, the reverse is also true; what may be best for load balancing may be bad for memory performance. Performance engineers, therefore, must strike a balance between optimal memory usage and optimal load balancing by measuring the performance to see what method produces the best results.

Loop scheduling information is conveyed to OpenMP on the parallel construct with the following syntax.


#pragma omp parallel for schedule(kind [, chunk size])

Four different loop scheduling types (hints) can be provided to OpenMP, as shown in the following table. The optional parameter (chunk), when specified, must be a loop-invariant positive integer.

Examples

Problem: Parallelize the following loop


for (i=0; i < NumElements; i++)
    {
       array[i] = StartVal;
       StartVal++;
    }

Solution: Watch for data dependenciesAs written, the loop contains a data dependency, making it impossible to parallelize without a quick change. The new loop, shown below, fills the array in the same manner, but without data dependencies. As a bonus, the new loop can also be written using the SIMD instructions.


 #pragma omp parallel for
     for (i=0; i < NumElements; i++)
    {
       array[i] = StartVal + i;
    }

Observe that the code is not 100% identical because the value of variable StartVal is not incremented. As a result, when the parallel loop is finished, the variable will have a value different from the one produced by the serial version. If the value of StartVal is needed after the loop, the additional statement, shown below, is needed.


// This works and is identical to the serial version.
    #pragma omp parallel for
     for (i=0; i < NumElements; i++)
    {
       array[i] = StartVal + i;
    }
    StartVal += NumElements;

Summary

OpenMP was written primarily to relieve the programmer from the details of threading, enabling a focus on the more important issues. Using the OpenMP pragmas, most loops can be threaded with one simple statement. This is the power of OpenMP and where a key benefit lies. This white paper has introduced the concepts and simpler side of OpenMP to get you started. The next two papers will build on this foundation making it possible to use OpenMP to thread more complex loops and more general constructs

References

OpenMP Specification