Anwendungen: Wofür eigentlich “Computing”?#

  • Computer: Berechner - ursprünglich Menschen

  • Frühe Anwendungsgebiete z.B. Berechnung von Flugbahnen von Geschossen

  • Berechnungen - Auslastung für Rechenwerke, z.B.:

    • Numerische Operationen, z.B. Matrixmultiplikation für Neuronale Netze oder Rotation von 3D-Objekten

    • Logische Operationen, z.B. Berechnung von kryptographsichen Hashes

    • Suche: Generierung eines Lösungsraums und Durchsuchen nach Lösungen

  • Computer werden auch für Aufgaben genutzt, wo das Rechenwerk hauptsächlich mit Warten beschäftigt ist, z.B.:

    • Endnutzeranwendungen, die auf Nutzereingaben warten

    • Datenbanken, wo auf permanente Speicher gewartet wird (in Datenbanken gibt es auch viele rechenintensive Aufgaben)

    • Business-Anwendungen, wo auf andere Business-Anwendungen gewartet wird

Anwendungsbeispiele, wo Computing dominiert

  • Wissenschaft: Simulationen, numerische Lösung von Gleichungssystemen, Suche

  • Machine Learning

  • Verarbeitung von Bildern, Videos, Audo

  • Spiele: Simulation und Graphik

  • Kryptographie: Sowohl beim Schützen als auch Angreifen

Warum braucht man High Performance?

  • Kürzere Laufzeit - z.B. wenn Analyse-Ergebnisse oder Graphiken in Echtzeit benötigt werden

  • Größere Probleme lösen - z.B. genauere Simulation von Wetter, Deep Neural Networks

  • Energieeffizienz - bei optimaler Auslastung und kürzerer Laufzeit weniger Energieverbrauch, z.B. Gesichtserkennung auf Smartphone

INFO
Anwendungsbeispiele aus dem wissenschaftlichen Computing:
Lecture 1, Folien 29 - 49, CS267 der UC Berkeley

(Ver)Einfach(t)e Beispiele#

Bildverarbeitung#

Ein digitales Bild ist im Endeffekt ein zweidimensionales Array von Pixeln. Jedes Pixel wird typischerweise entweder aus

  • 1 Wert bei Graustufenbildern von 0 (Schwarz) bis 1 (Weiß)

  • 3 Werten bei Farbbildern, die die Intensitäten von Rot, Grün und Blau angeben. Jeder dieser Werte kann zwischen 0 und 1 als Fließkommazahl oder z.B. als 8-Bit Integer zwischen 0 und 255 gespeichert werden.

Konvertierung in Graustufen#

Wenn ein Farbbild in Graustufen konvertiert wird, wird für jeden Pixel der Graufstufenwert als gewichtete Summe der Farbkomponenten berechnet (siehe Wikipedia):

GRAU = 0.2126 * ROT + 0.7152 * GRUEN + 0.0722 * BLAU

Pro Pixel sind also 5 Fließkommaoperationen (FLOP) notwendig (3 Multiplikationen und 2 Additionen). Zusätzlich müssen die meist als Ganzzahl repräsentierten Pixel erst in Fließkommazahlen und später zurück konvertiert werden. Beispiele:

  • 24 Megapixel Bild einer digitalen Kamera: 120 MFLOP

  • 90 Minuten 4K UHD Video mit 50 Hz: 90 Minuten * 60 Sekunden/Minute * 50 Bilder/Sekunde * 8,3 Megapixel * 5 FLOP = 11.2 TFLOP

Interessant hier ist, dass jedes Pixel komplett unabhängig von anderen Pixeln verarbeitet werden kann. Dies ermöglicht eine einfache und hochgradige Parallelisierung.

Convolution/Kernels#

Die Kernel-Technik wird für viele Filter angewandt. Jeder Pixel im Zielbild wird als gewichtete Summe des Pixels und seiner Nachbarn im Quellbild berechnet. Die Gewichte werden in einer Matrix angegeben. Z.B. beim Weichzeichnen mit Box Blur ist die Matrix:

      [[1 1 1]
1/9 *  [1 1 1]
       [1 1 1]]

Das heißt ein Pixel wird als Durchschnitt aller umgebenden Pixel berechnet. Auch hier kann jedes Pixel unabhängig voneinander berechnet werden - jedoch überlappen sich die Speicherbereiche:

  • Können effizientere Algorithmen Ergebnisse wiederverwenden, z.B. ist der Durchschnitt von 3 nebeneinanderliegenden Pixeln auch in der Zeile darüber und darunter relevant

  • Bei wiederholter Anwendung muss auf die Ergebnisse von anderen Pixeln gewartet werden

Game of Life/Stencil#

Siehe Wikipedia zu Conway’s Spiel des Lebens

Eine einfache Simulation. Ähnlich wie bei den Bildfiltern wird eine Matrix betrachtet und die Werte in der Zielmatrix hängen von den Nachbarn in der Ursprungsmatrix ab.

