Copy of pp

Wie kann man das Problem lösen?

PRAM nutzlos?

Laufzeitanalyse

im Detail

α: Zeit für die arithmetischen Operationen

β: Zeit zur Kommunikation zwischen Prozessoren

Paralleles Skalarprodukt

Ableitung nach p

Für ineffektiv

:

Einfachheitshalber ist n vielfaches von p

Lineares Feld

Mittlerer Prozessor empfängt Ergebnisse

: Lokale Berechnungen

: Akkumulation der Ergebnisse

Laufzeitberechnung nach optimaler Größe p

• Bei kleinem p Geschwindigkeit der arithmetischen Operationen höher
• Bei großem p wird die Kommunikationszeit im Netzwerk zu groß

Größe Eingabe n

Anzahl Prozessoren p

Kommunikationsparameter

Analyse von Laufzeitformeln

Hyperwürfel

Nicht analytisch lösbar

Unterschiede der Datenverteilungen

Zeilenorientiert:

Spaltenorientiert:

Lineares Feld

Hyperwürfel

Einzel-Akkumulationsoperation in log p

Parallele Matrix-Vektor-Multiplikation

Beispiel

Matrix wird mit Vektor multipliziert

• CRCW-PRAM, Laufzeit beträgt
• Prozessoren, jeder Prozessor (i,j) vergleicht A[i] und A[j],
• Gesamt also :

PRAM-Modell

Weiterentwicklungen

Phasen-PRAM versucht die Synchronität durch Phaseneinteilung zu beseitigen. Prozessoren arbeiten innerhalb einer Phase asynchron.

Verzögerungs-PRAM versucht Verzögerungszeiten zu modellieren.

• Abstraktion von Details der uns bekannten Rechner (endlicher Speicher, evtl. Caches)
• Unbeschränkte Anzahl von RAM-Rechnern
• Unbeschränkter globaler Speicher

• Prozessoren könnten versuchen gleichzeitig mit derselben Speicherzelle zu arbeiten

zum Glück nicht!

• die uniforme Zugriffszeit unrealistisch
• synchrone Arbeitsweise der Prozessoren unrealistisch

die Speicherzelle s erhält den folgenden Wert :

(jede Multipräfixoperation braucht für die Ausführung zwei Zyklen)

Betrachten eine MPADD-Operation (eines SB-RAM). Ausführung erfolgt auf einer Speicherzelle (s), welche mit dem Wert vorbesetzt ist. Jeder Prozessor (1 < i < n) stellt dabei einen eigenen Wert bereit. Sodass jeder Prozessor aufgrund der synchronen Ausführen den folgenden Wert erhält.

Ist die Vorhersage realistisch?

Kosten

NEIN

jetzt zum Wesentlichen

Variante 1 :

• gemeinsames Schreiben erlaubt, nur wenn gleiches geschrieben wird

Variante 2:

• ein beliebiger Prozessor gewinnt

Variante 3:

• die Summe der Werte der einzelnen

Prozessoren wird in die Speicherzelle

geschrieben

Variante 4:

• Prozessoren werden Prioritäten zugeordnet und derjenige, der die höchste Priorität hat, gewinnt

• EREW-PRAM (exclusive read, exclusive write)
• verbietet simultane Zugriffe auf selbige Speicherzellen

• CREW-PRAM (concurrent read, exclusive write)
• verbietet simultanes Beschreiben
• erlaubt simultanes Lesen

• ERCW-PRAM (exclusive read, concurrent write)
• verbietet simultanes Lesen
• erlaubt simultanes Beschreiben

• CRCW-PRAM (concurrent read, concurrent write)
• sowohl Beschreiben als auch Lesen erlaubt

Schreiben derselben Speicherzelle?

was passiert aber beim simultanen

BSP-Modell

• Architektur entwickelte sich schneller als die Modelle
• Parallelrechnerarchitektur soll dem BSP-Modell entsprechen

-> einfacher für Softwareentwickler

Aus welchen Einzelteilen besteht ein BSP-Modell?

• eine Anzahl von Prozessoren, wobei jeder mit einem Speicher ausgestattet sein kann
• einem Verbindungsnetzwerk (PTP zwischen Prozesorren)
• Synchronisationsmechanismus zum Synchronisieren der Berechnungseinheiten nach Ablauf von Zeiteinheiten

http://upload.wikimedia.org/wikipedia/en/thumb/e/ee/Bsp.wiki.fig1.svg/525px-Bsp.wiki.fig1.svg.png

Synchronisationsmechanismus kann maximal alle L Zeiteinheiten synchronisieren Superschritt dauert mindestens L

Zeiteinheiten

http://dooki.com/supercomputers/sgi/challenge/sgi.power_challenge.gif

Hello World dynamic

Die Berechnung besteht aus einer Folge von Superschritten

• pro Superschritt werden

lokale Berechnungen durch-

geführt

• verschickte Daten können

erst im nächsten Super-

schritt benutzt werden

• Am Ende Barrier-Synch

Hello World static

Superschritte

BSPlib

• unterstützt SPMD Programmierstil

• Verfügbar für C und Fortran
• Implementierungen in diversen Rechnern:
• Cray T3E
• IBM SP2
• SGI PowerChallenge

Die Ausführungszeit eines BSP-Programms setzt sich aus der Summer der Ausführungszeiten der Superschritte zusammen

• Der Router kann in einem Superschritt h-Relationen durchführen.
• Eine h-Relation ist ein Kommunikationsmuster, bei dem jeder

Prozessor maximal h Nachrichten empfangen/versenden kann

• Eine Berechnung wird wie folgt realisiert:
• p : # Prozessoren
• s : Berechnungsgeschwindigkeit der Prozessoren
• l : # Schritte für die Barrier-Synchronisation
• g : # Schritte, die im Mittel für den Transfer eines Wortes

innerhalb einer h-Relation gebraucht werden

Das Ausführen einer h-Relation mit m Worten pro Nachricht

benötigt Schritte.

Ausführungszeit eines Superschrittes setzt sich wie folgt zusammen :

1) Maximum der Dauer der lokalen Berechnungen von jedem Prozess

2) Kosten der globalen Kommunikation für die h-Relation

3) Kosten für die Barrier-Synchronisation

sodass man auf folgende Formel kommt :

Der Router

Kosten

LogP-Modell

Kritik am BSP-Modell:

• Größe der Superschritte muss groß genug

sein, um beliebige h-Relationen auszuführen

• Verschickte Nachrichten erst im nächsten

Superschritt verfügbar

• Parallelrechner besteht aus Prozessoren mit lokalem Speicher
• Hier ebenfalls Punkt-zu-Punkt-Verbindungen

Inhalt :

Zwischen zwei Prozessoren dürfen maximal

Nachrichten unterwegs sein

Beim LogGP-Modell wird ein zusätzlicher Parameter G eingeführt (Gap per Byte). Dieser gibt an, wie viele Zeiteinheiten aufgewendet werden müssen, um die Nachricht erfolgreich zu verschicken. Dabei ist die Bandbreite pro Prozessor. Die Zeit für das Verschicken einer Nachricht mit n Byte beträgt :

Nachteil: nur kleine Nachrichten konnten verschickt werden

LogGP-Modell

• L (latency) : obere Grenze für die Latenz
• o (overhead) : Verwaltungsaufwand eines Prozessors
• g (gap) : minimale Zeitspanne, die zwischen

dem Empfangen und versenden einer Nachricht vergehen muss

• P (processors) : # Prozessoren

Kommunikationsverhalten

überschritten wird ?

Was passiert wenn diese Größe

Zeiteinheiten

Das LogP-Modell erwartet kurze Nachrichten, somit muss eine zu große Nachricht zerlegt werden.

Die Zustellung einer Folge von n Nachrichten dauert

Was ist wenn die Nachricht an sich groß ist?

Zeiteinheiten

Ein Zugriff auf einen ein Element im Speicher eines anderen Prozessors dauert

Wenn diese zuvor genannte Anzahl überschritten wird,

wird derjenige Prozessor blockiert, bis er die Nachricht

ohne Überschreitung schicken kann

hat dies ?

Die Laufzeit wird durch das Maximum der Laufzeiten der einzelnen Prozessoren bestimmt

Was für eine Laufzeit

Kosten

• Benchmarks
• SPEC
• MFLOPS
• Analyse von Laufzeitformeln
• Paralleles Skalarprodukt
• Parallele Matrix-Vektor-Multiplikation

• Parallele Berechnungsmodelle
• PRAM-Modell
• BSP-Modell
• LogP-Modell

Parallele Berechnungsmodelle

• Beschreibung der Basisoperationen auf einer Abstraktionsebene
• Bewertung vor eigentlicher Implementierung
• Möglichst allgmeines Computermodell
• Algorithmusuntersuchung hinsichtlich Speicherverbrauchs sowie der Laufzeit

SPEC

Pentium 4, 3,2 GHz: 6,4 GFLOPS

Core i7, 3,2 GHz, 4 Kerne: 51,2 GFLOPS

Core i7 Sandy-Bridge, 3,4 GHz, 4 Kerne: 102,5 GFLOPS

Desktop Benchmarks

• processor-intensive (SPEC CPU 2006)
• graphics-intensive (wobei hierbei meist auch CPU-Aktivität nicht ganz ausgeschlossen sein kann)

FLOPS = CPU-Takt × Prozessorkerne × Instruktionen je Takt × CPUs im Rechenknoten

Best-Case-Abschätzung

Ausführung von FMADD-Befehlen in einer Schleife auf DP-FP

FLOPS

• RISC wird bevorteilt gegenüber CISC
• 32-Bit gegenüber 64-Bit
• Datenbandbreite in Netzwerken
• Compiler und Architektur

SPEC CPU 2006 :

• 12 Integer Benchmarks (CINT 2006)
• 17 Floating Point Benchmarks (CFP 2006)

• Man benutzt eine Benchmark-Suite
• Man möchte möglichst einen aussagekräftigen Wert für das gesamte System
• Langsame Programme würden das Resultat verfälschen

Gewichtete Werte nicht möglich, da verschiedene Betriebe verschieden rechnen könnten

• Bezug auf ein Referenzsystem

Angenommen der SPECRatio vom Computer A wäre 1.25 Mal höher als der vom Computer B

Da SPECRatio keine Einheit besitzt, muss ein geometrisches Mittel gebildet werden

von Artemij Voskobojnikov

und Oliver Junk