Performance Engineering

Die Kosten eines neuen Supercomputers der höchsten Leistungsklasse, wie etwa des gerade installierten Systems am FZ Jülich [5], betragen immerhin etwa 150 Millionen Euro über eine Nutzungszeit von 7 Jahren.  Die allgemeine ökonomische Bedeutung effizienterer Computerprogramme ist dabei nur ein Aspekt. Für den Wissenschaftler werden durch schnellere Programme zugewiesene Rechenzeit-Kontingente automatisch wertvoller. Durch eine verbesserte Nutzung des Kontingents kann mehr wissenschaftliche Wertschöpfung pro CPU-Stunde – und damit Euro – erzeugt werden. Darüber hinaus muss der Wissenschaftler unter Umständen von vorneherein ein geringeres Kontingent beantragen, was direkt anderen Projekten zugutekommt.

Wie soll man nun die Laufzeit optimieren? Experten auf dem Gebiet sind aber leider rar und sitzen zumeist in größeren Rechenzentren, also nicht gerade dort, wo intensive Entwicklung wissenschaftlicher Software stattfindet. Im besten Fall holen sich die Entwickler aus den Anwendungswissenschaften dort Hilfe. Entwickler, das sind zum überwiegenden Teil Doktoranden in den Lehrstühlen. Die Dissertation ist nach wenigen Jahren abgeschlossen, und das mühsam erarbeitete Know-How verschwindet, wenn nicht in die Wirtschaft dann doch zumindest an eine andere Einrichtung. Dies unterstreicht die tragende Rolle der akademischen Rechenzentren, die prinzipiell in der Lage sind, Wissen über effiziente Rechnernutzung langfristig zu sichern und immer wieder neu weiterzugeben: durch Kurse, durch Dokumentation, und auch durch direkte Zusammenarbeit. Dieses Wissen gipfelt in Strategien zum Performance Engineering, das wir hier genauer beleuchten wollen.

Zielmetriken und Optimierung

Wenn man etwas optimiert, also verbessert, dann muss zunächst eine Metrik definiert werden, mit der sich diese Verbesserung messen lässt. Die Spannbreite ist dabei sehr groß, und die passende Metrik hängt auch von der Zielsetzung ab. Am Anfang sollte die Wahl eines geeigneten Algorithmus stehen, der das gegebene Problem mit möglichst wenig Aufwand löst, also eine möglichst geringe Komplexität aufweist. Bei der Implementierung geht es darum, diesen Algorithmus effizient auf die Hardware abzubilden. Am einfachsten und glücklicherweise auch am verbreitetsten ist es, wenn die gleiche Problemstellung zwar mit unterschiedlichen Parametern aber ansonsten immer auf dieselbe Weise mehrfach gelöst werden muss. Eine Maschine wird hierbei optimal genutzt, wenn sie höchste Leistung bringt, also in einer gegebenen Zeit möglichst viel Arbeit erledigt wird. Die Metrik dafür ist die Leistung oder Performance, definiert durch das Verhältnis von Arbeit und Zeit:

Was Zeit bedeutet, ist klar: Es ist das, was man an der Uhr ablesen kann, also Sekunden oder Taktzyklen. Bei der Arbeit wird es schon komplizierter, denn es gibt viele verschiedene Konzepte von Arbeit: Ein Rechner-Architekt wird geneigt sein, eine Maschinen-Instruktion als die Basiseinheit der Arbeit zu definieren. Das funktioniert natürlich nur innerhalb einer begrenzten, binärkompatiblen Menge von Architekturen. Entwickler wissenschaftlicher Software hingegen haben eine andere Sicht auf die Arbeit, sie nutzen eher Flops (Gleitkomma-Operationen), Iterationen, Gitterpunkt-Updates oder auch einfach „einen Programmlauf“, eben alles, was im Kontext der Fragestellung des Programmes Sinn ergibt.

