Hardware-Accelerated Radix-Tree Based String Sorting for Big Data Applications
详细信息 查看全文
- 关键词：Radix ; Tree ; Big data ; Dictionary generation ; Semantic web ; String sorting ; Field ; programmable gate array
- 刊名：Lecture Notes in Computer Science
- 出版年：2017
- 出版时间：2017
- 年：2017
- 卷：10172
- 期：1
- 页码：47-58
- 丛书名：Architecture of Computing Systems - ARCS 2017
- ISBN：978-3-319-54999-6
- 卷排序：10172
文摘
In this paper, a scalable hardware architecture for string sorting in the application field of Big Data is presented. Current hardware architectures focus on the acceleration of sorting small sets of data with a maximum string length. In contrast, we propose an FPGA-accelerated architecture based on Radix-Trees, which has the ability to sort large sets of strings without practical limitation of the string length. The Radix-Tree is parameterizable and so is the design, which enables the adaptation for application-specific properties, such as diversity of strings and size of the used alphabet. The scalable design has a hierarchical processing and memory architecture, which operate in parallel. Optimal parameters and configurations are evaluated by using a dataset of the Semantic Web, as an example of Big Data applications. The results are analyzed with a focus on throughput, memory requirement, and utilization. The hardware design is faster for all values of the radix parameter and achieves a maximum speed-up factor of 2.78 compared to a software system.