Verteilte und Parallele Programmierung

PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-07-15

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:

figkevesm

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.

figsisd

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

figneumann

Abb. 1. Von-Neumann Architekturbild

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.

figharvard

SIMD-Architektur

  • Parallelität auf Datenebene
  • Ablaufsteuerung mit einer gemeinsamen Kontrolleinheit KE
  • Zentrales Speichermodell, aber jede Verarbeitungseinheit VE kann eigenen Speicher besitzen
  • Jede VE bearbeitet gleiche Instruktion Datenoperation wird auf N VEs verteilt
  • Gleiche Operation kann auf verschiedenen Operanden oder einem Operanden der Datenbreite W=N•W’ ausgeführt werden
  • Keine Programmsynchronisation erforderlich

figsimd

SIMD-Architektur

Vektor- & Array-Struktur

  • Sind Subarchitekturen von SIMD

  • Die Programmierung der SIMD-Architektur hängt von der verwendeten Subarchitektur ab.

Vektorarchitektur

Die Verarbeitungseinheiten VE sind linear als Vektorstruktur angeordnet. Jede VE verfügt über eigenen Speicher. Die einzelnen VEs sind mit ihrem jeweiligen linken und rechten Nachbarn verknüpft, und können über diese Verbindungen Daten austauschen.

Arrayarchitektur

Die Verarbeitungseinheiten VE sind als zweidimensionale Matrixstruktur verknüpft. Jede VE besitzt Kommunikationsverknüpfungen mit bis zu maximal vier Nachbareinheiten, so dass Zeilen und Spaltenverbindungen bestehen.

SIMD-Architektur

  • Beide SIMD-Architekturen sind Spezialmaschinen.

  • Sie sind gut geeignet für Algorithmen auf regulären Datenstrukturen, bei denen die gleiche Operation auf eine Vielzahl von Operanden angewendet werden soll.

    • Numerische Matrixoperationen wie Matrix- und Vektormultiplikation
    • Digitale Bildverabeitung mit zweidimensionalen Bildmatrizen

SIMD-Architektur

figvektor

Abb. 2. Vektorrechner

SIMD-Architektur

figmatrix

Abb. 3. Matrixrechner

MISD-Architektur

  • Diese Architektur verarbeitet mehrere Instruktionen parallel. Jede VE hat eigenen IS.
  • Alle Instruktionen operieren auf dem gleichen Datensatz oder über einen Datenstrom.
  • Pipeline-Computer (Instruktions-Pipeline in der CPU) gehören zur MISD-Klasse
  • Spezialmaschine;
    • Anwendung in der digitalen Bildverarbeitung und der Robotik Anwendung.
    • Z.B. Objektklassifikator: Das gleiche Video-Bild (oder Ausschnitt) wird auf verschiedene Algorithmen angewendet (Objektklassifikation).
    • Z.B. Space Shuttle flight control computer!

MISD-Architektur

figmisd

Abb. 4. MISD-Architekturaufbau; Der Hauptspeicher kann segmentiert sein (wie bei Harvard)

MIMD-Architektur

  • Jede VE arbeitet mit eigenen Instruktionsstrom.
  • Jede VE arbeitet mit eigenen Datenstrom.
  • Synchronisation zwischen den einzelnen VE ist erforderlich.
  • Synchronisationsobjekte sind von allen VEs geteilte Ressourcen.

figmimd

Speichermodelle

Exklusives Lesen (ER - ExclusiveRead)
Pro Zyklus kann höchstens ein Prozessor dieselbe Speicherzelle lesen.
Exklusives Schreiben (EW - ExclusiveWrite)
Pro Zyklus kann höchstens ein Prozessor dieselbe Speicherzelle beschreiben.
Konkurrierendes Lesen (CR - Concurrent Read)
Pro Zyklus können mehrere Prozessoren dieselbe Speicherzelle lesen.
Konkurrierendes Schreiben (CW - Concurrent Write)
Pro Zyklus können mehrere Prozessoren dieselbe Speicherzelle beschreiben. Es besteht Konfliktgefahr und Dateninkonsistenz, die mit verschiedenen Methoden gelöst werden können:
  • Common (C-CW) Gleichzeitige Schreibzugriffe auf dieselbe Speicherzelle sind nur erlaubt, wenn alle Schreibzugriffe den gleichen Datenwert liefern.
  • Arbitrary (A-CW) Einer der schreibenden Prozessoren gewinnt und belegt die Speicherzelle - Schutzmechanismus einer geteilten Ressource (Mutual Exclusion). Die anderen Schreibzugriffe werden ignoriert!
  • Priority (P-CW) Auswahl des Prozessors nach Prioritätengewichtung (z.B. Prozessorindex).

