D. schedule-Klausel

Eine parallele Region hat mindestens eine Barriere am Ende und kann zusätzliche Barrieren darin haben. Bei jeder Barriere müssen die anderen Mitglieder des Teams warten, bis der letzte Thread eintrifft. Um diese Wartezeit zu minimieren, sollte freigegebene Arbeit verteilt werden, damit alle Threads gleichzeitig an der Barriere ankommen. Wenn einige dieser freigegebenen Arbeiten in for Konstrukten enthalten sind, kann die schedule Klausel zu diesem Zweck verwendet werden.

Wenn es wiederholte Verweise auf dieselben Objekte gibt, kann die Auswahl des Zeitplans für ein for Konstrukt hauptsächlich durch Merkmale des Speichersystems bestimmt werden, z. B. das Vorhandensein und die Größe von Caches und ob Die Speicherzugriffszeiten einheitlich oder nichtuniform sind. Solche Überlegungen können es vorzuziehen, dass jeder Thread konsistent auf denselben Satz von Elementen eines Arrays in einer Reihe von Schleifen verweist, auch wenn einigen Threads relativ weniger Arbeit in einigen Schleifen zugewiesen wird. Diese Einrichtung kann mithilfe des static Zeitplans mit den gleichen Grenzen für alle Schleifen erfolgen. Im folgenden Beispiel wird Null als untere Grenze in der zweiten Schleife verwendet, obwohl k dies natürlicher wäre, wenn der Zeitplan nicht wichtig wäre.

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

In den Beispielen für die neu Standard wird davon ausgegangen, dass der Speicherzugriff nicht die dominante Berücksichtigung ist. Sofern nicht anders angegeben, wird davon ausgegangen, dass alle Threads vergleichbare Rechenressourcen erhalten. In diesen Fällen hängt die Auswahl des Zeitplans für ein for Konstrukt von allen gemeinsam genutzten Arbeiten ab, die zwischen der nächstgelegenen vorhergehenden Barriere und entweder der implizierten Abschlussbarriere oder der nächsten bevorstehenden Barriere durchgeführt werden sollen, wenn eine nowait Klausel vorhanden ist. Für jede Art von Zeitplan zeigt ein kurzes Beispiel, wie diese Zeitplanart wahrscheinlich die beste Wahl ist. Eine kurze Diskussion folgt jedem Beispiel.

Der static Zeitplan eignet sich auch für den einfachsten Fall, einen parallelen Bereich mit einem einzelnen for Konstrukt, wobei jede Iteration dieselbe Menge Arbeit erfordert.

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

Der static Zeitplan zeichnet sich durch die Eigenschaften aus, die jeder Thread ungefähr die gleiche Anzahl von Iterationen wie jeder andere Thread erhält, und jeder Thread kann die ihm zugewiesenen Iterationen unabhängig voneinander bestimmen. Daher ist keine Synchronisierung erforderlich, um die Arbeit zu verteilen, und unter der Annahme, dass jede Iteration dieselbe Menge Arbeit erfordert, sollten alle Threads gleichzeitig abgeschlossen werden.

Bei einem Team von P-Threads lassen Sie die Obergrenze(n/p) die ganze Zahl sein, die n = p*q - r mit 0 <= r < p entspricht. Eine Implementierung des static Zeitplans für dieses Beispiel würde q Iterationen den ersten p-1-Threads und q-r Iterationen dem letzten Thread zuweisen. Eine weitere akzeptable Implementierung würde q Iterationen den ersten p-r-Threads und q-1 Iterationen den re Standard ing r Threads zuweisen. In diesem Beispiel wird veranschaulicht, warum sich ein Programm nicht auf die Details einer bestimmten Implementierung verlassen sollte.

Der dynamic Zeitplan eignet sich für den Fall eines for Konstrukts mit den Iterationen, die unterschiedliche oder sogar unvorhersehbare Arbeitsmengen erfordern.

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

