MSDN Magazine > Home > Issues > 2008 > Oktober >  Paradigmenwechsel: Entwurfsüberlegungen für par...
Paradigmenwechsel
Entwurfsüberlegungen für parallele Programmierung
David Callahan

Dieser Artikel basiert auf einer Vorabversion von Visual Studio Tools. Änderungen der Informationen in diesem Artikel sind vorbehalten.

Themen in diesem Artikel:
  • Parallele Datenverarbeitung
  • Gleichzeitige Programmierung
  • Leistungsverbesserungen
 In diesem Artikel werden folgende Technologien verwendet:
Multithreading
Etwa zwischen 1986 und 2002 hat die Mikroprozessorleistung um rund 52 % pro Jahr zugenommen. Dieser verblüffende technische Fortschritt ist das Ergebnis der immer geringeren Kosten für Transistoren, wie durch das Mooresche Gesetz vorhergesagt, und der technischen Errungenschaften der Prozessorhersteller. Die Kombination dieser Faktoren hat der Microsoft-Forscher Jim Larus als „Mooresche Dividende“ bezeichnet. Wie diese Dividende die Entwicklung der modernen Softwarebranche möglich gemacht und Computern zu ihrer heutigen Verbreitung verholfen hat, darüber schreibt er unter go.microsoft.com/fwlink/?LinkId=124628.
Auf Softwareseite wird dieses Phänomen mitunter als „Free Lunch“ bezeichnet, also eine Art „Gratiszugabe“: eine Verbesserung der Anwendungsleistung durch Aktualisieren der zur Ausführung verwendeten Hardware. (Weitere Informationen zu diesem Thema bietet der englischsprachige Artikel „A Fundamental Turn Toward Concurrency in Software“ unter ddj.com/184405990.)
Aber das Prinzip ändert sich: Heute werden Leistungssteigerungen durch das Hinzufügen zusätzlicher Prozessoren erzielt. Die so genannten Mehrkernsysteme sind inzwischen allgegenwärtig. Natürlich lässt sich mit dem Mehrkernansatz die Leistung nur dann verbessern, wenn die Software mehrere Aktivitäten gleichzeitig ausführen kann. Die Leistungsgewinne, die Mehrprozessorcomputer versprechen, lassen sich nur dann tatsächlich erzielen, wenn mit sequenziellen Verfahren einwandfrei ausführbare Funktionen so umgeschrieben werden, dass mehrere Prozessoren verwendet werden können.

Gleichzeitigkeit und Parallelität
Bereits seit längerem mussten sich Programmierer im Zusammenhang mit Parallelität mit einer speziellen Herausforderung auseinandersetzen: der Gleichzeitigkeit. Zum Erzielen einer guten Reaktionsfähigkeit musste eine Möglichkeit gefunden werden, Aktivitäten mit langen Latenzzeiten aus dem Thread auszulagern, der auf Eingabeereignisse reagiert. In der Vergangenheit betrafen die meisten ausgelagerten Aktivitäten Datei-E/As, heute geht es mehr und mehr um die Kommunikation mit Webdiensten.
Microsoft .NET Framework hilft bei diesem typischen Programmierproblem durch sein asynchrones Programmiermodell und das Konzept von Arbeitsprozessen im Hintergrund. Während sich die Komplexitäten der parallelen Programmierung und der gleichzeitigen Programmierung vielfach entsprechen, sind die grundlegenden Muster und Ziele doch verschieden. Mehrkernprozessoren verringern nicht den Bedarf an gleichzeitiger Programmierung, sondern stellen vielmehr ein Verfahren dar, mit dem sich die Hintergrundaktivitäten und andere Berechnungen im System mit dem Ziel einer Leistungsverbesserung optimieren lassen.
Eine weitere bekannte Form der Gleichzeitigkeit betrifft Serveranwendungen. Anwendungen wie z. B. Webserver erhalten Ströme unabhängiger Anforderungen. Diese Programme versuchen, den Systemdurchsatz zu verbessern, indem viele Anforderungen gleichzeitig ausgeführt werden, wobei in der Regel für jede Anforderung ein separater Thread verwendet, aber jede Anforderung sequenziell verarbeitet wird. Durch diese Überlappung wird zwar die Zahl der bedienten Anforderungen pro Sekunde erhöht, die Latenzzeit der einzelnen Anforderungen (Sekunden pro Anforderung) wird jedoch nicht verbessert.
Auch diese Anwendungen profitieren von einer „Gratiszugabe“, und zwar einer, die etwas länger vorhalten wird, da die Mehrkernverarbeitung zusätzliche Kostensenkungen und Durchsatzsteigerungen bietet. Jedoch muss jede für Latenzen anfällige Anforderung, selbst in einer Serverumgebung, irgendwann parallele Programmierverfahren einsetzen, um eine akzeptable Leistung zu erreichen.
Die Programmierung für Gleichzeitigkeit gilt als besonders schwierig, selbst unter Fachleuten. Wenn sich logisch unabhängige Anforderungen verschiedene Ressourcen teilen (Wörterbücher, Pufferpools, Datenbankverbindungen usw.), muss der Programmierer diese gemeinsame Nutzung organisieren, was neue Probleme mit sich bringt. Diese Probleme (Datenraces, Deadlocks, Livelocks usw.) ergeben sich im Allgemeinen aus verschiedenen Ungewissheiten, die entstehen, wenn gleichzeitige Aufgaben dieselben Datenobjekte in einem Programm zu bearbeiten versuchen. Diese Probleme machen das Testen und die Fehlerbehebung – grundlegende Schritte der Softwareentwicklung – äußerst schwierig, wie Rahul Patil und Boby George kürzlich in „Tools und Verfahren zum Identifizieren von Parallelitätsproblemen“ (MSDN Magazin, Juni 2008, msdn.microsoft.com/magazine/cc546569) skizziert haben.
Die parallele Programmierung unterscheidet sich von der gleichzeitigen Programmierung insofern, als für eine logisch separate Aufgabe (die durch bekannte sequenzielle Konstrukte ausgedrückt werden kann, die in allen wichtigen Sprachen unterstützt werden), Möglichkeiten für die gleichzeitige Ausführung geschaffen werden müssen. (Später in diesem Artikel werde ich allgemeine Ansätze dafür beschreiben.) Wenn jedoch Möglichkeiten zur gleichzeitigen Ausführung durch Unteraufgaben eingeführt werden, die Datenobjekte gemeinsam nutzen, müssen plötzlich Sperren und Races berücksichtigt werden. Folglich gibt es bei der parallelen Programmierung in Sachen Korrektheit und Sicherheit dieselben Herausforderungen wie bei sequenziellen Programmen. Dazu kommen die Schwierigkeiten, die mit dem parallelen und gleichzeitigen Zugriff auf gemeinsame Ressourcen verbunden sind.
Die Kombination aus zusätzlichen Konzepten, neuen Fehlermodi und Testschwierigkeiten dürfte jeden Entwickler vor eine Herausforderung stellen. Möchten Sie sich damit wirklich näher beschäftigen? Die Antwort lautet sicher „Nein“! Doch viele werden um dieses Dickicht nicht herumkommen, wenn sie die benötigte Leistung erreichen wollen. Für einige der Hauptprobleme entwickelt Microsoft aktiv Lösungen, aber Lösungsstapel für maximale Produktivität sind noch nicht verfügbar.
Im vergangenen Jahr kündigte Microsoft seine Parallel Computing Initiative (go.microsoft.com/fwlink/?LinkId=124050) an, die nicht nur die Erstellung und effiziente Nutzung paralleler Programme untersuchen, sondern auch die Entwicklung einer neuen Generation von Anwendungen fördern soll, mit der sich die Mooresche Dividende direkt in Kundenvorteile umwandeln lässt. Einige Denkansätze zum Thema Parallelität werde ich später behandeln. Der Artikel „Verbesserte Unterstützung für Parallelität in der nächsten Version von Visual Studio“ von Stephen Toub und Hazim Shafi in dieser Ausgabe beschreibt einige der von uns angebotenen Bibliotheken und Tools. Im Artikel „Lösungen für 11 häufige Probleme in Multithreadcode“ von Joe Duffy, ebenfalls in dieser Ausgabe, werden Verfahren und Ansätze zur Verbesserung der Sicherheit bei gleichzeitigen Anwendungen diskutiert.
Referenzmaterial

