PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Rechnerarchitekturen für ML

Die Software für Implementierung der Modelle und Algorithmen ist stark verknüpft mit der Rechnerarchitektur

Performanzprobleme vor allem bei Training, aber auch bei Inferenz!

Parallelisierung kann die Performanz steigern

Effizienz: Optimierung von Rechenzeit + Speicherbedarf + Energie!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Rechnerklassifikation

• Datenverarbeitung bedeutet die Verarbeitung eines Daten- und eines Instruktionsstromes (DS/IS)
• Eine Datenverarbeitungsanlage enthält:

VE

Verarbeitungseinheit für Daten

SM

Speichermodul → (Static/Dynamic) RAM, Registerbank, Cache

KE

Kontrolleinheit für die Ablaufsteuerung, kann in VE enthalten sein.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

• Dabei sind diese drei Einheiten über Instruktionsströme und Datenströme gekoppelt:

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

• Man kann grob Rechnerarchitekturen nach der Art der Verarbeitung des DS/IS und möglicher Parallelisierung klassifizieren ⇒ Flynn Klassifikation

SISD

Single-Instruction ⊗ Single-Data Stream

SIMD

Single-Instruction ⊗ Multiple-Data Stream

MISD

Multiple-Instruction ⊗ Single-Data Stream

MIMD

Multiple-Instruction ⊗ Multiple-Data Stream

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Funktionale Dekomposition

• Die Modelle lassen sich je nach Architektur und Aufbau funktional darstellen → Funktionale Komposition mit Datenfluss

Neuronales Netzwerk

Jedes Neuron N besteht aus zwei gekoppelten Funktionen Σ als Summierer und f als Transferfunktion:

$$N(x_1,x_2,..,x_n) = f(\Sigma_j w_jx_j)$$

Das Netzwerk kann als eine große Funktion M(x) aus Funktionen (Neuronen einer Ebene sind zu einer Funktion L zusammengefasst) gebaut werden:

$$M(\vec{x}) = L_m(L_{m-1}(...(L_0))), L_i=\{N_{i,1},N_{i,2},..\}$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Funktionale Dekomposition eines SLP (Neuron N)

Die Berechnung aller {N_i} Funktionen in einer Ebene L_i kann parallel erfolgen!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Entscheidungsbäume

Auch ein Entscheidungsbaum kann funktional dargestellt werden durch geschachtelte konditionale Ausdrücke:

$$N({x_i}) = \left\{ {\begin{array}{*{20}{c}} {{v_1},{x_i} < \varepsilon } \\ {{v_2},{x_i} \geqslant \varepsilon } \end{array}} \right.$$

$$M(\vec x) = N({N_{x1}}({N_{x3}}(..),{N_{x4}}(..)),{N_{x2}}(..))$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Matrixalgebra

• Parallelisierung ist gut auf Probleme mit "Schleifeniterationen" anwendbar

• Matrixalgebra zeigt inherente Parallelität in Matrixoperationen (häufig sequenziell durch Schleifeniteration verabeitet)

Neuronale Netze (i.A. mit regulärer Struktur) können durch Matrixalgebra abgebildet werden

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Parallelisierung

Parallelisierung erfolgt auf der Daten- und Kontrollpfadebene

Kontrollpfadparallelität bedeutet Paritionierung einer Berechnung in separate Prozesse → Multiprocessing & Multithreading → Mehrprozessorechner (MCPU)

Datenpfadparallelität bedeutet die Belegung mehrerer Verarbeitungseinheiten (Rechenwerke) → GPU, FPGA, (CPU:MMX)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Inferenz

Bei Entscheidungsbäumen kann der Baum nur sequenziell berechntet werden (höchstens spekulativ mit parallelen Teilbäumen). Aber es gibt auch Multibäume (Random Forest). Diese können parallel berechnet werden.
Bei neuronalen Netzen können alle Neuronenfunktionen einer Ebene parallel berechnet werden.

Training

Bei Entscheidungsbäumen (Monobäumen) ist nur bei der Datenanalyse eine Parallelisierung möglich. Aber es gibt auch Multibäume (Random Forest). Diese können parallel erzeugt werden (mit gemeinsamer Datenanalyse).
Bei neuronalen Netzen ist Parallelisierung auf die Matrixalgebra anwendbar.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Berechnungskomplexität

Inferenz

Bei Entscheidungsbäumen hängt die Berechnungskomplexität nur noch von der Höhe des Baums (Anzahl der Ebenen) ab → Selektiv aktivierbare Teilberechnung (trivial, Berechnung einfacher Ausdrücke).
Bei neuronalen Netzen müssen i.A. alle Funktionen berechntet werden (Komplexität ist noch klein) und die Berechnung muss Datenabhängigkeiten beachten.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Training

Bei Entscheidungsbäumen müssen die Datenspalten vs. Parititionierung der Zielvariablen analysiert werden (also Rechenzeit ∝ |D||X|).
Bei neuronalen Netzen findet zunächst eine vollständig Berechnung aller Neuronenfunktionen statt (für alle Datensätze also Rechenzeit ∝ |D||NN|) und anschliessend werden alle Gewichte mit Fehlerfunktionen neu berechnet!
|D|: Anzahl der Dateninstanzen, |X|: Anzahl der Eingabevariablen, |NN|: Anzahl der Neuronen im KNN

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Approximation

• Tatsächlich ist jede Berechnung mit einem Digitalrechner eine Approximation!
  • Reelle Zahlen können nicht mit Digitalrechnern verarbeitet werden
  • Digitalrechner können nur ganze Zahle verarbeiten
  • Fliesskommaarithmetik ist tatsächlich Granzzahlrechnung mit einem "verschobenen" Komma

• Unterschiedliche Datentypen und Rechenwerke benötigen unterschiedlichen Speicherbedarf
  • Daten: Float64 → 64 Bit / 8 Byte,
    Rechenwerk (ALU): > 1M Logikgatter
  • Daten: Int16 → 16 Bit / 2 Byte,
    Rechenwerk (ALU): ≈ 10k Logikgatter

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

• Bei der Rechenzeit / Operation gab es früher großen Unterschied t_op(Float) ≫ t_op(Integer), heute gilt in modernen CPUs aber t_op(Float) ≈ t_op(Integer)

• Bei der Berechnung, z.B. Matrixalgebra, spielt aber in heutigen Rechnerarchitekturen der Datenfluss die Hauptrolle → Speicherzugriff ist langsam!

Parallelisierungsgrad P

Die maximalze Anzahl von binären Stellen (bits) pro Zeiteinheit (Taktzyklus) die von einer Datenverarbeitungsanlage verarbeitet werden kann.

• Es gilt: P = W • B

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Wortlänge W

Die Wortlänge oder Wortbreite gibt die Anzahl der Bits eines Datenpfades an.

Bitslice-Länge B

Die Bitslice-Länge setzt sich zusammen aus der Anzahl von Verarbeitungseinheiten VE, die parallel ausgeführt werden können, und der Anzahl der Pipeline-Stufen einer VE.

• Es gilt: B = N_VE • N_Stages

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Illustration Parallelisierungsgrad und Beispiel

Die Reduktion der Datenwortbreite bei Berechnungen bringt eine Steigerung der Verarbeitungsgeschwindigkeit wenn Datendurchsatz oder Ressourcen limitierende Faktoren sind!

Aber Reduktion der Datenwortbreite bedeutet approximatives Rechnen.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Hochparallele Verarbeitungsarchitekturen

Sze, Hardware for Machine Learning: Challenges and Opportunities

Fein granulierte parallele DV auf Datenpfadebene mit Multi-ALU Architekturen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

MACHINE LEARNING COMPUTE PLATFORMS

Moor I&S, A MACHINE LEARNING APPLICATION LANDSCAPE Metrik der Berechnungsplattformen für ML (CPU, GPU, DSP, FPGA, ASIC)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Generische Prozessoren und Rechner

• Berechnungen finden sequenziell statt:

  • Es gibt i.A. nur eine ALU (Rechenwerk)
  • Parallelität auf Kontrollpfadebene bei Mehrkern- oder Mehrprozessorrechnern möglich
  • Skalierbarkeit im Bereich [1.5,0.8N] bei N ≥ 2 Prozessoren/Kernen

• Wichtig: Mehrkernrechner nutzen einen geteilten Speicher (DRAM). Speicherhierarchie beachten!

  • Der L2/L1 Cache ist wesentlich für die Rechenleistung (Ops/s)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Grafikprozessoren

• Eine GPU entspricht der MIMD Klasse.
  • Aber: GPUs sind keine generischen Rechneranlagen sondern sind auf Grafikoperation (häufig Matrixalgebra) spezialisiert! (Aber: Übergang zu GPGPU Arch.)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

nielshagoort.com/2019/03/12/exploring-the-gpu-architecture/

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Vergleich CPU mit GPU Architektur

CPU sind kontrollpfadorientier, GPU sind datenpfadorientiert

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Digitallogik und FPGA

FPGA: Field Programmable (Logic) Gate Array

Funktionale Systeme können 1:1 unter Ausnutzung maximaler Parallelität auf Digitallogiksysteme abgebildet werden

• Aber Fliesskommarithmetik erfordert großen Ressourcenbedarf (Multi-ALU Architekturen nur begrenzt möglich)

• Daher Übergang auf Ganzzahlarithmetik und Intervallartihmetik (bzw. Festpunktarithmetik)!

• Ein FPGA kann (1) Algorithmen und (2) funktionale Modelle implementieren

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

1. Abbildung von Algorithmen (wie z.B. Gleichungslöser, Regler, FFT, usw.) ermöglicht beschleunigte Berechnung des Algorithmus → Lernalgrotihmen werden i.A. nicht auf FPGAs übertragen!

2. Abbildung von Funktionsmodellen hier das ANN und deren Berechnung (Vorwärtspropagation) auf FPGA

   • Problem: Training mit Backpropagation außerhalb i.A. mit CPU
   • Daher besser Übertragung eines in Software trainierten Modells auf die Hardware (d.h. nur für Inferenz)
   • Aber: Ein mit "Float64" trainiertes Modell muss auf Ganzzahlarithmetik "Int16" transformiert werden und kann u.U. schlechte Ergebnisse ergeben!
   • Daher schon Training mit Zieldatenformat und Einführung von speziellen approximativen Berechnungen (d.h. Übersetzung)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Generische KNN-FPGA Architekturen

• Bisher sind die Implementierungen von KNN in FPGA problemspezifisch

• Generische Architekturen wären problemspezifisch konfigurierbar

• Dazu müssen die Elementaroperationen und Verbindungselemente eines KNN in einem FPGA frei konfigurierbar implementiert werden

• Ein spezifisches KNN wird dann im FPGA durch Verbindung und Konfiguration der Elementarblöcke individuell angepasst

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Hao, A General Neural Network Hardware Architecture on FPGA Die FPGA Blöcke bilden Elementaroperationen von KNN ab

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul I: Rechnerarchitekturen für ML

Zusammenfassung

Jawandhiya, HARDWARE DESIGN FOR MACHINE LEARNING Taxonomie der Hardwarearchitekturen für KNN: Fexibilität vs. Effizienz