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
Related Links