Rechnerarchitektur für Vision-Systeme (I)

Gitternetzwerk

  • Über Maschennetz verbundene Prozessoren/Rechner
  • Reguläre zweidimensionale Verbindungsstruktur mit großer Anzahl von Verarbeitungseinheiten (VE) quadratisch angeordnet.
    • Häufig ist jede VE mit seinen direkten Nachbarn (4) verknüpft.
    • Jede VE besitzt i.A. lokalen Speicher.
  • Zweidimensionale Datenstrukturen wie Bilder lassen sich einfach auf diese Struktur abbilden.
  • Maximale Parallelität nur erreichbar bei Algorithmen und Operationen auf Pixel-Ebene, d.h. bei kurzer ”Berechnungslänge”.
  • Kommunikation in Netzen ist über weite Distanzen teuer (Zeit).
  • Algorithmen wie Gruppierung oder Mustererkennung erfordern langreichweitige Berechnungen. Führt zu hohem Kommunikationsüberhang zwischen den VEs.

Rechnerarchitektur für Vision-Systeme (I)

figvisiongitter

Rechnerarchitektur für Vision-Systeme (II)

Pyramidennetzwerk

  • Irreguläre dreidimensionale Verbindungsstruktur mit großer Anzahl von Verarbeitungseinheiten (VE), mehrstufig in (quadratischen) Ebenen angeordnet.
    • Jede VE ist mit seinen (4) direkten Nachbarn auf gleicher Ebene,
    • jeweils mit (4) VEs der unteren Ebene und (1) der oberen Ebene verknüpft (Σ=9).
    • Eine Pyramide besitzt 1/2log(N+1) Ebenen bei N VEs.
  • Gut geeignet für Divide-and-Conquer-Verfahren, wo ein Problem immer weiter mit einem Teilungsfaktor 2 zerlegt wird.
  • Nachteil: hoher Verbindungsaufwand (Netzwerk).
  • Auf verschiedenen Ebenen können Bilder mit unterschiedlicher Auflösung/Matrixgröße parallel verarbeitet werden.

Rechnerarchitektur für Vision-Systeme (II)

figvisionpyra

Rechnerarchitektur für Vision-Systeme - Netra

NETRA ist ein rekursiv definierter und hierarchischer Multiprozessor speziell für Vision-Systeme entwickelt.

DSP (Distributing-and-Scheduling-Processors)
Taskverteilung und Kontrolleinheiten. Erlauben dynamische Partitionierung (zeitlich- wie

räumlich) von Programmcode auf Verarbeitungseinheiten.

PE (Processing Element)

Verarbeitungseinheiten. Organisiert in Clustern der Größe 16-64 PEs. Bis 150 Cluster können gebildet werden. Jedes PE ist ein generischer High-Perfomance-Prozessor mit schneller FPU (Floating-Point-Unit).

C (Cluster)

Bindung von PEs zu einer Einheit. Jeder Cluster teilt sich einen gemeinsamen Datenspeicher. Dieser Speicher ist in einer Pipeline angeordnet. Alle PEs können über einen Kreuzmatrixschalter C mit den Datenspeichern M verbunden werden; die DSPs sind auch über C mit den PEs verknüpfbar.

Rechnerarchitektur für Vision-Systeme - Netra

IC (Interconnect)

Globale Verbindungsmatrix die die Cluster mit Speichermodulen M verbindet. Aufgebaut als vollständiges unidirektionales Verbindungsnetz M×N mit einer Kreuzschaltermatrix. Vollständiges Verbindungsnetz benötigt keine Synchronisation (Mutex/Arbiter).

M

Speichermodul welches parallelen und geteilten Zugriff unterstützt. Die Speichermodule M sind in einer Pipeline angeordnet. Die Zugriffszeit eines Moduls sei T Taktzyklen. Jede Pipeline besteht aus T Speichermodulen. Die Speicher-Pipeline kann daher einen Speicherzugriff pro Taktzyklus durchführen!

Rechnerarchitektur für Vision-Systeme - Netra

Systemarchitektur

fignetrasys

Rechnerarchitektur für Vision-Systeme - Netra

Prozessorcluster

fignetrapro

Kommunikationsstrukturen

  • Ein Verbindungsnetz (Netzwerk) ist das Medium, über das die Kommunikation der Verarbeitungs- und Kontrolleinheiten VE&KE (Prozessoren) untereinander und der Zugriff auf gemeinsame Ressourcen wie Hauptspeicher stattfindet.

figverbnetz

Abb. 5. Verbinungsnetz der Parallel Random Access Machine (PRAM)

Kommunikationsstrukturen

Metriken

Komplexität

Hardware-Aufwand für das Verbindungsnetz gemessen an der Anzahl und Art der Schaltelemente und Verbindungen.

Verbindungsgrad

Der Verbindungsgrad eines Kommunikationsknoten beschreibt die Anzahl der Verbindungen, die von dem Knoten zu anderen Knoten bestehen.

Geometrische Ausdehnung

Maximale Distanz für die Kommunikation (Anzahl der Knoten oder Schaltelemente) zwischen zwei Kommunikationsteilnehmern (VE/KE) [maximale Pfadlänge].

Regelmäßigkeit

Regelmäßige Strukturen in der Verbindungsmatrix lassen sich i.A. einfacher implementieren und modellieren (simulieren).

Erweiterbarkeit

Dynamische oder statische Anpassung an Veränderung der Parallelarchitektur.

Kommunikationsstrukturen

Latenz, Durchsatz/Übertragungsbandbreite

Maximale, meist theoretisch errechnete Übertragungsleistung des Verbindungsnetzes oder einzelner Verbindungen in [MBits/s]

Skalierbarkeit

Fähigkeit eines Verbindungsnetzes, bei steigender Erhöhung der Knotenzahl die wesentlichen Eigenschaften beizubehalten, wie z.B. den Datendurchsatz oder die Kommunikationslatenz.

Blockierung

Ein Verbindungsnetz heißt blockierungsfrei, falls jede gewünschte Verbindung zwischen zwei Kommunikationsteilnehmern (inklusive Speicher) unabhängig von bestehenden Verbindungen hergestellt werden kann.

Ausfalltoleranz oder Redundanz

Möglichkeit, Verbindungen zwischen einzelnen Knoten selbst dann noch zu schalten, wenn einzelne Elemente des Netzes (Schaltelemente, Leitungen) ausfallen.

  • Ein fehlertolerantes Netz muss also zwischen jedem Paar von Knoten mindestens einen zweiten, redundanten Weg bereitstellen.

Kommunikationsstrukturen

Komplexität der Wegfindung
Art und Weise, wie zwischen einem Kommunikationsstart- und endpunkt eine Nachricht vom Sender zum Zielknoten bestimmt wird: Routing. Die Wegfindung sollte einfach sein, und mittels eines schnellen Hardware- Algorithmus in jedem Verbindungselement implementierbar sein.

Kommunikationsstrukturen

Kommunikationsklassen

Durchschalte-oder Leitungsvermittlung
Direkte Verbindung zwischen Sender und Empfänger wird für die Zeit der Informationübertragung hergestellt.
  • Durchschaltnetze erreichen i.A. höhrer Durchsatzraten als Netze mit Paketvermittlung, aber Dauerverbindung reduziert u.U. Anzahl der möglichen Verbindungen.