Der dynamic Zeitplan zeichnet sich durch die Eigenschaft aus, dass kein Thread länger an der Barriere wartet, als es einen anderen Thread benötigt, um seine endgültige Iteration auszuführen. Diese Anforderung bedeutet, dass Iterationen jeweils jeweils threads zugewiesen werden müssen, sobald sie verfügbar sind, mit der Synchronisierung für jede Zuordnung. Der Synchronisierungsaufwand kann reduziert werden, indem eine minimale Blockgröße k größer als 1 angegeben wird, sodass Threads jeweils bis zu weniger als k re Standard zugewiesen werden. Dadurch wird sichergestellt, dass kein Thread bei der Barriere länger wartet, als ein anderer Thread benötigt, um seinen endgültigen Teil der (höchstens) k Iterationen auszuführen.

Der dynamic Zeitplan kann nützlich sein, wenn die Threads unterschiedliche Rechenressourcen erhalten, die den gleichen Effekt haben wie unterschiedliche Arbeitsmengen für jede Iteration. Ebenso kann der dynamische Zeitplan auch nützlich sein, wenn die Threads zu unterschiedlichen Zeiten an dem for Konstrukt eingehen, obwohl in einigen dieser Fälle der guided Zeitplan bevorzugt werden kann.

Der guided Zeitplan ist für den Fall geeignet, in dem die Threads zu unterschiedlichen Zeiten bei einem for Konstrukt mit jeder Iteration eingehen können, die etwa dieselbe Menge Arbeit erfordert. Diese Situation kann auftreten, wenn z. B. dem for Konstrukt ein oder mehrere Abschnitte oder for Konstrukte mit nowait Klauseln vorangestellt sind.

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

Ebenso dynamicgarantiert der guided Zeitplan, dass kein Thread länger wartet als ein anderer Thread, um seine endgültige Iteration auszuführen, oder endgültige k-Iterationen , wenn eine Blockgröße von k angegeben ist. Unter solchen Terminplänen zeichnet sich der guided Zeitplan durch die Eigenschaft aus, die für die kleinsten Synchronisierungen erforderlich ist. Bei Blockgröße k weist eine typische Implementierung q = ceiling(n/p)-Iterationen dem ersten verfügbaren Thread zu, legt n auf die Größere von n-q und p*k fest und wiederholt, bis alle Iterationen zugewiesen sind.

Wenn die Wahl des optimalen Zeitplans nicht so klar ist wie bei diesen Beispielen, ist der runtime Zeitplan praktisch für das Experimentieren mit verschiedenen Zeitplänen und Blockgrößen, ohne das Programm ändern und neu kompilieren zu müssen. Es kann auch nützlich sein, wenn der optimale Zeitplan (in irgendeiner vorhersehbaren Weise) von den Eingabedaten abhängt, auf die das Programm angewendet wird.

Um ein Beispiel für die Kompromisse zwischen verschiedenen Zeitplänen zu sehen, sollten Sie die Freigabe von 1000 Iterationen zwischen acht Threads in Betracht ziehen. Angenommen, in jeder Iteration gibt es eine invariante Menge an Arbeit, und verwenden Sie diese als Zeiteinheit.

Wenn alle Threads gleichzeitig beginnen, führt der static Zeitplan dazu, dass das Konstrukt in 125 Einheiten ohne Synchronisierung ausgeführt wird. Nehmen wir jedoch an, dass ein Thread 100 Einheiten verspätet eingetroffen ist. Dann warten Standard sieben Threads auf 100 Einheiten an der Barriere, und die Ausführungszeit für das gesamte Konstrukt steigt auf 225.

Da sowohl die als guided auch die dynamic Zeitpläne sicherstellen, dass kein Thread auf mehr als eine Einheit an der Barriere wartet, bewirkt der verzögerte Thread, dass die Ausführungszeiten für das Konstrukt nur auf 138 Einheiten erhöht werden, was möglicherweise durch Verzögerungen bei der Synchronisierung erhöht wird. Wenn solche Verzögerungen nicht vernachlässigbar sind, wird es wichtig, dass die Anzahl der Synchronisierungen 1000 ist dynamic , aber nur 41 für guided, vorausgesetzt, die Standardblockgröße eines. Mit einer Blockgröße von 25 dynamic und guided beide in 150 Einheiten enden, plus alle Verzögerungen aus den erforderlichen Synchronisierungen, die jetzt nur 40 bzw. 20 zahlen.