Über unsMediaKontaktImpressum
Dr. Michael Klemm & Dr. Dirk Schmidl 27. Juni 2017

Parallele Performance: So geht's

Parallele Programmierung eröffnet eine Vielfalt an Möglichkeiten für Performance-Optimierungen. © sakkmesterke / Fotolia.com
© sakkmesterke / Fotolia.com

Man erwartet sich von parallelen Programmen zumeist eine Steigerung der Leistungsfähigkeit. Das Programm soll entweder in kürzerer Zeit ein Ergebnis berechnen oder mehr Eingabedaten in der gleichen Zeit bearbeiten. Leider ist es häufig so, dass ein paralleles Programm nicht sofort die gewünschte Leistung bringt. Man ist versucht zu denken, ein Programm, ausgeführt auf n Rechenkernen, würde auch sofort die n-fache Leistung bringen. Häufig ist jedoch festzustellen, dass dem nicht so ist. Sofort stellt sich die Frage, wo denn das Problem liegen könnte und eine Verbesserung soll herbeigeführt werden.

Dieser Artikel beleuchtet einige der Aspekte der Analyse von (paralleler) Performance und diskutiert typische Stolpersteine, welche es den Programmierern von paralleler Software nicht ganz leicht machen, das Optimum an Leistung aus einer Applikation herauszukitzeln. Da gibt es zum Einen fundamentale Limits, die durch die Hardware definiert werden. Zum Anderen entstehen durch die Parallelisierung neue Probleme wie Lastungleichgewichte oder paralleler Overhead, die eine effektive Parallelisierung schwieriger machen. In diesem Artikel wollen wir den Blick für diese Probleme schärfen. Wir verzichten bewusst auf die Diskussion von Quellcode und zeigen die auftretenden Probleme in ihrer Allgemeinheit. Zu unterschiedlich sind die Lösungsansätze, die zur Behebung nötig sind, als dass sie an konkreten Beispielen behandelt werden könnten.

Der Prozess der Softwareoptimierung

Softwareoptimierung ist ähnlich zur Fehlersuche ein strukturierter Prozess, der iterativ durchlaufen eine Hilfestellung bei der Suche nach einem Performanceproblem und dessen Behebung bereitstellt. Einfaches "Trial-and-Error" wird selten zu einer zufriedenstellenden Lösung führen bzw. bindet wertvolle Entwicklerressourcen bei der Problemsuche. Daher ist es unerlässlich, durch methodisches Vorgehen das Problem zunächst einzugrenzen und anschließend eine geeignete Gegenmaßnahme im Quellcode zu implementieren.

Wichtig beim Analyseprozess ist die Unterstützung durch ein geeignetes Werkzeug, das die Leistung der Applikationen misst und für die Analyse anschaulich aufbereitet, sowie die Suche nach Performanceproblemen durch geeignete Filtermechanismen und Zusammenführung von Quellcode und Messung unterstützt. Es existieren zahlreiche unterschiedliche Werkzeuge mit unterschiedlichen Schwerpunkten und Analysefähigkeiten. Aus Platzgründen verzichten wir auf eine Beschreibung dieser Werkzeuge an dieser Stelle.

Abb.1: Angedachter Prozess zur Analyse und Optimierung. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.1: Angedachter Prozess zur Analyse und Optimierung. © Dr. Michael Klemm & Dr. Dirk Schmidl

Abb.1 zeigt den angedachten Prozess zur Analyse und Optimierung. Ausgehend von einem Benchmark (1), der den gewünschten und zu untersuchenden Teilbereich in der Applikation anspricht, führt man zunächst eine Messung durch (2). Diese ermittelt diejenigen Kennzahlen, die im Werkzeug genutzt werden können, das Problem einzugrenzen (3) und durch Änderungen am Quellcode behoben werden können (4). In Schritt (5) überprüft die Optimierende, ob das Problem behoben wurde oder ob weitere Maßnahmen nötig sind. Gegebenenfalls wird eine weitere Iteration durchgeführt, um etwaige weitere Maßnahmen zu beschließen oder aber die eben gemachte Änderung eventuell wieder rückgängig zu machen. Eine weitere Überprüfung (6) findet statt, um zu ermitteln, inwiefern die optimierte Applikation die gestellten Leistungsanforderungen erfüllt oder weitere Optimierungen durchgeführt werden sollen.

