MSDN Magazin > Home > Ausgaben > 2007 > October >  Parallele Leistung: Optimieren von verwaltetem ...
Parallele Leistung
Optimieren von verwaltetem Code für Mehrkerncomputer
Daan Leijen and Judd Hall

Themen in diesem Artikel:
  • Task Parallel Library
  • Parallel.For im Vergleich zu ThreadPool
  • Statische Arbeitsverteilung
  • Futures
In diesem Artikel werden folgende Technologien verwendet:
Parallel FX Library
Mehrprozessorcomputer entwickeln sich derzeit zum Standard. Gleichzeitig haben sich die Geschwindigkeitszuwächse einzelner Prozessoren verringert. Daher empfiehlt es sich, ein Programm parallel auf mehreren Prozessoren auszuführen, wenn Sie die Leistung verbessern möchten. Leider erweist sich das Schreiben von Algorithmen, die das Vorhandensein mehrerer Prozessoren ausnutzen, weiterhin als schwierig. Tatsächlich verwenden die meisten Anwendungen nur einen einzigen Kern und können die Geschwindigkeit nicht erhöhen, wenn sie auf einem Mehrkerncomputer ausgeführt werden. Es ist erforderlich, dass Programme auf eine neue Art und Weise geschrieben werden.

Einführung in TPL
Task Parallel Library (TPL) wurde entworfen, um das Schreiben von verwaltetem Code zu vereinfachen, der automatisch mehrere Prozessoren verwenden kann. Wenn Sie die Bibliothek verwenden, können Sie potenzielle Parallelität ganz einfach in vorhandenem sequenziellem Code ausdrücken, wobei die geöffneten parallelen Tasks gleichzeitig auf allen verfügbaren Prozessoren ausgeführt werden. In der Regel wird dadurch die Geschwindigkeit erheblich erhöht.
TPL wird in Zusammenarbeit zwischen Microsoft® Research, dem Microsoft-CLR-Team (Common Language Runtime) und dem Parallel Computing Platform-Team erstellt. TPL ist eine Hauptkomponente der Parallel FX Library, der nächsten Generation der parallelen Unterstützung für Microsoft .NET Framework. Obwohl Version 1.0 noch nicht veröffentlicht wurde, wird die erste Parallel FX Community Tech Preview (CTP) von MSDN® im Herbst 2007 verfügbar sein. Weitere Einzelheiten finden Sie unter http://blogs.msdn.com/somasegar. TPL erfordert keine Spracherweiterungen und funktioniert mit .NET Framework 3.5 und höher.
Visual Studio® 2008 wird vollständig unterstützt, und die gesamte Parallelität wird mithilfe von normalen Methodenaufrufen ausgedrückt. Angenommen, Sie haben zum Beispiel die folgende for-Schleife, mit der die Elemente eines Arrays quadriert werden:
for (int i = 0; i < 100; i++) { 
  a[i] = a[i]*a[i]; 
}
Da die Iterationen unabhängig voneinander sind, d. h. folgende Iterationen keine Statusaktualisierungen von früheren Iterationen lesen, können Sie TPL verwenden, um die potenzielle Parallelität mit einem Aufruf der parallel for-Methode auszudrücken:
Parallel.For(0, 100, delegate(int i) { 
  a[i] = a[i]*a[i]; 
});
Beachten Sie, dass es sich bei Parallel.For nur um eine normale statische Methode mit drei Argumenten handelt, von denen das letzte Argument ein Delegatausdruck ist. Dieser Delegat zeichnet den unveränderten Schleifentextkörper aus dem vorherigen Beispiel auf. Dadurch wird es besonders einfach, mit der Einführung von Parallelität in ein Programm zu experimentieren.
Die Bibliothek enthält komplizierte Algorithmen für die dynamische Arbeitsverteilung und passt sich der Arbeitsauslastung und dem jeweiligen Computer automatisch an. In der Zwischenzeit drücken die Primitive der Bibliothek nur die potenzielle Parallelität aus, garantieren sie jedoch nicht. Auf einem Einprozessorcomputer werden beispielsweise parallel for-Schleifen in Übereinstimmung mit der Leistung von streng sequenziellem Code sequenziell ausgeführt. Auf einem Dual-Core-Computer verwendet die Bibliothek jedoch zwei Arbeitsthreads, um die Schleife je nach Arbeitsauslastung und Konfiguration parallel auszuführen. Dies bedeutet, dass Sie noch heute Parallelität in Ihren Code einführen können. Als Folge werden Ihre Anwendungen mehrere Prozessoren automatisch verwenden, wenn sie verfügbar sind. Darüber hinaus weist der Code auch auf älteren Einprozessorcomputern eine gute Leistung auf.
Leider synchronisiert die Bibliothek parallelen Code, der gemeinsam genutzten Speicher verwendet, nicht richtig. Weiterhin ist der Programmierer dafür verantwortlich sicherzustellen, dass bestimmter Code sicher parallel ausgeführt werden kann. Andere Methoden, wie z. B. Sperren, werden immer noch zum Schutz gleichzeitiger Änderungen an gemeinsam genutztem Speicher benötigt. TPL bietet jedoch einige Abstraktionen, die die Synchronisierung unterstützen (siehe unten).