„The Future Evolution of High-Performance Microprocessors“, ein Vortrag von Norman Jouppi, Stanford University

„Thousand Core Chips: A Technology Perspective“, ein Vortrag von Shekhar Borkar
Eben habe ich die Formulierung „Möglichkeiten für die gleichzeitige Ausführung“ verwendet, womit eine weitere Unterscheidung zwischen paralleler und gleichzeitiger Programmierung getroffen wird. Wenn ein Entwickler asynchrone Programmiermuster oder Arbeitsprozesse im Hintergrund verwendet bzw. gleichzeitige Anforderungen auf einem Server behandelt, erwartet man, dass all die verschiedenen Threads Fortschritte machen. Der Betriebssystemplaner stellt dabei sicher, dass die Ressourcen gerecht auf alle Threads verteilt werden. Dies ist bei der parallelen Programmierung jedoch nicht sinnvoll. In besonderem Maße gilt dies beim Schreiben von Anwendungen, die auf neue Hardwaresysteme skaliert werden.
Möchten Sie wieder von der Gratiszugabe profitieren, also allein durch Hardwareaktualisierungen die Leistung der Software verbessern, so müssen Sie heute Möglichkeiten für mehr Parallelität schaffen, die morgen verwendet werden können. Ich werde im Folgenden nicht von „Threads“ sondern von „Aufgaben“ sprechen, um diese Verschiebung bei der Implementierung von Parallelität und meine Ansichten zu diesem Thema zu betonen: Entwickler, die sich mit der parallelen Programmierung befassen, werden ermutigt, Probleme in weit mehr Aufgaben zu zerteilen, als heute eigentlich notwendig ist.
Bei der Implementierung paralleler Programmiersysteme muss die Zuordnung dieser Aufgaben zu Systemthreads und Prozessoren nach Bedarf erfolgen. Auch wenn dies nur für wenige Programmierer offensichtlich sein dürfte, bestehen tiefgreifende Unterschiede, wie Systemressourcen vom Betriebssystem in Anspruch genommen und innerhalb eines Prozesses verwaltet werden, um parallele Programme effizient ausführen zu können. Dies ist quasi ein gedopter Threadpool, aber einer, der die Möglichkeiten zur Parallelität in einer Anwendung mit den verfügbaren Ressourcen in der aktuellen Hardware abstimmt, statt Threads einfach nur wie vom Programmierer angegeben zu verwalten.
Bei der gleichzeitigen Programmierung, besonders für Server, ergeben sich viele Schwierigkeiten aus der Koordinierung der Zugriffe zeitintensiver Threads auf gemeinsam genutzte Variable unter Verwendung von Tools wie z. B. Sperren. Durch den Wechsel zu paralleler Programmierung mit Aufgaben kann ein neues Konzept verwendet werden. Ich kann von einer Aufgabe B sprechen, die nach Aufgabe A ausgeführt wird, und Koordinationsprimitive anbieten, um dies auszudrücken. So kann sich der Programmierer mit dem Zeitplan der Arbeit beschäftigen. In der Regel passt dieser Zeitplan perfekt in die algorithmische Struktur des Programms und ergibt sich aus der strukturierten Verwendung von Abstraktionen paralleler Programmierung. Eine gute Abstimmung zwischen den Programmabstraktionen und den parallelen Algorithmen vermindert den Bedarf an traditionellen Gleichzeitigkeitsmechanismen, wie z. B. Sperren und Ereignissen, erheblich und umgeht (wenn auch nicht völlig) viele der Risiken gleichzeitiger Programmierung.
Ich werde nun einige Hauptansätze für die parallele Programmierung beschreiben und ihre Verwendung anhand von Abstraktionen vorführen, die derzeit entwickelt werden. Speziell werde ich mittels C# die C++ Parallel Pattern Library (PPL) sowie Parallel Extensions to .NET (verfügbar unter go.microsoft.com/fwlink/?LinkId=124621) vorstellen.

Strukturiertes Multithreading
Das am häufigsten verwendete Problemlösungsmuster ist „Teile und herrsche“: Dabei wird ein großes Problem in kleinere Probleme mit klar definierten Interaktionen geteilt, die separat gelöst werden können. Die Einzelergebnisse werden dann wieder zur Lösung des ursprünglichen Problems kombiniert. Anwenden lässt sich dieses Verfahren auf Probleme aller Größenordnungen. Da ist es wenig erstaunlich, dass die rekursive Anwendung dieser Idee auch ein Grundelement der parallelen Programmierung ist.
Strukturiertes Multithreading bezeichnet das Anbieten paralleler Formen zentraler, in Blöcke aufgeteilter, sequenzieller Anweisungen. Beispiel: Eine zusammengesetzte Anweisung { A; B; } mit sequenzieller Semantik, bei der erst A und dann B evaluiert wird, lässt sich zu einer parallelen Anweisung machen, indem das gleichzeitige Evaluieren von A und B ermöglicht wird. Das Gesamtkonstrukt wird jedoch nicht beendet, und die Steuerung fährt mit dem nächsten Konstrukt fort, bis beide Unteraufgaben abgeschlossen sind. Dieses Konzept ist nicht neu und unter dem Namen „cobegin-Anweisung“ bekannt. Manchmal wird dies auch als „fork-join-Parallelität“ bezeichnet, um die Struktur zu betonen. Dasselbe Grundkonzept kann auch auf Schleifen angewendet werden, wobei jede Iteration eine Aufgabe definiert, die gleichzeitig mit allen anderen Iterationen evaluiert werden kann. Eine solche parallele Schleife endet erst, wenn alle Iterationsaufgaben beendet sind.
Ein typisches Beispiel für das „Teile und herrsche“-Konzept ist der berühmte QuickSort-Algorithmus (Schnellsortierung). Hier zeige ich eine einfache Parallelisierung dieses Algorithmus mithilfe von C++-Konstrukten. Der grundlegende Algorithmus verwendet das erste Element eines Datenarrays als Schlüssel, partitioniert diese Daten in zwei Teile und aktualisiert das Array so, dass alle Werte, die kleiner als der Schlüssel sind, vor den Werten erscheinen, die größer als der Schlüssel sind. Dieser Schritt wird dann rekursiv angewendet, um die Daten zu sortieren. In der Regel gibt es einen Punkt, wo mithilfe eines nicht rekursiven Algorithmus, z. B. einer Einfügesortierung, der Aufwand in Blattnähe verringert wird.
Abbildung 1 zeigt zwei Features, die Microsoft derzeit entwickelt. Das erste Feature ist die neue Lambda-Syntax von C++, mit der sich eine Ausdrucks- oder Anweisungsliste äußerst einfach als Funktionsobjekt erfassen lässt. Durch die folgende Syntax wird ein Funktionsobjekt erstellt, das bei seinem Aufruf den Code in geschweiften Klammern evaluiert:
[=] { ParQuickSort(data, mid); }
 Abbildung 1 Schnellsortierung 
