Kapitel 7

Parallelverarbeitung:

sequentielle Verarbeitung:

Folge von Verarbeitungsaktionen auf Daten.

Modell zur Verarbeitung (abb7-1.jpg) ( strukturiert in Datensätze: Eingabe - und Ausgabedaten )
Abb. 7-1: sequentielle Verarbeitung
sequentielle Verarbeitung durch Von - Neumann - Rechner:
Verarbeitung bei Von - Neumann (abb7-2.jpg)
Abb. 7-2: Verarbeitung im Von - Neumann Rechner
SISD -Maschine:   Single Instruction
Single Data Stream

Problemfluß = Datenfluß   Aktionsfluß aus Instruktionsfluß

Grundmuster zur Parallelverarbeitung:

A) Freizügig einsetzbare Stationen:
Autos auf Rampen (abb7-2a.jpg)
größere weitgehend isolierte Probleme

Arbeit der einzelnen Stationen stark voneinander entkoppelt !

Stationen universell: aufwendig, teuer !

B) Feld gleichartiger Stationen:
Zug bei Beladung (abb7-2b.jpg)
Gesamtproblem zerfällt in isolierte gleichartige Teilprobleme

gleicher Takt, Beiträge der Stationen benötigen diesselbe Zeit

C) Fließband spezialisierter Stationen:
Fließband (abb7-2c.jpg)
Folge gleichartiger Probleme, Problem in Sequenz von Teilproblemen gliederbar

spezialisierte Stationen: Arbeitsteilung, gleicher Takt

Grobe Sicht: Sequenz

Feine Sicht: überlagernde Teilsequenzen

D) Netz von Stationen:
Netz (abb7-2d.jpg)
nebenläufiger Problemfluß: nebenläufig arbeitendes Systeme

Synchronisation entsprechender Problemflußabhängigkeiten

Von - Neumann - Rechner: Ebenen der Arbeit
  • Prozeßmengen
  • Befehlsfolge
  • Befehlsabwicklung
  • Operation
  • Operationsabwicklung

Von - Neumann - nahe Parallelrechner:

  1. Befehlsfließband in Prozessor ( SISD )
    Befehlsfolge  
    Befehl C:
    Befehl B:
    Befehl A:
      C1
    B1
    A1: Holen
      C2
    B2
    A2: Decodieren
      C3
    B3
    A3: Ausführen
    Zeitverlauf der Befehlsabarbeitung (abb7-3.jpg)
    Abb. 7-3: Befehle in der Zeit
  2. ALU - Feld: Vektorrechner ( SIMD )
    Abarbeitung von Operationen (abb7-4.jpg)
    Abb. 7-4: Operationen
  3. Mehrprozessor - Maschine ( MIMD )
    Mehrprozessor - Maschine (abb7-5.jpg)
    Abb. 7-5: Modell Mehrprozessormasch.
Probleme der Parallelisierung:

A) logisch

- Barrieren: Datenflußabhängigkeiten
- Geeignete Algorithmen

B) technisch

- Zentraler Speicher: Leistungsfähigkeit des Zugangs ( Datenrate )

Lösungsansätze:
  - schneller Zwischenspeicher ( Cache )
- Speicherbänke
Aufbau: Zentraler Speicher (abb7-6.jpg)
Abb. 7-6: Zentraler Speicher

Neuere Lösungsansätze:

- Aufgliederung des zentralen Speichers:

  • seperate private Speicher
  • Verbindungsnetzwerk zwischen Stationen

- Verzicht auf Variablen in Algorithmen:

  • Datenflußprogrammierung
  • Datenflußrechner

Verbindungsnetzwerk / Transportnetz:

Verbindungsnetzwerk (abb7-7.jpg)
Abb. 7-7: Modell: Netzwerk

Topologie: voll vermascht

sehr viele Stationen:

- Hardware - Aufwand
- Erweiterbarkeit
- Fehlertoleranz

Topologien: Ringe, Würfel, Bäume, ...

Beispiel: Würfel (abb7-8.jpg)
Abb. 7-8: Topologie Würfel

- Routing: Wegefindung; Weiterleitung

technische Neuerungen:

- optimierte Übertragung ( Gigabit / sec )
- Bus ( vereinfachtes Routing )
- Bus - Hierarchie

Konzeptionell: Zwei - Punkt - Verbindung => Gruppenkommunikation

Mehrprozessor - Maschine mit privaten Speichern:

z. B. : Transputer - Netz

Transputernetz ( MIMD ) (abb7-9.jpg)
Abb. 7-9: Prozessornetz

Connection Maschine: ( SIMD )

Connection - Maschine (abb7-10.jpg)
Abb.7-10: Connection - Maschine

aber Single Makro Instruction jeder Zelle ebenfalls programmgesteuert:

- Datenverknüpfung
- Routing in vorgeprägten Mustern

Zellenrechner:

  • zentraler Takt
  • je Zelle gleichartiges, sehr einfaches Programm, zyklisch
  • Datenaustausch mit Nachbarn im Netz
  • einfache regelmäßige Topologie
Zellenrechner (abb7-11.jpg)
Abb.: 7-11: Zellenrechner

Assoziativspeicher ( inhaltsadressierbare Speicher ):

Eingabemuster:  
0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0
   
Maske:  
1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0
   
      Treffer:  
   
0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0
0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1
0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 1
1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0
1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0
1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0
0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0
0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1
0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0

2 =>




7 =>


10 =>






Auswahl





Beispiel für Treffer:  
0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0
   
Tab.: 7-1

Verarbeitungsfunktion je Bit im Speicher:

- einfache Funktion: Gleichheit mit Eingabebit

Verarbeitungsfunktion je Wert im Speicher:

- einfache Funktion: Gleichheit aller nicht-maskierten Bits

Verarbeitungsfunktion für Speicher insgesamt:

- Treffer - Anzahl zur Ausgabeadressierung

Datenfluß - Rechner:

Ansatz: Verzicht auf Variablenkonzept, d. h. permanenter Speicher

Algorithmen funktional Operanden => Operation => Ergebnis

Datenflußrechner (abb7-12.jpg)
Abb.7-12: Beispiel: Datenflußrechner

Synchronisation nur entsprechend Datenfluß

Problem:  
  • Konfigurierung durch Konfiguration
  • Virtuelle Zellen und Verbindungen realisieren mit fester Grundkonfiguration
  • Manche Probleme erfordern prozedurale Algorithmen:
    - Interaktion mit Umwelt
Datenflußrechner:

am Beispiel: m! - Berechnung

m ! - Berechnung (abb7-13.jpg)
Abb.7-13: m! - Berechnung

Realisierung:

Realisierung der m ! Berechnung (abb7-14.jpg)
Abb. 7-14: Realisierung des Beispiels