Strukturierte Parallelität
Eine der wichtigsten Abstraktionen paralleler Programmierung besteht in einer parallelen Schleife. Sehen Sie sich zum Beispiel die folgende (naive) Matrixmultiplikationsroutine an:
void SeqMatrixMult(int size, double[,] m1, double[,] m2, double[,] result) 
{
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      result[i, j] = 0;
      for (int k = 0; k < size; k++) {
        result[i, j] += m1[i, k] * m2[k, j];
      }
    }
  }
}
In diesem Beispiel existieren die äußeren Iterationen unabhängig voneinander und können potenziell parallel durchgeführt werden. Sie können diese potenzielle Parallelität ganz einfach mit TPL verfügbar machen. Zuerst verweisen Sie während der Kompilierung auf die System.Concurrency.dll-Assembly. Anschließend können Sie die Bibliothek mithilfe einer using-Anweisung in Ihren Code importieren:
using System.Concurrency;
Sobald der Namespace verfügbar ist, können Sie die äußere for-Schleife der Matrixmultiplikation durch einen Aufruf an die statische Parallel.For-Methode ersetzen:
void ParMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
  Parallel.For( 0, size, delegate(int i) {
    for (int j = 0; j < size; j++) {
      result[i, j] = 0;
      for (int k = 0; k < size; k++) {
        result[i, j] += m1[i, k] * m2[k, j];
      }
    }
  });
}
Das Parallel.For-Konstrukt ist eine normale statische Methode mit drei Argumenten. Die ersten beiden Argumente geben die Iterationsbeschränkungen (zwischen 0 und der Größe) an. Das letzte Argument ist eine Delegatfunktion, die für jede Iteration aufgerufen wird. Dieser Delegat verwendet den Iterationsindex als erstes Argument und führt den unveränderten Schleifentextkörper des vorherigen Beispiels aus. Es sind keine Änderungen am ursprünglichen Schleifentextkörper notwendig, da Delegate automatisch die freien Variablen des Schleifentextkörpers aufzeichnen (wie result und m1). Weitere Informationen zu Delegatausdrücken erhalten Sie unter msdn.microsoft.com/msdnmag/issues/06/00/C20.
Wenn schließlich eine Ausnahme in einer beliebigen Iteration ausgelöst wurde, werden alle Iterationen abgebrochen. Die erste ausgelöste Ausnahme wird in dem aufrufenden Thread erneut ausgelöst und stellt sicher, dass Ausnahmen ordnungsgemäß weitergeleitet werden und nicht verloren gehen.
Ohne TPL wäre es viel schwieriger, die potenzielle Parallelität in dieser Schleife auszudrücken. Sogar mit Unterstützung der .NET ThreadPool-Klasse müssten Sie den Aufwand für die Synchronisierung und die Arbeitsteilung abwägen. Abbildung 1 zeigt die mithilfe des Threadpools parallelisierte Matrixmultiplikationsroutine.
void ThreadpoolMatrixMult(int size, double[,] m1, double[,] m2, 
    double[,] result)
{
  int N = size;                           
  int P = 2 * Environment.ProcessorCount; // assume twice the procs for 
                                          // good work distribution
  int Chunk = N / P;                      // size of a work chunk
  AutoResetEvent signal = new AutoResetEvent(false); 
  int counter = P;                        // use a counter to reduce 
                                          // kernel transitions    
  for (int c = 0; c < P; c++) {           // for each chunk
    ThreadPool.QueueUserWorkItem(delegate(Object o)
    {
      int lc = (int)o;
      for (int i = lc * Chunk;           // iterate through a work chunk
           i < (lc + 1 == P ? N : (lc + 1) * Chunk); // respect upper 
                                                     // bound
           i++) {
        // original inner loop body
        for (int j = 0; j < size; j++) {
          result[i, j] = 0;
          for (int k = 0; k < size; k++) {
            result[i, j] += m1[i, k] * m2[k, j];
          }
        }
      }
      if (Interlocked.Decrement(ref counter) == 0) { // use efficient 
                                                     // interlocked 
                                                     // instructions      
        signal.Set();  // and kernel transition only when done
      }
    }, c); 
  }
  signal.WaitOne();
}

Das Beispiel ist bereits relativ ausgereift. In ihm werden der Threadpool für Arbeitsaufgaben und ein Indikator zusammen mit einem einzelnen wait-Handle verwendet, um die Anzahl von Kernelübergängen zu minimieren. Außerdem wird die Schleife basierend auf der Anzahl der Prozessoren statisch in Blöcke aufgeteilt. Dabei werden zur besseren Anpassung an die dynamische Arbeitsauslastung doppelt so viele Blöcke wie nötig erstellt. Im Unterschied zur Parallel.For-Methode jedoch leitet die in Abbildung 1 dargestellte Methode keine Ausnahmen im Schleifentextkörper weiter und kann nicht abgebrochen werden.
Offensichtlich bereitet es größere Probleme, diesen Code zu schreiben. Zudem ist er im Vergleich zur Parallel.For-Methode anfälliger für Fehler. Obwohl die Threadpoolmethode manuell abgestimmt wird und eine nahezu optimale Arbeitsaufteilung verwendet, ist ihre Leistung in der Regel im Vergleich zur Parallel.For-Methode herabgesetzt. Abbildung 2 zeigt die Ergebnisse einiger Einzeltests. Die Ergebnisse stellen den relativen Geschwindigkeitszuwachs bei der Parallelisierung der äußeren Schleife einer Matrixmultiplikation mit 750 x 750 Elementen dar. 1 zeigt die Ausführungszeit für eine normale for-Schleife. Die Tests wurden auf einem Dual-Core-Computer mit vier Sockets und 3 GB Speicher und unter Windows Vista® Ultimate ausgeführt. Beachten Sie, dass auf dem Einkerncomputer die Parallel.For-Version praktisch die gleichen Vorgänge wie die direkte for-Schleife ausführt.
Abbildung 2 Leistung von Parallel.For im Vergleich zu ThreadPool 