Ein besonderes Augenmerk sollte auf den Benchmark selbst geworfen werden. Neben der erwähnten Eigenschaft, den richtigen Codeteil in der Applikation anzusprechen, sollte der Benchmark weitere Merkmale aufweisen. Zunächst muss der Benchmark leicht zu starten und zu wiederholen sein, denn man wird den iterativen Prozess mehrere Male durchlaufen müssen. Je komplexer der Start der Applikation und des Benchmarks ist, umso mühsamer wird die Analyse. Weiterhin ist es wünschenswert, dass der Benchmark möglichst kurz läuft, damit die Zeit zwischen Messung, Analyse und eventuellen Codeänderungen möglichst kurz ausfällt. Und zu guter Letzt sollte der Benchmark auch gleich eine Art von Ergebnisüberprüfung enthalten, so dass bereits während der Optimierungsarbeit festgestellt werden kann, ob ein Fehler gemacht wurde und das Programm zwar schneller, aber leider auch falsch rechnet.

Diese Analysen und Optimierungen bilden die Grundlage für die weitere Arbeit zur Identifikation und Behebung von Performanceproblemen. Bevor wir aber einige Beispiele für ebendiese Probleme beschreiben, möchten wir auf die erwähnten fundamentalen Einschränkungen seitens der Hardware eingehen.

Das "Roofline"-Modell

Um zu überprüfen, ob ein Programm die verwendete Hardware effizient ausnutzt, ist es wichtig, sich über die Möglichkeiten und Grenzen der eingesetzten Hardware bewusst zu sein. Eine häufig verwendete Metrik ist hierbei die Anzahl an (Fließkomma-)Operationen die ein Rechner theoretisch leisten kann. Ohne Beschränkung der Allgemeinheit beschränken wir uns hier auf Fließkomma-Operationen. Ähnliche Betrachtungen können für jede Art von Berechnung durchgeführt werden.

Ein Serverknoten des Rechenclusters der RWTH Aachen ist beispielsweise in der Lage, 691 GFLOPS (Milliarden Fließkomma-Operationen pro Sekunde) zu liefern. Eine Voraussetzung hierfür ist aber, dass die benötigten Daten für die Berechnungen schnell genug zu den Recheneinheiten der CPU transportiert werden. Dies setzt voraus, dass Daten in schnellem Zwischenspeicher (sogenannten Caches) gehalten und mehrfach verwendet werden können, da der Bus zum Hauptspeicher typischerweise deutlich langsamer ist als die Recheneinheiten. Der erwähnte Serverknoten ist beispielsweise in der Lage, 120 GB an Daten pro Sekunde über den Speicherbus zu transportieren. Bei einer Rechenoperation pro geladener Zahl reicht das nur aus, um 15 GFLOPS zu erreichen anstelle der theoretisch möglichen 691 GFLOPS.

Nimmt man diese beiden Limits als Basis für die Abwägung, welche Leistung man für seine Anwendung erwarten kann, so ist es entscheidend zu wissen, wie das Verhältnis zwischen Rechenoperationen und geladenen Daten in der Anwendung ist. Dieses Verhältnis wird auch als "Operational Intensity" bezeichnet und gibt an, wie viele FLOPS eine Anwendung für jedes aus dem Hauptspeicher geladene Byte ausführt. Basierend auf diesen Daten erlaubt einem das sogenannte Roofline-Modell eine Abschätzung der zu erreichenden Leistung einer Anwendung.

IT-Tage 2017 - Softwareentwicklung
Abb.2: Roofline-Modell für einen Rechenknoten aus dem RWTH-Rechencluster. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.2: Roofline-Modell für einen Rechenknoten aus dem RWTH-Rechencluster. © Dr. Michael Klemm & Dr. Dirk Schmidl

Im Roofline-Modell werden die Limits einer Maschine in einem Diagramm in Abhängigkeit zur Operational Intensity dargestellt, wie für unseren Beispielserver in Abb.2 dargestellt. Die horizontale Linie gibt die maximale Rechenleistung an, also 691 GFLOPS, und die linke ansteigende Gerade gibt die erreichbare Leistung für eine niedrige Operational Intensity an, die mit 120 GB/s an Speicherbandbreite erreicht werden kann. Verwendet man einen Algorithmus mit einer Operational Intensity von 0.25, also einer Rechenoperation für 4 geladene Bytes, dann kann man ablesen, dass die Maschine eine Leistung von 30 GFLOPS erreichen kann, wie an der linken roten Linie zu sehen. Verwendet der Algorithmus hingegen 16 FLOPS für jedes geladene Byte, dann kann man die Höchstleistung von 691 GFLOPS erreichen. Das Roofline-Modell erlaubt einem so eine realistische Einschätzung über die Limits der Maschine für den eigenen Algorithmus.