Paketvermittlung
Daten werden in Nachrichten (Paketen) gekapselt, i.A. mit fester Länge, und vom Sender an der Empfänger übertragen. Eine Datenkodierung und -dekodierung ist notwendig. Weiterhin ist i.A. eine Datenfragmentierung und -defragmentierung erforderlich. Die Nachrichten werden vom Sender zum Empfänger entsprechend einem Wegfindealgorithmus zwischen einzelnen Knoten geroutet.
  • Erhöhter Verwaltungsaufwand im Vergleich zu Durchschaltenetzen.

Kommunikationsstrukturen

figkommklassen

Abb. 6. Kommunikationsklassen: Schalt- zu Paketvermittlung

Kommunikationsstrukturen

Vorteile der Schaltnetze

  • Keine Protokollimplementierung für den Nachrichtenaustausch erforderlich.

  • Die maximale Übertragungsbandbreite (Durchsatz) eines Kommunikationskanals kann erreicht werden.

Nachteile der Schaltnetze

  • Jeder Knoten muss mit N:1-Multiplexern ausgestattet werden.

  • Eine universelle N ⊗ N - Schaltmatrix (jeder Kommunikationsteilnehmer Ni kann mit jedem anderen Teilnehmer Nj mit i ≠ j verbunden werden) erfordert großen Hardware-

  • Aufwand, und ist bei großen N nicht mehr wirtschaftlich. Synchronisation muss explizit erfolgen.

Kommunikationsstrukturen

Vorteile der Paketvermittlung und Nachrichtenaustausch

  • Über einen Kommunikationskanal können Verbindungen zwischen verschiedenen Kommunikationsteilnehmern aufgebaut werden.

  • Auch komplexe Netze können mit geringen Hardware-Aufwand (Routing) realisiert werden.

  • Implizite Synchronisation bereits vorhanden.

Nachteile der Paketvermittlung und Nachrichtenaustausch

  • Implementierung eines Protokollstacks mit Datenfrag- und defragmentierung und Routing.

  • Geringerer Netto-Datendurchsatz durch Header- und Trailerdaten im Nachrichtenpaket.

  • Höhere Übertragungslatenz durch Paketadministration und Routing.

Beispiel: Eine Implementierung eines IP-Protokollstacks mit Digitallogik benötigt ca. 1M Gates (ca. 4 Millionen Transistoren)!

Netzwerkarchitekturen und Topologien

Ein Netzwerk besteht aus Knoten N={n1,n2,…} und Verbindungen (Kanten) C={c1,c2,..}, die die Knoten untereinander verbinden. Das Netzwerk kann als ein Graph G(N,C) beschrieben werden, der i. A. zyklisch und gerichtet ist.

Parameter und Metriken von Netzwerken

Knotenzahl N
Gesamtzahl der Knoten, die ein Netzwerk oder ein Subnetzwerk bilden
Knotengrad (Konnektivität) K
Jeder Knoten hat mindestens eine, maximal K Verbindungen zu Nachbarknoten
Skalierbarkeit
Lässt sich das Netzwerk für belibiege Anzahl N von Knoten erweitern?
Routing
Strategie für die Weiterleitung und Zustellung von Daten von einem Senderknoten ns zu einem oder mehreren Empfängerknoten {ne1,ne2,…}

Netzwerkarchitekturen und Topologien

  • Unicast: nur ein Empfänger
  • Multicast: eine Gruppe von ausgezeichneten Empfängern
  • Broadcast: alle Knoten (in einem Bereich) sind Empfänger
Ausdehnung D
Maximaler Abstand (Distanz) zwischen zwei Knoten
Kosten O
Anzahl der Kanten NC
Effizienz η
Anzahl der Kanten NC im Verhältnis zur Anzahl der Knoten N
Latenz τ
Verzögerung τ bei der Zustellung von Daten durch Vermittlung (normiert und vereinfacht in Anzahl von Zwischenknoten)
Durchsatz B
Datendurchsatz (Bandbreite)

