Worksharing Using OpenMP*

Basics of Compilation

Using the OpenMP* pragmas requires an OpenMP-compatible compiler and thread-safe libraries. Adding the [Q]openmp option to the compiler instructs the compiler to pay attention to the OpenMP* pragmas and to insert threads. If you omit the [Q]openmp option, the compiler will ignore OpenMP* pragmas, which provides a very simple way to generate a single-threaded version without changing any source code.

For conditional compilation, the compiler defines the _OPENMP macro. If needed, the macro can be tested as shown in the following example.

#ifdef _OPENMP
   fn(); 
#endif

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 examples illustrate a good starting point.

In the first example, the following loop clips an array to the range from 0 to 255.

// clip an array to 0 <= x <= 255 
for (i=0; i < numElements; i++) {
  if (array[i] < 0)
  array[i] = 0;
  else if (array[i] > 255)
    array[i] = 255; 
}

You can thread it using a single OpenMP* pragma; insert the pragma immediately prior to the loop:

#pragma omp parallel for 
for (i=0; i < numElements; i++) {
  if (array[i] < 0)
  array[i] = 0;
  else if (array[i] > 255)
    array[i] = 255; 
}

In the second example, the loop generates a table of square roots for the numbers from 0 to 100.

double value; 
double roots[100]; 
for (value = 0.0; value < 100.0; value ++) { roots[(int)value] = sqrt(value); }

Thread the loop by changing the loop variable to a signed integer or unsigned integer and inserting a #pragma omp parallel pragma.

int value; 
double roots[100]; 
#pragma omp parallel for 
for (value = 0; value < 100; value ++) { roots[value] = sqrt((double)value); }

Avoiding Data Dependencies and Race Conditions

When a loop meets all five loop restrictions (listed above) and the compiler threads the loop, the loop still might 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) read or write the same location in shared memory. Consider the following example that calculates factorials.

// 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 the threading 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 difficult to detect because, for a given case or system, the threads might win the race in the order that happens to make the program function correctly. Because a program works once does not mean that the program will work under all conditions. Testing your program on various machines, some with Intel® Hyper-Threading Technology and some with multiple physical processors, is a good starting point to help identify race conditions.

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; however, thread checking tools can help.

Managing Shared and Private Data

Nearly every loop (in real applications) reads from or writes to memory; it's your responsibility, as the developer, to instruct the compiler what memory should be shared among the threads and what memory should be kept private. When memory is identified as shared, all threads access the 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, the 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 two ways:

• Declare the variable inside the loop-really inside the parallel OpenMP* pragma-without the static keyword.

• Specify the private clause on an OpenMP* pragma.

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

// 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 solves the problem.

#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); 
}

The temp variable can also be made private in the following way:

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

Every time you use 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. OpenMP* provides the reduction clause that is used to efficiently combine the mathematical reduction of one or more variables in a loop. The following example demonstrates how the loop can use 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]; }

In the case of the example listed above, the reduction 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 reduction operations, along with their initial values (mathematical identity values).

Multiple reductions in a loop are possible by specifying comma-separated variables and operations on a given parallel construct. Reduction variables must meet the following requirements:

• can be listed in just one reduction.

• cannot be declared constant.

• cannot be declared private in the parallel construct.

Load Balancing and 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 often 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 is 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 might be the case that the set of the first half of the loop consumes about as much time as the second half. In contrast, it might be impossible to find sets of loop iterations that have a uniform execution time. Regardless of the case, you should provide this extra loop scheduling information to OpenMP* so it can better distribute the iterations of the loop across the threads (and therefore processors) for optimum load balancing.

If you know that all loop iterations consume roughly the same amount of time, the OpenMP* schedule clause should be used to distribute the iterations of the loop among the threads in roughly equal amounts via the scheduling policy. In addition, you need to minimize the chances of memory conflicts that may arise because of false sharing due to using large chunks. This behavior 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 might be best for load balancing may be bad for memory performance. You must strike a balance between optimal memory usage and optimal load balancing by measuring the performance to see what method produces the best results.

Use the following general form on the parallel construct to schedule an OpenMP* loop:

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

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

Assume that you want to parallelize the following loop.

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

As written, the loop contains a data dependency, making it impossible to parallelize without a change. The new loop, shown below, fills the array in the same manner, but without data dependencies. The new loop benefits from using the SIMD instructions generated by the compiler.

#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;

OpenMP* Tasking Model

The OpenMP* tasking model enables you to parallelize a large range of applications. You can use several OpenMP* pragmas for tasking.

void test1(LIST *head) {
  #pragma intel omp parallel shared(head) {
    #pragma omp single {
      LIST *p = head; 
      while (p != NULL) {
        #pragma omp task firstprivate(p) { do_work1(p); }
        p = p->next;
     }
   }
}

#pragma omp parallel shared(data) {  
  #pragma omp single private(i) {
    for (i=0, i<N; i++) {
      #pragma omp task firstprivate(i shared(data) { do_work(data(i)); }
    }
  } 
}

#pragma omp task { 
  ...
  #pragma omp task { do_work1(); }
  #pragma omp task {  
    ...
    #pragma omp task {  do_work2(); }
    ...
  }
  #pragma omp taskwait
  ... 
}