// C++ using the Parallel Pattern Library 
template<class T>
void ParQuickSort(T * data, int length, T* scratch) {
  if(length < Threshold)  InsertionSort(data,length) 
  else {
    int mid = ParPartition(data[0], data, 
                length, scratch, /*inplace*/true);
    parallel_invoke(
                [=] { ParQuickSort(data, mid); },
                [=] { ParQuickSort(data+mid, length-mid); });
  }
}
Das einleitende [=] kennzeichnet das Lambda und zeigt an, dass alle im Ausdruck referenzierten Variablen außerhalb des aktuellen Bereichs in das Objekt kopiert werden sollen und dass alle Verweise auf diese Variablen im Textkörper des Lambda sich auf diese Kopien beziehen.
Das parallel_invoke ist ein Vorlagenalgorithmus, der (in diesem Fall) zwei solche Funktionsobjekte jeweils als separate Aufgabe evaluiert, damit diese Aufgaben gleichzeitig ausgeführt werden können. Wenn beide Aufgaben enden und (in diesem Fall) die beiden rekursiven Sortierungen beendet sind, wird wieder zu parallel_invoke zurückgekehrt und die Sortierung ist abgeschlossen.
Beachten Sie, dass sich die Parallelität in diesem Beispiel aus der rekursiven Anwendung der „Teile und herrsche“-Parallelität ergibt. Während es auf jeder Ebene nur zwei untergeordnete Aufgaben gibt, ist die Anzahl der Aufgaben bei den Blättern der Berechnung proportional zur Größe der sortierten Daten. Ich habe hier die gesamte Gleichzeitigkeit ausgedrückt, und ein solches Programm lässt sich auf größere Probleme oder mehr Kerne skalieren. Bei einem Problem fester Größe ist die Skalierbarkeit auf einen beliebigen Computer, mit dem ein bestimmter Aufwand verbunden ist, begrenzt. Dies ist eine Folge des berühmten Amdahlschen Gesetzes. Ein zentrales Ziel der Plattformanbieter besteht deshalb darin, diese Aufwände kontinuierlich zu senken. Dadurch kann die Auswahl von Werten wie Threshold (in Abbildung 1) sehr schwierig und für die Zukunft noch schwerer vorherzusagen sein, da sich die Systeme ändern. Einerseits müssen sie so groß sein, dass es nicht zu übermäßigem Aufwand kommt, aber andererseits dürfen sie auch nicht so groß sein, dass die zukünftige Skalierung begrenzt ist.
Dieser Vorlagenalgorithmus ist Teil unserer PPL, die Stephen Toub und Hazim Shafi in dieser Ausgabe beschreiben. Neben parallel_invoke gibt es auch parallel_for_each, das mit dem for_each der Standardvorlagenbibliothek (Standard Template Library, STL) vergleichbar ist. Für parallel_for_each gilt die Semantik, dass es sich bei jeder Iteration um eine separate Aufgabe handelt, die gleichzeitig mit den anderen Iterationsaufgaben ausgeführt werden kann, und dass parallel_for_each zurückkehrt, nachdem alle abgeschlossen sind. Es gibt auch weniger strukturierte Verfahren zur Erstellung einzelner Aufgaben, die mit einer allgemeinen Aufgabengruppe verbunden sind und dann warten, bis alle abgeschlossen sind. Diese bieten die gleiche grundlegende Funktionalität wie die Cilk-Erzeugungsprimitive (supertech.csail.mit.edu/cilk), basieren aber auf Standardfeatures von C++.
Eine mögliche Verwendung paralleler Schleifen ist Code zur Durchführung einer Strahlverfolgung. Ein solches Problem ist für jeden Ausgabepixel trivial parallel und kann in Code wie beispielsweise in Abbildung 2 gefasst werden. Verwendet wurde hier die Parallel.For-Methode von Parallel Extensions to .NET, das dieselben Grundmuster für verwaltete Entwickler enthält, wie sie auch von der PPL für C++-Entwickler unterstützt werden. Hier verwende ich einfache, geschachtelte Schleifen, um den Aufgabenraum zu beschreiben, der jedem Pixel auf einem rechteckigen Bildschirm entspricht. Bei diesem Code wird angenommen, dass die einzelnen im Textkörper einer Schleife aufgerufenen Methoden für die gleichzeitige Ausführung geeignet sind.
 Abbildung 2 Parallele Schleifen 
// C# using Parallel Extensions to the .NET Framework
public void RenderParallel(Scene scene, Int32[] rgb) 
{
    Parallel.For(0, screenHeight, y =>
    {
        Parallel.For (0, screenWidth, x =>  
        {
            Color color = TraceRay(new Ray(camera.Pos, 
                GetPoint(x, y, scene.Camera)), scene, 0);
            rgb[x + y*screenWidth] = color.ToInt32();
        });
    });
}
Werfen Sie hierzu wieder einen Blick in den Artikel von Joe Duffy zur Sicherheit bei Gleichzeitigkeit. Heute, wo die parallele Programmierung noch an ihren Anfängen steht, tragen die Entwickler die Last dieser Probleme. Caveat emptor.
Strukturiertes Multithreading ist ideal für die Arbeit mit Parallelität bei einer natürlichen, vielleicht rekursiven, möglicherweise unregelmäßigen Datenstruktur, bei der die Parallelität diese Struktur widerspiegelt. Dies gilt auch dann, wenn es einen Datenfluss innerhalb des Problems gibt. Das folgende Beispiel durchläuft ein Diagramm in topologischer Reihenfolge, sodass ein Knoten erst dann besucht wird, nachdem alle Vorgänger durchlaufen wurden. Für jeden Knoten gibt es ein Zählfeld, das mit der Zahl der Vorgänger initialisiert ist. Nachdem ein Knoten besucht wurde, verringere ich die Zähler der Nachfolger (wobei ich besonders darauf achte, dass dieser Vorgang sicher ist, da mehrere Vorgängeraufgaben dies gleichzeitig versuchen könnten). Sobald ein Zähler auf null gesetzt wurde, kann dieser Knoten besucht werden:
// C++
void topsort(Graph * g, void (*action)(Node*)) {
    g->forall_nodes([=] (Node *n) {
        n->count = n->num_predecessors();
        n->root = (n->count == 0); 
    });
    g->forall_nodes([=] (Node *n) {
        if(n->root) visit(n, action);
    });
}
Ich nehme an, dass das Diagramm eine Methode exportiert, die durch ein Funktionsobjekt parametrisiert wird, und alle Knoten im Diagramm parallel durchläuft und die Funktion anwendet. Diese Funktion verwendet die PPL intern zum Implementieren dieser Gleichzeitigkeit. Es gibt dann zwei Phasen: In der ersten werden die Vorgänger gezählt und Stammknoten identifiziert. Die zweite startet eine Tiefensuche (Depth-First Search, DFS) von jedem Stamm, bei der die Nachfolger verringert und schließlich besucht werden. Diese Funktion ist in Abbildung 3 dargestellt.
 Abbildung 3 Tiefensuche 
// C++ using the Parallel Pattern Library
// Assumes all predecessors have been visited.
void visit(Node *n, void (*action)(Node*)) {
    (*action)(n);
    // assume n->successors is some kind of STL container
    parallel_for_each(n->successors.begin(), 
         n->successors.end(), 
         [=](Node *s) {
           if(atomic_decrement(s->count) == 0) // safely does "-- s->count" 
            visit(s, action);
    });  
}
Die parallel_for_each-Methode durchläuft die Liste der Nachfolger, wendet auf jeden ein Funktionsobjekt an und ermöglicht die parallele Ausführung dieser Vorgänge. Nicht gezeigt ist die angenommene atomic_decrement-Funktion, die eine Strategie zum Steuern gleichzeitiger Zugriffe verwendet. Beachten Sie, dass sich hier die herkömmlichen Probleme der Gleichzeitigkeit in unseren ansonsten parallelen Algorithmus schleichen und dass sich diese Probleme mit zunehmender Komplexität der elementaren Vorgänge verstärken, wie im Strahlverfolgungsbeispiel.
Die Struktur dieses Algorithmus garantiert, dass „action“ exklusiven Zugriff auf seinen Parameter erhält, sodass keine zusätzlichen Sperren notwendig sind, wenn action diese Felder aktualisiert. Außerdem ist garantiert, dass alle Vorgänger aktualisiert worden sind und sich nicht ändern und dass kein Nachfolger aktualisiert wurde und kein Nachfolger geändert wird, bis action beendet ist. Die Frage, welcher Zustand stabil ist und welche Zustände gleichzeitig aktualisiert werden können, ist ein Hauptproblem bei der Erstellung fehlerfreier paralleler Algorithmen.
Die Stärke des strukturierten Multithreading besteht darin, dass die Möglichkeiten zur parallelen Ausführung (auch über partiell geordnete Berechnungen) leicht ausgedrückt werden können, ohne dass der grundlegende Algorithmus durch zahlreiche Methoden zum Verteilen der Arbeit auf Arbeitsthreads undurchsichtig wird. Dadurch ergibt sich, wie hier gezeigt, ein stärkerer kompositionaler Ansatz, bei dem eine Datenstruktur einige grundlegende parallele Methoden zum Durchlaufen bietet (wie z. B. Graph::forall_nodes), die dann zum Erstellen hochentwickelter paralleler Algorithmen verwendet werden können. Außerdem ist es praktisch, die gesamte Parallelität zu beschreiben, statt nur genug für zwei oder vier Prozessoren zu finden. Dies ist nicht nur einfacher, sondern es bietet natürliche Skalierungsmöglichkeiten für zukünftige Computer, die acht Prozessoren haben – womit wieder unsere „Gratiszugabe“ ins Spiel kommt.