Parallelität im Übermaß
Sie haben möglicherweise festgestellt, dass Sie noch mehr Parallelität bereitstellen können, indem Sie die zweite for-Schleife folgendermaßen parallelisieren:
Parallel.For( 0, size, delegate(int i) {
  Parallel.For( 0, size, delegate(int j) {
    result[i, j] = 0;
    for (int k = 0; k < size; k++) {
      result[i, j] += m1[i, k] * m2[k, j];
    }
  });
});
Auch wenn es legitim ist, parallele Schleifen zu schachteln, ist die Leistung dieser Methode aus zwei Gründen im Allgemeinen schlechter. Erstens bietet die äußere Schleife in diesem bestimmten Beispiel mehr als genug Gelegenheiten zur Parallelität, da in der Regel die Anzahl der zur Verfügung stehenden Kerne geringer als die Größe der Matrix ist. Zweitens ordnet jeder Delegatausdruck für die freien Variablen Speicher zu. Aus diesem Grund enthielt das anfängliche Beispiel nur eine einzige Zuordnung, deren Aufwand über die Iterationen amortisiert werden. Im neuen Code führt das innere Parallel.For leider Heapzuordnungen für jede Iteration der äußeren Schleife durch. Die Zuordnung ist in der CLR sehr effizient. Im Vergleich zu der in jeder Iteration durchgeführten Arbeit entsteht jedoch ein erheblicher Aufwand.
Beachten Sie, dass Sie die innere Schleife nicht parallelisieren können, da die Iterationen nicht unabhängig sind. Es entsteht ein Race, da jede Iteration dem result[i,j]-Ort einen Beitrag hinzufügt. Wenn Sie diese Schleife parallelisieren, könnten zwei Iterationen gleichzeitig den aktuellen Wert in ein Register lesen, hinzufügen und das Ergebnis zurückschreiben. Dabei würde eine Hinzufügung verloren gehen! Die einzige Möglichkeit, die innere Schleife effektiv zu parallelisieren besteht darin, die Hinzufügung sachgemäß mit einer Sperre zu schützen. Natürlich empfiehlt sich diese Vorgehensweise in der Praxis nicht: Selbst wenn Sie die zusätzlichen Zuordnungen im Augenblick ignorieren, wird die Leistung erheblich beeinträchtigt, da jede gleichzeitige Iteration um die gleiche Sperre konkurriert. Dieser Aspekt wird im Abschnitt zu den Aggregationsvorgängen eingehender besprochen. Weitere Informationen zu Races und Sperren erhalten Sie unter msdn.microsoft.com/msdnmag/issues/05/08/Concurrency/default.aspx.

Ein Strahlverfolgungsbeispiel
Die Strahlverfolgung ist eine einfache, jedoch leistungsfähige Methode zum Generieren fotorealistischer Darstellungen. Das Verfahren ist aber sehr rechenintensiv. Die Strahlverfolgung ist in der Tat ein ausgezeichneter Kandidat für Ihre Bibliothek, da jeder Strahl parallel berechnet werden kann. Hier wurde eine vorhandene Strahlverfolgung verwendet, die von Luke Hoban geschrieben wurde (siehe blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx). Sie wurde zur parallelen Ausführung mithilfe von TPL geändert. Die Strahlverfolgung generiert Bilder wie in Abbildung 3 dargestellt und wird als Beispiel in der Parallel FX CTP verfügbar sein. Die zentrale Schleife der ursprünglichen Strahlverfolgung wird durch alle Pixel des Ergebnisbilds wiederholt:
Abbildung 3 Parallele Strahlverfolgung (Klicken Sie zum Vergrößern auf das Bild)
void Render(Scene scene, Color[,] rgb)
{
  for (int y = 0; y < screenHeight; y++)
  {
    for (int x = 0; x < screenWidth; x++) {
      rgb[x,y] = TraceRay(new Ray(scene,x,y));
    }
  }
}
Da jeder Strahl einzeln verfolgt werden kann, musste nur eine einzige Zeile im ursprünglichen Code geändert werden, um ihn zu parallelisieren:
void Render(Scene scene, Color[,] rgb)
{  
  Parallel.For(0, screenHeight, delegate(int y) 
  {
    for (int x = 0; x < screenWidth; x++) {
      rgb[x,y] = TraceRay(new Ray(scene,x,y));
    }
  });
}
Auf einem Computer mit acht Kernen konnte der ursprüngliche Code 1,7 Frames pro Sekunde für ein Bild mit 350 mal 350 Pixeln generieren. Im Vergleich dazu generierte die parallele Version, die auf dem gleichen Computer mit acht Prozessoren ausgeführt wurde, 12 Frames pro Sekunde. Das bedeutet einen siebenfachen Geschwindigkeitszuwachs auf einem Computer mit acht Prozessoren. Dieses Ergebnis ist angesichts der relativ kleinen Änderung beachtlich. Mit 12 Frames pro Sekunde reicht die Geschwindigkeit gerade dafür aus, eine flüssige Animation mit auf dem Boden springenden Bällen zu erzeugen. Da dies eine sehr einfache Strahlverfolgung ist, können Sie sie möglicherweise so optimieren, dass Sie eine noch flüssigere Animation erhalten.

