Flynns Klassifikation

Flynnsche Klassifikation (Flynn‘sche Taxonomie)

• 1966 entwickelt, einfaches Modell, bis heute genutzt
• Beschränkung der Beschreibung auf die Befehls- und Datenströme

• Befehlsstrom
  • Folge von Maschinenbefehlen, werden vom Leitwerk als entschlüsselte Steuerinformation an das Rechenwerk weitergeleitet
• Datenstrom
  • Daten, die vom Rechenwerk bearbeitet werden, werden zwischen dem Speicher und den Prozessorregistern übertragen

SISD

Single Instruction Stream, Single Data Stream

SIMD

Single Instruction Stream,Multiple Data Stream

MISD

Multiple Instruction Stream, Single Data Stream

MIMD

Multiple Instruction Stream, Multiple Data Stream

Moore’s Law

The number of transistors incorporated in a chip will approximately double every 24 months. Gorden Moore

Quelle: http://en.wikipedia.org/wiki/Moore%27s_law

Expertenmeinung

Prognose für die Entwicklung von CPUs aus dem Jahre 1998

Expertenmeinung

Prognose für die Entwicklung von CPUs aus dem Jahre 1998

Expertenmeinung

Prognose für die Entwicklung von CPUs aus dem Jahre 1998

Realität

Quelle: http://www.maximumpc.com/article/home/history_dream_how_ultimate_pc_has_evolved_15_years

Hitzeentwicklung

Quelle: http://www.cadalyst.com/hardware/workstation-performance-tomorrow039s-possibilities-viewpoint-column-6351

Steigerung der FLOPS

$$ r < \frac{c}{1\frac{TByte}{s}} = \frac{299.792.458 \frac{m}{s}}{10^{12} \frac{Bit}{s}} = 0,3 \frac{mm}{Bit} $$

Motivation

Durch Steigerung der Taktrate / FLOPS eines einzelnen Prozessors ist keine nennenswerte Leistungssteigerung mehr zu erreichen, ohne große Nachteile in Kauf nehmen zu müssen.

<span class=‘fragment '

Aber: Im Programm vorhandene, unabhängige Rechenpakete können zeitgleich verarbeitet werden

Shared Memory Systeme

• Implizite Datenverteilung
• Implizite Kommunikation
• Es gibt verschiedene Typen von Shared-Memory Systemen
• Programmierung mit …
  • … OpenMP
  • … Java-Threads

Shared Memory Systeme

Auf den gemeinsamen Speicher kann von allen Threads eines Programms zugegriffen werden

SMP

Symmetric Multi Processing

ccNUMA

cache-coherent Non-Uniform Memory Architecture

Distributed Memory Systeme

• Explizite Datenverteilung
• Explizite Kommunikation
• Gute Skalierbarkeit
• Programmierung mit MPI

Speicherzugriff

Jeder Prozess hat seinen eigenen Speicherbereich

SMS vs. DMS

Speedup und Effizienz

Speedup und Effizienz sind Maßzahlen, um eine parallele Rechnung bewerten zu können

• Zeitverbrauch bei 1 CPU: $T(1)$

• Zeitverbrauch bei p CPUs: $T(p)$

• Speedup: $ S(p)= \frac{T(1)}{T(p)} $

  • Gibt an, wieviel schneller die parallele Berechnung ist
  • Idealfall: $ S(p) = p $

• Effizienz: $ E(p)= \frac{S(p)}{p} $

  • Gibt an, wie „gut“ die Implementierung der parallelen Berechnung ist
  • Idealfall: $ E(p)=1 $

Speedup und Effizienz

$$ T(1) = 6s, T(2) = 4s $$ $$ S(2) = \frac{6}{4} = 1,5 $$ $$ E(2) = \frac{1.5}{2} = 0,75 $$

Amdahl‘s Law

Beschreibt den Einfluss des seriellen Teils eines Programms auf dessen Skalierbarkeit

$$ s(p) = \frac{T(1)}{T(p)} = \frac{T(1)}{f \cdot T(1) + (1-f) \cdot \frac{T(1)}{p}} = \frac{1}{f+\frac{1-f}{p}} $$

• $f$: serieller Teil des Programms $(0 <= f<= 1)$
• $T(1)$: Zeitverbrauch mit 1 CPU
• $T(p)$: Zeitverbrauch mit p CPU
• $S(p)$: Speedup

Anmerkungen:

• Overhead wird nicht berücksichtigt
• Skalierbarkeit jedes Programms ist durch den seriellen Programmteil limitiert

Veranschaulichung

Wenn 80% (gemessen an der Programmlaufzeit) der Arbeit parallelisiert werden können und “nur” 20% immer seriell ausgeführt werden müssen, dann ergibt sich der Speedup wie folgt:

Amdahl‘s Law