GPU R‐Trie: Dictionary with ultra fast lookup

Krzysztof Kaczmarski , Albert Wolant

Abstract

R‐Trie dictionary is a multi‐way retrieval tree for arbitrary length binary keys. It is designed taking into account utilization of thousands of parallel vector threads, a fundamental technique of programming GPU processors. Dictionary bulk creation algorithm automatically scales to use as many threads as elements in the input batch, without any synchronization or page locking, exceeding 20·10^6 key insertions per second on a consumer class device. Bulk search procedure achieves 600·10^6 lookups per second in case of a Longest Prefix Match algorithm and 3·10^9 lookups per second in case of exact key matching. In this paper, we describe details of implementation, present results of run‐time experiments, and enumerate several open problems for future.
Author Krzysztof Kaczmarski (FMIS / DIPS)
Krzysztof Kaczmarski,,
- Department of Information Processing Systems
, Albert Wolant (FMIS)
Albert Wolant,,
- Faculty of Mathematics and Information Science
Journal seriesConcurrency and Computation-Practice & Experience, ISSN 1532-0626, (A 25 pkt)
Issue year2018
Vole5027
Pages1-16
Publication size in sheets0.75
Keywords in PolishCUDA, słownik, GPGPU, struktura indeksująca, drzewo wyszukiwania pozycyjnego
Keywords in EnglishCUDA, dictionary, GPGPU, index structure, radix search tree
ASJC Classification1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 1706 Computer Science Applications; 2614 Theoretical Computer Science; 1712 Software
Abstract in PolishSłownik R-Trie jest drzewem równoległego wyszukiwania kluczy binarnych o dowolnych długościach. Został zaprojektowany z dla równomiernego wykorzystania tysięcy wątków, podstawową techniką programowania procesorów GPU. Algorytm tworzenia słownika automatycznie skaluje się tak, aby wykorzystywał tyle wątków, ile elementów w partii wejściowej, bez synchronizacji lub blokowania stron, przekraczając liczbę 20 · 10 ^ 6 kluczy na sekundę na urządzeniu klasy konsumenckiej. Procedura wyszukiwania zbiorczego pozwala uzyskać 600 · 10 ^ 6 wyszukiwań na sekundę w przypadku algorytmu LPM (Longest Prefix Match) i 3 · 10 ^ 9 wyszukiwań na sekundę w przypadku dokładnego dopasowania klucza. W tym artykule opisujemy szczegóły implementacji, obecne wyniki eksperymentów oraz podajemy kilka interesujących problemów badawczych na przyszłość.
DOIDOI:10.1002/cpe.5027
URL https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.5027
Languageen angielski
Score (nominal)25
Score sourcejournalList
ScoreMinisterial score = 25.0, 08-11-2019, ArticleFromJournal
Publication indicators Scopus Citations = 1; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.851; WoS Impact Factor: 2018 = 1.167 (2) - 2018=1.148 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?