Post on 05-Apr-2015
transcript
Diplomarbeit
Clustering mittels Grafikprozessor
Robert Noll
betreut von
Prof. Dr. Christian Böhm
Bianca Wackersreuther
Clustering mittels Grafikprozessor
Grafikkarten :
Computerspiele mit realistischer 3D-Grafik
viel Leistung, geringe Preise
rasante Weiterentwicklung
programmierbare Shader
Clustering mittels Grafikprozessor
Floating Point Operations Per Second
Clustering mittels Grafikprozessor
Memory Bandwidth
Clustering mittels Grafikprozessor
Massiv Parallel (hunderte von Threads)
Daten-Parallel, SIMD
simple Befehle, aber schnell
Clustering mittels Grafikprozessor
NVIDIA CUDA SDK:
Direkter Speicherzugriff (statt Texturen)
Scatter-Write (keine Adress-Beschränkung)
Atomare Operationen
Shared Memory Cache (Register)
erweiterte C Syntax
Emulator funktioniert ohne Grafik-Karte
Clustering mittels Grafikprozessor
K-Means Clustering
1 Thread pro Datenpunkt
GPU berechnet Zuordnung und Abstand
Clustering mittels Grafikprozessor
K-Means 8D k=1024
CPU
GPU
um Faktor 5-8 schneller
Clustering mittels Grafikprozessor
DBScan Clustering
density-based Clustering Nachbarn im ℰ Radius
Kernpunkt wenn ≥ minPts
Cluster ausbreiten
Clustering mittels Grafikprozessor
DBScan Variante auf GPU
mehrere Seeds parallel
Nachbar-Markierung
Kollisionen
Clustering mittels Grafikprozessor
GPU-DBScan Kollisionsbehandlung
Erkennung durch AtomicOps
old := AtomicMax(addr,new);
Eintrag in Connection Matrix
Clustering mittels Grafikprozessor
GPU-DBScan Connection Matrix
Finale Cluster ID erst bei Abschluss einer Kette
Tabelle mit Finalen Cluster ID's für Seeds
Connection Matrix (Bits) Finale Cluser ID Tabelle
Abschluss 1, neue ID
ID ausbreiten
neuer Seed
Clustering mittels Grafikprozessor
DBScan 8D minPts=4 ℰ=0.01
CPU
GPU
um Faktor 5-7 schneller
Clustering mittels Grafikprozessor
Zusammenfassung
viel Leistung, niedrige Preise
massiv Parallel
technische Einschränkungen
Vielen Dank für die Aufmerksamkeit !