Parallelizing Reductions Using OpenMP

Parallelizing Reductions Using OpenMP

Not all variables can be scoped as either shared or private. The most obvious example of a more complex situation is a reduction. Listing 7.26 shows an example of a reduction. The variable total is computed by adding all the elements in an array.

Listing 7.26   Loop Containing a Reduction Operation

double calc( double* array, int length )

{

double total = 0.0;

for ( int i=0; i<length; i++ )

{

total += array[i];

}

return total;

}

The result returned by the variable total will need contributions from every thread. One way of making this happen would be to serialize access to the variable using a mutex or an atomic operation, but this would render any parallelization of the loop pointless.

The OpenMP specification allows for a reduction operation to be applied over a par-allel region. The reduction gives each thread a private copy of the reduction variable, which it uses for computation in the parallel region. At the end of the parallel region, the private copies of the reduction variable are combined to produce the final result. The syntax for the reduction clause is reduction(operator:variable). Listing 7.27 shows the loop parallelized using a reduction clause.

Listing 7.27   Loop Containing a Reduction Operation

double calc( double* array, int length )

{

double total = 0.0;

#pragma omp parallel for reduction( +: total ) for ( int i=0; i<length; i++ )

{

total += array[i];

}

return total;

}

The operator to which the reduction applies is not limited to additions. It includes a number of other operations such as subtraction; multiplication; the bitwise operations AND, OR, and XOR; and the logical operations AND and OR.