High Performance: Ansätze und Grenzen
Contents
High Performance: Ansätze und Grenzen#
High Performance Computing: wenn es nicht darum geht wie schnell sich ein Programm entwickeln lässt, sondern wie schnell es ausgeführt wird. Kontrast zu vielen Business-Applikationen.
Was sind limitierende Faktoren für die Schnelligkeit eines Programms:
(FL)OPS/s: Wie viele (Fließkomma-)Operation pro Sekunde können ausgeführt werden?
Latenz: Wie lange dauert der Zugriff auf 1 Datenwert?
Bandbreite: Wie viele Daten können pro Zeiteinheit gelesen/geschrieben werden?
Ggfs. noch wichtiger als ein System, das hohe FLOP/s und Bandbreite sowie niedrige Latenz bietet: ein Programm, das ein Problem mit weniger Operationen löst. Hierbei ist zu beachten:
“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” - Donald Knuth
Das bedeutet erst optimieren, wenn man rausgefunden hat, wo überhaupt das Performance-Problem ist. Optimierung kostet Zeit und macht einfachen Code oft kompliziert. Es gilt wie so oft das Paretoprinzip: 80% des Effekts (Laufzeit des Programms) kommen von 20% der Ursache (Code). Im Falle von Programmen ist die Verteilung meist noch extremer, z.B. 97% des Effekts von 3% der Ursache.
Ansatz 1: Schnellerer Prozessor#
Ein traditioneller Ansatz für schnellere Ausführung eines Programms war warten:
Moore’s Law: Alle 18 Monate verdoppelt sich die mögliche Transistorzahl auf einem Chip
Leitungen werden kürzer: höhere Taktfrequenz
Mehr Transistoren: komplexere Operationen können pro Takt ausgeführt werden
Moore’s Law ist 2021 noch intakt aber ein Ende absehbar:
Strukturgrößen stoßen an physikalische Grenzen
Die Kosten pro Transistor sinken nicht mehr - doppelt so großer Chip also auch doppelt so teuer
Die Beschleunigung für serielle Programme leidet schon länger:
“Power Wall”: Erst konnte die Frequenz nicht mehr gesteigert werden (ca. 2005), da hierbei der Energiedichte überproportional steigt (Mit Frequenz steigt auch Spannung, mit beiden die Energie, die als Hitze abgeführt werden muss)
“ILP Wall”: Auch komplexe Operationen wurden irgendwann in 1 Takt ausgeführt - zusätzliche Transistoren wurden verwendet, um Teile von seriellen Programmen parallel auszuführen. Hierbei gibt es prinzipielle Grenzen (Abhängigkeiten), praktische Grenzen (Erkennung von Parallelität) und Verschwendung (Spekulative Ausführung)
“Memory Wall”: Die Bandbreite des Hauptspeichers ist viel langsamer gewachsen als FLOP/s. Die Latenz noch viel langsamer als die Bandbreite.
Um den letzten Punkt (die “Memory Wall”) abzufedern werden viele Transistoren für Caches eingesetzt, die Teile des Hauptspeichers schneller auf dem Prozessor verfügbar machen. Mehr Informationen zu Caches:
https://stackoverflow.com/questions/1126529/what-is-the-cost-of-an-l1-cache-miss
http://igoro.com/archive/gallery-of-processor-cache-effects/
https://userpages.uni-koblenz.de/~unikorn/lehre/gdra/ss14/05 Speicher (VL16).pdf
Analysieren und optimieren Sie das vorgegebene Programm entsprechend der Anweisungen: Siehe hier
Die “ILP Wall” bezieht sich vor allem darauf vom Programmierer bzw. Compiler als seriell angegebene Instruktionen teilweise parallel auszuführen. Mit speziellen Befehlssätzen für Single Instruction Multiple Data (SIMD) gibt es die Möglichkeit auf einem einzelnen Prozessor explizit mehrere Datenwerte parallel zu bearbeiten. Beispiel:
Ein Bild soll maskiert werden, d.h. jeweils der gleiche Pixel aus Bild und Maske sollen kombiniert werden (z.B. Addition oder Binäres Und)
Jedes Pixel besteht aus 4 Bytes (Rot, Grün, Blau, Alpha)
Einfacher Ansatz: Schleife über y, x und 4 Pixel-Komponenten und dann Addition, d.h. xy4 Additionen
Der Prozessor verfügt über 64 Bit Register und SIMD-Befehlen, die es erlauben ein 64-Bit Register als 8 einzelne Bytes zu betrachten
Zu Beachten: Wegen Überträgen ist die Addition von 8 x 8 Bit anders als 1 x 64 Bit
SIMD-Ansatz: Schleife über y, x/2: Lade 2 Pixel zu je 4 Byte in das Register und addiere, d.h. x*y/2 Additionen
Nur noch ein Achtel der Additionen werden benötigt
Aktuelle x86-Prozessoren mit 512 Bit SIMD Registern/Instruktionen
Ein Nachteil von SIMD ist die zusätzliche Komplexität des Befehlssatzes des Prozessors. Insbesondere eine Herausforderung für Compiler. Ein ähnliches Prinzip sind Vektor-Befehle, die lange Zeit im Supercomputing beliebt waren (z.B. Cray Computer) und bei RISC-V wieder aufgegriffen werden. Eine interssante Diskussion dazu: https://medium.com/swlh/risc-v-vector-instructions-vs-arm-and-x86-simd-8c9b17963a31
Analysieren und optimieren Sie das vorgegebene Programm entsprechend der Anweisungen: Siehe hier
Illustrationen zum Ende der immer schnelleren seriellen Programme:
Lecture 1, Folien 55 - 71, CS 267 der UC Berkeley
Performance Optimierung von seriellen Programmen und SIMD:
Lecture 2, Folien 5 - 42 und 125 - 134, CS 267 der UC Berkeley
Das Roofline Performance-Modell kann die Performancegrenzen für Probleme auf einem bestimmten Prozessor/System zeigen. Dies hilft unter anderem, um zu entscheiden ob und wenn ja wo noch Optimierungspotenzial liegt. Es wird unterschieden zwischen
Compute-Intensive: pro Speicherwert werden viele Rechenoperationen durchgeführt. Der limitierende Faktor ist die Prozessorleistung. Performancegewinne können z.B. durch Nutzung von SIMD erzielt werden.
Data-Intensive: pro Rechenoperation werden viele Speicherwerte benötigt. Der limitierende Faktor ist die Speicherbandbreite - die Rechenleistung kann nicht voll ausgenutzt werden.
Roofline Modell:
- Gute Kurzübersicht auf Folien 2-4 und 16-17 vom RRZE FAU Erlangen-Nürnberg
- Erhöhen der Compute-Intensitiviy von Matrix-Multiplikation: Lecture 3, Folien 3 - 14, CS 267 der UC Berkeley
- Detailliert zu Roofline Modell: Lecture 3, Folien 54 - 99, CS 267 der UC Berkeley
Erstellen Sie ein Roofline-Profil für Ihre Maschine: Siehe hier
Ansatz 2: Mehr Prozessoren#
Als Alternative Verwendung der durch Moore’s Law verfügbaren Transistoren wurden mehrere gleichartige Prozessorkerne auf einen Chip gepackt. Statt 1 Prozessor, der doppelt so schnell rechnet, bekommt man nun 2 Prozessorkerne, die jeweils so schnell sind wie davor. Leider bedeutet, dass nicht automatisch doppelte Performance, insbesondere:
Die “Memory Wall” bleibt grundsätzlich bestehen - nun müssen sich ggfs. sogar mehrere Prozessorkerne den gleichen Speicherbus teilen
Serielle Programme laufen nur auf 1 Prozessorkern
Die Parallelisierung von Programmen ist a) schwierig für Menschen, b) schwierig für Computer (z.B. Compiler), c) nicht umsonst. Durch Kommunikation und Synchronisation bleibt bei einer Parallelisierung eines Programms auf n Prozessoren oft deutlich mehr als 1/n an Arbeit pro Prozessor übrig.
Trotz dieser Schwierigkeiten ist Parallele Hardware und Programmierung der absehbar dominante Weg für mehr Performance. Wir beschäftigen uns im weiteren Verlauf auch hauptsächlich mit Programmiermodellen, die die Parallelisierung für Mensch und/oder Maschine vereinfachen.
Seit ca. 2005 hat sich die Anzahl der Prozessorkernen auf einem Chip stetig weiterentwickelt. Dies bringt auch inder Produktion einen weiteren Vorteil: mit sinkenden Strukturgrößen sinkt auch der Yield, d.h. der Anteil an Chips, der fehlerfrei produziert wird. Bei vielen gleichartigen Kernen auf einem Chip kann der Yield erhöht werden, wenn man mehr Kerne auf dem Chip produziert als benötigt. Beispielsweise verwendet Apple M1 Chips für Einstiegsmodelle, wo nur 7 von 8 GPU Kernen aktiviert sind.
Parallele Programmierung für Performance ist nicht neu. Im Supercomputing z.B. schon lange üblich. D.h. es gibt auch viele Erfahrungen und Programmiermodelle auf die aufgebaut werden kann, auch wenn sich jetzt Einsatzort und -zweck teilweise verschieben.
Die Kerne auf einem Chip teilen sich üblicherweise den gleichen Hauptspeicher - wir sprechen von einer Shared Memory Architektur. Ansonsten sprechen wir von Distributed Memory: Prozessoren tauschen sich mit Nachrichten über einen Bus aus. Dies können Busse zwischen Prozessoren in einem System sein oder auch Netzwerke zwischen verschiedenen Systemen. Häufig sind Mischformen, z.B. ein Cluster von Shared Memory Systemen (z.B. 4-Kern-CPU), die per Netzwerk verbunden sind. Shared Memory kann auch realisiert werden bei verteilten Systemen - dann sind Zugriffe auf manche (lokale) Speicherbereiche schneller als auf andere (zu anderem Prozessor gehörend): Non-Uniform Memory Access (NUMA). Bei Shared Memory Systemen haben die einzelnen Prozessoren typischerweise eigene Caches - diese müssen konsistent gehalten werden.
Shared Memory |
Distributed Memory |
---|---|
Zugriff auf globalen Speicher von allen Prozessoren/Kernen |
Jeder Prozessor hat eigenen privaten Speicherbereich |
Implizite Kommunikation über gemeinsamen Speicher |
Explizite Kommunikationsbefehle |
Zugriffe auf geteilten Speicher müssen koordiniert werden |
Austausch über Nachrichten |
Im verteilten System kommen noch weitere Probleme hinzu - siehe entsprechende Vorlesung und die Fallacies of Distributed Computing.
Manche Probleme sind “embarrassingly parallel”, d.h. sie können in komplett unabhängige Unterprobleme unterteilt werden. Ein Beispiel sind Monte Carlo Simulationen in denen viele zufällig gewählte Szenarien unabhängig voneinander durchsimuliert werden. Hier kann mit n
Prozessoren ein n
-facher Geschwindigkeitszuwachs erreicht werden. Viele Aufgaben sind jedoch nicht “embarrassingly parallel”. Amdahl’s Law gibt an um wie viel ein Programm beschleunigt werden kann, das teilweise sequenziell ausgeführt werden muss:
p = Anteil am Programm, der parallel ausgeführt werden kann (an der Laufzeit, nicht am Code) Seit 2005
n = Anzahl der Prozessoren
Speedup s = 1 / ((1-p) + p/n) (Zeit auf 1 Prozessor getailt durch Zeit auf n Prozessoren) Zum Beispiel kann ein Programm, das zu 95% parallelisiert werden kann, auf 8 Prozessoren maximal um Faktor 5,9 beschleunigt werden.
Erstellen Sie eine Tabelle/ein Chart, das den maximalen Speedup für folgende Kombinationen zeigt:
- Prozessoren: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096
- Paralleler Anteil: 50%, 75%, 90%, 95%
Wie viel Zeit wird eingespart bei einem Programm mit parallelem Anteil 80%, das auf 1 Prozessor 24 Stunden läuft beim Umstieg von 1 auf 16 Prozessoren? Wie viel beim Umstieg von 16 auf 64 Prozessoren?
Ansatz 3: Heterogenes Computing#
Der Befehlssatz heute gängiger Allzweck-Prozessoren ist sehr komplex. Z.B. umfasst die Instruction Set Reference A-Z von Intel mehr als 2.000 Seiten. Diese Prozessorarchitektur wird auch für sehr vielseitige Anwendungen eingesetzt: Steuersysteme in Industrieanlagen, Spiele auf Desktoprechnern, Webserver, Audioverarbeitung, Graphik, Wissenschaftliche Berechnungen, usw. Für manche Anwendungen insbesondere welche mit hohem Performancebedarf spielen nur wenige Operationen und insbesondere relativ starr vordefinierte Kontrollflüsse eine Rolle. Beispielsweise wird zur Aufhellung eines Bilds nur die Addition benötigt, die nacheinander/parallel für alle Pixel ausgeführt wird. Weder gibt es Abhängigkeiten von einem Pixel zum nächsten noch kann es zu Sprüngen im Kontrollfluss (if-then-else) kommen. Etwas komplexer gilt das z.B. auch für Neuronale Netzwerke, wo die Hauptarbeit aus einer massiven Anzahl von Multiplizier-Addier-Operationen besteht. Ein Ansatz ist nun spezielle Rechenkerne zu bauen, die für bestimmte Anwendungsgebiete funktionieren. Die Vorteile sind:
Einfachere Kerne - weniger Transistoren pro Kern, dafür sehr viele Rechenkerne auf einem Chip, z.B. Google Tensor-Processing Unit (TPU) v1 für Neuronale Netze mit 65.536 8-Bit Multiply-Accumulate Einheiten
Taktraten nicht im Fokus, da die Performance aus der Parallelität kommt. Energiesparend. z.B. TPU v1 mit 700 MHz
Optimierte Speicheranbindung bzw. Caches/On-Chip Speicher, der Zugriffsmuster des Anwendungsgebiet berücksichtigt. Non-Uniform Memory Access (NUMA), d.h. bestimmte Speicherbereiche sind für bestimmte Rechenkerne effizienter zugreifbar. Lokalität der Anwendung wird ausgenutzt. Z.B. benachbarte Pixel auf GPU
Spezialisierte Chips gibt es auch schon lange, z.B. in Form von Digital Signal Processors (DSP). Aktuelle Beispiele:
Google Tensor Processing Unit (TPU) für Neuronale Netze
Graphics Processing Units (GPUs) für paralleles Computing statt nur für Computergraphiken
Interessant ist der Apple M1 als heterogener Prozessor mit 4 schnellen Single Thread Kernen, 4 langsameren Stromsparkernen, GPU und Neural Engine - spezielle Rechenkerne für Machine Learning. Neben der Zusammenstellung der Rechenkerne sind hier noch zwei interessante Aspekte:
Software: die Nutzung der Rechenkerne erfolgt über Computing-Frameworks (z.B. CoreML), die eigenständig für eine optimale Ausführung auf den verschiedenen Kernen sorgen. Das reduziert die Komplexität für Entwickler enorm.
Einheitlicher Speicher: Der M1 ist nicht nur ein Prozessor, sondern beinhaltet auch den Arbeitsspeicher, der von allen Rechenkernen gleichzeitig genutzt werden kann.
Der letzte Punkt ist interessant, da insbesondere bei der Nutzung von GPUs immer abgewogen werden muss, ob sich ein Transfer vom CPU Hauptspeicher zum GPU Speicher und zurück lohnt. Dies gilt auch bei bisherigen “integrierten Graphikeinheiten”, die den CPU Hauptspeicher für die integrierte GPU nutzen: hier wird ein extra Speicherbereich für die GPU reserviert und die Daten müssen in/aus diesen Bereich kopiert werden, wenn sie mit der CPU ausgetausch werden sollen.
Auch heutige Supercomputer sind meist heterogene Systeme, die zumindest CPUs und GPUs kombinieren. Siehe z.B. Lecture 1, Folien 15 - 26, CS 267 der UC Berkeley. der bwUniCluster 2.0 enthält neben CPUs auch GPUs.
Turing Lecture von John Hennessy und David Patterson zur Zukunft der Computerarchitektur:
- Folien: https://iscaconf.org/isca2018/docs/HennessyPattersonTuringLectureISCA4June2018.pdf
- Vortrag: https://www.youtube.com/watch?v=3LVeEjsn8Ts
Betrachten wir einen Prozessor mit einem Kern für sequenzielle Aufgaben und 4 Kernen für parallele Aufgaben. Aufgrund von technologischen Entwicklungen können Sie bei der nächsten Prozessorgeneration entweder den Kern für sequenzielle Aufgaben doppelt so schnell machen (A) oder die Anzahl der Kerne für parallele Aufgaben verdopplen (B). Wofür entscheiden Sie sich (d.h. wie hoch ist der jeweilige Speedup), wenn der typische Workload einen parallelen Anteil von 25%, 50%, 75%, 90% oder 95% hat?
Ganz anders: Quanten Computing#
Quantencomputer funktionieren anders als die uns bisher bekannten Prozessoren. Vor allem theoretisch konnte gezeigt werden, dass es möglich ist bestimmte Probleme effizienter zu lösen als mit klassischen Computern:
Shor’s Algorithmus zur Primfaktorzerlegung in polynomieller Zeit (schneller als bekannte klassische Algorithmen)
Grover’s Algorithmus zur Suche in einer unsortierten Datenbank mit Komplexität O(sqrt(N)) - schneller als der prinzipiell schnellstmögliche klassische Algorithmus mit O(N)
Quantensimulationen
Stark vereinfachte Beschreibung: Im Grundprinzip kann ein Quantenregister alle möglichen Werte gleichzeitig annehmen. Wenn man z.B. eine Hashfunktion invertieren will, dann berechnet man die Hashfunktion auf allen möglichen Inputs gleichzeitig. Danach muss man den Input selektieren, das den gewünschten Hashwert geliefert hat. Hier kommt das Problem des Quantencomputers ins Spiel: um einen Wert zu erhalten muss das Quantenregister gemessen werden und dabei erhält man nur genau einen Wert, der zufällig aus allen gleichzeitig eingenommenen Werten des Registers gewählt wird. Quantenalgorithmen wenden verschiedene Techniken an, um die Mess-Wahrscheinlichkeit für interessante Werte zu erhöhen.