Verwenden der Parallelität für Skalierbarkeit

Veröffentlicht: 04. Sep 2006

Von Joe Duffy

Seit geraumer Zeit ist das Thema „Parallelität“ in aller Munde. Dies liegt hauptsächlich daran, dass die bedeutendsten Hardwarehersteller sowohl Client- als auch Servercomputer mit mehreren Prozessorkernen ausstatten möchten, sowie daran, dass die heutige Software für solche Hardware nicht ausgelegt ist. Viele Artikel konzentrieren sich auf die Sicherung der Parallelität im Code, sie beschäftigen sich jedoch nicht damit, wie der Code überhaupt Parallelität erhält.

Laden Sie den Code zu diesem Artikel herunter: CLRInsideOut2006_09.exe (151 KB)

Beide Aufgaben sind wichtig und können sich aus unterschiedlichen Gründen als schwierig erweisen. Die zufällige Erstellung von neuen Threads und die Verteilung von Aufrufen an ThreadPool.QueueUserWorkItem über Ihre gesamte Codebasis wird nicht zu den gewünschten Ergebnissen führen. Sie müssen schon strukturierter vorgehen. Verschaffen wir uns zuerst einen Überblick über die Situation.

Im Laufe der 90er Jahre hat sich Parallelismus dahingehend entwickelt, dass Softwareskalierbarkeit in neueren Installationen der Prozessorarchitektur automatisch aktiviert wurde. Den meisten Nutzern muss es nicht unbedingt bewusst gewesen sein, dass es Parallelismus gibt oder sogar Codes auf eine andere Art geschrieben werden können, um dessen Vorteile zu nutzen. Nichtsdestotrotz wurde Parallelismus verwendet. ILP-Techniken (Instruction-Level Parallelism) sind unter vorhandenen sequenziellen Programmierungsmodellen schichtweise angeordnet und werden mit der Abstufung eines einzelnen Anweisungsstreams durchgeführt. Hierbei werden Vorhersagen für Ausführungszweige, Gewinnerwartungen und Datenflussausführungen in beliebiger Reihenfolge eingesetzt. Mithilfe von Pipelines kann zum Beispiel die Leistung um 25-30 Prozent gesteigert werden, je nach Tiefe der Pipeline und Arbeitslast. Aufgrund der gemeinsamen Verwendung solcher Techniken zusammen mit Erhöhung der Taktrate wird gewährleistet, dass die Software bei jeder neuen Hardwaregeneration schneller ausgeführt wird und hierbei nur minimale zusätzliche Softwarebeteiligung erforderlich ist.

Die Chiphersteller gehen nach wie vor davon aus, dass das Mooresche Gesetz weiterhin Gültigkeit hat (Verdopplung der Anzahl von Transistoren in Prozessoren ungefähr alle 18 Monate), für die Entwickler ändern sich jedoch die Verwendungsmöglichkeiten dieser Transistoren allmählich. Die Erhöhung der Taktrate neuer Chips mit der gleichen Geschwindigkeit wie in der Vergangenheit ist hauptsächlich aufgrund der erzeugten Wärme einfach nicht möglich. Die zusätzlichen Transistoren können jedoch dazu verwendet werden, weitere Speicher mit geringer Latenz und, falls die Software dafür ausgelegt ist, mehrere Kerne auf dem Chip zu platzieren. Achten Sie auf die Anforderungen. Die meiste Software ist heute single-threaded. Dies muss sich jedoch ändern, wenn Sie die zusätzlichen Kerne nutzen möchten.

In gewisser Weise wurde ein großer Teil der Verantwortung, die Software bei der nächsten Hardwaregeneration schneller ausführen zu können, von der Hardware an die Software übertragen. Mittel- bis langfristig gesehen bedeutet dies, dass Sie darüber nachdenken müssen, Architekturen anders zu entwickeln und zu implementieren, wenn der Code automatisch schneller ausgeführt werden soll. In diesem Artikel werden diese Architekturprobleme in aller Gründlichkeit untersucht und Ihnen alle Aspekte vorgestellt. Langfristig werden möglicherweise neue Programmierungsmodelle entwickelt, mit denen viele der auftretenden Herausforderungen abstrahiert werden können.

Auf dieser Seite

Hardwarethreads – eine Geschichte
Speicherhierarchien
Arbeitseinheiten
Wissen über Zeitaufwand
Definieren von Grenzen
Anzahl der Aufgaben
Freigegebener Status
Tools zur Profilerstellung von Parallelismus
Schlussbemerkung
Der Autor

Hardwarethreads – eine Geschichte

Symmetrische Multiprozessorcomputer (SMP-Computer), die unter Windows® ausgeführt werden können, sind bereits seit vielen Jahren erhältlich, finden jedoch normalerweise Einsatz bei Servern und High-End-Workstations. Diese Computer sind mit einer oder mehrere Platinen ausgestattet, wobei jede Platine in der Regel mehrere Sockets enthält, die wiederum über eine voll funktionsfähige CPU verfügen. Jede CPU besitzt On-Die-Cachespeicher, Interrupt-Controller, flüchtige Statusregister und einen Prozessorkern einschließlich Ausführungseinheiten. Der Windows-Auftragsplaner ordnet einzelnen, vollkommen unabhängigen CPUs einzelne Softwarethreads zu. Diese CPUs werden hinsichtlich Hardwarethreads als CPUs mit Single-Threading bezeichnet. Da alle Einheiten relativ unabhängig voneinander betrieben werden (abgesehen von der gemeinsam verwendeten Speicherarchitektur, die weiter unten erläutert wird), lässt sich der Ausführungsdurchsatz für jede neu hinzugefügte CPU erhöhen, wenn ausreichend Softwarethreads für die Ausführung zur Verfügung stehen.

Intel hat die HT-Technologie (Hyper-Threading) für Pentium  4-Prozessoren eingeführt. Mit HT werden zusätzliche Interrupt-Controller und flüchtige Statusregister in eine einzelne physische CPU in einen einzelnen Socket integriert, so dass mehrere Softwarethreads auf verschiedenen Logikprozessoren parallel ausgeführt werden können, obwohl sie die gleichen Ausführungseinheiten nutzen. Diese Vorgehensweise entspricht nahezu der von Supercomputerfirmen wie z. B. Tera durchgeführten Methode. Unter anderem können aufgrund der Latenz beim Zugriff auf den Speicher die Anweisungen zwischen zwei logischen CPU-Threads häufig ineinander verzahnt sein, was zu einer parallelen Beschleunigung führt. In diesem Sinne gelten HT-fähige CPUs als two-threaded CPUs, da der Windows-Auftragsplaner einem HT-Prozessor zwei ausführbare Threads gleichzeitig zuweisen kann. In der Praxis eignet sich HT für einige Arbeitslasten, und bei Programmen wurde eine Steigerung von 15-40 Prozent beobachtet.

