Kapitel 3.0 - 3.2

Michael J. Flynn charakterisiert Rechner als Operatoren auf zwei verschiedenartigen Informationsströmen: dem Befehlsstrom (bzw. den Befehlsströmen) und dem Datenstrom (bzw. den Datenströmen).

• SISD: Single Instruction stream over a Single Data stream von-Neumann-Architekturen (Einprozessorrechner)

• SIMD: Single Instruction stream over Multiple Data streams Vektorrechner

• MISD: Multiple Instruction streams over a Single Data stream Praktisch leer (ist umstritten); Ausnahme: heterogene Systeme verarbeiten die gleichen Daten und müssen zu einem übereinstimmenden Ergebnis → Space Shuttle Flight Control Computer

• MIMD: Multiple Instruction streams over Multiple Data streams Multiprozessorsysteme (MPP)

• Ein paralleles Programm lässt sich als halbgeordnete Menge (reflexiv, antisymmetrisch, transitiv) von Befehlen darstellen, wobei die Ordnung durch die Abhängigkeiten der Befehle untereinander gegeben ist

• Befehle, die nicht voneinander abhängig sind, können parallel ausgeführt werden (z.B. a[i] = a[i] + 1 vs. a[i] = a[i-1] +1)

• Eine total geordnete Teilmenge von Befehlen eines parallelen Programms bildet eine sequentielle Befehlsfolge

• Verschiedene sequentielle Befehlsfolgen können voneinander unabhängig sein (z.B. zwei for-Schleifen nacheinander)

Unterscheidung

• Ebenen der Parallelität in einem Programm

• Techniken der Parallelarbeit in der Hardware

1) Programmebene (oder Jobebene)

• Beispiel: gleichzeitig ausgeführte Programme in einem Betriebssystem; keine gemeinsamen Daten, wenig/keine Kommunikation untereinander

2) Prozessebene (oder Taskebene)

• Tasks (schwergewichtige Prozesse - heavy-weighted processes, coarse-grained tasks)

• Bsp.: Linux-Prozesse eines Programms; gemeinsame Daten, Kommunikation

3) Blockebene:

• Anweisungsblöcke oder leichtgewichtige Prozesse (threads, light-weighted processes) Unterschied zu schwergewichtigen Prozessen: weniger Befehle und gemeinsamer Adressraum; geringer Aufwand zur Prozesserzeugung

• Innere oder äußere parallele Schleifen in Fortran-Dialekten, Microtasking und coarse-grained-Datenfluß als Programmiertechnik

• Beispiel: häufig bei nummerischen Programmen durch parallel ausführbare Schleifeniterationen

4) Anweisungsebene (oder Befehlsebene)

• Einzelne Maschinenbefehle oder elementare Anweisungen (in der Sprache nicht weiter zerlegbare Datenoperationen) werden parallel zueinander ausgeführt

• Beispiel: optimierende Compiler für superskalare oder VLIW- Prozessoren; Analyse des sequentiellen Programms und ggf. Umordnung von Befehlen, um so Parallelität für den Prozessor nutzbar zu machen

5) Suboperationsebene

• Eine elementare Anweisung wird durch den Compiler oder in der Maschine in Suboperationen aufgebrochen, die parallel ausgeführt werden

• Beispiel: Vektoroperationen, die von einer Vektorpipeline „überlappend parallel“ ausgeführt werden; Vektor- und Matrixoperationen

• Voraussetzung: vektorisierende Compiler, komplexe Datenstrukturen Hohe Parallelität möglich, häufig durch einzelne, spezielle Operation ausdrückbar (i.G.z. konventionellen Sprachen mit Parallelisierung auf Blockebene)

• Die Körnigkeit oder Granularität (grain size) ergibt sich aus dem Verhältnis von Rechenaufwand zu Kommunikations- oder Synchronisationsaufwand

• Sie bemisst sich nach der Anzahl der Befehle in einer sequentiellen Befehlsfolge bevor eine Kommunikation oder Synchronisation ausgeführt wird

• Programm-, Prozess- und Blockebene werden häufig auch als grobkörnige (large/coarse grained) Parallelität bezeichnet

• Anweisungsebene wird als feinkörnige (finely grained) Parallelität bezeichnet

• Selten: mittelkörnige (medium grained) Parallelität, womit meist die Blockebene gemeint ist

• Suboperationsebene ist besonders, da noch feinkörniger als Anweisungsebene

• Modell eines idealisierten, speichergekoppelten Parallelrechner ohne Beachtung von Synchronisations- und Speicherzugriffskosten

• n-Prozessor-PRAM besteht aus n identischen Prozessoren (sequentiellen Registermaschinen), die alle auf einen gemeinsame Speicher (mit den Speicherzellen G[0],G[1],... ) zugreifen können

• Alle Prozessoren werden von einem gemeinsamen Takt gesteuert und führen zu einem Zeitpunkt dieselben oder auch verschiedenartige Rechenoperationen aus

• PRAM-Modelle idealisieren Parallelrechner, bei denen die Speicherzugriffe und die Programmausführungen von mehreren Prozessoren ohne zusätzliche Kosten synchronisiert werden

• Ob der global adressierbare Speicher auf die Prozessoren verteilt ist oder zentral ist, ist für das PRAM-Modell unerheblich

• Jeder Prozessor kann in Einheitszeit auf jede Speicherzelle zugreifen

• PRAM: eine Art speichergekoppeltes Multiprozessorsystem, bei dem nach jeder Operation eine (kostenlose) Synchronisation aller Prozessoren erfolgt

