Учитывая 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();
}
Я считаю, что лучший метод может быть найден с использованием задач, которые не помещают нити, которые не используются в цикле занятости.