Die Multi-Core-Technologie, die bereits für Client- und Servercomputer gleichermaßen verfügbar ist, repliziert die Pro-CPU-Architektur auf einem einzelnen Chip, so dass ein einzelner Socket mehrere, voll funktionsfähige CPUs enthalten kann. Die Dual-Core-Technologie steht nun zur Verfügung (zwei Kerne auf einem Chip), 4-Core- und 8-Core-Technologien usw. sind auch möglich. Im Gegensatz zu HT verfügen Multi-Core-CPUs über einzelne Ausführungseinheiten und sind daher normalerweise in der Lage, eine erhebliche parallele Beschleunigung zu erzielen. Ähnlich wie einzelne CPUs unterscheidet sich jeder Kern logisch vom anderen, abgesehen von der gemeinsam verwendeten Speicherarchitektur. Dies bedeutet, dass der Durchsatz durch Verwendung von zwei Kernen verdoppelt werden kann. Folglich stellt die Anzahl der Kerne die Anzahl der Threads dar, die gleichzeitig ausgeführt werden können. Diese Technologien schließen sich natürlich nicht gegenseitig aus. Ein HT-Computer mit 4 Sockets und 4 Kernen ergibt 32 Hardwarethreads. Das ist wirklich eine leistungsstarke Lösung.

Speicherhierarchien

Die Interaktion zwischen Speichern stellt häufig einen bedeutenden Faktor bei der Leistung moderner Software dar. Herkömmliche Computer verfügen über ein ziemlich komplexes Speichersystem, das mehrere Cachespeicherstufen zwischen den Prozessoren und den eigentlichen DRAM-Banken umfasst. SMP-Computer weisen in der Regel konsistente hierarchische Designs auf, obwohl außergewöhnlichere Architekturen angeboten werden und mit zunehmender Verfügbarkeit von stark parallelen Computern eine immer breitere Verwendung finden könnten. Eine solche außergewöhnlichen Architektur ist beispielsweise Non-Uniform Memory Access (NUMA), wobei Knoten von mehreren CPUs mehrere Hauptspeicher zugeordnet werden. Die knotenübergreifende Kommunikation ist möglich, jedoch auch sehr teuer. Verschiedene Windows-Komponenten und CLR ändern ihre Strategien, um NUMA gerecht zu werden. Intelligente parallele Codes müssen häufig gleich vorgehen.

Die den Cache entlastende parallele Software setzt den Speicher unter Ausnutzung der Lokalität intelligent und effizient ein und reduziert so die für eine bestimmte Berechnung erforderliche gesamte Anzahl von Zyklen. Es gibt zwei bedeutende Arten von Lokalitäten. Zuerst wäre die räumliche Lokalität zu nennen: Eng nebeneinander liegende Daten im Speicher werden bei Programmvorgängen eng zusammen verwendet. Während bei umfangreicheren Cachezeilen möglicherweise mehr Daten als nötig im Cache gespeichert werden, nutzt ein Programm mit guter räumlicher Lokalität dies aus, indem nachfolgend auf andere, bereits im Cache gespeicherte Adressen zugegriffen wird. Der CLR Garbage Collector maximiert die räumliche Lokalität, indem zum Beispiel Zuordnungen zusammenhängend vorgenommen werden.

Bei der zeitlichen Lokalität verbleibt der Speicher aus einem bestimmten Grund im Cache: Wenn kürzlich auf diesen zugegriffen wurde, ist zu erwarten, dass demnächst ein weiterer Zugriff erfolgt. Moderne Cachespeicher wenden Auslagerungsrichtlinien an, die mithilfe von Pseudo-LRU-Techniken (Least-Recently-Used) optimiert werden.

Sorgfältig geschriebene parallele Software kann sogar extrem lineare Beschleunigungen überwachen, die dadurch entstehen, dass mehr Daten im Cache verbleiben und weniger Daten von anderen Threads gemeinsam verwendet werden. Dies bedeutet, dass die Software auf einem Computer mit n CPUs n Mal schneller ausgeführt werden kann als auf einem Computer mit einer CPU. Der Zeitaufwand für einen Cachefehltreffer ist jedoch ziemlich hoch. Dies wird in Abbildung 1 mit einem relativen Vergleich der Cachezugriffskosten weiterführend dargestellt. Wie bei allen Faustregeln gilt, dass die Zahlen mit Vorsicht zu genießen sind und besonders auf die unterschiedlichen Aufträge geachtet werden sollte.

Abbildung 1: Logarithmisches Diagramm: Vergleich der Zugriffskosten
Abbildung 1 Logarithmisches Diagramm: Vergleich der Zugriffskosten

Parallele Software muss insbesondere die Lokalität berücksichtigen. Zwei Threads, die Daten auf sich überschneidenden Cachezeilen kontinuierlich aktualisieren, können einen Ping-Pong-Effekt der Cachezeile verursachen. Hierbei verbringen die Prozessoren sehr viel Zeit damit, einen exklusiven Zugriff auf eine Cachezeile zu erlangen, indem unter anderem die Kopien anderer Prozessoren ungültig gemacht werden. Einige Cachezeileninteraktionen sind offensichtlich, da auf der Anwendungsebene Daten tatsächlich gemeinsam verwendet werden. Andere Interaktionen sind weniger offensichtlich und resultieren daraus, dass sich Daten im Speicher eng nebeneinander befinden. Dies lässt sich jedoch leider nicht durch eine einfache Untersuchung des Algorithmus bestimmen.

Ebenso kann die Threadmigration, die später noch detaillierter erläutert wird, dazu führen, dass ein Thread auf einen anderen Prozessor übertragen wird und nachfolgend alle Cachezeilen, die sich vorher auf dem ursprünglichen Prozessor befanden, erfasst und ungültig gemacht werden müssen. Der Zeitaufwand dieser Cachemigration kann für jeden Zeilenzugriff, der eine Migration anfordert, den Zeitaufwand eines On-Die-Cachetreffers bis zu 50 Mal überschreiten. Bei NUMA-Computern hat dies möglicherweise aufgrund des Zeitaufwands für die Kommunikation zwischen den Knoten schwerwiegende Konsequenzen, obwohl das Migrationsproblem teilweise durch intelligente Verwendung der Prozessoraffinität vermieden werden kann. Dieser Zeitaufwand sollte beim Schreiben eines hochgradig parallelen Codes berücksichtigt werden. Mit der neuen GetLogicalProcessorInformation-API in Windows Vista können Sie Angaben zur Computerarchitektur abrufen, einschließlich Cachelayout und NUMA-Informationen, die zum Beispiel während der Zeitplanung dynamisch verwendet werden können.

Arbeitseinheiten

Damit die Software parallel ausgeführt wird, müssen die mit den Algorithmen zusammenhängenden Probleme in mehrere kleinere Probleme aufgeteilt werden: kleinere Arbeitseinheiten, die als Aufgaben bezeichnet werden. Eine Aufgabe erfordert eine Eingabe und erzeugt eine Ausgabe, ganz gleich, ob es sich bei dieser Ausgabe um ein Datenelement oder eine Aktion handelt. Sie kann alleine ausgeführt werden, obwohl sie möglicherweise leicht vom Status oder der Auftragserteilung abhängt, was zu Beginn nicht unbedingt ersichtlich ist.

Sie sagen jetzt vielleicht, dass dies auch für Funktionen gilt. Im Gegensatz zu normalen Funktionen, die beim Schreiben des Codes statisch definiert werden, müssen die Grenzen einer Aufgabe jedoch häufig dynamisch festgestellt werden, um die bei einer beliebigen Anzahl von CPUs skalierte Software zu schreiben. Oder zumindest müssen die Aufgaben in einer intelligenten Architektur stattfinden, die weiß, ob es sich lohnt, eine Aufgabe parallel auszuführen. Damit eine Aufgabe parallel ausgeführt werden kann, muss der Code darüber hinaus so eingerichtet werden, dass er parallel und nicht am aktuellen Thread sequentiell abgerufen wird. Unter Windows bedeutet dies normalerweise, dass der Code auf einem eigenen Betriebssystemthread ausgeführt wird. Bei CLR wird die Arbeit zur Ausführung auf dem ThreadPool möglicherweise in eine Warteschlange eingereiht.

Die physische Ausführungseinheit unter Windows ist ein Thread. Jeder Prozess entsteht durch einen einzelnen Thread, jedoch kann der in diesem Prozess ausgeführte Code natürlich zusätzliche Threads einführen und später nach Belieben löschen. Der Windows-Auftragsplaner ist für die Zuweisung von Threads zu Hardwarethreads und die Codeausführung verantwortlich. Wenn mehr Threads als Hardwarethreads vorhanden sind, muss der Auftragsplaner etwas ausgefeilter sein. Er wählt den ausführbaren Thread mit der höchsten Priorität (in Abhängigkeit vom intelligenten Anti-Starvation-Algorithmus) und führt ihn aus, bis ein Quantum abgelaufen ist. Sobald ein Quantum abgelaufen ist, tritt ein Kontextwechsel auf, und der gleiche Scheduling-Algorithmus wählt den nächsten auszuführenden Thread aus. Die Länge eines Quantums hängt vom Typ und der Konfiguration des Betriebssystems ab. Normalerweise beträgt sie ungefähr 20 ms für Clientplattformen und 120 ms für Serverplattformen. Ein Thread kann als Folge eines Ein-/Ausgabevorgangs blockiert werden, indem versucht wird, eine umstrittene Sperre abzurufen usw. In diesem Fall wählt der Auftragsplaner, genau wie bei einem Kontextwechsel, einen neuen auszuführenden Thread aus.

Wie bereits weiter oben erwähnt, ist es für die Leistung von herkömmlichen SMP-Systemen unerlässlich, dass sich so viele Daten wie möglich im Cachespeicher befinden. „Daten“ in diesem Sinne beziehen sich auf den ausgeführten Code, die vom Algorithmus des Threads geänderten Heap-Daten sowie den Stapel des Threads. Während Threads kontinuierlich zwischen CPUs übertragen werden, nutzt Windows automatisch eine so genannte ideale Prozessoraffinität zur Maximierung der Effizienz des Cachespeichers. Ein auf CPU 1 ausgeführter Thread, der einen Kontextwechsel erfährt, wird versuchen, wieder auf CPU 1 ausgeführt zu werden, da er davon ausgeht, dass sich noch einige seiner Daten im Cachespeicher befinden. Wenn CPU 1 ausgelastet ist, CPU 2 jedoch nicht, kann der Thread stattdessen CPU 2 zugewiesen werden, mit allen implizierten negativen Effekten des Cachespeichers.

Wissen über Zeitaufwand

Die Verwendung von Threads hat ihren Preis. Sie tragen zum Zeitaufwand für CPU und Speicher bei, den Sie berücksichtigen sollten. Wenn Sie die Skalierbarkeit der Algorithmen mithilfe von Parallelität erhöhen möchten, werden Sie wahrscheinlich genauso viel (oder sogar noch mehr) Zeit für herkömmliche Profilerstellungsvorgänge bezüglich der Leistung aufwenden. Die Ausführung eines nicht sorgfältig erstellten Algorithmus führt nur dazu, dass mehr Systemressourcen belegt werden. Die Gewährleistung, dass die wichtigsten kritischen Codeabschnitte so effizient wie möglich sequentiell ausgeführt werden, ist für die Ausnutzung der parallelen Skalierung von entscheidender Bedeutung.

Für die Ermittlung, welchen Zeitaufwand Sie gewähren können, gelten einige allgemeine Faustregeln. Der Zeitaufwand für die Erstellung eines Windows-Threads beträgt ungefähr 200.000 Zyklen, dagegen beträgt der Zeitaufwand für eine Löschung ca. 100.000 Zyklen. Sie wissen also sofort, dass ein erheblicher Overhead anfällt, wenn Sie einen neuen Thread entwickeln möchten, der 100.000 zusätzlichen Arbeitszyklen entspricht. Dabei werden Sie aller Wahrscheinlichkeit nach jedoch keinerlei Beschleunigung feststellen.

Der Speicher-Overhead hängt von der Konfiguration ab. Die meisten verwalteten Threads reservieren jedoch 1 MB Stapelplatz für Benutzer und führen für den gesamten Speicherplatz einen Commit durch. Dies bedeutet, dass der Speicher entweder im echten RAM oder in der Auslagerungsdatei physisch gesichert werden muss. Ein kleiner Satz von Kernelstackseiten ist ebenfalls erforderlich: drei Seiten bei 32-Bit-Systemen und sechs Seiten bei 64-Bit-Systemen. Ein zusätzlicher virtueller Speicher mit 10 - 20 KB wird von anderen Datenstrukturen verwendet, ist jedoch im Vergleich mit dem für den Stapel erforderlichen Speicher winzig klein. Threads der grafischen Benutzeroberfläche sind dennoch weiterhin etwas zeitaufwändiger, da sie zusätzliche Datenstrukturen einrichten müssen, wie beispielsweise eine Nachrichtenwarteschlange.

Wenn zu viele Threads mit gleicher Priorität vorhanden sind, müssen Sie häufiger einen Kontextwechsel durchführen. Ein Kontextwechsel umfasst 2.000 - 8.000 Zyklen, je nach Systemauslastung und Architektur. Hierbei werden auch der aktuelle flüchtige Status gespeichert, indem der nächste auszuführende Thread ausgewählt wird, und der flüchtige Status des nächsten Threads wiederhergestellt. Dies erscheint auf den ersten Blick vielleicht nicht viel, besonders im Vergleich zur Dauer eines Quantums und zum Zeitaufwand für nachfolgende Cachefehltreffer, bedeutet jedoch, dass reiner Overhead auf Kosten der Ausführung des Anwendungscodes anfällt.

In Anbetracht der Tatsache, dass Sie den Zeitaufwand für die Einführung und das Löschen von neuen Betriebssystemthreads sowie die negativen Konsequenzen, die unbeabsichtigt durch zu viele Aufgaben entstehen, reduzieren möchten, sollten Sie den CLR-Threadpool verwenden. Intelligente Threadeinführungen und Retirement-Algorithmen verbergen sich hier unter einer einfachen Benutzeroberfläche, so dass sich der Zeitaufwand für die Erstellung und das Löschen von Threads während der gesamten Verwendungsdauer des Programms amortisieren. Darüber hinaus ist die Verwendung der ThreadPool-Klasse kinderleicht.

Allerdings fällt auch hierbei ein gewisser Zeitaufwand an. Aufrufe an QueueUserWorkItem verursachen einen sequentiellen Zeitaufwand für den Aufrufer, und die Infrastruktur, mit der die Arbeit von der Warteschlange für ausstehende Arbeitselemente übertragen wird, bedeutet auch ein Overhead für die parallele Ausführung. Bei grobkörnigem Parallelismus ist dieser Zeitaufwand allerdings so niedrig, dass Sie ihn sicherlich nicht einmal wahrnehmen. Bei extrem feinkörnigem Parallelismus könnte dieser Zeitaufwand jedoch einen erheblichen Engpass für die Skalierbarkeit darstellen. Ziehen Sie in Betracht, Ihren eigenen kompakten ThreadPool aus den ohne oder mit wenig Sperren versehenen Low-Lock-Datenstrukturen zu erstellen. Hierdurch wird ein Teil des Zeitaufwands vermieden, der durch einen Allzweck-ThreadPool entsteht, wie beispielsweise die Gewährleistung der Fairness zwischen AppDomains, die Erfassung und Wiederherstellung von Sicherheitsinformationen usw. Für die meisten Verwendungen reicht der ThreadPool-Bestand jedoch vollkommen aus.

