Verteilte und Parallele Programmierung

Das Prozessmodell

Fluss und Pfad

• Ein Datenfluss (Graph aus Operationen oder Variablen) beschreibt den Verlauf und die Verarbeitung von Daten durch Operationen → Verhaltensbeschreibung

• Ein Datenpfad beschreibt die Verbindung von Komponenten zur Implementierung des Datenflusses → Strukturbeschreibung

• Der Kontrollfluss beschreibt die zustandsbasierte Steuerung einer Berechnung

  • Bedingte (↔ Datenfluss) Verzweigungen im Kontrollfluss
  • Schleifen im Kontrollfluss

• Der Kontrollpfad implementiert den Kontrollfluss → Zustandsautomat

Daten- und Kontrollpfade

Jeder generische Mikroprozessor und i.A. jedes anwendungsspezifische Digitallogiksystem läßt sich in die zwei funktionale Bereiche aufteilen:

1. Datenfluss → Datenpfade
2. Kontrollfluss → Kontrollpfad → Zustandsautomat

Datenpfad

• Führt Berechnungen durch
• Kann rein funktional (speicherlos, kombinatorisch) oder speicherbasiert mir Register-Transfer Architektur sein

Kontrollpfad

• Der Kontrollpfad ist immer zustandsbasiert (Speicher) und bestimmt die Reihenfolge von Operationen und Berechnungen

Daten- und Kontrollpfade

Parallelisierung

Der Programmfluss kann in Daten- und Kontrollfluss zerlegt werden, die jeweils im Daten- und Kontrollpfad eines Datenverarbeitungssystems verarbeitet werden.

Kontrollpfad

Parallelität auf Prozessebene (Multithreading) mit Interprozesskommunikation → Mittlere bis geringe Beschleunigung, mittlerer Overhead

Datenpfad

Parallelität auf Dateninstruktionsebene ohne explizite Kommunikation → Hohe Beschleunigung, geringer Overhead

Daten- und Kontrollpfade

Zustandsautomat

• Der Zustandsautomat ist für die sequenzielle Ablaufsteuerung zuständig:
  1. Der Zustandsautomat steuert den Datenfluss im Datenpfad;
  2. Er ist für die Ein- und Ausgabesteuerung zuständig,
  3. Implementierung von Handshake-Protokollen für den Datenaustausch mit anderen Systemblöcken (auch IPC), und
  4. Er behandelt Ausnahmesignale und Fehler.

Daten- und Kontrollpfade

Programm

• Ein (prozedurales/imperatives) Programm besteht aus mindestens einem Daten- und Kontrollpfad (oder Fluss)

• Ein Programm ist aus einer Vielzahl von Komponenten zusammengesetzt → Komposition

• Komposition von Datenfluss und Datenpfad:

  • Funktionale Komposition
  • Parallele Komposition

• Komposition von Daten- und Kontrollfluss/pfad:

  • Sequenzielle Komposition
  • Parallele Komposition

Daten- und Kontrollpfade

Basisblöcke und Parallelisierung

Datenflussgraph (DFG)

• Der DFG beschreibt Datenabängigkeiten zwischen einzelnen Berechnungen
• Ein DFG besteht i.A. aus einer Menge von einzelnen DFGs
• Unabhängige DFGs bzw. Teilgraphen können parallel berechnet werden