Hat der eigene Algorithmus eine Operational Intensity von 0.25 und man erreicht die 30 GFLOPS in der Berechnung, ist man am Limit der Maschine und weitere Optimierungen des Algorithmus sind nicht sinnvoll, auch wenn man nur 30 GFLOPS von einer Maschine erhält, die knapp 700 leisten kann. Der Grund ist der Datentransfer über den Speicherbus. Erreicht man aber nur 5 GFLOPS, kann der Algorithmus unter Umständen optimiert werden, um eine bessere Leistung zu erreichen. Schafft man es hingegen, den Algorithmus so zu verändern, dass mehr Berechnungen pro geladenem Byte durchgeführt werden, etwa durch Cache-Blocking, dann verschiebt man die Operational Intensity im Diagramm nach rechts und kann eine höhere Leistung erreichen.

Das Gesetz von Amdahl

Abb.3: Aufteilung in parallele und serielle Anteile für unterschiedliche Threadanzahl. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.3: Aufteilung in parallele und serielle Anteile für unterschiedliche Threadanzahl. © Dr. Michael Klemm & Dr. Dirk Schmidl

Parallelisiert man eine Anwendung, um auf mehreren Rechenkernen oder auch mehreren Servern gleichzeitig laufen zu können, so erwartet man eine Verringerung der Laufzeit. Häufig kann die Gesamtaufgabe in einzelne Pakete zerlegt werden, beispielsweise in vier Pakete, die dann parallel abgearbeitet werden. Läuft alles optimal, so kann hierdurch die Laufzeit auf ein Viertel reduziert werden.

In der Praxis gestaltet es sich häufig als schwierig, die gesamte Arbeit zu verteilen. Einzelne Teile der Ausführung, wie z. B. Ein- und Ausgabe, müssen häufig sequenziell abgearbeitet werden. Hierdurch bleibt ein Anteil der Ausführungszeit seriell. Abb.3a zeigt eine Programmausführung mit einem seriellen Anteil von ca. 10 Prozent. Auch wenn dieser Anteil sehr klein ist, gewinnt er mit zunehmender Anzahl an Rechenkernen an Bedeutung. Während der serielle Anteil auf 4 Kernen noch akzeptabel scheint, wie in Abb.3b dargestellt, dominiert er die Ausführung für den Fall von 24 Rechenkernen deutlich, s. Abb.3c.

Das Gesetz von Amdahl gibt eine obere Schranke für den zu erwartenden Gewinn bei optimierter Ausführung einer Anwendung an. Das Gesetz besagt, dass der Speedup, also der Faktor um den das Programm schneller wird, bei einer beliebigen Anzahl an Rechenkernen durch den Kehrwert von s beschränkt ist, wobei s der serielle Anteil der Anwendung ist [1]. Für das Beispiel aus Abb.3, mit s=10 Prozent, können wir also mehr als einen Speedup von 10 erreichen, da wir die Laufzeit des seriellen Anteils nicht durch mehr Threads verringern können.

Als Anwendungsentwickler sollte man sich daher bewusst sein, welchen Speedup man erreichen kann und wie groß der serielle Anteil der Anwendung ist. Unter Umständen ist es auch möglich, den seriellen Anteil zu verringern, indem man weitere Teile seines Codes parallelisiert. Eine weitere Möglichkeit besteht natürlich auch darin, den sequentiellen Anteil durch Optimierungen möglichst schnell zu machen. Manche Leistungsanalyse-Werkzeuge bieten einem daher die Möglichkeit, sich die erreichte Parallelität einer Anwendung anzeigen zu lassen und serielle Code-Regionen zu identifizieren.

Lastungleichgewichte machen das Leben schwer

Abb.4: Optimale Lastverteilung vs. Lastungleichgewicht. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.4: Optimale Lastverteilung vs. Lastungleichgewicht. © Dr. Michael Klemm & Dr. Dirk Schmidl