Dynamische Arbeitsverteilung
Beim manuellen Parallelisieren von Schleifen mithilfe des Threadpools teilen Entwickler die Arbeit häufig statisch auf. Bei einer Strahlverfolgung wird das Bild oft in gleiche Teile aufgeteilt, wobei jeder Teil von einem separaten Thread verarbeitet wird. Diese Vorgehensweise empfiehlt sich im Allgemeinen nicht, da die tatsächliche Arbeitsauslastung möglicherweise ungleich aufgeteilt ist. Wenn beispielsweise aufgrund von Reflektionen die Berechnung des unteren Teils vom Bild doppelt so lange dauert, warten die Threads für den oberen Teil des Bilds die meiste Zeit darauf, dass die unteren Threads fertig werden. Selbst wenn die Arbeit gleichmäßig verteilt ist, kann dies aufgrund von Seitenfehlern oder anderen im System gleichzeitig ausgeführten Prozessen auftreten.
Für eine gute Skalierung auf mehreren Prozessoren verwendet TPL Verfahren, die Arbeit „stehlen“, um Arbeitsaufgaben über die Arbeitsthreads dynamisch anzupassen und zu verteilen. Die Bibliothek besitzt einen Task-Manager, der standardmäßig einen Arbeitsthread pro Prozessor verwendet. Dadurch wird ein minimaler Threadwechsel durch das Betriebssystem sichergestellt. Jeder Arbeitsthread verfügt über seine eigene lokale Warteschlange mit der zu erledigenden Arbeit. Jeder Arbeitsprozess überträgt in der Regel nur neue Tasks in seine eigene Warteschlange und wechselt die Arbeit, wenn ein Task fertig gestellt ist. Wenn die lokale Warteschlange leer ist, sucht ein Arbeitsprozess selbst nach Arbeit und versucht sie aus den Warteschlangen anderer Arbeitsprozesse zu „stehlen“.
Der Vorteil besteht hier darin, dass fast keine Synchronisierung zwischen den Arbeitsprozessen auftritt, da die Warteschlangen verteilt sind und die meisten Vorgänge für den Arbeitsprozess lokal ausgeführt werden, was für die Skalierbarkeit von großer Bedeutung ist. Darüber hinaus wurde nachgewiesen, dass das „Stehlen“ von Arbeit gute Cachelokalitäts- und Arbeitsverteilungseigenschaften besitzt. Wenn zum Beispiel die Arbeitsauslastung ungleich verteilt ist, benötigt ein Arbeitsprozess möglicherweise für einen bestimmten Task mehr Zeit. Jetzt „stehlen“ jedoch andere Arbeitsprozesse aus seiner Warteschlange Arbeit, wodurch alle Prozessoren ausgelastet werden. In typischen Anwendungen ist eine dynamische Arbeitsverteilung von großer Bedeutung, da die Dauer eines Tasks nur schwer vorherzusagen ist. Dies trifft insbesondere auf Desktopsysteme zu, in denen Prozessoren für viele unterschiedliche Prozesse gemeinsam verwendet werden und nicht vorhergesagt werden kann, welche Zeitkontingente die Arbeitsthreads erhalten.
Abbildung 4 zeigt die dynamische Arbeitsverteilung unter Verwendung von vier Threads. Es wird das gleiche strahlverfolgte Bild wie in Abbildung 3 dargestellt. Hier verwendet jedoch jeder Arbeitsthread zum Rendern seiner Pixel eine andere Farbe. Sie sehen, dass die Bibliothek die Arbeit gleichmäßig unter den Arbeitsthreads verteilt hat und so eine dynamische Anpassung an die Arbeitsauslastung durchführt.
Abbildung 4 Verteilen von Arbeit unter Arbeitsthreads (Klicken Sie zum Vergrößern auf das Bild)
Die Bibliothek führt nicht nur eine dynamische Arbeitsverteilung durch, sondern passt auch die Anzahl der Arbeitsthreads dynamisch an, wenn Arbeitsprozesse blockiert werden. Zu den blockierten Vorgängen gehören Dateilesevorgänge, das Warten auf das Drücken einer Taste und das Abrufen des Benutzernamens (da damit auf das Netzwerk auf einer Domäne zugegriffen werden kann). Wenn ein Task unbeabsichtigt blockiert wird, kann die Leistung sinken, während der Grad an Parallelität fällt (das Programm verhält sich jedoch immer noch ordnungsgemäß). Die Bibliothek steigert die Leistung, indem sie eine automatische Nachverfolgung durchführt, um zu überprüfen, ob Arbeitsthreads blockiert sind. Gegebenenfalls fügt sie dann zusätzliche Arbeitsthreads ein, um den Grad an Parallelität beizubehalten. Nachdem die Blockierung der Vorgänge aufgehoben wurde, können sich einige Arbeitsprozesse zurückziehen, um den Aufwand für den Threadwechsel zu verringern.