• Annahmen über den globalen Speicher: unendlich groß und konstante Speicherzugriffszeit

• Beim Zugriff auf den gemeinsamen Speicher können Konflikte auftreten, wenn verschiedene Prozessoren die gleiche Speicherzelle lesen oder schreiben

Exclusive read (ER)

• Pro Zyklus kann höchstens ein Prozessor dieselbe Speicherzelle lesen

Exclusive write (EW)

• Pro Zyklus kann höchstens ein Prozessor dieselbe Speicherzelle beschreiben

Concurrent read (CR)

• Pro Zyklus können mehrere Prozessoren dieselbe Speicherzelle lesen

Concurrent write (CW)

• Pro Zyklus können mehrere Prozessoren dieselbe Speicherzelle beschreiben

• Um Konfusion zu vermeiden, müssen die Schreibkonflikte gelöst werden

Diese 4 Optionen sind miteinander kombinierbar

• EREW-PRAM: Gemeinsame Lese- oder Schreibzugriffe verboten

• CREW-PRAM: Gemeinsame Lesezugriffe erlaubt, mehrere Schreibzugriffe verboten -> Kommt der Realität am nächsten

• ERCW-PRAM: Exklusiver Lesezugriff, gemeinsamer Schreibzugriff

• CRCW-PRAM: Gemeinsame Lese- oder gemeinsame Schreibzugriffe erlaubt

  • Bei Schreibkonflikten wird nach einer der folgenden Methoden gehandelt

  • Common (C-CRCW): Gleichzeitige Schreibzugriffe auf dieselbe Zelle sind nur erlaubt, falls alle Schreibzugriffe dort denselben Wert ablegen wollen

  • Arbitrary (A-CRCW): Einer der schreibenden Prozessoren gewinnt und belegt die Speicherzelle mit seinem Wert, die anderen werden ignoriert

  • Priority (P-CRCW): Von den am Schreibkonflikt beteiligten Prozessoren gewinnt der Prozessor mit dem kleinsten Index; er beschreibt die Speicherzelle

Nachrichtengekoppeltes Maschinenmodell

Ein BSP-Rechner besteht aus:

• Einer Menge von Prozessoren (mit oder ohne lokalem Speicher)

• Einem Kommunikationsnetz für das Verschicken von Nachrichten zwischen den Prozessoren

• Einem Mechanismus für eine Barrierensynchronisation

• Bei der Ausführung wird von den Prozessoren eine Anzahl von parallelen Superschritten (‚superstep‘) durchgeführt, während derer sie unabhängig voneinander arbeiten

• Jeder Superschritt besteht aus

  • Einer festen Anzahl von Berechnungsschritten auf lokalen Variablen, die zu Beginn des Superschrittes zur Verfügung stehen

  • Dem Versand von Nachrichten im idealisierten Kommunikationsnetz

• Danach wird eine Barrierensynchronisation aller Prozessoren durchgeführt, bevor der nächste Superschritt starten kann

Ein BSP-Rechner ist durch folgende drei Parameter charakterisiert

• p ist die Anzahl der Prozessoren

• g ist ein Faktor, der Kommunikationskosten in Berechnungskosten umrechnet

• L ist die minimale Zeit zwischen zwei Synchronisationen, also die Zeit für die Ausführung eines Superschritts

Ist am Ende der Periode L der Superschritt beendet, so wird der nächste Superschritt durchgeführt

• Ansonsten wird eine weitere Periode L dem noch nicht vollendeten Superschritt zugeordnet

• Durch die Notation der Superschritte werden Kommunikation und Synchronisation voneinander entkoppelt

• Somit werden Verklemmungen durch ‚race conditions‘ vermieden

• Zum Zeitpunkt der Ausführung der Barriere am Ende eines Superschrittes ist der globale Zustand der Programmausführung wohldefiniert

Prozessoren arbeiten unabhängig voneinander und tauschen Daten aus, indem sie über ein Netzwerk Nachrichten versendn

• Nachrichtengekoppeltes Maschinenmodell

• Abstraktion von der konkreten Ausprägung des Netzwerks

LogP:

• Latenzzeit L (Latency) ist die maximal benötigte Zeit für die Übertragung einer kleinen (nur ein Wort oder wenige Wörter umfassenden) Nachricht

• Aufwand o (Overhead) beschreibt den Zeitbedarf für den Sende- bzw. den Empfangsvorgang Es wird davon ausgegangen, dass der Prozessor beim Senden oder Empfangen keine weiteren Operationen parallel dazu ausführen kann

• g (Gap) ist eine untere Schranke für die Zeit, die auf jedem Prozessor zwischen zwei aufeinanderfolgenden Übertragungsvorgängen eingehalten werden muss

• Prozessorzahl P, wobei jeder Prozessor optional einen lokalen Speicher besizzen kann

• Netzwerk besitzt eine endliche Bandbreite, so dass zu einem bestimmten Zeitpunkt höchstens L/g Nachrichten zwischen zwei Prozessoren unterwegs sein können

• Latenzzeit L ist als obere Schranke für eine Nachrichtenübertragung aufzufassen

PRAM

• speichergekoppeltes Modell

• „takt“synchron

• „gut“ zu programmieren

BSP

• nachrichtengekoppeltes Modell

• Superschritt-Synchronisationen

LogP

• nachrichtengekoppeltes Modell

• Explizite Kommunikation

• geeignet für Laufzeitabschätzungen