Distributed k-nearest neighbors using Locality Sensitive Hashing and SYCL

Abstract

More and more data is made available nowadays. This has the consequence that automatic or semi-automatic methods must be used to process these large data sets. One example of such a method is the classification. The nearest neighbor classifier, for example, assigns a class to a data point x based on its neighborhood. The naive approach to calculate nearest neighbors compares the data point x to all other data points in the data set. However, calculating the nearest neighbors for each data point using the naive approach has a quadratic complexity. This becomes more infeasible, the larger the data set grows. Therefore, approximate algorithms become more attractive. Such an algorithm is the Locality-Sensitive Hashing (LSH) algorithm, which uses hash tables together with locality-sensitive hash functions to reduce the data points that must be examined to calculate the nearest neighbors. In the course of this work sycl_lsh library has been developed. This library implements the LSH algorithm with two different locality-sensitive hash functions, random projections, and entropy-based hash functions. The implementation uses C++17 together with SYCL, which is an abstraction layer for OpenCL that allows targeting different hardware with a single source code. To support large data sets, the implementation utilizes multiple GPUs using MPI to enable the usage of both shared and distributed memory systems. The results include specific tests for all important runtime parameters showing their influence on the runtime, recall, and error ratio. Knowing the behavior of the LSH algorithm concerning the different parameters is essential to be able to tune the algorithm to achieve the desired results while meeting the runtime requirements. These tests have been conducted for both hash function types, which are further compared to each other. Besides, the obtained results show that the used approach can easily scale on multiple GPUs using both locality-sensitive hash function types, achieving a parallel speedup of up to 7.0 when utilizing eight GPUs. Furthermore, it is shown that the sycl_lsh library can be used with three different SYCL implementations, ComputeCpp, hipSYCL, and oneAPI, to target different hardware architectures without any significant performance differences.

In der heutigen Zeit stehen immer mehr Daten zur Verfügung. Daher müssen immer häufiger automatische oder semi-automatische Verfahren verwendet werden, um eine derartige Menge an Daten verarbeiten zu können. Ein Beispiel für ein solches Verfahren ist die Klassifizierung. Der Nächste-Nachbarn-Klassifikator zum Beispiel weist einem Datenpunkt x eine Klasse basierend auf den Klassen seiner Nachbarn zu. Der naive Ansatz, um die nächsten Nachbarn eines Punktes zu berechnen, vergleicht den Datenpunkt x mit allen anderen Datenpunkten. Bei der Berechnung der nächsten Nachbarn jeden Punktes mit Hilfe des naiven Ansatzes liegt eine quadratische Komplexität vor, was für große Datenmengen zu ineffizient ist. Um dies zu vermeiden, können approximative Verfahren verwendet werden. Ein solches Verfahren ist das Locality-Sensitive Hashing (LSH). Dieses Verfahren verwendet Hash-Tabellen zusammen mit lokalitätserhaltenden Hash-Funktionen, um die Anzahl an Datenpunkten, die bei der Suche der nächsten Nachbarn betrachtet werden müssen, zu reduzieren. Im Zuge dieser Masterarbeit wurde die sycl_lsh Bibliothek entwickelt. Diese Bibliothek implementiert den LSH Algorithmus mittels zweier verschiedener lokalitätserhaltender Hash-Funktionen, den random projections und den entropy-based Hash-Funktionen. Dabei verwendet die Implementierung C++17 zusammen mit SYCL, einer Abstraktionsschicht für OpenCL, die es erlaubt, mit nur einem Quellcode unterschiedliche Hardware ansprechen zu können. Um große Datenmengen verarbeiten zu können, unterstützt die Implementierung außerdem mehrere Grafikkarten in einem potentiell verteilten System unter Verwendung von MPI. Die Resultate umfassen, unter anderem, Tests für alle wichtigen Laufzeitparameter, um deren Auswirkungen auf die Laufzeit, Genauigkeit und Fehlerrate aufzuzeigen. Dieses Wissen um die Charakteristiken des LSH Algorithmus in Bezug auf die unterschiedlichen Parameter ist von großer Wichtigkeit, um die gewollten Resultate zu erreichen und gleichzeitig die Laufzeitanforderung aufrecht zu erhalten. Diese Tests wurden für beide Arten der lokalitätserhaltenden Hash-Funktionen durchgeführt, und deren Ergebnisse miteinander verglichen. Außerdem zeigten weitere Tests, dass der verwendete Parallelisierungsansatz auch unter Verwendung von mehreren Grafikkarten noch gut skaliert, unabhängig von dem verwendeten Typ der Hash-Funktionen. Dabei konnte eine Speedup von bis zu 7.0 unter Verwendung von acht GPUs erreicht werden. Des weiteren zeigen die Resultate, dass verschiedene SYCL Implementierungen verwendet werden können, um Code für unterschiedliche Hardware-Architekturen zu erstellen, ohne dabei signifikante Performance-Unterschiede hinnehmen zu müssen.