Parallelizing Approximate Search on Adaptive Radix Trees

摘要

Efficient searching in a number of strings is a common task in computer science and radix-trees are often used as a compact storage for string saving. One variant is the Adaptive-Radix-Tree (ART). ART has adaptive node sizes for more compact and cache-friendly memory layout. Graphical Processing Units (GPUs) can be used as hardware accelerator for massively parallel tasks and in addition they use very fast memory. We propose a parallel approximate search in the ART on CPU and GPU to optimize the throughput of queries and speed up applications that depends on these algorithms. Thereby we use the edit distance to compare two search keys in the tree and select appropriate values. We use the CPU for experimental comparison with the GPU, which have several thousand cores and modern processors typically have four to several dozens cores, but theses cores and RAM are more flexible. We propose several variations of the CPU algorithm like fixed vs. dynamic memory layouts and pointer vs. pointer-less data structures. In our experimental evaluation with OpenCL on ROCm 3.0, AMDs platform for GPU-Enabled HPC and Ultrascale Computing, the speedup and throughput of the GPU implementation for the approximate search in comparison with the best CPU variant are in the maximum up to factor 4.16 depending on the size of the tree and batch size. The speedup between the best and the worst CPU algorithm is up to factor 11.67, depending on tree and batch size.