Dem Gesetz von Amdahl liegt die Annahme zugrunde, dass der parallele Teil der Anwendung perfekt skaliert. Auch diese Annahme ist in der Praxis häufig nicht erfüllbar. Ein Grund für eine nicht optimale parallele Ausführung ist häufig ein Lastungleichgewicht. Ein Lastungleichgewicht liegt dann vor, wenn nicht alle Kerne die gleiche Zeit für die ihnen zugewiesene parallele Arbeit benötigen.

Abb.4 illustriert die parallele Ausführung einer parallelen Programmregion links mit perfekter Lastverteilung und rechts mit einem Lastungleichgewicht. In diesem Beispiel braucht der erste Kern deutlich länger für die Ausführung seiner Arbeit, hierdurch kommt es zu Wartezeiten auf den übrigen Kernen, bevor die parallele Programmregion verlassen werden kann.

Auch wenn das Problem in der Illustration einfach aussieht, gestaltet es sich häufig als sehr schwierig, eine gute Lastverteilung in der eigenen Anwendung zu erreichen. Generell kann ein Lastungleichgewicht zwei Gründe haben:

  1. Unterschiedlich große Arbeitspakete für einzelne Kerne.
    Häufig werden die Arbeitspakete gleichmäßig aufgeteilt, etwa indem alle Schleifeniterationen auf die Rechenkerne verteilt werden. Wenn aber nicht in allen Schleifeniterationen dasselbe passiert, kann die Ausführung unterschiedlich viele Prozessorinstruktionen benötigen und hierdurch ein Lastungleichgewicht entstehen.
  2. Kerne arbeiten mit unterschiedlicher Geschwindigkeit.
    Selbst wenn alle Kerne dieselbe Anzahl an Instruktionen ausführen, kann es zu einem Lastungleichgewicht kommen. Durch externe Faktoren wie beispielsweise Betriebssystem-Prozesse oder durch geteilte Ressourcen wie Caches oder Speicherbusse kann es bei einigen Kernen zu Verzögerungen kommen, so dass diese länger brauchen, ihre Instruktionen abzuarbeiten.

Um zu erkennen, ob in der eigenen Anwendung ein Lastungleichgewicht vorliegt, bieten Leistungsanalyse-Werkzeuge häufig die Möglichkeit, sich die Ausführungszeiten einzelner Threads/Prozesse anzeigen zu lassen. Das Verhältnis zwischen dem langsamsten Kern und der durchschnittlichen Laufzeit auf allen Kernen liefert einem einen Indikator dafür, wie viel Zeit man wegen Lastungleichgewichten verliert. Um zu unterscheiden, ob verschiedene Kerne unterschiedlich viele Instruktionen ausführen oder ob das Lastungleichgewicht an einer unterschiedlichen Geschwindigkeit der Kerne liegt, bieten einige Werkzeuge dem Nutzer die Möglichkeit, über sogenannte Hardware-Performance-Counter die Anzahl der ausgeführten Instruktionen zu messen.

Allgemein ist es günstig für eine gute Lastverteilung, die Arbeit dynamisch zur Laufzeit in möglichst kleinen Paketen zu verteilen, etwa durch dynamisches Schleifenscheduling oder durch taskbasierte Ansätze. Ein Nachteil hierbei kann im Overhead dieser Mechanismen liegen, den wir im Folgenden behandeln wollen.

Overhead durch Threading und Tasking

Während Lastungleichgewichte meist dann auftreten, wenn die genutzten Algorithmen das parallele Problem nicht gleichmäßig auf die verfügbaren Threads verteilen, gibt es eine weitere Klasse von Performanceproblemen, die durch das Threading selbst entstehen. Es ist sicherlich klar, dass das Erzeugen eines Threads nicht kostenlos erfolgt, sondern das Betriebssystem einen gewissen Aufwand betreiben muss, um einen Thread zum Leben zu erwecken. Die Details, was das Betriebssystem tun muss, um einen Thread zu erzeugen, gehen sicher über diesen Artikel hinaus. Wichtig ist nur, dass dieser Overhead sichtbar werden kann, wenn sehr viele Threads erzeugt werden.

