Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

Prof. Dr. Stefan Bosse

Universität Koblenz - FB Informatik - FG Praktiksche Informatik

1 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung ::

Einführung in die verteilte und parallele Datenverarbeitung

Was unterscheidet verteilte und parallele Datenverarbeitung?

Welche Eigenschaften besitzen verteilte gegenüber parallelen Systemen?

2 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Performanz

  • Wir werden noch Metriken und Maßzahlen für die Bewertung von verteilten und parallelen Systemen und Programmen kennen lernen
  • Startpunkt: Sequenzielle Performanz
    • Rechenzeit
    • Speicherbedarf
  • Messung der sequenziellen Performanz sollte vergleichbar (also normiert) sein bezüglich:
    • Rechnerarchitektur
    • Speicherarchitektur
    • Programmiersprache und ggfs. VM
3 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Benchmarks

  • Es gibt eine Vielzahl von Benchmarks um die Rechenleistung von Rechnern zu bestimmen:
    • Häufig elementare Maschineninstruktionen / Zeiteinheit (GIPS/FIPS)

Aber sind solche Masszahlen für uns hilfreich?

  • Besser Vergleich verschiedener Programmiersprachen und deren VM Leistung
    • Whetstone
    • Dhrystone
4 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Dhrystone

  • Berücksichtigt eine große Menge von Operationen die typischerweise in Programmen vorkommen:
  • Berechnung und Zuweisungsanweisung
  • Verschiedene Datentypen: Skalare, Arrays, Rekords, Objekte (mit Methoden)
  • Statische und dynamische Speicherallokation (in VMs i.a. immer dynamisch!)
  • Funktionen und Funktionsaufrufe
  • Kontrollflusskonstrukte (Schleifen, bedingte Verzweigungen)

https://dl.acm.org/doi/pdf/10.1145/358274.358283 Weicker, R. P. (1984). Dhrystone: a synthetic systems programming benchmark. Communications of the ACM, 27(10), 1013-1030

5 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Weicker, R. P. (1984) Analyse der prozentualen Verteilung von verschiedenen Anweisungen in verschiedenen Programmiersprachen

6 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Führe den Dhrystone Benchmark Test auf verschiedenen Rechnern und verschiedenen VM (und native C Version) aus. VMs: JavaScript, Python, Lua

Ergebnisse:

7 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Rechenzeiten

Rechenzeiten

Die Laufzeit eines Programms setzt sich aus verschiedenen Anteilen zusammen, die je nach Rechnerarchitektur, Betriebssystem und Softwarearchitektur variieren können.

  1. Startzeit der Laufzeitumgebung: native SOL/DLL, Betriebssystem, z.B. Prozess, und ggfs. VM
  2. Startzeit des Programms: Laden des Codes, Speichermanagement, Initialisierung von Daten
  3. Kommunikationszeit Dateneingabe
  4. Ausführung und Berechnung
  5. Bei Parallelisierung: Kommunikation
  6. Kommunikationszeit Datenausgabe
  7. Zeit für Programmterminierung
8 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Terminologie

Terminologie

Prozessor
Eine physische Datenverarbeitungseinheit als Teil einer Maschine die i.A. sequenziell einen Strom aus Anweisungen schrittweise verarbeitet.
Virtuelle Maschine
Ein Programm dass einen Prozessor emuliert.
Programm
Eine Menge aus Anweisungen, die von einem Prozessor oder einer Virtuellen Maschine verarbeitet werden kann. Ein Programm enthält neben Anweisungen auch Daten.
Prozess
Ein Programm in Ausführung mit einem zeitlich veränderlichen Daten- und Kontrollzustand
9 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

Verteiltes System

Ein verteiltes System ist eine System aus lose gekoppelten Prozessoren oder Computern, die über ein Kommunikationsnetzwerk miteinander verbunden sind (Multicomputer).

  • Speichermodell: Verteilter Speicher → Jeder Prozessor verfügt über privaten Speicher
  • Kommunikation: Nachrichtenbasiert über Netzwerke
  • Ressourcen: Nicht direkt geteilt
10 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

Paralleles System

Ein paralleles System ist ein Zusammenführung von stark gekoppelten Prozessoren (Multiprozessoren)

  • Speichermodell: Gemeinsamer geteilter Speicher (Shared Memory)
  • Kommunikation: Prozessoren greifen auf Speicher direkt über elektrische Signale zu → Switched Network (Kreuzschiene) | Bus → Punkt-zu-Punkt | Punkt-zu-N-Netzwerke
  • Ressourcen: Gemeinsam genutzt (Bus, Speicher, IO)

Man unterscheidet: Mehrkern und Mehrprozessor Rechner

11 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

1 Taxonomie von verteilten und parallelen Systemen

12 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilter Speicher

