zagnieżdżone pętle, równoległość w pętli wewnętrznej, ponowne wykorzystanie wątków

Question

Zastrzeżenie: poniższy przykład jest tylko fałszywym przykładem, aby szybko zrozumieć problem. Jeśli myślisz o problemie świata rzeczywistego, pomyśl o dynamicznym programowaniu.

problem: Mamy n * m matrycę i chcemy kopiowanie elementów z poprzedniego rzędu, jak w poniższym kodzie:

for (i = 1; i < n; i++) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 

Metoda: zewnętrzne iteracji pętli musiał zostaną wykonane w kolejności, zostaną wykonane sekwencyjnie. Pętlę wewnętrzną można zsynchronizować. Chcielibyśmy zminimalizować obciążenie związane z tworzeniem i zabijaniem wątków, więc chcielibyśmy stworzyć zespół wątków tylko raz, jednak wydaje się to niemożliwym zadaniem w OpenMP.

#pragma omp parallel private(j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for scheduled(dynamic) 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

Kiedy stosujemy ordered opcję na zewnętrznej pętli, kod zostanie wykonany sekwencyjny sposób, więc nie będzie przyrost wydajności. Szukam rozwiązania dla powyższego scenariusza, nawet jeśli musiałbym użyć jakiegoś obejścia.

Dodaję mój aktualny kod. Jest to faktycznie wolniejsze niż seq. wersja. Prosimy o zapoznanie się:

/* load input */ 
for (i = 1; i <= n; i++) 
    scanf ("%d %d", &in[i][W], &in[i][V]); 

/* init */ 
for (i = 0; i <= wc; i++) 
    a[0][i] = 0; 

/* compute */ 
#pragma omp parallel private(i,w) 
{ 
    for(i = 1; i <= n; ++i) // 1 000 000 
    { 
     j=i%2; 
     jn = j == 1 ? 0 : 1; 

     #pragma omp for 
     for(w = 0; w <= in[i][W]; w++) // 1000 
      a[j][w] = a[jn][w]; 

     #pragma omp for 
     for(w = in[i][W]+1; w <= wc; w++) // 350 000 
      a[j][w] = max(a[jn][w], in[i][V] + a[jn][w-in[i][W]]); 
    } 
} 

chodzi o pomiar, używam coś takiego:

double t; 
t = omp_get_wtime(); 
// ... 
t = omp_get_wtime() - t; 

Answer 1

Podsumowując Zrównoleglanie w OpenMP w tym konkretnym przypadku: To nie jest tego warte.

Dlaczego? Operacje w wewnętrznych pętlach są proste. Kod został skompilowany z -O3, więc wywołanie max() zostało prawdopodobnie zastąpione kodem funkcji. Napowietrzna domniemana bariera jest prawdopodobnie wystarczająco wysoka, aby zrekompensować wzrost wydajności, a ogólny narzut jest wystarczająco duży, aby kod równoległy był nawet wolniejszy niż kod sekwencyjny. Dowiedziałem się też, nie ma prawdziwy wzrost wydajności w taki konstrukt:

#pragma omp parallel private(i,j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

bo to wydajność jest podobna do tej jednej

for (i = 1; i < n; i++) 
{ 
    #pragma omp parallel for private(j) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
} 

dzięki wbudowanym w wątku ponowne w GCC libgomp, zgodnie do tego artykułu: http://bisqwit.iki.fi/story/howto/openmp/

Ponieważ zewnętrzna pętla nie może być paralelizowana (bez opcji ordered) wygląda na to, że nie ma możliwości znaczącego poprawienia wydajności p omawiany rogram przy użyciu OpenMP. Jeśli ktoś czuje, że zrobiłem coś złego i jest to możliwe, chętnie obejrzę i przetestuję rozwiązanie.