Seminar GPU-Algorithmik & Parallel Patterns: Map/Reduce/Scan, Stencils, Histograms

Inhaltsverzeichnis

• Abstract
• Zielgruppe und Voraussetzungen
• Lernziele
• Inhalte und Module
• Praxisübungen
• Agenda

Abstract

Dieses Seminar behandelt GPU-Algorithmik unabhängig von einer konkreten API und übersetzt klassische Parallel-Patterns in GPU-taugliche Implementierungen. Inhalte sind Map/Reduce/Scan, Histogramme, Sortier- und Partitionierungsansätze, Stencil-Operatoren und Tiling-Strategien. Die Muster werden sowohl konzeptionell als auch in Code-Übungen erarbeitet und anschließend in CUDA oder OpenCL umgesetzt. Ergebnis ist eine belastbare Methodik zur Entwicklung performanter Kernel für neue Problemstellungen.

Zielgruppe und Voraussetzungen

• Zielgruppe: Entwicklung von numerischen, datenintensiven oder bild-/signalverarbeitenden Anwendungen
• Voraussetzungen: Grundkenntnisse in CUDA oder OpenCL, plus Basisverständnis Speicherhierarchie. Empfehlenswert: GPU-Computing Grundlagen: Architektur, Parallelität, Speicherhierarchie + (CUDA Programmierung Grundlagen: Kernels, Memory, Toolchain oder OpenCL Programmierung Grundlagen: Plattformmodell, Kernels, Runtime)

Lernziele

• Probleme als Parallel-Patterns formulieren
• Work-Efficiency vs Parallelism korrekt abwägen
• Reduktionen und Scans ohne Skalierungsfallen entwerfen
• Speicher- und Synchronisationskosten in Algorithmen berücksichtigen

Inhalte und Module

• Pattern-Überblick: Map, Gather/Scatter, Reduce, Scan, Sort/Partition
• Work-Efficiency: serieller Anteil, Synchronisationskomplexität, Atomics vs Privatization
• Tiling und Datenlokalität: Shared/Local Memory als Algorithmusbestandteil
• Stencils und Nachbarschaften: Halo-Handling, Boundaries, Mehrstufenpipelines
• Histogramme: Konflikte, Privatization, Merging-Strategien
• Numerische Aspekte: Stabilität, Determinismus, Reproduzierbarkeit (Einordnung)
• API-Abbildung: Pattern → Kernelstruktur (CUDA/OpenCL)

Praxisübungen

• Parallel Reduction: naive → blockweise → hierarchisch
• Prefix Sum (Scan) in vereinfachter Form
• Histogramm-Varianten: atomar vs privatisiert
• Stencil mit Tiling und Boundary-Handling
• Mini-Designreview: Patternwahl, Datenlayout, Synchronisation

Agenda

• Tag 1
  • Pattern-Framework und Reduktionen
  • Scan-Grundlagen und Anwendungsfälle
  • Übungen: Reduction + Scan light
• Tag 2
  • Histogramme und Konfliktstrategien
  • Stencils, Tiling, Boundaries
  • Übungen: Histogramm + Stencil Tiling