Datenparallelität
Datenparallelität bezeichnet die Anwendung einiger allgemeiner Vorgänge auf ein Datenaggregat, um entweder ein neues Datenaggregat zu erstellen oder das Aggregat auf einen Skalarwert zu reduzieren. Der Parallelität ergibt sich dadurch, dass derselbe logische Vorgang auf jedes Element angewendet wird, unabhängig von den umgebenden Elementen. Es gab viele Sprachen mit verschiedenen Unterstützungsgraden für Aggregatvorgänge, aber das bei weitem erfolgreichste ist das für Datenbanken verwendete: SQL. LINQ bietet sowohl in C# als auch in Visual Basic direkte Unterstützung für SQL-artige Operatoren, und die mit LINQ ausgedrückten Abfragen können einem Datenanbieter wie z. B. ADO.NET übergeben oder anhand von gespeicherten Objektsammlungen oder sogar XML-Dokumenten evaluiert werden.
Teil von Parallel Extensions to .NET ist eine Implementierung von LINQ to Objects und LINQ to XML, die eine parallele Evaluierung der Abfrage umfasst. Diese Implementierung heißt PLINQ und kann zum bequemen Arbeiten mit Datenaggregaten verwendet werden. Das folgende Beispiel zeigt den Kernel des bekannten „K-means“-Algorithmus für statistisches Clustering: Bei jedem Schritt gibt es K Punkte im Raum, die als Clusterzentrum infrage kommen. Zunächst wird jeder Punkt dem nächstgelegenen Cluster zugeordnet. Anschließend wird für alle Punkte, die demselben Cluster zugeordnet sind, das Clusterzentrum neu berechnet, indem der Durchschnitt der Positionen aller Punkte in diesem Cluster berechnet wird. Dies wird fortgesetzt, bis eine Konvergenzbedingung erfüllt ist, bei der die Positionen der Clusterzentren stabil werden. Die zentrale Schleife dieser Algorithmusbeschreibung wird ziemlich direkt in PLINQ übersetzt, wie Abbildung 4 zeigt.
 Abbildung 4 Zentrumsermittlung 
// C# using PLINQ
var q = from p in points.AsParallel()
        let center = nearestCenter(p, clusters) 
                     // "index" of nearest cluster to p
        group p by center into g
        select new
        {
             index = g.Key,
             count = g.Count(),
             position = g.Aggregate(new Vector(0, 0, 0),
                    (accumulated, element) => accumulated + element,
                    (accumulated1, accumulated2) => 
                                     accumulated1 + accumulated2,
                    (accumulated) => accumulated
                    ) / g.Count()
        };
var newclusters = q.ToList();
Der Unterschied zwischen LINQ und PLINQ besteht in der AsParallel-Methode in Bezug auf die Datenerfassungspunkte. Dieses Beispiel zeigt auch, dass LINQ das zentrale „map-reduce“-Schema umfasst, aber mit einer sauberen Integration in herkömmliche Sprachen. Ein ganz spezieller Punkt in diesem Beispiel ist das Verhalten des Aggregate-Operators. Der dritte Parameter ist ein Delegat, der eine Methode zum Kombinieren partieller Summen bietet. Wenn diese Methode vorhanden ist, erfolgt die Implementierung parallel, indem die Eingabe in Teile zerlegt, jeder Abschnitt parallel vermindert und dann diese partiellen Ergebnisse kombiniert werden.
Die große Stärke der Datenparallelität besteht darin, dass geeignete Algorithmen in der Regel viel sauberer und lesbarer ausgedrückt werden, als wenn ein strukturierter Multithreading-Ansatz zum Einsatz kommt, bei dem angenommene Datenstrukturen unübersichtlich werden können. Außerdem bietet die abstraktere Beschreibung dem System mehr Gelegenheit zur Optimierung auf eine Weise, die den Algorithmus bei manueller Durchführung stärker verschleiern würde. Schließlich bietet diese abstrakte Darstellung auch mehr Flexibilität in Sachen Ausführungsziel: Mehrkern-CPU, GPU oder Skalierung auf ein Cluster. Solange die Blattfunktionen, z. B. nearestCenter, keine Nebeneffekte haben, entstehen auch keine der Probleme durch Datenraces oder Deadlocks, wie es sie bei der threadorientierten Programmierung gibt.