In modernen Implementierungen von Thread-Modellen werden Threads typischerweise jedoch nicht mehr erzeugt und terminiert, sondern in Thread-Pools auf Vorrat gehalten. Was sich auf dem ersten Blick als eine gute Idee erweist und sicherlich auch ist, verschiebt nur das Problem. Auch hier treten Kosten auf, einen Thread aus dem Pool aufzuwecken und ihm die durchzuführende Berechnung zu übergeben. Ebenso entstehen wiederum Kosten, wenn der Thread nach getaner Arbeit in den Pool zurückgegeben wird.

Warum ist das wichtig? Obwohl der Overhead durch geschickte Optimierung des Thread-Managements möglichst gering gehalten werden kann, wird er dennoch sichtbar, wenn bei sehr vielen Threads die Menge an Arbeit pro Thread sehr klein wird (beispielsweise um Lastungleichgewichte zu vermeiden). Weiterhin erfordern viele Algorithmen, dass die Threads nicht völlig unabhängig arbeiten, sondern sich regelmäßig synchronisieren. Insbesondere können Barrieren, die nur überschritten werden dürfen, wenn alle Threads dieselbe Barriere erreicht haben, sehr teuer in der Ausführung werden.

Abb.5: Implementierung einer Barriere als Baumstruktur. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.5: Implementierung einer Barriere als Baumstruktur. © Dr. Michael Klemm & Dr. Dirk Schmidl

Abb.5 zeigt eine typische Implementierung einer solchen Barriere, wie sie entweder am Ende einer parallelen Region oder zur erwähnten Synchronisation genutzt wird. Die Abbildung zeigt eine Baumstruktur, bei der Threads immer paarweise eingesammelt werden ("Join") und rekursiv Gruppen von Gruppen gebildet werden, bis alle Threads synchronisiert wurden. Mit steigender Threadanzahl wird die Tiefe des Baumes größer und es dauert länger, bis alle Threads synchronisiert wurden.

Ähnliche Argumente können angebracht werden, wenn es um die Verwendung von taskbasierten Programmiermodellen geht. Ebenso wie die Verwaltung von Threads ist das Management von Tasks ebenfalls mit Kosten verbunden. Diese sind im Vergleich zu Threading typischerweise deutlich geringer, aber wiederum bei Tasks mit sehr kurzer Laufzeit durchaus spürbar. Das Einfügen eines Tasks in eine Warteschlange zur späteren Ausführung kostet ebenso, wie das Herausnehmen eines Tasks, um ihn mittels eines Threads auszuführen.

Das einzige probate Mittel gegen diese Effekte ist, stets genügend Arbeit pro Thread oder pro Task einzuplanen und damit den relativen Overhead klein zu halten. Leider ist das leichter gesagt, als getan. Auch im Sinne von Amdahls Gesetz heißt das in der Realität, dass Parallelität auf unterster (Schleifen-)Ebene nicht zum gewünschten Ergebnis führt. Es muss vielmehr auf bereits sehr hoher algorithmischer Ebene mit der Parallelisierung begonnen werden. Nur so lassen sich genügend viele und ausreichend große Arbeitspakete für sehr viele Threads bzw. Tasks schnüren.

Ausgesperrt

Abb.6: Einfache Hashtabelle mit verketteter Liste zur Konfliktbehandlung. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.6: Einfache Hashtabelle mit verketteter Liste zur Konfliktbehandlung. © Dr. Michael Klemm & Dr. Dirk Schmidl

Eine weitere Quelle von Verdruss auf Seiten des parallelen Programmierers sind Konflikte, die auftreten, wenn auf gemeinsam genutzte Ressourcen von mehreren Threads aus gleichzeitig lesend und schreibend zugegriffen werden sollen. Typische Beispiele sind Dateizugriffe, Speicherallokationen oder gemeinsam benutzte Datenstrukturen. In solchen Fällen wird häufig der konkurrierende Zugriff durch Sperrobjekte (engl. locks) vermieden. Leider geht damit ein Stück weit die Parallelität verloren: es ist ja genau der Zweck des Sperrobjektes, einen Teil des Codes nur von einem oder wenigen Threads ausführen zu lassen, um die Datenstruktur zu schützen.