Netzwerkarchitekturen und Topologien

  • In nachrichtenbasierten Vermittlungsnetzwerken ist ein Knoten eines Netzwerkes:
  1. Quelle von Nachrichten, die Daten kapseln,
  2. Empfänger von Nachrichten, und
  3. Vermittler (Router) von Nachrichten (Zwischenknoten)
  • In einem geschalteten Netzwerk mit direkter Datenvermittlung ist ein Knoten eines Netzwerkes
  1. Quelle von Daten, und
  2. Empfänger von Daten

Dynamische Verbindungsnetzwerke

  • Direkte Schaltung von Verbindungen ermöglicht die Übertragung von einem Sender- zu einem Empfängerknoten.

Crossbar Switch

figcrossbar

Abb. 7. Vollständiger Kreuzschalter (Crossbar Switch) mit Schaltelementen [PA, Vornberger,1998]; Hier Verbindung Prozessor P mit Speichermodul M

Dynamische Verbindungsnetzwerke

Parameter

  • Knotenzahl: N
  • Knotengrad: 1
  • Skalierbar: Ja
  • Routing: Nicht erforderlich - konfliktfrei
  • Ausdehnung: 1
  • Kosten: N2

Vorteile

  • Jeder Knoten kann mit jedem anderen Knoten jederzeit verbunden (geschaltet) werden → Dynamische Konnektivität des Netzwerkes
  • Ausdehnung optimal klein (und Latenz minimal)
  • Keine Nachrichtenkapselung und kein Kommunikationsprotokoll erforderlich
  • Skalierung bezüglich Leistung ist gut

Dynamische Verbindungsnetzwerke

Nachteile

  • Hohe Kosten und hoher Hardware-Aufwand, der quadratisch mit der Anzahl der Knoten wächst
  • Skalierung bezüglich Kosten ist schlecht
  • Fehlende Synchronisation zwischen Sender und Empfänger

Mehrstufen (Multistage) Verbindungsnetzwerke

  • Mehrstufiger Aufbau des Netzwerkes
  • Kompromiss bezüglich Skalierung zwischen Kreuzschaltern und Bussystemen

Parameter

  • Knotenzahl: N
  • Knotengrad: 1
  • Skalierbar: Ja
  • Routing: Nicht erforderlich - aber nicht konfliktfrei!
  • Ausdehnung: 1 (oder n - Stufenzahl)
  • Kosten: Nlog2N

Dynamische Verbindungsnetzwerke

figmultistage

Abb. 8. Aufbau eines Mehrstufen Netzwerks (n-stufig) [PA, Vornberger, 1998]

Dynamische Verbindungsnetzwerke

Mehrstufiges Permutations-Netzwerk

  • Jede Stufe besteht aus Binärschaltern, die entweder durchgeschaltet oder gekreuzt geschaltet sind.
  • Die Ausgänge einer Stufe k werden über ein Permutationsverfahren mit den Eingängen der nächsten Stufe k+1 verbunden.

figpermsw

Abb. 9. Nicht konfliktfreies Mehrstufennetzwerk [PA, Vornberger, 1998]

Dynamische Verbindungsnetzwerke

Bus

  • Alle Knoten nutzen eine gemeinsame Kommunikationsverbindung
  • Bus-basierte Netzwerke skalieren bezüglich Kosten gut, aber nicht bezüglich der Leistung (Flaschenhals!)

figbus

Abb. 10. Topologie des Bus-basierten Netzwerkes

Dynamische Verbindungsnetzwerke

Parameter

  • Knotenzahl: N
  • Knotengrad: 1
  • Skalierbar: Jein
  • Routing: Nicht erforderlich - aber nicht konfliktfrei
  • Ausdehnung: 1
  • Kosten: 1

Dynamische Verbindungsnetzwerke

Bus Arbiter und Architektur

figbusarb

Protokoll

LISTEN
Aktueller Eigentümer des Busses (ACK=1) sendet eine Listen Nachricht an alle Teilnehmer. Nachfolgend wird nur der adressierte Teilnehmer Daten empfangen.
TALK
Der aktuelle Eigentümer des Busses gibt seine Adresse bekannt.
UNLISTEN
Alle Teilnehmer warten auf Kontrollkommandos
UNTALK
Kein Teilnehmer ist Datensender.

