Verteilte und Parallele Programmierung

Plattformen und Netzwerke

Eigenschaften von Parallelarchitekturen

Rekonfigurierbarkeit

Unterschiedliche Ebenen der Algorithmik erfordern unterschiedliche Rechnerarchitekturen. Sowohl SI and MI-Ausführung muss dynamisch (re-)konfigurierbar möglich sein → Dynamische Anpassung der Architektur an Algorithmen.

Flexible Kommunikation

Fein granulierte und Hochgeschwindigkeitskommunikation ist für effiziente Ausführung der Algorithmen und Tasks erforderlich. Kommunikation zwischen Tasks und den unterschiedlichen Verarbeitungsebenen.

Ressourcen Allokation und Partitionierbarkeit

Gesamtsystem muss aus unabhängigen Teilsystemen bestehen, um effiziente Implementierung der (unterschiedlichen) Tasks zu ermöglichen. Ressourcen (Prozessoren, Speicher) müssen dynamisch und fein granuliert an die Tasks/Prozesse gebunden werden können.

Eigenschaften von Parallelarchitekturen

Lastbalanzierung und Task Scheduling

Besonders für high-level (=komplexe) Algorithmen mit starker Datenabhängigkeit sind Lastverteilung und zeitliches Taskscheduling von großer Bedeutung, aber nicht trivial.

• In low-level Algorithmen mit geringer Datenabhängigkeit erreicht man Lastbalanzierung meistens durch Datenpartitionierung.

Unabhängigkeit von Topologie- und Datengröße

Durch die hohe Komplexität von Algorithmen (z.B. Vision) muss die Architektur unabhängig von detaillierten Annahmen bezüglich Datenstruktur (z.B. Matrixgrößen oder Datenbreite) und bestimmter Algorithmik sein!

• Betrifft auch dynamisch konfigurierbare und skalierbare Kommunikationsstrukturen.

Eigenschaften von Parallelarchitekturen

Fehlertoleranz

Bei der Bearbeitung von komplexen Aufgaben mit komplexen Systemen spielt Fehlertoleranz eine wichtige Rolle. Ein Ausfall einer einzelnen Komponente darf nicht zum Ausfall des gesamten Systems führen. Statische Redundanz ist aber teuer (Ressourcen- bedarf)!

Ein- und Ausgabe (IO)

Neben geringer Bearbeitungs- und Rechenzeit ist der Datentransfer der Eingangs- und Ausgangsdaten (Ergebnisse) gleichbedeutend. Performanz und Architektur von IO ist ein Kernbestandteil paralleler Systeme!

Klassifikation Rechnerarchitektur

- Eine Datenverarbeitungsanlage enthält:

VE

Verarbeitungseinheit für Daten → Generischer Prozessor, Applikationspezifischer Pro- zessor, Applikationspezifische Digitallogik, Teileinheit

SM

Speichermodul → RAM, Registerbank, Cache

KE

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

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

Klassifikation Rechnerarchitektur

Klassifikation nach Flynn

• Durch Beschreibung von Daten- und Kontrollfluss:

SISD

Single-Instruction ⊗ Single-Data Stream

SIMD

Single-Instruction ⊗ Multiple-Data Stream

MISD

Multiple-Instruction ⊗ Single-Data Stream

MIMD

Multiple-Instruction ⊗ Multiple-Data Stream

SISD-Architektur Eigenschaften

• Von-Neuman-Architektur gehört zur SISD- Klasse
• SISD-Architekturen verarbeiten einen sequenziellen Daten- und Kontrollstrom.
• Nur eine VE und KE wird benötigt.
• Ein zentraler Speicher für Daten und Instruktionen
• Keine algorithmische Parallelisierung implementierbar - nur implizit mittels Pipeline- Verfahren.
• Programmiermodell: explizite Ablaufsteuerung; simulierte konkurrierende Programmierung mit Software-Threads.

SISD-Architektur - Von-Neumann Architektur

Phasen der Befehlsausführung

1. Befehlsholphase: ℘(BZ) → BR
2. Dekodierungsphase: BR → {S1,S2,..}
3. Operandenholphase: ℘ → R
4. Befehlsausführung: χ
5. Rückschreibephase: R → ℘
6. Adreßrechnung: Ψ(BZ,SR,BR) → BZ

Architekturkomponenten

BZ, BR, S

Befehlszähler, Befehlsregister, Steuersignale

SR,R,℘

Statusregister, Register, Speicher

A,D

Adress- und Datenbus

SISD-Architektur - Von-Neumann Architektur

SISD-Architektur - Harvard-Architektur

• Getrennte Daten- und Instruktionsspeicher

• Mehrere Datenbusse und Datenspeicher ä Spezialmaschine optimiert für datenintensive Algorithmen

• Parallelisierung auf Instruktionsebene: Teilphasen der Befehlsausführung können nebenläufig ausgeführt wer- den, z.B. Befehls- und Operandenholphase.

SIMD-Architektur