Is Array Reduction Possible in OpenMP, and How Can It Be Achieved?

Array Reduction in OpenMP

Problem:

Parallelizing a program requires array reduction but it is believed to be impossible in OpenMP. Is there an alternative?

Answer:

Yes, array reduction is possible in OpenMP. Here are two alternative methods:

Method 1: Private Sum Reduction with Critical Section

• Create private versions of the array in each thread.
• Perform the reductions in parallel.
• Merge the values in a critical section to preserve correct results.

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
#pragma omp parallel
{
    int S_private[10] = {0};
    #pragma omp for
    for (int n=0 ; n<10 ; ++n ) {
        for (int m=0; m<=n; ++m){
            S_private[n] += A[m];
        }
    }
    #pragma omp critical
    {
        for(int n=0; n<10; ++n) {
            S[n] += S_private[n];
        }
    }
}

Method 2: Private Sum Reduction without Critical Section

• Create a private array with dimensions [10 * nthreads].
• Perform the reductions in parallel and store the results in the private array.
• Merge the values into the original array without a critical section.

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
int *S_private;
#pragma omp parallel
{
    const int nthreads = omp_get_num_threads();
    const int ithread = omp_get_thread_num();

    #pragma omp single 
    {
        S_private = new int[10*nthreads];
        for(int i=0; i<(10*nthreads); i++) S_private[i] = 0;
    }
    #pragma omp for
    for (int n=0 ; n<10 ; ++n )
    {
        for (int m=0; m<=n; ++m){
            S_private[ithread*10+n] += A[m];
        }
    }
    #pragma omp for
    for(int i=0; i<10; i++) {
        for(int t=0; t<nthreads; t++) {
            S[i] += S_private[10*t + i];
        }
    }
}
delete[] S_private;

The above is the detailed content of Is Array Reduction Possible in OpenMP, and How Can It Be Achieved?. For more information, please follow other related articles on the PHP Chinese website!