GPU-beschleunigte Support-Vector Machines

Abstract

Data-Mining gewinnt immer mehr an Bedeutung, denn es stehen immer mehr Daten zur Verfügung. Um der stetig wachsenden Anzahl an Daten entgegenzuwirken, werden eine immer stärkere Hardware, bessere Algorithmen und optimierte Implementierungen benötigt. Es ist beispielsweise möglich mithilfe massiver Parallelität auf Grafikkarten die Rechenzeit zu verkürzen. Eine Möglichkeit Daten zu klassifizieren ist das überwachte maschinelle Lernen. Die Support-Vector Machine (SVM) ist eines dieser Verfahren. Sie erstellt ein Modell, worin die Trainingsdaten als Punkte im Raum interpretiert werden. Es werden diejenigen Datenpunkte gesucht, mit denen ein linearer Separator aufgestellt werden kann, der die Daten durch das breiteste Band voneinander trennt (large margin classifier). Anhand dieses gelernten Modells können dann neue Daten effizient klassifiziert werden. In dieser Arbeit wird eine Least Square Support Vektor Maschine implementiert. Bei der Least Squares Support Vektor Maschine werden nicht die wenigen Datenpunkte gesucht, die für die Separation wichtig sind (Support Vektoren), sondern bei allen Datenpunkten der proportionale Fehler bestimmt, und daraus die separierende Hyperebene abgeleitet. Die Least Squares Support Vektor Maschine wird mithilfe von NVIDIAs CUDA Parallel Programming Models für Grafikkarten implementiert und für NVIDIAs QUADRO GP100 optimiert. Dabei wurde explizit darauf geachtet, dass die GPU-Implementierung möglichst verzweigungsfrei ist. Außerdem wird die SoA Datenstruktur verwendet, und die Zugriffe über das Shared Memory optimiert. Damit konnte, bei ähnlicher Genauigkeit, auf der NVIDIAs QUADRO GP100 Grafikkarte, mit ca. 2,3 TFLOPS mit doppelter Genauigkeit, eine Laufzeitverbesserung um mehr als das 300-Fache gegenüber der gebräuchlichen CPU-Library for Support Vector Machines, LIBSVM, Implementierung gemessen werden.