Komplexere Fragestellungen ergeben sich bei hoch parallelen Programmen, die zumindest prinzipiell in der Lage sind, auf Höchstleistungsrechnern zu laufen. Dort ist neben der reinen Rechengeschwindigkeit auch Skalierbarkeit gefragt: Wird der Ressourcen-Einsatz, also die Anzahl der Rechenknoten verdoppelt, sollte das Programm auch doppelt so viel Arbeit in gleicher Zeit erledigen. Die Zielmetrik ist also die Beschleunigung bei Vervielfachung der Ressourcen. Schließlich spielt die Frage des Energieverbrauchs eine immer wichtigere Rolle. Nicht so sehr, weil man die Stromrechnung drücken oder die Umwelt schonen möchte – die Möglichkeiten, die der Anwender hier zur Einflussnahme besitzt, sind eher überschaubar. Beim Energieverbrauch ist ein betrieblicher Gesichtspunkt viel wichtiger. Moderne Parallelrechner haben eine stark fluktuierende Leistungsaufnahme, die sehr von der Art der laufenden Programme abhängt. Die Verlustleistung eines modernen Server-Prozessors kann je nach Code um einen Faktor zwei schwanken, wenn man alle Register wie teilweise Belegung von Kernen und die Justierung der Taktfrequenz ausreizt. Die Stromversorgung des Gesamtsystems muss auf den „heißesten“ Fall ausgelegt sein, der freilich in der Praxis (fast) nie auftaucht. Wenn man die elektrische Leistungsaufnahme des Systems künstlich deckeln kann, können Investitionen in die Infrastruktur eingespart werden. Dies kann durch technische Maßnahmen geschehen wie die automatische Reduktion der Taktfrequenz, aber auch der Code und die Ausführungsmodalitäten sind nicht zu unterschätzen. Eine optimierte Implementierung kann „kälter“ laufen, weil sie bei geringerer Taktfrequenz das Gleiche aus der Hardware holt, und trägt so dazu bei, den Leistungsdeckel einzuhalten. Sinnvolle Zielmetriken für solche Szenarien sind also Leistungsaufnahme und Energieverbrauch.

Performance-Modelle

Es gibt also viele Gründe, sich um die Optimierung der Code-Performance zu kümmern. Selbst wenn man davon ausgeht, dass der beste Algorithmus zum Einsatz kommt, ist die Arbeit damit noch lange nicht vorbei, denn die Interaktion der implementierten Software mit der Hardware ist entscheidend. Zu dieser Frage gibt es genügend Literatur, aber die Herangehensweise ähnelt oft mehr „Versuch und Irrtum“ als strukturiertem Vorgehen. So unangenehm es für die von Abstraktion getriebenen Informatiker sein mag: Eine Voraussetzung für das Schreiben effizienter Software ist es, die Abstraktionsebenen, die moderne Programmiermodelle und Sprachen dem Entwickler bieten, zumindest zum Teil aufzubrechen. Welchen Code generiert der Compiler? Welche Recheneinheiten gibt es und wie nutzt sie das Programm? Wo sind die Engpässe in der Hardware? Wie werden Threads auf die Kerne gebunden? Was passiert mit einer Nachricht, die zwischen Prozessen übermittelt wird? Ohne dieses Basiswissen ist eine Beurteilung der Performance nicht möglich. Andererseits sind bereits Multicore-Prozessoren und erst recht große Parallelrechner extrem komplizierte Gebilde, und es ist für Anwendungsentwickler selbstverständlich unmöglich, alle Details zu überblicken.

Auf der Suche nach einem strukturierten Prozess der Performance- oder Ressourcen-Optimierung stößt man schnell auf einige notwendige Komponenten: Wissen über die Hardware, die Hotspots der Implementierung (d.h. die Stellen, an denen die meiste Laufzeit verbraucht wird), mögliche Overheads des verwendeten Programmiermodells und der Parallelisierung und vor allem ein Modell der Wechselwirkung zwischen Hardware und Software. Ein einfaches und dennoch leistungsfähiges Konzept auf der Ebene des Prozessors ist das Roofline-Modell. Der Prozessor wird dabei reduziert auf die beiden prinzipiellen Ressourcen, die die Hardware bereitstellt: die Ausführung von Code, d.h. Instruktionen, und die Übertragung von Daten. Darf man annehmen, dass ein gegebenes Stück Code in immer gleicher Weise mit unterschiedlichen Daten sehr oft nacheinander ausgeführt wird (wie es bei schleifenbasierten Programmen im wissenschaftlichen Rechnen meist der Fall ist), dann ist eine Untergrenze für die Ausführungszeit gegeben durch:

Dabei ist Tcode die Zeit für die reine Ausführung der Instruktionen ohne Berücksichtigung von Datentransfers, und Tdata ist die Zeit für die Datenübertragung, z.B. vom Hauptspeicher in die CPU. Das Modell nimmt an, das diese beiden Zeitbeiträge sich perfekt überlappen. Um Tcode bzw. Tdata bestimmen zu können, müssen weitere Annahmen gemacht werden, beispielsweise über die konkrete Ausführung von Maschineninstruktionen und über Datenvolumina. Vereinfacht man abermals, so ist Code mit Gleitkomma-Operationen gleichzusetzen und Daten mit den zur Ausführung besagter Operationen benötigten Bytes aus dem Hauptspeicher. Dann wird obige Formel zu:

Hier ist W die Anzahl auszuführender Flops, V das Datenvolumen zum und vom Hauptspeicher, b dessen Bandbreite und Ppeak die Spitzenrechenleistung der CPU in Flops/Sekunde. Um von der Zeit zur Performance zu kommen, teilt man die Arbeit durch die minimale Zeit und kommt auf:

Dies ist die konventionelle Form des „naiven“ Roofline-Modells [1], in der als Eigenschaften der Hardware lediglich Ppeak bzw. b eingehen. Der Code wird auf eine Zahl I, die arithmetische Intensität, reduziert. Sie gibt das Verhältnis der Anzahl ausgeführter Operationen zur über den Speicherbus transferierten Datenmenge an. Trotz dieser groben Vereinfachungen ist das Roofline-Modell (ggf. mit einigen Verfeinerungen, siehe Abbildung 1) überaus nützlich, denn wenn die tatsächliche (gemessene) Performance stark vom vorhergesagten Maximum abweicht, deutet dies auf eine Ineffizienz hin, die es ggf. zu beheben gilt. Wenn die Vorhersage stimmt, gewinnt man wertvolle Einsichten über die Engpässe bei der Ausführung.

Abbildung 1: Visualisierung des Roofline-Modells. Die Grafik zeigt ein verbessertes Roofline-Diagramm mit verschiedenen Dächern, die sich auf unterschiedliche mögliche Engpässe beziehen. Bandbreiten von Speicherinterfaces und Caches sind durch schräge Dächer, Rechenleistung unter verschiedenen Randbedingungen (wie fehlende SIMD-Unterstützung) als horizontale Dächer eingezeichnet. Der Code wird allein durch die arithmetische Intensität I parametrisiert.

Roofline und Verwandte sind sogenannte analytische oder „White-box“-Performance-Modelle. Sie basieren auf bekannten Eigenschaften der Hardware (Ausführungszeit von Befehlen, Bandbreiten, Latenzen) und stark vereinfachten Annahmen über ihre Wechselwirkung mit der Software, und sie gelten nur unter ganz bestimmten Annahmen. Dieses Vorgehen ähnelt dem in der Physik, wo man störende Einflüsse zunächst ignoriert, um das Modell handhabbar zu machen, und sie dann später als Korrekturen wieder einführt. Das Ganze ist allerdings sehr aufwendig und kann nur schlecht automatisiert werden. So simpel das Roofline-Modell scheint, ist es doch nicht trivial, für einen einfachen Algorithmus wie einen Stencil-Glätter alles richtig zu machen, geschweige denn für ein echtes Anwendungsprogramm. Auch wird die Modellbildung bei hochparallelen Programmen deutlich schwieriger, weil mehr Einflussfaktoren zusammenkommen, wie z.B. Variationen in der Kommunikationslatenz oder -bandbreite. Dort helfen „Black box“-Modelle, die man in der Naturwissenschaft wohl als phänomenologisch bezeichnen würde. Aus gemessenen Eigenschaften eines Systems werden Voraussagen abgeleitet, deren Vorhersagekraft nicht schlechter sein muss als bei analytischen Ansätzen. Beispielsweise kann man die Beschleunigung eines hochparallelen Programmes über die Anzahl verwendeter Prozessoren messen und aufgrund dieser Messungen verschiedene phänomenologische Skalierungsmodelle erstellen [2]. Das am besten passende Modell kann dann verwendet werden, um nicht skalierbare Komponenten zu identifizieren, wenn beispielsweise ein Term auftaucht, der unerwartet langsam mit der Zahl der Prozessoren skaliert.

Performance Engineering

Schließlich können die beschriebenen, modellbasierten Analyseverfahren in einen strukturierten Prozess eingebunden werden, das Performance Engineering (PE). Dabei geht es darum, aus den mittels Werkzeugen und analytischer Methoden gewonnenen Informationen ein Bild vom Performance-Verhalten einer Anwendung zu zeichnen, das detailliert genug ist, um informierte Entscheidungen über mögliche Optimierungen zu fällen. Man muss hier einem weit verbreiteten Missverständnis entgegenwirken: PE ist mehr als die Anwendung eines oder mehrerer Softwarewerkzeuge, die mehr oder weniger vollständige Informationen über ein Programm liefern. Es ähnelt vielmehr dem wissenschaftlichen Prozess, in dem Vorhersagen oder Erklärungsversuche mittels nachvollziehbarer Experimente bestätigt oder falsifiziert werden. Das oben beschriebene Roofline-Modell bildet ein gutes Beispiel: Sogar wenn es eine gute Vorhersage der Performance einer Schleife liefert, ist das im Allgemeinen noch kein Beweis, dass alle Modellannahmen und Parameter korrekt waren. Durch eine direkte Messung des Datenverkehrs zum Hauptspeicher mittels geeigneter Werkzeuge kann zumindest diese Modellkomponente leicht verifiziert und das Modell damit auf wesentlich festere Füße gestellt werden.

Im Performance Engineering steht nicht immer ein Modell am Anfang; die Analyse beginnt oft mit der Suche nach Hotspots. Ist ein solcher gefunden und handelt es sich dabei nicht um ein Standardproblem, können durchaus zunächst Werkzeuge zum Einsatz kommen, die mittels Hardware Performance Countern die Wechselwirkung des Codes mit der Hardware zu studieren erlauben. Dabei werden bereits wichtige Erkenntnisse gewonnen: Nutzt der Code bestimmte Engpässe zu 100% aus? Welche Rolle spielt der Compiler? Werden SIMD-Befehle genutzt? Ist die Last ausreichend balanciert? Spielt Overhead durch Kommunikation eine wichtige Rolle? Durch solcher Art Messungen vorbereitet, kann der folgende Blick in den Code bereits entscheidende Hinweise auf ein Performance-Modell oder zumindest wichtige Einflussfaktoren liefern. Wie auch immer man beginnt, irgendwo auf dem Weg wird eine Hypothese über die wichtigsten dieser Einflussgrößen entwickelt. Solche Hypothesen sind Verhaltensmuster oder Patterns [3]. Ein häufiges Pattern ist z.B. die Limitierung der Performance durch die Speicherbandbreite, andere sind unbalancierte Arbeitslast, ungleichmäßige Verteilung des Datenverkehrs über ccNUMA-Domänen, übermäßiger Overhead durch Synchronisation, etc. Das Pattern kann durch weitere Messungen und/oder die Erstellung und Validierung eines Performance-Modells bestätigt werden und liefert dann eine klare Aussage über Optimierungspotenziale. Nach einer Änderung im Code, die den identifizierten Engpass abmildert oder eliminiert, beginnt der Prozess von vorne (siehe Abbildung 2).

Performance Engineering ist also keine Programm, das nach einem vorgegebenen Algorithmus abläuft, sondern ein Prozess, der von wissenschaftlichem Denken geprägt ist und damit hinterfragbar, dokumentierbar und nachhaltig gestaltet werden kann.

Abbildung 2: Ein möglicher Prozess für das Performance Engineering (vereinfacht). Ein Pattern ist eine Hypothese über leistungslimitierende Faktoren, das im besten Falle zu einem Performance-Modell führt. Das Pattern und das Modell können mittels Messungen validiert oder widerlegt werden. Der Prozess ist zyklisch angelegt, denn nach der Validierung ist entweder eine neue Hypothese oder ein Neustart der Analyse erforderlich.

Ausblick

Es ist noch viel Arbeit zu leisten, bis die Idee eines strukturierten Prozesses für das Performance Engineering bei allen Entwicklern und Entwicklerinnen im wissenschaftlichen Rechnen angekommen sein wird. Auch die Methoden, Modelle und Werkzeuge, die dabei zum Einsatz kommen, sind noch lange nicht perfekt. Vielleicht ist das kurz vor dem Ende von Moore’s Law [6] und der damit einhergehenden Diversifizierung der Hard- und Software auch gar nicht möglich. Machbar ist allerdings eine ressourcenbasierte und vor allem wissenschaftlich fundierte Sicht auf das Thema Code-Performance, die sich dort durchsetzen muss, wo solches Know-How langfristig gesichert werden kann: an akademischen Rechenzentren, die einen engen Kontakt zu den Anwendungswissenschaften pflegen. Auch die Deutsche Forschungsgemeinschaft hat das erkannt und im Jahr 2016 eine Ausschreibung zum Thema „Performance Engineering für wissenschaftliche Software“ herausgegeben. Seit 2017 werden sechs Projekte gefördert, die sich mit Blaupausen für die Bereitstellung entsprechender Dienste beschäftigen [4].

Referenzen

1. S. Williams, A. Waterman, D. Patterson: Roofline: An Insightful Visual Performance Model for Multicore Architectures. Commun. ACM. 52 (4): 65-76 (2009). DOI:10.1145/1498765.1498785
2. F. Wolf et al. (2014) Catwalk: A Quick Development Path for Performance Models. In: Lopes L. et al. (eds) Euro-Par 2014: Parallel Processing Workshops. Euro-Par 2014. Lecture Notes in Computer Science, vol 8806. Springer, Cham. DOI:10.1007/978-3-319-14313-2_50
3. J. Treibig, G. Hager, and G. Wellein: Performance patterns and hardware metrics on modern multicore processors: Best practices for performance engineering. Proc. 5th Workshop on Productivity and Performance (PROPER 2012) at Euro-Par 2012, August 28, 2012, Rhodes Island, Greece. Euro-Par 2012: Parallel Processing Workshops, Lecture Notes in Computer Science 7640, 451-460 (2013), Springer, ISBN 978-3-642-36948- DOI: 10.1007/978-3-642-36949-0_50
4. gauss-allianz.de/de/project/call/Performance%20Engineering%20fu%CC%88r%20wissenschaftliche%20Software
5. www.fz-juelich.de/SharedDocs/Pressemitteilungen/UK/DE/2018/2018-09-18-juwels-einweihung.html
6. G. E. Moore: Cramming more components onto integrated circuits. Electronics 38 (8), 114-117 (1965)

Autoren & Copyright

Georg Hager
HPC Services
Regionales RechenZentrumErlangen (RRZE)
Friedrich-Alexander-Universität Erlangen-Nürnberg
Martensstraße 1, 91058 Erlangen
E-Mail

Gerhard Wellein
Department Informatik
Friedrich-Alexander-Universität Erlangen-Nürnberg
Martensstraße 3, 91058 Erlagen
E-Mail

© Springer-Verlag Berlin Heidelberg 2018