Równoległe sumy sumaryczne (przedrostki) w OpenMP: przekazywanie wartości między wątkami
Załóżmy, że mam funkcjęf(i)
który zależy od indeksui
(wśród innych wartości, których nie można wstępnie obliczyć). Chcę wypełnić tablicęa
po to abya[n] = sum(f(i)) from i=0 to n-1
.
Edytować: Po komentarzu Hristo Ilieva zdałem sobie sprawę z tego, co robięsuma skumulowana / prefiks.
Można to zapisać w kodzie jako
float sum = 0;
for(int i=0; i<N; i++) {
sum += f(i);
a[i] = sum;
}
Teraz chcę użyć OpenMP, aby to zrobić równolegle. Jednym ze sposobów, w jaki mogę to zrobić z OpenMP, jest zapisanie wartości dlaf(i)
równolegle, a następnie zadbaj o zależność w sposób seryjny. Jeślif(i)
jest powolną funkcją, więc może działać dobrze, ponieważ pętla nierównoległa jest prosta.
#pragma omp parallel for
for(int i=0; i<N; i++) {
a[i] = f(i);
}
for(int i=1; i<N; i++) {
a[i] += a[i-1];
}
Ale można to zrobić bez nierównoległej pętli z OpenMP. Rozwiązanie, które wymyśliłem, jest skomplikowane i być może hackish. Więc moje pytanie brzmi, czy istnieje prostszy, mniej skomplikowany sposób na zrobienie tego z OpenMP?
Poniższy kod zasadniczo uruchamia pierwszy kod, który podałem dla każdego wątku. Wynikiem tego są wartościa
w danym wątku są poprawne do stałej. Zapisuję sumę dla każdego wątku do tablicysuma
znthreads+1
elementy. To pozwala mi komunikować się między wątkami i określać stałe przesunięcie dla każdego wątku. Następnie poprawiam wartościa[i]
z przesunięciem.
float *suma;
#pragma omp parallel
{
const int ithread = omp_get_thread_num();
const int nthreads = omp_get_num_threads();
const int start = ithread*N/nthreads;
const int finish = (ithread+1)*N/nthreads;
#pragma omp single
{
suma = new float[nthreads+1];
suma[0] = 0;
}
float sum = 0;
for (int i=start; i<finish; i++) {
sum += f(i);
a[i] = sum;
}
suma[ithread+1] = sum;
#pragma omp barrier
float offset = 0;
for(int i=0; i<(ithread+1); i++) {
offset += suma[i];
}
for(int i=start; i<finish; i++) {
a[i] += offset;
}
}
delete[] suma;
Prostym testem jest tylko ustawienief(i) = i
. Wtedy rozwiązanie jesta[i] = i*(i+1)/2
(aw nieskończoności jest-1/12).