Definieren von Grenzen

Eine nicht unwichtige Aktivität stellt das Festlegen der Arbeitsaufteilung dar. Bei CPU-abhängigen Arbeitslasten konzentriert sich die Aufgabe mehr darauf, den mit der gleichzeitigen Ausführung verbundenen Leistungsaufwand zu vermeiden. Die meisten Arbeitslasten sind jedoch von der CPU unabhängig. Sie kombinieren verschiedene Ein- und Ausgabeformen sowie die Synchronisierung zwischen den CPU-Aufgaben, die allerdings beide zu vorhersehbaren Sperrmustern führen können. Daher beschäftigt sich die gleichzeitige Ausführung, wie bei den meisten Codes, eher mit dem Manipulieren von komplexen Koordinationsmustern als mit niedrigeren Leistungsgraden.

Vielleicht besteht die einfachste Methode zur Arbeitsaufteilung in der Verwendung des parallelen Servermodells. Bei Servern wie SQL Server oder ASP.NET wird jede eingehende Anforderung als unabhängige Aufgabe betrachtet und folglich auf ihrem eigenen Thread ausgeführt. Die Hostsoftware schränkt häufig die Anzahl der verwendeten echten Betriebssystemthreads ein, damit nicht übermäßig viele Threads parallel ausgeführt werden. Die meisten Arbeitslasten dieser Art bestehen aus vollkommen unabhängigen Aufgaben, die auf unterschiedliche Datensätze und Ressourcengruppen zugreifen und somit zu äußerst effizienten parallelen Beschleunigungen führen. Bei Clientprogrammen passen jedoch nur wenige Arbeitslasten problemlos in dieses Modell. Das Auffangen von und die Reaktion auf Peer-to-Peer-Kommunikation kann zum Beispiel über dieses Modell erfolgen. Wenn allerdings keine große Anzahl arbeitsintensiver Anforderungen eingeht, ist die Obergrenze für mögliche Beschleunigungen ziemlich eingeschränkt.

Eine Alternative besteht darin, willkürliche Unteraufgaben im Code festzulegen. Hierzu kann eine logischere und subjektivere Definition von „bedeutende Aufgabe“ verwendet werden, die für clientseitige Arbeitslasten förderlicher ist. Komplexe Softwarevorgänge bestehen zum Beispiel normalerweise aus mehreren logischen Schritten, die im Programm als unabhängige Funktionsaufrufe dargestellt werden, die wiederum selbst mehrere Schritte umfassen usw. Möglicherweise möchten Sie alle Funktionsaufrufe als unabhängige Aufgabe darstellen, zumindest diejenigen, die umfangreich genug sind. Dies ist kompliziert, da Sie Abhängigkeiten anfordern müssen, so dass dieser Ansatz wesentlicher komplexer wird. Die meisten modernen imperativen Programme sind voll von unstrukturierten Schleifen, Zugriffen auf Daten über nicht transparente Zeiger, die möglicherweise im Speicher nicht eng nebeneinander liegen, und Funktionsaufrufen, von denen keine explizit dokumentieren, welche Abhängigkeiten vorliegen. Und natürlich gibt es auch verborgene Threadaffinität, der Sie sich möglicherweise nicht bewusst sind. Daher erfordert diese Technik eindeutig ein profundes Verständnis des Problems, das der Code zu beheben versucht, sowie der effizientesten Methode zur parallelen Ausführung, damit möglichst Abhängigkeiten beseitigt werden.

Eine allgemeine ähnliche Methode ist der Abzweigungs-/Zusammenführungsparallelismus. Hierbei zweigt eine Masteraufgabe mehrere untergeordnete Aufgaben ab, die wiederum selbst weitere untergeordnete Aufgaben abzweigen können, und jede Masteraufgabe wird nachfolgend mit den entsprechenden untergeordneten Aufgaben an einer wohldefinierten Stelle wieder zusammengeführt. Stellen Sie sich zum Beispiel ein Parallelismusmodell auf Aufgabenebene vor, das als „Future“ für Abzweigung-/Zusammenführung bezeichnet wird. In diesem Modell wird diese Methode basierend auf den Funktionsaufrufen als Aufgabeneinheit gekapselt. Dies kann durch den neuen Typ „Future <T>“ dargestellt werden (eine Implementierung von „Future <T>“ steht auf der Website für das MSDN ®- Magazin als Download zur Verfügung):

int a() { /* some work */ }
int b() { /* some work */ }
int c()
{
    Future<int> fa = a();
    Future<int> fb = b();
    // do some work
    return fa.Value + fb.Value;
}

Die Bedeutung dieses Codes besteht darin, dass die Aufrufe von a und b mit dem Text von c parallel ausgeführt werden können, die Entscheidung für welche Aufrufe obliegt der Implementierung des Future<int>-Moduls. Wenn c die Ergebnisse dieser Aufrufe benötigt, greift der Text auf die Value-Eigenschaft des Future-Werts zu. Dies hat zur Folge, dass auf den Abschluss der Arbeit gewartet wird, oder, falls die Arbeit noch nicht asynchron ausgeführt wurde, dass die Funktion auf dem aufrufenden Thread lokal ausgeführt wird. Diese Syntax wird der vorhandenen IAsyncResult-Klasse eng zugeordnet, besitzt aber als zusätzlichen Vorteil weitere Intelligenz darüber, wie viel Parallelität in das Programm eingeführt werden soll. Während intelligentere Implementierungen leicht vorstellbar sind, sieht eine einfache Übersetzung dieses Codes ungefähr so aus:

int a() { /* some work */ }
int b() { /* some work */ }
delegate int Del();
int c()
{
    Del da = a; IAsyncResult fa = da.BeginInvoke(null, null);
    Del db = b; IAsyncResult fb = db.BeginInvoke(null, null);
    // do some work
    return da.EndInvoke(fa) + db.EndInvoke(fb);
}

Andere Methoden sind möglich, wie beispielsweise die Verwendung von länger auszuführenden Unteraufgaben anstatt der Anforderung, dass untergeordnete Aufgaben nie länger als übergeordnete Aufgaben ausgeführt werden. Dies setzt häufig komplexere Synchronisierungen und Rendezvousmuster voraus. Die Abzweigung/Zusammenführung ist einfach, da die Einsatzdauer von einzelnen Arbeitern offensichtlich ist.

In der bisherigen Erläuterung wurde Parallelismus von einem codezentrierten Blickwinkel betrachtet. Eine andere Technik ist häufig einfacher: Datenparallelismus. Dieser eignet sich normalerweise für Probleme und Datenstrukturen, die daten- und berechnungsintensiv sind oder deren einzelne Vorgänge häufig auf unterschiedliche Daten zugreifen.

