Parallelisieren verschachtelte für die Schleife in Bezug auf die Symmetrie aller -gegenüber-allen Vergleich mit C++/OpenMP

Question

Ich habe das einfache Problem, alle Elemente miteinander zu vergleichen. Der Vergleich selbst ist symmetrisch und muss daher nicht zweimal durchgeführt werden.

Das folgende Codebeispiel zeigt, was ich suche die Indizes der Zugriff auf Elemente durch zeigt:

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

Die Ausgabe lautet:

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

So wird jedes Element im Vergleich zu jeder einmal andere . Wenn ich diesen Code parallelisieren möchte, habe ich das Problem, dass ich mich zuerst an die dynamische Terminplanung halten muss, da die Berechnungszeit jeder Iteration sehr stark variiert UND ich Kollaps nicht verwenden kann, da die verschachtelten Iterationen indexiert sind. abhängig von der äußeren Schleife. Die Verwendung von #pragma omp parallel for schedule(dynamic, 3) für die äußere Schleife kann zu Einzelkernausführungen am Ende führen, während die Verwendung für die innere Schleife zu solchen Ausführungen innerhalb jeder Iteration der äußeren Schleife führen kann.

Gibt es eine ausgefeiltere Art, dies zu tun/parallelisieren?

Answer 1

Ich habe gedacht, es nicht gründlich, aber Sie versuchen können, wie dies einige Ansatz zu:

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

Tatsächlich ist der OpenMP Standard sagt, die für den Zusammenbruch:

Die Iterationszahl für jede zugeordnete Schleife vor dem Eintritt berechnet auf die äußerste Schleife. Wenn die Ausführung einer zugeordneten Schleife einen der Werte ändert, die zum Berechnen einer der Iterationszählungen verwendet wurden, ist das Verhalten nicht angegeben.

So können Sie Ihre Schleifen nicht zusammenbrechen, was der einfachste Weg gewesen wäre. Da jedoch in der Reihenfolge, sind die Paare von Indizes nicht besonders interessiert sind, berechnet wird, können Sie ein wenig Ihre Loops wie folgt ändern:

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); 
    } 
} 

Dies sollten Sie alle Paare geben Sie wollen, in einem etwas Mangled Order, aber mit festen Iterationslimits, die eine ausgeglichene Parallelisierung ermöglichen, und sogar Schleifenzusammenbrüche, wenn Sie möchten. wenn n gerade einfach ist, entspricht die Spalte n/2 wird zweimal angezeigt werden, so Sie entweder mit ihr leben oder Sie leicht den Algorithmus ändern, um das zu vermeiden ...

Answer 3

ich habe bisher gute Ergebnisse mit den folgenden:

#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); 
     } 
} 

sie daran erinnern, dass printf keine parallele Arbeitsbelastung gerade nicht tun, so wäre es am besten, wenn Sie haben es auf Ihre spezifische Arbeit hin profiliert. Sie können versuchen, schedule(dynamic, 10) oder etwas größer als 10 hinzuzufügen, abhängig davon, wie viele Iterationen Sie ausführen.