Verteilter Speicher

  • Jeder Prozessor hat eigenen Speicher
  • Netzwerk aus Prozessoren/Maschinen
  • Zugriff auf Speicher erfordert nachrichtenbasierte Netzwerkkommunikation
  • Vorteil: Speicher ist skalierbar mit Anzahl der Prozessoren
  • Nachteil: Langsamer Speicherzugriff zwischen Prozessen

computing.llnl.gov

13 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Geteilter Speicher

Geteilter Speicher

Unified Memory Architecture

  • Symmetrisches Multiprocessing (SMP)
  • Vorteil: Konstante Zugriffszeit auf Speicher
  • Vorteil: Schneller Speicherzugriff zwischen Prozessen

Non Unified Memory Architecture

  • Vorteil: Clustering von SMPs
  • Nachteil: Ungleiche Zugriffszeiten auf Speicher



14 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Speichermodell und Speicherarchitekturen

Speichermodell und Speicherarchitekturen

Das Speichermodell und die Speicherarchitektur einer Rechneranlage bestimmen wesentlich über die Performanz und Skalierbarkeit von paralleler und verteilter Datenverarbeitung!

15 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Speicherhierarchie

Speicherhierarchie

  • Speichersysteme sind in modernen Rechneranlagen mehrstufig aufgebaut.
  • Speicher enthält: 1. Daten 2. Anweisungen (Code)
  • Das Speichersystem S eines Rechners besteht aus einer Pipeline von unterschiedlichen Speichermodulen si mit unterschiedlichen Speichergrößen mi:

S(M)=s1(m1)→s2(m2)→..→sk(mk)

16 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Speicherhierarchie

Warum gibt es ein hierarchisches Speichersystem?

Je größer die Speicherkapazität eines Speichermodules ist, desto langsamer ist der Speicherzugriff. Daher unterschiedliche Ebenen mit unterschiedlichen Größen und Zugriffszeiten (Cachekonzept)

17 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte Systeme

Verteilte Systeme

Entwurfskriterien und Eigenschaften

Namensgebung
Wie können wir ein Objekt benennen, das weit entfernt an einem unbekanntem Ort ist?
Robustheit
Was passiert, wenn eine Maschine oder ein Netzwerk ausfällt?
Sicherheit
Wie können wir unser System vor Versagen, Betrug, Eindringen, Diebstahl von Daten, ... schützen?
18 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte Systeme

Performance
Langsamer als je zuvor?
Konsistenz
Ich mache eine Banktransaktion, die Bestätigung der Transaktion ging verloren, und die Transaktion wurde wiederholt. Mein Konto wurde zweimal belastet? Was passiert bei gleichzeitigen Zugriff?
Skalierbarkeit
Was passiert mit diesen Kriterien, wenn wir die Anzahl der Prozessoren/Maschinen um das Zehnfache erhöhen?
19 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Parallele Systeme

Definition

  • Zerlegung (Partitionierung) eines sequenziellen Algorithmus oder eines Programms in parallele Tasks (Prozesse) → Parallele Komposition

  • Ausführung der Prozesse parallel (nebenläufig und ggfs. konkurrierend) auf mehreren Verarbeitungseinheiten (u. A. generische programmgesteuerte Prozessoren)

20 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Motivation für parallele Datenverarbeitung

  • Verkleinerung der Berechnungslatenz

Def. Latenz: Gesamte oder Teilbearbeitungszeit eines Datensatzes

  • Erhöhung des Datendurchsatzes

Def. Datendurchsatz: Anzahl der verarbeiteten Datensätze pro Zeiteinheit

21 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Parallele Systeme

  • Latenz und Bandbreite sind zunächst unabhängig!

  • Pipelining kann die Bandbreite erhöhen (nur sinnvoll bei Datenströmen), aber nicht die Latenz!

  • Parallele Tasks können die Latenz verringern

Unterschied von Latenz (oben, einzelner Datensatz) zu Bandbreite (unten, Datensatzstrom)

22 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Parallele Systeme

Parallelität und Nebenläufigkeit

  • Parallelität und Nebenläufigkeit ist ein zeitliches Ablaufmodell
  • Beschreibt eine zeitliche Überlappung oder Gleichzeitigkeit bei der Ausführung von parallelen Prozessen
  • Nebenläufigkeit kann ohne Synchronisation auskommen!
  • Häufig mit Konkurrenz verwechselt (English aber richtig: Concurrency==Parallelität, Gelichzeitigkeit)

Konkurrenz

  • Concurrency → übereinstimmend!
  • Konkurrenz beschreibt den Wettbewerb um geteilte Ressourcen!
  • Wettbewerb bedeutet Konflikt welcher aufgelöst werden muss!
  • Synchronisation zw. Prozessen!
  • Konsens Programmiermodell!
23 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

blog.golang.org (Links) Zeitlich überlappende parallele Ausführung von Datenverarbeitung (Rechts) Zeitlich versetzte und synchroniserte Datenverabeitung mit geteilten Ressourcen und Konkurrenz

24 / 38

Stefan Bosse - VPP - Modul A Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme