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:

ÜBUNG: Caches

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

ÜBUNG: SIMD

Analysieren und optimieren Sie das vorgegebene Programm entsprechend der Anweisungen: Siehe hier

INFO
Illustrationen zum Ende der immer schnelleren seriellen Programme:
Lecture 1, Folien 55 - 71, CS 267 der UC Berkeley
INFO
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.

INFO
Roofline Modell:
ÜBUNG: Roofline

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

Shared Memory Architektur

Distributed Memory Architektur

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.

ÜBUNG: Amdahl's Gesetz

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.

INFO
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
ÜBUNG: Amdahl's Gesetz mit heterogenen Prozessoren

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.