2.1.3 Grobklassifikation nach Flynn

Im Jahre 1966 unterschied Michael Flynn [Fly66] parallele Architekturen bzgl. des Datenstroms und des Stromes der Programmanweisungen, so daß sich 4 Formen der Parallelität ergeben.

 

Tabelle 2.1: Flynn Klassifikation (Flynn's taxonomy)

Single	Multiple
Instruction Stream
SISD	MISD	Single	Data
SIMD	MIMD	Multiple	Stream

SISD :  
Klassische Architektur

• nur prozessorinterne Parallelität (bitparallel, look-ahead)
• Pseudeoparallelität mittels Multitasking und Time-Sharing (Durchsatzerhöhung der Anlage)

SIMD :  
Parallelität auf Anweisungsebene

1.

Die Daten sind über die Prozessoren verteilt, ein Programm wird ''im Gleichschritt'' auf allen Prozessoren abgearbeitet. Meist sehr einfache, dafür aber viele Prozessoren (Prozessorfelder CM2, MasPar).
Ein typisches Problem bei SIMD sind Programmalternativen :

Liefert der Test ''?'' bei 2 Prozessen der SIMD-Maschine unterschiedliche Ergebnisse (T/F), ändert sich das Struktogramm in

,d.h. eigentlich läuft ab :

2.

Der Vektorrechner   benutzt das Pipelining derart, daß im Unterschied zum skalaren Rechner die gleiche Befehlssequenzen mit $n$ Datensätzen wiederholt werden. Eine typische Operation ist die SAXPY-Operation $\,\underline{y} := \underline{y} + {\alpha} \underline{x}\,$ in Abb. 2.1, welche auf einen Vektor  $\underline{y}$ den mit der reellen Zahl $\alpha$ skalierten Vektor  $\underline{x}$ addiert. Die Pipeline besteht in diesem Falle aus Addition, Multiplikation, Lade- und Speicheroperationen welche mit den Vektorregistern durchgeführt werden. Nach einem ''Startup'' wird i.a. pro Taktzyklus ein Ergebnis $y_i$ geliefert, obwohl in der skalaren Rechnung mehr Takte notwendig sind.

  

Abbildung 2.1: SAXPY im Vektorrechner

Um hohe MFLOP-Raten zu erreichen, müssen die Vektorregister stets gefüllt sein ! Bei Nichtbeachtung dieser Forderung ist der Einsatz des Vektorrechners sinnlos, da nur die skalare Rechenleistung erreicht wird. In nebenstehender Abbildung tritt ein Vektor  $\underline{\alpha}$ auf, welcher nichts anderes als das Auffüllen des entsprechenden Vektorregisters mit dem Skalar $\alpha$ symbolisiert. Dies wird automatisch vom Compiler getan, da der Vektorrechner eigentlich nur die Operation $\,\underline{y} := \underline{y} + \underline{\alpha}^T \circledast \underline{x}\,$ effizient behandeln kann.

Aus der Sicht des Mathematikers im Sinne der Parallelisierung mathematischer Algorithmen beschleunigt der Vektorrechner ''nur'' die sequentiellen Algorithmen ohne etwas an ihnen zu ändern.

MIMD :  
Bedeutet Parallelität auf Programmebene, d.h. jeder Prozessor arbeitet sein eigenes Programm ab. Dies geschieht in der Regel aber nicht unabhängig voneinander, daher unterscheidet man :

1.

konkurrierende Prozesse (gemeinsame Ressourcen)

2.

kommunizierende Prozesse (Datenfluß, Datenaustausch)

Unterscheide
Programm (statisch) :  
Exakte Niederschrift eines Algorithmus

Prozeß (dynamisch) :  
Folge von Aktionen, einzige Annahme: positive Geschwindigkeit.





Oft repräsentiert jeder Prozeß dasselbe Programm, allerdings mit unterschiedlichen Daten.
$\Longrightarrow$ SPMD als Unterklasse der MIMD

SPMD :  
Single Program Multiple Data

• Wird auf größeren Parallelrechnersystemen und vor allem bei massiv parallelen Rechnern verwendet.
• Datenparallelität muß vorhanden sein.
• Kein SIMD, da kein Gleichschritt in Anweisungsebene erforderlich. Jedoch müssen im Normalfall in den Synchronisationszeitpunkten Daten angeglichen werden.