Ressourcen bestmöglich nutzen

Um die Ressourcen von Multicore-Architekturen effizient auszuschöpfen, ist es eventuell erforderlich, das Programm zu parallelisieren. Dafür stehen mindestens die zwei folgenden Möglichkeiten zur Verfügung:

• Video: Ein Algorithmus kann in einzelne, von der Bildschirmposition abhängige Teilbereiche zerlegt werden.
• Netzwerkverarbeitung: Parallelisiert wird, indem unterschiedliche Funktionen auf unterschiedlichen Prozessoren abgearbeitet werden. 

Der erste Schritt bei der Überarbeitung des Programms zur bestmöglichen Nutzung der Multicore-Ressourcen besteht darin, die serielle Implementierung zu optimieren. Denn die Verbesserung der seriellen Performance erfolgt typischerweise einfacher und ohne großen Zeitaufwand und die Gefahr, dass sich Fehler einschleichen ist gering. Die serielle Optimierung kann bewirken, dass man mit weniger Parallelisierung auskommt und sich ganz auf das parallele Verhalten konzentrieren kann und nicht auf eine Mischung serieller und paralleler Probleme.

Freescale

Allerdings ist die serielle Optimierung nicht das Endziel. Es sollen nur Änderungen durchgeführt werden, die die Parallelisierung erleichtern und die Leistungssteigerung fördern. Insbesondere sollten serielle Optimierungen vermieden werden, die eine Parallelisierung stören oder limitieren. Beispielsweise die Einführung unnötiger Datenabhängigkeiten oder die Ausnutzung einer Single-Core-spezifischen Hardwarearchitektur (zum Beispiel Cache-Kapazität).

Keine unnötigen Datenabhängigkeiten

Entwickler kennen jede Menge Tricks, die herangezogen werden können, um die serielle Performance eines Programms zu steigern. Die planlose Anwendung solcher Verbesserungen ist jedoch im Allgemeinen eine schlechte Idee.

„Programmierer vergeuden enorm viel Zeit damit, über die Geschwindigkeit unkritischer Teile ihrer Programme nachzudenken. Entsprechende Versuche einer Effizienzverbesserung resultieren meistens in erheblichen negativen Auswirkungen beim Debuggen und bei der Programmpflege. Wir sollten kleine Effizienzsteigerungen in 97 % aller Fälle außer Acht lassen: eine voreilige Optimierung ist die Wurzel allen Übels.“ (Donald Knuth, „Structured Programming with go to Statements.)

Zur Entscheidungsfindung sollte man Messungen und eine sorgfältige Analyse heranziehen, jeweils nur einen Parameter ändern und anschließend nochmals peinlich genau messen, um sicher zu gehen, dass die Änderungen hilfreich waren. Die Idee besteht darin, einen iterativen, auf den im Bild gezeigten Schritten basierenden Ansatz zu nutzen. 

Das Konzept für das serielle Performance-Tuning.Freescale

1. Schritt Vorbereiten: Zusammenstellen von Regressionstests und Benchmarks, die die Leistung des Programms verbessern sollen. Anschließend werden die für die Benchmarkmessung verwendeten Datensätze sorgfältig untersucht, um sicherzustellen, dass alle Fälle, vom besten bis zum schlechtesten Szenario, abgedeckt werden. Folgende Fragen sollte man sich zu Beginn stellen:

• Wie sehen meine Ziele aus? Den Leistungsdurchsatz eines Programms zu steigern, kann eine komplizierte, zeitraubende und fehlerbehaftete Aufgabe sein. Man sollte aufhören, wenn Ergebnisse erzielt wurden, die „gut genug“ sind.
• Alle Verbesserungen werden aufgrund von Analysen der Programmausführung vorgenommen, aber welche Szenarien sind am wichtigsten? Man sollte sich auf den Normalbetrieb, Betrieb unter hoher Last, Wiederherstellung nach Fehlern oder eine ausgewogene Mischung solcher Szenarien konzentrieren.
• Welche Performance-Parameter sind für das jeweilige Programm sinnvoll? Es ist wichtig, zu wissen, was man messen will, um die Ziele zu quantifizieren oder nachvollziehen zu können, dass diese erreicht wurden.

Es sollten Benchmarks angelegt werden, über die die Performancedaten gesammelt werden können. Alle Optimierungen erfolgen relativ zu den Benchmarks. Deshalb ist es wichtig, die Szenarien, für die die Performance in erster Linie verbessert werden soll, sorgfältig auszuwählen. Außerdem ist es gut, Fälle mit einzubeziehen, die zu einer unterschiedlichen Auslastung führen, um zu sehen, wie gut die Performance skaliert werden kann.

Kompromisse mit anderen Bereichen