Eine allgemeine Datenparallelismustechnik wird als Partitionierung bezeichnet. Der schleifenbasierte Parallelismus wendet zum Beispiel diese Methode an, um Berechnungen über einen Elementenbereich zu verteilen. Nehmen Sie einmal an, Sie besitzen 16 logische CPUs, einen Array mit 100.000 Elementen und eine Arbeitskomponente, die ohne oder nur mit geringen Abhängigkeiten ausgeführt werden kann und 20 Prozent der Zeit gesperrt ist. Sie könnten den Array in 20 zusammenhängende Teile mit jeweils 5.000 Elementen aufteilen (weiter unten wird erläutert, wie diese Zahlen berechnet wurden), 19 Threads abzweigen, wobei der aktuelle Thread für eine Partition verwendet wird, und jeden Thread so anordnen, dass die Berechnungen parallel erfolgen. Die parallele Abfrageverarbeitung in Datenbanken wie SQL Server wendet eine ähnliche Methode an. Diese Technik wird in Abbildung 2 dargestellt.

Abbildung 2: Partitionsbasierter Parallelismus
Abbildung 2 Partitionsbasierter Parallelismus

In diesem Beispiel wird ein Array mit 100.000 Elementen gezeigt, das über vier Threads verteilt ist. Beachten Sie, dass ein gewisser Teil des sequentiellen Overheads für die Aufteilung anfällt. In einigen Fällen, in denen eine Zusammenführung erforderlich ist, fällt zusätzlicher Zeitaufwand häufig zum Zusammenführen der Ergebnisse an, einschließlich für die Verbindung von nicht verarbeiteten Threads.

Die ForAll-Schleifen sind in der Regel eine herkömmliche Methode zum Ausdrücken des partitionsbasierten Parallelismus in Programmiersprachen. Eine beispielhafte ForAll<T>-API-Implementierung wird in Abbildung 3 dargestellt. Ähnliche Methoden können auch zur Parallelisierung von Schleifen verwendet werden. Zum Beispiel können Sie statt „IList<T>“ ein „int“ aus dem Parametersatz herausnehmen bzw. diesem hinzufügen und die Schleifeniterationsnummer in einen Action<int>-Delegaten einfügen.

Dieser Code geht von einer grundlegenden Annahme aus, die sich als fatal erweisen könnte: Es wird erwartet, dass der übertragene Action<T>-Delegat für eine parallele Ausführung sicher ist. Dies bedeutet, dass eine richtige Synchronisierung zur Beseitigung von Parallelitätsfehlern verwendet werden muss, falls er sich auf den freigegebenen Status bezieht. Andernfalls ist zu erwarten, dass die korrekten Funktionen und die Zuverlässigkeit des Programms ziemlich schlecht sind.

Eine andere Datenparallelismustechnik ist die Erstellung von Pipelines, wobei mehrere Vorgänge parallel ausgeführt werden, so dass mithilfe eines schnellen, freigegebenen Puffers Daten untereinander übertragen werden. Dieser Vorgang ähnelt einem Fließband, da jeder Schritt im Prozess die Chance erhält, mit einigen Daten zu interagieren und diese anschließend an den nächsten Schritt zu übergeben. Diese Technik erfordert einen intelligenten Synchronisierungscode, damit die Zeit minimiert wird, die an eindeutigen Engpässen aufgewendet wird: die Stelle, an der benachbarte Schritte in der Pipeline über einen freigegebenen Puffer miteinander kommunizieren.

Anzahl der Aufgaben

Die Berechnung der Anzahl der zu erstellenden Aufgaben ist nicht einfach. Wenn der Durchsatz die einzige Priorität ist, können Sie ein theoretisches Ziel verwenden, wie beispielsweise die folgende Gleichung, in der BP den Prozentsatz der Zeit darstellt, die die Aufgaben gesperrt sind:

NumThreads = NumCPUs / (1 – BP)

Die Anzahl der Threads soll also dem Verhältnis zwischen der Anzahl der CPUs und dem Prozentsatz der Zeit, in der Aufgaben tatsächlich ausgeführt werden, entsprechen. Dies wurde im ForAll-Beispiel weiter oben dargestellt. Diese Gleichung ist zwar ein guter theoretischer Ausgangspunkt, erzielt aber leider keine genauen Ergebnisse. HT wird zum Beispiel nicht berücksichtigt, bei der Speicher mit hohen Latenzen parallele Berechnungen zulassen, ansonsten jedoch nicht für einen vollen Prozessor berücksichtigt werden sollen. Und sie setzt ein wenig naiv voraus, dass Sie den Wert von BP voraussagen können, der sich aber nicht einfach feststellen lässt, besonders nicht für eine Komponente, die heterogene Aufgaben plant, fast so wie der CLR-Threadpool. Wenn Zweifel bestehen, ist es besser, sich auf den Threadpool zum Zuweisen von Aufgaben an die Betriebssystemthreads zu verlassen und eher Parallelität verstärkt auszudrücken.

Es gibt eine natürliche Beschleunigungskurve für die Algorithmen. Auf dieser Kurve liegen zwei besonders interessante Punkte. Zuerst stellt sich die Frage, wie hoch die Mindestanzahl der Aufgaben ist, die von der Parallelisierung der Berechnung profitiert. Bei kleinen Berechnungen kann es vorkommen, dass bei Verwendung einer niedrigen Anzahl von Aufgaben ein zu hoher Overhead entsteht (Threaderstellung und Cachefehltreffer) und dass bei einer hohen Anzahl die Ausführung der sequentiellen Version entspricht und sie sogar noch übertrifft. Die zweite Frage lässt sich so formulieren: Wie hoch ist bei einer unendlichen Anzahl von Hardwarethreads die maximale Anzahl von Threads, die einem Problem zugewiesen werden können, bevor eine Leistungsverschlechterung anstatt eine fortlaufende Beschleunigung auftritt? Alle Probleme erreichen diesen Punkt abnehmender Rückgaben. Wenn Sie ein Problem noch weiter aufteilen, wird schließlich die feinste Abstufung von einzelnen Anweisungen erreicht.

Eine lineare Beschleunigung würde bedeuten, dass die Zeit, die zur Ausführung eines Problems mit p Prozessoren benötigt wird, 1/p der Zeit beträgt, die zur Ausführung eines Problems mit einem Prozessor benötigt wird. Laut Amdahlschem Gesetz ist die Möglichkeit für die Erzielung solcher Beschleunigungen eingeschränkt. Dieses Gesetz besagt ganz einfach, dass die maximale Beschleunigung durch den Anteil der sequentiellen Ausführung, der nach Einführung des Parallelismus noch übrig bleibt, eingeschränkt wird. Formeller gesehen besagt dieses Gesetz, wenn S der Prozentsatz des Problems ist, das sequentiell ausgeführt werden muss (falls es nicht parallelisiert werden kann), und p die Anzahl der verwendeten CPUs darstellt, kann die ungefähr zu erwartende Beschleunigung wie folgt ausgedrückt werden:

1/(S + ((1 – S)/p))