Abb.6 zeigt exemplarisch die zugegeben einfache Implementierung einer Hashtabelle. Ausgehend von einem Array (senkrecht auf der linken Seite) verzweigt eine verkettete Liste zur Konfliktbehandlung. Möchte man nun die Hashtabelle gegen Zugriffskonflikten schützen, so bieten sich zunächst drei Varianten an, welche in Abb.6 als rote Rechtecke markiert sind. Variante eins sperrt schlicht die gesamte Hashtabelle. Man kann sich denken, dass dies die schlechteste Variante ist. Bei guten Hashfunktionen sollten Zugriffskonflikte auf den selben Bereich der Tabelle sehr selten vorkommen. Das macht sich Variante zwei zu Nutze: statt die gesamte Tabelle zu sperren, wird nur der Teil mittels Sperrobjekt gesichert, der auch wirklich von einem Thread zugegriffen wird. Somit sollte die Chance auf eine gegenseitige Behinderung mit einem anderen Thread minimiert werden. Variante drei geht schließlich noch einen Schritt weiter und verlagert die Nutzung des Sperrobjektes in die verkettete Liste hinein. Damit betrifft eine Sperre nur noch dann zwei Threads, wenn sie gerade im gleichen Bereich der Hashtabelle an der gleichen Stelle zugreifen wollen.

Welche Variante ist jetzt die richtige? Wie so oft lässt sich diese Frage nicht so eindeutig beantworten. Für die Varianten zwei und drei spricht sicher, dass sie sehr wahrscheinlich mehr Parallelität erlauben, als Variante eins. Jedoch ist der Implementierungsaufwand für diese beiden Varianten deutlich höher, als bei Variante eins. Auch darf man nicht vergessen, dass die Benutzung eines Sperrobjektes stets einen Overhead verursacht, auch wenn nicht auf die Freigabe der Sperre gewartet werden muss. Somit kommt es auf die Benutzung der Datenstruktur an, welche Variante zum Einsatz kommen sollte.

Anzumerken ist noch, dass die sogenannten "lock-freien Datenstrukturen" nur bedingt eine Lösung darstellen. Während der Name suggeriert, dass diese Datenstrukturen völlig ohne Sperrobjekte auskommen, so verschieben sie in der Tat das Problem nur auf eine andere Ebene. Statt Sperrobjekte im üblichen Sinn zu benutzen, wenden sie atomare Instruktionen des Prozessors an, um die jeweiligen internen Daten entsprechend so zu verändern, dass konkurrierende Zugriffe keine zerstörerische Wirkung entfalten und die Datenstruktur stets konsistent bleibt. Wie Sperren auch, können die genutzten atomaren Operationen störend auf die Parallelität einwirken, da auch sie faktisch eine Serialisierung der Ausführung bewirken (sollen).

NUMA-Effekte verstehen

Abb.7: Verteilung von Threads, Daten und Arbeit auf NUMA-Architekturen. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.7: Verteilung von Threads, Daten und Arbeit auf NUMA-Architekturen. © Dr. Michael Klemm & Dr. Dirk Schmidl

Begibt man sich von der algorithmischen Ebene wieder auf die Hardware-Ebene, so erkennt man, dass ein Großteil der verwendeten Serversysteme und auch besonders leistungsstarke Desktopsysteme ihre Rechenleistung häufig aus zwei oder mehr Prozessoren beziehen. Hierdurch ergibt sich für den Programmierer solcher Systeme eine neue Herausforderung in Bezug auf die Speichernutzung. Wie in Abb.7a dargestellt, haben fast alle Prozessoren inzwischen eine direkte Anbindung an Hauptspeicher. Über einen Bus sind aber alle Prozessoren miteinander so verbunden, dass jeder Prozessor jeden Speicher lesen und schreiben kann. In dem gegebenen Beispiel erfolgt der Zugriff von Prozessor 1 auf Speicher 1 aber direkt, wohingegen der Zugriff auf Speicher 2 indirekt über den Bus passiert. Die Zugriffszeiten unterscheiden sich hierbei und können negative Auswirkungen auf die Laufzeit einer Anwendung haben. Solche Systeme nennt man wegen dieses Speicherzugriffsverhaltens Systeme mit nicht-uniformem Speicherzugriff (Non-Uniform Memory Access – NUMA [2]).