Dynamische Verbindungsnetzwerke

figdynnetcomp

Abb. 11. Skalierung von Kosten und Leistung der verschiedenen dyn. Verbindungsnetze in Abhängigkeit der Knotenzahl N [PA, Vornberger, 1998]

Statische Verbindungsnetzwerke

  • Nachrichtenbasierte Kommunikation, d.h. die zu übertragenen Daten werden in Nachrichten gekapselt

  • In den meisten Topologien ist die Vermittlung von Nachrichten durch andere Knoten entlang eines Pfades (S→ni1→ni2→…→E) erforderlich

figstarmesh

Abb. 12. Zwei Grenzfälle: Vollständig verbundenes Maschennetzwerk und Sternnetzwerk

Statische Verbindungsnetzwerke

Sternnetzwerk

  • Master-Slave Netzwerk Hierarchie
  • Ein ausgezeichneter Knoten ist Master, der mit jedem anderen Knoten (Slave) verbunden ist
  • Kommunikation findet immer über den Master (=Router) statt

Parameter

  • Knotenzahl: N
  • Knotengrad: 1 (Slave), N-1 (Master)
  • Skalierbar: Ja
  • Routing: erforderlich - wähle Ziel in zwei Schritten über Master
  • Ausdehnung: 2
  • Geschlossen: nein
  • Kosten: N-1

Statische Verbindungsnetzwerke

Binärer Baum

Parameter

  • Knotenzahl: N
  • Knotengrad: 3
  • Skalierbar: Ja
  • Routing: erforderlich - laufe vom Start aufwärts zum gemeinsamen Vorfahren und dann abwärts zum Ziel
  • Ausdehnung: 2*k (k - Höhe des Baums)
  • Geschlossen: nein
  • Kosten: Nlog2N

Statische Verbindungsnetzwerke

figtree

Abb. 13. Topologie Binärbaum (a) und N-Baum (b) Netzwerk [PA, Vornberger, 1998]

Statische Verbindungsnetzwerke

Lineares Array - Kette - und Ring

Parameter

  • Knotenzahl: N
  • Knotengrad: 2
  • Skalierbar: Ja
  • Routing: erforderlich - wähle Richtung und laufe in diese Richtung
  • Ausdehnung: N-1 (Kette), N/2 (Ring)
  • Geschlossen: nein (Kette), ja (Ring)
  • Kosten: N-1 (Kette), N (Ring)

figchain

Abb. 14. Kette und Ring (technologisch schwierig) [PA, Vornberger, 1998]

Statische Verbindungsnetzwerke

2D Gitter

  • ökonomisch und techn. geeignet für material-integrierte verdrahtete Sensornetzwerke (elektrische und optische Kommunikationstechnologien)

Parameter

  • Knotenzahl: N
  • Knotengrad: 4
  • Skalierbar: Ja
  • Routing: erforderlich (Δ-Distanz Routing)
  • Ausdehnung: 2*(√N-1)(ohne wraparound), 1+(√N-1) (mit wraparound)
  • Geschlossen: nein (ohne wraparound), ja (mit wraparound)
  • Kosten: 2(N-√N) (ohne wraparound)

Statische Verbindungsnetzwerke

fig2dnet

Abb. 15. 2D Gitter und Torus (technologisch schwierig) [PA, Vornberger, 1998]

Statische Verbindungsnetzwerke

Δ-Distanz Routing

  • Routing: Wandere horizontal (erste Dimension) bis zur Zielspalte, dann wandere vertikal bis zur Zielzeile (zweite Dimension)

  • Einfaches Δ-Distanz Routing in m-dimensionalen Gitternetzwerken:

    • M: Nachricht
    • moveto: vermittelt Nachricht an Nachbarknoten in Richtung DIR
    • Δ0: relative Distanz zwischen Sender und Empfänger in Knoteneinheiten
    • Δ: bei jeder Vermittlung geänderter Vektor, anfänglich Δ0=Δ, am Ziel: Δ=(0,0,..)
    • Δi: i-te Komponente von Δ
    • Nullvektor 0=(0,0,..) → Ziel erreicht!