Aggregation
Eine for-Schleife wird häufig für das Durchlaufen durch eine Domäne verwendet und aggregiert die Werte in einem einzigen Ergebnis. Sehen Sie sich zum Beispiel die folgenden Iterationen an, mit denen die Primzahlen unter 100 zusammenfasst werden:
int sum = 0;
for(int i = 0; i < 100; i++) {
  if (isPrime(i)) sum += i;
}
Leider kann diese Schleife in diesem Zustand nicht parallelisiert werden, da durch die Parallelisierung ein Datenrace entstehen würde. Jede Iteration ändert die freigegebene sum-Variable ohne Sperrschutz. Wenn zwei gleichzeitige Iterationen die Summe zur gleichen Zeit erhöhen, können beide möglicherweise den gleichen Wert in ein Register lesen, hinzufügen und das Ergebnis zurückschreiben. In diesem Fall ginge eine Hinzufügung verloren. In einer korrekten Version kann die Hinzufügung mithilfe einer Sperre folgendermaßen geschützt werden:
int sum = 0;
Parallel.For(0, 100, delegate(int i) {
  if (isPrime(i)) {
    lock (this) { sum += i; }
  }
});
Die Leistung des Programms ist jetzt jedoch herabgesetzt, da alle parallelen Iterationen um die gleiche Sperre und die gleiche Speicherstelle (sum) konkurrieren. Es wäre von Vorteil, wenn jeder Arbeitsthread einen lokalen Summenthread beibehalten könnte und sich die Hinzufügung auf die globale Summe am Ende der Schleife beschränken würde. Dieses Muster wird vom Parallel.Aggregate-Vorgang aufgezeichnet. Folglich können wir das Beispiel folgendermaßen neu schreiben:
int sum = Parallel.Aggregate(0, 100, // iteration domain
              0,                     // initial value
              delegate(int i) { return (isPrime(i) ? i : 0) }, // apply 
                                                      // on each element
              delegate(int x, int y) { return x+y; }  // combine results
          );
Der gesamte Vorgang verwendet fünf Argumente. Die ersten zwei Argumente geben die Iterationsdomäne an, die auch ein Enumerator sein kann. Das nächste Argument ist der anfängliche Wert für das Ergebnis. Die nächsten zwei Argumente stellen Delegatfunktionen dar. Die erste Funktion wird auf jedes Element angewendet, und die andere Funktion kombiniert die Elementergebnisse.
Die Bibliothek verwendet automatisch eine lokale Threadvariable, um die lokalen Threadergebnisse ohne Sperre zu berechnen und nur eine Sperre für die Kombination der endgültigen lokalen Threadergebnisse zu verwenden. Beachten Sie, dass die Elemente bei einer parallelen Aggregation in einer anderen Reihenfolge als bei einer sequenziellen Aggregation kombiniert werden können. Deshalb muss die kombinierende Delegatfunktion assoziierend sein, und beim anfänglichen Wert muss es sich um ein Einheitselement handeln.

Abzweigungs-/Zusammenführungsparallelität
Ein weiteres häufiges paralleles Muster ist der Abzweigungs-/Zusammenführungsparallelität. Betrachten Sie das folgende Beispiel für eine sequenzielle Schnellsortierungsimplementierung:
static void SeqQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
  if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
  
  int pivot = Partition(domain, lo, hi);
  SeqQuickSort(domain, lo, pivot - 1); 
  SeqQuickSort(domain, pivot + 1, hi); 
} 
Der Algorithmus ist generisch im Elementtyp T und benötigt nur T-Instanzen, die verglichen werden können. Unter einer bestimmten Schwelle greift der Algorithmus auf die Einfügesortierung zurück, die bei einer kleinen Anzahl von Elementen besser funktioniert. Andernfalls partitionieren Sie das Eingabearray in zwei Teile und wenden die Schnellsortierung auf jeden Teil separat an. Diese zwei Sortierungen können parallel durchgeführt werden, da jede Sortierung einen anderen Teil des Arrays bearbeitet. Wir können dies ganz einfach mit der Parallel.Do-Methode ausdrücken:
static void ParQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
  if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
  
  int pivot = Partition(domain, lo, hi);
  Parallel.Do(
    delegate { ParQuickSort(domain, lo, pivot - 1); },
    delegate { ParQuickSort(domain, pivot + 1, hi); }
  );
} 
Bei der Parallel.Do-Methode handelt es sich um eine statische Methode, die zwei oder mehr Delegate als Argumente verwendet und sie potenziell parallel ausführt. Da die Schnellsortierung rekursiv ist, ist die bereitgestellte Parallelität von großem Umfang, weil durch jeden Aufruf weitere parallele Tasks eingeführt werden. Da auch in diesem Fall die Bibliothek keine parallele Ausführung garantiert, werden die meisten Tasks sequenziell ausgeführt, was für eine gute Leistung von großer Bedeutung ist.

Tasks und Futures
In allen vorherigen Beispielen wurde strukturierte Parallelität demonstriert, in der der Bereich des parallelen Codes vom lexikalischen Bereich bestimmt wird. Es können jedoch nicht alle parallelen Algorithmen auf diese Weise ausgedrückt werden. Glücklicherweise stellt die Bibliothek auch Unterstützung für allgemeine parallele Tasks bereit:
class Task
{
  Task( Action action );
  
  void Wait();
  void Cancel();
  bool IsCompleted { get; }  
  ...
}
Ein Task wird durch Bereitstellen einer zugeordneten Aktion erstellt, die potenziell parallel ausgeführt werden kann. Die Aktion wird zwischen dem Erstellungszeitpunkt des Tasks und dem ersten Aufruf der Wait-Methode ausgeführt. Die verbundene Aktion kann parallel auf einem anderen Thread ausgeführt werden, sie wird jedoch keinesfalls unter den Threads migrieren. Diese Garantie ist für Programmierer von großem Nutzen, da sie threadaffine Abstraktionen wie kritische Abschnitte in Windows verwenden können und sich keine Gedanken darüber machen müssen, dass zum Beispiel LeaveCriticalSection in einem anderen Thread als EnterCriticalSection ausgeführt wird. Wenn ein Task abgeschlossen wurde, kehrt Wait sofort zurück.
Jede in der verbundenen Aktion ausgelöste Ausnahme wird in einem Task gespeichert und erneut ausgelöst, wenn Wait aufgerufen wird. Ebenso sammeln die Parallel.For- und Parallel.Do-Funktionen alle ausgelösten Ausnahmen und werden erneut ausgelöst, wenn alle Tasks abgeschlossen sind. Dadurch wird sichergestellt, dass Ausnahmen niemals verloren gehen und ordnungsgemäß an abhängige Elemente weitergeleitet werden.
Schließlich können Sie den Task und alle in den verbundenen Aktionen (untergeordneten Tasks) erstellten Tasks abbrechen, indem Sie Cancel aufrufen. Der Abbruch ist nicht präemptiv, und ein ausgeführter Task muss die Arbeit durch Rückruf in die Bibliothek kooperativ beenden. Dies kann zum Beispiel durch Erstellen neuer Tasks oder durch Aufrufen der Wait-Methode durchgeführt werden. Wenn der übergeordnete Task abgebrochen wurde, werden diese Bibliotheksaufrufe eine (synchrone) OperationCanceled-Ausnahme auslösen, um die Aktion zu beenden.
Sie können Tasks als verbesserten Threadpool betrachten, in dem Arbeitsaufgaben ein Handle zurückgeben, das abgebrochen oder gewartet werden kann, und in dem Ausnahmen weitergeleitet werden. Es gibt auch eine Abwandlung von Tasks, Futures genannt, bei denen die zugeordnete Aktion ein Ergebnis berechnet:
class Task<T> : Task
{
  Task ( Func<T> function );
  T Value { get; }            // does an implicit wait
}
Ein Future ist ein Task, der ein Ergebnis berechnet. Es wird nicht mit einer normalen Aktion erstellt, sondern mit einer Aktion, die ein Ergebnis zurückgibt. Dieses Ergebnis ist ein Delegat des Func<T>-Typs, wobei T der Typ des Futurewerts ist.
Das Ergebnis des Futures wird durch die Value-Eigenschaft abgerufen. Die Value-Eigenschaft ruft Wait intern auf, um sicherzustellen, dass der Task abgeschlossen und der Ergebniswert berechnet wurde. Da Wait aufgerufen wurde, löst das Aufrufen von Value alle Ausnahmen aus, die während der Berechnung des Werts ausgelöst wurden. Ein Future hat folglich entweder einen Wert oder einen Ausnahmewert, der durch die Berechnung bestimmt wird.
Futures sind ein altes Konzept, das bereits in Multi-Lisp implementiert wurde. Beachten Sie, dass das Konzept der Futures insofern nicht „sicher“ ist, als der Programmierer für das sachgemäße Sperren von gemeinsam genutztem Speicher verantwortlich ist. Dies steht im Gegensatz zu Methoden, bei denen die Aktion eines Futures automatisch in eine Speichertransaktion integriert ist.
Die Futureabstraktion funktioniert gut mit symbolischem Code, der weniger strukturiert als Schleifen ist. Betrachten Sie zum Beispiel die folgende Definition für binäre Strukturknoten und Leafs:
class Node : Tree {
  int   depth;  // The depth of the tree 
  Tree  left;   // The left sub tree
  Tree  right;  // The right sub tree
  ...
}

class Leaf : Tree {
  int value;  // values are stored in the leafs
  ...
}
Angenommen, es wird eine virtuelle Sum-Methode auf einer Struktur definiert, in der gesamten Werte der Leafs zusammengefasst werden. Ein Leaf gibt einfach seinen Wert zurück. Knoten fügen die Summen ihrer Unterstrukturen hinzu:
override int Sum() {
   int l = left.Sum();
   int r = right.Sum();
   return (r + l);
}
In diesem Fall können alle untergeordnete Berechnungen parallel ausgeführt werden, da sie voneinander unabhängig sind. Die Parallelität ist hier lexikalisch begrenzt, und Sie können Parallel.Do verwenden. Zum Zweck dieser Demonstration werden jedoch Futures verwendet:
override int Sum()
{   
   Task<int> l = new Task<int>( left.Sum );
   int r       = right.Sum();
   return (r + l.Value);
}
Für jede linke Unterstruktur wird ein neues Future vom Typ „int“ erstellt, und es wird dabei ein Delegat als Konstruktorargument übergeben. In diesem Beispiel übergeben wir die sum-Methode der linken Unterstruktur, left.Sum, ohne sie aufzurufen. Anschließend wird die Summe der rechten Unterstruktur berechnet. Durch Erstellen des Futures können andere Prozessoren die Bewertung der Summe der linken Unterstruktur potenziell parallel starten. Am Ende wird der Wert des Futures mithilfe der Value-Eigenschaft angefordert.
Wenn der Task bereits von einem anderen Arbeitsthread berechnet wurde, gibt dieser Aufruf praktischerweise sofort den Ergebniswert zurück. Sollte der Task weiterhin auf einem anderen Arbeitsthread ausgeführt werden, wird die Blockierung erst beendet, wenn das Ergebnis verfügbar ist (es wird aber ein anderer Arbeitsthread geplant, um den Grad an Parallelität beizubehalten).
In einem anderen sehr häufigen Szenario wird der Task überhaupt nicht gestartet. In diesem Fall führt der Aufruf von Value den Task direkt auf dem aufrufenden Thread aus. Auf diese Vorgehensweise wird häufig zurückgegriffen, und sie ist sehr effizient, da nur ein indirekter Methodenaufruf benötigt wird. Wenn Sie dagegen auf vom Betriebssystem bereitgestellte Signale warten, ist es unmöglich, das Signal auszulösen. In diesem Fall kann nur der aufrufende Thread blockiert werden, was sich im Allgemeinen negativ auf die Leistung auswirkt. In diesem Beispiel kann der Wert eindeutig berechnet werden, und die Bibliothek führt die verbundene Aktion direkt aus, statt den Thread zu blockieren.
Da der Umfang der in Leafs durchgeführten Arbeit sehr gering ist, empfiehlt es sich, den Arbeitsumfang für jeden Task zu erhöhen, indem die Summenbildung sequenziell bei einer bestimmten Strukturtiefe durchgeführt wird. Dies bedeutet zum Beispiel, dass Sie für eine sequenzielle sum-Methode „SeqSum“ Folgendes schreiben können:
override int Sum()
{   
   if (depth < 10) return SeqSum();
 
   Task<int> l = new Task<int>( left.Sum );
   int r         = right.Sum();
   return (r + l.Value);
}
Im Allgemeinen hängt die geeignete Schwellenwertbeschränkung vom Umfang der erledigten Arbeit in der Aktion eines Tasks im Vergleich zum Aufwand für die Zuordnung eines Taskobjekts ab. Die Zuordnung ist erfahrungsgemäß relativ unkompliziert, und die Schwellenwertbeschränkung liegt in der Regel bei 100 Gleitkommamultiplikationen.
Da Futures echte erstklassige Werte sind, können Sie sie für die Einführung von Parallelität zwischen logisch unterschiedlichen Teilen eines Programms verwenden. Zum Beispiel ist es möglich, Futures in Datenstrukturen zu speichern, in denen eine andere Phase die Werte dieser Futures anfordert. Ein passender Ort dafür sind Spieleanwendungen. Eine Phase könnte zum Beispiel die neue Integrität aller Zeichen als Future berechnen, während andere Phasen die Werte dieser Integritätsfutures zu einem späteren Zeitpunkt verwenden. Auf einem Mehrkerncomputer können diese Futures parallel zu der in jeder Phase ausgeführten Arbeit berechnet werden.