Auf einem solchen NUMA-System ist es wichtig. drei Punkte bei der Programmierung und Ausführung eines Programms zu berücksichtigen.

  1. Die Verteilung der Threads auf dem System. 

    Im Normalfall übernimmt das Betriebssystem die Aufgabe, Prozesse und Threads auf die verfügbaren Rechenkerne zu verteilen. Der Vorteil des Betriebssystems ist, dass es einen Überblick über alle laufenden Programme hat und dies in die Verteilung der verfügbaren Ressourcen mit einbeziehen kann. In Anwendungen, die auf Leistung optimiert werden sollen, kann dies aber negative Auswirkungen haben. Insbesondere auf NUMA-Systemen kann es vorkommen, dass Threads/Prozesse auf Sockel migriert werden, die eine große Entfernung zu den Daten haben. Hierdurch werden Speicherzugriffe unnötig teuer. Hat man eine Maschine ausschließlich für die eigene Anwendung zur Verfügung, ist es ratsam, eine feste Verteilung der Threads vorzugeben und dies nicht dem Betriebssystem zu überlassen. Möglichkeiten hierzu stellen üblicherweise Betriebssysteme zur Verfügung, häufig gibt es um dies zu bewerkstelligen, auch einfache Optionen in den zur Parallelisierung verwendeten Programmierparadigmen. In Abb.7b wurden die Threads T1 und T2 so verteilt, dass je ein Thread auf einem der Sockel läuft.

  2. Die Verteilung der Daten in den verschiedenen Speicherbereichen.

    Die Verteilung der Daten wird auch vom Betriebssystem gesteuert. Alle gängigen Betriebssysteme verwenden hierzu die sogenannte First-Touch-Strategie. Hierbei legt das Betriebssystem die Daten in den Speicherbereich, der den kürzesten Abstand zum Thread und dessen Rechenkern hat, der die Daten das erste Mal im Speicher im Schreibzugriff benutzt. Um die in Abb.7c dargestellte Verteilung des Feldes A zu erreichen, muss man also dafür sorgen, dass Thread T1 die ersten 50 und T2 die zweiten 50 Elemente des Feldes initialisiert. In der Praxis funktioniert die Verteilung allerdings nicht elementweise sondern pro Speicherseite.

  3. Die Verteilung der Arbeit zwischen den Threads.

    Als letzten Punkt muss der Programmierer noch erreichen, dass die Daten auch von den Threads verwendet werden, die auf den nahe gelegenen Kernen laufen. Der einfachste Fall ist hierbei, wenn die Daten in einer parallelen Schleife bearbeitet werden. Wie in Abb.7d dargestellt, müssen dann nur die Schleifeniterationen in gleicher Art und Weise aufgeteilt werden, wie in der Initialisierung des Feldes. Verwendet man hingegen einen taskbasierten Ansatz, hat man häufig keine Kontrolle über die Verteilung der Tasks auf Threads. In diesem Fall ist man auf die Implementierung des Laufzeitsystems angewiesen und muss hoffen, dass dieses alles richtig macht.

NUMA-Effekte sind schwer zu analysieren, da sie von der Verteilung der Daten auf dem System abhängen und man sie im Allgemeinen nicht im Berechnungskern der Anwendung im Source-Code erkennen kann. Um solchen Effekten auf die Spur zu kommen, erlauben viele Analysewerkzeuge den Zugriff auf prozessorspezifische Hardware-Performance-Counter. Über diese Counter kann man die Anzahl an lokalen und entfernten Speicherzugriffen messen, um zu ermitteln, wie häufig Daten von einem anderen Sockel und dessen Speicher geladen werden. Ist das Verhältnis schlecht, muss man die Stelle im Code finden, an der die Daten initialisiert werden, um eine bessere Verteilung zu erreichen. Eine weitere Möglichkeit der Optimierung ist es, die Speicherseiten nachträglich zu migrieren, sofern das Betriebssystem hierzu Mechanismen zur Verfügung stellt.

"False Sharing" vermeiden

Abb.8: Zwei Rechenkerne im Prozessor mit je einem lokalen Cache pro Kern. © Dr. Michael Klemm & Dr. Dirk Schmidl
Abb.8: Zwei Rechenkerne im Prozessor mit je einem lokalen Cache pro Kern. © Dr. Michael Klemm & Dr. Dirk Schmidl