Mit zunehmender Prozessoranzahl nähert sich dieser Ausdruck 1/S an. Wenn Sie daher nur (angenommen) 85 Prozent des Problems parallelisieren können, können Sie auch nur eine Beschleunigung von 1/0,85 bzw. ungefähr 6,6 erzielen. Jeglicher mit der Synchronisierung und der Einführung der Parallelität zusammenhängende Overhead trägt zu S bei. In der Praxis gibt es dennoch gute Nachrichten: Die Verteilung der Aufgaben auf mehrere Prozessoren weist auch Vorteile auf, die schwer quantifiziert und gemessen werden können. Beispielsweise wird es den parallelen Threads ermöglicht, ihre (separaten) Cachespeicher in einem „heißen“ Zustand zu halten, in dem eine optimale Arbeitsweise gewährleistet ist.

Jeder Algorithmus, der echte Ressourcen verwaltet, muss auch die computerübergreifende Nutzung berücksichtigen. Software, die ausschließlich lokale Entscheidungen zur Maximierung des Parallelismus trifft – besonders in einer Serverumgebung wie ASP.NET – kann (und wird!) ein Chaos sowie einen Konflikt für Ressourcen, einschließlich CPUs, verursachen. Eine ForAll-Schleife kann zum Beispiel die Prozessorauslastung abfragen, bevor die optimale Anzahl der Aufgaben dynamisch festgelegt wird. Anstatt des in Abbildung 3 gezeigten Algorithmus, der von der System.Environment.ProcessorCount-Eigenschaft abhängig ist, können Sie auch die in Abbildung 4 dargestellte GetFreeProcessors-Funktion verwenden.

Dieser Algorithmus ist nicht perfekt. Er ist nur ein statistischer Snapshot des Computerstatus zum Ausführungszeitpunkt und besagt nichts über die Vorgänge nach der Ergebnisausgabe. Er könnte extrem optimistisch oder pessimistisch sein. Und natürlich berücksichtigt er nicht die Tatsache, dass einer der abgefragten Prozessoren die GetFreeProcessors-Funktion selbst ausführt, was eine nützliche Verbesserung ergeben würde. Eine andere interessante statistische Kennzahl ist der Leistungszähler „System\Processor Queue Length“, mit dem Sie feststellen können, wie viele Threads sich in der Planungswarteschlange befinden und darauf warten, dass ein Prozessor freigegeben wird. Eine große Anzahl deutet daraufhin, dass alle neu eingeführten Aufgaben einfach auf die Entleerung der Warteschlange warten müssen, vorausgesetzt, alle Threads verfügen über die gleiche Priorität.

Es gibt einige interessante Gründe dafür, eher zu viel als zu wenig Parallelität zu erstellen. Wenn Sie heterogene Aufgaben verwenden möchten, kann das Modell, bei dem jede Aufgabe bis zum Abschluss auf einem Thread ausgeführt wird, zu Fairnessproblemen führen. Die Ausführung von Aufgabe A dauert wesentlich länger als die von Aufgabe B, was dazu führen kann, dass Aufgabe B de facto ausgeschlossen wird, wenn nicht zusätzliche Ressourcen freigegeben werden. Dies ist besonders schlimm, wenn Aufgabe A die Ausführung anderer Aufgaben blockiert und der Algorithmus dies nicht berücksichtigt.

Ein weiterer Grund zur beabsichtigten Überparallelisierung besteht in der asynchronen Ein-/Ausgabe. Windows bietet E/A-Komplettierungsports für überlegene Skalierbarkeit, sodass ausstehende E/A-Anforderungen nicht unbedingt einen Betriebssystemthread verwenden müssen. Die Ein-/Ausgabe beginnt asynchron, und sobald sie abgeschlossen ist, sendet Windows ein Fertigstellungspaket an den zugrunde liegenden Port. Normalerweise ist ein Threadpool von ausreichender Größe an den Port gebunden und wird vom Threadpool auf dem CLR verwaltet. Er wartet auf die Verarbeitung der Fertigstellungspakete, sobald diese verfügbar sind. Bei einer geringen Fertigstellungsrate kann die möglichst schnelle parallele Erstellung einer großen Anzahl von E/A-Anforderungen zu einer besseren Skalierbarkeit führen, als wenn jede Aufgabe hinter der anderen wartet, bis sie an der Reihe ist, die asynchrone Ein-/Ausgabe zu initiieren. Dies gilt für Dateien, Netzwerke und Ein-/Ausgaben mit zugewiesenem Speicher, obwohl Sie sich ständig der Tatsache bewusst sein sollten, dass eine feste Anzahl von gemeinsam verwendeten Ressourcen auf dem Computer vorhanden ist. Wenn zu heftig um sie geworben wird, nimmt die Skalierbarkeit ab und nicht zu.

Freigegebener Status

Bei jeder Einführung von Parallelität müssen Sie sich Gedanken über den Schutz des freigegebenen Status machen. Dies ist von entscheidender Bedeutung. Sie sollten den Artikel von Vance Morrison in der MSDN ®- Magazin-Ausgabe vom August 2005 lesen (msdn.microsoft.com/msdnmag/issues/05/08/Concurrency), in dem die Bedeutung der Sperren erläutert wird (möglicherweise in englischer Sprache). Die ordnungsgemäße Ausführung sollte immer Priorität vor der Leistung haben, und falls Sie Parallelität verwenden, ohne Sperren zu berücksichtigen, ist Ihr Code möglicherweise nicht korrekt. Hier soll nicht wiederholt werden, was Vance bereits sehr gut erklärt hat, sondern eher die Leistung solcher Techniken betrachtet werden.

