Premium
GPU R‐Trie: Dictionary with ultra fast lookup
Author(s) -
Kaczmarski Krzysztof,
Wolant Albert
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5027
Subject(s) - trie , computer science , prefix , parallel computing , key (lock) , tree (set theory) , matching (statistics) , binary tree , search tree , binary number , synchronization (alternating current) , binary search algorithm , algorithm , theoretical computer science , data structure , search algorithm , arithmetic , programming language , operating system , mathematics , combinatorics , computer network , philosophy , linguistics , statistics , channel (broadcasting)
Summary 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.