Auch Caches können – ähnlich wie NUMA – interessante Effekte auf die Leistung einer Applikation haben. Einer der üblichen Tricks zur Leistungssteigerung ist sicher das bekannte "Cache-Blocking", bei dem versucht wird, über bessere Ausnutzung des Caches eine bessere Leistung zu erreichen. Weniger bekannt ist das sogenannte "False Sharing", das vornehmlich bei der parallelen Programmierung auftritt.

Abb.8 zeigt die zwei Rechenkerne mit je einem lokalen Cache. Das entspricht abgesehen von der Anzahl der Rechenkerne im Wesentlichen der Architektur moderner Prozessoren aller namhaften Hersteller. Auf die Abbildung des meist vorhandenen L3-Cache haben wir in diesem Bild verzichtet, da er für unsere Betrachtung nicht besonders wichtig ist. Der Speicherzugriff findet bei solchen Architekturen über sogenannte Cachezeilen statt, d. h. es werden nicht einzelne Bytes aus dem Speicher geholt, sondern immer ganze Bündel von beispielsweise 64 Bytes.

Nehmen wir an, dass auf jedem Kern je ein Thread arbeitet, der den hellblauen bzw. rot hinterlegten Speicherbereich immer wieder liest und schreibt. Liegen diese beiden Bereiche innerhalb der gleichen Cachezeile, so wird Kern 1 zunächst diese Cachezeile in seinen lokalen Cache holen. Will nun Thread 2 auf Kern 2 seine Daten anfassen, so muss Kern 2 bei Kern 1 nachfragen und die Daten aus dessen Cache holen. Je nach Prozessorarchitektur findet diese Kommunikation und der Austausch über den L3-Cache oder über den Hauptspeicher statt (z. B. bei NUMA-Systemen). Dieser Austausch kann bei heutigen Systemen leicht hunderte von Nanosekunden dauern. Zu beachten ist, dass der Kommunikationsoverhead zwar real ist, dass es aber keine "echte" Kommunikation zwischen beiden Threads gibt, da auf unterschiedliche Elemente der Cachezeile zugegriffen wird; deshalb nennt man diesen Effekt "False Sharing".

Besonders kritisch wird die Sache dann, wenn beide Kerne kontinuierlich dieselben Cachezeilen anfragen und ebendiese Cachezeilen zwischen allen beteiligten Kernen immer wieder hin und her wandern. Dann steigt die Latenz des Speicherzugriffs aufgrund des Austausches der Cachezeile extrem an und wird in der Applikation sichtbar. Die Folge ist dann eine messbare Verlangsamung der Applikation. Die Lösung des Ganzen ist typischerweise, ein "Padding" einzuführen, so dass Threads auf unterschiedlichen Rechenkernen nicht auf dieselbe Cachezeile zugreifen und die genutzten Daten nicht nur logisch sondern auch physisch disjunkt ausgerichtet sind.

Fazit

Parallele Programmierung eröffnet eine Vielfalt an Möglichkeiten für Performance-Optimierungen. Parallele Programme stoßen häufig an Systemgrenzen, die man im sequentiellen Fall entweder überhaupt nicht oder nur marginal zu spüren bekommen hat. Meist äußern sich diese Probleme in mangelnder Skalierbarkeit der Applikation mit wachsender Anzahl Threads. Dann ist es an der Zeit, einen kühlen Kopf zu bewahren, den Prozess zur Performanceanalyse zu durchlaufen und das Problem einzugrenzen. In vielen Fällen wird man auf eines der genannten Probleme stoßen und kann dann mit der Behebung beginnen. Wichtig ist stets, im Blick zu haben, was ein erreichbares Ziel ist. Fordern Sie nicht mehr, als Ihnen die Hardware zur Verfügung stellen kann. In diesem Sinne: Glückauf!

nach Oben
Autoren

Dr. Michael Klemm

Dr.-Ing. Michael Klemm arbeitet im Bereich Compilerbau, Design paralleler Programmiersprachen, effiziente parallele Programmierung sowie Performance- Analyse und Performance-Optimierung. Er ist bei der Intel Software and Services...
>> Weiterlesen

Dr. Dirk Schmidl

Dr. Dirk Schmidl arbeitet am IT Center der RWTH Aachen in der Gruppe für Hochleistungsrechnen. Dirk Schmidl promovierte in 2016 an der RWTH mit Fokus auf der Optimierung von OpenMP-Programmen auf großen Shared-Memory- Systemen.
>> Weiterlesen
botMessage_toctoc_comments_929