Hardware-Accelerated Radix-Tree Based String Sorting for Big Data Applications

Christopher Blochwitz, Julian Wolff, Jan Moritz Joseph, Stefan Werner, Dennis Heinrich, Sven Groppe, Thilo Pionteck

Abstract

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.
Original languageEnglish
Title of host publicationArchitecture of Computing Systems - ARCS 2017
EditorsJens Knoop, Wolfgang Karl, Martin Schulz, Koji Inoue, Thilo Pionteck
Number of pages12
Volume10172
Place of PublicationCham
PublisherSpringer International Publishing
Publication date04.03.2017
Pages47-58
ISBN (Print)978-3-319-54998-9
ISBN (Electronic)978-3-319-54999-6
DOIs
Publication statusPublished - 04.03.2017
Event30th International Conference on Architecture of Computing Systems - Vienna, Austria
Duration: 03.04.201706.04.2017

Research Areas and Centers

  • Research Area: Intelligent Systems
  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)

DFG Research Classification Scheme

  • 409-04 Operating, Communication, Database and Distributed Systems

Fingerprint

Dive into the research topics of 'Hardware-Accelerated Radix-Tree Based String Sorting for Big Data Applications'. Together they form a unique fingerprint.

Cite this