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 !