Równoległe zagnieżdżanie dla pętli w odniesieniu do symetrii wszystkich najbardziej zgodnych z C++/OpenMP

Question

Mam prosty problem porównywania wszystkich elementów ze sobą. Samo porównanie jest symetryczne, dlatego nie trzeba tego robić dwa razy.

Poniższy przykład kodu pokazuje, co szukam pokazując wskaźników z dostępnych elementów:

int n = 5; 
for (int i = 0; i < n; i++) 
{ 
    for (int j = i + 1; j < n; j++) 
    { 
     printf("%d %d\n", i,j); 
    } 
} 

wyjście jest:

0 1 
0 2 
0 3 
0 4 
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 

Więc każdy element jest porównywana do siebie raz . Kiedy chcę zrównoleglić ten kod, mam problem, że najpierw muszę trzymać się dynamicznego szeregowania, ponieważ czas obliczania każdej iteracji zmienia się w ogromnym stopniu I nie mogę użyć zwinięcia z powodu faktu, że zagnieżdżone iteracje są indeksowane. zależne od zewnętrznej pętli.

Zastosowanie zewnętrznej pętli może prowadzić do wykonania pojedynczego rdzenia na końcu, podczas gdy użycie tego w pętli wewnętrznej może prowadzić do takich wykonań w każdej iteracji zewnętrznej pętli.

Czy istnieje bardziej wyrafinowany sposób robienia/porównywania tego?

Answer 1

Nie myślałem o tym dokładnie, ale ty można spróbować podejścia takiego też:

int total = n * (n-1)/2; // total number of combinations 
#pragma omp parallel for 
for (int k = 0; k < total; ++k) { 
    int i = first(k, n); 
    int j = second(k, n, i); 
    printf("%d %d\n", i,j); 
} 

int first(int k, int n) { 
    int i = 0; 
    for (; k >= n - 1; ++i) { 
    k -= n - 1; 
    n -= 1; 
    } 
    return i; 
} 

int second(int k, int n, int i) { 
    int t = i * (2*n - i - 1)/2; 
    return (t == 0 ? k + i + 1 : (k % t) + i + 1); 
} 

Answer 2

istocie, średnia OpenMP mówi na upadek, że:

Ilość iteracji dla każdego powiązanego pętli obliczonego przed wejściem do pętli peryferyjnych. Jeśli wykonanie dowolnej powiązanej pętli zmieni dowolną z wartości użytych do obliczenia dowolnej liczby iteracji, wówczas zachowanie nie jest określone.

Nie można więc zwinąć pętli, co byłoby najprostszym sposobem. Jednakże, ponieważ nie jesteś szczególnie zainteresowany w kolejności pary indeksów są obliczane można zmienić nieco swoje pętle następująco:

for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n/2; j++) { 
     int ii, jj; 
     if (j < i) { 
      ii = n - 1 - i; 
      jj = n - 1 - j; 
     } 
     else { 
      ii = i; 
      jj = j + 1; 
     } 
     printf("%d %d\n", ii, jj); 
    } 
} 

To powinno dać wszystkie pary, które chcesz, w nieco zmutowana kolejność, ale z ustalonymi granicami iteracji, które pozwalają na zrównoważoną równoległość, a nawet pętlę, jeśli chcesz. Po prostu, jeśli n jest parzyste, kolumna odpowiadająca n/2 będzie wyświetlana dwa razy, więc albo żyjesz z nią, albo nieznacznie modyfikujesz algorytm, aby tego uniknąć ...

Answer 3

już wcześniej miał dobre wyniki z następujących czynności:

#pragma omp parallel for collapse(2) 
for (int i = 0; i < n; ++i) { 
     for (int j = 0; j < n; ++j) { 
       if (j <= i) 
         continue; 
       printf("%d %d\n", i, j); 
     } 
} 

pamiętam, że printf nie robić żadnych równoległe obciążenie właśnie, tak byłoby najlepiej, gdyby profilowałeś go w swojej pracy. Możesz spróbować dodać schedule(dynamic, 10) lub coś większego niż 10 w zależności od liczby wykonywanych iteracji.