Replizierbare Tasks
Die Bibliothek basiert auf nur zwei Primitivkonzepten: Tasks und replizierbaren Tasks. Alle anderen Abstraktionen, wie z. B. Futures und parallel for-Schleifen, werden im Verhältnis zu diesen Primitiven ausgedrückt. Dadurch wird sichergestellt, dass sich Vorgänge mit einer einheitlichen Semantik regulär verhalten. Ausnahmen werden zum Beispiel immer problemlos verbreitet, und alle Abstraktionen können abgebrochen werden (einschließlich parallel for-Schleifen).
Beachten Sie, dass replizierbare Tasks eigentlich für Bibliotheksersteller vorgesehen sind, die die von TPL angebotenen Standardabstraktionen erweitern möchten, und in normalem Code nur sparsam (wenn überhaupt) verwendet werden sollen. Ein replizierbarer Task wird folgendermaßen direkt von einem normalen Task abgeleitet:
class ReplicableTask : Task
{
  ReplicableTask( Action action );
}
Ein replizierbarer Task stellt einen Task dar, der von mehreren Threads gleichzeitig ausgeführt werden kann und das universelle, allgemeingültige Parallelitätsmuster aufzeichnet, während die dynamischen Vorgänge der Arbeitsverteilung abstrahiert werden. Der Konstruktor verwendet einen action-Delegat, der potenziell parallel auf einem anderen Thread und potenziell von mehreren Threads gleichzeitig ausgeführt wird. Wenn eine Ausnahme in einer dieser Ausführungen ausgelöst wird, wird nur eine von ihnen gespeichert und erneut durch Wait ausgelöst.
Ein replizierbarer Task kann verwendet werden, wenn sich andere Threads potenziell an der Arbeit beteiligen. Alle Parallel.For- und Parallel.ForEach-Variationen werden mithilfe replizierbarer Tasks implementiert. Zum Beispiel können Sie das grundlegende Parallel.For folgendermaßen naiv implementieren:
static void For( int from, int to, Action<int> body )
{
  int index = from;
  ReplicableTask rtask = new ReplicableTask( delegate {
    int i;
    while ((i = Interlocked.Increment(ref index)-1) < to) {
      body(i);
    }
  });
  rtask.Wait();
}
Da alle replizierbaren Tasks die Indexvariable gemeinsam verwenden, kann der action-Delegat, der an den Konstruktor für replizierbare Tasks übergeben wird, von so vielen Threads wie nötig ausgeführt werden. Während der Implementierung können auf diese Art und Weise im Leerlauf befindliche Prozessoren in die Arbeit einbezogen werden.
Bei dieser Implementierung fordert jeder Arbeitsthread einen Index nach dem anderen an. Dies entspricht der dynamic(1)-Strategie von OpenMP und funktioniert gewöhnlich gut, wenn die Arbeitsauslastung jedes Indexes erhebliche Unterschiede aufweisen kann. (Weitere Informationen zu diesem Thema finden Sie unter msdn.microsoft.com/msdnmag/issues/05/10/OpenMP.) Diese Strategie kann jedoch zu einem Cachekonflikt führen, wenn die Arbeitsauslastung pro Index klein ist. In diesem Fall wäre es besser, einen Satz an Indexen zur gleichen Zeit zu verarbeiten. Hier sehen Sie eine Variation von Parallel.For mit Bezug auf die dynamic(n)-Strategie von OpenMP und mit einem Satz an Indexen als Argument:
static void ForWithStride( int stride, int from, int to, Action<int> body )
{
  int index = from;
  if (stride <= 0) stride = 1;
  ReplicableTask rtask = new ReplicableTask( delegate {
    int i;
    while ((i = Interlocked.Add(ref index,stride)-stride) < to) {
      int end = Math.Min(i+stride, to);
      do {
        body(i);
        i++;
      } 
      while (i < end)
    }
  });
  rtask.Wait();
}
Replizierbare Tasks stellen eine leistungsfähige Abstraktion zum Implementieren verschiedener paralleler Iterationsstrategien dar. Erfahrungsgemäß funktionieren die standardmäßigen Parallel.For- und Foreach-Implementierungen jedoch in vielen Szenarios gut, und wir hoffen, dass in der Praxis kein großer Bedarf an zusätzlicher Expressivität replizierbarer Tasks besteht.

Der Task-Manager
Alle Tasks werden einem Task-Manager zugeordnet, der die Tasks verwaltet und Arbeitsthreads beim Ausführen von Tasks beaufsichtigt. Obwohl immer ein standardmäßiger Task-Manager verfügbar ist, kann eine Anwendung auch explizit einen Task-Manager erstellen. Die Schnittstelle des Task-Managers wird folgendermaßen definiert:
class TaskManager : IDisposable
{
  TaskManager();
  TaskManager( int maxConcurrentThreads );

  static TaskManager Current     { get; }
  int    MaxConcurrentThreads    { get; }
  ...
}

class Task 
{
  Task( TaskManager taskManager, Action action )
  ...
}
Ein Task-Manager besitzt einen verbundenen Grad an Parallelität, der von der MaxConcurrentThreads-Eigenschaft zurückgegeben wird. Sie gibt dem Manager die ideale Anzahl der Threads an, die zu einem bestimmten Zeitpunkt Tasks ausführen. Dies ist ein Hinweis. Wenn der Manager folglich weitere für die Bearbeitung der Vorwärtsrichtung benötigt, wird eine dynamische Anpassung durchgeführt. Wenn Sie einen Task-Manager erstellen, können Sie diese Zahl explizit bereitstellen. Der Standardeintrag entspricht der Anzahl der Prozessoren.
Im Allgemeinen müssen Sie nie einen Task-Manager explizit erstellen, da immer ein Standard verfügbar ist. Möglicherweise möchten Sie jedoch mehrere Task-Manager verwenden, von denen jeder einen unterschiedlichen Grad an Parallelität besitzt oder jedes Handle einen separaten Satz an Tasks hat. In diesem Fall können Sie einen neuen Task-Manager erstellen und den speziellen Taskkonstruktor verwenden, der einen Task-Manager als erstes Argument verwendet und diesen Task sowie alle untergeordneten Tasks in diesem Task-Manager ausführt. Sehen Sie sich z. B. den folgenden Code an:
using (TaskManager tm = new TaskManager(2)) {  // only use 2 worker
                                               // threads for tasks
  new Task( tm, delegate {
    // tasks created in this delegate use the tm task manager by default
    ...
    // finally, show some statistics
    Console.WriteLine( "statistics: " + tm );  
  }).Wait();
}
Eine andere wichtige Verwendung der Schnittstelle des Task-Managers besteht darin, den gesamten Code mithilfe eines einzigen Arbeitsthreads sequenziell auszuführen. Folglich werden alle Tasks und parallel for-Schleifen sequenziell ausgeführt. Diese Strategie eignet sich ausgezeichnet für Debugvorgänge, mit denen Sie vor der parallelen Ausführung des Codes auf einem Mehrprozessorcomputer überprüfen können, ob die Codefunktionen bei sequenzieller Ausführung richtig funktionieren.

Daan Leijen ist bei Microsoft Research als Forscher tätig. Zurzeit gilt sein Hauptinteresse der deklarativen und funktionalen Programmierung, Typrückschlusssystemen und parallelem Computing.

Judd Hallist Program Manager II bei Microsoft.

Page view tracker