Statische Verbindungsnetzwerke

Algorithm 1. (Δ Routing)

\[\begin{mdmathpre}%mdk \mathkw{TYPE}~\mathid{DIM}~=~\{1,2,...,\mathid{m}\}~\\ \mathkw{TYPE}~\mathid{DIR}~=~\{\mathid{NORTH},\mathid{SOUTH},\mathid{EAST},\mathid{WEST},\mathid{UP},\mathid{DOWN},...\}\\ //~\mathid{Numerical}~\mathid{mapping}~\mathid{of}~\mathid{directions}\\ \mathkw{DEF}~\mathid{dir}~=~\mathkw{function}(\mathid{i})~→~\\ \mdmathindent{2}\mathkw{match}~\mathid{i}~\mathkw{with}\\ \mdmathindent{2}-2~\rightarrow \mathid{NORTH}~|~-1~\rightarrow \mathid{WEST}~|~1~\rightarrow \mathid{EAST}~|~2~\rightarrow \mathid{SOUTH}~...\\ //~\mathid{Routing}~\mathid{and}~\mathid{message}~\mathid{passing}\\ \mathkw{DEF}~\mathid{route}_\mathid{xy}~=~\mathkw{function}~(Δ,Δ0,\mathid{M})~→\\ \mdmathindent{2}\mathkw{if}~Δ~≠~0~\mathkw{then}\\ \mdmathindent{4}\mathkw{for}~\mathid{first}~\mathid{i}~∈~\mathid{DIM}~\mathkw{with}~Δ\mathid{i}~≠~0~\mathkw{do}\\ \mdmathindent{6}\mathkw{if}~Δ\mathid{i}~>~0~\mathkw{then}\\ \mdmathindent{8}\mathid{moveto}(\mathid{dir}(\mathid{i}));~\\ \mdmathindent{8}\mathid{route}_\mathid{xy}(Δ~\mathid{with}~Δ\mathid{i}:=Δ\mathid{i}-1,Δ0,\mathid{M})\\ \mdmathindent{6}\mathkw{elseif}~Δ\mathid{i}~<~0~\mathkw{then}\\ \mdmathindent{8}\mathid{moveto}(\mathid{dir}(-\mathid{i}));~\\ \mdmathindent{8}\mathid{route}_\mathid{xy}(Δ~\mathid{with}~Δ\mathid{i}:=Δ\mathid{i}+1,Δ0,\mathid{M})\\ \mdmathindent{2}\mathkw{else}~\mathid{deliver}(\mathid{M}) \end{mdmathpre}%mdk \]

Statische Verbindungsnetzwerke

3D Gitter

  • ökonomisch und techn. geeignet für material-integrierte verdrahtete Sensornetzwerke

Parameter

  • Knotenzahl: N
  • Knotengrad: 6
  • Skalierbar: Ja
  • Routing: erforderlich (Δ-Distanz Routing)
  • Ausdehnung: 3*(√3N-1)
  • Kosten: 3(N-√3N)

fig3dnet

Statische Verbindungsnetzwerke

Zusammenfassung Gitternetzwerke

figxnet

Kommunikationsstrukturen - Routing

Routing: Flusssteuerung bei nachrichtengekoppelten Netzen

Store-and-forward

  • Nachricht wird von jedem Zwischenknoten in Empfang genommen

  • Nachricht wird vollständig zwischengespeichert

  • Sendung der Nachricht auf Pfad zum nächsten Knoten nach vollständigen Empfang

Virtual-cut-through

  • Nachricht wird als Kette von Übertragungseinheiten transportiert

  • Kopfteil der Nachricht enthält die Empfängeradresse und bestimmt den Weg

  • Bei Ankunft der ersten Übertragungseinheit wird diese sofort an den nächsten Knoten weitergeleitet (Pipeline-Verfahren)

  • Nachrichtenspeicherung nur im Konfliktfall (wenn Pfad belegt ist)

Kommunikationsstrukturen - Routing

Wormhole-routing

  • Ist der Pfad zum nächsten Knoten nicht belegt, Verhalten wie Cut-through

  • Ist Kommunikationskanal belegt, müssen alle vorherigen Knoten ebenfalls Datentransfer einstellen, d.h. die Vorgänger-Knoten werden blockiert.

  • D.h. keine Nachrichtenspeicherung in den Verbindungsknoten

  • Es werden nur Puffer für eine Übertragungseinheit benötigt (Kopf).

Kommunikationsstrukturen - Routing

figrouting

Abb. 16. Vergleich S&T und VC Routing: Das Cut-through Routing benötigt deutlich weniger Kommunikationsschritte als das Store-and-Foreward Routing-Verfahren.

Kommunikation

Paketstruktur

figpaket

Abb. 17. Aufbau eines Nachrichtenpakets: Header (Zustell- und Absendeinfomationen, Overhead), Nutzdaten (Datenlast), und optional Trailer (Prüfsumme, EOP Marker, .., Overhead)

Latenz

Die Zeit zum Übertragen einer Nachricht zwischen zwei Netzwerkknoten mit N Byte setzt sich zusammen aus:

\[T{(N)_{S \to D}} = {T_{overhead}} + {T_{routing}} + {T_{transfer}} + {T_{conflict}} \]

Kommunikation

Toverhead → Θ(1)
Zeit die benötigt wird, ein Paket vom Speicher in den Kommunikationskanal und aus dem Kanal in den Speicher zu übertragen → abhängig von Hardware
Ttransfer → Θ(N)
Zeit die zur eigentlichen Datenübertragung benötigt wird.
Tconflict
Mittlere Zeit in der ein Kommunikationskanal blockiert ist. Abhängig von Auslastung des Kanals.
  • Die Transferzeit von N Byte Nutzdaten erhöht sich durch die Paketadministration (Header & Trailer) NPA und ergibt sich aus der Bandbreite B [Byte/s] des Kommunikationskanals:
\[{T_{transfer}} = \frac{{N + {N_{PA}}}}{B} \]

Kommunikation

  • Die Routingzeit (Latenz) hängt vom verwendeten Routing-Verfahren ab:
\[\begin{gathered} {T_{routing - SF}}(N,H) = H\left( {\frac{{{N_{paket}}}}{B} + \Delta } \right) \hfill \\ {T_{routing - CS}}(N,H) = \frac{{{N_{paket}}}}{B} + H\Delta \hfill \\ \end{gathered} \]
  • Dabei ist H die Anzahl von Knoten, die ein Paket auf seiner Route durchlaufen muss.
  • Ein Hardwareoverhead beim Senden und Empfangen eines Knotens wird mit Δ gekennzeichnet.

Es gilt:

\[{T_{routing - CS}}(N,H) < {T_{routing - SF}}(N,H) \]

Kommunikation - Zusammenfassung

Hardware

  • Es gibt zwei wesentliche Architekturklassen die parallele und verteilte Datenverarbeitung sehr stark beeinflusst → Performanz → maximaler / effektiver Speedup:

    • Rechnerarchitektur (Horizontale und vertikale Parallelisierung, Speicher)
    • Kommunikationsarchitektur (Art und Topologie), Ein- und Ausgabegeräte, Konflikte und Blockierung

Software

  • Auf der algorithmischen Seite beeinflussen folgenden Klassen die Performanz, Effizienz, die Rechenzeit, und den Speicherbedarf von parallelen und verteilten Systemen:

    • Partitionierung des Algorithmus in Prozesse
    • Datenabhängigkeiten, Datenverteilung und Datenaggregation
    • Synchronisation → Kommunikation → Nachrichtenaustausch
    • Kommunikations- und Routingprotokolle!

Kommunikation - Zusammenfassung

Kommunikation erhöht den sequenziellen Anteil eines parallelen Programms und reduziert den (max.) Performanzgewinn gegenüber rein sequenziellen Programmen gleicher Art