Performance-Optimierungen bedeuten oft Kompromisse mit anderen Bereichen wie Speicherbedarf, Codepflege oder Portabilität. Man sollte sich darüber klar werden wie weit Kompromisse gehen dürfen. Um keine Fehler einzubauen, ist es zudem wichtig, eine gute Regressions-Testsuite zur Hand zu haben.

Das Tuning der seriellen Performance ist ein iterativer Prozess, der die wiederholte Ausführung des Programms voraussetzt, um die Performance zu messen und sicherzustellen, dass die korrekte Funktionalität erhalten bleibt. Für diese Aktivitäten sollte man auf gute, automatisierte Ressourcen zurückgreifen können.

2. Schritt Messen: Sammeln der Performance-Daten mithilfe von Profiling oder Simulation. Sobald die Performance ein vernünftiges Maß erreicht hat, sollte man aufhören. Um die Performance zu messen, setzt man üblicherweise „Profiler“ ein. Ein Profiler ist ein Programm, das die Ausführung eines anderen Programms beobachtet und Daten zu dessen Performance sammelt. Es gibt mehrere verschiedene Konzepte, die für das Profiling herangezogen werden:

• Sampling: Ein „Sampling Profiler“ zeichnet Messwerte in gleich bleibenden Intervallen auf.
• Instrumentierung: Ein auf Instrumentierung basierender Profiler kompiliert oder linkt für die Messung zusätzliche Anweisungen in das Programm.
• Emulation oder Simulation: Bei diesen Konzepten wird das Programm in einer Umgebung ausgeführt, die die Ausführungsumgebung emuliert oder simuliert.

Die Qualität der Performance-Daten unterliegt in verschiedener Hinsicht gewissen Schwankungen in Bezug auf Vollständigkeit und Abbildung der „echten Performance“. Beim Sampling erfolgen Messungen nur in gleich bleibenden Intervallen, daher ist keine absolut vollständige Analyse des Programmverhaltens möglich. Nicht auf Sampling basierende Konzepte ergeben abhängig von der Granularität des Messvorgangs vollständige Daten. Aber jedes Profiling-Konzept bringt gewisse Effekte mit sich, die sich darauf auswirken, wie nahe die Messungen der Programmausführung ohne Messkonzept kommen. Konzepte mit geringem Overhead kommen der typischen Ausführung deutlich näher als solche mit hohem Overhead wie Instrumentierung oder Interpretation. Diese können die Timing-Eigenschaften des Programms deutlich verfälschen.

Die Ergebnisse unterscheiden sich von Tool zu Tool, was Granularität und Format angeht. Profiler messen üblicherweise Daten relativ zu Funktionen, wobei einfache Messungen sich auf die Zeit beziehen, in der Aufrufe und Rücksprünge jeder Funktion ablaufen. Einige Profiler erfassen Informationen mit höherer Granularität oder ermöglichen dem Anwender das Hinzufügen von Instrumentierungspunkten.

Die Ausgangswerte von Profilern unterscheiden sich beträchtlich, von einfachen Reports bis hin zu komplexen GUIs mit Bedienelementen für Filterung und Sortierung. Zwei weit verbreitete Formen der Ausgangswerte sind:

• Flaches Profil: Ein flaches Profil ist im Allgemeinen ein tabellarischer Bericht, der nach Funktionen angeordnete Statistiken beinhaltet und beispielsweise auflistet, wie lange eine Funktion für die Ausführung benötigt hat (in Prozent und Zeiteinheiten) und wie oft die Funktion aufgerufen wurde.
• Aufrufdiagramm: In einem Aufrufdiagramm ist die Ausführungszeit in Bezug auf Aufrufketten, wiederum nach Funktion sortiert, dargestellt. Ein Aufrufdiagramm zeigt, welche Funktionen wie oft von einer bestimmten Funktion aufgerufen wurden, und wie viel Zeit für die Ausführung benötigt wurde.

Normalerweise werden beide Arten von Auswertungen herangezogen. Ein flaches Profil eröffnet eine gute Möglichkeit, schnell herauszufinden, wo viel Zeit verloren geht. Aus einem Aufrufdiagramm lässt sich gut ersehen, wo eine Funktion genutzt wird.

Schnell herausfinden wo viel Zeit verlorengeht

Die Auswahl der (des) Profiler(s) erfolgt anhand üblichen Kriterien wie Verfügbarkeit, Kosten, Zielplattform, Erfahrungswerten und so weiter. Mindestens ein Profiler sollte eingesetzt werden, der misst, welcher Anteil der Ausführungszeit außerhalb des Programms verbracht wird, um ein möglichst vollständiges Performance-Bild zu erstellen. Bei der Entwicklung eines Embedded-Systems muss eventuell ein Emulations- oder Simulations-basierter Profiler herangezogen werden, falls die Hardware noch nicht verfügbar ist oder im Zielsystem nicht genügend konsistenter Zielspeicher zur Verfügung steht.

Bei der Messung der Performance ist es wichtig, dass jedes Mal die gleichen Tools und die gleichen Benchmarks benutzt werden. Nur so ist sichergestellt, dass Steigerungen der Performance auch wirklich echte Verbesserungen sind. Bevor irgendwelche Änderungen durchgeführt werden, sollten die Daten der ersten Messreihe als Ausgangsbasis gesammelt werden. Alle Änderungen des Codes, die beibehalten werden, sollten bessere Ergebnisse bringen als die Ausgangsbasis.

3. Schritt Tuning: Anhand der Messwerte lässt sich analysieren, wo das Programm viel Zeit benötigt und ob dies in einer vernünftigen Relation steht. Eine wichtige Daumenregel beim Performance-Tuning lautet, „immer nur eine Änderung gleichzeitig“ vorzunehmen. Das kann eine Zeile Code oder eine Funktion sein. Die Menge an Code, die sich in einer Iteration ändert, hängt letztendlich von der Applikation, der Komplexität des Codes und anderen Faktoren ab. Bei jeder Iteration im Rahmen des Tunings sollten die im Profiling gesammelten Messwerte herangezogen werden, um nach der größtmöglichen Verbesserung zu suchen, die mit vernünftigen Mitteln realisierbar ist.

Ziele nicht zu hoch stecken

Bei der Performance-Verbesserung des seriellen Programms sollten die Ziele nicht zu hoch gesteckt sein. Einen Algorithmus, der lange Zeit benötigt, dahingehend zu ändern, dass er sich linear anstatt logarithmisch skalieren lässt, wäre ein gutes Beispiel für eine Modifikation, die gerechtfertigt ist.

Zuerst sollten Messwerte auf Hotspots hin untersucht werden. Hotspots sind Bereiche die einen übermäßig hohen Anteil der Ausführungszeit beanspruchen. Sie lassen sich mithilfe von flachen Profilen finden. Denn eine 10%-ige Verbesserung einer Funktion, die 50 % der gesamten Ausführungszeit in Anspruch nimmt, führt zu einer Verbesserung von insgesamt 5 %; eine 10%-ige Verbesserung einer Funktion, die 5 % der gesamten Ausführungszeit belegt, führt dagegen nur zu einer Verbesserung von insgesamt 0,5 %. Wurde das Programm bereits um 30 % verbessert, kann dies dazu führen, dass alle nachfolgenden Verbesserungen um 30 % geringer ausfallen.

Hat man sich für die Untersuchung eines Hotspots entschieden, muss darüber nachgedacht werden, warum dieser so viel Zeit beansprucht und ob dies noch in einem vernünftigen Rahmen liegt. Zeit vergeht mit:

• Berechnungen: die Ausführung der Befehle ist der erste Punkt, an den man in der Regel denkt. Deshalb muss zuerst darüber nachgedacht werden, ob ein passender Algorithmus eingesetzt wird. Beim Betrachten der Profiling-Daten für unterschiedliche Lastszenarien muss herausgefunden werden, ob sich der Algorithmus wie erwartet skalieren lässt.
• Werden alle Berechnungen wirklich benötigt? Möglicherweise können Berechnungen aus einer Schleife extrahiert oder Lookup-Tabellen verwendet werden, um die Rechenzeit zu reduzieren.
• Werden die richtigen Datentypen und -strukturen verwendet? Muss man größere Speicherbereiche hin- und herschieben, so dauert das typischerweise länger (zum Beispiel lassen sich Fließkommazahlen oft schneller verarbeiten als solche mit doppelter Präzision). Untersucht werden müssen die Auswirkungen unterschiedlicher Sprachkonstrukte auf der Plattform (zum Beispiel den für das Exception Handling benötigten Overhead).
• Ist die Struktur des Programms gut aufgebrochen? Bei Funktionen, deren Ausführungszeit nicht wesentlich länger ist als der Overhead eines Call/Returns, sind Inlining oder Refactoring eine gute Idee.
• Strategien für die Persistenz des Programms: Die Re-Initialisierung und Wiederverwendung einer Datenstruktur (oder Klasse) kann effizienter sein als die Realisierung einer neuen.
• Warteschleifen: manche Operationen müssen nur Zeit beim Warten totschlagen, was insbesondere in seriellen Programmen problematisch ist. I/O-Operationen wie Netzwerk- oder File-System-Zugriffe nehmen genauso wie Interaktionen mit Anwendern viel Zeit in Anspruch. Die Caching-Strategie kann auf weitere Verbesserungen hin analysiert werden, die typische Lösung aber liegt in einer parallelen Datenvorhaltung. An diesem Punkt sollte der Hang zur Parallelität vermieden, aber die Abhängigkeit beachtet werden.
• Datenbewegungen: beim Arbeiten mit großen Datenmengen kann es vorkommen, dass Programme häufig Daten in den Speicher laden beziehungsweise herausschreiben. Die Reduzierung unnötiger Speicherbewegungen kann sehr hilfreich sein. Memory-Profiler sind gute Tools, um die Verwendung des Speichers zu verstehen und zu verbessern.
• Obwohl dies die serielle Performance möglicherweise verbessern könnte, sollte man die Daten nicht lokal konzentriert organisieren (zum Beispiel indem gemeinsam genutzte Daten, im Speicher nahe beieinander abgelegt werden, was statt mehrerer kleinerer Operationen nur eine einzige bedeuten würde). Diese Art der Optimierung wird besser innerhalb der Parallelisierung durchgeführt, wenn gleichzeitig Faktoren wie Cache-Breite und Cache-Regeln in Betracht gezogen werden.

Es ist empfehlenswert, mehrere Informationsquellen für die Prüfung jedes Hotspots zu nutzen. Zum einen gibt es den Code selbst. Eine Menge Informationen lassen sich auch aus dem von einem Profiler erzeugten Aufrufdiagramm ableiten. Werden die von einer Funktion durchgeführten Aufrufe und die Aufrufe an eine bestimmte Funktion analysiert, wird ersichtlich, wie die Funktion genutzt wird und wie sie funktioniert.

Berechnungszeit reduzieren

Befindet sich die am Hotspot verbrauchte Zeit in einem vernünftigen Rahmen, so kann man zum nächsten übergehen. Wenn nicht, muss über eine Modifikation zur Verbesserung nachgedacht werden, ohne die Parallelisierung zu stören. Bevorzugt werden sollten eher Änderungen mit denen sich die Berechnungszeit reduzieren lässt, und nicht solche, die für eine minimale Datenmenge sorgen. An dieser Stelle sollte man sich darauf konzentrieren, das Programm auf die wesentlichen Berechnungen zu reduzieren, die für dessen korrekte Funktion ausreichen.

Es gibt Modifikationen, die die Performance-Werte vorübergehend verschlechtern, jedoch weitere Änderungen, die zu einer insgesamt besseren Performance führen, erst ermöglichen. Auch die Reihenfolge der Änderungen kann signifikante Auswirkungen haben. Bevorzugt werden sollten in erster Linie Modifikationen, die die Möglichkeiten für weitere Änderungen so wenig wie möglich einschränken.

4. Schritt Analyse: Kam es durch die Änderungen zu keinen positiven Auswirkungen müssen diese zurückgenommen und analysiert werden. Bei positiven Auswirkungen befasst man sich mit dem nächsten Engpass. Beachtet werden sollte, dass manche Änderungen die Performance nicht unmittelbar verbessern, jedoch Änderungen ermöglichen, die zu weiteren Performance-Steigerungen führen. Jede Änderung sollte analysiert werden. Die minimale Anforderung an eine „gute Änderung“ besteht darin, dass sie keine Fehler induziert und direkt oder indirekt weitere Änderungen ermöglicht, mit deren Hilfe die im Schritt Vorbereitung erarbeiteten Performanceparameter verbessert werden können. Hier kommt die Maxime „reparieren Sie nichts, was funktioniert“ ins Spiel. Angenommen durch eine Änderung konnte das Programm um 3 % schneller gemacht werden. Es handelt sich jedoch um alten Code, der jahrelang gut funktioniert hat. Dann stellt sich die Frage, ob man sich für diese 3 % der Gefahr aussetzen sollte, neue Fehler einzubringen? Auch das Risiko muss natürlich in Betracht gezogen werden. Analysiert werden diese Kriterien, indem man die Regressions-Suite noch einmal ausführt und das Programm mithilfe der Benchmarks noch einmal misst.

Im Einklang mit wichtigen Anforderungen

Schlägt die Regression fehl oder ist die Performance schlechter als vor der Änderung, so wurde in Bezug auf das Programm oder die Modifikation etwas übersehen. In diesem Fall muss das Programm nochmals vor und nach der Modifikation analysiert werden. Ist keine Reparatur möglich, muss die Modifikation rückgängig gemacht werden. Lässt sich keine vernünftige Modifikation finden, geht man zum nächsten Hotspot.

War die Regression erfolgreich und hat sich die Performance verbessert, dann ist zu überprüfen, ob die Änderungen mit anderen wichtigen Anforderungen im Einklang stehen. Solche Kriterien lassen sich oft nur schwer mit Automatismen validieren, sollten aber auf jeden Fall Teil der Prüfliste sein.

(ah)