14 Parallele Rechner 14.1 Parallele Rechner - Einführung 14.2 Leistung 14.3 Kommuniklationsarchitektur 14.4 Typen paralleler Architekturen

14 Parallele Rechner

14.1 Parallele Rechner - Einführung14.2 Leistung 14.3 Kommuniklationsarchitektur14.4 Typen paralleler Architekturen

RW-Systemarchitektur Kap. 132

(Echter) Parallelismus• Bisher meist Pseudo-Parallelismus von nebenläufigen

Systemen• Jetzt: Echter Parallelismus – „Schnelles Lösen großer

Probleme durch eine Menge kooperierender und kommunizierender Rechenelemente (RE) (processing units)“ (Almasi/Gottlieb)

• Ziele1. Leistungssteigerung,2. Reduktion von Wartungsaufwand oder Gewicht durch die

Integration von Funktionen bei eingebetteten Systemen,3. Steigerung der Ausfallsicherheit durch Redundanz.

Wir konzentrieren uns erst nur auf den ersten Aspekt, später auf den zweiten.


Paralleles Rechnen• erwartete Leistungssteigerung für

Anwendungen:– gleichzeitiges Arbeiten an verschiedenen Teilen

des Problemraums,– Koordination zur Sicherung der Konsistenz,– Kommunikation zum Informationsaustausch.

• Neue Aufgaben:– Koordination – SW-Aufgabe– Kommunikation - Architekturunterstützung

P1 P2

Kommunikation

Synchronisation


Parallele Rechner• Schnelles Lösen großer Probleme durch eine Menge kooperierender und kommunizierender Rechenelemente.

• "... eine Menge von Rechenelementen..."– Wie viele? Wie mächtig ist jeder? Nur Prozessoren oder komplette

Rechner? Skalierbarkeit? Kosten?

• "... kommunizierende ..."– Wie kommunizieren Rechenelemente? (z.B. über gemeinsamen

Speicher oder durch Nachrichtenaustausch)

– Architektur des Verbindungsnetzwerks? (Bus, Kreuzschienenschalter (crossbar), mehrstufiges Netzwerk, ...)

– Bewertungskriterien : Kosten, Latenz, Durchsatz, Skalierbarkeit, Fehlerttoleranz


• "... kooperierender ..."– wichtige Konzepte: Synchronisation, Granularität und Autonomie– Synchronisation sichert Konsistenz

• Primitive Operationen (test&set, fetch&add, ...);

– Granularität legt die Größe von Teilaufgaben fest.• kleinere Granularität größerer Parallelismus mehr Kommunikation größerer

Overhead.

• Granularitäten Zahl von Instruktionen Parallelismus

• Programmniveau 10^6+ Befehle

• Taskniveau 10^3-10^6 Befehle Task-Parallelismus

• Schleifenniveau 10-1000 Befehle SW-Pipelining

• Anweisungsniveau 2-10 Befehle Befehlsanordnung

– Autonomie: SIMD- oder MIMD-Rechner• MIMD-Rechner sind allgemeiner einsetzbar, aber der Overhead kann bei häufiger

Synchronisation groß sein.


• "Schnelles Lösen großer Probleme ..."– Universalrechner gegenüber Spezialrechner

• Jeder Rechner kann irgendetwas effizient lösen!

– Welche Anwendungen lassen sich parallelisieren:• Leicht parallelisierbare Anwendungen (embarrassingly parallel

applications)– Viele wissenschaftliche Anwendungen mit hohem Datenparallelismus

• mittelleicht parallelisierbare Anwendungen– ingenieurwiss. Anwendungen (finite-Elemente-Methoden, VLSI-CAD)

• schlecht parallelisierbare Anwendungen– MS Word, Übersetzer usw.


14.2 Leistung• Wichtige Metriken:

– Latenz – Ausführungszeit für eine Operation, z.B. einen Block in den Cache zu laden, eine Nachricht vom Sender zum Empfänger zu schicken, …

– Leistung – Zahl der Operationen pro Zeiteinheit,– Kosten – Beitrag zur Ausführungszeit von Programmen.

• Kein einfacher Zusammenhang wg. Parallelismus! Auf Rechner ohne Parallelismus: Leistung = 1/ Latenz Kosten eines Programms = Latenz x Zahl der ausgeführten Operationen


Beispiel• Architekturkomponente führt Operation in 100ns aus

• Leistung: 10 Mops

• Interne Pipelinetiefe 10 => höchste Leistung 100 Mops

• Tatsächliche Leistung hängt vom Füllgrad der Pipeline ab, insbesondere von Abhängigkeiten

• Annahme: Anwendung führt 100 M Operationen aus. Kosten?– #Operation * Operationslatenz ergibt 10s (obere Schranke)

– #Operation / Höchstleistung ergibt 1s (untere Schranke)• nimmt vollständige Überlappung aller Latenzen an

– Wenn die Anwendung 50ns nützliche Arbeit erledigen kann, bevor sie auf das Ergebnis einer Operation warten muss, sind die Kosten der Operation die anderen 50ns der Latenz.


Kommunikation (lineares Modell)

• Transferzeit (n) = T0 + n/B für Daten der Größe n,• T0 ist die Einrichtezeit (setup time),• B die Transferrate, die Zahl der übermittelten Datenelemente pro

Zeiteinheit.

• Bei gemeinsamem Speicher: Einrichtezeit = Speicherzugriffszeit• Bei Rechner mit Nachrichtenaustausch: Einrichtezeit = Zeit, nach

der das erste Bit beim Empfänger ankommt.• Bei Transfers über den Bus beinhaltet sie die Zeit für alle Aktionen,

bis der Transfer beginnt, Arbitrierung usw.• Mit der Größe des Transfers geht die Transferzeit asymptotisch

gegen die Transferrate B.


Kommunikation über ein Verbindungsnetzwerk

• Kommunikationszeit (n) =Initiierungsaufwand + Belegungszeit + Netzwerkverzögerung

• Initiierungsaufwand = die Zeit, die der Sender mit der Initiierung der Kommunikation beschäftigt ist; evtl. konstant oder Funktion von n.

• Belegungszeit = Zeit, für welche die langsamste Komponente auf dem Kommunikationspfad belegt und damit für andere Transfers gesperrt ist. Begrenzt die Häufigkeit von Transfers.

• Netzwerkverzögerung = Zeit, ein Bit durch das Netzwerk zu leiten + weitere Zeiten, bis Empfänger die geschickten Daten nutzen kann.

• Wenn Kommunikation in Pipeline-Form passiert, müssen alle drei Größen berücksichtigt werden.


Kommunikations-Kosten-Modell• Etwas differenzierter:

• Komm.Zeit pro Nachricht = Overhead + Assist-Belegungszeit+ Netzwerkverzögerung+ Größe/Bandbreite + Contention

• = ov + oc + l + n/B + Tc

• Jede Komponente auf dem Übermittlungsweg hat Belegung und Verzögerung

– Gesamtverzögerung ist die Summe der Verzögerungen

– Gesamtbelegungszeit (1/Bandbreite) ist Maximum der Belegungszeiten

• Komm.Kosten = Frequenz * (Komm.Zeit - Überlappung)


14.3 Kommunikations-Architektur• Schnittstelle ähnlich der ISA: Abstraktion für Programmierer

• Ziele sind:– breite Anwendbarkeit,– Programmierbarkeit– Skalierbarkeit– geringe Kosten

KommunikationsarchitekturOperationen für Kommunikation und Synchronisation,Datentypen

Organisation, Protokolle usw.


Schichten in parallelen Rechnern

VLSI/CAD

Mehrfach-Programmbetrieb

Gemein.Adressraum

Nachrichten-austausch

Daten-parallel

Datenbanken Wissenschaftl. Rechnen Parallele Anwendungen

Programmiermodelle

Kommunikations-AbstraktionNutzer/System-Schnittstelle

Übersetzungoder Bibiothek

BS-Unterstützung

Kommunikations-Hardware

Physikalisches Kommunikations-Medium

Hardware/Software Schnittstelle


Entwurfsfragen• Benennung:

– Wie werden kommunizierte Daten benannt?

• Latenz: – Wie hoch ist die Latenz für geschützte Kommunikation?

• Bandbreite: – Wie viele Daten können pro Zeiteinheit kommuniziert werden?

• Synchronisation: – Wie können sich Produzenten und Konsumenten von Daten

synchronisieren?

• Knoten-Granularität: – Wie teilt man die Ressourcen gut auf?

• Zahl und Leistung der Prozessoren, Aufteilung des Speichers usw.


14.4 Typen paralleler Architekturen

• Gemeinsamer Speicher

• Nachrichtenaustausch

• Datenparallel

• Datenfluss

• Systolische Felder

PE PE PE

PE PE PE

PE PE PE

Controlprocessor

WaitingMatching

InstructionFetch

Execute FormToken

Network

Network

Token Queue

TokenStore

ProgStore

M

PE

M

PE PE PE


Michael Flynns Taxonomie

• # instruction x # Data– Single Instruction Single Data (SISD)– Single Instruction Multiple Data (SIMD)– Multiple Instruction Single Data– Multiple Instruction Multiple Data (MIMD)

• Später hinzu gekommen:– Single Program Multiple Data (SPIMD)


Verbindungsnetzwerk

P P P

M M

Verbindungsnetzwerk

P MM P

• Charakteristik: Alle Prozessoren können direkt auf alle Speicherzellen zugreifen u.a. zur bequemen und schnellen Kommunikation miteinander.

– bequem: (i) Ortstransparenz (wo ist eine Speicherzelle); (ii) gleiche Abstraktion unterstützt wie bei heutigen Monoprozessoren,

– schnell: verglichen mit den anderen Modellen.

• Speicher zentral angeordnet oder verteilt.

• Besserer Name wäre Rechner mit einem globalen Adressraum.

• Typisches Problem: Skalierbarkeit.

Architekturen mit gemeinsamem Speicher

M


Architekturen mit Nachrichtenaustausch• Prozessoren können direkt nur auf lokalen Speicher zugreifen und

alle Kommunikation und Synchronisation geschieht mittels Nachrichten.

• Eigenschaften:– Das Senden einer Nachricht verursacht häufig mehrere Overheads:

• Aufbau des Nachrichtenkopfs; Kopieren der Daten in den Netzwerk-Puffer; Senden der Daten; Empfangen der Daten im Puffer; Kopieren der Daten aus dem Puffer, von Kernraum in den Benutzerraum - oft BS involviert.

– Synchronisation mit Nachrichten basiert auf (aufwendigen) Handshake-Protokollen.

– Ein Vorteil: Skalierbarkeit.

Verbindungsnetzwerk

P P PM M M


Gemeinsamer Speicher vergl. mit Nachrichtenaustausch

• Rechner mit einem Adressraum können durch Rechner mit Nachrichtenaustausch simuliert werden:– Lesen aus einer oder Schreiben in eine nichtlokale Speicherzelle

realisiert durch Senden und Empfangen entsprechender Nachrichten.

– Der Unterschied liegt in der Geschwindigkeit und der Leistung:Ein Rechner mit einem Adressraum ist spezialisiert auf Lesen aus dem und Schreiben in den Speicher, unterstützt in Hardware und ist deshalb viel schneller. Der Prozessor kann außerdem parallel dazu anderes tun, z.B. Rechnen.


Datenparallele Architekturen• Programmier-Modell:

– Annahme: Ein Prozessor assoziiert mit jedem Datenelement und unterstützt mit billiger globaler Synchronisation.

• Beispiel:– Jedes Berechnungselement besitzt einen Mitarbeiterdatensatz mit seinem

Gehalt; man berechne eine soziale abgestufte Gehaltserhöhung:

– Code:

– Die Gesamtheit der Operationen auf der Gesamtheit der Daten braucht eine kleine Zahl von Zyklen.0

• Häufigste Vertreter: Graphik-Coprozessoren für Rendering großer Szenen

If gehalt > 100000€ then

gehalt = gehalt *1.05

else gehalt = gehalt *1.10


Datenparallele Architekturen (2)• Datenparallele Architekturen oft charakterisiert durch:

– Einen Befehlsstrom

– Schwache Prozessoren mit beschränktem lokalen Speicher

– Effizientes Verbindungsnetzwerk

• Grenzen der Anwendbarkeit ist eine offene Frage: aber numerische Algorithmen sind bereits auf GPUs effizient realisiert worden.


Datafluss-Architekturen• In Datenfluss-Rechnern werden Operationen durch die Verfügbarkeit von

Operanden aktiviert.

• Im Gegensatz dazu sind traditionelle Rechner Steuerflussrechner, die Folgen von Befehlen mit explizitem oder implizitem Steuerfluss (control flow) ausführen.

• Vorteil: alle Abhängigkeiten sind explizit dargestellt im Datenflussgraphen; kein Problem, vorhandene Parallelität zu identifizieren.

1 b c e

a

d

f

+ - *

*

*

a=(b+1)*(b-c)d=c*ef=a*d

Datenflussgraph


Datafluss-Architekturen (2)

• Architektur:

• Probleme:– Granularität der Operationen

– Effiziente Behandlung von komplexen Datenstrukturen wie Feldern

– Komplexität der Mustererkennungs-und Speichereinheiten

– Evtl. zu großer Grad an Parallelität

WaitingMatching

InstructionFetch

Execute FormToken

Network

Network

Token Queue

TokenStore

ProgStore


Systolische Architekturen

Grundprinzip: Ersetzen eines einzigen REs durch ein reguläres Feld von Berechnungselementen, zwischen denen Daten fließen.

Hoher Durchsatz ohne große Erweiterung der Speicherbandbreite, Operanden fließen von BE zu BE.

• Unterschied zu einem Rechner mit Operationsfließband:– Prozessorfeld kann nichtlinear sein, z.B. hexagonal

– Verbindungen zwischen REs können in mehrere Richtungen gehen

– REs können lokalen Befehls- und Datenspeicher haben und sind universeller als eine Pipeline-Stufe

M

RE

M

RE RE RE


Systolische Architekturen (2)• Example: Systolische Feld für 1-D-Konvolution

• Probleme:– Systemintegration: Transfer der Daten vom Originalfeld in das systolische

Feld und zurück

– Übersetzung von imperativen Programmen in Programme für systolische Felder

– Universelle systolische Felder?

x(i+1) x(i) x(i-1) x(i-k)

y(i) y(i+1)

y(i) = w(j)*x(i-j)

j=1

k

y(i+k+1) y(i+k)W (1) W (2) W (k)


Architekturthemen


Benennungen – Einen globalen linearen Addressraum

• (gemeinsamer Speicher)

oder– Einen globalen segmentierten Addressraum

• (globale Objecte)

oder– Mehrere lokale Address/Namensräume

• (Nachrichtenaustausch)

• Benennungsstrategie hat Einfluss auf:• Programmierer / Software• Leistung• Entwurfskomplexität


Klassen von Anwendungen• Compute-Server

– Unabhängige Nutzer mit unabhängigen Berechnungen auf einem gemeinsamen Höchstleistungsrechner

– Synchronisation nur für den koordinierten Zugriff auf Ressourcen.• Speicher, Festplatten, Dateisystem

• Datenbank-Server– Benutzer führen Transaktionen auf einer gemeinsamen Datenbank

aus, z.B. Buchungssysteme von Banken, Flugreservierungen, Internet-Auktionen

– Synchronisation notwendig, um Konsistenz zu garantieren

• Leicht parallelisierbare Anwendungen– rechenintensive Aufgabe, die mehrere REs ausnützt– Synchronisation benötigt zur Koordination

losegekoppelt

starkgekoppelt


Beispiel einer parallelen Anwendung

• Diskretisierte Darstellung eines kontinuierlichen Systems

– Räumlich: Aufteilung auf ein Gitter– zeitlich: Zustand alle dT

Zeiteinheiten neu berechnen

• Beispielberechnung

• Lokalität– Neuberechnung hängt nur von den

Werten der Nachbarfelder ab

Finite-Elemente Modell

For time from 0 to maxTfor each mesh element

Update mesh value


Abbildung auf parallele Zielarchitektur •Partitionierung

–Teile Gitter in Gebiete auf

–Teile Gebiete Prozessoren zu

•Berechnung auf jedem Prozessor

räumliche Partitionierung

For time from 0 to maxTGet boundary values from

neighborsFor each mesh element

Update mesh valueSend boundary values to

neighbors

P1P1

P4P4

P7P7

P2P2

P5P5

P8P8

P3P3

P6P6

P9P9


Komplikationen• Kommunikations-Overhead

– N x N-Gitter, M Prozessoren

– Elemente / Prozessor = N2 / M• Arbeit pro Iteration

– Grenzelemente / Prozessor ~ N / Sqrt(M)• Kommunikation pro Iteration

– Kommunikation zu Berechnungslast ~ Sqrt(M) / N• Limitierender Faktor bei steigender Zahl von Prozessoren: Kommunikation

• Irregularitäten– Irreguläres Gitter, unterschiedliche Berechnungslast / Gitterelement

– Macht Partitionierung und Lastverteilung schwierig

• Synchronisation– Muss alle REs in gleicher Iteration halten

– Bestimmung globaler Eigenschaften wie Konvergenz

Documents

14 Parallele Rechner 14.1 Parallele Rechner - Einführung 14.2 Leistung 14.3 Kommuniklationsarchitektur 14.4 Typen paralleler Architekturen