Dies lässt sich auch als Schablone/Stencil bezeichnen - die gleiche Schablone wird für jeden Zielwert über die Quellmatrix gelegt. Auch andere Probleme, z.B. aus der Sparse Matrix Algebra oder wie bereits erwähnt Bildbearbeitung lassen sich so umsetzen.

Künstliche Neuronale Netze#

Künstliche Neuronale Netze verketten Input-Variablen (z.B. Pixel eines Bilds) über künstliche Neuronen, die in verschiedenen Architekturen angeordnet und miteinanders vernetzt sind, zu Ausgabe-Variablen (z.B. zeigt einen Affen, zeigt eine Kuh, …). Die künstlichen Neuronen bilden gewichtete Summen über Eingänge (Input-Variablen oder Ausgänge von anderen Neuronen), wenden eine Aktivierungsfunktion an und geben den erhaltenen Wert als Ausgabe-Variable oder Input für ein weiteres Neuron aus. Die Berechnung der Ausgaben über gewichtete Summen sind also im Endeffekt hauptsächlich Matrix-Multiplikationen - ebenso verhält sich beim Training eines Netzwerks über Backpropagation. Hier wird vereinfacht ausgedrückt für ein Trainingsbeispiel das Netz ausgewertet, der errechnete Wert mit dem Zielwert verglichen und die Differenz als Anpassung entsprechend der Gewichte rückwärts durch das Neuronale Netz weitergegeben.

Heutige Neuronale Netze zeichnen sich durch sehr viele Neuronen aus. Das führt zu sehr vielen Gewichten, die berechnet werden müssen, z.B. das Inception Netzwerk mit ca. 25 Millionen Parametern. Das Training eines Beispiels wird damit aufwändig und gleichzeitig erfordert es eine sehr hohe Anzahl von Trainingsbeispielen, um genügend Informationen für alle Parameter zu sammeln, z.B. 50.000 Trainingsbilder in ImageNet.

N-Body Simulationen#

N-Body Simulationen simulieren das Verhalten von vielen Objekten zwischen denen Kräfte wirken. Dies können beispielsweise einzelne Atome in einer Gassimulation sein oder Planeten und Sterne in der Astrophysik, um die Entstehung von Galaxien zu simulieren.

Ein einfaches Beispiel wäre die 2D-Simulation von einem Stern und einem Planeten. Zu beiden Objekten wird die x und y Koordinate, die Masse und die x und y Geschwindigkeit gespeichert. Nun wird für kleine Zeitschritte für beide Objekte berechnet:

  • Gravitionskraft vom anderen Objekt

  • Auswirkung auf die Beschleunigung

  • Auswirkung auf die Geschwindigkeit

  • Neue Koordinaten basierend auf der Geschwindigkeit

Es wird also eine diskrete Simulation durchgeführt. Bei vielen Objekten ist zu beachten, dass jedes Objekt von allen anderen Objekten auswirkt. Je nach modellierter Kraft können weiter entfernte Objekte ignoriert oder zusammengefasst werden.

Muster#

Bei den unterschiedlichen Anwendungen im High Performance Computing gibt es wiederkehrende Berechnungsmuster, die notwendig sind, um sie zu lösen. Praktische Anwendungen erfordern oft mehrere Muster, die wie Bausteine zusammengesetzt werden. Die Analogie mit Bausteinen ist ggfs. zu einfach:

  • Oftmals ist die Aufteilung des Problems in Bausteine nicht trivial, sondern erfordert ein Umdenken (z.B. Graph als Matrix repräsentieren oder andersrum, Fouriertransformation)

  • Um zwei Bausteine “aufeinander” zu bauen sind teils umfangreiche Transformationen/Zwischenschritte notwendig - “Glue Code”

Beispiele für Muster:

  • Matrix-Algebra: Bildverarbeitung, 3D-Graphik, physikalische Simulationen (z.B. Wärmeverteilung), Machine Learning, Video-Komprimierung, …

  • N-Body Simulationen: Moleküle, Planeten/Sterne/Galaxien, …

  • Graphen-Suche: IP-Routing, Natural Language Processing, Baumbasierte ML-Modelle, Kollisionsdetektion, …

Einige solcher Muster werden wir als Beispiele in den folgenden Kapiteln näher betrachten. Dabei deuten wir den genauen Zusammenhang zwischen Anwendung und Muster oft nur an, wenn hierzu umfangreiches domänenspezifisches (z.B. Physik) oder mathematisches Hintergrundwissen erforderlich ist.

Für die Muster gibt es oft umfangreiches Material in der Literatur und konkrete Softwareprojekte, die das Muster allgemein oder für bestimmte Ausprägungen hochperformant auf unterschiedlichen Architekturen lösen.

INFO
Eine Übersicht zu den Mustern (Computation und Communication) von wichtigen Anwendungen findet sich in Kapitel 3, insbesondere Abbildungen 3, 4 und 6 aus "The Landscape of Parallel Computing Research: A View From Berkeley" von Asanovíc et al., 2006