Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators
| Název práce v češtině: | Analýza a řešení výzev implementace vyhledávání k nejbližších sousedů pro GPU akcelerátory |
|---|---|
| Název v anglickém jazyce: | Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators |
| Klíčová slova: | kNN|top-k|parallel|GPU|CUDA |
| Klíčová slova anglicky: | kNN|top-k|parallel|GPU|CUDA |
| Akademický rok vypsání: | 2021/2022 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra distribuovaných a spolehlivých systémů (32-KDSS) |
| Vedoucí / školitel: | doc. RNDr. Martin Kruliš, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 01.11.2021 |
| Datum zadání: | 02.11.2021 |
| Datum potvrzení stud. oddělením: | 10.11.2021 |
| Datum a čas obhajoby: | 06.09.2023 09:00 |
| Datum odevzdání elektronické podoby: | 18.07.2023 |
| Datum odevzdání tištěné podoby: | 24.07.2023 |
| Datum proběhlé obhajoby: | 06.09.2023 |
| Oponenti: | RNDr. Jakub Yaghob, Ph.D. |
| Zásady pro vypracování |
| The k-nearest neighbor search (or the top-k problem) is well established search pattern known to database systems, but also integrated in many data processing and data analysis algorithms (k-means clustering, self-organized maps training, permutation-based indexing, etc.). Although its sequential implementation is trivial and typically based on basic data structures like regular heaps, its concurrent implementation brings many challenges. These challenges become even more profound in many-core parallel systems like GPU accelerators. There are many techniques that can be used to mitigate these challenges such as data privatization and parallel reduction and many research publications have address this topic; however, no publications proposed universal solution or complex performance overview of various problem configurations. The main objective of this thesis is to explore existing solutions for GPU-based top-k selection, perform their empirical evaluation, and propose universal solution for all possible scenarios. Furthermore, it is expected that additional performance optimizations may be discovered during the exploration. |
| Seznam odborné literatury |
| V. Garcia, E. Debreuve, and M. Barlaud. Fast k nearest neighbor search using gpu. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 1-6. IEEE, 2008.
M. Krulis, H. Osipyan, and S. Marchand-Maillet. Optimizing sorting and top-k selection steps in permutation based indexing on gpus. In East European Conference on Advances in Databases and Information Systems, pages 305{317. Springer, 2015. M. Krulis and M. Kratochvil. Detailed analysis and optimization of cuda k-means algorithm. In 49th International Conference on Parallel Processing - ICPP '20, New York, NY, USA, 2020. Association for Computing Machinery. S. Li and N. Amenta. Brute-force k-nearest neighbors search on the gpu. In International Conference on Similarity Search and Applications, pages 259-270. Springer, 2015. X. Tang, Z. Huang, D. Eyers, S. Mills, and M. Guo. Efficient selection algorithm for fast k-nn search on gpus. In 2015 IEEE International Parallel and Distributed Processing Symposium, pages 397-406. IEEE, 2015. |