Effizienteres Dokumenten-Clustering durch Grafikprozessoren
Status
Finished bachelor thesis
Student
- Marco Janc
Finished
2011
-
Formalia
- Targeted audience
-
- AI Bachelor
- Preconditions
-
- Erfahrung in der Programmierung mit Java (notwendig)
- Fähigkeit zum Lesen und Verstehen englischer wissenschaftlicher Publikationen
Task description
Sollen Dokumente nach inhaltlichen Gesichtspunkten gruppiert werden (Dokumenten-Clustering), so ist es erforderlich zu bestimmen, wie ähnlich sich die einzelnen Dokumente sind. Die Berechnung der Ähnlichkeitswerte für alle möglichen Dokumentpaare ist aufwendig, da eine große Anzahl von gleichartigen Rechenoperationen durchgeführt werden muss.
Aufgrund der hohen Rechen- aber geringen Steuerungsintensität des Verfahrens kann der Grafikkartenprozessor (GPU) dazu verwendet werden, die Bestimmung der Dokumentähnlichkeiten zu beschleunigen, da dieser im Vergleich zum Hauptprozessor (CPU) für diese spezielle Art von Berechnungen optimiert ist.
In dieser Arbeit sollen Dokumente unter Verwendung des Grafikkartenprozessors gruppiert werden. Dazu soll GPGPU (General Purpose Computation on Graphics Processing Unit) beispielsweise in der Form von CUDA (Compute Unified Device Architecture) verwendet werden. Eine anschließende Evaluation soll prüfen, wie stark sich der Clustering-Prozess durch die zusätzliche Verwendung des Grafikkartenprozessors beschleunigen lässt.
Die Bachelorarbeit umfasst somit folgender Schritte:
- Aufarbeitung der Literatur
- Entwurf eines Konzepts zum Dokumenten-Clustering mit GPGPU
- Auswahl und Einarbeitung in ein GPGPU-Rahmenwerk wie CUDA
- Implementierung eines Dokumenten-Clustering-Verfahrens mit GPGPU
- Evaluierung der Laufzeit
Ein Rechner mit einer geeigneten Grafikkarte wird bei Bedarf zur Verfügung gestellt.
Literature
-
- John D. Owens; David Luebke; Naga Govindaraju; Mark Harris; Jens Krüger; Aaron E. Lefohn; Timothy J. Purcell (2007).
- A Survey of General-Purpose Computation on Graphics Hardware. Computer Graphics Forum 26(1)
-
- Wu, Ren; Zhang, Bin; Hsu, Meichun (2009).
- Clustering billions of data points using GPUs. In: UCHPC-MAW '09: Proceedings of the combined workshops on UnConventional high performance computing workshop plus memory access workshop. ACM, New York, NY, USA.