Informatik Master

• enthält mehrere Threads
• Threads haben untereinander einen shared memory
• eine Workgroup wird von einem Streaming Multiprozessor(SM und SMX) ausgeführt

• Warps sind gruppierte Threads ( 32 Threads pro Gruppe) erzeugt und verwaltet von Streaming Multiprozessor
• mehrere Warps pro Workgroup möglich
• Jeder Thread in einem Warp hat seinen eigenen Programmablauf
• Der Warp Scheduler:
  • teilt die Threads in Warps ein
  • findet den nächsten ausführbaren Warp

Ist ein If-Else Statement in einem Thread, können die Threads für die das If gilt und die für die das else gilt nicht zeitgleich abgearbeitet werden. Es entsteht ein Performanzverlust

Threads innerhalb eines Warps können zeitgleich immer nur einen gemeinsamen Befehl abarbeiten, d.h. verzweigen die Threads innerhalb eines Warps unterschiedlich (Warp Divergence) müssen alle Threads in alle Zweige hineingehen aber nur ihren Zweig ausführen --> Performenzverlust

 

Von langsam nach schnell:

1. Interleaved Adressing (divergent)
2. Interleaved Adressing (Shared Mem Bank Conflicts)
3. Sequential Adressing 
4. Warp Unrolling

Wenn mehere Threads auf dieselbe Speicherbank zu greifen wird der Zugriff serialsiert ( die Threads werden einzelen abgearbeitet). Dies führt zu Performanzverlust

1. Map:
   • One-to-One (Addition zweier Vektoren)
2. Transpose:
   • One-to-One (Transponieren einer Matrix Stichwort: row major order oder column major order)
3. Gather:
   • Many-to-One 
4. Stencil:
   • Several-to-One (Kernel bei der Bildverarbeitung)
5. Scatter - 1:
   • One-to-Many ( Kernel invertiert )
6. Scater - 2:
   • One-to-One , Ziel ist jedoch datenabhängig ( Hashtabellen)
7. Reduktion:
   • all-to-one
8. scan/sort:
   • all-to-all

Hillis/Steel :

Vorteil wenn wenige Elemente verarbeitet werden sollen

• work : n log(n)
• steps: log(n)

Blelloch:

Vorteil wenn viele Elemente verarbeitet werden sollen

upsweep:

• work:  O(n)
• steps: log(n)

downsweep:

• work: O(n)
• steps: log(n)

Eng-gekoppelte Systeme:

• besteht aus mehreren gekoppelten Prozessoren
• ein gemeinsamer Shared Memory

Lose-gekoppelte Systeme:

• besteht aus mehreren gekoppelten Prozessoren
• kein gemeinsamer Shared Memory

1. SISD: Entspricht dem klassischen von-Neumann-Rechner (Sequentielle Programmierung)
2. MISD: Keine gegenwärtige Architektur entspricht diesem Modell
3. SIMD: Rechner der 70er und 80er ; Vektorrechner ; GPU
4. MIMD: Multi Prozessor oder Multi-Core Rechner

byte = 8 bit

char = 16 bit

short = 16 bit 

int = 32 bit

float = 32 bit

long = 64 bit 

double = 64 bit

a) Von hoher Bitzahl nach niedriger Bitzahl. 

b) Summiert man die einzelnen Bits auf, muss das bisherige Ergebnis immer durch den nächsten Summanden teilbar sein. Ansonsten braucht man ein Padding

Beispiel: 

float a; byte b;

a+b= 8bit + (24 bit) + 32 bit = 8 Byte

b+a=32 bit + 8 bit = 5 Byte

a) Stack: 

• beinhaltet lokale Variablen und return Adressen
• Viel schnellere Zuweisung als auf Heap 
• Daten können ohne Pointer verwendet werden
• Datenstruktur wie Stack (Last in First out --> LIFO)
• Jeder Thread hat einen Stack

b) Heap:

• Variablenzuweisungen sind langsamer als auf dem Stack
• Pointer notwendig, new/malloc und am ende delete notwendig
• Verwendet man wenn man nicht weiß, wie viele Daten man zu Laufzeit benötigt oder wenn viele Daten zugewiesen werden müssen

Beide auf RAM

Abarbeitung von Threads hängt eng mit Abarbeitung von Prozessen zusammen!

a)

•  In Ausführung befindendes Programm
•  Programmcode und alle zur Ausführung nötigen Informationen
•  Kommunitkation:

Durch getrennte Adressräume ist für die Kommunikation zwischen verschiedenen Prozessen eine explizite Kommunikation über Sockets, MPI, ... notwendig

b) 

• Threadmodell ist eine Erweiterung des Prozessmodells
• Jeder Prozess besteht anstatt aus einem aus mehreren Berechnungsströmen --> Thread
•  Verschiedene Threads eines Prozesses teilen sich den Adressraum eines Prozesses --> gemeinsamer Adressraum
• Kommunikation:

Durch den gemeinsamen Adressraum erfolgt die Kommunikation zwischen Threads über den Zugriff auf geteilte Variablen

• Threads greifen gleichzeitig auf eine gemeinsamen Adressraum zu, da die Kommunikation implizizt über gemeinsame Variablen erfolgt
•  zeitkritische Abläufe = Racing Conditions 

 Zugriff auf gemeinsame Variablen koodinieren bzw synchronisieren

• Parallelität ist möglich, wenn Rechner mehrere Recheneinheiten (Prozessoren) hat.
• Echte Gleichzeitigkeit

• Wenn ein Rechner nur eine Recheneinheit hat, kann Gleichzeitigkeit nur simuliert werden, in dem mit hoher Frequenz kontinuirlich von einem Vorgang auf den nächsten umgeschaltet wird. 
• Nebenläufigkeit / Pseudoparallelität

2 oder mehrere Threads blockieren sich gegenseitig durch ihre Sperr- bzw. Synchronisationsmechanismen.

BSP:

T1 versucht zuerst S1 und dann S2 zu belegen, Nach Sperrung von S1 wird er unterbrochen (verliert Prozessor)

T2 versucht zuerst S2 und dann S1 zu belegen, Nach Sperrung von S1 wird er unterbrochen (verliert Prozessor)

->Nachdem T1 S1 und T2 S2 belegt hat, warten beide auf die Freigabe der fehlenden Sperre durch den jeweils anderen Thread

• statisch:
  • feste Anzahl an Threads wird zu Beginn des Programms erzeugt und am Ende beendet
• dynamisch:
  • Threads können zu jedem Zeitpunkt des Programms erzeugt und beendet werden
• allgmein:
  • Zu Beginn der Abarbeitung ist meist nur ein Thread aktiv, der das Hauptprogramm abarbeitet

1. Fork-Join:
   • Ein bereits existierender T1 spaltet mit einem Fork-Aufruf einen weiteren T2 ab.Bei einem Join-Aufruf des T1 wartet dieser bis T2 beendet ist
2. Parbegin und Parend:
   • Zwischen den Sprachkonstrukten Parbegin und Parend werden Anweisungen und Funktionen angegeben, die seperaten Threads zur Ausführung zugeordnet werden

1. Single Program, Multiple Data:
   • Feste Anzahl an Threads
   • wird zu Beginn gestartet,
   • wenden dasselbe Programm auf verschiedene Daten an
   • Matritzenrechnungen
2.  Manager-Worker:
   • Ein Manager-Thread, der oft dem Hauptprogramm entspricht
   • mehrere meist gleichartige Worker-Threads, die die eigentlichen Berechnungen durchführen
3.  Pipelining:
   • funktionalen Zerlegung einer Aufgabe
   • Threads arbeiten einen Anwendungsalgorithmus parallel  abb
   • trotz hoher Datenabhängigkeit
     • Daten werden zwischen Threads weitergereicht
4.  Taskpool:
   • feste Anzahl an Threads
   • existieren von Anfang bis Ende
   • Aus dem Taskpool werden Task entnommen und abgelegt
   • Programmende, wenn Pool leer und Threads ihr Tasks abgearbeitet haben
5. Producer-Consumer:
   • zwei verschiedene Threadgruppen
   • Produzenten-Threads erzeugen Daten
   • Konsumenten-Threads verarbeiten diese
   • Für die Übergabe der Daten wird ein Datenpuffer verwendet

• Ausführbereite Threads konkurrieren um die Ausführung auf einem freien Prozessor
• Zuordnung durch Scheduler der JVM
• Threads können Prioritäten zugeordnet werden
  • Genaues Scheduling der Threads ist trotzdem nicht gewährleistet

• Alle 18 Monate verdoppelt sich die Anzahl der Transistoren in einem Prozessor
  • Verdopplung der Integrationsdichte, also der Anzahl an Transistoren pro Flächeneinheit
• Früher:
  • steigende Anzahl an Transistoren wurde primär zur Steigerung der Taktrate genutzt
• Heute:
  • zusätzliche Transistoren werden genutzt, um mehrere Prozessorkerne in einem Prozessor zu vereinen
  • Jeder Prozessorkern stellt eine eigenständige Ausführungseinheit dar

Laufzeitverbesserung durch Parallelisierung ist begrenzt durch: 

• Anzahl der Rechenressourcen
• Sequientiell ausführbare Anteile des Algorithmus
  • maximal erreichbarer Speedup wird ausschließlich durch sequentiellen Anteil bestim

\(T = T_{s}+ T_{p}\)

SpeedUp:

Gibt an wie schnell ein Speicher transferiert werden kann

Einheit: Byte/s

• GPU
  • verwendet mehr Transistoren für Datenverarbeitung und Berechnungen
  • verwendet mehr Transistoren für Steuerung und Caches
  • hat viel mehr Kerne
  • ist Hardwarenäher
  • optimized for throughput (stuff/time)
  • benötigt viel Input
• CPU:
  • optimized for Latency (time) 
  • schnelle Abhandlung einer Aufgabe

• schneller Pufferspeicher
• Hauptspeicher ist sehr langsam
  • häufig zugegriffene Daten werden im Cache gespeichert
• Cache kann nicht alle Daten halten. Daher können sie verdrängt werden
• Nachladen von Daten dauert lange,
  • Geschwindigkeitseinbruch, da nicht weitergerechnet werden kann
• Cache Lines:
  • Es werden immer ganze Cache Lines in die Caches eingelesen bzw. zurückgeschrieben

Speicherbausteine sind unterschiedlich schnell. Sortiert von langsam nach schnell:

1. DRAM: Hauptspeicher
2. SRAM: Caches
3. Register

SIMT= Single Instroction Multiple Threads

• GPU verwendet SIMT
• Mehrere Threads führen jeweils den gleichen Befehl aus
• Befehle sind piplined innerhalb der Threads

• Bei Zugriff auf globalen Speicher wird immer die gesamte Busbreite ausgenutzt,
  • über jede Leitung werden Daten übertragen 
• Bei Übertragung auf compute Shader
  • benachbarte Threads können auf benachbarte Speicherbereiche zugreifen
    • coalesced access
  • Warp Sheduler kümmert sich darum, dass jeder Thread seine Daten bekommt und die Zugriffe auf globalen Speicher minimiert werden, indem immer alle Bits des Datenbusses genutzt werden

• Speicher begrenzt = memory-bound:
  • Algorithmus rechnet nur wenig
  • die meiste Zeit wird für Speicherzugriffe verwendet.
  • Maß ist die Speicherbandbreite
• Rechenbegrenzt = compute-bound:
  • Algorithmus lastet die arithmetischen Einheiten der Kerne vollständig aus
  • Maß ist GFLOPS/s