Ein häufig verwendetes Verfahren zur Nutzung der Parallelität ist die Verwendung von Pipelining. Bei diesem Modell durchläuft ein Datenelement verschiedene Phasen der Pipeline, wo es untersucht und transformiert wird, bevor es an die nächste Phase übergegeben wird. Der Datenfluss ist die Verallgemeinerung der Idee, bei der Datenwerte Knoten in einem Diagramm durchlaufen und die Berechnung erst bei Verfügbarkeit der Eingabedaten ausgelöst wird. Die Parallelität entsteht durch die gleichzeitige Ausführung unterschiedlicher Knoten und durch die mehrfache Aktivierung eines Knotens für verschiedene Eingabedaten.
Parallel Extensions to .NET unterstützt die Möglichkeit zur expliziten Erstellung einzelner Aufgaben (vom Typ „Task“, der zugrunde liegenden Methode für die Implementierung von strukturiertem Multitasking) und zum Identifizieren einer zweiten Aufgabe, deren Ausführung beginnt, sobald die erste abgeschlossen ist. Das Konzept der Futures dient als Brücke zwischen den Welten der imperativen Programmierung und der Datenflussprogrammierung. Ein Future bezeichnet einen Wert, der durch eine Berechnung erstellt werden wird. Dank dieser Trennung kann ich definieren, was mit einem Wert geschehen soll, bevor dieser Wert bekannt ist.
Die continueWith-Methode auf einem Future wird durch einen Delegaten parametrisiert, der zum Erstellen einer Aufgabe verwendet wird, die ausgeführt wird, sobald der Futurewert verfügbar ist. Das Ergebnis eines Aufrufs an continueWith ist ein neuer Future, der das Ergebnis des Delegatparameters angibt. Bei der imperativen Programmierung werden Aufgaben häufig auf Nebeneffekte untersucht. Deshalb ist continueWith auch als Methode auf Task verfügbar.
Ein Beispiel für diesen Stil ist die Parallelität im Strassen-Algorithmus für die Matrizenmultiplikation. Dabei handelt es sich um eine blockorientierte Version des grundlegenden Algorithmus zur Matrizenmultiplikation. Die zwei Eingabematrizen werden jeweils in vier Unterblöcke geteilt, die dann algebraisch zu den Unterblöcken der Ausgabematrix kombiniert werden. (Details dazu enthält der Wikipedia-Artikel zum Strassen-Algorithmus unter wikipedia.org/wiki/Strassen_algorithm.)
Eine dieser Aufgaben könnte wie folgt aussehen:
// C# using Parallel Extensions to the .NET Framework
var m1 = Future.StartNew(() => (A(1,1)+B(1,1))*(A(2,2)+B(2,2));
Aus Gründen der Klarheit habe ich innerhalb des Delegaten anstelle von Code die mathematische Schreibweise verwendet, um die Berechnung auszudrücken. A und B sind die Eingabematrizen, A(1,1) ist der linke obere Unterblock der Matrix A. Die Addition ist ein Standardvorgang bei Matrizen, und die Multiplikation ist die rekursive Anwendung des Strassen-Algorithmus. Die Ausgabe ist eine temporäre Matrix, die den Ergebnissen dieses Ausdrucks entspricht.
Die ersten sieben Unteraufgaben sind unabhängig, aber die letzten vier benötigen die ersten sieben als Eingabe. Das grundlegende Datenflussdiagramm ist in Abbildung 5 dargestellt. Hier ist die Aufgabe c11 abhängig von den Ergebnissen der Aufgaben m2 und m3. Ich möchte, dass diese Aufgabe erst ausgeführt werden kann, wenn die Eingaben verfügbar sind. In C# kann dies wie folgt ausgedrückt werden: 
var c11 = Task.ContinueWhenAll(delegate { ... },  m2, m3);
Abbildung 5 Unteraufgaben (zum Vergrößern auf das Bild klicken)
Dies zeigt einen Datenfluss mit mittlerem Detailgrad, bei dem die Einheit der Berechnung einige hundert bis einige tausend Operationen sind, im Gegensatz zu einem Datenfluss mit hohem Detailgrad, wo jeder Vorgang eine einzelne arithmetische Operation sein kann. Spezielle Methoden für die Konzepte „when all“ und „when any“ machen dies besser lesbar, können aber einfach zusätzlich zu den grundlegenden Methoden implementiert werden, wie von Stephen Toub erklärt (siehe blogs.msdn.com/pfxteam/archive/2008/07/23/8768673.aspx).
Wie auch bei strukturiertem Multithreading habe ich Möglichkeiten für Parallelität gefunden. Wenn nur ein Prozessor zur Verfügung steht, lassen sich die Unteraufgaben auch einfach seriell in der Reihenfolge ihrer Erstellung ausführen. Stehen aber zusätzliche Ressourcen zur Verfügung, können Sie von diesen profitieren, da die Randbedingungen für die Ausführungsreihenfolge in den Unteraufgaben vorliegen. Im Unterschied zu strukturiertem Multithreading lässt sich praktischerweise eine Aufgabe zum Organisieren des Datenflussdiagramms verwenden, ohne dass die einzelnen Unteraufgaben Kenntnis davon haben, wie ihre Ergebnisse verwendet und kombiniert werden – eine andere Herangehensweise für einen gemeinsamen Methodensatz zur Behandlung paralleler Algorithmen.
Oft werden Daten in eine Anwendung gestreamt und sollen so verarbeitet werden. In diesem Fall sind die Datenpfade ziemlich konstant. Statt eine Aufgabe mit dem Abschluss anderer Aufgaben zu verknüpfen, soll eine Aufgabe mit der Verfügbarkeit des nächsten Datenelements verknüpft werden. Ein Bereich, in dem dieser Ansatz besonders sinnvoll ist, ist die Robotik. Dort befindet sich der algorithmische Entscheidungsfindungsprozess am Zusammenfluss verschiedener Ströme von Sensordaten, die mit unterschiedlichen Geschwindigkeiten ankommen.
Das Microsoft Robotics SDK (go.microsoft.com/fwlink/?LinkId=124622) verwendet diesen Ansatz, bei dem zu den zentralen Konzepten Datenströme (Ports) sowie die Bindung von Aufgaben, die u. a. bei Ankunft von Daten (Nachrichten) aktiviert werden, gehören. Damit haben wir eine Klasse von Problemen eingekreist, die nicht mit dem Wechsel zu Mehrkernsystemen zusammenhängen, sondern bei denen, wie bei Webservern, Parallelität ein zentrales Merkmal ist, das als Teil der Gesamtarchitektur der Anwendung behandelt werden muss. Ähnliche Probleme gibt es auch bei verteilten Anwendungen außerhalb des Robotikbereichs, aber das würde zu weit führen.

Streamingparallelität
Neben dem Mehrkernkonzept ist ein weiteres wichtiges Feature der Computerarchitektur die Mehrschichtigkeit der Speicherhierarchie: Register, eine oder mehrere Ebenen Chipcache, DRAM-Speicher und schließlich Bedarfsauslagerung (demand paging) von Daten auf einen Datenträger. Die meisten Programmierer haben glücklicherweise mit diesem Aspekt der Systemarchitektur nicht viel zu tun bzw. müssen sich darum keine Gedanken machen, weil die Größe ihrer Programme begrenzt ist und ziemlich gut in den Cache passt, an den die meisten Verweise auf Speicher schnell zurückgegeben werden. Wenn sich jedoch ein Datenwert nicht im Chipcache befindet, kann der Abruf aus dem DRAM Hunderte von Zyklen dauern. Die Latenz beim Bereitstellen dieser Daten lässt die Programmausführung scheinbar langsamer werden, da der Prozessor einen Großteil der Zeit mit dem Warten auf die Datenausgabe verbringt.
Einige Prozessorarchitekturen unterstützen mehrere logische Prozessoren pro physischer Verarbeitungskern. Dies wird normalerweise als (Hardware-) Multithreading bezeichnet und zu einem gewissen Grad bereits bei bekannten Prozessoren eingesetzt (z. B. hat Intel dies bei einigen seiner Produkte als Hyperthreading bezeichnet). Eine Motivation für das Multithreading besteht in der Toleranz für die Latenz des Speicherzugriffs. Während ein logischer Hardwarethread auf Speicher wartet, können von den anderen Hardwarethreads Befehle ausgegeben werden. Dieses Verfahren kommt ebenfalls bei modernen GPUs zum Einsatz, allerdings wesentlich aggressiver.
Mit steigender Anzahl von Verarbeitungskernen wächst auch die Anzahl der Anforderungen, die an ein Speichersystem gestellt werden können, und es ergibt sich ein neues Problem, nämlich die Bandbreitenbeschränkungen. Ein Prozessor kann nur eine bestimmte Anzahl von Übertragungen pro Sekunde zum oder vom DRAM-Speicher unterstützen. Wenn diese Zahl erreicht ist, lassen sich durch die weitere Verwendung von Parallelität keine zusätzlichen Vorteile erzielen. Zusätzliche Threads führen nur zu zusätzlichen Speicheranforderungen, die sich einfach hinter früheren Anforderungen einreihen und auf ihre Verarbeitung durch die Speichercontroller warten. GPUs besitzen in der Regel Speichersubsysteme, die eine höhere Gesamtbandbreite unterstützen (gemessen in Gigabyte pro Sekunde), weil sie viel mehr Parallelität unterstützen (und erwarten) und von der zusätzlichen Bandbreite profitieren können.
Aktuelle Mehrkern-Chiparchitekturen können auch die Anzahl der Kerne schneller steigern als die Speicherbandbreite, sodass bei den meisten Problemen, bei denen ein Dataset nicht in den Speicher passt, die Verwendung der Speicherhierarchie von entscheidender Bedeutung ist. Diese Unausgewogenheit macht einen Programmierstil namens Datenstromverarbeitung sinnvoll, bei dem das Hauptaugenmerk darauf liegt, Datenblöcke im Chipcache (oder eventuell im privaten Speicher) abzulegen und dann mit diesen Daten so viele Vorgänge wie möglich durchzuführen, bevor sie durch den nächsten Block ersetzt werden. Diese Vorgänge können intern parallel ablaufen, um mehrere Kerne nutzen zu können, oder die Verarbeitung kann datenflussartig in einer Pipeline stattfinden. Am wichtigsten ist es jedoch, mit den Daten so viele Vorgänge wie möglich durchzuführen, während sich diese im Cache befinden.
Zwar gab es bereits Vorschläge für spezielle Sprachen, um die Angabe von Streamingalgorithmen zu ermöglichen und deren Ausführung sorgfältig zu planen, aber dies lässt sich in vielen Fällen auch durch sorgfältige Planung erreichen. Beispielsweise kann dieses Verfahren auf das QuickSort-Beispiel angewendet werden. Wenn das sortierte Dataset so groß ist, dass es nicht in den Cache passt, werden bei dem einfachen Verfahren, das Arbeit „stiehlt“, die größten und gröbsten Teilprobleme auf verschiedene Kerne verteilt, die dann unabhängige Datasets bearbeiten. Dabei geht der Vorteil eines gemeinsamen Chipcaches verloren.
Wenn Sie jedoch den Algorithmus so ändern, dass Parallelität nur für Datasets verwendet wird, die in den Cache passen, profitieren Sie von den Vorteilen des Streaming (siehe Abbildung 6). Auch in diesem Beispiel werden große Problemstellungen in kleinere Problemstellungen zerlegt (und bei der Partitionierung Parallelität verwendet), aber wenn beide Teilprobleme nicht gleichzeitig in den Cache passen, werden sie sequenziell abgearbeitet. Dies bedeutet, dass ein kleines Dataset nach seinem Laden in den Cache mithilfe aller verfügbaren Ressourcen vollständig sortiert wird, und zwar noch während es sich im Cache befindet und ohne dass es in den Speicher übertragen wird. Erst danach wird das nächste Dataset in Angriff genommen.
 Abbildung 6 Verwendung von Parallelität bei kleineren Datasets 
// C++ using the Parallel Pattern Library
template<class T>
void ParQuickSort(T * data, int length, T* scratch, int cache_size) {
    if(length < Threshold)  InsertionSort(data,length) 
    else {
           int mid = ParPartition(data[0], data, 
                length, scratch, /*inplace*/true);
           if(sizeof(*data)*length < cache_size)
                parallel_invoke(
                  [=]{ ParQuickSort(data, mid, cache_size); },
                  [=]{ ParQuickSort(data+mid, length-mid, cache_size);});
           else {
                  ParQuickSort(data, mid, cache_size);
                  ParQuickSort(data+mid, length-mid, cache_size);
           }
    }
}
Beachten Sie, dass dieser Code explizit mit der Größe des Caches parametrisiert werden musste. Dabei handelt es sich um ein implementierungsspezifisches Feature. Dies ist ungünstig und wird zum Problem, wenn diese Berechnung das System mit anderen Aufträgen oder anderen Aufgaben innerhalb des gleichen Auftrags teilt. Aber es zeigt eine der Schwierigkeiten beim Versuch, durch komplexe parallele Systeme gute Leistung zu erzielen. Nicht immer tritt dieses Problem auf, aber um bei Mehrkernchips gute Leistungen zu erreichen, muss bei der Entwicklung in bestimmten Fällen sorgfältig die Interaktion zwischen Parallelität und Speicherhierarchie abgewogen werden.

SPMD (Single Program, Multiple Data)
Im Rahmen der Hochleistungsdatenverarbeitung wird Parallelität in technischen und wissenschaftlichen Anwendungen schon seit geraumer Zeit genutzt, nachdem in den 1980er Jahren viel in diesem Bereich gearbeitet wurde. Vorherrschend sind hierbei besonders parallele Schleifen über Datenarrays, wobei die Textkörper der Schleifen in der Regel eine recht einfache Codestruktur haben.
Das bereits erwähnte Strahlverfolgungsfragment ist ein Beispiel dafür. Das sich daraus ergebende vorherrschende Parallelitätsmodell wird als SPMD (Single Program, Multiple Data) bezeichnet. Dieser Begriff spielt auf die klassische Taxonomie der Computerarchitektur nach Michael Flynn an, zu der beispielsweise die Typen SIMD (Single Instruction, Multiple Data) und MIMD (Multiple Instruction, Multiple Data) gehören. In diesem Modell lässt sich das Verhalten jedes Prozessors (Arbeiter, Thread) als Satz von Prozessoren verstehen, die logisch an einem einzelnen Problem beteiligt sind, sich aber die Arbeit teilen. In der Regel handelt es sich bei der Arbeit um separate Iterationen einer Schleife, die mit verschiedenen Teilen eines Arrays arbeiten.
Das Prinzip der Arbeitsteilung im SPMD-Stil liegt auch dem OpenMP-Erweiterungssatz (openmp.org) für C, C++, und FORTRAN zugrunde. Das zentrale Konzept ist hier ein paralleler Bereich, wo ein einzelner Aktivitätsthread in ein „Team“ von Threads aufgezweigt wird, die dann zusammen gemeinsam genutzte Schleifen ausführen. Ein Barrierensynchronisierungsmechanismus dient zum Koordinieren dieses Teams, damit es als Gruppe von einer Schleifenschachtelung zur nächsten gelangt. So wird sichergestellt, dass keine Datenwerte gelesen werden, bevor sie von den anderen Threads im Team berechnet wurden. Am Ende des Bereichs treffen die einzelnen Threads des Teams wieder zusammen, und der ursprüngliche Einzelthread wird fortgesetzt, bis er auf den nächsten parallelen Bereich trifft.
Diese Methode der parallelen Programmierung kann auch bei Systemen ohne gemeinsam genutzten Speicher verwendet werden, wo an den Phasengrenzen mittels knotenübergreifender Kommunikation auf Grundlage eines Nachrichtenaustauschs Daten an die Stellen kopiert werden, an denen sie benötigt werden. Dieses Verfahren dient zum Anwenden Tausender Prozessorknoten, um die extreme Leistung zu erreichen, die beispielsweise für die Klimamodellierung und für pharmazeutische Entwicklungen erforderlich sind.
Wie auch bei strukturiertem Multithreading kann sich ein paralleler Bereich in OpenMP innerhalb einer Funktion befinden, d. h., dem Aufrufer dieser Funktion muss nicht bewusst sein, dass in der Implementierung Parallelität zum Einsatz kommt. Beim SPMD-Modell muss jedoch sorgfältig überlegt werden, wie die mit dem Problem verbundene Arbeit auf die Arbeitsprozesse im Team verteilt wird.
Bei einer Ungleichverteilung der Last, bei der ein Arbeitsprozess eine längere Aufgabe als seine Teamkameraden hat, müssen die anderen Teammitglieder auf das Ende der Berechnung warten. Ähnliches gilt für Umgebungen, in denen Systemressourcen gemeinsam mit anderen Aufträgen genutzt werden: Wenn ein Arbeitsprozess vom Betriebssystem unterbrochen wird, damit eine andere Aufgabe ausgeführt werden kann, werden die übrigen Arbeitsprozesse durch dieses künstliche Ungleichgewicht beeinträchtigt.
Zukünftige Hardwaresysteme werden möglicherweise andere Arten von Prozessorkernen besitzen, beispielsweise einige große Kerne, die viel Energie verbrauchen, aber einzelne Threads schnell abarbeiten können, kombiniert mit kleinen Kernen, die weniger Energie benötigen und für parallele Vorgänge optimiert sind. Eine solche Umgebung ist sehr schwierig für ein SPMD-Modell, weil es die Strategie zum Verteilen der Arbeit auf die Arbeitsprozesse sehr kompliziert macht. Solche Probleme werden mit dem Ansatz des strukturierten Multithreading elegant umgangen, aber zum Preis einer geringen Zunahme des Planungsaufwands und eines eventuellen Verlusts der Kontrolle über die Speicherhierarchie für Code, wo OpenMP gut geeignet ist.

Gleichzeitige Datenstrukturen
Die bisherige Diskussion hat sich fast vollständig mit Steuerungsparallelität beschäftigt, also damit, wie sich separate Aufgaben identifizieren und beschreiben lassen, die mehreren verfügbaren Kernen zugeordnet werden können. In Sachen Parallelität gibt es aber auch die Datenseite. Wenn die Wirkung einer Aufgabe darin besteht, eine Datenstruktur zu aktualisieren (beispielsweise einen Wert in eine Hashtabelle einzufügen), kann dieser Vorgang logisch unabhängig von gleichzeitig ausgeführten Aufgaben sein.
Standardimplementierungen von Datenstrukturen unterstützen keinen gleichzeitigen Zugriff und können auf verschiedene Arten scheitern, die überraschend, nicht vorhersehbar und schwer zu reproduzieren sind. Einfach eine Sperre um die gesamte Datenstruktur zu erstellen kann einen Engpass im Programm verursachen, wodurch alle Aufgaben serialisiert werden. Dies führt zu einem Verlust von Parallelität, weil zu wenige Datenspeicherorte gleichzeitig genutzt werden.
Es ist daher wichtig, neben den parallelen Steuerungsabstraktionen neue, gleichzeitige Versionen allgemeiner Datenstrukturen zu erstellen: Hashtabellen, Stapel, Warteschlangen, verschiedene Arten von Mengendarstellungen. Diese Versionen besitzen eine definierte Semantik für die unterstützten Methoden, die gleichzeitig aufgerufen werden können, und sie sind so konstruiert, dass beim Zugriff durch mehrere Aufgaben Engpässe vermieden werden.
Ein Beispiel dafür ist ein Standardansatz zum parallelen Suchen der zugehörigen Komponenten eines Diagramms. Die grundlegende Strategie besteht darin, einige Tiefentraversierungen des Diagramms zu starten, die Knoten zu ermitteln, wo es zu Kollisionen kommt, und dann ein reduziertes Diagramm zu bilden. Die Funktion oberster Ebene hätte die in Abbildung 7 dargestellte grundlegende Struktur.
 Abbildung 7 Tiefentraversierungen 
// C++ 
// assign to each Node::component a representative node in 
// the connected component containing that node
void components(Graph * g) {
  g->forall_nodes([=] (Node * n) { 
    n->component = UNASSIGNED; 
  });
  Roots roots; 
  EdgeTable edges;
  g->forall_nodes([&roots, &edges] (Node * n) {
    if(atomic_claim(n, n)) {
      roots.add(n);
      component_search(n,n, &edges);
    }
  });
  // recusively combine reduced graph (roots, edges)
       ...
}
Wir werden die Komponenten implizit darstellen, indem jeder Knoten auf ein repräsentatives Element zeigt. Als Eingabe dient ein Diagramm, und ich nehme an, dass dieses Diagramm eine forall_nodes-Methode unterstützt, mit der das Diagramm mithilfe von strukturierten Multithreading-Verfahren durchlaufen werden kann. Die Parametrisierung erfolgt durch ein Funktionsobjekt, das auf jeden Knoten angewendet wird. Diese Schnittstelle isoliert den parallelen Algorithmus von den strukturellen Details des Diagramms, behält aber die Haupteigenschaft des strukturierten Multithreading bei, nämlich dass die Parallelität methodenintern ist und hochgradig strukturiert sein kann.
Zuerst werden die Komponentenfelder mit einem definierten Wert initialisiert, dann werden parallele Tiefensuchen logisch von jedem Knoten aus gestartet. Jede Suche beginnt durch Inanspruchnehmen des Startknotens. Da der Knoten auch von einer anderen Suche erreicht werden kann, handelt es sich bei dieser Inanspruchnahme im Grunde um einen atomarischen Test, mit dem festgestellt wird, welche Suche den Knoten zuerst erreicht. Diese Funktion könnte wie folgt aussehen: 
// C++
// atomically set n->commponent to component if it is UNASSIGNED
// return true if and only this transition was made.
bool atomic_claim(Node * n, Node * component) {
    n->lock();  
    Node * c = n->component;
    if(c == UNASSINGED) n->component = n;
    n->unlock();
    return c == UNASSIGNED;
}
Ich habe eine knotenweise Sperre angenommen, aber in diesem einfachen Beispiel hätte ich auch das Windows-Primitiv verwenden können, um einen ineinandergreifenden Vergleich und Austausch für Zeigerwerte durchzuführen. Das Hauptproblem besteht darin, dass eine einzelne globale Sperre zum Schutz vor gleichzeitigem Zugriff durch mehrere Aufgaben unseren Parallelitätsversuch vereiteln würde, da die Datenparallelität entfernt wird, selbst wenn ein hoher Grad an Steuerungsparallelität vorhanden ist.
Es ist nicht genau eine Sperre pro Knoten erforderlich. Vielmehr könnten die Knoten auch einem kleineren Satz von Sperren zugeordnet werden. Dabei muss jedoch darauf geachtet werden, dass kein Skalierungsengpass verursacht wird, indem eine Zahl verwendet wird, die speziell auf heutige Prozessorzahlen zugeschnitten ist. Statt explizite Sperren zu verwenden, untersucht Jim Larus die Verwendung eines „Transaktionsspeichers“. Dadurch soll es Entwicklern ermöglicht werden, einfach Codeintervalle zu deklarieren, die von gleichzeitig ausgeführtem Code isoliert werden, wobei die Implementierung nach Bedarf Sperren einführt, um diese Semantik zu garantieren.
Nachdem Sie eine neue Stammkomponente identifiziert haben, fügen Sie diese den gemeinsam genutzten Datenstrukturstämmen hinzu. Logisch ist dies ein Satz aller Stammkomponenten, die in diesem ersten Schritt des Algorithmus gefunden wurden. Während es logisch nur eine Instanz dieses Containers gibt, muss seine Implementierung für gleichzeitige Hinzufügungen optimiert werden. Als Teil von PPL und Parallel Extensions to .NET wird Microsoft entsprechende Implementierungen von Vektoren, Warteschlangen und Hashtabellen anbieten, die als Bausteine verwendet werden können.
Die Tiefensuche von einem Knoten aus iteriert über die benachbarten Knoten und versucht, jeden für seine Komponente in Anspruch zu nehmen. Wenn dies erfolgreich ist, wird dieser Knoten rekursiv bearbeitet (siehe Abbildung 8).
 Abbildung 8 Rekursive Suche 
// C++ using the Parallel Pattern Library
// a depth first search from "n" through currently 
// unassigned nodes which are 
// set to refer to "component". Record inter-component edges in "edges"
void component_search(Node * n, Node * component, EdgeTable * edges) {

  parallel_for_each(n->adjacents.begin(), 
    n->adjacents.end(), 
    [=] (Node * adj) {
    if(atomic_claim(adj, component) 
      component_search(adj, component, edges);
    else if(adj->component != component) {
      edges->insert(adj->component, component);
    }
  });
}
Wenn dieses Inanspruchnehmen fehlschlägt, also diese oder eine andere Aufgabe den Knoten zuerst erreicht hat, muss untersucht werden, ob er einer anderen Komponente hinzugefügt wurde. Wenn dies der Fall ist, werden die zwei Komponenten in der freigegebenen Datenstruktur, EdgeTable, aufgezeichnet. Diese Tabelle kann mit einer gleichzeitigen Hashtabelle erstellt werden, um die Doppelung von Informationen zu vermeiden. Wieder ist dies eine logisch gemeinsam genutzte Struktur, bei der angemessene Unterstützung für gleichzeitigen Zugriff sichergestellt sein muss, um Konflikte und Verlust effektiver Parallelität zu vermeiden.
Die beiden Strukturen, Stämme und Ränder bilden ein logisches Diagramm, das die Konnektivität zwischen den ursprünglichen Komponentenschätzungen aufzeichnet. Zum Abschließen des Algorithmus werden verbundene Komponenten in diesem logischen Diagramm gesucht. Anschließend werden diese Informationen auf Knotenebene mit abschließenden Vertretern aktualisiert (nicht gezeigt).

Zusammenfassung
Ein Verlust der Datengleichzeitigkeit ist selbstverständlich nur eine von vielen Überraschungen bei der parallelen Programmierung. Seien Sie daher nicht überrascht, wenn Ihre ersten Versuche mit diesem neuen Ansatz entweder unerwartet fehlschlagen (z. B. weil Sperren vergessen wurden) oder langsamer sind als die sequenzielle Ausführung (Aufgaben zu klein, zu viele Sperren, Verlust von Cacheeffizienz, unzureichende Speicherbandbreite, Datenkonflikte usw.).
Indem Microsoft weiter in den Bereich der parallelen Programmierung investiert, werden sich die Abstraktionen ebenso wie Tools zur Diagnose und Vermeidung zugehöriger Probleme ständig verbessern. Außerdem ist zu erwarten, dass sich die Hardware verbessert und neue Features integriert werden, die diverse Kosten senken. Aber das braucht Zeit.
Der Wechsel zur Parallelität ist ein Wendepunkt für die Softwarebranche, und es müssen neue Verfahren eingesetzt werden. Entwickler müssen Parallelität für diejenigen Teile ihrer Anwendungen nutzen, die heute zeitkritisch sind oder in Zukunft mit größeren Datasets ausgeführt werden sollen. Ich habe verschiedene Arten des Verständnisses und der Verwendung von Parallelität in Anwendungen beschrieben, und ich habe dies anhand von neuen Tools verdeutlicht, die bei Microsoft im Rahmen unserer Parallel Computing Initiative entwickelt werden.


Einblicke: Die nächste Steigerung um den Faktor 100
Seit 1975 ist die Mikroprozessorleistung in jedem Jahrzehnt um den Faktor 100 gestiegen, getrieben von exponentiellem Wachstum bei den Taktfrequenzen (Faktor 3000) und Transistorzahlen (Faktor 300.000). Die Befehlsleistung ist um das Acht- bis Einhundertfache gewachsen (man vergleiche ein 8-Bit-ADD mit einem SSE4.1-DPPS-Dot-Produkt aus gepackten 4-SP-Float-Vektoren) und die On-Die-Caches sind jetzt so groß wie die ersten Festplatten. Unsere Branche hat jeden Faktor 100 genutzt, um immer und immer wieder beeindruckende neue Erfahrungen zu ermöglichen. Das ist der Wind in unseren Segeln.
Aber nun müssen wir einen anderen Weg einschlagen, um eine erneute Steigerung um den Faktor 100 zu erreichen. Wir können weiter auf die Dividende des Mooreschen Gesetzes warten, die vier weitere Verdoppelungen der Transistorzahl pro Chipfläche (die 32-, 22-, 16-, 11-nm-Knoten) in einem Zwei-Jahres-Rhythmus verspricht. Aber inzwischen befinden wir finden uns in den asymptotisch sinkenden Randbereichen verschiedener Wachstumskurven, insbesondere Spannungsskalierung und Verlustleistung (Energiegrenze), Parallelität auf Anweisungsebene (Komplexitätsgrenze) und Speicherlatenz (Speichergrenze).
Die Energiegrenze Die dynamische Leistung eines Mikroprozessors ist proportional zu NCV2f, also der Anzahl der schaltenden Transistoren × Schaltkapazität × Spannung im Quadrat × Frequenz. Mit jeder Verkleinerung der Lithografieknoten verdoppelt sich potenziell die Anzahl der Transistoren pro Chipfläche (↑N), die Transistoren werden kleiner (↓C) und die verwendete Schaltspannung sinkt (↓V). Die Versorgungsspannung ist bereits von 15 V auf heute 1 V zurückgegangen, was die zum Schalten erforderliche Energie um den Faktor 100 verringert hat. Leider liegt die Schwellenwertspannung eines CMOS bei mindestens 0,7 V, sodass weitere Einsparungen maximal in Höhe von (1,0/0,7) × 2 = Faktor 2 zu erwarten sind. Da jedoch gleichzeitig die Komplexität (↑N) und die Frequenz (↑f) der Mikroprozessoren gesteigert wurde, ist trotz dieser Einsparungen die Energieabgabe eines Die auf nur wenigen Quadratzentimetern Silizium von 1 W auf 100 W gestiegen, womit die Grenzen heute machbarer Kühllösungen erreicht sind. Es ist nur noch wenig Spielraum vorhanden – die Energiefrage ist ein Nullsummenspiel. Die Taktfrequenzen werden sich nie wieder so schnell vervielfachen, wie sie es in der Vergangenheit getan haben. Eine erneute Verbesserung um den Faktor 100 werden wir hier nicht herausholen können.
Die Komplexitätsgrenze Hochleistungsmikroprozessoren nutzen eine komplexe, ungeordnete Ausführungsreihenfolge, um innerhalb eines Threads die Parallelität auf Befehlsebene auszunutzen. Aber der Möglichkeit weiterer deutlicher Verbesserungen mit diesem Ansatz sind praktische Grenzen gesetzt. Der serielle Code selbst und die Datenabhängigkeiten begrenzen die mögliche nutzbare Parallelität. Auf Hardwareseite werden mitunter bis zu N2 mehr Stromkreise benötigt, um N Vorgänge parallel ausführen zu können. Die Entwurfs- und Überprüfungskosten im Vorfeld wachsen proportional. Was aber am wichtigsten ist: Angenommen, die parallele Software kommt, dann ergibt sich aus der Energiegrenze, dass energieeffizientere Mikroarchitekturen bessere Architekturen sind: Ergebnisse/Joule sticht Ergebnisse/Nanosekunde aus.
Die Speichergrenze Die DRAM-Zugriffslatenz (Verzögerung) verbessert sich nur relativ langsam. Daher nutzen CPUs Caches, um den DRAM vollständig zu meiden. Aber Caches sind eine teure Lösung: Ein vollständiger Cachefehler kann heute bis zu 300 Taktzyklen kosten. Als Faustregel gilt, dass sich durch eine Vervierfachung der Cachegröße die Zahl der Cachefehler halbieren lässt. Die Komplexität eines CPU-Kerns ergibt sich zu einem erheblichen Teil aus der Tolerierung langer und nicht voraussagbarer Speicherzugriffe. Es ist jedoch einfacher, die Speicherbandbreite zu skalieren. Dann lässt sich Parallelität auf Speicherebene anwenden: parallele Softwarethreads, die viele gleichzeitige Speicherzugriffe gleichzeitig ausgeben. Zwar kann es immer noch vorkommen, dass ein einzelner Thread lange auf seinen Zugriff warten muss, aber der Gesamtdurchsatz der parallelen Berechnung ist sehr hoch.
Die serielle Prozessorleistung wird sich weiter verbessern, im nächsten Jahrzehnt aber deutlich langsamer. Gute CPU-Designer und Compilerentwickler werden immer wieder Möglichkeiten finden, hier und dort weitere 5 % oder 10 % herauszuholen. Was selbstverständlich gut ist, weil eine Menge guter Software seriell ist und dem Amdahlschen Gesetz unterliegt. Aber das alles kann nicht die nächste Verhundertfachung bringen, auf die wir warten. Dazu wird Software erforderlich sein, die Parallelität nutzt. Sofern ausreichend gute Software auf den Markt kommt, stehen die Prozessoranbieter bereits in den Startlöchern, um parallele Prozessoren mit Dutzenden von Kernen und Speicherlösungen für hohe Bandbreite zu liefern. Wenn wir die Software liefern, werden sie nachziehen.
– Jan Graut, Softwarearchitekt, Parallel Computing Platform Team, Microsoft

David Callahan ist Distinguished Engineer und leitender Architekt im Parallel Computing Platform Team für Visual Studio. Er kam vom Supercomputerhersteller Cray Inc. zu Microsoft und besitzt umfassende Erfahrung im Bereich der Parallelisierung von Compilern sowie in Bezug auf parallele Algorithmen, Architekturen und Sprachen.
Page view tracker