Als Techniken für die Synchronisierung werden am häufigsten Sperr- und Low-Lock-Vorgänge verwendet. Sperrtechniken verwenden Primitive, wie z. B. Win32® Mutex, CRITICAL_SECTION, CLR-Monitor, ReaderWriterLock oder zugeordnete Sprachschlüsselwörter (zum Beispiel „lock“ in C# und „SyncLock“ in Visual Basic®) dazu, einen gewissen Grad an wechselseitigem Ausschluss zu erzielen. Um diesen Ausschluss zu erreichen, wird eine API aufgerufen. Ein interner Algorithmus sorgt dafür, dass zwei Codeabschnitte, die die gleiche Sperre verwenden, nicht in den geschützten Codebereich gelangen können. So lange wie sich alle Benutzer nach dem Protokoll richten, ist der Code sicher.

Low-Lock-Vorgänge können mithilfe von Interlock-Primitiven erstellt werden, die per Hardwareunterstützung für atomare Lade-Vergleich-Speicheranweisungen implementiert werden. Sie gewährleisten, dass eine einzelne Speicheraktualisierung atomar ist und zur Entwicklung eines hochgradig skalierbaren Codes verwendet werden kann, der wiederum optimistische Parallelität nutzt. Das Schreiben eines solchen Codes erweist sich als schwieriger, er verursacht jedoch keine Sperren. (Falls Sie sich fragen sollten, wie Sperren geschrieben werden: Sperren werden mithilfe solcher Primitiver geschrieben.)

Diese Aufrufe sind allerdings mit Zeitaufwand verbunden. Abbildung 5 zeigt für Ausführungen ohne Konflikte eine Micro-Benchmark, in der der Zeitaufwand von CPU-Zyklen für unterschiedliche Sperrentypen erläutert wird.

Abbildung 5: Kostenvergleich der verschiedenen Sperren
Abbildung 5 Kostenvergleich der verschiedenen Sperren

Solche Messungen sind interessant für das Verständnis der Auswirkungen der Leistung von Sperren (besonders wenn dynamische Entscheidungen zur parallelen Ausführung getroffen werden und in diesen Fällen eine größere Codemenge zur Verfügung stehen muss, als dann tatsächlich parallel ausgeführt wird). Wenn Sie sicherstellen, dass die Synchronisierung mit der richtigen Abstufung erfolgt, kann ein Zeitaufwand wie dieser nicht die Ausführung des Codes dominieren. Es gibt noch einen weiteren Zeitaufwand, der noch nicht erwähnt wurde, wie zum Beispiel die Interaktion zwischen den Interlock-Vorgängen und der Speicherhierarchie. Solche Interaktionen sind jedoch aufgrund des Speicherplatzes leider nicht möglich. Nichtsdestotrotz gilt die Auswirkung auf die Skalierbarkeit als der interessantere Teil. Leider müssen Sie häufig hinsichtlich der Skalierbarkeit und der sequentiellen geradlinigen Ausführungsleistung Kompromisse schließen. Diese Kompromisse sollten durch Messungen bestätigt werden.

Es gibt keine Garantie, dass ein Thread ausgeführt werden kann, solange eine Sperre aktiviert ist. Wenn sein Quantum abgelaufen ist, kann daher ein nachfolgender Thread ausgeführt werden und versuchen, dieselbe Sperre abzurufen. Darüber hinaus kann ein ausführbarer Thread mit einer höheren Priorität einen unter einer Sperre ausgeführten Thread verdrängen. Dies kann ein Phänomen hervorrufen, das als Prioritätsinversion bezeichnet wird, sowie zu Sperrkonvois führen, wenn die Eingangsrate bei einer umstrittenen Sperre außergewöhnlich hoch ist. Die meisten Sperren reagieren auf umstrittene Erfassungsversuche mit „Lightweight-Spinning“ auf Systemen mit mehreren CPUs, da davon ausgegangen wird, dass der Thread, der die Sperre aktiviert hat, sie bald freigibt. Wenn dies fehlschlägt, weil entweder der Besitzer die Sperre länger als erwartet aufrechterhält oder weil sie möglicherweise aufgrund eines Kontextwechsels ausgelagert wurde, wird sie blockiert. Für ein hochgradig paralleles System gilt: Je mehr Sperren vorhanden sind, desto mehr Threads sind zur Auslastung der CPUs erforderlich und desto geringer ist die Wahrscheinlichkeit, dass Ihr System problemlos skaliert werden kann.

Daher sollten Sie eine wichtige Frage im Hinterkopf behalten: Wie erziele ich während der Aktivierung einer Sperre den geringsten Arbeitsaufwand, um die erforderliche Anzahl von Sperren zu reduzieren? Leser-Schreiber-Sperren tragen hierzu bei, indem bei gleichzeitiger Gewährleistung des wechselseitigen Ausschlusses für Schreibvorgänge mehrere Threads Daten lesen können. Bei den meisten Systemen ist das Verhältnis der Leser zu den Schreibern sehr hoch, und daher kann der Gewinn für die Skalierbarkeit erheblich sein. Der Artikel „Concurrent Affairs“ (möglicherweise in englischer Sprache) von Jeffrey Richter in der MSDN-Magazin-Ausgabe von Juni 2006 eignet sich hervorragend als Lektüre für weitere Informationen (siehe msdn.microsoft.com/msdnmag/issues/06/06/ConcurrentAffairs).

Wenn Sie allerdings von vornherein einen freigegebenen Status vermeiden können, ist es erst gar nicht erforderlich, den Zugriff zu synchronisieren. Eine allgemeine Methode zur Erhöhung der Skalierbarkeit der Algorithmen, die kritische Datenstrukturen ändern – Daten, auf die die meisten Threads zugreifen müssen – besteht darin, Sperren ganz zu vermeiden. Diese Methode kommt in drei verschiedenen Formen vor, in aufsteigender Reihenfolge des Schwierigkeitsgrads für die Implementierung: Immutabilität, Isolierung und Sperrfreiraum.

Immutabilität bedeutet, dass eine einmal erstellte Instanz sich nicht ändert bzw. sich zumindest während eines festgelegten und bekannten Zeitraums nicht ändert. Eine CLR-Zeichenfolge ist beispielsweise nicht mutabel und erfordert daher auch keine Sperre für den Zugriff auf die einzelnen Zeichen. Wenn sich der Status nicht in Bewegung befindet, ist keine Sperre erforderlich. Dies lässt sich jedoch nur schwer erzielen, wenn mehrere Orte mit Statuszeigern vorhanden sind, die atomar überwacht werden sollen.

Die Isolierung beseitigt jeglichen gleichzeitigen Zugriff auf Daten, indem separate Kopien beibehalten werden. Viele threadsichere C-Implementierungen von Malloc und Freigabevorgängen verwalten zum Beispiel einen Pool des verfügbaren Speichers pro Thread, sodass zuordnende Threads nicht um den Pool kämpfen (bei dem es sich in einem C-Programm wahrscheinlich um einen Hotspot handelt). Ebenso erhöht der Garbage Collector (GC) des CLR-Servers mithilfe eines Zuordnungskontexts pro Thread und eines Speichersegments pro CPU den Durchsatz von Speicherzuordnungen. Dieses Verfahren setzt normalerweise ein regelmäßiges Rendezvous mit einer zentralen Kopie von Datenstrukturen voraus und kann manchmal Zeitaufwand erfordern, der mit Kopieren und der Gewährleistung zusammenhängt, dass interessante Datenbits nicht veralten.

Der Sperrfreiraum ist eine komplizierte Methode, die hier nur kurz umrissen werden soll. Wenn Sie das Speichermodell des Zielcomputers wirklich verstanden haben und bereit sind, noch wesentlich mehr Codes zu schreiben und zu verwalten, können Sie intelligente Datenstrukturen erstellen, die beim parallelen Zugriff problemlos skaliert werden. Meistens kann der resultierende Code nur sehr schwer auf korrekte Funktion getestet und verwaltet werden, so dass sich der Aufwand nicht lohnt. Bei diesen Techniken lohnt es sich, die gemessenen Bereiche des Programms auf Skalierungs- oder Leistungsprobleme zu untersuchen, die aufgrund der Verwendung von Sperren verursacht werden können.

Tools zur Profilerstellung von Parallelismus

Wie also können Sie die Skalierbarkeit des Codes messen und verbessern? In diesem gesamten Artikel wurden die Techniken, Ansätze und der Zeitaufwand eher kritisch betrachtet. Leider gibt es keine Zauberformel, die für alle Parallelitätsprobleme gilt. Ebenso gibt es auch keine einfache Antwort auf die Frage, wie Probleme profiliert und/oder bessere Ansätze identifiziert werden können, mit denen eine parallele Beschleunigung erzielt werden kann. Es ist durchaus möglich, dass Sie all die hier aufgeführten Verfahren und Ausgaben ausführen (sowie einige, die nicht behandelt wurden, wie zum Beispiel Debugging), und dennoch keine Veränderungen feststellen, so als hätten Sie weiterhin einen sequentiellen Algorithmus verwendet. Es gibt so genannte peinliche Parallelitätsprobleme, für die rezeptbuchähnliche Algorithmen geschrieben und online sowie in Lehrbüchern veröffentlicht wurden. Leider sind die meisten Programme in der Praxis nicht so einfach.

Im Folgenden finden Sie einige Tipps zur Profilerstellung des parallelen Algorithmus. Es wird immer der neue Visual Studio® 2005-Profiler verwendet. Dieser Profiler ist in die normale Visual Studio-Benuteroberfläche integriert (unter dem Menüelement „Tools | Performance Tools | New Performance Session“) und verfügt im Unterverzeichnis „\Team Tools\PerformanceTools\ Visual Studio“ auch über die Befehlszeilenversion „VSPerfCmd.exe“. (Weitere Verwendungsdetails zu diesem Tool finden Sie unter msdn2.microsoft.com/ms182403.aspx, möglicherweise in englischer Sprache.) Dieser Profiler dient zur Erstellung von VSP-Dateien, die mit dem Befehl „VSPerfReport.exe“ übertragen werden, um eine CSV- oder XML-Datei zur weiteren Analyse zu erstellen. Im Folgenden werden einige Punkte erläutert, auf die Sie achten sollten.

Stellen Sie sicher, dass die CPUs ausgelastet sind. Wenn die Prozessoren nur geringfügig ausgelastet sind, tritt sehr wahrscheinlich einer der beiden Fälle auf. Entweder verwenden Sie zu wenige Prozessoren für die Auslastung des Problems oder Threads werden beim Warten gesichert, höchstwahrscheinlich aufgrund der übermäßigen Synchronisierung an den kritischen Stellen im Code. Der Task-Manager ist in der Regel völlig ausreichend für diese Aufgabe, obwohl auch der Leistungszähler „Processor\% Processor Time“ (über PerfMon.exe) angewendet werden kann.

Vergewissern Sie sich, dass das Programm nicht zu häufig fehlschlägt. Besonders bei datenintensiven Anwendungen müssen Sie darauf achten, dass der physische Speicher nicht regelmäßig überläuft. In diesem Fall kann ein System voll mit Threads die Festplatte kontinuierlich auslasten, während Daten ständig seitenweise eingelagert und ausgelagert werden müssen. (Erinnern Sie sich anhand des vorherigen Diagramms daran, wie zeitaufwändig der Festplattenzugriff ist?) Der Task-Manager kann diese Daten, die als Spalte ausgewählt werden müssen, genauso wie „PerfMon.exe“ übermitteln. „VSPerfCmd“ kann über ETW-Ereignisse diese Daten auch mit dem folgenden Befehl ausgeben:

VSPerfCmd.exe /events:on,Pagefault /start:SAMPLE /output:<reportFile name> /launch:<exeFile name>

Verwenden Sie anschließend den folgenden Befehl, wenn das Programm abgeschlossen ist:

VSPerfCmd.exe /shutdown

Sie können auch verschiedene Einstellungen für das Abtastintervall ausprobieren.

Stellen Sie fest, wofür das Programm die meiste CPU-Zeit aufwendet.  Dies ist besonders wichtig, wenn diese CPU-Zeit während der Aktivierung von Sperren auftritt. Möglicherweise kann auch der zusätzliche Code, der zur Erstellung von Threads und zur Durchführung von Synchronisierungen sowie für alle weiteren mit diesen beiden Aufgaben verbundenen Vorgänge erforderlich ist, die meiste Ausführungszeit in Anspruch nehmen.

Untersuchen Sie die Leistungszähler „System\Context Switches/sec“ und „System\Processor Queue Length“.  Mit diesen Zählern können Sie leichter feststellen, ob zu viele Threads vorhanden sind, die zu viel Zeit bei Kontextwechseln und Threadmigrationen vergeuden. Wenn dies der Fall ist, versuchen Sie den Algorithmus zu optimieren, der die Anzahl der zu verwendenden Aufgaben festlegt.

Suchen Sie nach einem Speicherhierarchie- und Cacheproblem.  Falls sich die Probleme mit keiner der vorgeschlagenen Abhilfemaßnahmen beseitigen lassen und eigentlich eine höhere Beschleunigung auftreten sollte, liegt möglicherweise ein Speicherhierarchie- und Cacheproblem vor. Wenn viel Zeit für Cachefehltreffer und Außerkraftsetzungen aufgewendet wird, kann die Beschleunigung des Programms erheblich eingeschränkt werden. Mithilfe der Partitionierung von Daten in mehrere Cachezeilen und der Verwendung von einigen der oben genannten Ansätze, wie z. B. Isolierung, kann dieses Problem möglicherweise behoben werden. Jede CPU verfügt über Leistungszähler, die im Visual Studio-Profiler abgefragt werden können und zum Beispiel zurückgezogene Anweisungen und Cachefehltreffer behandeln. Eine niedrige Anzahl zurückgezogener Anweisungen weist daraufhin, dass mehr Zeit für Vorgänge mit hoher Latenz aufgewendet wird, wie beispielsweise Cachefehltreffer. Cachespezifische Zähler dienen zur Feststellung, wo und wie häufig Fehltreffer auftreten.

Während die genauen Zähler prozessorspezifisch sind, verfügt die Visual Studio-Benutzeroberfläche über eine einfache Menüoption für deren Verwendung (siehe Abbildung 6). Sie können diese Zähler auch mit dem folgenden Befehl abfragen:

VSPerfCmd.exe /QueryCounters

Abbildung 6: Profiler-Eigenschaften
Abbildung 6 Profiler-Eigenschaften

Schlussbemerkung

Die Skalierbarkeit mithilfe von Parallelismus war historisch gesehen bisher auf Serverumgebungen und High-End-Workstations begrenzt. Da jedoch neue Hardware verstärkt Parallelismus auf Threadebene einsetzt, nämlich Architekturen mit mehreren Kernen, muss gängige Clientsoftware schließlich die verfügbaren Ressourcen bewältigen und effizient nutzen. Dies bringt auch einige einzigartige Herausforderungen mit sich. Der Parallelismus ist ganz offensichtlich kein Ersatz für einen hochgradig wirksamen sequentiellen Code, sondern vielmehr eine Technik für die noch schnellere Ausführung eines bereits optimierten sequentiellen Algorithmus.

Dieser Artikel hat eine schnelle Übersicht auf hoher Ebene geliefert. Sie sind vermutlich erst einmal abgeschreckt und halten dieses Thema für viel zu schwierig, und damit hätten Sie nicht einmal Unrecht. Diese Techniken erleichtern Ihnen jedoch die Erstellung eines Codes, der problemlos bei neueren Prozessoren mit mehreren Kernen skaliert werden kann, da diese im Laufe der Zeit immer häufiger eingesetzt werden. Da Infrastrukturen wie der CLR-Threadpool und Tools wie Visual Studio weiterentwickelt werden, um diese Programmierungsmethode besser zu unterstützen, lassen sich viele der Schwierigkeiten besser bewältigen.

Senden Sie Fragen und Kommentare in englischer Sprache an clrinout@microsoft.com.

Der Autor

Joe Duffy ist Mitarbeiter des CLR-Teams von Microsoft. Er beschäftigt sich mit der Entwicklung von Parallelitätsabstraktionen, Programmierungsmodellen und der Infrastruktur für die Plattform. Er hat kürzlich ein Buch veröffentlicht, .NET Framework 2.0 (Wrox/Wiley, 2006), und schreibt bereits ein neues Buch mit dem Titel Concurrent Programming on Windows (Addison-Wesley). Er veröffentlich auch häufig Artikel in diesem Blog: www.bluebytesoftware.com/blog.

Ausgabe von September 2006 des MSDN-Magazins.

Anzeigen: