Algorithm Engineering „GPU Algorithmen“

Stefan Edelkamp

Übersicht

GPU Architektur und Effektivität CUDA Programmierung Matrixmultiplikation Lösen von linearen Gleichungssystemen Anwendung: Probabilistische Modellprüfung Experimente Breitensuche und Retrograde Analyse auf der

GPU

GPU Architektur (GTX 280 Chip)

Effektivität

CUDA

CUDA Programmierung

CUDA Programmierung

CUDA Programmierung

Hierarchischer Speicher

Lösen von linearen Gleichungssystemen

Darstellung dünner Matrizen

Adaption

Berechnung auf der GPU

Anwendung: Probabilistische Modellprüfung

Anwendung: Probabilistische Modellprüfung

Anwendung: Probabilistische Modellprüfung

Anwendung: Probabilistische Modellprüfung

Anwendung: Probabilistische Modellprüfung

Aufteilung der Matrix

Termination

Algorithmus

Experimente

Experimente

Experimente

Ergebnis

Experimente

Ergebnis

Einfache vs. Doppelte Präzision

Breitensuche auf der GPU

Perfektes Hashen auf der CPUExpansion und Ranking auf der GPU

PseudeCode

Kernel Funktionen

Solitär

Ergebnisse Solitär

Frösche und Kröten

Ergebnis Frösche und Kröten

Lösung: 115worst-case: 117Züge

Fuchs und Gänse

Ergebnis Fuchs und Hennen