Учитывая n частичные суммы, можно суммировать все частичные суммы за log2 параллельных шагов. Например, предположим, что имеется восемь потоков с восемью частичными суммами: s0, s1, s2, s3, s4, s5, s6, s7. Это можно уменьшить с помощью log2(8) = 3 последовательных шагов, подобных этому;

thread0     thread1    thread2    thread4
s0 += s1    s2 += s3   s4 += s5   s6 +=s7
s0 += s2    s4 += s6
s0 += s4

Я хотел бы сделать это с помощью OpenMP, но не хочу использовать предложение OpenMP reduction. Я придумал решение, но я думаю, что лучшее решение можно найти, возможно, используя предложение OpenMP task.

Это более общий подход, чем скалярное сложение. Позвольте мне выбрать более полезный случай: сокращение массива (см. здесь , здесь, и здесь для получения дополнительной информации редукции массива).

Допустим, я хочу уменьшить массив a. Вот код, который заполняет частные массивы параллельно для каждого потока.

int bins = 20;
int a[bins];
int **at;  // array of pointers to arrays
for(int i = 0; i<bins; i++) a[i] = 0;
#pragma omp parallel
{
    #pragma omp single   
    at = (int**)malloc(sizeof *at * omp_get_num_threads());        
    at[omp_get_thread_num()] = (int*)malloc(sizeof **at * bins);
    int a_private[bins];
    //arbitrary function to fill the arrays for each thread
    for(int i = 0; i<bins; i++) at[omp_get_thread_num()][i] = i + omp_get_thread_num();
}

На данный момент у меня есть массив указателей на массивы для каждого потока. Теперь я хочу сложить все эти массивы и записать окончательную сумму в a. Вот решение, которое я придумал.

#pragma omp parallel
{
    int n = omp_get_num_threads();
    for(int m=1; n>1; m*=2) {
        int c = n%2;
        n/=2;
        #pragma omp for
        for(int i = 0; i<n; i++) {
            int *p1 = at[2*i*m], *p2 = at[2*i*m+m];
            for(int j = 0; j<bins; j++) p1[j] += p2[j];
        }
        n+=c;
    }
    #pragma omp single
    memcpy(a, at[0], sizeof *a*bins);
    free(at[omp_get_thread_num()]);
    #pragma omp single
    free(at);
}

Позвольте мне попытаться объяснить, что делает этот код. Предположим, есть восемь потоков. Давайте определим оператор += для суммирования по массиву. например s0 += s1 это

for(int i=0; i<bins; i++) s0[i] += s1[i]

тогда этот код будет делать

n   thread0     thread1    thread2    thread4
4   s0 += s1    s2 += s3   s4 += s5   s6 +=s7
2   s0 += s2    s4 += s6
1   s0 += s4

Но этот код не идеален, как хотелось бы.

Одна из проблем заключается в том, что существует несколько неявных барьеров, которые требуют синхронизации всех потоков. В этих барьерах не должно быть необходимости. Первый барьер - между заполнением массивов и сокращением. Второй барьер находится в #pragma omp for объявлении сокращения. Но я не могу использовать предложение nowait с этим методом для устранения барьера.

Другая проблема в том, что есть несколько потоков, которые не нужно использовать. Например с восемью потоками. На первом этапе сокращения требуется только четыре потока, на втором этапе - два потока, а на последнем этапе - только один поток. Однако этот метод задействует в редукции все восемь потоков. Хотя другие потоки в любом случае мало что делают и должны идти прямо к барьеру и ждать, так что это, вероятно, не представляет большой проблемы.

Мне кажется, что лучший метод можно найти с помощью предложения omp task. К сожалению, у меня мало опыта работы с предложением task, и все мои усилия до сих пор приводили к сокращению лучше, чем то, что у меня было сейчас, потерпело неудачу.

Может ли кто-нибудь предложить лучшее решение для сокращения логарифмического времени, например, Предложение OpenMP task?

Я нашел способ, который решает проблему с барьером. Это уменьшается асинхронно. Единственная оставшаяся проблема заключается в том, что он по-прежнему помещает потоки, которые не участвуют в сокращении, в цикл занятости. Этот метод использует что-то вроде стека для отправки указателей в стек (но никогда не выталкивает их) в критических секциях (это был один из ключей как критические секции не имеют неявных барьеров. Стек работает последовательно, а сокращение - параллельно.

Вот рабочий пример.

#include <stdio.h>
#include <omp.h>
#include <stdlib.h>
#include <string.h>

void foo6() {
    int nthreads = 13;
    omp_set_num_threads(nthreads);
    int bins= 21;
    int a[bins];
    int **at;
    int m = 0;
    int nsums = 0;
    for(int i = 0; i<bins; i++) a[i] = 0;
    #pragma omp parallel
    {
        int n = omp_get_num_threads();
        int ithread = omp_get_thread_num();
        #pragma omp single
        at = (int**)malloc(sizeof *at * n * 2);
        int* a_private = (int*)malloc(sizeof *a_private * bins);

        //arbitrary fill function
        for(int i = 0; i<bins; i++) a_private[i] = i + omp_get_thread_num();

        #pragma omp critical (stack_section)
        at[nsums++] = a_private;

        while(nsums<2*n-2) {
            int *p1, *p2;
            char pop = 0;
            #pragma omp critical (stack_section)
            if((nsums-m)>1) p1 = at[m], p2 = at[m+1], m +=2, pop = 1;
            if(pop) {
                for(int i = 0; i<bins; i++) p1[i] += p2[i];
                #pragma omp critical (stack_section)
                at[nsums++] = p1;
            }
        }

        #pragma omp barrier
        #pragma omp single
        memcpy(a, at[2*n-2], sizeof **at *bins);
        free(a_private);
        #pragma omp single
        free(at);
    }
    for(int i = 0; i<bins; i++) printf("%d ", a[i]); puts("");
    for(int i = 0; i<bins; i++) printf("%d ", (nthreads-1)*nthreads/2 +nthreads*i); puts("");
}

int main(void) {
    foo6();
}

Я считаю, что можно найти лучший метод с использованием задач, которые не помещают неиспользуемые потоки в цикл занятости.