Implementierung und Evaluation GPU beschleunigter B+-Bäume in C++/OpenCL
- Masterarbeit -
Description:
In the course of this work a B+-tree search algorithm for use on the Graphics Processing Unit (GPU) has been developed and implemented alongside a benchmarking harness (GPUBP). The algorithm’s performance with varying branching factors, search widths, batch- and tree sizes was evaluated. Initially the tree will be transferred once before multiple batches of more than 2 × 104 queries are performed for highest throughput. When on the GPU, the tree is considered static and no updates are performed. On the test platform the GPU memory bandwith was determined to be the limiting factor according to the results, when utilization was maximized. Additionally a Central Processing Unit (CPU) based search was implemented using multithreading and Group Prefetching (GP). A speedup of up to 17.7× could be measured comparing the GPU search using implicit B+-trees in relation to the custom CPU implementation. The measurements suggest that the CPU and GPU implementations using batched processing have similar latencies.
Anforderungen/Kenntnisse:
C++, OpenCL, B+-Tree
Bearbeitung:
F. Esch
Betreuung:
Prof. Dr. rer. nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5706
